ProblemReductions
This is the documentation for the open source package ProblemReductions, a package for the reduction (or transformation) between computational hard problems. Although the reduction is a common concept in the field of computational complexity, every textbook on this topic defines its own set of problems and reduction rules. Unfortunately, these rules are not directly accessible to the public, especially for people in fields such as quantum many-body physics and statistical physics. This package aims to collect a set of well-known problems and their reductions in one place, and provide a unified interface to access them. We hope this will lower the barrier for researchers to enter this fascinating field.
Framework
ProblemReductions defines a set of computational hard problems and the reduction rules between them. In the following diagram, we use an arrow pointing from problem A to problem B to indicate that there is a reduction rule from problem A to problem B.
The reduction rules induce a directed graph, called the reduction graph, where the nodes are the problems and the edges are the reductions. Problem A can be reduced to problem B if and only if there is a path from A to B. This reduction may consist of multiple steps, and the reduction path may not be unique.
The following example shows how to use the package to solve a simple factoring problem $? \times ? = 3$ by reducing it to an Ising model.
julia> using ProblemReductionsjulia> factoring = Factoring(2, 1, 3) # define the factoring problemFactoring{Int64}(2, 1, 3)julia> paths = reduction_paths(Factoring, SpinGlass);julia> length(paths) # you may find multiple reduction paths2julia> res = reduceto(paths[1], factoring); # perform the reductionjulia> problem_size(target_problem(res))(num_vertices = 25, num_edges = 47)
The Factoring problem is defined with two inputs of bit width 2 and 1, respectively. We first query the reduction paths from the Factoring problem to the SpinGlass problem using reduction_paths, and find multiple paths. Each path is a ReductionPath instance. We pick one reduction path and perform the reduction using reduceto. The result is a ConcatenatedReduction instance, which contains not only the target problem, but also the intermediate reductions in the reduction path. The target problem is an Ising model with 25 spins, which is exactly solvable using the BruteForce method implemented in findbest:
julia> sol = findbest(target_problem(res), BruteForce()); # solve the target problem
julia> extract_solution.(Ref(res), sol) # extract the solution to the original problem
1-element Vector{Vector{Int64}}:
[1, 1, 1]The solution to the original problem is extracted using extract_solution. Note that the findbest funciton returns a set of equally good solutions, so broadcasting is used here.
Model Problems
A model problem is a subclass of AbstractProblem that defines the size function of a computational problem. Facts affecting the computational complexity classification of the problem also include the topology of the problem and the domain of the variables.
The required interfaces are specified in AbstractProblem. The following code lists all problems subtyping it:
julia> ProblemReductions.concrete_subtypes(AbstractProblem)18-element Vector{Any}: BinaryMatrixFactorization KSatisfiability Satisfiability BicliqueCover CircuitSAT Coloring DominatingSet IndependentSet Matching MaxCut MaximalIS PaintShop QUBO SetCovering SetPacking SpinGlass VertexCovering Factoring
Please check Problems zoo and our paper arXiv:2501.00227 for more their definitions and properties.
Graph Topology
Model problems are often defined on graphs. When limiting a model problem to a specific graph topology, the hardness of the problem can be drastically different. To handle this, we define the following graph types:
SimpleGraph: A simple graph is an undirected graph with no self-loops or multiple edges between the same pair of vertices.HyperGraph: A hypergraph is a generalization of a graph in which an edge can connect any number of vertices.UnitDiskGraph: A unit disk graph is a graph in which vertices are placed in the Euclidean plane and edges are drawn between vertices that are within a fixed distance of each other. Similarly, we have an aliasGridGraphfor unit disk graphs with integer coordinates (i.e. vertices are placed on a grid).
To define a graph topology, the minimum required functions are: vertices and edges. More interfaces are specified in the Graphs package.
Reduction Rules
A problem reduction rule is a function that reduces a problem to another problem. By solving the target problem, we can extract the solution to the original problem. The reduction rule is defined as a function that takes an instance of the original problem and returns an AbstractReductionResult instance of the target problem.
reduceto: Reduce the source problem to a target problem of a specific type. Returns anAbstractReductionResultinstance, which contains the target problem.target_problem: Return the target problem of the reduction result.extract_solution: Extract the solution to the target problem back to the original problem.
Optional functions include:
extract_multiple_solutions: Extract a set of solutions to the target problem back to the original problem. You may want to implement this when you want to make extracting multiple solutions faster.
The reduction_graph function returns the reduction graph of the problems that induced by the reduction rules defined in ProblemReductions:
julia> rgraph = ProblemReductions.reduction_graph()ReductionGraph(Graphs.SimpleGraphs.SimpleDiGraph{Int64}(23, [Int64[], [3, 20], [2, 5, 20, 22], Int64[], [19], Int64[], Int64[], [15], [15], [19] … Int64[], [21], Int64[], [14], [5], [10, 13, 16], [21, 23], [8, 17], [6], [7]], [Int64[], [3], [2], Int64[], [3, 18], [22], [23], [21], Int64[], [19] … [17], [8, 9], [19], [21], Int64[], [5, 10, 13], [2, 3], [15, 20], [3], [20]]), Any[BinaryMatrixFactorization, KSatisfiability, Satisfiability, BicliqueCover, CircuitSAT, Coloring, DominatingSet, IndependentSet, Matching, MaxCut … SetCovering, SetPacking, SpinGlass, VertexCovering, Factoring, SpinGlass{var"#s54", T} where {var"#s54"<:SimpleGraph, T}, AbstractSatisfiabilityProblem, IndependentSet{var"#s54", T} where {var"#s54"<:SimpleGraph, T}, Coloring{3, T} where T, DominatingSet{var"#s56", T} where {var"#s56"<:SimpleGraph, T}], Dict{Pair{Int64, Int64}, Function}((2 => 3) => ProblemReductions.var"#354#359"{Pair{UnionAll, UnionAll}}(KSatisfiability => Satisfiability), (19 => 13) => ProblemReductions.var"#354#359"{Pair{UnionAll, UnionAll}}(SpinGlass{var"#s54", T} where {var"#s54"<:SimpleGraph, T} => QUBO), (20 => 23) => ProblemReductions.var"#354#359"{Pair{UnionAll, UnionAll}}(AbstractSatisfiabilityProblem => DominatingSet{var"#s56", T} where {var"#s56"<:SimpleGraph, T}), (19 => 10) => ProblemReductions.var"#354#359"{Pair{UnionAll, UnionAll}}(SpinGlass{var"#s54", T} where {var"#s54"<:SimpleGraph, T} => MaxCut), (5 => 19) => ProblemReductions.var"#354#359"{Pair{UnionAll, UnionAll}}(CircuitSAT => SpinGlass{var"#s54", T} where {var"#s54"<:SimpleGraph, T}), (8 => 15) => ProblemReductions.var"#354#359"{Pair{UnionAll, UnionAll}}(IndependentSet => SetPacking), (19 => 16) => ProblemReductions.var"#351#356"{Vector{Any}, Int64}(Any[BinaryMatrixFactorization, KSatisfiability, Satisfiability, BicliqueCover, CircuitSAT, Coloring, DominatingSet, IndependentSet, Matching, MaxCut … SetCovering, SetPacking, SpinGlass, VertexCovering, Factoring, SpinGlass{var"#s54", T} where {var"#s54"<:SimpleGraph, T}, AbstractSatisfiabilityProblem, IndependentSet{var"#s54", T} where {var"#s54"<:SimpleGraph, T}, Coloring{3, T} where T, DominatingSet{var"#s56", T} where {var"#s56"<:SimpleGraph, T}], 16), (3 => 2) => ProblemReductions.var"#354#359"{Pair{UnionAll, UnionAll}}(Satisfiability => KSatisfiability), (18 => 5) => ProblemReductions.var"#354#359"{Pair{UnionAll, UnionAll}}(Factoring => CircuitSAT), (15 => 21) => ProblemReductions.var"#354#359"{Pair{UnionAll, UnionAll}}(SetPacking => IndependentSet{var"#s54", T} where {var"#s54"<:SimpleGraph, T})…))julia> rgraph.graph{23, 23} directed simple Int64 graphjulia> rgraph.nodes23-element Vector{Any}: BinaryMatrixFactorization KSatisfiability Satisfiability BicliqueCover CircuitSAT Coloring DominatingSet IndependentSet Matching MaxCut ⋮ SetPacking SpinGlass VertexCovering Factoring SpinGlass{var"#s54", T} where {var"#s54"<:SimpleGraph, T} AbstractSatisfiabilityProblem IndependentSet{var"#s54", T} where {var"#s54"<:SimpleGraph, T} Coloring{3, T} where T DominatingSet{var"#s56", T} where {var"#s56"<:SimpleGraph, T}
The number of rules is the same as the number of edges in the output graph. Both the problem set, and the reduction rules are designed to be extensible, so that users can easily add new problems and reductions to the package.
It is worth noting that the reduction graph changes whenever there is a new reduceto function is added, regardless it is in this package or by users. This is because the reduction graph checks all method tables of the reduceto function, and will automatically add new nodes and edges when a new problem type or reduction method is added.