Orientable quadratic equations in free metabelian groups

Igor Lysenok; Alexander Ushakov

doi:10.1016/j.jalgebra.2021.04.013

Orientable quadratic equations in free metabelian groups

Igor Lysenok
, Alexander Ushakov

Department of Mathematical Sciences

RAS - Steklov Mathematical Institute

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

We prove that the Diophantine problem for orientable quadratic equations in free metabelian groups is decidable and furthermore, NP-complete. In the case when the number of variables in the equation is bounded, the problem is decidable in polynomial time.

Original language	English
Pages (from-to)	303-326
Number of pages	24
Journal	Journal of Algebra
Volume	581
DOIs	https://doi.org/10.1016/j.jalgebra.2021.04.013
State	Published - 1 Sep 2021

Keywords

Diophantine problem
Free metabelian group
NP-completeness
Quadratic equation

Access to Document

10.1016/j.jalgebra.2021.04.013

Cite this

@article{a3e7ba2318a64dceacdfe9aef4f74f06,

title = "Orientable quadratic equations in free metabelian groups",

abstract = "We prove that the Diophantine problem for orientable quadratic equations in free metabelian groups is decidable and furthermore, NP-complete. In the case when the number of variables in the equation is bounded, the problem is decidable in polynomial time.",

keywords = "Diophantine problem, Free metabelian group, NP-completeness, Quadratic equation",

author = "Igor Lysenok and Alexander Ushakov",

note = "Publisher Copyright: {\textcopyright} 2021 Elsevier Inc.",

year = "2021",

month = sep,

day = "1",

doi = "10.1016/j.jalgebra.2021.04.013",

language = "English",

volume = "581",

pages = "303--326",

}

TY - JOUR

T1 - Orientable quadratic equations in free metabelian groups

AU - Lysenok, Igor

AU - Ushakov, Alexander

PY - 2021/9/1

Y1 - 2021/9/1

N2 - We prove that the Diophantine problem for orientable quadratic equations in free metabelian groups is decidable and furthermore, NP-complete. In the case when the number of variables in the equation is bounded, the problem is decidable in polynomial time.

AB - We prove that the Diophantine problem for orientable quadratic equations in free metabelian groups is decidable and furthermore, NP-complete. In the case when the number of variables in the equation is bounded, the problem is decidable in polynomial time.

KW - Diophantine problem

KW - Free metabelian group

KW - NP-completeness

KW - Quadratic equation

UR - https://www.scopus.com/pages/publications/85105293417

UR - https://www.scopus.com/pages/publications/85105293417#tab=citedBy

U2 - 10.1016/j.jalgebra.2021.04.013

DO - 10.1016/j.jalgebra.2021.04.013

M3 - Article

AN - SCOPUS:85105293417

SN - 0021-8693

VL - 581

SP - 303

EP - 326

JO - Journal of Algebra

JF - Journal of Algebra

ER -

Orientable quadratic equations in free metabelian groups

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this