Finding hardness reductions automatically using SAT solvers

Helena Bergold, Manfred Scheucher, Felix Schröder
2/9/2024
cs.CCcs.AIcs.DS

No official code found. Best implementation: manfredscheucher/supplemental-completion-problems (2 stars, MIT, last commit 2026-04-25).

Abstract

In this article, we show that the completion problem, i.e. the decision problem whether a partial structure can be completed to a full structure, is NP-complete for many combinatorial structures. While the gadgets for most reductions in literature are found by hand, we present an algorithm to construct gadgets in a fully automated way. Using our framework which is based on SAT, we present the first thorough study of the completion problem on sign mappings with forbidden substructures by classifying thousands of structures for which the completion problem is NP-complete. Our list in particular includes interior triple systems, which were introduced by Knuth towards an axiomatization of planar point configurations. Last but not least, we give an infinite family of structures generalizing interior triple system to higher dimensions for which the completion problem is NP-complete.

View on arXivView PDF

Code Implementations(1)

manfredscheucher/supplemental-completion-problemsCommunity100%
MIT

supplemental material to the article "Finding hardness reductions automatically using SAT solvers"

20Sage, PythonApr 26, 20235 months agoMIT

Similar Papers

Reinforced Generation of Combinatorial Structures: Hardness of Approximation

78% match2025

CSPs with Few Alien Constraints

78% match2024

A Structural Complexity Analysis of Hierarchical Task Network Planning

75% match2024

The Equivalence Theorem: First-Class Relationships for Structurally Complete Database Systems

75% match2026

What makes math problems hard for reinforcement learning: a case study

74% match1 repo362024

The Birkhoff completion of finite lattices

74% match2024

Cite this paper

@article{bergold2024finding,
  title  = {Finding hardness reductions automatically using SAT solvers},
  author = {Helena Bergold and Manfred Scheucher and Felix Schröder},
  year   = {2024},
  eprint = {2402.06397},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2402.06397v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2402.06397.svg)](https://codeofpaper.com/paper/2402.06397)

Discussion