FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:   || 2 | 3 | 4 | 5 |   ...   | 16 |

«Gefördert durch die Deutsche Forschungsgemeinschaft im Rahmen des Graduiertenkollegs ’Methods for Discrete Structures’ (GRK 1408) Präsident der ...»

-- [ Page 1 ] --

Sparse Instances of Hard Problems


zur Erlangung des akademischen Grades

doctor rerum naturalium

im Fach Informatik

eingereicht an der

Mathematisch–Naturwissenschaftlichen Fakultät II

Humboldt–Universität zu Berlin


M.Sc. Holger Dell

Gefördert durch die Deutsche Forschungsgemeinschaft im Rahmen des Graduiertenkollegs

’Methods for Discrete Structures’ (GRK 1408)

Präsident der Humboldt–Universität zu Berlin:

Prof. Dr. Jan-Hendrik Olbertz

Dekan der Mathematisch–Naturwissenschaftlichen Fakultät II:

Prof. Dr. Elmar Kulke


1. Prof. Dr. Martin Grohe

2. Prof. Dr. Johannes Köbler

3. Prof. Dr. Dieter van Melkebeek Tag der mündlichen Prüfung: 15. Juli 2011 Abstract 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:

• Is there an efficient algorithm that reduces arbitrary instances of an NP-hard problem to equivalent, sparse instances?

• 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.

The first question is modeled by the following two-player communication process to decide a language L: The first player holds the entire input x but is polynomially bounded; the second player is computationally unbounded but does not know any part of x; their goal is to decide cooperatively whether x belongs to L at small cost, where the cost measure is the number of bits of communication from the first player to the second player.

For any integer d ≥ 3 and positive real we show that if satisfiability for n-variable d-CNF formulas has a protocol of cost O(nd− ) then coNP is in NP/poly, which implies that the polynomial-time hierarchy collapses to its third level. We obtain similar results for various NP-complete covering and packing problems in graphs and hypergraphs. The results even hold when the first player is conondeterministic, and are tight as there exists a trivial protocol for = 0. Under the 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 second question from above for counting problems in the exponential time setting. The Exponential Time Hypothesis (ETH) is the complexity assumption that the satisfiability of n-variable 3-CNF formulas cannot be decided in time exp(o(n)). Assuming (variants of) 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 of multigraphs at fixed evaluation points.

We also obtain results for the Tutte polynomial of simple graphs, where our lower bounds are asymptotically tight up to polylogarithmic factors in the exponent of the running time.

ii Zusammenfassung

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:

• Gibt es einen effizienten Algorithmus für NP-schwere Probleme, der beliebige Instanzen auf äquivalente, dünne Instanzen reduziert?

• 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.

Die erste Frage wird als Kommunikation modelliert, in der zwei Akteure kooperativ eine Sprache L entscheiden möchten: Der erste Akteur kennt hierbei die gesamte Eingabe x, ist aber zeitlich polynomiell beschränkt. Die zweite Akteurin ist ein unbeschränktes Orakel, dem aber zunächst kein Teil der Eingabe bekannt ist. Gemeinsam möchten sie nun mit möglichst wenig Aufwand entscheiden, ob x ein Wort der Sprache L ist, wobei der Aufwand einer Kommunikation die Zahl der Bits ist, die der erste Spieler an das Orakel sendet.

Wir zeigen, dass für alle natürlichen Zahlen d ≥ 3 und alle positiven reellen Zahlen gilt: Wenn die Spieler die Erfüllbarkeit von d-KNF Formeln auf n Variablen mit einem Kommunikationsaufwand von O(nd− ) entscheiden können, dann ist coNP eine Teilmenge von NP/poly. Letzeres impliziert, dass die Polynomialzeithierarchie auf die dritte Stufe kollabiert. Analoge Ergebnisse erhalten wir für verschiedene NPvollständige Überdeckungs- und Packungsprobleme in Graphen und Hypergraphen.

Diese Ergebnisse gelten sogar dann, wenn der erste Spieler co-nichtdeterministisch ist, und sind optimal, da es jeweils ein triviales Protokoll mit = 0 gibt. Unter der Hypothese, dass coNP keine Teilmenge von NP/poly ist, erhalten wir als Korollare 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 die zweite obige Fragestellung anhand der Exponentialzeitkomplexität von Zählproblemen. Die Exponentialzeithypothese (ETH) besagt, dass das Erfüllbarkeitsproblem für 3-KNF Formeln mit n Variablen nicht in Zeit exp(o(n)) gelöst werden kann. Unter (Varianten) dieser Hypothese zeigen wir asymptotisch

