About: PP (complexity)

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: PP (complexity) Goto Sponge NotDistinct Permalink

An Entity of Type : dbo:Disease, within Data Space : el.dbpedia.org associated with source document(s)

In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time. The complexity class was defined by Gill in 1977.

Attributes	Values
rdf:type	disease
rdfs:label	PP (complexity) (en)
rdfs:comment	In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time. The complexity class was defined by Gill in 1977. (en)
sameAs	PP (complexity) PP (complexity)
dbp:wikiPageUsesTemplate	dbt:ECCC dbt:Anchor dbt:Cite_book dbt:Cite_journal dbt:Reflist dbt:Short_description dbt:ComplexityClasses dbt:CZoo
Subject	Probabilistic complexity classes Quantum complexity theory
gold:hypernym	Problems
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/PP_(complexity)?oldid=1040620532&ns=0
Wikipage page ID	659322 (xsd:integer)
page length (characters) of wiki page	15521 (xsd:nonNegativeInteger)
Wikipage revision ID	1040620532 (xsd:integer)
has abstract	In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time. The complexity class was defined by Gill in 1977. If a decision problem is in PP, then there is an algorithm for it that is allowed to flip coins and make random decisions. It is guaranteed to run in polynomial time. If the answer is YES, the algorithm will answer YES with probability more than 1/2. If the answer is NO, the algorithm will answer YES with probability less than or equal to 1/2. In more practical terms, it is the class of problems that can be solved to any fixed degree of accuracy by running a randomized, polynomial-time algorithm a sufficient (but bounded) number of times. Turing machines that are polynomially-bound and probabilistic are characterized as PPT, which stands for probabilistic polynomial-time machines. This characterization of Turing machines does not require a bounded error probability. Hence, PP is the complexity class containing all problems solvable by a PPT machine with an error probability of less than 1/2. An alternative characterization of PP is the set of problems that can be solved by a nondeterministic Turing machine in polynomial time where the acceptance condition is that a majority (more than half) of computation paths accept. Because of this some authors have suggested the alternative name Majority-P. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/PP_(complexity)
is Wikipage redirect of	PP (complexity class) PP (class) PQP Probabilistic Polynomial-Time Probabilistic Polynomial-time Probabilistic Polynomial Time Probabilistic polynomial-time Probabilistic polynomial-time (PPT) Probabilistic polynomial time Probabilistic polynomial time (PPT)
is Link from a Wikipage to another Wikipage of	ACC0 AWPP (complexity) Accumulator (cryptography) Arthur–Merlin protocol BPL (complexity) BPP (complexity) BQP Boolean satisfiability problem Monte Carlo algorithm Boson sampling Naor–Reingold pseudorandom function Ciphertext indistinguishability Circuit complexity Complexity class Algorithmic complexity List of complexity classes IP (complexity) Indistinguishability obfuscation Karp–Lipton theorem Gödel Prize Low (complexity)

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (72 GB total memory, 1 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software