On Random 3-sat

计算机科学 数学 可满足性 组合数学
作者
A. El Maftouhi,W. Fernandez de la Vega
出处
期刊:Combinatorics, Probability & Computing [Cambridge University Press]
卷期号:4 (03): 189-195 被引量:28
标识
DOI:10.1017/s0963548300001590
摘要

Let S be a set of m clauses each containing three literals chosen at random in a set {p1, ¬p1,…,pn, ¬pn} of n propositional variables and their negations. Let be the set of all such S with m = cn for a fixed c > 0. We show, improving significantly over the first moment upper bound , that if m and n tend to infinity with , then almost all are unsatisfiable.
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
更新
大幅提高文件上传限制,最高150M (2024-4-1)

科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
2秒前
五木发布了新的文献求助10
3秒前
7秒前
方远锋发布了新的文献求助10
8秒前
abhiseka发布了新的文献求助10
8秒前
10秒前
13秒前
清萍红檀完成签到,获得积分10
15秒前
kklkimo完成签到,获得积分10
18秒前
isvv完成签到,获得积分10
26秒前
负责冰海完成签到,获得积分10
30秒前
大模型应助欣喜的代容采纳,获得10
30秒前
五木完成签到,获得积分10
33秒前
35秒前
旺仔完成签到,获得积分10
37秒前
111完成签到,获得积分10
38秒前
42秒前
43秒前
sunyanghu369完成签到,获得积分10
47秒前
鱼贝贝发布了新的文献求助10
47秒前
大个应助candleshi采纳,获得30
48秒前
48秒前
guanyu108完成签到,获得积分10
50秒前
abhiseka完成签到,获得积分10
51秒前
黑黑完成签到,获得积分20
53秒前
名丿完成签到,获得积分10
56秒前
刘依梦完成签到 ,获得积分10
57秒前
嘟嘟完成签到,获得积分10
58秒前
李健应助科研通管家采纳,获得10
59秒前
完美世界应助科研通管家采纳,获得10
59秒前
隐形曼青应助科研通管家采纳,获得10
59秒前
SciGPT应助科研通管家采纳,获得10
59秒前
59秒前
秋雪瑶应助科研通管家采纳,获得10
59秒前
高高雨寒完成签到 ,获得积分10
59秒前
1分钟前
1分钟前
1分钟前
依旧完成签到 ,获得积分10
1分钟前
聪慧水池完成签到,获得积分10
1分钟前
高分求助中
Sustainable Land Management: Strategies to Cope with the Marginalisation of Agriculture 1000
Corrosion and Oxygen Control 600
Yaws' Handbook of Antoine coefficients for vapor pressure 500
Python Programming for Linguistics and Digital Humanities: Applications for Text-Focused Fields 500
Division and square root. Digit-recurrence algorithms and implementations 400
行動データの計算論モデリング 強化学習モデルを例として 400
Johann Gottlieb Fichte: Die späten wissenschaftlichen Vorlesungen / IV,1: ›Transzendentale Logik I (1812)‹ 400
热门求助领域 (近24小时)
化学 材料科学 医学 生物 有机化学 工程类 生物化学 纳米技术 物理 内科学 计算机科学 化学工程 复合材料 遗传学 基因 物理化学 催化作用 电极 光电子学 量子力学
热门帖子
关注 科研通微信公众号,转发送积分 2552956
求助须知:如何正确求助?哪些是违规求助? 2178376
关于积分的说明 5614066
捐赠科研通 1899369
什么是DOI,文献DOI怎么找? 948370
版权声明 565554
科研通“疑难数据库(出版商)”最低求助积分说明 504353