Einfache Probleme mit hartzählenden Versionen

20

Wikipedia bietet Beispiele für Probleme, bei denen die Zählversion schwierig ist, während die Entscheidungsversion einfach ist. Einige von diesen zählen perfekte Übereinstimmungen, zählen die Anzahl der Lösungen zu SAT und die Anzahl der topologischen Sortierungen. $2$

Gibt es noch andere wichtige Klassen (Beispiele in Gittern, Bäumen, Zahlentheorie usw.)? Gibt es ein Kompendium solcher Probleme?

Es gibt viele Arten von Problemen in , die -harte Zählversionen haben. $P$ $\#P$

Gibt es eine Version eines natürlichen Problems in , die vollständiger verstanden oder einfacher ist als die allgemeine zweiteilige perfekte Übereinstimmung (bitte erläutern Sie, warum dies einfacher ist, beispielsweise nachweislich in den untersten Klassen der Hierarchie usw.) in einem anderen Bereich (wie Zahlentheorie, Gitter) oder zumindest für bestimmte einfache zweigliedrige Graphen, deren Zählversion -hart ist? $P$ $NC$ $\#P$

Beispiele aus Gittern, Polytopen, Punktzählung, Zahlentheorie werden geschätzt .

reference-request counting-complexity nt.number-theory permanent decision-trees T ....
quelle

1

Vermutlich möchten Sie natürliche Probleme, da [durch Reduktion von #SAT, Probleme, die # P-hart sind unter [Reduktionen, die mit einer Zahl ungleich Null multipliziert werden], HP-harte Entscheidungsprobleme haben] und [durch die Identitätsfunktion, {x: x ist 1+ (Anzahl_von_Variablen_ ( )) Einsen oder [eine Null, gefolgt von einer befriedigenden Zuordnung zu ]} ist # P-schwer unter der nächst strengeren Art der Reduktion, aber ihre Entscheidungsversion ist trivial].

ϕ

$\phi$

ϕ

$\phi$

@ RickyDemer Ihr Schreiben ist prägnant. Ja, ich möchte natürliche Probleme.

T ...

Verstehen wir perfekte Übereinstimmungen in zweigeteilten Diagrammen wirklich nicht vollständig? Es gibt auch einen RNC2-Algorithmus für das Problem.

Sasho Nikolov

1

Ja tun wir nicht Wir haben keine determinis

- Algorithmus.

N C

$NC$

T ....

8

Ist hier ein wirklich ausgezeichnetes Beispiel (ich kann voreingenommen sein).

Bei einer teilweise geordneten Menge:
a) Hat sie eine lineare Ausdehnung (dh eine Gesamtreihenfolge, die mit der Teilreihenfolge kompatibel ist)? Trivial: Alle Posets haben mindestens eine lineare Erweiterung.
B) Wie viele hat es? # P-vollständig, um dies zu bestimmen (Brightwell und Winkler, Counting Linear Extensions , Order, 1991)
c) Können wir sie alle schnell generieren? Ja, in konstant abgeschriebener Zeit (Pruesse und Ruskey, Generating Linear Extensions Fast , SIAM J Comp 1994)

Gara Pruesse
quelle

3

+1: Ich stimme zu, dass es ein wirklich hervorragendes Beispiel ist (ich habe darüber nachgedacht, es selbst zu posten und habe dann diese Antwort gesehen). Auch wenn jemand sagt "Was ist mit der Entscheidung, ob es mindestens eine andere lineare Erweiterung gibt", ist dieses Problem völlig trivial: Eine Gesamtbestellung hat 1 Erweiterung, alle anderen Posets haben> 1 passiert, wenn es genau ein Paar unvergleichbarer Elemente gibt). Tatsächlich gibt es eine vollständige Klassifizierung von Posets mit bis zu 7 linearen Extensionen (siehe Hanamura-Iwata, IPL 2011 ).

Joshua Grochow

Dies ist in der Tat ein schönes Beispiel. Es gibt ein viel "einfacheres" Problem, das jedoch die gleichen Eigenschaften aufweist (einfacher in dem Sinne, dass diese Eigenschaften fast trivial zu beweisen sind). Zählen der Anzahl erfüllender Zuordnungen einer DNF: a) Jede nicht leere DNF ist erfüllbar. B) Die Zählung ist # P-vollständig (Reduktion auf #SAT). C) Die Zählung kann mit polynomieller Verzögerung erfolgen (eine möglicherweise konstante amortisierte Zeit) darüber nachzudenken)

holf

