P - Revision history

Vipul: /* Formal definitions */

2011-12-28T01:49:14Z

Formal definitions

← Older revision		Revision as of 01:49, 28 December 2011
Line 10:		Line 10:
	! No. !! Shorthand !! Definition		! No. !! Shorthand !! Definition
	\|-		\|-
	\| 1 \|\| single tape Turing machine \|\| there exists a [[Turing machine]] using a single tape for the input (and that allows for both reading and writing on the tape) that accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.		\| 1 \|\| single tape Turing machine \|\| there exists a (deterministic) [[Turing machine]] using a single tape for the input (and that allows for both reading and writing on the tape) that accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.
	\|-		\|-
	\| 2 \|\| multiple tape Turing machine \|\| there exists a [[Turing machine]] with access to finitely many read/write tapes, including one for the input (and that allows for both reading and writing on the tape) that accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.		\| 2 \|\| multiple tape Turing machine \|\| there exists a (deterministic) [[Turing machine]] with access to finitely many read/write tapes, including one for the input (and that allows for both reading and writing on the tape) that accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.
	\|-		\|-
	\| 3 \|\| machine with log-time random access \|\| there exists a program that can perform random access on a read/write memory in time logarithmic to the amount of memory used, ''and'' the program accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.		\| 3 \|\| machine with log-time random access \|\| there exists a program that can perform random access on a read/write memory in time logarithmic to the amount of memory used, ''and'' the program accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.
	\|}		\|}

	Loosely speaking, a language is in P if there is a polynomial time algorithm for recognition of the language.		Loosely speaking, a language is in P if there is a polynomial time algorithm for recognition of the language.

	==Key features==		==Key features==

Vipul: /* Loose definition */

2011-12-28T01:48:45Z

Loose definition

← Older revision		Revision as of 01:48, 28 December 2011
Line 3:		Line 3:
	===Loose definition===		===Loose definition===

	The '''polynomial time''' complexity class, denoted '''PTIME''' or '''P''', is a [[time complexity class]] defined loosely as follows. A language is said to be in the polynomial time complexity class if there is a polynomial time algorithm for determining whether a string is in the language. Here, the ''polynomial'' is an ''upper bound'' on the time taken, it is in terms of the ''length'' of the string, it is a ''worst case'' measure (i.e., worst case over all possible strings of the length), and we are interested in the ''asymptotic'' behavior for sufficiently large strings.		The '''polynomial time''' complexity class, denoted '''PTIME''' or '''P''', is a [[deterministic time complexity class]] defined loosely as follows. A language is said to be in the polynomial time complexity class if there is a polynomial time algorithm for determining whether a string is in the language. Here, the ''polynomial'' is an ''upper bound'' on the time taken, it is in terms of the ''length'' of the string, it is a ''worst case'' measure (i.e., worst case over all possible strings of the length), and we are interested in the ''asymptotic'' behavior for sufficiently large strings.

	===Formal definitions===		===Formal definitions===

Vipul at 01:48, 28 December 2011

2011-12-28T01:48:15Z

