Polynomial Space Counting Problems

DOI10.1137/0218073MaRDI QIDQ3034822zbMATH OpenOpenAlexFDO

Authors Richard E. Ladner

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

zbMATH Keywords

computational complexitypolynomial spaceTuring machinecounting problemsalternating Turing machinesoraclesRelativization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Recommendations

• scientific article; zbMATH DE number 4066859
• On the complexity of counting in the polynomial hierarchy
• Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
• Descriptive complexity of \(\#\)P functions
• scientific article; zbMATH DE number 1670534

Cited in

(29)

• Complexity and approximability of quantified and stochastic constraint satisfaction problems
• The Complexity of Counting Functions with Easy Decision Version
• The effect of combination functions on the complexity of relational Bayesian networks
• The complexity of iterated reversible computation
• A very hard log-space counting class
• Functions computable in polynomial space
• The complexity of counting models of linear-time temporal logic
• Descriptive complexity for counting complexity classes
• On the complexity of query result diversification
• Counting QBF solutions at level two
• Counting problems for Parikh images
• The Complexity of Computing the Size of an Interval
• Logical characterizations of weighted complexity classes
• scientific article; zbMATH DE number 4066859 (Why is no real title available?)
• Semiring reasoning frameworks in AI and their computational complexity
• Refinement-based enumeration of QBF solutions
• scientific article; zbMATH DE number 4064488 (Why is no real title available?)
• Preimage problems for reaction systems
• Descriptive complexity and weighted Turing machines
• OuterCount: a first-level solution-counter for quantified Boolean formulas
• Ancestors, descendants, and gardens of Eden in reaction systems
• Synthesis for continuous time
• On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety
• The complexity of problems for quantified constraints
• Implicit recursion-theoretic characterizations of counting classes
• The complexity of Bayesian networks specified by propositional and relational languages
• On computing the total variation distance of hidden Markov models
• FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS
• scientific article; zbMATH DE number 1953880 (Why is no real title available?)

This page was built for publication: Polynomial Space Counting Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3034822)