Subset sum problem in polycyclic groups. (January 2018)

• Record Type: Journal Article
• Authors: Nikolaev, Andrey; Ushakov, Alexander
• Is Part Of: Journal of symbolic computation. Volume 84(2018)
• Page Start: 84
• Page End: 94
• Publication Date: 2018-01
• Subjects: 03D15 -- 20F65 -- 20F10 -- 20F16; Polycyclic groups -- Nilpotent groups -- Subset sum problem -- NP-completeness; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2017.03.007
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: We consider a group-theoretic analogue of the classic subset sum problem. It is known that every virtually nilpotent group has polynomial time decidable subset sum problem. In this paper we use subgroup distortion to show that every polycyclic non-virtually-nilpotent group hasNP -complete subset sum problem.