Como um problema pode estar no NP, ser difícil do NP e não completo do NP?

Durante muito tempo, pensei que um problema era NP-completo se fosse (1) NP-difícil e (2) estivesse em NP.

No entanto, no famoso artigo "O método elipsóide e suas conseqüências na otimização combinatória" , os autores afirmam que o problema do número cromático fracionário pertence ao NP e é NP-difícil, mas ainda não é conhecido como NP-completo. Na terceira página do artigo, os autores escrevem:

... observamos que o problema de empacotamento de vértices de um gráfico é, em certo sentido, equivalente ao problema de número cromático fracionário, e comentamos o fenômeno de que esse último problema é um exemplo de um problema em que é N P -hard mas (como por agora) não conhecido por ser N P -completo.$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$

Como isso é possível? Estou faltando um detalhe sutil na definição de NP-complete?

Parece que o problema é o tipo de reduções utilizadas para cada um deles, e eles estão usando os diferentes: eles provavelmente média " -Hard wrt reduções cozinhar" e " N P -completo wrt reduções Karp".$\mathsf{NP}$$\mathsf{NP}$

Às vezes, as pessoas usam a versão redução Cook, -hardness porque é aplicável a problemas computacionais mais gerais (e não apenas problemas de decisão). Embora a definição original de ambos N P -hardness e N P reduções de Cook usados -completeness (polinomial-time Turing reduções) tornou-se raro usar reduções de Cook para N P -completeness (a menos que seja explicitamente indicado). Não me lembro de qualquer trabalho recente que usou N P -Complete significar N P wrt -completo reduções Cook. (Como observação, observe o primeiro problema a ser provado para N $\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$-hard não era TAUT e a integridade do SAT está implícita nessa prova.)

Agora, se você olhar para a seção 7 do papel, parte inferior da página 195, você vai ver que eles significam reduções wrt Turing -hardness.$\mathsf{NP}$

Então, o que eles querem dizer aqui é que o problema está no , é difícil para N P wrt reduções de Cook, mas não se sabe ser difícil para N P wrt reduções Karp (em tempo polinomial muitos-um reduções).$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$