About: Parity P     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : dbo:Disease, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon
http://dbpedia.demo.openlinksw.com/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FParity_P&invfp=IFP_OFF&sas=SAME_AS_OFF

In computational complexity theory, the complexity class ⊕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 ⊕P problem is "does a given graph have an odd number of perfect matchings?" The class was defined by Papadimitriou and Zachos in 1983.

AttributesValues
rdf:type
rdfs:label
  • ⊕P (ca)
  • Parity P (en)
rdfs:comment
  • En teoria de la complexitat, la classe de complexitat ⊕P (pronunciada "P paritat") és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing no determinista en temps polinòmic, on la condició d'acceptar és que el nombre de camins de computació sigui senar. També es pot definir com la classe de problemes de decisió que resolt una màquina de Turing no determinista i que: * si el nombre de camins és senar, la resposta es SI * si el nombre de camins és parell, la resposta es NO (ca)
  • In computational complexity theory, the complexity class ⊕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 ⊕P problem is "does a given graph have an odd number of perfect matchings?" The class was defined by Papadimitriou and Zachos in 1983. (en)
dcterms:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
sameAs
dbp:wikiPageUsesTemplate
has abstract
  • En teoria de la complexitat, la classe de complexitat ⊕P (pronunciada "P paritat") és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing no determinista en temps polinòmic, on la condició d'acceptar és que el nombre de camins de computació sigui senar. També es pot definir com la classe de problemes de decisió que resolt una màquina de Turing no determinista i que: * si el nombre de camins és senar, la resposta es SI * si el nombre de camins és parell, la resposta es NO La classe ⊕P és una classe comptadora, i es pot veure com trobar el bit menys significatiu de la resposta del problema corresponent a la classe #P. El problema de trobar el bit més significatiu és a la classe PP. (ca)
  • In computational complexity theory, the complexity class ⊕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 ⊕P problem is "does a given graph have an odd number of perfect matchings?" The class was defined by Papadimitriou and Zachos in 1983. ⊕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 ⊕P; for example, there is a relativized universe (see oracle machine) where P = ⊕P ≠ NP = PP = EXPTIME, as shown by Beigel, Buhrman, and Fortnow in 1998. While Toda's theorem shows that PPP contains PH, P⊕P is not known to even contain NP. However, the first part of the proof of Toda's theorem shows that BPP⊕P contains PH. Lance Fortnow has written a concise proof of this theorem. ⊕P contains the graph isomorphism problem, and in fact this problem is low for ⊕P. It also trivially contains UP, since all problems in UP have either zero or one accepting paths. More generally, ⊕P is low for itself, meaning that such a machine gains no power from being able to solve any ⊕P problem instantly. The ⊕ symbol in the name of the class may be a reference to use of the symbol ⊕ 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. (en)
gold:hypernym
prov:wasDerivedFrom
page length (characters) of wiki page
foaf:isPrimaryTopicOf
is Link from a Wikipage to another Wikipage of
is Wikipage redirect of
is foaf:primaryTopic of
Faceted Search & Find service v1.17_git139 as of Feb 29 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 59 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software