9
$\begingroup$

The definition of P is a language that can be decided by a polynomial time algorithm. The definition of P/poly can be taken to mean a language that can be decided by a polynomial-size circuit (see http://pages.cs.wisc.edu/~jyc/02-810notes/lecture09.pdf). Now, why can't a polynomial-sized circuit be simulated in polynomial time?

$\endgroup$
  • 4
    $\begingroup$ P/poly can compute undecidable languages (exercise). $\endgroup$ – Yuval Filmus Mar 8 at 20:26
  • $\begingroup$ Thanks, but what is wrong with my argument - that a polynomial-size circuit can be simulated in polynomial time? $\endgroup$ – dcw Mar 8 at 20:29
  • 3
    $\begingroup$ It’s wrong. The polynomial size circuits for different input lengths could be radically different, and so cannot all be described by a single Turing machine. $\endgroup$ – Yuval Filmus Mar 8 at 20:30
  • $\begingroup$ Thanks, but where in the definition P does it say we're restricted to a single Turing machine? All the definitions I've seen are like in mathworld.wolfram.com/PolynomialTime.html $\endgroup$ – dcw Mar 8 at 20:38
  • 3
    $\begingroup$ @dcw A language is in P if there is a Turing machine such that... $\endgroup$ – David Richerby Mar 8 at 20:53
18
$\begingroup$

The point about circuits is that a circuit has a fixed number of inputs. This means that, to define a language, we need a family of circuits $C_0, C_1, C_2, \dots$ such that the circuit $C_i$ tells you which strings of length $i$ are in the language, for each $i$. This doesn't require that there should be any relationship between the circuits $C_i$ and $C_{i+1}$: they could be completely different. In particular, for any set $S\subseteq\mathbb{N}$, you could set declare $C_i=\mathrm{true}$ if $i\in S$ and $C_i=\mathrm{false}$ for $i\notin S$. Even if $S$ is undecidable!

In contrast, a language is in $\mathrm{P}$ if there is a single Turing machine that tells you whether every possible input of every possible length is in the language. Now, you can't play any funny games about inputs of different lengths.

You're correct that we can evaluate any fixed circuit in $\mathrm{P}$. But that's not necessarily enough to decide a language in $\mathrm{P/poly}$. To do that, we would first need to compute the length of the input, then use that to determine which circuit $C_i$ we need to evaluate, and then evaluate the circuit. As the example above shows, the "determine which circuit" part might not even be computable, let alone computable in polynomial time.

$\endgroup$
  • 1
    $\begingroup$ It's been years since I studied all this and I had (almost) forgotten the definition of $\mathrm{P/poly}$, but reading this answer brought it all back: I remember having the same confusion when I first encountered the definition and arriving at the same resolution/understanding. :-) $\endgroup$ – ShreevatsaR Mar 9 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.