Computational complexity - Revision history

Fall2024 Wiki Team11 at 04:56, 16 December 2024

2024-12-16T04:56:03Z

← Older revision		Revision as of 00:56, 16 December 2024
Line 28:		Line 28:

	== Algorithm Discussion ==		== Algorithm Discussion ==
	~~Computational complexity~~ of an algorithm can be calculated by establishing a relationship between the length of the input and the number of steps (time complexity) or amount of space that algorithm takes (space complexity) to compute the problem. This relationship is usually represented as a function. The smaller the value of this function, the higher the efficiency of the algorithm. Function value also indicates the growth rate with respect to size of the input.		Complexity of an algorithm can be calculated by establishing a relationship between the length of the input and the number of steps (time complexity) or amount of space that algorithm takes (space complexity) to compute the problem. This relationship is usually represented as a function. The smaller the value of this function, the higher the efficiency of the algorithm. Function value also indicates the growth rate with respect to size of the input.

	==== Asymptotic Notations ====		==== Asymptotic Notations ====

Fall2024 Wiki Team11: minor edits

2024-12-16T04:54:34Z

minor edits

← Older revision		Revision as of 00:54, 16 December 2024
Line 28:		Line 28:

	== Algorithm Discussion ==		== Algorithm Discussion ==
	Computational complexity can be calculated ~~by algorithm analysis, and~~ by establishing a relationship between length of the ~~algorithm~~ input and the number of steps ~~it takes~~ (time complexity) or amount of space it takes (space complexity). This relationship is usually represented as a function. The smaller the value of this function, the higher the efficiency of the algorithm. Function value also indicates the growth rate with respect to size of the input.		Computational complexity of an algorithm can be calculated by establishing a relationship between the length of the input and the number of steps (time complexity) or amount of space that algorithm takes (space complexity) to compute the problem. This relationship is usually represented as a function. The smaller the value of this function, the higher the efficiency of the algorithm. Function value also indicates the growth rate with respect to size of the input.

	==== Asymptotic Notations ====		==== Asymptotic Notations ====

Fall2024 Wiki Team11: minor edits

2024-12-16T04:48:50Z

minor edits

← Older revision		Revision as of 00:48, 16 December 2024
Line 13:		Line 13:

	===== NP (Non-deterministic Polynomial Time) Class =====		===== NP (Non-deterministic Polynomial Time) Class =====
	If the solution of a problem can be verified in polynomial time, then the problem is considered as a Class NP problem. These problems require a solution ~~to be available which~~ can be verified, ~~however,~~ finding solution itself may take more than polynomial time.<ref name=":0" /><ref name=":3" />		If the solution of a problem can be verified in polynomial time, then the problem is considered as a Class NP problem. These problems require a solution that can be verified, but finding a solution itself may take more than polynomial time.<ref name=":0" /><ref name=":3" />

	===== NP-Hard Class =====		===== NP-Hard Class =====
Line 22:		Line 22:

	=== History ===		=== History ===
	The history of computational complexity can be traced back to the paper, ''On computable numbers with an application to the Entsheidungs problem<ref>A. M. Turing, “On computable numbers with an application to the Entsheidungs problem,” in ''The London Mathematical Society'', 1936. https://doi.org/10.1112/plms/s2-42.1.230</ref>,'' published in 1936 by A M Turing. In this paper, Turing introduced his famous Turing Machine and provided a convincing formalization of computable function. In following years, once the theory was established to determine which problem can and cannot be solved, questions regarding relative computational difficulty came up.<ref>S. A. Cook, “An overview of computational complexity,” ''Communications of the ACM,'' vol. 26, no. 6, pp. 400-408, 1983. https://doi.org/10.1145/358141.358144</ref> This can be considered as the birth of computational complexity. Rabin M O in his paper, ''Degree of difficulty of computing a function and partial ordering or recursive sets<ref>M. O. Rabin, “Degree of difificulty of computing a function and a partial ordering or recursive sets,” Hebrew University, Jerusalem, Israel, 1960.</ref>,'' in 1960 made an attempt to measure the amount of work inherent in computing a function along with defining the degree of difficulty of computing a function. Another influential paper that was published in 1965 by Hartmanis and Stearns, ''On the computational complexity of algorithms<ref>J. Hartmanis, R. Stearns, “On the Computational Complexity of Algorithms,” ''American Mathematical Society,'' 1965. http://dx.doi.org/10.2307/1994208</ref>'', discussed the method of categorizing problems according to how hard they are to compute. As part of this paper, a variety of theorems were established. It also provided a way to classify functions or recognition problems according to their computational complexity and laid out definitions of time complexity and space complexity. Paper by Alan Cobham in 1965, ''The intrinsic computational difficulty of functions<ref>A. Cobham, “The intrinsic computational difficulty of functions,” ''Logic, methodology and philosophy of science,'' pp. 24-30, 1965. https://doi.org/10.2307/2270886</ref>'', discussed the relative difficulty between addition and multiplication and characterised an important class of functions computable in time bounded by a polynomial in the length of input. These papers from Cobhem, Hartemanis and Rabin can be considered as the ~~founding papers~~ for the field of computational complexity. Manuel Blum in 1967, formulated axioms known as Blum Axioms, that specify desirable properties of complexity measures on the set of computation function. Field of computational complexity started to grow from 1971 onwards, with studies from Steven Cook, Leonid Levin and Richard Karp which expanded the study of problems belonging to class NP-Complete.		The history of computational complexity can be traced back to the paper, ''On computable numbers with an application to the Entsheidungs problem<ref>A. M. Turing, “On computable numbers with an application to the Entsheidungs problem,” in ''The London Mathematical Society'', 1936. https://doi.org/10.1112/plms/s2-42.1.230</ref>,'' published in 1936 by A M Turing. In this paper, Turing introduced his famous Turing Machine and provided a convincing formalization of computable function. In following years, once the theory was established to determine which problem can and cannot be solved, questions regarding relative computational difficulty came up.<ref>S. A. Cook, “An overview of computational complexity,” ''Communications of the ACM,'' vol. 26, no. 6, pp. 400-408, 1983. https://doi.org/10.1145/358141.358144</ref> This can be considered as the birth of computational complexity. Rabin M O in his paper, ''Degree of difficulty of computing a function and partial ordering or recursive sets<ref>M. O. Rabin, “Degree of difificulty of computing a function and a partial ordering or recursive sets,” Hebrew University, Jerusalem, Israel, 1960.</ref>,'' in 1960 made an attempt to measure the amount of work inherent in computing a function along with defining the degree of difficulty of computing a function. Another influential paper that was published in 1965 by Hartmanis and Stearns, ''On the computational complexity of algorithms<ref>J. Hartmanis, R. Stearns, “On the Computational Complexity of Algorithms,” ''American Mathematical Society,'' 1965. http://dx.doi.org/10.2307/1994208</ref>'', discussed the method of categorizing problems according to how hard they are to compute. As part of this paper, a variety of theorems were established. It also provided a way to classify functions or recognition problems according to their computational complexity and laid out definitions of time complexity and space complexity. Paper by Alan Cobham in 1965, ''The intrinsic computational difficulty of functions<ref>A. Cobham, “The intrinsic computational difficulty of functions,” ''Logic, methodology and philosophy of science,'' pp. 24-30, 1965. https://doi.org/10.2307/2270886</ref>'', discussed the relative difficulty between addition and multiplication and characterised an important class of functions computable in time bounded by a polynomial in the length of input. These papers from Cobhem, Hartemanis and Rabin can be considered as the foundation for the field of computational complexity. Manuel Blum in 1967, formulated axioms known as Blum Axioms, that specify desirable properties of complexity measures on the set of computation function. Field of computational complexity started to grow from 1971 onwards, with studies from Steven Cook, Leonid Levin and Richard Karp which expanded the study of problems belonging to class NP-Complete.

	=== Need for Computational Complexity ===		=== Need for Computational Complexity ===
