NP完整问题等效的这两个定义是否等效？
定义1（通常定义） 问题b是NP完成的，如果
- b在
- NP中的c中为np，则C是b definity 2（在几个文档中）的多项式时间
（在几个文档中） 则A问题B是NP算法
- 如果B在np中，
- ，如果B允许多项式时间算法，则NP中的所有问题也接受了多项式时间算法
（如“如“某些编码问题）的固有性无关...，...，... Berlekamp，McEliece和Tilborg”以及其他文件
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
定义1是如果您将可简化的性能定义为多项式映射可降低性（有时称为多项式时间多种可还原性），则获得了NP完整性的定义。也就是说，您可以通过进行多项式工作以转换输入，然后对目标问题进行一次调用，从而将一个问题减少到另一个问题。这是NP完整性的标准定义。
定义2是如果您使用多项式时间的杜松时间可还原性（称为 polynomial time dising降低性 time_reduction＃turing_reductions“ rel =“ nofollow noreferrer”> cook降低），其中允许您花费多项式时间，包括与oracle（求解器）的任意电话，以解决您要降低的问题。
Definition 1 is the definition of NP-completeness you get if you define reducibility to be polynomial-time mapping reducibility (sometimes called polynomial-time many-one reducibility). That is, you’re allowed to reduce one problem to another by doing polynomial work to transform the input, then make a single call to the target problem. This is the standard definition of NP-completeness.
Definition 2 is the (nonstandard) definition of NP-completeness you get if you use polynomial-time Turing reducibility (called Cook reductions), in which you are allowed to spend polynomial time including an arbitrary number of calls to an oracle (solver) for the problem you’re reducing to.