💻 computer science

A SAT-based Approach for Specification, Analysis, and Justification of Reductions between NP-complete Problems

This paper proposes a novel, interactive SAT-based framework using the URSA solver to bridge the gap between informal descriptions and formal proofs for developing, analyzing, and validating reductions between NP-complete problems.

Original authors: Predrag Janičić

Published 2026-06-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Predrag Janičić

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to prove that two different puzzles are actually the same game, just played with different rules. In the world of computer science, these puzzles are called NP-complete problems. They are notoriously difficult to solve, but if you can solve one, you can solve them all.

The paper by Predrag Janičić introduces a new tool to help computer scientists prove that these puzzles are connected. Think of this tool as a "Proof Assistant for Puzzle Mappers."

Here is how the paper explains this approach, broken down into simple concepts:

1. The Problem: The "Trust Me" Gap

Usually, when a mathematician wants to prove that Puzzle A is as hard as Puzzle B, they write a long, handwritten essay explaining how to turn a Puzzle A into a Puzzle B.

The Issue: These essays are written in "natural language" (like English). They are often vague, prone to human error, and hard to double-check. It's like a chef writing a recipe that says "add a pinch of salt" without specifying which salt or how much.
The Risk: Sometimes these proofs have hidden logical holes. If you get the direction wrong (trying to turn B into A instead of A into B), the whole proof falls apart.

2. The Solution: The "ursa" Tool

The author proposes using a computer system called ursa. Think of ursa as a super-strict translator that speaks two languages:

C-like Code: A programming language that looks like standard computer code (easy for humans to read).
SAT (Satisfiability): A strict logic language that computers can check perfectly.

Instead of writing a vague essay, you write a short computer program that describes the puzzle and the "translation" (reduction) between them. ursa then takes this code and asks a powerful logic engine: "Is it possible for this translation to fail?"

3. How It Works: The "Magic Box" Analogy

The paper describes a workflow that acts like a Magic Box with three steps:

Step 1: The Input (The Puzzle): You tell the box, "Here is a specific instance of Puzzle A (e.g., a map with 6 cities)."
Step 2: The Translation (The Reduction): You give the box a set of instructions on how to turn Puzzle A into Puzzle B.
Step 3: The Check (The Verification): The box doesn't just check one example. It checks every possible example of a certain size at once.

The Creative Metaphor: The "Bug Hunter"
Imagine you are building a bridge between two islands (Puzzle A and Puzzle B).

Old Way: You walk across the bridge once, look at it, and say, "It looks sturdy."
New Way (ursa): You build a machine that simulates every possible storm (every possible input) that could hit a bridge of that size.
- If the machine finds a storm that breaks the bridge, it gives you the exact coordinates of the break (a "counterexample"). You fix your code.
- If the machine runs through millions of storms and the bridge never breaks, you gain immense confidence that your bridge is solid.

4. What the Paper Actually Claims

The paper does not claim that this tool replaces human mathematicians or that it can prove everything for infinite sizes. Here is what it does claim:

It Bridges the Gap: It connects the messy, informal way we usually write proofs with the strict, formal way computers check logic.
It's a "Safety Net": It doesn't replace human intuition; it supplements it. It helps researchers find their own mistakes before they publish.
It Checks "Bounded" Sizes: The tool can prove a reduction is correct for all puzzles up to a certain size (e.g., all graphs with 50 nodes). It cannot prove it for infinite sizes (like graphs with a billion nodes), but checking a large, finite number is often enough to be very confident.
It's Easy to Use: Because ursa uses code that looks like standard C, you don't need to learn a weird new language. You can copy-paste your existing logic into it.
It Checks Complexity: Because the tool has rules about how loops work, it makes it easy to see if your translation is fast enough (polynomial time), which is a requirement for these proofs.

5. Real-World Examples in the Paper

The author tested this by taking classic, hard puzzles like:

Clique: Finding a group of friends where everyone knows everyone.
Vertex Cover: Finding the minimum number of people to stop all conversations in a group.
3-Coloring: Coloring a map so no touching areas have the same color.

They wrote code to translate "Clique" into "Vertex Cover" and vice versa. The tool ran simulations and confirmed that the translations worked perfectly for all tested sizes, catching no errors.

Summary

This paper presents a practical, automated workshop for computer scientists. Instead of guessing if their logic for connecting two difficult problems is correct, they can run their logic through ursa. If ursa says "No errors found for all inputs up to size X," the scientist can proceed with their proof with much higher confidence, knowing they haven't missed a subtle logical trap. It turns a "trust me" argument into a "check me" argument.

