Representing binary variables as complex phases on the unit circle yields an implicit regularization that improves ground-state recovery in QUBO, sparse coding, and planted Ising models.
Planted-solution SAT and Ising benchmarks from integer factorization
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We present a family of planted-solution benchmark instances for satisfiability (SAT) solvers and Ising optimization derived from integer factorization. Given two primes $p$ and $q$, the construction encodes the arithmetic constraints of $N = p \times q$ as a conjunctive normal form (CNF) formula whose satisfying assignments correspond to valid factorizations of~$N$. The known pair $(p,q)$ serves as a built-in ground truth, enabling unambiguous verification of solver output. We show that for two $d$-bit primes the total number of carry contractions is on the order of $d^4$. Empirical benchmarks with SAT solvers show that median runtime grows exponentially in the bit-length of the factors over the range tested. The construction provides a scalable, structured, and verifiable benchmark family controlled by a single parameter, accompanied by open-source generation software.
fields
cond-mat.stat-mech 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Implicit Binarization via Complex Phase Dynamics in Combinatorial Optimization
Representing binary variables as complex phases on the unit circle yields an implicit regularization that improves ground-state recovery in QUBO, sparse coding, and planted Ising models.