Eylem Seç
The Computational Complexity of Presburger Arithmetic
Başlık:
The Computational Complexity of Presburger Arithmetic
Yazar:
Nguyen Luu, Danh, author.
ISBN:
9780438081598
Yazar Ek Girişi:
Fiziksel Tanımlama:
1 electronic resource (238 pages)
Genel Not:
Source: Dissertation Abstracts International, Volume: 79-11(E), Section: B.
Advisors: Igor Pak Committee members: Matthias Aschenbrenner; Artem Chernikov; Igor Pak; Alexander Sherstov.
Özet:
A wide variety of problems in Discrete Optimization and Integer Programming can be naturally phrased in the language of Presburger Arithmetic (PA), which is the first order logic on the integers with only additions and inequalities. Understanding the exact computational complexity of PA is a classical topic in both logic and computer science. In this dissertation, we give answers to several open questions in this area.
Most important in PA are the numbers of variables and inequalities involved. The main question addressed in Part I of the dissertation is: By restricting the number of variables and inequalities in PA, do we obtain polynomial complexity? We give a negative solution to this, which also settles two questions by Kannan and Barvinok--Woods on Parametric Integer Programming and Short Presburger Arithmetic, respectively. Our argument combines elements from Number Theory and Discrete Geometry. As applications, we apply our tools to analyze the VC-dimensions of PA formulas, as well as a variant theory, called Parametric Presburger Arithmetic..
In Part II, we investigate the related theory of Short Generating Functions developed by Barvinok and Woods. First, we first extend their polynomial time algorithm for enumerating projected integer points in polytopes to the unbounded polyhedra case. Then we demon- strate several limitations of their general theory under simple point set operations such as projection and union, in the sense that the lengths of the generating functions do not remain polynomially bounded. The reasoning here parallels with Part I, and crucially exploits the structures of PA definable sets.
In Part III, we present two different problems. The first one concerns an extension of PA with scalar multiplications by algebraic irrationals. We show that it has high nonelementary complexity far exceeding that of classical PA, even with a restricted number of variables and inequalities. The second problem is about minimizing the number of integer points in a polytope under translation. We show that it is NP-hard by embedding arbitrary polynomial functions as integer point counting functions of polytopes. We derive from this a consequence about the universality of Ehrhart quasi-polynomials. .
Notlar:
School code: 0031
Konu Başlığı:
Tüzel Kişi Ek Girişi:
Mevcut:*
Yer Numarası | Demirbaş Numarası | Shelf Location | Lokasyon / Statüsü / İade Tarihi |
---|---|---|---|
XX(694678.1) | 694678-1001 | Proquest E-Tez Koleksiyonu | Arıyor... |
On Order
Liste seç
Bunu varsayılan liste yap.
Öğeler başarıyla eklendi
Öğeler eklenirken hata oldu. Lütfen tekrar deneyiniz.
:
Select An Item
Data usage warning: You will receive one text message for each title you selected.
Standard text messaging rates apply.