Skip to main content

Module analysis

problemreductions::rules

Module analysis 

Source
Expand description

Topology analysis utilities for the reduction graph.

Structs§

ConnectivityReport
Result of checking graph connectivity at the problem-type level.
IsolatedProblem
An isolated problem type with its variant count.
ReachabilityReport
Result of checking NP-hardness proof chains from 3-SAT.
UnreachableProblem
A problem type not reachable from 3-SAT via directed reduction paths.

Enums§

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.