减少的类型和硬度的相关定义

Question

令A可还原为b，即，$ a leq b $。因此，接受$ a $的图灵机可以使用$ b $的Oracle访问。让Turing Machine接受$ a $ be $ m_ {a} $，而$ b $ be $ o_ {b} $的Oracle。减少的类型：

• 简化图灵：$ m_ {a} $可以对$ o_ {b} $进行多个查询。

• KARP降低：也称为“多项式时间修补缩减”：必须在Poly Time中构建$ O_ {B} $的输入。此外，必须通过多项式将查询数量到$ o_ {b} $界定。在这种情况下：$ p^{a} = p^{b} $。

• 多个图灵减少：$ m_ {a} $在最后一步中只能对$ o_ {b} $进行一个查询。因此，无法修改Oracle响应。但是，构建输入到$ o_ {b} $所花费的时间不必由多项式界定。等效：（$ leq_ {m} $表示多个减少）

  $ a leq_ {m} b $如果$ 存在$ a computable函数$ f： sigma^{ ast} to sigma^{ ast} $，以便$ f（x） in B in b iff x in $。

• 库克还原：也称为“多项式时间多一减少”：一个多一的减少，其中将输入构造为$ o_ {b} $所花费的时间必须由多项式界定。等效：（$ leq^{p} _ {m} $表示多个减少）

  $ a leq^p_ {m} b $如果$ 存在$ a 聚时 可计算函数$ f： sigma^{ ast} to sigma^{ ast} $，使得$ f（x） in B iff x in a $。

• 简约的减少：也称为“多项式时间一对一”：库克减少，其中每种$ a $ a $ a $ a $ a映射到$ b $的唯一实例。等效：（$ leq^{p} _ {1} $表示parsimonious减少）

  $ a leq^p_ {1} b $如果$ 存在$ a 聚时 可计算的双歧射击$ f： sigma^{ ast} to sigma^{ ast} $，使得$ f（x） in B iff x in a $。

  这些减少保留了解决方案的数量。因此，$ ＃m_ {a} = #o_ {b} $。

我们可以通过界限Oracle查询的数量来定义更多类型的减少类型，但是排除这些查询的数量可以告诉我，我是否正确使用了所使用的不同类型的减少类型的命名法。 NP完整问题是否因减少厨师的减少或简约的减少而定义？任何人都可以举例说明一个问题在库克下且不会减少的问题。

如果我没有错，则将＃p-Complete类定义有关KARP减少。

Answer 1

您对简约减少的定义是不正确的。您将其与多项式时间降低相混淆，这是KARP减少的特殊情况。他们没有保留“解决方案”的数量。请参见 这个答案 有关减少证书数量的更多信息。

剩下的似乎很好，尽管通常最好在二维图表中查看它们：

• 还原的复杂性：可计算，多项式时间，对数空间等。
• 访问类型：图灵，多一，一对一等。

NP完整问题是否因减少厨师的减少或简约的减少而定义？

$ mathsf {np} $硬度和完整性是定义的WRT karp降低（多个），而不是cook或parsimonious降低。

任何人都可以举例说明一个问题在库克下且不会减少的问题。

采用SAT的补充，在库克降低的$ mathsf {np} $上是完整的，在karp降低下，它不认为$ mathsf {np} $是完整的。 KARP降低包括多时间降低。

＃p-Complete类是针对KARP降低的

注意 $ mathsf {＃p} $ 不是决策类问题，而是一类功能计算问题。它的硬度和完整性通常是定义的WRT库克减少（Poly Time Turing）。参见例如Arora和Barak，第346页。

Answer 2

减少KARP的定义是不正确的。减少KARP是多项式的图丁减少，其中甲骨文 $ o_b $ 在最后一步中，完全称为一次。