On the public citation graph
On the power of parity polynomial time
0 signed · 78 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.
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.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1007/3-540-08342-1_37openalex-snapshot
On the difference between one and many
inferredcites →https://doi.org/10.1007/3-540-16486-3_112openalex-snapshot
Probabilistic quantifiers, adversaries, and complexity classes : An overview
inferredcites →https://doi.org/10.1007/3-540-16486-3_85openalex-snapshot
The complexity of sparse sets in P
inferredcites →https://doi.org/10.1007/bfb0009651openalex-snapshot
Two remarks on the power of counting
inferredcites →https://doi.org/10.1007/bfb0017131openalex-snapshot
Structure of complexity classes: Separations, collapses, and completeness
inferredcites →https://doi.org/10.1007/bfb0036487openalex-snapshot
Two remarks on the power of counting
inferredcites →https://doi.org/10.1016/0020-0190(76)90097-1openalex-snapshot
Relative complexity of checking and evaluating
inferredcites →https://doi.org/10.1016/0020-0190(83)90044-3openalex-snapshot
BPP and the polynomial hierarchy
inferredcites →https://doi.org/10.1016/0020-0190(87)90036-6openalex-snapshot
Random oracles separate PSPACE from the polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0022-0000(82)90002-2openalex-snapshot
Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis
inferredcites →https://doi.org/10.1016/0022-0000(89)90020-2openalex-snapshot
Probabilistic complexity classes and lowness
inferredcites →https://doi.org/10.1016/0304-3975(75)90016-xopenalex-snapshot
A comparison of polynomial time reducibilities
inferredcites →https://doi.org/10.1016/0304-3975(79)90044-6openalex-snapshot
The Complexity of Computing the Permanent
inferredcites →https://doi.org/10.1016/0304-3975(85)90140-9openalex-snapshot
Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
inferredcites →https://doi.org/10.1016/0304-3975(86)90165-9openalex-snapshot
On the construction of parallel computers from various bases of boolean functions
inferredcites →https://doi.org/10.1016/0304-3975(88)90022-9openalex-snapshot
Complexity classes without machines: On complete languages for UP
inferredcites →https://doi.org/10.1016/0304-3975(92)90084-sopenalex-snapshot
Counting classes: thresholds, parity, mods, and fewness
inferredcites →https://doi.org/10.1016/s0019-9958(82)90439-9openalex-snapshot
On the unique satisfiability problem
inferredcites →https://doi.org/10.1109/psct.1987.10319246openalex-snapshot
Probabilistic Complexity Classes and Lowness
inferredcites →https://doi.org/10.1109/psct.1987.10319254openalex-snapshot
Self-Reducible, P-Selective, Near-Testable, and P-Cheatable Sets: The Effect of Internal Structure on the Complexity of a Set
inferredcites →https://doi.org/10.1109/psct.1987.10319267openalex-snapshot
One-Way Functions, Robustness, and the Non-Isomorphism of NP-Complete Sets
inferredcites →https://doi.org/10.1109/sfcs.1985.49openalex-snapshot
Separating the polynomial-time hierarchy by oracles
inferredcites →https://doi.org/10.1137/0206023openalex-snapshot
On Isomorphisms and Density of $NP$ and Other Complete Sets
inferredcites →https://doi.org/10.1137/0208032openalex-snapshot
The Complexity of Enumeration and Reliability Problems
inferredcites →https://doi.org/10.1137/0210008openalex-snapshot
Relative to a Random Oracle A , ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
inferredcites →https://doi.org/10.1137/0212027openalex-snapshot
On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
inferredcites →https://doi.org/10.1137/0212038openalex-snapshot
Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
inferredcites →https://doi.org/10.1137/0217018openalex-snapshot
Complexity Measures for Public-Key Cryptosystems
inferredcites →https://doi.org/10.1137/0217058openalex-snapshot
Nondeterministic Space is Closed under Complementation
inferredcites →https://doi.org/10.1137/0217078openalex-snapshot
The Boolean Hierarchy I: Structural Properties
inferredcites →https://doi.org/10.1137/0218007openalex-snapshot
The Boolean Hierarchy II: Applications
inferredcites →https://doi.org/10.1145/12130.12133openalex-snapshot
With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
inferredcites →https://doi.org/10.1145/12130.12160openalex-snapshot
A note on one-way functions and polynomial-time isomorphisms
inferredcites →https://doi.org/10.1145/5925.5938openalex-snapshot
Relativizing complexity classes with sparse oracles
inferredcites →https://doi.org/10.7916/d83x8frjopenalex-snapshot
On the Power of Probabilistic Polynomial Time: PNP[log] ⊆ PP
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1006/jcss.1995.1036openalex-snapshot
The Power of the Middle Bit of a #P Function
inferred← citeshttps://doi.org/10.1007/3-540-48340-3_38openalex-snapshot
Generalized Regular Counting Classes
inferred← citeshttps://doi.org/10.1007/3-540-51486-4_73openalex-snapshot
Polynomial-time functions generate SAT: On P-splinters
inferred← citeshttps://doi.org/10.1007/3-540-51498-8_2openalex-snapshot
Complexity classes with complete problems between P and NP-C
inferred← citeshttps://doi.org/10.1007/3-540-54458-5_61openalex-snapshot
Unambiguity and fewness for logarithmic space
inferred← citeshttps://doi.org/10.1007/3-540-55210-3_200openalex-snapshot
Graph isomorphism is low for PP
inferred← citeshttps://doi.org/10.1007/978-3-642-60322-8_20openalex-snapshot
The BP-Operator and the Power of Counting Classes
inferred← citeshttps://doi.org/10.1007/978-3-662-03927-4_7openalex-snapshot
Polynomial Time and Beyond
inferred← citeshttps://doi.org/10.1007/978-981-97-2340-9_18openalex-snapshot
On the Power of Counting the Total Number of Computation Paths of NPTMs
inferred← citeshttps://doi.org/10.1007/bf01374526openalex-snapshot
Structure and importance of logspace-MOD class
inferred← citeshttps://doi.org/10.1007/bf02090390openalex-snapshot
Limitations of the upward separation technique
inferred← citeshttps://doi.org/10.1007/bf02090768openalex-snapshot
On the power of parity polynomial time
inferred← citeshttps://doi.org/10.1007/bfb0017131openalex-snapshot
Structure of complexity classes: Separations, collapses, and completeness
inferred← citeshttps://doi.org/10.1007/bfb0020812openalex-snapshot
Structure and importance of logspace-MOD-classes
inferred← citeshttps://doi.org/10.1007/bfb0028561openalex-snapshot
On the structure of valiant's complexity classes
inferred← citeshttps://doi.org/10.1007/bfb0029633openalex-snapshot
Separating ⊕L from L, NL, co-NL and AL (=P) for Oblivious turing machines of linear access time
inferred← citeshttps://doi.org/10.1007/bfb0035749openalex-snapshot
Limitations of the upward separation technique (preliminary version)
inferred← citeshttps://doi.org/10.1007/bfb0035795openalex-snapshot
A combinatorial technique for separating counting complexity classes
inferred← citeshttps://doi.org/10.1007/bfb0036187openalex-snapshot
Polynomial time machines equipped with word problems over algebraic structures as their acceptance criteria
inferred← citeshttps://doi.org/10.1016/0020-0190(92)90002-dopenalex-snapshot
On the power of enumerative counting
inferred← citeshttps://doi.org/10.1016/0304-3975(92)90369-qopenalex-snapshot
Polynomial-time 1-Turing reductions from #PH to #P
inferred← citeshttps://doi.org/10.1016/b978-0-444-88071-0.50007-2openalex-snapshot
A Catalog of Complexity Classes
inferred← citeshttps://doi.org/10.1051/ita/1992260605071openalex-snapshot
Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access
inferred← citeshttps://doi.org/10.1109/ccc.1997.612317openalex-snapshot
Acceptance by transformation monoids (with an application to local self reductions)
inferred← citeshttps://doi.org/10.1109/ccc.2007.34openalex-snapshot
Time-Space Tradeoffs for Counting NP Solutions Modulo Integers
inferred← citeshttps://doi.org/10.1109/sct.1991.160238openalex-snapshot
Counting classes are at least as hard as the polynomial-time hierarchy
inferred← citeshttps://doi.org/10.1109/sct.1991.160248openalex-snapshot
Complexity classes and sparse oracles
inferred← citeshttps://doi.org/10.1109/sct.1991.160254openalex-snapshot
On one query, self-reducible sets
inferred← citeshttps://doi.org/10.1109/sfcs.1989.63527openalex-snapshot
On the computational power of PP and (+)P
inferred← citeshttps://doi.org/10.1137/0220053openalex-snapshot
PP is as Hard as the Polynomial-Time Hierarchy
inferred← citeshttps://doi.org/10.1145/348210.348215openalex-snapshot
Algebraic acceptance mechanisms for polynomial time machines
inferred← citeshttps://doi.org/10.1145/3519935.3520075openalex-snapshot
Complexity classification of counting graph homomorphisms modulo a prime number
inferred← citeshttps://doi.org/10.48550/arxiv.0809.1836openalex-snapshot
The complexity of counting solutions to Generalised Satisfiability Problems modulo k
inferred← citeshttps://doi.org/10.48550/arxiv.1806.03501openalex-snapshot
An Overview Of Some Semantic And Syntactic Complexity Classes
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.