<p>Reading the question <a href="https://cstheory.stackexchange.com/questions/27215/natural-np-complete-problems-with-large-witnesses/27219">Natural NP-Complete Problems with Large Witnesses</a>, I was interested in this language:</p>

<blockquote>
  <p>$L = \{ \varphi ~~:~~ \varphi \text{ is SAT formula with more than } |\varphi|^2 \text{ satisfying assignments}\}$</p>
</blockquote>

<p>It made me think of the following generalization. Let $A$ be a language in $\textsf{NP}$ and fix a corresponding verifier machine $M$. My question is, <strong>What is known about the language consisting of members of $A$ that have at least $f(n)$ witnesses</strong> (where $n$ is the size of the input and witnesses are relative to the verifier $M$)?</p>

<p>...</p>

<p>More formally: We have a deterministic polynomial-time verifier $M$, so a <em>witness</em> of $a \in A$ relative to $M$ is a string $w$ such that $M(a,w) = 1$. The language under consideration is</p>

<blockquote>
  <p>$L_A^f = \Big\{ a \in A ~~:~~ \#\{ w \mid M(a,w) = 1 \} \geq f(|a|) \Big\}$.</p>
</blockquote>

<p>In English, $L_A^f$ consists of, for each $n$, the members of $A$ of size $n$ that have at least $f(n)$ witnesses relative to $M$.</p>

<p>Some preliminary observations:</p>

<ol>
<li>$L_A^1 = A$ no matter what verifier you use.</li>
<li>For any $A$ in NP with verifier $M$, you can make a verifier $M'$ for $A$ such that $L_A^f = A$. Just have $M'$ accept every witness $w$ that is accepted by $M$, plus $f(n)$ padded versions of the witness as well. Then $a \in A$ if and only if it has at least $f(n)$ witnesses relative to $M'$. This shows that if you aren't careful about first fixing the verifier, you can get trivial answers.</li>
</ol>

<p>Some example questions/directions:</p>

<ol>
<li><p>What can we say about "parsimonious" or "minimal" verifiers? For instance, is there an NP-Complete language $A$ and verifier $M$ where $L_A^f$ becomes, say, not NP-Complete, or even trivial or empty, for some small $f$? What about $L_A^2$ (the members of $A$ with at least two witnesses)?</p></li>
<li><p>On the other hand what about succinctly-represented families of solutions? Could we have $f = \omega(p(n))$ for all polynomials $p$, and some "reasonable" or "natural" verifier for an NP-Complete language $A$, and yet $L_A^f$ is in NP? (Meaning that the fact that a given $a \in A$ has superpolynomially many witnesses is provable without listing all the witnesses.)</p></li>
<li><p>Anything about the above for a specific language $A$ such as SAT would be interesting.</p></li>
</ol>

<p>Possibly (slightly) related: <a href="https://cstheory.stackexchange.com/questions/20035/does-second-x-is-np-complete-imply-x-is-np-complete">Does "Second-X is NP-Complete" Imply "X is NP-Complete"?</a></p>

CC BY-SA 3.0
2014-11-24T21:41:09.283Z
For 1, check complexity classes UP and FewP.
Tsuyoshi Ito
CC BY-SA 3.0
2014-11-25T01:17:31.487Z
@TsuyoshiIto, thanks, those are good special cases.
usul
<cc.complexity-theory><np><np-complete>
Properties of "second-order" NP (complete) languages
usul
# Properties of "second-order" NP (complete) languages

(Asked by: username_0 on 2014-11-24)

Reading the question [Natural NP-Complete Problems with Large Witnesses](https://cstheory.stackexchange.com/questions/27215/natural-np-complete-problems-with-large-witnesses/27219), I was interested in this language:

> $L = \{ \varphi ~~:~~ \varphi \text{ is SAT formula with more than } |\varphi|^2 \text{ satisfying assignments}\}$

It made me think of the following generalization. Let $A$ be a language in $\textsf{NP}$ and fix a corresponding verifier machine $M$. My question is, **What is known about the language consisting of members of $A$ that have at least $f(n)$ witnesses** (where $n$ is the size of the input and witnesses are relative to the verifier $M$)?

...

More formally: We have a deterministic polynomial-time verifier $M$, so a *witness* of $a \in A$ relative to $M$ is a string $w$ such that $M(a,w) = 1$. The language under consideration is

> $L\_A^f = \Big\{ a \in A ~~:~~ \#\{ w \mid M(a,w) = 1 \} \geq f(|a|) \Big\}$.

In English, $L\_A^f$ consists of, for each $n$, the members of $A$ of size $n$ that have at least $f(n)$ witnesses relative to $M$.

Some preliminary observations:

1. $L\_A^1 = A$ no matter what verifier you use.
2. For any $A$ in NP with verifier $M$, you can make a verifier $M'$ for $A$ such that $L\_A^f = A$. Just have $M'$ accept every witness $w$ that is accepted by $M$, plus $f(n)$ padded versions of the witness as well. Then $a \in A$ if and only if it has at least $f(n)$ witnesses relative to $M'$. This shows that if you aren't careful about first fixing the verifier, you can get trivial answers.

Some example questions/directions:

1. What can we say about "parsimonious" or "minimal" verifiers? For instance, is there an NP-Complete language $A$ and verifier $M$ where $L\_A^f$ becomes, say, not NP-Complete, or even trivial or empty, for some small $f$? What about $L\_A^2$ (the members of $A$ with at least two witnesses)?
2. On the other hand what about succinctly-represented families of solutions? Could we have $f = \omega(p(n))$ for all polynomials $p$, and some "reasonable" or "natural" verifier for an NP-Complete language $A$, and yet $L\_A^f$ is in NP? (Meaning that the fact that a given $a \in A$ has superpolynomially many witnesses is provable without listing all the witnesses.)
3. Anything about the above for a specific language $A$ such as SAT would be interesting.

Possibly (slightly) related: [Does "Second-X is NP-Complete" Imply "X is NP-Complete"?](https://cstheory.stackexchange.com/questions/20035/does-second-x-is-np-complete-imply-x-is-np-complete)

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

> **Comments:**
> **username_1**: For 1, check complexity classes UP and FewP.  
> **username_0**: @TsuyoshiIto, thanks, those are good special cases.  

---

## 0 answers

