P=NP, isn't it?

Question

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?

Answer 1

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.

Answer 2

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.