← Older revision		Revision as of 01:48, 28 December 2011
Line 1:		Line 1:
	==Definition==		==Definition==

	The '''polynomial time''' complexity class, denoted '''PTIME''' or '''P''', is defined as follows. A language ~~<math>L</math>~~ is said to be in the polynomial time complexity class if it ~~satisfies~~ the ~~following equivalent conditions:~~		===Loose definition===

			The '''polynomial time''' complexity class, denoted '''PTIME''' or '''P''', is a [[time complexity class]] defined loosely as follows. A language is said to be in the polynomial time complexity class if there is a polynomial time algorithm for determining whether a string is in the language. Here, the ''polynomial'' is an ''upper bound'' on the time taken, it is in terms of the ''length'' of the string, it is a ''worst case'' measure (i.e., worst case over all possible strings of the length), and we are interested in the ''asymptotic'' behavior for sufficiently large strings.

			===Formal definitions===

	{\| class="sortable" border="1"		{\| class="sortable" border="1"

Vipul: /* Larger complexity classes */

2011-12-27T20:52:01Z

Larger complexity classes

← Older revision		Revision as of 20:52, 27 December 2011
Line 46:		Line 46:
	\|-		\|-
	\| [[Contained in::co-RP]] \|\| complement of a language in RP. \|\| [[co-RP contains P]] \|\| open problem -- both separation and collapse plausible \|\| {{intermediate complexity classes\|P\|co-RP}}		\| [[Contained in::co-RP]] \|\| complement of a language in RP. \|\| [[co-RP contains P]] \|\| open problem -- both separation and collapse plausible \|\| {{intermediate complexity classes\|P\|co-RP}}
			\|-
			\| [[Contained in::ZPP]] (zero-error probabilistic polynomial time) \|\| intersection of RP and co-RP \|\| \|\| \|\| {{intermediate complexity classes\|P\|ZPP}}
	\|-		\|-
	\| [[Contained in::BPP]] (bounded-error probabilistic polynomial time)\|\| allows use of random bits, probability of errors both ways. \|\| [[BPP contains P]] \|\| open problem -- both separation and collapse plausible \|\| {{intermediate complexity classes\|P\|BPP}}		\| [[Contained in::BPP]] (bounded-error probabilistic polynomial time)\|\| allows use of random bits, probability of errors both ways. \|\| [[BPP contains P]] \|\| open problem -- both separation and collapse plausible \|\| {{intermediate complexity classes\|P\|BPP}}

Vipul: /* Key features */

2011-12-27T20:50:20Z

Key features

← Older revision		Revision as of 20:50, 27 December 2011
Line 29:		Line 29:

	The definition of the complexity class depends only on the asymptotic nature of the time taken as a function of the length of the string. In particular, if two languages have cofinite intersection (i.e., they are the same except for finitely many strings in each language that is not in the other) then one is in P if and only if the other is in P.		The definition of the complexity class depends only on the asymptotic nature of the time taken as a function of the length of the string. In particular, if two languages have cofinite intersection (i.e., they are the same except for finitely many strings in each language that is not in the other) then one is in P if and only if the other is in P.

			===Worst case rather than average case===

			{{further\|[[Worst case versus average case]]}}

			As for most complexity classes, the definition of polynomial time must take into account the ''worst case'' time taken among possible input strings, including both the strings that are in the language and the strings that are not in the language. We are not trying to compute the ''average'' time taken among all possible input strings. It is true that a polynomial time algorithm must be polynomial time on average as well, but the converse need not be true.

	==Relation with other complexity classes==		==Relation with other complexity classes==

Vipul: /* Smaller complexity classes */

2011-12-27T20:36:21Z

Smaller complexity classes

@@ Line 74: / Line 74: @@
 |-
 | [[Contains::L]] (deterministic logspace) || in addition to read-only input, read/write workspace of length bounded by a constant times the logarithm of the length of the input string. Must be used ''nondeterministically'' || || || || {{intermediate complexity classes|L|P}}
 |}

Vipul: /* Larger complexity classes */

2011-12-27T20:32:27Z

Larger complexity classes

Vipul: /* Larger complexity classes */

2011-12-27T20:28:19Z

Larger complexity classes

@@ Line 40: / Line 40: @@
 |-
 | [[Contained in::co-RP]] || complement of a language in RP. || [[co-RP contains P]] || open problem -- both separation and collapse plausible || {{intermediate complexity classes|P|co-RP}}
 |-
 | [[Contained in::NP]] || allows coming up magically with a string that helps provide "proof" || [[NP contains P]] || [[P equals NP conjecture]]. Separation is widely believed, i.e., it is believed that P is not equal to NP. || {{intermediate complexity classes|P|NP}}
@@ Line 52: / Line 56: @@
 |-
 | [[Contained in::Delta2P]] || || || || {{intermediate complexity classes|P|Delta2P}}
 |}

Vipul at 20:23, 27 December 2011

2011-12-27T20:23:28Z

