一种Hopfield神经网络算法复杂性研究的新方法

首先分析了基于Hopfield神经网络的TSP问题求解方法,提出从研究能量函数、状态空间分布和可行解的关系来研究以Hopfield为代表的优化神经网络的计算复杂性的思想;并给出从状态空间到线性表的映射方法,引入状态-程序复杂性。分析结果表明,绝对状态一程序复杂性更为充分地反映能量函数的求解过程;相对状态-程序复杂性提供了一种在多项式时间内对NP问题算法的有效性进行衡量的尺度。     

PH的一种复杂性类分解

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

求解SAT问题的局部搜索算法及其平均时间复杂性分析

ＳＡＴ问题在人工智能、ＶＬＳＩ设计和计算机理论等领域有着广泛的应用背景，近年来，局部搜索算法在求解ＳＡＴ问题时得到了巨大的成功。本文除提出了多种改进策略之外，还对一般局部搜索算法进行了平均时间复杂性分析。     

演化算法求解近似最大匹配问题的时间复杂性分析

虽然演化算法已经广泛地被用于求解不同的组合优化问题，但是对于其时间复杂性目前仍然了解得比较少。最近，在这方面有了一些初步的研究，然而迄今的结果大多局限于讨论一些简单的演化算法(如(1 1)类型的演化策略)和人造的模型问题(如二进制类型的示例问题)，很少涉及到使用种群、杂交操作演化算法和传统的组合优化问题。因此，理论上需要分析演化算法，求解一些典型的组合优化问题的时间复杂性。     

一类非线性规划的模拟退火求解

本文针对一类非线性规划问题，提出并设计了模拟退火求解算法，分析证明了算法能够渐近敛于全局最优解且具有多项式计算复杂性，为研究非线性规划提供了新的有效的求解途径。实例计算也表明，模拟退火求解非线性规划确实是有效的。     

兑换零钱问题的动态规划算法研究*

兑换零钱问题是一个求解组合优化的问题。首先对兑换零钱问题进行了分析,证明了该问题满足动态规划的最优化原理,并给出了其动态规划解法;然后对本算法进行了时间复杂性和空间复杂性分析,得到时间复杂性由通常的动态规划算法的O（Mn2）提高到本算法的O（n3）,空间复杂性由通常的动态规划算法的O（Mn）提高到本算法的O（n2）,因此效率有了较大提高。最后通过实验对算法进行验证,证明了算法的高效性。该算法可以广泛应用于自动售货机。     

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

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

演化算法时间复杂性的趋势条件

计算时间复杂性是演化理论中的一个重大课题.将趋势分析引入演化算法的平均时间复杂性分析,可用于很广一类演化算法及许多问题.基于趋势分析,研究了确定演化算法时间复杂性的一些有用的趋势条件.这些条件应用于完全欺骗问题以验证其有效性.     

基于EREW的最优并行背包算法

背包问题属于著名的NP完全问题，在信息密码学领域和数论研究中具有极重要的应用。分枝限界算法对于某些背包实例的求解表现了较好的性能，但其在最坏情形下的时间复杂性为O(2^n)。Horowitz和Sahni利用分治方法，提出了著名的二表算法，算法的时间和空间复杂性被分别降至O(n2^n／2)和O(2^n／2)。虽然二表算法是迄今为止串行求解背包问题最有效的算法，但对于实践应用中维数稍大的问题实例，该算法仍难在合理的时间内对其求解。     

一种面向对象多态复杂性的度量方法

提出了一种类级多态复杂性和系统级多态复杂性的度量方法。该方法对强制多态、重载多态、类型参数化多态和包含多态这四种类型的多态进行分析,得出反映类的多态复杂性的量度,即强制多态复杂性（CCPP）、重载复杂性（CMC）、参数多态复杂性（CPMP）、包含多态复杂性（CCTP）;然后通过整合得到度量系统级的多态复杂性。实验证明,该方法能够正确有效地度量面向对象软件的多态复杂性。     

