scientific article; zbMATH DE number 3814972
From MaRDI portal
Publication:3662618
zbMATH Open0515.68040MaRDI QIDQ3662618FDOQ3662618
Authors: Michael Sipser 
Publication date: 1982
Title of this publication is not available (Why is that?)
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Cited In (26)
- Towards a unified complexity theory of total functions
- Separating complexity classes with tally oracles
- The 1-versus-2 queries problem revisited
- Dot operators
- A uniform approach to define complexity classes
- A characterization of the leaf language classes
- Capturing complexity classes with Lindström quantifiers
- Relativized counting classes: Relations among thresholds, parity, and mods
- On the complexity of the parity argument and other inefficient proofs of existence
- Robust algorithms: a different approach to oracles
- Complexity classes without machines: on complete languages for UP
- On the relative complexity of hard problems for complexity classes without complete problems
- A note on complete problems for complexity classes
- LWPP and WPP are not uniformly gap-definable
- A general method to construct oracles realizing given relationships between complexity classes
- Error-bounded probabilistic computations between MA and AM
- On complete problems, relativizations and logics for complexity classes
- Relativizing relativized computations
- Towards a Unified Complexity Theory of Total Functions
- Relativization of Gurevich’s Conjectures
- Computational tameness of classical non-causal models
- On the complexity of ranking
- Hard languages in NP \(\cap\) coNP and NIZK proofs from unstructured hardness
- Parity, circuits, and the polynomial-time hierarchy
- On an optimal quantified propositional proof system nal proof system and a complete language for NP ∩ co-NP for NP ∩ co-NP
- On complete one-way functions
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3662618)
