# P=NP? A reduction of CNF boolean satisfiability to the circulation problem in an undirected graph

The picture below shows how to reduce the Boolean Satisfiability problem in CNF to the circulation problem in undirected graph (see here). As you can see, a[i] are the variables and C[j] are the clauses of a formula in the conjunctive normal form. If there is an edge between a variable (or negated variable) and a clause, it means that the variable participates in that clause with the respective sign.

The flows between variables and their negations are unconstrained. The direction of the resulting flow indicates whether the variable is true or false.

The flows between variables and clauses are unconstrained, as long as edges exist.

There is an additional vertex at the bottom connected to all the clauses, with the edges having the minimum flow of 1 and unconstrained max flow through that edge.

If a circulation doesn't exist, it means that the formula is unsatisfiable.

Do you see any flaws in this solution?

• I'm not sure whether finding flaws in an attempted P=NP proof is a good fit for this site. Our mission is to build an archive of knowledge, in the form of questions and answers, that will be useful to others. The obvious starting point would be for you to see if you can prove your solution is correct.
– D.W.
Mar 8 at 8:15
• Another obvious approach would be to implement it and test it on test suites/benchmarks, as mentioned in cs.stackexchange.com/q/133849/755, cs.stackexchange.com/q/115682/755, cs.stackexchange.com/q/145102/755. It's your job to exhaust all reasonable approaches on your own before asking.
– D.W.
Mar 8 at 8:19

Consider the CNF formula $$a \wedge \neg a$$. This has two clauses, $$a$$, and $$\neg a$$. If I understand your scheme correctly this maps to the following flow problem:
Now consider the CNF formula $$a \wedge b$$. This has two clauses, $$a$$ and $$b$$. If I understand your scheme correctly this maps to the following flow problem: