Publication:4743737
From MaRDI portal
zbMath0506.68039MaRDI QIDQ4743737
Christos H. Papadimitriou, Stathis Zachos
Publication date: 1982
DB lookup for MSC labels failed
Related Items
On the acceptance power of regular languages, On quasilinear-time complexity theory, Modulo classes and logarithmic advice, Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy, On sets polynomially enumerable by iteration, Turing machines with few accepting computations and low sets for PP, Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P, On sparse hard sets for counting classes, Threshold circuits of small majority-depth, Gap-definable counting classes, Universally serializable computation, A second step towards complexity-theoretic analogs of Rice's Theorem, A complexity theory for feasible closure properties, Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access