scientific article
From MaRDI portal
Publication:3662618
zbMath0515.68040MaRDI QIDQ3662618
Publication date: 1982
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (25)
On the complexity of the parity argument and other inefficient proofs of existence ⋮ A characterization of the leaf language classes ⋮ Relativization of Gurevich’s Conjectures ⋮ On an optimal quantified propositional proof system nal proof system and a complete language for NP ∩ co-NP for NP ∩ co-NP ⋮ A note on complete problems for complexity classes ⋮ A general method to construct oracles realizing given relationships between complexity classes ⋮ Relativized counting classes: Relations among thresholds, parity, and mods ⋮ Computational tameness of classical non-causal models ⋮ Complexity classes without machines: on complete languages for UP ⋮ On the relative complexity of hard problems for complexity classes without complete problems ⋮ Capturing complexity classes with Lindström quantifiers ⋮ On the complexity of ranking ⋮ Towards a Unified Complexity Theory of Total Functions ⋮ Separating complexity classes with tally oracles ⋮ Towards a unified complexity theory of total functions ⋮ Parity, circuits, and the polynomial-time hierarchy ⋮ A uniform approach to define complexity classes ⋮ The 1-versus-2 queries problem revisited ⋮ On Complete Problems, Relativizations and Logics for Complexity Classes ⋮ LWPP and WPP are not uniformly gap-definable ⋮ Error-bounded probabilistic computations between MA and AM ⋮ Dot operators ⋮ On complete one-way functions ⋮ Relativizing relativized computations ⋮ Robust algorithms: a different approach to oracles
This page was built for publication:
