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

20

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

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

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

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

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

reference-request counting-complexity nt.number-theory permanent decision-trees Т ....
источник

1

Предположительно, вам нужны естественные проблемы, поскольку [из-за сокращения #SAT проблемы, которые # P-hard при [сокращениях, которые умножают ответ на ненулевое число], имеют проблемы решения HP-hard] и [с помощью функции тождественности, {x: x равен 1+ (number_of_variables_ (

ϕ

$\phi$ )) или [ноль, за которым следует удовлетворительное присвоение

ϕ

$\phi$ ]}, # P-hard при следующем наиболее строгом сокращении, но его версия решения тривиальна].

@RickyDemer ваше письмо лаконично. Да, я хочу естественные проблемы.

T ....

Разве мы не до конца понимаем идеальные соответствия в двудольных графах? Кроме того, есть алгоритм RNC2 для этой проблемы.

Сашо Николов

1

Да нет. У нас нет детерминированного алгоритма

N C

$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 ), и, если я правильно помню, теперь есть даже детерминированный полиномиальное время решение. Но подсчет количества таких представлений позволит вам вычислить функцию суммы делителей , которая является случайным полиномиальным временем, эквивалентным факторингу . Так что проблема с подсчетом, вероятно, сложная. $\sigma(n)$ $n$

Джеффри Шаллит
источник

«Таким образом, проблема подсчета, вероятно , трудно» вы имеете в виду возможно

жесткий? у тебя есть доказательства?

# P

$\#P$

T ....

Под «вероятно сложным» я подразумеваю, что это случайное полиномиальное время, эквивалентное целочисленной факторизации.

Джеффри Шаллит

3

Итак, чтобы сделать это явным: проблема не в # P-hard (если только не разберется весь ад).

Эмиль Йержабек поддерживает Монику

@JeffreyShallit Есть ли пример

?

# P

$\#P$

Т ....

Я думаю, что следующий пример еще проще: «Имеет ли

правильный делитель больше

» против «Сколько правильных делителей больше

имеет

?». Версия решения эквивалентна «

составная», поэтому она в

, но версия для подсчета не выглядит проще, чем факторинг.

n

$n$

1

$1$

1

$1$

n

$n$

n

$n$

P

$P$

Дэн Брамлев

17

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

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

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

Марцио де Биаси
источник

Эта статья «Наш подход состоит в том, чтобы показать, что с помощью оракула, который считает эйлеровы схемы, машина Тьюринга может ...» и «Мы хотим вычислить число

эйлеровых ориентаций

"Разрыв абзаца" Мы строим для любого нечетного простого числа

граф

, число сфер которого равно

по модулю

. "И" Мы повторяем этот процесс для каждого простого числа p между

и

, где

, и ... "конечно, предполагают, что они дают только параллельное сокращение, а не даже

N

$N$

G

$G$

p

$p$

G_{p}

$G_p$

N

$N$

p

$p$

m

$m$

m^{2}

$m^2$

| E | = m

$|E| = m$

; -query снижение.

m^{ϵ}

$m^{\epsilon}$

@MarzioDeBiasi - это решение об эйлеровых кругах в Северной Каролине?

T ....

1

@AJ. Вам просто нужно вычислить четность степени каждого узла и проверить, все ли они четны. Кажется, определенно в NC.

Сашо Николов

4

Вы можете взять четность из

битов, используя формулу размера

или линейную схему размера глубины

. Так что, если ваш граф задан как матрица смежности, вычислите четность каждой строки, отрицайте и возьмите AND. И из

битов можно сделать формулу линейного размера, так что в целом вы получите булеву формулу размера

и булеву схему размера

глубины

n

$n$

O (n^{2})

$O(n^2)$

O (\log n)

$O(\log n)$

n

$n$

O (n^{3})

$O(n^3)$

O (n^{2})

$O(n^2)$

O (\log n)

$O(\log n)$ (на основе И-ИЛИ). Так что проблема на самом деле в

.

{N C}^{1}

$\mathsf{NC}^1$

Сашо Николов

2

На самом деле проблема в

.

{A C}^{0} [2]

$\mathrm{AC}^0[2]$

Эмиль Йержабек поддерживает Монику

6

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

holf
источник

5

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

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

Пусть поле и быть набор -many градусов- -мерное многочленов над -annihilating полином является любой (нетривиальным) й $\mathbb{F}$ $\vec{f} = (f_1, ..., f_k)\in\mathbb{F}[x_1, ..., x_n]$ $k$ $d$ $n$ $\mathbb{F}.$ $\vec{f}$ $A$ $A(f_1, ..., f_k) = 0.$

Решение легко: над любым полем, и для любых многочленов - если существует такое аннуляторное для , ((Посредством аргумента подсчета размеров.)) $k$ $(f_1, ..., f_k)$ $k \ge n+1,$ $A$ $(f_1, ..., f_k)$

Подсчет трудно: Определить аннулирующий-EVAL в качестве функциональной задачи оценки уничтожающего полинома на каком - то момент : Учитывая простой и множество , которые имеют минимальный унитарный уничтожающий $p,$ $(f_1, ..., f_k)\in\mathbb{Z}[x_1, ..., x_n]$ выход целое число $A(t_1, ..., t_k)\in\mathbb{Z}[t_1, ..., t_k],$ $A(0, ..., 0)\bmod{p}.$

ANNIHILATING-EVAL это -hard. Кроме того, аннулирующий многочлен не имеет небольшое представление схемы , если не разрушается. $\#\mathsf{P}$ $A(t_1, ..., t_k)$ $\mathsf{PH}$

Даниэль Апон
источник

1

m^{ϵ}

$m^{\hspace{.02 in}\epsilon}$

1

Все ресурсы, которые я могу найти, похоже, не согласны с определениями. Позвольте AE быть проблемой, которую обсуждает ваш ответ. (... продолжение)

1

(

$\big(\hspace{-0.07 in}$

^{0}

$^0$

)

$\hspace{-0.06 in}\big)$

^{| |}

$^{\hspace{-0.06 in}||\hspace{-0.06 in}}$

^{AE}

$^{\text{AE}}$

^{[\sqrt{n}]}

$^{\hspace{-0.05 in}[\sqrt{n}]}$

1

\subseteq

$\subseteq$

^{AE}

$^{\text{AE}}$

^{[\sqrt[3]{n}]}

$^{[\sqrt[3]{n}]}$

/

$\hspace{-0.06 in}\big/\hspace{-0.04 in}$ поли .

1

k

$k$

n

$n$

m a x d e g f_{i}

$max deg f_i$

{N P}^{# P}

$\mathsf{NP}^{\mathsf{\# P}}$

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

Ответы: