Łatwe problemy z trudnymi do zliczenia wersjami

20

Wikipedia podaje przykłady problemów, w których liczenie wersji jest trudne, natomiast wersja decyzyjna jest łatwa. Niektóre z nich liczą doskonałe dopasowania, licząc liczbę rozwiązań SAT i liczbę sortowań topologicznych. $2$

Czy są jeszcze jakieś inne ważne klasy (powiedzmy przykłady z sieci, drzew, teorii liczb i tak dalej)? Czy istnieje kompendium takich problemów?

Istnieje wiele rodzajów problemów w które mają wersje z zliczaniem. $P$ $\#P$

Czy istnieje wersja z naturalnym problemem w , który jest bardziej lub całkowicie zrozumiałym prostszy niż ogólna dwustronnego idealnego dopasowania (proszę podać szczegóły na temat dlaczego prostsze, takie jak bycie provably w najniższych klas -hierarchy i tak dalej), w innej strefie (takich jak teoria liczb, sieci) lub przynajmniej dla konkretnych prostych wykresów dwustronnych, których wersja zliczania jest ? $P$ $NC$ $\#P$

Docenione zostaną przykłady z sieci, polytopów, liczenia punktów, teorii liczb .

reference-request counting-complexity nt.number-theory permanent decision-trees T ....
źródło

1

Przypuszczalnie chcesz naturalnych problemów, ponieważ [przez redukcję z #SAT, problemy, które # P trudny w [redukcjach, które mnożą odpowiedź przez liczbę niezerową] mają problemy decyzyjne trudne HP] i [przez funkcję tożsamości, {x: x to 1+ (liczba_zmiennych__ ( )) lub [zero, po którym następuje zadowalające przypisanie do ]} jest # P-twarde przy następnym najbardziej ścisłym typie redukcji, ale jego wersja decyzyjna jest banalna].

ϕ

$\phi$

ϕ

$\phi$

@RickyDemer twoje pisanie jest zwięzłe. Tak, chcę naturalnych problemów.

T ....

Czy naprawdę nie rozumiemy do końca idealnych dopasowań w grafach dwustronnych? Istnieje również algorytm RNC2 dla problemu.

Sasho Nikolov

1

Tak, my nie. Nie mamy deterministycznego algorytmu .

N C

$NC$

T ....

8

Oto naprawdę doskonały przykład (mogę być stronniczy).

Biorąc pod uwagę częściowo uporządkowany zestaw:
a) czy ma rozszerzenie liniowe (tj. Całkowite zamówienie zgodne z porządkiem częściowym)? Trywialne: Wszystkie zestawy mają co najmniej jedno rozszerzenie liniowe
b) Ile ma? # P-complete, aby to ustalić (Brightwell i Winkler, Counting Linear Extensions , Order, 1991)
c) Czy możemy je wszystkie szybko wygenerować? Tak, w stałym zamortyzowanym czasie (Pruesse i Ruskey, Szybkie generowanie rozszerzeń liniowych , SIAM J Comp 1994)

Gara Pruesse
źródło

3

+1: Zgadzam się, że to naprawdę doskonały przykład (myślałem o opublikowaniu go sam, a potem zobaczyłem tę odpowiedź). Również, żeby ktoś powiedział: „Co o podejmowaniu decyzji, czy istnieje co najmniej jeden inny przedłużenie liniowe”, że problemem jest również całkowicie trywialny: całkowity porządek ma 1 rozszerzenie, wszystkie inne Posets mieć> 1. i wykrywania dokładnie 2 rozszerzenie jest również łatwa (to zdarza się, jeśli jest dokładnie jedna para nieporównywalnych elementów). W rzeczywistości istnieje pełna klasyfikacja poetów z maksymalnie 7 rozszerzeniami liniowymi (patrz Hanamura-Iwata, IPL 2011 ).

Joshua Grochow

To naprawdę dobry przykład. Istnieje o wiele „prostszy” problem, jednak posiadający ten sam rodzaj właściwości (prostszy w tym sensie, że właściwości te są prawie trywialne do udowodnienia). Zliczanie liczby zadowalających przypisań DNF: a) każdy niepusty DNF jest zadowalający b) zliczanie jest zakończone # P (redukcja do #SAT) c) wyliczenie można wykonać z opóźnieniem wielomianowym (być może stałym czasem zamortyzowanym, mieć pomyśleć o tym)

holf

