Reductions

Problem reductions allow transforming one NP-hard problem into another while preserving solution structure.

Why Reductions?

• Solve problems indirectly: Transform to a problem with a better solver
• Prove equivalence: Show problems have the same computational complexity
• Hardware mapping: Transform to problems supported by quantum hardware

Available Reductions

Reduction Traits

#![allow(unused)]
fn main() {
pub trait ReduceTo<T: Problem>: Problem {
    type Result: ReductionResult<Source = Self, Target = T>;
    fn reduce_to(&self) -> Self::Result;
}

pub trait ReductionResult: Clone {
    type Source: Problem;
    type Target: Problem;

    fn target_problem(&self) -> &Self::Target;
    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize>;
}
}

See:

• Using Reductions
• Available Reductions
• Reduction Graph