Parameterized Complexity of Theory of Mind Reasoning in Dynamic Epistemic Logic

Theory of mind refers to the human capacity for reasoning about others’ mental states based on observations of their actions and unfolding events. This type of reasoning is notorious in the cognitive science literature for its presumed computational intractability. A possible reason could be that it may involve higher-order thinking (e.g., ‘you believe that I believe that you believe’). To investigate this we formalize theory of mind reasoning as updating of beliefs about beliefs using dynamic epistemic logic, as this formalism allows to parameterize ‘order of thinking.’ We prove that theory of mind reasoning, so formalized, indeed is intractable (specifically, PSPACE-complete). Using parameterized complexity we prove, however, that the ‘order parameter’ is not a source of intractability. We furthermore consider a set of alternative parameters and investigate which of them are sources of intractability. We discuss the implications of these results for the understanding of theory of mind.     

Quantitative Feedback Theory Revisited

This paper reexamines Horowitz's original formulation of the Quantitative Feedback Theory (QFT) problem in the light of recent developments in robust control. A simple proof of optimality of the loop transmission function in the sense of Horowitz is developed. A difficulty with Horowitz's formulation at high frequencies is corrected.     

基于确定学习理论和Lempel-Ziv复杂度的非线性系统动态特征提取

对非线性系统产生的非线性非平稳信号进行有效的特征表达是特征提取领域重要且困难的问题.本文基于确定学习理论和Lempel-Ziv复杂度（LZ复杂度）提出一种新的非线性系统动态特征提取方法.新方法将从系统的动力学轨迹中提取特征.通过确定学习理论对产生回归轨迹的非线性动力学系统的未知系统动态进行局部准确建模/辨识,1）使用LZ复杂度对辨识得到的动力学轨迹进行特征表达,并提出时间复杂度和空间复杂度两个指标组成时空LZ复杂度,从时间域和空间域的角度刻画系统动力学轨迹的复杂程度.2）对提出的动态特征提取方法进行敏感度分析,定量评价系统的动态特征指标相对于系统从周期轨迹到混沌轨迹的参数变化敏感程度.3）通过数值仿真和实验分析以验证动态特征提取的有效性.与从系统状态轨迹中提取特征相比,本文提出的动态特征提取方法可以从系统内在动态的角度对原系统进行更好的表达.     

Progress in Computational Complexity Theory

We briefly survey a number of important recent achievements in Theoretical Computer Science (TCS), especially Computational Complexity Theory. We will discuss the PCP Theorem, its implications to inapproximability on combinatorial optimization problems; space bounded computations, especially deterministic logspace algorithm for undirected graph connectivity problem; deterministic polynomial-time primality test; lattice complexity, worst-case to average-case reductions; pseudorandomness and extractor constructions; and Valiant's new theory of holographic algorithms and reductions.     

Dynamic Programming Revisited: Improving Knapsack Algorithms

The contribution of this paper is twofold: At first an improved dynamic programming algorithm for the bounded knapsack problem is given. It decreases the running time for an instance with n items and capacity c from to , which is the same pseudopolynomial complexity as usually given for the 0--1 knapsack problem. In the second part a general approach based on dynamic programming is presented to reduce the storage requirements for combinatorial optimization problems where it is computationally more expensive to compute the explicit solution structure than the optimal solution value. Among other applications of this scheme it is shown that the 0--1 knapsack problem as well as the bounded knapsack problem can be solved in time and space. Received: October 15, 1998; revised March 10, 1999     

复杂适应系统理论与计算机作战模拟

该文介绍了CAS理论的基本思想，对以往的作战模拟手段存在的缺欠和应用CAS理论于作战模拟的优势进行了分析，并对应用CAS理论的计算机平台进行了讨论。以此为基础，建立仿真模型。针对这一模型，说明CAS理论在军事仿真中的其他应用。     

计算机网络行为的复杂性理论研究

在信息时代的大背景下,计算机网络行为越来越复杂,传统的研究计算机网络行为的方法已难适应大规模的计算机网络。为更好地管理和控制复杂的计算机网络,提高网络服务的质量,将复杂性理论应用于计算机网络行为的研究,探索出一种复杂网络行为研究新方法。分析计算机网络行为研究的传统方法之不足,阐明复杂性理论应用于计算机网络行为研究的有效性,并概述其发展现状,以及指明其广泛的应用前景。     

Dynamic Galois Theory

Given a separable polynomial over a field, every maximal idempotent of its splitting algebra defines a representation of its splitting field. Nevertheless such an idempotent is not computable when dealing with a computable field if this field has no factorization algorithm for separable polynomials. Moreover, even when such an algorithm does exist, it is often too heavy. So we suggest to address the problem with the philosophy of lazy evaluation: make only computations needed for precise results, without trying to obtain a priori complete information about the situation. In our setting, even if the splitting field is not computable as a static object, it is always computable as a dynamic one. The Galois group has a very important role in order to understand the unavoidable ambiguity of the splitting field, and this is even more important when dealing with the splitting field as a dynamic object. So it is not astonishing that successive approximations to the Galois group (which is again a dynamic object) are a good tool for improving our computations. Our work can be seen as a Galois version of the Computer Algebra software D5 ( Della Dora et al., 1985).     

平均计算时间复杂度优化的动态粒子群优化算法

粒子群优化(PSO:Particle Swarm Optimization)算法已经被广泛地应用,其中包括大量实时性要求很高的领域,如宽带数字信号处理。传统PSO算法需要对大量粒子分别进行若干次迭代运算,这将导致该算法的平均计算时间复杂度较高,运算延时大,不能满足这种高实时性要求。因此,需要在不影响性能的前提下降低PSO算法的平均计算时间复杂度。提出了一种粒子数量可变的动态粒子群优化(DPSO:Dynamic PSO)算法,其核心是丢弃粒子判定条件,在迭代过程中,根据该条件动态地抛弃一些粒子,从而降低算法的平均计算时间复杂度。此外,在算法迭代过程中对粒子的个体极值进行变异,从而避免陷入局部最优解。实验和理论分析结果表明,在算法的平均计算时间复杂度方面,对于相同的优化结果,DPSO算法的平均计算时间复杂度比传统PSO算法降低了30%左右;在算法的性能方面,对于单峰值目标函数,DPSO算法与传统PSO算法的优化性能相当,而对于多峰值目标函数,DPSO算法的优化性能要优于传统PSO算法。     

动态网络最短路问题的复杂性与近似算法

有向网络的最短路问题在交通、通信系统的最优路径计算以及多阶段决策过程的最优轨线设计等实际问题中有着重要应用.经典模型及算法解决固定弧权条件下的最短路问题,而实际中,网络往往是动态的,即弧权依赖于时间变化,例如在交通拥堵时运行时间会变长,这时经典的最短路算法不再适用.文中证明了动态网络的最短路问题是NP-困难的;给出了最短路稳定性的充要条件,并在此基础上提出一种基于稳定区间的近似算法,通过模拟实验验证了该算法的有效性.     

系统论视野下城市治理的复杂性分析

在城市化进程日益深化的客观规律下,城市作为人类生活的主要空间,发挥着满足人类物质生活和精神需要的重要作用.由于城市规模日益扩大,不可控因素增多,城市面临着越来越复杂的治理问题,亟需一个整体、系统的思维来认识城市治理中的复杂性.在系统论指导下,运用系统科学的分析方法,从城市治理客体的复杂性、城市治理主体的复杂性和城市治理...     

An Information Theory Framework for the Analysis of Scene Complexity

