The NP-Completeness Column: An Ongoing Guide
Explore this paper's citation graph
Summary
It is proved here that the number ofrules in any irredundant Horn knowledge base involving n propositional variables is at most n 0 1 times the minimum possible number of rules.
- Type
- article
- Published
- 1982-01-01
- Cited by
- 35,564
- References
- 732
- OpenAlex
- https://openalex.org/W2148043549
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:2211006
Keywords
Completeness (order theory), Column (typography), Mathematical proof, PSPACE, Presentation (obstetrics)
References
- Well structured parallel programs are not easier to schedule
- Probabilistic Machines Can Use Less Running Time
- On the complexity of evaluating multivariate polynomials
- The Complexity of Go
- The Computational Complexity of the m -Center Problems on the Plane
- On the Computational Complexity of Combinatorial Problems
- Polygon-to-Chain Reductions and Network Reliability.
- Bounds on minimax edge length for complete binary trees
- Topics in Computational Geometry
- New Mathematical Diversions from "Scientific American"
- An application of higher reciprocity to computational number theory
- NP-Complete Problems on Some Tree-Structured Graphs: a Review
- Drawing planar graphs
- Sur le problème des courbes gauches en Topologie
- At play in the fields of scheduling theory
- Approximate algorithms for the edge-coloring of graphs
- CorrigendumAverage time analyses of simplified Davis-Putnam procedures: Information processing letters 15(2) (September 1983) pp. 72–75
- NP-Completeness of the Hamiltonian Cycle Problem for Bipartite Graphs
- Intersection Graph Algorithms
- A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus
Cited by
- Optimal level schedules for mixed-model, multi-level just-in-time assembly systems
- An Illustrative Discussion of Different Perspectives in Network Engineering
- Evaluation of parallel metaheuristics
- Computational complexity in P systems
- On the Complexity of the MPA Problem in Probabilistic Networks
- Metaheurísticas de optimización combinatoria: uso de Simulated Annealing para un problema de calendarización
- Asymmetric Boltzmann machines
- Scalable QoS routing in MPLS networks using mobile code
- On the Computational Complexity of Planning and Story Understanding
- Manipulation of copeland elections
- Data Path Allocation Techniques for High-level Synthesis of Low BIST Area Overhead Designs
- Connectionist approaches for solver selection in constrained project scheduling
- Complexity Results for Mixed-Model Assembly Lines with Approximation Algorithms for the Single Station Case
- Partitioning Graphs into Two Trees
- Process scheduling in heterogeneous multiprocessor systems
- Supporting Uncertainty in Standard Database Management Systems
- Computational complexity of inferring phylogenies from chromosome inversion data.
- Polynomial Time Manhattan Routing Without Doglegs - a Generalization of Gallai's Algorithm
- System-level memory power and performance optimization for system-on-a-chip embedded systems
- A Preemption-Aware On-line Routing Algorithm for MPLS Networks