On the public citation graph

New problems complete for nondeterministic log space

0 signed · 133 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/978-1-4684-2001-2_9openalex-snapshot

Reducibility among Combinatorial Problems

inferredcites →https://doi.org/10.1007/978-3-662-40087-6_1openalex-snapshot

On the Structure of Feasible Computations

inferredcites →https://doi.org/10.1016/c2009-0-22103-9openalex-snapshot

Symbolic Logic and Mechanical Theorem Proving

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

Relationships between nondeterministic and deterministic tape complexities

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

Space-bounded reducibility among combinatorial problems

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

The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines

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

On the complexity of LR(k) testing

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

The complexity of theorem-proving procedures

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.2001.1764openalex-snapshot

On the Complexity of Some Problems on Groups Input as Multiplication Tables

inferred← citeshttps://doi.org/10.1007/11611257_45openalex-snapshot

The Complexity of Problems on Implicitly Represented Inputs

inferred← citeshttps://doi.org/10.1007/3-540-08353-7_172openalex-snapshot

Time and tape bounded auxiliary pushdown automata

inferred← citeshttps://doi.org/10.1007/3-540-08860-1_22openalex-snapshot

A pspace complete problem related to a pebble game

inferred← citeshttps://doi.org/10.1007/3-540-10003-2_85openalex-snapshot

Symmertric space-bounded computation (extended abstract)

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

Bounding the bandwidth of NP-complete problems

inferred← citeshttps://doi.org/10.1007/3-540-10854-8_30openalex-snapshot

On the LBA problem

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

Logspace hierarchies, polynomial time and the complexity of fairness problems concerning ω-machines

inferred← citeshttps://doi.org/10.1007/3-540-28520-2_3openalex-snapshot

Foundations of Complexity Theory

inferred← citeshttps://doi.org/10.1007/3-540-28520-2_8openalex-snapshot

Other Public-Key Cryptosystems and Protocols

inferred← citeshttps://doi.org/10.1007/3-540-36377-7openalex-snapshot

The essence of computation: complexity, analysis, transformation

inferred← citeshttps://doi.org/10.1007/3-540-45007-6_31openalex-snapshot

Minimizing Finite Automata Is Computationally Hard

inferred← citeshttps://doi.org/10.1007/3-540-45655-4_59openalex-snapshot

On Reachability in Graphs with Bounded Independence Number

inferred← citeshttps://doi.org/10.1007/3-540-50647-0_110openalex-snapshot

Fast parallel algorithms and the complexity of parallelism (basic issues and recent advances)

inferred← citeshttps://doi.org/10.1007/3-540-51486-4_84openalex-snapshot

Oracle branching programs and Logspace versus P

inferred← citeshttps://doi.org/10.1007/3-540-52292-1_20openalex-snapshot

The complexity of graph problems for succinctly represented graphs

inferred← citeshttps://doi.org/10.1007/3-540-59119-2_188openalex-snapshot

Learning decision lists and trees with equivalence-queries

inferred← citeshttps://doi.org/10.1007/3-540-59175-3_103openalex-snapshot

Multihead two-way probabilistic finite automata

inferred← citeshttps://doi.org/10.1007/3-540-60084-1_75openalex-snapshot

The complexity of searching succinctly represented graphs

inferred← citeshttps://doi.org/10.1007/978-1-4020-5571-3_6openalex-snapshot

The Complexity of Pure Literal Elimination

inferred← citeshttps://doi.org/10.1007/978-1-4615-3422-8_30openalex-snapshot

The Complexity of Algorithmic Problems on Succinct Instances

inferred← citeshttps://doi.org/10.1007/978-3-030-14812-6_41openalex-snapshot

Supportive Oracles for Parameterized Polynomial-Time Sub-Linear-Space Computations in Relation to L, NL, and P

inferred← citeshttps://doi.org/10.1007/978-3-031-18461-1_51openalex-snapshot

Parameterized-NL Completeness of Combinatorial Problems by Short Logarithmic-Space Reductions and Immediate Consequences of the Linear Space Hypothesis

inferred← citeshttps://doi.org/10.1007/978-3-031-62687-6_17openalex-snapshot

Logical Expressibility of Syntactic NL for Complementarity and Maximization

inferred← citeshttps://doi.org/10.1007/978-3-319-03780-6_28openalex-snapshot

Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems

inferred← citeshttps://doi.org/10.1007/978-3-319-03898-8_28openalex-snapshot

Completeness Results for Parameterized Space Classes

inferred← citeshttps://doi.org/10.1007/978-3-319-09698-8_26openalex-snapshot

Minimal and Hyper-Minimal Biautomata

inferred← citeshttps://doi.org/10.1007/978-3-319-10512-3_12openalex-snapshot

Weak Singular Hybrid Automata

inferred← citeshttps://doi.org/10.1007/978-3-322-95233-2_14openalex-snapshot

Complexity of Closeness, Sparseness and Segment Equivalence for Context-Free and Regular Languages

inferred← citeshttps://doi.org/10.1007/978-3-540-24749-4_28openalex-snapshot

