Technical Perspective: The Surprising Power of Spectral Refutation

NP-hard problems are assumed to be computationally intractable, meaning that no efficient (polynomial time) algorithm is guaranteed to correctly solve every input instance. One way of coping with NP-hardness is via the use of reliable heuristics. These are efficient algorithms that might not solve every input instance, but when they claim a solution, the solution is guaranteed to be correct. Consider the canonical NP-complete problem of SAT (determining whether a Boolean formula of the form (x1 x2 x3) (x2 x4) . . . A heuristic for finding satisfying assignments will naturally be reliable, because one can efficiently check whether the assignment found indeed satisfies all clauses of the input formula.