Polynomial Space Counting Problems
From MaRDI portal
Publication:3034822
DOI10.1137/0218073zbMath0692.68036OpenAlexW1993180032MaRDI QIDQ3034822
Publication date: 1989
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0218073
computational complexityTuring machinepolynomial spacecounting problemsalternating Turing machinesoraclesRelativization
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)
Related Items
On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety, Unnamed Item, Unnamed Item, The effect of combination functions on the complexity of relational Bayesian networks, Processing succinct matrices and vectors, OuterCount: a first-level solution-counter for quantified Boolean formulas, Ancestors, descendants, and gardens of Eden in reaction systems, The complexity of Bayesian networks specified by propositional and relational languages, The complexity of problems for quantified constraints, On Computing the Total Variation Distance of Hidden Markov Models., The complexity of counting models of linear-time temporal logic, A very hard log-space counting class, Functions computable in polynomial space, On the Complexity of Query Result Diversification, Preimage Problems for Reaction Systems, FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS, Counting problems for parikh images, Synthesis for continuous time
