The threshold for random k-SAT is 2k log 2-O(k)

• 成果类型: Article
• 署名作者: Achlioptas, D; Peres, Y
• 署名单位: Microsoft; University of California System; University of California Berkeley
• 刊物名称: JOURNAL OF THE AMERICAN MATHEMATICAL SOCIETY
• ISSN/ISSBN: 0894-0347
• DOI: 10.1090/S0894-0347-04-00464-3
• 发表日期: 2004
• 页码: 947-973
• 关键词: probabilistic analysis; unsatisfiability threshold; heuristics