大门|大门-CS-2005 |问题45

考虑三个决策问题P1、P2和P3。众所周知，P1是可判定的，P2是不可判定的。以下哪一项是正确的？ （A） 如果P1可还原为P3，则P3是可判定的 （B） 如果P3可还原为P2，则P3是不可判定的 （C） 如果P2可还原为P3，则P3是不可判定的 （D） 如果P3可还原为P2的补码，则P3是可判定的 答复: （C） 说明： 背景： 在计算复杂性理论中，一个决策问题只有两个可能的结果是或否。 如果存在一种有效的方法或算法，可以对决策问题给出正确的是/否答案，则称决策问题是可决策的。 如果没有一个算法总是能给出正确的是/否解，那么决策问题就是不可判定的。

在可还原性方面：A≤ _P B表示A是一个决策问题，在多项式时间p内可化简为B。这意味着A的实例可以转化为B的实例，在B的解之后，我们可以得到问题A的解。 因此，我们可以得出一些结论：

1. If A ≤p B and B is decidable then A is also decidable.
This is because if there exists a specific algorithm for solving B and we can 
also reduce A to B then we can have a solution of A as well. Hence A is decidable.

However the reverse is not true i.e. if A ≤p B and A is decidable 
then B is also decidable because A can have an algorithm existing for its correct 
solution but might be the case that B does not.

2. If A ≤p B and A is undecidable then B is also undecidable.
This is because if A is undecidable even when it can be reduced to B that simply 
reflects even B cannot provide an algorithm by which we can solve B and hence A. 
So decision problem B is also undecidable.

然而，相反的情况在这里也不正确，即如果≤ _P B是不可判定的，那么A也是不可判定的，因为可能存在A的算法，可以为A提供解决方案。

根据上述结论，我们可以说选项1、2和4是错误的，选项3是正确的。

Option 1: P1 ≤p P3 and given P1 is decidable gives no conclusion for P3.
Option 2: P3 ≤p P2 and given P2 is undecidable gives no conclusion for P3.
Option 3: P2 ≤p P3 and given P2 is undecidable gives conclusion for P3 to be 
          undecidable.
Option 4: P3 ≤p P2’s complement and given P2 is undecidable therefore P2’s 
           complement is also undecidable gives no conclusion for P3.

这一解释是由 安倍晋香。

访问以下文章了解更多信息： 不可判定性与可约性 维基百科： 简化（复杂性） 这个问题的小测验