文献

J-GLOBAL ID：202202222499033935   整理番号：22A0917431

最小公式サイズ問題は(ETH)ハードである【JST・京大機械翻訳】

The Minimum Formula Size Problem is (ETH) Hard

著者 (1件)： Ilango Rahul (MIT,Cambridge,USA)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2022  号： FOCS  ページ： 427-432  発行年： 2022年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 長年の未解決問題は,最小回路サイズ問題(MCSP)がNP完全であるかどうかである。事実,MCSPが探索対決定低減を持つかどうかは20年以上にわたって公開されている。指数的時間仮説の下で,最小(DeMorgan)公式サイズ問題,MFSPはこれにP.建築物でないので,MFSPは多項式時間(正確な)探索対決定低減を持ち,その結果,回復しないことを示した。著者らの主な手法は,関連する全関数の式の複雑さと部分関数の公式複雑性を関連させ,BuchfuhrerとUmansの”葉重み付け”技術を用いて証明した。Copyright 2022 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *重みづけ
準シソーラス用語： 多項式時間 ,  未解決問題 , 【Automatic Indexing@JST】

分類 (1件)： 図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (1件)： サイズ