Byłbym bardzo zainteresowany wiedzieć, czy DNF spełniające zadania można wygenerować w stałym zamortyzowanym czasie (CAT). W tym czasie i mój artykuł z Frankiem w 1994 r. Rozszerzenia liniowe były pierwszym „naturalnie zdefiniowanym” obiektem, dla którego zliczanie było trudne, a generowanie było tak szybkie, jak to możliwe, po amortyzacji (tj. CAT). Rozwiązania DNF również wydają się być prawdopodobnym kandydatem do tego. Czy ktoś ma referencje?

Gara Pruesse

@GaraPruesse Nie mam na to referencji. W przypadku monotonu-DNF jest to równoważne z wyliczeniem uderzenia zestawu hipergraphów, a niektóre techniki poprawy opóźnienia przedstawiono w „Skutecznych algorytmach dualizacji hipergraphów na dużą skalę” Keisuke Murakami i Takeaki Uno dl.acm.org/citation.cfm? id = 2611867 . Powinniśmy sprawdzić, czy daje CAT. W przypadku DNF moja intuicja jest taka, że jeśli istnieje mała klauzula, to masz już wystarczająco dużo rozwiązań do brutalnego wymuszania. W przeciwnym razie masz tylko duże klauzule, które z większym prawdopodobieństwem kolidują i które mogą być wykorzystane do zaprojektowania algorytmu CAT.

holf

17

Ciekawym przykładem teorii liczb jest wyrażenie dodatniej liczby całkowitej jako sumy czterech kwadratów. Można to zrobić stosunkowo łatwo w losowym czasie wielomianowym (patrz mój artykuł z Rabinem z 1986 r. Na stronie https://dx.doi.org/10.1002%2Fcpa.3160390713 ), a jeśli dobrze pamiętam, teraz jest nawet deterministyczny czas wielomianowy rozwiązanie. Ale policzenie liczby takich reprezentacji pozwoliłoby obliczyć funkcję sumy dzielników , która jest losowym wielomianowym czasem równoważnym faktorowaniu . Problem liczenia jest więc prawdopodobnie trudny. $\sigma(n)$ $n$

Jeffrey Shallit
źródło

„Więc problem liczenia jest prawdopodobnie trudny” masz na myśli prawdopodobnie trudny? masz dowody?

# P

$\#P$

T ....

Przez „prawdopodobnie trudne” rozumiem, że jest to losowy czas wielomianowy równoważny rozkładowi na liczby całkowite.

Jeffrey Shallit,

3

Mówiąc wprost: problem nie jest trudny do #P (chyba że rozpęta się piekło).

Emil Jeřábek wspiera Monikę

@JeffreyShallit Czy istnieje przykład ?

# P

$\#P$

T ....

Myślę, że następujący przykład jest jeszcze prostszy: „Czy ma właściwy dzielnik większy niż ” vs. „Ile prawidłowych dzielników większych niż ma

?”. Wersja decyzyjna jest równoważna „

jest złożona”, więc jest w

, ale wersja zliczająca nie wygląda na łatwiejszą niż faktoring.

n

$n$

1

$1$

1

$1$

n

$n$

n

$n$

P

$P$

Dan Brumleve

17

Bardzo ładnym i prostym przykładem z teorii grafów jest zliczanie obwodów eularskich na niekierowanym wykresie.

Wersja decyzyjna jest łatwa (... a problem Siedmiu Mostów Królewskich nie ma rozwiązania :-)

Wersja liczenie jest # P-hard: Graham R. Brightwell Piotr Winkler: Liczenie Eulera Circuits jest # P-Complete . ALENEX / ANALCO 2005: 259–262

Marzio De Biasi
źródło

Artykuł ten „Naszym podejściem jest wykazanie, że przy pomocy wyroczni, która liczy obwody Eulera, maszyna Turinga może… i” Chcemy obliczyć liczbę

orientacji Eulera

„Podział akapitu” Budujemy dla dowolnej nieparzystej liczby pierwszej

, wykres

którego liczba kul jest równa

modulo

. ”I„ Powtarzamy ten proces dla każdej liczby pierwszej p pomiędzy

i

, gdzie

, i… ”z pewnością sugerują, że dają tylko równoległe zmniejszenie, a nie nawet

N

$N$

G

$G$

p

$p$

G_{p}

$G_p$

N

$N$

p

$p$

m

$m$

m^{2}

$m^2$

| E | = m

$|E| = m$

redukcja zapytania.

m^{ϵ}

$m^{\epsilon}$

@MarzioDeBiasi jest decyzja obwodu Eulera w NC?

T ....

1

@AJ. Wystarczy obliczyć parzystość stopnia każdego węzła i sprawdzić, czy wszystkie są równe. Zdaje się zdecydowanie być w NC.

Sasho Nikolov

4

Możesz przyjąć parzystość

bitów za pomocą formuły rozmiaru

lub liniowego obwodu wielkości głębokości

. Więc jeśli twój wykres jest podany jako macierz przylegania, oblicz parzystość każdego wiersza, zaneguj i weź AND. I z

bitów może być wykonana z liniowego wzoru rozmiaru, tak, ogólnie rzecz biorąc, można uzyskać

Wielkość logiczny wzór i

Wielkość logiczny obwód głębokości

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)$ (w stosunku do AND-OR). Tak więc problem jest w rzeczywistości w

