If you want to make money online : Register now

[Answers] bounded length CoNP proof

, , No Comments
Problem Detail: 

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.

Asked By : user1685224

Answered By : Shaull

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42376

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback