Is something like DTIME(poly(n))/log(n) in P? Can the log-length advice be somehow hardwired into a DTM for P?

  • 9
    $\begingroup$ No, because P/log (or even P/1 for that matter) contains some undecidable languages. Voted to close as off topic (too basic). $\endgroup$ Dec 5 '10 at 20:31
  • 10
    $\begingroup$ qwiki.stanford.edu/index.php/Complexity_Zoo:P#plog $\endgroup$ Dec 5 '10 at 20:50
  • 7
    $\begingroup$ Tsuyoshi, while I don't disagree with your assessment that this is basic, it's helpful to then point the user to where they might find the answer (as Michael did). $\endgroup$ Dec 5 '10 at 21:46
  • 4
    $\begingroup$ @Suresh: At least I tried to be helpful by giving a brief explanation. I think that my comment already contained some terms to search. If you do not think that it was helpful, then we have simply different views about what is helpful. $\endgroup$ Dec 5 '10 at 23:51
  • 3
    $\begingroup$ Let me play the devil's advocate here: If we answer all basic questions in the comments before closing them, wont that encourage people to come here and ask basic questions? And surely there are at least 100 times as many people who would like to ask basic questions than research-level questions, so that would lead to this site being flooded with basic questions. $\endgroup$ Dec 6 '10 at 3:34

As pointed in the comments, You cannot do this in general, However, if you're willing to restrict the class and add some some structure you can achive this. For example, you can use the self-reducibility of SAT to remove the advice, i.e if $NP\in P/log$ then $NP=P$.

In general, the same is true for complexity classes with self-reducible complete problem, and similar arguments for complexity classes with instance checkers $(EXP,PSPACE,P^{\#P})$ will allow you to remove even larger advices (polynomial) with the difference that now you need to use probabilistic machines.

  • 3
    $\begingroup$ This is a nice answer. $\endgroup$ Dec 6 '10 at 9:01

Your Answer

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