Sorting, linear time and the satisfiability problem
type: Item
instance of: scholarly article
title: Sorting, linear time and the satisfiability problem
zbMATH Open document ID: 0860.68035
DOI: 10.1007/BF02127798
author: Etienne Grandjean
published in: Annals of Mathematics and Artificial Intelligence
publication date: 1996-12-01T00:00:00Z
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68W10
zbMATH DE Number: 951951
zbMATH Keywords: Horn renaming
zbMATH Keywords: NP-complete problem
describes a project that uses: Ltur
MaRDI profile type: Publication
cites work: Q4091421
cites work: Q3948568
cites work: Fast probabilistic algorithms for Hamiltonian circuits and matchings
cites work: Recognizing disguised NR(1) instances of the satisfiability problem
cites work: On pointers versus addresses
cites work: Q5668821
cites work: Unique satisfiability of Horn sets can be solved in nearly linear time
cites work: Q3750122
cites work: A uniform method for proving lower bounds on the computational complexity of logical theories
cites work: The complexity of theorem-proving procedures
cites work: Short propositional formulas represent nondeterministic computations
cites work: Time bounded random access machines
cites work: Q3651735
cites work: Q4283234
cites work: Exact complexity of problems of incompletely specified automata
cites work: Linear time transformations between combinatorial problems
cites work: Linear-time algorithms for testing the satisfiability of propositional horn formulae
cites work: Q4692802
cites work: Q4198056
cites work: A Natural NP-Complete Problem with a Nontrivial Lower Bound
cites work: A Nontrivial Lower Bound for an NP Problem on Automata
cites work: Invariance properties of RAMs and linear time
cites work: Linear Time Algorithms and NP-Complete Problems
cites work: Q4474839
cites work: Q4281688
cites work: Q3826533
cites work: A linear algorithm for renaming a set of clauses as a Horn set
cites work: Unique Horn renaming and Unique 2-Satisfiability
cites work: On Time Versus Space
cites work: Q3862379
cites work: The Complexity of Very Simple Boolean Formulas with Applications
cites work: Nondeterministic Space is Closed under Complementation
cites work: Unification as a complexity measure for logic programming
cites work: Space-bounded reducibility among combinatorial problems
cites work: Complete problems for deterministic polynomial time
cites work: New problems complete for nondeterministic log space
cites work: Fast Simulation of Turing Machines by Random Access Machines
cites work: Q5585020
cites work: Renaming a Set of Clauses as a Horn Set
cites work: The complexity of on-line simulations between multidimensional turing machines and random access machines
cites work: LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
cites work: Q4281695
cites work: Random access machines with multi-dimensional memories
cites work: On O(Tlog T) reduction from RAM computations to satisfiability
cites work: The complexity of satisfiability problems
cites work: Satisfiability Is Quasilinear Complete in NQL
cites work: Storage Modification Machines
cites work: A nonlinear lower bound for random-access machines under logarithmic cost
cites work: Q4023850
cites work: Complexity problems in computational theory
cites work: The problem of space invariance for sequential machines
cites work: Power indices and easier hard problems
cites work: The method of forced enumeration for nondeterministic automata
cites work: Depth-First Search and Linear Graph Algorithms
cites work: Q4385524
cites work: Q4385515
cites work: Q3707407
cites work: Q4038687
full work available at URL: https://doi.org/10.1007/bf02127798
OpenAlex ID: W2066617111
description: scientific article; zbMATH DE number 951951