On the complexity of simulating space-bounded quantum computations

This paper studies the space-complexity of predicting the long-term behavior of a class of stochastic processes based on evolutions and measurements of quantum mechanical systems. These processes generalize a wide range of both quantum and classical space-bounded computations, including unbounded error computations given by machines having algebraic number transition amplitudes or probabilities. It is proved that any space s quantum stochastic process from this class can be simulated probabilistically with unbounded error in space O(s), and therefore deterministically in space O(s²).     

Integrating psychology and politics.

Comments on the article "A house divided? The psychology of red and blue America" by D. C. Seyle and M. L. Newman (see record 2006-11202-001). Seyle and Newman concluded that the red and blue metaphor is inaccurate and proposed a purple America strategy to better convey that the majority of people do not align themselves with political extremes. There is interdisciplinary agreement on this. Although not cited by Seyle and Newman, the findings by Professor Fiorina of Stanford University were reported by the APA Monitor on Psychology in its coverage of the 2005 APA State Leadership Conference (Murray Law, 2005). In contrast to their social psychological analysis, Seyle and Newman were incorrect in concluding that "[a]s psychologists, we are not in a position to change either the elements of the American political system that may spur this conflict or even the decisions made by pundits, politicians, and reporters about the terms they choose to use in political discussion" (p. 579). (PsycINFO Database Record (c) 2010 APA, all rights reserved)     

The complexity of economic equilibria for house allocation markets

We prove NP-completeness of deciding the existence of an economic equilibrium in so-called house allocation markets. House allocation markets are markets with indivisible goods in which every agent holds exactly one copy of some good.     

Optimal Solutions for the Temporal Precedence Problem

Abstract. In this paper we refer to the Temporal Precedence Problem on Pure Pointer Machines . This problem asks for the design of a data structure, maintaining a set of stored elements and supporting the following two operations: insert and precedes . The operation insert (a) introduces a new element a in the structure, while the operation precedes (a,b) returns true iff element a was inserted before element b temporally. In [11] a solution was provided to the problem with worst-case time complexity O (log log n ) per operation and O(n log log n) space, where n is the number of elements inserted. It was also demonstrated that the precedes operation has a lower bound of Ω (log log n ) for the Pure Pointer Machine model of computation. In this paper we present two simple solutions with linear space and worst-case constant insertion time. In addition, we describe two algorithms that can handle the precedes (a,b) operation in O (log log d ) time, where d is the temporal distance between the elements a and b .     

最佳基数排序

基数排序由于其效率高而被广泛应用。通常,基数排序所用的基数是10,然而,如果求得一个基数r_(best),并且用r_(best)为基数进行基数排序使排序时间达到最小,则这将具有非常重要的意义。本文给出了求r_(best)的方法,分析了以r_(best)为基数进行基数排序的时间复杂度,提出了进一步提高效率的措施,并将以r_(best)为基数的基数排序速度与以10为基数的基数排序进行了比较。     

Computational complexity of queries based on itemsets

We investigate determining the exact bounds of the frequencies of conjunctions based on frequent sets. Our scenario is an important special case of some general probabilistic logic problems that are known to be intractable. We show that despite the limitations our problems are also intractable, namely, we show that checking whether the maximal consistent frequency of a query is larger than a given threshold is NP-complete and that evaluating the Maximum Entropy estimate of a query is PP-hard. We also prove that checking consistency is NP-complete.     

Width-restricted layering of acyclic digraphs with consideration of dummy nodes

This paper deals with the problem of finding graph layerings restricted to a given maximal width. However, other than previous approaches for width-restricted layering, we take into account the space for dummy nodes, which are introduced by edges crossing a layer. The main result is that the problem of finding a width-restricted layering under consideration of dummy nodes is NP-complete even when all regular nodes have the same constant width and all dummy nodes have the same constant width.     

PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance

We consider the problem of PAC-learning distributions over strings, represented by probabilistic deterministic finite automata (PDFAs). PDFAs are a probabilistic model for the generation of strings of symbols, that have been used in the context of speech and handwriting recognition, and bioinformatics. Recent work on learning PDFAs from random examples has used the KL-divergence as the error measure; here we use the variation distance. We build on recent work by Clark and Thollard, and show that the use of the variation distance allows simplifications to be made to the algorithms, and also a strengthening of the results; in particular that using the variation distance, we obtain polynomial sample size bounds that are independent of the expected length of strings.     

The complexity of some reachability problems for a system on a finite group

We consider a system defined as the product of a finite set of periodic systems on cyclic groups. It is of interest to determine if certain subgroups and unions of subgroups of the state set are reachable from a specified initial state, and in particular to determine the computational complexity of verifying such reachability. These questions are motivated by certain problems that arise in the modelling and control of discrete event systems and certain forms of periodic scheduling. Our main result is that deciding whether or not the union of a certain set of subgroups is reachable or not is NP-complete.     

The vulnerability of geometric sequences based on fields of odd characteristic

A new method of cryptologic attack on binary sequences is given, using their linear complexities relative to odd prime numbers. We show that, relative to a particular prime number p, the linear complexity of a binary geometric sequence is low. It is also shown that the prime p can be determined with high probability by a randomized algorithm if a number of bits much smaller than the linear complexity is known. This determination is made by exploiting the imbalance in the number of zeros and ones in the sequences in question, and uses a new statistical measure, the partial imbalance.This project was sponsored by the National Security Agency under Grant No. MDA904-91-H-0012. The United States Government is authorized to reproduce and distribute reprints notwithstanding any copyright notation hereon.