Computational complexity theory - Revision history

The BestEditor4: /* growthexperiments-addlink-summary-summary:3|0|0 */

2025-05-26T19:18:46Z

Link suggestions feature: 3 links added.

← Previous revision		Revision as of 19:18, 26 May 2025
Line 45:		Line 45:
	Many types of Turing machines are used to define complexity classes, such as [[deterministic Turing machine]]s, [[probabilistic Turing machine]]s, [[non-deterministic Turing machine]]s, [[quantum Turing machine]]s, [[symmetric Turing machine]]s and [[alternating Turing machine]]s. They are all equally powerful in principle, but when resources (such as time or space) are bounded, some of these may be more powerful than others.		Many types of Turing machines are used to define complexity classes, such as [[deterministic Turing machine]]s, [[probabilistic Turing machine]]s, [[non-deterministic Turing machine]]s, [[quantum Turing machine]]s, [[symmetric Turing machine]]s and [[alternating Turing machine]]s. They are all equally powerful in principle, but when resources (such as time or space) are bounded, some of these may be more powerful than others.

	A deterministic Turing machine is the most basic Turing machine, which uses a fixed set of rules to determine its future actions. A probabilistic Turing machine is a deterministic Turing machine with an extra supply of random bits. The ability to make probabilistic decisions often helps algorithms solve problems more efficiently. Algorithms that use random bits are called [[randomized algorithm]]s. A non-deterministic Turing machine is a deterministic Turing machine with an added feature of non-determinism, which allows a Turing machine to have multiple possible future actions from a given state. One way to view non-determinism is that the Turing machine branches into many possible computational paths at each step, and if it solves the problem in any of these branches, it is said to have solved the problem. Clearly, this model is not meant to be a physically realizable model, it is just a theoretically interesting abstract machine that gives rise to particularly interesting complexity classes. For examples, see [[non-deterministic algorithm]].		A deterministic Turing machine is the most basic Turing machine, which uses a fixed set of rules to determine its future actions. A probabilistic Turing machine is a deterministic Turing machine with an extra supply of random bits. The ability to make probabilistic decisions often helps algorithms solve problems more efficiently. Algorithms that use random bits are called [[randomized algorithm]]s. A non-deterministic Turing machine is a deterministic Turing machine with an added feature of non-determinism, which allows a Turing machine to have multiple possible future actions from a given state. One way to view non-determinism is that the Turing machine branches into many possible computational paths at each step, and if it solves the problem in any of these branches, it is said to have solved the problem. Clearly, this model is not meant to be a physically realizable model, it is just a theoretically interesting [[abstract machine]] that gives rise to particularly interesting complexity classes. For examples, see [[non-deterministic algorithm]].

	===Other machine models===		===Other machine models===
Line 55:		Line 55:
	For a precise definition of what it means to solve a problem using a given amount of time and space, a computational model such as the [[deterministic Turing machine]] is used. The time required by a deterministic Turing machine <math>M</math> on input <math>x</math> is the total number of state transitions, or steps, the machine makes before it halts and outputs the answer ("yes" or "no"). A Turing machine <math>M</math> is said to operate within time <math>f(n)</math> if the time required by <math>M</math> on each input of length <math>n</math> is at most <math>f(n)</math>. A decision problem <math>A</math> can be solved in time <math>f(n)</math> if there exists a Turing machine operating in time <math>f(n)</math> that solves the problem. Since complexity theory is interested in classifying problems based on their difficulty, one defines sets of problems based on some criteria. For instance, the set of problems solvable within time <math>f(n)</math> on a deterministic Turing machine is then denoted by [[DTIME]](<math>f(n)</math>).		For a precise definition of what it means to solve a problem using a given amount of time and space, a computational model such as the [[deterministic Turing machine]] is used. The time required by a deterministic Turing machine <math>M</math> on input <math>x</math> is the total number of state transitions, or steps, the machine makes before it halts and outputs the answer ("yes" or "no"). A Turing machine <math>M</math> is said to operate within time <math>f(n)</math> if the time required by <math>M</math> on each input of length <math>n</math> is at most <math>f(n)</math>. A decision problem <math>A</math> can be solved in time <math>f(n)</math> if there exists a Turing machine operating in time <math>f(n)</math> that solves the problem. Since complexity theory is interested in classifying problems based on their difficulty, one defines sets of problems based on some criteria. For instance, the set of problems solvable within time <math>f(n)</math> on a deterministic Turing machine is then denoted by [[DTIME]](<math>f(n)</math>).

	Analogous definitions can be made for space requirements. Although time and space are the most well-known complexity resources, any [[Complexity\|complexity measure]] can be viewed as a computational resource. Complexity measures are very generally defined by the [[Blum complexity axioms]]. Other complexity measures used in complexity theory include [[communication complexity]], [[circuit complexity]], and [[decision tree complexity]].		Analogous definitions can be made for space requirements. Although time and space are the most well-known complexity resources, any [[Complexity\|complexity measure]] can be viewed as a [[computational resource]]. Complexity measures are very generally defined by the [[Blum complexity axioms]]. Other complexity measures used in complexity theory include [[communication complexity]], [[circuit complexity]], and [[decision tree complexity]].

	The complexity of an algorithm is often expressed using [[big O notation]].		The complexity of an algorithm is often expressed using [[big O notation]].
Line 65:		Line 65:
	# Average-case complexity: This is the complexity of solving the problem on an average. This complexity is only defined with respect to a [[probability distribution]] over the inputs. For instance, if all inputs of the same size are assumed to be equally likely to appear, the average case complexity can be defined with respect to the uniform distribution over all inputs of size <math>n</math>.		# Average-case complexity: This is the complexity of solving the problem on an average. This complexity is only defined with respect to a [[probability distribution]] over the inputs. For instance, if all inputs of the same size are assumed to be equally likely to appear, the average case complexity can be defined with respect to the uniform distribution over all inputs of size <math>n</math>.
	# [[Amortized analysis]]: Amortized analysis considers both the costly and less costly operations together over the whole series of operations of the algorithm.		# [[Amortized analysis]]: Amortized analysis considers both the costly and less costly operations together over the whole series of operations of the algorithm.
	# Worst-case complexity: This is the complexity of solving the problem for the worst input of size <math>n</math>.		# [[Worst-case complexity]]: This is the complexity of solving the problem for the worst input of size <math>n</math>.
	The order from cheap to costly is: Best, average (of [[discrete uniform distribution]]), amortized, worst.		The order from cheap to costly is: Best, average (of [[discrete uniform distribution]]), amortized, worst.

Umbe1987: changed "finite" to "infinite" as I think it makes more sense given the sentence (I might be wrong though, please anybody check).

2025-04-29T15:08:45Z

changed "finite" to "infinite" as I think it makes more sense given the sentence (I might be wrong though, please anybody check).

