On polynomial time isomorphisms of some new complete sets
作者：
Highlights：
•
摘要
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 EXTAPE complete sets arising from algebraic word problems are polynomial time isomorphic to the previously known complete sets in the corresponding classes.
论文关键词：
论文评审过程：Received 27 December 1976, Revised 1 August 1977, Available online 2 December 2003.
论文官网地址：https://doi.org/10.1016/0022-0000(78)90027-2
