Pages that link to "Item:Q4109298"

The following pages link to New problems complete for nondeterministic log space (Q4109298):

Displaying 41 items.

• Solving linear equations parameterized by Hamming weight (Q309792) (← links)
• The complexity of intersecting finite automata having few final states (Q347114) (← links)
• Correctness of linear logic proof structures is NL-complete (Q534703) (← links)
• Knapsack problems for NL (Q673615) (← links)
• Multihead two-way probabilistic finite automata (Q675857) (← links)
• Minimizing finite automata is computationally hard (Q703578) (← links)
• The complexity of the satisfiability problem for Krom formulas (Q800915) (← links)
• The complexity of pure literal elimination (Q862401) (← links)
• Linear connectivity problems in directed hypergraphs (Q1029330) (← links)
• Complete problems in the first-order predicate calculus (Q1075318) (← links)
• Henkin quantifiers and complete problems (Q1088983) (← links)
• Symmetric space-bounded computation (Q1167537) (← links)
• Oracle branching programs and Logspace versus \(P^*\) (Q1183604) (← links)
• The parallel complexity of finite-state automata problems (Q1186807) (← links)
• Capturing complexity classes by fragments of second-order logic (Q1193408) (← links)
• The logic of constraint satisfaction (Q1204865) (← links)
• A very hard log-space counting class (Q1208403) (← links)
• Complexity of some problems in Petri nets (Q1238999) (← links)
• On log-tape isomorphisms of complete sets (Q1249940) (← links)
• Sorting, linear time and the satisfiability problem (Q1817067) (← links)
• Boundedness, empty channel detection, and synchronization for communicating finite automata (Q1819939) (← links)
• An approximate max-flow min-cut relation for undirected multicommodity flow, with applications (Q1894701) (← links)
• Equivalence classes and conditional hardness in massively parallel computations (Q2121067) (← links)
• On the space and circuit complexity of parameterized problems: classes and completeness (Q2343093) (← links)
• An efficiently solvable graph partition problem to which many problems are reducible (Q2365814) (← links)
• The complexity of searching implicit graphs (Q2676567) (← links)
• Note on the complexity of Las Vegas automata problems (Q3421911) (← links)
• Gradually intractable problems and nondeterministic log-space lower bounds (Q3700836) (← links)
• Classifying the computational complexity of problems (Q3781088) (← links)
• COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE (Q3839875) (← links)
• The complexity of searching succinctly represented graphs (Q4645179) (← links)
• Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space (Q5096446) (← links)
• The 2CNF Boolean formula satisfiability problem and the linear space hypothesis (Q5111278) (← links)
• On the complexity of the Cayley semigroup membership problem (Q5121913) (← links)
• The complexity of weakly recognizing morphisms (Q5223827) (← links)
• FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS (Q5495421) (← links)
• Minimal and hyper-minimal biautomata (Q5890813) (← links)
• On the complexity of some problems on groups input as multiplication tables (Q5956010) (← links)
• The 2CNF Boolean formula satisfiability problem and the linear space hypothesis (Q6098146) (← links)
• Strong backdoors for default logic (Q6570091) (← links)
• Strong backdoors for default logic (Q6610193) (← links)