TY - GEN
T1 - A uniform reduction theorem extending a result of J. Grollmann and A. Selman
AU - Regan, Kenneth W.
N1 - Publisher Copyright:
© 1986, Springer-Verlag.
PY - 1986
Y1 - 1986
N2 - We derive a recursion-theoretic result telling when a family of reductions to a class can be replaced by a single oracle Turing machine. The theorem is a close analogue of the Uniform Boundedness Theorem of functional analysis, specializing it to the Cantor-set topology on ℙ(Σ*). This generalizes one of the main theorems of J. Grollmann and A. Selman [FOCS '84], namely that NP-hardness implies uniform NP-hardness for ‘promise problems’. We investigate other consequences and problems arising from the theorem.
AB - We derive a recursion-theoretic result telling when a family of reductions to a class can be replaced by a single oracle Turing machine. The theorem is a close analogue of the Uniform Boundedness Theorem of functional analysis, specializing it to the Cantor-set topology on ℙ(Σ*). This generalizes one of the main theorems of J. Grollmann and A. Selman [FOCS '84], namely that NP-hardness implies uniform NP-hardness for ‘promise problems’. We investigate other consequences and problems arising from the theorem.
UR - https://www.scopus.com/pages/publications/84913447610
U2 - 10.1007/3-540-16761-7_82
DO - 10.1007/3-540-16761-7_82
M3 - Conference contribution
AN - SCOPUS:84913447610
SN - 9783540167617
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 324
EP - 333
BT - Automata, Languages and Programming - 13th International Colloquium, Proceedings
A2 - Kott, Laurent
PB - Springer Verlag
T2 - 13th International Colloquium on Automata, Languages and Programming, ICALP 1986
Y2 - 15 July 1986 through 19 July 1986
ER -