Some Computational Aspects of distance-sat

In many AI fields, one must face the problem of finding a solution that is as close as possible to a given configuration. This paper addresses this problem in a propositional framework. We introduce the decision problem distance-sat, which consists in determining whether a propositional formula admits a model that disagrees with a given partial interpretation on at most d variables. The complexity of distance-sat and of several restrictions of it are identified. Two algorithms based on the well-known Davis/Logemann/Loveland search procedure for the satisfiability problem sat are presented so as to solve distance-sat for CNF formulas. Their computational behaviors are compared with the ones offered by sat solvers on sat encodings of distance-sat instances. The empirical evaluation allows us to draw firm conclusions about the respective performances of the algorithms and to relate the difficulty of distance-sat with the difficulty of sat from the practical side. A preliminary version of this paper appeared with the title “distance-sat: Complexity and Algorithms” in the proceedings of the 16 ^th National Conference on Artificial Intelligence (AAAI’99), pages 642–647, 1999.     

命题线性时序逻辑的对偶模型问题的复杂性

定义了一个命题线性时序逻辑的对偶模型的概念.一个公式f的对偶模型是指f的满足以下条件的两个模型(即状态的w序列):在每个位置上这两个模型对原子命题的赋值都是对偶的.然后,对于确定一个公式f是否有对偶模型的判定问题(记为DM)和在一个Kripke-结构中确定是否存在从两个给定状态出发的对偶模型满足给定公式f的判定问题(记为KDM)的复杂性进行了研究.证明了以下结果:对于只含有F(\"Future\")算子的命题线性时序逻辑,DM和KDM都是NP完全的;而对于以下命题线性时序逻辑,DM和KDM都是PSPACE完全的:含有F,X (\"Next\")算子的逻辑、含有U(\"Until\")算子的逻辑、含有U,S,X算子的逻辑以及由Wolper给出的含有正规语言算子的逻辑(一般称为扩展时序逻辑,简称ETL).     

The complexity of agent design problems: Determinism and history dependence

The agent design problem is as follows: given a specification of an environment, together with a specification of a task, is it possible to construct an agent that can be guaranteed to successfully accomplish the task in the environment? In this article, we study the computational complexity of the agent design problem for tasks that are of the form “achieve this state of affairs” or “maintain this state of affairs.” We consider three general formulations of these problems (in both non-deterministic and deterministic environments) that differ in the nature of what is viewed as an “acceptable” solution: in the least restrictive formulation, no limit is placed on the number of actions an agent is allowed to perform in attempting to meet the requirements of its specified task. We show that the resulting decision problems are intractable, in the sense that these are non-recursive (but recursively enumerable) for achievement tasks, and non-recursively enumerable for maintenance tasks. In the second formulation, the decision problem addresses the existence of agents that have satisfied their specified task within some given number of actions. Even in this more restrictive setting the resulting decision problems are either pspace-complete or np-complete. Our final formulation requires the environment to be history independent and bounded. In these cases polynomial time algorithms exist: for deterministic environments the decision problems are nl-complete; in non-deterministic environments, p-complete.     

Symbolic modeling in robotics: Genesis,applicaton, and future prospects

This survey article gives an overview of software packages for generating numerically efficient manipulator models in symbolic form, i.e. as computer programs written in a high-level language such as C or FORTRAN. We chronicle the history of computational robot dynamics and, to some extent, multibody systems dynamics. We survey several mechanical computer-aided engineering software packages because they have charted the course for symbolic robot modeling software. The attractive features of various programs regarding areas of application (vehicles, robots, satellites, etc.) and design possibilities (kinematic and dynamic analysis, modal analysis, optimization of mechanical design, numerical efficiency of generated symbolic models, etc.) are emphasized. Finally, as an example, we present the SYM program package in more detail and point out the new strategic area of robotics which has emerged during the last two years: computer-aided generation of control laws.     

谈计算机专业实践教学中计算思维能力的培养

阐述了计算理论(可计算性与计算机复杂性理论)中的几个典型问题,以图灵机模型、停机问题、近似算法及装箱问题等为例从不同角度分析计算理论与计算思维的密切联系,强调计算机专业实践教学中计算思维能力培养的必要性。     

On the arithmetic complexity of matrix Kronecker powers

In this paper we study the arithmetic complexity of computing the pth Kronecker power of an n × n matrix. We first analyze a straightforward inductive computation which requires an asymptotic average of p multiplications and p – 1 additions per computed output. We then apply efficient methods for matrix multiplication to obtain an algorithm that achieves the optimal rate of one multiplication per output at the expense of increasing the number of additions, and an algorithm that requires O(log p) multiplications and O(log²p) additions per output.     

On the Complexity of Mining Quantitative Association Rules

The discovery of quantitative association rules in large databases is considered an interesting and important research problem. Recently, different aspects of the problem have been studied, and several algorithms have been presented in the literature, among others in (Srikant and Agrawal, 1996; Fukuda et al., 1996a; Fukuda et al., 1996b; Yoda et al., 1997; Miller and Yang, 1997). An aspect of the problem that has so far been ignored, is its computational complexity. In this paper, we study the computational complexity of mining quantitative association rules.     

PAC学习模型研究

计算学习理论为比较两算法的性能提供了形式化的框架，并能确定某概念类的计算复杂度和样本复杂度。而PAC学习模型是计算学习理论的基础，它为研究学习及泛化问题提供了一种基本的概率框架：先介绍了基本的PVC学习模型并对其进行了深入的分析，给出了判断一概念类是否是PAC学习的方法；然后针对基本PAC学习模型的不足进行了相应的扩展；最后介绍了计算学习理论中的一些其它模型。     

新的多视点视频编码优化算法

分析研究了多视点视频编码中的TZSearch算法的性能与不足,并针对平行摄像机采集的多视点视频序列,提出一种新的多视点视频编码优化算法。主要从搜索模型选取、搜索策略、自适应阈值设置三个方面进行算法优化,以减少算法计算复杂度。在多视点视频软件测试平台——JMVC4.0上进行验证,结果表明:在保证重建视频质量在容忍度内,同时编码开销可控的前提下,优化算法与原始算法相比,算法平均编码时间减少75%左右,大大提高了编码的实时性。     

符号序列间的LZ复杂性距离及其应用

在符号序列LZ复杂性的计算原理上,提出了序列间条件LZ复杂性的概念.基于条件LZ复杂性,定义了一个非空序列间的LZ复杂性距离并证明了该距离满足距离测度的4个基本性质.将LZ复杂性距离应用于计算语言学和生物信息学的研究领域,选取20种自然语言文本和29种有胎盘哺乳动物的全线粒体基因组,将它们视为不同符号集上的符号序列,分别计算两类符号序列的LZ复杂性距离矩阵.基于LZ复杂性距离矩阵,重构了20种语言的语言关系树和29种哺乳动物的系统进化树.其结果符合它们真实的演化关系,说明了LZ复杂性距离定量刻画符号序列间差异的有效性.