scientific article; zbMATH DE number 3799016
From MaRDI portal
zbMath0506.68039MaRDI QIDQ4743737
Stathis Zachos, Christos H. Papadimitriou
Publication date: 1982
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
Alternating and empty alternating auxiliary stack automata., Stathis Zachos at 70!, A complexity theory for feasible closure properties, The operators min and max on the polynomial hierarchy, Counting Homomorphisms to Square-Free Graphs, Modulo 2, The complexity of combinatorial problems with succinct input representation, The complexity class θp2: Recent results and applications in AI and modal logic, Some observations on the connection between counting and recursion, A note on separating the relativized polynomial time hierarchy by immune sets, The complexity of computational problems about Nash equilibria in symmetric win-lose games, A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison, The complexity of computing minimal unidirectional covering sets, Universally serializable computation, On the power of parity polynomial time, Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access, Meta-kernelization with structural parameters, Stability, vertex stability, and unfrozenness for special graph classes, Unnamed Item, \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP], Barnette's conjecture through the lens of the \(Mod_k P\) complexity classes, Polynomial size \(\Omega\)-branching programs and their computational power, The consequences of eliminating NP solutions, The Complexity Landscape of Outcome Determination in Judgment Aggregation, On sets polynomially enumerable by iteration, On the acceptance power of regular languages, On quasilinear-time complexity theory, Modulo classes and logarithmic advice, Turing machines with few accepting computations and low sets for PP, Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P, Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy, On sparse hard sets for counting classes, Quantum and classical complexity classes: Separations, collapses, and closure properties, Lower bounds and the hardness of counting properties, On Toda’s Theorem in Structural Communication Complexity, The strong exponential hierarchy collapses, Model checking for fragments of the interval temporal logic HS at the low levels of the polynomial time hierarchy, The Complexity of Symmetric Boolean Parity Holant Problems, Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP, Threshold circuits of small majority-depth, Enumerative counting is hard, A second step towards complexity-theoretic analogs of Rice's Theorem, A common algebraic description for probabilistic and quantum computations, Structural control in weighted voting games, Tally NP sets and easy census functions., Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2, A note on parallel queries and the symmetric-difference hierarchy., On the probabilistic closure of the loose unambiguous hierarchy, Kolmogorov characterizations of complexity classes, Gap-definable counting classes, A dichotomy for real weighted Holant problems, The complexity of Kemeny elections
