Module analysis 

Analysis utilities for the reduction graph.

Detects primitive reduction rules that are dominated by composite paths, using asymptotic normalization plus monomial-dominance comparison.

This analysis is sound but incomplete: it reports Dominated only when the symbolic comparison is trustworthy, and Unknown when metadata is too weak to compare safely.

Structs

ConnectivityReport

Result of checking graph connectivity at the problem-type level.

DominatedRule

A primitive reduction rule proven dominated by a composite path.

IsolatedProblem

An isolated problem type with its variant count.

ReachabilityReport

Result of checking NP-hardness proof chains from 3-SAT.

UnknownComparison

A candidate comparison that could not be decided soundly.

UnreachableProblem

A problem type not reachable from 3-SAT via directed reduction paths.

Enums

ComparisonStatus

Result of comparing one primitive rule against one composite path.

UnreachableReason

Classification of a problem type that is unreachable from 3-SAT.

Functions

check_connectivity

Check reduction graph connectivity: find isolated problems and connected components.

check_reachability_from_3sat

Check which problems are reachable from 3-SAT (KSatisfiability) via directed reduction paths. Problems without such a path are classified as P-time, intermediate, orphan, or missing a proof chain.

compare_overhead

Compare two overheads across all common fields.

find_dominated_rules

Find all primitive reduction rules dominated by composite paths.

format_problem_variant