Line 28:		Line 28:

	== Algorithm Discussion ==		== Algorithm Discussion ==
	Computational complexity can be calculated by algorithm analysis by establishing a relationship between length of the algorithm input and the number of steps it takes (time complexity) or amount of space it takes (space complexity). This relationship is usually represented as a function. The smaller the value of this function, the higher the efficiency of the algorithm. Function value also indicates the growth rate with respect to size of the input.		Computational complexity can be calculated by algorithm analysis, and by establishing a relationship between length of the algorithm input and the number of steps it takes (time complexity) or amount of space it takes (space complexity). This relationship is usually represented as a function. The smaller the value of this function, the higher the efficiency of the algorithm. Function value also indicates the growth rate with respect to size of the input.

	==== Asymptotic Notations ====		==== Asymptotic Notations ====
Line 36:		Line 36:
	'''''O - notation''''' represents the upper bound or the worst case, i.e. maximum time (or space) required for an algorithm. For functions ''f'' and ''t,''		'''''O - notation''''' represents the upper bound or the worst case, i.e. maximum time (or space) required for an algorithm. For functions ''f'' and ''t,''

	<math>f(n) = O(t(n))</math>		<math>f(n) = O(t(n))</math>,

	if <math>f(n) \leq c.t(n)</math> for all <math>n\geq d</math>, where ''c'' and ''d'' are positive integers<ref name=":1">Reza Zanjirani Farahani, Masoud Hekmatfar, Facility Location - Concepts, Models, Algorithms and Case Studies, Physica-Verlag, 2009. https://doi.org/10.2307/2270886</ref><ref name=":2">M. Sipser, Introduction To The Theory Of Computation, Thomson Course Technology, 2006.</ref>		if <math>f(n) \leq c.t(n)</math> for all <math>n\geq d</math>, where ''c'' and ''d'' are positive integers<ref name=":1">Reza Zanjirani Farahani, Masoud Hekmatfar, Facility Location - Concepts, Models, Algorithms and Case Studies, Physica-Verlag, 2009. https://doi.org/10.2307/2270886</ref><ref name=":2">M. Sipser, Introduction To The Theory Of Computation, Thomson Course Technology, 2006.</ref>
Line 43:		Line 43:
	'''Ω''' '''''- notation''''' represents lower bound or the best case, i.e. minimum time (or space) required for an algorithm. For functions, ''f'' and ''t,''		'''Ω''' '''''- notation''''' represents lower bound or the best case, i.e. minimum time (or space) required for an algorithm. For functions, ''f'' and ''t,''

	<math>f(n) = \Omega (t(n))</math>		<math>f(n) = \Omega (t(n))</math>,

	if <math>f(n)\geq c.t(n)</math> for all <math>n\geq d</math>, where ''c'' and ''d'' are positive integers<ref name=":1" /><ref name=":2" />		if <math>f(n)\geq c.t(n)</math> for all <math>n\geq d</math>, where ''c'' and ''d'' are positive integers<ref name=":1" /><ref name=":2" />
Line 168:		Line 168:

	==== Computer science and algorithm efficiency analysis ====		==== Computer science and algorithm efficiency analysis ====
	It helps in designing efficient algorithms and aids in software/ hardware selection. It enables comparison of multiple algorithms that can be used for solving a specific problem. Computational complexity helps in optimizing database queries and information retrieval processes.		It helps in designing efficient algorithms and aids in software/hardware selection. It enables comparison of multiple algorithms that can be used for solving a specific problem. Computational complexity helps in optimizing database queries and information retrieval processes.

	==== Quantum Computing ====		==== Quantum Computing ====
	Quantum computing is majorly used for cybersecurity, artificial intelligence, data management, data analytics and optimization. With the help of quantum complexity theory, quantum algorithms can be made exponentially efficient compared to classical algorithms. This enables businesses to solve problems which cannot be solved by conventional computing devices.		Quantum computing is majorly used for cybersecurity, artificial intelligence, data management, data analytics and optimization. With the help of quantum complexity theory, quantum algorithms can be made exponentially efficient compared to classical algorithms. This enables businesses to solve problems which cannot be solved by conventional computing devices.

	==== Game Theory ====		==== Game Theory<ref>T. Roughgarden, “Complexity Theory, Game Theory, and Economics: The Barbados Lectures,” ''Foundations and Trends® in Theoretical Computer Science,'' vol. 14, pp. 222-407, 2020. http://dx.doi.org/10.1561/0400000085</ref> ====
	Game theory deals with optimal decision making in any strategic setting. It is extensively used for analysing customer behaviour, market trend, develop effective business strategies, competitive product pricing etc. Computational complexity helps in defining the most efficient algorithm for approaching the game and to come up with best outcome while considering all the possible variations.		Game theory deals with optimal decision making in any strategic setting. It is extensively used for analysing customer behaviour, market trend, develop effective business strategies, competitive product pricing etc. Computational complexity helps in defining the most efficient algorithm for approaching the game and to come up with best outcome while considering all the possible variations.

Line 180:		Line 180:

	== Conclusion ==		== Conclusion ==
	Computational complexity provides a framework for analysing, comparing and selecting the most efficient algorithm and also enables the selection of best suited hardware and software combination. The algorithms or problems are categorised in classes P, NP, NP-Complete, NP-Hard and the worst-case complexity is represented using Big-O notation. Computational complexity has been evolving continuously for past few decades and remains a major area of study. Computational complexity is extensively used in the field of game theory, quantum mechanics, health system where the number of ~~computing is~~ huge and cannot be solved using conventional methods.		Computational complexity provides a framework for analysing, comparing and selecting the most efficient algorithm and also enables the selection of best suited hardware and software combination. The algorithms or problems are categorised in classes P, NP, NP-Complete, NP-Hard and the worst-case complexity is represented using Big-O notation. Computational complexity has been evolving continuously for past few decades and remains a major area of study. Computational complexity is extensively used in the field of game theory, quantum mechanics, health system where the number of computations are huge and cannot be solved using conventional methods.

	== Sources ==		== Sources ==
	<references responsive="0" />		<references responsive="0" />

Fall2024 Wiki Team11: Citations updated

2024-12-16T04:33:26Z

Citations updated

