A note on disjunctive form tautologies
Abstract
Cook [1] and Karp [2] have shown that a large class of combinatorial decision problems can be solved in time bounded by a polynomial in the size of the problem iff there is a polynomial time procedure for deciding whether a disjunctive formula with at most three literals per disjunct in the propositional calculus is a tautology.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Apr 01, 1973
- Source ID
- 10.1145/1811123.1811124
Entities
People
- Andreas Bernhard Meyer
- D. Brand
- M. Bauer
- M. Fischer
- M. Paterson
Organizations
- Massachusetts Institute of Technology
- Office of Naval Research
- University of Toronto
- University of Warwick