On the probabilistic closure of the loose unambiguous hierarchy

Edward A. Hirsch, Dmitry Sokolov

Результат исследований: Научные публикации в периодических изданияхстатья

Аннотация

Unambiguous hierarchies [1-3] are defined similarly to the polynomial hierarchy; however, all witnesses must be unique. These hierarchies have subtle differences in the mode of using oracles. We consider a "loose" unambiguous hierarchy prUH• with relaxed definition of oracle access to promise problems. Namely, we allow to make queries that miss the promise set; however, the oracle answer in this case can be arbitrary (a similar definition of oracle access has been used in [4]). In this short note we prove that the first part of Toda's theorem PH⊂BP.⊕P⊂PPP can be strengthened to PH=BP.prUH•, that is, the closure of our hierarchy under Schöning's BP operator equals the polynomial hierarchy. It is easily seen that BP.prUH•⊂BP.⊕P. The proof follows the same lines as Toda's proof, so the main contribution of the present note is a new definition that allows to characterize PH as a probabilistic closure of unambiguous computations.

Язык оригиналаанглийский
Страницы (с-по)725-730
Число страниц6
ЖурналInformation Processing Letters
Том115
Номер выпуска9
DOI
СостояниеОпубликовано - 1 сен 2015

Предметные области Scopus

  • Теоретические компьютерные науки
  • Обработка сигналов
  • Информационные системы
  • Прикладные компьютерные науки

Fingerprint Подробные сведения о темах исследования «On the probabilistic closure of the loose unambiguous hierarchy». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать