Search
Семинар 11 февраля 2005 года
Пятница, 11 февраля, комната 106. Начало в 17:30.
Докладчик: К. Первышев.
Тема: Точная иерархия по времени для вероятностных алгоритмов с подсказкой.
Abstract
Можем ли мы решить большее количество задач, используя большее количество времени? Положительный ответ на этот вопрос (т.е. строгая иерархия по времени) для синтаксических классов DTime и NTime был получен ещё в 60-70х годах с помощью диагонализации. Однако эту технику нельзя напрямую использовать с семантическими классами --- теми, для которых неизвестно эффективного способа перечисления машин, принадлежащих этим классам. В частности, на данный момент нельзя исключить случай BPTime[n]=BPP, где BPTime[t] --- класс вероятностных машин с ограниченной двусторонней ошибкой, заканчивающих работу за время t, BPP --- объединение таких классов для всех полиномов t. Такая же неопределённость имеется с классами RPTime, NTime 
coNTime, AMTime и другими.
В 2002 году Barak предложил новый подход к проблеме, доказав иерархию для классов схем (т.е. алгоритмов, использующих короткую подсказку, одну и ту же для всех входов данной длины). В 2004 году Fortnow, Santhanam и Trevisan доказали наличие иерархии для версии BPTime и RPTime с подсказкой, состоящей всего из одного бита. В докладе будет дано более простое доказательство их результатов.