Hyper-polynomial hierarchies and the polynomial jump
| Autor: | Marcus Schaefer, Steven Homer, Stephen A. Fenner, Randall Pruim |
|---|---|
| Rok vydání: | 2001 |
| Předmět: |
Polynomial
Turing degree General Computer Science 0102 computer and information sciences 01 natural sciences Theoretical Computer Science Combinatorics symbols.namesake Operator (computer programming) Computer Science::Logic in Computer Science Limit (mathematics) 0101 mathematics Turing Mathematics PSPACE computer.programming_language Hyper-polynomial hierarchy Polynomial hierarchy Discrete mathematics 010102 general mathematics Polynomial jump 010201 computation theory & mathematics symbols Sequences of degrees computer Computer Science::Formal Languages and Automata Theory Computer Science(all) |
| Zdroj: | Theoretical Computer Science. 262(1-2):241-256 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/s0304-3975(00)00193-6 |
| Popis: | Assuming that the polynomial hierarchy (PH) does not collapse, we show the existence of ascending sequences of ptime Turing degrees of length ω 1 CK in PSPACE such that successors are polynomial jumps of their predecessors. Moreover these ptime degrees are all uniformly hard for PH. This is analogous to the hyperarithmetic hierarchy, which is defined similarly but with the (computable) Turing degrees. The lack of uniform least upper bounds for ascending sequences of ptime degrees causes the limit levels of our hyper-polynomial hierarchy to be inherently non-canonical. This problem is investigated in depth, and various possible structures for hyper-polynomial hierarchies are explicated, as are properties of the polynomial jump operator on the languages which are in PSPACE but not in PH. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect