Abstract: An introduction to the problems considering complexity of simultaneous divisibilities of values of linear polynomials is presented. Some history facts, recent results and open questions that stimulate further research are discussed.

Keywords: NP-completeness, existential Presburger arithmetic with divisibility, systems of divisibilities of values of linear polynomials, quadratic diophantine equations

ACM Classification Keywords: F.1.3 Complexity Measures and Classes, Reducibility and completeness; F.2.1 Analysis of Algorithms and Problem Complexity, Numerical Algorithms and Problems, Numbertheoretic computations

Link:

Review of some problems on the complexity of simultaneous divisibility of linear polynomials

Nikolay K. Kosovskii, Mikhail Starchak

http://www.foibg.com/ijima//vol05/ijima05-03-p06.pdf