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