Lecture 10 | NP-Completeness

:material-circle-edit-outline: 约 116 个字

• P问题：确定性图灵机能够在多项式时间内解决的问题
• NP问题：非确定性图灵机能够在多项式时间内解决的问题 == 确定性图灵机能够在多项式时间内验证（答案正确性）的问题

NP问题：一个能够在多项式时间内验证（答案正确性）的问题能否在多项式时间内解决的问题？

NPC问题：