P = NP?

[Agamemnus]

I want to solve the greatest mystery in computer science, but I can't if I don't know what it means!

Someone please provide me with a real and understandable
explanation of what NP complete means, and what the question "Is P = NP?" mean.

PLEASE!

*DIES*

[Plasma]

In essence, the P = NP question asks: if positive solutions to a YES/NO problem can be verified quickly, can the answers also be computed quickly?

Good luck solving it if you can't even read.

[Agamemnus]

That's it? :o

EDIT: I got the solution, I'm just running through all the cases. Stand by.

[Agamemnus]

"In essence, the P = NP question asks: if positive solutions to a YES/NO problem can be verified quickly, can the answers also be computed quickly?"

A = problem asker
B = problem answerer (taker)

A asks B problem P.
B answers the solution S in time "n" through process P1.
A knows instantly whether B answered it correctly because A knows all possible answers. This takes time "0".

Introduce outside observer C.

C gets the answer from B.
C, by applying the rules to the question, can find out whether "S" is a satisfactory solution, which takes time "m".
[is C = A?]

Questions:

Can m = 0? Possibly, because the question may be trivial.
ex: Prove that 0==0

Can m > 0? Possibly, because the answer may take time to compute.
ex: 6 = 5 + z, solve for z. Takes 2 steps. 5 + z - 5 = 6 - 5. z = 6 - 5 = 1.

Can m < n? Possibly.
ex: 6 = 5 + z, solve for z. Takes 2 steps to solve. 5 + z - 5 = 6 - 5. z = 6 - 5 = 1. Takes 1 step to verify: 6 = 5 + (1). 6 = 6.

Can m = n? Possibly.
ex: Prove that 0==0.
0 steps to solve.
0 steps to verify.
(heheheh)

Therefore,

0 <= m <= n

[Agamemnus]

At least I solved it for k=0, I think.

[LooseCaboose]

P is the class of problems that can be solved on a deterministic turing machine in polynomial time. Algorithms that we accept as being reasonably fast in implementation belong in in the P class.

NP is the class of problems that can be solved on a non-deterministic turing machine in Polynomial time given the right information. A non-deterministic turing machine is a theoritical machine that instead of executing an instruction and moving to a new state, it executes an instruction and moves to several states, each of which is essentially of copy of the original machine. A non-deterministic turing machine is therefore massively parallel, anything that is computable on a non-deterministic turing machine is also computable on a deterministic turing machine, although much more slowly and not necessarly in polynomial time. The right information is important because to belong to the NP class there must exist an algortithm:

Code:

A(w, C)

Where w is the problem input string and C is a 'certificate' containing the right information to solve the problem. The problem only belongs to the NP class if there exists some C that can produce a YES answer in polynomial time.

NP complete problems, are the problems in the NP class that are the least likely to belong to the P class. If a single NP-Complete problem can be proved to be in P, then it can be easily followed that all NP problems belong in P and therefore:

Code:

P = NP

Algorithms belonging to the NP class include the travelling salesman problem and the knasack problem.

A good example for determining whether P = NP is given in the wikipedia:
http://en2.wikipedia.org/wiki/Complexity...s_P_and_NP].

Goingback to Plasma357's explanation:

In essence, the P = NP question asks: if positive solutions to a YES/NO problem can be verified quickly, can the answers also be computed quickly?

Note the words verified and computed, they are important.

Say our problem is that we have two large numbers, X = 250 and Y = 69799. We want to know if Y is a multiple of any integer between 1 and X. Computationally this is difficult because we need to manually test every value, however if the answer is YES because Y is a multiple of 223 then the answer can be verified very quickly with a single division. But just because the problem can be /verified/ quickly, doesn't mean that it can be /computed/ quickly.

Therefore,
0 <= m <= n

Can either m or n be non-polynomial in time? Yes, for example asking what is the best move from a given point in a chess game takes exponential time to solve. Therefore you have solved nothing. Unfortunately, to prove that P = NP, you are going to have to implement an algorithm that is NP-Complete for any given case in polynomial time on a deterministic turing machine (or your favourite language which sports dynamic memory). I really doubt that you are going to solve this problem when you had to ask what the problem was in the first place, there are computer scientists all over the world currently scratching their heads on this problem and they have a far greater understanding of the problem that you or I.

[Agamemnus]

Ok, so what prevents me from solving a problem on a deterministic machine in polynomial time and then solving that same problem in polynomial time on a non-deterministic, infinitely-parallel machine?

Furthermore, an infinitely-parallel machine would be able to solve an NP problem in time "w" and verify it in time "C". If the only things that you need to specify in an infinitely-parallel machine are the inputs, you can then solve any problem in n steps because you reduce the combinatorial explosion to a linear computation. The reverse of which must be n or fewer steps ("m" steps).

Am I not getting something? :normal:

[LooseCaboose]

Ok, so what prevents me from solving a problem on a deterministic machine in polynomial time and then solving that same problem in polynomial time on a non-deterministic, infinitely-parallel machine?

