SIGACT News Complexity Theory Column 76: an atypical survey of typical-case heuristic algorithms
---
paper_title: Complete sets and closeness to complexity classes

paper_content:

We consider two setsA andB to be close to each other if the census of their symmetric difference,A ▵B, is a slowly increasing function (e.g. a polynomial.) The classes of sets which are polynomially close to some set in a complexity classC (likeP) are studied and characterized. We investigate the question whether complete sets forNP or EXPTIME can be polynomially close to a set inP. Some of the obtained results strengthen or generalize results by Yesha [24], e.g. it is shown that no EXPTIME-hard set can be polynomially close to any set inP.
---
paper_title: On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets

paper_content:

Let $\Sigma $ be a finite alphabet. A set $S \subset \Sigma ^ * $ is called sparse if the number of members of S having length at most n is bounded above by a polynomial in n. Let $ \leqq _m^P $ denote polynomial-time many-one reducibility, and let $ \leqq _{bptt}^P $ denote the more general polynomial-time bounded positive truth-table reducibility. We prove: (1) $ \leqq _{bptt}^P $ reducibility of a coNP-hard set to a sparse set implies ${\text{NP}} = {\text{P}}$, and (2) $ \leqq _{bptt}^P $ reducibility of an NP-hard set to a sparse set which is itself in NP implies ${\text{NP}} = {\text{P}}$. (1) generalizes Fortune’s result [F]. He proved it for the case of $ \leqq _m^P $ reducibility. (2), for the case of $ \leqq _m^P $ reducibility, was proved by Mahaney [M], even without assuming that the sparse set itself is in NP. Our results imply that if a coNP-hard set is a finite union of sets which are $ \leqq _m^P $ reducible to sparse sets, then ${\text{NP}} = {\text{P}}$. We then investigate a certain non...
---
paper_title: On polynomial time bounded truth-table reducibility of NP sets to sparse sets

paper_content:

We prove that if P # NP, then there exists a set in NP that is polynomial time bounded truth-table reducible (in short, <Ft,-reducible) to no sparse set. In other words, we prove that no sparse <[tt-hard set exists for NP unless P = NP. By using the technique proving this result, we investigate intractability of several number theoretic decision problems, i.e., decision problems defined naturally from number theoretic problems. We show that for those number theoretic decision problems, if it is not in P, then it is _<Ft,-reducible to no sparse set.
---
paper_title: Comparison of polynomial-time reducibilities

paper_content:

Comparison of the polynomial-time-bounded reducibilities introduced by Cook [1] and Karp [4] leads naturally to the definition of several intermediate truth-table reducibilities. We give definitions and comparisons for these reducibilities; we note, in particular, that all reducibilities of this type which do not have obvious implication relationships are in fact distinct in a strong sense. Proofs are by simultaneous diagonalization and encoding constructions. Work of Meyer and Stockmeyer [7] and Gill [2] then leads us to define nondeterministic versions of all of our reducibilities. Although many of the definitions degenerate, comparison of the remaining nondeterministic reducibilities among themselves and with the corresponding deterministic reducibilities yields some interesting relationships.
---
paper_title: Complete sets and closeness to complexity classes

paper_content:

We consider two setsA andB to be close to each other if the census of their symmetric difference,A ▵B, is a slowly increasing function (e.g. a polynomial.) The classes of sets which are polynomially close to some set in a complexity classC (likeP) are studied and characterized. We investigate the question whether complete sets forNP or EXPTIME can be polynomially close to a set inP. Some of the obtained results strengthen or generalize results by Yesha [24], e.g. it is shown that no EXPTIME-hard set can be polynomially close to any set inP.
---
paper_title: On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets

paper_content:

