期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2002
卷号：2002
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We present the first example of a natural distribution on instances of an NP-complete problem, with the following properties. With high probability a random formula from this distribution (a) is unsatisfiable, (b) has a short proof that can be found easily, and (c) does not have a short (general) resolution proof. This happens already for a very low clause/variable density ratio of = log n ( n is the number of variables). This is the first example of such a natural distribution for which general resolution proofs are not the best way for proving unsatisfiability of random instances. Our result gives hope that efficient proof methods might be found for random 3-CNFs with small clause density (significantly less than n ).
= log n ( n is the number of variables). This is the first example of such a natural distribution for which general resolution proofs are not the best way for proving unsatisfiability of random instances. Our result gives hope that efficient proof methods might be found for random 3-CNFs with small clause density (significantly less than 
