CODEWITHSUNDEEP
algorithmnp-completesat
nahum-6
nahum-6

Reputation: 33

Twice-3SAT NP-complete

I wanted to solve the following problem about 3SAT . "TWICE-3SAT Input: how to show it is NP-hard and has more than one satisfiable assignments"

Upvotes: 3

Views: 737

Answers (1)

Rafał Dowgird
Rafał Dowgird

Reputation: 45081

Reduction from 3SAT: take a 3SAT instance and add a dummy variable with a dummy clause, i.e. [original formula] AND (dummy OR not dummy OR dummy). The dummy will not affect the evaluated value of the formula whatever dummy's value is.

The resulting instance has twice as much satisfying assignments as the original one, because each original assignment generates two for the modified formula: one with dummy = true and another with dummy = false. So the resulting instance has at least 2 satisfying assignments iff the original one has at least one.

Upvotes: 3

Related Questions