如果x是NP完整的，并且y在NP中，为什么y也必须是np complete
假设x和y是x≤py，即，x的决策问题。如果x是NP算法，而y在NP中，为什么y也必须是NP complete。
Suppose X and Y are decision problems for which X≤ P Y, i.e., X is polynomial-time reducible to Y . If X is NP-complete and Y is in NP, why Y must also be NP-complete.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
如果x完成NP，特别是NP硬，即每个NP问题z都是可还原为x的多项式时间，而x又是y可还原为y的多项式时间，因此y也很难。 NP和NP都硬性意味着您已完成NP，因此Y已完成。
If X is NP complete, in particular it is NP hard, that is, every NP problem Z is polynomial-time reducible to X, which in turn is polynomial-time reducible to Y, thus Y is also NP hard. Being both NP and NP hard means you're NP complete, therefore Y is NP complete.