Bagaimana sebuah masalah bisa di NP, NP-hard dan bukan NP-complete?

Untuk waktu yang paling lama saya berpikir bahwa masalah adalah NP-lengkap jika keduanya (1) NP-hard dan (2) ada di NP.

Namun, dalam makalah terkenal "Metode ellipsoid dan konsekuensinya dalam optimasi kombinatorial" , para penulis mengklaim bahwa masalah bilangan kromatik fraksi milik NP dan NP-keras, namun tidak diketahui NP-lengkap. Pada halaman ketiga makalah ini, penulis menulis:

... kami mencatat bahwa masalah vertex-kemasan dari grafik adalah dalam arti setara dengan masalah nomor kromatik pecahan, dan komentar pada fenomena bahwa masalah yang terakhir ini adalah contoh dari masalah di yang merupakan N P -Hard tetapi (seperti untuk saat ini) tidak diketahui sebagai N P -complete.$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$

Bagaimana ini mungkin? Apakah saya melewatkan detail halus dalam definisi NP-complete?

Tampaknya masalahnya adalah jenis pengurangan yang digunakan untuk masing-masing, dan mereka menggunakan yang berbeda: mereka mungkin berarti " -hard wrt Cook reduksi" dan " N P- komplet pengurangan Karp reduksi Karp".$\mathsf{NP}$$\mathsf{NP}$

Kadang-kadang orang menggunakan versi pengurangan Cook dari -newness karena ini berlaku untuk masalah komputasi yang lebih umum (bukan hanya masalah keputusan). Meskipun definisi asli dari kedua N P -hardness dan N P pengurangan Masak digunakan -completeness (polinomial-waktu Turing pengurangan) telah menjadi jarang menggunakan pengurangan Masak selama N P -completeness (kecuali dinyatakan secara eksplisit). Saya tidak ingat kertas baru yang telah digunakan N P -Lengkap berarti N P -Lengkap wrt pengurangan Masak. (Sebagai catatan masalah pertama yang harus terbukti N $\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$-Beras itu TAUT bukan SAT dan kelengkapan untuk SAT tersirat dalam bukti itu.)

Sekarang jika Anda melihat bagian 7 dari kertas, bagian bawah halaman 195, Anda akan melihat bahwa mereka berarti pengurangan wrt Turing -hardness.$\mathsf{NP}$

Jadi apa yang mereka maksud di sini adalah bahwa masalahnya adalah di , sulit untuk N P wrt pengurangan Cook, tetapi tidak diketahui menjadi sulit bagi N P wrt pengurangan Karp (polinomial-waktu banyak-satu pengurangan).$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$