Masalah NP-lengkap dengan jumlah polinomial yes-instance?

Saya memiliki kesan bahwa untuk setiap masalah NP-complete, untuk banyak ukuran input , jumlah yes-instance atas semua kemungkinan input ukuran n , adalah (setidaknya) eksponensial dalam .$n$$n$$n$

Apakah ini benar? Bisakah itu dibuktikan (mungkin hanya dengan asumsi bahwa )? Atau bisakah kita, mungkin secara artifisial, menemukan masalah di mana untuk semua (cukup besar) , jumlah yes-instance paling banyak polinomial dalam ?$P\neq NP$$n$$n$

Alasan saya pada dasarnya adalah memberikan contoh-ya untuk 3-SAT, kita dapat mengidentifikasi literal di setiap klausa yang membuatnya benar dan mengganti variabel lain dalam klausa dengan variabel lain, tanpa mengubah itu memuaskan. Karena kita bisa melakukannya dengan setiap klausa, itu mengarah ke jumlah eksponensial dari yes-instance. Hal yang sama berlaku untuk banyak masalah lain seperti jalur hamiltonian: kita dapat dengan bebas mengubah tepi yang tidak ada di jalur. Saya kemudian dengan bodoh beralasan bahwa karena reducibilitas terlibat di mana dalam beberapa cara solusi harus disimpan, itu harus berlaku untuk semua masalah NP-lengkap.

Tampaknya juga berlaku untuk masalah yang mungkin NP-menengah dari isomorfisme grafik (di mana kita dapat dengan bebas menerapkan perubahan yang sama untuk kedua grafik jika kita tahu pemetaan). Saya bertanya-tanya apakah itu juga berlaku untuk faktorisasi bilangan bulat.

Bahasa yang hanya memiliki banyak contoh-ya secara polinomi disebut $\ne$

Ini pertanyaan terpisah apakah jumlah yes-instance adalah eksponensial. (Orang bisa membayangkan bahwa jumlah contoh-ya mungkin lebih dari polinomial tetapi kurang eksponensial.) Dugaan Berman-Hartmanis relevan di sini; itu menyiratkan bahwa semua masalah NP-lengkap memiliki banyak contoh ya secara eksponensial. Dugaan itu tetap merupakan masalah terbuka.