Perfect-completeness reduction benchmark library

Family 105: Perfect completeness for 2-to-1 games. First review, 8 October 2026.

Problem and potential new use

Solver researchers can test whether exact satisfiable cases and low-value gap cases expose weaknesses in approximation pipelines.

Applicability and commercial boundary

An NP-hardness theorem is not a new efficient label-assignment solver. Fixed-gap alphabets and reductions must be reconstructed rather than invented.

Initial business decision

Research infrastructure. Buyer demand and profitability remain hypotheses. This first pass does not establish a validated commercial market.

Next verification action

Read the reduction and identify small concrete instances suitable for reproducible stress fixtures.

Evidence scope

Catalog statement reviewed; inspect linked opportunity dossier for any deeper source review. This record alone does not establish full manuscript or proof verification.

Source revision fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb. See source metadata for the exact manuscripts and available scope notes.