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

From: Jim Nastos (nastos_at_cs.ualberta.ca)
Date: 04/04/04

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

Relevant Pages

• Re: Phonemes
... >>> the Cambridge Encyclopedia of Language. ... >>> Why would there be a theoretical maximum? ... >> I would suspect that there would some upper limit, ... would put a theoretical upper limit on phonemes. ...
(sci.lang)
• Re: Phonemes
... David Wright Sr. ... >> the Cambridge Encyclopedia of Language. ... >> Why would there be a theoretical maximum? ... > upper limit, but also having serious problems with a lack of redundancy. ...
(sci.lang)
• Re: Phonemes
... > the Cambridge Encyclopedia of Language. ... I would suspect that there would some upper limit, (not necessarily absolute, ... The next meetings of the Heinlein Readers Group ... The Heinlein Society is full of people who really believe, ...
(sci.lang)