Complexity theory citation sought

From: Henning Makholm <henning@xxxxxxxxxxx>
Date: Mon, 30 May 2005 19:07:03 +0100

It is not hard to prove that

If any NP-complete problem is also in coNP, then NP=coNP.

Unfortunately my audience (who are not complexity theorists) cannot be
expected to see trough this claim in seconds, and I don't want to bore
them with a spelled-out proof either.

Is there a standard reference I can give for this fact?

--
Henning Makholm "Jeg forstår mig på at anvende sådanne midler på
folks legemer, at jeg kan varme eller afkøle dem,
som jeg vil, og få dem til at kaste op, hvis det er det,
jeg vil, eller give afføring og meget andet af den slags."
.

Follow-Ups:
- Re: Complexity theory citation sought
  - From: tchow
- Re: Complexity theory citation sought
  - From: Mitch Harris

Prev by Date: Re: are Real Numbers evil? The answer(?).
Next by Date: Re: are Real Numbers evil? The answer(?).
Previous by thread: Finding just one solution to N-queen problem by observing the pattern of solutions
Next by thread: Re: Complexity theory citation sought
Index(es):
- Date
- Thread

Relevant Pages

Re: Complexity theory citation sought
... Unfortunately my audience (who are not complexity theorists) cannot be ... expected to see trough this claim in seconds, and I don't want to bore ...
(comp.theory)
Re: Complexity theory citation sought
... > If any NP-complete problem is also in coNP, ... >Is there a standard reference I can give for this fact? ... since you just have to switch NP and coNP everywhere in the ... Prev by Date: ...
(comp.theory)