Complete problems for deterministic polynomial time

Cites Work

Title not available (Why is that?)
The complexity of theorem-proving procedures
An observation on time-storage trade off
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Recognition and parsing of context-free languages in time n3
Unit Refutations and Horn Sets
Space-bounded reducibility among combinatorial problems

Cited In (83)

Arithmetizing uniform \(NC\)
The parallel complexity of deadlock detection
Two \(P\)-complete problems in the theory of the reals
Synthesis from component libraries with costs
Testing membership: Beyond permutation groups
The complexity of the satisfiability problem for Krom formulas
Complete problems in the first-order predicate calculus
The unique Horn-satisfiability problem and quadratic Boolean equations.
Idempotent \(n\)-permutable varieties.
New problems complete for nondeterministic log space
The word and generator problems for lattices
Optimizing propositional calculus formulas with regard to questions of deducibility
On digital nondeterminism
The equivalence of finite valued transducers (on HDT0L languages) is decidable
Reversible pushdown automata
The incremental maintenance of a depth-first-search tree in directed acyclic graphs
On the complexity of decision problems for some classes of machines and applications
A hierarchy of propositional Horn formuls
Stratification and knowledge base management
Recognition of \(q\)-Horn formulae in linear time
Polynomial-time inference of all valid implications for Horn and related formulae
Classes of bounded nondeterminism
Parallel complexity of logical query programs
Maximum renamable Horn sub-CNFs
The complexity of searching implicit graphs
Complexity of equations over sets of natural numbers
On the space and circuit complexity of parameterized problems: classes and completeness
The complexity of linear programming
Depth-first search is inherently sequential
A topological approach to dynamic graph connectivity
Iterated stack automata and complexity classes
Extending regular expressions with homomorphic replacement
Capturing complexity classes by fragments of second-order logic
Alternating multihead finite automata
Complexity of some problems concerningL systems
The complexity of searching succinctly represented graphs
COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE
On the construction of parallel computers from various basis of Boolean functions
The Nielsen reduction and P-complete problems in free groups
Nivat's processing systems: decision problems related to protection and synchronization
On the complexity of some problems on groups input as multiplication tables
On the complexity of deciding fair termination of probabilistic concurrent finite-state programs
\(\varepsilon\)-productions in context-free grammars
Sorting, linear time and the satisfiability problem
Regular languages of nested words: fixed points, automata, and synchronization
The complexity of the exponential output size problem for top-down and bottom-up tree transducers
Logic programs and connectionist networks
An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems
McNaughton families of languages.
Deadlocks and traps in Petri nets as Horn-satisfiability solutions and some related polynomially solvable problems
The equivalence of Horn and network complexity for Boolean functions
New techniques for proving the decidability of equivalence problem
The maximum flow problem is log space complete for P
Parallel models of computation: An introductory survey
LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
On the parallel complexity of discrete relaxation in constraint satisfaction networks
Incremental branching programs
Automata-theoretic techniques for modal logics of programs
On the Average Case Complexity of Some P-complete Problems
Computational complexity of some problems involving congruences on algebras
Oracle branching programs and Logspace versus \(P^*\)
Algorithms for the maximum satisfiability problem
Prediction-preserving reducibility
Priority systems with many identical processes
Complexity results for prefix grammars
Descriptional complexity of iterated uniform finite-state transducers
Title not available (Why is that?)
Bounded self-stabilizing Petri nets
On the complexity of computational problems associated with simple stochastic games
DECIDABILITY AND COMPLEXITY ANALYSIS OF FORBIDDEN STATE PROBLEMS FOR DISCRETE EVENT SYSTEMS
Pushdown reachability with constant treewidth
Perspective on complexity measures targeting read-once branching programs
On problems with short certificates
Universal proof theory: feasible admissibility in intuitionistic modal logics
Games for active XML revisited
A short certificate of the number of universal optimal strategies for stopping simple stochastic games
Computational complexity and constraint logic programming languages
Resolution deduction to detect satisfiability for another class including non-Horn sentences in propositional logic
On the parallel complexity of loops
Complexity and expressive power of second-order extended Horn logic
Interconvertibility of a class of set constraints and context-free-language reachability
COMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRA

This page was built for publication: Complete problems for deterministic polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1235982)