← Older revision		Revision as of 00:33, 16 December 2024
Line 10:		Line 10:

	===== P (Polynomial Time) Class =====		===== P (Polynomial Time) Class =====
	If a problem can be solved in polynomial time, then it is considered as a Class P problem. Problems in this class are efficiently solvable, however, the time required to solve grows polynomially with the size of input.<ref name=":0">R. Vanderbei, Linear Programming Foundations and Extensions, Springer, 2014.</ref> Linear programming problems are considered under P class.		If a problem can be solved in polynomial time, then it is considered as a Class P problem. Problems in this class are efficiently solvable, however, the time required to solve grows polynomially with the size of input.<ref name=":0">R. Vanderbei, Linear Programming Foundations and Extensions, Springer, 2014. https://doi.org/10.1057/palgrave.jors.2600987</ref><ref name=":3">Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach, New York: Cambridge University Press, 2009. http://dx.doi.org/10.1017/CBO9780511804090</ref> Linear programming problems are considered under P class.

	===== NP (Non-deterministic Polynomial Time) Class =====		===== NP (Non-deterministic Polynomial Time) Class =====
	If the solution of a problem can be verified in polynomial time, then the problem is considered as a Class NP problem. These problems require a solution to be available which can be verified, however, finding solution itself may take more than polynomial time.<ref name=":0" />		If the solution of a problem can be verified in polynomial time, then the problem is considered as a Class NP problem. These problems require a solution to be available which can be verified, however, finding solution itself may take more than polynomial time.<ref name=":0" /><ref name=":3" />

	===== NP-Hard Class =====		===== NP-Hard Class =====
	NP-Hard problems may or may not fall under NP Class. A problem H is NP-Hard if for every problem L in NP, there exists a polynomial time reduction from L to H.<ref name=":0" /> These are usually optimization problems.		NP-Hard problems may or may not fall under NP Class. A problem H is NP-Hard if for every problem L in NP, there exists a polynomial time reduction from L to H.<ref name=":0" /><ref name=":3" /> These are usually optimization problems.

	===== NP-Complete Class =====		===== NP-Complete Class =====
	NP-Complete problems are a subset of NP class. If all the problems in a NP can be reduced to problem H in polynomial time, then problem H is considered as NP-Complete.<ref name=":0" /> NP Complete problems are the hardest problems to solve. These are usually decision problems.		NP-Complete problems are a subset of NP class. If all the problems in a NP can be reduced to problem H in polynomial time, then problem H is considered as NP-Complete.<ref name=":0" /><ref name=":3" /> NP Complete problems are the hardest problems to solve. These are usually decision problems.

	=== History ===		=== History ===
	The history of computational complexity can be traced back to the paper, ''~~“On~~ computable numbers with an application to the Entsheidungs ~~problem”~~<ref>A. M. Turing, “On computable numbers with an application to the Entsheidungs problem,” in ''The London Mathematical Society'', 1936. https://doi.org/10.1112/plms/s2-42.1.230</ref>,'' published in 1936 by A M Turing. In this paper, Turing introduced his famous Turing Machine and provided a convincing formalization of computable function. In following years, once the theory was established to determine which problem can and cannot be solved, questions regarding relative computational difficulty came up.<ref>S. A. Cook, “An overview of computational complexity,” ''Communications of the ACM,'' vol. 26, no. 6, pp. 400-408, 1983. https://doi.org/10.1145/358141.358144</ref> This can be considered as the birth of computational complexity. Rabin M O in his paper, ''~~“Degree~~ of difficulty of computing a function and partial ordering or recursive ~~sets”~~<ref>M. O. Rabin, “Degree of difificulty of computing a function and a partial ordering or recursive sets,” Hebrew University, Jerusalem, Israel, 1960.</ref>,'' in 1960 made an attempt to measure the amount of work inherent in computing a function along with defining the degree of difficulty of computing a function. Another influential paper that was published in 1965 by Hartmanis and Stearns, “''On the computational complexity of algorithms~~''”''~~<ref>J. Hartmanis, R. Stearns, “On the Computational Complexity of Algorithms,” ''American Mathematical Society,'' 1965. http://dx.doi.org/10.2307/1994208</ref>'', discussed the method of categorizing problems according to how hard they are to compute. As part of this paper, a variety of theorems were established. It also provided a way to classify functions or recognition problems according to their computational complexity and laid out definitions of time complexity and space complexity. Paper by Alan Cobham in 1965, ''~~“The~~ intrinsic computational difficulty of ~~functions”~~<ref>A. Cobham, “The intrinsic computational difficulty of functions,” ''Logic, methodology and philosophy of science,'' pp. 24-30, 1965. https://doi.org/10.2307/2270886</ref>'', discussed the relative difficulty between addition and multiplication and characterised an important class of functions computable in time bounded by a polynomial in the length of input. These papers from Cobhem, Hartemanis and Rabin can be considered as the founding papers for the field of computational complexity. Manuel Blum in 1967, formulated axioms known as Blum Axioms, that specify desirable properties of complexity measures on the set of computation function. Field of computational complexity started to grow from 1971 onwards, with studies from Steven Cook, Leonid Levin and Richard Karp which expanded the study of problems belonging to class NP-Complete.		The history of computational complexity can be traced back to the paper, ''On computable numbers with an application to the Entsheidungs problem<ref>A. M. Turing, “On computable numbers with an application to the Entsheidungs problem,” in ''The London Mathematical Society'', 1936. https://doi.org/10.1112/plms/s2-42.1.230</ref>,'' published in 1936 by A M Turing. In this paper, Turing introduced his famous Turing Machine and provided a convincing formalization of computable function. In following years, once the theory was established to determine which problem can and cannot be solved, questions regarding relative computational difficulty came up.<ref>S. A. Cook, “An overview of computational complexity,” ''Communications of the ACM,'' vol. 26, no. 6, pp. 400-408, 1983. https://doi.org/10.1145/358141.358144</ref> This can be considered as the birth of computational complexity. Rabin M O in his paper, ''Degree of difficulty of computing a function and partial ordering or recursive sets<ref>M. O. Rabin, “Degree of difificulty of computing a function and a partial ordering or recursive sets,” Hebrew University, Jerusalem, Israel, 1960.</ref>,'' in 1960 made an attempt to measure the amount of work inherent in computing a function along with defining the degree of difficulty of computing a function. Another influential paper that was published in 1965 by Hartmanis and Stearns, ''On the computational complexity of algorithms<ref>J. Hartmanis, R. Stearns, “On the Computational Complexity of Algorithms,” ''American Mathematical Society,'' 1965. http://dx.doi.org/10.2307/1994208</ref>'', discussed the method of categorizing problems according to how hard they are to compute. As part of this paper, a variety of theorems were established. It also provided a way to classify functions or recognition problems according to their computational complexity and laid out definitions of time complexity and space complexity. Paper by Alan Cobham in 1965, ''The intrinsic computational difficulty of functions<ref>A. Cobham, “The intrinsic computational difficulty of functions,” ''Logic, methodology and philosophy of science,'' pp. 24-30, 1965. https://doi.org/10.2307/2270886</ref>'', discussed the relative difficulty between addition and multiplication and characterised an important class of functions computable in time bounded by a polynomial in the length of input. These papers from Cobhem, Hartemanis and Rabin can be considered as the founding papers for the field of computational complexity. Manuel Blum in 1967, formulated axioms known as Blum Axioms, that specify desirable properties of complexity measures on the set of computation function. Field of computational complexity started to grow from 1971 onwards, with studies from Steven Cook, Leonid Levin and Richard Karp which expanded the study of problems belonging to class NP-Complete.

	=== Need for Computational Complexity ===		=== Need for Computational Complexity ===

Fall2024 Wiki Team11: doi links added to sources

2024-12-16T00:37:04Z

doi links added to sources

