Understanding Fermat's Last Theorem

[Mentallic]

What does this mean? I'm aware it's one of the millennium problems but I can't seem to find any general understanding of what really is required to be proven here. For example, I understand the Riemann hypothesis clearly (thank god)

I've also heard there are many implications in the science and mathematics if this is proven/disproven. What are these, and how do they relate to this problem?

It's sometimes the case that even though something has yet to be proven, it's accepted as true since the formula (or whatever) has worked for all numerical cases thus far. Is this problem swaying more towards P=NP or P$\neq$NP?

I'm just out of high school so if this can be explained with mathematics at my level, it would be even better else, an explanation with words will probably surpass any high-level mathematics in its ability to get its point across to me.

Thank you!

edit: I mean Fermat's Last Theorem.

 

[CRGreathouse]

For example, I understand the Riemann hypothesis clearly (thank god)

I find it hard to imagine that you understand the Riemann hypothesis clearly but don't understand P = NP. P = NP is extremely simple to understand; the RH, less so.

Would you explain your understanding of the RH, just to sate my curiosity?

What does this mean? I'm aware it's one of the millennium problems but I can't seem to find any general understanding of what really is required to be proven here.

P is the class of decision ("yes-no") problems that can be solved in polynomial time. That is, there is some polynomial f(x) such that a problem of size x can be solved in time at most f(x) computational steps. Bubble sort takes about n^2/2 steps to sort n elements; thus, sorting is in P.

NP is the class of decision problems for which a "YES" answer can be checked in polynomial time. That is, there is some "proof" (whatever that means!) that a checking program can use to verify that a solution is correct. There's no obvious way to tell that 2931297790285276172100889 is composite, but it's easy to check that it is composite if I give you a proof in the form of a factor (1891204835771). So COMPOSITES is in NP.

P = NP means that all decision problems that can be easily checked can be easily solved. That is, there's no need for a proof -- the problem could be solved without it in polynomial time. (It might take a billion times longer, or 10^100 * n^20 times longer... but still in polynomial time.)

P ≠ NP means that there is some problem which can be checked in polynomial time but which cannot be solved in polynomial time.

It's sometimes the case that even though something has yet to be proven, it's accepted as true since the formula (or whatever) has worked for all numerical cases thus far. Is this problem swaying more towards P=NP or P$\neq$NP?

There is a strong consensus for P ≠ NP. (There's a survey showing a surprising number of experts as undecided; I couldn't immediately find a link, though.)

I've also heard there are many implications in the science and mathematics if this is proven/disproven. What are these, and how do they relate to this problem?

There are probably thousands of results in computer science that are proved conditional on P ≠ NP. For example, if P ≠ NP there are problems which are in NP but are neither in P nor in NPC (NP-complete; in a certain sense, the 'hardest' problems in NP). This class is called NP-Intermediate and probably includes graph isomorphism.

 

[Mentallic]

I find it hard to imagine that you understand the Riemann hypothesis clearly but don't understand P = NP. P = NP is extremely simple to understand; the RH, less so.

Would you explain your understanding of the RH, just to sate my curiosity?

Oh my yes you got me there. I've mistaken Fermat's Last Theorem for the Riemann hypothesis

Thanks a lot for that explanation! But I still have a few more queries:

You keep mentioning that it can be solved in polynomial time. If each problem has an independent polynomial time (i.e. The time to solve f(x) for a given size x is different for each problem) then how is it possible that you can call it polynomial time, not constant time or exponential time (or any other for that fact)?

Also, I'm having difficulty comprehending how to even start proving/disproving P=NP in any shape or form. I know this has yet to be proven, but mathematicians have spent a great deal of time trying to. What would one even start doing if they were intent on trying to prove this hypothesis?

Finally, how is it possible that a proof of this "thing" would allow for knowing if each and every problem can be solved (and exactly what type of problems are they)? Possibly an example in terms of something more elementary in mathematics would make this clearer.

 

[CRGreathouse]

You keep mentioning that it can be solved in polynomial time. If each problem has an independent polynomial time (i.e. The time to solve f(x) for a given size x is different for each problem) then how is it possible that you can call it polynomial time, not constant time or exponential time (or any other for that fact)?

I'm going to interpret your question as "What is the difference between polynomial time and exponential time?".

A problem is solvable in exponential time if, for every unit increase in the problem size (e.g., every additional byte of input) the time required is multiplied by some fixed amount. A problem is solvable in polynomial time if multiplying the input size by some fixed fraction multiplies time required by some fixed number (need not be the same number).

So "+1 size => x2 time" is exponential, while "x2 size => x8 time" is polynomial. You can see that these are quite different: if the current size is 100, then the polynomial example will take 8 times as long to do size 200, while the exponential example will take about 1.3 x 10³⁰ times as long.

Yes, different problems can use different polynomials.