Nothing stops you from doing that, in fact that is true for all problems that are solvable in polynomial time on a deterministic machine. The problem is the other way around, if a problem can be solved on a non-deterministic machine in polynomial time, there is no guarantee that it can be solved in polynomial time on a deterministic machine, for all NP-Complete algorithms nobody has yet proved a method of doing so, not to say that it is unprovable.

Furthermore, an infinitely-parallel machine would be able to solve an NP problem

Yes, thats what non-deterministic machines do, they solve NP problems in polynomial time. Class P refers to algorithms that can be solved in polynomial time on a /deterministic/ machine, class NP refers to algorithms that can be solved in polynomial time on a /non-deterministic/ machine.

To prove that P= NP, you need to show that all algortithms in class NP can also be solved in polynomial time on a /deterministic/ machine. The simplest (sic) method of doing this is to implement an NP-Complete algorithm such as the knapsack problem in polynomial time on a deterministic machine (ie a personal computer).

The problem in going from the massively parallel non-determinstic machine to the deterministic machine is that an algorithm that took polynomial time on the former is quickly going to become non-polynomial on the latter because the parallel threads of execution now need to be executed sequentially.

IMHO the problem of P = NP is more likely to be disproved than proved, possibly in a similar way to Turing's halting problem, for example this program (taken from the Wikipedia page I gave you) solves the subset-sub problem (NP-Complete) in polynomial time on a deterministic machine if and only if P = NP.

Code:

// Algorithm that accepts the NP-complete language SUBSET-SUM.
    //
    // This is a polynomial-time algorithm if and only if P=NP.
    //
    // "Polynomial-time" means it returns "YES" in polynomial time when
    // the answer should be "YES", and runs forever when it's "NO".
    //
    // Input:  S = a finite set of integers
    // Output: "YES" if any subset of S adds up to 0.
    //         Otherwise, it runs forever with no output.
    // Note:  "Program number P" is the program you get by
    //         writing the integer P in binary, then
    //         considering that string of bits to be a
    //         program.  Every possible program can be
    //         generated this way, though most do nothing
    //         because of syntax errors.  

    
    FOR N = 1...infinity
        FOR P = 1...N
            Run program number P for N steps with input S
            IF the program outputs a list of distinct integers
                AND the integers are all in S
                AND the integers sum to 0
            THEN
                OUTPUT "YES" and HALT

The only problem is that if the answer is NO then the program runs forever, and we don't know how long it takes to compute the answer if it is YES. Therefore we can only ever be certain of the outcome if the answer is returned as YES (and that could take infinite time), otherwise the result is unknown.

Am I not getting something?

Yes, you are trying to tackle a problem that is way over your head and because of your lack of knowledge in the area you will over simplify the problem and make incorrect assumptions, much as you did in that physics argument with Glenn. Im not being nasty here, just stating facts, you are not likely to solve this problem in an afternoon, when great mathmaticians such as Turing struggled for years without getting anywhere.

If you are really serious about solving one of these problems, then start by doing some research into it, read /several/ books on the subject and look at some of the failed and half-proofs that have been suggested, figure out why they don't work and see if you can improve them or whether an alternative approach is required. Don't try and whip up some half-cocked proof in a a few minutes after having one person explain what the problem is to you.

[Agamemnus]

What I was tryin' to say is that an infinite parallel-processing machine can use just one of its processors to solve a problem, which would be solvable on a deterministic machine, too. If it uses more than one processor (say infinite), then obviously it cannot take the same time on a deterministic machine because more calculations are taking place.

EDIT: An' I don't see what the big problem of "they know P<>NP but they can't prove it" is, since OBVIOUSLY, given the most efficient algorithm you CANNOT compress two parallel processors into one and still use the same amount of time.

[LooseCaboose]

What I was tryin' to say is that an infinite parallel-processing machine can use just one of its processors to solve a problem, which would be solvable on a deterministic machine, too. If it uses more than one processor (say infinite), then obviously it cannot take the same time on a deterministic machine because more calculations are taking place.

You're still missing the point, if P = NP then all problems belonging to class NP also belong to the class P, we are talking about the problem here, not the algorithm to solve the problem, obviously if P = NP then the algorithm used to solve a problem in NP must be different to the algorithm used to solve it in P. What P = NP says, is that such algorithms exists, however, such algorithms are yet to be found.

I have already said that all problems that can be solved on a non-deterministic machine can also be solved on a deterministic machine, just not in the same amount of time. The travelling salesman problem is solvable on a standard PC, however for moderately large values of n it starts taking longer than the age of the universe to solve. If we had a non-deterministic turing machine (they are only theoritical) we could solve it in an acceptable amount of time.

An' I don't see what the big problem of "they know P<>NP but they can't prove it" is, since OBVIOUSLY, given the most efficient algorithm you CANNOT compress two parallel processors into one and still use the same amount of time.

They don't know that P != NP, it hasn't been proved either way. Some mathmaticians/computer scientists believe that P = NP, others believe it doesn't. As for the second part, you need different algorithms, think Quicksort and Bubblesort, they both solve the same problem, but they do it in a very different amount of time.