The complexity of almost linear diophantine problems
type: Item
instance of: scholarly article
title: The complexity of almost linear diophantine problems
zbMATH Open document ID: 0716.68050
DOI: 10.1016/S0747-7171(08)80051-X
author: Volker Weispfenning
published in: Journal of Symbolic Computation
publication date: 1990-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03F30
Mathematics Subject Classification ID: 11Y16
zbMATH DE Number: 4180804
zbMATH Keywords: Presburger arithmetic
zbMATH Keywords: complexity bounds
MaRDI profile type: MaRDI publication profile
cites work: Contributions to the theory of Diophantine equations II. The Diophantine equation y 2 = x 3 + k
cites work: The complexity of logical theories
cites work: Q3952057
cites work: Q5674430
cites work: A Decision Procedure for the First Order Theory of Real Addition with Order
cites work: The computational complexity of logical theories
cites work: Q4082296
cites work: The complexity of Presburger arithmetic with bounded quantifier alternation depth
cites work: A Bound on Solutions of Linear Integer Equalities and Inequalities
cites work: An NP-Complete Number-Theoretic Problem
cites work: The Diophantine Problem for Addition and Divisibility
cites work: Q4063432
cites work: Presburger arithmetic with bounded quantifier alternation
cites work: Complexity of Subcases of Presburger Arithmetic
cites work: On the SUP-INF Method for Proving Presburger Formulas
cites work: The polynomial-time hierarchy
cites work: Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories
Recommended article: The Computational Complexity of Simultaneous Diophantine Approximation Problems
Recommended article: On polynomial-time solvable linear Diophantine problems
Recommended article: Hardness of approximating the minimum solutions of linear Diophantine equations
Recommended article: Generic complexity of the Diophantine problem
Recommended article: The complexity of linear problems in fields
Recommended article: Q5005133
Recommended article: Q3197949
Recommended article: On the complexity of linear arithmetic with divisibility
Recommended article: Q4941892
Recommended article: On the complexity of recognizing the Hilbert basis of a linear Diophantine system
description: scientific article; zbMATH DE number 4180804