Vipul at 21:02, 27 December 2011

2011-12-27T21:02:14Z

← Older revision		Revision as of 21:02, 27 December 2011
Line 6:		Line 6:

	This complexity class can also be defined as the intersection of the [[RP]] and [[co-RP]] complexity classes.		This complexity class can also be defined as the intersection of the [[RP]] and [[co-RP]] complexity classes.

			==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]] (randomized polynomial time) \|\| Unlike ZPP, there is no definitive ''No'' answer type here but only a ''Yes'' and a ''Maybe'' \|\| \|\| \|\| {{intermediate complexity classes\|ZPP\|RP}}
			\|-
			\| [[contained in::co-RP]] \|\| Unlike ZPP, there is no definitive ''Yes'' answer type here but only a ''No'' and a ''Maybe'' \|\| \|\| \|\| {{intermediate complexity classes\|ZPP\|co-RP}}
			\|-
			\| [[contained in::BPP]] (bounded-error probabilistic polynomial time) \|\| There are only ''maybe yes'' and ''maybe no'' answers, no definitive answers, but bounds on error rates \|\| \|\| \|\| {{intermediate complexity classes\|ZPP\|BPP}}
			\|-
			\| [[contained in::PP]] (probabilistic polynomial time) \|\| Like BPP, weaker bounds on error rates \|\| \|\| \|\| {{intermediate complexity classes\|ZPP\|PP}}
			\|-
			\| [[contained in::NP intersect co-NP]] \|\| \|\| \|\| \|\| {{intermediate complexity classes\|ZPP\|NP intersect co-NP}}
			\|-
			\| [[contained in::NP]] \|\| \|\| \|\| \|\|
			\|-
			\| [[contained in::co-NP]] \|\| \|\| \|\| \|\|
			\|}

			===Smaller complexity classes===

			{\| class="sortable" border="1"
			! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes
			\|-
			\| [[contains::P]] \|\| \|\| \|\| \|\|
			\|}

Vipul: Created page with "{{complexity class}} ==Definition== The '''zero-error probabilistic polynomial time''' complexity class, abbreviated '''ZPP''', is defined as follows. A language $L$ ..."

2011-12-27T20:56:01Z

Created page with "{{complexity class}} ==Definition== The '''zero-error probabilistic polynomial time''' complexity class, abbreviated '''ZPP''', is defined as follows. A language <math>L</math>..."

New page

{{complexity class}}

==Definition==

The '''zero-error probabilistic polynomial time''' complexity class, abbreviated '''ZPP''', is defined as follows. A language <math>L</math> is in ZPP if there exists a [[Turing machine]] that has access to a random oracle and runs in polynomial time and has one of three outputs: ''Yes'', ''No'', and ''Undecided''. If the output is ''Yes'', the string is in <math>L</math>. If the output is ''No'', the string is not in <math>L</math>. if the output is ''Undecided'', then the string may or may not be in <math>L</math>. Further, for any fixed choice of input string, the probability of returning ''Maybe'' is bounded from above by a number strictly less than 1.

This complexity class can also be defined as the intersection of the [[RP]] and [[co-RP]] complexity classes.

ZPP - Revision history

Vipul at 21:02, 27 December 2011

Vipul: Created page with "{{complexity class}} ==Definition== The '''zero-error probabilistic polynomial time''' complexity class, abbreviated '''ZPP''', is defined as follows. A language L..."

Vipul: Created page with "{{complexity class}} ==Definition== The '''zero-error probabilistic polynomial time''' complexity class, abbreviated '''ZPP''', is defined as follows. A language $L$ ..."