In this paper we present a new framework for the analysis of scene visibility and radiosity complexity. We introduce a number of complexity measures from information theory quantifying how difficult it is to compute with accuracy the visibility and radiosity in a scene. We define the continuous mutual information as a complexity measure of a scene, independent of whatever discretisation, and discrete mutual information as the complexity of a discretised scene. Mutual information can be understood as the degree of correlation or dependence between all the points or patches of a scene. Thus, low complexity corresponds to low correlation and vice versa. Experiments illustrating that the best mesh of a given scene among a number of alternatives corresponds to the one with the highest discrete mutual information, indicate the feasibility of the approach. Unlike continuous mutual information, which is very cheap to compute, the computation of discrete mutual information can however be quite demanding. We will develop cheap complexity measure estimates and derive practical algorithms from this framework in future work.     

高动态猝发扩频信号低复杂度快速捕获技术

研究超高速飞行器组网的猝发扩频信号快速捕获技术,与卫星导航等传统卫星通信系统相比,其飞行器的动态更大,使用的载波频率更高,使得多普勒特性增加了一个数量级以上,对扩频信号捕获算法的搜索带宽和捕获时间都提出了更高的要求.针对上述需求,对已有的双块补零捕获算法(DBZP)进行改进,通过调整优化算法的分块方案和参数设置获取更大的多普勒频偏搜索范围.同时提出了列压缩算法,显著减低算法的计算复杂度.通过仿真证明了改进的双块补零算法能成功捕获高动态的猝发信号,并且通过仿真和计算分析得到了适用于高动态猝发信号的双块补零最优列压缩比.     

Complexity Model Based Proactive Dynamic Voltage Scaling for Video Decoding Systems

Significant power savings can be achieved on voltage/ frequency configurable platforms by dynamically adapting the frequency and voltage according to the workload (complexity). Video decoding is one of the most complex tasks performed on such systems due to its computationally demanding operations like inverse filtering, interpolation, motion compensation and entropy decoding. Dynamically adapting the frequency and voltage for video decoding is attractive due to the time-varying workload and because the utility of decoding a frame is dependent only on decoding the frame before the display deadline. Our contribution in this paper is twofold. First, we adopt a complexity model that explicitly considers the video compression and platform specifics to accurately predict execution times. Second, based on this complexity model, we propose a dynamic voltage scaling algorithm that changes effective deadlines of frame decoding jobs. We pose our problem as a buffer-constrained optimization and show that significant improvements can be achieved over the state-of-the-art dynamic voltage scaling techniques without any performance degradation. Index     

基于动态消息调度的SCMA低复杂度检测算法

稀疏码多址接入(Sparse Code Multiple Access,SCMA)是第五代无线通信网络一种竞争性的非正交多址技术,能够满足海量连接的需求。现有上行SCMA通信系统中采用串行策略MPA(Message Passing Algorithm)来译码收敛速度比同步更快,然而,串行MPA按照预先定义好的顺序进行消息更新,存在信息收敛速度不理想的问题。该文提出一种基于节点剩余度的动态消息调度算法RMPA(Residual MPA),在每一轮迭代中动态选择具有最大剩余度的消息进行更新。仿真表明,所提出的算法性能优于基于串行策略的MPA算法,且能在译码性能和复杂度之间保持很好的平衡。     

适配分辨率动态变化的低复杂度视频场景切换检测方法

在数字电视图像后处理中,许多图像增强和指标检测算法模块需要参考前后帧的时域信息,因此当场景内容发生切换时,需要设计出一种准确且可靠的场景切换检测的方法,用以切断场景切换前和场景切换后的各种时域算法的前后关联性。针对网络电视播放视频节目前后帧经常出现的分辨率变化的特性以及场景切换检测中常见的问题,对数字电视图像后处理中的视频场景切换检测算法进行了优化设计,提出了一种基于动态阶数控制直方图分布的优化检测算法。实验结果表明, 相比传统算法,所提算法在场景切换检测的准确度上有显著的提升,针对暗场景下的场景切换以及网络电视中分辨率改变的情形具有较高的准确度。