1
$\begingroup$

All decision problems (i.e.language membership problems), which are verifiable in polynomial time by a deterministic Turing machine are called NP problems. Further, these problems can be solved by a non-deterministic Turing machine in a polynomial time and in exponential time by a deterministic Turing machine.

Do we have a decision problem that is not verifiable by a deterministic Turing machine in polynomial time but decidable?

| cite | improve this question | |
$\endgroup$
  • 2
    $\begingroup$ This seems related, specifically "The most important thing to realize from a theoretical standpoint is that NP is actually a relatively small class of all decidable languages". $\endgroup$ – Guildenstern May 24 '14 at 15:44
5
$\begingroup$

No to the question in your title; yes to the question in the body of your post.

By the non-deterministic time hierarchy theorem, every decidable NEXP-hard decision problem is "a decision problem that is not verifiable by a deterministic Turing machine in polynomial time but decidable".

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Explanation of edit: the restriction to decidable NEXP-hard problems is required because the halting problem is NEXP-hard but is not "a decision problem that is not verifiably by a deterministic polytime TM but decidable." $\endgroup$ – David Richerby May 24 '14 at 12:04
  • $\begingroup$ Ah, yes. $\;\;$ $\endgroup$ – user12859 May 24 '14 at 19:07
0
$\begingroup$

A concrete counterexample could be Quantifed Boolean Formula, which is only verifiable in polynomial time if PSPACE=P. There's a whole myriad of other examples. You might also want to look at coNP-complete problems. For these a polynomial TM can only verify counterexamples (unless coNP=NP). The language of all tautologies is a prominent example for that class.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Why give a conditional example (i.e., one that relies on some conjecture about complexity classes) when there are so many unconditional ones? $\endgroup$ – David Richerby May 24 '14 at 12:00
  • 2
    $\begingroup$ @DavidRicherby Because I find those problems a lot more intuitive than many of the NEXP-problems, and I think that at least PSPACE $\neq$ P is not the weirdest thing to assume. But OK, I get your point. I'll change my answer accordingly. $\endgroup$ – john_leo May 24 '14 at 13:30

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.