On the public citation graph

Polynomial Space Counting Problems

0 signed · 70 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/978-1-4684-2001-2_9openalex-snapshot
Reducibility among Combinatorial Problems
inferredcites →https://doi.org/10.1016/0304-3975(76)90061-xopenalex-snapshot
The polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(79)90043-4openalex-snapshot
A second step toward the polynomial hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(79)90044-6openalex-snapshot
The Complexity of Computing the Permanent
inferredcites →https://doi.org/10.1137/0204037openalex-snapshot
Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
inferredcites →https://doi.org/10.1137/0206054openalex-snapshot
On Relating Time and Space to Size and Depth
inferredcites →https://doi.org/10.1137/0208032openalex-snapshot
The Complexity of Enumeration and Reliability Problems
inferredcites →https://doi.org/10.1137/0214060openalex-snapshot
On Approximation Algorithms for # P
inferredcites →https://doi.org/10.1145/322234.322243openalex-snapshot
Alternation
inferredcites →https://doi.org/10.1145/800125.804029openalex-snapshot
Word problems requiring exponential time(Preliminary Report)

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/11602613_75openalex-snapshot
Recursion Theoretic Operators for Function Complexity Classes
inferred← citeshttps://doi.org/10.1007/3-540-45007-6_7openalex-snapshot
Complexity Theory Made Easy
inferred← citeshttps://doi.org/10.1007/3-540-45465-9_2openalex-snapshot
Towards a Predictive Computational Complexity Theory
inferred← citeshttps://doi.org/10.1007/3-540-48224-5_84openalex-snapshot
The Complexity of Computing the Size of an Interval
inferred← citeshttps://doi.org/10.1007/978-3-031-16681-5_19openalex-snapshot
OuterCount: A First-Level Solution-Counter for Quantified Boolean Formulas
inferred← citeshttps://doi.org/10.1007/978-3-032-04590-4_12openalex-snapshot
Refinement-Based Enumeration of QBF Solutions
inferred← citeshttps://doi.org/10.1007/978-3-319-06686-8_19openalex-snapshot
Processing Succinct Matrices and Vectors
inferred← citeshttps://doi.org/10.1007/978-3-319-15579-1_42openalex-snapshot
Preimage Problems for Reaction Systems
inferred← citeshttps://doi.org/10.1007/978-3-642-31653-1_18openalex-snapshot
From Equivalence to Almost-Equivalence, and Beyond—Minimizing Automata with Errors
inferred← citeshttps://doi.org/10.1007/978-3-662-47666-6_19openalex-snapshot
The Odds of Staying on Budget
inferred← citeshttps://doi.org/10.1007/bfb0029956openalex-snapshot
The complexity of policy evaluation for finite-horizon partially-observable Markov decision processes
inferred← citeshttps://doi.org/10.1007/s00224-009-9194-6openalex-snapshot
The Complexity of Problems for Quantified Constraints
inferred← citeshttps://doi.org/10.1007/s00224-015-9666-9openalex-snapshot
Processing Succinct Matrices and Vectors
inferred← citeshttps://doi.org/10.1007/s00236-016-0284-zopenalex-snapshot
The complexity of counting models of linear-time temporal logic
inferred← citeshttps://doi.org/10.1007/s10601-024-09369-4openalex-snapshot
Counting QBF solutions at level two
inferred← citeshttps://doi.org/10.1016/0304-3975(93)90252-oopenalex-snapshot
A very hard log-space counting class
inferred← citeshttps://doi.org/10.1016/j.artint.2018.06.001openalex-snapshot
The complexity of Bayesian networks specified by propositional and relational languages
inferred← citeshttps://doi.org/10.1016/j.ic.2005.02.002openalex-snapshot
Functions computable in polynomial space
inferred← citeshttps://doi.org/10.1016/j.ic.2026.105446openalex-snapshot
Descriptive complexity and weighted Turing machines
inferred← citeshttps://doi.org/10.1016/j.ijar.2017.03.014openalex-snapshot
The effect of combination functions on the complexity of relational Bayesian networks
inferred← citeshttps://doi.org/10.1016/j.jco.2007.03.008openalex-snapshot
On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety
inferred← citeshttps://doi.org/10.1016/j.tcs.2015.05.046openalex-snapshot
Ancestors, descendants, and gardens of Eden in reaction systems
inferred← citeshttps://doi.org/10.1016/j.tcs.2015.06.032openalex-snapshot
Synthesis for continuous time
inferred← citeshttps://doi.org/10.1016/s1571-0653(04)00324-5openalex-snapshot
Complexity and Approximability of Quantified and Stochastic Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.1093/ietisy/e91-d.4.990openalex-snapshot
Recursion Theoretic Operators for Function Complexity Classes
inferred← citeshttps://doi.org/10.1109/ccc.1998.694621openalex-snapshot
Complexity issues in Markov decision processes
inferred← citeshttps://doi.org/10.1109/ccc.2006.36openalex-snapshot
QMA/qpoly \subseteq PSPACE/poly: De-Merlinizing Quantum Protocols
inferred← citeshttps://doi.org/10.1109/lics.2013.16openalex-snapshot
Quantitative Monadic Second-Order Logic
inferred← citeshttps://doi.org/10.1109/lics.2017.8005090openalex-snapshot
Computing quantiles in Markov chains with multi-dimensional costs
inferred← citeshttps://doi.org/10.1109/lics.2017.8005150openalex-snapshot
Descriptive Complexity for counting complexity classes
inferred← citeshttps://doi.org/10.1109/sct.1990.113964openalex-snapshot
A very hard log space counting class
inferred← citeshttps://doi.org/10.1109/sct.1991.160269openalex-snapshot
Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits
inferred← citeshttps://doi.org/10.1137/0221040openalex-snapshot
Circuit Definitions of Nondeterministic Complexity Classes
inferred← citeshttps://doi.org/10.1137/120904524openalex-snapshot
On the Complexity of Package Recommendation Problems
inferred← citeshttps://doi.org/10.1137/s0097539705447013openalex-snapshot
The Complexity of Computing the Size of an Interval
inferred← citeshttps://doi.org/10.1137/s0097539793304601openalex-snapshot
The Complexity of Planar Counting Problems
inferred← citeshttps://doi.org/10.1142/s0129054113400327openalex-snapshot
FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS
inferred← citeshttps://doi.org/10.1145/2213556.2213592openalex-snapshot
On the complexity of package recommendation problems
inferred← citeshttps://doi.org/10.1145/2602136openalex-snapshot
On the Complexity of Query Result Diversification
inferred← citeshttps://doi.org/10.1145/2627748openalex-snapshot
On the Complexity of Query Result Diversification
inferred← citeshttps://doi.org/10.1145/347476.347480openalex-snapshot
Complexity of finite-horizon Markov decision process problems
inferred← citeshttps://doi.org/10.1145/3672608.3707850openalex-snapshot
Solution Counts of Some Prominent Quantified Boolean Formulas Families
inferred← citeshttps://doi.org/10.1145/384101.384126openalex-snapshot
Strongly-local reductions and the complexity/efficient approximability of algebra and optimization on abstract algebraic structures
inferred← citeshttps://doi.org/10.1287/moor.25.1.118.15214openalex-snapshot
The Complexity of Optimal Small Policies
inferred← citeshttps://doi.org/10.14778/2536354.2536358openalex-snapshot
On the complexity of query result diversification
inferred← citeshttps://doi.org/10.1609/aaai.v29i1.9680openalex-snapshot
Bayesian Networks Specified Using Propositional and Relational Constructs: Combined, Data, and Domain Complexity
inferred← citeshttps://doi.org/10.1609/aaai.v34i06.6552openalex-snapshot
Symbolic Top-k Planning
inferred← citeshttps://doi.org/10.1609/aaai.v35i7.16783openalex-snapshot
On the Complexity of Sum-of-Products Problems over Semirings
inferred← citeshttps://doi.org/10.1613/jair.1.13970openalex-snapshot
Semiring Reasoning Frameworks in AI and Their Computational Complexity
inferred← citeshttps://doi.org/10.1613/jair.505openalex-snapshot
The Computational Complexity of Probabilistic Planning
inferred← citeshttps://doi.org/10.23638/lmcs-16(1:9)2020openalex-snapshot
Descriptive Complexity for Counting Complexity Classes
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2018.130openalex-snapshot
On Computing the Total Variation Distance of Hidden Markov Models
inferred← citeshttps://doi.org/10.4230/lipics.itcs.2021.36openalex-snapshot
Two Combinatorial MA-Complete Problems
inferred← citeshttps://doi.org/10.46298/theoretics.23.10openalex-snapshot
The Complexity of Iterated Reversible Computation
inferred← citeshttps://doi.org/10.48550/arxiv.1402.3452openalex-snapshot
Processing Succinct Matrices and Vectors
inferred← citeshttps://doi.org/10.48550/arxiv.1409.8228openalex-snapshot
The Odds of Staying on Budget
inferred← citeshttps://doi.org/10.48550/arxiv.1601.04661openalex-snapshot
Efficient Quantile Computation in Markov Chains via Counting Problems for Parikh Images
inferred← citeshttps://doi.org/10.48550/arxiv.cs/0502058openalex-snapshot
The Complexity of Computing the Size of an Interval
inferred← citeshttps://doi.org/10.48550/arxiv.quant-ph/0510230openalex-snapshot
QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols
inferred← citeshttps://doi.org/10.48550/arxiv.quant-ph/0603069openalex-snapshot
The Jones polynomial: quantum algorithms and applications in quantum complexity theory
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.