Re: P vs NP: my proof of P != NP
From: Jim Nastos (nastos_at_cs.ualberta.ca)
Date: 04/04/04
- Next message: chongo: "all paths between 2 nodes"
- Previous message: The Ghost In The Machine: "Re: functions that halt"
- In reply to: Mikhail N. Kupchik: "Re: P vs NP: my proof of P != NP"
- Next in thread: tchow_at_lsa.umich.edu: "Re: P vs NP: my proof of P != NP"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Sun, 4 Apr 2004 14:51:57 -0600
On Sun, 4 Apr 2004, Mikhail N. Kupchik 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.
I don't know what statement you think I was referring to, but I clearly
said that your statement that "there is no upper limit" is incorrect. For
any A in P, there will exist a limit, k, for which A is accepted by a
Turing machine which is O(n^k) time-bounded. There is no such thing as
having a language with "no upper limit time-complexity."
And, in case you are still confused, my above statement does not say
that every language in P is accepted by an O(n^k) time-bounded TM.
J
- Next message: chongo: "all paths between 2 nodes"
- Previous message: The Ghost In The Machine: "Re: functions that halt"
- In reply to: Mikhail N. Kupchik: "Re: P vs NP: my proof of P != NP"
- Next in thread: tchow_at_lsa.umich.edu: "Re: P vs NP: my proof of P != NP"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
