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

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

Date: Sun, 4 Apr 2004 16:33:16 +0300

"Jim Nastos" <nastos@cs.ualberta.ca> wrote:
>
> On Sun, 4 Apr 2004, Mikhail N. Kupchik wrote:
> > I mean we choose A with no constraints on time-compexity degree.
> > ( it can be O(n), O(n^2), ... an so on - there is no upper limit )
> > but surely when A is fixed its complexity degree is known, fixed, and
> > limited ;-)
>
> Your statement that "there is no upper limit" is actually incorrect, as
your
> next phrase indicates, since any A in P will be accepted by some TM
> which is time-bounded by some O(n^k) for some finite k.
>
My statement is correct. We can build such reduction only supposing that
P=NP. And because arbitrary decision problem from P cannot be accepted by
time-bounded TM (by some O(n^k) for some finite k), we come to conclusion
that supposition was wrong.
I suggest you to read the proof (at least the sketch) first, then try to
refute it.

        -- Mikhail Kupchik

Relevant Pages

  • Re: The Starting Point Problem - for Howard Hershey
    ... complexity". ... I suppose Howard has never upgraded his computer. ... gave absoletely no indication of intent to represent Sean's meaning or ... Sean misuses the phrase to ...
    (talk.origins)
  • Re: The Starting Point Problem - for Howard Hershey
    ... complexity". ... Sean's misuse of that term. ... Sean misuses the phrase to ... "level of functional complexity" in the sense that Sean does. ...
    (talk.origins)
  • Re: The Starting Point Problem - for Howard Hershey
    ... complexity". ... Sean's misuse of that term. ... Sean misuses the phrase to ... "level of functional complexity" in the sense that Sean does. ...
    (talk.origins)
  • Re: AD Password complexity - passwords too long?
    ... Pass phrase length is far more ... Password complexity encourages folks to ... I can set my password to 9-10 characters, but if I try to set it for 10+ characters, they get the error message that they do not meet the complexity requirements. ...
    (Focus-Microsoft)
  • Re: Truenaming (Tome of Magic)
    ... thus the difficulty reflexs ... the complexity and seems justified. ... only apply to a specific phrase, used on a specific target. ...
    (rec.games.frp.dnd)