我可以验证解决多项式时间中的问题，如果它始终需要2 ^ n $位，则非确定性算法将如何到达解决方案？

Question

决策问题：给定整数作为 $ k $ 和 $ m $ 的输入。是 $ 2 ^ $ + $ m $ a $ Prime $ ？

验证器

m = int(input('Enter integer for M: '))
sum_of_2**K+M=int(input('enter the sum of 2^k+m: '))

if AKS.sum_of_2**K+M == True:

  # Powers of 2 can be verified in O(N) time
  # make sure there is all 0-bits after the 1st ONE-bit
  
  # Use difference to verify problem

  if sum_of_2**K+M - (M) is a power_of_2:
    OUTPUT Solution Verified

.

2的动力约为 $ 2 ^ n $ 数字。考虑 $ 2 ^ k $ 其中 $ k $ = 100000.比较 $ k $ 它的解决方案中的数字数量！也注意到2 的 powers有 $ 2 ^ n $ 位作为其 0位联合机构基本上用于指数 $ n $ 。

问题

非确定性机器如何解决多项式时间中的这个问题？

Answer 1

验证者是K和M的多项式。它甚至是k的多项式和尺寸，但这并不是我们所依赖的“在P”中。它必须在k的大小和尺寸的尺寸中是多项式。如果k= 100,000则k的尺寸仅为17位。不太可能在此数量中可以检查多项式时间中的原始算法 - 即使m= -1，我们也没有在k算法中具有更快的多项式的多项式。

它不是被证明是不可能的，但非常不可能。即使我给了你100,000位号码的50,000位除数，你也无法验证它足够快。

Answer 2

当我看到它时，这个决策问题显然是在P的。因此，没有任何非确定性的图灵机无法猜测。非确定性图灵机将调用给定问题实例的多项式时间验证者，并且在多项式时间中解决问题。