P/poly

P/poly

In computational complexity theory, P/poly is the complexity class of languages recognized by a polynomial-time Turing machine with a polynomial-bounded advice function. It is also (equivalently) defined as the class of languages that have a polynomial-size non-uniform circuit family, non-uniform PSIZE. This means that the machine that recognizes a language may use a different advice function or use a different circuit depending on the length of the input, and that the advice function or circuit will vary only on the size of the input.

For example, the popular Miller-Rabin primality test can be formulated as a P/poly algorithm: the "advice" is a list of candidate "a" values to test. It is possible to precompute a list of at most "n" values such that every composite "n"-bit number will be certain to have a witness "a" in the list. For example, if we're testing a 32-bit number, it is enough to test "a" = 2, 7, and 61. [http://primes.utm.edu/prove/prove2_3.html] This follows from the fact that for each composite "n", 3/4s of all possible "a" values are witnesses; a simple counting argument similar to the one in the proof that BPP in P/poly below shows that there "exists" a suitable list of "a" values for every input size, although finding it may be expensive.

Note that P/poly, unlike other polynomial-time classes such as P or BPP, is not generally considered a practical class for computing. Indeed, it contains every undecidable unary language, none of which can be solved in general by real computers. On the other hand, if the input length is bounded by a relatively small number and the advice strings are short, it can be used to model practical algorithms with a separate expensive preprocessing phase and a fast processing phase, as in the example above.

Importance of P/poly

P/poly is an important class for several reasons. For theoretical computer science, there are several important properties that depend on P/poly:

*If NPP/poly then PH (the polynomial hierarchy) collapses to Sigma_2P.
*If PSPACEP/poly then PSPACE = Sigma_2P cap Pi_2P.
*If EXPTIMEP/poly then EXPTIME = Sigma_2P.

One of the most interesting reasons that P/poly is important is the property that if NP is not a subset of P/poly, then PNP. This observation was the center of many attempts to prove PNP.

P/poly is also used in the field of cryptography. Security is often defined 'against' P/poly adversaries. Besides including most practical models of computation like BPP, this also admits the possibility that adversaries can do heavy precomputation for inputs up to a certain length, as in the construction of rainbow tables.

Although not all languages in P/poly are sparse languages, there is a polynomial-time Turing reduction from any language in P/poly to a sparse language. [Jin-Yi Cai. Lecture 11: P=poly, Sparse Sets, and Mahaney's Theorem. CS 810: Introduction to Complexity Theory. The University of Wisconsin at Madison. September 18, 2003. http://pages.cs.wisc.edu/~jyc/810notes/lecture11.pdf]

Adleman theorem

The Adleman theorem, proved by Leonard Adleman, states that BPPP/poly, where BPP is the set of problems solvable with randomized algorithms with two-sided error in polynomial time.

Proof

Let "L" be a language in BPP, and let "M(x,r)" be a polynomial algorithm that decides "L" with error ≤ 1/3 (where "x" is the input string and "r" is a set of random bits).

Construct a new machine "M'(x,R)", which runs "M" "n" times (where "n" is the input length and "R" is a set of n different random rs. Thus, M' is also polynomial, and has an error probability ≤ 1/3"n".

Therefore if Bad("x"):"x"→"R" is defined as { "R" : "M'(x,R)" is incorrect}, we have:

:forall x, mbox{Prob}_R [R in mbox{Bad}(x)] leq frac{1}{3^n}.

Thus, the probability that a specific "R" that is bad for all "x" is ≤ 2"n"/3"n". In this expression we get 2^n because the input size is "n", so there are 2^n possible inputs. If we can fix "R" then we can construct an algorithm that is deterministic. Hence we have :exists x, mbox{Prob}_R [R in igcup mbox{Bad}(x)] leq frac{2^n}{3^n} < 1.

In words, if the probability some "R" is bad for all "x" is less than 1, then there must be an "R" that is good for all "x". Take such an "R" to be the advice string in our P/poly algorithm.

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • poly — poly·acrylate; poly·acrylic; poly·acrylonitrile; poly·act; poly·actinal; poly·adel·phia; poly·adel·phous; poly·allel; poly·alphabetic; poly·amide; poly·amine; poly·an·dria; poly·an·dric; poly·an·drist; poly·an·dri·um; poly·an·drous; poly·an·dry;… …   English syllables

  • Poly(NIPAM) — Poly(N isopropylacrylamide) Structure du poly(N isopropylacrylamide). La structure entre crochets constitue, en se répétant, le squelette des chaînons du polymère. Le poly(N isopropylacrylamide) (abrégé en polyNIPAM, PNIPAM ou PNIPAAm) est un… …   Wikipédia en Français

  • Poly (feuilleton televise) — Poly (feuilleton télévisé) Pour les articles homonymes, voir Poly. Poly Titre original Poly Autres titres francophones Poly et le mystère du château Genre Feuilleton d aventures, familial Créateur(s) …   Wikipédia en Français

  • poly- — ♦ Élément, du gr. polus « nombreux; abondant » (⇒ multi , pluri ). ⊗ CONTR. Mon(o) , uni . ● poly Préfixe, du grec polus, nombreux, indiquant la multiplicité. (En chimie, indique qu un composé possède plusieurs fonctions, différentes ou… …   Encyclopédie Universelle

  • Poly en Espagne — Titre original Poly en Espagne Genre Feuilleton d aventures, familial Créateur(s) Cécile Aubry Pays d’origine  France …   Wikipédia en Français

  • Poly en tunisie — Titre original Poly en Tunisie Genre Feuilleton d aventures, familial Créateur(s) Cécile Aubry Pays d’origine  France Chaîne d’origine …   Wikipédia en Français

  • Poly a Venise — Poly à Venise Poly à Venise Titre original Poly à Venise Genre Feuilleton d aventures, familial Créateur(s) Cécile Aubry Pays d’origine  France Chaîne d’origine ORT …   Wikipédia en Français

  • Poly au portugal — Titre original Poly au Portugal Genre Feuilleton d aventures, familial Créateur(s) Cécile Aubry Pays d’origine  France Chaîne d’origine …   Wikipédia en Français

  • Poly en espagne — Titre original Poly en Espagne Genre Feuilleton d aventures, familial Créateur(s) Cécile Aubry Pays d’origine  France Chaîne d’origine …   Wikipédia en Français

  • Poly et le secret des sept etoiles — Poly et le secret des sept étoiles Poly et le secret des sept étoiles Titre original Poly et le secret des sept étoiles Genre Feuilleton d aventures, familial Créateur(s) Cécile Aubry Pays d’origine  France Chaî …   Wikipédia en Français

  • Poly à venise — Titre original Poly à Venise Genre Feuilleton d aventures, familial Créateur(s) Cécile Aubry Pays d’origine  France Chaîne d’origine ORT …   Wikipédia en Français

Share the article and excerpts

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