Mengapa varian penghitungan masalah keputusan sulit tidak secara otomatis sulit?

Sudah diketahui bahwa 2-SAT ada di P. Namun, tampaknya cukup menarik bahwa menghitung jumlah solusi untuk formula 2-SAT yang diberikan, yaitu, # 2-SAT adalah # P-hard. Yaitu, kami memiliki contoh masalah yang keputusannya mudah, tetapi berhitung itu sulit.

Tetapi pertimbangkan masalah NP-complete sewenang-wenang (katakanlah 3-COL). Bisakah kita segera mengatakan sesuatu tentang kekerasan varian penghitungannya?

Sungguh yang saya tanyakan adalah: mengapa kita perlu bukti lain untuk menunjukkan varian penghitungan masalah keputusan sulit juga # P-hard? (Terkadang Anda melihat pengurangan pelit yang mempertahankan jumlah solusi, dan sebagainya). Maksud saya benar-benar, jika masalah penghitungan itu mudah, Anda dapat secara otomatis menyelesaikan masalah keputusan juga! Jadi bagaimana tidak sulit? (Oke, mungkin itu sulit, tapi saya tidak yakin untuk definisi apa yang sulit).

Alasannya bukan teorema otomatis bahwa "keputusan sulit menyiratkan bahwa penghitungan itu sulit" adalah bahwa kedua pernyataan ini menggunakan definisi berbeda dari "keras".

• Masalah keputusan sulit jika NP- lengkap di bawah banyak-satu pengurangan polinomial (alias pengurangan Karp, alias pengurangan pemetaan polinomial-waktu).

• Masalah penghitungan sulit jika #P -lengkap di bawah pengurangan Turing polinomial waktu (alias pengurangan Cook).

Dengan demikian, jika masalah keputusan adalah NP- lengkap, kita tahu bahwa masalah penghitungan yang sesuai adalah NP-keras tetapi itu bukan definisi dari apa masalah penghitungan sulit. Menjadi #P -lengkap tampaknya menjadi pernyataan yang jauh lebih kuat dari sekedar menjadi NP -hard - Toda telah menunjukkan bahwa masalah #P -lengkap sulit untuk seluruh hierarki polinomial di bawah pengurangan acak sehingga, sebagai kelas kompleksitas, #P terasa lebih dekat ke PSPACE daripada ke  NP .

Pergi ke arah yang berlawanan, itu jelas benar bahwa, jika masalah penghitungan mudah dalam arti berada di  FP , maka masalah keputusan dalam  P . Lagi pula, jika Anda dapat menghitung dengan efisien, Anda tentu dapat mengetahui apakah jawabannya bukan nol. Namun, hanya karena versi penghitungannya "tidak sulit" (yaitu, tidak #P -lengkap ) tidak menyiratkan bahwa itu "mudah" (yaitu, dalam  FP ). Teorema Ladner meluas ke  #P jadi, jika FP$\,\neq\,$** # P ** lalu ada hierarki tak terbatas dari kelas kompleksitas yang berbeda di antara mereka sehingga masalah penghitungan "tidak sulit" kami dapat diselesaikan untuk salah satu dari kelas tersebut dan, karenanya, tidak menjadi "mudah" (dalam  FP ).

Karena itu, saya tidak berpikir kita memiliki contoh tandingan untuk dugaan bahwa masalah keputusan menjadi NP -complete berarti bahwa versi penghitungan adalah #P -complete. Jadi, itu bukan teorema tetapi secara empiris benar.