Advanced Techniques in Exact Algorithms for NP-Hard Problems
Explore the realm of exact algorithms for NP-hard problems, delving into complexities, hypotheses, and state-of-the-art advancements like ETH and savings in runtime. Uncover the need for precise solutions in challenging scenarios and the quest for optimal time bounds in algorithmic research.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Models of Exact Algorithms for NP-Hard Problems Rahul Santhanam University of Edinburgh
Plan of the Talk Preliminaries and Motivation Informational Bottlenecks: Proof Complexity and Related Models Computational Bottlenecks: OPP and Compression Alternative Paradigms and Future Work
Plan of the Talk Preliminaries and Motivation Informational Bottlenecks: Proof Complexity and Related Models Computational Bottlenecks: OPP and Compression Alternative Paradigms and Future Work
NP-Hard Problems NP-complete: 3-SAT, CNF-SAT, Circuit-SAT, Independent Set, 3-Colourability, Vertex Cover, Subset Sum #P-complete: #SAT, #IS, Permanent PSPACE-complete: QBF-SAT For all of these problems, solvability in P implies NP=P Hardness is often circumvented by approximation, average-case solutions etc.
The Need for Exact Algorithms There are real-world contexts in which hard problems need to be solved exactly, eg., verification Exact solvability also connects to other areas of theory, eg., parameterized algorithms and complexity lower bounds Basic question: For an NP-hard problem L, what is the smallest asymptotic time bound? Brute-force search gives exp upper bound
Hardness Hypotheses Under traditional NP P hypothesis, no NP-hard problem can be solved in poly time But this says nothing about super-poly time solutions Exponential-Time Hypothesis (ETH): [IPZ01] 3-SAT cannot be solved in time 2o(n) ETH is very robust hypothesis. It implies none of the problems mentioned before are solvable in time 2o(n) [IPZ01, DHMTW12] However, different problems might have different best exponent c for which problem is in time cnbut not in time dnfor d < c
Notation m: input size; n: witness size/number of variables Brute-force algorithm runs in time 2npoly(m) We are interested in algorithms running in time 2n-f(n)poly(m), for f(n) asymptotically as large as possible We call f the savings of the algorithm
State of the Art 3-SAT: ~ 1.308n[H11] k-SAT: Savings (n/k) [PPSZ98, S99] CNF-SAT: Savings (n/log(m/n)) [AS03, S05, IMP12] 3-COL: ~ 1.329n[BE05] Subset Sum: ~ 1.414n[HS74] Circuit SAT: No non-trivial savings known QBF-SAT: Savings (n1/(k+1)) for k quants [SW15]
Can We Do Better? Are the analyses of known algorithms tight? What are worst-case instances of these algorithms?
More Generally... Can we formulate classes of algorithms including all those known to be useful, and show fundamental barriers on the power of these algorithms? Complexity theory is itself an attempt to do this, but is too liberal in terms of algorithms it allows Good analogy: Extended formulations of LPs and SDPs for approximation algorithms Which properties of instances guarantee hardness for known algorithms?
Motivation Doing better would not just give us improved algorithms but also possibly lower bounds using Williams connection [W10,W11] On the other hand, theory of hard instances could help in formulating benchmarks for SAT solvers Moreover, there is a heuristic connection between explicit hard instances for known algorithms and circuit lower bounds
Plan of the Talk Preliminaries and Motivation Informational Bottlenecks: Proof Complexity and Related Models Computational Bottlenecks: OPP and Compression Alternative Paradigms and Future Work
The Role of Proof Complexity Propositional proof complexity studies the hardness of explicit tautologies for various propositional proof systems, i.e., non- deterministic algorithms Paradigm: To decide if x is in L, either find a proof that x is in L or find a proof that x not in L For algorithm to have small running time, either there exists a small proof that x in L, or there exists a small proof that x not in L For L=SAT, former is true, so we try rule out latter
Proof Systems as Models of Algorithms Hardness against a non-deterministic algorithm implies hardness against any deterministic algorithm which operates by fixing the non-deterministic choices Well-known example: Connection between branching (DLL) algorithms and tree resolution
Branching (DLL) Algorithms Iteratively apply A strategy to choose which variable of the formula to set next A policy to decide which value to set it to Simplify the resulting formula according to rules which preserve satisfiability (unit propagation, pure literal elimination, subsumption) If at any point the formula evaluates to false, backtrack by choosing a different value for most recently set variable
Branching Algorithms and Tree Resolution If a CNF formula is unsatisfiable, a tree resolution proof of unsatisfiability can be derived from the recursion tree of any det branching algorithm run on . Size of proof is essentially size of recursion tree Iterative procedure Associate, with each leaf of the recursion tree, an unsatisfied clause C of Suppose we branch on a variable x at a node v of the recursion tree, and suppose clauses C1and C2have been associated with children of v. Then associate with v the clause C obtained by resolving C1and C2on x
Branching Algorithms and Tree Resolution Lower bound on size of tree resolution proof implies lower bound on the recursion tree size for corresponding branching algorithm If branching algorithm is run on unsatisfiable formula, it will take time proportional to recursion tree size
Hard Instances for Branching Algorithms First non-trivial algorithm for k-SAT [MS85], as well as several further improvements[S93, S96, K99] were branching algorithms [PI99] show that there are unsatisfiable k- CNFs which require tree resolution proofs of size 2n- (n/k^{1/8}) Improved by [BI12] to size 2n- (n/k^{1/4}) Instances encode linear equations mod p for some prime p
Other Proof Systems Just as Tree Resolution corresponds to branching algorithms, other (stronger) proof systems correspond to more general models of algorithms Best practical SAT solvers are based on clause learning, which is an idea closely related to the proof complexity view Lower bounds on proof complexity are often based on some notion of progress towards a complete proof
Issues with Direct Use of Proof Complexity A resolution-based lower bound can only apply to unsatisfiable formulas, since satisfiable formulas trivially have small proofs Suppose we tweak the branching algorithm model by timing out after f(n) steps, for some f. Then running algorithm on unsat formula doesn t give unsatisfiability proof Alternatively, suppose the strategy rule is probabilistic, and restarts are allowed. Again link with proof complexity breaks down
Satisfiable Hard Instances [ABM03] showed that random k-CNFs of a certain density (below the conjectured satisfiability threshold) are hard for certain natural branching algorithms (Ordered DLL and variants) Analysis uses proof complexity Issues Not clear for which algorithms precisely the lower bound holds Lower bound is of form 2 (n): not quite tight enough for us
Myopic and Drunk Algorithms [AHI04] formulate two models of branching- type algorithms Myopic algorithms: Here the policy and strategy are restricted to learn only n1- clauses at a time Drunk algorithms: Here the strategy can be arbitrarily complex but the policy is to set a variable purely at random Myopic and drunk algorithms capture most algorithms considered in random SAT literature
Exploiting Myopia and Drunkenness Theorem [AHI04]: Strongly expanding systems of linear equations cannot be solved by myopic algorithms in time 2n^{1- (1)} Theorem [AHI04]: There are explicit k-CNFs n such that any drunk algorithm takes time at least 2n- (n/k^{1/8})on nwith all but exponentially small probability
Features of [AHI04] Formalizations of natural algorithmic models which refine branching paradigm Use of proof complexity results ([BSW01] for myopic lower bound, [PI99] for drunk lower bound)
The Priority Branching Tree Model Considered in [ABBIMP05] Information about variables is revealed one piece at a time algorithm gets to see which clauses the variable occurs in. It can decide which piece to see based on variables it s seen so far and values it s set them to Theorem[ABBIMP05]: Expanding systems of linear equations cannot be solved by pBT s in time 2o(n) PBT and Myopic models both insist on info about input to be revealed locally
Plan of the Talk Preliminaries and Motivation Informational Bottlenecks: Proof Complexity and Related Models Computational Bottlenecks: OPP and Compression Alternative Paradigms and Future Work
State of the Art Algorithms for Variants of SAT k-SAT: [PPZ97] and [PPSZ98] use randomized branching with restarts; [S99] uses local search CNF-SAT: [S05] uses a branching (on disjunctions) reduction to [PPSZ98]/[S99] Formula-SAT: [S10] uses deterministic branching QBF-SAT: [SW15] uses branching + memoization None of these algorithms seem to fall into paradigms discussed
OPP Class of algorithms defined in [PP10] OPP = One-sided error probabilistic polynomial-time algorithms OPP algorithm with success probability >= 1/f(n) can be converted to randomized zero- error algorithm with expected running time O(f(n) poly(n)) just by repetition OPP-Search (solving search problem), and OPP-Decision (solving decision problem)
The Benefits of OPP Simple and flexible model which doesn t try to model too closely how algorithms actually work Not too liberal in the algorithms it allows any exp-time algorithm derived from an OPP algorithm consists of independent repetitions of a single poly-time probabilistic algorithm Covers many algorithms analyzed in literature
Examples of OPP Algorithms [PPZ99] algorithm for k-SAT: Try random assignment in random order of variables using unit propagation rule to simplify formula [S99] algorithm for k-SAT: Try random walk of linear length from random point in solution space, restart if unsuccessful Many branching algorithms: If analysis is local , such algorithms can be made OPP
... And a Couple That Dont Seem to Be [PPSZ98] algorithm for k-SAT does quasi-poly time preprocessing before using [PPZ99] idea [S10] algorithm for Formula-SAT is branching algorithm whose analysis is not local enough OPP algorithms are all poly-space and highly parallelizable, so algorithms without these properties aren t OPP The notion of OPP exposes commonalities and distinctions that weren t clear before, and is applicable to other NP problems
Limitations of OPP Theorem [PP10]: There is no OPP-Decision algorithm solving Circuit-SAT with success probability 2-n+o(n) unless all of NP has circuits of size 2n^ for some < 1 Note that ETH only rules out algorithms for Circuit-SAT that take sub-exponential time Idea of proof is to use duality between circuits and instances
OPP and k-SAT The theorem of [PP10] talks about Circuit-SAT, but we have no non-trivial algorithmic results for Circuit-SAT anyway How about k-SAT? Can we show that known algorithms achieve close to best possible bounds modulo standard complexity-theoretic hypotheses? Theorem [D12]: There is no OPP-Search algorithm for 3-SAT with success probability at least 2-n^ , for any < 1, unless NP in coNP/poly
Druckers Result Drucker s result assumes OPP algorithms with non-trivial success probability for a weaker problem, i.e., 3-SAT, and derives complexity consequences at the poly-time level The proof is complicated, proceeding through a non-deterministic direct product theorem for exponentially small error Challenge: Give a simpler proof of Drucker s result
Witness Compression Let L be an NP language defined by a poly-time relation R Let f be a function such that f(n) < n for all n. An f(n)-wc (witness compressor) for R is a poly-time reduction from R to some poly-time relation R such that <x,y> with |y|=n is mapped to <x ,y > with |y | <= f(n) An f(n)-wc for R yields an O(2f(n)poly(n)) time algorithm for LR, just by brute force search But when do non-trivial algorithms yield wc?
Variants of Witness Compression Witness compression for search problems can be defined analogously, with the reduction from R to R being a Levin reduction Can also define probabilistic witness compression, where R is a probabilistic poly- time predicate. Probabilistic witness compression yields probabilistic exact algorithm
Algorithms Yielding Witness Compression Witness compression was defined (slightly differently) by [DH11] [DH11] show that k-SAT algorithm of [DGHKKPRS02] and CNF-SAT algorithm of [S05] can be seen as witness compression Similarly to OPP, branching algorithms with local analysis give witness compression [PPZ99] gives probabilistic wc
Limitations of Witness Compression Theorem: If there is < 1 such that Circuit-SAT has n-wcs, then there is < 1 such that NP has circuits of size 2n^ Proof idea: Iterate witness compressor O(log(n)) times Theorem looks very similar to main result of [PP10] for OPP
Witness Compression vs OPP Clearly f(n)-wc for L implies OPP algorithm with success probability 2-f(n): OPP algorithm just tries a random compressed witness Theorem: OPP algorithm with success probability at least 2-f(n)implies probabilistic (f(n)+O(1))-wc for Circuit-SAT Proof idea is to use hashing, similar to [PP10] Theorem gives a cleaner way to view main result of [PP10] Also, by Drucker s result, n -wc for 3-SAT search problem for any < 1 implies NP in coNP/poly
Detour: Witness Compression vs Instance Compression/Kernelization Kernelization is a classic paradigm in parameterized algorithms: To design FPT algorithm, reduce instance in poly time to instance whose size depends only on the parameter Witness compression variant: Reduce instance in poly time to instance of an NP problem with witness size a function of the parameter Witness kernelization also gives FPT algorithms Power and limitations?
Detour: Witness Compression vs Instance Compression/Kernelization A sequence of results [BDFH09, FS11, D12] gives evidence against polynomial kernelization based on assumption that Polynomial Hierarchy (PH) is infinite [D13] can be seen as giving evidence against polynomial witness kernelization based on assumption that PH is infinite In some natural settings, latter result is stronger Perhaps indication that witness kernelization might be useful to look at for FPT researchers?
Plan of the Talk SAT Algorithms and Proof Complexity: Preliminaries Paradigms for Branching Algorithms, and Satisfiable Hard Instances Hard Instances for State of the Art Algorithms Alternative Paradigms and Future Work
More Fiddling with Branching A starting point for a lot of what I ve talked about is the difficulty of modelling (natural variants of) branching algorithms OPP and witness compression owe some of their robustness to the fact that arbitrary poly- time computations are included Branching can naturally be combined with poly-time algorithms: Branch until instance becomes poly-time solvable
Branching with Backdoors Backdoors were defined in [WGS03] as sets of variables such that restrictions to these variables results in poly-time solvability Consider branching algorithms for which leaves of recursion tree are not yes or no but poly- time computations applied to restricted instance, yielding a witness if instance is a yes Challenge: Give complexity-theoretic evidence that such trees have to be large for 3-SAT
Models Based on Hard Inputs Solving systems of linear equations is hard for many branching-type models, eg., Tree Resolution, Myopic Algorithms, Priority Branching Trees This motivates an inverted view of models Fix a class of inputs first, and then try to define interesting classes of algorithms for which these inputs are hard
Models Based on Hard Inputs Of course such models could be easily gamed: encode solutions to fixed inputs into the model But perhaps this would be harder to do if we insist that the model solves a family of inputs derived from a basic set Challenge: Try to model largest natural class of algorithms for which solving linear systems is hard
Future Work Give evidence that brute force search is not universal, i.e., for L in NP and in DTIME(2f(n)) but without f(n)-wc Is there a nice model which captures branching algorithms, deterministic and randomized, with or without restarts? Formal connections between hard instances for models and circuit lower bounds Models of exponential-space algorithms such as memoization, split-and-list
