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 条
  • [31] Exponential Lower Bounds for Policy Iteration
    Fearnley, John
    AUTOMATA, LANGUAGES AND PROGRAMMING, PT II, 2010, 6199 : 551 - 562
  • [32] Tight Double Exponential Lower Bounds
    Bliznets, Ivan
    Hecher, Markus
    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2024, 2024, 14637 : 124 - 136
  • [33] Oblique projections: formulas, algorithms, and error bounds
    Kayalar, Selahattin
    Weinert, Howard L.
    Mathematics of Control, Signals, and Systems, 1989, 2 (01) : 33 - 45
  • [34] PRINCIPLE OF OBTAINING LOWER BOUNDS OF THE COMPLEXITY OF FORMULAS
    MAMATOV, IA
    DOKLADY AKADEMII NAUK SSSR, 1979, 245 (04): : 782 - 784
  • [35] On some lower bounds and approximation formulas for n!
    Obaid, Mustafa A.
    LIFE SCIENCE JOURNAL-ACTA ZHENGZHOU UNIVERSITY OVERSEAS EDITION, 2012, 9 (03): : 743 - 745
  • [36] NEW FORMULAS FOR LOWER BOUNDS TO EXPECTATION VALUES
    WEINHOLD, F
    PHYSICAL REVIEW, 1969, 183 (01): : 142 - &
  • [37] Asymptotic lower bounds and formulas for diophantine inequalities
    Freeman, DE
    NUMBER THEORY FOR THE MILLENNIUM II, 2002, : 57 - 74
  • [38] Better lower bounds for monotone threshold formulas
    Radhakrishnan, J
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1997, 54 (02) : 221 - 226
  • [39] Solving Random Satisfiable 3CNF Formulas in Expected Polynomial Time
    Krivelevich, Michael
    Vilenchik, Dan
    PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2006, : 454 - +
  • [40] On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds [Extended Abstract]
    Chen, Lijie
    Rothblum, Ron D.
    Tell, Roei
    Yogev, Eylon
    2020 IEEE 61ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2020), 2020, : 13 - 23
12345