【摘 要】
：
在计算科学中,NP完全问题在区分可计算问题的复杂度类发挥着重大的作用,不仅是因为任意NP问题都可多项式时间归约到此类问题,而且若存在一个NP完全问题在确定图灵机多项式时
【机 构】
：
上海大学理学院,南昌工程学院理学院
论文部分内容阅读
在计算科学中,NP完全问题在区分可计算问题的复杂度类发挥着重大的作用,不仅是因为任意NP问题都可多项式时间归约到此类问题,而且若存在一个NP完全问题在确定图灵机多项式时间内可解,那么,所有的NP问题都可在多项式时间内解决.现在广泛认为NP完全问题不存在多项式时间算法,尽管尚未有效地证明,但识别一个问题是否为NP完全问题已经显得尤为重要.从描述复杂性角度阐述计算复杂性与逻辑之间的关联,通过具体实例：集合覆盖和控制集问题,讲述如何应用一阶投射方法证明一个NP问题的完全性.这种通过逻辑归约的方法被证明是十分有用
其他文献
利用位移结构的性质和特点,对以往文献中的两类位移算子进行推广,研究了Hankel,Toeplitz和Vandermonde矩阵在三类新型位移算子下的位移秩.此外,给出了位移秩在线性控制系统中
1988年，Lutwak首次明确地提出了经典相交体的概念．2005年，Haberl和Ludwig对经典相交体进行了推广，给出了Lp-相交体的概念．最近，汪卫等提出了广义相交体的概念．主要利用Lp—Brunn—Mi
研究了一类不确定性奇异系统的严格无源和ISS问题．利用线性矩阵不等式（LMI）方法，给出了系统严格无源和ISS的充分条件．当获取的线性矩阵不等式条件不能被满足时，考虑状态反馈问题，并
双曲守恒律方程组的活塞问题可被视为一阶拟线性双曲组的一种特殊的混合初边值问题，运用一阶拟线性双曲组经典间断解的结果，通过拼接子问题的经典解，以构造的方式证明了当活塞的
讨论了分数阶离散混沌系统驱动系统和相应系统都是相同混沌映射、但是参数不同时的同步问题，采用了参数自适应算法实现了分数阶离散logistic映射的同步，并且给出了同步的充分条
首先研究了基于Kac-Moody代数sl（2,C[λ~（-1）,λ）获得一类新的谱问题.得到的谱问题可以视为AKNS谱问题的一个推广,由此可以引出耦合Burgers方程族.作为该方程族的可积特征得到了
利用动力系统理论研究了一类广义K(2,2)方程的紧孤子.研究结果显示,幂零奇点与紧孤子之间存在着密切联系.此外,通过分析幂零奇点,相比于众所周知的三角函数形式的紧孤子,发现
对于增广线性系统,Bai等研究了广义SOR方法（Bai Z Z,Parlett B,Wang Z Q.On generaliged successive overrelaxation methods for augmented linear systems.Numerische Mathe
有向图G^σ的斜能量Es（G^σ）定义为G^σ的斜邻接矩阵特征值的绝对值之和．令H2n,m是顶点个数为2n，边数为m，具有完美匹配且不含偶圈的图的集合．得到了H2n,m中具有最小斜能量的图，其中2
利用分数阶导数算子-∞βt研究线性分数阶振动系统在谐波激励下的稳态响应。采用复指数函数形式的谐波激励，利用待定函数法得到与激励同频率的稳态响应，以及幅频关系和相频关系