Reductions that Lie

All of the reductions currently used in complexity theory (≤p, ≤γ, ≤R) have the property that they are honest. If A ≤ B then whatever machine M reduces A to B is such that: if on input x, M outputs y then x ε A ↔ y ε B. It would appear that this membership preserving property is intrinsic to the notion of reduction. We will see that it is not. We introduce reductions that lie and sometimes produce outputs y ε B when x? A. We will use these reductions to further clarify the computational complexity of some problems raised by Gauss.

Authors

• Leonard M. Adleman
• Kenneth L. Manders

Keywords

• Polynomials
• Mathematics
• Complexity theory
• NP-complete problem
• Turing machines
• Laboratories
• Computer science
• Computational complexity
• Gaussian processes
• Hip
• Random Time
• Polynomial-time Algorithm
• Set Partitioning
• Number Theory
• Non-deterministic Polynomial-time
• Turing Machine
• Partitioning Problem