Let $\Sigma $ be a finite alphabet. A set $S \subset \Sigma ^ * $ is called sparse if the number of members of S having length at most n is bounded above by a polynomial in n. Let $ \leqq _m^P $ denote polynomial-time many-one reducibility, and let $ \leqq _{bptt}^P $ denote the more general polynomial-time bounded positive truth-table reducibility. We prove: (1) $ \leqq _{bptt}^P $ reducibility of a coNP-hard set to a sparse set implies ${\text{NP}} = {\text{P}}$, and (2) $ \leqq _{bptt}^P $ reducibility of an NP-hard set to a sparse set which is itself in NP implies ${\text{NP}} = {\text{P}}$. (1) generalizes Fortune’s result [F]. He proved it for the case of $ \leqq _m^P $ reducibility. (2), for the case of $ \leqq _m^P $ reducibility, was proved by Mahaney [M], even without assuming that the sparse set itself is in NP. Our results imply that if a coNP-hard set is a finite union of sets which are $ \leqq _m^P $ reducible to sparse sets, then ${\text{NP}} = {\text{P}}$. We then investigate a certain non...
---
paper_title: On reductions of NP sets to sparse sets

paper_content:

Ogiwara and Watanabe showed that if SAT is bounded truth-table reducible to a sparse set, then P = NP. In this paper we simplify their proof, strengthen the result and use it to obtain several new results. Among the new results are the following:*Applications of the main theorem to log-truth-table and log-Turing reductions of NP sets to sparse sets. One typical example is that if SAT is log-truth-table reducible to a sparse set then NP is contained in DTIME (2^O^(^l^o^g^^^2^n^)). *Generalizations of the main theorem which yields results similar to the main result at arbitrary levels of the polynomial hierarchy and which extend as well to strong nondeterministic reductions. *The construction of an oracle relative to which P NP but there are NP-complete sets which are f(n)-tt-reducible to a tally set, for any f(n) @e @w(log n). This implies that, up to relativization, some of our results are optimal.
---
paper_title: The complexity of manipulative attacks in nearly single-peaked electorates

paper_content:

Many electoral control and manipulation problems--which we will refer to in general as "manipulative actions" problems--are NP-hard in the general case. Many of these problems fall into polynomial time if the electorate is single-peaked, i.e., is polarized along some axis/issue. However, real-world electorates are not truly single-peaked--for example, there may be some maverick voters--and to take this into account, we study the complexity of manipulative-action algorithms for the case of nearly single-peaked electorates.
---
paper_title: On polynomial time bounded truth-table reducibility of NP sets to sparse sets

paper_content:

We prove that if P # NP, then there exists a set in NP that is polynomial time bounded truth-table reducible (in short, <Ft,-reducible) to no sparse set. In other words, we prove that no sparse <[tt-hard set exists for NP unless P = NP. By using the technique proving this result, we investigate intractability of several number theoretic decision problems, i.e., decision problems defined naturally from number theoretic problems. We show that for those number theoretic decision problems, if it is not in P, then it is _<Ft,-reducible to no sparse set.
---
paper_title: Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy

paper_content:

Several problems concerning superpolynomial size circuits and superpolynomial-time advice classes are investigated. First we consider the implications of NP (and other fundamental complexity classes) having circuits slighter bigger than polynomial. We prove that if such circuits exist, for example if NP has n logn size circuits, the exponential hierarchy collapses to the second level. Next we consider the consequences of the bottom levels of the exponential hierarchy being contained in small advice classes. Again various collapses result. For example, if EXP NP \(\subseteq\)EXP/poly then EXP NP =EXP.
---
paper_title: Hardness Amplification for Errorless Heuristics

paper_content:

Production of optically pure D-leucine and L-leucine ester by treating a racemic mixture of N-acyl-D,L-leucine ester with a proteolytic enzyme and separating the resulting N-acyl-L-leucine and N-acyl-D-leucine ester from the solution with subsequent removal of the N-acyl and ester groups to provide L-leucine and D-leucine, respectively.
---
paper_title: Competing Provers Yield Improved Karp-Lipton Collapse Results

paper_content:

