1
$\begingroup$

Cook and Levin showed in 1971 how deterministically in polynomial time from every non deterministic Turing machine M, that halts in polynomial number of moves/steps, and string w to create the boolean formula $\Phi_{M,w}$ in conjunctive normal form that is true for each accept path/route of M on w and false for each reject path/route of M on w and therefore $\Phi_{M,w}$ is satisfiable if and only if M accepts w.

Suppose $NTM_{CNFFAL}$ is non deterministic Turing machine that decides in polynomial time the language CNFFAL, that is the language of all strings that are encoding of falsifiable boolean formulas in conjunctive normal form, by just guessing truth assignment that evaluates the input boolean formula to false.

Let f be any boolean formula in conjunctive normal form.

Therefore $\Phi_{NTM_{CNFFAL},f}\equiv\lnot f$ since Cook and Levin reduction is parsimonious and $\Phi_{NTM_{CNFFAL},f}$ is also in conjunctive normal form.

Therefore f is falsifiable if and only if $\Phi_{NTM_{CNFFAL},f}$ is satisfiable.

Therefore f is satisfiable if and only if $\Phi_{NTM_{CNFFAL},f}$ is falsifiable.

This suppose to show that $CNFSAT\le_PCNFFAL$, where CNFSAT is the language of all strings that are encoding of satisfiable boolean formula in conjunctive normal form, also show that CNFFAL is NP Complete, since CNFSAT is already NP Complete and we all know that $CNFFAL\in\Bbb{P}$.

Therefore $\Bbb{P=NP}$, isn't it?

$\endgroup$
  • 3
    $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jan 17 '18 at 22:32
  • 4
    $\begingroup$ I find all the bold-faced words a little bit overwhelming, don't you? $\endgroup$ – Andrej Bauer Jan 18 '18 at 7:41
  • 1
    $\begingroup$ It hurts my eyes.. $\endgroup$ – Aditya Jan 18 '18 at 17:50
1
$\begingroup$

In the comments of Yuval Filmus' answer, the OP suggested that while, for any two CNF formulas $f$ and $\tilde{f}$,

($f \text{ falsifiable} \iff \tilde{f} \text{ satisfiable}) \iff (f \text{ satisfiable} \iff \tilde{f} \text{ falsifiable}$)

wasn't usually true, it was implied in that specific case by the parsimonious reduction of the CNFFAL instance $f$ to the CNFSAT instance $\tilde{f}$, thus proving that

$f \text{ satisfiable} \iff \Phi_{NTM_{CNFFAL},f} \text{ falsifiable}$.

This answer is supposed to show evidence that it isn't the case (assuming it isn't clear to the reader), as a complement of the previously mentioned answer (per request of the OP in the comments).


I'll try to exhibit an example making clear that it isn't the case. Now, building the corresponding $\Phi_{NTM_{CNFFAL},f}$ of some $f$ would be a bit tedious, so I'll build a parsimonious reduction from CNFFAL to SAT instead (contrast with the parsimonious reduction from CNFFAL to CNFSAT used in the question), but such that the falsifiability of the SAT instance doesn't imply the satisfiability of the CNFFAL instance.

I claim that, for any CNF formula $f$, any assignment $(a_1, \dots, a_n)$ falsifying $f(a_1, \dots, a_n)$ allows me to build a unique satisfying assignment of $\tilde{f}(a_1, \dots, a_n, c) = \lnot f(a_1, \dots, a_n) \land c$ (and vice-versa). This (admittedly dumb) reduction from CNFFAL to SAT preserves the number of solutions so it's parsimonious.

Now let's assume $f(a, b) = (a \lor b) \land (\lnot a \lor b) \land (a \lor \lnot b) \land (\lnot a \lor \lnot b)$.

There indeed are as many ways to falsify $f$ as to satisfy $\tilde{f}$ (4, per the previous parsimonious reduction). Therefore:

$f \text{ falsifiable} \iff \tilde{f} \text{ satisfiable}$

However there also are 4 ways to falsify $\tilde{f}$ (just set $c$ to 0) whereas $f$ is clearly unsatisfiable. Therefore:

$\lnot(f \text{ satisfiable} \iff \tilde{f} \text{ falsfiable})$

Contrast this with that excerpt of the reasoning in the question:

Therefore $\Phi_{NTM_{CNFFAL},f}\equiv\lnot f$ since Cook and Levin reduction is parsimonious and $\Phi_{NTM_{CNFFAL},f}$ is also in conjunctive normal form.

Therefore f is falsifiable if and only if $\Phi_{NTM_{CNFFAL},f}$ is satisfiable.

Therefore f is satisfiable if and only if $\Phi_{NTM_{CNFFAL},f}$ is falsifiable.


