已入深夜,您辛苦了!由于当前在线用户较少,发布求助请尽量完整地填写文献信息,科研通机器人24小时在线,伴您度过漫漫科研夜!祝你早点完成任务,早点休息,好梦!

On provably disjoint NP-pairs

作者
Alexander Alexandrovich Razborov
出处
期刊:BRICS Report Series [Aarhus University Library]
卷期号:1 (36) 被引量:99
标识
DOI:10.7146/brics.v1i36.21607
摘要

In this paper we study the pairs (U,V) of disjoint NP-sets representable in a theory T of Bounded Arithmetic in the sense that T proves U intersection V = \emptyset. For a large variety of theories T we exhibit a natural disjoint NP-pair which is complete for the class of disjoint NP-pairs representable in T. This allows us to clarify the approach to showing independence of central open questions in Boolean complexity from theories of Bounded Arithmetic initiated in [1]. Namely, in order to prove the independence result from a theory T, it is sufficient to separate the corresponding complete NP-pair by a (quasi)poly-time computable set. We remark that such a separation is obvious for the theory S(S_2) + S Sigma^b_2 - PIND considered in [1], and this gives an alternative proof of the main result from that paper. [1] A. Razborov. Unprovability of lower bounds on circuit size in certain fragments of Bounded Arithmetic. To appear in Izvestiya of the RAN, 1994.

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
刚刚
wwwjy完成签到 ,获得积分10
1秒前
无语的汉堡完成签到 ,获得积分10
3秒前
3秒前
曹琳完成签到,获得积分10
6秒前
徐zhipei完成签到 ,获得积分10
7秒前
灵巧乐儿发布了新的文献求助10
8秒前
原神大王发布了新的文献求助10
11秒前
11秒前
HONG完成签到 ,获得积分10
12秒前
14秒前
16秒前
16秒前
wwwwwww关注了科研通微信公众号
17秒前
灵巧乐儿完成签到,获得积分10
18秒前
20秒前
zzz完成签到,获得积分10
21秒前
直率的惜寒完成签到,获得积分10
22秒前
22秒前
kiko发布了新的文献求助30
24秒前
故意的棒棒糖完成签到 ,获得积分10
25秒前
27秒前
小新完成签到 ,获得积分10
27秒前
宋忠赫完成签到,获得积分10
27秒前
29秒前
小阿然完成签到 ,获得积分10
29秒前
YOSH发布了新的文献求助10
30秒前
红烧粽子叶完成签到,获得积分10
33秒前
33秒前
wwwwwww发布了新的文献求助10
34秒前
sl发布了新的文献求助30
34秒前
欢欢完成签到 ,获得积分10
37秒前
万能图书馆的应助被Bobo采纳,获得10
39秒前
Crssss的应助被daomaihu采纳,获得100
39秒前
宋忠赫发布了新的文献求助10
40秒前
仔哥完成签到,获得积分10
41秒前
kiko完成签到,获得积分20
42秒前
华仔的应助被一颗星采纳,获得10
42秒前
42秒前
47秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
拉伸高分子熔体中缠结行为的模拟和小角中子散射研究 2000
Sex, Aging, and Death in a Medieval Medical Compendium: Trinity College Cambridge MS R.14.52, Its Texts, Language, and Scribe 500
高分子基功能界面水蒸发材料与应用研究 500
外场增强的水汽发电研究 500
基于结构调控的功能化水诱导发电材料与器件研究 500
基于界面调控的高效湿气发电材料与器件研究 500
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 计算机科学 工程类 有机化学 化学工程 生物化学 物理 复合材料 内科学 催化作用 光电子学 人工智能 细胞生物学 无机化学 物理化学 数学
热门帖子
关注 科研通微信公众号,转发送积分 8189808
求助须知:如何正确求助?哪些是违规求助? 9576985
关于积分的说明 21850907
捐赠科研通 7787770
什么是DOI,文献DOI怎么找? 3435793
关于科研通互助平台的介绍 2559825
邀请新用户注册赠送积分活动 2482680