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

McGill University
RAS - Steklov Mathematical Institute

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

17 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	Theory of Computing Systems
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 - https://www.scopus.com/pages/publications/77951498733

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

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 - Theory of Computing Systems

JF - Theory of Computing Systems

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