The Experts below are selected from a list of 1488 Experts worldwide ranked by ideXlab platform
Paul Beame - One of the best experts on this subject based on the ideXlab platform.
-
Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space
SIAM Journal on Computing, 2016Co-Authors: Paul Beame, Chris Beck, Russell ImpagliazzoAbstract:We give the first time-space trade-off lower bounds for Resolution proofs that apply to superlinear space. In particular, we show that there are formulas of size $N$ that have Resolution Refutations of size (and space) $T(N)= N^{\Theta(\log N)}$ (and like all formulas have another Resolution Refutation of space $N$) but for which no Resolution Refutation can simultaneously have space $S(N) = T(N)^{o(1)}$ and size $T(N)^{O(1)}$. In other words, any substantial reduction in space results in a super-polynomial increase in total size. We also show somewhat stronger time-space trade-off lower bounds for regular Resolution, which are also the first to apply to superlinear space. For any function $T$ that is at most weakly exponential, $T(N) = 2^{o(N^{1/4})}$, we give a tautology that has regular Resolution proofs of size and space $T(N)$, but no such proofs with space $S(N) = T(N)^{1-\Omega(1)}$ and size $T(N)^{O(1)}$. Thus, any polynomial reduction in space has a superpolynomial cost in size. These tautologies...
-
AAAI - Non-restarting SAT solvers with simple preprocessing can efficiently simulate Resolution
2014Co-Authors: Paul Beame, Ashish SabharwalAbstract:Propositional satisfiability (SAT) solvers based on conflict directed clause learning (CDCL) implicitly produce Resolution Refutations of unsatisfiable formulas. The precise class of formulas for which they can produce polynomial size Refutations has been the subject of several studies, with special focus on the clause learning aspect of these solvers. The results, however, assume the use of non-standard and nonasserting learning schemes, or rely on polynomially many restarts for simulating individual steps of a Resolution Refutation, or work with a theoretical model that significantly deviates from certain key aspects of all modern CDCL solvers such as learning only one asserting clause from each conflict and other techniques such as conflict guided backjumping and phase saving. We study non-restarting CDCL solvers that learn only one asserting clause per conflict and show that, with simple preprocessing that depends only on the number of variables of the input formula, such solvers can polynomially simulate Resolution. We show, moreover, that this preprocessing allows one to convert any CDCL solver to one that is non-restarting.
-
time space tradeoffs in Resolution superpolynomial lower bounds for superlinear space
Symposium on the Theory of Computing, 2012Co-Authors: Paul Beame, Chris Beck, Russell ImpagliazzoAbstract:We give the first time-space tradeoff lower bounds for Resolution proofs that apply to superlinear space. In particular, we show that there are formulas of size N that have Resolution Refutations of space and size each roughly Nlog2 N (and like all formulas have Resolution Refutations of space N) for which any Resolution Refutation using space S and length T requires T ≥ (N0.58 log2 N/S)Ω(log log N/log log log N). By downward translation, a similar tradeoff applies to all smaller space bounds. We also show somewhat stronger time-space tradeoff lower bounds for Regular Resolution, which are also the first to apply to superlinear space. Namely, for any space bound S at most 2o(N1/4) there are formulas of size $N$, having clauses of width 4, that have Regular Resolution proofs of space S and slightly larger size T=O(NS), but for which any Regular Resolution proof of space S1-e requires length TΩ(log log N/ log log log N).
-
STOC - Time-space tradeoffs in Resolution: superpolynomial lower bounds for superlinear space
Proceedings of the 44th symposium on Theory of Computing - STOC '12, 2012Co-Authors: Paul Beame, Chris Beck, Russell ImpagliazzoAbstract:We give the first time-space tradeoff lower bounds for Resolution proofs that apply to superlinear space. In particular, we show that there are formulas of size N that have Resolution Refutations of space and size each roughly Nlog2 N (and like all formulas have Resolution Refutations of space N) for which any Resolution Refutation using space S and length T requires T ≥ (N0.58 log2 N/S)Ω(log log N/log log log N). By downward translation, a similar tradeoff applies to all smaller space bounds. We also show somewhat stronger time-space tradeoff lower bounds for Regular Resolution, which are also the first to apply to superlinear space. Namely, for any space bound S at most 2o(N1/4) there are formulas of size $N$, having clauses of width 4, that have Regular Resolution proofs of space S and slightly larger size T=O(NS), but for which any Regular Resolution proof of space S1-e requires length TΩ(log log N/ log log log N).
-
simplified and improved Resolution lower bounds
Foundations of Computer Science, 1996Co-Authors: Paul Beame, Toniann PitassiAbstract:We give simple new lower bounds on the lengths of Resolution proofs for the pigeonhole principle and for randomly generated formulas. For random formulas, our bounds significantly extend the range of formula sizes for which non-trivial lower bounds are known. For example, we show that with probability approaching 1, any Resolution Refutation of a randomly chosen 3-CNF formula with at most n/sup 6/5-/spl epsiv// clauses requires exponential size. Previous bounds applied only when the number of clauses was at most linear in the number of variables. For the pigeonhole principle our bound is a small improvement over previous bounds. Our proofs are more elementary than previous arguments, and establish a connection between Resolution proof size and maximum clause size.
Alexander Nadel - One of the best experts on this subject based on the ideXlab platform.
-
Form Methods Syst Des DOI 10.1007/s10703-015-0224-5 Efficient generation of small interpolants in CNF
2016Co-Authors: Yakir Vizel Alex, Yakir Vizel, Vadim Ryvchin, Alexander Nadel, Er Nadel Vadim RyvchinAbstract:Abstract Interpolation-based model checking (ITP) McMillan (in CAV, 2003) is an efficient and complete model checking procedure. However, for large problems, interpolants gener-ated by ITP might become extremely large, rendering the procedure slow or even intractable. In this work we present a novel technique for interpolant generation in the context of model checking. The main novelty of our work is that we generate small interpolants in conjunctive normal form (CNF) using a twofold procedure: first we propose an algorithm that exploits Resolution Refutation properties to compute an interpolant approximation. Then we introduce an algorithm that takes advantage of inductive reasoning to turn the interpolant approxima-tion into an interpolant. Unlike ITP, our approach maintains only the relevant subset of the Resolution Refutation. In addition, the second part of the procedure exploits the properties of the model checking problem at hand, in contrast to the general-purpose algorithm used in ITP. We developed a new interpolation-based model checking algorithm, called CNF-ITP. Our algorithm takes advantage of the smaller interpolants and exploits the fact that the inter-polants are given in CNF. We integrated our method into a SAT-based model checker and experimented with a representative subset of the HWMCC’12 benchmark set. Our experi
-
Efficient generation of small interpolants in CNF
Formal Methods in System Design, 2015Co-Authors: Yakir Vizel, Alexander Nadel, Vadim RyvchinAbstract:Interpolation-based model checking (ITP) McMillan (in CAV, 2003) is an efficient and complete model checking procedure. However, for large problems, interpolants generated by ITP might become extremely large, rendering the procedure slow or even intractable. In this work we present a novel technique for interpolant generation in the context of model checking. The main novelty of our work is that we generate small interpolants in conjunctive normal form (CNF) using a twofold procedure: first we propose an algorithm that exploits Resolution Refutation properties to compute an interpolant approximation. Then we introduce an algorithm that takes advantage of inductive reasoning to turn the interpolant approximation into an interpolant. Unlike ITP, our approach maintains only the relevant subset of the Resolution Refutation. In addition, the second part of the procedure exploits the properties of the model checking problem at hand, in contrast to the general-purpose algorithm used in ITP. We developed a new interpolation-based model checking algorithm, called CNF-ITP. Our algorithm takes advantage of the smaller interpolants and exploits the fact that the interpolants are given in CNF. We integrated our method into a SAT-based model checker and experimented with a representative subset of the HWMCC'12 benchmark set. Our experiments show that, overall, the interpolants generated by our method are 117 times smaller than those generated by ITP. Our CNF-ITP algorithm outperforms ITP, and at times solves problems that ITP cannot solve. We also compared CNF-ITP to the successful IC3 Bradely (in VMCAI, volume 6538 of lecture notes in computer science, 2011) algorithm. We found that CNF-ITP outperforms IC3 Bradely (in VMCAI, volume 6538 of lecture notes in computer science, 2011) in a large number of cases.
-
efficient generation of small interpolants in cnf
Computer Aided Verification, 2013Co-Authors: Yakir Vizel, Vadim Ryvchin, Alexander NadelAbstract:Interpolation-based model checking (ITP) [14] is an efficient and complete model checking procedure. However, for large problems, interpolants generated by ITP might become extremely large, rendering the procedure slow or even intractable. In this work we present a novel technique for interpolant generation in the context of model checking. The main novelty of our work is that we generate small interpolants in Conjunctive Normal Form (CNF) using a twofold procedure: First we propose an algorithm that exploits Resolution Refutation properties to compute an interpolant approximation. Then we introduce an algorithm that takes advantage of inductive reasoning to turn the interpolant approximation into an interpolant. Unlike ITP, our approach maintains only the relevant subset of the Resolution Refutation. In addition, the second part of the procedure exploits the properties of the model checking problem at hand, in contrast to the general-purpose algorithm used in ITP. We developed a new interpolation-based model checking algorithm, called CNF-ITP. Our algorithm takes advantage of the smaller interpolants and exploits the fact that the interpolants are given in CNF. We integrated our method into a SAT-based model checker and experimented with a representative subset of the HWMCC'12 benchmark set. Our experiments show that, overall, the interpolants generated by our method are 42 times smaller than those generated by ITP. Our CNF-ITP algorithm outperforms ITP, and at times solves problems that ITP cannot solve. We also compared CNF-ITP to the successful IC3 [3] algorithm. We found that CNF-ITP outperforms IC3 [3] in a large number of cases.
-
CAV - Efficient Generation of Small Interpolants in CNF
Computer Aided Verification, 2013Co-Authors: Yakir Vizel, Vadim Ryvchin, Alexander NadelAbstract:Interpolation-based model checking (ITP) [14] is an efficient and complete model checking procedure. However, for large problems, interpolants generated by ITP might become extremely large, rendering the procedure slow or even intractable. In this work we present a novel technique for interpolant generation in the context of model checking. The main novelty of our work is that we generate small interpolants in Conjunctive Normal Form (CNF) using a twofold procedure: First we propose an algorithm that exploits Resolution Refutation properties to compute an interpolant approximation. Then we introduce an algorithm that takes advantage of inductive reasoning to turn the interpolant approximation into an interpolant. Unlike ITP, our approach maintains only the relevant subset of the Resolution Refutation. In addition, the second part of the procedure exploits the properties of the model checking problem at hand, in contrast to the general-purpose algorithm used in ITP. We developed a new interpolation-based model checking algorithm, called CNF-ITP. Our algorithm takes advantage of the smaller interpolants and exploits the fact that the interpolants are given in CNF. We integrated our method into a SAT-based model checker and experimented with a representative subset of the HWMCC'12 benchmark set. Our experiments show that, overall, the interpolants generated by our method are 42 times smaller than those generated by ITP. Our CNF-ITP algorithm outperforms ITP, and at times solves problems that ITP cannot solve. We also compared CNF-ITP to the successful IC3 [3] algorithm. We found that CNF-ITP outperforms IC3 [3] in a large number of cases.
-
A Scalable Algorithm for Minimal Unsatisfiable Core Extraction
arXiv: Logic in Computer Science, 2006Co-Authors: Nachum Dershowitz, Ziyad Hanna, Alexander NadelAbstract:We propose a new algorithm for minimal unsatisfiable core extraction, based on a deeper exploration of Resolution-Refutation properties. We provide experimental results on formal verification benchmarks confirming that our algorithm finds smaller cores than suboptimal algorithms; and that it runs faster than those algorithms that guarantee minimality of the core.
Russell Impagliazzo - One of the best experts on this subject based on the ideXlab platform.
-
Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space
SIAM Journal on Computing, 2016Co-Authors: Paul Beame, Chris Beck, Russell ImpagliazzoAbstract:We give the first time-space trade-off lower bounds for Resolution proofs that apply to superlinear space. In particular, we show that there are formulas of size $N$ that have Resolution Refutations of size (and space) $T(N)= N^{\Theta(\log N)}$ (and like all formulas have another Resolution Refutation of space $N$) but for which no Resolution Refutation can simultaneously have space $S(N) = T(N)^{o(1)}$ and size $T(N)^{O(1)}$. In other words, any substantial reduction in space results in a super-polynomial increase in total size. We also show somewhat stronger time-space trade-off lower bounds for regular Resolution, which are also the first to apply to superlinear space. For any function $T$ that is at most weakly exponential, $T(N) = 2^{o(N^{1/4})}$, we give a tautology that has regular Resolution proofs of size and space $T(N)$, but no such proofs with space $S(N) = T(N)^{1-\Omega(1)}$ and size $T(N)^{O(1)}$. Thus, any polynomial reduction in space has a superpolynomial cost in size. These tautologies...
-
time space tradeoffs in Resolution superpolynomial lower bounds for superlinear space
Symposium on the Theory of Computing, 2012Co-Authors: Paul Beame, Chris Beck, Russell ImpagliazzoAbstract:We give the first time-space tradeoff lower bounds for Resolution proofs that apply to superlinear space. In particular, we show that there are formulas of size N that have Resolution Refutations of space and size each roughly Nlog2 N (and like all formulas have Resolution Refutations of space N) for which any Resolution Refutation using space S and length T requires T ≥ (N0.58 log2 N/S)Ω(log log N/log log log N). By downward translation, a similar tradeoff applies to all smaller space bounds. We also show somewhat stronger time-space tradeoff lower bounds for Regular Resolution, which are also the first to apply to superlinear space. Namely, for any space bound S at most 2o(N1/4) there are formulas of size $N$, having clauses of width 4, that have Regular Resolution proofs of space S and slightly larger size T=O(NS), but for which any Regular Resolution proof of space S1-e requires length TΩ(log log N/ log log log N).
-
STOC - Time-space tradeoffs in Resolution: superpolynomial lower bounds for superlinear space
Proceedings of the 44th symposium on Theory of Computing - STOC '12, 2012Co-Authors: Paul Beame, Chris Beck, Russell ImpagliazzoAbstract:We give the first time-space tradeoff lower bounds for Resolution proofs that apply to superlinear space. In particular, we show that there are formulas of size N that have Resolution Refutations of space and size each roughly Nlog2 N (and like all formulas have Resolution Refutations of space N) for which any Resolution Refutation using space S and length T requires T ≥ (N0.58 log2 N/S)Ω(log log N/log log log N). By downward translation, a similar tradeoff applies to all smaller space bounds. We also show somewhat stronger time-space tradeoff lower bounds for Regular Resolution, which are also the first to apply to superlinear space. Namely, for any space bound S at most 2o(N1/4) there are formulas of size $N$, having clauses of width 4, that have Regular Resolution proofs of space S and slightly larger size T=O(NS), but for which any Regular Resolution proof of space S1-e requires length TΩ(log log N/ log log log N).
Neil Thapen - One of the best experts on this subject based on the ideXlab platform.
-
Random Resolution Refutations
computational complexity, 2019Co-Authors: Pavel Pudlák, Neil ThapenAbstract:We study the random Resolution Refutation system defined in Buss et al . (J Symb Logic 79(2):496–525, 2014 ). This attempts to capture the notion of a Resolution Refutation that may make mistakes but is correct most of the time. By proving the equivalence of several different definitions, we show that this concept is robust. On the other hand, if $${{\bf P} \neq {\bf NP}}$$ P ≠ NP , then random Resolution cannot be polynomially simulated by any proof system in which correctness of proofs is checkable in polynomial time. We prove several upper and lower bounds on the width and size of random Resolution Refutations of explicit and random unsatisfiable CNF formulas. Our main result is a separation between polylogarithmic width random Resolution and quasipolynomial size Resolution, which solves the problem stated in Buss et al . ( 2014 ). We also prove exponential size lower bounds on random Resolution Refutations of the pigeonhole principle CNFs, and of a family of CNFs which have polynomial size Refutations in constant-depth Frege.
-
Computational Complexity Conference - Random Resolution Refutations
Electronic Colloquium on Computational Complexity, 2017Co-Authors: Pavel Pudlák, Neil ThapenAbstract:We study the random Resolution Refutation system definedin [Buss et al. 2014]. This attempts to capture the notion of a Resolution Refutation that may make mistakes but is correct most of the time. By proving the equivalence of several different definitions, we show that this concept is robust. On the other hand, if P does not equal NP, then random Resolution cannot be polynomially simulated by any proof system in which correctness of proofs is checkable in polynomial time. We prove several upper and lower bounds on the width and size of random Resolution Refutations of explicit and random unsatisfiable CNF formulas. Our main result is a separation between polylogarithmic width random Resolution and quasipolynomial size Resolution, which solves the problem stated in [Buss et al. 2014]. We also prove exponential size lower bounds on random Resolution Refutations of the pigeonhole principle CNFs, and of a family of CNFs which have polynomial size Refutations in constant depth Frege.
-
Total Space in Resolution
SIAM Journal on Computing, 2016Co-Authors: Ilario Bonacina, Nicola Galesi, Neil ThapenAbstract:We show quadratic lower bounds on the total space used in Resolution Refutations of random $k$-CNFs over $n$ variables and of the graph pigeonhole principle and the bit pigeonhole principle for $n$ holes. This answers the open problem of whether there are families of $k$-CNF formulas of polynomial size that require quadratic total space in Resolution. The results follow from a more general theorem showing that, for formulas satisfying certain conditions, in every Resolution Refutation there is a memory configuration containing many clauses of large width.
-
FOCS - Total Space in Resolution
2014 IEEE 55th Annual Symposium on Foundations of Computer Science, 2014Co-Authors: Ilario Bonacina, Nicola Galesi, Neil ThapenAbstract:We show quadratic lower bounds on the total space used in Resolution Refutations of random k-CNFs over n variables, and of the graph pigeonhole principle and the bit pigeonhole principle for n holes. This answers the long-standing open problem of whether there are families of k-CNF formulas of polynomial size which require quadratic total space in Resolution. The results follow from a more general theorem showing that, for formulas satisfying certain conditions, in every Resolution Refutation there is a memory configuration containing many clauses of large width.
Ilario Bonacina - One of the best experts on this subject based on the ideXlab platform.
-
SETH and Resolution
Banff International Research Station for Mathematical Innovation and Discovery, 2020Co-Authors: Ilario BonacinaAbstract:There are unsatisfiable $k$-CNF formulas in n variables such that each regular Resolution Refutation of those has size at least $2^{n(1 - c_k)}$ where where $c_k$ goes to 0 as $k$ goes to infinity. The problem of finding $k$-CNF formulas for which we can prove such strong size lower bounds in Resolution (or stronger systems) is open. A lower bound of this form for Resolution would imply that CDCL solvers cannot disprove the Strong Exponential Time Hypothesis. In this talk we give a simple proof of the result for regular Resolution with the idea in mind to attack the problem for general Resolution (or stronger systems). (Talk based on joint works with Navid Talebanfard)Non UBCUnreviewedAuthor affiliation: UPC Universitat Politècnica de CatalunyaPostdoctora
-
Space proof complexity for random 3-CNFs
Information and Computation, 2017Co-Authors: Patrick Bennett, Ilario Bonacina, Nicola Galesi, Tony Huynh, Michael Molloy, Paul WollanAbstract:Abstract We investigate the space complexity of refuting 3-CNFs in Resolution and algebraic systems. We prove that every Polynomial Calculus with Resolution Refutation of a random 3-CNF φ in n variables requires, with high probability, Ω ( n ) distinct monomials to be kept simultaneously in memory. The same construction also proves that every Resolution Refutation of φ requires, with high probability, Ω ( n ) clauses each of width Ω ( n ) to be kept at the same time in memory. This gives a Ω ( n 2 ) lower bound for the total space needed in Resolution to refute φ. These results are best possible (up to a constant factor) and answer questions about space complexity of 3-CNFs. The main technical innovation is a variant of Hall's Lemma. We show that in bipartite graphs with bipartition ( L , R ) and left-degree at most 3, L can be covered by certain families of disjoint paths, called VW -matchings, provided that L expands in R by a factor of ( 2 − ϵ ) , for ϵ 1 5 .
-
ICALP - Total Space in Resolution Is at Least Width Squared
2016Co-Authors: Ilario BonacinaAbstract:Given an unsatisfiable k-CNF formula phi we consider two complexity measures in Resolution: width and total space. The width is the minimal W such that there exists a Resolution Refutation of phi with clauses of at most W literals. The total space is the minimal size T of a memory used to write down a Resolution Refutation of phi where the size of the memory is measured as the total number of literals it can contain. We prove that T = Omega((W - k)^2).
-
Total Space in Resolution
SIAM Journal on Computing, 2016Co-Authors: Ilario Bonacina, Nicola Galesi, Neil ThapenAbstract:We show quadratic lower bounds on the total space used in Resolution Refutations of random $k$-CNFs over $n$ variables and of the graph pigeonhole principle and the bit pigeonhole principle for $n$ holes. This answers the open problem of whether there are families of $k$-CNF formulas of polynomial size that require quadratic total space in Resolution. The results follow from a more general theorem showing that, for formulas satisfying certain conditions, in every Resolution Refutation there is a memory configuration containing many clauses of large width.
-
Improving Resolution width lower bounds for k-CNFs with applications to the Strong Exponential Time Hypothesis
Information Processing Letters, 2016Co-Authors: Ilario Bonacina, Navid TalebanfardAbstract:A Strong Exponential Time Hypothesis lower bound for Resolution has the form 2 ( 1 - ? k ) n for some k-CNF on n variables such that ? k ? 0 as k ? ∞ . For every large k we prove that there exists an unsatisfiable k-CNF formula on n variables which requires Resolution width ( 1 - O ? ( k - 1 / 3 ) ) n and hence tree-like Resolution Refutations of size at least 2 ( 1 - O ? ( k - 1 / 3 ) ) n . We also show that for every unsatisfiable k-CNF ? on n variables, there exists a tree-like Resolution Refutation of ? of size at most 2 ( 1 - ? ( 1 / k ) ) n . For every unsatisfiable k-CNF formula we give short treelike Resolution Refutations.We improve previous width lower bounds for k-CNFs.Our results provide evidence for the Strong Exponential Time Hypothesis.