← Older revision		Revision as of 20:37, 15 December 2024
Line 22:		Line 22:

	=== History ===		=== History ===
	The history of computational complexity can be traced back to the paper, ''“On computable numbers with an application to the Entsheidungs problem”<ref>A. M. Turing, “On computable numbers with an application to the Entsheidungs problem,” in ''The London Mathematical Society'', 1936. ~~<nowiki>~~https://doi.org/10.1112/plms/s2-42.1.230~~</nowiki>~~</ref>,'' published in 1936 by A M Turing. In this paper, Turing introduced his famous Turing Machine and provided a convincing formalization of computable function. In following years, once the theory was established to determine which problem can and cannot be solved, questions regarding relative computational difficulty came up.<ref>S. A. Cook, “An overview of computational complexity,” ''Communications of the ACM,'' vol. 26, no. 6, pp. 400-408, 1983.</ref> This can be considered as the birth of computational complexity. Rabin M O in his paper, ''“Degree of difficulty of computing a function and partial ordering or recursive sets”<ref>M. O. Rabin, “Degree of difificulty of computing a function and a partial ordering or recursive sets,” Hebrew University, Jerusalem, Israel, 1960.</ref>,'' in 1960 made an attempt to measure the amount of work inherent in computing a function along with defining the degree of difficulty of computing a function. Another influential paper that was published in 1965 by Hartmanis and Stearns, “''On the computational complexity of algorithms''”''<ref>J. Hartmanis, R. Stearns, “On the Computational Complexity of Algorithms,” ''American Mathematical Society,'' 1965.</ref>'', discussed the method of categorizing problems according to how hard they are to compute. As part of this paper, a variety of theorems were established. It also provided a way to classify functions or recognition problems according to their computational complexity and laid out definitions of time complexity and space complexity. Paper by Alan Cobham in 1965, ''“The intrinsic computational difficulty of functions”<ref>A. Cobham, “The intrinsic computational difficulty of functions,” ''Logic, methodology and philosophy of science,'' pp. 24-30, 1965.</ref>'', discussed the relative difficulty between addition and multiplication and characterised an important class of functions computable in time bounded by a polynomial in the length of input. These papers from Cobhem, Hartemanis and Rabin can be considered as the founding papers for the field of computational complexity. Manuel Blum in 1967, formulated axioms known as Blum Axioms, that specify desirable properties of complexity measures on the set of computation function. Field of computational complexity started to grow from 1971 onwards, with studies from Steven Cook, Leonid Levin and Richard Karp which expanded the study of problems belonging to class NP-Complete.		The history of computational complexity can be traced back to the paper, ''“On computable numbers with an application to the Entsheidungs problem”<ref>A. M. Turing, “On computable numbers with an application to the Entsheidungs problem,” in ''The London Mathematical Society'', 1936. https://doi.org/10.1112/plms/s2-42.1.230</ref>,'' published in 1936 by A M Turing. In this paper, Turing introduced his famous Turing Machine and provided a convincing formalization of computable function. In following years, once the theory was established to determine which problem can and cannot be solved, questions regarding relative computational difficulty came up.<ref>S. A. Cook, “An overview of computational complexity,” ''Communications of the ACM,'' vol. 26, no. 6, pp. 400-408, 1983. https://doi.org/10.1145/358141.358144</ref> This can be considered as the birth of computational complexity. Rabin M O in his paper, ''“Degree of difficulty of computing a function and partial ordering or recursive sets”<ref>M. O. Rabin, “Degree of difificulty of computing a function and a partial ordering or recursive sets,” Hebrew University, Jerusalem, Israel, 1960.</ref>,'' in 1960 made an attempt to measure the amount of work inherent in computing a function along with defining the degree of difficulty of computing a function. Another influential paper that was published in 1965 by Hartmanis and Stearns, “''On the computational complexity of algorithms''”''<ref>J. Hartmanis, R. Stearns, “On the Computational Complexity of Algorithms,” ''American Mathematical Society,'' 1965. http://dx.doi.org/10.2307/1994208</ref>'', discussed the method of categorizing problems according to how hard they are to compute. As part of this paper, a variety of theorems were established. It also provided a way to classify functions or recognition problems according to their computational complexity and laid out definitions of time complexity and space complexity. Paper by Alan Cobham in 1965, ''“The intrinsic computational difficulty of functions”<ref>A. Cobham, “The intrinsic computational difficulty of functions,” ''Logic, methodology and philosophy of science,'' pp. 24-30, 1965. https://doi.org/10.2307/2270886</ref>'', discussed the relative difficulty between addition and multiplication and characterised an important class of functions computable in time bounded by a polynomial in the length of input. These papers from Cobhem, Hartemanis and Rabin can be considered as the founding papers for the field of computational complexity. Manuel Blum in 1967, formulated axioms known as Blum Axioms, that specify desirable properties of complexity measures on the set of computation function. Field of computational complexity started to grow from 1971 onwards, with studies from Steven Cook, Leonid Levin and Richard Karp which expanded the study of problems belonging to class NP-Complete.

	=== Need for Computational Complexity ===		=== Need for Computational Complexity ===
Line 38:		Line 38:
	<math>f(n) = O(t(n))</math>		<math>f(n) = O(t(n))</math>

	if <math>f(n) \leq c.t(n)</math> for all <math>n\geq d</math>, where ''c'' and ''d'' are positive integers<ref name=":1">Reza Zanjirani Farahani, Masoud Hekmatfar, Facility Location - Concepts, Models, Algorithms and Case Studies, Physica-Verlag, 2009.</ref><ref name=":2">M. Sipser, Introduction To The Theory Of Computation, Thomson Course Technology, 2006.</ref>		if <math>f(n) \leq c.t(n)</math> for all <math>n\geq d</math>, where ''c'' and ''d'' are positive integers<ref name=":1">Reza Zanjirani Farahani, Masoud Hekmatfar, Facility Location - Concepts, Models, Algorithms and Case Studies, Physica-Verlag, 2009. https://doi.org/10.2307/2270886</ref><ref name=":2">M. Sipser, Introduction To The Theory Of Computation, Thomson Course Technology, 2006.</ref>

	===== Big-Omega Notation =====		===== Big-Omega Notation =====
Line 176:		Line 176:
	Game theory deals with optimal decision making in any strategic setting. It is extensively used for analysing customer behaviour, market trend, develop effective business strategies, competitive product pricing etc. Computational complexity helps in defining the most efficient algorithm for approaching the game and to come up with best outcome while considering all the possible variations.		Game theory deals with optimal decision making in any strategic setting. It is extensively used for analysing customer behaviour, market trend, develop effective business strategies, competitive product pricing etc. Computational complexity helps in defining the most efficient algorithm for approaching the game and to come up with best outcome while considering all the possible variations.

	==== Healthcare system<ref>Thomas G. Kannampallil, Guido F. Schauer, Trevor Cohen, Vimla L. Patel, “Considering complexity in healthcare systems,” ''Journal of Biomedical Informatics,'' vol. 44, no. 6, pp. 943-947, 2011.</ref> ====		==== Healthcare system<ref>Thomas G. Kannampallil, Guido F. Schauer, Trevor Cohen, Vimla L. Patel, “Considering complexity in healthcare systems,” ''Journal of Biomedical Informatics,'' vol. 44, no. 6, pp. 943-947, 2011. https://doi.org/10.2307/2270886</ref> ====
	Various aspects of healthcare system such as patient management, continuity of patient care, nursing etc requires efficient decision-making processes. These complex tasks are broken down into fairly smaller and manageable tasks using computational models while giving due consideration to interrelatedness of systems.		Various aspects of healthcare system such as patient management, continuity of patient care, nursing etc requires efficient decision-making processes. These complex tasks are broken down into fairly smaller and manageable tasks using computational models while giving due consideration to interrelatedness of systems.

Fall2024 Wiki Team11 at 00:24, 16 December 2024

2024-12-16T00:24:12Z

