Pseudo-polynomial transformation¶

Map instances between numerical decision problems while preserving yes/no membership and polynomially controlling computation, encoding growth, and the target's largest numerical parameter.

Version: v1 · 2026-08-30 · History
Domain-specific #: 2566
Origin domain: computational complexity
Subdomain: strong np completeness reductions
Aliases: Pseudo-polynomial reduction, Pseudopolynomial transformation

Core Idea¶

A pseudo-polynomial transformation is a many-one instance map between numerical decision problems that preserves yes/no membership and controls both ordinary encoding size and the magnitudes of the numerical parameters. For encodings \(L_1,L_2\), it supplies a function \(f\) such that \(w\in L_1\) exactly when \(f(w)\in L_2\). Unlike an ordinary polynomial-time reduction, its computation may be polynomial in the source encoding length together with the source problem's maximum numerical parameter. Additional size inequalities prevent the map from hiding an exponential blow-up or mapping polynomially bounded source instances to numerically unbounded target instances.^[1]

Fix for each problem \(\Pi\) an encoding and a magnitude function \(\operatorname{Num}_{\Pi}(w)\) that returns the largest relevant numerical value in instance \(w\). A qualifying map is computable in time polynomial in \((|w|,\operatorname{Num}_{\Pi_1}(w))\), has a polynomial lower relation from output length back to input length, and bounds \(\operatorname{Num}_{\Pi_2}(f(w))\) polynomially in source length and source magnitude. These clauses let a polynomially bounded NP-complete restriction of the source map to a polynomially bounded restriction of the target, which is the step needed to transfer strong NP-hardness.^[2]

The term does not mean any reduction whose implementation happens to use numerical arithmetic, any pseudo-polynomial algorithm, or any polynomial-time reduction. Runtime measured in numeric value rather than bit length is essential, but it is not sufficient: the output-length and target-magnitude conditions also matter. A reduction that preserves decisions while encoding a source number as an exponentially larger target number can destroy the strong-NP argument. The direction of transfer matters as well: a transformation from a known strongly NP-complete source supports target hardness only when the target is independently shown to lie in the relevant class for completeness.^[3]

Structural Signature¶

Source problem and encoding. A numerical decision problem supplies legal strings, membership, and a declared bit representation.
Target problem and encoding. A second decision problem receives the constructed instance under its own representation conventions.
Magnitude function. The largest designated numerical parameter separates value-sensitive cost from ordinary bit length.
Instance map. A total computable function constructs one target encoding from each source encoding.
Membership preservation. Yes-instances map to yes-instances and no-instances to no-instances.
Pseudo-polynomial runtime bound. Construction time is polynomial in source length and source numerical magnitude.
Length relation. A polynomial relation prevents the output from compressing the source in a way that breaks the restriction argument.
Target-magnitude bound. Target numerical values remain polynomially controlled by source size and magnitude.

What It Is Not¶

Not a pseudo-polynomial algorithm. An algorithm solves one problem; the transformation maps instances between two problems.
Not an ordinary polynomial reduction. Pseudo-polynomial construction time may be exponential in bit length when values are large.
Not a weak-NP certificate. The map is commonly used to establish strong hardness rather than to classify a source as weak.
Not a PTAS reduction. Approximation-preserving reductions control objective guarantees, not this numeric-magnitude restriction.
Not a unary re-encoding trick. Encoding conventions and magnitude bounds are declared rather than silently changed.
Not hardness by itself. Target class membership and the source theorem remain separate premises.

Scope of Application¶

The abstraction is literal wherever practitioners can identify the same constitutive roles, apply the same boundary tests, and obtain the same kind of output. The following habitats are uses of Pseudo-polynomial transformation itself, not metaphors based only on resemblance.

Strong NP-completeness proofs. Transporting hardness from a bounded-numeric restriction of a known source problem.
Scheduling. Mapping jobs, processing times, or deadlines while controlling their generated magnitudes.
Packing and partitioning. Relating numerical capacity problems without losing value-sensitive complexity.
Combinatorial optimization. Auditing whether a construction proves ordinary or strong hardness.
Encoding analysis. Separating bit-length growth from numeric-value growth.
Reduction verification. Checking all four defining obligations instead of membership preservation alone.

