Encyclopedia > P > Parity P
Parity P
In computational complexity theory, the complexity class {oplus}mathbf{P} (pronounced "parity P") is the class of decision problems solvable by a nondeterministic Turing machine in polynomial time, where the acceptance condition is that the number of accepting computation paths is odd. An example of a {oplus}mathbf{P} problem is "does a given graph have an odd number of perfect matchings?
Information are taken from Wikipedia, the open encyclopedia, to which contribute many volunteers from around the whole world. Texts are available under the following conditions GNU Free Documentation License.
Encyklopedie (cz) Encyklopédia (sk) Enzyklopädie (de)