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?" The class was defined by Papadimitriou and Zachos in 1983.

{oplus}mathbf{P} is a counting class, and can be seen as finding the least significant bit of the answer to the corresponding #P problem. The problem of finding the most significant bit is in PP. PP is believed to be a considerably harder class than {oplus}mathbf{P}; for example, there is a relativized universe (see oracle machine) where P = {oplus}mathbf{P} ≠ NP = PP = EXPTIME, as shown by Beigel, Buhrman, and Fortnow in 1998. Furthermore, PPP contains PH, whereas mathbf{P}^oplus}mathbf{P is not known to even contain NP.

{oplus}mathbf{P} contains the graph isomorphism problem, and in fact this problem is low for {oplus}mathbf{P}. It also trivially contains UP, since all problems in UP have either zero or one accepting paths. More generally, {oplus}mathbf{P} is low for itself, meaning that such a machine gains no power from being able to solve any {oplus}mathbf{P} problem instantly.

The oplus symbol in the name of the class may be a reference to use of the symbol oplus in Boolean algebra to refer the exclusive disjunction operator. This makes sense because if we consider "accepts" to be 1 and "not accepts" to be 0, the result of the machine is the exclusive disjunction of the results of each computation path.

References

* C. H. Papadimitriou and S. Zachos. [http://portal.acm.org/citation.cfm?id=720053 Two remarks on the power of counting] . In "Proceedings of the 6th GI Conference in Theoretical Computer Science", "Lecture Notes in Computer Science", volume 145, Springer-Verlag, pp. 269-276. 1983.
* [http://qwiki.caltech.edu/wiki/Complexity_Zoo#parityp Complexity Zoo: +P: Parity P]
* R. Beigel, H. Buhrman, and L. Fortnow. NP might not be as easy as detecting unique solutions. In "Proceedings of ACM STOC'98", pp. 203-208. 1998.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Parity — is a concept of equality of status or functional equivalence. It has several different specific definitions.* Parity (physics), the name of the symmetry of interactions under spatial inversion * Parity (mathematics) indicates whether a number is… …   Wikipedia

  • Parity — Par i*ty, n. [L. paritas, fr. par, paris, equal: cf. F. parit[ e]. See {Pair}, {Peer} an equal.] 1. The quality or condition of being equal or equivalent; a like state or degree; equality; equivalence; close correspondence; analogy; as, parity of …   The Collaborative International Dictionary of English

  • parity — I noun alikeness, analogy, approximation, balance, close correspondence, coequality, comparability, comparison, correlation, correspondence, equability, equality, equation, equilibrium, equipoise, equivalence, equivalency, identical value,… …   Law dictionary

  • parity — parity. Факт рождения ребенка; используется как количественный показатель при описании родословных <pedigree>: 0 живых детей нет (независимо от количества беременностей), 1, 2 и т.д. число родов (независимо от числа родившихся детей).… …   Молекулярная биология и генетика. Толковый словарь.

  • parity — (n.) 1570s, equality of rank or status, from M.Fr. parité, from L.L. paritas equality, from L. adj. par (gen. paris) equal (see PAIR (Cf. pair) (n.)). Meaning condition in which adversaries have equal resources is from 1955, originally in… …   Etymology dictionary

  • parity — [n] equality, balance adequation, affinity, agreement, analogy, approximation, closeness, coequality, conformity, congruity, consistency, correspondence, equal terms, equivalence, equivalency, likeness, nearness, par, parallelism, paraphernalia,… …   New thesaurus

  • parity — ► NOUN 1) equality or equivalence. 2) Mathematics the fact of being an even or an odd number. ORIGIN Latin paritas, from par equal …   English terms dictionary

  • parity — parity1 [par′ə tē] n. pl. parities [Fr parité < L paritas < par, equal: see PAR1] 1. the state or condition of being the same in power, value, rank, etc.; equality 2. resemblance; similarity 3. equivalence in value of one currency expressed …   English World dictionary

  • parity — For convertibles, level at which a convertible security s market price equals the aggregate value of the underlying common stock; value/worth of the convertible bond considered only as an equity instrument ( conversion ratio times common price).… …   Financial and business terms

  • parity — parity1 /par i tee/, n. 1. equality, as in amount, status, or character. 2. equivalence; correspondence; similarity; analogy. 3. Finance. a. equivalence in value in the currency of another country. b. equivalence in value at a fixed ratio between …   Universalium

  • parity —    In communications, a simple form of error checking that uses an extra or redundant bit after the data bits but before the stop bit or bits. Parity may be set as follows:    • Odd    Indicates that the sum of all the 1 bit is set to zero; if it …   Dictionary of networking

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”