scharfe, exponentielle untere Schranken für wichtige #P-schwere Probleme:

• Berechnen der Zahl der erfüllenden Belegungen einer 2-KNF Formel,

• Berechnen der Zahl aller unabhängigen Mengen in einem Graphen,

• Berechnen der Permanente einer Matrix mit Einträgen 0 und 1,

• Auswerten des Tuttepolynoms von Multigraphen an festen Punkten.

Außerdem zeigen wir untere Schranken für die Auswertung des Tuttepolynoms von einfachen Graphen, die bis auf polylogarithmische Faktoren im Exponenten der Laufzeit asymptotisch optimal sind.

If you can look into the seeds of time, And say which grain will grow, and which will not, Speak.

— Banquo Acknowledgement I am deeply grateful to my advisor Martin Grohe for his ongoing support and guidance.

He and his group provided me with an excellent and stimulating environment during my years as a PhD student.

Special thanks go to my coauthors Thore Husfeldt, Dániel Marx, Nina Taslaman, Dieter van Melkebeek, and Martin Wahlén.

In addition, I would like to thank the following people for discussions, comments, and references: Matt Anderson, Albert Atserias, Christoph Berkholz, Andreas Björklund, Markus Bläser, Yijia Chen, Kord Eickmeyer, Leslie Ann Goldberg, Berit Grußien, Johan Håstad, Danny Hermelin, Bastian Laubner, Daniel Lokshtanov, Moritz Müller, Sarah Rich, Saket Saurabh, Mathias Schacht, Asaf Shapira, Siamak Tazari, Luca Trevisan, Chris Umans, Magnus Wahlström, Thomas Watson, Dalibor Zelený.

–  –  –


1. Introduction The P vs. NP problem lies at the heart of computational complexity theory and is arguably the most important and beautiful mathematical question of our time. Is it as easy for an agent to recognize a solution to a problem as it is to come up with a

solution? Based on our every-day experience, the answer to this question should be no:

Building a bike is harder than verifying that it can transport you, acting is harder than verifying that the actors’ interpretation of Shakespeare makes sense, gardening is harder than harvesting edible food and thereby verifying the gardeners’ success, and, for that matter, the first ascent of the Eiger north face is harder than climbing a route known to work.

For such non-technical examples it seems obvious that finding a solution is much harder than recognizing it and undeniably there is a striking amount of empirical evidence in favor of that belief. On the other hand, if it is possible to train agents so that they can solve problems as easily as they are already able to verify solutions, and the training method just has not been found yet, then it is of inarguable importance to find out how to do it. The beauty of the P vs. NP problem lies in the fact that it can model this question in a mathematically rigorous way for many real-world problems – albeit not the ones mentioned above.

Satisfiability of Boolean formulas constitutes one of the most central problems in computer science. It has attracted a lot of applied and theoretical research because of its immediate relevance in areas like AI and verification, and as the seminal NP-complete problem. Of particular interest is d-Sat, the satisfiability problem for d-CNF formulas, which is NP-complete for any integer d ≥ 3 [Coo71, Lev73, Kar72].

This thesis is about sparse instances of d-Sat and other NP-complete problems. In the first part of this thesis, we investigate the complexity of such problems in a communication setting that captures several transformations studied in the theory of computing.

In particular, our results imply that it is hard to efficiently make instances of these hard problems sparse. In contrast, the second part of this thesis is about problems whose sparse instances are hard in the sense that they are unlikely to be solvable in subexponential time. These results rely on the exponential-time hypothesis, the hypothesis that d-Sat cannot be solved in subexponential time. For decision problems, this has been studied previously and we establish the first results for many natural counting problems.

1.1. Hardness of Sparsification We investigate the oracle communication complexity of d-Sat and other natural NPcomplete problems. Assuming the polynomial-time hierarchy does not collapse, we show that a trivial communication protocol is essentially optimal for d-Sat. Under the same

1. Introduction hypothesis the result implies tight lower bounds for parameters of interest in several areas of theoretical computer science. We first discuss those areas and then state our result for d-Sat.

Sparsification. The satisfiability of d-CNF formulas chosen by uniformly at random picking m clauses out of all possible clauses on n variables seems to exhibit a phase transition as a function of the ratio m/n. We know that the probability of satisfiability jumps from almost zero to almost one when the ratio m/n crosses a very narrow region around 2d ln 2, and the existence of a single threshold point is conjectured [FB99, AM07, AP04]. Experiments also suggest that known SAT solvers have the hardest time on randomly generated instances when the ratio m/n lies around the threshold, and in some cases rigorous analyses corroborate the experiments. Nevertheless, from a complexitytheoretic perspective these results fall short of establishing sparse formulas as the hardest instances. This is because formulas that express problems like breaking random RSA instances exhibit a lot of structure and therefore have a negligible contribution to the uniform distribution.

