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).
Original languageEnglish
Title of host publicationSTACS 94 (STACS 1994)
Pages439-448
Number of pages10
DOIs
StatePublished - 1 Jan 1994

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Nature
Volume775
ISSN (Print)0302-9743

ID: 127142139