Matches in DBpedia 2014 for { <http://dbpedia.org/resource/PPA_(complexity)> ?p ?o. }
Showing items 1 to 18 of
18
with 100 items per page.
- PPA_(complexity) abstract "PPA is a complexity class, standing for "Polynomial Parity Argument" (on a graph). Introduced by Christos Papadimitriou in 1994 (page 528), PPA is a subclass of TFNP. It is a class of search problems that can be shown to be total by an application of the handshaking lemma: any undirected graph that has a vertex whose degree is an odd number must have some other vertex whose degree is an odd number. This observation means that if we are given a graph and an odd-degree vertex, and we are asked to find some other odd-degree vertex, then we are searching for something that is guaranteed to exist (so, we have a total search problem).PPA is defined as follows. Suppose we have a graph on whose vertices are -bit binary strings, and the graph is represented by a polynomial-sized circuit that takes a vertex as input and outputs its neighbors. (Note that this allows us to represent an exponentially-large graph on which we can efficiently perform local exploration.) Suppose furthermore that a specific vertex (say the all-zeroes vector) has an odd number of neighbors. We are required to find another odd-degree vertex. Note that this problem is in NP—given a solution it may be verified using the circuit that the solution is correct. A function computation problem belongs to PPA if it admits a polynomial-time reduction to this graph search problem. A problem is complete for the class PPA if in addition, this graph search problem is reducible to that problem.PPA contains PPAD as a subclass. This is because the corresponding problem that defines PPAD, known as END OF THE LINE, can be reduced (in a straightforward way) to the above search for an additional odd-degree vertex (essentially, just by ignoring the directions of the edges in END OF THE LINE).There is an un-oriented version of the Sperner lemma known to be complete for PPA. The problem of searching for a second Hamiltonian cycle on a 3-regular graph is a member of PPA, but is not known to be complete for PPA.".
- PPA_(complexity) wikiPageID "25494843".
- PPA_(complexity) wikiPageRevisionID "532136956".
- PPA_(complexity) hasPhotoCollection PPA_(complexity).
- PPA_(complexity) subject Category:Complexity_classes.
- PPA_(complexity) type Abstraction100002137.
- PPA_(complexity) type Class107997703.
- PPA_(complexity) type Collection107951464.
- PPA_(complexity) type ComplexityClasses.
- PPA_(complexity) type Group100031264.
- PPA_(complexity) comment "PPA is a complexity class, standing for "Polynomial Parity Argument" (on a graph). Introduced by Christos Papadimitriou in 1994 (page 528), PPA is a subclass of TFNP. It is a class of search problems that can be shown to be total by an application of the handshaking lemma: any undirected graph that has a vertex whose degree is an odd number must have some other vertex whose degree is an odd number.".
- PPA_(complexity) label "PPA (complexity)".
- PPA_(complexity) sameAs m.09rts3_.
- PPA_(complexity) sameAs Q7120092.
- PPA_(complexity) sameAs Q7120092.
- PPA_(complexity) sameAs PPA_(complexity).
- PPA_(complexity) wasDerivedFrom PPA_(complexity)?oldid=532136956.
- PPA_(complexity) isPrimaryTopicOf PPA_(complexity).