Обследование #P и / или подсчет проблем

23

Может кто-нибудь предложить хороший и недавний опрос по подсчету проблем и / или проблем, которые #P.

cc.complexity-theory reference-request counting-complexity Тайфун Пей
источник
Эти документы, кажется, немного и далеко друг от друга. Я был бы очень заинтересован в хорошей обзорной работе на эту тему. Я заметил, что Википедия даже не содержит "Список # P-полных проблем". Также интересно, что сегодня было 3 вопроса с просьбой дать рекомендации для подсчета проблем.
bbejot

Ответы:

13

Л. Фортноу. Подсчет сложности . В L. Hemaspaandra и A. Selman, редакторы, Ретроспективная теория сложности II, стр. 81-107. Springer, 1997

Это дает больше структурной точки зрения сложности (классы сложности, оракулы и т. Д.) И обсуждает другие классы, связанные с #P. Несмотря на то, что это от почти 15 лет назад, это действительно не что устарели с точки зрения результатов.

Джошуа Грохов
источник
1
@ Тайфун: Чего не хватает? Не то чтобы я не соглашался с вами, мне просто любопытно, что конкретно вы хотели бы увидеть в дополнение.
Джошуа Грохов
9

Пиньян Лу опубликовал опрос через ECCC в середине 2011 года. В нем сравниваются три популярные системы подсчета:

  • Подсчет графа гомоморфизмов,
  • Подсчет удовлетворенности ограничений (#CSP) и
  • рамки Holant
  • (и ограничения этих рамок).

Он также обсуждает текущие теоремы дихотомии и методы доказательства, используемые для их получения.

Си Чен опубликовал опрос в качестве гостевой колонки для новостей SIGACT в конце 2011 года. В нем обсуждаются результаты и методы, приведшие к его работам с Цзинь-И Цаем и Пиньяном Лу и включающие его в себя дихотомии для подсчета гомоморфизмов графа, определяемого неориентированным целевым графом с комплексные веса ( arXiv ) и неотрицательно-взвешенные #CSP ( arXiv ).

Примерно в то же время Кай и Чен опубликовали дихотомию для комплексно-взвешенных #CSP ( arXiv ), которую Кай обсуждал в гостевом посте в Потерянном письме Годеля и в блоге P = NP .

Тайсон Уильямс
источник
Ницца! Я прочитаю это!
Tayfun Pay
3

Другая схема подсчета проблем исходит из вычисления полинома Тутте графа. В этой структуре любые два комплексных числа определяют проблему подсчета.

Книга Matroid Applications посвящает главу 6 полиному Тутте и его приложениям . Предыдущая ссылка - это отсканированное изображение этой главы с сайта Джеймса Оксли , одного из соавторов. В прошлом семестре он преподавал курс, основанный на этой главе.

Еще одна хорошая ссылка на эту тему - это обзорная статья валлийца.

Тайсон Уильямс
источник