6
$\begingroup$

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

$\endgroup$
9
  • 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$ Commented Dec 5, 2010 at 20:31
  • 10
    $\begingroup$ qwiki.stanford.edu/index.php/Complexity_Zoo:P#plog $\endgroup$ Commented Dec 5, 2010 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$ Commented Dec 5, 2010 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$ Commented Dec 5, 2010 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$ Commented Dec 6, 2010 at 3:34

1 Answer 1

9
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ This is a nice answer. $\endgroup$ Commented Dec 6, 2010 at 9:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.