The solvability problem for quadratic equations over free groups is NP-complete

O. Kharlampovich; I. G. Lysënok; A. G. Myasnikov; N. W.M. Touikan

doi:10.1007/s00224-008-9153-7

The solvability problem for quadratic equations over free groups is NP-complete

O. Kharlampovich, I. G. Lysënok, A. G. Myasnikov, N. W.M. Touikan

Department of Mathematical Sciences

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

15 Scopus citations

Abstract

We prove that the problems of deciding whether a quadratic equation over a free group has a solution is NP-complete.

Original language	English
Pages (from-to)	250-258
Number of pages	9
Journal	Mathematical Systems Theory
Volume	47
Issue number	1
DOIs	https://doi.org/10.1007/s00224-008-9153-7
State	Published - Jul 2010

Keywords

Equations over free groups
NP-completeness

Access to Document

10.1007/s00224-008-9153-7

Cite this

@article{768a9040e29f4672b84f3eed7d1c243f,

title = "The solvability problem for quadratic equations over free groups is NP-complete",

abstract = "We prove that the problems of deciding whether a quadratic equation over a free group has a solution is NP-complete.",

keywords = "Equations over free groups, NP-completeness",

author = "O. Kharlampovich and Lys{\"e}nok, {I. G.} and Myasnikov, {A. G.} and Touikan, {N. W.M.}",

year = "2010",

month = jul,

doi = "10.1007/s00224-008-9153-7",

language = "English",

volume = "47",

pages = "250--258",

number = "1",

}

TY - JOUR

T1 - The solvability problem for quadratic equations over free groups is NP-complete

AU - Kharlampovich, O.

AU - Lysënok, I. G.

AU - Myasnikov, A. G.

AU - Touikan, N. W.M.

PY - 2010/7

Y1 - 2010/7

N2 - We prove that the problems of deciding whether a quadratic equation over a free group has a solution is NP-complete.

AB - We prove that the problems of deciding whether a quadratic equation over a free group has a solution is NP-complete.

KW - Equations over free groups

KW - NP-completeness

UR - http://www.scopus.com/inward/record.url?scp=77951498733&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77951498733&partnerID=8YFLogxK

U2 - 10.1007/s00224-008-9153-7

DO - 10.1007/s00224-008-9153-7

M3 - Article

AN - SCOPUS:77951498733

SN - 1432-4350

VL - 47

SP - 250

EP - 258

JO - Mathematical Systems Theory

JF - Mathematical Systems Theory

IS - 1

ER -

The solvability problem for quadratic equations over free groups is NP-complete

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this