本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：工作論文
- 編號：工作論文 #1196
- 日期：2026-03-18
摘要
我們考慮其閘在非關聯代數（例如擬群或迴圈）中執行乘法的電路和表達式。我們定義一類稱為多交換代數，由阿貝爾群的迭代准直積形成。我們證明擬群可以表達任意布林函數當且僅當它不是多交換函數時，在這種情況下它的「表達式求值」和「電路值」問題分別是 NC1 完全和 P 完全。對於一般代數來說，情況並非如此，我們給出一個反例。我們證明，如果代數的 TC0 既是多交換的又具有可解的乘法半群（例如，對於冪零環或冪零群），「表達式求值」也是 NC1 完全的。因此，在非關聯情況下，關於可解性在電路複雜性中的作用的早期結果以幾種不同的方式概括。