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

From: Mikhail N. Kupchik (mikhkup_at_mail.ru)
Date: 04/02/04 

Date: Fri, 2 Apr 2004 21:37:41 +0300

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. Even stronger, every problem from
DTIME(exp( O(n) )) is reducible to some problem from P of fixed degree.
Surely class should be called more precisely "DTIME(exp( O(n) ))", not "EXP"
(unless theorem 10 is applied more than once).
(Don't be too captious, it was only informal concept of the proof. Formal
details are in pdf file).

Surely the result "DTIME( O(n^k) ) \subseteq DTIME( O(n^(k-1)) )" is in
contradiction with Hartmanis/Stearns P-hierarhy theorem so supposition
"P=NP" was wrong.

        -- Mikhail Kupchik