On Polynomial Time Isomorphism of Complete Sets
Berman, L.; Hartmanis, Juris
IN this note we show that the recently discovered NP complete sets arising in number theory, the PTAPE complete sets arising in game theory and EXPTAPE complete sets arising from algebraic word problems are polynomial time isomorphic to the previously known complete sets in the corresponding categories.
computer science; technical report
Previously Published As