New NP-hard and NP-complete polynomial and integer divisibility problems (Q1062447): Difference between revisions

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.