5
$\begingroup$

I didn't understand some things about $ P/POLY$ class, and I will be thankful if you could help me. as I learned in class,

a turing machine M accepts language L with advice $ {a_n} $ if: M(x,$ a_|x| $ ) = 1 <=> x in L

  1. Does it mean that M with the advice decides L (halts on every input)? or recognizes L? (accept every x in L but may not halt on x that is not in L)

Generally, if a language L is in P it means that there is polynomial time machine that decides it right? I feel like it really confused me.

then we defined: $ P/POLY $ = union of (DTIME($n^{k1}), n^{k2})$ on every $k1,k2$ in $N$ .

we proved in class that there is a unary language which is undecidable, and that every unary language is in $P/1$. that means that there is language in $P/1$ which is undecidable.

  1. I don't understand it because $P/1$ is in $ P/POLY $ . as I understand by the definition, there is poly time machine that decides it.. so what do I get wrong?
$\endgroup$
6
$\begingroup$

if $L\in P/poly$ then there is a machine that decides any input $x$, given the advice $a_{|x|}$.

However, if the advice is not given, maybe no machine can decide $L$. This is what happens in the unary case. Note that the machine doesn't know the advice and cannot compute it, i.e., the set of advices (for a specific $L$) may be an undecidable language.

On the other hand, if someone gives you this (possibly undecidable) set, you have more power at hands. Similarly, if you can compute this set (for a certain $L$), say get $a_n$ in $f(n)$ time, then $L$ clearly belongs to $DTIME(poly(f(n)))$.

$\endgroup$
  • 1
    $\begingroup$ I understand, but we proved that every unary language L is in P/1 by describing a turing machine with the advice: 1 if 1^n is in L, and 0 otherwise, so we do know the advice here, but yet there is a unary lanauge that is undecidable, so how is that? $\endgroup$ – CnR Jul 20 '15 at 9:22
  • 2
    $\begingroup$ exactly because the "advice" there is undecidable. The advice is still 1 if x is in $L$ and 0 otherwise, but there is no TM that can compute this advice (=undecidable). $\endgroup$ – Ran G. Jul 20 '15 at 12:17

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.