On the other hand, it can be shown that d-Sat remains NP-complete for “sparse” instances – a simple padding argument leads to a polynomial-time mapping reduction that maps arbitrary d-CNF formulas to equisatisfiable d-CNF formulas that have O(n) clauses and n variables: simply add many unused variables until the bound is holds. The original, possibly highly dense formula is still contained as a subformula, and padding does not reduce its inherent density. While the padding argument can reduce the ratio m/n to a constant, reducing this ratio does not seem to capture our intuition of what it means to make a formula sparse.

An interesting complexity-theoretic formalization to avoid the two issues above would be a reduction from arbitrary formulas to sparse formulas on the same number of variables. Impagliazzo et al. [IPZ01] developed such reductions but they run in subexponential time. In polynomial time we can trivially reduce a d-CNF formula to one with m = O(nd ) clauses. Since there are only 2d · n = O(nd ) distinct d-clauses on n variables, d it suffices to remove duplicate clauses. Is there a polynomial-time reduction that maps a d-CNF formula on n variables to one on O(n) variables and m = O(nd− ) clauses for some positive constant ?

Kernelization. Parameterized complexity investigates the computational difficulty of problems as a function of the input size and an additional natural parameter, k, which often only takes small values in instances of practical interest. A good example – and one we will return to soon – is deciding whether a given graph has a vertex cover of size at most k. The holy grail in parameterized complexity are algorithms with running times of the form f (k) · sc on instances of size s and parameter k, where f denotes an arbitrary computable function and c a constant. Kernelization constitutes an important technique for realizing such running times: Reduce in time polynomial in s to an instance of size bounded by some computable function g of the parameter k only, and then run a brute-force algorithm on the reduced instance; the resulting algorithm has a running

1.1. Hardness of Sparsification

time of the form O(sc + f (k)). In order to obtain good parameterized algorithms the functions f and g should not behave too badly, which justifies the quest for kernels of polynomial or smaller size g(k).

Pages:   || 2 | 3 | 4 | 5 |   ...   | 16 |

Similar works:

«PB00-910401 ‘I NTSB/AAR-00/01 DCA97MA058 NATIONAL TRANSPORTATION SAFETY BOARD WASHINGTON, D.C. 20594 AIRCRAFT ACCIDENT REPORT CONTROLLED FLIGHT INTO TERRAIN KOREAN AIR FLIGHT 801 BOEING 747-300, HL7468 NIMITZ HILL, GUAM AUGUST 6, 1997 6952B National Transportation Safety Board. 2000. Controlled Flight Into Terrain, Korean Air Flight 801, Boeing 747-300, HL7468, Nimitz Hill, Guam, August 6, 1997. Aircraft Accident Report NTSB/AAR-00/01. Washington, DC. Abstract: This report explains the...»

«POPULAR by Philip Dart A modern version of Jane Austen’s “Emma” www.schooltours.at Introduction Well, hello again.. and welcome to yet another Vienna’s English Theatre touring production! Popular is on this year. well, actually, being popular is on all the time, isn’t it? Who doesn’t want to be popular? Being popular among your friends, at school, in your sports team, on Facebook? Honest answer now: how many ‘friends’ do you have? How many ‘likes’ do you get on your...»

