Are there any "natural" examples of decidable problems that are definitively known not to be in NP? The decidable languages I know of that are not contained in NP are usually derived from the time hierarchy theorem, which produces "artificial" languages based on diagonalization.
$\begingroup$
$\endgroup$
3
asked Mar 15, 2013 at 18:06
-
$\begingroup$ other known examples are also based on diagonalization which can be "embedded/encoded" in problems that do not seem to refer to TMs directly. $\endgroup$– vznCommented Mar 16, 2013 at 5:39
-
$\begingroup$ re duplicate status. dont agree this question is equivalent to the other question because this one asks for a "natural" problem, which has special meaning (but is not usually strictly formally defined or definable), & the other does not. so they are similar & there could be some overlap, but there may exist problems that fit the other question but not be "natural". $\endgroup$– vznCommented Mar 19, 2013 at 15:16
-
$\begingroup$ Some of the answers there contain problems I would consider as "natural", e.g. equivalence of regular expressions, so you have to come up with a very narrow definition of "natural" to separate the questions. $\endgroup$– fraflCommented Mar 20, 2013 at 16:36
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
From an answer to a related question on NP-hard problems which are not contained in NP: probably the most natural example is determining whether two regular expressions (including the Kleene star for arbitrary repetition, and a squaring operation to allow compact expressions of very large fixed numbers of repetitions) are equivalent. The resulting problem is EXPSPACE complete. Because EXPSPACE contains NEXP, which contains NP strictly (by the time hierarchy theorem), this is a decideable problem which is not in NP.
answered Mar 15, 2013 at 18:14
-
$\begingroup$ nearly identical, determining if $L=\Sigma*$ for regular expressions with exponentiation $\endgroup$– vznCommented Mar 16, 2013 at 5:12
-
2$\begingroup$ Wikipedia's List of PSPACE-complete problems contains "Equivalence problem for regular expressions". The EXPSPACE-complete problem needs the additional operator of squaring, according to Wikipedia's EXPSPACE-page. $\endgroup$ Commented Mar 16, 2013 at 11:04
-
$\begingroup$ @ThomasKlimpel: This doesn't really make sense to me. Can't squaring be achieved in-line anyway, by replacing e.g. $(a|bc)^2 = (a|bc)(a|bc)$? $\endgroup$ Commented Mar 18, 2013 at 14:11
-
2$\begingroup$ Yes, squaring can be achieved in-line. But this increases the size of the input, and complexity classes depend on how you measure the size of the input. It wouldn't matter if it were just a constant factor, but you can apply squaring multiple times. In effect, it's easy to see that squaring can be used to emulate exponentiation such that the size of the input only increases by a constant factor. $\endgroup$ Commented Mar 18, 2013 at 18:03
$\begingroup$
$\endgroup$
1
a variation of Posts Correspondence Problem for bounded length input (but not the standard "bounded" version eg in Garey/Johnson that is called "bounded PCP" that limits the number of blocks in the solution to the cardinality of the block set) is complete for NEXPSpace and therefore larger than NP which is properly in Pspace. [1]
ie let there also be an input parameter $n$ specified in binary that determines the maximal length of the PCP answer. this is apparently complete for NEXPSpace via a straightfwd proof. havent seen a proof in the literature. it proceeds in a way similar to the construction relating it to TMs in [2]
note that all problems that are known to be larger than NP are also larger than PSpace. otherwise it (a proof of a language that is not in NP but is still in PSpace) might be something close to a coNP$\neq$NP and therefore also P$\neq$NP proof (because P is closed under complement), or resolve some other "nearby" currently open complexity class separation.
[1] Decidable restrictions of the Post Correspondence Problem
[2] A polynomial reduction from any NP-complete problem to bounded PCP
-
$\begingroup$ more directly a language not in NP but in PSpace would be a NP$\neq$PSpace proof (currently open). $\endgroup$– vznCommented Mar 16, 2013 at 15:07