• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Мероприятия

Семинар лаборатории теоретической информатики: "On the complexity of quantified integer programming". Докладчик: Д. Чистиков

Мероприятие завершено
На очередном семинаре лаборатории теоретической информатики в среду 20 июня состоится доклад 
Дмитрия Чистикова
"On the complexity of quantified integer programming".
Время проведения:18:10 - 19:30
Адрес мероприятия: Кочновский проезд, д. 3, ауд. 503
Заказ пропуска: evavilova@hse.ru

Аннотация

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.