We investigate tradeoffs of various basic complexity measures such as size, space, and width. We show examples of formulas that have optimal proofs with respect to any one of these parameters, but optimizing one param...
详细信息
We investigate tradeoffs of various basic complexity measures such as size, space, and width. We show examples of formulas that have optimal proofs with respect to any one of these parameters, but optimizing one parameter must cost an increase in the other. These results have implications to the efficiency (or rather, inefficiency) of some commonly used SAT solving heuristics. Our proof relies on a novel connection of the variable space of a proof to the black-white pebbling measure of an underlying graph.
In this paper we give a new proof of Richardson's theorem [31]: a global function G(A) of a cellular automaton A is injective if and only if the inverse of G(A) is a global function of a cellular automaton. Moreov...
详细信息
In this paper we give a new proof of Richardson's theorem [31]: a global function G(A) of a cellular automaton A is injective if and only if the inverse of G(A) is a global function of a cellular automaton. Moreover, we show a way how to construct the inverse cellular automaton using the method of feasible interpolation from [20]. We also solve two problems regarding complexity of cellular automata formulated by Durand [12]. (C) 2009 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim
We investigate the substitution Frege (SF) proof system and its relationship to extended Frege (EF) in the context of modal and superintuitionistic (si) propositional logics. We show that EF is p-equivalent to tree-li...
详细信息
We investigate the substitution Frege (SF) proof system and its relationship to extended Frege (EF) in the context of modal and superintuitionistic (si) propositional logics. We show that EF is p-equivalent to tree-like SF, and we develop a "normal form" for SF-proofs. We establish connections between SF for a logic L, and EF for certain bimodal expansions of L. We then turn attention to specific families of modal and si logics. We prove p-equivalence of EF and SF for all extensions of KB, all tabular logics, all logics of finite depth and width, and typical examples of logics of finite width and infinite depth. In most cases, we actually show an equivalence with the usual EF system for classical logic with respect to a naturally defined translation. On the other hand, we establish exponential speed-up of SF over EF for all modal and si logics of infinite branching, extending recent lower bounds by P. Hrubes. We develop a model-theoretical characterization of maximal logics of infinite branching to prove this result. (C) 2008 Elsevier B.V. All rights reserved.
We demonstrate that the Cutting Plane (CP) rank of a polytope defined by a system of inequalities derived from a set of unsatisfiable clauses can be arbitrarily larger than the Resolution width of the clauses, thus de...
详细信息
ISBN:
(纸本)9783540852377
We demonstrate that the Cutting Plane (CP) rank of a polytope defined by a system of inequalities derived from a set of unsatisfiable clauses can be arbitrarily larger than the Resolution width of the clauses, thus demonstrating the two measures are incomparable. More specifically, we show there exists an infinite family of unsatisfiable clauses defined over n is an element of N, which have constant Resolution width, but, yield polytopes which have CP rank Omega(log(2) n).
We explore the relationships between the computational problem of recognizing expander graphs, and the problem of efficiently approximating proof length in the well-known system of emph{resolution}. This program build...
详细信息
We explore the relationships between the computational problem of recognizing expander graphs, and the problem of efficiently approximating proof length in the well-known system of emph{resolution}. This program builds upon known connections between graph expansion and resolution lower bounds.A proof system $P$ is emph{(quasi-)automatizable} if there is a search algorithm which finds a $P$-proof of a given formula $f$ in time (quasi)polynomial in the length of a shortest $P$-proof of $f$. It is open whether resolution is (quasi-)automatizable. We prove several conditional non-automatizability results for resolution modulo new conjectures concerning the complexity of identifying bipartite expander graphs. Our reductions use a natural family of formulas and exploit the well-known relationships between expansion and length of resolution proofs. Our hardness assumptions are unsupported; we survey known results as progress towards establishing their plausibility. The major contribution is a conditional hardness result for the quasi-automatizability of resolution
Resolution refinements called w-resolution trees with lemmas (WRTL) and with input lemmas (WRTI) are introduced. Dag-like resolution is equivalent to both WRTL and WRTI when there is no regularity condition. For regul...
详细信息
Resolution refinements called w-resolution trees with lemmas (WRTL) and with input lemmas (WRTI) are introduced. Dag-like resolution is equivalent to both WRTL and WRTI when there is no regularity condition. For regular proofs, an exponential separation between regular dag-like resolution and both regular WRTL and regular WRTI is given. It is proved that DLL proof search algorithms that use clause learning based on unit propagation can be polynomially simulated by regular WRTI. More generally, non-greedy DLL algorithms with learning by unit propagation are equivalent to regular WRTI. A general form of clause learning, called DLL-Learn, is defined that is equivalent to regular WRTL. A variable extension method is used to give simulations of resolution by regular WRTI, using a simplified form of proof trace extensions. DLL-Learn and non-greedy DLL algorithms with learning by unit propagation can use variable extensions to simulate general resolution without doing restarts. Finally, an exponential lower bound for WRTL where the lemmas are restricted to short clauses is shown.
We call a pseudorandom generator G(n) : {0, 1}(n) --> {0, 1}(m) hard for a propositionalproof system P if P cannot efficiently prove the (properly encoded) statement G(n)(x(1),..., x(n)) not equal b for any string...
详细信息
We call a pseudorandom generator G(n) : {0, 1}(n) --> {0, 1}(m) hard for a propositionalproof system P if P cannot efficiently prove the (properly encoded) statement G(n)(x(1),..., x(n)) not equal b for any string b is an element of{0, 1}(m). We consider a variety of "combinatorial" pseudorandom generators inspired by the Nisan-Wigderson generator on the one hand, and by the construction of Tseitin tautologies on the other. We prove that under certain circumstances these generators are hard for such proof systems as resolution, polynomial calculus, and polynomial calculus with resolution (PCR).
We prove that an omega (log(4) n) lower bound for the three- party number- on- the- forehead ( NOF) communication complexity of the set- disjointness function implies an n.( 1) size lower bound for treelike Lovasz - S...
详细信息
We prove that an omega (log(4) n) lower bound for the three- party number- on- the- forehead ( NOF) communication complexity of the set- disjointness function implies an n.( 1) size lower bound for treelike Lovasz - Schrijver systems that refute unsatisfiable formulas in conjunctive normal form (CNFs). More generally, we prove that an n(Omega(1)) lower bound for the ( k + 1)- party NOF communication complexity of set disjointness implies a 2(n Omega(1)) size lower bound for all treelike proof systems whose formulas are degree k polynomial inequalities.
We prove a dichotomy theorem for the rank of the uniformly generated (i.e. expressible in First-Order (170) Logic) propositional tautologies in both the Lovdsz-Schrijver (LS) and Sherali-Adams (SA) proof systems. More...
详细信息
ISBN:
(纸本)9781595936318
We prove a dichotomy theorem for the rank of the uniformly generated (i.e. expressible in First-Order (170) Logic) propositional tautologies in both the Lovdsz-Schrijver (LS) and Sherali-Adams (SA) proof systems. More precisely, we first show that the propositional translations of FO formulae that are universally trite, i.e. hold in all finite and infinite models, have LS proofs whose rank is constant, independently from the size of the (finite) universe. In contrast to that, we prove that the propositional formulae that hold in all finite models but fail in some infinite structure require proofs whose SA rank grows poly-logarithmically with the size of the universe. Up to now, this kind of so-called "complexity Gap" theorems have been known for Tree-like Resolution and, in some-how restricted forms, for the Resolution and Nullstellensatz proof systems. As far as we are aware, this is the first time the Sherali-Adams lift-and-project method has been considered as a propositionalproof system. An interesting feature of the SA proof system is that it is static and rank-preserving simulates LS, the Lovisz-Schrijver proof system without semidefinite cuts.
We consider the Sherali-Adams (SA) operator as a proof system for integer linear programming and prove linear lower bounds on the SA rank required to prove both the pigeon hole and least number principles. We also def...
详细信息
ISBN:
(纸本)9783540730002
We consider the Sherali-Adams (SA) operator as a proof system for integer linear programming and prove linear lower bounds on the SA rank required to prove both the pigeon hole and least number principles. We also define the size of a SA proof and show that that while the pigeon hole principle requires linear rank, it only requires at most polynomial size.
暂无评论