Can Freecell Algorithms Solve the P vs NP Problem?

[lax1113]

Hey guys,
So I am a big fan of math, but at the moment, I am limited to calculus, so I don't really know much math at all. With that being said, I also happen to watch the show numbers, which is the first place I heard about the problem P vs NP. So after looking it up, I saw that it is a problem that if anyone can prove, they are awarded a million dollars; sounds nuts! Anyway, I was wondering what could be that insanely hard that so many brilliant minds could work on it but still not figure it out, so of course, I looked for a problem statement, and with my limited math knowledge, it was similar to reading a foreign language. This issue popped up again however, when I, after playing a few games of free cell to pass the time, searched to find out if anyone made a freecell algorithm. (I know people have made them for windows games like minesweeper, but it seemed to me this one would be a lot more difficult because there are so many possibilities that change constantly, but then again, it seems hard for me to believe that chess programs can be made to play perfect also.) So anyway, now as I am reading about this, it says that a freecell algorithm would somehow solve the problem P vs NP.

So now as if I wasn't already confused enough from my first glance at the problem statement, I went back for a second helping. Still, written in sanskrit to me. So, I was wondering if one of you math geniuses out there could try to come up with an analogy as to what this problem actually is? Just to put my curiosity to rest and help me get some sleep! (just kidding of course.)

Thanks in advance for any attempt at explaining a supposedly impossible math problem to a calculus student.

 

[epkid08]

Taken from claymath:

one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.

An analogy might be the riemann hypothesis; so many verifications of the hypothesis are found to be true, but is it possible to prove?

 

[Werg22]

Hi lax1113,

A very simple problem in mathematics is to solve one-variable equations of the first degree. For example, take the equation x - 2 = 3. You can see that 5 is a solution because 5 - 2 is 3. You can see that verifying if a value of x solves the equation very simple; I substitute in the said value, subtract 2 and compare the result with 3. If we didn't know that 5 is a solution, we could simply write x = 3 + 2 and then find x = 5.

Both finding the solution to the equation and verifying the validity of a solution are simple. P = NP says, roughly speaking, that all problems for which proposed solutions are simple to verify are also simple to solve, and vice versa.

I said "roughly speaking" because I haven't defined what I mean by "simple". In computer science, a useful concept is that of the complexity or running time of a program. It's a relatively simple concept and you can learn more about it if you look it up on Wikipedia. That said, a program that adds up all numbers in a sequence of n integers has complexity O(n), a program that sums up all the entries of a n x n matrix has complexity O(n^2), a program that computes a^b may have complexity O(log b).

Consider the programs that have polynomial complexity, i.e. have complexity O(p(n)) where p is a polynomial in n and n is the "size" of the problem handled by the program. p(n) doesn't need to be the "tightest" bound on the complexity of the program, a program that has complexity O(log n) also has complexity O(n), O(n^2), O(n^3) because a program that has complexity O(log n) is less "complex" than one that has complexity O(n), or one that has complexity O(n^2) or again O(n^3). Now, we can be more precise in our interpretation of N = NP: it basically says that every problem for which a proposed solution can be verified in polynomial time can also be solved in polynomial time.

Hope this helps.

 

[lax1113]

Werg,
I think i might have understod it better, but to me it seems kind of common knowledge that if you can verify a solution it must be solved. Is it that the math this involves is more advanced than anything i know? or is it just the idea that it needs to be PROVEN and not just assumed that makes it such a hard problem.

 

[HallsofIvy]

"If you can verify a solution it must be solved". Yes, that's true. But that's not the point. The question is whether solving an equation is significantly harder than verifying a solution you are already given.

If I were to claim that x= 2 is a solution of x⁵- 4x⁴+ 3x³- 2x²+ 3x- 6= 0, you could easily determine whether that is true or not. Finding all solutions is much harder. The questio nis whether is "significantly harder" in the sense Werg22 gave.

 

[-Job-]

Another way of putting P vs NP is the following: suppose you're given a set containing n positive and/or negative integers and you're asked to determine if any subset of the numbers sums to 0.

Finding a subset that sums to 0 is difficult because there are 2ⁿ subsets to look at. If you decided to look through all the subsets you'd have to perform at least 2ⁿ comparisons - this solution is valid but scales exponentially because depending on how large the set is, you may have to (in the worst case) perform 2ⁿ comparisons.

Suppose that, in a different scenario you're also given n integers but instead are asked to check if a given subset of the n integers sums to 0, then that's a lot easier - you just sum the n numbers - this scales polynomially because you can sum n numbers in under n² operations.