← Older revision		Revision as of 20:24, 15 December 2024
Line 10:		Line 10:

	===== P (Polynomial Time) Class =====		===== P (Polynomial Time) Class =====
	If a problem can be solved in polynomial time, then it is considered as a Class P problem. Problems in this class are efficiently solvable, however, the time required to solve grows polynomially with the size of input<ref name=":0">R. Vanderbei, Linear Programming Foundations and Extensions, Springer, 2014.</ref>. Linear programming problems are considered under P class.		If a problem can be solved in polynomial time, then it is considered as a Class P problem. Problems in this class are efficiently solvable, however, the time required to solve grows polynomially with the size of input.<ref name=":0">R. Vanderbei, Linear Programming Foundations and Extensions, Springer, 2014.</ref> Linear programming problems are considered under P class.

	===== NP (Non-deterministic Polynomial Time) Class =====		===== NP (Non-deterministic Polynomial Time) Class =====
	If the solution of a problem can be verified in polynomial time, then the problem is considered as a Class NP problem. These problems require a solution to be available which can be verified, however finding solution itself may take more than polynomial time<ref name=":0" />.		If the solution of a problem can be verified in polynomial time, then the problem is considered as a Class NP problem. These problems require a solution to be available which can be verified, however, finding solution itself may take more than polynomial time.<ref name=":0" />

	===== NP-Hard Class =====		===== NP-Hard Class =====
	NP-Hard problems may or may not fall under NP Class. A problem H is NP-Hard if for every problem L in NP, there exists a polynomial time reduction from L to H<ref name=":0" />. These are usually optimization problems.		NP-Hard problems may or may not fall under NP Class. A problem H is NP-Hard if for every problem L in NP, there exists a polynomial time reduction from L to H.<ref name=":0" /> These are usually optimization problems.

	===== NP-Complete Class =====		===== NP-Complete Class =====
	NP-Complete problems are a subset of NP class. If all the problems in a NP can be reduced to problem H in polynomial time, then problem H is considered as NP-Complete<ref name=":0" />. NP Complete problems are the hardest problems to solve. These are usually decision problems.		NP-Complete problems are a subset of NP class. If all the problems in a NP can be reduced to problem H in polynomial time, then problem H is considered as NP-Complete.<ref name=":0" /> NP Complete problems are the hardest problems to solve. These are usually decision problems.

	=== History ===		=== History ===
	The history of computational complexity can be traced back to the paper, ''“On computable numbers with an application to the Entsheidungs problem”<ref>A. M. Turing, “On computable numbers with an application to the Entsheidungs problem,” in ''The London Mathematical Society'', 1936.</ref>,'' published in 1936 by A M Turing. In this paper, Turing introduced his famous Turing Machine and provided a convincing formalization of computable function. In following years, once the theory was established to determine which problem can and cannot be solved, questions regarding relative computational difficulty came up<ref>S. A. Cook, “An overview of computational complexity,” ''Communications of the ACM,'' vol. 26, no. 6, pp. 400-408, 1983.</ref>. This can be considered as the birth of computational complexity. Rabin M O in his paper, ''“Degree of difficulty of computing a function and partial ordering or recursive sets”<ref>M. O. Rabin, “Degree of difificulty of computing a function and a partial ordering or recursive sets,” Hebrew University, Jerusalem, Israel, 1960.</ref>,'' in 1960 made an attempt to measure the amount of work inherent in computing a function along with defining the degree of difficulty of computing a function. Another influential paper that was published in 1965 by Hartmanis and Stearns, “''On the computational complexity of algorithms''”<ref>J. Hartmanis, R. Stearns, “On the Computational Complexity of Algorithms,” ''American Mathematical Society,'' 1965.</ref>, discussed the method of categorizing problems according to how hard they are to compute. As part of this paper, a variety of theorems were established. It also provided a way to classify functions or recognition problems according to their computational complexity and laid out definitions of time complexity and space complexity. Paper by Alan Cobham in 1965, ''“The intrinsic computational difficulty of functions”''<ref>A. Cobham, “The intrinsic computational difficulty of functions,” ''Logic, methodology and philosophy of science,'' pp. 24-30, 1965.</ref>, discussed the relative difficulty between addition and multiplication and characterised an important class of functions computable in time bounded by a polynomial in the length of input. These papers from Cobhem, Hartemanis and Rabin can be considered as the founding papers for the field of computational complexity. Manuel Blum in 1967, formulated axioms known as Blum Axioms, that specify desirable properties of complexity measures on the set of computation function. Field of computational complexity started to grow from 1971 onwards, with studies from Steven Cook, Leonid Levin and Richard Karp which expanded the study of problems belonging to class NP-Complete.		The history of computational complexity can be traced back to the paper, ''“On computable numbers with an application to the Entsheidungs problem”<ref>A. M. Turing, “On computable numbers with an application to the Entsheidungs problem,” in ''The London Mathematical Society'', 1936. <nowiki>https://doi.org/10.1112/plms/s2-42.1.230</nowiki></ref>,'' published in 1936 by A M Turing. In this paper, Turing introduced his famous Turing Machine and provided a convincing formalization of computable function. In following years, once the theory was established to determine which problem can and cannot be solved, questions regarding relative computational difficulty came up.<ref>S. A. Cook, “An overview of computational complexity,” ''Communications of the ACM,'' vol. 26, no. 6, pp. 400-408, 1983.</ref> This can be considered as the birth of computational complexity. Rabin M O in his paper, ''“Degree of difficulty of computing a function and partial ordering or recursive sets”<ref>M. O. Rabin, “Degree of difificulty of computing a function and a partial ordering or recursive sets,” Hebrew University, Jerusalem, Israel, 1960.</ref>,'' in 1960 made an attempt to measure the amount of work inherent in computing a function along with defining the degree of difficulty of computing a function. Another influential paper that was published in 1965 by Hartmanis and Stearns, “''On the computational complexity of algorithms''”''<ref>J. Hartmanis, R. Stearns, “On the Computational Complexity of Algorithms,” ''American Mathematical Society,'' 1965.</ref>'', discussed the method of categorizing problems according to how hard they are to compute. As part of this paper, a variety of theorems were established. It also provided a way to classify functions or recognition problems according to their computational complexity and laid out definitions of time complexity and space complexity. Paper by Alan Cobham in 1965, ''“The intrinsic computational difficulty of functions”<ref>A. Cobham, “The intrinsic computational difficulty of functions,” ''Logic, methodology and philosophy of science,'' pp. 24-30, 1965.</ref>'', discussed the relative difficulty between addition and multiplication and characterised an important class of functions computable in time bounded by a polynomial in the length of input. These papers from Cobhem, Hartemanis and Rabin can be considered as the founding papers for the field of computational complexity. Manuel Blum in 1967, formulated axioms known as Blum Axioms, that specify desirable properties of complexity measures on the set of computation function. Field of computational complexity started to grow from 1971 onwards, with studies from Steven Cook, Leonid Levin and Richard Karp which expanded the study of problems belonging to class NP-Complete.

	=== Need for Computational Complexity ===		=== Need for Computational Complexity ===

Fall2024 Wiki Team11 at 02:47, 15 December 2024

2024-12-15T02:47:49Z

