“给定算法，决定它是否在多项式时间中运行”是NP中的这个问题吗？

Question

这个问题是不是可解除的（可将其删除为删除问题），但是是半解解码的，因此可验证（因为这两个定义等同于：如何证明半解解码=可验证？）。

但是，这是该问题的多时间可验证吗？

一个决策问题 $ p $ 是多时间验证的iff有一个算法

Answer 1

no。如果问题是多项式时间可验证，它将在指数时间中可解决，因此可判定;但我们已经知道这不是可判定的。

为什么在指数时间？因为 $ v $ 运行时间 $ | w | ^ k $ ，它可以读取最多 $ | w | ^ k $ 输入的输入。因此，枚举所有可能的字符串 $ c $ 以大多数 $ | w | ^ k $ ，并运行 $ v $ 在其中每个。运行时间将是 $ 2 ^ {| w | ^ k} $ ，这是有限的，因此足以使原始问题可解除。