Fungsi carian sedang dalam pembinaan.
Fungsi carian sedang dalam pembinaan.

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

A Satisfiability Algorithm for Synchronous Boolean Circuits Algoritma Kepuasan untuk Litar Boolean Segerak

Hiroki MORIZUMI

  • pandangan teks lengkap

    0

  • Petikan Ini

Ringkasan:

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).

Jawatankuasa
IEICE TRANSACTIONS on Information Vol.E104-D No.3 pp.392-393
Tarikh penerbitan
2021/03/01
Diumumkan
2020/11/02
ISSN dalam talian
1745-1361
DOI
10.1587/transinf.2020FCL0004
Jenis Manuskrip
Special Section LETTER (Special Section on Foundations of Computer Science — New Trends of Theory of Computation and Algorithm —)
kategori

Pengarang

Hiroki MORIZUMI
  Shimane University

Kata kunci

Contents [show]