P!=NP (duh) Part 1 of 4:

A Humble P vs NP Proposal

This blog series is an open call for feedback and discussion of a novel concept and informal proof that I would like to formally submit to the great P vs NP cabal. Having worked on the problem off and on for almost 10 years (mostly in a silo) it’s high time to share the outcomes of my efforts and see if they have any merit.

This series will cover all the concepts in my original paper:

pnp_arxiv.pdf

In a sentence, P does not equal NP, it was silly to think it ever could. The problems that are in NP can be so mind-bogglingly difficult no real machine could ever solve them in a reasonable time.

My intended reader may have any level of technical knowledge but must have a fascination and prerequisite knowledge of the P vs NP problem.

Source: Wikimedia Commons

Intuition that P != NP

It always bugged me that many descriptions of P vs NP emphasize that NP problems only need to have some solutions be quickly verifiable. The only solutions they seem to care about are those that answer “yes” and can provide an easy-to-verify example to the decision problem.

The subset sum problem asks us to identify if any subset of a list of integers sums to 0. There are an exponential number of possible “answers”, as every possible subset might sum to 0 in some instances. An algorithm for subset sum must perform a search, looking through all possible subsets of the input. As it works, it will prove many subsets do not sum to 0, and if it finds one that does, hooray! It can stop and rest. However, if there are no subsets that sum to 0 it will have to prove that fact, which will almost always be harder than when there is a positive example.

Subset (Sum)mary

If you’re looking for a needle that may or MAY NOT be in a haystack, it will always be easier to find a needle than it will be to prove that there is no needle. Many descriptions of NP overemphasize the importance of how easy it is to prove that a needle is a needle when you find it. The algorithm solving the problem could care less, it is concerned with how hard it is to find the dang needle in the first place. More importantly, if the size of the haystack is getting exponentially larger as the input gets larger, and the algorithm does not have any shortcuts for easily searching through large swathes of the haystack, then THAT will determine if a problem is difficult, not whether or not it’s easy to prove that a needle is a needle.

Subset Sum Metaphor Components. Note: subset sum is an example of a “difficult” problem, as the haystack grows very quickly as n becomes large, AND there is no known algorithm that has enough shortcuts to keep up with how fast the haystack grows.

Again for clarity, easy problems either have haystacks that grow slowly or have shortcuts that allow the algorithm to quickly prove that large sections of the haystack do not contain the needle. I say all this to point out that there is very little intuitive reason why a problem that is easy to verify should also be easy to solve, as the work required of the verifier is incidental to the true difficulty of the problem.

Proof Overview

The proof covered in this series has three sections.

1. We walk through the Halting Problem, as the intuition behind it will prove invaluable for understanding our proof of P!=NP. (<post 2>)
2. We lay out an extremely difficult problem and prove that it is in NP. In a sentence, the problem asks: “For a machine M of length n, and an input set X, does M stop in s steps for any possible M(x).?” (<post 3>)
3. We prove that for sufficiently complex problems, there are combinations of M and x that prevent any algorithm from solving the problem in P time. Similar to the Halting Problem, there are self-referential inputs to our problem that by their nature, cannot be solved for in P time. (<post 4>)