← Previous revision		Revision as of 15:08, 29 April 2025
Line 228:		Line 228:
	==Intractability== <!-- This section is linked from [[Minimax]], [[Intractability]], [[Intractable]] -->		==Intractability== <!-- This section is linked from [[Minimax]], [[Intractability]], [[Intractable]] -->
	{{See also\|Combinatorial explosion}}		{{See also\|Combinatorial explosion}}
	A problem that can theoretically be solved, but requires impractical and ~~finite~~ resources (e.g., time) to do so, is known as an '''''{{visible anchor\|intractable problem}}'''''.<ref>Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2007) [[Introduction to Automata Theory, Languages, and Computation]], Addison Wesley, Boston/San Francisco/New York (page 368)</ref> Conversely, a problem that can be solved in practice is called a '''''{{visible anchor\|tractable problem}}''''', literally "a problem that can be handled". The term ''[[wikt:infeasible\|infeasible]]'' (literally "cannot be done") is sometimes used interchangeably with ''[[wikt:intractable\|intractable]]'',<ref>{{cite book \|title=Algorithms and Complexity \|first=Gerard \|last=Meurant \|year=2014 \|isbn=978-0-08093391-7 \|page=[https://books.google.com/books?id=6WriBQAAQBAJ&pg=PA4 p. 4]\|publisher=Elsevier }}</ref> though this risks confusion with a [[feasible solution]] in [[mathematical optimization]].<ref>		A problem that can theoretically be solved, but requires impractical and infinite resources (e.g., time) to do so, is known as an '''''{{visible anchor\|intractable problem}}'''''.<ref>Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2007) [[Introduction to Automata Theory, Languages, and Computation]], Addison Wesley, Boston/San Francisco/New York (page 368)</ref> Conversely, a problem that can be solved in practice is called a '''''{{visible anchor\|tractable problem}}''''', literally "a problem that can be handled". The term ''[[wikt:infeasible\|infeasible]]'' (literally "cannot be done") is sometimes used interchangeably with ''[[wikt:intractable\|intractable]]'',<ref>{{cite book \|title=Algorithms and Complexity \|first=Gerard \|last=Meurant \|year=2014 \|isbn=978-0-08093391-7 \|page=[https://books.google.com/books?id=6WriBQAAQBAJ&pg=PA4 p. 4]\|publisher=Elsevier }}</ref> though this risks confusion with a [[feasible solution]] in [[mathematical optimization]].<ref>
	{{cite book		{{cite book
	\|title=Writing for Computer Science		\|title=Writing for Computer Science

Cedar101: \textsf

2025-04-18T04:24:02Z

\textsf

← Previous revision		Revision as of 04:24, 18 April 2025
Line 239:		Line 239:
	}}</ref>		}}</ref>

	Tractable problems are frequently identified with problems that have polynomial-time solutions (<math>P</math>, <math>PTIME</math>); this is known as the [[Cobham–Edmonds thesis]]. Problems that are known to be intractable in this sense include those that are [[EXPTIME]]-hard. If <math>NP</math> is not the same as <math>P</math>, then [[NP-hard]] problems are also intractable in this sense.		Tractable problems are frequently identified with problems that have polynomial-time solutions (<math>\textsf{P}</math>, <math>\textsf{PTIME}</math>); this is known as the [[Cobham–Edmonds thesis]]. Problems that are known to be intractable in this sense include those that are [[EXPTIME]]-hard. If <math>\textsf{NP}</math> is not the same as <math>\textsf{P}</math>, then [[NP-hard]] problems are also intractable in this sense.

	However, this identification is inexact: a polynomial-time solution with large degree or large leading coefficient grows quickly, and may be impractical for practical size problems; conversely, an exponential-time solution that grows slowly may be practical on realistic input, or a solution that takes a long time in the worst case may take a short time in most cases or the average case, and thus still be practical. Saying that a problem is not in <math>P</math> does not imply that all large cases of the problem are hard or even that most of them are. For example, the decision problem in [[Presburger arithmetic]] has been shown not to be in <math>P</math>, yet algorithms have been written that solve the problem in reasonable times in most cases. Similarly, algorithms can solve the NP-complete [[knapsack problem]] over a wide range of sizes in less than quadratic time and [[SAT solver]]s routinely handle large instances of the NP-complete [[Boolean satisfiability problem]].		However, this identification is inexact: a polynomial-time solution with large degree or large leading coefficient grows quickly, and may be impractical for practical size problems; conversely, an exponential-time solution that grows slowly may be practical on realistic input, or a solution that takes a long time in the worst case may take a short time in most cases or the average case, and thus still be practical. Saying that a problem is not in <math>\textsf{P}</math> does not imply that all large cases of the problem are hard or even that most of them are. For example, the decision problem in [[Presburger arithmetic]] has been shown not to be in <math>\textsf{P}</math>, yet algorithms have been written that solve the problem in reasonable times in most cases. Similarly, algorithms can solve the NP-complete [[knapsack problem]] over a wide range of sizes in less than quadratic time and [[SAT solver]]s routinely handle large instances of the NP-complete [[Boolean satisfiability problem]].

	To see why exponential-time algorithms are generally unusable in practice, consider a program that makes <math>2^n</math> operations before halting. For small <math>n</math>, say 100, and assuming for the sake of example that the computer does <math>10^{12}</math> operations each second, the program would run for about <math>4 \times 10^{10}</math> years, which is the same order of magnitude as the [[age of the universe]]. Even with a much faster computer, the program would only be useful for very small instances and in that sense the intractability of a problem is somewhat independent of technological progress. However, an exponential-time algorithm that takes <math>1.0001^n</math> operations is practical until <math>n</math> gets relatively large.		To see why exponential-time algorithms are generally unusable in practice, consider a program that makes <math>2^n</math> operations before halting. For small <math>n</math>, say 100, and assuming for the sake of example that the computer does <math>10^{12}</math> operations each second, the program would run for about <math>4 \times 10^{10}</math> years, which is the same order of magnitude as the [[age of the universe]]. Even with a much faster computer, the program would only be useful for very small instances and in that sense the intractability of a problem is somewhat independent of technological progress. However, an exponential-time algorithm that takes <math>1.0001^n</math> operations is practical until <math>n</math> gets relatively large.

Cedar101: /* Important open problems */ \textsf{}

2025-04-18T04:22:53Z

Important open problems: \textsf{}

← Previous revision		Revision as of 04:22, 18 April 2025
Line 190:		Line 190:

	===Problems in NP not known to be in P or NP-complete===		===Problems in NP not known to be in P or NP-complete===
	It was shown by Ladner that if <math>P \neq NP</math> then there exist problems in <math>NP</math> that are neither in <math>P</math> nor <math>NP</math>-complete.<ref name="Ladner75" /> Such problems are called [[NP-intermediate]] problems. The [[graph isomorphism problem]], the [[discrete logarithm problem]] and the [[integer factorization problem]] are examples of problems believed to be NP-intermediate. They are some of the very few NP problems not known to be in <math>P</math> or to be <math>NP</math>-complete.		It was shown by Ladner that if <math>\textsf{P} \neq \textsf{NP}</math> then there exist problems in <math>\textsf{NP}</math> that are neither in <math>\textsf{P}</math> nor <math>\textsf{NP}</math>-complete.<ref name="Ladner75" /> Such problems are called [[NP-intermediate]] problems. The [[graph isomorphism problem]], the [[discrete logarithm problem]] and the [[integer factorization problem]] are examples of problems believed to be NP-intermediate. They are some of the very few NP problems not known to be in <math>\textsf{P}</math> or to be <math>\textsf{NP}</math>-complete.

	The [[graph isomorphism problem]] is the computational problem of determining whether two finite [[graph (discrete mathematics)\|graph]]s are [[graph isomorphism\|isomorphic]]. An important unsolved problem in complexity theory is whether the graph isomorphism problem is in <math>P</math>, <math>NP</math>-complete, or NP-intermediate. The answer is not known, but it is believed that the problem is at least not NP-complete.<ref name="AK06">{{Citation		The [[graph isomorphism problem]] is the computational problem of determining whether two finite [[graph (discrete mathematics)\|graph]]s are [[graph isomorphism\|isomorphic]]. An important unsolved problem in complexity theory is whether the graph isomorphism problem is in <math>\textsf{P}</math>, <math>\textsf{NP}</math>-complete, or NP-intermediate. The answer is not known, but it is believed that the problem is at least not NP-complete.<ref name="AK06">{{Citation
	\| first1 = Vikraman		\| first1 = Vikraman
	\| last1 = Arvind		\| last1 = Arvind
Line 215:		Line 215:
	\| year = 1988}}</ref> Since it is widely believed that the polynomial hierarchy does not collapse to any finite level, it is believed that graph isomorphism is not NP-complete. The best algorithm for this problem, due to [[László Babai]] and [[Eugene Luks]] has run time <math>O(2^{\sqrt{n \log n}})</math> for graphs with <math>n</math> vertices, although some recent work by Babai offers some potentially new perspectives on this.<ref>{{cite arXiv \|last=Babai \|first=László \|date=2016 \|title=Graph Isomorphism in Quasipolynomial Time \|eprint=1512.03547 \|class=cs.DS }}</ref>		\| year = 1988}}</ref> Since it is widely believed that the polynomial hierarchy does not collapse to any finite level, it is believed that graph isomorphism is not NP-complete. The best algorithm for this problem, due to [[László Babai]] and [[Eugene Luks]] has run time <math>O(2^{\sqrt{n \log n}})</math> for graphs with <math>n</math> vertices, although some recent work by Babai offers some potentially new perspectives on this.<ref>{{cite arXiv \|last=Babai \|first=László \|date=2016 \|title=Graph Isomorphism in Quasipolynomial Time \|eprint=1512.03547 \|class=cs.DS }}</ref>

	The [[integer factorization problem]] is the computational problem of determining the [[prime factorization]] of a given integer. Phrased as a decision problem, it is the problem of deciding whether the input has a prime factor less than <math>k</math>. No efficient integer factorization algorithm is known, and this fact forms the basis of several modern cryptographic systems, such as the [[RSA (algorithm)\|RSA]] algorithm. The integer factorization problem is in <math>NP</math> and in <math>co\~~text~~{-}NP</math> (and even in UP and co-UP<ref>{{cite web\|first=Lance\|last=Fortnow\|author-link=Lance Fortnow\|title=Computational Complexity Blog: Factoring\|date=2002-09-13\|url=http://weblog.fortnow.com/2002/09/complexity-class-of-week-factoring.html\|website=weblog.fortnow.com}}</ref>). If the problem is <math>NP</math>-complete, the polynomial time hierarchy will collapse to its first level (i.e., <math>NP</math> will equal <math>co\~~text~~{-}NP</math>). The best known algorithm for integer factorization is the [[general number field sieve]], which takes time <math>O(e^{\left(\sqrt[3]{\frac{64}{9}}\right)\sqrt[3]{(\log n)}\sqrt[3]{(\log \log n)^2}})</math><ref>Wolfram MathWorld: [http://mathworld.wolfram.com/NumberFieldSieve.html Number Field Sieve]</ref> to factor an odd integer <math>n</math>. However, the best known [[quantum algorithm]] for this problem, [[Shor's algorithm]], does run in polynomial time. Unfortunately, this fact doesn't say much about where the problem lies with respect to non-quantum complexity classes.		The [[integer factorization problem]] is the computational problem of determining the [[prime factorization]] of a given integer. Phrased as a decision problem, it is the problem of deciding whether the input has a prime factor less than <math>k</math>. No efficient integer factorization algorithm is known, and this fact forms the basis of several modern cryptographic systems, such as the [[RSA (algorithm)\|RSA]] algorithm. The integer factorization problem is in <math>\textsf{NP}</math> and in <math>\textsf{co-NP}</math> (and even in UP and co-UP<ref>{{cite web\|first=Lance\|last=Fortnow\|author-link=Lance Fortnow\|title=Computational Complexity Blog: Factoring\|date=2002-09-13\|url=http://weblog.fortnow.com/2002/09/complexity-class-of-week-factoring.html\|website=weblog.fortnow.com}}</ref>). If the problem is <math>\textsf{NP}</math>-complete, the polynomial time hierarchy will collapse to its first level (i.e., <math>\textsf{NP}</math> will equal <math>\textsf{co-NP}</math>). The best known algorithm for integer factorization is the [[general number field sieve]], which takes time <math>O(e^{\left(\sqrt[3]{\frac{64}{9}}\right)\sqrt[3]{(\log n)}\sqrt[3]{(\log \log n)^2}})</math><ref>Wolfram MathWorld: [http://mathworld.wolfram.com/NumberFieldSieve.html Number Field Sieve]</ref> to factor an odd integer <math>n</math>. However, the best known [[quantum algorithm]] for this problem, [[Shor's algorithm]], does run in polynomial time. Unfortunately, this fact doesn't say much about where the problem lies with respect to non-quantum complexity classes.

	===Separations between other complexity classes===		===Separations between other complexity classes===
	Many known complexity classes are suspected to be unequal, but this has not been proved. For instance <math>P \subseteq NP \subseteq PP \subseteq PSPACE</math>, but it is possible that <math>P = PSPACE</math>. If <math>P</math> is not equal to <math>NP</math>, then <math>P</math> is not equal to <math>PSPACE</math> either. Since there are many known complexity classes between <math>P</math> and <math>PSPACE</math>, such as <math>RP</math>, <math>BPP</math>, <math>PP</math>, <math>BQP</math>, <math>MA</math>, <math>PH</math>, etc., it is possible that all these complexity classes collapse to one class. Proving that any of these classes are unequal would be a major breakthrough in complexity theory.		Many known complexity classes are suspected to be unequal, but this has not been proved. For instance <math>\textsf{P} \subseteq \textsf{NP} \subseteq \textsf{PP} \subseteq \textsf{PSPACE}</math>, but it is possible that <math>\textsf{P} = \textsf{PSPACE}</math>. If <math>\textsf{P}</math> is not equal to <math>\textsf{NP}</math>, then <math>\textsf{P}</math> is not equal to <math>\textsf{PSPACE}</math> either. Since there are many known complexity classes between <math>\textsf{P}</math> and <math>\textsf{PSPACE}</math>, such as <math>\textsf{RP}</math>, <math>\textsf{BPP}</math>, <math>\textsf{PP}</math>, <math>\textsf{BQP}</math>, <math>\textsf{MA}</math>, <math>\textsf{PH}</math>, etc., it is possible that all these complexity classes collapse to one class. Proving that any of these classes are unequal would be a major breakthrough in complexity theory.

	Along the same lines, <math>co\~~text~~{-}NP</math> is the class containing the [[Complement (complexity)\|complement]] problems (i.e. problems with the ''yes''/''no'' answers reversed) of <math>NP</math> problems. It is believed<ref>[http://www.cs.princeton.edu/courses/archive/spr06/cos522/ Boaz Barak's course on Computational Complexity] [http://www.cs.princeton.edu/courses/archive/spr06/cos522/lec2.pdf Lecture 2]</ref> that <math>NP</math> is not equal to <math>co\~~text~~{-}NP</math>; however, it has not yet been proven. It is clear that if these two complexity classes are not equal then <math>P</math> is not equal to <math>NP</math>, since <math>P = co\~~text~~{-}P</math>. Thus if <math>P = NP</math> we would have <math>co\~~text~~{-}P = co\~~text~~{-}NP</math> whence <math>NP = P = co\~~text~~{-}P = co\~~text~~{-}NP</math>.		Along the same lines, <math>\textsf{co-NP}</math> is the class containing the [[Complement (complexity)\|complement]] problems (i.e. problems with the ''yes''/''no'' answers reversed) of <math>\textsf{NP}</math> problems. It is believed<ref>[http://www.cs.princeton.edu/courses/archive/spr06/cos522/ Boaz Barak's course on Computational Complexity] [http://www.cs.princeton.edu/courses/archive/spr06/cos522/lec2.pdf Lecture 2]</ref> that <math>\textsf{NP}</math> is not equal to <math>\textsf{co-NP}</math>; however, it has not yet been proven. It is clear that if these two complexity classes are not equal then <math>\textsf{P}</math> is not equal to <math>\textsf{NP}</math>, since <math>\textsf{P} = \textsf{co-P}</math>. Thus if <math>P = NP</math> we would have <math>\textsf{co-P} = \textsf{co-NP}</math> whence <math>\textsf{NP} = \textsf{P} = \textsf{co-P} = \textsf{co-NP}</math>.

	Similarly, it is not known if <math>L</math> (the set of all problems that can be solved in logarithmic space) is strictly contained in <math>P</math> or equal to <math>P</math>. Again, there are many complexity classes between the two, such as <math>NL</math> and <math>NC</math>, and it is not known if they are distinct or equal classes.		Similarly, it is not known if <math>\textsf{L}</math> (the set of all problems that can be solved in logarithmic space) is strictly contained in <math>\textsf{P}</math> or equal to <math>\textsf{P}</math>. Again, there are many complexity classes between the two, such as <math>\textsf{NL}</math> and <math>\textsf{NC}</math>, and it is not known if they are distinct or equal classes.

	It is suspected that <math>P</math> and <math>BPP</math> are equal. However, it is currently open if <math>BPP = NEXP</math>.		It is suspected that <math>\textsf{P}</math> and <math>\textsf{BPP}</math> are equal. However, it is currently open if <math>\textsf{BPP} = \textsf{NEXP}</math>.

	==Intractability== <!-- This section is linked from [[Minimax]], [[Intractability]], [[Intractable]] -->		==Intractability== <!-- This section is linked from [[Minimax]], [[Intractability]], [[Intractable]] -->

TTWIDEE: /* Best, worst and average case complexity */ Improved wording

2025-04-02T11:00:01Z

Best, worst and average case complexity: Improved wording

← Previous revision		Revision as of 11:00, 2 April 2025
Line 60:		Line 60:

	===Best, worst and average case complexity===		===Best, worst and average case complexity===
	[[File:Sorting quicksort anim.gif\|thumb\|Visualization of the [[quicksort]] [[algorithm]] ~~that~~ has [[Best, worst and average case\|average case performance]] <math>\mathcal{O}(n\log n)</math>]]		[[File:Sorting quicksort anim.gif\|thumb\|Visualization of the [[quicksort]] [[algorithm]], which has [[Best, worst and average case\|average case performance]] <math>\mathcal{O}(n\log n)</math>]]
	The [[best, worst and average case]] complexity refer to three different ways of measuring the time complexity (or any other complexity measure) of different inputs of the same size. Since some inputs of size <math>n</math> may be faster to solve than others, we define the following complexities:		The [[best, worst and average case]] complexity refer to three different ways of measuring the time complexity (or any other complexity measure) of different inputs of the same size. Since some inputs of size <math>n</math> may be faster to solve than others, we define the following complexities:
	# Best-case complexity: This is the complexity of solving the problem for the best input of size <math>n</math>.		# Best-case complexity: This is the complexity of solving the problem for the best input of size <math>n</math>.

Remsense: Reverted 1 edit by 2600:100A:B051:BEF8:0:17:43A1:1F01 (talk) to last revision by Jorjulio

2025-03-29T15:30:19Z

Reverted 1 edit by 2600:100A:B051:BEF8:0:17:43A1:1F01 (talk) to last revision by Jorjulio

← Previous revision		Revision as of 15:30, 29 March 2025
Line 226:		Line 226:
	It is suspected that <math>P</math> and <math>BPP</math> are equal. However, it is currently open if <math>BPP = NEXP</math>.		It is suspected that <math>P</math> and <math>BPP</math> are equal. However, it is currently open if <math>BPP = NEXP</math>.

			==Intractability== <!-- This section is linked from [[Minimax]], [[Intractability]], [[Intractable]] -->
	==Intractability==
			{{See also\|Combinatorial explosion}}
	A problem that can theoretically be solved, but requires impractical and finite resources (e.g., time) to do so, is known as an . Conversely, a problem that can be solved in practice is called a , literally "a problem that can be handled". The term ''infeasible'' (literally "cannot be done") is sometimes used interchangeably with ''intractable'', though this risks confusion with a feasible solution in mathematical optimization.		A problem that can theoretically be solved, but requires impractical and finite resources (e.g., time) to do so, is known as an '''''{{visible anchor\|intractable problem}}'''''.<ref>Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2007) [[Introduction to Automata Theory, Languages, and Computation]], Addison Wesley, Boston/San Francisco/New York (page 368)</ref> Conversely, a problem that can be solved in practice is called a '''''{{visible anchor\|tractable problem}}''''', literally "a problem that can be handled". The term ''[[wikt:infeasible\|infeasible]]'' (literally "cannot be done") is sometimes used interchangeably with ''[[wikt:intractable\|intractable]]'',<ref>{{cite book \|title=Algorithms and Complexity \|first=Gerard \|last=Meurant \|year=2014 \|isbn=978-0-08093391-7 \|page=[https://books.google.com/books?id=6WriBQAAQBAJ&pg=PA4 p. 4]\|publisher=Elsevier }}</ref> though this risks confusion with a [[feasible solution]] in [[mathematical optimization]].<ref>
			{{cite book
			\|title=Writing for Computer Science
			\|first=Justin
			\|last=Zobel
			\|page=[https://books.google.com/books?id=LWCYBgAAQBAJ&pg=PA132 132]
			\|year=2015
			\|publisher=Springer
			\|isbn=978-1-44716639-9
			}}</ref>

	Tractable problems are frequently identified with problems that have polynomial-time solutions (, ); this is known as the Cobham–Edmonds thesis. Problems that are known to be intractable in this sense include those that are EXPTIME-hard. If is not the same as , then NP-hard problems are also intractable in this sense.		Tractable problems are frequently identified with problems that have polynomial-time solutions (<math>P</math>, <math>PTIME</math>); this is known as the [[Cobham–Edmonds thesis]]. Problems that are known to be intractable in this sense include those that are [[EXPTIME]]-hard. If <math>NP</math> is not the same as <math>P</math>, then [[NP-hard]] problems are also intractable in this sense.

	However, this identification is inexact: a polynomial-time solution with large degree or large leading coefficient grows quickly, and may be impractical for practical size problems; conversely, an exponential-time solution that grows slowly may be practical on realistic input, or a solution that takes a long time in the worst case may take a short time in most cases or the average case, and thus still be practical. Saying that a problem is not in does not imply that all large cases of the problem are hard or even that most of them are. For example, the decision problem in Presburger arithmetic has been shown not to be in , yet algorithms have been written that solve the problem in reasonable times in most cases. Similarly, algorithms can solve the NP-complete knapsack problem over a wide range of sizes in less than quadratic time and SAT ~~solvers~~ routinely handle large instances of the NP-complete Boolean satisfiability problem.		However, this identification is inexact: a polynomial-time solution with large degree or large leading coefficient grows quickly, and may be impractical for practical size problems; conversely, an exponential-time solution that grows slowly may be practical on realistic input, or a solution that takes a long time in the worst case may take a short time in most cases or the average case, and thus still be practical. Saying that a problem is not in <math>P</math> does not imply that all large cases of the problem are hard or even that most of them are. For example, the decision problem in [[Presburger arithmetic]] has been shown not to be in <math>P</math>, yet algorithms have been written that solve the problem in reasonable times in most cases. Similarly, algorithms can solve the NP-complete [[knapsack problem]] over a wide range of sizes in less than quadratic time and [[SAT solver]]s routinely handle large instances of the NP-complete [[Boolean satisfiability problem]].

	To see why exponential-time algorithms are generally unusable in practice, consider a program that makes operations before halting. For small , say 100, and assuming for the sake of example that the computer does operations each second, the program would run for about years, which is the same order of magnitude as the age of the universe. Even with a much faster computer, the program would only be useful for very small instances and in that sense the intractability of a problem is somewhat independent of technological progress. However, an exponential-time algorithm that takes operations is practical until gets relatively large.		To see why exponential-time algorithms are generally unusable in practice, consider a program that makes <math>2^n</math> operations before halting. For small <math>n</math>, say 100, and assuming for the sake of example that the computer does <math>10^{12}</math> operations each second, the program would run for about <math>4 \times 10^{10}</math> years, which is the same order of magnitude as the [[age of the universe]]. Even with a much faster computer, the program would only be useful for very small instances and in that sense the intractability of a problem is somewhat independent of technological progress. However, an exponential-time algorithm that takes <math>1.0001^n</math> operations is practical until <math>n</math> gets relatively large.

	Similarly, a polynomial time algorithm is not always practical. If its running time is, say, , it is unreasonable to consider it efficient and it is still useless except on small instances. Indeed, in practice even or algorithms are often impractical on realistic sizes of problems.		Similarly, a polynomial time algorithm is not always practical. If its running time is, say, <math>n^{15}</math>, it is unreasonable to consider it efficient and it is still useless except on small instances. Indeed, in practice even <math>n^3</math> or <math>n^2</math> algorithms are often impractical on realistic sizes of problems.

	==Continuous complexity theory==		==Continuous complexity theory==

2600:100A:B051:BEF8:0:17:43A1:1F01: I fixed all the problems

2025-03-29T15:21:41Z

I fixed all the problems

← Previous revision		Revision as of 15:21, 29 March 2025
Line 226:		Line 226:
	It is suspected that <math>P</math> and <math>BPP</math> are equal. However, it is currently open if <math>BPP = NEXP</math>.		It is suspected that <math>P</math> and <math>BPP</math> are equal. However, it is currently open if <math>BPP = NEXP</math>.

			==Intractability==
	==Intractability== <!-- This section is linked from [[Minimax]], [[Intractability]], [[Intractable]] -->
		⚫	A problem that can theoretically be solved, but requires impractical and finite resources (e.g., time) to do so, is known as an . Conversely, a problem that can be solved in practice is called a , literally "a problem that can be handled". The term ''infeasible'' (literally "cannot be done") is sometimes used interchangeably with ''intractable'', though this risks confusion with a feasible solution in mathematical optimization.
	{{See also\|Combinatorial explosion}}
⚫	A problem that can theoretically be solved, but requires impractical and finite resources (e.g., time) to do so, is known as an ~~'''''{{visible anchor\|intractable problem}}'''''~~.~~<ref>Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2007) [[Introduction to Automata Theory, Languages, and Computation]], Addison Wesley, Boston/San Francisco/New York (page 368)</ref>~~ Conversely, a problem that can be solved in practice is called a ~~'''''{{visible anchor\|tractable problem}}'''''~~, literally "a problem that can be handled". The term ''~~[[wikt:~~infeasible~~\|infeasible]]~~'' (literally "cannot be done") is sometimes used interchangeably with ''~~[[wikt:~~intractable~~\|intractable]]~~'',<ref>{{cite book \|title=Algorithms and Complexity \|first=Gerard \|last=Meurant \|year=2014 \|isbn=978-0-08093391-7 \|page=[https://books.google.com/books?id=6WriBQAAQBAJ&pg=PA4 p. 4]\|publisher=Elsevier }}</ref> though this risks confusion with a [[feasible solution]] in [[mathematical optimization]].~~<ref>~~
	{{cite book
	\|title=Writing for Computer Science
	\|first=Justin
	\|last=Zobel
	\|page=[https://books.google.com/books?id=LWCYBgAAQBAJ&pg=PA132 132]
	\|year=2015
	\|publisher=Springer
	\|isbn=978-1-44716639-9
	}}</ref>

	Tractable problems are frequently identified with problems that have polynomial-time solutions (~~<math>P</math>~~, ~~<math>PTIME</math>~~); this is known as the [[Cobham–Edmonds thesis]]. Problems that are known to be intractable in this sense include those that are [[EXPTIME]]-hard. If ~~<math>NP</math>~~ is not the same as ~~<math>P</math>~~, then [[NP-hard]] problems are also intractable in this sense.		Tractable problems are frequently identified with problems that have polynomial-time solutions (, ); this is known as the Cobham–Edmonds thesis. Problems that are known to be intractable in this sense include those that are EXPTIME-hard. If is not the same as , then NP-hard problems are also intractable in this sense.

	However, this identification is inexact: a polynomial-time solution with large degree or large leading coefficient grows quickly, and may be impractical for practical size problems; conversely, an exponential-time solution that grows slowly may be practical on realistic input, or a solution that takes a long time in the worst case may take a short time in most cases or the average case, and thus still be practical. Saying that a problem is not in ~~<math>P</math>~~ does not imply that all large cases of the problem are hard or even that most of them are. For example, the decision problem in [[Presburger arithmetic]] has been shown not to be in ~~<math>P</math>~~, yet algorithms have been written that solve the problem in reasonable times in most cases. Similarly, algorithms can solve the NP-complete [[knapsack problem]] over a wide range of sizes in less than quadratic time and [[SAT ~~solver]]s~~ routinely handle large instances of the NP-complete [[Boolean satisfiability problem]].		However, this identification is inexact: a polynomial-time solution with large degree or large leading coefficient grows quickly, and may be impractical for practical size problems; conversely, an exponential-time solution that grows slowly may be practical on realistic input, or a solution that takes a long time in the worst case may take a short time in most cases or the average case, and thus still be practical. Saying that a problem is not in does not imply that all large cases of the problem are hard or even that most of them are. For example, the decision problem in Presburger arithmetic has been shown not to be in , yet algorithms have been written that solve the problem in reasonable times in most cases. Similarly, algorithms can solve the NP-complete knapsack problem over a wide range of sizes in less than quadratic time and SAT solvers routinely handle large instances of the NP-complete Boolean satisfiability problem.

	To see why exponential-time algorithms are generally unusable in practice, consider a program that makes ~~<math>2^n</math>~~ operations before halting. For small ~~<math>n</math>~~, say 100, and assuming for the sake of example that the computer does ~~<math>10^{12}</math>~~ operations each second, the program would run for about ~~<math>4 \times 10^{10}</math>~~ years, which is the same order of magnitude as the [[age of the universe]]. Even with a much faster computer, the program would only be useful for very small instances and in that sense the intractability of a problem is somewhat independent of technological progress. However, an exponential-time algorithm that takes ~~<math>1.0001^n</math>~~ operations is practical until ~~<math>n</math>~~ gets relatively large.		To see why exponential-time algorithms are generally unusable in practice, consider a program that makes operations before halting. For small , say 100, and assuming for the sake of example that the computer does operations each second, the program would run for about years, which is the same order of magnitude as the age of the universe. Even with a much faster computer, the program would only be useful for very small instances and in that sense the intractability of a problem is somewhat independent of technological progress. However, an exponential-time algorithm that takes operations is practical until gets relatively large.

	Similarly, a polynomial time algorithm is not always practical. If its running time is, say, ~~<math>n^{15}</math>~~, it is unreasonable to consider it efficient and it is still useless except on small instances. Indeed, in practice even ~~<math>n^3</math>~~ or ~~<math>n^2</math>~~ algorithms are often impractical on realistic sizes of problems.		Similarly, a polynomial time algorithm is not always practical. If its running time is, say, , it is unreasonable to consider it efficient and it is still useless except on small instances. Indeed, in practice even or algorithms are often impractical on realistic sizes of problems.

	==Continuous complexity theory==		==Continuous complexity theory==

Jorjulio: In second (and last) paragraph under "Problem instances", changed "15" to "14" to agree with adjacent map and its caption.

2025-03-15T12:05:09Z

In second (and last) paragraph under "Problem instances", changed "15" to "14" to agree with adjacent map and its caption.

← Previous revision		Revision as of 12:05, 15 March 2025
Line 13:		Line 13:
	A [[computational problem]] can be viewed as an infinite collection of ''instances'' together with a set (possibly empty) of ''solutions'' for every instance. The input string for a computational problem is referred to as a problem instance, and should not be confused with the problem itself. In computational complexity theory, a problem refers to the abstract question to be solved. In contrast, an instance of this problem is a rather concrete utterance, which can serve as the input for a decision problem. For example, consider the problem of [[primality testing]]. The instance is a number (e.g., 15) and the solution is "yes" if the number is prime and "no" otherwise (in this case, 15 is not prime and the answer is "no"). Stated another way, the ''instance'' is a particular input to the problem, and the ''solution'' is the output corresponding to the given input.		A [[computational problem]] can be viewed as an infinite collection of ''instances'' together with a set (possibly empty) of ''solutions'' for every instance. The input string for a computational problem is referred to as a problem instance, and should not be confused with the problem itself. In computational complexity theory, a problem refers to the abstract question to be solved. In contrast, an instance of this problem is a rather concrete utterance, which can serve as the input for a decision problem. For example, consider the problem of [[primality testing]]. The instance is a number (e.g., 15) and the solution is "yes" if the number is prime and "no" otherwise (in this case, 15 is not prime and the answer is "no"). Stated another way, the ''instance'' is a particular input to the problem, and the ''solution'' is the output corresponding to the given input.

	To further highlight the difference between a problem and an instance, consider the following instance of the decision version of the [[travelling salesman problem]]: Is there a route of at most 2000 kilometres passing through all of Germany's 15 largest cities? The quantitative answer to this particular problem instance is of little use for solving other instances of the problem, such as asking for a round trip through all sites in [[Milan]] whose total length is at most 10 km. For this reason, complexity theory addresses computational problems and not particular problem instances.		To further highlight the difference between a problem and an instance, consider the following instance of the decision version of the [[travelling salesman problem]]: Is there a route of at most 2000 kilometres passing through all of Germany's 14 largest cities? The quantitative answer to this particular problem instance is of little use for solving other instances of the problem, such as asking for a round trip through all sites in [[Milan]] whose total length is at most 10 km. For this reason, complexity theory addresses computational problems and not particular problem instances.

	===Representing problem instances===		===Representing problem instances===

Ringo62: /* Complexity measures */

2025-02-01T08:36:56Z

Complexity measures

← Previous revision		Revision as of 08:36, 1 February 2025
Line 53:		Line 53:

	===Complexity measures===		===Complexity measures===
	For a precise definition of what it means to solve a problem using a given amount of time and space, a computational model such as the [[deterministic Turing machine]] is used. The ''time required'' by a deterministic Turing machine <math>M</math> on input <math>x</math> is the total number of state transitions, or steps, the machine makes before it halts and outputs the answer ("yes" or "no"). A Turing machine <math>M</math> is said to operate within time <math>f(n)</math> if the time required by <math>M</math> on each input of length <math>n</math> is at most <math>f(n)</math>. A decision problem <math>A</math> can be solved in time <math>f(n)</math> if there exists a Turing machine operating in time <math>f(n)</math> that solves the problem. Since complexity theory is interested in classifying problems based on their difficulty, one defines sets of problems based on some criteria. For instance, the set of problems solvable within time <math>f(n)</math> on a deterministic Turing machine is then denoted by [[DTIME]](<math>f(n)</math>).		For a precise definition of what it means to solve a problem using a given amount of time and space, a computational model such as the [[deterministic Turing machine]] is used. The time required by a deterministic Turing machine <math>M</math> on input <math>x</math> is the total number of state transitions, or steps, the machine makes before it halts and outputs the answer ("yes" or "no"). A Turing machine <math>M</math> is said to operate within time <math>f(n)</math> if the time required by <math>M</math> on each input of length <math>n</math> is at most <math>f(n)</math>. A decision problem <math>A</math> can be solved in time <math>f(n)</math> if there exists a Turing machine operating in time <math>f(n)</math> that solves the problem. Since complexity theory is interested in classifying problems based on their difficulty, one defines sets of problems based on some criteria. For instance, the set of problems solvable within time <math>f(n)</math> on a deterministic Turing machine is then denoted by [[DTIME]](<math>f(n)</math>).

	Analogous definitions can be made for space requirements. Although time and space are the most well-known complexity resources, any [[Complexity\|complexity measure]] can be viewed as a computational resource. Complexity measures are very generally defined by the [[Blum complexity axioms]]. Other complexity measures used in complexity theory include [[communication complexity]], [[circuit complexity]], and [[decision tree complexity]].		Analogous definitions can be made for space requirements. Although time and space are the most well-known complexity resources, any [[Complexity\|complexity measure]] can be viewed as a computational resource. Complexity measures are very generally defined by the [[Blum complexity axioms]]. Other complexity measures used in complexity theory include [[communication complexity]], [[circuit complexity]], and [[decision tree complexity]].

194.230.148.16: /* Upper and lower bounds on the complexity of problems */

2025-01-27T09:46:06Z

Upper and lower bounds on the complexity of problems

← Previous revision		Revision as of 09:46, 27 January 2025
Line 73:		Line 73:
	To classify the computation time (or similar resources, such as space consumption), it is helpful to demonstrate upper and lower bounds on the maximum amount of time required by the most efficient algorithm to solve a given problem. The complexity of an algorithm is usually taken to be its worst-case complexity unless specified otherwise. Analyzing a particular algorithm falls under the field of [[analysis of algorithms]]. To show an upper bound <math>T(n)</math> on the time complexity of a problem, one needs to show only that there is a particular algorithm with running time at most <math>T(n)</math>. However, proving lower bounds is much more difficult, since lower bounds make a statement about all possible algorithms that solve a given problem. The phrase "all possible algorithms" includes not just the algorithms known today, but any algorithm that might be discovered in the future. To show a lower bound of <math>T(n)</math> for a problem requires showing that no algorithm can have time complexity lower than <math>T(n)</math>.		To classify the computation time (or similar resources, such as space consumption), it is helpful to demonstrate upper and lower bounds on the maximum amount of time required by the most efficient algorithm to solve a given problem. The complexity of an algorithm is usually taken to be its worst-case complexity unless specified otherwise. Analyzing a particular algorithm falls under the field of [[analysis of algorithms]]. To show an upper bound <math>T(n)</math> on the time complexity of a problem, one needs to show only that there is a particular algorithm with running time at most <math>T(n)</math>. However, proving lower bounds is much more difficult, since lower bounds make a statement about all possible algorithms that solve a given problem. The phrase "all possible algorithms" includes not just the algorithms known today, but any algorithm that might be discovered in the future. To show a lower bound of <math>T(n)</math> for a problem requires showing that no algorithm can have time complexity lower than <math>T(n)</math>.

	Upper and lower bounds are usually stated using the [[big O notation]], which hides constant factors and smaller terms. This makes the bounds independent of the specific details of the computational model used. For instance, if <math>T(n) = 7n^2 + 15n + 40</math>, in big O notation one would write <math>T(n) = O(n^2)</math>.		Upper and lower bounds are usually stated using the [[big O notation]], which hides constant factors and smaller terms. This makes the bounds independent of the specific details of the computational model used. For instance, if <math>T(n) = 7n^2 + 15n + 40</math>, in big O notation one would write <math>T(n) \in O(n^2)</math>.


	==Complexity classes==		==Complexity classes==