如果决策问题处于$ P $，则必须在多项式时间内找到解决方案？

Question

找到解决方案的函数问题

• 给定 $ n $ 的整数。

• find $ 2 $ 整数从 $ n $ 。（但是，少于 $ n $ ）

• 具有等于 $ n $ 。

这意味着我们必须排除整数 $ 1 $ 和 $ n $ 。

是伪多项式

的算法

N = 10

numbers = []

for a in range(2, N):
    numbers.append(a)


for j in range(length(numbers)):
  if N/(numbers[j]) in numbers:
   OUTPUT N/(numbers[j]) X numbers[j]
   break

.

输出

Soltuion Verified: 5 x 2 = N and N=10

.

解决决策问题

的算法

if AKS-primality(N) == False:
  OUTPUT YES

.

问题

由于决策问题在 $ p $ 中，必须找到一个解决方案也可以在多项式时间内可解决Δ

Answer 1

否，您列出的示例是一个经典榜样：据我所知，要素似乎不是 $ p $ ，但确定是否a数字是素数肯定是 $ p $ 。

另一个例子：考虑游戏 hex 。考虑决策问题：给定 $ n $ ，确定第一个玩家是否在 $ n \n\n\中有一个获胜的hex策略时代N $ 板。有一个相应的函数问题：给定 $ n $ ，找到这样的获胜策略。嗯，决策问题是微不足道的（众所周知，答案总是“是”），但函数问题被认为是非常努力的（据我们所知）。