| LDR | | 02269nmm uu200409 4500 |
| 001 | | 000000334091 |
| 005 | | 20240805175121 |
| 008 | | 181129s2018 |||||||||||||||||c||eng d |
| 020 | |
▼a 9780438081598 |
| 035 | |
▼a (MiAaPQ)AAI10828057 |
| 035 | |
▼a (MiAaPQ)ucla:16940 |
| 040 | |
▼a MiAaPQ
▼c MiAaPQ
▼d 248032 |
| 082 | 0 |
▼a 510 |
| 100 | 1 |
▼a Nguyen Luu, Danh. |
| 245 | 14 |
▼a The Computational Complexity of Presburger Arithmetic. |
| 260 | |
▼a [S.l.] :
▼b University of California, Los Angeles.,
▼c 2018 |
| 260 | 1 |
▼a Ann Arbor :
▼b ProQuest Dissertations & Theses,
▼c 2018 |
| 300 | |
▼a 238 p. |
| 500 | |
▼a Source: Dissertation Abstracts International, Volume: 79-11(E), Section: B. |
| 500 | |
▼a Adviser: Igor Pak. |
| 502 | 1 |
▼a Thesis (Ph.D.)--University of California, Los Angeles, 2018. |
| 520 | |
▼a 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. Understandin |
| 520 | |
▼a 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 |
| 520 | |
▼a 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 |
| 520 | |
▼a 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 res |
| 590 | |
▼a School code: 0031. |
| 650 | 4 |
▼a Mathematics. |
| 690 | |
▼a 0405 |
| 710 | 20 |
▼a University of California, Los Angeles.
▼b Mathematics 0540. |
| 773 | 0 |
▼t Dissertation Abstracts International
▼g 79-11B(E). |
| 773 | |
▼t Dissertation Abstract International |
| 790 | |
▼a 0031 |
| 791 | |
▼a Ph.D. |
| 792 | |
▼a 2018 |
| 793 | |
▼a English |
| 856 | 40 |
▼u http://www.riss.kr/pdu/ddodLink.do?id=T14999110
▼n KERIS |
| 980 | |
▼a 201812
▼f 2019 |
| 990 | |
▼a 관리자 |