5
$\begingroup$

(from my class's slides)

"NP and P/Poly both use an external string for computation. However, for L in NP, any witness is rejected if x $\notin$ L. For L in P/Poly, there can be bad advice!"

I'm having a hard time understanding why this is true. My intuition is that if there are indeed 'bad advice', i.e advice that make the Turing Machine return bad answers, doesn't it mean that a situation where ALL of the advice are 'bad' is technically possible?

$\endgroup$
9
$\begingroup$

Lets review the definition of the class $P/poly$ by Turing machines which take advice.

The class $T(n)/a(n)$ is the set of languages decidable by a Turing machine which runs in time $T(n)$ with advice of length $a(n)$.

More formally, $L\in T(n)/a(n)$ if there exists a Turing machine $M(x,y)$ and a sequence of strings $\left\{\alpha_n\right\}_{n\in\mathbb{N}}$, with $\alpha_n\in\left\{0,1\right\}^{a(n)}$, such that for all $x\in\left\{0,1\right\}^n$ $M$ runs in time $T(n)$ and $x\in L \iff M(x,\alpha_n)=1$.

$P/Poly=\bigcup\limits_{c,d}n^c/n^d$.

As you can see in the definition above, we only require the existence of some sequence of advice $\alpha_n$ that we can trust. Perhaps for some different sequence, $\beta_n\in\left\{0,1\right\}^{a(n)}$, and some $x\notin L$, it holds that $M(x,\beta_{|x|})=1$, but we don't care, since we only required the existence of a "good" sequence of advice.

This is unlike the case with $NP$, where if $x\notin L$, all witnesses must be rejected.

$\endgroup$

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.