整数分解的复杂性

Question

在尼尔森和志南的量子信息和量子计算中，它们定义了复杂性类 np 如下（第142页）：

语言 $ l $ 在 np 中，如果有一个图灵机 $ m $ 具有以下属性。

1. 如果 $ x \ in l $ 中，则存在一个证人字符串 $ w $ 这样< Span Class=“Math-Container”> $ M $ 停止在状态 $ q_y $ （“是状态”）之后 $ | x | $ 在状态 $ x $ -blank - $ w $ 。
2. 如果 $ x \ not \ in l $ 那么对于所有字符串 $ w $ 试图发挥证人的作用 机器在状态 $ q_n $ （“no状态”）在 $ | x | $ 当 $ m $ 开始时 state $ x $ -blank- $ w $ 。

本定义是由要分解决策问题的激励，其中它们识别“证人字符串” $ w $ ，具有 $ x $ 。

我的混乱是基于如何定义 np ，似乎我们能够构建用于解决分解决策问题的多项式时间算法。对于给定的字符串 $ x $ ，在状态 $ m $ =“math-container”> $ x $ -blank- $ w $ 所有 $ w ，并检查机器是否在 $ q_y $ 中停止。由于存在 $ o（| x |）$ 证人来检查，并且对于每个证人，机器将停止在多项式时间中，因此该算法将确定是否 $ x $ 在多项式时间内具有因素。

显然这应该不起作用，但我不确定我的逻辑中的缺陷。

Answer 1

问题是，您所提出的算法是关于输入的数值的多项式，但不相对于输入的大小。 $ n $ 的二进制编码需要大多数 $ \ lceil \ log n \ rceil $ 比特，所以一种算法，它采用 $ n $ 和预制级 $ \ oomega（n）$ 操作实际上是指数。这些算法在伪多项式时间。

另外，您似乎是混淆的因子和原始测试。给出一个可能的决策版本 $（n，x）$ 检查 $ n $ 有一个因子 $ \ le x $ （虽然您的提议是指仅给出 $ n $ 的情况，而且你循环找到可能的因素）。在检查给定的数字是否已知在 $ p $ 时，认为要在p中的外部介绍。