Yet some more complexity results for default logic

We identify several new tractable subsets and several new intractable simple cases for reasoning in the propositional version of Reiter's default logic. The majority of our findings are related to brave reasoning. By making some intuitive observations, most classes that we identify can be derived quite easily from some subsets of default logic already known in the literature. Some of the subsets we discuss are subclasses of the so-called “extended logic programs”. All the tractable subsets presented in this paper can be recognized in linear time.     

Some results on uniform arithmetic circuit complexity

We introduce a natural set of arithmetic expressions and define the complexity class AE to consist of all those arithmetic functions (over the fieldsF _2n) that are described by these expressions. We show that AE coincides with the class of functions that are computable with constant depth and polynomial-size unbounded fan-in arithmetic circuits satisfying a natural uniformity constraint (DLOGTIME-uniformity). A 1-input and 1-output arithmetic function over the fieldsF2n may be identified with ann-input andn-output Boolean function when field elements are represented as bit strings. We prove that if some such representation is X-uniform (where X is P or DLOGTIME), then the arithmetic complexity of a function (measured with X-uniform unbounded fan-in arithmetic circuits) is identical to the Boolean complexity of this function (measured with X-uniform threshold circuits). We show the existence of a P-uniform representation and we give partial results concerning the existence of representations with more restrictive uniformity properties.The research of G. S. Frandsen was partially carried out while visiting Dartmouth College, New Hampshire. He was partially supported by the Danish Natural Science Research Council (Grant No. 11-7991) and by the ESPRIT II Basic Research Actions Program of the EC under Contract No. 3075 (project ALCOM). D. A. M. Barrington's research was supported by NSF Computer and Computation Theory Grant CCR-8714714.     

Some applications of the McCreight-Meyer algorithm in abstract complexity theory

The McCreight-Meyer algorithm is a priority-queue construction from abstract recursion theory which was designed for the proof of the so-called Naming or Honesty theorem. We explain the ideas behind the algorithm, pointing at its behaviour as a “closure operator” and obtaining various known and new results as corollaties of more general assertions.     

Some recent results in heuristic search theory

The paper summarizes recent analytical investigations of the mathematical properties of heuristics and their influence on the performance of common search techniques. The results are reported without proofs together with discussions of motivations and interpretations. The highlights include the following: the optimality of A*; relations between the precision of the heuristic estimates and the average complexity of the search; comparisons of the average complexities of A* and BACKTRACKING; procedures for comparing and combining nonadmissible heuristic functions; the influence of the weight w (in f = (l - w) g + wh) on the complexity of A*; the pruning power of alphabeta, SSS*, and SCOUT; the effect of successor ordering on search complexity, and the effect of search depth of the quality of decisions in game-playing.     

Some convergence results in Dempster–Shafer theory

 Belief functions and basic probability assignments defined on a finite frame of discernment are given an intuitive extension in this paper. Some convergence results are then given on sets converging from above and below; also, a weakened form of one of the Borel–Cantelli lemmas is given. The paper concludes with a theorem on the Dempster–Shafer random variable.     

Some results on the computational complexity of symmetric connectionist networks

Connectionists models are currently being investigated actively by many researchers in artificial intelligence, information theory and computational neuroscience. These networks have been shown to be applicable to a wide range of domains such as content addressable memories, semantic nets, computer vision, natural language parsing, speech recognition, and approximation schemes for difficult optimization problems. In this paper, we address several basic problems related to the computational complexity of discrete Hopfield nets (connectionist networks with symmetric connections).This research was supported in part by AFOSR Grant No. AFOSR-89-1151 and NSF Grant No. IRI-88-09324.     

Conditional independence in probability theory on MV-algebras

Conditional independence relation of observables on an MV-algebra with product is formulated and basic properties are proven. An analogy with a classical definition of conditional independence of random variables is discussed and the MV-algebraic concept of conditioning is further explored.     

Improved results on the probabilistic theory of the joint linear complexity of multisequences

