我有2 ^ n $位大小证书的决策问题，如果它是$ np $的情况，我将如何验证我的决策问题？

Question

决策问题： $ 2 ^ k $ + $ m $ 一个素数？

$ k $ 和 $ m $ 的输入只有整数。解决方案是 $ 2 ^ $ + $ m $ 的总和。 （使用AKs来决定Prime ）

2的动力约为 $ 2 ^ n $ 数字。考虑 $ 2 ^ k $ 其中 $ k $ = 100000.比较 $ k $ 它的解决方案中的数字数量！

问题

看到决策问题的证书可以是 $ 2 ^ $ 大小，我如何验证多项式时间中的决策问题，考虑到我只能查看转换状态本身是证书？

换句话说，多项式时间验证者看起来像这个决定问题？

Answer 1

决策问题有是/否答案，因此它不能有“指数大小”。您在询问搜索问题，那些肯定可以具有指数尺寸。是的，如果解决方案的大小（以某种适当紧凑的格式写下来）是指数在原始问题的尺寸的指数中，甚至不可能在多项式时间中写下答案。

在任何情况下，P和NP严格仅适用于决策问题。但是看看Belare的“决策与搜索”两者之间的关系。