Via competing provers, we show that if a language A is self-reducible and has polynomial-size circuits then S2A = S2. Building on this, we strengthen the Kamper-AFK theorem, namely, we prove that if NP ⊆ (NP ∩ coNP)/poly then the polynomial hierarchy collapses to S2NP∩coNP. We also strengthen Yap's theorem, namely, we prove that if NP ⊆ coNP/poly then the polynomial hierarchy collapses to S2NP. Under the same assumptions, the best previously known collapses were to ZPPNP and ZPPNPNP, respectively ([SIAM Journal on Computing 28 (1) (1998) 311; Journal of Computer and System Sciences 52 (3) (1996) 421], building on [Proceedings of the 12th ACM Symposium on Theory of Computing, ACM Press, New York, 1980, pp. 302-309; Journal of Computer and System Sciences 39 (1989) 21; Theoretical Computer Science 85 (2) (1991) 305; Theoretical Computer Science 26 (3) (1983) 287]). It is known that S2 ⊆ ZPPNP [Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Silver Spring, MD, 2001, pp. 620-629]. That result and its relativized version show that our new collapses indeed improve the previously known results. The Kamper-AFK theorem and Yap's theorem are used in the literature as bridges in a variety of results--ranging from the study of unique solutions to issues of approximation--and so our results implicitly strengthen those results.
---
paper_title: Average case complete problems

paper_content:

Many interesting combinatorial problems were found to be NP-complete. Since there is little hope to solve them fast in the worst case, researchers look for algorithms which are fast just “on average,” This matter is sensitive to the choice of a particular NP-complete problem and a probability distribution of its instances. Some of these tasks are easy and some not. But one needs a way to distinguish the “difficult on average” problems. Such negative results could not only save “positive” efforts but may also be used in areas (like cryptography) where hardness of some problems is a frequent assumption. It is shown in [1] that the Tiling problem with uniform distribution of instances has no polynominal “on average” algorithm, unless every NP-problem with every simple probability distribution has it.
---
paper_title: Relativized Separations of Worst-Case and Average-Case Complexities for NP

paper_content:

Non-relativization of complexity issues can beinterpreted as showing that these issues cannot be resolvedby "black-box" techniques. We show that the assumptionDistNP is contained in AvgP does not imply that NP =RP byrelativizing techniques. More precisely, we give an oraclerelative to which the assumption holds but the conclusionfails. Moreover, relative to our oracle, there are problems inthe intersection of NP and CoNP that require exponential circuit complexity.We also give an alternate version where DistNP is contained in AvgPis true, but a problem in the second level of the polynomialhierarchy is hard on the uniform distribution.
---
paper_title: On Isomorphisms and Density of $NP$ and Other Complete Sets

paper_content:

If all $NP$ complete sets are isomorphic under deterministic polynomial time mappings (p-isomorphic) then $P \ne NP$ and if all PTAPE complete sets are P-isomorphic then $P \ne {\text{PTAPE}}$. We show that all $NP$ complete sets known (in the literature) are indeed p-isomorphic and so are the known PTAPE complete sets. This shows that, in spite of the radically different origins and attempted simplification of these sets, all the known $NP$ complete sets are identical but for simple isomorphic codings computable in deterministic polynomial time.Furthermore, if all $NP$ complete sets are p-isomorphic then they all must have similar densities and, for example, no language over a single letter alphabet can be $NP$ complete, nor can any sparse language over an arbitrary alphabet be $NP$ complete. We show that complete sets in EXPTIME and EXPTAPE cannot be sparse and therefore they cannot be over a single letter alphabet. Similarly, we show that the hardest context-sensitive languages cannot be sparse. We als...
---
paper_title: Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis

paper_content:

A set S ⊂ Σ∗ is sparse if there is a polynomial p such that the number of strings in S of length at most n is at most p(n). All known NP-complete sets, such as SAT, are polynomial-time isomorphic and are not sparse. The main result of this paper is that if there is a sparse NP-complete set under polynomial-time many-one reductions, then P = NP. We also show that if there is a sparse NP-complete set under polynomial-time Turing reductions, then the polynomial-time hierarchy collapses to Δ2P.
---
paper_title: Search versus Decision for Election Manipulation Problems

paper_content:

