Funktionsproblem - Function problem

In der Berechnungskomplexitätstheorie ist ein Funktionsproblem ein Rechenproblem, bei dem für jede Eingabe eine einzelne Ausgabe (einer Gesamtfunktion ) erwartet wird, die Ausgabe jedoch komplexer ist als die eines Entscheidungsproblems . Bei Funktionsproblemen ist die Ausgabe nicht einfach 'ja' oder 'nein'.

Formale Definition

Ein funktionales Problem ist definiert als Relation über Strings eines beliebigen Alphabets : ${\displaystyle P}$${\displaystyle R}$ ${\displaystyle \Sigma}$

${\displaystyle R\subseteq\Sigma^{*}\times \Sigma^{*}}$

Ein Algorithmus löst , wenn für jede Eingabe , für die es ein Befriedigendes gibt , der Algorithmus eine solche erzeugt . ${\displaystyle P}$${\displaystyle x}$${\displaystyle y}$${\displaystyle (x,y)\in R}$${\displaystyle y}$

Beispiele

Ein bekanntes Funktionsproblem ist das Functional Boolean Satisfiability Problem, kurz FSAT . Das Problem, das eng mit dem SAT- Entscheidungsproblem verwandt ist, lässt sich wie folgt formulieren:

Suchen Sie bei einer booleschen Formel mit Variablen eine Zuweisung , die auswertet oder entscheidet, dass eine solche Zuweisung nicht existiert.${\displaystyle\varphi}$${\displaystyle x_{1},\ldots,x_{n}}$${\displaystyle x_{i}\rightarrow \{{\text{TRUE}},{\text{FALSE}}\}}$${\displaystyle\varphi}$${\displaystyle {\text{TRUE}}}$

In diesem Fall wird die Beziehung durch Tupel von geeignet codierten booleschen Formeln und erfüllenden Zuweisungen gegeben. Während ein SAT-Algorithmus, der mit einer Formel gefüttert wird , nur "unerfüllbar" oder "erfüllbar" zurückgeben muss, muss ein FSAT-Algorithmus im letzteren Fall eine zufriedenstellende Zuweisung zurückgeben. ${\displaystyle R}$${\displaystyle\varphi}$

Andere bemerkenswerte Beispiele sind das Problem des Handlungsreisenden , das nach der Route des Verkäufers fragt, und das Problem der Ganzzahlfaktorisierung , das nach der Liste der Faktoren fragt.

Beziehung zu anderen Komplexitätsklassen

Betrachten Sie ein beliebiges Entscheidungsproblem in der Klasse NP . Nach der Definition von NP hat jede Probleminstanz , die mit 'ja' beantwortet wird, ein Zertifikat mit polynomialer Größe, das als Beweis für die 'ja'-Antwort dient. Somit bildet die Menge dieser Tupel eine Relation, die das Funktionsproblem "gegeben in , finde ein Zertifikat für " darstellt. Dieses Funktionsproblem wird als Funktionsvariante von bezeichnet ; es gehört zur Klasse FNP . ${\displaystyle L}$${\displaystyle x}$${\displaystyle y}$${\displaystyle (x,y)}$${\displaystyle x}$${\displaystyle L}$${\displaystyle y}$${\displaystyle x}$${\displaystyle L}$

FNP kann insofern als das Funktionsklassenanalogon von NP betrachtet werden , als Lösungen von FNP- Problemen effizient (dh in polynomieller Zeit in Bezug auf die Länge der Eingabe) verifiziert , aber nicht unbedingt effizient gefunden werden können . Im Gegensatz dazu besteht die Klasse FP , die man sich als das Funktionsklassenanalogon von P vorstellen kann, aus Funktionsproblemen, deren Lösungen in polynomieller Zeit gefunden werden können.

Selbstreduzierbarkeit

