Output details
11 - Computer Science and Informatics
University of Leeds
A Tight Karp-Lipton Collapse Result in Bounded Arithmetic
<10>Karp-Lipton collapse results explore complexity consequences of the (unlikely) assumption that SAT is decidable by polynomial-size circuits. We present the *first* Karp-Lipton collapse which is tight in the sense that the collapse consequence even characterises the assertion. This answers a question posed by Turing award winner Stephen Cook and Jan Krajicek. The technically involved proof formalises a hard/easy argument in bounded arithmetic. The conference version appeared at CSL'08 (one of the two best conferences in computational logic) and was selected (among 7 from 31 papers) for the special edition in ACM Transactions on Computational Logic.