搜索筛选:
搜索耗时2.2111秒,为你在为你在102,285,761篇论文里面共找到 19 篇相符的论文内容
发布年度:
[期刊论文] 作者：吕义忠,
来源：南京航空航天大学学报 年份：1998
为了使用Ｆｌｅｕｒｙ的算法，在每一步都必须去判断图Ｇ－ｅ的连通性［１］。本文将给出一个十分简单的判断图的连通性的线性算法。为了证明它的正确性，本文将证明以下三个条件是等价的：（１）图Ｇ是连通的；（２）Ｍ的任意......
[期刊论文] 作者：吕义忠,
来源：计算机研究与发展 年份：1999
ＮＰ是否包含在Ｐ／ｐｏｌｙ中的问题迄今仍为开问题。８０年代初证明了如果ＮＰ∪→Ｐ／ｐｌｙ，则ＰＨ＝∑２，最近，又有了如果ＮＰ∪→Ｐ／ｐｏｌｙ，则ＰＨ＝ＺＰＰ的问题。文中将借助于广义一阶逻辑ζ（ι）及其上的模型论以证明存在ＮＰ中的语言，它们没有多项式......
[期刊论文] 作者：吕义忠,
来源：南京大学学报：自然科学版 年份：1989
紧致性是一阶模型论的重要性质之一,本文给出紧致性定理的一个比较完整的纯语义证明。...
[期刊论文] 作者：吕义忠,
来源：南京航空航天大学学报（英文版） 年份：2004
复杂性研究中的一个重点问题是非一致复杂类的测度问题.Aldman已经证明了BPPP/poly,而Kannan证明了EXPSPACEP/poly.本文提出逼近接受的概念,用来讨论K-团问题的非一致复...
[期刊论文] 作者：吕义忠,
来源：计算机工程与应用 年份：1985
前言 从1983到1984,在西德的Aachen、意大利的Florence和法国的Paris等地召开了五次国际数理逻辑和计算机科学软件会议,根据会议动态,数理逻辑与计算机软件相结合在人工智能和数据库管理等方面的发展和应用十分引人注目。为了深入了解计算机的人工智能功能......
[期刊论文] 作者：吕义忠,郭容,
来源：南京大学学报：自然科学版 年份：1993
如果允许1次说谎的Ulam集U~(1)=(x_1,x_0)为n可解,则恒有x_1(n十1)十x_0≤2~π(见[3]命题3(ii))现设U~(1)的解为k,又设l=min(x_1(n+1)+x_0≤2~π),本文证明,k=l当且仅当x_1为...
[期刊论文] 作者：吕义忠,郭容,
来源：数学年刊：A辑 年份：1992
本文得到了对任意正整数m的Ulam问题的一般解法。...
[期刊论文] 作者：吕义忠,顾蕾,
来源：计算机研究与发展 年份：1992
one-way函数是否存在迄今仍为一个开问题.文献[5]提出了分层one-way函数的概念.本文在布尔线路中讨论了分层one-way函数的存在性并得到结果:（1）给定k≥j】0,若存在j-honest的2k...
[期刊论文] 作者：吕义忠,陈玉泉,
来源：计算机研究与发展 年份：1995
本文引进相对的多项式化归和相对多一多项式同构等概念，对ＵＰ、βｎ的ＦｅｗＰ的相对完全集讨论它们的相对同构问题。并得到如下结果：１（１）对任何≤ｍ＾Ｐ，Ｂｎ－βｎ＾Ｂｎ完全集Ｃ，Ｃ≈Ｐ＾ＢｎＡｎ←→Ｃ为Ｐ＾Ｂｎ柱。（２）对任何≤ｍ＾Ｐ，Ｂ－ＦｅｗＰ＾Ｂ完全集Ｃ，Ｃ≈Ｐ＾Ｂ∪Ａｎ←→Ｃ为......
[期刊论文] 作者：陈玉泉,吕义忠,
来源：南京大学学报：数学半年刊 年份：1995
本文给出ＵＰ、βｎ和ＦｅｗＰ与ＮＰ和ＰＳＰＡＣＥ相对于Ｔａｌｌｙ集的分离结果。同时还引入强ｎ－范畴机和强ｐ－范畴机等概念，并比较它们所接受的语言类在Ｐ－ＮＰ情况下的性质，得到如下结果；存在递归ｏｒａｃｌｅＡ和Ｂ，以及递归Ｔａｌｌｙ集Ｔ和Ｔ＾１，使得：（１）Ｐ＾Ａ－β＾Ａｎ且Ｐ＾ＡＲ≠β＾ＡＮ，（２）Ｐ＾Ｂ＝ＦｅｗＰ＾Ｂ......
[会议论文] 作者：吕义忠,郭容,
来源：中国计算机学会理论计算机科学91学术年会 年份：1991
...
[期刊论文] 作者：吕义忠,高晓波,
来源：南京航空航天大学学报：英文版 年份：2000
复杂性研究中的一个重点问题是非一致复杂类的测度问题。Aldman已经证明了 BPP P/poly,而 Kannan证明了 EXPSPACE P/poly。本文提出逼近接受的概念 ,用来讨论 K-团问题的非一...
[期刊论文] 作者：吕义忠,孙慧澄,
来源：计算机研究与发展 年份：1991
[He 88]在第三部分“UP有图灵完全语言吗”?的标题下构造了一个递归Oracle A,并且证明UP~A 无图灵完全语言。本文构造了一个NP Oracle B 并且证明UP~B 有多项式完全语言(从而...
[期刊论文] 作者：吕义忠,孙慧澄,
来源：南京航空航天大学学报 年份：1996
在计算复杂性领域里，大多数复杂类都是按照接受它们的图灵机而加以描述的。８０年代初，人们广泛关注被多项式大小的线路可判定的集合类并且得到了许多有趣的结果。但是，迄今是否ＮＰ完全......
[期刊论文] 作者：吕义忠,刘建斌,
来源：软件学报 年份：1994
本文对Ｏｒａｃｌｅ图灵机在接受计算中的查询次数加以限制，并且得到结果：存在无穷多个非多等价的递归集Ａ，Ｂ，Ａ＇，Ｂ＇，Ａ＇＇，Ｂ＇＇，Ａ＇＇＇，Ｂ＇＇＇，它们满足性质：Ｐ（Ａ，ｑ）＝Ｐ（Ａ，ｑ＋１），Ｐ（Ｂ，ｑ）≠Ｐ（Ｂ，ｑ＋１），ｐ（Ａ＇，ｑ）＝Ｐ（Ａ＇），Ｐ（Ｂ＇，ｑ）≠Ｐ（Ｂ＇），ＮＰ（Ａ＇＇，ｑ＋１），ＮＰ（Ｂ＇＇，ｑ）≠ＮＰ（Ｂ＇＇，ｑ＋１），ＮＰ（Ａ＇＇，ｑ）＝ＮＰ（Ａ＇＇），ＮＰ（Ｂ......
[期刊论文] 作者：吕义忠,孙慧澄,
来源：自然杂志 年份：1995
自从1965年J.Edmonds和A.Cobham提出P-NP问题以来已有30年的研究历史。目前环绕这个问题的大量学术论文和研究专著已使它发展成为计算机科学中最新和最活跃的研究领域之...
[期刊论文] 作者：吕义忠,高晓波,,
来源：南京航空航天大学学报（英文版） 年份：2000
复杂性研究中的一个重点问题是非一致复杂类的测度问题.Aldman已经证明了BPPP/poly,而Kannan证明了EXPSPACEP/poly.本文提出逼近接受的概念,用来讨论K-团问题的非一致复...
[期刊论文] 作者：吕义忠,裴列笠,,
来源：南京大学学报(自然科学版) 年份：1987
我们在此给出一个在意大利 IDS—80图形计算机系统上实观的符号库。我们扼要地溉述了该库的构造和使用方法。这个库是一个遵循机械设计统一标准 UNI 的标准符号库并且我们的方法(模型扩张)是新的和有价值的。......
[期刊论文] 作者：曹子宁,吕义忠,石纯一,
来源：软件学报 年份：2001
One-Way函数在计算复杂性和密码技术中均有重要的应用.将Grollmann和Selman的结果推广到相对化和非一致复杂类的情形,证明了复杂类UP/poly,UP,P/poly等之间的包含关系与强相...
相关搜索：
