The class P/poly is the
set of languages that have polynomial-size
circuit families, i.e., L is in P/poly if there is a k, a sequence of
Boolean circuits C_{0}, C_{1}, … where C_{n}
has n inputs and at most n^k gates,
such that
and all x=x_{1}x_{2}…x_{n},

_{n}(x

_{1},x

_{2},…,x

_{n})=1.

_{27}may have no relation whatsoever to C

_{28}.

Suppose NP is in P/poly and has a (non-uniform) circuit family that accepts it. Karp and Lipton show that NP in P/poly implies collapses in uniform models of computation as well.

The main result shows that if NP is in P/poly then the polynomial hierarchy collapses to the second level, giving us evidence that NP is not in P/poly and hope that we can prove P≠NP by showing superpolynomial lower bounds on the circuit computing some NP problem.

The paper also gives a general (though controversial)
definition of advice and a collapse of EXP to
Σ_{2}^{p}∩Π_{2}^{p} if
EXP is in P/poly (credited to Meyer), and similar results for PSPACE
and the Permanent.

Kannan uses Karp-Lipton to show
that some language in
Σ_{2}^{p}∩Π_{2}^{p} does
not have linear-size circuits, or more generally for every k, there is
a language L_{k} in
Σ_{2}^{p}∩Π_{2}^{p} that
cannot be computed by nonuniform n^{k}-size circuits.

Later extensions to Karp-Lipton:

- If NP in P/poly then the polynomial-time hierarchy collapses to S
_{2}^{P}⊆ ZPP^{NP}⊆ Σ_{2}^{p}∩Π_{2}^{p}. (see Cai and Köbler-Watanabe) - If EXP, PSPACE or
the Permanent is in P/poly then EXP, PSPACE or
the Permanent is in MA ⊆
S
_{2}^{P}respectively. (see Babai-Fortnow-Lund) - If NP is in BPP (in P/poly) then the polynomial-time hierarchy is in BPP. (Zachos)

_{2}

^{P}does not have n

^{k}-size circuit for any fixed k. Can one improve (1) to show that if NP in P/poly then the polynomial-time hierarchy collapses to MA? This would imply MA does not have n

^{k}-size circuits for any fixed k.

## No comments:

## Post a Comment