A Solution of the P versus NP Problem?

Do you have a reference to a reputable source that proves the optimization version is cook-reducable to decision version?

I don't get why having multiple optimal paths would falsify my algorithm. Can you provide an explicit counter-example?

Here is why I think the algorithm is correct:

At each step the edge that we are considering is either contained in all the optimal solutions or only some of them. If the edge is contained in all the solutions, increasing its weight to infinity would change the optimal solution and we pick that edge in our solution. Otherwise (if the edge is contained in only some of the solutions) increasing the weight would not change the solution because there is another optimal solution that does not contain that edge so we do not pick that edge.

So we can prove this theorem: At every step of the algorithm if an edge is picked, it is contained in all the optimal solutions.

So the algorithm does not pick any extra edges. Now we have to prove that it includes all the necessary edges. But that is easy because each time that we choose not to including an edge, we are sure that there is an optimal solution in the remaining graph so we are never left with a graph with no optimal solution.

I think you assumed that I meant we change the edge weights from infinity back to their original value at each step but that is not what I meant.

In practical terms, a solution to P=NP is very likely to have absolutely no impact on our algorithms, even if the solution is that P=NP. The main utility is in our understanding of complexity theory, and a better understanding of why certain problems, and certain instances of problems, have to be hard.

Let me explain why P=NP probably won't have any impact, since you see a lot of bullshit claiming lots of bad things will happen. The description of complexity classes like P and NP sweep a lot of details under the rug, and those details matter a lot of practical matters.

The more important of these matters is that complexity is based on worst-case running time, not average-case or typical-case. Often times, we can solve most instances of "hard" problems. We can factor most integers, for example--half of them are divisible by 2, and another sixth divisible by 3. If we limit are inputs to factoring products of two primes of roughly equal size, that is difficult. SAT is another example: it may be the canonical NP-complete problem, but many people think nothing of using a SAT solver (or its cousin, the SMT solver) to solve for things like "how do I find an input that can reach this program point." Except if solving that condition requires, say, finding SHA256(x) = binary digits of pi.

This is one of the main cruxes of P?=NP that doesn't come out much: it's not so much that problems are hard or easy, it's that there's this field of problem instances that seem to be intrinsically hard. Indeed, if you look at restricted versions of these NP-complete problems, you'll find that some restrictions still retain NP-complete, but a very slight reduction in those restrictions suddenly admits a very simple, fast, easy solution.

The related notion that you see people sometimes bring up and dismiss is that P and NP hide constants. This objection tends to be dismissed because most people have no familiarity with polynomial-time algorithms with massive constants. But such algorithms do exist, and they tend to crop up in combinatorial-style algorithms. Which, incidentally, is probably what a polynomial algorithm for an NP-complete problem would be.

Let me explain by analogy of a not-so-recently-solved problem that's a weaker but related notion to P?=NP, L?=SL. This question is essentially asking "could you solve every problem that's equivalent to checking for connectivity in an undirected graph using only constant memory" [1]. The answer turns out to be yes. In essence, there is a deterministic string of coin flips deciding your next vertex that will, if followed, eventually guarantee that you will hit every node in the graph that you can reach within a certain amount of time--if your graph has certain properties. And it's possible to transform every graph into one with this property by replacing every node with an expander graph that's only of size 3^2^16 at the smallest. But since the new graph is 3^2^16 * N, that large number is a constant factor that "doesn't matter".

These kinds of constants show up a lot in combinatorial algorithms. All of these algorithms basically have the property that you can solve the input fairly easy if the input has some structure, but to guarantee that the input has that structure, you need to embed it in a very large instance. I argue that, if P=NP were to hold, it would have a similar form to these algorithms. We know that there are some instances that just seem to be intrinsically harder than others, and we know that there are large classes of instances that can be easily solved with fast algorithms. If we haven't been able to generalize the fast algorithms to cover the hard instances but a "fast" (ignoring constants) algorithm must exist, then the apparent complexity has to be generated from sort of fiendish complexity-multiplying, combinatoric structure.

We already see in modern security algorithms that ciphers and hashes have to carefully choose their parameters to make sure they stay in a hard subset of their input algorithms. So even if P=NP, the hard subset is likely to remain much harder than the easy subset, and that gap is sufficient to maintain security.

[1] A very imprecise characterization.

As far was most mathematicians and computer scientists would go, ZF and predicate logic together with a fixed definition of turing machines.

Let me take a stab at explaining that, although I'm not really an expert and probably misunderstanding something. Hopefully someone else will be able to correct me where I'm wrong.

The clique function takes a bit string representation of a graph with m nodes (one bit for each pair of nodes, 1s where there is an edge between two nodes) and outputs whether the graph has a fully connected subgraph of size s (a clique).

CNF and DNF are conjunctive and disjunctive normal forms, respectively. CNF has the form (x OR (NOT y) OR ... ) AND ((NOT z) OR y OR ... ) AND ..., while DNF has AND and OR exchanged. Any boolean function can be expressed as CNF or DNF, but this might blow up its size exponentially.

The monotone network complexity is the number of binary {AND,OR} gates you need to compute a function. Monotone because increasing the input (setting a bit to 1) never decreases the output. The basic gates have this property, and if you never use NOT the composition has it too. This means that monotone networks can only compute monotone functions. The clique function is monotone, since adding an edge can never destroy an existing clique.

The CNF-DNF-approximators mentioned are a technique for creating a CNF (or DNF) of such a network by introducing a limited amount of errors (hence approximator) at each step. This is done by switching between CNF and DNF at each gate, but discarding parts of the formula that get too large. (I don't really understand how that keeps the error bounded.)

Using the properties of the clique function, it is possible to show that the total number of errors by a limited CNF-approximator must be large, which means that the switching procedure must have been applied many times. This gives a lower bound on the number of gates in any monotone network that computes the clique function, and this bound is exponential.

The paper under discussion attempts to extend this result to non-monotone networks, which can also make use of negation. To do that, it extends the CNF/DNF-switching to also handle negated variables without introducing significantly more errors. (Again, I don't understand how that works.)

Assuming the extension is correct, any bound on the monotone network complexity using CNF-DNF-approximators also holds for the non-monotone network complexity of the given monotone function.

Applying this to the exponential lower bound of the clique function, this means that there is no non-monotone network of a polynomial number of gates that computes it, which implies that there is no polynomial-time Turing machine, which implies P != NP.