Es würde mich sehr interessieren, ob DNF-zufriedenstellende Zuordnungen in einer konstanten Amortisationszeit (CAT) generiert werden können. Zu der Zeit und meiner Arbeit mit Frank im Jahr 1994 waren lineare Erweiterungen das erste "natürlich definierte" Objekt, für das die Zählung schwierig war und die Erzeugung so schnell wie möglich war, wenn sie amortisiert wurde (dh CAT). DNF-Lösungen scheinen dafür ebenfalls in Frage zu kommen. Hat jemand eine Referenz?

Gara Pruesse

@GaraPruesse Ich habe keine Referenzen dafür. Für monotone-DNF entspricht dies der Aufzählung der Treffermenge von Hypergraphen, und einige Techniken zur Verbesserung der Verzögerung werden in "Effiziente Algorithmen zur Dualisierung von Hypergraphen im großen Maßstab" von Keisuke Murakami und Takeaki Uno dl.acm.org/citation.cfm? id = 2611867 . Wir sollten prüfen, ob es CAT gibt. Für DNF ist meine Intuition, dass Sie, wenn es eine kleine Klausel gibt, bereits genug Lösungen für Brute Forcing haben. Andernfalls haben Sie nur große Klauseln, die dann eher in Konflikt geraten und zum Entwerfen eines CAT-Algorithmus verwendet werden können.

Freitag,

17

Ein interessantes Beispiel aus der Zahlentheorie ist das Ausdrücken einer positiven ganzen Zahl als Summe von vier Quadraten. Dies kann relativ einfach in zufälliger Polynomzeit geschehen (siehe meinen Artikel von 1986 mit Rabin unter https://dx.doi.org/10.1002%2Fcpa.3160390713 ), und wenn ich mich recht erinnere, gibt es jetzt sogar eine deterministische Polynomzeit Lösung. Wenn Sie jedoch die Anzahl solcher Darstellungen zählen, können Sie die Teilersummenfunktion berechnen , die eine zufällige Polynomzeit ist, die der Faktorisierung von . Das Zählproblem ist also wahrscheinlich schwierig. $\sigma(n)$ $n$

Jeffrey Shallit
quelle

"Also ist das Zählproblem wahrscheinlich schwer" meinst du wahrscheinlich

schwer? Hast du Beweise?

# P

$\#P$

T ....

Mit "wahrscheinlich schwer" meine ich, dass es eine zufällige Polynomzeit ist, die der ganzzahligen Faktorisierung entspricht.

Jeffrey Shallit

3

Um es deutlich zu machen: Das Problem ist nicht # P-schwer (es sei denn, die Hölle bricht los).

Emil Jeřábek unterstützt Monica

@JeffreyShallit Gibt es ein

Beispiel?

# P

$\#P$

T ....

Ich denke, das Folgende ist ein noch einfacheres Beispiel: "Hat

einen richtigen Teiler größer als

" vs. "Wie viele richtige Teiler größer als

hat

?". Die Entscheidungsversion ist äquivalent zu "

ist zusammengesetzt", also ist es in

, aber die Zählversion sieht nicht einfacher aus als Factoring.

n

$n$

1

$1$

1

$1$

n

$n$

n

$n$

P

$P$

Dan Brumleve

17

Ein sehr schönes und einfaches Beispiel aus der Graphentheorie ist das Zählen der Anzahl von Eularschen Kreisen in einem ungerichteten Graphen.

Die Entscheidungsversion ist einfach (... und das Problem der Sieben Brücken von Königsberg hat keine Lösung :-)

Die Zählversion ist # P-schwer: Graham R. Brightwell, Peter Winkler: Das Zählen von Eulerschaltungen ist # P-vollständig . ALENEX / ANALCO 2005: 259 & ndash; 262

Marzio De Biasi
quelle

"Unser Ansatz ist es, zu zeigen, dass eine Turingmaschine mit Hilfe eines Orakels, das Eulerschaltungen zählt, ... und" Wir wollen die Anzahl

der Eulerschen Orientierungen von berechnen

"Absatzumbruch" Wir konstruieren für jede ungerade Primzahl

einen Graphen

dessen Anzahl der Kugeln

modulo

. "Und" Wir wiederholen diesen Vorgang für jede Primzahl p dazwischen

und

, wobei

, und ... "deuten sicherlich darauf hin, dass sie nur eine parallele Reduktion geben und nicht einmal ein

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-Reduktion.

m^{ϵ}

$m^{\epsilon}$

@MarzioDeBiasi ist Euler'sche Kreisentscheidung in NC?

T ....

1

@AJ. Sie müssen nur die Parität des Grades jedes Knotens berechnen und prüfen, ob alle gerade sind. Scheint definitiv in NC zu sein.

Sasho Nikolov

4

Sie können die Parität der nehmen

Bits unter Verwendung eines

eine Größe Formel oder eine lineare Größe der Schaltung Tiefe

. Wenn Ihr Diagramm also als Adjazenzmatrix angegeben ist, berechnen Sie die Parität jeder Zeile, negieren Sie und führen Sie ein UND aus. AND von

Bits kann mit einer linearen Größenformel durchgeführt werden, sodass Sie insgesamt eine Boolesche Formel der Größe

und eine Boolesche Schaltung der Größe

der Tiefe

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)$ (über die UND-ODER-Basis). Das Problem liegt also in

