DOI

We introduce and study two classifications refining the polynomial hierarchy. Both extend the difference hierarchy over NP and are analogs of some hierarchies from recursion theory. We answer some natural questions on the introduced classifications, e.g. we extend the result of J.Kadin that the difference hierarchy over NP does not collapse (if the polynomial hierarchy does not collapse).
Язык оригиналаанглийский
Название основной публикацииSTACS 94 (STACS 1994)
Страницы439-448
Число страниц10
DOI
СостояниеОпубликовано - 1 янв 1994

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ИздательSpringer Nature
Том775
ISSN (печатное издание)0302-9743

ID: 127142139