HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

3-sat to 2-sat reduction

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
satreductionstackoverflow

Problem

It is known that 3-SAT belong to - NP-Complete complexity problems, while 2-SAT belong to P as there is known polynomial solution to it.

So you can state that there is no such reduction from 3-SAT to 2-SAT unless $P=NP$.

I am looking for strong proof for this state, regardless NP belong to P or not.

Solution

You can prove it by contradiction:

Suppose that $P \neq NP$ and there is a polynomial-time reduction from 3-SAT to 2-SAT; then 2-SAT is NP-complete, but 2-SAT is also solvable in polynomial time, so
for all decision problems $A \in NP$ you can decide $x \in A$ reducing $x$ to the corresponding 2-SAT instance in polynomial time and solve it in polynomial time (and the total time is still polynomial); so $A \in P$ and hence $NP \subseteq P$. But we also have $P \subseteq NP$, so $P = NP$ which is a contradiction. :-)

Context

StackExchange Computer Science Q#18643, answer score: 11

Revisions (0)

No revisions yet.