scientific article; zbMATH DE number 719756
From MaRDI portal
Publication:4321931
zbMath0826.68048MaRDI QIDQ4321931
José L. Balcázar, Joaquim Gabarró, Josep Diaz
Publication date: 6 February 1995
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (57)
Collapse of PP with a semi-random source to BPP ⋮ A degree bound on decomposable trees ⋮ Computational depth: Concept and applications ⋮ Computing queries with higher-order logics ⋮ The operators min and max on the polynomial hierarchy ⋮ The complexity of generating test instances ⋮ Nondeterministic functions and the existence of optimal proof systems ⋮ Query order in the polynomial hierarchy ⋮ On an optimal quantified propositional proof system nal proof system and a complete language for NP ∩ co-NP for NP ∩ co-NP ⋮ Unnamed Item ⋮ On efficiency of notations for natural numbers ⋮ Nonuniform reductions and NP-completeness ⋮ Recursion theoretic characterizations of complexity classes of counting functions ⋮ Average-case intractability vs. worst-case intractability ⋮ The computational complexity of QoS measures for orchestrations. The computational complexity of QoS measures ⋮ Nontriviality for exponential time w.r.t. weak reducibilities ⋮ Question answering by humans and machines: a complexity-theoretic view ⋮ How We Think of Computing Today ⋮ P-immune sets with holes lack self-reducibility properties. ⋮ On the Complexity of Equilibria Problems in Angel-Daemon Games ⋮ Upper bounds on ATSP neighborhood size. ⋮ On the Degree of Extension of Some Models Defining Non-Regular Languages ⋮ Base invariance of feasible dimension ⋮ Hard sets are hard to find ⋮ Almost complete sets. ⋮ Equilibria problems on games: complexity versus succinctness ⋮ Oracles and Advice as Measurements ⋮ Characterizing the super-Turing computing power and efficiency of classical fuzzy Turing machines ⋮ Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy ⋮ Reversal complexity revisited ⋮ Data independence of read, write, and control structures in PRAM computations ⋮ A second step toward the strong polynomial-time hierarchy ⋮ The complexity of stochastic sequences ⋮ Baire categories on small complexity classes and meager-comeager laws ⋮ On the asymmetric complexity of the group-intersection problem ⋮ Parallel algorithms for separable permutations ⋮ Expressibility of Higher Order Logics ⋮ On the degrees of non-regularity and non-context-freeness ⋮ The P\(\neq\) NP conjecture in the context of real and complex analysis ⋮ On pseudorandomness and resource-bounded measure ⋮ Prediction and dimension ⋮ Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions ⋮ If P \(\neq\) NP then some strongly noninvertible functions are invertible ⋮ Closure and nonclosure properties of the classes of compressible and rankable sets ⋮ Exponential separation of quantum and classical online space complexity ⋮ Polylog depth, highness and lowness for E ⋮ Some complexity bounds for subtype inequalities ⋮ Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets ⋮ Weak completeness notions for exponential time ⋮ The zero-one law holds for BPP ⋮ On theoretical and empirical algorithmic analysis of the efficiency gap measure in partisan gerrymandering ⋮ The Projective Noether Maple Package: Computing the dimension of a projective variety ⋮ On an optimal propositional proof system and the structure of easy subsets of TAUT. ⋮ Recursive computational depth. ⋮ Sparse sets and collapse of complexity classes ⋮ Degrees of Dowd-type generic oracles ⋮ Complexity of the \(r\)-query tautologies in the presence of a generic oracle
This page was built for publication:
