Output details
11 - Computer Science and Informatics
University of Leeds
Article title
A Tight Karp-Lipton Collapse Result in Bounded Arithmetic
Type
D - Journal article
Title of journal
ACM Transactions on Computational Logic
Article number
22
Volume number
11
Issue number
4
First page of article
-
ISSN of journal
1529-3785
Year of publication
2010
URL
-
Number of additional authors
1
Additional information
<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.
Interdisciplinary
-
Cross-referral requested
-
Research group
None
Citation count
5
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
