Feasible Real Random Access Machines

We present a modified real RAM model which is equipped with the usual discrete and real-valued arithmetic operations and with a finite precision test <_kwhich allows comparisons of real numbers only up to a variable uncertainty 1/(k+1). Furthermore, ourfeasible RAMhas an extended semantics which allows approximative computations. Using a logarithmic complexity measure we prove that all functions computable on a RAM in time (t) can be computed on a Turing machine in time (t²·log(t)·log log(t)). Vice versa all functions computable on a Turing machine in time (t) are computable on a RAM in time (t). Thus, our real RAM model does not only express exactly the computational power of Turing machines on real numbers (in the sense of Grzegorczyk), but it also yields a high-level tool for realistic time complexity estimations on real numbers.     

The Accuracy and the Computational Complexity of a Multivariate Binned Kernel Density Estimator

The computational cost of multivariate kernel density estimation can be reduced by prebinning the data. The data are discretized to a grid and a weighted kernel estimator is computed. We report results on the accuracy of such a binned kernel estimator and discuss the computational complexity of the estimator as measured by its average number of nonzero terms.     

Computation Models for Parameterized Complexity

A parameterized computational problem is a set of pairs (x, k), where k is a distinguished item called “parameter”. FPT is the class of fixed-parameter tractable problems: for any fixed value of k, they are solvable in time bounded by a polynomial of degree α, where α is a constant not dependent on the parameter. In order to deal with parameterized intractability, Downey and Fellows have introduced a hierarchy of classes W[l] ? W[2] ? ? containing likely intractable parameterized problems, and they have shown that such classes have many natural, complete languages. In this paper we analyze several variations of the halting problem for nondeterministic Turing machines with parameterized time, and we show that its parameterized complexity strongly depends on some resources like the number of tapes, head and internal states, and on the size of the alphabet. Notice that classical polynomial-time complexity fails in distinguishing such features. As byproducts, we show that parameterized complexity is a useful tool for the study of the intrinsic power of some computational models, and we underline the different “computational powers” of some levels of the parameterized hierarchy.     

On the Computational Complexity of the Minimum Committee Problem

Two special cases of the Minimum Committee Problem are studied, the Minimum Committee Problem of Finite Sets (MCFS) and the Minimum Committee Problem of a System of Linear Inequalities(MCLE). It is known that the first of these problems is NP-hard (see (Mazurov et al., Proc. Steklov Inst. Math., 1:67–101, 2002)). In this paper we show the NP-hardness of two integer optimization problems connected with it. In addition, we analyze the hardness of approximation to the MCFS problem. In particular, we show that, unless NP⊂TIME(n ^O(loglogn )), for every ε>0 there are no approximation algorithms for this problem with approximation ratio (1–ε)ln (m–1), where m is the number of inclusions in the MCFS problem. To prove this bound we use the SET COVER problem, for which a similar result is known (Feige, J. ACM, 45:634–652, 1998). We also show that the Minimum Committee of Linear Inequalities System (MCLE) problem is NP-hard as well and consider an approximation algorithm for this problem.      

A New View of the Computational Complexity of IVP for ODE

The cost of solving an initial value problem for ordinary differential equations to accuracy 2 is polynomial in ln. Adaptive step-size control is never theoretically more costly than fixed step-size control, and can be an unbounded factor less costly. These results contradict the standard theory, but are based on more realistic assumptions.     

无原子布氏代数理论的计算复杂性

研究无原子布氏代数的计算复杂性 .得到了下面的新定理 :定理 1　无原子布氏代数理论Δ具有完全的量词消去法 ,也就是说每一个式子都Δ等价于一个开式子 .定理 2　无原子布氏代数的初等型Γ (x1,… ,xn)是由型内的不含量词的全体开式子所唯一决定 .定理 3　无原子布氏代数的一个长度为 n的语句的判断过程所消耗的 Turing时间和空间都是属于 2 2 cn指数级 .     

完全二叉树理论的计算复杂度

完全二叉树的一阶理论已被证明具有量词消去的性质,进而计算了完全二叉树模型中元素的CB秩.本文利用有界Ehrenfeucht-Frassé博弈研究完全二叉树的一阶理论,证明了此理论的时间计算复杂度上界为22cn,空间计算复杂度上界为2dn(其中n为输入长度,c,d为合适的常数).     

Analyzing the Complexity of Finding Good Neighborhood Functions for Local Search Algorithms

A drawback to using local search algorithms to address NP-hard discrete optimization problems is that many neighborhood functions have an exponential number of local optima that are not global optima (termed L-locals). A neighborhood function η is said to be stable if the number of L-locals is polynomial. A stable neighborhood function ensures that the number of L-locals does not grow too large as the instance size increases and results in improved performance for many local search algorithms. This paper studies the complexity of stable neighborhood functions for NP-hard discrete optimization problems by introducing neighborhood transformations. Neighborhood transformations between discrete optimization problems consist of a transformation of problem instances and a corresponding transformation of solutions that preserves the ordering imposed by the objective function values. In this paper, MAX Weighted Boolean SAT (MWBS), MAX Clause Weighted SAT (MCWS), and Zero-One Integer Programming (ZOIP) are shown to be NPO-complete with respect to neighborhood transformations. Therefore, if MWBS, MCWS, or ZOIP has a stable neighborhood function, then every problem in NPO has a stable neighborhood function. These results demonstrate the difficulty of finding effective neighborhood functions for NP-hard discrete optimization problems.This research is supported in part by the Air Force Office of Scientific Research (F49620-01-1-0007, FA9550-04-1-0110).     

