CS Paper Radar

Further simulations between tropical and linear programming

Edward A. Hirsch, Dmitrii Sluch

cs.CC math.OC ·submitted 2026-11-18 14:52 UTC · v1
theory

Abstract

Propositional proof systems that apply various kinds of cuts to linear inequalities (such as Cutting Planes [CCT87] and Lift&Project [BCC93,Pud99,Das05]) or operate with disjunctions of linear inequalities (such as Res(CP) [Kra98] and Res(LP) [HK06]) have been in the focus of research for the past 30 years. Recently, tropical proof systems were introduced [AGH25]; they resemble the latter systems but differ from them in important respects. The relations between the traditional systems and the new tropical systems have remained largely unknown, and exponential lower bounds for tropical systems were limited to non-CNF examples. In this paper we prove several new polynomial simulations between these systems. To this end, we introduce Thr-Res (Threshold Resolution), a new natural daglike proof system operating on threshold conditions over the Boolean literals: lines asserting that at least s literals of a given multiset are true. Its main difference from CP is that the rounding rule (without it CP is incomplete) is replaced by a weaker rule that allows one to perform "resolution" steps with linear combinations beyond Boolean clauses; also, in its addition rules, Thr-Res resembles input resolution [Cha70]: a derived line is combined with an input clause or an axiom, whereas CP can add up any two derived lines. By varying the maximum value of s, one obtains systems ranging in strength from Resolution to MP-NSR, the static tropical (min-plus) proof system introduced in [AGH25]. As a consequence, we prove that MP-NSR is polynomially simulated by CP and L&P (even by their unary versions), which automatically yields exponential lower bounds on the size of MP-NSR proofs for formulas in CNF. We complement it with simulations in the converse direction: binary daglike MP-PCR (a dynamic version of MP-NSR) polynomially simulates L&P; it also polynomially simulates CP when division axioms are added.

Closest papers

Nearest neighbours by meaning across the whole index.

Separating comb inequalities is NP-hard

cs.CC ·2026-10-06 ·Yohan Finet, Victor Drouin-Touchette
similarity 0.58
Abstract

Comb inequalities are important cutting planes for the symmetric travelling salesman problem, yet the complexity of their exact separation has remained a longstanding question in polyhedral combinatorics. We present a reduction from 3-SAT proving that deciding whether a comb inequality is violated is NP-complete and that the corresponding separation problem is NP-hard. This result holds even when the input vector belongs to the subtour elimination polytope, every edge value is zero, one half or one and the support graph is nonplanar with maximum degree four. The reduction constructs a graph in which six-vertex ladder gadgets encode Boolean relations and cubic graphs enforce consistency among occurrences of each logical variable. For a propositional logic formula with $v$ variables and $m$ clauses, the constructed graph has $40v+70m+30$ vertices and a linear number of positive edges. The reduction also proves hardness when every permitted tooth has two or four vertices with half of the tooth in the handle. We discuss consequences for approximating the maximum comb violation, optimization over the comb relaxation and explain why hardness of separation does not automatically transfer to larger inequality families.

0.35

Symbolic Execution of Constrained Horn Clauses

cs.LO cs.PL ·2026-10-02 ·Johannes Weiser, Zafer Esen, Philipp Rümmer
similarity 0.57
Abstract · 34 pages, 8 figures

Constrained Horn clauses (CHCs) are a fragment of first-order logic widely used as an intermediate language for verification. We study constrained resolution as a calculus for reasoning about the satisfiability of sets of CHCs. Constrained resolution forms a simple alternative to model checking algorithms such as CEGAR and IC3 and is here shown to exhibit complementary features. We show that, when CHCs encode programs, forward symbolic execution corresponds to positive unit hyper-resolution, and backward symbolic execution to SLD resolution, which are special cases of constrained resolution. We formalize forward and backward reasoning for linear and non-linear CHCs and transition systems, prove refutational completeness under fair strategies, and develop subsumption criteria for pruning redundant derivations. We moreover show that backward resolution with subsumption generalizes $k$-induction to non-linear CHCs, and that forward constrained resolution is related to the problem of constructing proofs in incorrectness logic. Lastly, we provide an experimental evaluation in the Eldarica CHC solver on benchmarks from CHC-COMP.

