We study multi-structural games, played on two sets $\mathcal{A}$ and $\mathcal{B}$ of structures. These games generalize Ehrenfeucht-Fra\"{i}ss\'{e} games. Whereas Ehrenfeucht-Fra\"{i}ss\'{e} games capture the quantifier rank of a first-order sentence, multi-structural games capture the number of quantifiers, in the sense that Spoiler wins the $r$-round game if and only if there is a first-order sentence $\phi$ with at most $r$ quantifiers, where every structure in $\mathcal{A}$ satisfies $\phi$ and no structure in $\mathcal{B}$ satisfies $\phi$. We use these games to give a complete characterization of the number of quantifiers required to distinguish linear orders of different sizes, and develop machinery for analyzing structures beyond linear orders.

We study multi-structural games, played on two sets ${\mathcal{A}}$ and ${\mathcal{B}}$ of structures. These games generalize Ehrenfeucht-Fraïssé games. Whereas Ehrenfeucht-Fraïssé games capture the quantifier rank of a first-order sentence, multi-structural games capture the number of quantifiers, in the sense that Spoiler wins the r-round game if and only if there is a first-order sentence ϕ with at most r quantifiers, where every structure in ${\mathcal{A}}$ satisfies ϕ and no structure in ${\mathcal{B}}$ satisfies ϕ. We use these games to give a complete characterization of the number of quantifiers required to distinguish linear orders of different sizes, and develop machinery for analyzing structures beyond linear orders.

Inferences about structured patterns in human decision making have been drawn from medium-scale simulated competitions with human subjects. The concepts analyzed in these studies include level-k thinking, satisficing, and other human error tendencies. These concepts can be mapped via a natural depth of search metric into the domain of chess, where copious data is available from hundreds of thousands of games by players of a wide range of precisely known skill levels in real competitions. The games are analyzed by strong chess programs to produce authoritative utility values for move decision options by progressive deepening of search. Our experiments show a significant relationship between the formulations of level-k thinking and the skill level of players. Notably, the players are distinguished solely on moves where they erred -- according to the average depth level at which their errors are exposed by the authoritative analysis. Our results also indicate that the decisions are often independent of tail assumptions on higher-order beliefs. Further, we observe changes in this relationship in different contexts, such as minimal versus acute time pressure. We try to relate satisficing to insufficient level of reasoning and answer numerically the question, why do humans blunder?

