The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Masalah kepuasan litar telah dikaji secara intensif sejak Ryan Williams menunjukkan hubungan antara masalah dan sempadan bawah untuk kerumitan litar. Dalam surat ini, kami membentangkan algoritma #SAT untuk litar Boolean segerak bagi n input dan s get dalam masa $2^{nleft(1 - rac{1}{2^{O(s/n)}} ight)}$ if s=o(n log n).
Hiroki MORIZUMI
Shimane University
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.
Salinan
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
Salinan
@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},}
Salinan
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 -