NP-Equivalent¶
A decision or output problem that is both NP-hard and NP-easy under polynomial-time Turing reductions.
Core Idea¶
A decision or output-producing problem is NP-equivalent under a specified polynomial-time oracle-reduction convention if it is both NP-hard and NP-easy. NP-hard means an NP-complete decision problem can be solved using this problem as an oracle. NP-easy means the candidate's specified answer—its Boolean result or full requested output—can be computed with polynomial work and queries to some NP decision oracle.[^ref-2ce3a4aaf6bb]
Scope of Application¶
Klocker explicitly includes decision and function problems; the label is especially useful beyond yes/no tasks for witnesses or optima. His specific RTPP1 asks for a maximum-profit feasible closed walk under arc costs, penalties, a cost interval and an at-most-twice arc-use rule. Corollary 3.2.6 proves Q′_D ≤ᴾ_T RTPP1 ≤ᴾ_T Q′_D for an associated NP-complete decision problem, on finite rational-encoded inputs. The left direction supplies hardness; the right supplies easiness. This does not classify every routing variant.[^ref-2ce3a4aaf6bb]
Clarity¶
NP-hard alone is only a lower bound; NP-easy alone is only an upper bound. NP-equivalence requires both for the exact candidate problem. It does not turn a non-Boolean output problem into an NP-complete decision language.[ref-2ce3a4aaf6bb][ref-22826b449af8]
Manages Complexity¶
Two reductions replace a vague claim of “NP difficulty” with a checkable sandwich: an NP-complete problem below and an NP decision oracle above. The comparison classifies relative difficulty without requiring an actual fast solution.[^ref-2ce3a4aaf6bb]
Abstract Reasoning¶
State the problem, answer type and encoding. Prove that a solver for it can decide a known NP-complete task with polynomial overhead. Separately give a polynomial-time algorithm that returns its specified answer, including full reconstruction if it is an output task, with NP decision-oracle calls. If either direction is missing, report only the supported half.[ref-2ce3a4aaf6bb][ref-22826b449af8]
Knowledge Transfer¶
The proof pattern covers decisions as well as search and optimization tasks, but output reconstruction algorithms differ. The live Computational Problem identity is the strict genus; NP-equivalent is not automatically NP-complete. A satisfying assignment can be built by repeated SAT queries as Goldreich proves in Proposition 3.7; an optimum route requires its own finite bounds and reconstruction argument. “Equivalent” remains tied to the stated reduction model.[^ref-22826b449af8]
[^ref-2ce3a4aaf6bb]: TU Wien, formal NP-equivalence definitions and optimization proof. [^ref-22826b449af8]: Goldreich, P, NP, and NP-Completeness: The Basics of Computational Complexity, author-hosted 2008 version, §3.3.1 Proposition 3.7.
Relationships to Other Abstractions¶
Current abstraction NP-Equivalent Domain-specific
Parents (1) — more general patterns this builds on
-
NP-Equivalent is a kind of Computational problem Domain-specific
NP-equivalent tasks are computational problems.
Hierarchy path (1) — routes to 1 parentless root
- NP-Equivalent → Computational problem → Function (Mapping)
Neighborhood in Abstraction Space¶
NP-Equivalent sits in a sparse region of the domain-specific corpus (66th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Computational Complexity & Hardness (17 abstractions)
Nearest neighbors
- Computational hardness assumption — 0.86
- GI (complexity) — 0.86
- GI-complete — 0.84
- Strong NP-completeness — 0.83
- P versus NP Problem — 0.83
Computed from structural-signature embeddings · 2026-10-08