edoc-Server der Humboldt-Universität zu Berlin

Dissertation

Autor(en): Holger Dell
Titel: Sparse instances of hard problems
Gutachter: Martin Grohe; Johannes Köbler; Dieter van Melkebeek
Erscheinungsdatum: 01.09.2011
Volltext: pdf (urn:nbn:de:kobv:11-100192642)
Fachgebiet(e): Informatik
Schlagwörter (ger): Komplexitätstheorie, Ausdünnung, Kernelisierung, Probabilistisch verifizierbare Beweise, Zählprobleme, Exponentialzeithypothese
Schlagwörter (eng): complexity theory, sparsification, kernelization, probabilistically checkable proofs, counting problems, exponential time hypothesis
Einrichtung: Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
Lizenz: Namensnennung - Keine kommerzielle Nutzung - Keine Bearbeitung (CC BY NC ND)
Zitationshinweis: Dell, Holger: Sparse instances of hard problems; Dissertation, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am 01.09.2011, urn:nbn:de:kobv:11-100192642
Metadatenexport: Um den gesamten Metadatensatz im Endnote- oder Bibtex-Format zu speichern, klicken Sie bitte auf den entsprechenden Link. Endnote   Bibtex  
print on demand: Wenn Sie auf dieses Icon klicken, können Sie ein Druckexemplar dieser Publikation bestellen.
Diese Seite taggen: Diese Icons führen auf so genannte Social-Bookmark-Systeme, auf denen Sie Lesezeichen anlegen, persönliche Tags vergeben und Lesezeichen anderer Nutzer ansehen können.
  • connotea
  • del.icio.us
  • Furl
  • RawSugar

Abstract (ger):
Diese Arbeit nutzt und verfeinert Methoden der Komplexitätstheorie, um mit diesen die Komplexität dünner Instanzen zu untersuchen. Dazu gehören etwa Graphen mit wenigen Kanten oder Formeln mit wenigen Bedingungen beschränkter Weite. Dabei ergeben sich zwei natürliche Fragestellungen: (a) Gibt es einen effizienten Algorithmus, der beliebige Instanzen eines NP-schweren Problems auf äquivalente, dünne Instanzen reduziert? (b) Gibt es einen Algorithmus, der dünne Instanzen NP-schwerer Probleme bedeutend schneller löst als allgemeine Instanzen gelöst werden können? Wir formalisieren diese Fragen für verschiedene Probleme und zeigen, dass positive Antworten jeweils zu komplexitätstheoretischen Konsequenzen führen, die als unwahrscheinlich gelten. Frage (a) wird als Kommunikation modelliert, in der zwei Akteure kooperativ eine NP-schwere Sprache entscheiden möchten und dabei möglichst wenig kommunizieren. Unter der komplexitätstheoretischen Annahme, dass coNP keine Teilmenge von NP/poly ist, erhalten wir aus unseren Ergebnissen erstaunlich scharfe untere Schranken für interessante Parameter aus verschiedenen Teilgebieten der theoretischen Informatik. Im Speziellen betrifft das die Ausdünnung von Formeln, die Kernelisierung aus der parameterisierten Komplexitätstheorie, die verlustbehaftete Kompression von Entscheidungsproblemen, und die Theorie der probabilistisch verifizierbaren Beweise. Wir untersuchen Fragestellung (b) anhand der Exponentialzeitkomplexität von Zählproblemen. Unter (Varianten) der bekannten Exponentialzeithypothese (ETH) erhalten wir exponentielle untere Schranken für wichtige #P-schwere Probleme: das Berechnen der Zahl der erfüllenden Belegungen einer 2-KNF Formel, das Berechnen der Zahl aller unabhängigen Mengen in einem Graphen, das Berechnen der Permanente einer Matrix mit Einträgen 0 und 1, das Auswerten des Tuttepolynoms an festen Punkten.
Abstract (eng):
In this thesis, we use and refine methods of computational complexity theory to analyze the complexity of sparse instances, such as graphs with few edges or formulas with few constraints of bounded width. Two natural questions arise in this context: (a) Is there an efficient algorithm that reduces arbitrary instances of an NP-hard problem to equivalent, sparse instances? (b) Is there an algorithm that solves sparse instances of an NP-hard problem significantly faster than general instances can be solved? We formalize these questions for different problems and show that positive answers for these formalizations would lead to consequences in complexity theory that are considered unlikely. Question (a) is modeled by a communication process, in which two players want to cooperatively decide an NP-hard language and at the same time communicate as few as possible. Under the complexity-theoretic hypothesis that coNP is not in NP/poly, our results imply surprisingly tight lower bounds for parameters of interest in several areas, namely sparsification, kernelization in parameterized complexity, lossy compression, and probabilistically checkable proofs. We study the question (b) for counting problems in the exponential time setting. Assuming (variants of) the exponential time hypothesis (ETH), we obtain asymptotically tight, exponential lower bounds for well-studied #P-hard problems: Computing the number of satisfying assignments of a 2-CNF formula, computing the number of all independent sets in a graph, computing the permanent of a matrix with entries 0 and 1, evaluating the Tutte polynomial at fixed evaluation points.
Zugriffsstatistik: Die Daten für die Zugriffsstatistik der einzelnen Dokumente wurden aus den durch AWStats aggregierten Webserver-Logs erstellt. Sie beziehen sich auf den monatlichen Zugriff auf den Volltext sowie auf die Startseite. Die Zugriffsstatistik wird nicht standardisiert erfasst und kann maschinelle Zugriffe enthalten.
 
