Bisakah masalah grafik alami menjadi sulit secara universal?

Apakah ada alam masalah grafik -Lengkap, yang tetap -Lengkap bahkan ketika itu dibatasi untuk setiap polinomial-waktu kelas grafik dikenali? Untuk menghindari kasus yang mengalami kemunduran, mari kita perhatikan hanya kelas grafik padat , di mana jumlah grafik non-isomorfik -vertex tumbuh secara eksponensial dengan .N $\mathsf{NP}$$\mathsf{NP}$$\leq n$$n$

Catatan:

(1) Baik jawaban "ya" atau "tidak" akan cukup menarik. Jika jawabannya adalah ya, maka kita akan memiliki properti grafik alami yang bisa disebut universal hard, karena itu mempertahankan kekerasan bahkan ketika terbatas pada kelas grafik yang masuk akal. Jika jawabannya tidak, itu berarti bahwa setiap properti grafik natural lengkap dapat dipermudah pada beberapa kelas grafik nontrivial.$\mathsf{NP}$$\mathsf{NP}$

(2) Penting untuk mempertimbangkan hanya kelas grafik yang dapat dikenali polinomial waktu, untuk mengecualikan bahwa kekerasan properti hanya bergeser ke kelas. Sebagai contoh, 3-COLORABILITY menjadi sepele ketika terbatas pada grafik 3-warna.

Definisi "alami" agak kabur, tetapi ada alasan sepele jawabannya di sini kemungkinan "tidak". Misalkan sebaliknya bahwa ada masalah seperti itu, . Jika P hanya bertindak pada komponen pertama dari grafik yang disediakan, maka P mudah pada kelas grafik di mana komponen pertama adalah turunan dari P dan komponen kedua mengkode sertifikat P yang memegang komponen pertama. Lebih lanjut, kelas grafik ini dapat dikenali dari waktu. Memang, hal yang sama berlaku jika kita dapat menetapkan sebagian grafik sebagai "ini adalah sertifikat dan bukan bagian dari komponen masalah", dalam arti bahwa kita dapat menyelinap masuk ke sertifikat ini tanpa mempengaruhi jawaban yang sebenarnya.$P$$P$$P$$P$$P$

Sebagian besar masalah "alami", sejauh yang saya tahu, memungkinkan penunjukan bagian grafik. Berikut ini beberapa contohnya

• Max Clique: cukup pastikan bahwa bagian sertifikat dari grafik tidak memiliki klik besar (mis. Mengkodekannya menggunakan pencocokan)
• Jalur Hamiltonian: simpul ekor diganti dengan grafik sertifikat yang memiliki jalur Hamiltonian yang mudah ditemukan sendiri
• Sirkuit Hamilton: sama dengan jalur Hamilton kecuali beberapa titik yang ditunjuk diganti dengan grafik sertifikat yang mengandung siklus Hamilton
• Max Cut: ini tidak mempengaruhi solusi selama tidak ada tepi pada bagian grafik lainnya, jadi kami hanya memastikan bahwa cut maksimum di sini mudah ditemukan (mis. Kami menyandikan menggunakan pencocokan)
• Penutup vertex: sertifikat dikodekan lagi oleh pencocokan

Kami memastikan bahwa bagian sertifikat dari grafik ditetapkan seperti itu, sehingga tidak kehilangannya di sisa grafik (meskipun menunjuk secara implisit melalui struktur grafik mungkin cukup mudah untuk sebagian besar masalah "alami").

$P=NP$