Under the auspices of the Computational Complexity Foundation (CCF) REPORTS > DETAIL:

### Paper:

TR03-030 | 27th February 2003 00:00

#### Certifying Unsatisfiability of Random 2k-SAT Formulas using Approximation Techniques TR03-030
Authors: Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich
Publication: 23rd April 2003 21:27
Keywords:

Abstract:

Abstract. It is known that random k-SAT formulas with at least
(2^k*ln2)*n random clauses are unsatisfiable with high probability. This
result is simply obtained by bounding the expected number of satisfy-
ing assignments of a random k-SAT instance by an expression tending
to 0 when n, the number of variables tends to infinity. This argument
does not give us an efficient algorithm certifying the unsatisfiability of a
given random instance. For even k it is known that random k-SAT in-
stances with at least Poly(logn)*n^(k/2) clauses can be efficiently certified
as unsatisfiable. For k = 3 we need at least n^((3/2)+epsilon) random clauses.
In case of even k we improve the aforementioned results in two ways.
There exists a constant C such that 4-SAT instances with at least C*n^2
clauses can be efficiently certified as unsatisfiable. Moreover, we give
a satisfiability algorithm which runs in expected polynomial time over
all k-SAT instances with C*n^(k/2) clauses. Our proofs are based on the
direct application of known approximation algorithms on the one hand,
and on a recent estimate of the theta-function for random graphs with a
linear number of edges, on the other hand.

ISSN 1433-8092 | Imprint
{"ft_lang_label":"__label__en","ft_lang_prob":0.91892743,"math_prob":0.9207482,"size":1255,"snap":"2022-40-2023-06","text_gpt3_token_len":292,"char_repetition_ratio":0.12470024,"word_repetition_ratio":0.040609136,"special_character_ratio":0.20796813,"punctuation_ratio":0.05957447,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.98913574,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16],"im_url_duplicate_count":[null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-10-01T17:51:10Z\",\"WARC-Record-ID\":\"<urn:uuid:24dc4178-8c46-4772-ab55-57472caae57e>\",\"Content-Length\":\"21916\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:b83d189f-2c62-44e9-bc9d-ca494c57bd82>\",\"WARC-Concurrent-To\":\"<urn:uuid:247b48ad-2b37-4a25-b2d8-8db93c2241bd>\",\"WARC-IP-Address\":\"132.77.150.87\",\"WARC-Target-URI\":\"https://eccc.weizmann.ac.il/report/2003/030/\",\"WARC-Payload-Digest\":\"sha1:3W4K7YOS5ZLQ6FWLGKFOI77RTM7EVOKA\",\"WARC-Block-Digest\":\"sha1:6U4YCJ4TTX4CZ5PPSCKOSON6ETWFM2CO\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-40/CC-MAIN-2022-40_segments_1664030336880.89_warc_CC-MAIN-20221001163826-20221001193826-00240.warc.gz\"}"}