The word problem of the Brin-Thompson group is coNP-complete

J. C. Birget

doi:10.1016/j.jalgebra.2020.02.013

The word problem of the Brin-Thompson group is coNP-complete

J. C. Birget

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

Abstract

We prove that the word problem of the Brin-Thompson group nV over a finite generating set is coNP-complete for every n≥2. It is known that {nV:n≥1} is an infinite family of infinite, finitely presented, simple groups. We also prove that the word problem of the Thompson group V over a certain infinite set of generators, related to boolean circuits, is coNP-complete.

Original language	English (US)
Pages (from-to)	268-318
Number of pages	51
Journal	Journal of Algebra
Volume	553
DOIs	https://doi.org/10.1016/j.jalgebra.2020.02.013
State	Published - Jul 1 2020

All Science Journal Classification (ASJC) codes

Algebra and Number Theory

Keywords

Brin-Thompson group
Computational complexity
Word problem
coNP-completeness

Access to Document

10.1016/j.jalgebra.2020.02.013

Cite this

@article{060e49c34e0e423fa24eb330d9197284,

title = "The word problem of the Brin-Thompson group is coNP-complete",

abstract = "We prove that the word problem of the Brin-Thompson group nV over a finite generating set is coNP-complete for every n≥2. It is known that {nV:n≥1} is an infinite family of infinite, finitely presented, simple groups. We also prove that the word problem of the Thompson group V over a certain infinite set of generators, related to boolean circuits, is coNP-complete.",

keywords = "Brin-Thompson group, Computational complexity, Word problem, coNP-completeness",

author = "Birget, {J. C.}",

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

year = "2020",

month = jul,

day = "1",

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

language = "English (US)",

volume = "553",

pages = "268--318",

journal = "Journal of Algebra",

issn = "0021-8693",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - The word problem of the Brin-Thompson group is coNP-complete

AU - Birget, J. C.

PY - 2020/7/1

Y1 - 2020/7/1

N2 - We prove that the word problem of the Brin-Thompson group nV over a finite generating set is coNP-complete for every n≥2. It is known that {nV:n≥1} is an infinite family of infinite, finitely presented, simple groups. We also prove that the word problem of the Thompson group V over a certain infinite set of generators, related to boolean circuits, is coNP-complete.

AB - We prove that the word problem of the Brin-Thompson group nV over a finite generating set is coNP-complete for every n≥2. It is known that {nV:n≥1} is an infinite family of infinite, finitely presented, simple groups. We also prove that the word problem of the Thompson group V over a certain infinite set of generators, related to boolean circuits, is coNP-complete.

KW - Brin-Thompson group

KW - Computational complexity

KW - Word problem

KW - coNP-completeness

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

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

U2 - 10.1016/j.jalgebra.2020.02.013

DO - 10.1016/j.jalgebra.2020.02.013

M3 - Article

AN - SCOPUS:85080060439

SN - 0021-8693

VL - 553

SP - 268

EP - 318

JO - Journal of Algebra

JF - Journal of Algebra

ER -

The word problem of the Brin-Thompson group is coNP-complete

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this