Originaltitel:
On Monotonicity Testing and the 2-to-2 Games Conjecture
Inhalt des Buches:
Dieses Buch erörtert zwei Fragen der Komplexitätstheorie: das Problem der Monotonieprüfung und die 2-to-2 Games Conjecture.
Die Monotonieprüfung ist ein Problem aus dem Bereich der Eigenschaftsprüfung, das erstmals von Goldreich et al. im Jahr 2000 untersucht wurde. Die Eingabe des Algorithmus ist eine Funktion, und das Ziel ist es, einen Tester zu entwerfen, der so wenig Abfragen wie möglich an die Funktion stellt, monotone Funktionen akzeptiert und nicht monotone Funktionen mit einer Wahrscheinlichkeit nahe 1 zurückweist.
Das erste Ergebnis dieses Buches ist ein im Wesentlichen optimaler Algorithmus für dieses Problem. Die Analyse des Algorithmus stützt sich stark auf eine neuartige, gerichtete und robuste Analogie einer booleschen isoperimetrischen Ungleichung von Talagrand aus dem Jahr 1993.
Das Theorem der probabilistisch überprüfbaren Beweise (PCP) ist einer der Eckpfeiler der modernen theoretischen Computerwissenschaft. Ein Bereich, in dem PCPs unverzichtbar sind, ist das Gebiet der Härte der Approximation. Hier geht es darum, zu beweisen, dass einige Optimierungsprobleme schwer zu lösen sind, selbst wenn sie nur annähernd gelöst werden können. Viele Ergebnisse zur Härte der Approximation wurden mithilfe des PCP-Theorems bewiesen; für einige Probleme wurden jedoch keine optimalen Ergebnisse erzielt. Dieses Buch befasst sich mit einigen dieser Probleme, insbesondere mit dem 2-zu-2-Spielproblem und dem Vertex-Cover-Problem.
Das zweite Ergebnis dieses Buches ist ein Beweis der 2-zu-2-Spiele-Vermutung (mit unvollkommener Vollständigkeit), der neue Härte der Approximationsergebnisse für Probleme wie das Vertex-Cover-Problem und die unabhängige Menge impliziert. Sie dient auch als starker Beweis für die Vermutung der eindeutigen Spiele, ein notorisch verwandtes offenes Problem in der theoretischen Informatik. Der Kern des Beweises ist eine Charakterisierung kleiner Mengen von Knoten in Grassmann-Graphen, deren Kantenausdehnung von 1 weg begrenzt ist.
Weitere Daten des Buches:
| ISBN: | 9781450399685 |
| Autor: | |
| Verlag: | |
| Sprache: | Englisch |
| Einband: | Hardcover |
Kauf:
Derzeit verfügbar, auf Lager.
