0
$\begingroup$

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. A reduction of CNF boolean satisfiability to the circulation problem in an undirected graph

Do you see any flaws in this solution?

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Mar 8 at 8:15
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Mar 8 at 8:19

1 Answer 1

6
$\begingroup$

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:

flow problem

This clearly has a solution (1 flow going in a circle) while the formula itself is clearly unsatisfiable. So your algorithm gives false positives.

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:

flow problem 2

This has no solution (there doesn't exist a cycle in the graph), yet the formula is clearly satisfiable. So your algorithm also gives false negatives.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.