Re: P vs NP: my proof of P != NP

From: Gerhard Woeginger (gwoegi_at_figipc56.tu-graz.ac.at)
Date: 04/02/04 

Date: 02 Apr 2004 18:43:52 GMT

Mikhail N. Kupchik <mikhkup@mail.ru> wrote:
# Hello Gerhard,
#
#> # 2. Then I prove that _every_ problem from EXP is P-reducible to #
# AEASAT.
#> But that does not agree with the abstract of your paper: There you
#> clearly state that in fact you prove that _every_ problem from P
#> (!!!not from EXP!!!) is P-reducible to AEASAT.
#>
#> And that result is not surprising at all.
#> It looks as if (1) and the correct version of (2) imply: P=NP -> P=P.
#> True, but not very impressive.
#
# Yes you're right I should explain more clearly.
# I prove that if P=NP then every problem of P (which degree of complexity is
# _not limited_), is reducible to some
# problem from P of _fixed_ degree.

What is the "degree of complexity" of some problem in P?

--Gerhard

__________________________________________________________________
Gerhard J. Woeginger http://wwwhome.cs.utwente.nl/~woegingergj/