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