Beachten Sie, dass das oben eingeführte Problem FSAT nur mit polynomiell vielen Aufrufen eines Unterprogramms gelöst werden kann, das das SAT- Problem entscheidet: Ein Algorithmus kann zunächst fragen, ob die Formel erfüllbar ist. Danach kann der Algorithmus die Variable auf TRUE setzen und erneut fragen. Wenn die resultierende Formel immer noch erfüllbar ist, bleibt der Algorithmus auf TRUE fixiert und fixiert weiterhin , ansonsten entscheidet er, dass FALSE sein muss und fährt fort. Somit ist FSAT in polynomieller Zeit unter Verwendung eines Orakel- Entscheidungs- SAT lösbar . Im Allgemeinen ist ein Problem in NP heißt selbst reduzierbar , wenn seine Funktionsvariante , das ursprüngliche Problem in Polynomialzeit mit einem Orakel entscheiden , gelöst werden kann. Jedes NP-vollständige Problem ist selbstreduzierbar. Es wird vermutet, dass das ganzzahlige Faktorisierungsproblem nicht selbstreduzierbar ist. ${\displaystyle\varphi}$${\displaystyle x_{1}}$${\displaystyle x_{1}}$${\displaystyle x_{2}}$${\displaystyle x_{1}}$

Kürzungen und komplette Probleme

Funktionsprobleme kann reduziert viel wie Entscheidungsprobleme: Funktionsprobleme gegeben und wir sagen , dass reduziert sich auf , wenn es polynomial-berechenbare Funktionen vorhanden ist und so , dass für alle Instanzen von und mögliche Lösungen von , es gilt ${\displaystyle \Pi_{R}}$${\displaystyle \Pi_{S}}$${\displaystyle \Pi_{R}}$${\displaystyle \Pi_{S}}$${\displaystyle f}$${\displaystyle g}$${\displaystyle x}$${\displaystyle R}$${\displaystyle y}$${\displaystyle S}$

• Wenn eine -Lösung hat, dann hat eine -Lösung.${\displaystyle x}$${\displaystyle R}$${\displaystyle f(x)}$${\displaystyle S}$
• ${\displaystyle (f(x),y)\in S\implies (x,g(x,y))\in R.}$

Es ist daher möglich, analog zum NP-vollständigen Problem FNP-vollständige Probleme zu definieren :

Ein Problem ist FNP-vollständig, wenn jedes Problem in FNP auf reduziert werden kann . Die Komplexitätsklasse FNP-vollständiger Probleme wird mit FNP-C oder FNPC bezeichnet . Daher ist das Problem FSAT auch ein FNP-vollständiges Problem, und das gilt genau dann, wenn . ${\displaystyle \Pi_{R}}$${\displaystyle \Pi_{R}}$${\displaystyle\mathbf{P} =\mathbf{NP}}$${\displaystyle\mathbf{FP} =\mathbf{FNP}}$

Totale Funktionsprobleme

Die zur Definition von Funktionsproblemen verwendete Relation hat den Nachteil, dass sie unvollständig ist: Nicht jede Eingabe hat ein Gegenstück, so dass . Daher ist die Frage der Berechenbarkeit von Beweisen nicht von der Frage nach ihrer Existenz getrennt. Um dieses Problem zu lösen, ist es zweckmäßig, die Beschränkung von Funktionsproblemen auf totale Relationen zu betrachten, was die Klasse TFNP als Unterklasse von FNP ergibt . Diese Klasse enthält Probleme wie die Berechnung reiner Nash-Gleichgewichte in bestimmten strategischen Spielen, bei denen es garantiert eine Lösung gibt. Wenn TFNP außerdem ein FNP-vollständiges Problem enthält, folgt daraus . ${\displaystyle R(x,y)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle (x,y)\in R}$${\displaystyle\mathbf{NP} ={\textbf{co-NP}}}$

Siehe auch

• Entscheidungsproblem
• Suchproblem
• Zählproblem (Komplexität)
• Optimierungsproblem

Verweise