我的理解关于三种问题类型是正确的吗?
为了证明问题X属于NP:
- 展示X可以在多项式时间内被确定性地验证(或者X可以使用非确定性图灵机求解)。
为了证明问题X属于NP-完全:
- 展示X可以在多项式时间内被确定性地验证(或者X可以使用非确定性图灵机求解)。
- 展示存在已知的NP-完全问题L,使得L可以约化到X。
- 展示存在已知的NP-完全问题L,使得X可以约化到L(这一步是否必要?若必要,这是什么区别了纯NP-难问题和NP-完全问题?)。
为了证明问题X属于NP-难:
- 展示存在已知的NP-完全问题L,使得L可以约化到X。