Division durch zwei Funktionen in #P

19

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?2 F # P F # PF2F#PF#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 ? # PFF?#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.

Igor Pak
quelle
3
@Kaveh: Wenn eine # P- Funktion und g ( y ) eine Polyzeitfunktion ist , dann ist f ( g ( y ) ) in # P , aber g ( f ( x ) ) nicht unbedingt (vermutlich) ). Zum Beispiel scheint es keinen Grund zu geben, warum alle nicht-negativen GapP-Funktionen in # P sein sollten , aber sie sind auf diese Weise auf # P reduzierbar . f(x)#Pg(y)f(g(y))#Pg(f(x))#P#P
Emil Jeřábek unterstützt Monica
1
@JoshuaGrochow: Ja, es ist "Akzeptieren, wenn und nur wenn Sie beide 2F-Zeugen in lexikografischer Reihenfolge erraten haben".
1
@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. U P P X = { L | gibt es eine Polynom-Zeit Prädikat P und ein Polynom q , so dass für alle x , 1 x L | | { y | | y | q ( | x | ) P ( x , y ) } |PPUPPX={L|x1. xL||{y| 2. x L | | { y | | y | q ( | x | ) P ( x , y ) } | | 1 } Dann muss gezeigt werden, wo U P P X in der Komplexitätshierarchie gehört. Es ist hoffentlich der Fall, dass U P P X = P P|y|q(|x|)P(x,y)}||<1 2. xL||{y| |y|q(|x|)P(x,y)}||1}UPPXUPPX=PP
Tayfun Pay
2
Wie schwer ist es zu sagen, ob eine Funktion in #PP immer gerade ist? Ich gehe davon aus, dass es unentscheidbar ist.
Peter Shor
2
@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:

4

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 P um , z. B. kann unsere Funktion f 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 f immer gerade ist, so dass Sie F : = f / 2 definieren können und ich keinen Grund sehe, warum F in P wäre .PPAPffF:=f/2FP

domotorp
quelle
2
Okay. Jetzt bin ich verwirrt. Hat nicht drei Hamilton-Zyklen? K4
Peter Shor
5
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 f die Anzahl der Hamilton - Zyklen in seine G , der durch gehen e . Ist F / 2 in #P? efGeF/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
Joshua Grochow
2
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