0.19

An upper bound of 4.268 for the random 3-SAT satisfiability threshold

cs.DM math.PR ·2026-10-06 ·Fedor Vorobyev
theory similarity 0.57
Abstract · 16 pages, 1 figure. Includes a complete Lean 4 formalization and a reproducible rational certificate

We prove that a random 3-SAT formula with $n$ variables and $\lfloor 4.268n\rfloor$ clauses is unsatisfiable with high probability. The satisfiability threshold has attracted considerable attention: successive upper bounds reached 4.4898 in the work of Díaz, Kirousis, Mitsche, and Pérez-Giménez, while the cavity method predicts a value near 4.267. Our bound brings the rigorous upper estimate close to this prediction. The proof builds on earlier interpolation methods, including the energetic approach of Achlioptas and Menchaca-Méndez. We study the smallest number of clauses that any assignment must violate, comparing the random formula with a simpler system of constraints on individual variables. This comparison reduces the bound to a finite calculation, which we verify using exact rational arithmetic. The proof is formalized in Lean 4.

0.26

Automated Theorem Generation in First-Order Logic by Construction from Triangular Standard Contradictions

cs.AI ·2026-10-30 ·Yang Xu, Shuwei Chen, Hailin Guo, Jun Liu
theory similarity 0.56
Abstract · 46 pages, 11 figures

Automated theorem generation (ATG) seeks to construct new theorems rather than merely prove given conjectures. Existing approaches typically generate candidate statements that require subsequent proof or formal verification. We propose a constructive framework for ATG in first-order logic based on triangular standard contradictions. The method constructs minimally unsatisfiable clause sets from selected first-order literals, then forms theorems by retaining some clauses as premises and taking the negation of one clause, or a conjunction of clauses, as the conclusion. Minimal unsatisfiability ensures that the remaining premises are satisfiable, avoiding trivial inference by explosion, while unsatisfiability of the full set guarantees the resulting entailment. Theorems are therefore correct by construction, without a separate proof procedure for each instance. Extending the previously developed $Δ_1$ generator, we introduce seven methods, $Δ_2$--$Δ_8$, forming a unified family of eight theorem-generation methods. Four generators, $Δ_1$--$Δ_4$, have been implemented and released. We also formulate a general $Δ$-class method encompassing the family. Combinatorial analysis demonstrates the capacity to generate large numbers of distinct theorems systematically. This framework offers a principled foundation for automated theorem discovery and the construction of logically guaranteed knowledge.

0.28

A Polynomial Time Approximation for the Minimization of Implication Systems and Horn CNFs

cs.DM ·2026-11-15 ·Endre Boros, Ondrej Cepek, Kazuhisa Makino
similarity 0.55
Abstract

An implication system is a collection of rules of the form $B \imp H$, where the set $B$ of Boolean variables is the {\em body} of the rule, while $H$ is the set of its {\em heads}. Such a rule is an aggregate representation of individual implications $B\imp h$, for $h\in H$ which correspond to the clauses of an equivalent CNF representation of a Horn Boolean function. An implication system is {\em body-minimum}/{\em clause-minimum} if it has the minimum number of bodies/clauses among all logically equivalent implication systems. The corresponding minimization problems appear not only in the context of implication systems, but also as problems for closure systems, directed hypergraphs, representation of dependencies in relational databases, or in Horn CNF minimization. While body-minimization is known to be solvable in polynomial time (and there are several algorithms in the literature that solve this task), clause-minimization is known to be NP-hard. In fact, body-minimization has a particular canonical solution, called the GD-basis of the underlying Horn function that also can be computed efficiently. In this paper, we utilize a known connection between the two minimization problems stating that for every implication system there always exists a logically equivalent clause-minimum implication system which has the same bodies as its canonical GD-basis, see (B{é}rczi and B{é}rczi-Kov{á}cs, 2017), and (Adaricheva and Nation, 2014). We use this fact to design a polynomial time approximation algorithm which for any $δ>0$ outputs a $(\frac{1}{4} + δ)n$-factor approximation of the logically equivalent clause-minimum implication system on $n$ variables. This is an improvement from the best known algorithm so far that provides only an $(n-1)$-factor approximation, see (Hammer and Kogan, 1993).

