User scott aaronson - MathOverflow

Is deciding whether a Turing machine provably runs forever equivalent to the halting problem?

2013-05-22T02:03:49Z

Assume for this question that ZF set theory is sound.

Now consider the language "PROVELOOP," which consists of all descriptions of Turing machines M, for which there exists a ZF proof that M runs forever on a blank input.

It's clear that PROVELOOP is recursively-enumerable, and hence reducible to the halting problem. I can also prove that PROVELOOP is undecidable (details below). But I can't see how to prove that PROVELOOP is Turing-equivalent to the halting problem! (This is contrast to, say, the set of all descriptions of Turing machines that provably halt, which is just the same thing as the set of all descriptions of Turing machines that do halt!)

I'm guessing that there's a reduction from HALT that I haven't thought of, though it would be exciting if PROVELOOP were to have intermediate degree like the Friedberg-Muchnik languages. In any case, whatever the answer, I assume it must be known! Hence this question.

Proof that PROVELOOP is undecidable. Consider the following problem, which I'll call "Consistent Guessing" (CG). You're given as input a description of a Turing machine M. If M accepts given a blank input, then you need to accept, while if M rejects you need to reject. If M runs forever, then you can either accept or reject, but in either case you must halt.

By adapting the undecidability proof for HALT, we can easily show that CG is undecidable also. Namely, suppose P solves CG. Let Q take as input a Turing machine description $\langle M \rangle$, and solve CG for the machine $M(\langle M \rangle)$ by calling P as a subroutine. Then $Q(\langle Q \rangle)$ (i.e., Q run on its own description) must halt, accept if it rejects, and reject if it accepts.

Let's now prove that CG is Turing-reducible to PROVELOOP. Given a description of a Turing machine M for which we want to solve CG, simply create a new Turing machine M', which does the same thing as M except that if M accepts, then M' goes into an infinite loop instead. Then if M accepts, then M' loops, and moreover there's a ZF proof that M' loops. On the other hand, if M rejects, then M' also rejects, and there's no ZF proof that M' loops (by the assumption that ZF is sound). If M loops, then there might or might not be a ZF proof that M' loops -- but in any case, by calling PROVELOOP on M', we separate the case that M accepts from the case that M rejects, and therefore solve CG on M. So $CG \le_{T} PROVELOOP$, and PROVELOOP is undecidable as well.

One more note. In the comments of this blog post, Andy Drucker supplied a proof that CG is not equivalent to HALT, but rather has Friedberg-Muchnik-like intermediate status. So, the situation is

$0 \lt_{T} CG \le_{T} PROVELOOP \le_{T} HALT$

with at least one of the last two inequalities strict. Again, I'm sure this is all implicit in some computability paper from the 1960s or something, but I wouldn't know where to find it.

"psi-epistemic theories" in 3 or more dimensions

2012-04-30T00:23:39Z

In their recent paper The Quantum State Can Be Interpreted Statistically, Lewis et al. end with a very nice mathematical question, one whose answer (either way) would have interesting implications for the foundations of quantum mechanics. In the hopes of getting some non-quantum math folks interested in their question---and maybe even finding someone to say "the answer is trivial for the following reason..." :-)---I decided to state the question for the MO community, shorn of all the physics and philosophy.

Let H_d be the set of unit vectors in $\mathbb{C}^d$. A ψ-epistemic theory in d dimensions consists of the following:

A measurable space Λ (called the "space of ontic states").
A function mapping each unit vector ψ∈H_d to a probability measure D_ψ over Λ.
A function f(λ,M,i)∈[0,1], which takes as input an ontic state λ∈Λ, an ordered orthonormal basis M=(v₁,...,v_d) for $\mathbb{C}^d$, and an index i∈{1,...,d}.

f must satisfy the following two conditions:

(i) $\sum_{i=1}^{d}f(\lambda,M,i)=1$ for all λ and M. (Intuitively, f must give rise to a probability distribution over the "measurement outcomes" v₁,...,v_d in M.)

(ii) $\int_{\lambda \sim D_{\psi}} f(\lambda,M,i) d\lambda = |v_{i}^{*}\psi|^{2}$ for all ψ, M, and i. (Intuitively, the probability of the measurement outcome v_i, averaged over all λ drawn from D_ψ, must equal the squared projection of ψ onto v_i.)

Note that we can trivially satisfy conditions (i) and (ii) as follows:

Λ=H_d
D_ψ assigns probability 1 to λ=ψ, and probability 0 to all other states in Λ
f(ψ,M,i) = |v_i^*ψ|²

Thus, let Supp(D)⊆Λ be the support of D, and call a ψ-epistemic theory nontrivial if there exist ψ≠ϕ such that $Supp(D_{\psi})\cap Supp(D_{\phi}) \ne \emptyset$.

Observe that, if ψ and ϕ are orthogonal, then Supp(D_ψ) and Supp(D_ϕ) must be disjoint. This is because, if we set v₁=ψ and v₂=ϕ, then $v_{1}^{*}\psi = v_{2}^{*}\phi = 1$ and $v_{1}^{*}\phi = v_{2}^{*}\psi = 0$, which is not possible if D_ψ and D_ϕ have any nonzero overlap. Motivated by this observation, call a theory maximally nontrivial if $Supp(D_{\psi})\cap Supp(D_{\phi}) \ne \emptyset$ whenever ψ and ϕ are not orthogonal.

I can now state Lewis et al.'s open problem:

Does there exist a maximally-nontrivial ψ-epistemic theory in dimensions d≥3?

Update: See the comments for an extremely nice solution by George Lowther, plus my followup questions.

I know of two results directly relevant to this problem.

First, there exists a maximally-nontrivial theory in dimension d=2, which was found by Kochen and Specker in 1967. See this paper by Rudolph for more details, including why the obvious generalizations to 3 or more dimensions seem to fail. Briefly, the Kochen-Specker theory is defined as follows:

Λ=H₂.
D_ψ assigns probability measure $2 | \psi^{*} \phi|^{2} - 1$ to ϕ if $| \psi^{*} \phi|^{2} \geq 1/2$, and probability measure 0 to ϕ otherwise.
f(ψ,M,i) = 1 if $|v_{i}^{*} \psi|^{2} \geq 1/2$, and f(ψ,M,i) = 0 otherwise.

(Warning: I converted from a different representation, and can't promise I didn't get a factor of 2 wrong or something like that.)

