本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：工作論文
- 編號：工作論文 #885
- 日期：2026-03-18
摘要
我們研究解方程式和確定程序在固定有限廬半群上的可滿足性的計算複雜度。我們透過展示可解非冪零群子類的擬多項式時間演算法來部分回答[4]的開放性問題，並將這個問題與自然電路複雜性猜想連結起來。在 $M$ 是非週期的特殊情況下，我們表明，當廬半群屬於變數 $DA$ 時，「程式可滿足性」在 $P$ 中，否則是 NP 完全的。相反，我們給出了一個非週期外部 $DA$ 的例子，其中「方程式可滿足性」可以在多項式時間內計算，並討論兩個問題的相對複雜性。我們也研究了這些問題屬於 $P$ 的類別的閉包性質，以及這些問題無法形成代數簇的程度。