In their celebrated paper (Furst et al., Math. Syst. theory 17(1), 13-27 (12)), Furst, Saxe, and Sipser used random restrictions to reveal the weakness of Boolean circuits of bounded depth, establishing that constant-...
详细信息
In their celebrated paper (Furst et al., Math. Syst. theory 17(1), 13-27 (12)), Furst, Saxe, and Sipser used random restrictions to reveal the weakness of Boolean circuits of bounded depth, establishing that constant-depth and polynomial-size circuits cannot compute the parity function. Such local restrictions have played important roles and have found many applications in complexity analysis and algorithm design over the past three decades. In this article, we give a brief overview of two intriguing applications of local restrictions: the first one is for the Isomorphism Conjecture and the second one is for moderately exponential time algorithms for the Boolean formula satisfiability problem.
Algorithmic statistics studies explanations of observed data that are good in the algorithmic sense: an explanation should be simple i.e. should have small Kolmogorov complexity and capture all the algorithmically dis...
详细信息
ISBN:
(纸本)9783319587479;9783319587462
Algorithmic statistics studies explanations of observed data that are good in the algorithmic sense: an explanation should be simple i.e. should have small Kolmogorov complexity and capture all the algorithmically discoverable regularities in the data. However this idea can not be used in practice because Kolmogorov complexity is not computable. In this paper we develop algorithmic statistics using space-bounded Kolmogorov complexity. We prove an analogue of one of the main result of 'classic' algorithmic statistics (about the connection between optimality and randomness deficiences). The main tool of our proof is the Nisan-Wigderson generator.
The cooperation of alliance needs a powerful agent to coordinate each other's activities. The broker agent who holds the structural holes position usually initiate this kind of governance because of the advantage ...
详细信息
The cooperation of alliance needs a powerful agent to coordinate each other's activities. The broker agent who holds the structural holes position usually initiate this kind of governance because of the advantage of information and control. This paper tied to turn the focus from sharing the cake to making a bigger cake: exploring the relationship between governance and performance of triple alliance. Basing on two dimension of external environment complex and exploration capability, we design four situations. Using the simulation experiment we extend the Aggarwal's model and explore how the governance initiated by broker agent affects the triple alliance's performance. The results show that except for the extreme case of high complex and low capability governance will lead to different performance level. The final performance depends on the reasonable matching among complex, capability and governance. At the end we discuss the contribution and the possibility of extension in the future.
Engaging in exploring multi-agent collaboration requires determining how to govern the shared activities. We examine the performance implications of selecting alternate modes of governance in multi-agent alliance rela...
详细信息
ISBN:
(纸本)9781510817371
Engaging in exploring multi-agent collaboration requires determining how to govern the shared activities. We examine the performance implications of selecting alternate modes of governance in multi-agent alliance relationships. A core set of results in this study relates to the ways in which governance structure interacts with agents' search capabilities. Alliance performance improves when the needs and supplies of coordination and exploration are matched. We find situations in which there is an inverted U relationship between governance mode and performance. At the end we discuss the contribution and the possibility of extension in the future.
Graph embeddings of bounded Euler genus (that means, embeddings with bounded orientable or nonorientable genus) help to design time-efficient algorithms for many graph problems. Since linear-time algorithms are known ...
详细信息
ISBN:
(纸本)9781450327107
Graph embeddings of bounded Euler genus (that means, embeddings with bounded orientable or nonorientable genus) help to design time-efficient algorithms for many graph problems. Since linear-time algorithms are known to compute embeddings of any bounded Euler genus, one can always assume to work with embedded graphs and, thus, obtain fast algorithms for many problems on any class of graphs of bounded Euler genus. Problems on graphs of bounded Euler genus are also important from the perspective of finding space-efficient algorithms, mostly focusing on problems related to finding paths and matchings in graphs. So far, known space-bounded approaches needed the severe assumption that an embedding is given as part of the input since no space-efficient embedding procedure for nonplanar graphs was known. The present work sidesteps this assumption and shows that embeddings of any bounded Euler genus can be computed in deterministic logarithmic space (logspace);allowing to generalize results on the space complexity of path and matching problems from embedded graphs to graphs of bounded Euler genus. The techniques developed for the embedding procedure also allow to compute canonical representations and, thus, solve the isomorphism problem for graphs of bounded Euler genus in logspace.
Purpose: Following Holland, complex adaptive systems (CASs) are collections of interacting, autonomous, learning decision makers embedded in an interactive environment. Modeling CASs is challenging for a variety of re...
详细信息
Purpose: Following Holland, complex adaptive systems (CASs) are collections of interacting, autonomous, learning decision makers embedded in an interactive environment. Modeling CASs is challenging for a variety of reasons including the presence of heterogeneity, spatial relationships, nonlinearity, and, of course, adaptation. The challenges of modeling CASs can largely be overcome by using the individual-level focus of agent-based modeling. Agent-based modeling has been used successfully to model CASs in many disciplines. Many of these models were implemented using agent-based modeling software such as Swarm, Repast 3, Repast Simphony, Repast for High-Performance Computing, MASON, NetLogo, or StarLogo. All of these options use modular imperative architectures with factored agents, spaces, a scheduler, logs, and an interface. Many custom agent-based models also use this kind of architecture. This paper's contribution is to introduce and apply a theoretical formalism for analyzing modular imperative agent-based models of CASs. This paper includes an analysis of three example models to show how the formalism is useful for predicting the execution time and space requirements for representations of common CASs. Method: The paper details the formalism and then uses it to prove several new findings about modular imperative agent-based models. Results: It is proven that the asymptotic time and space performance ofmodular imperative agent-based modeling studies is computationally optimal for a common class of problems. Here 'optimal' means that no other technique can solve the same problem computationally using less asymptotic time or space. Modular imperative agent-based models are shown to be universal models, subject to the correctness of the Church-Turing thesis. Several other results are also proven about the time and space performance of modular imperative agent-based models. The formalism is then used to predict the performance of three models and the results are fou
The more unambiguous statement of the P versus NP problem and the judgement of its hardness, are the key ways to find the full proof of the P versus NP problem. There are two sub-problems in the P versus NP problem. T...
详细信息
The more unambiguous statement of the P versus NP problem and the judgement of its hardness, are the key ways to find the full proof of the P versus NP problem. There are two sub-problems in the P versus NP problem. The first is the classifications of different mathematical problems (languages), and the second is the distinction between a non-deterministic Turing machine (NTM) and a deterministic Turing machine (DTM). The process of an NTM can be a power set of the corresponding DTM, which proves that the states of an NTM can be a power set of the corresponding DTM. If combining this viewpoint with Cantor's theorem, it is shown that an NTM is not equipotent to a DTM. This means that "generating the power set P(A) of a set A" is a non-canonical example to support that P is not equal to NP.
We briefly survey a number of important recent uchievements in Theoretical Computer Science （TCS）, especially computational complexity theory. We will discuss the PCP Theorem, its implications to inapproximability o...
详细信息
We briefly survey a number of important recent uchievements 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.
暂无评论