On the public citation graph
On the structure of valiant's complexity classes
0 signed · 48 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.1006/jcom.1993.1031openalex-snapshot
On the Intrinsic Complexity of Elimination Theory
inferredcites →https://doi.org/10.1006/jcom.1996.0019openalex-snapshot
Hilbert's Nullstellensatz Is in the Polynomial Hierarchy
inferredcites →https://doi.org/10.1006/jcom.1999.0537openalex-snapshot
A Note on Non-complete Problems in NPR
inferredcites →https://doi.org/10.1007/978-1-4612-0701-6_7openalex-snapshot
Algebraic Settings for the Problem “P ≠ NP?”
inferredcites →https://doi.org/10.1007/978-3-540-70529-1_283openalex-snapshot
Computational Complexity
inferredcites →https://doi.org/10.1007/978-3-662-03338-8openalex-snapshot
Algebraic Complexity Theory
inferredcites →https://doi.org/10.1007/978-3-662-04179-6openalex-snapshot
Completeness and Reduction in Algebraic Complexity Theory
inferredcites →https://doi.org/10.1007/978-3-662-04179-6_3openalex-snapshot
Some Complete Families of Polynomials
inferredcites →https://doi.org/10.1007/bf02090768openalex-snapshot
On the power of parity polynomial time
inferredcites →https://doi.org/10.1007/bfb0009651openalex-snapshot
Two remarks on the power of counting
inferredcites →https://doi.org/10.1007/bfb0028987openalex-snapshot
On the power of parity polynomial time
inferredcites →https://doi.org/10.1007/bfb0036487openalex-snapshot
Two remarks on the power of counting
inferredcites →https://doi.org/10.1016/0016-0032(58)90688-4openalex-snapshot
An introduction to probability theory and its applications
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(81)90069-4openalex-snapshot
On the structure of sets in NP and other complexity classes
inferredcites →https://doi.org/10.1016/0304-3975(82)90114-1openalex-snapshot
A uniform approach to obtain diagonal sets in complexity classes
inferredcites →https://doi.org/10.1016/0304-3975(86)90135-0openalex-snapshot
NP is as easy as detecting unique solutions
inferredcites →https://doi.org/10.1016/0304-3975(94)00068-9openalex-snapshot
Relativizations of the P=?NP question over the reals (and other ordered rings)
inferredcites →https://doi.org/10.1016/s0168-0072(98)00060-8openalex-snapshot
Saturation and stability in the theory of computation over the reals
inferredcites →https://doi.org/10.1016/s0304-3975(99)00183-8openalex-snapshot
Cook's versus Valiant's hypothesis
inferredcites →https://doi.org/10.1016/s0747-7171(87)80063-9openalex-snapshot
Feasible arithmetic computations: Valiant's hypothesis
inferredcites →https://doi.org/10.1017/s0962492900002774openalex-snapshot
Complexity theory and numerical analysis
inferredcites →https://doi.org/10.1090/s0273-0979-1989-15750-9openalex-snapshot
On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
inferredcites →https://doi.org/10.1137/0204037openalex-snapshot
Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
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.1145/321864.321877openalex-snapshot
On the Structure of Polynomial Time Reducibility
inferredcites →https://doi.org/10.1145/3749740.3749750openalex-snapshot
Completeness Classes in Algebra
inferredcites →https://doi.org/10.1145/800157.805047openalex-snapshot
The complexity of theorem-proving procedures
inferredcites →https://doi.org/10.2307/2344620openalex-snapshot
An Introduction to Probability Theory and its Applications.
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1006/jcom.1999.0537openalex-snapshot
A Note on Non-complete Problems in NPR
inferred← citeshttps://doi.org/10.1007/11786986_45openalex-snapshot
The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games
inferred← citeshttps://doi.org/10.1007/3-540-44683-4_2openalex-snapshot
On Implications between P-NP-Hypotheses: Decision versus Computation in Algebraic Complexity
inferred← citeshttps://doi.org/10.1007/978-3-319-34171-2_18openalex-snapshot
Some Complete and Intermediate Polynomials in Algebraic Complexity Theory
inferred← citeshttps://doi.org/10.1007/978-3-642-03073-4_36openalex-snapshot
On Ladner’s Result for a Class of Real Machines with Restricted Use of Constants
inferred← citeshttps://doi.org/10.1007/978-3-642-03816-7_17openalex-snapshot
A Dichotomy Theorem for Polynomial Evaluation
inferred← citeshttps://doi.org/10.1007/s00224-007-9022-9openalex-snapshot
From a Zoo to a Zoology: Towards a General Theory of Graph Polynomials
inferred← citeshttps://doi.org/10.1016/j.ic.2011.11.001openalex-snapshot
On Ladnerʼs result for a class of real machines with restricted use of constants
inferred← citeshttps://doi.org/10.1016/s0304-3975(99)00183-8openalex-snapshot
Cook's versus Valiant's hypothesis
inferred← citeshttps://doi.org/10.1016/s0377-2217(02)00269-2openalex-snapshot
Some aspects of studying an optimization or decision problem in different computational models
inferred← citeshttps://doi.org/10.1109/sfcs.2001.959912openalex-snapshot
The complexity of factors of multivariate polynomials
inferred← citeshttps://doi.org/10.1137/s0097539798367880openalex-snapshot
The Computational Complexity of Immanants
inferred← citeshttps://doi.org/10.1561/0400000039openalex-snapshot
Arithmetic Circuits: A Survey of Recent Results and Open Questions
inferred← citeshttps://doi.org/10.48550/arxiv.0902.2300openalex-snapshot
A Dichotomy Theorem for Polynomial Evaluation
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.