New NP-hard and NP-complete polynomial and integer divisibility problems
type: Item
instance of: scholarly article
title: New NP-hard and NP-complete polynomial and integer divisibility problems
zbMATH Open document ID: 0572.68027
DOI: 10.1016/0304-3975(84)90130-0
published in: Theoretical Computer Science
publication date: 1984-01-01T00:00:00Z
review text: The author continues his research of two previous papers [J. Comput. Syst. Sci. 14, 210-221 (1977; Zbl 0359.65043); SIAM J. Comput. 7, 458-464 (1978; Zbl 0386.68049)] showing new problems involving sparse polynomials and integer divisibility to be NP-hard. Using a result of Linnik, which gives a polynomial upper bound for the smallest prime in arithmetic progression, the author proves NP-completeness of a problem involving an unbounded number of sparse polynomials. This problem was previously known to be NP-hard. Additional problems involving recurrence relations, differential equations, eigenvalues of sparse matrices and more are also shown to be NP-hard.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 12D05
zbMATH DE Number: 3913671
zbMATH Keywords: NP-hardness
zbMATH Keywords: sparse polynomials
zbMATH Keywords: integer divisibility
zbMATH Keywords: NP-completeness
zbMATH Keywords: recurrence relations
zbMATH Keywords: differential equations
zbMATH Keywords: eigenvalues of sparse matrices
author: David A. Plaisted
reviewed by: Giora Slutzki
MaRDI profile type: Publication
full work available at URL: 0304-3975(84)90130-0
OpenAlex ID: W2031046967
cites work: Q4198056
cites work: Q4142699
cites work: Q4135671
cites work: Q5612629
cites work: Q3231252
cites work: Q5844339
cites work: Q4162483
cites work: Some Polynomial and Integer Divisibility Problems are $NP$-Hard
cites work: Sparse complex polynomials and polynomial reducibility
cites work: Every Prime Has a Succinct Certificate
description: scientific article; zbMATH DE number 3913671