NP-complete problems for systems of linear polynomial's values divisibilities

DOI10.3103/S1063454117020078zbMath1420.68095OpenAlexW2729187770MaRDI QIDQ2402582

Nikolaĭ Nikolaevich Kosovskiĭ, M. R. Starchak, Tat'yana Matveevna Kosovskaya, N. K. Kosovskii

Publication date: 20 September 2017

Published in: Vestnik St. Petersburg University. Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3103/s1063454117020078

zbMATH Keywords

NP-completenessNP-hardnesssystem of linear polynomial's values divisibilities

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Linear Diophantine equations (11D04)

Cites Work

• The number of steps for construction of a Boolean solution to polynomial congruences and systems of polynomial congruences
• The Diophantine Problem for Addition and Divisibility
• On the Complexity of Linear Arithmetic with Divisibility
• The complexity of satisfiability problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: NP-complete problems for systems of linear polynomial's values divisibilities