FNP (Komplexität) - FNP (complexity)

In Komplexitätstheorie , die Komplexitätsklasse FNP ist die Funktion Problem Verlängerung des Entscheidungsproblem Klasse NP . Der Name ist etwas falsch, da es sich technisch gesehen um eine Klasse von binären Beziehungen handelt , nicht um Funktionen, wie die folgende formale Definition erklärt:

Eine binäre Beziehung P ( x , y ), bei der y höchstens polynomiell länger als x ist , liegt genau dann in FNP vor, wenn es einen deterministischen Polynomzeitalgorithmus gibt, der bestimmen kann, ob P ( x , y ) sowohl für x als auch für y gilt .

Diese Definition beinhaltet keinen Nichtdeterminismus und ist analog zur Verifiziererdefinition von NP.

Es gibt eine NP-Sprache, die direkt jeder FNP-Beziehung entspricht und manchmal als Entscheidungsproblem bezeichnet wird, das durch diese FNP-Beziehung hervorgerufen wird oder dieser entspricht . Es ist die Sprache, die gebildet wird, indem alle x genommen werden, für die P ( x , y ) gilt, wenn etwas y gegeben ist ; Es kann jedoch mehr als eine FNP-Beziehung für ein bestimmtes Entscheidungsproblem geben.

Bei vielen Problemen in NP, einschließlich vieler NP-vollständiger Probleme, wird gefragt, ob ein bestimmtes Objekt vorhanden ist, z. B. eine zufriedenstellende Zuordnung, eine Diagrammfarbe oder eine Clique einer bestimmten Größe. Die FNP-Versionen dieser Probleme fragen nicht nur, ob es existiert, sondern auch, welchen Wert es hat, wenn dies der Fall ist. Dies bedeutet, dass die FNP-Version jedes NP-vollständigen Problems NP-schwer ist . Bellare und Goldwasser zeigten 1994 unter Verwendung einiger Standardannahmen, dass es Probleme in NP gibt, so dass ihre FNP-Versionen nicht selbstreduzierbar sind , was bedeutet, dass sie schwieriger sind als ihr entsprechendes Entscheidungsproblem.

Für jedes P ( x , y ) in FNP, das Suchproblem mit P verbunden ist ( x , y ) ist: Da x , finden eine y , so daß P ( x , y ) gilt, oder Zustand , dass kein solches y existiert. Das Suchproblem für jede Beziehung in FNP kann genau dann in Polynomzeit gelöst werden, wenn P = NP ist . Dieses Ergebnis wird normalerweise als "FP = FNP genau dann angegeben, wenn P = NP "; Damit diese Aussage wahr ist, muss FP und FNP neu definiert werden, damit die Mitglieder von FP und FNP keine Beziehungen sind, sondern Suchprobleme im Zusammenhang mit Beziehungen.

Ermäßigungen

Sei P 1 und P 2 zwei Probleme in FNP mit zugehörigen Verifizierungsalgorithmen A 1 , A 2 . Eine Reduktion P 1 und P 2 ist definiert als zwei effizient berechenbare Funktionen f und g , so dass

  • f ordnet die Eingänge x auf P 1 den Eingängen f ( x ) auf P 2 zu  ;
  • g ordnet die Ausgänge y auf P 2 den Ausgängen g (y) auf P 1 zu  ;
  • Für alle x und y : Wenn A 2 ( f ( x ), y ) true zurückgibt, gibt A 1 ( x , g ( y )) true zurück;
  • Für alle x : Wenn A 2 ( f ( x ), y ) false zurückgibt, gibt A 1 ( x , g ( y )) für alle y false zurück .

Verwandte Komplexitätsklassen

  • FP ist die Menge von binären Beziehungen, für die es einen Polynomzeitalgorithmus gibt, der bei gegebenem x etwas y findet, für das P ( x , y ) gilt. Die Beziehung zwischen FNP und FP ist analog zu der Beziehung zwischen NP und P.
  • TFNP ist eine Teilmenge von FNP: Es enthält die Beziehungen in FNP, für die für jedes x mindestens ein y existiert, für das P ( x , y ) gilt.

Verweise

Externe Links