Beispiele für

16

Ich benötige eine Liste von vollständigen Sprachen. Im Complexity Zoo sind zwei solche Probleme aufgeführt :Σ2p

  • Mindestäquivalent DNF. Gibt es bei einer DNF-Formel F und einer Ganzzahl k eine DNF-Formel, die F mit k oder weniger Vorkommen von Literalen äquivalent ist?
  • Kürzester Implikant. Gibt es bei gegebener Formel F und Integer k eine Konjunktion von k oder weniger Literalen, die F impliziert?

Ein weiteres grundlegendes vollständiges Problem:Σ2p

  • & phiv; & phiv; = uvΣichSAT . Bei einer quantifizierten Booleschen Formel der Form ist gültig?φφφ=uvϕ(u,v)φ

Ich bin jedoch hoffentlich auf der Suche nach einem Problem, bei dem Grafiken verwendet werden (z. B. ein Clique-Problem).

gdiazc
quelle
10
Schauen Sie sich dieses Kompendium an: ovid.cs.depaul.edu/documents/phcom.pdf
Huck Bennett
Das sieht sehr nützlich aus. Danke vielmals!
Gdiazc
5
@HuckBennett: gute umfrage! Warum machst du daraus keine Antwort?
Marzio De Biasi

Antworten:

8

Ein eher aktuelles Ergebnis, das nicht in der Arbeit von Schaefer und Umans enthalten ist, ist die 2-CLIQUE COLORING OF PERFECT GRAPHS .

Σ2p

Marzio De Biasi
quelle
7

Entscheidung über das Vorhandensein einer "evolutionär stabilen Strategie" in einem normalen Spiel. Siehe http://www.cs.duke.edu/~conitzer/ess.pdf .

Das Setup ist ein symmetrisches 2-Spieler-Spiel. Eine evolutionär stabile Strategie ist eine (randomisierte) Strategie, die (a) ein symmetrisches Nash-Gleichgewicht ist und (b) keine guten "symmetrischen Abweichungen" aufweist: In diesem Gleichgewicht kann ein Spieler von einer Strategie abweichen und den gleichen Nutzen aufrechterhalten. dann würde sich der andere Spieler strikt verschlechtern, um dann ebenfalls von dieser Strategie abzuweichen.

usul
quelle