6
$\begingroup$

Question: Let $A \subseteq $ {0,1}$^* $ be a language which satisfies $|A \cap ${0,1}$^n|=n^3 $ for all $n\ge 10$ Prove that $A \in NP$ implies $A \in coNP$.

Thoughts I've been having difficulty with this problem. My idea is somehow showing that each set of $n^3$ words cannot be a verifier for A and therefore A is in coNP. The problem is that as I see it, proving this will take exp time as I have an exponential number of options for strings from which to choose n^3 from. Would like some suggestions about how to prove this.

$\endgroup$
6
$\begingroup$

Assume that $A\in NP$, and let $V$ be a verifier for it. That is, $V$ takes as input $(x,y)$ and outputs 1 if $y$ witnesses that $x\in A$. That is, we can write $A=\{x:\exists y,\ V(x,y)=1\}$.

We show that $A\in coNP$, by showing that $\overline{A}\in NP$. We construct a verifier $V'$ for $\overline{A}$ as follows:

Given input $x$, $V'$ expects a witness of the form $(w_1,y_1,...,w_{n^3},y_{n^3})$, where $|x|=n$, such that $y_i$ is a witness that $w_i\in A$, and for every $i$ we have $w_i\neq x$. That is, a witness for $x$ not being in $A$ is simply a list of all the $n^3$ words that are in $A$. Clearly verifying this can be done in polynomial time using $V$ (which we assume to run in polynomial time).

$\endgroup$

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.