scientific article; zbMATH DE number 3799016
From MaRDI portal
Publication:4743737
zbMATH Open0506.68039MaRDI QIDQ4743737FDOQ4743737
Authors: Stathis Zachos, Christos Papadimitriou 
Publication date: 1982
Title of this publication is not available (Why is that?)
Cited In (52)
- On the power of counting the total number of computation paths of NPTMs
- Weighted automata and logics meet computational complexity
- Polynomial size \(\Omega\)-branching programs and their computational power
- On Toda’s Theorem in Structural Communication Complexity
- Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
- A dichotomy for real weighted Holant problems
- \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
- Threshold circuits of small majority-depth
- Some observations on the connection between counting and recursion
- Constructive separations and their consequences
- Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
- The complexity landscape of outcome determination in judgment aggregation
- Alternating and empty alternating auxiliary stack automata.
- Stability, vertex stability, and unfrozenness for special graph classes
- Enumerative counting is hard
- Lower bounds and the hardness of counting properties
- The complexity of Kemeny elections
- Tally NP sets and easy census functions.
- Model checking for fragments of the interval temporal logic HS at the low levels of the polynomial time hierarchy
- On the probabilistic closure of the loose unambiguous hierarchy
- A note on separating the relativized polynomial time hierarchy by immune sets
- Turing machines with few accepting computations and low sets for PP
- On sparse hard sets for counting classes
- A second step towards complexity-theoretic analogs of Rice's Theorem
- A common algebraic description for probabilistic and quantum computations
- Universally serializable computation
- Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
- Kolmogorov characterizations of complexity classes
- Stathis Zachos at 70!
- Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access
- The complexity of combinatorial problems with succinct input representation
- The consequences of eliminating NP solutions
- Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2
- The strong exponential hierarchy collapses
- Quantum and classical complexity classes: Separations, collapses, and closure properties
- Structural control in weighted voting games
- Meta-kernelization with structural parameters
- On sets polynomially enumerable by iteration
- Gap-definable counting classes
- A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison
- A note on parallel queries and the symmetric-difference hierarchy.
- The complexity class θp2: Recent results and applications in AI and modal logic
- The operators min and max on the polynomial hierarchy
- On quasilinear-time complexity theory
- Counting homomorphisms to trees modulo a prime
- Barnette's conjecture through the lens of the \(Mod_k P\) complexity classes
- On the power of parity polynomial time
- The complexity of symmetric Boolean parity Holant problems (extended abstract)
- A complexity theory for feasible closure properties
- On the acceptance power of regular languages
- Modulo classes and logarithmic advice
- The complexity of computational problems about Nash equilibria in symmetric win-lose games
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 Q4743737)
