A satisfiability algorithm and average-case hardness for formulas over the full binary basis

DOI10.1007/s00037-013-0067-7zbMath1286.68208MaRDI QIDQ354655

Kazuhisa Seto, Suguru Tamaki

Publication date: 19 July 2013

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2433/189761

zbMATH Keywords

satisfiability; exact algorithm; average-case hardness; formula; parity gate

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)