This paper develops and tests formulas for representing playing strength at chess by the quality of moves played, rather than by the results of games. Intrinsic quality is estimated via evaluations given by computer chess programs run to high depth, ideally so that their playing strength is sufficiently far ahead of the best human players as to be a `relatively omniscient' guide. Several formulas, each having intrinsic skill parameters s for `sensitivity' and c for `consistency', are argued theoretically and tested by regression on large sets of tournament games played by humans of varying strength as measured by the internationally standard Elo rating system. This establishes a correspondence between Elo rating and the parameters. A smooth correspondence is shown between statistical results and the century points on the Elo scale, and ratings are shown to have stayed quite constant over time. That is, there has been little or no `rating inflation'. The theory and empirical results are transferable to other rational-choice settings in which the alternatives have well-defined utilities, but in which complexity and bounded information constrain the perception of the utility values.

Systems Engineering often involves computer modelling the behaviour of proposed systems and their components. Where a component is human, fallibility must be modelled by a stochastic agent. The identification of a model of decision-making over quantifiable options is investigated using the game-domain of Chess. Bayesian methods are used to infer the distribution of players' skill levels from the moves they play rather than from their competitive results. The approach is used on large sets of games by players across a broad FIDE Elo range, and is in principle applicable to any scenario where high-value decisions are being made under pressure.

We introduce resource-bounded betting games and propose a generalization of Lutz's resource-bounded measure in which the choice of the next string to bet on is fully adaptive. Lutz's martingales are equivalent to betting games constrained to bet on strings in lexicographic order. We show that if strong pseudorandom number generators exist, then betting games are equivalent to martingales for measure on E and EXP. However, we construct betting games that succeed on certain classes whose Lutz measures are important open problems: the class of polynomial-time Turing-complete languages in EXP and its superclass of polynomial-time Turing-autoreducible languages. If an EXP-martingale succeeds on either of these classes, or if betting games have the "finite union property" possessed by Lutz's measure, one obtains the nonrelativizable consequence $\mbox{BPP} \neq \mbox{EXP}$. We also show that if $\mbox{EXP} \neq \mbox{MA}$, then the polynomial-time truth-table-autoreducible languages have Lutz measure zero, whereas if $\mbox{EXP} = \mbox{BPP}$, they have measure one.

We define probabilistic martingales based on randomized approximation schemes, and show that the resulting notion of probabilistic measure has several desirable robustness properties. Probabilistic martingales can simulate the "betting games" and can cover the same class that a "natural proof" diagonalizes against, as implicitly already shown. The notion would become a full-fledged measure on bounded-error complexity classes such as BPP and BPE if it could be shown to satisfy the "measure conservation" axiom for these classes. We give a sufficient condition in terms of simulation by "decisive" probabilistic martingales that implies not only measure conservation, but also a much tighter bounded error probabilistic time hierarchy than is currently known. In particular it implies BPTIME[O(n)]/spl ne/BPP, which would stand in contrast to recent claims of an oracle A giving BPTIME/sup A/[O(n)]=BPP/sup A/. This paper also makes new contributions to the problem of defining (deterministic) measure on P and other sub-exponential classes.

We study families of Boolean circuits with the property that the number of gates at distance t fanning into or out of any given gate in a circuit is bounded above by a polynomial in t of some degree k. We prove that such circuits require size /spl Omega/(n/sup 1+1/k//log n) to compute several natural families of functions, including sorting, finite field arithmetic, and the "rigid linear transformations" of L. Valiant (1977). Our proof develops a "separator theorem" in the style of R. Lipton and R. Tarjan (1979) for a new class of graphs, and our methods may have independent graph-theoretic interest.

A realistic model of computation called the block-move (BM) model is developed. The BM regards computation as a sequence of finite transductions in memory, and operations are timed according to a memory cost parameter $\mu $. Unlike previous memory-cost models, the BM provides a rich theory of linear time, and in contrast to what is known for Turing machines (TMs), the BM is proved to be highly robust for linear time. Under a wide range of $\mu $ parameters, many forms of the BM model, ranging from a fixed-wordsize random-access machine (RAM) down to a single finite automaton iterating itself on a single tape, are shown to simulate each other up to constant factors in running time. The BM is proved to enjoy efficient universal simulation, and to have a tight deterministic time hierarchy. Relationships among BM and TM time complexity classes are studied.

We prove that if strong pseudorandom number generators exist, then the class of languages that have polynomial-sized circuits (P/poly) is not measurable within exponential time, in terms of the resource-bounded measure theory of Lutz. We prove our result by showing that if P/poly has measure zero in exponential time, then there is a natural proof against P/poly, in the terminology of Razborov and Rudich (1994). We also provide a partial converse of this result.

We present a general technique for showing that many properties of recursive languages are not provable. Here “provable” is taken with respect to a given sound, recursively axiomatized formal system J, such as Peano arithmetic. A representative application (Theorems 6.1–6.2) concerns the property of intractability, i.e., non-membership in the class P. It says that there exists a language E such that E is not in P, but the formal assertion ‘E is not in P’ is independent of J. Moreover, given any recursive language A ∉ P, we can construct E such that also E ⩽mP A. Our techniques strengthen similar results in the literature and lead to several other applications pertaining to P-immune sets, oracle separations, and the Berman-Hartmanis conjecture. We explain the phenomenon of unprovability in terms of both recursive properties of the formal systems J under consideration, and topological properties of complexity classes in a natural space which we call R. Provable properties correspond to closed sets of r. The topology provides geometric intuition for recognizing classes which are not closed in R, such as NPP (unless it is empty). We show how independence results follow immediately for these classes. In conclusion we argue that the type of independence result presented here forms an obstacle for day-to-day work in complexity theory, but does not bear directly on the possible independence of the P = NP question from Peano arithmetic or set theory. However, we believe our tools capable of measuring the link between the structure of a given language E ∉ P and the formal strength needed to prove the assertion ‘E ∉ P.’ Research in this direction has already been initiated by D. Joseph (J. Comput. System Sci. 25 (1983), 205–228).