NP-completeness conditions for consistency verification of some types of systems of linear Diophantine dis-equations

DOI10.3103/S1063454116030067zbMath1426.68102OpenAlexW2529986378MaRDI QIDQ1709490

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

Publication date: 5 April 2018

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

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

zbMATH Keywords

NP-completenesssystem of linear Diophantine dis-equations

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)

Uses Software

• Refal

Cites Work

• The number of steps for construction of a Boolean solution to polynomial congruences and systems of polynomial congruences
• Efficient solution of linear diophantine equations
• Solving a System of Linear Diophantine Equations with Lower and Upper Bounds on the Variables
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• On the Complexity of Linear Arithmetic with Divisibility
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: NP-completeness conditions for consistency verification of some types of systems of linear Diophantine dis-equations