← Older revision		Revision as of 20:23, 27 December 2011
Line 13:		Line 13:
	\|}		\|}

	Loosely speaking, a language is in P if there is a polynomial time algorithm for recognition of the language. The [[Church-Turing thesis]] states the notion of ''polynomial time'' is robust and does not change based on the nature of the machine, ~~although~~ the ''degree'' of the polynomial that can be achieved does depend on the machine specifications (so some algorithms may be much faster with log-time random access than with sequential access as for the tapes in a Turing machine).		Loosely speaking, a language is in P if there is a polynomial time algorithm for recognition of the language.
			==Key features==

			===Robustness based on complexity-theoretic Church-Turing thesis===

			The [[complexity-theoretic Church-Turing thesis]] states the notion of ''polynomial time'' is robust and does not change based on the nature of the machine, as long as we are dealing with ''deterministic'' machines, and we do not have access to random oracles or quantum computing.

			However, the ''degree'' of the polynomial that can be achieved does depend on the machine specifications (so some algorithms may be much faster with log-time random access than with sequential access as for the tapes in a Turing machine). There may be an algorithm on one kind of machine that takes time <math>O(N\log N)</math> but on another machine takes time <math>O(N^2)</math> where <math>N</math> is the length of the string.

			===Independence of algorithm from length of the string===

			The Turing machine, or more generally the program or algorithm used to determine whether a string is in the language, is ''independent'' of the length of the string. (Internally, it may make cases based on the length of the string, but that's a different matter). A related complexity class where the algorithm can take polynomial-sized advice based on the length of the string is termed [[P/poly]].

			===Asymptotic nature===

			The definition of the complexity class depends only on the asymptotic nature of the time taken as a function of the length of the string. In particular, if two languages have cofinite intersection (i.e., they are the same except for finitely many strings in each language that is not in the other) then one is in P if and only if the other is in P.

			==Relation with other complexity classes==

			===Larger complexity classes===

			{\| class="sortable" border="1"
			! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes
			\|-
			\| [[Contained in::RP]] \|\| allows use of random bits. In polynomial time, the algorithm returns a ''Yes'' or ''Maybe'' with ''Yes'' indicating that the string is definitely in the language. Probability of saying ''Maybe'' if the string is in the language is bounded away from 1. \|\| [[RP contains P]] \|\| open problem -- both separation and collapse plausible \|\| {{intermediate complexity classes\|P\|RP}}
			\|-
			\| [[Contained in::co-RP]] \|\| complement of a language in RP. \|\| [[co-RP contains P]] \|\| open problem -- both separation and collapse plausible \|\| {{intermediate complexity classes\|P\|co-RP}}
			\|-
			\| [[Contained in::NP]] \|\| allows coming up magically with a string that helps provide "proof" \|\| [[NP contains P]] \|\| [[P equals NP conjecture]]. Separation is widely believed, i.e., it is believed that P is not equal to NP. \|\| {{intermediate complexity classes\|P\|NP}}
			\|-
			\| [[Contained in::co-NP]] \|\| complement of a language in NP. \|\| [[co-NP contains P]] \|\| equivalent to [[P equals NP conjecture]] \|\| {{intermediate complexity classes\|P\|co-NP}}
			\|-
			\| [[Contained in::NP intersect co-NP]] \|\| the language is both in NP and co-NP \|\| [[NP intersect co-NP contains P]] \|\| Unknown, separation plausible but unclear. \|\| {{intermediate complexity classes\|P\|NP intersect co-NP}}
			\|-
			\| [[Contained in::Sigma2P]] \|\| \|\| \|\| \|\| {{intermediate complexity classes\|P\|Sigma2P}}
			\|-
			\| [[Contained in::Pi2P]] \|\| \|\| \|\| \|\| {{intermediate complexity classes\|P\|Pi2P}}
			\|-
			\| [[Contained in::Delta2P]] \|\| \|\| \|\| \|\| {{intermediate complexity classes\|P\|Delta2P}}
			\|}

Vipul: moved Polynomial time to P over redirect

2011-12-27T20:07:24Z

moved Polynomial time to P over redirect

← Older revision	Revision as of 20:07, 27 December 2011
(No difference)

← Older revision		Revision as of 20:32, 27 December 2011
Line 37:		Line 37:
	! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes		! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes
	\|-		\|-
	\| [[Contained in::RP]] \|\| allows use of random bits. In polynomial time, the algorithm returns a ''Yes'' or ''Maybe'' with ''Yes'' indicating that the string is definitely in the language. Probability of saying ''Maybe'' if the string is in the language is bounded away from 1. \|\| [[RP contains P]] \|\| open problem -- both separation and collapse plausible \|\| {{intermediate complexity classes\|P\|RP}}		\| [[Contained in::RP]] (randomized polynomial time) \|\| allows use of random bits. In polynomial time, the algorithm returns a ''Yes'' or ''Maybe'' with ''Yes'' indicating that the string is definitely in the language. Probability of saying ''Maybe'' if the string is in the language is bounded away from 1. \|\| [[RP contains P]] \|\| open problem -- both separation and collapse plausible \|\| {{intermediate complexity classes\|P\|RP}}
	\|-		\|-
	\| [[Contained in::co-RP]] \|\| complement of a language in RP. \|\| [[co-RP contains P]] \|\| open problem -- both separation and collapse plausible \|\| {{intermediate complexity classes\|P\|co-RP}}		\| [[Contained in::co-RP]] \|\| complement of a language in RP. \|\| [[co-RP contains P]] \|\| open problem -- both separation and collapse plausible \|\| {{intermediate complexity classes\|P\|co-RP}}
	\|-		\|-
	\| [[Contained in::BPP]] \|\| allows use of random bits, probability of errors both ways. \|\| [[BPP contains P]] \|\| open problem -- both separation and collapse plausible \|\| {{intermediate complexity classes\|P\|BPP}}		\| [[Contained in::BPP]] (bounded-error probabilistic polynomial time)\|\| allows use of random bits, probability of errors both ways. \|\| [[BPP contains P]] \|\| open problem -- both separation and collapse plausible \|\| {{intermediate complexity classes\|P\|BPP}}
	\|-		\|-
	\| [[Contained in::PP]] \|\| error rates are allowed to come close to half. \|\| [[PP contains P]] \|\| \|\| {{intermediate complexity classes\|P\|PP}}		\| [[Contained in::PP]] (probabilistic polynomial time) \|\| error rates are allowed to come close to half. \|\| [[PP contains P]] \|\| \|\| {{intermediate complexity classes\|P\|PP}}
	\|-		\|-
	\| [[Contained in::NP]] \|\| allows coming up magically with a string that helps provide "proof" \|\| [[NP contains P]] \|\| [[P equals NP conjecture]]. Separation is widely believed, i.e., it is believed that P is not equal to NP. \|\| {{intermediate complexity classes\|P\|NP}}		\| [[Contained in::NP]] (nondeterministic polynomial time) \|\| allows coming up magically with a string that helps provide "proof" \|\| [[NP contains P]] \|\| [[P equals NP conjecture]]. Separation is widely believed, i.e., it is believed that P is not equal to NP. \|\| {{intermediate complexity classes\|P\|NP}}
	\|-		\|-
	\| [[Contained in::co-NP]] \|\| complement of a language in NP. \|\| [[co-NP contains P]] \|\| equivalent to [[P equals NP conjecture]] \|\| {{intermediate complexity classes\|P\|co-NP}}		\| [[Contained in::co-NP]] \|\| complement of a language in NP. \|\| [[co-NP contains P]] \|\| equivalent to [[P equals NP conjecture]] \|\| {{intermediate complexity classes\|P\|co-NP}}
Line 57:		Line 57:
	\| [[Contained in::Delta2P]] \|\| \|\| \|\| \|\| {{intermediate complexity classes\|P\|Delta2P}}		\| [[Contained in::Delta2P]] \|\| \|\| \|\| \|\| {{intermediate complexity classes\|P\|Delta2P}}
	\|-		\|-
	\| [[Contained in::PH]] \|\| \|\| \|\| \|\|{{intermediate complexity classes\|P\|PH}}		\| [[Contained in::PH]] (polynomial hierarchy) \|\| \|\| \|\| \|\|{{intermediate complexity classes\|P\|PH}}
	\|-		\|-
	\| [[Contained in::PSPACE]] \|\| algorithm that requires polynomial space to write on in addition to the read-only input. \|\| \|\| \|\| {{intermediate complexity classes\|P\|PSPACE}}		\| [[Contained in::PSPACE]] (polynomial space)\|\| algorithm that requires polynomial space to write on in addition to the read-only input. \|\| \|\| \|\| {{intermediate complexity classes\|P\|PSPACE}}
	\|-		\|-
	\| [[Contained in::Quasipolynomial time]] (sometimes abbreviated QP, but that might be confused with quantum polynomial time) \|\| time taken is exponential in a polynomial of the logarithm of the input length \|\| \|\| \|\| {{intermediate complexity classes\|P\|Quasipolynomial time}}		\| [[Contained in::Quasipolynomial time]] (sometimes abbreviated QP, but that might be confused with quantum polynomial time) \|\| time taken is exponential in a polynomial of the logarithm of the input length \|\| \|\| \|\| {{intermediate complexity classes\|P\|Quasipolynomial time}}
	\|-		\|-
	\| [[Contained in::SUBEXP]] \|\| \|\| \|\| \|\| {{intermediate complexity classes\|P\|SUBEXP}}		\| [[Contained in::SUBEXP]] (subexponential time) \|\| \|\| \|\| \|\| {{intermediate complexity classes\|P\|SUBEXP}}
			\|}

			===Smaller complexity classes===

			{\| class="sortable" border="1"
			! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes
			\|-
			\| [[Contains::NL]] (nondeterministic logspace) \|\| in addition to read-only input, read/write workspace of length bounded by a constant times the logarithm of the length of the input string. Can be used ''nondeterministically'' \|\| \|\| \|\| \|\| {{intermediate complexity classes\|NL\|P}}
			\|-
			\| [[Contains::L]] (deterministic logspace) \|\| in addition to read-only input, read/write workspace of length bounded by a constant times the logarithm of the length of the input string. Must be used ''nondeterministically'' \|\| \|\| \|\| \|\| {{intermediate complexity classes\|L\|P}}
	\|}		\|}