Seminar of the laboratory: "On the complexity of quantified integer programming". Lecturer: D. Chistikov
Event ended
On June 20, 2018 Dmitry Chistikov will give a lecture "On the complexity of quantified integer programming".
Address: Faculty of computer science HSE, Kochnovsky proezd, 3.
Language: English
Time: 18:10-19:30
Hall: 503
If you have questions, please contact the manager of the laboratory Ekaterina Vavilova: evavilova@hse.ru.
Language: English
Time: 18:10-19:30
Hall: 503
If you have questions, please contact the manager of the laboratory Ekaterina Vavilova: evavilova@hse.ru.
Abstract
Quantified integer programming is the problem of deciding assertions of the form "for all/there exists x_k ... for all x_2 there exists x_1 such that A x >= c", where vectors of variables x_k, ..., x_1 form the vector x, all variables are interpreted over N (alternatively, over Z), and A and c are a matrix and vector over Z of appropriate sizes. We show that quantified integer programming with alternation depth k is complete for the k-th level of the polynomial hierarchy.
Joint work with Christoph Haase.
Joint work with Christoph Haase.