.

{N C}^{1}

$\mathsf{NC}^1$

Sasho Nikolov

2

Tatsächlich liegt das Problem in

.

{A C}^{0} [2]

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

Emil Jeřábek unterstützt Monica

6

In Bezug auf Ihre zweite Frage sind Probleme wie Monotone-2-SAT (Entscheidung über die Erfüllbarkeit einer CNF-Formel mit höchstens 2 positiven Literalen durch Klausel) völlig trivial (Sie müssen nur prüfen, ob Ihre Formel leer ist oder nicht) Das Zählproblem ist # P-schwer. Es ist schwierig, die Anzahl der erfüllenden Aufgaben einer solchen Formel auch nur annähernd zu bestimmen (siehe Dan Roth, Artificial Intelligence, 1996).

holf
quelle

5

Aus [Kayal, CCC 2009] : Irgendwann explizit vernichtende Polynome auswerten

Aus der Zusammenfassung: "Dies ist das einzige natürliche Rechenproblem, bei dem die Bestimmung der Existenz eines Objekts (in unserem Fall das vernichtende Polynom) effizient durchgeführt werden kann, die tatsächliche Berechnung des Objekts jedoch nachweislich schwierig ist."

Lassen ein Feld und seine ein Satz sein -many Grad- -variate Polynome über Ein -annihilating Polynoms ist eine beliebige (nicht-triviale) 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.$

Entscheidung ist einfach: über jedes Feld und für alle Polynome - wenn gibt es eine solche vernichtende für . ((Über ein Argument zur Dimensionszählung.)) $k$ $(f_1, ..., f_k)$ $k \ge n+1,$ $A$ $(f_1, ..., f_k)$

Zählen sind hart: Definieren vernichtenden-EVAL als Funktionsproblem auf einem gewissen Punkt eine vernichtende Polynom Auswertung : Bei einer Primzahl und eine Gruppe , die eine minimale monic vernichtenden $p,$ $(f_1, ..., f_k)\in\mathbb{Z}[x_1, ..., x_n]$ Ausgang der ganze Zahl $A(t_1, ..., t_k)\in\mathbb{Z}[t_1, ..., t_k],$ $A(0, ..., 0)\bmod{p}.$

ANNIHILATING-EVAL ist -hard. Darüber hinaus ist die vernichtende Polynom nicht über eine kleine Schaltungsdarstellung , es sei denn zusammenbricht. $\#\mathsf{P}$ $A(t_1, ..., t_k)$ $\mathsf{PH}$

Daniel Apon
quelle

1

Wie bei Marzios Beispiel scheint der Nachweis von Anspruch 15.2 in diesem Papier darauf hinzudeuten, dass sie nur unter parallelen Reduktionen und nicht sogar unter

Härte zeigen

-Abfragekürzungen.

m^{ϵ}

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

1

Die Ressourcen, die ich finden kann, scheinen in den Definitionen nicht übereinzustimmen. Lassen Sie AE das Problem sein, das Ihre Antwort bespricht. (... Fortsetzung)

1

(Fortsetzung folgt ...) Ich habe versucht , nicht mehr genau , was Basis-Klasse , die sie verwenden , um herauszufinden, würde aber sehr überrascht sein , wenn ihr Ergebnis ist besser als #P =

(

$\big(\hspace{-0.07 in}$ DLOGTIME-Uniform TC

^{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}]}$ . (... Fortsetzung)

1

(Fortsetzung folgt ...) Soweit ich sehen kann, ist es nicht nicht folgen , dass LWPP

MP

\subseteq

$\subseteq$

^{AE}

$^{\text{AE}}$

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

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

/

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

1

Im Allgemeinen, dh für willkürliches

(sogar weniger als

), ist die Entscheidung aufgrund des Jacobi-Kriteriums einfach, oder? (Beachten Sie, dass das Jacobi-Kriterium nur in Merkmal>

funktioniert ; in klein positivem Merkmal gibt es ein modifiziertes Jacobi-Kriterium aufgrund von Mittman-Saxena-Scheiblechner , das aber anscheinend nur zu einem

Algorithmus für die Entscheidung ...)

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

Einfache Probleme mit hartzählenden Versionen

Antworten: