Легкие проблемы с жесткими подсчетами версий

20

В Википедии приводятся примеры проблем, где версия для подсчета трудна, а версия для принятия решения проста. Некоторые из них подсчитывают идеальные соответствия, подсчитывают количество решений для SAT и количество топологических сортировок.2

Существуют ли другие важные классы (например, примеры в решетках, деревьях, теории чисел и т. Д.)? Есть ли сборник таких проблем?

Есть много типов проблем в , которые имеют -Жесткие версии подсчета.# PP#P

Существует ли версия естественной проблемы в которая более понятна или проще, чем обычное двустороннее идеальное сопоставление (пожалуйста, включите подробности о том, почему проще, например, доказуемо быть в младших классах иерархии и т. Д.) В какой-то другой области (например, теория чисел, решетки) или, по крайней мере, для отдельных простых двудольных графов, чья версия счета P -hard?N C # PPNC#P

Будут оценены примеры из решеток, многогранников, подсчета точек, теории чисел .

Т ....
источник
1
Предположительно, вам нужны естественные проблемы, поскольку [из-за сокращения #SAT проблемы, которые # P-hard при [сокращениях, которые умножают ответ на ненулевое число], имеют проблемы решения HP-hard] и [с помощью функции тождественности, {x: x равен 1+ (number_of_variables_ ( ϕ )) или [ноль, за которым следует удовлетворительное присвоение ϕ ]}, # P-hard при следующем наиболее строгом сокращении, но его версия решения тривиальна].
@RickyDemer ваше письмо лаконично. Да, я хочу естественные проблемы.
T ....
Разве мы не до конца понимаем идеальные соответствия в двудольных графах? Кроме того, есть алгоритм RNC2 для этой проблемы.
Сашо Николов
1
Да нет. У нас нет детерминированного алгоритма NC
T ....

Ответы:

8

Вот действительно отличный пример (я могу быть предвзятым).

Для частично упорядоченного множества:
а) имеет ли оно линейное расширение (т. Е. Полный порядок, совместимый с частичным порядком)? Тривиально: все посеты имеют хотя бы одно линейное расширение.
Б) Сколько у него? # P-complete для определения этого (Brightwell and Winkler, Counting Linear Extensions , Order, 1991)
c) Можем ли мы сгенерировать их все быстро? Да, в постоянном амортизированном времени (Pruesse и Ruskey, Быстрое создание линейных расширений , SIAM J Comp 1994)

Гара Прюссе
источник
3
+1: я согласен, что это действительно отличный пример (подумал о том, чтобы опубликовать его сам, а затем увидел этот ответ). Кроме того , чтобы кто - то говорит « А что насчет принятия решения , если есть по крайней мере один другой линейное расширение», эта проблема также вполне тривиальна: в общей сложности порядка имеет 1 расширение, все остальные Posets есть> 1. И обнаружения ровно 2 расширения также легко (это происходит, если есть ровно одна пара несопоставимых элементов). Фактически, существует полная классификация наборов с количеством линейных расширений до 7 (см. Hanamura-Iwata, IPL 2011 ).
Джошуа Грохов
Это действительно хороший пример. Однако существует гораздо более «простая» проблема, обладающая такими же свойствами (проще в том смысле, что эти свойства почти тривиально доказать). Подсчет количества удовлетворяющих присвоений DNF: a) каждый непустой DNF является выполнимым b) подсчет является # P-полным (сокращение до #SAT) c) перечисление может быть выполнено с полиномиальной задержкой (возможно постоянное время амортизации, думать об этом)
Холф
Мне было бы очень интересно узнать, могут ли DNF удовлетворяющие задания генерироваться в постоянном амортизированном времени (CAT). В то время и в моей работе с Фрэнком в 1994 году линейные расширения были первым «естественно определенным» объектом, для которого подсчет был трудным, а генерация была такой же быстрой, как и при амортизации (т. Е. CAT). Решения DNF кажутся вероятным кандидатом на это. У кого-нибудь есть ссылка?
Гара Прюссе
@GaraPruesse У меня нет ссылок на это. Для монотонного DNF это эквивалентно перечислению множества гиперграфов, и некоторые методы улучшения задержки представлены в «Эффективных алгоритмах дуализации крупномасштабных гиперграфов» Кейсуке Мураками и Takeaki Uno dl.acm.org/citation.cfm? id = 2611867 . Мы должны проверить, дает ли это CAT. Для DNF моя интуиция заключается в том, что если есть небольшой пункт, то у вас уже есть достаточно решений для грубой форсировки. В противном случае у вас есть только большие предложения, которые могут столкнуться с большей вероятностью, что может быть использовано для разработки алгоритма CAT.
Holf
17

