On the public citation graph

Quantitative Relativizations of Complexity Classes

0 signed · 152 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/bf01683260openalex-snapshot

Relativization of questions about log space computability

inferredcites →https://doi.org/10.1007/bf01744301openalex-snapshot

On relativizing auxiliary pushdown machines

inferredcites →https://doi.org/10.1007/bfb0012797openalex-snapshot

On relativization and the existence of complete sets

inferredcites →https://doi.org/10.1007/bfb0036945openalex-snapshot

Immunity

inferredcites →https://doi.org/10.1016/0020-0190(83)90024-8openalex-snapshot

On sparse sets in NP–P

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/0304-3975(75)90016-xopenalex-snapshot

A comparison of polynomial time reducibilities

inferredcites →https://doi.org/10.1016/0304-3975(76)90061-xopenalex-snapshot

The polynomial-time hierarchy

inferredcites →https://doi.org/10.1016/0304-3975(76)90062-1openalex-snapshot

Complete sets and the polynomial-time hierarchy

inferredcites →https://doi.org/10.1016/0304-3975(78)90003-8openalex-snapshot

Log space machines with multiple oracle tapes

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(80)90017-1openalex-snapshot

Indexings of subrecursive classes

inferredcites →https://doi.org/10.1016/0304-3975(80)90027-4openalex-snapshot

On counting problems and the polynomial-time hierarchy

inferredcites →https://doi.org/10.1016/0304-3975(81)90061-xopenalex-snapshot

Bounded query machines: On NP and PSPACE

inferredcites →https://doi.org/10.1016/0304-3975(81)90062-1openalex-snapshot

Bounded query machines: On NP() and NPQUERY()

inferredcites →https://doi.org/10.1016/0304-3975(82)90085-8openalex-snapshot

Strong nondeterministic polynomial-time reducibilities

inferredcites →https://doi.org/10.1016/0304-3975(83)90003-8openalex-snapshot

Oracle-dependent properties of the lattice of NP sets

inferredcites →https://doi.org/10.1016/s0022-0000(70)80006-xopenalex-snapshot

Relationships between nondeterministic and deterministic tape complexities

inferredcites →https://doi.org/10.1137/0204037openalex-snapshot

Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

inferredcites →https://doi.org/10.1137/0207018openalex-snapshot

Rudimentary Predicates and Relative Computation

inferredcites →https://doi.org/10.1137/0211048openalex-snapshot

Relativizing Time, Space, and Time-Space

inferredcites →https://doi.org/10.1137/0212037openalex-snapshot

Positive Relativizations of Complexity Classes

inferredcites →https://doi.org/10.1145/800105.803408openalex-snapshot

Polynomial reducibilities and upward diagonalizations

inferredcites →https://doi.org/10.2307/2272354openalex-snapshot

Turing machines and the spectra of first-order formulas

What points at this work

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

inferred← citeshttps://doi.org/10.1002/9781118032916.biblioopenalex-snapshot

Bibliography

inferred← citeshttps://doi.org/10.1002/9781118595091.refsopenalex-snapshot

References

inferred← citeshttps://doi.org/10.1006/inco.2000.2884openalex-snapshot

Bounded Queries, Approximations, and the Boolean Hierarchy

inferred← citeshttps://doi.org/10.1006/jcss.1996.0061openalex-snapshot

P-Selective Sets and Reducing Search to Decision vs Self-Reducibility

inferred← citeshttps://doi.org/10.1006/jcss.2001.1815openalex-snapshot

Reducing the Number of Solutions of NP Functions

inferred← citeshttps://doi.org/10.1006/jcss.2002.1835openalex-snapshot

New Lowness Results for ZPPNP and Other Complexity Classes

inferred← citeshttps://doi.org/10.1007/11750321_27openalex-snapshot

Cluster Computing and the Power of Edge Recognition

inferred← citeshttps://doi.org/10.1007/3-540-13345-3_41openalex-snapshot

Robust algorithms: A different approach to oracles

inferred← citeshttps://doi.org/10.1007/3-540-16078-7_87openalex-snapshot

