-1
$\begingroup$

$A$ is a given language so that $A \in NP$.

Assume that $P = NP$.

Is $A'$ necessarily in NP?

What I did:

$A \in NP , P=NP$

$P=coP$ (Can be proven by running a TM $M$ as a decider for P, and building a TM $M'$ and switching 'accept's to 'reject's and vice-versa).


If $P=NP$, then $L \in NP \Rightarrow L \in P$

$P=coP \Rightarrow L' \in P \Rightarrow L' \in NP \Rightarrow L \in coNP$


Which proves that $coP=coNP$

And hence that $NP=coNP$

So $A \in NP \Rightarrow A \in coNP \Rightarrow A' \in NP$

So the answer is YES


Is this the correct way of solving this kind of questions?

Is there a better way?

Did I make any mistakes?

Is the proof of $coP=coNP$ correct?

Thanks in advance

$\endgroup$
  • 1
    $\begingroup$ By $A'$ you mean the complement? \overline{A} gets you more commonly used notation. $\endgroup$ – Raphael Feb 2 '16 at 13:36
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – Raphael Feb 2 '16 at 13:36
1
$\begingroup$

You are correct. Though you don't have to argue over accept/reject states. You can exploit that deterministic languages are closed under complement.

That can make your argument very concise: $A \in NP \Rightarrow A \in P \Rightarrow A' \in P \Rightarrow A' \in NP$

$\endgroup$
  • 1
    $\begingroup$ Please consider not to encourage undesirable posting behaviour. $\endgroup$ – Raphael Feb 2 '16 at 13:37
  • 1
    $\begingroup$ "You can exploit that deterministic languages are closed under complement." -- Which you would prove exactly like proposed. (In the context of homework, students usually have to prove everything the class does not have a theorem for.) $\endgroup$ – Raphael Feb 2 '16 at 13:40

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.