On the public citation graph

Probability one separation of the Boolean hierarchy

https://doi.org/10.1007/bfb0039602
0 signed · 34 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/3-540-16486-3_87openalex-snapshot
Randomness, relativizations, and polynomial reducibilities
inferredcites →https://doi.org/10.1007/3-540-16486-3_93openalex-snapshot
The boolean hierarchy: Hardware over NP
inferredcites →https://doi.org/10.1007/3-540-16761-7_93openalex-snapshot
More complicated questions about maxima and minima, and some closures of NP
inferredcites →https://doi.org/10.1007/bf01744434openalex-snapshot
Relativized polynomial hierarchies extending two levels
inferredcites →https://doi.org/10.1007/bfb0028832openalex-snapshot
On the boolean closure of NP
inferredcites →https://doi.org/10.1016/0022-0000(88)90042-6openalex-snapshot
The complexity of facets resolved
inferredcites →https://doi.org/10.1109/sfcs.1985.49openalex-snapshot
Separating the polynomial-time hierarchy by oracles
inferredcites →https://doi.org/10.1109/sfcs.1985.56openalex-snapshot
The complexity of facets resolved
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/0216022openalex-snapshot
Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete
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/800070.802195openalex-snapshot
On the random oracle hypothesis
inferredcites →https://doi.org/10.1145/800070.802199openalex-snapshot
The complexity of facets (and some facets of complexity)
inferredcites →https://doi.org/10.4064/-21-1-449-458openalex-snapshot
More about the closure of NP

What points at this work

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

inferred← citeshttps://doi.org/10.1006/inco.2000.2884openalex-snapshot
Bounded Queries, Approximations, and the Boolean Hierarchy
inferred← citeshttps://doi.org/10.1007/11611257_30openalex-snapshot
P-Selectivity, Immunity, and the Power of One Bit
inferred← citeshttps://doi.org/10.1007/3-540-52846-6_73openalex-snapshot
Structural complexity theory: Recent surprises
inferred← citeshttps://doi.org/10.1007/3-540-55210-3_193openalex-snapshot
On complexity classes and algorithmically random languages
inferred← citeshttps://doi.org/10.1007/978-1-4613-3394-4_14openalex-snapshot
Measure One Results in Computational Complexity Theory
inferred← citeshttps://doi.org/10.1007/bf01184814openalex-snapshot
Strong Self-Reducibility Precludes Strong Immunity
inferred← citeshttps://doi.org/10.1007/bf01202284openalex-snapshot
On the power of deterministic reductions to C=P
inferred← citeshttps://doi.org/10.1007/bf01303054openalex-snapshot
On computing Boolean connectives of characteristic functions
inferred← citeshttps://doi.org/10.1007/bf01578842openalex-snapshot
An observation on probability versus randomness with applications to complexity classes
inferred← citeshttps://doi.org/10.1007/bfb0083671openalex-snapshot
Computational complexity of languages counting random oracles
inferred← citeshttps://doi.org/10.1007/s00224-004-1114-1openalex-snapshot
NP-Partitions over Posets with an Application to Reducing the Set of Solutions of NP Problems
inferred← citeshttps://doi.org/10.1016/0020-0190(93)90216-vopenalex-snapshot
The generic oracle hypothesis is false
inferred← citeshttps://doi.org/10.1016/s0022-0000(05)80084-4openalex-snapshot
The random oracle hypothesis is false
inferred← citeshttps://doi.org/10.1109/icci.1992.227701openalex-snapshot
The generic oracle hypothesis fails
inferred← citeshttps://doi.org/10.1137/0220015openalex-snapshot
Some Observations on Separating Complexity Classes
inferred← citeshttps://doi.org/10.1137/1036051openalex-snapshot
Relativizations of the P =? NP and Other Problems: Developments in Structural Complexity Theory
inferred← citeshttps://doi.org/10.1137/s0097539794261970openalex-snapshot
Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets
inferred← citeshttps://doi.org/10.1145/219817.219822openalex-snapshot
Worlds to die for
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2025.29openalex-snapshot
A Counterexample to the Generalized Linial-Nisan Conjecture
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.