On the Diophantine problem related to power circuits Full article
| Journal |
Groups, Complexity, Cryptology
ISSN: 1867-1144 , E-ISSN: 1869-6104 |
||
|---|---|---|---|
| Output data | Year: 2026, Volume: 18, Number: 1, Article number : 2, Pages count : 4 DOI: 10.46298/jgcc.2026.18.1.17270 | ||
| Tags | Diophantine problem, power circuit | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Russian Science Foundation | 25-11-20023 |
Abstract:
Abstract. Myasnikov, Ushakov, and Won introduced power circuits in 2012 to construct a polynomial-time algorithm for the word problem in the Baumslag group, which has a non-elementary Dehn function. Power circuits are computational structures that support addition and the operation (x,y) → x · 2y on integers. They also posed the question of decidability of the Diophantine problem over the structure ⟨N>0;+,x · 2y,≤,1⟩, which is closely related to power circuits. In this paper, we prove that the Diophantine problem over this structure is undecidable.
Cite:
Rybalov A.
On the Diophantine problem related to power circuits
Groups, Complexity, Cryptology. 2026. V.18. N1. 2 :1-4. DOI: 10.46298/jgcc.2026.18.1.17270 Scopus OpenAlex
On the Diophantine problem related to power circuits
Groups, Complexity, Cryptology. 2026. V.18. N1. 2 :1-4. DOI: 10.46298/jgcc.2026.18.1.17270 Scopus OpenAlex
Dates:
| Submitted: | Jan 12, 2026 |
| Accepted: | Apr 1, 2026 |
| Published print: | Apr 2, 2026 |
| Published online: | Apr 2, 2026 |
Identifiers:
| ≡ Scopus: | 2-s2.0-105034837429 |
| ≡ OpenAlex: | W7147172997 |