Dresden 2026 – scientific programme
Parts | Days | Selection | Search | Updates | Downloads | Help
DY: Fachverband Dynamik und Statistische Physik
DY 43: Poster: Statistical Physics
DY 43.9: Poster
Wednesday, March 11, 2026, 15:00–18:00, P5
Reduction of interaction order in hard combinatorial optimization through conditionally independent degrees of freedom — •Alexandru Ciobanu1, David Dahmen1, John Paul Strachan2, and Moritz Helias1 — 1Forschungszentrum Jülich, Jülich, Germany — 2Peter Grünberg Institut (PGI-14), Aachen, Germany
Combinatorial optimization problems have a broad range of applications and map to physical systems with complex dynamics. Among them, the 3-SAT problem is prominent due to its NP-complete nature. In physics terms, its solution corresponds to finding the ground state of a disordered Ising spin Hamiltonian with third-order, or tensor, interactions. The large growth of the number of third-order interactions with number of variables poses technical difficulties for the physical implementation of minimizers. In this work, we employ the renormalization group to create a pairwise interacting system from the original third-order system while preserving the free energy. Our procedure utilizes additional degrees of freedom that now exhibit conditional independence. A step-wise trace of the extra variables while running the minimization is therefore computable, yielding a state-dependent effective interaction. We use the effective interaction to reconstruct the original third-order energy spectrum.
Keywords: renormalization group; conditional independece; hard combinatorial optimization