Kolmogorov characterizations of complexity classes
type: Item
instance of: scholarly article
title: Kolmogorov characterizations of complexity classes
zbMATH Open document ID: 0727.68045
DOI: 10.1016/0304-3975(91)90282-7
author: Gerd Wechsung
author: Lane A. Hemaspaandra
published in: Theoretical Computer Science
publication date: 1991-01-01T00:00:00Z
review text: The paper uses the notion of (resource-bounded) Kolmogorov-complexity to characterize the classes \(\Theta_ k^ p=P(\Sigma_ k^ p)\)- with logarithmically many queries to the oracle. The notion of pronouncements (query answer) of an oracle machine is introduced. Its Kolmogorov complexity determines whether classes of the polynomial-time hierarchy collapse.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 4201620
zbMATH Keywords: polynomial hierarchy
zbMATH Keywords: Kolmogorov complexity
MaRDI profile type: Publication
full work available at URL: 0304-3975(91)90282-7
OpenAlex ID: W1989364208
cites work: P-Printable Sets
cites work: Probabilistic polynomial time is closed under parity reductions
cites work: On the power of parity polynomial time
cites work: Q4198056
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: Complexity classes without machines: on complete languages for UP
cites work: Sparse sets in NP-P: EXPTIME versus NEXPTIME
cites work: Q3805899
cites work: The strong exponential hierarchy collapses
cites work: \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
cites work: The complexity of optimization problems
cites work: Q3815511
cites work: A note on sparse oracles for NP
cites work: Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
cites work: Q4743737
cites work: Complexity of Presburger arithmetic with fixed quantifier dimension
cites work: A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
cites work: Relative complexity of checking and evaluating
description: scientific article; zbMATH DE number 4201620