2017-04-03

P=NP is indecidable (conjecture)

"P equals NP?" is a million dollars unsolved problem.

"P" is the class of problems where we have algorithms that solves the problem in polynomial time.

"NP" the class of problems that can be proven in polynomial time once you "guess" the solution.

This is analogous with the sorting problem: it's easier to check the sorting of a list than to actually sort a list.

Of course, if you can fully solve the problem in polynomial time, you can also prove it in polynomial time, so P is included in NP. However, NP seems to contain some very hard problems that cannot be currently solved in polynomial time. It is believed that NP contains some problems that can never be possibly solved in P.

I will not do a formal proof, more like an argument or a sketch. You might have more patience and skills to develop some of this ideas even if they might have flaws in the current form.

You can take it as a conjecture, a mathematical joke or "food for thoughts".

Let's see how it goes: