The theorems suggest that Tautology is a good candidate for an interesting set not in [P] and I feel it is worth spending considerable effort trying to prove this conjecture. Such a proof would be a major breakthrough in complexity theory.
Slashdot Deals: Cyber Monday Sale Extended! Courses ranging from coding to project management - all eLearning deals 20% off with coupon code "CYBERMONDAY20". ×
An anonymous reader writes: In the afternoon of May 4, 1971, in the Stouffer's Somerset Inn in Shaker Heights, Ohio, Steve Cook presented his STOC paper proving that Satisfiability is NP-complete and Tautology is NP-hard.