Buchumschlag

A Study of NP-Completeness and Undecidable Word Problems in Semigroups

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Abdullah, Duaa, Hamoud, Jasem
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity 68R05, 05C85, 68Q15, 68Q17, 68Q25
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Algorithms for Minimum Membership Dominating Set Problem
von: Reddy, Sangam Balchandar, et al.
Veröffentlicht: (2024)

Coordinatewise Balanced Covering for Linear Gain Graphs, with an Application to Coset-List Min-2-Lin over Powers of Two
von: Alpay, Faruk, et al.
Veröffentlicht: (2026)

The Separation of $NP$ and $PSPACE$
von: Lin, Tianrong
Veröffentlicht: (2021)

Tight complexity bounds for diagram commutativity verification
von: Malko, Artem, et al.
Veröffentlicht: (2025)

The Gallai Vertex Problem is $Θ_2^p$-Complete
von: Nikabadi, Amir, et al.
Veröffentlicht: (2026)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
von: Bergougnoux, Benjamin, et al.
Veröffentlicht: (2025)

Polynomial Identity Testing via Evaluation of Rational Functions
von: Hu, Ivan, et al.
Veröffentlicht: (2022)

The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs
von: Ahn, Jungho, et al.
Veröffentlicht: (2022)

Complexity of Sequence-to-Graph Alignment with Co-Linear Chaining
von: Li, Xingfu
Veröffentlicht: (2026)

DAG Scheduling in the BSP Model
von: Papp, Pál András, et al.
Veröffentlicht: (2023)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
von: Lin, Tianrong
Veröffentlicht: (2023)

Toward P vs NP: An Observer-Theoretic Separation via SPDP Rank and a ZFC-Equivalent Foundation within the N-Frame Model
von: Edwards, Darren J.
Veröffentlicht: (2025)

On the Complexity of Bipartite Degree Realizability
von: Miklós, István
Veröffentlicht: (2025)

P not equal to NP
von: Delgado, Daniel Cardona
Veröffentlicht: (2023)

Unifying lower bounds for algebraic machines, semantically
von: Seiller, Thomas, et al.
Veröffentlicht: (2018)

Generalisations of Matrix Partitions : Complexity and Obstructions
von: Barsukov, Alexey, et al.
Veröffentlicht: (2021)

Perfect Edge Domination in $P_6$-free Graphs and in Graphs Without Efficient Edge Dominating Sets
von: Grippo, Luciano N., et al.
Veröffentlicht: (2025)

A polynomial-time algorithm for deciding the Hilbert Nullstellensatz over $\mathbb{Z}_2$. A proof of $\mathbf{P}=\mathbf{NP}$ hypothesis
von: Petrov, Petar P.
Veröffentlicht: (2022)

Completeness classes in algebraic complexity theory
von: Bürgisser, Peter
Veröffentlicht: (2024)

A non-iterative polynomial algorithm for linear programming
von: Jing-Yuan, Wei
Veröffentlicht: (2013)

A dichotomy theorem on the complexity of 3-uniform hypergraphic degree sequence graphicality
von: Logsdon, Sara, et al.
Veröffentlicht: (2024)

On 3-colorability of (claw, diamond)-free graphs
von: Hodur, Nadzieja, et al.
Veröffentlicht: (2026)

Undefinability of Approximation of 2-to-2 Games
von: Dawar, Anuj, et al.
Veröffentlicht: (2025)

Topological structure and a polynomial-time solution of linear programming over the real numbers
von: Wei, Jing-Yuan
Veröffentlicht: (2018)

Polynomial-Time Solutions for Longest Common Subsequence Related Problems Between a Sequence and a Pangenome Graph
von: Li, Xingfu, et al.
Veröffentlicht: (2026)

Cluster Vertex Deletion Problems on Cubic Graphs
von: Rusu, Irena
Veröffentlicht: (2025)

On the Complexity of the Minimum-($k,ρ$)-Shortcut Problem
von: Avila, Tatiana Rocha, et al.
Veröffentlicht: (2026)

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
von: Larrauri, Alberto
Veröffentlicht: (2025)

Optimal Hardness of Online Algorithms for Large Independent Sets
von: Gamarnik, David, et al.
Veröffentlicht: (2025)

CircuitBuilder: From Polynomials to Circuits via Reinforcement Learning
von: Zhang, Weikun K., et al.
Veröffentlicht: (2026)

Beyond the Existential Theory of the Reals
von: Schaefer, Marcus, et al.
Veröffentlicht: (2022)

Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem
von: Ilmavirta, Joonas, et al.
Veröffentlicht: (2023)

Refutation of Spectral Graph Theory Conjectures with Search Algorithms)
von: Roucairol, Milo, et al.
Veröffentlicht: (2024)

Vanishing of Schubert Coefficients
von: Pak, Igor, et al.
Veröffentlicht: (2024)

Positivity of Schubert Coefficients
von: Pak, Igor, et al.
Veröffentlicht: (2024)

Regenerative Ulam-von Neumann Algorithm: An Innovative Markov chain Monte Carlo Method for Matrix Inversion
von: Ghosh, Soumyadip, et al.
Veröffentlicht: (2024)

Efficient Algorithms for Injectivity and Bounded Surjectivity of One-dimensional Nonlinear Cellular Automata
von: Wang, Chen, et al.
Veröffentlicht: (2023)

Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs
von: Böhnlein, Toni, et al.
Veröffentlicht: (2024)

Resolution of The Linear-Bounded Automata Question
von: Lin, Tianrong
Veröffentlicht: (2021)

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
von: Lin, Tianrong
Veröffentlicht: (2021)