逼近于BPP和PP的概率复杂性语言类的多项式有界线路复杂性研究

本文通过图灵机多项式"?"输出有界和多项式错误输出有界概念的引入,研究了逼近于BPP和PP的一些概率复杂性语言类的多项式有界线路复杂性。     

PH的一种复杂性类分解

本文基于ΔPK-复杂性类给出多项式时间谱系PH的一个分解,并讨论了相关的一些性质。利用该分解给出PH是否只有有限个层次这一重要计算复杂性理论问题的两个充分条件,并证明了NP中稀疏集构成的语言类在LP2∧中。     

欧氏空间货郎担问题的一个多项式时间近似方案的改进与实现

货郎担问题的实例是给定n个结点和任意一对结点{i,j}之间的距离di,j,要求找出一条封闭的回路,该回路经过每个结点一次且仅一次,并且费用最小,这里的费用是指回路上相邻结点间的距离和.货郎担问题是NP难的组合优化问题,是计算机算法研究的热点之一.在过去几十年中,这一经典问题成为许多重要算法思想的测试平台,并促使一些研究领域的出现,如多面体理论和复杂性理论.欧氏空间上的货郎担问题,结点限制在欧氏空间,距离定义为欧氏距离.即使是这样,欧氏空间上的货郎担问题仍然是NP难的.1996年,Arora提出欧氏空间上货郎担问题的第1个多项式时间近似方案.对其中货郎担问题的算法进行了改进：提出一种新的构造方法,使应用于该算法的“补丁引理”结论由常数6改进到常数3,从而使算法的时间复杂度大幅减少;同时,编程实现了该算法,并对实验结果进行了分析.     

具有多项式时间复杂性的离散事件系统安全诊断

离散事件系统的故障诊断能将已发生的不可观故障事件及时诊断出来,但往往容易忽略故障诊断期间系统的安全性.为解决这一问题,提出了一种具有多项式时间复杂性的安全故障诊断方法.先对离散事件系统的安全可诊断性进行了形式化,再通过构造一个非法语言识别器对系统被禁止操作序列进行识别,并在此基础上构建了一个对系统实施安全诊断的安全验证器,得到了一个关于离散事件系统安全可诊断性的充分必要条件,实现了对系统的安全故障诊断.同时,通过对安全验证器的构建与安全可诊断性的判定的复杂性分析,得到了该安全故障诊断方法可在多项式时间内实现等结论.     

Packing问题的计算复杂性

本文讨论了离散模型与连续问题的关系以及图灵机的计算能力,在此基础上扩充了问题及NP完全问题的定义,根据解空间的拓扑结构特点将NP完全的Packing问题分为三类,并对多边形Packing问题进行了有益的探讨。这对设计Packing问题的求解算法具有借鉴意义。     

相对于单元素语言的多项式时间谱系的研究

通过讨论相对于单元素语言的多项式时间谱系,得到了Ⅱp1(A)∈△1的一个充分条件,进而研究了多项式时间谱系中的类∑p1内的单元素语言T与计算复杂性理论中的重要相对化语言类CO-NP(T)、P(NP)、∑p t-1(T)、△p1、NP(T)、NP等之间的联系.     

Few算子和多项式时间概率算法PP的能力

本文提出Ｆｅｗ算子并研究其决定的复杂性类，得到了复杂性类ＰｔｔＣ的新刻划．利用此刻划讨论了多项式时间概率复杂性类ＰＰ的能力．     

有关时间自动机重置的若干问题的计算复杂性

自动机的重置序列也称为同步序列,具有以下特性：有限自动机通过运行重置序列w,可从任意一个未知的或无法观测到的状态q₀到达某个特定状态q_w.这仅依赖于w,而与开始运行w时的状态q₀无关.这一特性可用于部分可观察的复杂系统的自动恢复,而无需重启,甚至有时不能重启.基于此,重置问题自出现以来便得到关注和持续研究.最近几年,它被扩展到可以描述诸如分布式、嵌入式实时系统等复杂系统的无限状态模型上,比如时间自动机和寄存器自动机等.以时间自动机的重置问题的计算复杂性为研究对象,发现重置问题与可达性问题有着紧密的联系.主要贡献是：（1）利用时间自动机可达性问题的最新成果,完善完全的确定的时间自动机重置问题的计算复杂性结论;（2）对部分规约的确定的时间自动机,研究得出,即使在输入字母表大小减至2的情况下,其复杂性仍是PSPACE-完全的;特别地,在单时钟情况下是NLOGSPACE-完全的;（3）对完全的非确定的时间自动机,研究得出其D_i-可重置问题（i=1,2,3）是不可判定的,其重置问题与非确定的寄存器自动机重置问题在指数时间可以相互归约,通过证明指数时间归约相对高复杂性类具有封闭性,利用非确定的寄存器自动机的结论得出单时钟的时间自动机的重置问题是Ackermann-完全的、限界的重置问题是NEXPTIME-完全的.这些复杂性结论,说明关于时间自动机的重置问题大都是难解的,一方面,为时间系统的可重置性的检测和求解奠定坚实的理论基础,另一方面,为以后寻找具有高效算法的特殊结构的时间系统（即具有高效算法的问题子类）给予理论指导.     

P与NP问题研究

P与NP问题被列为七大世界数学难题之首,由于其相关概念抽象而复杂,许多该领域的学生学者,对其相关概念的理解存在谬误,不少已发表的研究论文都体现了这一谬误。用中文通俗讲解到底什么是P和NP问题以及它们的关系,透过抽象的定义揭示其本质。列举一些科研论文上常见的对P和NP问题理解上的谬误,通过分析揭示其错误实质。同时并对解决这一问题可能的研究方法作一综述,对研究前景做一展望,为在该方向上学习和研究的学生学者,提供有价值的参考。由于文中包括:对复杂抽象的概念进行通俗而深入的剖析,对已有的研究进展进行摘要概括,对未来可能的研究方法和研究路线进行综述和分析,故能对该领域的研究者在概念的正确把握、文献的查阅和研究方向的选择上提供助益。     

