Introduce overhead system

[GiggleLiu]

Each problem has a size, which is a mapping from some instance properties to numbers.
e.g. For independent set problem on Petersen graph, we have "num_vertices = 10, num_edges = 15".

A reduction overhead can be represented by a polynomial, e.g.
By reducing an IndependentSet problem on simple graph to grid graph, it has "num_vertices ~ num_vertices ^ 2, num_edges ~ num_vertices ^ 2", which is a mapping from the properties of target problem to a polynomial of properties of source problem.

[GiggleLiu]

TODO:

1. design a symbolic expression system (maybe use string), support expressions like:

• "num_edges ~ num_vertices ^ 2"
• "1.44^num_edges"

2. a polynomial validator, e.g. for the above examples, the first one returns true, the second one returns false.
3. complexity validator, expression sould only contain, exp, poly, O(n^3) like expression, which will be used for complexity analysis. (low priority)

[isPANN]

Core Components

ProblemSize — concrete name → value bindings for a problem instance:

Graph: {num_vertices: 100, num_edges: 450}
SAT:   {num_vars: 50, num_clauses: 200, num_literals: 600}

Expr — symbolic expression AST (Abstract syntax tree) for a single output field.

ReductionOverhead — named collection of Expr, one per output field. Maps output field names to expressions over the source problem's size variables.

Required Operations

Operation	Description
Evaluate	Substitute concrete ProblemSize values into each Expr, produce output ProblemSize
Compose	Given A→B and B→C overheads, substitute B→C's variables with A→B's expressions to get A→C
Validate	Check all Expr variables ⊆ source problem's size names, output fields ⊆ target problem's size names
is_polynomial	Reject non-polynomial overhead (e.g. 1.44 ^ num_edges)
degree	Extract polynomial degree bound for complexity analysis

Registration

Overhead is declared via the #[reduction] attribute macro and collected at startup via inventory:

#[reduction(
    overhead = { /* Expr construction here */ }
)]
impl ReduceTo<QUBO<f64>> for MaximumIndependentSet<SimpleGraph, i32> { ... }

Rust Ecosystem Status

Rust has no mature general-purpose symbolic computation library comparable to SymPy.

• Symbolica — the only serious Rust CAS (72K SLoC), but oriented towards physics (Feynman integrals, rational polynomials). LGPL-licensed. Overkill for our needs.
• rusymbols, symbolic_math, mathcore, cas-rs — abandoned, unstable, or too minimal.

Our requirements are narrow enough that a self-contained implementation (~300-500 LOC) is the right call.

Two Approaches to Expr Construction

Approach A: Parse-based

Expressions are written as text, parsed into AST. Two variants:

Runtime parse — String literals parsed at startup (use a classical Pratt parser):

#[reduction(
    overhead = { ReductionOverhead::new(vec![("num_vars", "num_vertices ^ 2")]) }
)]

Compile-time parse — the #[reduction] proc macro parses the expression during cargo build and emits Expr construction code directly. Same syntax for the user, but parse errors become compile errors:

#[reduction(
    overhead = { num_vars ~ num_vertices ^ 2 }
)]
// macro expands to: ReductionOverhead::new(vec![("num_vars", Expr::Pow(...))])

Both variants are fundamentally the same idea — write text, have a parser interpret it. The difference is only when the parser runs.

Pros: concise and declarative; naturally supports serialization and external input (config files); easy to display/debug.

Cons: parser must be written and maintained either way; variable name typos caught at runtime (runtime variant) or compile time (macro variant); no IDE autocomplete inside the expression text; syntax ambiguity decisions are the parser's burden.

Approach B: Constructor API (SymPy-style)

SymPy's core design: expressions are constructed in the host language via operator overloading. sympify("x**2") exists as convenience, but the primary path is x = Symbol('x'); expr = x**2.

Apply the same idea in Rust — implement Add, Mul, etc. on Expr:

#[reduction(
    overhead = {
        let n = Expr::var("num_vertices");
        ReductionOverhead::new(vec![("num_vars", n.pow(2))])
    }
)]

Pros: compile-time type checking on expression structure; IDE autocomplete and refactoring; no parser needed for internal use; zero syntax ambiguity.

Cons: slightly more verbose; variable name typos still caught at runtime; needs a separate Display/parse layer for serialization.

Comparison

	Runtime parse	Compile-time macro parse	Constructor API
Conciseness	✅	✅	slightly longer
Syntax error detection	❌ runtime	✅ compile time	✅ compile time
Variable name check	❌ runtime	✅ possible in macro	❌ runtime
IDE support	❌	❌	✅
Parser maintenance	runtime parser	proc macro parser	not needed internally
Serialization	✅ natural	✅ natural	needs separate impl
Macro complexity	low	high	low

Recommendation by AI

Constructor API as the primary internal path, with parser retained for I/O.

Rationale for Rust specifically:

• Rust's type system and operator overloading (Add, Mul traits) make construction-based APIs idiomatic and natural.
• Constructor API needs no parser at all for the internal registration path — the existing #[reduction] macro stays simple. Compile-time macro parse would require embedding a full expression parser inside the proc macro, significantly increasing macro complexity for marginal benefit over the constructor approach.
• The parser is still needed but only as a serialization/deserialization layer (Display, debug, config files), which is a narrower and less critical role.

Future (Low Priority)

• Simplifier: constant folding, (x^a)^b → x^(ab)
• Complexity classifier: Poly(k) / Exp