On generalized kolmogorov complexity

inferred← citeshttps://doi.org/10.1007/3-540-16486-3_111openalex-snapshot

Parallel computation and the NC hierarchy relativized

inferred← citeshttps://doi.org/10.1007/3-540-17179-7_25openalex-snapshot

On simple and creative sets in NP

inferred← citeshttps://doi.org/10.1007/3-540-18170-9_182openalex-snapshot

On the power of single-valued nondeterministic polynomial time computations

inferred← citeshttps://doi.org/10.1007/3-540-19488-6_150openalex-snapshot

On restricting the access to an NP-oracle

inferred← citeshttps://doi.org/10.1007/3-540-44450-5_29openalex-snapshot

Is the Standard Proof System for SAT P-Optimal?

inferred← citeshttps://doi.org/10.1007/3-540-44612-5_35openalex-snapshot

Reducing the Number of Solutions of NP Functions

inferred← citeshttps://doi.org/10.1007/3-540-44612-5_42openalex-snapshot

On NP-Partitions over Posets with an Application to Reducing the Set of Solutions of NP Problems

inferred← citeshttps://doi.org/10.1007/3-540-45066-1_14openalex-snapshot

On Functions and Relations

inferred← citeshttps://doi.org/10.1007/3-540-46541-3_36openalex-snapshot

Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Results

inferred← citeshttps://doi.org/10.1007/3-540-46691-6_33openalex-snapshot

Analysis of Quantum Functions

inferred← citeshttps://doi.org/10.1007/3-540-55808-x_14openalex-snapshot

Promise problems and access to unambiguous computation

inferred← citeshttps://doi.org/10.1007/3-540-56279-6_70openalex-snapshot

Relativizations of the P=? NP and other problems: Some developments in structural complexity theory

inferred← citeshttps://doi.org/10.1007/3-540-58325-4_166openalex-snapshot

Computing solutions uniquely collapses the polynomial hierarchy

inferred← citeshttps://doi.org/10.1007/3-540-63577-7_50openalex-snapshot

Exact learning via teaching assistants (Extended abstract)

inferred← citeshttps://doi.org/10.1007/978-1-4612-1872-2_7openalex-snapshot

The Complexity of Obtaining Solutions for Problems in NP and NL

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/978-3-031-93930-3_13openalex-snapshot

Search Versus Search for Collapsing Electoral Control Types

inferred← citeshttps://doi.org/10.1007/978-3-540-24597-1_35openalex-snapshot

Stringent Relativization

inferred← citeshttps://doi.org/10.1007/978-3-540-30551-4_20openalex-snapshot

Random Access to Advice Strings and Collapsing Results

inferred← citeshttps://doi.org/10.1007/978-3-540-69407-6_25openalex-snapshot

The Shrinking Property for NP and coNP

inferred← citeshttps://doi.org/10.1007/978-3-642-00596-1_11openalex-snapshot

Coalgebraic Hybrid Logic

inferred← citeshttps://doi.org/10.1007/978-3-642-29344-3_29openalex-snapshot

Structural Complexity of Multiobjective NP Search Problems

inferred← citeshttps://doi.org/10.1007/978-3-642-77735-6_3openalex-snapshot

On Sets with Small Information Content

inferred← citeshttps://doi.org/10.1007/978-3-7091-6597-3_25openalex-snapshot

Complexity Theory and Interaction

inferred← citeshttps://doi.org/10.1007/bf00264313openalex-snapshot

Sets with small generalized Kolmogorov complexity

inferred← citeshttps://doi.org/10.1007/bf01185399openalex-snapshot

A refinement of the low and high hierarchies

inferred← citeshttps://doi.org/10.1007/bf01692055openalex-snapshot

On relativizations with restricted number of accesses to the oracle set

inferred← citeshttps://doi.org/10.1007/bf01692056openalex-snapshot

RelativizedNC

inferred← citeshttps://doi.org/10.1007/bf02125350openalex-snapshot