Bei Formatversionen eines Dokuments, die aus mehreren Dateien bestehen (insbesondere HTML), wird jeweils der monatlich höchste Zugriffswert auf eine der Dateien (Kapitel) des Dokuments angezeigt.
 
Um die detaillierten Zugriffszahlen zu sehen, fahren Sie bitte mit dem Mauszeiger über die einzelnen Balken des Diagramms.
Startseite: 2 Zugriffe PDF: 8 Zugriffe Startseite: 6 Zugriffe PDF: 16 Zugriffe Startseite: 3 Zugriffe PDF: 12 Zugriffe Startseite: 5 Zugriffe PDF: 9 Zugriffe PDF: 15 Zugriffe PDF: 30 Zugriffe Startseite: 3 Zugriffe PDF: 36 Zugriffe Startseite: 6 Zugriffe PDF: 35 Zugriffe Startseite: 2 Zugriffe PDF: 25 Zugriffe PDF: 26 Zugriffe PDF: 24 Zugriffe PDF: 32 Zugriffe PDF: 23 Zugriffe Startseite: 2 Zugriffe PDF: 33 Zugriffe Startseite: 1 Zugriffe PDF: 30 Zugriffe Startseite: 1 Zugriffe PDF: 37 Zugriffe Startseite: 1 Zugriffe PDF: 37 Zugriffe Startseite: 2 Zugriffe PDF: 48 Zugriffe PDF: 33 Zugriffe Startseite: 4 Zugriffe PDF: 29 Zugriffe Startseite: 1 Zugriffe PDF: 29 Zugriffe Startseite: 2 Zugriffe PDF: 18 Zugriffe Startseite: 2 Zugriffe PDF: 39 Zugriffe Startseite: 3 Zugriffe PDF: 38 Zugriffe PDF: 38 Zugriffe Startseite: 1 Zugriffe PDF: 38 Zugriffe Startseite: 2 Zugriffe PDF: 39 Zugriffe Startseite: 3 Zugriffe PDF: 46 Zugriffe Startseite: 2 Zugriffe PDF: 25 Zugriffe PDF: 26 Zugriffe PDF: 33 Zugriffe Startseite: 2 Zugriffe PDF: 23 Zugriffe Startseite: 2 Zugriffe PDF: 23 Zugriffe Startseite: 5 Zugriffe PDF: 38 Zugriffe
Oct
11
Nov
11
Dec
11
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Jul
14
Aug
14
Sep
14
Monat Oct
11
Nov
11
Dec
11
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Jul
14
Aug
14
Sep
14
Startseite 2 6 3 5     3 6 2         2 1 1 1 2   4 1 2 2 3   1 2 3 2     2 2 5
PDF 8 16 12 9 15 30 36 35 25 26 24 32 23 33 30 37 37 48 33 29 29 18 39 38 38 38 39 46 25 26 33 23 23 38

Gesamtzahl der Zugriffe seit Oct 2011:

  • Startseite – 63 (1.85 pro Monat)
  • PDF – 991 (29.15 pro Monat)
 
 
Generiert am 31.10.2014, 13:12:58