<p>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?</p>

<p>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. <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.94.7156&amp;rep=rep1&amp;type=pdf" rel="noreferrer">here</a>.)</p>

CC BY-SA 2.5
2010-08-21T14:24:29.117Z
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.
Joshua Grochow
CC BY-SA 2.5
2010-08-21T08:31:54.423Z
2010-08-21T08:31:54.423Z
Magnus Wahlström
<p>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(n<sup>polylog n</sup>). Perhaps someone here can instantiate the function $f$ and get a concrete problem out.</p>

<p>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.</p>

<p>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.</p>

<p>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).</p>

CC BY-SA 2.5
2010-09-17T15:57:17.603Z
What if you substitute $f$ with a given propositional formula on $n+m$ variables (letting $x_i$'s and $y_j$'s be bits)?
Ryan Williams
CC BY-SA 2.5
2010-09-17T17:37:22.833Z
Yeah, I guess that would work.
Robin Kothari
CC BY-SA 2.5
2010-09-17T04:04:38.357Z
2010-09-17T04:04:38.357Z
Robin Kothari
<p>For Class 2, one somewhat silly example is </p>

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

<p>R is in Class 2 but undecidable.</p>

CC BY-SA 2.5
2010-09-18T18:45:46.837Z
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|.
Joshua Grochow
CC BY-SA 2.5
2010-09-23T20:51:35.210Z
@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.
Andy Drucker
CC BY-SA 2.5
2010-09-23T22:53:39.410Z
Ah yes.  That's how I convinced myself before, too :).  Thanks.
Joshua Grochow
CC BY-SA 2.5
2010-08-20T22:32:11.737Z
2010-08-20T22:32:11.737Z
Andy Drucker
<p>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?</p>

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

<p>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.</p>

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

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

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

<ol>
<li>There is a polynomial p such that (x,y) in R implies |y| is at most p(|x|).</li>
<li>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.</li>
<li>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).</li>
</ol>

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

<p>(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.)</p>

<blockquote>
  <p>Are there natural relational problems in class 2?</p>
</blockquote>

CC BY-SA 2.5
2010-08-19T16:31:14.533Z
I am not sure of the question. Do you want problems that are obviously in one of the classes but not the other?
Lev Reyzin
CC BY-SA 2.5
2010-08-19T17:53:01.787Z
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.
Joshua Grochow
CC BY-SA 2.5
2010-08-20T03:51:42.907Z
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.
Andy Drucker
CC BY-SA 2.5
2010-08-20T04:01:50.540Z
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.
Andy Drucker
CC BY-SA 2.5
2010-08-20T18:51:36.207Z
Andy -- why not post that as an answer instead of a comment?
Joshua Grochow
CC BY-SA 2.5
2010-08-20T22:35:44.573Z
Sure, done.
(what's up with these 15-character minimums?)
Andy Drucker
<cc.complexity-theory><complexity-classes><np>
Two Variants of NP
Joshua Grochow
# Two Variants of NP

(Asked by: username_0 on 2010-08-19)

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?

**Tags:** cc.complexity-theory, complexity-classes, np

> **Comments:**
> **username_1**: I am not sure of the question. Do you want problems that are obviously in one of the classes but not the other?  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_2**: 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.  
> **username_0**: Andy -- why not post that as an answer instead of a comment?  
> **username_2**: Sure, done. (what's up with these 15-character minimums?)  

---

## 3 answers

### Answer by username_2 on 2010-08-20. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_0**: 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|.  
> **username_2**: @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.  
> **username_0**: Ah yes.  That's how I convinced myself before, too :).  Thanks.  

---

### Answer by username_3 on 2010-08-21. Score: 5

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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.94.7156&rep=rep1&type=pdf).)

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_4 on 2010-09-17. Score: 2

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).

> **Comments:**
> **username_5**: What if you substitute $f$ with a given propositional formula on $n+m$ variables (letting $x_i$'s and $y_j$'s be bits)?  
> **username_4**: Yeah, I guess that would work.  

---

