New method expresses many NP problems as standard quadratic programs
Standard Quadratic Formulations of Many NP Problems: A Simplex-Based Compilation Framework for Combinatorial Optimization
Emerging Technologies
Summary
Hard computational problems like finding the largest group of connected friends in a network or solving puzzles can be tough to tackle directly. The authors show how to rewrite many such problems into a specific type of math problem called a standard quadratic program, which involves minimizing a smooth equation on certain variables. Their approach connects classical graph ideas with continuous optimization, allowing structured ways to represent problems like satisfiability and coloring. They also describe how to recover solutions to the original problems from these new representations.
What this means in practice
- •For optimization software developers: Integrate a unified framework to encode diverse NP problems as standard quadratic programs for improved solver compatibility and solution recovery.
- •For quantum computing engineers: Use exact quadratic formulations to design problem encodings compatible with quantum annealers and other quantum optimization devices.
Authors
Mohammad-Ali Miri, Babak Emami, PoJen Wang
Abstract
The standard quadratic program (StQP) minimizes a quadratic form over nonnegative variables that sum to one. We compose classical graph reductions with regularized Motzkin--Straus clique formulations to express discrete optimization problems in this continuous domain. The graph matrix has diagonal entries $τ$, zeros on edges, and ones on nonedges. For $0<τ<1$, its minimum is $τ/ω(G)$, where $ω(G)$ is the clique number. Its strict local minimizers are precisely the uniform distributions on maximal cliques, and its global minimizers encode maximum cliques. At $τ=1/2$, integer scaling gives coefficients in $\{0,1,2\}$ and minimum $1/ω(G)$, yielding an NP-complete StQP threshold problem with a restricted coefficient alphabet. We give explicit formulations for satisfiability, coloring, Hamiltonian cycles, independent set, vertex cover, set packing, three-dimensional matching, and graph isomorphism. A regularized weighted clique formulation combined with local-state compatibility graphs gives an exact compiler for finite-domain factor models specified by complete local tables, including QUBO, with at most four simplex coordinates per binary pair factor. The catalog covers Karp's 21 problems: twelve use direct graph formulations, and nine use factor-state formulations, including six obtained through binary-linear feasibility. For each route we record dimensions, coefficient structure, and recovery rules. We analyze interaction count, coefficient range, objective separation, perturbation tolerance, support recovery, and decoding overhead. The separation bounds quantify the effects of clique size, factor weights, and offsets. In the complete factor-state construction, every assignment, including each suboptimal assignment, is a strict local minimum.