Are there any superpolynomial time set $\mathsf{SP}$ in between $\mathsf{P}$ and $\mathsf{EXPTIME}$ such that the problem $\mathsf{SP}=\mathsf{NSP}$ has a known answer?

UPDATE: It must be defined by time and strictly between $\mathsf{P}$ and $\mathsf{EXPTIME}$. I was wondering, what if Cobham's thesis is wrong and we are fighting with $\mathsf{P=NP}$ because of that thesis when the really useful question is another one? Maybe one that's even already answered?

  • 5
    $\begingroup$ Look up "translation" in a book on complexity theory. $\endgroup$
    – Markus Bläser
    Oct 16 '12 at 21:06

Take any time complexity class and its corresponding nondeterministic counterpart: $\mathsf{DTime(F)}$ and $\mathsf{NTime}(F)$ where $F$ is a family of nice functions containing polynomials and bounded by exponential functions. You are asking if we know these two classes are equal. We don't know!

Take $SAT$ as an example. A certificate can be verified in linear time so it is in $\mathsf{NTime}(n)$. However there is no algorithm that solves even very simple instances of $SAT$ (e.g. decide if the propositional statement that n+1 pigeons can be mapped into n holes is false) significantly faster than brute-force, i.e. exponential time. In other words, we don't even know if $\mathsf{NTime}(n) \subseteq \mathsf{DTime}(f)$ where $f$ is a little bit smaller than exponential function $2^n$. IF what you are asking was true then the lhs would be subset of your $\mathsf{NTime}(F)$ and therefore by your assumption a subset of $\mathsf{DTime}(F)$ where $F$ is smaller than exponential functions.

The question about $\mathsf{P}$ and $\mathsf{NP}$ is not only important because of Cobham's thesis that efficient computations are captured by $\mathsf{P}$, we don't know any simulation of nondeterminisitic time bounded machines by deterministic ones which doesn't use brute force search for the certificate. So the essential question about $\mathsf{P}$ vs. $\mathsf{NP}$ is can we find a certificate in a space exponentially faster than brute-force search of the space?

In fact, the question was known in Russian literature as the perebor problem (the brute-force search problem).

If you don't accept Cobham's thesis then you can think of $\mathsf{P}$ vs. $\mathsf{NP}$ question as the flagship of questions about the relation between verifying and constructing answers, or as I said above, as the question about existence of deterministic search algorithms which are exponentially faster than brute-force search.


Your Answer

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