The previous statement stems from the fact that $\tilde{f}$ uses more variables than $f$, hence the number of possible assignments of $\tilde{f}$ is greater than the number of possible assignments of $f$. Indeed, if those two numbers of possibilities were equal, the reduction being parsimonious would indeed lead to the equivalence of $f$ being satisfiable and $\tilde{f}$ being falsifiable (by a simple counting argument, as the set of falsifiable assignments is the complement of the set of satisfiable assignments).

In the question, $\Phi_{NTM_{CNFFAL},f}$ has been obtained thanks to Cook-Levin's reduction from an arbitrary NP problem to CNFSAT. That formula doesn't necessarily requires the same amount of variable as $f$ (and is actually very likely to require a far greater amount), so the equivalence doesn't necessarily holds.

$\endgroup$
  • $\begingroup$ Every falsifying assignment of $f$ is accept path/route of $NTM_{CNFFAL}$ on $f$ that is satisfying assignment of $\Phi_{NTM_{CNFFAL},f}$ and every satisfying assignment of $f$ is reject path/route of $NTM_{CNFFAL}$ on $f$ that is falsifying assignment of $\Phi_{NTM_{CNFFAL},f}$. Even if $\Phi_{NTM_{CNFFAL},f}$ has more boolean variables, atoms, literals and clauses than f, still $\Phi_{NTM_{CNFFAL},f}\equiv\lnot f$, no? $\endgroup$ – user82913 Jan 18 '18 at 0:27
  • 1
    $\begingroup$ @user82913 Well not quite but close ! Let's assume you "identify the variables of $f$" inside $\Phi_{NTM_{CNFFAL},f}$ and that you set them to a falsifying assignment of $f$. Now, there are still other variables you need to set which help to ensure the assignment encodes a correct execution, for instance, describing a state at some instant t... just completely mess with them so that they have incoherent values (for instance the assignement would describe a machine in two different states at the same time). That way, you have $\lnot f$ true but $\Phi_{NTM_{CNFFAL},f}$ false. $\endgroup$ – Caninonos Jan 18 '18 at 1:02
  • $\begingroup$ But $\Phi_{NTM_{CNFFAL},f}$ can still be helpful to decide the satisfiability of f somehow, no? $\endgroup$ – user82913 Jan 18 '18 at 1:19
9
$\begingroup$

Every CNF is falsifiable (choose a clause and choose a truth assignment which falsifies it). Unfortunately, the opposite of "CNF $\varphi$ is satisfiable" is not "CNF $\varphi$ is falsifiable". Rather, it is "CNF $\varphi$ is not satisfiable".

Also, even the two were opposites, your proof would only show that NP=coNP, which is not known to imply that P=NP.

$\endgroup$
  • 1
    $\begingroup$ I agree with the error, but I just want to clarify your last remark : you're saying that if "satisfiable" was equivalent to "not falsifiable" and that an arbitrary CNF formula wasn't trivially falsifiable (implicitly implied because the converse would be very weird with the previous assumption), then it would only prove NP=coNP. Correct ? $\endgroup$ – Caninonos Jan 17 '18 at 21:17
  • 1
    $\begingroup$ Right, it would only show that NP=coNP. $\endgroup$ – Yuval Filmus Jan 17 '18 at 21:19
  • 1
    $\begingroup$ @user82913 Actually, I thought the Cook-Levin theorem was a reduction of any NP problem to SAT (and not necessarily CNFSAT) and I'm not sure there is a parsimonious reduction from SAT to CNFSAT. But maybe I'm misremembering things. At least, your reasoning has to fail somewhere because if it's correct, it also proves CNF formulas are both falsifiable and satisfiable which sounds very wrong. $\endgroup$ – Caninonos Jan 17 '18 at 21:38
  • 2
    $\begingroup$ @user82913 i don't think it's wrong that a CNF formula is both falsifiable and satisfiable. The problem is that you prove that all of them are. $\endgroup$ – Caninonos Jan 17 '18 at 21:53
  • 1
    $\begingroup$ @user82913 Ah sorry, I think I know why even if you assume that CNFSAT is parsimonious (which it might actually be, contrary to what I remembered, that's not the problem) your equivalence doesn't hold. The number of accepting paths for $\Phi_{NTM_{CNFFAL},f}$ certainly is the same as the number of ways to falsify $f$. The thing is, $\Phi_{NTM_{CNFFAL},f}$ and $f$ don't necessarily have the same size, so the number of ways to falsify $\Phi_{NTM_{CNFFAL},f}$ isn't necessarily the same as the number of ways to satisfy $f$, in particular, the former might be far greater than the later (0). $\endgroup$ – Caninonos Jan 17 '18 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy