๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

The complexity of almost linear diophantine problems

โœ Scribed by V. Weispfenning

Book ID
104344982
Publisher
Elsevier Science
Year
1990
Tongue
English
Weight
542 KB
Volume
10
Category
Article
ISSN
0747-7171

No coin nor oath required. For personal study only.

โœฆ Synopsis

We studied formulas of elementary number theory resulting from formulas of Presburger arithmetic PrA (additive elementary theory of integers with order) by substituting for some variables, polynomials and integer values of rational functions in a single new variable y, and quantifying over y. We show that the extension ALA (almost linear arithmetic) of PrA obtained in this way, has essentially the same upper and lower complexity bounds as the original theory. The same applies to the fragments of ALA obtained by restricting the number or type of quantifiers in formulas. We also show new upper complexity bounds for quantifier elimination in PrA and its fragments. The results form a common extension of known complexity bounds for PrA and for the existential almost linear problems studied by Gurari & lbarra. The method is applicable also to other extensions of PrA without order, related to the famous bounds for binary forms of A. Baker.

๐Ÿ“œ SIMILAR VOLUMES

On the Linear Diophantine Problem of Fro
On the Linear Diophantine Problem of Frobenius
โœ J.L. Davison ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 351 KB

Suppose \(a, b, c\) are three positive integers with \(\mathrm{gcd}=1\). We consider the function \(f(a, b, c)\) defined to be the largest integer not representable as a positive integral linear combination of \(a, b, c\). We give a new lower bound for \(f(a, b, c)\) which is shown to be tight, and

On a linear diophantine problem of Frobe
On a linear diophantine problem of Frobenius
โœ G.R. Hofmeister; A.M. Ibrahim; G.A. Shadia ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 117 KB
On a Linear Diophantine Problem of Frobe
On a Linear Diophantine Problem of Frobenius: Extending the Basis
โœ Stefan Matthias Ritter ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 233 KB

Let X k =[a 1 , a 2 , ..., a k ], k>1, be a subset of N such that gcd(X k )=1. We shall say that a natural number n is dependent (on X k ) if there are nonnegative integers x i such that n has a representation n= k i=1 x i a i , else independent. The Frobenius number g(X k ) of X k is the greatest i

The Computational Complexity of Some Pro
The Computational Complexity of Some Problems of Linear Algebra
โœ Jonathan F Buss; Gudmund S Frandsen; Jeffrey O Shallit ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 330 KB

We consider the computational complexity of some problems dealing with matrix rank. Let E, S be subsets of a commutative ring R. Let x 1 , x 2 , ..., x t be variables. Given a matrix M=M(x 1 , x 2 , ..., x t ) with entries chosen from E \_ [x 1 , x 2 , ..., x t ], we want to determine maxrank S (M)=