<p>The class ${\cal C}$ you are proposing is probably not $NP$. (If ${\cal C} = NP$, then every $NP$ language would have linear-size witnesses, which would imply that every $NP \subseteq TIME[2^{O(n)}]$ and $NP \neq EXP$, among other things). </p>

<p>It is very natural to consider such classes; they arise in several settings. In <a href="http://homepages.inf.ed.ac.uk/rsanthan/Papers/segsepfinal.pdf">this paper</a>, Rahul Santhanam (implicitly) proposed the notation $TIGU(t(n),g(n))$ for time-$t(n)$ computation with $g(n)$-guess bits. Hence ${\cal C} = \bigcup_{k} TIGU(n^k,kn)$. In <a href="http://www.stanford.edu/~rrwill/sat-journal-final.pdf">this paper</a>, I defined an analogous class $NTIBI[t(n),b(n)]$. (NTIBI stands for "nondeterministic time and bits".) Also, Cai and Chen would call your class $GC(O(n), P)$ (GC stands for "Guess and Check", cf. L. Cai and J. Chen. On the amount of nondeterminism and the power of verifying. SIAM Journal on Computing, 1996). Finally, if you search for "bounded nondeterminism" you may find three more notations for the same class...</p>

CC BY-SA 3.0
2012-05-09T20:50:52.860Z
2012-05-09T20:50:52.860Z
Ryan Williams
<p>This is related to the question <a href="https://cstheory.stackexchange.com/questions/2271/is-the-witness-size-of-membership-for-every-np-language-already-known">Is the Witness Size of Membership for Every NP Language Already Known?</a></p>

<p>Some natural $\mathsf{NP}$(-complete) problems have linear length witnesses: a satisfying assignment for $SAT$, a sequence of vertices for $HAMPATH$, etc.</p>

<p>Consider the complexity class "$\mathsf{NP}$ restricted to linear length witnesses". Formal definition of this complexity class, call it $\mathcal{C}$: $L\in\mathcal{C}$ if $\exists L'\in\mathsf{P}\colon (x\in L \iff \exists w\in\{0, 1\}^{O(|x|)}\colon (x, w)\in L')$.</p>

<p>Is this a known complexity class? What are its properties?</p>

CC BY-SA 3.0
2012-05-09T18:36:24.613Z
Can't you always achieve that by padding?
Mahdi Cheraghchi
CC BY-SA 3.0
2012-05-09T19:54:33.693Z
As MCH pointed out, if $L$ is any $\mathsf{NP}$ language with witnesses of size $O(n^k)$, then $pad(L) := \{ x10^{|x|^{k}} : x \in L\}$ is an $\mathsf{NP}$ language with linear-size witnesses, and $L$ and $pad(L)$ are polynomial-time many-one equivalent. Your class isn't quite $\mathsf{NP}$, but it's basically the same. The class you suggest is not closed under polytime many-one reductions, but for every $L$ in $\mathsf{NP}$ there is some language in your class that is polytime many-one equivalent to $L$.
Joshua Grochow
<cc.complexity-theory><complexity-classes><np>
What is $\mathsf{NP}$ restricted to linear size witnesses?
argentpepper
# What is $\mathsf{NP}$ restricted to linear size witnesses?

(Asked by: username_0 on 2012-05-09)

This is related to the question [Is the Witness Size of Membership for Every NP Language Already Known?](https://cstheory.stackexchange.com/questions/2271/is-the-witness-size-of-membership-for-every-np-language-already-known)

Some natural $\mathsf{NP}$(-complete) problems have linear length witnesses: a satisfying assignment for $SAT$, a sequence of vertices for $HAMPATH$, etc.

Consider the complexity class "$\mathsf{NP}$ restricted to linear length witnesses". Formal definition of this complexity class, call it $\mathcal{C}$: $L\in\mathcal{C}$ if $\exists L'\in\mathsf{P}\colon (x\in L \iff \exists w\in\{0, 1\}^{O(|x|)}\colon (x, w)\in L')$.

Is this a known complexity class? What are its properties?

**Tags:** cc.complexity-theory, complexity-classes, np
> **Comments:**
> **username_1**: Can't you always achieve that by padding?  
> **username_2**: As MCH pointed out, if $L$ is any $\mathsf{NP}$ language with witnesses of size $O(n^k)$, then $pad(L) := \{ x10^{|x|^{k}} : x \in L\}$ is an $\mathsf{NP}$ language with linear-size witnesses, and $L$ and $pad(L)$ are polynomial-time many-one equivalent. Your class isn't quite $\mathsf{NP}$, but it's basically the same. The class you suggest is not closed under polytime many-one reductions, but for every $L$ in $\mathsf{NP}$ there is some language in your class that is polytime many-one equivalent to $L$.  

---

## 1 answers

### Answer by username_3 on 2012-05-09. Score: 29 | Accepted answer

The class ${\cal C}$ you are proposing is probably not $NP$. (If ${\cal C} = NP$, then every $NP$ language would have linear-size witnesses, which would imply that every $NP \subseteq TIME[2^{O(n)}]$ and $NP \neq EXP$, among other things).

It is very natural to consider such classes; they arise in several settings. In [this paper](http://homepages.inf.ed.ac.uk/rsanthan/Papers/segsepfinal.pdf), Rahul Santhanam (implicitly) proposed the notation $TIGU(t(n),g(n))$ for time-$t(n)$ computation with $g(n)$-guess bits. Hence ${\cal C} = \bigcup\_{k} TIGU(n^k,kn)$. In [this paper](http://www.stanford.edu/~rrwill/sat-journal-final.pdf), I defined an analogous class $NTIBI[t(n),b(n)]$. (NTIBI stands for "nondeterministic time and bits".) Also, Cai and Chen would call your class $GC(O(n), P)$ (GC stands for "Guess and Check", cf. L. Cai and J. Chen. On the amount of nondeterminism and the power of verifying. SIAM Journal on Computing, 1996). Finally, if you search for "bounded nondeterminism" you may find three more notations for the same class...


---

