显示NP,NP-完整性或NP-硬度

Question

我对这三个类别的理解是否正确？

为了表明问题X是NP:

1. 表明X可以在多项式时间内确定性地验证(或者X可以使用NTM解决)

要显示问题,X是NP-Complete:

1. 表明X可以在多项式时间内确定性地验证(或者X可以使用NTM解决)
2. 表明给定已知的NP-C问题L,L≤pX
3. 证明给定一个已知的NP-C问题L,X≤pL(这一步是否必要？如果是这样,这是区分纯NP-Hard问题与NP-C问题的原因吗？)

为了表明问题X是NP-Hard:

1. 表明给定已知的NP-C问题L,L≤pX

Answer 1

你几乎得到了它.

鉴于一个问题X,要显示它是NPC,你不需要显示X ?p L,因为一些NPC问题L.

事实上,这是有保证的,因为你已经证明它X是NP(1),你知道L是NP-Complete.通过NP完全的定义,这意味着有来自NP的所有问题的多项式时间减少L,其中包括X,所以基本上你在证明鼻咽癌是多余的步骤(3).

一种更优雅的方式来显示证明每个属性需要做什么的陈述:

显示X是NP:

1. 表明X可以在多项式时间内确定性地验证(或者X可以使用NTM解决)

显示X是NP-Hard:

1. 表明给定已知的NP-Hard问题L,L≤pX

要么

2. 显示对于LNP 中的任何问题,L≤pX(对于SAT,这实际上只执行一次,并且是NP-Hard的定义).

要显示问题,X是NP-Complete:

1. 显示X是NP-Hard
2. 显示X在NP中