QUADRATIC EQUATIONS IN HYPERBOLIC GROUPS ARE NP-COMPLETE

被引：8

作者：

Kharlampovich, Olga ^{[1
]}

Mohajeri, Atefeh ^{[2
]}

Taam, Alexander ^{[3
,4
]}

Vdovina, Alina ^{[5
]}

机构：

[1] CUNY Hunter Coll, Dept Math & Stat, 695 Pk Ave, New York, NY 10065 USA

[2] McGill Univ, Dept Math & Stat, 805 Sherbrooke St W, Montreal, PQ H3A 0B9, Canada

[3] CUNY, Dept Math, Grad Ctr, 365 Fifth Ave, New York, NY 10016 USA

[4] Stevens Inst Technol, Dept Math Sci, Hoboken, NJ 07030 USA

[5] Newcastle Univ, Sch Math & Stat, Newcastle Upon Tyne NE1 7RU, Tyne & Wear, England

来源：

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY | 2017年 / 369卷 / 09期

基金：

英国工程与自然科学研究理事会;

关键词：

FREE-PRODUCTS; WICKS FORMS; NUMBER;

D O I：

10.1090/tran/6829

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove that in a torsion-free hyperbolic group Gamma, the length of the value of each variable in a minimal solution of a quadratic equation Q = 1 is bounded by N vertical bar Q vertical bar(3) for an orientable equation, and by N vertical bar Q vertical bar(4) for a nonorientable equation, where vertical bar Q vertical bar is the length of the equation and the constant N can be computed. We show that the problem, whether a quadratic equation in G has a solution, is in NP, and that there is a PSpace algorithm for solving arbitrary equations in Gamma. If additionally Gamma is non-cyclic, then this problem (of deciding existence of a solution) is NP-complete. We also give a slightly larger bound for minimal solutions of quadratic equations in a toral relatively hyperbolic group.

引用

页码：6207 / 6238

页数：32