演化算法的时间复杂性

演化算法在工程领域取得了广泛的应用,但是其基础理论尚未完全建立。文章讨论了演化算法的时间复杂性,提出一个估计(1+1)EA平均计算时间的简单方法,对几个实例的应用显示了该方法分析演化算法计算时间的有效性。     

基于图灵模型的P=？ NP问题分析

P=？NP问题是计算复杂性中的核心问题。2000年,美国克雷实验室将其收录为“千禧年大奖”七个问题之首。本文基于图灵模型,对P=？NP问题的研究现状、P=NP／P≠NP 证明方法、NPC问题求解方法及研究进展进行阐述。     

The Turing way to parameterized complexity

We propose a general proof technique based on the Turing machine halting problem that allows us to establish membership results for the classes W[1], W[2], and W[P]. Using this technique, we prove that Perfect Code belongs to W[1], Steiner Tree belongs to W[2], and α-Balanced Separator, Maximal Irredundant Set, and Bounded DFA Intersection belong to W[P].     

A note on alternating one-pebble Turing machines with sublogarithmic space

Inoue et al. [A. Inoue, A. Ito, K. Inoue, T. Okazaki, Some properties of one-pebble Turing machines with sublogarithmic space, Theoret. Comput. Sci. 341 (2005) 138-149] conjectured that the language {ww|w∈⁺{a,b}} is not accepted by any alternating one-pebble Turing machine with sublogarithmic space. In this paper we disprove the conjecture by showing that there exists an alternating one-pebble Turing machine accepting the language in loglogn space.     

The complexity of tensor calculus

Tensor calculus over semirings is shown relevant to complexity theory in unexpected ways. First, evaluating well-formed tensor formulas with explicit tensor entries is shown complete for $\bigoplusP$, for NP, and for #P as the semiring varies. Indeed the permanent of a matrix is shown expressible as the value of a tensor formula in much the same way that Berkowitzs theorem expresses its determinant. Second, restricted tensor formulas are shown to capture the classes LOGCFL and NL, their parity counterparts $\bigoplusLOGCFL$ and $\bigoplusL$, and several other counting classes. Finally, the known inclusions $\NP/\poly \subseteq \bigoplusP/\poly$, $\LOGCFL/\poly \subseteq \bigoplusLOGCFL/\poly$, and $\NL/\poly \subseteq \bigoplusL/\poly$, which have scattered proofs in the literature (Valiant & Vazirani 1986; Gál & Wigderson 1996), are shown to follow from the new characterizations in a single blow. As an intermediate tool, we define and make use of the natural notion of an algebraic Turing machine over a semiring $ \mathcal{S}$.     

Linear logic by levels and bounded time complexity

We give a new characterization of elementary and deterministic polynomial time computation in linear logic through the proofs-as-programs correspondence. Girard’s seminal results, concerning elementary and light linear logic, achieve this characterization by enforcing a stratification principle on proofs, using the notion of depth in proof nets. Here, we propose a more general form of stratification, based on inducing levels in proof nets by means of indices, which allows us to extend Girard’s systems while keeping the same complexity properties. In particular, it turns out that Girard’s systems can be recovered by forcing depth and level to coincide. A consequence of the higher flexibility of levels with respect to depth is the absence of boxes for handling the paragraph modality. We use this fact to propose a variant of our polytime system in which the paragraph modality is only allowed on atoms, and which may thus serve as a basis for developing lambda-calculus type assignment systems with more efficient typing algorithms than existing ones.     

Independence results about context-free languages and lower bounds

We show that for any axiomatizable, sound formal system F there exist instances of natural problems about context-free languages, lower bounds of computations and P versus NP that are not provable in F for any recursive representation of these problems. Most previous independence results in computer science have been proven for specific representations of the problems, by exploiting the ‘opaqueness’ of Turing machine names. Our results rely on the complexity of the logical structure of the problem and yield independence results which do not depend on the representations of problems. We show, for example, that there exists a nonregular context-free language L₀ such that for no cf-grammar G, L(G) = L₀, it is provable in F that “L(G) is not regular”. We also show, among other results about P and NP, that there exists a recursive oracle A such that NP^A ≠ P^A, and that this fact is not provable in F for any recursive representation of A.

The difference of what is and is not provable in F is well illustrated by questions about polynomial time isomorphisms (p-isomorphisms) of NP-complete sets. We show that for every NP-complete set, L, there is a representation of L by a nondeterministic polynomial time machine for which we can prove that L is NP-complete. Furthermore, if L is p-isomorphic to SAT, then this is also provable in F for some representation of L. On the other hand, if there exist NP-complete sets not p-isomorphic to SAT, then there exists an NP-complete set L for which, independent of its representation, there is no proof in F that L is or is not p-isomorphic to SAT.     

A Turing machine time hierarchy

The time separation results concerning classes of languages over a single-letter alphabet accepted by multi-tape nondeterministic Turing machines, well-known from Seiferas, Fischer and Meyer (1978), are supplemented. Moreover, via a universal machine a modified time complexity measure UTIME of Turing machines computations which is sensitive to multiplication by constants (i.e., UTIME(t) ? UTIME(kt), where UTIME(t) is the class of languages of complexity not larger than t) is introduced. On the level of this measure, the results concerning languages over one- and two-letter alphabets are refined. The proof tools are versions of a translational diagonalization and of an unpadding technique.