基于NP验证者的定义 [英] NP verifier-based definition

问题描述

我是一名计算机科学专业的学生，​​在理解基于验证者的NP问题定义时遇到了一些问题.

i'm a computer science student and i'm having some problem understanding the verifier based definition of NP problems.

定义说，如果可以在给定的证书"的情况下，通过确定性的图腾机在政治时间内验证问题，那么NP中就存在问题.

The definition says that a problem is in NP if can be verified in polinomial time by a deterministic turing machine, given a "certificate".

但是，如果证书正是有问题的解决方案，那会发生什么呢?这只是一点点，而且明显地受输入大小的限制，并且显然可以在常量时间(即政策时间)内进行验证.

But what happens, if the certificate is exactly the problem solution? It's only a bit, and it's obviuosly polinomially limited by the input size, and it's obviously verifiable in constant, thus polinomial time.

因此，每个决策问题都将属于NP.

Therefore, each decision problem would belong to NP.

我在哪里错了?

推荐答案

但是，如果证书正是有问题的解决方案，那会发生什么呢?只是一点点，而且明显地受输入大小的限制，并且显然可以在常量时间(即政策时间)内进行验证.

But what happens, if the certificate is exactly the problem solution? It's only a bit, and it's obviuosly polinomially limited by the input size, and it's obviously verifiable in constant, thus polinomial time.

为什么显然"?您可能需要花费大量时间来验证解决方案，在这种情况下，问题不必出在NP上.关键是，即使证书只是一个决策问题位，您也不知道该位应为零还是一以解决问题. (如果您一直都知道，那么P或NP中的任何决策问题都可以在恒定时间内解决.)

Why "obviously"? You might have to spend an exponential amount of time verifying the solution, in which case the problem need not be in NP. The point is that, even though the certificate is a single bit for a decision problem, you don't know whether that bit should be zero or one to solve the problem. (If you always did know that, then any decision problem in P or in NP would be solvable in constant time.)

这篇关于基于NP验证者的定义的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！