Satisfiability Problems Complete for Deterministic Logarithmic Space

inferred← citeshttps://doi.org/10.1007/978-3-540-24749-4_29openalex-snapshot

A Logspace Approximation Scheme for the Shortest Path Problem for Graphs with Bounded Independence Number

inferred← citeshttps://doi.org/10.1007/978-3-540-30538-5_40openalex-snapshot

Complexity of Linear Connectivity Problems in Directed Hypergraphs

inferred← citeshttps://doi.org/10.1007/978-3-540-74915-8_33openalex-snapshot

Correctness of Multiplicative (and Exponential) Proof Structures is NL-Complete

inferred← citeshttps://doi.org/10.1007/978-3-642-22321-1_24openalex-snapshot

Nodes Connected by Path Languages

inferred← citeshttps://doi.org/10.1007/978-3-642-30642-6_4openalex-snapshot

The Complexity of Intersecting Finite Automata Having Few Final States

inferred← citeshttps://doi.org/10.1007/978-3-642-31653-1_18openalex-snapshot

From Equivalence to Almost-Equivalence, and Beyond—Minimizing Automata with Errors

inferred← citeshttps://doi.org/10.1007/978-3-642-33293-7_20openalex-snapshot

On the Space Complexity of Parameterized Problems

inferred← citeshttps://doi.org/10.1007/978-3-642-95289-0_12openalex-snapshot

On the Complexity of Decision Problems for Classes of Simple Programs on Strings

inferred← citeshttps://doi.org/10.1007/978-3-662-43951-7_30openalex-snapshot

Hardness Results for Intersection Non-Emptiness

inferred← citeshttps://doi.org/10.1007/978-94-015-9383-0_19openalex-snapshot

A Complete Neural Network Algorithm for Horn-SAT

inferred← citeshttps://doi.org/10.1007/978-94-017-0522-6_10openalex-snapshot

Computable Quantifiers and Logics over Finite Structures

inferred← citeshttps://doi.org/10.1007/978-981-19-9582-8_16openalex-snapshot

Fine Grained Space Complexity and the Linear Space Hypothesis (Preliminary Report)

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

An approximate max-flow min-cut relation for undirected multicommodity flow, with applications

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

Gradually intractable problems and nondeterministic log-space lower bounds

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

Sorting, linear time and the satisfiability problem

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

Multihead two-way probabilistic finite automata

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

Boundedness, empty channel detection and synchronization for communicating finite state machines

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

The complexity of problems concerning graphs with regularities

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

Closure under complementation of logspace complexity classes - A survey -

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

Logical syntax and computational complexity

inferred← citeshttps://doi.org/10.1007/s00037-014-0089-9openalex-snapshot

The complexity of intersecting finite automata having few final states

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

Solvable Set/Hyperset Contexts: II. A Goal-Driven Unification Algorithm for the Blended Case

inferred← citeshttps://doi.org/10.1007/s00446-021-00418-2openalex-snapshot

Equivalence classes and conditional hardness in massively parallel computations

inferred← citeshttps://doi.org/10.1007/s00453-014-9944-yopenalex-snapshot

On the Space and Circuit Complexity of Parameterized Problems: Classes and Completeness

inferred← citeshttps://doi.org/10.1007/s00453-015-0098-3openalex-snapshot

Solving Linear Equations Parameterized by Hamming Weight

inferred← citeshttps://doi.org/10.1007/s10817-005-9008-8openalex-snapshot

The Complexity of Pure Literal Elimination

inferred← citeshttps://doi.org/10.1016/0004-3702(92)90003-gopenalex-snapshot

The logic of constraint satisfaction

inferred← citeshttps://doi.org/10.1016/0004-3702(96)00014-8openalex-snapshot

The complexity of searching implicit graphs

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

A simple parallel algorithm for finding a satisfying truth assignment to a 2-cnf formula

inferred← citeshttps://doi.org/10.1016/0020-0190(93)90038-bopenalex-snapshot

An efficiently solvable graph partition problem to which many problems are reducible

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

Knapsack problems for NL

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

A note on the monotone complexity of 2-REF

inferred← citeshttps://doi.org/10.1016/0022-0000(84)90010-2openalex-snapshot

Complete problems in the first-order predicate calculus

inferred← citeshttps://doi.org/10.1016/0168-0072(86)90040-0openalex-snapshot

Henkin quantifiers and complete problems

inferred← citeshttps://doi.org/10.1016/0196-6774(87)90019-8openalex-snapshot

Universal traversal sequences for paths and cycles

inferred← citeshttps://doi.org/10.1016/0304-3975(77)90014-7openalex-snapshot

Complexity of some problems in Petri nets

inferred← citeshttps://doi.org/10.1016/0304-3975(78)90018-xopenalex-snapshot

On log-tape isomorphisms of complete sets

inferred← citeshttps://doi.org/10.1016/0304-3975(82)90058-5openalex-snapshot

Symmetric space-bounded computation

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

The complexity of the satisfiability problem for Krom formulas

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

Boundedness, empty channel detection, and synchronization for communicating finite automata

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

Capturing complexity classes by fragments of second-order logic

inferred← citeshttps://doi.org/10.1016/0304-3975(93)90252-oopenalex-snapshot

A very hard log-space counting class

inferred← citeshttps://doi.org/10.1016/0890-5401(91)90017-vopenalex-snapshot

Oracle branching programs and Logspace versus P

inferred← citeshttps://doi.org/10.1016/0890-5401(92)90002-wopenalex-snapshot

The parallel complexity of finite-state automata problems

inferred← citeshttps://doi.org/10.1016/b978-0-12-115350-2.50014-2openalex-snapshot

SOME OPEN QUESTIONS AND RECENT RESULTS ON TREE TRANSDUCERS AND TREE LANGUAGES11Preparation of this paper was supported in part by the National Science Foundation under Grant No. MCS79-04012.

inferred← citeshttps://doi.org/10.1016/b978-0-444-88071-0.50007-2openalex-snapshot

A Catalog of Complexity Classes

inferred← citeshttps://doi.org/10.1016/j.entcs.2004.08.064openalex-snapshot

Obtaining Memory-Efficient Solutions to Boolean Equation Systems

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

The 2CNF Boolean formula satisfiability problem and the linear space hypothesis

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

Minimizing finite automata is computationally hard

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

Linear connectivity problems in directed hypergraphs

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

Correctness of linear logic proof structures is NL -complete

inferred← citeshttps://doi.org/10.1016/s0019-9958(79)90082-2openalex-snapshot

Equality languages and fixed point languages

inferred← citeshttps://doi.org/10.1016/s0019-9958(85)80041-3openalex-snapshot

A taxonomy of problems with fast parallel algorithms

inferred← citeshttps://doi.org/10.1016/s0049-237x(08)70326-4openalex-snapshot

Bibliography

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

The complexity of weakly recognizing morphisms

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

Note on the complexity of Las Vegas automata problems

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

On the complexity of some problems on groups input as multiplication tables

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

Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space

inferred← citeshttps://doi.org/10.1109/fscs.1990.89595openalex-snapshot

Approximation through multicommodity flow

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

Correctness of Multiplicative Additive Proof Structures is NL-Complete

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

A fine-grained hierarchy of hard problems in the separated fragment

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

A very hard log space counting class

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

Capturing complexity classes by fragments of second order logic

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

One-way log-tape reductions

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

Random walks, universal traversal sequences, and the complexity of maze problems

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

Logical reducibility and monadic NP

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

Existential second-order logic over graphs: charting the tractability frontier

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

Logspace Hierarchies, Polynomial Time and the Complexity of Fairness Problems Concerning $\omega $-Machines

inferred← citeshttps://doi.org/10.1137/20m134109xopenalex-snapshot

Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space

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

The Complexity of Finding Paths in Graphs with Bounded Independence Number

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

Free Bits, PCPs, and Nonapproximability---Towards Tight Results

inferred← citeshttps://doi.org/10.1142/4002#t=tocopenalex-snapshot

Algorithms: Design Techniques and Analysis

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

FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS

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

Minimal and Hyper-Minimal Biautomata

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

COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE

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

Explaining Non-Entailment by Model Transformation for the Description Logic EL

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

Strong Backdoors for Default Logic

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

A fast parallel algorithm for the maximal independent set problem

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

Symmetric Complementation

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

A fast parallel algorithm for the maximal independent set problem

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

The random access hierarchy

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

Symmetric complementation

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

Existential second-order logic over graphs

inferred← citeshttps://doi.org/10.1305/ndjfl/1093638014openalex-snapshot

On the existence of polynomial time algorithms for interpolation problems in propositional logic.

inferred← citeshttps://doi.org/10.14232/actacyb.22.3.2016.9openalex-snapshot

On Nonpermutational Transformation Semigroups with an Application to Syntactic Complexity

inferred← citeshttps://doi.org/10.21236/ada108823openalex-snapshot

Symmetric Complementation. Revision

inferred← citeshttps://doi.org/10.22331/q-2023-08-09-1079openalex-snapshot

Code-routing: a new attack on position verification

inferred← citeshttps://doi.org/10.2307/2273858openalex-snapshot

Classifying the computational complexity of problems

inferred← citeshttps://doi.org/10.3217/jucs-015-01-0033openalex-snapshot

Dynamic Query Optimization under Access Limitations and Dependencies

inferred← citeshttps://doi.org/10.32388/ge8x3popenalex-snapshot

NP on Logarithmic Space

inferred← citeshttps://doi.org/10.32388/ge8x3p.2openalex-snapshot

NP on Logarithmic Space

inferred← citeshttps://doi.org/10.32388/qcdn1gopenalex-snapshot

SAT is as hard as solving Homogeneous Diophantine Equation of Degree Two

inferred← citeshttps://doi.org/10.4230/lipics.ccc.2018.25openalex-snapshot

On the Complexity of the Cayley Semigroup Membership Problem

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

Completeness Results for Parameterized Space Classes

inferred← citeshttps://doi.org/10.5555/3329995.3330029openalex-snapshot

A fine-grained hierarchy of hard problems in the separated fragment

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.