Also, I'm having difficulty comprehending how to even start proving/disproving P=NP in any shape or form. I know this has yet to be proven, but mathematicians have spent a great deal of time trying to. What would one even start doing if they were intent on trying to prove this hypothesis?

It's not clear how the problem can be solved. I would expect it to be extremely difficult. The only real progress that has been made (IMO) on the problem has been ruling out large classes of techniques toward solving the problem. For example, techniques which relativize cannot be used to solve the conjecture. Scott Aaronson has a good paper on the latest of these, algebraization.

Finally, how is it possible that a proof of this "thing" would allow for knowing if each and every problem can be solved (and exactly what type of problems are they)?

I'm really not sure what you're saying here.

 

[Mentallic]

(e.g., every additional byte of input)...
Yes, different problems can use different polynomials.

Ahh I see. I was unsure if the same problem could be increased in size which would thus show whether the problem is being solved in polynomial or exponential time.

It's not clear how the problem can be solved. I would expect it to be extremely difficult. The only real progress that has been made (IMO) on the problem has been ruling out large classes of techniques toward solving the problem.

Interesting! I can see now that not knowing where to even try and head towards would make proving something very difficult indeed.

I'm really not sure what you're saying here.

Sorry, I'll try be more clear:

There are probably thousands of results in computer science that are proved conditional on P ≠ NP.

I cannot seem to comprehend how this one result of P$\neq$NP can seemingly prove thousands of other independent results in computer science.
It's just that I can't seem to find an example for myself with elementary math that has the power to do what P$\neq$NP can do.

 

[JSuarez]

I cannot seem to comprehend how this one result of PNP can seemingly prove thousands of other independent results in computer science.
It's just that I can't seem to find an example for myself with elementary math that has the power to do what PNP can do.

This happens because there is a particular class of NP problems that are called NP-complete; if you managed to find a polynomial time algorithm that solves a NP-complete problem, them all NP problems can also be solved in a polynomial time.

This works like this: in the seventies, Stephen Cook in the US and Leonid Levin in the USSR proved that there was one NP-problem (called SATISFIABILITY, or SAT; it has to do with logical expressions), such that, given another arbitrary NP-problem, say R, there was a translation algorithm that enable us to transform any instance of R in an instance of SAT, in a polynomial number of steps. Therefore, if we had an polynomial-time algorithm for SAT, we could first reduce any instance of R to SAT, and then decide the instance of SAT; as the composition of two polynomials is a polynomial, we could decide R in polynomial time.

Since then, hundreds of problems were shown to be NP-complete. To give an example, do you remember the Minesweeper game? It's NP-complete: if you manage to come up with an algorithm that solves Minesweeper in a number of steps that is polynomial in the size of the board, then you can solve any other NP problem.

 

[CRGreathouse]

I cannot seem to comprehend how this one result of P$\neq$NP can seemingly prove thousands of other independent results in computer science.
It's just that I can't seem to find an example for myself with elementary math that has the power to do what P$\neq$NP can do.

JSuarez mentions one class of results: a problem known to be NP-Complete is known to be in P if and only if P = NP. So proving that P ≠ NP would prove that none of these problems are in P.

Another class of results are approximation theorems. These take the form "Problem X cannot be approximated to within Y in polynomial time, unless P = NP". (Of course if P = NP they can be approximated as closely as desired in polynomial time, since they can be solved exactly in polynomial time.) For one random example: maximum bin packing cannot be approximated more closely than 1.5 times the optimal in polynomial time, unless P = NP. Some problems, like SET-COVER, cannot be approximated tow within any constant factor unless P = NP.

But there are many unrelated results conditional on P ≠ NP. Perhaps someone familiar with complexity theory (or even TCS more broadly) will stop by and add their favorite examples. For now: http://qwiki.stanford.edu/wiki/Complexity_Zoo:T#tally ) has no NP-Complete problems, unless P = NP. I already mentioned the NP-Intermediate result, conditional on P ≠ NP.Edit: For some good reasons to think P ≠ NP, see
http://scottaaronson.com/blog/?p=122

 

[CRGreathouse]

I cannot seem to comprehend how this one result of P$\neq$NP can seemingly prove thousands of other independent results in computer science.

Here's a simpler explanation that's more "big picture" and probably closer to what you wanted.

Many interesting problems in computer science are closely tied to the question of P vs. NP. For example, if a question of the form "Can X be approximated arbitrarily closely within polynomial time?" (where X is an NP-compete problem) can be answered in the negative, then P ≠ NP. But current methods do not allow us to prove P ≠ NP, so we can't prove interesting problems of this form either. But often the rest of the problem can be solved, so instead of proving the interesting theorem Y, instead we prove a theorem of the form
If P ≠ NP, then Y.

So hundreds -- no, make that thousands -- of papers have been published which take this exact path: while they cannot prove Y, they can prove Y conditional on P ≠ NP. So it is not that P ≠ NP will show us thousands of new things (though its proof might!), but more that it ties up the loose ends on many different and otherwise unrelated projects.

Did that make sense?