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

DOI10.3103/S1063454116030067MaRDI QIDQ1709490zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2237527 (Why is no real title available?)
• Boundary intervals method for visualization of polyhedral solution sets
• Efficient solution of linear diophantine equations
• 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
• The number of steps for construction of a Boolean solution to polynomial congruences and systems of polynomial congruences

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

Describes a project that uses

Uses Software

• Refal

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)