Sorting, linear time and the satisfiability problem

DOI10.1007/BF02127798MaRDI QIDQ1817067zbMATH OpenOpenAlexFDO

Authors Etienne Grandjean

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

zbMATH Keywords

NP-complete problemHorn renaming

Mathematics Subject Classification ID

Searching and sorting (68P10) Parallel algorithms in computer science (68W10)

Recommendations

• scientific article; zbMATH DE number 515731
• scientific article; zbMATH DE number 515738
• The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness
• A simplified NP-complete satisfiability problem

Cites work

• scientific article; zbMATH DE number 3936518 (Why is no real title available?)
• scientific article; zbMATH DE number 3986645 (Why is no real title available?)
• scientific article; zbMATH DE number 4101157 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3767009 (Why is no real title available?)
• scientific article; zbMATH DE number 108391 (Why is no real title available?)
• scientific article; zbMATH DE number 177809 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 512978 (Why is no real title available?)
• scientific article; zbMATH DE number 512986 (Why is no real title available?)
• scientific article; zbMATH DE number 515731 (Why is no real title available?)
• scientific article; zbMATH DE number 1142299 (Why is no real title available?)
• scientific article; zbMATH DE number 1142308 (Why is no real title available?)
• scientific article; zbMATH DE number 2079027 (Why is no real title available?)
• scientific article; zbMATH DE number 194823 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• scientific article; zbMATH DE number 3400923 (Why is no real title available?)
• A Natural NP-Complete Problem with a Nontrivial Lower Bound
• A Nontrivial Lower Bound for an NP Problem on Automata
• A linear algorithm for renaming a set of clauses as a Horn set
• A nonlinear lower bound for random-access machines under logarithmic cost
• A uniform method for proving lower bounds on the computational complexity of logical theories
• Complete problems for deterministic polynomial time
• Complexity problems in computational theory
• Depth-First Search and Linear Graph Algorithms
• Exact complexity of problems of incompletely specified automata
• Fast Simulation of Turing Machines by Random Access Machines
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Introduction to algorithms.
• Invariance properties of RAMs and linear time
• LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
• Linear Time Algorithms and NP-Complete Problems
• Linear time transformations between combinatorial problems
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• New problems complete for nondeterministic log space
• Nondeterministic Space is Closed under Complementation
• On O(Tlog T) reduction from RAM computations to satisfiability
• On Time Versus Space
• On pointers versus addresses
• Power indices and easier hard problems
• Random access machines with multi-dimensional memories
• Recognizing disguised NR(1) instances of the satisfiability problem
• Renaming a Set of Clauses as a Horn Set
• Satisfiability Is Quasilinear Complete in NQL
• Short propositional formulas represent nondeterministic computations
• Space-bounded reducibility among combinatorial problems
• Storage Modification Machines
• The Complexity of Very Simple Boolean Formulas with Applications
• The complexity of on-line simulations between multidimensional turing machines and random access machines
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures
• The method of forced enumeration for nondeterministic automata
• The problem of space invariance for sequential machines
• Time bounded random access machines
• Unification as a complexity measure for logic programming
• Unique Horn renaming and Unique 2-Satisfiability
• Unique satisfiability of Horn sets can be solved in nearly linear time

Cited in

(15)

• Linear time and the power of one first-order universal quantifier
• On unique graph 3-colorability and parsimonious reductions in the plane
• A descriptive complexity approach to the linear hierarchy.
• Deterministic sorting in nearly logarithmic time on the hypercube and related computers
• Graph properties checkable in linear time in the number of vertices
• Linear Time Algorithms and NP-Complete Problems
• Exact complexity of problems of incompletely specified automata
• Algebraic and logical characterizations of deterministic linear time classes
• On the expressive power of monadic least fixed point logic
• The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness
• Sorting in linear time?
• Purely Functional Worst Case Constant Time Catenable Sorted Lists
• Enumeration complexity of conjunctive queries with functional dependencies
• Enumeration complexity of conjunctive queries with functional dependencies
• Nonerasing, counting, and majority over the linear time hierarchy

Describes a project that uses

Uses Software

• Ltur

This page was built for publication: Sorting, linear time and the satisfiability problem

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