Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas

被引：0
|
作者：
机构：
[1] Alekhnovich, Michael
[2] Hirsch, Edward A.
[3] Itsykson, Dmitry
来源：
Alekhnovich, M. (misha@ias.edu) | 1600年 / Kluwer Academic Publishers卷 / 35期
关键词：
Algorithms;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
引用
收藏
页码：1 / 3
相关论文
共 50 条
  • [41] Exponential Lower Bounds for AC(0)-Frege Imply Superpolynomial Frege Lower Bounds
    Filmus, Yuval
    Pitassi, Toniann
    Santhanam, Rahul
    ACM TRANSACTIONS ON COMPUTATION THEORY, 2015, 7 (02)
  • [42] EXPONENTIAL LOWER BOUNDS TO SOLUTIONS OF THE SCHRODINGER-EQUATION - LOWER BOUNDS FOR THE SPHERICAL AVERAGE
    FROESE, R
    HERBST, I
    COMMUNICATIONS IN MATHEMATICAL PHYSICS, 1983, 92 (01) : 71 - 80
  • [43] Exponential Lower Bounds and Separation for Query Rewriting
    Kikot, Stanislav
    Kontchakov, Roman
    Podolskii, Vladimir
    Zakharyaschev, Michael
    AUTOMATA, LANGUAGES, AND PROGRAMMING, ICALP 2012, PT II, 2012, 7392 : 263 - 274
  • [44] Exponential Lower Bounds for Polytopes in Combinatorial Optimization
    Fiorini, Samuel
    Massar, Serge
    Pokutta, Sebastian
    Tiwary, Hans Raj
    De Wolf, Ronald
    JOURNAL OF THE ACM, 2015, 62 (02)
  • [45] Strongly Exponential Lower Bounds for Monotone Computation
    Pitassi, Toniann
    Robere, Robert
    STOC'17: PROCEEDINGS OF THE 49TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2017, : 1246 - 1255
  • [46] Exponential Lower Bounds for Monotone Span Programs
    Robere, Robert
    Pitassi, Toniann
    Rossman, Benjamin
    Cook, Stephen A.
    2016 IEEE 57TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2016, : 406 - 415
  • [47] DLP in semigroups: Algorithms and lower bounds
    Han, Jiao
    Zhuang, Jincheng
    JOURNAL OF MATHEMATICAL CRYPTOLOGY, 2022, 16 (01) : 278 - 288
  • [48] Quantum query algorithms and lower bounds
    Ambainis, A
    Classical and New Paradigms of Computation and Their Complexity Hierarchies, 2004, 23 : 15 - 32
  • [49] Propositional lower bounds: Algorithms and complexity
    Cadoli, M
    Palopoli, L
    Scarcello, F
    ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 1999, 27 (1-4) : 129 - 148
  • [50] Lower complexity bounds for interpolation algorithms
    Gimenez, Nardo
    Heintz, Joos
    Matera, Guillermo
    Solerno, Pablo
    JOURNAL OF COMPLEXITY, 2011, 27 (02) : 151 - 187
12345