Clarity¶

A clear account of Pseudo-polynomial transformation must preserve the recognition invariant stated in the Core Idea rather than rely on the title alone. Declare both encodings and the exact numerical parameters used by each magnitude function. State all polynomial bounds separately rather than calling the construction efficient without a cost model. Prove both directions of decision preservation for every legal source instance. Name the strongly NP-complete source restriction and separately verify the target's class membership. These declarations are not editorial extras: each changes what observations count, which transformations are licensed, and what conclusion can be drawn. A reader should be able to reconstruct the input, the operative rule, the output, and at least one defeater from the account without consulting an implementation or guessing an unstated convention.

Manages Complexity¶

Pseudo-polynomial transformation manages complexity by replacing a diffuse field of observations or possible operations with a bounded role structure: source problem and encoding supplies a numerical decision problem supplies legal strings, membership, and a declared bit representation.; target problem and encoding supplies a second decision problem receives the constructed instance under its own representation conventions.; magnitude function supplies the largest designated numerical parameter separates value-sensitive cost from ordinary bit length.; instance map supplies a total computable function constructs one target encoding from each source encoding.; membership preservation supplies yes-instances map to yes-instances and no-instances to no-instances.. The compression is useful because it localizes disagreement. One can ask whether the input was properly formed, whether a constitutive relation held, whether an alternative explanation defeats the inference, or whether the output was overinterpreted. The same compression can mislead when its discarded detail is exactly what the decision requires. A reference-grade use therefore reports both the invariant retained and the information intentionally lost.

Abstract Reasoning¶

Fix source and target languages and reject malformed encodings explicitly.
Define the largest-numerical-parameter functions before analyzing runtime.
Construct the target instance and prove yes/no equivalence in both directions.
Bound construction time in source length and numerical magnitude.
Prove the polynomial relation between input and output encoding lengths.
Bound every target numerical parameter by a polynomial in source length and magnitude.
Apply the map only after identifying the source's polynomially bounded NP-complete restriction.
Test the candidate interpretation against the nearest named confusable rather than accepting a shared surface feature.
State the conclusion at the same scope as the source conditions, and retain uncertainty or nonuniqueness where the construct does not remove it.

Knowledge Transfer¶

The strict upward abstraction is Function Mapping. Pseudo-polynomial Transformation instantiates Function Mapping because it is literally a function from encoded source instances to encoded target instances, specialized by decision preservation and quantitative bounds. Within strong np completeness reductions, the full mechanism transfers literally when the same roles and boundary tests recur. Beyond that domain, only the parent-level skeleton should travel. Reusing the label Pseudo-polynomial transformation after removing its constitutive vocabulary would hide a change of mechanism behind an analogy. The honest transfer rule is therefore two-stage: recognize the domain-specific pattern first, then lift only the parent relation that remains invariant under a substrate change.

Examples¶

Canonical¶

A scheduling reduction maps a numerical source instance \(w\) to jobs with processing times computed from the source integers. Membership is preserved, construction takes time polynomial in \(|w|\) and \(\operatorname{Num}_{\Pi_1}(w)\), output length cannot be exponentially smaller than the input, and every generated duration is polynomially bounded in those source measures. Therefore a polynomially bounded hard source family remains polynomially bounded after mapping.

Mapped back: input and conventions → constitutive role test → bounded output → explicit interpretation and defeater check.

Applied / In Practice¶

A proposed reduction multiplies two source integers and then raises 2 to that product to create one target capacity. The yes/no proof may be correct and the number may be writable in a compact exponent notation, but the designated target magnitude is exponentially larger than the source magnitude. The target-magnitude clause fails, so the construction cannot serve as a pseudo-polynomial transformation for transferring strong NP-hardness.

Mapped back: field observation or problem → candidate recognition → confusable and limit checks → appropriately scoped conclusion.

Structural Tensions¶