混沌振荡系统的空时复杂度

基于相轨迹随时间的变化规律,提出了混沌振荡系统空时复杂度的概念,给出了空时复杂度的定义和计算方法.定义物理意义直观明确,与Lyapunov指数计算相比,方法计算量少,便于实际应用.以Duffing振子为例,通过数值仿真与实验,研究了混沌振荡系统的空时复杂度,实验结果表明空时复杂度可以很好地刻画Duffing振子丰富的动力学特性.     

Computational complexity in additive hedonic games

We investigate the computational complexity of several decision problems in hedonic coalition formation games and demonstrate that attaining stability in such games remains NP-hard even when they are additive. Precisely, we prove that when either core stability or strict core stability is under consideration, the existence problem of a stable coalition structure is NP-hard in the strong sense. Furthermore, the corresponding decision problems with respect to the existence of a Nash stable coalition structure and of an individually stable coalition structure turn out to be NP-complete in the strong sense.     

Polynomial Computability of Certain Rudimentary Predicates

The class of rudimentary predicates is defined as the smallest class of numerical predicates that contains the equality and concatenation predicates and is closed under the operations of propositional logic, explicit transformations, and bounded quantification. Two classes of rudimentary predicates are considered. The first of them consists of the predicates whose prenex normal form of a special type has the quantifier prefix of the form . Predicates of the second class can have an arbitrary quantifier prefix, but restrictions are imposed on the Skolem deciding functions. It is proved that any predicate from each of these classes can be computed by a suitable deterministic algorithm in polynomial time.     

Complexity of games and bounded rationality

An attempt is made to propose a concept of limited rationality for choice junctions based on computability theory in computer science.

Starting with the observation that it is possible to construct a machine simulating strategies of each individual in society, one machine for each individual's preference structure, we identify internal states of this machine with strategies or strategic preferences. Inputs are possible actions of other agents in society thus society is effectively operating as a game generated by machines. The main result states that effective realization of game strategies bound by the “complexity of computing machines'.     

一类新的广义割圆序列的线性复杂度及其自相关值

最近,丁存生基于新的割圆类(V_0,V_1)构造了循环码并研究了其性质.本文利用割圆类(V_0, V_1)构造了周期为pq的2阶二元序列,并计算了其自相关值、线性复杂度和极小多项式.     

有限可换主理想环上模理论可判定性及其复杂性

本文利用初等等价的工具，引用Ｅｈｅｎｆｅｕｃｈｔ Ｇａｍｅ理论，证明了有限可换主理想环上模的理论是可判定的，并且判定过程的计算复杂性上界为２^ｃｎ２．     

Studying the Complexity of Global Verification for NP-Hard Discrete Optimization Problems

This paper examines the complexity of global verification for MAX-SAT, MAX-k-SAT (for k3), Vertex Cover, and Traveling Salesman Problem. These results are obtained by adaptations of the transformations that prove such problems to be NP-complete. The class of problems PGS is defined to be those discrete optimization problems for which there exists a polynomial time algorithm such that given any solution , either a solution can be found with a better objective function value or it can be concluded that no such solution exists and is a global optimum. This paper demonstrates that if any one of MAX-SAT, MAX-k-SAT (for k3), Vertex Cover, or Traveling Salesman Problem are in PGS, then P=NP.     

C0复杂度的数学基础

对于许多同时具有强烈非线性和非平稳性的连续生物医学信号来说，计算其复杂度往往要求：1）在数据长度比较短的情况下也可以得出比较鲁棒的估计值；2）无需对原始信号作像二值化这样的过分的粗粒化，我们以前所提出的C0复杂度就是这样的一种度量，但是这种度量缺乏严格的数学基础，因而影响到它的应用，提出了一种改进形式，并严格证明了它的重要性质。从而表明这个量在一定条件下可以作为时间序列随机程度的指标，因而在随机性复杂度的意义下也可作为复杂性的一个定量指标，由于这个量有计算速度快的优点，因此特别适合于一些需要大量计算复杂度的场合，例如计算长时间过程中滑动窗口中复杂度的动态变化。     

Complexity Classes and Completeness in Algebraic Geometry

Foundations of Computational Mathematics - We study the computational complexity of sequences of projective varieties. We define analogues of the complexity classes P and NP for these and prove the...     

具有2n线性复杂度的2n周期二元序列的3错线性复杂度

线性复杂度和k错线性复杂度是度量密钥流序列的密码强度的重要指标.通过研究周期为2n的二元序列线性复杂度,提出将k错线性复杂度的计算转化为求Hamming重量最小的错误序列.基于Games-Chan算法,讨论了线性复杂度为2n的2n周期二元序列的3错线性复杂度分布情况;给出了对应k错线性复杂度序列的完整计数公式, k=3,4.对于一般的线性复杂度为2n-m的2n周期二元序列,也可以使用该方法给出对应k错线性复杂度序列的计数公式.