Polynomial advice

A machine takes advice when, on an input x of length n, it also reads a string α n that depends only on n Arora and Barak, Definition 6.10. With the advice placed in front of the input as the pair (α |x|, x), encoded as frame (α |x|) ++ x, a language is in PAdvice when it consists of the inputs whose pair lies in a problem decidable in polynomial time, for advice of polynomial length. This is the class ⋃ DTIME(n ^ c) / n ^ d of Arora and Barak, Theorem 6.11, the original definition of P/poly Karp and Lipton.

Hardwiring the advice into circuits for the pairs gives circuits for the language: at each length n the first 2 |α n| + 1 inputs are fixed to the bits of frame (α n), which costs two gates for the constants (PPoly.of_advice). With P ⊆ P/poly (PPoly.exists_of_mem_P), every language in PAdvice is in PPoly (PAdvice_subset_PPoly). The machine enters only through the hypothesis that the problem of pairs is in Complexity.P. The converse inclusion needs a machine evaluating circuits in polynomial time, which is not proved here.

Main definitions

• Cslib.Circuits.Boolean.PAdvice: polynomial time with polynomial advice.

Main results

• Cslib.Circuits.Boolean.PPoly.of_advice: hardwiring advice of polynomial length into circuits of polynomial size.
• Cslib.Circuits.Boolean.PAdvice_subset_PPoly: P/advice ⊆ P/poly.

References

• S. Arora, B. Barak, Computational Complexity: A Modern Approach, Section 6.3
• R. M. Karp, R. J. Lipton, Some connections between nonuniform and uniform complexity classes

theorem Cslib.Circuits.Boolean.PPoly.of_advice {L M : Language Bool} (hM : M ∈ PPoly) (α : ℕ → List Bool) (hα : PolynomiallyBounded fun (n : ℕ) => (α n).length) (h : ∀ (x : List Bool), x ∈ L ↔ Turing.MultiTapeTM.frame (α x.length) ++ x ∈ M) : L ∈ PPoly

Hardwiring advice. If x ∈ L exactly when frame (α |x|) ++ x ∈ M, with M in P/poly and advice α of polynomial length, then L is in P/poly: fixing the first inputs of the circuits for M to the bits of frame (α n) costs two gates.

def Cslib.Circuits.Boolean.PAdvice : Set (Language Bool)

Polynomial time with polynomial advice Arora and Barak, Definition 6.10: the languages L with advice α of polynomial length and a problem A of pairs, decidable in polynomial time for the encoding frame u ++ x of (u, x), such that x ∈ L exactly when (α |x|, x) ∈ A.

theorem Cslib.Circuits.Boolean.PAdvice_subset_PPoly : PAdvice ⊆ PPoly

P/advice ⊆ P/poly Arora and Barak, Theorem 6.11: a language decided in polynomial time with polynomial advice has circuits of polynomial size.