We improve previous results on the asymptotic behavior and the expected value of the joint linear complexity of random multisequences over finite fields.These results are of interest for word-based stream ciphers in cryptology.     

How to prove representation-independent independence results

A true assertion about the input-output behavior of a Turing machine M may be independent of (i.e., impossible to prove in) a theory T because the computational behavior of M is particularly opaque, or because the function or set computed by M is inherently subtle. The latter sorts of representation-independent independence results are more satisfying. For π₂ assertions, the best-known techniques for proving independence yield representation-independent results as a matter of course. This paper illustrates current understanding of unprovability for π₂ assertions by demonstrating that very weak conditions on classes of sets S and R guarantee that there exists a set L₀ ε R - S such that L₀ is not probably infinite (hence, not provably nonregular, nondeterministics, noncontext-free, not in P, etc.). Under slightly stronger conditions, such L₀'s may be found within every L ε R - S.     

Several results in program size complexity

Intuitively, the program size complexity of a binary string measures the amount of information in the string. Researchers have formalized this notion in a number of different ways. Here, we demonstrate similarities between some of these formulations. We also investigate in some detail the properties of Kolmogorov's complexity measure.     

On miniaturized problems in parameterized complexity theory

We introduce a general notion of miniaturization of a problem that comprises the different miniaturizations of concrete problems considered so far. We develop parts of the basic theory of miniaturizations. Using the appropriate logical formalism, we show that the miniaturization of a definable problem in W[t]$\mathrm{W}[t]$ lies in W[t]$\mathrm{W}[t]$, too. In particular, the miniaturization of the dominating set problem is in W[2]$\mathrm{W}[2]$. Furthermore, we investigate the relation between f(k)·n^o(k)$f(k)·n^{\mathrm{o}(k)}$ time and subexponential time algorithms for the dominating set problem and for the clique problem.     

Some elements of a Galois theory of the structure and complexity of the tree automorphism problem

Engeler's generalization of Galois theory is applied to the tree automorphism problem. We compute the Galois group of each instance of this problem. The group yields information on four aspects of problem difficulty: lower bounds for the time complexity of different solution approaches, ‘hard’ instances of the problem, dependence of problem difficulty on structural parameters of the input and relative solvability. In addition we show that an approximation of this information can be obtained from the group of the problem of finding ‘approximate’ tree automorphisms.     

Entropy and algorithmic complexity in quantum information theory

A theorem of Brudno says that the entropy production of classical ergodic information sources equals the algorithmic complexity per symbol of almost every sequence emitted by such sources. The recent advances in the theory and technology of quantum information raise the question whether a same relation may hold for ergodic quantum sources. In this paper, we discuss a quantum generalization of Brudno’s result which connects the von Neumann entropy rate and a recently proposed quantum algorithmic complexity.     

Assessing complexity in cellular automata using information theory

ABSTRACT

We discuss two ways in which information theory can be used to assess complexity in a system of interacting agents. In the first part, we adopt a global viewpoint and propose a characterization of complexity based on successive maximum entropy estimations of the probability density describing the system, thereby quantifying the respective role played by low and high orders of interaction. In the second part we reconsider the question from a local perspective, focussing on the statistical dependencies between neighbouring agents. These tools are tried on simple cellular automata in order to put them in perspective with other notions of complexity usually employed for such systems. We show that these approaches are hardly comparable, despite some overlap in simple cases. However this allows to interpret complexity in terms of interactions at work in a system (instead of making reference to any particular realization of this dynamics), and to shed some light on the role of initial conditions in complex systems.

Clustering of the 88 non-equivalent Elementary Cellular Automata according to their position in the space of information processing features. Rules are coloured according to their Wolfram class. ECA in class I are shown in black, class II in red, chaotic automata (class III) in green and automata displaying complex behaviour (class IV) in blue. In spite of some important important differences, information features and Wolfram class are seen to overlap to a certain extent.