報 每日報告新聞網
聖塔非研究所

摘要 我們研究確定固定有限廬半群上的方程組是否有解的計算複雜度

2022-09-02 · 已發表論文 · 更新 2026/03/19 上午04:20

摘要 我們研究確定固定有限廬半群上的方程組是否有解的計算複雜度。在[6]中，顯示在群的限制情況下，如果群是阿貝爾群且是 NP 完全群，則問題是容易處理的。我們證明，在任意有限廬半群的情況下，如果該廬半群整除阿貝爾群和交換冪等廬半群的直積，則問題在 P 中，否則是 NP 完全的。在右側僅出現常數的受限情況下，我們表明，如果廬半群屬於 R 1 V L 1 類，則問題出在 P 中，否…

SFI 頁面

本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。

原文連結

論文資訊

  • 類型：已發表論文
  • 日期：2022-09-02

摘要

我們研究確定固定有限廬半群上的方程組是否有解的計算複雜度。在[6]中，顯示在群的限制情況下，如果群是阿貝爾群且是 NP 完全群，則問題是容易處理的。我們證明，在任意有限廬半群的情況下，如果該廬半群整除阿貝爾群和交換冪等廬半群的直積，則問題在 P 中，否則是 NP 完全的。在右側僅出現常數的受限情況下，我們表明，如果廬半群屬於 R-1 V L-1 類，則問題出在 P 中，否則是 NP 完全的。