Query complexity, or why is it difficult to separateNP A ∩coNP A fromP A by random oraclesA?

inferred← citeshttps://doi.org/10.1007/bfb0017153openalex-snapshot

Strong and robustly strong polynomial time reducibilities to sparse sets

inferred← citeshttps://doi.org/10.1007/bfb0028595openalex-snapshot

Uniformly defining complexity classes of functions

inferred← citeshttps://doi.org/10.1007/bfb0039591openalex-snapshot

Towards a theory of relativizations: Positive relativizations

inferred← citeshttps://doi.org/10.1007/bfb0055799openalex-snapshot

Average-case intractability vs. worst-case intractability

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.1007/s002240000079openalex-snapshot

Functions Computable with Nonadaptive Queries to NP

inferred← citeshttps://doi.org/10.1016/0020-0190(87)90087-1openalex-snapshot

Separation with the Ruzzo, Simon, and Tompa relativization implies Dspace(log n) ≠ Nspace(log n)

inferred← citeshttps://doi.org/10.1016/0020-0190(88)90176-7openalex-snapshot

On sparse oracles separating feasible complexity classes

inferred← citeshttps://doi.org/10.1016/0020-0190(89)90193-2openalex-snapshot

A note on sparse sets and the polynomial-time hierarchy

inferred← citeshttps://doi.org/10.1016/0020-0190(96)00030-0openalex-snapshot

Functions computable with limited access to NP

inferred← citeshttps://doi.org/10.1016/0022-0000(85)90053-4openalex-snapshot

Qualitative relativizations of complexity classes

inferred← citeshttps://doi.org/10.1016/0022-0000(89)90014-7openalex-snapshot

Positive relativizations of the P = ? NP problem

inferred← citeshttps://doi.org/10.1016/0022-0000(89)90018-4openalex-snapshot

On hiding information from an oracle

inferred← citeshttps://doi.org/10.1016/0022-0000(89)90025-1openalex-snapshot

The strong exponential hierarchy collapses

inferred← citeshttps://doi.org/10.1016/0022-0000(92)90022-bopenalex-snapshot

Turing machines with few accepting computations and low sets for PP

inferred← citeshttps://doi.org/10.1016/0304-3975(85)90085-4openalex-snapshot

On some natural complete operators

inferred← citeshttps://doi.org/10.1016/0304-3975(85)90158-6openalex-snapshot

Robust algorithms: A different approach to oracles

inferred← citeshttps://doi.org/10.1016/0304-3975(85)90168-9openalex-snapshot

On bounded query machines

inferred← citeshttps://doi.org/10.1016/0304-3975(90)90138-8openalex-snapshot

Robust machines accept easy sets

inferred← citeshttps://doi.org/10.1016/0304-3975(90)90168-hopenalex-snapshot

Positive relativizations for log space computability

inferred← citeshttps://doi.org/10.1016/0304-3975(91)90070-iopenalex-snapshot

Strong and robustly strong polynomial-time reducibilities to sparse sets

inferred← citeshttps://doi.org/10.1016/0304-3975(92)90318-aopenalex-snapshot

Separating complexity classes with tally oracles

inferred← citeshttps://doi.org/10.1016/0304-3975(95)00076-3openalex-snapshot

Optimal advice

inferred← citeshttps://doi.org/10.1016/j.cosrev.2008.02.001openalex-snapshot

The consequences of eliminating NP solutions

inferred← citeshttps://doi.org/10.1016/j.ic.2005.03.003openalex-snapshot

Reductions between disjoint NP-Pairs

inferred← citeshttps://doi.org/10.1016/j.ic.2007.02.001openalex-snapshot

Cluster computing and the power of edge recognition

inferred← citeshttps://doi.org/10.1016/j.jcss.2013.01.012openalex-snapshot

Tractable counting of the answers to conjunctive queries

inferred← citeshttps://doi.org/10.1016/j.tcs.2009.05.021openalex-snapshot

Nondeterministic functions and the existence of optimal proof systems

inferred← citeshttps://doi.org/10.1016/j.tcs.2015.10.026openalex-snapshot

