Division durch zwei Funktionen in #P

Sei eine ganzzahlige Funktion, so dass in . Folgt daraus, dass in ? Gibt es Gründe zu der Annahme, dass dies wahrscheinlich nicht immer zutrifft? Gibt es Referenzen, über die ich Bescheid wissen sollte? $F$ $2F$ $\#P$ $F$ $\#P$

Etwas überraschend kam diese Situation (mit einer viel größeren Konstante) für eine Funktion für die ist ein altes offenes Problem. $F$ $F \in? \#P$

Anmerkung: Mir ist die Veröffentlichung M. Ogiwara, L. Hemachandra, Eine Komplexitätstheorie für mögliche Verschlusseigenschaften bekannt, in der ein verwandtes Division-durch-2-Problem untersucht wurde (siehe Thm 3.13). Ihr Problem ist jedoch anders, da sie die Aufteilung für alle Funktionen über den Etagenbetreiber definieren. Dies ermöglichte es ihnen, die Paritätsprobleme schnell zu reduzieren.

cc.complexity-theory complexity-classes counting-complexity Igor Pak
quelle

@Kaveh: Wenn

eine

Funktion und

eine Polyzeitfunktion ist , dann ist

, aber

nicht unbedingt (vermutlich) ). Zum Beispiel scheint es keinen Grund zu geben, warum alle nicht-negativen GapP-Funktionen in

, aber sie sind auf diese Weise auf

reduzierbar .

f (x)

$f(x)$

# P

$\#P$

g (y)

$g(y)$

f (g (y))

$f(g(y))$

# P

$\#P$

g (f (x))

$g(f(x))$

# P

$\#P$

# P

$\#P$

Emil Jeřábek unterstützt Monica

@JoshuaGrochow: Ja, es ist "Akzeptieren, wenn und nur wenn Sie beide 2F-Zeugen in lexikografischer Reihenfolge erraten haben".

@JoshuaGrochow Wenn Sie Division mit NO Boden Funktion tun dann

kollabiert auf die folgende Komplexitätsklasse, die ich nur über Satz 5.9 auf TCTC Buch definiert.

gibt es eine Polynom-Zeit Prädikat P und ein Polynom q , so dass für alle

P P

${\bf PP}$

U P P X = {L |

${\bf UPPX} = \{ L |$

x

$x$

1.

$\bf 1.$

x \notin L \Rightarrow | | {y |

$x \not \in L \Rightarrow ||\{y|$

Dann muss gezeigt werden, wo

in der Komplexitätshierarchie gehört. Es ist hoffentlich der Fall, dass

| y | \leq q (| x |) \land P (x, y)} | | < 1

$|y|\leq q(|x|) \wedge P(x,y)\}|| < 1$

2.

$\bf 2.$

x \in L \Rightarrow | | {y |

$x \in L \Rightarrow ||\{y|$

| y | \leq q (| x |) \land P (x, y)} | | \geq 1

$|y|\leq q(|x|) \wedge P(x,y)\}|| \geq 1$

}

$\}$

U P P X

${\bf UPPX}$

U P P X = P P

${\bf UPPX} = {\bf PP}$

Tayfun Pay

Wie schwer ist es zu sagen, ob eine Funktion in #PP immer gerade ist? Ich gehe davon aus, dass es unentscheidbar ist.

Peter Shor

@PeterShor: Das ist sicherlich nicht zu entscheiden. Man kann eine Maschine nehmen, die genau dann akzeptiert, wenn der Zählzeuge alle 1s und dieselbe Länge wie die Eingabe hat und M in genau [dieser Länge] Schritten anhält.

Antworten:

Ich versuche meine Intuition zu geben, warum ich denke, dass dies unwahrscheinlich ist. Nehmen Sie Ihr Lieblingsproblem in und wandeln Sie es in ein Problem in , z. B. kann unsere Funktion die Anzahl der Hamilton-Zyklen in einem eingegebenen 3-regulären Graphen sein, der eine bestimmte feste Flanke enthält. Aus dem Paritätsargument wissen wir, dass immer gerade ist, so dass Sie und ich keinen Grund sehe, warum in . $PPA$ $\sharp P$ $f$ $f$ $F:=f/2$ $F$ $\sharp P$

domotorp
quelle

Okay. Jetzt bin ich verwirrt. Hat

nicht drei Hamilton-Zyklen?

K_{4}

$K_4$

Peter Shor

Okay ... ich habe nachgesehen. Das Theorem besagt, dass jede Kante in einer geraden Anzahl von (ungerichteten) Hamilton-Zyklen in einem 3-regulären Graphen erscheint, nicht dass es eine gerade Anzahl von Hamilton-Zyklen insgesamt gibt. Also die richtige Zählproblem ist: ein Drei-regulären Graph und eine Kante gegeben

, lassen

die Anzahl der Hamilton - Zyklen in seine

, der durch gehen

. Ist

in #P?

e

$e$

f

$f$

G

$G$

e

$e$

F / 2

$F/2$

Peter Shor

In der Tat lustig, dass niemand früher bemerkt ... Ich habe es hinzugefügt.

Domotorp

Obwohl ich im Allgemeinen Ihrer Intuition zustimme, denke ich in diesem Fall, dass

tatsächlich in #P ist: Sei e = (v_1, v_2) die Kante in G. Sei u, w die Nachbarn von v_1, die nicht ' t v_2. Die folgende NP-Maschine hat f / 2-Akzeptanzpfade: Errate einen Hamilton-Zyklus, der das Kantenpaar (u, v_1) und (v_1, v_2) enthält. (Der Punkt ist, dass der Beweis der geraden Parität eine Diskrepanz zwischen solchen Ham-Zyklen und jenen erzeugt, die (w, v_1) und (v_1, v_2) enthalten.) Damit die Intuition funktioniert, benötigen Sie also etwas in PPA, das z Ein zählendes Argument, oder das vermeidet eine leichte Entführung ...

f / 2

$f/2$

Joshua Grochow

Die Tatsache ist nicht wahr. Zum Beispiel ist es einfach zu überprüfen, ob es für alle verbundenen 3-regulären Graphen auf 8 Eckpunkten fehlschlägt (siehe en.wikipedia.org/wiki/Table_of_simple_cubic_graphs#8_nodes für eine Liste), außer für den Würfel (der kantentransitiv ist). .

Emil Jeřábek unterstützt Monica