NP-completeness conditions for consistency verification of some types of systems of linear Diophantine dis-equations
DOI10.3103/S1063454116030067zbMATH Open1426.68102OpenAlexW2529986378MaRDI QIDQ1709490FDOQ1709490
Authors: Nikolai Kossovski, 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
Recommendations
- NP completeness conditions for verifying the consistency of several kinds of systems of linear Diophantine congruences and equations
- NP completeness conditions for verifying the consistency of several kinds of systems of linear Diophantine discongruences
- NP-complete problems for systems of linear polynomial's values divisibilities
- Compatibility of systems of linear constraints over the set of natural numbers
- NP-hard classes of linear algebraic systems with uncertainties
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
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the complexity of linear arithmetic with divisibility
- Solving a system of linear Diophantine equations with lower and upper bounds on the variables.
- The Computational Complexity of Simultaneous Diophantine Approximation Problems
- Efficient solution of linear diophantine equations
- The number of steps for construction of a Boolean solution to polynomial congruences and systems of polynomial congruences
- Boundary intervals method for visualization of polyhedral solution sets
- Title not available (Why is that?)
Cited In (5)
- A new PCP outer verifier with applications to homogeneous linear equations and max-bisection
- On the complexity of recognizing the Hilbert basis of a linear Diophantine system
- NP-complete problems for systems of linear polynomial's values divisibilities
- NP completeness conditions for verifying the consistency of several kinds of systems of linear Diophantine discongruences
- NP completeness conditions for verifying the consistency of several kinds of systems of linear Diophantine congruences and equations
Uses Software
This page was built for publication: NP-completeness conditions for consistency verification of some types of systems of linear Diophantine dis-equations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1709490)
