Active constraints,indefinite quadratic test problems,and complexity

The observation that at leasts constraints are active when the Hessian of the Lagrangian hass negative eigenvalues at a local minimizer is used to obtain two results: (i) a class of nearly concave quadratic minimization problem can be solved in polynomial time; (ii) a class of indefinite quadratic test problems can be constructed with a specified number of positive and negative eigenvalues and with a known global minimizer.The authors thank the reviewers for their constructive comments. The first author was supported by the National Science Foundation Grant DMS-85-20926 and by the Air Force Office of Scientific Research Grant AFOSR-ISSA-86-0091.     

What Makes a Theory Testable, or Is Intelligent Design Less Scientific Than String Theory?

I compare the theory of intelligent design to string theory to see on what basis, if any, only the former can be justifiably excluded as being scientific.We shall see that the classic criterion of testability or falsifiability is sometimes not so straightforward, and that there are other criteria to help us make such a distinction.     

An algorithm for single-item economic lot-sizing problem with general inventory cost, non-decreasing capacity, and non-increasing setup and production cost

This paper considers an economic lot-sizing model with non-decreasing capacity constraint, non-increasing setup cost and production cost, and a general inventory cost. We prove that when periodic starting inventory is not less than a certain critical value, it is optimal to produce nothing; this critical value can be computed easily which results in a new effective algorithm.     

An efficient distributed algorithm for canonical labeling on directed split-stars

We consider the problem of canonical labeling in anonymous directed split-stars. This paper proposes a distributed algorithm for finding the vertex sets with specified leading symbols in directed split-stars and which has a linear message and constant time complexity. The algorithm runs on an asynchronous timing model without shared memory. In addition, our algorithm generalizes the previous distributed algorithms on directed split-stars that we know.     

从弹簧滑块到地震预测:BK模型今昔谈

Burridge-Knopoff弹簧－滑块模型作为一个概念性的地震模型，自1967年提出以来一直为地震学家和物理学家所关注，对BK模型的研究成为物理学与地震学之间的一个活跃的交叉领域，BK模型的一些性质，例如确定性浑沌，自组织，孤立波，等等，能够为理解地震的性质和解决地震预测问题提供有用的线索，BK模型与目前的一些悬而未决的复杂性物理问题的联系，使它不仅对地震研究，而且对更普遍的多体系统问题的研究，都有重要的影响。     

基于代数等价路径的一致P-函数非线性互补问题的可行内点算法

对一致P-函数非线性互补问题，提出了一种新的基于代数等价路径的可行内点算法，并讨论了计算复杂性．该算法可以在任一内部可行点启动，并且全局收敛；当初始点靠近中心路径时，此算法便成为中心路径跟踪算法，特别对于单调线性互补问题，总迭代次数为O（√nL），其中L是问题的输入长度。     

On the evaluation at (<Emphasis Type="Italic">j</Emphasis>, <Emphasis Type="Italic">j</Emphasis><Superscript>2</Superscript>) of the Tutte polynomial of a ternary matroid

F. Jaeger has shown that up to a ± sign the evaluation at (j, j ²) of the Tutte polynomial of a ternary matroid can be expressed in terms of the dimension of the bicycle space of a representation over GF(3). We give a short algebraic proof of this result, which moreover yields the exact value of ±, a problem left open in Jaeger's paper. It follows that the computation of t(j, j ²) is of polynomial complexity for a ternary matroid.E. Gioan: C.N.R.S., MontpellierM. Las Vergnas: C.N.R.S., Paris     

量子通信

量子通信是经典通信和量子力学相结合的一门新兴交叉学科。文章综述了量子通信领域的研究进展，既包括人们所熟知的量子隐形传态、密集编码和量子密码学，也包括刚刚兴起但却有巨大潜力的量子通信复杂度和远程量子通信等领域。文章介绍了量子通信的基本理论框架，同时也涉及了这个领域最新的实验研究的进展。     

相关攻击与相关免疫函数

本文首先介绍了如何采用ＤＣ攻击法对一类流密码体制进行相关攻击，从而说明在密码学中有必要研究相关免疫（ＣＩ）函数。在综述了域Ｆ２上相关免疫（ＣＩ）函数的研究进展的同时，给出了ＣＩ函数在一般有限域上的特性和构造，并进一步研究有限环Ｚ／（ｍ）时的情景，本文详尽描述了ＣＩ函数的五种充要条件。最后提出了几个值得研究的未解决的问题。