← Older revision		Revision as of 22:47, 14 December 2024
Line 10:		Line 10:

	===== P (Polynomial Time) Class =====		===== P (Polynomial Time) Class =====
	If a problem can be solved in polynomial time, then it is considered as a Class P problem. Problems in this class are efficiently solvable, however, the time required to solve grows polynomially with the size of input. Linear programming problems are considered under P class. ~~[1]~~		If a problem can be solved in polynomial time, then it is considered as a Class P problem. Problems in this class are efficiently solvable, however, the time required to solve grows polynomially with the size of input<ref name=":0">R. Vanderbei, Linear Programming Foundations and Extensions, Springer, 2014.</ref>. Linear programming problems are considered under P class.

	===== NP (Non-deterministic Polynomial Time) Class =====		===== NP (Non-deterministic Polynomial Time) Class =====
	If the solution of a problem can be verified in polynomial time, then the problem is considered as a Class NP problem. These problems require a solution to be available which can be verified, however finding solution itself may take more than polynomial time. ~~[1]~~		If the solution of a problem can be verified in polynomial time, then the problem is considered as a Class NP problem. These problems require a solution to be available which can be verified, however finding solution itself may take more than polynomial time<ref name=":0" />.

	===== NP-Hard Class =====		===== NP-Hard Class =====
	NP-Hard problems may or may not fall under NP Class. A problem H is NP-Hard if for every problem L in NP, there exists a polynomial time reduction from L to H. These are usually optimization problems. ~~[1]~~		NP-Hard problems may or may not fall under NP Class. A problem H is NP-Hard if for every problem L in NP, there exists a polynomial time reduction from L to H<ref name=":0" />. These are usually optimization problems.

	===== NP-Complete Class =====		===== NP-Complete Class =====
	NP-Complete problems are a subset of NP class. If all the problems in a NP can be reduced to problem H in polynomial time, then problem H is considered as NP-Complete. NP Complete problems are the hardest problems to solve. These are usually decision problems. ~~[1]~~		NP-Complete problems are a subset of NP class. If all the problems in a NP can be reduced to problem H in polynomial time, then problem H is considered as NP-Complete<ref name=":0" />. NP Complete problems are the hardest problems to solve. These are usually decision problems.

	=== History ===		=== History ===
	The history of computational complexity can be traced back to the paper, ''“On computable numbers with an application to the Entsheidungs problem”,'' published in 1936 by A M Turing. In this paper, Turing introduced his famous Turing Machine and provided a convincing formalization of computable function. In following years, once the theory was established to determine which problem can and cannot be solved, questions regarding relative computational difficulty came up ~~[3]~~. This can be considered as the birth of computational complexity. Rabin M O in his paper, ''“Degree of difficulty of computing a function and partial ordering or recursive sets”,'' in 1960 made an attempt to measure the amount of work inherent in computing a function along with defining the degree of difficulty of computing a function ~~[4]~~. Another influential paper that was published in 1965 by Hartmanis and Stearns, “''On the computational complexity of algorithms''”, discussed the method of categorizing problems according to how hard they are to compute. As part of this paper, a variety of theorems were established. It also provided a way to classify functions or recognition problems according to their computational complexity and laid out definitions of time complexity and space complexity ~~[5]~~. Paper by Alan Cobham in 1965, ''“The intrinsic computational difficulty of ~~a function”~~'', discussed the relative difficulty between addition and multiplication and characterised an important class of functions computable in time bounded by a polynomial in the length of input ~~[6]~~. These papers from Cobhem, Hartemanis and Rabin can be considered as the founding papers for the field of computational complexity. Manuel Blum in 1967, formulated axioms known as Blum Axioms, that specify desirable properties of complexity measures on the set of computation function. Field of computational complexity started to grow from 1971 onwards, with studies from Steven Cook, Leonid Levin and Richard Karp which expanded the study of problems belonging to class NP-Complete.		The history of computational complexity can be traced back to the paper, ''“On computable numbers with an application to the Entsheidungs problem”<ref>A. M. Turing, “On computable numbers with an application to the Entsheidungs problem,” in ''The London Mathematical Society'', 1936.</ref>,'' published in 1936 by A M Turing. In this paper, Turing introduced his famous Turing Machine and provided a convincing formalization of computable function. In following years, once the theory was established to determine which problem can and cannot be solved, questions regarding relative computational difficulty came up<ref>S. A. Cook, “An overview of computational complexity,” ''Communications of the ACM,'' vol. 26, no. 6, pp. 400-408, 1983.</ref>. This can be considered as the birth of computational complexity. Rabin M O in his paper, ''“Degree of difficulty of computing a function and partial ordering or recursive sets”<ref>M. O. Rabin, “Degree of difificulty of computing a function and a partial ordering or recursive sets,” Hebrew University, Jerusalem, Israel, 1960.</ref>,'' in 1960 made an attempt to measure the amount of work inherent in computing a function along with defining the degree of difficulty of computing a function. Another influential paper that was published in 1965 by Hartmanis and Stearns, “''On the computational complexity of algorithms''”<ref>J. Hartmanis, R. Stearns, “On the Computational Complexity of Algorithms,” ''American Mathematical Society,'' 1965.</ref>, discussed the method of categorizing problems according to how hard they are to compute. As part of this paper, a variety of theorems were established. It also provided a way to classify functions or recognition problems according to their computational complexity and laid out definitions of time complexity and space complexity. Paper by Alan Cobham in 1965, ''“The intrinsic computational difficulty of functions”''<ref>A. Cobham, “The intrinsic computational difficulty of functions,” ''Logic, methodology and philosophy of science,'' pp. 24-30, 1965.</ref>, discussed the relative difficulty between addition and multiplication and characterised an important class of functions computable in time bounded by a polynomial in the length of input. These papers from Cobhem, Hartemanis and Rabin can be considered as the founding papers for the field of computational complexity. Manuel Blum in 1967, formulated axioms known as Blum Axioms, that specify desirable properties of complexity measures on the set of computation function. Field of computational complexity started to grow from 1971 onwards, with studies from Steven Cook, Leonid Levin and Richard Karp which expanded the study of problems belonging to class NP-Complete.

	=== Need for Computational Complexity ===		=== Need for Computational Complexity ===
Line 38:		Line 38:
	<math>f(n) = O(t(n))</math>		<math>f(n) = O(t(n))</math>

	if <math>f(n) \leq c.t(n)</math> for all <math>n\geq d</math>, where ''c'' and ''d'' are positive integers ~~''[7] [8]''~~		if <math>f(n) \leq c.t(n)</math> for all <math>n\geq d</math>, where ''c'' and ''d'' are positive integers<ref name=":1">Reza Zanjirani Farahani, Masoud Hekmatfar, Facility Location - Concepts, Models, Algorithms and Case Studies, Physica-Verlag, 2009.</ref><ref name=":2">M. Sipser, Introduction To The Theory Of Computation, Thomson Course Technology, 2006.</ref>

	===== Big-Omega Notation =====		===== Big-Omega Notation =====
Line 45:		Line 45:
	<math>f(n) = \Omega (t(n))</math>		<math>f(n) = \Omega (t(n))</math>

	if <math>f(n)\geq c.t(n)</math> for all <math>n\geq d</math>, where ''c'' and ''d'' are positive integers ~~''[7] [8]''~~		if <math>f(n)\geq c.t(n)</math> for all <math>n\geq d</math>, where ''c'' and ''d'' are positive integers<ref name=":1" /><ref name=":2" />

	===== Big-Theta Notation =====		===== Big-Theta Notation =====
Line 52:		Line 52:
	<math>f(n)=\Theta(t(n))</math>,		<math>f(n)=\Theta(t(n))</math>,

	if <math>c_1.t(n)\leq f(n) \leq c_2.t(n)</math> for all <math>n\geq d</math>, where ''c<sub>1</sub>'', ''c<sub>2</sub>'' and ''d'' are positive integers ~~'' [7] [8]''~~		if <math>c_1.t(n)\leq f(n) \leq c_2.t(n)</math> for all <math>n\geq d</math>, where ''c<sub>1</sub>'', ''c<sub>2</sub>'' and ''d'' are positive integers<ref name=":1" /><ref name=":2" />

	=== Common Big-O Notations ===		=== Common Big-O Notations ===
Line 176:		Line 176:
	Game theory deals with optimal decision making in any strategic setting. It is extensively used for analysing customer behaviour, market trend, develop effective business strategies, competitive product pricing etc. Computational complexity helps in defining the most efficient algorithm for approaching the game and to come up with best outcome while considering all the possible variations.		Game theory deals with optimal decision making in any strategic setting. It is extensively used for analysing customer behaviour, market trend, develop effective business strategies, competitive product pricing etc. Computational complexity helps in defining the most efficient algorithm for approaching the game and to come up with best outcome while considering all the possible variations.

	==== Healthcare system ====		==== Healthcare system<ref>Thomas G. Kannampallil, Guido F. Schauer, Trevor Cohen, Vimla L. Patel, “Considering complexity in healthcare systems,” ''Journal of Biomedical Informatics,'' vol. 44, no. 6, pp. 943-947, 2011.</ref> ====
	Various aspects of healthcare system such as patient management, continuity of patient care, nursing etc requires efficient decision-making processes. These complex tasks are broken down into fairly smaller and manageable tasks using computational models while giving due consideration to interrelatedness of systems.		Various aspects of healthcare system such as patient management, continuity of patient care, nursing etc requires efficient decision-making processes. These complex tasks are broken down into fairly smaller and manageable tasks using computational models while giving due consideration to interrelatedness of systems.

Line 183:		Line 183:

	== Sources ==		== Sources ==
	<references />		<references responsive="0" />

Fall2024 Wiki Team11: Undo revision 7430 by Fall2024 Wiki Team11 (talk)

2024-12-15T02:44:06Z

Undo revision 7430 by Fall2024 Wiki Team11 (talk)

