Re: An approach to proving P != NP

Hi,

It is very unclear to me - I hoped to give some resonable answer but I
have no any :).

See coments below:

Ralph wrote:
1) Call problems which are in NP and for which a solution can be
verified in polynomial time, NP0 problems.
This includes all NP-complete problems and all problems in P.

Let's say all NP problems because we know that P is in NP (even if P=NP
or P!=NP we know that any problem in P is also in NP).

2) Call problems in NP for which a solution can be
verified by an algorithm in NP0, NP1 problems.

Eeee - any of NP problems can have solution verified by some algorithm?
What is difference between NP0 and NP1? Have you had some kind of
recursion in mind?

3) For any K, call problems in NP for which a solution can be
verified by an algorithm in NP^K-1, NP^K problems.

Well... if NP^K means expotential time, then any of NP problems satisfy
this. Because NP<=PSPACE<=EXPTIME

4) Now, if P = NP then NP^K = P for any K.
But if NP^K != P then (perhaps) we have a hierarchy of
increasingly difficult problems. Presumably for sufficently
large K we have problems that are so difficult that we can prove
that they are not in P!

I don't get it - sorry :)

5) So to start we need to find problems that are in NP for which
verifying a solution involves solving an NP-Complete problem.
That is problems that are in NP1 - NP0 assuming NP1 != NP0.
At this point (my first step) my foot becomes stuck in the bog.

6) Can anybody pose a problem satisfying 5?.

Try PSPACE-complete problems (for example TQBF).

In my opinion it will lead to nowhere :).

Cheers,

Radek Hofman

.

Relevant Pages

  • Re: simple and beauty strategy
    ... The relation between the complexity classes P and NP is studied in ... positive solutions can be verified in polynomial time given the right ... the NP-complete problems are the "toughest" ... that every algorithm which decides the truth of Presburger statements ...
    (rec.gambling.lottery)
  • Re: one sentence proof of 4 Color Mapping Problem; direct method
    ... for you to determine whether you can color this map with THREE ... So an algorithm for this machine would look ... building the algorithm in P to solve the NP-complete problems, ... Perhaps the equivalency is the idea that Eucl geom is what is ...
    (sci.math)
  • Re: What big scientific changes will ...
    ... poliaminal time, a non poliaminal algo is no solution for me. ... NP-complete problems are not as hard as they seem. ... If such an algorithm existed, ... algorithm exists and in 1882 this was proven by von Lindemann. ...
    (sci.math)
  • Re: Question about the minesweeper consistency problem (NP-complete problems)
    ... > algorithm that solves the problem and whose EXPECTED running time is ... So, for the NP-complete problems, there are a large ...
    (sci.math)