The second result is that, for all finite d, there exists a nontrivial ψ-epistemic theory (though it's far from being maximally nontrivial). This is the main result of Lewis et al.

My own guess is that maximally-nontrivial theories don't exist for d≥3, but I'd only give it 60% confidence.

To anticipate some questions:

Yes, I'd also be interested in this problem with $\mathbb{R}$ in place of $\mathbb{C}$ (though I suspect the two cases are pretty similar).
Yes, I'd be interested in negative results for restricted classes of theories. Here are a few examples of restrictions one could look at, in various combinations: Λ=H_d, f∈{0,1}, f is continuous, symmetry under unitary transformations, symmetry under relabeling of the v_i's.
No, I don't know how to rule out that the answer could depend on the Axiom of Choice or something crazy like that (but I doubt it).

Update (March 20, 2013): Adam Bouland, Lynn Chua, George Lowther, and myself now have a paper on ψ-epistemic theories originating with this MO post. The paper contains the construction below, but also proves impossibility results for ψ-epistemic theories when an additional symmetry condition is imposed.

Can a string's sophistication be defined in an unsophisticated way?

2012-07-31T15:05:01Z

This question is about sophistication, a way of measuring the amount of "interesting, non-random information" in a binary string, which was proposed by Kolmogorov and others in the 1980s. I'll define all the needed concepts below, but for further reading, I recommend this paper by Antunes and Fortnow, this PhD thesis by Antunes, or this paper by Gacs, Tromp, and Vitanyi.

Given an n-bit string x, recall that K(x), the Kolmogorov complexity of x, is the length in bits of the shortest program p (in some fixed universal programming language) such that p()=x: that is, p halts and outputs x when given a blank input. Given a set S ⊆ {0,1}ⁿ, one can also define K(S) to be the length in bits of the shortest program that outputs the 2ⁿ-bit characteristic sequence of S. Finally, one can define K(x|S) to be the length in bits of the shortest program p such that p(S)=x: that is, p halts and outputs x when fed the characteristic sequence of S as input.

The "problem" with Kolmogorov complexity is that it's maximized by random strings, which are intuitively not very "complex" at all. This motivates the following alternatives to K(x):

Given an n-bit string x and a constant c>0, the oxymoronically-named naïve sophistication of x, or NSoph_c(x), is the smallest possible value of K(S), over all sets S ⊆ {0,1}ⁿ such that x∈S and K(x|S) ≥ log₂|S| - c. Intuitively, NSoph measures the minimum number of bits needed to specify a set of which x is an incompressible or Kolmogorov-random element. I call it "naïve" because it's the first measure I would think of that's sort of like Kolmogorov complexity but small for random strings (small because for random strings, one can take S={0,1}ⁿ, whence NSoph_c(x)=O(1)).

Meanwhile, the coarse sophistication of x or CSoph(x), defined by Antunes, is the smallest possible value of 2K(S)+log₂|S|-K(x), over all sets S ⊆ {0,1}ⁿ such that x∈S. Intuitively, CSoph measures the minimum number of bits needed to specify x via a "two-part code," where the first part specifies a set S containing x, the second part gives the index of x in S, and a penalty gets applied both for K(S) (the length of the first part of the code) and for K(S)+log₂|S|-K(x) (the amount by which the total code length exceeds K(x)). Despite the unwieldy definition, Antunes amasses evidence that CSoph is in various ways the "right" measure of the non-random information in a string.

My question is now the following:

Let c=O(1). Is NSoph_c(x), my "unsophisticated kind of sophistication," always close to CSoph(x), Antunes' "sophisticated kind of sophistication"? Or can there be a large gap between the two? If so, how large?

Here's what I know about this question:

CSoph(x) ≤ 2NSoph_c(x)+c. To see this: let the set S minimize K(S) subject to x∈S and K(x|S) ≥ log₂|S| - c. Then CSoph(x) ≤ 2K(S)+log₂|S|-K(x) ≤ 2NSoph_c(x)+log₂|S|-K(x) ≤ 2NSoph_c(x)+log₂|S|-K(x|S) ≤ 2NSoph_c(x)+c.
NSoph_c(x) can be about twice as large as CSoph(x). To see this: first, as observed by Antunes, if x is an n-bit string, then CSoph(x) never exceeds n/2+o(n). (For we can always achieve that bound by setting S={x} if K(x)≤n/2, or S={0,1}ⁿ if K(x)>n/2.) Second, as discussed by Gacs, Tromp, Vitanyi, it's possible to construct what Kolmogorov called "absolutely non-random objects," meaning n-bit strings x such that K(x|S) ≤ log₂|S| - O(1) whenever K(S) ≤ n - clog(n). For these strings, we clearly have NSoph_c(x) ≥ n-O(log n) if c=O(1). Combining now yields the result.

As a final note, NSoph and CSoph are both different from the "ordinary sophistication" Soph, which is defined as follows: Soph_c(x) is the smallest possible value of K(S), over all sets S ⊆ {0,1}ⁿ such that x∈S and K(S) + log₂|S| ≤ K(x)+c. Intuitively, Soph_c(x) measures the minimum number of bits needed for the first part of a near-minimal two-part code specifying the string x. One can observe the following (I'll give details on request):

NSoph_c(x) ≤ Soph_c(x)
CSoph(x) ≤ Soph_c(x)+c
There exist strings x for which Soph_c(x) is very large but NSoph_c(x) and CSoph(x) are both very small.

I'll also observe that NSoph_c(x), CSoph(x), and Soph_c(x) are all upper-bounded by the Kolmogorov complexity K(x) (or rather, by K(x)+c).

Update: Sorry, just minutes after writing this post, I think I see the answer to one direction of my problem! Consider the "absolutely non-random objects" x discussed above. These objects satisfy K(x) ≥ NSoph_c(x) ≥ n-O(log n). But precisely because their Kolmogorov complexity is so large, they should also satisfy CSoph(x)=O(log n), achieved by setting S={0,1}ⁿ. On the other hand, I still don't know whether CSoph(x) can ever be larger than NSoph_c(x) (only that, if so, it's never more than a factor of 2 larger). And I'd still be extremely interested if anyone could answer that question.

Can you cover the Boolean cube {0,1}^n with O(1) Hamming-balls each of radius n/2-c*sqrt(n)?

2012-06-18T12:18:21Z

(where c>0 and the balls need not be disjoint?)

This is an embarrassingly simple question, yet somehow I couldn't find an answer (not even, "this is a well-known open problem") after spending some time googling the literature on covering codes.

A simple probabilistic argument shows that you can cover the Boolean cube with O(n) Hamming balls of radius $n/2-c\sqrt n$ each, for any $c>0$. My guess would be that you can't do it with (much) fewer---O(1) Hamming balls seems aggressively optimistic---but I don't know if it's known how to prove that.

(In the language of coding theory, I want to know whether $K_2(n,n/2-c\sqrt n)$, the minimum size of a binary covering code with radius $n/2-c\sqrt n$, can be upper-bounded by a constant depending only on c, not on n, at least for some c>0.)

A Kakeya-like problem: must a union of annuli fill the plane?

2012-10-01T01:32:49Z

Let $S$ be a subset of $\mathbb{R}^2$ with the following property. For all $x \in \mathbb{R}^2$ and $\varepsilon \gt 0$, there exists a nontrivial interval $[a,b] \subseteq [1-\varepsilon,1]$, such that $S$ contains all circles centered at $x$ whose radius is in $[a,b]$. Then my question is:

Can the complement of $S$ have positive Lebesgue measure?

Update: Thanks so much to Terry Tao for sketching an answer to the above question! Alas, on further reflection, I realized the condition "there exists a nontrivial interval $[a,b] \subseteq [1-\varepsilon,1]$ such that $S$ contains all circles centered at $x$ whose radius is in $[a,b]$" was a bit stronger than I intended. What if we only know that, for all $x \in \mathbb{R}^2$ and $\varepsilon \gt 0$, the set $S$ contains a set of circles, centered at $x$, that has positive Lebesgue measure within the annulus $ { y : | y-x | \in [1-\varepsilon,1] }$? (But the set of radii could, for example, be a fat Cantor set, which contains no nontrivial intervals?) Or, even weaker, what if we only know (as in my comment below) that for all $x \in \mathbb{R}^2$ and $\varepsilon \gt 0$, the set $S$ contains a circle centered at $x$ whose radius is between $1-\varepsilon$ and $1$? Is that already enough to force $S$ to have full measure?

This question could be seen as another variant of the Kakeya/Besicovitch problem in the plane. We know, from Besicovitch, that a subset of the plane can have measure zero, yet still contain a translate of every unit line segment. From that, I think it follows that a Lebesgue-measurable subset $S$ of the plane can have arbitrarily-small positive measure, yet still, for every unit line segment $L$ and every $\varepsilon \gt 0$, contain all the horizontal translates of $L$ by distances in $[a,b]$, for some nontrivial interval $[a,b] \subseteq [0,\varepsilon]$. (For example, let $S$ contain all the translates of the Besicovitch set by distances that are most $\delta 2^{-b}$ from the $b^{th}$ rational number in some ordering, for arbitrarily-small $\delta \gt 0$.) If this works, then certainly the complement of $S$ can have positive (in fact, arbitrarily large) Lebesgue measure.

On the other hand, Marstrand (sorry, behind a paywall) proved that, if a subset $S \subseteq \mathbb{R}^2$ contains a circle centered about $x$ for every $x \in \mathbb{R}^2$, then $S$ must have positive Lebesgue measure. So the situation might be interestingly different for circles than for lines.

Answer by Scott Aaronson for What are some examples of ingenious, unexpected constructions?

2012-08-25T02:43:37Z

One of my favorite "simple ingenious constructions" in theoretical computer science from the past few decades is Barak et al.'s construction of a computer program that can never be "obfuscated": that is, for which having the code of the program is always more useful than just being able to run the program as a black box.

Such a program is constructed as follows. First, choose three "secret" n-bit strings a,b,c uniformly at random (I'll assume they're all nonzero). Then consider a program P with the following behavior:

P(0,x) = b if x=a, or 0ⁿ otherwise

P(1,<Q>) = c if Q(0,a)=b, or 0ⁿ otherwise (where Q is some other program and <Q> is its code)

Now suppose you want to learn the secret string c. If all you can do is feed various inputs to P and observe the outputs, then it's not hard to see that the best you can possibly do is "brute-force search": on average, you'll have to try ~2ⁿ inputs to P before you see any output other than 0ⁿ. By contrast, if someone gives you the actual code for P, then no matter how badly they've "obfuscated" that code, you can always learn c with just a single access. The trick, much like in Turing's original proof of the unsolvability of the halting program, is to feed P its own code as input:

P(1,<P>) = c.

Answer by Scott Aaronson for Saying things rapidly about integer factorisations

2012-08-05T19:56:32Z

An expert on computational number theory will be able to provide much, much more detail than I can, but the short answer is that as far as anyone knows, primality-testing is the rare exception, and almost all of these problems are hard (for a classical computer)! That is, the detailed properties of the prime factorization, like whether there are more than two prime factors, whether there's a repeated factor, etc., are not known to be in P and are generally believed to have the same order of difficulty as factoring itself (even where explicit reductions aren't known, as in most cases they aren't). For more details, you might start with the book Algorithmic Number Theory by Bach and Shallit.

(Note: There are, of course, a few easy ones, like testing whether N is a prime power! But I wonder if there's some general conjecture to the effect that no property of the prime factorization is in P, unless the property is "degenerate" in such-and-such a sense.)

Answer by Scott Aaronson for Do all uncountable sets contain elements with infinite Kolmogorov complexity?

2012-08-01T15:07:47Z

Contrary to what some of the commenters said, there's no great difficulty in generalizing Kolmogorov complexity to infinite strings. For example, given a language L⊆{0,1}^*, we could let K(L) be the length of the shortest program that decides L, or K(L)=∞ if L is undecidable. (Or we could also talk about programs that recognize L, in which case even the language HALT would have a finite complexity.)

In either case, the OP's intuition is essentially correct: if a set S of languages is uncountable, then since there are only countably many decidable or recognizable languages, clearly there must exist a language L∈S such that K(L)=∞.

Answer by Scott Aaronson for Blackbox Theorems

2012-06-18T17:10:21Z

In theoretical computer science, possibly the best example is the PCP Theorem: it's used all over the place, from cryptography to quantum computing, yet very few of us understand the details (especially for the strong, "modern" versions of it).

Answer by Scott Aaronson for "psi-epistemic theories" in 3 or more dimensions

2012-05-02T08:43:53Z

Since George Lowther seems to have a lot of late nights, I decided to express my gratitude to him by writing up his lovely answer myself and thereby saving him the trouble.

The answer to my (and Lewis et al.'s) question is that yes, maximally-nontrivial ψ-epistemic theories do exist for every finite dimension $d$.

The first realization is that we can "mix" small ε-balls around any two non-orthogonal vectors.

Lemma 1: Given any two non-orthogonal unit vectors $\psi,\phi \in \mathbb{C}^d$, there exists a ψ-epistemic theory $T = T(\psi,\phi)$ such that $Supp(D_{\psi})$ and $Supp(D_{\phi})$ have nonempty intersection. Moreover, for this $T$, there exists an $\epsilon \gt 0$ (for example, $\epsilon = |\psi^{*} \phi|/2d$) such that $Supp(D_{\psi'})$ and $Supp(D_{\phi'})$ have nonempty intersection for all $\psi',\phi'$ such that $||\psi - \psi'||,||\phi - \phi'||\lt \epsilon$.

Proof: Our ontic state space will be $\Lambda = H_{d} \times [0,1]$. Given an orthonormal basis $M=(v_1,...,v_d)$, first sort the $v_i$'s in decreasing order of $min(|v_{i}^{∗}\psi|,|v_{i}^{∗}\phi|)$. Then the outcome of measurement M on ontic state $(w,p)\in \Lambda$ will equal the smallest positive integer $i$ such that

$|v_1^* w|^2+...+|v_{i−1}^*w|^2 \le p \le |v_1^* w|^2+...+|v_i^*w|^2$.

In other words, $f((w,p),M,i)$ will equal $1$ if $i$ satisfies the above and no $j \lt i$ does, and $0$ otherwise. For now, assume that $D_{w}$ is simply the uniform distribution over all states $(w,p)$ with $p \in [0,1]$. It is easy to check that this yields a valid ψ-epistemic theory, albeit so far a trivial one.

Since $|\psi^{*} \phi|\gt 0$, I claim that there exists an $\epsilon \gt 0$ such that for all orthonormal bases $M=(v_1,...,v_d)$, there exists an $i$ such that $|v_{i}^{∗}\psi|\ge \epsilon$ and $|v_{i}^{∗}\phi|\ge \epsilon$. Indeed, by the triangle inequality, setting $\epsilon := |\psi^{*} \phi| / d$ will work.

Now, the above means that, for all measurements $M$ and all $p \in [0,\epsilon]$, the outcome is always $i=1$ when $M$ is applied to either of the ontic states $(\psi,p)$ or $(\phi,p)$. Following Lewis et al., this implies that we can "mix" the corresponding distributions $D_{\psi}$ and $D_{\phi}$---i.e., have them intersect each other in the region $p \in [0,\epsilon]$---without affecting any outcome of any measurement $M$.

Furthermore, suppose $\psi'$ and $\phi'$ are $\epsilon /2$-close to $\psi$ and $\phi$ respectively, in some standard metric such as trace distance. Then by continuity, we can similarly mix the distributions $D_{\psi'}$ and $D_{\phi'}$---i.e., have them intersect each other in the region $p\in [0,\epsilon /2]$---without affecting any measurement outcome. (One subtlety is that, as we vary $M$, the sorting procedure can make $v_1$ "jump" discontinuously from one basis vector of $M$ to another. However, this jumping is not a problem, since it depends only on the fixed vectors $\psi$ and $\phi$, not on $\psi'$ or $\phi'$. So it happens the same way everywhere in the $\epsilon /2$-balls.) QED

The second realization is that we can take "convex combinations" of ψ-epistemic theories. Given two ψ-epistemic theories $T=(\Lambda,D,f)$ and $T'=(\Lambda',D',f')$ (where $D,D'$ are the functions that map vectors $\psi \in H^d$ onto ontic distributions), and a constant $c \in (0,1)$, define the new theory $c T + (1-c)T' =(\Lambda_c,D_c,f_c)$ as follows:

$\Lambda_c := \Lambda \cup \Lambda'$.
$D_c := c D + (1-c) D'$.
$f_c : \Lambda_c \rightarrow [0,1]$ equals $f$ on $\Lambda$ and $f'$ on $\Lambda'$.

Lemma 2: $c T + (1-c)T'$ is a ψ-epistemic theory. Furthermore, if $T$ mixes the ontic distributions of two vectors $\psi$ and $\phi$, and $T'$ mixes the ontic distributions of two other vectors $\psi'$ and $\phi'$, then $c T + (1-c)T'$ mixes both pairs of distributions.

Proof: Immediate.

Using Lemmas 1 and 2, we now construct a maximally-nontrivial ψ-epistemic theory. Let $T(\psi,\phi)$ be the theory returned by Lemma 1 given vectors $\psi,\phi\in H^d$. Also, for all positive integers $n$, let $A_n$ be a $1/n$-net for $H^d$: that is, a finite subset $A_n \subseteq H^d$ such that for all $v\in H^d$, there exists a $w \in A_n$ satisfying $|| w - v || \lt 1/n$. By making small perturbations, we can easily ensure the property that $u^{*}v \neq 0$ for all $u,v\in A_n$. Then our theory $T$ is defined as follows:

$$T = \frac{6}{\pi^2} \sum_{n=1}^{\infty} \frac{1}{n^2} \left( \frac{1}{|A_n|^2} \sum_{u,v \in A_n} T(u,v) \right). $$

One can check that $T$ mixes the distributions $D_{\psi}$ and $D_{\phi}$ for all non-orthogonal $\psi$ and $\phi$.

Comment: As often in math, I'd say the true value of knowing this answer is that it points us toward the questions we (or rather Lewis et al.) "really" meant to ask! In the above construction, the overlap between $D_{\psi}$ and $D_{\phi}$ is indeed nonzero for any non-orthogonal $\psi,\phi$, but the amount of overlap falls off (by my crude estimate) as $ ( |\psi^{*} \phi| / d) ^{ \Theta(d) } $ .

A skeptic of ψ-epistemic theories might argue that for large $d$ (and of course, $d$ can be huge in quantum mechanics), such an overlap is physically irrelevant. So one obvious followup question is how large the overlap can be---for example, whether it can fall off only as $(|\psi^{*} \phi| / d)^{O(1)}$. I'd better stop here, though, since I know MO is not for open-ended research discussions. The question, as I stated it, has been answered.

The "sensitivity" of 2-colorings of the d-dimensional integer lattice

2010-07-11T23:48:03Z

Consider the $d$-dimensional integer lattice, $Z^d$. Call two points in $Z^d$ "neighbors" if their Euclidean distance is 1 (i.e., if they differ by 1 on exactly one coordinate).

Let $C$ be a two-coloring of $Z^d$, which makes each point either red or blue. We'll assume $C$ has the following "nontriviality" property: the origin is colored red, but on each of the $d$ axes through the origin, there's a point on that axis that's colored blue.

Let the "sensitivity" of a point $x$ with respect to $C$, or $s_x(C)$, be the number of $x$'s neighbors that are colored differently from $x$. Then let $s(C) = \max_{x \in Z^d} s_x(C)$.

QUESTION: Can you give me any decent lower bound on $s(C)$ in terms of $d$? For example, that $s(C) \ge k \sqrt{d}$ for some constant $k > 0$?

REMARK 1: If you prove a lower bound of the form $k d^l$ (for constants $k,l > 0$), then you'll have solved an old open problem in the study of Boolean functions, namely the "sensitivity versus block sensitivity" problem (posed by Noam Nisan in 1991). But please don't let that discourage you! My variant feels more approachable, and maybe something is even already known about it.

(I'll be happy to supply full details of the reduction on request. But here's the basic idea: let $f : \lbrace 0,1 \rbrace ^n \rightarrow \lbrace 0,1 \rbrace$ be a Boolean function such that the block sensitivity $bs(f)$ is much much larger than the sensitivity $s(f)$. Then there must be an input $x$ of $f$ that has $bs(f)$ disjoint sensitive blocks. Let $d=bs(f)$. Then we can construct a two-coloring of $Z^d$ with the properties listed above, and such that $s(C) \le 2 s(f)$ where $s(f)$ is the sensitivity of $f$. The input $x$ gets mapped to the origin of $Z^d$, while each of the $d$ sensitive blocks of $x$ gets mapped to one of the axes of $Z^d$. To map a Boolean assignment to an integer, in a way that preserves the sensitivity, we use the Gray Code. Finally, we color each point $y \in Z^d$ either red or blue, depending on whether $f(x)$ is 0 or 1 for the corresponding Boolean point $x$.)

REMARK 2: I can give an example of a coloring with $s(C) = O(\sqrt{d})$, meaning that $s(C) \ge k \sqrt{d}$ really is the best lower bound one can hope for. This coloring can be obtained by starting from "Rubinstein's function" -- a Boolean function $f : \lbrace 0,1 \rbrace ^n \rightarrow \lbrace 0,1 \rbrace$ with $bs(f) = n/2$ and $s(f) = 2 \sqrt{n}$ -- and then applying the reduction sketched in Remark 1.

(For those who are interested, let me now go ahead and describe a coloring with $s(C) = O( \sqrt{d} )$ explicitly. Assume for simplicity that $d$ is a perfect square. Partition the $d$ coordinates of $x$ into $\sqrt{d}$ "blocks" of $\sqrt{d}$ coordinates each. Then we'll color $x$ blue, if and only if at least one of the blocks has a single coordinate equal to $2$ and all other coordinates equal to $0$. I'll leave it as an exercise for you to verify that $s(C) = 2 \sqrt{d}$.)

Note: I edited the above paragraph a little, to simplify the construction and insert a missing factor of 2.

REMARK 3: At the moment, I don't even have a proof that $s(C)$ has to grow with $d$ (!!). But I suspect at least $s(C) \ge k \log d$ ought to be doable.

EDIT: Sorry to switch notations in the middle of the game, but I have a better one if you want to talk about low dimensions (per domotorp's question below)! Let's let $r_x(C)$ be the number of axes (up/down, left/right, etc.) along which $x$ has a neighbor that's colored differently than $x$ is. Then let $r(C) = \max_x r_x(C)$. Clearly $r(C) \le s(C) \le 2r(C)$ for all $C$.

In fact, something even stronger than that is true: given any coloring $C$, one can create a new coloring C' that satisfies $s(C')=r(C)$, by simply "blowing up" each point $x$ into a cube of $2^d$ points, which are all colored the same way $x$ was colored in $C$. The nontriviality and sensitivity properties will clearly be preserved; all this transformation does is to eliminate the problem of a point having two differently-colored neighbors along the same axis. So without loss of generality, we can shift attention to $r(C)$.

Now let $r_d = \min_C r(C)$ over all nontrivial colorings $C$ of $Z^d$.

Then here's what I know:

$r_1 = 1$

$r_2 = 2$

$r_3 = 2$

$r_4 = 2$

$r_5 \in \lbrace 2,3 \rbrace$

UPDATE: I created an image that shows an explicit coloring of $Z^3$ that satisfies both the nontriviality condition and $r(C)=2$. (That is, from every point, you can change color by moving along at most 2 different axes.) As explained above, this can easily be converted into a coloring with $s(C)=2$ as well.

domotorp is right that proving $r_5=3$ could be a great start...

Pi1-sentence independent of ZF, ZF+Con(ZF), ZF+Con(ZF)+Con(ZF+Con(ZF)), etc.?

2011-06-08T06:19:22Z

Let

ZF₁ = ZF,

ZF_k+1 = ZF + the assumption that ZF₁,...,ZF_k are consistent,

ZF_ω = ZF + the assumption that ZF_k is consistent for every positive integer k,

... and similarly define ZF_α for every computable ordinal α.

Then a commenter on my blog asked a question that boils down to the following: can we give an example of a Π₁-sentence (i.e., a universally-quantified sentence about integers) that's provably independent of ZF_α for every computable ordinal α? (AC and CH don't count, since they're not Π₁-sentences.)

An equivalent question is whether, for every positive integer k, there exists a computable ordinal α such that the value of BB(k) (the k^th Busy Beaver number) is provable in ZF_α.

I apologize if I'm overlooking something obvious.

Update: I'm grateful to François Dorais and the other answerers for pointing out the ambiguity in even defining ZF_α, as well as the fact that this issue was investigated in Turing's thesis. Emil Jeřábek writes: "Basically, the executive summary is that once you manage to make the question sufficiently formal to make sense, then every true Π₁ formula follows from some iterated consistency statement."

So, I now have a followup question: given a positive integer k, can we say something concrete about which iterated consistency statements suffice to prove the halting or non-halting of every k-state Turing machine? (For example, would it suffice to use ZF_α for some encoding of α, where α is the largest computable ordinal that can be defined using a k-state Turing machine?)

Answer by Scott Aaronson for nontrivial theorems with trivial proofs

2011-05-25T03:56:43Z

The union bound:

Pr[A or B] ≤ Pr[A] + Pr[B]

for any two events A and B, regardless of their dependence. This is probably the single most trivial-to-prove theorem I know whose explicit formulation I've actually found useful. (Indeed, more than useful: indispensable! There's a huge number of problems in theoretical computer science and combinatorics that are much easier for a beginner to solve if you give the two-word hint "union bound," than if you don't. And one stops being a beginner at roughly the point when one internalizes the "union bound" hint, and starts applying it to every problem one encounters... :-) )

"Closed-form" functions with half-exponential growth

2010-11-09T18:51:19Z

Let's call a function f:N→N half-exponential if there exist constants 1<c<d such that for all sufficiently large n,

cⁿ < f(f(n)) < dⁿ.

Then my question is this: can we prove that no half-exponential function can be expressed by composition of the operations +, -, *, /, exp, and log, together with arbitrary real constants?

There have been at least two previous MO threads about the fascinating topic of half-exponential functions: see here and here. See also the comments on an old blog post of mine. However, unless I'm mistaken, none of these threads answer the question above. (The best I was able to prove was that no half-exponential function can be expressed by monotone compositions of the operations +, *, exp, and log.)

To clarify what I'm asking for: the answers to the previous MO questions already sketched arguments that if we want (for example) f(f(x))=e^x, or f(f(x))=e^x-1, then f can't even be analytic, let alone having a closed form in terms of basic arithmetic operations, exponentials, and logs.

By contrast, I don't care about the precise form of f(f(x)): all that matters for me is that f(f(x)) has an asymptotically exponential growth rate. I want to know: is that hypothesis already enough to rule out a closed form for f?

"Simpler" statements equivalent to Con(PA) or Con(ZFC)?

2011-04-24T20:16:29Z

Given any reasonable formal system F (e.g., Peano Arithmetic or ZFC), we all know that one can construct a Turing machine that runs forever iff F is consistent, by enumerating the theorems of F and halting if it ever proves 0=1.

However, what interests me here is that the "obvious" such Turing machine will be an extremely complicated one. Besides the axioms of F, it will need to encode the symbols and inference rules of first-order logic, which (among other things) presumably requires writing a parser for context-free expressions. If you actually wrote the Turing machine out, it might have millions of states! Even in a high-level programming language, the task of writing a program that enumerates all the theorems of ZFC is not one that I'd casually give as homework.

Notice that this situation stands in striking contrast to that of universal Turing machines, which we've known since the 1960s how to construct with an extremely small number of states (albeit usually at the price of a complicated input encoding). It also contrasts with the observation that very small Turing machines can already exhibit "complicated, unpredictable" behavior: for example, the 5th Busy Beaver number is still unknown, and it seems like a plausible guess that the values of (say) BB(10) or BB(20) are independent of ZFC.

Thus my question:

Is any "qualitatively simpler" class of computer programs known, which can be proved to run forever iff ZFC is consistent? Here, by "qualitatively simpler," I mean doing something that looks much more straightforward than enumerating all the first-order consequences of the ZFC axioms, but that can nevertheless be proved by some nontrivial theorem to be equivalent to such an enumeration. Feel free to replace ZFC by ZF, PA, or any other system to which Gödel's Theorem applies if it makes a difference.

This question is clearly related to the well-known goal of finding "natural" or "combinatorial" statements that are provably independent of PA of ZFC, but it's not identical. For one thing, I don't demand that your statement have any independent mathematical interest---just that the computer program corresponding to your statement be easier to write than a program that enumerates all ZFC-theorems!

One concrete goal would be to find the smallest n for which you can prove that the value of BB(n) (the nth Busy Beaver number) is independent of ZFC. (It's clear that BB(n) is independent of ZFC for all n≥n₀, where n₀ is the number of states in a Turing machine that enumerates all ZFC-proofs and halts if it proves 0=1.)

As a first step, though, I'll be delighted to learn of any theorem that simplifies the task of writing proof-enumerating programs. (Even if the programs are still expressed in a high-level formalism, and are still horrendously complicated when compiled down to Turing machines.)

Answer by Scott Aaronson for Philosophical Question related to Largest Known Primes

2011-04-25T20:24:47Z

First of all, I don't think the idea that "knowing a prime requires knowing its decimal expansion" accords well with mathematical practice. Unless I'm mistaken, the largest known primes are all Mersenne primes, and (for good reason!) are almost always written in the form p=2^k-1, not by their decimal expansions. Granted, the currently-known Mersennes are small enough that one could calculate their decimal expansions in Maple or Mathematica, if for some reason one wanted to. But even if that weren't the case (say, if k had 10,000 digits), I'd still be perfectly happy to describe p=2^k-1 as a "known prime," provided someone knew both k and a proof that p was prime.

On the other hand, similar to what you suggested with your "NextPrime" function, what about

p := the 10^{10^10000}th prime number ?

Certainly p exists, and one can even write a program to output it. But is p therefore "known"? Saying so seems to stretch the meaning of the word "known" beyond recognition.

Trying to arrive at some principled criterion that separates the two examples above, here's the best that I came up with:

An n-digit prime number p is "known" if there's a known algorithm to output the digits of p that runs in poly(n) time (together with a proof that the algorithm does indeed output a prime number and halt in poly(n) steps).

(Strictly speaking, the above definition covers "known-ness" for infinite families of primes, rather than individual primes -- since once you fix p, you can always output it in O(1) time. But this is a standard caveat.)

As far as I can see, the above definition correctly captures the intuition that a prime p is "known" if we know a closed-form formula for p (which can be evaluated in polynomial time), but not if we merely know a non-constructive definition of p (for which it takes exponential time to determine which p we're talking about).

A very interesting test case for my definition is

p := the first prime larger than 10^{10^10000}.

According to my definition, the above prime is currently "unknown", but will become "known" if someone proves the conjecture that the spacing between two consecutive n-digit primes never exceeds q(n) for some fixed polynomial q.

If you accept my definition, then a "function that always generates primes" almost certainly would trivialize largest-prime contests, since presumably it would give a deterministic way to generate n-digit primes in n^O(1) time, for n as large as you like (which is not something that we currently have).

Now, maybe there are cases where my definition fails to match up with "intuitive knowability" -- if so, I look forward to seeing counterexamples!

Succinctly naming big numbers: ZFC versus Busy-Beaver

2010-08-06T00:57:01Z

Years ago, I wrote an essay called Who Can Name the Bigger Number?, which posed the following challenge:

You have fifteen seconds. Using standard math notation, English words, or both, name a single whole number---not an infinity---on a blank index card. Be precise enough for any reasonable modern mathematician to determine exactly what number you’ve named, by consulting only your card and, if necessary, the published literature.

The essay went on to discuss systems for naming increasingly huge numbers concisely---including the Ackermann function, the Busy Beaver function, and super-recursive generalizations of Busy Beaver.

Recently (via Eliezer Yudkowsky), the claim has come to my attention that there are ways to concisely define vastly bigger numbers than even the super-recursive Busy Beaver numbers, using set theory. (See for example this page by Agustín Rayo, which proposes a definition based on second-order set theory.) However, whether these definitions work or not seems to hinge on some very delicate issues about definability in set theory.

So, I have a specific question about fast-growing integer sequences that are "well-defined," as I understand the term. But first, let me be clear about some ground rules: I'm certainly fine with integer sequences whose values are unprovable from (say) the axioms of ZFC, as sufficiently large Busy Beaver numbers are. Crucially, though, the values of the sequence must not depend on any controversial beliefs about transfinite sets. So for example, the "definition"

n := 1 if CH is true, 2 if CH is false

makes sense in the language of ZFC, but it wouldn't be acceptable for my purposes. Even a formalist---someone who sees CH, AC, large-cardinal axioms, etc. as having no definite truth-values---should be able to agree that we've picked out a specific positive integer.

Let me now describe the biggest numbers I know how to name, consistent with the above rules, and then maybe you can blow my numbers out of the water.

Given a Turing machine M, let S(M) be the number of steps made by M on an initially blank tape, or 0 if M runs forever. Then recall that BB(n), or the n^th Busy Beaver number, is defined as the maximum of S(M) over all n-state Turing machines M. BB(n) is easily seen to grow faster than any computable function. But for our purposes, BB(n) is puny! So let's define $BB_1(n)$ to be the analogue of BB(n), for Turing machines equipped with an oracle that computes $BB_0(n):=BB(n)$. Likewise, for all positive integers k, let $BB_k$ be the Busy Beaver function for Turing machines that are equipped with an oracle for $BB_{k-1}$. It's not hard to see that $BB_k$ grows faster than any function computable with a $BB_{k-1}$ oracle.

But we can go further: let $BB_{\omega}$ be the Busy Beaver function for Turing machines equipped with an oracle that computes $BB_k(n)$ given (k,n) as input. Then let $BB_{\omega+1}$ be the Busy Beaver function for Turing machines with an oracle for $BB_{\omega}$, and so on. It's clear that we can continue in this way through all the computable ordinals --- i.e. those countable ordinals $\alpha$ for which there exists a way to describe any $\beta < \alpha$ using a finite number of symbols, together with a Turing machine that decides whether $\beta < \beta'$ given the descriptions of each.

Next, let $\alpha(n)$ be the largest computable ordinal that can defined (in the sense above) by a Turing machine with at most n states. Then we can define

$f(n) := BB_{\alpha(n)}(n),$

which grows faster than $BB_{\alpha}$ for any fixed computable ordinal $\alpha$.

A different way to define huge numbers is the following. Given a predicate $\phi$ in the language of ZFC, with one free variable, say that $\phi$ "defines" a positive integer m if m is the unique positive integer that satisfies $\phi$, and the value of $m$ is the same in all models of ZFC.

Then let z(n) be the largest number defined by any predicate with n symbols or fewer.

One question that immediately arises is the relationship between f(n) and z(n). I don't think it's hard to show that there exists a constant c such that $f(n) < z(n+c)$ for all n (please correct me if I'm wrong!) But what about the other direction? Does z(n) grow faster than any function definable in terms of Turing machines, or can we find a function similar to f(n) that dominates z(n)? And are there other ways of specifying big numbers that dominate them both?

Update (8/5): After reading the first few comments, it occurred to me that the motivation for this question might not make sense to you, if you don't recognize a distinction between those mathematical questions that are "ultimately about finite processes" (for example: whether a given Turing machine halts or doesn't halt; the values of the super-recursive Busy Beaver numbers; most other mathematical questions), and those that aren't (for example: CH, AC, the existence of large cardinals). The former I regard as having a definite answer, independently of the answer's provability in any formal system such as ZFC. (If you doubt that there's a fact of the matter about whether a given Turing machine halts or runs forever, then you might as well also doubt that there's a fact of the matter about whether a given statement is or isn't provable in ZFC!) For questions like CH and AC, by contrast, one can debate whether it even means anything to discuss their truth independently of their provability in some formal system.

In this question, I'm asking about integer sequences that are "ultimately definable in terms of finite processes," and which one can therefore regard as taking definite values, independently of one's beliefs about set-theoretic questions. Of course, "ultimately definable in terms of finite processes" is a vague term. But one can list many statements that certainly satisfy the criterion (for example: anything expressible in terms of Turing machines and whether they halt), and others that certainly don't (for example: CH and AC). A large part of what I'm asking here is just how far the boundaries of the "definable in terms of finite processes" extend!

Yes, it's possible that my question could degenerate into philosophical disagreements. But a priori, it's also possible that someone can give a sequence that everyone agrees is "definable in terms of finite processes," and that blows my f(n) and z(n) out of the water. The latter would constitute a completely satisfying answer to the question.

Update (8/6): It's now been demonstrated to my satisfaction that z (as I defined it) is blown out of the water by f. The reason is that z is defined by quantifying over all models of ZFC. But by the Completeness Theorem, this means that z can also be defined "syntactically," in terms of provability in ZFC. In particular, we can compute z using an oracle for the $BB_1$ function (or possibly even the BB function?), by defining a Turing machine that enumerates all positive integers m as well as all ZFC-proofs that the predicate $\phi$ picks out m.

So thanks -- I didn't want to prejudice things, but this is actually the answer I was hoping for! If it wasn't clear already, I'm interested in big numbers not so much for their own sake, but as a concrete way of comparing the expressive power of different notational systems. And I have a strong intuition that Turing machines are a "maximally expressive" notational system, at least for those numbers that meet my criterion of being "ultimately defined in terms of finite processes" (so in particular, independent of the truth or falsehood of statements like CH). If one could use ZFC to define integer sequences that blew my sequence f(n) out of the water (and that did so in a model-independent way), that would be a serious challenge to my intuition.

So let me refocus the question: is my intuition correct, or is there some more clever way to use ZFC to define an integer sequence that blows f(n) out of the water?

Actually, a proposal for using ZFC to at least match the growth rate of f now occurs to me. Recall that we defined the sequence z by maximizing over all models M of ZFC. However, this definition ran into problems, related to the "self-hating models" that contain nonstandard integers encoding proofs of Not(Con(ZFC)). So instead, given a model M of ZFC and a positive integer k, let's call M "k-true" if every $\Pi_k$ arithmetical sentence S is true in M if and only if S is semantically true (i.e., true for the standard integers). (Here a $\Pi_k$ arithmetical sentence means a sentence with k alternating quantifiers, all of which range only over integers.)

Now, let's define the function

$z_k(n)$

exactly the same way as z(n), except that now we only take the maximum over those models M of ZFC that are k-true.

This remains to be proved, but my guess is that $z_k(n)$ should grow more-or-less like $BB_{k+c}(n)$, for some constant c. Then, to get faster-growing sequences, one could strengthen the k-truth requirement, to require the models of ZFC being maximized over to agree with what's semantically true, even for sentences about integers that are defined using various computable ordinals. But by these sorts of devices, it seems clear that one can match f but not blow it out of the water---and indeed, it seems simpler just to forget ZFC and talk directly about Turing machines.

Anti-concentration bound for permanents of Gaussian matrices?

2010-11-12T13:01:32Z

In a recent paper with Alex Arkhipov on "The Computational Complexity of Linear Optics," we needed to assume a reasonable-sounding probabilistic conjecture: namely, that the permanent of a matrix of i.i.d. Gaussian entries is "not too concentrated around 0." Here's a formal statement of our conjecture:

There exists a polynomial $p$ such that for all $n$ and $\delta>0$, $\Pr_{X\sim\mathcal{N}\left( 0,1\right) _{\mathbb{C}}^{n\times n}}\left[\left\vert \operatorname*{Per}\left( X\right) \right\vert \leq \frac{\sqrt{n!}}{p\left( n/\delta\right) }\right] \leq \delta. $

This conjecture seems interesting even apart from our application, so I wanted to bring it to people's attention -- maybe there's a simple/known proof that we're missing!

Here's what we do know:

The expectation of Per(X) is of course 0 (by symmetry), while the standard deviation is $\sqrt{n!}$. Thus, our conjecture basically says that "Per(X) is polynomially smaller than its standard deviation only a 1/poly(n) fraction of the time."
Recently, Terry Tao and Van Vu proved a wonderful anti-concentration bound for the permanents of Bernoulli matrices, which can be stated as follows: for all $\varepsilon > 0$ and sufficiently large n, $\Pr_{X\in\left\{ -1,1\right\} ^{n\times n}}\left[ \left\vert \operatorname*{Per}\left( X\right) \right\vert \leq \frac{\sqrt{n!}% }{n^{\varepsilon n}}\right] \leq \frac{1}{n^{0.1}}.$ Unfortunately, their result falls short of what we need in three respects. First, it's for Bernoulli matrices rather than Gaussian matrices. (Though of course, the Gaussian case might well be easier than the Bernoulli case, which is our main reason for optimism!) Second, and most important, Tao and Vu only prove that Per(X) is at least a 1/n^εn fraction of its standard deviation with high probability, whereas we need that it's at least a 1/poly(n) fraction. Third, they upper-bound the probability of a "bad event" by 1/n^0.1, whereas we'd like to upper-bound it by 1/p(n) for any polynomial p.
The numerical evidence that we've obtained is strongly consistent with our conjecture being true (see figure below).
We can prove that our conjecture holds with the determinant in place of the permanent. To do so, we use the fact that if X is Gaussian, then because of the rotational invariance of the Gaussian measure, there's an explicit formula for all the moments of Det(X) -- even the fractional and inverse moments.
One might wonder if we can also calculate the higher moments of Per(X), and use that to prove our conjecture. Indeed, we can show that $\operatorname*{E}_{X\sim\mathcal{N}\left( 0,1\right) _{\mathbb{C}}^{n\times n}}\left[ \left\vert \operatorname*{Per}\left( X\right)\right\vert ^{4}\right] =\left( n!\right) ^{2}\left( n+1\right)$, which then implies the following weak anti-concentration bound: for all β<1, $\Pr_{X\sim\mathcal{N}\left( 0,1\right) _{\mathbb{C}}^{n\times n}}\left[ \left\vert \operatorname*{Per}\left( X\right) \right\vert \geq \beta\sqrt{n!}\right] \geq\frac{\left( 1-\beta^{2}\right) ^{2}}{n+1}$. Unfortunately, computing the 6th, 8th, and higher moments seems difficult.

See section 8 of our paper for the proofs of 4 and 5.

Short of proving our anti-concentration conjecture, here are two easier questions whose answers would also greatly interest us:

Can we at least reprove Tao and Vu's bound for Gaussian matrices rather than Bernoulli matrices? In their paper, Tao and Vu say their result holds for "virtually any (not too degenerate) discrete distribution." I don't think the Gaussian distribution would present serious new difficulties, but I'm not sure.
Does the pdf of Per(X) diverge at the origin? (We don't even know the answer to that question in the case of Det(X).) I don't know of any formal implications between this question and the anti-concentration question, but it would be great to answer anyway.

Answer by Scott Aaronson for Are there any interesting examples of random NP-complete problems?

2010-07-12T21:17:10Z

Important update (Oct. 6, 2010): I'm pleased to say that I gave the "random 3SAT" problem in the OP to Allan Sly, and he came up with a simple NP-hardness proof. I've posted the proof to my blog with Allan's kind permission.

Sorry that I'm extraordinarily late to this discussion!

Regarding Tim's specific question: if we stick enough clauses in our instance that every 3SAT instance (satisfiable or not) occurs as a subformula with high probability, then certainly the resulting problem will be NP-hard. Indeed, it would suffice to have a large enough set of clauses that we can always find a subformula that can serve as the output of one of the standard reductions. On the other hand, I don't know of any techniques for proving NP-hardness that are tailored to the setting Tim has in mind -- it's a terrific question!

Since I can't answer the question he asked, let me talk for a while about a question he didn't ask (but that I, and apparently some of the commenters, initially thought he did). Namely, what's known about the general issue of whether there are NP-complete problems that one can show are NP-hard on average (under some natural distribution over instances)?

(1) The short answer is, it's been one of the great unsolved problems of theoretical computer science for the last 35 years! If there were an NP-complete problem that you could prove was as hard on average as it was on the worst case, that would be a huge step toward constructing a cryptosystem that was NP-hard to break, which is one the holy grails of cryptography.

(2) On the other hand, if you're willing go above NP-complete, we know that certain #P-complete problems (like the Permanent over large finite fields) have worst-case/average-case equivalence. That is to say, it's exactly as hard to compute the permanent of a uniform random matrix as it is to compute the permanent of any matrix, and this can be proven via an explicit (randomized) reduction.

(3) Likewise, if you're willing to go below NP-complete, then there are cryptographic problems, such as shortest lattice vector (mentioned by Rune) and discrete logarithm, that are known to have worst-case/average-case equivalence. Indeed, this property is directly related to why such problems are useful for cryptography in the first place! But alas, it's also related to why they're not believed to be NP-complete. Which brings me to...

(4) We do have some negative results, which suggest that worst-case/average-case equivalence for an NP-complete problem will require very new ideas if it's possible at all. (Harrison was alluding to these results, but he overstated the case a little.) In particular, Feigenbaum and Fortnow showed that, if there's an NP-complete problem that's worst-case/average-case equivalent under randomized, nonadaptive reductions, then the polynomial hierarchy collapses. (Their result was later strengthened by Bogdanov and Trevisan.) There are analogous negative results about basing crytographic one-way functions on an NP-complete problem: for example, Akavia, Goldreich, Goldwasser, and Moshkovitz (erratum). At present, though, none of these results rule out the possibility of a problem being NP-complete on average under the most general kind of reductions: namely, randomized adaptive reductions (where you can decide what to feed the oracle based on its answers to the previous queries).

(5) Everything I said above implicitly assumed that, when we say we want an average-case NP-complete problem, we mean with a distribution over instances that's efficiently samplable. (For example, 3SAT with randomly generated clauses would satisfy that condition, as would almost anything else that arises naturally.) If you allow any distribution at all, then there's a "cheating" way to get average-case NP-completeness. This is Levin's universal distribution U, where each instance x occurs with probability proportional to $2^{-K(x)}$, K(x) being the Kolmogorov complexity of x. In particular, for any fixed polynomial-time Turing machine M, the lexicographically-first instance on which M fails will have a short description (I just gave it), and will therefore occur in U with large probability!

(6) If you're willing to fix a polynomial-time algorithm M, then there's a beautiful result of Gutfreund, Shaltiel, and Ta-Shma that gives an efficiently-samplable distribution over NP-complete problem instances that's hard for M, assuming $NP \nsubseteq BPP$. The basic idea here is simple and surprising: you feed M its own code as input, and ask it to find you an instance on which it itself fails! If it succeeds, then M itself acts as your sampler of hard instances, while if it fails, then the instance you just gave it was the hard instance you wanted!

(7) Finally, what about "natural" distributions, like the uniform distribution over all 3SAT instances with n clauses and m~4.3n variables? For those, alas, we generally don't have any formal hardness results.

Answer by Scott Aaronson for What's known about the relationship about EQP and BQP?

2010-10-01T19:50:26Z

Hi Henry,

One reason why EQP isn't studied more is that it's not even uniquely defined! In particular, which complexity class you get might depend on the specific quantum gates you assume are available. (For BQP, by contrast, the Solovay-Kitaev Theorem assures us that any universal set of quantum gates can approximate any other universal set to within exponentially small error.)

Still, you could forge ahead, fix a particular universal set of gates (say, Hadamard and Toffoli), and study the resulting class EQP.

In that case, it's not hard to construct an oracle relative to which BQP (and even BPP) are not contained in EQP -- for example, just take the MAJORITY function with a promised (1/3,2/3) gap in the Hamming weight. (You can prove that's not in EQP using the polynomial method.) Nor is it hard to construct an oracle relative to which EQP is not contained in BPP (Bernstein and Vazirani's Recursive Fourier Sampling problem, for example).

Outside the oracle world, the main result about EQP I know of is due to Mosca (don't have the reference offhand), who showed that, if you're careful to define EQP with a large enough set of gates, then it contains FACTORING (i.e., Shor's algorithm can be made zero-error). This gives pretty good evidence that EQP (suitably defined) is not contained in BPP.

I would guess that EQP ≠ BQP in the unrelativized world, but I don't have any evidence for that (and of course, it's possible that EQP equals BQP under some definitions but doesn't under others).

Answer by Scott Aaronson for How do we know that P != LINSPACE without knowing if one is a subset of the other?

2010-10-01T16:27:32Z

Suppose by contradiction that P=SPACE(n). Then there exists an algorithm to simulate an n-space Turing machine in (say) n^c time, for some constant c. But this means that there exists an algorithm to simulate an n²-space Turing machine in n^2c time. Therefore SPACE(n²) is also contained in P. So

P = SPACE(n) = SPACE(n²).

But SPACE(n) = SPACE(n²) contradicts the Space Hierarchy Theorem. QED

(Notice that in this proof, we showed neither that P is not contained in SPACE(n), nor that SPACE(n) is not contained in P! We only showed that one or the other must be true, by using the different closure properties of polynomial time and linear space. It's conjectured that P and SPACE(n) are incomparable.)

Answer by Scott Aaronson for What is the easiest randomized algorithm to motivate to the layperson?

2010-09-10T12:35:43Z

Michael, how about approximating the volume of some shape in $\Re^n$ by sampling random points?

This example has the following advantages:

It seems easy enough to explain at a cocktail party (depending, of course, on the guests).
It's used constantly in "real life" (indeed, pretty much any Monte Carlo simulation in physics, etc. could be interpreted as solving this problem).
We don't know how to derandomize it. Indeed, the problem is easily seen to be PromiseBPP-complete (assuming of course that whether a point $x \in \Re^n$ belongs to the shape is decidable in polynomial time).

Answer by Scott Aaronson for What are some applications of other fields to mathematics?

2010-07-25T16:21:02Z

I can think of at least three things that the question might mean, and it would probably help if Steve clarified which ones count for him!

(1) Other fields suggesting new questions for mathematicians to think about, or new conjectures for them to prove. Examples of that sort are ubiquitous, and account for a significant fraction of all of mathematics! (Archimedes, Newton, and Gauss all looked to physics for inspiration; many of the 20th-century greats looked to biology, economics, computer science, etc. Even for those mathematicians who take pride in taking as little inspiration as possible from the physical world, it's arguable how well they succeed at it.)

(2) Other fields helping the process of mathematical research. Computers are an obvious example, but I gather that this sort of application isn't what Steve has in mind.

(3) Other fields leading to new or better proofs, for theorems that mathematicians care about even independently of the other fields. This seems to me like the most interesting interpretation. But it raises an obvious question: if a field is leading to new proofs of important theorems, why shouldn't we call that field mathematics? One way out of this definitional morass is the following: normally, one thinks of mathematics as arranged in a tree, with logic and set theory at the root, "applied" fields like information theory or mathematical physics at the leaves, and everything else (algebra, analysis, geometry, topology) as trunks or branches. Definitions and results from the lower levels get used at the higher levels, but not vice versa. From this perspective, what the question is really asking for is examples of "unexpected inversions," where ideas from higher in the tree (and specifically, from the "applied" leaves) are used to prove theorems lower in the tree.

Such inversions certainly exist, and lots of people probably have favorite examples of them --- so it does seem like great fodder for a "big list" question. At the risk of violating Steve's "no theoretical computer science" rule, here are some of my personal favorites:

(i) Grover's quantum search algorithm immediately implies that Markov's inequality, that

$\max_{x \in [-1,1]} |p'(x)| \leq d^2 \max_{x \in [-1,1]} |p(x)|$

for all degree-d real polynomials p, is tight.

(ii) Kolmogorov complexity is often useful for proving statements that have nothing to do with Turing machines or computability.

(iii) The quantum-mechanical rules for identical bosons immediately imply that |Per(U)|≤1 for every unitary matrix U.

Answer by Scott Aaronson for Is all non-convex optimization heuristic?

2010-07-20T04:12:31Z

In some sense, the fundamental difficulty with non-convex optimization is that you very quickly run up against NP-completeness. If $P\ne NP$, then there's not going to be any efficient, general-purpose method to solve non-convex optimization problems or convert them into convex ones.

Having said that, as Carl wrote, of course there are plenty of interesting things to prove about non-convex optimization, if you're willing to give up on a fast algorithm that always works! For example, approximation guarantees, convergence in mild exponential time...

Answer by Scott Aaronson for Problems known to be in both NP and coNP, but not known to be in P

2010-07-17T20:35:40Z

Under popular derandomization assumptions, the following problems are in $NP\cap coNP$:

Graph Isomorphism and Automorphism (as well as Group Isomorphism, Ring Isomorphism, ...)
Group Membership (e.g., given invertible matrices $A$ and $B_1,...,B_k$, is $A$ in the group generated by $B_1,...,B_k$?)

(More precisely, these problems are known to be in $NP\cap coAM$. $coAM$ is a "close cousin" of $coNP$, and equals the latter under derandomization hypotheses: see this paper by Klivans and van Melkebeek.)

Besides factoring, there are various other number-theoretic problems in $NP\cap coNP$, such as decision versions of Discrete Logarithm (both in $Z_p^*$ and in elliptic curve groups).

If you're willing to allow promise problems (i.e., the algorithm only has to output a correct answer if the input satisfies some property), then there are lots of natural examples of $NP\cap coNP$ problems. A trivial example is, "given two Boolean formulas F and G, and promised that exactly one of them is satisfiable, decide which." A nontrivial example is the Approximate Shortest Vector problem, mentioned previously by Niel. What's rarer are interesting $NP\cap coNP$ problems that don't have a promise (or where the promise is easy to check).

Answer by Scott Aaronson for Intuitive crutches for higher dimensional thinking

2010-07-16T22:21:06Z

Here are some of the crutches I've relied on. (Admittedly, my crutches are probably much more useful for theoretical computer science, combinatorics, and probability than they are for geometry, topology, or physics. On a related note, I personally have a much easier time thinking about $R^n$ than about, say, $R^4$ or $R^5$!)

If you're trying to visualize some 4D phenomenon P, first think of a related 3D phenomenon P', and then imagine yourself as a 2D being who's trying to visualize P'. The advantage is that, unlike with the 4D vs. 3D case, you yourself can easily switch between the 3D and 2D perspectives, and can therefore get a sense of exactly what information is being lost when you drop a dimension. (You could call this the "Flatland trick," after the most famous literary work to rely on it.)
As someone else mentioned, discretize! Instead of thinking about $R^n$, think about the Boolean hypercube $\lbrace 0,1 \rbrace ^n$, which is finite and usually easier to get intuition about. (When working on problems, I often find myself drawing $\lbrace 0,1 \rbrace ^4$ on a sheet of paper by drawing two copies of $\lbrace 0,1 \rbrace ^3$ and then connecting the corresponding vertices.)
Instead of thinking about a subset $S \subseteq R^n$, think about its characteristic function $f : R^n \rightarrow \lbrace 0,1 \rbrace$. I don't know why that trivial perspective switch makes such a big difference, but it does ... maybe because it shifts your attention to the process of computing $f$, and makes you forget about the hopeless task of visualizing S!
One of the central facts about $R^n$ is that, while it has "room" for only $n$ orthogonal vectors, it has room for $\exp(n)$ almost-orthogonal vectors. Internalize that one fact, and so many other properties of $R^n$ (for example, that the $n$-sphere resembles a "ball with spikes sticking out," as someone mentioned before) will suddenly seem non-mysterious. In turn, one way to internalize the fact that $R^n$ has so many almost-orthogonal vectors is to internalize Shannon's theorem that there exist good error-correcting codes.
To get a feel for some high-dimensional object, ask questions about the behavior of a process that takes place on that object. For example: if I drop a ball here, which local minimum will it settle into? How long does this random walk on $\lbrace 0,1 \rbrace ^n$ take to mix?

Answer by Scott Aaronson for Is there a promise version of 3-coloring equivalent to Graph Isomorphism?

2010-07-12T20:15:22Z

Hi Steven,

(1) To start with the "duh" observation, you could define an artificial class, namely "those 3-coloring instances that are obtained by starting from Graph Isomorphism and then applying a standard NP-completeness reduction." That would indeed give you a subclass of 3-coloring instances that are provably polynomially equivalent to graph isomorphism, but I'm guessing it's not what you had in mind. :-)

(2) I can't think of a "natural" subclass of 3-coloring instances that are reducible to graph isomorphism and not as a consequence of being in P. I'd be interested and surprised if there was one -- 3-coloring and GI are both about graphs, but in complexity terms they're extremely different! GI has lots of special group-theoretic structure, which in some sense can't be shared by 3-coloring (or any other NP-complete problem) unless the polynomial hierarchy collapses.

(3) On the other hand, if you're willing to talk about nonuniform algorithms (i.e., algorithms that can take "advice" depending on the input length n), then here's another "duh" observation. Suppose you have a fixed graph G on n vertices, together with a 3-coloring of G. Then you can 3-color any graph G' that happens to be isomorphic to G, provided you can compute an isomorphism between G and G'. Or if you prefer decision problems: given as advice a graph G that's 3-colorable and another graph H that isn't, and also given a decision oracle for GI, you can decide 3-colorability for those graphs that happen to be isomorphic to either G or H.

Sorry the above wasn't more helpful... :-)

Analogue of the Chebyshev polynomials over C?

2009-12-14T21:31:55Z

I've been driven up a wall by the following question: let p be a complex polynomial of degree d. Suppose that |p(z)|≤1 for all z such that |z|=1 and |z-1|≥δ (for some small δ>0). Then what's the best upper bound one can prove on |p(1)|? (I only care about the asymptotic dependence on d and δ, not the constants.)

For the analogous question where p is a degree-d real polynomial such that |p(x)|≤1 for all 0≤x≤1-δ, I know that the right upper bound on |p(1)| is |p(1)|≤exp(d√δ). The extremal example here is p(x)=T_d((1+δ)x), where T_d is the d^th Chebyshev polynomial.

Indeed, by using the Chebyshev polynomial, it's not hard to construct a polynomial p in z as well as its complex conjugate z*, such that

(i) |p(z)|≤1 for all z such that |z|=1 and |z-1|≥δ, and

(ii) p(1) ~ exp(dδ).

One can also show that this is optimal, for polynomials in both z and its complex conjugate.

The question is whether one can get a better upper bound on |p(1)| by exploiting the fact that p is really a polynomial in z. The fastest-growing example I could find has the form p(z)=C_d,δ(1+z)^d. Here, if we choose the constant C_d,δ so that |p(z)|≤1 whenever |z|=1 and |z-1|≥δ, we find that

p(1) ~ exp(dδ²)

For my application, the difference between exp(dδ) and exp(dδ²) is all the difference in the world!

I searched about 6 approximation theory books---and as often the case, they answer every conceivable question except the one I want. If anyone versed in approximation theory can give me a pointer, I'd be incredibly grateful.

Thanks so much! --Scott Aaronson

PS. The question is answered below by David Speyer. For anyone who wants to see explicitly the polynomial implied by David's argument, here it is:

p_d,δ(z) = z^d T_d((z+z^-1)(1+δ)/2+δ),

where T_d is the d^th Chebyshev polynomial.

Comment by Scott Aaronson

2013-05-22T04:43:21Z

However, notice that both my argument and yours only used the assumption that ZF is consistent, nothing more! Admittedly ZF doesn't prove that the reduction works, but ZF does prove the conditional result that the reduction works assuming Con(ZF). And I said at the outset that I was happy to assume even the soundness of ZF!

Comment by Scott Aaronson

2013-05-22T04:38:50Z

Thanks, Joel! Here's my simplification of your argument, avoiding the use of the recursion theorem. Given a TM M, construct a new TM M' that simulates M, but that while it runs, also (in parallel) searches for a proof in ZF that 0=1, and halts if it ever finds one. Meanwhile, if M ever halts, then M' terminates the 0=1 branch and simply runs forever. Then in any case M' runs forever. But if M halts then ZF proves that M' loops, while if M loops then ZF doesn't prove that M' loops (assuming ZF is consistent). So by running PROVEHALT on M', we also decide whether M halts, QED.

Comment by Scott Aaronson

2013-05-22T03:15:52Z

François: Yes, I know that CG is not a set; rather, it's what you call a separation problem and what complexity theorists would call a promise problem (the promise being that M halts). But the notion of Turing-reducibility can be generalized to promise problems in a fairly straightforward way, and once you do that $CG\le_T PROVELOOP$ becomes meaningful. Your last observation, implying that in fact $CG\lt_T PROVELOOP$, is quite interesting and not something I knew -- thanks for that!

Comment by Scott Aaronson

2013-05-22T03:07:13Z

Thanks, Noah! But yes, that second step was precisely the one that I couldn't see how to do.

Comment by Scott Aaronson

2013-04-29T21:32:14Z

Timothy, when you write that there are algorithms that run in time polynomial in the value of the permanent, I assume you mean for nonnegative matrices only! For general matrices, I believe even deciding whether the permanent is (say) 0 or 1 is #P-hard under nondeterministic reductions.

Comment by Scott Aaronson

2013-04-18T05:26:53Z

The trouble I have is that none of the alternative definitions on offer seem accessible to someone first learning about tensors! Related to that (in my mind), they don't make clear how one would actually represent a tensor on a computer (e.g., how many degrees of freedom are there, and what do we do with them?). So, is there a way to explain what tensors are that satisfies those constraints but also leads to fewer wrong intuitions?

Comment by Scott Aaronson

2013-03-20T19:17:04Z

Hi Kolia, thanks very much! As it happens, I just learned of your paper with Vitanyi a couple weeks ago, and had revisited this question intending to post an update to it, explaining that you and Vitanyi had "essentially" answered it!

Comment by Scott Aaronson

2013-02-16T06:29:05Z

So, that's why I think we need to take $\Lambda$ and $\Lambda'$ disjoint. Please let me know if I'm missing something!

Comment by Scott Aaronson

2013-02-16T06:27:25Z

Sorry for the delay! Manas Patra and S. Carnahan: I also thought about defining convex combinations of theories, $T_c=cT+(1-c)T'$, by using the same ontic space, and letting $f_c=cf+(1-c)f'$. But I think there's a problem: the resulting theory $T_c$ might no longer reproduce quantum mechanics, even if $T$ and $T'$ did. If we were only mixing $f$'s or only mixing $D$'s, then we'd be fine, by linearity. But when we mix both of them, we get unwanted cross-terms: the integral of $f(\lambda,M,i)d \lambda$ over $\lambda$ drawn from $D'$, and of $f'(\lambda,M,i)d \lambda$ over $\lambda$ from $D$.

Comment by Scott Aaronson

2012-10-28T19:57:35Z

Jonah, I suggest declaring May to be Quadratic Reciprocity Awareness Month (5 being the first prime congruent to 1 mod 4). You could organize a march on Washington DC, with sign-carrying algebraic number theorists bussed in from as far away as Cambridge, MA. It would probably get some news coverage, and I, for one, would be happy to participate. :-D

Comment by Scott Aaronson

2012-10-01T21:24:23Z

Ah, OK -- thanks!

Comment by Scott Aaronson

2012-10-01T21:01:22Z

Sean, what do you mean by "artifact of the proof"? (Or rather: how could a theorem not be an artifact of its proof? :) )

Comment by Scott Aaronson

2012-10-01T20:46:44Z

Thanks, Sean! Fortunately, I'm happy to assume that S is measurable. But I hadn't realized that Terry's "wlog S is open" observation applies even when S need not contain any nontrivial annuli. So, do I understand you correctly that if, for all x, S contains circles centered at x whose radii are arbitrarily close to 1, then S has full Lebesgue measure? If so ... wow, that's wild!

Comment by Scott Aaronson

2012-10-01T17:16:36Z

Also, just to make sure I understand: does your adaptation of Marstrand's argument actually require that the intervals [a,b] are nontrivial? Or would it also be true that any subset S of R^2 must have full Lebesgue measure, provided that it contains, for every x, circles centered at x whose radii are arbitrarily close to 1? Possibly-related, do we get the slightly stronger conclusion that, if a subset T of R^2 has positive Lebesgue measure, then there must exist a specific point x such that the circles centered at x (of radius between a and b) intersect T on a set of positive measure?

Comment by Scott Aaronson

2012-10-01T17:12:19Z

Thanks so much, Terry! I thought the point of my "translation" construction was that, even after you add an additional degree of freedom to the lines problem (by saying that there must be line segments in every direction arbitrary close to any given line), the set S can still have arbitrarily-small Lebesgue measure. But I suppose the catch is that the degree of freedom we've added doesn't "count" for measurability purposes, because of the "arbitrarily close" proviso?

User scott aaronson - MathOverflow

Is deciding whether a Turing machine *provably* runs forever equivalent to the halting problem?

"psi-epistemic theories" in 3 or more dimensions

Can a string's sophistication be defined in an unsophisticated way?

Can you cover the Boolean cube {0,1}^n with O(1) Hamming-balls each of radius n/2-c*sqrt(n)?

A Kakeya-like problem: must a union of annuli fill the plane?

Answer by Scott Aaronson for What are some examples of ingenious, unexpected constructions?

Answer by Scott Aaronson for Saying things rapidly about integer factorisations

Answer by Scott Aaronson for Do all uncountable sets contain elements with infinite Kolmogorov complexity?

Answer by Scott Aaronson for Blackbox Theorems

Answer by Scott Aaronson for "psi-epistemic theories" in 3 or more dimensions

The "sensitivity" of 2-colorings of the d-dimensional integer lattice

Pi1-sentence independent of ZF, ZF+Con(ZF), ZF+Con(ZF)+Con(ZF+Con(ZF)), etc.?

Answer by Scott Aaronson for nontrivial theorems with trivial proofs

"Closed-form" functions with half-exponential growth

"Simpler" statements equivalent to Con(PA) or Con(ZFC)?

Answer by Scott Aaronson for Philosophical Question related to Largest Known Primes

Succinctly naming big numbers: ZFC versus Busy-Beaver

Anti-concentration bound for permanents of Gaussian matrices?

Answer by Scott Aaronson for Are there any interesting examples of random NP-complete problems?

Answer by Scott Aaronson for What's known about the relationship about EQP and BQP?

Answer by Scott Aaronson for How do we know that P != LINSPACE without knowing if one is a subset of the other?

Answer by Scott Aaronson for What is the easiest randomized algorithm to motivate to the layperson?

Answer by Scott Aaronson for What are some applications of other fields to mathematics?

Answer by Scott Aaronson for Is all non-convex optimization heuristic?

Answer by Scott Aaronson for Problems known to be in both NP and coNP, but not known to be in P

Answer by Scott Aaronson for Intuitive crutches for higher dimensional thinking

Answer by Scott Aaronson for Is there a promise version of 3-coloring equivalent to Graph Isomorphism?

Analogue of the Chebyshev polynomials over C?

Comment by Scott Aaronson

Comment by Scott Aaronson

Comment by Scott Aaronson

Comment by Scott Aaronson

Comment by Scott Aaronson

Comment by Scott Aaronson

Comment by Scott Aaronson

Comment by Scott Aaronson

Comment by Scott Aaronson

Comment by Scott Aaronson

Comment by Scott Aaronson

Comment by Scott Aaronson

Comment by Scott Aaronson

Comment by Scott Aaronson

Comment by Scott Aaronson

Is deciding whether a Turing machine provably runs forever equivalent to the halting problem?