The complexity of the Weight Problem for permutation groups

Peter J. Cameron; Taoyang Wu

doi:10.1016/j.endm.2007.01.034

The complexity of the Weight Problem for permutation groups

Peter J. Cameron^*, Taoyang Wu

^*Corresponding author for this work

Centre for Interdisciplinary Research in Computational Algebra

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

Abstract

Given a metric d on a permutation group G, the corresponding weight problem is to decide whether there exists an element g ∈ G such that d(g, e) = k for some k ∈ N. In this paper we show that this problem is NP-complete for many well known metrics.

Original language	English
Pages (from-to)	109-116
Number of pages	8
Journal	Electronic Notes in Discrete Mathematics
Volume	28
DOIs	https://doi.org/10.1016/j.endm.2007.01.034
Publication status	Published - 1 Mar 2007

Keywords

Metrics
NP-complete
Permutation Group
Weight Problem

Access to Document

10.1016/j.endm.2007.01.034

Cite this

@article{79e149fa72b34507bab4ab9c2176a42e,

title = "The complexity of the Weight Problem for permutation groups",

abstract = "Given a metric d on a permutation group G, the corresponding weight problem is to decide whether there exists an element g ∈ G such that d(g, e) = k for some k ∈ N. In this paper we show that this problem is NP-complete for many well known metrics.",

keywords = "Metrics, NP-complete, Permutation Group, Weight Problem",

author = "Cameron, \{Peter J.\} and Taoyang Wu",

year = "2007",

month = mar,

day = "1",

doi = "10.1016/j.endm.2007.01.034",

language = "English",

volume = "28",

pages = "109--116",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

}

TY - JOUR

T1 - The complexity of the Weight Problem for permutation groups

AU - Cameron, Peter J.

AU - Wu, Taoyang

PY - 2007/3/1

Y1 - 2007/3/1

N2 - Given a metric d on a permutation group G, the corresponding weight problem is to decide whether there exists an element g ∈ G such that d(g, e) = k for some k ∈ N. In this paper we show that this problem is NP-complete for many well known metrics.

AB - Given a metric d on a permutation group G, the corresponding weight problem is to decide whether there exists an element g ∈ G such that d(g, e) = k for some k ∈ N. In this paper we show that this problem is NP-complete for many well known metrics.

KW - Metrics

KW - NP-complete

KW - Permutation Group

KW - Weight Problem

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

U2 - 10.1016/j.endm.2007.01.034

DO - 10.1016/j.endm.2007.01.034

M3 - Article

AN - SCOPUS:33847246424

SN - 1571-0653

VL - 28

SP - 109

EP - 116

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

The complexity of the Weight Problem for permutation groups

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this