本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
對前饋布林電路的隨機實例進行了分析和數值研究。眾所周知，評估這些電路是一個 P 完全問題，因此，在最壞的情況下，即使給定大規模並行計算機，在遠小於電路深度的時間內，也被認為是不可能執行的。儘管如此，我們發現，對於一些隨機電路的集合，很快就會飽和到固定的真值，因此可以在比電路深度少得多的並行時間內完成電路的評估。對於其他係綜，不會發生飽和，電路評估顯然很困難。特別是，對於一些由五個或更多輸入的連接詞組成的隨機電路，每一層的真實輸出數都是一個混沌序列。最後，雖然平均情況複雜性取決於係綜的選擇，但結果表明，對於所有係綜，可以在多對數並行時間內同時建立典型電路及其解決方案。