Hardness in P
Abstract/Contents
- Abstract
- The celebrated theory of NP-Hardness classifies problems into ``easy" (in P) and ``NP-hard" (probably not in P). While the easy problems do have polynomial time algorithms, a polynomial runtime like O(n^2) or O(n^3) can be too slow, especially as our data continues to grow. Many fundamental ``easy" problems have resisted decades of attempts at getting truly fast algorithms and are typically solved by approximations and heuristics in practice. A striking example is the O(n^2) time Local Alignment problem from Bioinformatics: one of the most cited scientific papers of all time is a heuristic algorithm that solves it efficiently (in near-linear time) but without optimality guarantees. Why can't we solve Local Alignment optimally in near-linear time? The class P is full of many such fundamental problems arising in all areas of computation. Can we design formal tools for finding out which ones "probably cannot be solved more efficiently", and why not? This thesis makes progress towards building such a theory of hardness in P. We follow an approach that can be viewed as a refinement of NP-Hardness. To prove a lower bound, e.g. that Local Alignment cannot be solved in O(n^{2-eps}) time for some eps> 0, we prove via reductions that such an algorithm would imply breakthrough algorithms for other famous problems and refute widely believed conjectures, e.g. we would solve k-SAT in O((2-eps)^n) time for some eps> 0, refuting the so-called Strong Exponential Time Hypothesis (SETH). In this thesis, we design many novel reductions of this form. Assuming SETH and a small number of other conjectures, that are similar in spirit but more fine-grained than the "P not equal NP" assumption, we deduce that the current algorithms for a long list of important problems in P cannot be substantially improved. The list includes the following basic problems and many others. - Problems on Strings: Longest Common Subsequence, Parsing Context-Free Grammars, Dynamic Time Warping, and RNA Folding. - Problems on Graphs: Graph Radius and Median, Betweenness Centrality, Subtree Isomorphism, and Single-Source Max-Flow. - Problems on Dynamic Data: Reachability, Strongly Connected Components, Maximum Matching, and Shortest Paths. Besides these lower bounds, this thesis offers a few high-level contributions that enhance this theory for hardness in P. New Conjectures: We highlight a new conjecture on the complexity of Clique that has lead to several interesting results. Better Conjectures: We show that many lower bounds can be based on better conjectures that are more likely to hold. Connections to Circuit Complexity: We make this theory more appealing by showing that refuting our conjectures can lead to breakthroughs in classical complexity theory. More Relevant Lower Bounds: We adapt this theory to prove lower bounds for more realistic instances, e.g. showing that some graph problems remain hard if the input is planar.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2017 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Abboud, Amir Elie |
|---|---|
| Associated with | Stanford University, Computer Science Department. |
| Primary advisor | Williams Vassilevska, Virginia, 1980- |
| Thesis advisor | Williams Vassilevska, Virginia, 1980- |
| Thesis advisor | Charikar, Moses |
| Thesis advisor | Reingold, Omer |
| Thesis advisor | Williams, Ryan C |
| Advisor | Charikar, Moses |
| Advisor | Reingold, Omer |
| Advisor | Williams, Ryan C |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Amir Elie Abboud. |
|---|---|
| Note | Submitted to the Department of Computer Science. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2017. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2017 by Amir Elie Abboud
Also listed in
Loading usage metrics...