多项式时间谱系和外部信息源A∈PH/Poly

可计算复杂性理论的一个中心问题是多项式时间谱系是否崩溃.Balc(?)zar、Book和Sch(?)ning在文献[1]中利用稀疏集作为外部信息源研究了这个问题,他们证明了如下重要定     

再论有限群中元的阶之集

设G为有限群,π_e(G)为G的元的阶之集.对正整数集的任一子集m,令h(m)为满足π_e(G)=m的有限群G的同构类类数.文献[1]中作者提出了如下猜想:对正整数集的所有子集,h(m)∈{0,1,∞}.最近,Mazurov证明了如下结果:如果m=π_e(L_3(5)),则h(m)=2.于是他给出了上述猜想的一个否定回答.本文将给出h(m)=2的另一个例子.定理 设G是有限群.则π_e(G)=π_e(L_3.(9)),当且仅当G≌L_3(9)或L_3(9).2_1.由于没有找到集合m满足h(m)=3,我们提出如下问题.问题 是否存在一个正整数k,使得对正整数集的任一子集m,总有h(m)∈{0,     

E~3中平均曲率向量为固有函数的曲面

B.Y.Chen指出:E~n中一个紧致子流形x:M~m→E~n是有限型的,当且仅当它的平均曲率向量h满足方程 P(△)h=0,其中P是一个非平凡多项式,△是M上的Laplace算子。寻找满足上述方程的子流形也是很有意思的问题。我们证明了:     

周期半群环的单位元的存在性

Ponizovski(?)在文献[1]中提出下面的问题:问题 什么样的半群环是有单位元的环?李方在文献[2]中研究了纯正半群环的情形,本文考虑周期半群环的情形,将周期半群环的单位元存在性问题归结到幂等元生成的子半群环的单位元存在性问题,符号同文献[2].本文的主要结果如下:定理 设S是周期半群.则RS含单位元当且仅当R含单位元,且存在E(S)的一个有限子集U,使得S=SU=US,在此条件下,有I_(RS)=I_R.此定理的证明难点在于下面的引理的证明.引理 设S是周期半群.若RS含单位元,则R含单位元.引理的证明大意:假设集合A={T:T是周期半群,RT含单位元,但R〈E(T)〉不     

语言时间扩展——一种功能时间程序设计方法

1 问题计算机软件系统中存在两类执行时间约束.一类为系统各部分之间时间先后的相对约束、如互斥、同步等;另一类为系统某一部分执行时间上的绝对约束,此类典型实例为实时系统.传统程序设计注重于描述系统的功能,对于第一类约束,常采用隐式的方法,如PV操作、管程等实现.这种隐式的方法,增加了系统设计和语义验证的难度,影响软件开发效率.对于第二类约束,目前往往是设计并使用一种新的语言:实时程序设计语言来完成.     

某些Henon映射的非游荡集

对于Henon映射 ,Ta ,b(x ,y) =(1-ax2 y ,bx) ,Benedicks和Carleson证明了在 (a ,b) =(2 ,0 )附近且b >0 ,存在一个正测度集合E ,如果 (a ,b)∈E ,对应的映射Ta ,b有奇怪吸引子 .Viana猜测 ,对于 (a ,b)∈E ,非游荡集Ω(Ta,b) =Λa ,b∪ { qa ,b} ,其中Λa,b是奇怪吸引子 ,qa,b是映射Ta ,b在第三象限内的不动点 .我们证明了对于正测度集合E1 E这个猜测成立 .     

百万美元数学难题的解决……

破解这一数学难题将会使破解者变得富有,但是它对于我们所有人的价值却是无法计算的。如果P=NP,为什么会关系如此重大,《新科学家》杂志为此作出了解释——"亲爱的同事们,我很高兴地宣布,我已经证明了P不等同于NP,这一证明用10磅和12磅的字体附在后面"。维奈     

由一类图的着色导出的素数子集的分类

设P表示全体素数的集合,D(?)P。令G(Z,D)表示这样一个图:它的顶点集是全体整数的集合,两个顶点x和y之间有边连结当且仅当|x—y}∈D。Eggleton,Erds和Skilton等在文献中证明了:不论对任何素数子集D(?)P,图G(Z,D)的色数至     

O(n)时间有限Abel群同构检验算法

计算群论和复杂性理论中的一个重要问题是,有限群同构检验是可行的,还是NP完全的?这个问题迄今没有解决。C.Savage和陈溧分别得到一个O(n~2)时间的n阶Abel群同构检验算法。 本文得到,存在O(n)时间的n阶Abel群同构检验算法。即使使用对数成本的RAM,完成这样     

关于相对化的P与NP问题的一个注记

李祥在文献[1]中得到如下结果: 定理1 下述命题等价: (1) P≠NP; (2) NPT~∞是递归可表现的类; (3) ((?)A∈NP)(P~A≠NP~A); (4) ((?)A∈NP)(P~A≠NP~A或A∈NPT~∞)。 这里,NPT~∞表示全体无穷的NP图灵完全语言构成的集类。针对定理1的第4款,李祥提出了如下问题:是否有两个无穷的NP图灵完全语言A及B,使P~A=NP,P~B≠NP~B?~(**)本文对     

图的二分问题唯一全局最优解实例与骨架计算复杂性

骨架分析是近年来理论计算机科学研究的热点, 对于NP-难解问题的启发式算法设计具有重要意义. 由于骨架计算复杂性研究十分困难, 现有的骨架分析方法多采用实验统计手段. 针对现有方法中存在的骨架规模小的缺陷, 给出图的二分问题GBP(graph bi-partitioning problem)的唯一全局最优解实例构造算法, 有效提高了骨架的规模. 同时, 利用该算法从理论上证明了寻找GBP问题的完整骨架属于NP-难解问题, 即在P≠NP的假设下, 不存在多项式时间的算法可以确保得到GBP问题的完整骨架. 本文的工作拓广了骨架计算复杂性研究的范围, 所提出的唯一全局最优解实例构造算法对于NP-难解问题启发式算法设计亦具有较高的参考价值.     

Yang-Mills-Higgs-Kibble系统的静态解

一、引言无质量的杨-米尔斯场在提供静态有限能量解上和与它相应的Abel场不同.这个情况当且仅当时空为5维时发生,这时这些解对应于等价的4维欧氏空间中存在着瞬子解.在最近的工作中,胡和生考虑了有质量Yang-Mills场中同样的问题,特别证明了在5维时不存在静态解.虽然,如所周知,从一个环路的水平出发,在质量趋向于零的极限时存在着不连     

求解析取范式永真性问题的一个近似快速算法

NP完全问题是一类在计算复杂性理论中被证明为较难求解的问题,这类问题中包含有很多在理论和实际中很有意义的问题。NP完全问题中的一个问题的对偶问题若存在快速(多项式意义下)的求解算法,则所有NP完全问题都有快速的求解算法。但目前人们还没有找到一个求解NP完全问题的真正快速算法,并且有迹象表明求解NP完全问题的真正快速算法是不存在的。本文针对一个典型的NP完全问题的对偶问题——析取范式永真性     

自由格的若干定理

格的一个等式类K上由一个弱偏格生成的自由格的定义可以按自由代数的理论或仿照K上由偏格生成的自由格的定义来给出。 定理1(存在定理) 设u=相似文献   

关于局部连通性的注记

文[1,2]对“连续开映射保持局部连通性”的经典结果分别作了改进。本文继续改进了文[1,2]的结果。定义1 对拓扑空间x的子集A,如果ACint C1(A)(int和C1分别表示集合的内部和闭包),则称它为pre-open集。定理1 设x是拓扑空间,则当且仅当对x∈x和包含x的开集U,存在一个pre-open连通集A,使得时,x是局部连通的。定理2 设x是拓扑空间,则当且仅当x的     

含瞬时态生灭Q矩阵问题

设E为非负整数集Z_+或整数集Z.称E×E上矩阵Q=(q_(ij):i,j∈E)为生灭矩阵,如果Q满足以下条件: (ⅰ)q_(ij)=0 |i-j|>1,0相似文献   

反链方法及其在正则三值逻辑函数计数上的应用

为适应不确定推理之需要,Mukaidono提出并系统地研究了正则三值逻辑函数的理论.这类函数个数的计算十分复杂,至今仅对自变量个数小于7的情形提出了若干结果.本文将反链方法与该类计算联系起来,从而为解决该类问题提供了一种新的可能途径.定义1 　设E={0,1/2,1},在E上除通常序“≤”外,再定义偏序(?)为:0(?)1/2,1(?)1/2,i(?)i.这两种序在E~n上各诱导出相应的乘积序,仍记为“≤”或“(?)”.映射f:E~n→E称正则函数,若(?)a,b∈E~n,当a(?)b时f(a)(?)f(b).正则函数f:E~n→E称单调函数,(?)a,b∈E~n,当a≤b时f(a)≤f(b).以下用F(n,R)记全体n元正则函数之集,用F(n,M)记全体n元单调函数之集.定义2 设(P,≤)是非空偏序集,a,b∈P.若有c∈P使c≤a且c≤b,则称a与b有公根.设A与B是P中的反链,若(?)a∈A和(?)b∈B,a与b有(无)公根,则称序对(A,B)为全(无)公根反链对.以下用E(n)表示(E~n,(?))中全体无公根反链对之集.令N(n)={1,…,n}.W(n)={L:L(?)N(n),L≠φ},用N(n,C)表示(W(n),(?))中全体全公根反链之集.定义3 设a=(a_1,…,a_n)∈(E~n.(?)).     

关于Amann的一个定理的注记

设E是Banach空间,P为E中锥,f:R×P→P。关于算子方程x=f(λ,x)多重解的存在性,H.Amann进行了深入的研究,他证明了 定理(H.Amann) 设E为Banach空间,P为E中正规体锥,f:R~+×P→P全连续,二次连续右可微,f(0,0)=0,λ~*=sup{λ∈R~+:(?)∈P使     

关于对角型不定方程sum from i=1 to n(a_ix_i~u)=0

文献[1]有一个猜想:m是正偶数,整数a,b,c满足(a±b±c)(a±b)(a±c)(b±c)≠0,u充分大且使q=um+1素,则不定方程ax~u+by~u= cz~u仅有平凡解.Granville证明了此猜想.本文在较少的条件下,对更一般的问题得到了更好的结论.定义 a_1,…,a_n是整数,ε_i∈{0,1,-1},若sum from i=1 to nε_ia_i=0当且仅当ε_i全为零,则称整数 a_1,…,a_n简单无关.定理 设m>1是整数,a_1,…,a_n简单无关,且     

某些交错群和对称群的刻划

设G为群,π_e(G)为G中元的阶之集.在文献中作者证明了G(?)A_n当且仅当(1)π_e(G)=π_e(A_n),(2)|G|=|A_n|.对某些交错群,如A_5,A_7,A_8可以仅用上述条件(1)加以刻划.在文献中作者证明了对所有的对称群S_n,n≥2,可用上述条件(1)和(2)加以刻划.然而,对群S_i,i=2,3,…,6均不能由条件(1)单独确定.