← Older revision		Revision as of 22:44, 14 December 2024
Line 22:		Line 22:

	=== History ===		=== History ===
	The history of computational complexity can be traced back to the paper, ''“On computable numbers with an application to the Entsheidungs ~~problem '''<ref''' name=A. M. Turing'''>'''[The London Mathematical Society, 1936/ On computable numbers with an application to the Entsheidungs problem]'''<nowiki></ref></nowiki>'''”~~,'' published in 1936 by A M Turing. In this paper, Turing introduced his famous Turing Machine and provided a convincing formalization of computable function. In following years, once the theory was established to determine which problem can and cannot be solved, questions regarding relative computational difficulty came up [3]. This can be considered as the birth of computational complexity. Rabin M O in his paper, ''“Degree of difficulty of computing a function and partial ordering or recursive sets”,'' in 1960 made an attempt to measure the amount of work inherent in computing a function along with defining the degree of difficulty of computing a function [4]. Another influential paper that was published in 1965 by Hartmanis and Stearns, “''On the computational complexity of algorithms''”, discussed the method of categorizing problems according to how hard they are to compute. As part of this paper, a variety of theorems were established. It also provided a way to classify functions or recognition problems according to their computational complexity and laid out definitions of time complexity and space complexity [5]. Paper by Alan Cobham in 1965, ''“The intrinsic computational difficulty of a function”'', discussed the relative difficulty between addition and multiplication and characterised an important class of functions computable in time bounded by a polynomial in the length of input [6]. These papers from Cobhem, Hartemanis and Rabin can be considered as the founding papers for the field of computational complexity. Manuel Blum in 1967, formulated axioms known as Blum Axioms, that specify desirable properties of complexity measures on the set of computation function. Field of computational complexity started to grow from 1971 onwards, with studies from Steven Cook, Leonid Levin and Richard Karp which expanded the study of problems belonging to class NP-Complete.		The history of computational complexity can be traced back to the paper, ''“On computable numbers with an application to the Entsheidungs problem”,'' published in 1936 by A M Turing. In this paper, Turing introduced his famous Turing Machine and provided a convincing formalization of computable function. In following years, once the theory was established to determine which problem can and cannot be solved, questions regarding relative computational difficulty came up [3]. This can be considered as the birth of computational complexity. Rabin M O in his paper, ''“Degree of difficulty of computing a function and partial ordering or recursive sets”,'' in 1960 made an attempt to measure the amount of work inherent in computing a function along with defining the degree of difficulty of computing a function [4]. Another influential paper that was published in 1965 by Hartmanis and Stearns, “''On the computational complexity of algorithms''”, discussed the method of categorizing problems according to how hard they are to compute. As part of this paper, a variety of theorems were established. It also provided a way to classify functions or recognition problems according to their computational complexity and laid out definitions of time complexity and space complexity [5]. Paper by Alan Cobham in 1965, ''“The intrinsic computational difficulty of a function”'', discussed the relative difficulty between addition and multiplication and characterised an important class of functions computable in time bounded by a polynomial in the length of input [6]. These papers from Cobhem, Hartemanis and Rabin can be considered as the founding papers for the field of computational complexity. Manuel Blum in 1967, formulated axioms known as Blum Axioms, that specify desirable properties of complexity measures on the set of computation function. Field of computational complexity started to grow from 1971 onwards, with studies from Steven Cook, Leonid Levin and Richard Karp which expanded the study of problems belonging to class NP-Complete.

	=== Need for Computational Complexity ===		=== Need for Computational Complexity ===

Fall2024 Wiki Team11 at 02:31, 15 December 2024

2024-12-15T02:31:22Z

← Older revision		Revision as of 22:31, 14 December 2024
Line 22:		Line 22:

	=== History ===		=== History ===
	The history of computational complexity can be traced back to the paper, ''“On computable numbers with an application to the Entsheidungs ~~problem”~~,'' published in 1936 by A M Turing. In this paper, Turing introduced his famous Turing Machine and provided a convincing formalization of computable function. In following years, once the theory was established to determine which problem can and cannot be solved, questions regarding relative computational difficulty came up [3]. This can be considered as the birth of computational complexity. Rabin M O in his paper, ''“Degree of difficulty of computing a function and partial ordering or recursive sets”,'' in 1960 made an attempt to measure the amount of work inherent in computing a function along with defining the degree of difficulty of computing a function [4]. Another influential paper that was published in 1965 by Hartmanis and Stearns, “''On the computational complexity of algorithms''”, discussed the method of categorizing problems according to how hard they are to compute. As part of this paper, a variety of theorems were established. It also provided a way to classify functions or recognition problems according to their computational complexity and laid out definitions of time complexity and space complexity [5]. Paper by Alan Cobham in 1965, ''“The intrinsic computational difficulty of a function”'', discussed the relative difficulty between addition and multiplication and characterised an important class of functions computable in time bounded by a polynomial in the length of input [6]. These papers from Cobhem, Hartemanis and Rabin can be considered as the founding papers for the field of computational complexity. Manuel Blum in 1967, formulated axioms known as Blum Axioms, that specify desirable properties of complexity measures on the set of computation function. Field of computational complexity started to grow from 1971 onwards, with studies from Steven Cook, Leonid Levin and Richard Karp which expanded the study of problems belonging to class NP-Complete.		The history of computational complexity can be traced back to the paper, ''“On computable numbers with an application to the Entsheidungs problem '''<ref''' name=A. M. Turing'''>'''[The London Mathematical Society, 1936/ On computable numbers with an application to the Entsheidungs problem]'''<nowiki></ref></nowiki>'''”,'' published in 1936 by A M Turing. In this paper, Turing introduced his famous Turing Machine and provided a convincing formalization of computable function. In following years, once the theory was established to determine which problem can and cannot be solved, questions regarding relative computational difficulty came up [3]. This can be considered as the birth of computational complexity. Rabin M O in his paper, ''“Degree of difficulty of computing a function and partial ordering or recursive sets”,'' in 1960 made an attempt to measure the amount of work inherent in computing a function along with defining the degree of difficulty of computing a function [4]. Another influential paper that was published in 1965 by Hartmanis and Stearns, “''On the computational complexity of algorithms''”, discussed the method of categorizing problems according to how hard they are to compute. As part of this paper, a variety of theorems were established. It also provided a way to classify functions or recognition problems according to their computational complexity and laid out definitions of time complexity and space complexity [5]. Paper by Alan Cobham in 1965, ''“The intrinsic computational difficulty of a function”'', discussed the relative difficulty between addition and multiplication and characterised an important class of functions computable in time bounded by a polynomial in the length of input [6]. These papers from Cobhem, Hartemanis and Rabin can be considered as the founding papers for the field of computational complexity. Manuel Blum in 1967, formulated axioms known as Blum Axioms, that specify desirable properties of complexity measures on the set of computation function. Field of computational complexity started to grow from 1971 onwards, with studies from Steven Cook, Leonid Levin and Richard Karp which expanded the study of problems belonging to class NP-Complete.

	=== Need for Computational Complexity ===		=== Need for Computational Complexity ===

Fall2024 Wiki Team11 at 02:25, 15 December 2024

2024-12-15T02:25:52Z