0.30

IneqAgent: Agentic Inequality Proving in Lean with Symbolic Computation

cs.AI ·2026-10-14 ·Gaolei He, Jinhui Li, Ruobing Zuo, Xia Zeng, Zhengfeng Yang
theory similarity 0.55
Abstract

Formal inequality proving requires mathematical reasoning and exact computation, often connected through intermediate lemmas and goal reformulations. We introduce IneqAgent, an agentic framework combining LLM reasoning with symbolic computation for inequality proving in Lean4. Lemma-level Monte Carlo Tree Search coordinates lemma construction, goal reformulation, and symbolic backend selection. Complementary sum-of-squares, Bernstein, and successive difference-substitution backends produce exact certificates for local Lean proof generation. The agent integrates these proofs with LLM-generated steps and uses Lean feedback to construct complete proofs checked against the original theorem statements. On four benchmarks, IneqAgent with DeepSeek-V4-Flash solves 175 of 186 problems (94.09%), achieving the highest overall success rate among the evaluated methods. Across four backbones, it achieves higher success rates at low LLM inference cost thresholds than Direct Agent using the same backbone, with lower mean inference costs over each method's successful runs. We also obtain Lean-verified strengthenings of Dittert's conjecture in dimensions four and five, and certify the Holens--Djokovic $(4,4)$ inequality, implying Merris's conjecture in dimension four.

0.17

Formalizing the Omega Test in Dafny

cs.LO cs.PLcs.SC ·2026-09-28 ·Ariadna Brănici-Faraon, Ştefan Ciobâcă, Diana-Elena Gratie
published similarity 0.54
Abstract · In Proceedings FROM 2026, arXiv:2609.30324

We present a formalization in Dafny of the Omega Test, an algorithm used to decide the satisfiability of a system of inequalities. The implementation defines executable representations for rational numbers, linear expressions, inequalities, equalities, divisibility constraints, and systems of constraints, together with their semantic interpretation through valuations. We fully specify and verify the implementation in Dafny. We describe the lessons learned and how the formalization process led to new insights into the algorithm.

0.42

Formally Certifying the Vertex Set of a Polyhedron Faster than Informal Enumeration

cs.LO math.COmath.OC ·2026-10-08 ·Xavier Allamigeon, Yazid Id-Sahra, Pierre-Yves Strub
similarity 0.54
Abstract · 20 pages, 3 figures, 2 tables

The computation of the vertices of a polyhedron described by a system of linear inequalities is a central problem in polyhedral computation. It is a fundamental step in the conversion between H-representations, by linear inequalities, and V-representations, by vertices and extreme rays. This operation plays an important role both in the study of polyhedra and their combinatorics in mathematics and in applications to software and system verification. We present a certificate-based approach for formally verifying the computation of the vertices of a polyhedron. Given an informally computed list of vertices, our method allows to certify in the proof assistant Rocq that the list is complete, or even exact. The cornerstone of the method is a new completeness criterion based on an abstract simplicial complex that generalizes a triangulation of the normal fan of the polyhedron. A significant advantage over previous approaches is that the usually expensive numerical computations are essentially reduced to membership tests to the polyhedron, while the other steps are cheap combinatorial tests. We implement the certification method and prove its correctness in the proof assistant Rocq. We experiment with it on a variety of polyhedra, including Birkhoff polytopes, cross-polytopes, cubes, permutahedra, hypersimplices, and high-dimensional polytopes involved in the disproof of the Hirsch conjecture. Our experiments show that certification with the Rocq-to-OCaml extracted checker is typically 1.5x to over 5x faster than vertex enumeration by the state-of-the-art informal C implementation lrslib of the reverse search method.

0.28