A Study of NP-Completeness and Undecidable Word Problems in Semigroups
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912790735749120 |
|---|---|
| author | Abdullah, Duaa Hamoud, Jasem |
| author_facet | Abdullah, Duaa Hamoud, Jasem |
| contents | In this paper we explore fundamental concepts in computational complexity theory and the boundaries of algorithmic decidability. We examine the relationship between complexity classes \textbf{P} and \textbf{NP}, where $L \in \textbf{P}$ implies the existence of a deterministic Turing machine solving $L$ in polynomial time $O(n^k)$. Central to our investigation is polynomial reducibility. Also, we demonstrate the existence of an associative calculus $A(\mathfrak{T})$ with an algorithmically undecidable word problem, where for a Turing machine $\mathfrak{T}$ computing a non-recursive function $E(x)$, we establish that $q_1 01^x v \equiv q_0 01^i v \Leftrightarrow x \in M_i$ for $i \in \{0,1\}$, where $M_i = \{x \mid E(x) = i\}$. This connection between computational complexity and algebraic undecidability illuminates the fundamental limits of algorithmic solutions in mathematics. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_22123 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Study of NP-Completeness and Undecidable Word Problems in Semigroups Abdullah, Duaa Hamoud, Jasem Computational Complexity 68R05, 05C85, 68Q15, 68Q17, 68Q25 In this paper we explore fundamental concepts in computational complexity theory and the boundaries of algorithmic decidability. We examine the relationship between complexity classes \textbf{P} and \textbf{NP}, where $L \in \textbf{P}$ implies the existence of a deterministic Turing machine solving $L$ in polynomial time $O(n^k)$. Central to our investigation is polynomial reducibility. Also, we demonstrate the existence of an associative calculus $A(\mathfrak{T})$ with an algorithmically undecidable word problem, where for a Turing machine $\mathfrak{T}$ computing a non-recursive function $E(x)$, we establish that $q_1 01^x v \equiv q_0 01^i v \Leftrightarrow x \in M_i$ for $i \in \{0,1\}$, where $M_i = \{x \mid E(x) = i\}$. This connection between computational complexity and algebraic undecidability illuminates the fundamental limits of algorithmic solutions in mathematics. |
| title | A Study of NP-Completeness and Undecidable Word Problems in Semigroups |
| topic | Computational Complexity 68R05, 05C85, 68Q15, 68Q17, 68Q25 |
| url | https://arxiv.org/abs/2512.22123 |