So whereas solving this Subset-Sum problem seems to require exponentially many operations (comparisons, additions, logical operations, etc), verifying a solution to Subset-Sum can be done quickly in only polynomially many operations.

P in P vs NP stands for the class of problems that can be deterministically (non-randomly) solved in polynomially many operations. NP stands for the class of problems whose solutions can be deterministically verified in polynomially many operations. When we say polynomially or exponentially, that's always with respect to the size of the input that the problem takes.

SubSet sum is in NP (because we've shown we can verify its solutions in polynomial time), however we don't know whether it is in P (a solution to Subset-Sum seems to require exponentially many operations to solve (in the worst case), but maybe we're just not being clever enough).

If Subset sum is in P then the classes of P and NP are equal, otherwise they're different. This is because Subset sum is something called an NP-Complete problem - NP-Complete problems are special because every problem in NP can be reduced to it. This means that if it turns out that you can solve subset-sum in polynomially many operations, then you can also solve every problem in NP in polynomially many operations. NP-Complete problems are some of the toughest problems to solve, but they come up quite often (especially in computer programming).

If you can find a way to solve Subset-sum (or any NP-Complete problem) in polynomially many operations then you have shown that P is equal to NP. If you find a way to show that Subset-Sum (or any NP-Complete problem) can't be solved in polynomially-many operations, then you've shown that P is not equal to NP.

Some very visual (and easy to understand problems) are NP-Complete such as the Clique problem, or variable-sized Sudoku. NP-Complete problems make good puzzle games because a solution to the puzzle is tough to find, but since solutions are easy to verify you'll quickly know when you've solved the puzzle.

Finally, note that most likely P is not equal to NP. Another possibility is that P is not equal to NP, but that this can't be proven. If P were shown to be equal to NP then we'd be able to program computers to efficiently (different than easily) find theorems, or even to create music we'll like, etc. Note also that if it turns out that P is not equal to NP then we can still do these things, but not efficiently, so in the best case we can have a machine randomly guess theorems and check if they're valid (but then it can take forever to find something).

 

[-Job-]

One more thing to add to this, which i find to be very interesting. The classes of P and NP are said to be equal if they contain the same problems, however it can be shown that they're not "exactly equal", by which i mean, there are problems whose solutions require at least n^a operations to find but whose solutions require at least n^b operations to verify, where a is different than b.

However this isn't relevant to P vs NP because we have defined that P and NP are equal if every problem whose solutions can be verified in n^a can also be solved in n^b, it doesn't say anything about lower bounds (it uses can rather than at least) and doesn't require a and b to be equal.

But it does bring up the question of "if P and NP were to be equal, why wouldn't they be exactly equal"?

(BTW, perhaps this thread should be moved to the new Computer Science forum, we get so little theoretical Computer Science threads there it would make that forum a little more on topic).

 

[lax1113]

-Job-
I am sorry, if i knew that it dealt more with CS than math I certainly would have given it to the perspective forum. However, I know this problem mostly from reading about it on sites like claymath and the sort, so it seemed to me from first glance to be a math problem. I would like to thank everyone for posting their interpretation of the probem and trying to put it in simpler terms for me, I do think that I am very close to understanding it. The example of having a program be able to efficiently create music to our tastes seemed to really resonate with me. Although i was starting to understand it from previous posts, this one was the first one that made me understand the actual purpose of it, and applications that it could be used for. Thanks again to all that replied to it!

 

[-Job-]

One note on being able to automate the creation of music and the search for mathematical theorems: it has been said that if P = NP then we can automate human creativity. The reason for this (i imagine) is that there are plenty of things (such as art) which it seems we can easily recognize as being remarkable and pleasant, but which we know are difficult to create following a deterministic process. However, what constitutes "easy to do" for a human is very different than what constitutes "efficiently computable" for a machine because we are talking about "different architectures", so there's no reason to suspect that what a human can compute in polynomial time coincides with what a machine can compute in polynomial time.

In addition, these applications of P=NP are fairly abstract (because for one they involve likes and dislikes) so there's no formal proof that "creating art" is an NP-Complete problem, in fact i can see where in some scenarios it's not, so i would leave this in the realm of realistic speculation because until we have formal definitions to work with we won't know the true complexity of these things.

 

[lax1113]

-Job-
What you say seems to be very frightening. If a machine can mimic human creativity, then isn't that what most science fiction novels/movies of robots taking over the world all about? (I robot... AI...) I mean if a machine can efficiently think like a human, they have the power to process everything so much quicker, so it seems to me that P vs NP isn't a very good thing haha. Maybe I'm getting abit ahead of myself, but really the problem itself is a lot more clearer now. I went from soe thing related to free cell, now to what i know from all the great posts. Thanks a lot guys!

 

[Cincinnatus]

One note on being able to automate the creation of music and the search for mathematical theorems: it has been said that if P = NP then we can automate human creativity. The reason for this (i imagine) is that there are plenty of things (such as art) which it seems we can easily recognize as being remarkable and pleasant, but which we know are difficult to create following a deterministic process. However, what constitutes "easy to do" for a human is very different than what constitutes "efficiently computable" for a machine because we are talking about "different architectures", so there's no reason to suspect that what a human can compute in polynomial time coincides with what a machine can compute in polynomial time.

In addition, these applications of P=NP are fairly abstract (because for one they involve likes and dislikes) so there's no formal proof that "creating art" is an NP-Complete problem, in fact i can see where in some scenarios it's not, so i would leave this in the realm of realistic speculation because until we have formal definitions to work with we won't know the true complexity of these things.

This is of course why everyone reasonable thinks that P does not equal NP, we just don't know how to prove it. In fact, the main endeavor of complexity theory today is largely to prove that various other problems are equivalent to proving P versus NP. All those complexity class diagrams that people draw are almost all contingent on P not equaling NP. If P did equal NP they'd mostly all collapse.

 

[Werg22]

-Job-
What you say seems to be very frightening. If a machine can mimic human creativity, then isn't that what most science fiction novels/movies of robots taking over the world all about? (I robot... AI...) I mean if a machine can efficiently think like a human, they have the power to process everything so much quicker, so it seems to me that P vs NP isn't a very good thing haha. Maybe I'm getting abit ahead of myself, but really the problem itself is a lot more clearer now. I went from soe thing related to free cell, now to what i know from all the great posts. Thanks a lot guys!

There's nothing frightening about it. Machines don't have freewill regardless of whether or not they can produce good music.

 

[enigmahunter]

NP is just the derived concept from a nondeterministic Turing machine.
The interesting problems of NP are the NP complete problems. Every problems in NP are polynomial time reducible to the problems in this completeness class. If we find a polynomial time algorithm for any of NP complete problem, NP becomes P. But no one has found the polynomial time algorithm for any of more than 3000 thousands http://en.wikipedia.org/wiki/List_of_NP-complete_problems" .

Machines don't have freewill regardless of whether or not they can produce good music

A computer cannot compete with a human for certain things.

1. AI can beat a chess master in a chess game, but hardly beat human in a "Go" game.
2. A human can find an acquaintance in the crowd relatively easy in comparison to an AI machine.
...

It is because AI relies on search mechanisms, but sometimes it involves a high computational complexity and the algorithms for pattern recognitions are not mature enough comparing with human's.

Anyhow, a contemporary AI can mimic certain human behaviours such as autonomous driving using http://en.wikipedia.org/wiki/Neural_network" .

 

[-Job-]

The interesting problems of NP are the NP complete problems.

There's a few non NP-Complete problems in NP (or at least not known to be NP-Complete)that i find very interesting, these are:
1. Factoring
2. Graph Isomorphism

Remarkably these problems haven't been shown to be NP-Complete. The second one in particular is surprising seeing as SubGraph Isomorphism is NP-Complete. They don't seem to be neither in P nor NP-Complete.

 

[-Job-]

There's nothing frightening about it. Machines don't have freewill regardless of whether or not they can produce good music.

In the same way that i don't know that i have freewill I'm not sure whether a machine would or would not have it as well. Personally i don't find it impossible for machines to have the same free will as humans, because i don't think that it's out of the picture that we both have none. I may only think that i have free will, possibly because i know that i will do something before i do it, but in my opinion that doesn't imply that the decision to do something was made by me or that i had a chance to change it.

Here's an idea, unreasonable (unpleasant) as you might find it: the activity generated as part of the decision to move my foot will have local impact on my brain before it reaches the foot and causes movement. This type of association of know-decision -> see-decision-carried-out could condition us to think that we "have decided" to do something when we have merely identified the decision before it has been carried out.

 

[lax1113]

I like the analogy between machine free will and humanistic free will. However, to the poster that claimed that machines cannot have free will, I am not trying to just refute anything you say, but how can anyone be sure of a machine not having free will when something like this problem has not been proven? Alot of psychological research claims that genes influence everything a person does, so by our genes dictating our actions is that in a way limiting our free will? I think this goes back to what job was saying, but I really think you can only say machines don't have free will, until, they have been given free will. In whatever way you want to think about it, big bang/religious pretext, humans were at one point made. Whether they evolved from a much simpler organism, that organism or cell was still at one point created right? So by this way, woudln't it be possible for humans to create something that eventually would develop its own free will?