Один интересный пример из теории чисел выражает положительное целое число в виде суммы четырех квадратов. Это можно сделать относительно легко за случайное полиномиальное время (см. Мою статью 1986 года с Рабином на https://dx.doi.org/10.1002%2Fcpa.3160390713 ), и, если я правильно помню, теперь есть даже детерминированный полиномиальное время решение. Но подсчет количества таких представлений позволит вам вычислить функцию суммы делителей , которая является случайным полиномиальным временем, эквивалентным факторингу n . Так что проблема с подсчетом, вероятно, сложная.σ(n)n

Джеффри Шаллит
источник
«Таким образом, проблема подсчета, вероятно , трудно» вы имеете в виду возможно жесткий? у тебя есть доказательства? #P
T ....
Под «вероятно сложным» я подразумеваю, что это случайное полиномиальное время, эквивалентное целочисленной факторизации.
Джеффри Шаллит
3
Итак, чтобы сделать это явным: проблема не в # P-hard (если только не разберется весь ад).
Эмиль Йержабек поддерживает Монику
@JeffreyShallit Есть ли пример ? #P
Т ....
Я думаю, что следующий пример еще проще: «Имеет ли правильный делитель больше 1 » против «Сколько правильных делителей больше 1 имеет n ?». Версия решения эквивалентна « n составная», поэтому она в P , но версия для подсчета не выглядит проще, чем факторинг. n11nnP
Дэн Брамлев
17

Очень хороший и простой пример из теории графов - подсчет числа элерических цепей в неориентированном графе.

Вариант решения прост (... и проблема Семи Мостов Кенигсберга не имеет решения :-)

Версия для подсчета # P-hard: Грэм Р. Брайтвелл, Питер Винклер: Подсчет Eulerian Circuits - # P-Complete . ALENEX / ANALCO 2005: 259-262

Марцио де Биаси
источник
Эта статья «Наш подход состоит в том, чтобы показать, что с помощью оракула, который считает эйлеровы схемы, машина Тьюринга может ...» и «Мы хотим вычислить число эйлеровых ориентаций G. "Разрыв абзаца" Мы строим для любого нечетного простого числа p граф G p , число сфер которого равно N по модулю p . "И" Мы повторяем этот процесс для каждого простого числа p между м и м 2 , где | E | = м , и ... "конечно, предполагают, что они дают только параллельное сокращение, а не даже мNGpGpNpmm2|E|=m ; -query снижение. mϵ
@MarzioDeBiasi - это решение об эйлеровых кругах в Северной Каролине?
T ....
1
@AJ. Вам просто нужно вычислить четность степени каждого узла и проверить, все ли они четны. Кажется, определенно в NC.
Сашо Николов
4
Вы можете взять четность из битов, используя формулу размера O ( n 2 ) или линейную схему размера глубины O ( log n ) . Так что, если ваш граф задан как матрица смежности, вычислите четность каждой строки, отрицайте и возьмите AND. И из n битов можно сделать формулу линейного размера, так что в целом вы получите булеву формулу размера O ( n 3 ) и булеву схему размера O ( n 2 ) глубины O ( log n )nO(n2)O(logn)nO(n3)O(n2)O(logn)(на основе И-ИЛИ). Так что проблема на самом деле в . NC1
Сашо Николов
2
На самом деле проблема в . AC0[2]
Эмиль Йержабек поддерживает Монику
6

Что касается вашего второго вопроса, такие проблемы, как Monotone-2-SAT (определение выполнимости формулы CNF, имеющей не более 2 положительных литералов по выражению), совершенно тривиальны (вам просто нужно проверить, пуста или нет ваша формула), но проблема подсчета # P-hard. Даже приблизительное количество удовлетворительных заданий по такой формуле сложно (см. «О сложности приближенных рассуждений», Дэн Рот, Искусственный интеллект, 1996).

holf
источник
5

Из [Kayal, CCC 2009] : Явное вычисление аннулирующих полиномов в некоторой точке

Из аннотации: `` Это единственная естественная вычислительная проблема, в которой определение существования объекта (в нашем случае аннулирующего полинома) может быть выполнено эффективно, но фактическое вычисление объекта доказуемо сложно. ''

Пусть поле и F = ( F 1 , . . . , Е к ) F [ х 1 , . , , , Х п ] быть набор к -many градусов- й п -мерное многочленов над F . F -annihilating полином является любой (нетривиальным) й ( е 1 , . .Ff=(f1,...,fk)F[x1,...,xn]kd nF.fAA(f1,...,fk)=0.

Решение легко: над любым полем, и для любых многочленов ( F 1 , . . . , Е к ) - если к п + 1 , существует такое аннуляторное для ( F 1 , . . . , Е к ) , ((Посредством аргумента подсчета размеров.))k(f1,...,fk)kn+1,A(f1,...,fk)

Подсчет трудно: Определить аннулирующий-EVAL в качестве функциональной задачи оценки уничтожающего полинома на каком - то момент : Учитывая простой и множество ( е 1 , . . . , Е к ) Z [ х 1 , . , , , Х п ] , которые имеют минимальный унитарный уничтожающий А ( т 1 , . . . , Т к ) Zp,(f1,...,fk)Z[x1,...,xn] выход целое число ( 0 , . . . , 0 ) по модулю р .A(t1,...,tk)Z[t1,...,tk],A(0,...,0)modp.

ANNIHILATING-EVAL это -hard. Кроме того, аннулирующий многочлен ( т 1 , . . . , Т к ) не имеет небольшое представление схемы , если Р Н не разрушается.#PA(t1,...,tk)PH

Даниэль Апон
источник
1
mϵ
1
Все ресурсы, которые я могу найти, похоже, не согласны с определениями. Позвольте AE быть проблемой, которую обсуждает ваш ответ. (... продолжение)
1
( 0 ) || AE [n]
1
AE[n3]/поли .
1
knmaxdegfiNP#P