25

This is related to the question 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?

Community
  • 1
argentpepper
  • 2,281
  • 15
  • 27
  • Can't you always achieve that by padding? – Mahdi Cheraghchi May 09 '12 at 18:36
  • 5
    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 May 09 '12 at 19:54

1 Answers1

28

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

Ryan Williams
  • 27,465
  • 7
  • 115
  • 164