Pseudorandom generators against advised context-free languages

inferred← citeshttps://doi.org/10.1016/s0019-9958(83)80023-0openalex-snapshot

On the random oracle hypothesis

inferred← citeshttps://doi.org/10.1016/s0022-0000(05)80009-1openalex-snapshot

A taxonomy of complexity classes of functions

inferred← citeshttps://doi.org/10.1016/s0304-3975(98)00060-7openalex-snapshot

A hierarchy based on output multiplicity

inferred← citeshttps://doi.org/10.1016/s0304-3975(99)00266-2openalex-snapshot

Exact learning via teaching assistants

inferred← citeshttps://doi.org/10.1016/s0890-5401(03)00119-6openalex-snapshot

Inverting onto functions

inferred← citeshttps://doi.org/10.1051/ita/1987210404191openalex-snapshot

The difference and truth-table hierarchies for NP

inferred← citeshttps://doi.org/10.1109/ccc.1996.507682openalex-snapshot

Much ado about functions

inferred← citeshttps://doi.org/10.1109/ccc.1996.507683openalex-snapshot

Inverting onto functions

inferred← citeshttps://doi.org/10.1109/ccc.1996.507688openalex-snapshot

Complements of multivalued functions

inferred← citeshttps://doi.org/10.1109/ccc.2004.1313791openalex-snapshot

Reductions between disjoint NP-pairs

inferred← citeshttps://doi.org/10.1109/ccc.2004.29openalex-snapshot

Reductions between disjoint NP-pairs

inferred← citeshttps://doi.org/10.1109/focs.2013.84openalex-snapshot

Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers

inferred← citeshttps://doi.org/10.1109/lics.2006.44openalex-snapshot

PSPACE Bounds for Rank-1 Modal Logics

inferred← citeshttps://doi.org/10.1109/sct.1988.5286openalex-snapshot

Bounded query computations

inferred← citeshttps://doi.org/10.1109/sct.1989.41826openalex-snapshot

Turning machines with few accepting computations and low sets for PP

inferred← citeshttps://doi.org/10.1109/sct.1989.41827openalex-snapshot

On the relativized power of additional accepting paths

inferred← citeshttps://doi.org/10.1109/sct.1990.113976openalex-snapshot

A note on relativizing complexity classes with tally

inferred← citeshttps://doi.org/10.1109/sct.1990.113978openalex-snapshot

On separating complexity classes

inferred← citeshttps://doi.org/10.1109/sct.1992.215396openalex-snapshot

How hard are sparse sets?

inferred← citeshttps://doi.org/10.1109/sct.1993.336541openalex-snapshot

P-selective sets, and reducing search to decision vs. self-reducibility

inferred← citeshttps://doi.org/10.1109/sct.1994.315819openalex-snapshot

On functions computable with nonadaptive queries to NP

inferred← citeshttps://doi.org/10.1109/sct.1995.514727openalex-snapshot

On superlinear lower bounds in complexity theory

inferred← citeshttps://doi.org/10.1109/sfcs.1984.715929openalex-snapshot

Sparse Oracles And Uniform Complexity Classes

inferred← citeshttps://doi.org/10.1109/sfcs.1984.715952openalex-snapshot

Complexity Measures For Public-Key Cryptosystems

inferred← citeshttps://doi.org/10.1109/sfcs.1985.49openalex-snapshot

Separating the polynomial-time hierarchy by oracles

inferred← citeshttps://doi.org/10.1137/0212037openalex-snapshot

Positive Relativizations of Complexity Classes

inferred← citeshttps://doi.org/10.1137/0214043openalex-snapshot

On Restricting the Size of Oracles Compared with Restricting Access to Oracles

inferred← citeshttps://doi.org/10.1137/0215035openalex-snapshot

Relativizations of Unambiguous and Random Polynomial Time Classes

inferred← citeshttps://doi.org/10.1137/0217018openalex-snapshot

Complexity Measures for Public-Key Cryptosystems

