关于Ramsey数的若干研究

Ramsey数N(q_1,q_2,…,q_n;t)是组合数学中很有意义的一个数,但至今人们只求出了它的很有限个具体数值,因此,给出N(q_1,q_2,…,q_n;t)的尽可能小的上界和尽可能大的下界是有意义的.     

枚举素跨比极峰值的算法研究

称相邻两素数的差的绝对值为该两素数间的跨度,称两相邻素数间的跨度与该两相邻素数中较小者之比为该较小素数的素跨比,在由所有的素跨比按其所对应的素数从小到大的次序构成的素跨比序列中,若某素跨比大于排在其后的每一个素跨比,则称该素跨比为素跨比极峰值。 素跨比代表了素数性质的一个重要方面,素跨比极峰值的分布在某种程序上揭示了素数     

Ramsey数r（k,l）的新下界公式

本文给出并证明了Ｒａｍｓｅｙ数ｒ（ｋ，ｌ）的一个新下界公式ｒ（ｋ，ｌ）≥１．５（ｋ－１）（ｌ－１），此下界公式与文献［１，２］所给出的下界公式ｒ（ｋ，ｌ）＞（ｎ２＾ｎ／２）／（ｅ√２，ｎ＝ｍｉｎ（ｋ，ｌ）相比，当ｋ，ｌ较小时，或ｋ，ｌ相差较大明要优越。     

Ramsey数的性质研究

本文得出了若干有关Ramsey数性质的结论,这些结论可直接用来推导Ram-sey数的下界公式,也可用来改进已有的Ramsey数的下界结果,本文中定理的证明思路,还能用于研究其它的图论和组合数学问题。     

关于相对化的P=?NP问题的注记

问题P=?NP在相对化后随外部信息集的不同可能有相反的答案.本文得出如下进一步的结果:1.存在着无穷个集合S₁,S₂,…,这些集合的复杂度依次严格上升,并且在它们分别地作为外部信息集合,能交替地使命题P=NP和P≠NP,相对比;2.存在着在NP类之外的递归集A,使得P=NP等价于P^A=NP^A.     

离线非确定图灵机的空间─—访问数对偶定理

离线非确定图灵机的空间─—访问数对偶定理宋恩民，李行长（华中理工大学计算机系）本文讨论的是离线非确定图灵机的计算所使用的空间与对工作单元的访问次数之间的对偶问题，这是在计算理论中的一个重要问题（［ｎ］，［２］）。本文证明了，在离线非确定的情况下，当ｆ...     

求Ramsey数下界的循环巧妙图搜索算法研究

本文研究通过构造循环巧妙图而搜寻Ｒａｍｓｅｙ数下界的算法，给出了一个效率较高的算法，该算法已经编程实现，并由此得出了一个具有４６点（４，７）循环巧妙图，从而证明了ｒ（４，７）≥４７。     

Ramsey数的若干新性质

Ramsey数N(q_1,q_2,…,q_n;t)是组合数学中很有意义的一类数.经过研究,作者得到了以下结果,利用这些结果能导出一些Ramsey数的新下界. 本文所用代表数的符号均表示任意正整数. 定理1 若q_0、q_1、…、qn≥t≥2,则N(q_0+q_1-1,q_2,q_3,…,q_n;t)≥N(q_0.q_2,q_3…,q_n;t)+N(q_1,q_2,…,q_n;t)-1.     

确定Ramsey数下界值的随机算法

文[1—2]借助于计算机得到了几个Ramsey数的下界值,但由于计算机确定Ramsey数的下界值往往需要判断多达指数级的各种情况,因此所需的计算时间常使人难以接受.本文提出了一种确定Ramsey数r(k,l)下界值的随机算法,该算法试图随机而有针对性地构造一个有n个顶点的简单图G,使G中既无k个顶点的团又无l个顶点的独立集,从而确定n+1是r