gotchaMinor
Why does P/Poly can also receive bad advice?
Viewed 0 times
whycanbadalsoreceiveadvicedoespoly
Problem
(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?
"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?
Solution
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.
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.
Context
StackExchange Computer Science Q#61073, answer score: 9
Revisions (0)
No revisions yet.