A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis

被引：12
作者：
Seto, Kazuhisa [1 ]
Tamaki, Suguru [1 ]
机构：
[1] Kyoto Univ, Grad Sch Informat, Kyoto, Japan
来源：
2012 IEEE 27TH ANNUAL CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC) | 2012年
关键词：
satisfiability; exact algorithm; formula; parity gate; average-case hardness; AFFINE EXTRACTORS; LOWER BOUNDS; K-SAT; CIRCUITS; COMPLEXITY; SEARCH; SIZE;
D O I：
10.1109/CCC.2012.29
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We present a moderately exponential time algorithm for the satisfiability of Boolean formulas over the full binary basis. For formulas of size at most cn, our algorithm runs in time 2((1-mu c)n) for some constant mu(c) > 0. As a byproduct of the running time analysis of our algorithm, we get strong average-case hardness of affine extractors for linear-sized formulas over the full binary basis.
引用
收藏
页码：107 / 116
页数：10
相关论文
共 34 条
[1]   SIGMA-11-FORMULAE ON FINITE STRUCTURES [J].
AJTAI, M .
ANNALS OF PURE AND APPLIED LOGIC, 1983, 24 (01) :1-48
[2]  
Andreev A.E., 1987, Moscow Univ. Math. Bull, V42, P63
[3]  
[Anonymous], PROBABILISTIC ALGORI
[4]  
Arvind V, 2003, LECT NOTES COMPUT SC, V2906, P168
[5]  
Biere A., 2008, HDB SATISFIABILITY
[6]   On the construction of affine extractors [J].
Bourgain, Jean .
GEOMETRIC AND FUNCTIONAL ANALYSIS, 2007, 17 (01) :33-57
[7]  
Calabro C, 2009, LECT NOTES COMPUT SC, V5917, P75, DOI 10.1007/978-3-642-11269-0_6
[8]  
Calabro C, 2006, ANN IEEE CONF COMPUT, P252
[9]  
Dantsin E, 2004, LECT NOTES COMPUT SC, V2996, P141
[10]  
DANTSIN E, 2008, HDB SATISFIABILITY
1234