On the public citation graph

On completeness for NP via projection translations

https://doi.org/10.1007/bf01195200

0 signed · 27 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.1002/malq.19770233608openalex-snapshot

Some Remarks on Generalized Spectra

inferredcites →https://doi.org/10.1006/jctb.1995.1006openalex-snapshot

Graph Minors .XIII. The Disjoint Paths Problem

inferredcites →https://doi.org/10.1007/3-540-13331-3_51openalex-snapshot

Reduction to NP-complete problems by interpretations

inferredcites →https://doi.org/10.1007/978-1-4684-2001-2_9openalex-snapshot

Reducibility among Combinatorial Problems

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

Toward logic tailored for computational complexity

inferredcites →https://doi.org/10.1016/0020-0190(91)90121-wopenalex-snapshot

Complete problems for symmetric logspace involving free groups

inferredcites →https://doi.org/10.1016/0022-0000(92)90043-iopenalex-snapshot

Using the Hamiltonian path operator to capture NP

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

The polynomial-time hierarchy

inferredcites →https://doi.org/10.1093/logcom/1.3.305openalex-snapshot

Comparing the Expressibility of Languages Formed Using NP-Complete Operators

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

Languages that Capture Complexity Classes

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

Nondeterministic Space is Closed under Complementation

inferredcites →https://doi.org/10.1142/2085openalex-snapshot

Current Trends in Theoretical Computer Science

inferredcites →https://doi.org/10.1142/s0218196792000141openalex-snapshot

REFINING KNOWN RESULTS ON THE GENERALIZED WORD PROBLEM FOR FREE GROUPS

What points at this work

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

inferred← citeshttps://doi.org/10.1002/malq.19970430102openalex-snapshot

Regular Subgraphs in Graphs and Rooted Graphs and Definability in Monadic Second ‐ Order Logic

inferred← citeshttps://doi.org/10.1002/malq.19970430203openalex-snapshot

Logics with Zero‐One Laws that Are Not Fragments of Bounded‐Variable Infinitary Logic

inferred← citeshttps://doi.org/10.1007/3-540-56992-8_25openalex-snapshot

Logical characterization of bounded query classes II: Polynomial-time oracle machines

inferred← citeshttps://doi.org/10.1007/978-3-031-86319-6_14openalex-snapshot

NP-completeness by First-order and Quantifier-free Interpretations and Related Topics

inferred← citeshttps://doi.org/10.1007/978-3-662-44465-8_41openalex-snapshot

On the Complexity of Symbolic Verification and Decision Problems in Bit-Vector Logic

inferred← citeshttps://doi.org/10.1007/978-3-7091-9461-4_7openalex-snapshot

The Role of Monotonicity in Descriptive Complexity Theory

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

Incorporating generalized quantifiers and the least fixed point operator

inferred← citeshttps://doi.org/10.1007/s00224-017-9787-4openalex-snapshot

Bounded-Depth Succinct Encodings and the Structure they Imply on Graphs

inferred← citeshttps://doi.org/10.1016/0168-0072(94)90036-1openalex-snapshot

Context-sensitive transitive closure operators

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

Complete problems for monotone NP

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

Graph properties checkable in linear time in the number of vertices

inferred← citeshttps://doi.org/10.1016/s0168-0072(98)00057-8openalex-snapshot

Succinctness as a source of complexity in logical formalisms

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

Succinct representation, leaf languages, and projection reductions

inferred← citeshttps://doi.org/10.4204/eptcs.410.3openalex-snapshot

Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)

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.