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

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

• Next message: Mikhail N. Kupchik: "Re: P vs NP: my proof of P != NP"

```Date: 03 Apr 2004 15:02:24 GMT

```

Mikhail N. Kupchik <mikhkup@mail.ru> wrote:
# Hello Gerhard,
#
# "Gerhard Woeginger" wrote:
#
# > # 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?

# Let A to be some decision problem in class P.
# By definition of P, there exists a turing machine M which decides A in
# polynomial time
# p_M(n) = O(n^{k_M}). (1)
# Let k_M in (1) the above expression to be smallest possible integer value
# that satisfies (1).
# k = min( k_M ) for all M deciding A.
# (Yes I know k_M could be real but I don't want to bother about its existence
# and existence of minimum in the set of all k_Ms).
#
# k is a degree of polynomial that bounds time of calculation of "the most
# quick" Turing Machine that solves A.
# I called it "degree of complexity" of A, "degree of time-complexity" is
# probably more precise.

Hmmm...

But then of course every problem in P is polynomial time
reducible to some problem in P of fixed complexity degree.

In fact, every problem in P is polynomial time reducible to
EVERY other problem in P (except to the empty set and to the
universal set). And this is independent of P=NP or P!=NP...

--Gerhard

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

• Next message: Mikhail N. Kupchik: "Re: P vs NP: my proof of P != NP"

## Relevant Pages

• {{Millennium Problems}}
... verified in polynomial time, so this problem is in '''NP'''. ... single fast algorithm for any of them is known. ... complexity for instances with 50–10,000 variables is ... {{quote|...it would transform mathematics by allowing a computer to ...
(sci.math)
• Re: Rules FAQ
... > player knows the entire game situation. ... > the complexity of the game with N intersections, ... Go with Japanese rules is EXPTIME-complete (believed to be ... definitely cannot be solved in polynomial time. ...
(rec.games.go)
• Re: question on complexity theorem proposition
... Assume there exists an algorithm ... Computing in polynomial time is an intensionnal property becasue for the same input/ouput relation, there exist TM computing it in polynomial time and other computing it in, say, non-PR time. ... Notice that the usual complexity classes are extensionnal classes are they are classes of *functions* and not classes of algorithms. ...
(comp.theory)
• Re: Could P = NP be true?
... polynomial time without demonstrating an algorithm (or the equivalent, ... but rather that there is a barrier to proving it true. ... There is a major gap between computabiltiy theory and complexity ...
(comp.theory)