Technical Summary: A SAT-based Approach for Specification, Analysis, and Justification of Reductions between NP-complete Problems

Problem Statement
The paper addresses the challenges inherent in the specification, analysis, and verification of reductions between NP-complete problems. While identifying a problem as NP-complete is foundational to computational complexity theory, the standard methodology relies on informal, pen-and-paper proofs. These proofs are prone to misconceptions and errors, such as reducing in the wrong direction, failing to establish bidirectionality, or neglecting to prove membership in NP. Existing tools for this domain are scarce; most are educational prototypes lacking the ability to confirm new NP-completeness results, while interactive theorem provers (e.g., Isabelle, Coq), though rigorous, remain confined to specialized communities and are difficult to access for general researchers and students. There is a significant gap between informal reduction descriptions and fully formalized mathematical proofs.

Methodology
The authors propose a novel workflow powered by ursa, an open-source, SAT-based constraint solving system. The methodology leverages ursa's unique imperative-declarative nature, which allows users to specify problems using a C-like language while delegating the solving mechanism to a SAT solver.

The core workflow involves three primary components:

Specification of Input Instances: Defining the problem instance (e.g., a graph for Clique or Vertex Cover).
Certificate Verification: Specifying a procedure to verify a potential solution (certificate). In ursa, variables not assigned concrete values are treated as symbolic, allowing the system to search for valid certificates.
Reduction Implementation: Encoding the transformation function $R$ that maps an instance of problem $X$ to an instance of problem $Y$ .

The approach utilizes bounded verification. Instead of attempting a general mathematical proof, the system symbolically executes the reduction and verification procedures for all possible input instances up to a specific size (determined by fixed bit-vector bounds and loop unrolling). The system translates these constraints into Propositional Satisfiability (SAT) problems.

Key Contributions

Automated Justification of Reductions: The paper demonstrates that the correctness (or at least soundness) of a reduction can be automatically verified for bounded input sizes. This is achieved by asserting that the satisfiability of the source problem instance is equivalent to the satisfiability of the reduced target instance, often linking the certificates of both problems.
Bridging the Formalization Gap: The workflow serves as an intermediate layer between informal descriptions and strict foundational formalizations. It supplements human intuition by providing rapid, automated feedback on the logical validity of a reduction.
Ease of Implementation via C-like Syntax: Unlike other tools requiring custom specification languages, ursa allows users to write certificate checkers and reductions in a language nearly identical to C. This lowers the barrier to entry and facilitates the direct translation of algorithmic logic.
Complexity Analysis: Due to ursa's restrictions on loop formation (loops must have known, ground bounds), it is trivial to establish that the specified procedures run in polynomial time, a necessary condition for proving NP-completeness.

Results and Examples
The paper validates the methodology through several concrete examples drawn from Karp's list of 21 NP-complete problems:

Clique to Vertex Cover: The authors implement the reduction in both directions. They demonstrate that for specific graph sizes (e.g., 6 vertices), the system can verify that the reduction preserves the "yes"/"no" answer and correctly maps certificates.
3SAT to 3-Coloring: A more complex reduction involving "gadget" graphs is implemented. The authors show how to verify the soundness of this reduction (ensuring no false positives are introduced) for symbolic inputs of a fixed size (e.g., 10 variables, 15 clauses). The system generates formulas with thousands of variables and clauses, which are solved in seconds to confirm the absence of counterexamples.
Solver Generation: The paper illustrates that a solver for a target problem (e.g., Vertex Cover) can be constructed as a by-product of proving its NP-completeness via reduction from a known problem (e.g., Clique), without needing a dedicated solver for the target problem.

Significance and Claims
The paper modestly claims that this approach does not replace human intuition or provide a general mathematical proof for all input sizes. Instead, it functions as a powerful prototyping and debugging tool.

Error Detection: The primary utility is the rapid exposure of logical errors in reduction directions or certificate mappings. If the system finds a counterexample (a model where the assertion fails), it pinpoints the flaw in the reduction logic.
Confidence Building: By confirming that a reduction holds for all instances up to a certain size, the approach substantially bolsters confidence in the reduction before a researcher attempts a general informal or formal proof.
Educational and Research Utility: The workflow is presented as a valuable resource for students learning complexity theory and for researchers designing new NP-completeness proofs, offering a practical alternative to the tedious and error-prone manual verification of reductions.

The authors conclude that while this bounded verification is non-uniform and does not constitute a general proof, it effectively fills a crucial gap in the current landscape of complexity theory research and education. Future work aims to apply this approach to recent research publications and potentially integrate the methodology into interactive theorem provers for higher levels of trust.