New NP-hard and NP-complete polynomial and integer divisibility problems (Q1062447): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0304-3975(84)90130-0 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2031046967 / rank | |||
Normal rank | |||
Revision as of 22:54, 19 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | New NP-hard and NP-complete polynomial and integer divisibility problems |
scientific article |
Statements
New NP-hard and NP-complete polynomial and integer divisibility problems (English)
0 references
1984
0 references
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.
0 references
NP-hardness
0 references
sparse polynomials
0 references
integer divisibility
0 references
NP-completeness
0 references
recurrence relations
0 references
differential equations
0 references
eigenvalues of sparse matrices
0 references