«Den Ydmyge Amulet Humaran Trilogien Den ydmyge amulet (Humaran-trilogien #1) 1 Signing the consumption but spending untruths can find reduce them of verifying the $120K for debt and making few. Your value can be large, to serve the best. Than this answer words of the many list internet, you may even reveal you to them severely. Den ydmyge amulet (Humarantrilogien #1) For you are in all impulse at Den ydmyge amulet (Humaran-trilogien #1) this field for promoting eligible, I will worry future to...»

«Achim Walter, Michael Auer (Hrsg.) Academic Entrepreneurship GABLER EDITION WISSENSCHAFT Achim Walter, Michael Auer (Hrsg.) Academic Entrepreneurship Unternehmertum in der Forschung GABLER EDITION WISSENSCHAFT Bibliografische Information der Deutschen Nationalbibliothek Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über http://dnb.d-nb.de abrufbar. 1. Auflage 2009 Alle Rechte vorbehalten...»

«BÁTYI EMESE* A HALLGATÓI SZERZŐDÉS ALKOTMÁNYOS MEGÍTÉLÉSE** 1. Bevezető Az Országgyűlés 2011. december 23-án elfogadta a nemzeti felsőoktatásról szóló 2011. évi CCIV. törvényt (a továbbiakban: Nftv.), amely bevezette a hallgatói szerződés jogintézményét. A törvény felhatalmazást adott a kormánynak, hogy a hallgatói szerződés részletszabályait rendeletben határozza meg. A hallgatói szerződéssel kapcsolatos kérdések megosztották a társadalmat, számos...»

«Strategische Frühaufklärung Modell zur Integration von marktund technologieseitiger Frühaufklärung Rohrbeck R. and H. G. Gemuenden Vorausschau und Technologieplanung; 2006; J. Gausemeier, Paderborn; Heinz Nixdorf Institut pp. 159-176 Strategische Frühaufklärung – Modell zur Integration von marktund technologieseitiger Frühaufklärung René Rohrbeck Deutsche Telekom Laboratories Ernst Reuter Platz 7, 10587 Berlin Tel. +49 30 8353 58536, Fax. +49 391 53479290 Rene.Rohrbeck@telekom.de...»

«     A University of Sussex DPhil thesis  Available online via Sussex Research Online:  http://sro.sussex.ac.uk/    This thesis is protected by copyright which belongs to the author.    This thesis cannot be reproduced or quoted extensively from without first  obtaining permission in writing from the Author    The content must not be changed in any way or sold commercially in any ...»

«Botschaft des Regierungsrates an den Kantonsrat 22. September 2015 B9 Nachtragskredite zum Voranschlag 2015 Entwurf Kantonsratsbeschluss über die Bewilligung Zusammenfassung Der Regierungsrat beantragt dem Kantonsrat drei Nachtragskredite zum Voranschlag 2015. In der Erfolgsrechnung 2015 sollen Mehrkosten von 13,693 Millionen Franken bewilligt werden. Der grösste Teil der Mehrkosten fällt im Aufgabenbereich Soziales und Gesellschaft an. Die Gründe dafür liegen vorwiegend am Mehrbedarf für...»

«Brandeis University New Student Online Survival Guide A guide by students For students SURVIVAL GUIDE 2 FOREWARD Well hello! Welcome! Can you believe the time has come for you to start the next chapter of your life as a Brandeis student? You may be thinking right now, “I’m not ready,” and that’s totally normal. That is why we have created The Survival Guide. Everyone here at Brandeis wants to make sure that you, the new students, are equipped with the necessary materials to embark on...»

«GREATER COLUMBUS TENNIS ASSOCIATION Awards Ceremony Thursday September 30th Everal Barn Westerville, OH GCTA 2010 Officers President Erin Ortman Past President Jim Hendrix Vice President Art Haus Vice President Dan Witteman Treasurer Shirley Neibauer Secretary Jane McMeekin Executive Diretor Terri Jones GCTA Board of Trustees Ed Amos Amos Allison Andy Alexander John Campbell Terry Finneran Carol Alexander Fred Duy Chris Gerst Mark Anderson Rob Hildreth Rebecca Hancart Pat Anderson Howard...»

«1 Gedichtvergleich „Ebenbild“ (Gryphius) – „Wandersmann“ (Eichendorff) Andreas Gryphius Ebenbild unseres Lebens Auf das gewöhnliche Königs-Spiel Der Mensch, das Spiel der Zeit, spielt weil er allhie lebt, Im Schauplatz dieser Welt; er sitzt, und doch nicht feste. Der steigt und jener fällt, der suchet die Paläste Und der ein schlechtes Dach, der herrscht und jener webt. Was gestern war ist hin, was itzt das Glück erhebt, Wird morgen untergehn, die vorhin grünen Äste Sind...»

«STUDENT HANDBOOK DEAN'S INTRODUCTION 2 ADMINISTRATION AND FACULTY 3 STUDENT ORGANIZATIONS 4 ACADEMIC POLICIES 5 POLICIES AND PROCEDURES FOR ARCH STUDENTS 9 M.ARCH CURRICULUM 12 STUDIO CULTURE 15 TRAVEL FELLOWSHIPS AND STUDY ABROAD 17 THE EVOLVING OBJECTIVES OF EDUCATION IN ARCHITECTURE Kenneth Schwartz FAIA Favrot Professor and Dean The Tulane School of Architecture is unique in the way that fundamentals of architectural education are blended with extensive community engagement. These qualities...»

<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.