DocumentCode :
2653253
Title :
A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis
Author :
Seto, Kazuhisa ; Tamaki, Suguru
Author_Institution :
Grad. Sch. of Inf., Kyoto Univ., Kyoto, Japan
fYear :
2012
fDate :
26-29 June 2012
Firstpage :
107
Lastpage :
116
Abstract :
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-μc)n for some constant μ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.
Keywords :
Boolean algebra; computability; computational complexity; Boolean formulas; affine extractors; average-case hardness; exponential time algorithm; full binary basis; linear-sized formulas; satisfiability algorithm; Algorithm design and analysis; Educational institutions; Encoding; Informatics; Logic gates; Polynomials; Reactive power; average-case hardness; exact algorithm; formula; parity gate; satisfiability;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computational Complexity (CCC), 2012 IEEE 27th Annual Conference on
Conference_Location :
Porto
ISSN :
1093-0159
Print_ISBN :
978-1-4673-1663-7
Type :
conf
DOI :
10.1109/CCC.2012.29
Filename :
6243386
Link To Document :
https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=2653253
بازگشت