.

{N C}^{1}

$\mathsf{NC}^1$

Sasho Nikolov

2

W rzeczywistości problem dotyczy

.

{A C}^{0} [2]

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

Emil Jeřábek wspiera Monikę

6

Jeśli chodzi o twoje drugie pytanie, problemy takie jak Monotone-2-SAT (decydujące o spełnianiu formuły CNF posiadającej co najwyżej 2 literały pozytywne według klauzul) są całkowicie trywialne (musisz tylko sprawdzić, czy twoja formuła jest pusta, czy nie), ale problem liczenia to # P-trudny. Nawet przybliżenie liczby spełniających zadania takich formuł jest trudne (patrz O twardości przybliżonego rozumowania, Dan Roth, Artificial Intelligence, 1996).

holf
źródło

5

From [Kayal, CCC 2009] : Jawna ocena wielomianów anihilujących w pewnym momencie

Ze streszczenia: `` Jest to jedyny naturalny problem obliczeniowy, w którym określenie istnienia obiektu (w naszym przypadku wielomian anihilujący) może być wykonane skutecznie, ale rzeczywiste obliczenie obiektu jest trudne. ''

Niech będzie pola i jest zestaw to wiele stopnio -variate wielomianów ponad -annihilating Wielomian może być dowolny (nietrywialnym) st $\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.$

Decyzja jest łatwe: Przez dowolne pole, a za wielomianów - jeśli jest taka anihilujący do . ((Za pomocą argumentu zliczającego wymiary.)) $k$ $(f_1, ..., f_k)$ $k \ge n+1,$ $A$ $(f_1, ..., f_k)$

Zliczanie jest trudne: Określanie unicestwiania-EVAL jako funkcjonalny problemu oceniając wielomianu niwecząc w pewnym momencie : względu głównym a zestaw , które mają minimalny monic unicestwiania $p,$ $(f_1, ..., f_k)\in\mathbb{Z}[x_1, ..., x_n]$ wyjście całkowitą $A(t_1, ..., t_k)\in\mathbb{Z}[t_1, ..., t_k],$ $A(0, ..., 0)\bmod{p}.$

ANNIHILATING-EVAL to twardy. Co więcej, anihilujący wielomian nie ma reprezentacji małego obwodu, chyba że zawali. $\#\mathsf{P}$ $A(t_1, ..., t_k)$ $\mathsf{PH}$

Daniel Apon
źródło

1

Podobnie jak w przypadku Marzio, dowód tego twierdzenia w artykule 15.2 wydaje się wskazywać, że wykazują twardość tylko przy równoległych redukcjach, a nie nawet przy ograniczeniach zapytań .

m^{ϵ}

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

1

Wszystkie zasoby, które mogę znaleźć, wydają się nie zgadzać w sprawie definicji. Niech AE będzie problemem, który omawia twoja odpowiedź. (... ciąg dalszy)

1

(ciąg dalszy ...) Ja nie próbowali wypracować bardziej właśnie klasy base one wykorzystać, ale byłoby bardzo zaskoczony, jeśli ich wynik był lepszy niż #P = DLOGTIME-uniform TC

(

$\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}]}$ . (... ciąg dalszy)

1

(ciąg dalszy ...) O ile widzę, to jednak nie wynika z tego LWPP

MP

\subseteq

$\subseteq$

^{AE}

$^{\text{AE}}$

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

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

/

$\hspace{-0.06 in}\big/\hspace{-0.04 in}$ poli .

1

Mówiąc bardziej ogólnie, tj. Dla arbitralnej

(nawet mniejszej niż

), decyzja jest łatwa ze względu na jakobskie kryterium, prawda? (Należy zauważyć, że kryterium jakobianowe działa tylko w charakterystyce>

; w małej dodatniej charakterystyce istnieje zmodyfikowane kryterium jakobskie z powodu Mittmana-Saxeny-Scheiblechnera , ale najwyraźniej prowadzi to tylko do

algorytm decyzji ...)

k

$k$

n

$n$

m a x d e g f_{i}

$max deg f_i$

{N P}^{# P}

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

Joshua Grochow

Łatwe problemy z trudnymi do zliczenia wersjami

Odpowiedzi: