Sorting, linear time and the satisfiability problem
From MaRDI portal
Publication:1817067
DOI10.1007/BF02127798zbMath0860.68035OpenAlexW2066617111MaRDI QIDQ1817067
Publication date: 1 December 1996
Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02127798
Related Items
Algebraic and logical characterizations of deterministic linear time classes ⋮ Unnamed Item ⋮ On unique graph 3-colorability and parsimonious reductions in the plane ⋮ Graph properties checkable in linear time in the number of vertices ⋮ A descriptive complexity approach to the linear hierarchy. ⋮ The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness ⋮ Exact complexity of problems of incompletely specified automata ⋮ Enumeration complexity of conjunctive queries with functional dependencies ⋮ Nonerasing, counting, and majority over the linear time hierarchy ⋮ Linear time and the power of one first-order universal quantifier ⋮ On the expressive power of monadic least fixed point logic
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unique Horn renaming and Unique 2-Satisfiability
- On O(Tlog T) reduction from RAM computations to satisfiability
- Random access machines with multi-dimensional memories
- A uniform method for proving lower bounds on the computational complexity of logical theories
- Short propositional formulas represent nondeterministic computations
- The method of forced enumeration for nondeterministic automata
- The problem of space invariance for sequential machines
- LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
- Fast probabilistic algorithms for Hamiltonian circuits and matchings
- Space-bounded reducibility among combinatorial problems
- Complete problems for deterministic polynomial time
- A linear algorithm for renaming a set of clauses as a Horn set
- Invariance properties of RAMs and linear time
- Exact complexity of problems of incompletely specified automata
- Time bounded random access machines
- Unique satisfiability of Horn sets can be solved in nearly linear time
- The Complexity of Very Simple Boolean Formulas with Applications
- A Nontrivial Lower Bound for an NP Problem on Automata
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Unification as a complexity measure for logic programming
- A Natural NP-Complete Problem with a Nontrivial Lower Bound
- Fast Simulation of Turing Machines by Random Access Machines
- A nonlinear lower bound for random-access machines under logarithmic cost
- Nondeterministic Space is Closed under Complementation
- Recognizing disguised NR(1) instances of the satisfiability problem
- Storage Modification Machines
- Linear time transformations between combinatorial problems
- Complexity problems in computational theory
- The complexity of on-line simulations between multidimensional turing machines and random access machines
- New problems complete for nondeterministic log space
- On Time Versus Space
- Satisfiability Is Quasilinear Complete in NQL
- Renaming a Set of Clauses as a Horn Set
- Linear Time Algorithms and NP-Complete Problems
- On pointers versus addresses
- The complexity of satisfiability problems
- Depth-First Search and Linear Graph Algorithms
- The complexity of theorem-proving procedures
- Power indices and easier hard problems
This page was built for publication: Sorting, linear time and the satisfiability problem
