A Satisfiability Algorithm for Synchronous Boolean Circuits
Summary :
The circuit satisfiability problem has been intensively studied since Ryan Williams showed a connection between the problem and lower bounds for circuit complexity. In this letter, we present a #SAT algorithm for synchronous Boolean circuits of n inputs and s gates in time $2^{nleft(1 - rac{1}{2^{O(s/n)}} ight)}$ if s=o(n log n).
- Publication
- IEICE TRANSACTIONS on Information Vol.E104-D No.3 pp.392-393
- Publication Date
- 2021/03/01
- Publicized
- 2020/11/02
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2020FCL0004
- Type of Manuscript
- Special Section LETTER (Special Section on Foundations of Computer Science — New Trends of Theory of Computation and Algorithm —)
- Category
Authors
Hiroki MORIZUMI
Shimane University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hiroki MORIZUMI, "A Satisfiability Algorithm for Synchronous Boolean Circuits" in IEICE TRANSACTIONS on Information,
vol. E104-D, no. 3, pp. 392-393, March 2021, doi: 10.1587/transinf.2020FCL0004.
Abstract: The circuit satisfiability problem has been intensively studied since Ryan Williams showed a connection between the problem and lower bounds for circuit complexity. In this letter, we present a #SAT algorithm for synchronous Boolean circuits of n inputs and s gates in time $2^{nleft(1 - rac{1}{2^{O(s/n)}}
ight)}$ if s=o(n log n).
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2020FCL0004/_p
Copy
@ARTICLE{e104-d_3_392,
author={Hiroki MORIZUMI, },
journal={IEICE TRANSACTIONS on Information},
title={A Satisfiability Algorithm for Synchronous Boolean Circuits},
year={2021},
volume={E104-D},
number={3},
pages={392-393},
abstract={The circuit satisfiability problem has been intensively studied since Ryan Williams showed a connection between the problem and lower bounds for circuit complexity. In this letter, we present a #SAT algorithm for synchronous Boolean circuits of n inputs and s gates in time $2^{nleft(1 - rac{1}{2^{O(s/n)}}
ight)}$ if s=o(n log n).},
keywords={},
doi={10.1587/transinf.2020FCL0004},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - A Satisfiability Algorithm for Synchronous Boolean Circuits
T2 - IEICE TRANSACTIONS on Information
SP - 392
EP - 393
AU - Hiroki MORIZUMI
PY - 2021
DO - 10.1587/transinf.2020FCL0004
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E104-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2021
AB - The circuit satisfiability problem has been intensively studied since Ryan Williams showed a connection between the problem and lower bounds for circuit complexity. In this letter, we present a #SAT algorithm for synchronous Boolean circuits of n inputs and s gates in time $2^{nleft(1 - rac{1}{2^{O(s/n)}}
ight)}$ if s=o(n log n).
ER -
English