inferred← citeshttps://doi.org/10.1137/0217056openalex-snapshot

On Sets Truth-Table Reducible to Sparse Sets

inferred← citeshttps://doi.org/10.1137/0219058openalex-snapshot

Bounded Query Classes

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/s0097539703427550openalex-snapshot

Algebraic Properties for Selector Functions

inferred← citeshttps://doi.org/10.1137/s0097539791200351openalex-snapshot

Complexity-Restricted Advice Functions

inferred← citeshttps://doi.org/10.1137/s0097539793247439openalex-snapshot

Oracles That Compute Values

inferred← citeshttps://doi.org/10.1137/s0097539794268315openalex-snapshot

Computing Solutions Uniquely Collapses the Polynomial Hierarchy

inferred← citeshttps://doi.org/10.1142/9789812794499_0040openalex-snapshot

Relativization: a Revisionistic Retrospective

inferred← citeshttps://doi.org/10.1142/s0129054100000326openalex-snapshot

UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS

inferred← citeshttps://doi.org/10.1142/s0129054103002047openalex-snapshot

ANALYSIS OF QUANTUM FUNCTIONS

inferred← citeshttps://doi.org/10.1142/s0129054105003376openalex-snapshot

ADVICE FOR SEMIFEASIBLE SETS AND THE COMPLEXITY-THEORETIC COST(LESSNESS) OF ALGEBRAIC PROPERTIES

inferred← citeshttps://doi.org/10.1142/s0129054199000198openalex-snapshot

SELF-SPECIFYING MACHINES

inferred← citeshttps://doi.org/10.1142/s0218196720500198openalex-snapshot

Solutions to twisted word equations and equations in virtually free groups

inferred← citeshttps://doi.org/10.1145/1122480.1122495openalex-snapshot

Open questions in the theory of semifeasible computation

inferred← citeshttps://doi.org/10.1145/1462179.1462185openalex-snapshot

PSPACE bounds for rank-1 modal logics

inferred← citeshttps://doi.org/10.1145/193820.193828openalex-snapshot

Semi-membership algorithms

inferred← citeshttps://doi.org/10.1145/2670418.2670436openalex-snapshot

Beautiful structures

inferred← citeshttps://doi.org/10.1145/2696081.2696095openalex-snapshot

Disjoint NP-Pairs and Propositional Proof Systems

inferred← citeshttps://doi.org/10.1145/28395.28408openalex-snapshot

The strong exponential hierarchy collapses

inferred← citeshttps://doi.org/10.1145/3457588.3457597openalex-snapshot

SIGACT News Complexity Theory Column 108

inferred← citeshttps://doi.org/10.1145/3501300openalex-snapshot

Coalgebraic Reasoning with Global Assumptions in Arithmetic Modal Logics

inferred← citeshttps://doi.org/10.1145/5925.5937openalex-snapshot

The polynomial-time hierarchy and sparse oracles

inferred← citeshttps://doi.org/10.1145/5925.5938openalex-snapshot

Relativizing complexity classes with sparse oracles

inferred← citeshttps://doi.org/10.18452/9148openalex-snapshot

New lowness results for ZPP (NP) and other complexity classes

inferred← citeshttps://doi.org/10.31274/rtd-180813-10619openalex-snapshot

On the structure of intractable sets

inferred← citeshttps://doi.org/10.4086/cjtcs.1999.003openalex-snapshot

inferred← citeshttps://doi.org/10.47749/t/unicamp.2010.772316openalex-snapshot

Complexidade computacional e o problema P vs NP

inferred← citeshttps://doi.org/10.48550/arxiv.1303.1717openalex-snapshot

Oracle Pushdown Automata, Nondeterministic Reducibilities, and the CFL Hierarchy over the Family of Context-Free Languages

inferred← citeshttps://doi.org/10.48550/arxiv.1406.4106openalex-snapshot

Beautiful Structures: An Appreciation of the Contributions of Alan Selman

inferred← citeshttps://doi.org/10.48550/arxiv.cs/9910006openalex-snapshot

Self-Specifying Machines

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.