Kolmogorov complexity and combinatorial methods in communication complexity

We introduce a method based on Kolmogorov complexity to prove lower bounds on communication complexity. The intuition behind our technique is close to information theoretic methods.We use Kolmogorov complexity for three different things: first, to give a general lower bound in terms of Kolmogorov mutual information; second, to prove an alternative to Yao’s minmax principle based on Kolmogorov complexity; and finally, to identify hard inputs.We show that our method implies the rectangle and corruption bounds, known to be closely related to the subdistribution bound. We apply our method to the hidden matching problem, a relation introduced to prove an exponential gap between quantum and classical communication. We then show that our method generalizes the VC dimension and shatter coefficient lower bounds. Finally, we compare one-way communication and simultaneous communication in the case of distributional communication complexity and improve the previous known result.     

Evolving complexity

A review of efforts to implement the process of evolution in a computational medium. The review will cover prominent examples, and discuss the major classes of implementations, their successes, and the obstacles they face. This work was presented, in part, at the International Symposium on Artificial Life and Robotics, Oita, Japan, February 18–20, 1996     

Generalized kolmogorov complexity and other dual complexity measures

We construct and analyze some dual complexity measures that indicate the time it takes to obtain the desired object. The existence of optimal dual complexity measures is established. Various relations between dual measures and complexities are determined. The relationship of these measures to program quality is demonstrated.Translated from Kibernetika, No. 4, pp. 21–29, 54, July–August, 1990.     

Shape complexity

The complexity of 3D shapes that are represented in digital form and processed in CAD/CAM/CAE, entertainment, biomedical, and other applications has increased considerably. Much research was focused on coping with or on reducing shape complexity. However, what exactly is shape complexity? We discuss several complexity measures and the corresponding complexity reduction techniques. Algebraic complexity measures the degree of polynomials needed to represent the shape exactly in its implicit or parametric form. Topological complexity measures the number of handles and components or the existence of non-manifold singularities, non-regularized components, holes or self-intersections. Morphological complexity measures smoothness and feature size. Combinatorial complexity measures the vertex count in polygonal meshes. Representational complexity measures the footprint and ease-of-use of a data structure, or the storage size of a compressed model. The latter three vary as a function of accuracy.     

Graph complexity

Summary We develop a complexity theory based on the concept of the graph instead of the Boolean function. We show its relation to the Boolean complexity and prove some lower bounds to the complexity of explicitly given graphs.The paper was written while the first author was visiting Department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago     

High end complexity

Despite the general recognition of complexity as an important concept and decades of work, very little progress has been made in the attempt to define complexity. It is suggested that this is due to the fact that the definition of complex behaviour is itself complex, forming a scale from the simple to the more and more complex. Those systems at the high end of the scale are not at present well modelled, and reasons why this might be the case are presented. The possibility that quantum theories may be able to model such high end complexity is investigated.     

Quantifying knowledge complexity

One of the many contributions of the paper of Goldwasser, Micali and Rackoff is the introduction of the notion of knowledge complexity. Knowledge complexity zero (also known as zero-knowledge) has received most of the attention of the authors and all the attention of their followers. In this paper, we present several alternative definitions of knowledge complexity and investigate the relations between them. Received: July 22, 1997.     

Individual communication complexity

We initiate the theory of communication complexity of individual inputs held by the agents. This contrasts with the usual communication complexity model, where one counts the amount of communication for the worst-case or the average-case inputs. The individual communication complexity gives more information (the worst-case and the average-case can be derived from it but not vice versa) and may in some cases be of more interest. It is given in terms of the Kolmogorov complexities of the individual inputs. There are different measures of communication complexity depending on whether the protocol is guaranteed to be correct for all inputs or not, and whether there's one-way or two-way communication. Bounds are provided for the communication of specific functions and connections between the different communication measures are shown. Some counter-intuitive results: for deterministic protocols that need to communicate Bob's input to Alice they need to communicate all of Bob's input (rather than the information difference with Alice's input), and there are so-called “non-communicable” inputs.