Wann impliziert "X ist NP-vollständig" "#X ist # P-vollständig"?

Sei ein (Entscheidungs-) Problem in NP und sei # dessen Zählversion. $X$ $X$

Unter welchen Bedingungen ist bekannt, dass "X NP-vollständig ist" "#X ist # P-vollständig"? $\implies$

Natürlich ist die Existenz einer sparsamen Reduktion eine solche Bedingung, aber dies ist offensichtlich und die einzige Bedingung, die mir bekannt ist. Das ultimative Ziel wäre zu zeigen, dass keine Bedingung erforderlich ist.

Formal sollte man mit dem Zählproblem # das durch eine Funktion definiert ist, und dann das Entscheidungsproblem für eine Eingabezeichenfolge als ? $X$ $f : \{0,1\}^* \to \mathbb{N}$ $X$ $s$ $f(s) \ne 0$

cc.complexity-theory np-hardness counting-complexity Tyson Williams
quelle

Suchen Sie etwas mehr als "X ist NP-vollständig unter sparsamen Kürzungen"?

Joshua Grochow

@usul: Nein. Wenn wir die Annahme fallen lassen, dass X NP-vollständig ist, dann ist die bipartite Übereinstimmung in P (also definitiv nicht sparsam NP-vollständig, wenn vorausgesetzt wird ), aber die Zählversion ist # P-vollständig. Wenn wir jedoch wirklich X NP-vollständig wollen, dann kenne ich ein Problem X nicht so aus dem Kopf, dass: 1) X NP-vollständig ist, 2) X bei sparsamen Reduktionen nicht NP-vollständig ist, und 3) #X ist # P-vollständig. Aber ich habe nicht wirklich darüber nachgedacht.

P \neq N P

$P \neq NP$

Joshua Grochow

Aber gibt es ein Problem, das dies negiert? dh X ist NP-vollständig und #X ist nicht # P-vollständig?

Suresh Venkat

@YoshioOkamoto: Das beweist, dass #X ∈ #P X ∈ NP impliziert . Es ist in die falsche Richtung und verfehlt das Problem der Vollständigkeit. Im Wesentlichen geht es darum, welche zusätzlichen Anforderungen erforderlich sind, damit eine 1: 1-Reduktion für Entscheidungsprobleme in NP (für willkürliche Entscheidungsprobleme oder für ein NP- vollständiges Problem) das Vorhandensein von a zur Folge hat effiziente Reduktion Zählen für Probleme in #P (für beliebige Zählen Probleme, oder von einem #P -komplette Problem).

Niel de Beaudrap

@ColinMcQuillan Es könnte umgekehrt angegeben werden. Beginnen Sie mit einem Zählproblem und definieren Sie ein Entscheidungsproblem, indem Sie fragen, ob die Ausgabe ungleich Null ist.

Tyson Williams

Wann impliziert "X ist NP-vollständig" "#X ist # P-vollständig"?

Antworten: