One per Triangle 3-SAT → IndSet · ALG 19.2
The reduction 3-SAT → IndSet from ALG 19.2: every clause of ψ becomes a triangle whose vertices are its literals, and every pair of conflicting literals (x and ¬x) in different triangles gets an edge. With k = the number of clauses, ψ is satisfiable ⇔ the graph has an independent set of size k. Each round, find a satisfying assignment or an independent set of size k, as the goal says. If none exists, press Unsatisfiable!
time –
score 0
streak 0
best sprint 0
Pick a level and press sprint or practice. In a sprint you have 2 minutes: every solved formula is +1, a correct “Unsatisfiable!” is +1, a wrong one costs 10 seconds.
Fun fact: in 1972 Richard Karp published a list of 21 NP-complete problems, connected by reductions like this one. Clique and 3-dimensional matching are on it.
← ADS2 Arcade