← Older revision		Revision as of 22:25, 14 December 2024
Line 10:		Line 10:

	===== P (Polynomial Time) Class =====		===== P (Polynomial Time) Class =====
	If a problem can be solved in polynomial time, then it is considered as a Class P problem. Problems in this class are efficiently solvable, however, the time required to solve grows polynomially with the size of input~~<ref name=":0">R. Vanderbei, Linear Programming Foundations and Extensions, Springer, 2014.</ref>~~. Linear programming problems are considered under P class.		If a problem can be solved in polynomial time, then it is considered as a Class P problem. Problems in this class are efficiently solvable, however, the time required to solve grows polynomially with the size of input. Linear programming problems are considered under P class. [1]

	===== NP (Non-deterministic Polynomial Time) Class =====		===== NP (Non-deterministic Polynomial Time) Class =====
	If the solution of a problem can be verified in polynomial time, then the problem is considered as a Class NP problem. These problems require a solution to be available which can be verified, however finding solution itself may take more than polynomial time~~<ref name=":0" />~~.		If the solution of a problem can be verified in polynomial time, then the problem is considered as a Class NP problem. These problems require a solution to be available which can be verified, however finding solution itself may take more than polynomial time. [1]

	===== NP-Hard Class =====		===== NP-Hard Class =====
	NP-Hard problems may or may not fall under NP Class. A problem H is NP-Hard if for every problem L in NP, there exists a polynomial time reduction from L to H~~<ref name=":0" />~~. These are usually optimization problems.		NP-Hard problems may or may not fall under NP Class. A problem H is NP-Hard if for every problem L in NP, there exists a polynomial time reduction from L to H. These are usually optimization problems. [1]

	===== NP-Complete Class =====		===== NP-Complete Class =====
	NP-Complete problems are a subset of NP class. If all the problems in a NP can be reduced to problem H in polynomial time, then problem H is considered as NP-Complete~~<ref name=":0" />~~. NP Complete problems are the hardest problems to solve. These are usually decision problems.		NP-Complete problems are a subset of NP class. If all the problems in a NP can be reduced to problem H in polynomial time, then problem H is considered as NP-Complete. NP Complete problems are the hardest problems to solve. These are usually decision problems. [1]

	=== History ===		=== History ===
	The history of computational complexity can be traced back to the paper, ''“On computable numbers with an application to the Entsheidungs problem”~~<ref>A. M. Turing, “On computable numbers with an application to the Entsheidungs problem,” in ''The London Mathematical Society'', 1936.</ref>~~,'' published in 1936 by A M Turing. In this paper, Turing introduced his famous Turing Machine and provided a convincing formalization of computable function. In following years, once the theory was established to determine which problem can and cannot be solved, questions regarding relative computational difficulty came up~~<ref>S. A. Cook, “An overview of computational complexity,” ''Communications of the ACM,'' vol. 26, no. 6, pp. 400-408, 1983.</ref>~~. This can be considered as the birth of computational complexity. Rabin M O in his paper, ''“Degree of difficulty of computing a function and partial ordering or recursive sets”~~<ref>M. O. Rabin, “Degree of difificulty of computing a function and a partial ordering or recursive sets,” Hebrew University, Jerusalem, Israel, 1960.</ref>~~,'' in 1960 made an attempt to measure the amount of work inherent in computing a function along with defining the degree of difficulty of computing a function. Another influential paper that was published in 1965 by Hartmanis and Stearns, “''On the computational complexity of algorithms''”~~<ref>J. Hartmanis, R. Stearns, “On the Computational Complexity of Algorithms,” ''American Mathematical Society,'' 1965.</ref>~~, discussed the method of categorizing problems according to how hard they are to compute. As part of this paper, a variety of theorems were established. It also provided a way to classify functions or recognition problems according to their computational complexity and laid out definitions of time complexity and space complexity. Paper by Alan Cobham in 1965, ''“The intrinsic computational difficulty of ~~functions”''<ref>A. Cobham, “The intrinsic computational difficulty of functions,” ''Logic, methodology and philosophy of science,~~'' ~~pp. 24-30, 1965.</ref>~~, discussed the relative difficulty between addition and multiplication and characterised an important class of functions computable in time bounded by a polynomial in the length of input. These papers from Cobhem, Hartemanis and Rabin can be considered as the founding papers for the field of computational complexity. Manuel Blum in 1967, formulated axioms known as Blum Axioms, that specify desirable properties of complexity measures on the set of computation function. Field of computational complexity started to grow from 1971 onwards, with studies from Steven Cook, Leonid Levin and Richard Karp which expanded the study of problems belonging to class NP-Complete.		The history of computational complexity can be traced back to the paper, ''“On computable numbers with an application to the Entsheidungs problem”,'' published in 1936 by A M Turing. In this paper, Turing introduced his famous Turing Machine and provided a convincing formalization of computable function. In following years, once the theory was established to determine which problem can and cannot be solved, questions regarding relative computational difficulty came up [3]. This can be considered as the birth of computational complexity. Rabin M O in his paper, ''“Degree of difficulty of computing a function and partial ordering or recursive sets”,'' in 1960 made an attempt to measure the amount of work inherent in computing a function along with defining the degree of difficulty of computing a function [4]. Another influential paper that was published in 1965 by Hartmanis and Stearns, “''On the computational complexity of algorithms''”, discussed the method of categorizing problems according to how hard they are to compute. As part of this paper, a variety of theorems were established. It also provided a way to classify functions or recognition problems according to their computational complexity and laid out definitions of time complexity and space complexity [5]. Paper by Alan Cobham in 1965, ''“The intrinsic computational difficulty of a function”'', discussed the relative difficulty between addition and multiplication and characterised an important class of functions computable in time bounded by a polynomial in the length of input [6]. These papers from Cobhem, Hartemanis and Rabin can be considered as the founding papers for the field of computational complexity. Manuel Blum in 1967, formulated axioms known as Blum Axioms, that specify desirable properties of complexity measures on the set of computation function. Field of computational complexity started to grow from 1971 onwards, with studies from Steven Cook, Leonid Levin and Richard Karp which expanded the study of problems belonging to class NP-Complete.

	=== Need for Computational Complexity ===		=== Need for Computational Complexity ===
Line 38:		Line 38:
	<math>f(n) = O(t(n))</math>		<math>f(n) = O(t(n))</math>

	if <math>f(n) \leq c.t(n)</math> for all <math>n\geq d</math>, where ''c'' and ''d'' are positive integers<ref name=":1">Reza Zanjirani Farahani, Masoud Hekmatfar, Facility Location - Concepts, Models, Algorithms and Case Studies, Physica-Verlag, 2009.</ref><ref name=":2">M. Sipser, Introduction To The Theory Of Computation, Thomson Course Technology, 2006.</ref>		if <math>f(n) \leq c.t(n)</math> for all <math>n\geq d</math>, where ''c'' and ''d'' are positive integers ''[7] [8]''

	===== Big-Omega Notation =====		===== Big-Omega Notation =====
Line 45:		Line 45:
	<math>f(n) = \Omega (t(n))</math>		<math>f(n) = \Omega (t(n))</math>

	if <math>f(n)\geq c.t(n)</math> for all <math>n\geq d</math>, where ''c'' and ''d'' are positive integers~~<ref name=":1" /><ref name=":2" />~~		if <math>f(n)\geq c.t(n)</math> for all <math>n\geq d</math>, where ''c'' and ''d'' are positive integers ''[7] [8]''

	===== Big-Theta Notation =====		===== Big-Theta Notation =====
Line 52:		Line 52:
	<math>f(n)=\Theta(t(n))</math>,		<math>f(n)=\Theta(t(n))</math>,

	if <math>c_1.t(n)\leq f(n) \leq c_2.t(n)</math> for all <math>n\geq d</math>, where ''c<sub>1</sub>'', ''c<sub>2</sub>'' and ''d'' are positive integers~~<ref name=":1" /><ref name=":2" />~~		if <math>c_1.t(n)\leq f(n) \leq c_2.t(n)</math> for all <math>n\geq d</math>, where ''c<sub>1</sub>'', ''c<sub>2</sub>'' and ''d'' are positive integers '' [7] [8]''

	=== Common Big-O Notations ===		=== Common Big-O Notations ===
Line 176:		Line 176:
	Game theory deals with optimal decision making in any strategic setting. It is extensively used for analysing customer behaviour, market trend, develop effective business strategies, competitive product pricing etc. Computational complexity helps in defining the most efficient algorithm for approaching the game and to come up with best outcome while considering all the possible variations.		Game theory deals with optimal decision making in any strategic setting. It is extensively used for analysing customer behaviour, market trend, develop effective business strategies, competitive product pricing etc. Computational complexity helps in defining the most efficient algorithm for approaching the game and to come up with best outcome while considering all the possible variations.

	==== Healthcare system<ref>Thomas G. Kannampallil, Guido F. Schauer, Trevor Cohen, Vimla L. Patel, “Considering complexity in healthcare systems,” ''Journal of Biomedical Informatics,'' vol. 44, no. 6, pp. 943-947, 2011.</ref> ====		==== Healthcare system ====
	Various aspects of healthcare system such as patient management, continuity of patient care, nursing etc requires efficient decision-making processes. These complex tasks are broken down into fairly smaller and manageable tasks using computational models while giving due consideration to interrelatedness of systems.		Various aspects of healthcare system such as patient management, continuity of patient care, nursing etc requires efficient decision-making processes. These complex tasks are broken down into fairly smaller and manageable tasks using computational models while giving due consideration to interrelatedness of systems.

Line 183:		Line 183:

	== Sources ==		== Sources ==
	<references ~~responsive="0"~~ />		<references />