Why is 2-SAT decidable in linear time when maximising the number of satisfied two-literal clauses is NP-hard?
answer
- which version of the problem is asked
- hard constraint versus scored preference
- implications hold only if all clauses must
- breaking clauses removes forced propagation
- the decision form asks at least k
basics
~20 sDeciding 2-SAT works because every clause is a hard constraint, so falsifying one literal forces its partner and consequences propagate. Once clauses may be broken, nothing is forced — you are choosing which to sacrifice — and that version is NP-hard at width two.
solid answer
~50 sThe linear-time 2-SAT algorithm depends on a clause being a hard constraint. `(a or b)` becomes `not a -> b`, and that implication is sound only while every clause must hold; from it the algorithm propagates forced literals and looks for a variable trapped in a cycle with its own negation. In the maximisation version you are permitted to break clauses, so falsifying a literal no longer forces its partner — the implication graph stops being a valid deduction. What remains is a choice of which clauses to sacrifice, and the decision form (can at least `k` clauses be satisfied?) is NP-complete even with two literals per clause. The lesson is not that optimisation is always hard: maximum matching in a graph with no odd cycle is an optimisation problem with a polynomial algorithm. It is that relaxing hard constraints can destroy the propagation an easy algorithm was built on.
go deeper
The habit to build is asking which version of a problem is on the table: must every rule hold, or are we scoring how many hold? Those are different problems with different costs.
Explain why the rewrite into implications stops being sound once clauses may break, and state the decision form of the maximisation question — at least k clauses satisfied — since classification is defined over decisions.
When a product turns hard constraints into weighted preferences, name what that costs. Exactness by propagation disappears and the work moves to search or a best-effort answer; put that in the plan rather than discovering it later.
Decide deliberately which rules are hard and which are soft. Soft rules are friendlier to users and strictly more expensive to satisfy optimally, so the usual right answer is a narrow hard core plus scored preferences, chosen with that cost understood.
## The same clauses, a different question Two questions about one set of two-literal clauses: 1. **Is there an assignment satisfying every clause?** This is 2-SAT, decidable in time linear in the formula. 2. **What is the largest number of clauses any assignment can satisfy?** This is the maximisation version, and its decision form — *can at least `k` clauses be satisfied?* — is NP-complete. Same objects, same clause width, opposite verdicts. The reason is worth understanding, because the flip appears whenever a product turns rules into preferences. ## Why the implication disappears The linear-time algorithm rests on one rewrite: `(a or b)` is the same as `not a -> b` together with `not b -> a`. That rewrite is only valid under the assumption that **every clause must hold**. If `a` is false, the clause can only survive by making `b` true — so `b` is forced. Remove the assumption and the deduction evaporates: - If clauses may be broken, `a` false leaves `b` genuinely free; keeping `b` false merely costs one unsatisfied clause. - The implication graph therefore stops encoding consequences and starts encoding *suggestions*. Strong components no longer certify anything: a variable trapped with its own negation now simply means some clause in that cycle must be given up, not that the instance is hopeless. - What replaces deduction is a choice over subsets — which clauses to sacrifice — and those choices interact, because one variable appears in many clauses. That is the whole mechanism. Nothing about the *size* of the instance changed; what changed is that a constraint became a score. ## The flip is not a rule about optimisation The tempting generalisation — *optimisation versions are hard, decision versions are easy* — is false in both directions, and an interviewer will probe it. | Problem | Hard constraint version | Best-effort version | |---|---|---| | Two-literal clauses | Satisfy all: linear time | Satisfy the most: NP-hard | | Two-way vertex split | Every edge crosses the split: linear time | Most edges cross the split: NP-hard | | Pairing up compatible items | — | Largest set of disjoint pairs, on a graph with no odd cycle: polynomial | The third row is the counterexample that keeps the claim honest. Finding the largest set of pairwise-disjoint edges is an optimisation problem, it is solved exactly in polynomial time, and it underpins several of the easy cases in this area. So optimisation is not the culprit. The culprit is the loss of forced propagation: the easy algorithms in this family all work by turning a constraint into a consequence, and a constraint that may be violated produces no consequence. Note also that complexity classes are defined for **decision** problems. "Maximise the satisfied clauses" is stated as a decision by adding a threshold — *at least `k`?* — and that is the version described as NP-complete. Being sloppy about which version is on the table is one of the commonest errors in this material. ## Direction matters One more check, because it is easy to get backwards. The maximisation problem **contains** the decision problem as a special case: if you could compute the maximum, you would compare it with the clause count and answer 2-SAT for free. Hardness therefore flows from the special case upward to the general one, never downward. The NP-hardness of the maximisation version says nothing whatever about 2-SAT, whose linear-time algorithm stands untouched. ## What to do about it at work When a specification turns "these rules must hold" into "satisfy as many of these rules as you can", say what it costs: - The exact, propagation-based answer is gone, along with the cheap proof that no solution exists. - The replacement is search or a best-effort answer with an explicit quality story — a separate discussion with its own trade-offs. - The usual settlement is a small hard core of rules that must hold, kept narrow enough to stay decidable, plus scored preferences over the rest. That shape is chosen deliberately rather than discovered after the scheduler stops finishing. The interview-grade version of this answer is short: *hard constraints deduce, soft constraints search*.
- Is there a graph problem showing the same easy-to-hard flip under a best-effort objective?Yes. Deciding whether a graph splits into two sides with every edge crossing is a linear traversal, but finding the split where the *most* edges cross is NP-hard. Both concern a two-way partition; the first demands that no edge is violated and therefore propagates, the second only scores, and propagation disappears.
- Does the NP-hardness of the maximisation version say anything about the complexity of 2-SAT itself?No, and the direction is the point. Maximising subsumes deciding — compute the maximum, compare it with the clause count, and you have answered 2-SAT — so hardness flows from the special case up to the general problem, never down. The linear-time result for 2-SAT is unaffected.
saying these in an interview costs you the question
- Assumes the best-effort version of an easy problem must also be easy.
- Says 2-SAT must be NP-hard because maximising satisfied clauses is.
- Believes every maximisation problem over graphs or formulas is NP-hard.
- Treats the implication graph as sound even when clauses may go unsatisfied.
- Quotes a complexity without saying whether all clauses or most clauses are meant.