A Comparison of Polynomial Time Reducibilities
A Comparison of Polynomial Time Reducibilities
复制标题
多项式时间约简性的比较
DOI：
10.1016/0304-3975(75)90016-x
复制
发表时间：
1975
期刊：
影响因子：
--
通讯作者：
A. Selman
中科院分区：
文献类型：
--
作者：
R. Ladner;N. Lynch;A. Selman
比较Cook [1]和Karp [4]引入的多项式时间有界可约性，自然引出几种中间真值表可约性的定义。我们给这些可约性的定义和比较，我们注意到，特别是，所有这种类型的可约性，没有明显的蕴涵关系，实际上是不同的，在很强的意义上。Meyer和Stockmeyer [7]和Gill [2]的工作引导我们定义所有可约性的非确定性版本。虽然许多定义退化，其余的非确定性可约性之间的比较，并与相应的确定性可约性产生一些有趣的关系。
Comparison of the polynomial-time-bounded reducibilities introduced by Cook [1] and Karp [4] leads naturally to the definition of several intermediate truth-table reducibilities. We give definitions and comparisons for these reducibilities; we note, in particular, that all reducibilities of this type which do not have obvious implication relationships are in fact distinct in a strong sense. Proofs are by simultaneous diagonalization and encoding constructions.Work of Meyer and Stockmeyer [7] and Gill [2] then leads us to define nondeterministic versions of all of our reducibilities. Although many of the definitions degenerate, comparison of the remaining nondeterministic reducibilities among themselves and with the corresponding deterministic reducibilities yields some interesting relationships.