T1: Value versus encoding length. A polynomial in a number's value can be exponential in its bit length. Diagnostic: Report both measures for every runtime and size claim.
T2: Decision preservation versus resource preservation. A logically correct map can destroy the bounded-number restriction. Diagnostic: Check magnitude bounds after proving yes/no equivalence.
T3: Compact notation versus semantic magnitude. An exponent may be written briefly while denoting an enormous target parameter. Diagnostic: Apply the target problem's declared magnitude function to the constructed object.
T4: Reduction direction versus theorem direction. Hardness travels from the known hard source to the target, not conversely. Diagnostic: Write the source, target, and claimed conclusion on one line before proving anything.
T5: Strong hardness versus completeness. A reduction supplies hardness while membership supplies completeness. Diagnostic: Identify the independent target-membership proof.
T6: Autonomy versus generic mapping. Function Mapping supplies input-output relation but not numeric restriction preservation. Diagnostic: Remove magnitude and length clauses and test whether only a generic function remains.

Structural–Framed Character¶

Pseudo-polynomial transformation is strongly structural: its verdict follows from explicit languages, functions, bounds, and quantified preservation clauses under a fixed encoding model. The five framing criteria point in a consistent direction. Evaluative weight is limited to whether the defining conditions are met, not whether the outcome is desirable. Human practice matters to the extent that experts choose conventions, instruments, or reporting thresholds, but those choices do not make every verdict arbitrary. Institutional history explains the name and standard use; it does not replace the recognition rule. The operative vocabulary travels within the home field and closely adjacent subfields, while transfer farther away requires translation to the parent prime. Thus recognition remains disciplined even where interpretation is defeasible.

Structural Core vs. Domain Accent¶

What is skeletal. Pseudo-polynomial Transformation instantiates Function Mapping because it is literally a function from encoded source instances to encoded target instances, specialized by decision preservation and quantitative bounds. This is the part that can be expressed without the candidate's specialist nouns.

What is domain-bound. The irreducible domain accent is numerical decision problems, bit-length versus value, maximum numerical parameters, strongly NP-complete bounded restrictions, and the four-condition reduction theorem. Remove those elements and the result is no longer Pseudo-polynomial transformation; it is only the parent relation or a loose analogy.

Why this does not clear the prime bar. The name does not recur with unchanged diagnostics across three independent domains. What transfers is already represented by prime:function_mapping. The candidate remains autonomous because its in-domain recognition rule, failure modes, and consequences are stable, but its vocabulary and interventions do not float free of the home substrate.

Pseudo-polynomial Transformation instantiates Function Mapping because it is literally a function from encoded source instances to encoded target instances, specialized by decision preservation and quantitative bounds.

The prospective workspace queue contains one strict upward edge to prime:function_mapping. No live DAG mutation is authorized.

Relationships to Other Abstractions¶

Current abstraction Pseudo-polynomial transformation Domain-specific

Parents (1) — more general patterns this builds on

Pseudo-polynomial transformation is a kind of Function (Mapping) Prime

Pseudo-polynomial Transformation instantiates Function Mapping because it is literally a function from encoded source instances to encoded target instances, specialized by decision preservation and quantitative bounds.

Hierarchy path (1) — routes to 1 parentless root

Pseudo-polynomial transformation → Function (Mapping)

Neighborhood in Abstraction Space¶

Pseudo-polynomial transformation sits in a sparse region of the domain-specific corpus (82^nd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Complexity Reductions & Decidability (10 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Polynomial-time reduction. Requires time polynomial in encoding length alone and normally lacks the special magnitude clauses.
Pseudo-polynomial algorithm. Solves a problem in value-sensitive time rather than translating instances.
PTAS reduction. Preserves approximation performance and parameters rather than strong-NP bounded restrictions.
Strong NP-completeness. A property of a problem established using the transformation plus other premises.
Unary encoding. A representation choice that may align length and value but is not the transformation definition.
Karp reduction. The general polynomial-time many-one form from which this numeric-sensitive form differs.

References¶

[1] Garey, M. R., and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, pp. 94–102. W. H. Freeman. ISBN 978-0-7167-1045-5. registry ↩

[2] Martello, S., and Toth, P. (1990). Knapsack Problems: Algorithms and Computer Implementations. Wiley. ISBN 978-0-471-92420-3. registry ↩

[3] Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., and Protasi, M. (1999). Complexity and Approximation. Springer. https://doi.org/10.1007/978-3-642-58412-1 registry ↩