Zugang zum Dokument
Borchert, Bernd ; Lange, Klaus-Joern ; Stephan, Frank ; Tesson, Pascal ; Therien, Denis:
The dot-depth and the polynomial hierarchy correspond on the delta levels
|
 PDF 193kB
|
| Zitierfähiger Link: | Bitte nutzen Sie diese URL, um auf das Dokument zu verlinken oder es zu zitieren: http://nbn-resolving.de/urn:nbn:de:bsz:21-opus-12234 |
|---|---|
| URL: | http://tobias-lib.uni-tuebingen.de/volltexte/2004/1223/ |
| Originalveröffentlichung: | WSI ; 2004-03 |
| Urheber: | Wilhelm-Schickard-Institut |
| Fachgebiet/Einrichtung: | Bereich 17 Fakultät für Informations- und Kognitionswissenschaften (ohne Institutszuordnung) |
| Dokumentart: | Report (Bericht) |
| Sprache: | Englisch |
| Erstellungsjahr: | 2004 |
| Publikationsdatum: | 17.05.2004 |
| Kurze Inhaltszusammenfassung auf Englisch | It is well-known that the Sigma_k- and Pi_k-levels of the dot-depth hierarchy and the polynomial hierarchy correspond via leaf languages. In this paper this correspondence will be extended to the Delta_k-levels of these hierarchies: Leaf^P(Delta_k^L) = Delta_k^p. |
| Kontrollierte Schlagwörter (Deutsch): | Komplexitätsklasse , Dot-Depth-Hierarchie , Straubing-Thérien-Hierarchie , Komplexitätsklasse NP |
| Freie Schlagwörter (Deutsch): | Polynomialzeit-Hierarchie |
| DDC-Sachgruppe: | Informatik |
| Lizenz: |
Veröffentlichungsvertrag (Version 1998)
|