Most theoretical definitions about the complexity of manipulating elections focus on the decision problem of recognizing which instances can be successfully manipulated rather than the search problem of finding the successful manipulative actions. Since the latter is a far more natural goal for manipulators, that definitional focus may be misguided if these two complexities can differ. Our main result is that they probably do differ: If P ≠ NP ∩ coNP (which itself is well known to hold if integer factoring is hard), then for election manipulation, election bribery, and some types of election control, there are election systems for which the problem of recognizing which instances can be successfully manipulated is polynomial-time solvable, yet the task of producing the successful manipulations cannot be done in polynomial time.
---
paper_title: Derandomizing polynomial identity tests means proving circuit lower bounds

paper_content:

We show that derandomizing Polynomial Identity Testing is, essentially, equivalent to proving circuit lower bounds for NEXP. More precisely, we prove that if one can test in polynomial time (or, even, nondeterministic subexponential time, infinitely often) whether a given arithmetic circuit over integers computes an identically zero polynomial, then either (i) NEXP ⊄ P/poly or (ii) Permanent is not computable by polynomial-size arithmetic circuits. We also prove a (partial) converse: If Permanent requires superpolynomial-size arithmetic circuits, then one can test in subexponential time whether a given arithmetic formula computes an identically zero polynomial.Since Polynomial Identity Testing is a coRP problem, we obtain the following corollary: If RP=P (or, even, coRP⊆ ∩ e > 0 NTIME(2(ne)), infinitely often), then NEXP is not computable by polynomial-size arithmetic circuits. Thus, establishing that RP=coRP or BPP=P would require proving superpolynomial lower bounds for Boolean or arithmetic circuits. We also show that any derandomization of RNC would yield new circuit lower bounds for a language in NEXP.
---
paper_title: Derandomization That is Rarely Wrong From Short Advice That is Typically Good

paper_content:

For every ∈ > 0, we present a deterministic log-space algorithm that correctly decides undirected graph connectivity on all but at most 2 n ∈ of the n- vertex graphs. The same holds for every problem in Symmetric Log-space (i.e., SL.
---
paper_title: Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds

paper_content:

The area of derandomization attempts to provide efficient deterministic simulations of randomized algorithms in various algorithmic settings. Goldreich and Wigderson introduced a notion of “typically-correct” deterministic simulations, which are allowed to err on few inputs. In this paper, we further the study of typically-correct derandomization in two ways. ::: ::: First, we develop a generic approach for constructing typically-correct derandomizations based on seed-extending pseudorandom generators, which are pseudorandom generators that reveal their seed. We use our approach to obtain both conditional and unconditional typically-correct derandomization results in various algorithmic settings. We show that our technique strictly generalizes an earlier approach by Shaltiel based on randomness extractors and simplifies the proofs of some known results. We also demonstrate that our approach is applicable in algorithmic settings where earlier work did not apply. For example, we present a typically-correct polynomial-time simulation for every language in BPP based on a hardness assumption that is (seemingly) weaker than the ones used in earlier work. ::: ::: Second, we investigate whether typically-correct derandomization of BPP implies circuit lower bounds. Extending the work of Kabanets and Impagliazzo for the zero-error case, we establish a positive answer for error rates in the range considered by Goldreich and Wigderson. In doing so, we provide a simpler proof of the zero-error result. Our proof scales better than the original one and does not rely on the result by Impagliazzo, Kabanets, and Wigderson that NEXP having polynomialsize circuits implies that NEXP coincides with EXP.
---
paper_title: Undirected connectivity in log-space

paper_content:

We present a deterministic, log-space algorithm that solves st-connectivity in undirected graphs. The previous bound on the space complexity of undirected st-connectivity was log4/3(ṡ) obtained by Armoni, Ta-Shma, Wigderson and Zhou (JACM 2000). As undirected st-connectivity is complete for the class of problems solvable by symmetric, nondeterministic, log-space computations (the class SL), this algorithm implies that SL = L (where L is the class of problems solvable by deterministic log-space computations). Independent of our work (and using different techniques), Trifonov (STOC 2005) has presented an O(log n log log n)-space, deterministic algorithm for undirected st-connectivity. ::: Our algorithm also implies a way to construct in log-space a fixed sequence of directions that guides a deterministic walk through all of the vertices of any connected graph. Specifically, we give log-space constructible universal-traversal sequences for graphs with restricted labeling and log-space constructible universal-exploration sequences for general graphs.
---
paper_title: The intractability of resolution

paper_content:

Abstract We prove that, for infinitely many disjunctive normal form propositional calculus tautologies ξ, the length of the shortest resolution proof of ξ cannot be bounded by any polynomial of the length of ξ. The tautologies we use were introduced by Cook and Reckhow (1979) and encode the pigeonhole principle. Extended resolution can furnish polynomial length proofs of these formulas.
---
paper_title: Satisfiability Solvers

paper_content:

Publisher Summary The past few years have seen enormous progress in the performance of Boolean satisfiability (SAT) solvers. Despite the worst-case exponential run time of all known algorithms, satisfiability solvers are increasingly leaving their mark as a general-purpose tool in areas as diverse as software and hardware verification, automatic test-pattern generation, planning, scheduling, and even challenging problems from algebra. Annual SAT competitions have led to the development of dozens of clever implementations of such solvers, exploration of new techniques, and creation of an extensive suite of real-world instances as well as challenging hand-crafted benchmark problems. Modern SAT solvers provide a black-box procedure that can often solve hard structured problems with over a million variables and several million constraints. This chapter describes the main solution techniques used in modern SAT solvers, classifying them as complete and incomplete methods. It discusses recent insights explaining the effectiveness of these techniques on practical SAT encodings and presents several extensions of the SAT approach currently under development. These extensions further expand the range of applications to include multiagent and probabilistic reasoning.
---
paper_title: Resolution lower bounds for the weak pigeonhole principle

paper_content:

We prove that any Resolution proof for the weak pigeonhole principle, with n holes and any number of pigeons, is of length Ω(2ne), (for some global constant e > 0). One corollary is that a certain propositional formulation of the statement NP ⊄ P/poly does not have short Resolution proofs.
---
paper_title: The Complexity of Propositional Proofs

paper_content:

An electrode for use in an organic cell is provided by forming a thin film of a metal such as aluminum on the sheet of an organic electroconductive material such as polyacetylene by, for example, a vacuum evaporation method, and then forming an atom-interdiffused layer at the interface between the sheet and the thin film by a recoil ion implantation method, thereby enhancing the current collecting efficiency of the electrode.
---
paper_title: The efficiency of resolution and Davis-Putnam procedures

paper_content:

We consider several problems related to the use of resolution-based methods for determining whether a given boolean formula in conjunctive normal form is satisfiable. First, building on the work of Clegg, Edmonds, and Impagliazzo in [Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, Philadelphia, PA, 1996, ACM, New York, 1996, pp. 174--183], we give an algorithm for unsatisfiability that when given an unsatisfiable formula of F finds a resolution proof of F. The runtime of our algorithm is subexponential in the size of the shortest resolution proof of F. Next, we investigate a class of backtrack search algorithms for producing resolution refutations of unsatisfiability, commonly known as Davis--Putnam procedures, and provide the first asymptotically tight average-case complexity analysis for their behavior on random formulas. In particular, for a simple algorithm in this class, called ordered DLL, we prove that the running time of the algorithm on a randomly generated k-CNF formula with n variables and m clauses is $2^{\Theta(n(n/m)^{1/(k-2)})}$ with probability $1-o(1)$. Finally, we give new lower bounds on $\mbox{res}(F)$, the size of the smallest resolution refutation of F, for a class of formulas representing the pigeonhole principle and for randomly generated formulas. For random formulas, Chvatal and Szemeredi [J. ACM, 35 (1988), pp. 759--768] had shown that random 3-CNF formulas with a linear number of clauses require exponential size resolution proofs, and Fu [On the Complexity of Proof Systems, Ph. D. thesis, University of Toronto, Toronto, ON, Canada, 1995] extended their results to k-CNF formulas. These proofs apply only when the number of clauses is $\Omega(n \log n)$. We show that a lower bound of the form $2^{n^{\gamma}}$ holds with high probability even when the number of clauses is $n^{(k+2)/4-\epsilon}$.
---
paper_title: Truth vs. Proof in Computational Complexity

paper_content:

Theoretical Computer Science is blessed (or cursed?) with many open problems. For some of these questions, such as the P vs NP problem, it seems like it could be decades or more before they reach resolution. So, if we have no proof either way, what do we assume about the answer? We could remain agnostic, saying that we simply don’t know, but there can be such a thing as too much skepticism in science. For example, Scott Aaronson once claimed [Aar10] that in other sciences P 6= NP would by now have been declared a law of nature. I tend to agree. After all, we are trying to uncover the truth about the nature of computation and this quest won’t go any faster if we insist on discarding all evidence that is not in the form of mathematical proofs from first principles.
---
paper_title: Linear upper bounds for random walk on small density random 3-CNFs

paper_content:

We analyze the efficiency of the random walk algorithm on random 3-CNF instances, and prove linear upper bounds on the running time of this algorithm for small clause density, less than 1.63. Our upper bound matches the observed running time to within a multiplicative factor. This is the first sub-exponential upper bound on the running time of a local improvement algorithm on random instances. Our proof introduces a simple, yet powerful tool for analyzing such algorithms, which may be of further use. This object, called a terminator, is a weighted satisfying assignment. We show that any CNF having a good (small weight) terminator is assured to be solved quickly by the random walk algorithm. This raises the natural question of the terminator threshold which is the maximal clause density for which such assignments exist (with high probability). We use the analysis of the pure literal heuristic presented by Broder, Frieze and Upfal and show that for small clause densities good terminators exist. Thus we show that the pure literal threshold (/spl ap/ 1.63) is a lower bound on the terminator threshold. One nice property of terminators is that they can be found efficiently, via linear programming. This makes tractable the future investigation of the terminator threshold, and also provides an efficiently computable certificate for short running time of the simple random-walk heuristic.
---
paper_title: Towards a study of low-complexity graphs ?

paper_content:

We propose the study of graphs that are defined by low-complexity distributed and deterministic agents. We suggest that this viewpoint may help introduce the element of individual choice in models of large scale social networks. This viewpoint may also provide interesting new classes of graphs for which to design algorithms. ::: ::: We focus largely on the case where the "low complexity" computation is AC 0. We show that this is already a rich class of graphs that includes examples of lossless expanders and power-law graphs. We give evidence that even such low complexity graphs present a formidable challenge to algorithms designers. On the positive side, we show that many algorithms from property testing and data sketching can be adapted to give meaningful results for low-complexity graphs.
---
paper_title: Short proofs are narrow—resolution made simple

paper_content:

The width of a Resolution proof is defined to be the maximal number of literals in any clause of the proof. In this paper, we relate proof width to proof length (=size), in both general Resolution, and its tree-like variant. The following consequences of these relations reveal width as a crucial “resource” of Resolution proofs. In one direction, the relations allow us to give simple, unified proofs for almost all known exponential lower bounds on size of resolution proofs, as well as several interesting new ones. They all follow from width lower bounds, and we show how these follow from natural expansion property of clauses of the input tautology. In the other direction, the width-size relations naturally suggest a simple dynamic programming procedure for automated theorem proving—one which simply searches for small width proofs. This relation guarantees that the runnuing time (and thus the size of the produced proof) is at most quasi-polynomial in the smallest tree-like proof. This algorithm is never much worse than any of the recursive automated provers (such as DLL) used in practice. In contrast, we present a family of tautologies on which it is exponentially faster.
---
paper_title: Parity, circuits, and the polynomial-time hierarchy

paper_content:

A super-polynomial lower bound is given for the size of circuits of fixed depth computing the parity function. Introducing the notion of polynomial-size, constant-depth reduction, similar results are shown for the majority, multiplication, and transitive closure functions. Connections are given to the theory of programmable logic arrays and to the relativization of the polynomial-time hierarchy.
---
paper_title: Boosting Combinatorial Search Through Randomization

paper_content:

Unpredictability in the running time of complete search procedures can often be explained by the phenomenon of "heavy-tailed cost distributions", meaning that at any time during the experiment there is a non-negligible probability of hitting a problem that requires exponentially more time to solve than any that has been encountered before (Gomes et al. 1998a). We present a general method for introducing controlled randomization into complete search algorithms. The "boosted" search methods provably eliminate heavy-tails to the right of the median. Furthermore, they can take advantage of heavy-tails to the left of the median (that is, a nonnegligible chance of very short runs) to dramatically shorten the solution time. We demonstrate speedups of several orders of magnitude for state-of-the-art complete search procedures running on hard, real-world problems.
---
paper_title: Backdoors to Satisfaction

paper_content:

A backdoor set is a set of variables of a propositional formula such that fixing the truth values of the variables in the backdoor set moves the formula into some polynomial-time decidable class. If we know a small backdoor set we can reduce the question of whether the given formula is satisfiable to the same question for one or several easy formulas that belong to the tractable class under consideration. In this survey we review parameterized complexity results for problems that arise in the context of backdoor sets, such as the problem of finding a backdoor set of size at most k, parameterized by k. We also discuss recent results on backdoor sets for problems that are beyond NP.
---
paper_title: Linear Programming: Foundations and Extensions

paper_content:

Preface. Part 1: Basic Theory - The Simplex Method and Duality. 1. Introduction. 2. The Simplex Method. 3. Degeneracy. 4. Efficiency of the Simplex Method. 5. Duality Theory. 6. The Simplex Method in Matrix Notation. 7. Sensitivity and Parametric Analyses. 8. Implementation Issues. 9. Problems in General Form. 10. Convex Analysis. 11. Game Theory. 12. Regression. Part 2: Network-Type Problems. 13. Network Flow Problems. 14. Applications. 15. Structural Optimization. Part 3: Interior-Point Methods. 16. The Central Path. 17. A Path-Following Method. 18. The KKT System. 19. Implementation Issues. 20. The Affine-Scaling Method. 21. The Homogeneous Self-Dual Method. Part 4: Extensions. 22. Integer Programming. 23. Quadratic Programming. 24. Convex Programming. Appendix A: Source Listings. Answers to Selected Exercises. Bibliography. Index.
---

Title: SIGACT News Complexity Theory Column 76: an atypical survey of typical-case heuristic algorithms

Section 1: Introduction
Description 1: Provide context for the survey, introducing the problem of finding polynomial-time deterministic algorithms for NP-hard problems and describing the scenario of heuristic algorithms that are "almost never wrong."

Section 2: Quite Old Complexity Results that Limit the Performance of Heuristic Algorithms
Description 2: Discuss historical complexity results that indicate limitations on the asymptotic error frequency of deterministic heuristic algorithms for NP-hard problems.

Section 3: Polynomial Error Frequency
Description 3: Explain key research findings regarding the impossibility of polynomial-time heuristic algorithms for NP-hard problems achieving low polynomial error frequencies.

Section 4: Subexponential Error Frequency
Description 4: Explore research on quasi-polynomial and subexponential error frequencies, and discuss their implications for heuristic algorithms for NP-hard problems.

Section 5: Padding, and What Error Frequencies Can We Expect?
Description 5: Address the "padding" technique and realistic error frequencies for NP-hard problems, along with the broader implications on complexity classes.

Section 6: The 1970s, Berman-Hartmanis, and Inheritance of Frequency of Correctness: If I'm Frequently Easy, Then So Are All These Famous Problems
Description 6: Discuss the historical significance of Berman-Hartmanis results and their implications on the frequency of correctness for heuristic algorithms.

Section 7: Deterministic Heuristic Algorithms for Problems Solvable With Randomness
Description 7: Compare deterministic heuristics for NP-hard problems with those for problems solvable with randomization (BPP), including insights from research on derandomization.

Section 8: When Heuristics Fail Often in Theory But Work Well In Reality
Description 8: Address the dichotomy between theoretical failure of heuristics in worst-case scenarios and their success in solving practical instances, particularly focusing on SAT solvers.

Section 9: Compressible Instances
Description 9: Propose models based on the compressibility of SAT instances, examining how real-world structures can lead to efficiently solvable instances despite theoretical hardness.

Section 10: The Distance from Practical Instances to Theoretically Easy Instances
Description 10: Introduce the concept of backdoor sets and discuss the relationship between practical solvability of SAT instances and their closeness to theoretically easy instances.