We study the effect of query order on computational power, and show that $\pjk$-the languages computable via a polynomial-time machine given one query to the jth level of the boolean hierarchy followed by one query to the kth level of the boolean hierarchy-equals $\redttnp{j+2k-1}$ if j is even and k is odd, and equals $\redttnp{j+2k}$ otherwise. Thus, unless the polynomial hierarchy collapses, it holds that for each $1\leq j \leq k$: $\pjk = \pkj \iff (j=k) \lor (j{is even} \land k=j+1)$. We extend our analysis to apply to more general query classes.

Lane A. Hemaspaandra Harald Hempel Gerd Wechsung

Carl Gustav Hempel (1905-1997) formulated the dilemma that carries his name in an attempt to determine the boundaries of physics. Where does physics go over into metaphysics? The purpose of this contribution is to indicate how a recently developed field of research, the physics of computation, might offer a new answer to that old question: The boundary between physics and metaphysics is the boundary between what can and what cannot be computed in the age of the universe.

C. W. J. Beenakker

Recently Dicks-Linnell determined the $L^2$-Betti numbers of the orientable surface-plus-one-relation groups, and their arguments involved some results that were obtained topologically by Hempel and Howie. Using algebraic arguments, we now extend all these results of Hempel and Howie to a larger class of two-relator groups, and we then apply the extended results to determine the $L^2$-Betti numbers of the non-orientable surface-plus-one-relation groups.

Yago Antolin Warren Dicks Peter A. Linnell

During the past decade, nine papers have obtained increasingly strong consequences from the assumption that boolean or bounded-query hierarchies collapse. The final four papers of this nine-paper progression actually achieve downward collapse---that is, they show that high-level collapses induce collapses at (what beforehand were thought to be) lower complexity levels. For example, for each $k\geq 2$ it is now known that if $\psigkone=\psigktwo$ then $\ph=\sigmak$. This article surveys the history, the results, and the technique---the so-called easy-hard method---of these nine papers.

Edith Hemaspaandra Lane A. Hemaspaandra Harald Hempel

First-order phase transitions (PTs) with more than one globally conserved charge, so-called noncongruent PTs, have characteristic differences compared to congruent PTs (e.g., dimensionality of phase diagrams and location of critical points and endpoints). Here we discuss the noncongruent features of the QCD PT and compare it with the nuclear liquid-gas (LG) PT, for symmetric and asymmetric matter in heavy-ion collisions and neutron stars. In addition, we have identified a principle difference between the LG and the QCD PT: they have opposite slopes in the pressure-temperature plane.

Matthias Hempel Veronica Dexheimer Stefan Schramm Igor Iosilevskiy

The notion of bounded FC-nilpotent group is introduced and it is shown that any such group is nilpotent-by-finite, generalizing a result of Neumann on bounded FC-groups.

Nadja Hempel Daniel Palacin

For n-bridge decompositions of links in S^3, we propose a practical method to ensure that the Hempel distance is at least two.

Kazuto Takao

In Hempel's paradox of the ravens, seeing a red pencil is considered as supporting evidence that all ravens are black. Also known as the Paradox of Confirmation, the paradox and its many resolutions indicate that we cannot underestimate the logical and statistical elements needed in the assessment of evidence in support of a hypothesis. Most of the previous analyses of the paradox are within the Bayesian framework. These analyses and Hempel himself generally accept the paradoxical conclusion; it feels paradoxical supposedly because the amount of evidence is extremely small. Here I describe a nonBayesian analysis of various statistical models with an accompanying likelihood-based reasoning. The analysis shows that the paradox feels paradoxical because there are natural models where observing a red pencil has no relevance to the color of ravens. In general the value of the evidence depends crucially on the sampling scheme and on the assumption about the underlying parameters of the relevant model.

Yudi Pawitan

Motivated by a generalization of Hempel's dilemma, I introduce a novel notion of empirical structure, as well as theory supervenience as a new reductive relationship between theories. One theory supervenes on another theory if the empirical structure of the latter theory refines the empirical structure of the former theory. I then argue that (1) empirical structure physicalism, the thesis that the current special sciences supervene both on current and on future physics, avoids both horns of Hempel's dilemma; (2) in particular, mental theories remain empirically dispensable in the future; (3) empirical structure realism, the thesis that earlier theories of physics supervene on later theories of physics, is supported by an optimistic meta-induction; (4) this optimistic meta-induction can coexist with the well-known pessimistic meta-induction; (5) empirical structure physicalism is appropriately labeled as a type of physicalism; and (6) empirical structure physicalism is compatible with multiple realization. To illustrate the plausibility of empirical structure physicalism, I also briefly address the so-called knowledge argument.

Balazs Gyenis

Hemaspaandra, Hempel, and Wechsung [cs.CC/9909020] raised the following questions: If one is allowed one question to each of two different information sources, does the order in which one asks the questions affect the class of problems that one can solve with the given access? If so, which order yields the greater computational power? The answers to these questions have been learned-inasfar as they can be learned without resolving whether or not the polynomial hierarchy collapses-for both the polynomial hierarchy and the boolean hierarchy. In the polynomial hierarchy, query order never matters. In the boolean hierarchy, query order sometimes does not matter and, unless the polynomial hierarchy collapses, sometimes does matter. Furthermore, the study of query order has yielded dividends in seemingly unrelated areas, such as bottleneck computations and downward translation of equality. In this article, we present some of the central results on query order. The article is written in such a way as to encourage the reader to try his or her own hand at proving some of these results. We also give literature pointers to the quickly growing set of related results and applications.

Edith Hemaspaandra Lane A. Hemaspaandra Harald Hempel