11
$\begingroup$

Here are two variations on the definition of NP. They (almost certainly) define distinct complexity classes, but my question is: are there natural examples of problems that fit into these classes?

(My threshold for what counts as natural here is a bit lower than usual.)

Class 1 (a superclass of NP): Problems with polynomial-size witnesses that take superpolynomial but subexponential time to verify. For concreteness, let's say time $n^{O(\log n)}$. This is equivalent to the class of languages recognized by nondeterministic machines that take time $n^{O(\log n)}$ but can only make poly(n) nondeterministic guesses.

Are there natural problems in class 1 that is not known/thought to be either in $NP$ nor in $DTIME(n^{O(\log n)})$?

Class 1 is a class of languages, as usual. Class 2, on the other hand, is a class of relational problems:

Class 2: A binary relation R = {(x,y)} is in this class if

  1. There is a polynomial p such that (x,y) in R implies |y| is at most p(|x|).
  2. There is a poly(|x|)-time algorithm A such that, for all inputs x, if there is a y such that (x,y) is in R, then (x,A(x)) is in R, and if there is no such y, then A(x) rejects.
  3. For any poly(|x|)-time algorithm B, there are infinitely many pairs (x,w) such that B(x,w) differs from R(x,w) (here I am using R to denote its own characteristic function).

In other words, for all instances, some witness is easy to find if there is one. And yet not all witnesses are easily verifiable.

(Note that if R is in class 2, then the projection of R onto its first factor is simply in P. This is what I meant by saying that class 2 is a class of relational problems.)

Are there natural relational problems in class 2?

$\endgroup$
  • $\begingroup$ I am not sure of the question. Do you want problems that are obviously in one of the classes but not the other? $\endgroup$ – Lev Reyzin Aug 19 '10 at 16:31
  • $\begingroup$ No. For each class, I am wondering separately if there are natural problems that fit into the class but are not known to fit into other standard complexity classes. For example, I would like to know if there is a natural problem in class 1 that is not known to be in NP. $\endgroup$ – Joshua Grochow Aug 19 '10 at 17:53
  • 1
    $\begingroup$ I think you want to rewrite condition 2 for Class 2, since otherwise A can be the trivial algorithm which always rejects. Your verbal description below seems more sensible. $\endgroup$ – Andy Drucker Aug 20 '10 at 3:51
  • 1
    $\begingroup$ For Class 2, one somewhat silly example is R(p, a) = {p is an integer polynomial, a is in the range of p, and |a| = O(poly(|p|)}. R is in Class 2 but undecidable. $\endgroup$ – Andy Drucker Aug 20 '10 at 4:01
  • $\begingroup$ Andy -- why not post that as an answer instead of a comment? $\endgroup$ – Joshua Grochow Aug 20 '10 at 18:51
6
$\begingroup$

For Class 2, one somewhat silly example is

R(p, a) = {p is an integer polynomial, a is in the range of p, and |a| = O(poly(|p|)}.

R is in Class 2 but undecidable.

$\endgroup$
  • $\begingroup$ Before I thought this was right but now I've confused myself. Let r be a poly bound, and let p be an integer poly. Then $\{x : |p(x)| \leq r(|p|)\}$ is finite, where |p| denotes the bit-length of the description of p. So I think the problem is decidable, but still appears difficult as the best general bounds on this set are (I think) exponential in |p|. $\endgroup$ – Joshua Grochow Sep 18 '10 at 18:45
  • $\begingroup$ @Joshua: I don't quite understand your comment. But I should've clarified, I meant $p$ to be a multivariate polynomial. Then setting $a = 0$, and asking if $R(p, a)$ holds, is asking whether $p = 0$ has a solution in integers. This is Hilbert's 10th problem, and the problem is undecidable. $\endgroup$ – Andy Drucker Sep 23 '10 at 20:51
  • $\begingroup$ Ah yes. That's how I convinced myself before, too :). Thanks. $\endgroup$ – Joshua Grochow Sep 23 '10 at 22:53
5
$\begingroup$

I would request that you clarify the witness condition in class 1 a bit. It seems that any appropriately bounded problem from co-NP would seem to do the trick, is this what you intended?

For example, take the class of all graphs that do not have a clique of size $\log n$. The witness, of course, is the graph itself, and performing this check is (I believe) not believed to be possible in polynomial time. (See for example the parameterized complexity status of the problem, and the results of Chen et al. here.)

$\endgroup$
  • $\begingroup$ If the witness condition seems ambiguous, then take my definition in terms of nondeterministic Turing machines instead. Your example is in deterministic time $n^{O(\log n)}$, which is indeed contained in class 1 and not though to be in $NP$. I would hope to find a natural problem in class 1 that is neither known to be in $NP$ nor known to be in $DTIME(n^{O(\log n)})$ (I'll update the question accordingly). I wonder if a version of some other parametrized problem might do the trick, but I'm not too familiar with parametrized complexity. $\endgroup$ – Joshua Grochow Aug 21 '10 at 14:24
2
$\begingroup$

This isn't an example of a natural problem, but a family of problems in Class 1, but probably not in NP or QP = DTIME(npolylog n). Perhaps someone here can instantiate the function $f$ and get a concrete problem out.

Let $f(x_1,x_2,\ldots, x_n,y_1,y_2,\ldots,y_m)$ be a polynomial time computable predicate, with m = polylog n.

The problem $\exists x \forall y f(x_1,x_2,\ldots, x_n,y_1,y_2,\ldots,y_m)$ is in your class 1.

It's probably not in QP because it can express all problems in NP, and it's probably not in NP because it can express all problems in co-NTIME(polylog).

$\endgroup$
  • 1
    $\begingroup$ What if you substitute $f$ with a given propositional formula on $n+m$ variables (letting $x_i$'s and $y_j$'s be bits)? $\endgroup$ – Ryan Williams Sep 17 '10 at 15:57
  • $\begingroup$ Yeah, I guess that would work. $\endgroup$ – Robin Kothari Sep 17 '10 at 17:37

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.