0
$\begingroup$

CNFSAT is the language of all strings that are encoding of satisfiable boolean formula in conjunctive normal form while CNFFAL is the language of all strings that are encoding of falsifiable boolean formula in conjunctive normal form.

Any boolean formula is satisfiable if and only if exists an truth assignment of True and False to the boolean variables so that the boolean formula evaluates to true.

Any boolean formula is falsifiable if and only if exists an truth assignment of True and False to the boolean variables so that the boolean formula evaluates to false.

CNFFAL is in $\Bbb{P}$, because the deterministic Turing machine that decides CNFFAL in polynomial time only needs to find falsifiable clause and deciding whether or not disjunction of literals is falsifiable is as hard as deciding 1SAT that is deciding the satisfiability of conjunction of unit clauses, where each unit clause is single literal, and it is also in $\Bbb{P}$.

Because of the fact that $\Bbb{P\subseteq NP}$ CNFFAL is also in $\Bbb{NP}$ and also non deterministic Turing machine to decide CNFFAL is to guess and choose an truth assignment non deterministically and accept if the input boolean formula evaluates to false, reject otherwise.

According to the fact that $CNFFAL\in\Bbb{NP}$ and to the paper of Cook, Levin and Karp that was submitted in 1971, it is also true that $CNFFAL\le_PCNFSAT$.

I want to know if $CNFFAL\le_PCNFSAT\implies CNFSAT\le_PCNFFAL$.

In other words I want to know if it is also true that $CNFSAT\le_PCNFFAL$, because I read the 1971 paper of Cook, Levin and Karp and as I understood, the deterministic polynomial time reduction from an arbitrary NP language to satisfiability problem is done by first describing the non deterministic Turing machine that decides the arbitrary NP language in polynomial time and then there is polynomial time deterministic algorithm to generate the boolean formula that is true on every accept path/route of the non deterministic Turing machine for the input string and it is false on every reject path/route of the non deterministic Turing machine for the input string.

Therefore the string is in the arbitrary NP language if and only if the non deterministic Turing machine that decides the arbitrary NP language in polynomial time accepts the string and the non deterministic Turing machine accepts the string if and only if there exists an accept path/route, i.e. the non deterministic Turing machine has an accept path/route for the input string and there exists an accept path/route or the non deterministic Turing machine has an accept path/route for the input string if and only if the boolean formula is satisfiable.

Let $NTM_{CNFFAL}$ be the non deterministic Turing machine that decides CNFFAL in polynomial time as described above.

Therefore if the input boolean formula $\alpha$ is falsifiable then there exists an accept path/route, i.e. $NTM_{CNFFAL}$ for $\alpha$ as input has accept path/route, but if $\alpha$ is also satisfiable then there also exists reject path/route, i.e. $NTM_{CNFFAL}$ also has reject path/route for $\alpha$, but if $\alpha$ is unsatisfiable then all paths/routes of $NTM_{CNFFAL}$ are accept and therefore the boolean formula $\beta$ generated from $NTM_{CNFFAL}$ is tautology and not falsifiable.

Therefore $\alpha$ is unsatisfiable if and only if $\beta$ is tautology.

Therefore $\alpha$ is satisfiable if and only if $\beta$ is falsifiable.

So my question is does $CNFSAT\equiv_PCNFFAL$?

$\endgroup$
1
$\begingroup$

No, $CNFFAL\le_P CNFSAT$ doesn't appear to imply $CNFSAT\le_P CNFFAL$, as far as we know.

As you say, we know that $CNFFAL\le_P CNFSAT$ is true. However, $CNFSAT\le_P CNFFAL$ is true if and only if $P = NP$.

Consequently, the claim $CNFFAL\le_PCNFSAT\implies CNFSAT\le_PCNFFAL$ is logically equivalent to the claim that $P=NP$. There is no known proof that $P=NP$ (and many would consider it surprising if that is true).

I didn't understand why you think the implication does hold. I couldn't quite follow your reasoning. The notation $\beta$ is never explained clearly (I don't know what you mean by "the boolean formulated generated by a NTM"; NTMs don't generate boolean formulas, so that would need to be defined more clearly). It's hard to know what you might be thinking, but if I were forced to speculated, I'd guess that the flaw in your reasoning might have something to do with the situation where $\alpha$ is both satisfiable and falsifiable. Then it's true that $NTM_{CNFFAL}$ has both an accept path and a reject route, but so what? It's not clear why that would imply anything interesting.

$\endgroup$
  • $\begingroup$ Why CNFSAT is NP Complete? How exactly the reduction from arbitrary NP language to CNFSAT is done? $\endgroup$ – user82452 Jan 10 '18 at 23:07
  • $\begingroup$ @StackExchange, that's a separate question. We're not a discussion forum -- please don't use the comments to ask a new question. A new question should be posted by posting a new question. But in this case, instead, I suggest doing some research. That's covered in standard textbooks and resources (see Cook's theorem). $\endgroup$ – D.W. Jan 10 '18 at 23:33
0
$\begingroup$

If CNFSAT <_P CNFFAL that would make CNFFAL NP-complete but CNFFAL is in P. So such reduction is not possible otherwise CNFSAT would belong to P.

$\endgroup$
  • $\begingroup$ When you say "is not possible", I don't think that's right. I think the correct statement is "not possible unless P = NP"... as explained in my answer. $\endgroup$ – D.W. Jan 12 '18 at 8:15

Your Answer

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