Survei tentang #P dan / atau masalah penghitungan

23

Adakah yang bisa menyarankan survei yang baik dan baru-baru ini tentang penghitungan masalah dan / atau masalah yang # P.

cc.complexity-theory reference-request counting-complexity Tayfun Pay
sumber
Makalah-makalah ini tampaknya sangat sedikit. Saya akan sangat tertarik dengan makalah survei yang baik tentang masalah ini. Saya mencatat bahwa Wikipedia bahkan tidak mengandung "Daftar masalah # P-complete". Menarik juga bahwa ada 3 pertanyaan hari ini yang meminta referensi untuk menghitung masalah.
bbejot

Jawaban:

13

L. Fortnow. Menghitung kompleksitas . Dalam L. Hemaspaandra dan A. Selman, editor, Complexity Theory Retrospective II, halaman 81-107. Springer, 1997

Ini memberi lebih banyak sudut pandang kompleksitas struktural (kelas kompleksitas, nubuat, dll.), Dan membahas kelas-kelas lain yang terkait dengan #P. Meskipun dari hampir 15 tahun yang lalu, itu benar-benar tidak yang keluar dari tanggal dalam hal hasil.

Joshua Grochow
sumber
1
@Ayfun: Apa yang hilang? Bukan berarti saya tidak setuju dengan Anda, saya hanya ingin tahu apa yang ingin Anda lihat sebagai tambahan.
Joshua Grochow
12

Coba catatan kuliah ETH Mark Jerrum . Versi gratis tersedia dari situs webnya di sini .

RJK
sumber
Saya rasa saya menemukannya secara gratis! ;)
Tayfun Bayar
9

Pinyan Lu menerbitkan survei melalui ECCC pada pertengahan 2011. Ini membandingkan tiga kerangka penghitungan populer:

  • Menghitung Homomorfisme Grafik,
  • Menghitung Kepuasan Kendala (#CSP), dan
  • kerangka kerja Holant
  • (dan batasan kerangka kerja ini).

Dia juga membahas teorema dikotomi saat ini dan teknik pembuktian yang digunakan untuk mendapatkannya.

Xi Chen menerbitkan survei sebagai kolom tamu untuk SIGACT News pada akhir 2011. Ini membahas hasil dan teknik yang mengarah ke dan termasuk makalahnya dengan Jin-Yi Cai dan Pinyan Lu pada dikotomi untuk menghitung grafik homomorfisme yang ditentukan oleh grafik target tidak langsung dengan bobot kompleks ( arXiv ) dan #CSPs non-negatif-tertimbang ( arXiv ).

Pada waktu yang hampir bersamaan, Cai dan Chen menerbitkan dikotomi untuk #CSPs berbobot kompleks ( arXiv ), yang dibahas Cai dalam posting tamu di Godel's Lost Letter dan blog P = NP .

Tyson Williams
sumber
Bagus! Saya akan membaca ini!
Tayfun Bayar
3

Kerangka kerja lain untuk menghitung masalah berasal dari komputasi polinomial Tutte dari suatu grafik. Dalam kerangka ini, dua bilangan kompleks menentukan masalah penghitungan.

Buku Aplikasi Matroid mencurahkan bab 6 untuk The Tutte Polinomial dan Aplikasi-nya . Tautan sebelumnya adalah untuk memindai bab itu dari situs web James Oxley , salah satu penulis bersama. Semester terakhir, ia mengajar kursus berdasarkan bab itu.

Referensi bagus lainnya tentang topik ini adalah makalah yang mirip survei oleh Welsh.

Tyson Williams
sumber