User john watrous - MathOverflow

How fast are a ruler and compass?

2010-07-22T18:06:18Z

This may be more of a recreational mathematics question than a research question, but I have wondered about it for a while. I hope it is not inappropriate for MO.

Consider the standard assumptions for ruler and compass constructions: We have an infinitely large sheet of paper, which we associate with the complex plane, that is initially blank aside from the points 0 and 1 being marked. In addition we have an infinite ruler and a compass that can be stretched to an arbitrary length.

Let us define a move to be one of the two actions normally associated with a ruler and compass:

Use the ruler to draw the line defined by any two distinct points already marked on the paper.
Stretch the compass from any one marked point to another and draw the resulting circle.

Assume that all intersection points among lines and circles drawn by these operations are automatically marked on the paper.

Now define $D(n)$ to be the maximum distance between any two marked points that can be constructed in this way with $n$ moves.

Questions:

Is anyone aware of results about the function $D(n)$ or something equivalent?
It is not difficult to prove $D(n) > 2^{2^{cn}}$ for some positive constant $c$ for sufficiently large $n$. Can one do better? If so, can one prove an upper bound on $D(n)$?

Answer by John Watrous for Where does the game-theoretic characterization of PH come from?

2010-08-27T18:06:44Z

The answer to part (a) of your question is this reference:

A. Meyer and L. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. In Proceedings of the 13th IEEE Symposium on Switching and Automata Theory, pages 125-129, 1972. [pdf]

What an amazing paper this was! Two later papers that discuss refinements of the result include these:

C. Wrathall. Complete sets and the polynomial-time hierarchy. Theoretical Computer Science 3:23-33, 1977.

A. Chandra, D. Kozen, and L. Stockmeyer. Alternation. Journal of the ACM 28(1):114-133, 1981.

Answer by John Watrous for Space Bounded Communication Complexity of Identity

2010-07-30T14:01:59Z

Here's an argument that I believe shows that $\log n - \omega(1)$ is impossible. (This argument came out of a discussion I had with Steve Fenner.)

Let Alice's input be $x\in\{0,1\}^n$ and let Bob's input be $y\in\{0,1\}^n$ . Assume the shared memory stores states in $\{0,1\}^m$ , and its initial state is $0^m$. We are interested in lower-bounding $m$ for any protocol that computes EQ$(x,y)$.

A given protocol is defined by two collections of functions $\{f_x\}$ and $\{g_y\}$ , representing the functions applied to the shared memory by Alice on each input $x$ and Bob on each input $y$, respectively, along with some answering criterion. To be more specific, let us assume that if the shared memory ever contains the string $1^{m-1}b$ then the output of the protocol is $b$ (for each $b\in\{0,1\}$ ). For convenience, let us also assume that $f_x(1^{m-1}b) = 1^{m-1}b\:$ and $g_y(1^{m-1}b) = 1^{m-1}b\:$ for every $x,y\in\{0,1\}^n$ and $b\in\{0,1\}$ . In other words, Alice and Bob don't change the shared memory once they know the answer.

Now, for each $x,y\in\{0,1\}^n$ , consider what happens when Alice and Bob run the protocol on the input $(x,y)$. Define $A_{x,y}\subseteq\{0,1\}^m$ to be the set of all states of the shared memory that Alice receives at any point in the protocol, and likewise define $B_{x,y}\subseteq\{0,1\}^m$ to be the states of the shared memory that Bob receives. Also define \[ S_{x,y} = \{0w\,:\,w\in A_{x,y}\} \cup \{1w\,:\,w\in B_{x,y}\}. \] We will assume Alice goes first, so $0^m \in A_{x,y}$ for all $x,y$. Let us also make the following observations:

By the definition of $A_{x,y}$ and $B_{x,y}$, it holds that $f_x(A_{x,y}) \subseteq B_{x,y}$ and $g_y(B_{x,y}) \subseteq A_{x,y}$ for all $x,y$.
For every $x,y$ with $x\not=y$ it holds that $1^{m-1}0\in A_{x,y} \cup B_{x,y}$, because Alice and Bob output 0 when their strings disagree.
For every $x$ it holds that $1^{m-1}0\not\in A_{x,x} \cup B_{x,x}$, because Alice and Bob do not output 0 when their strings agree.

Now let us prove that $S_{x,x}\not=S_{y,y}$ whenever $x\not=y$. To do this, let us assume toward contradiction that $x\not=y$ but $S_{x,x} = S_{y,y}$ (i.e., $A_{x,x} = A_{y,y}$ and $B_{x,x} = B_{y,y}$), and consider the behavior of the protocol on the input $(x,y)$.

Let $w_t$ be the contents of the shared memory after $t$ turns have passed in the protocol, so we have $w_0 = 0^m$, $w_1 = f_x(w_0)$, $w_2 = g_y(w_1)$, and so on. It holds that \[ \begin{array}{c} w_0 = 0^m \in A_{x,x}\\ w_1 = f_x(w_0) \in f_x(A_{x,x}) \subseteq B_{x,x} = B_{y,y},\\ w_2 = g_y(w_1) \in g_y(B_{y,y}) \subseteq A_{y,y} = A_{x,x}, \end{array} \] and in general \[ \begin{array}{c} w_{2t + 1} = f_x(w_{2t}) \in f_x(A_{x,x}) \subseteq B_{x,x} = B_{y,y}\\ w_{2t+2} = g_y(w_{2t+1}) \in g_y(B_{y,y}) \subseteq A_{y,y} = A_{x,x} \end{array} \] for each $t\in\mathbb{N}$. It follows that $A_{x,y} \subseteq A_{x,x}$ and $B_{x,y} \subseteq B_{y,y}$.

But now we have our contradiction, assuming the protocol is correct: given that $A_{x,y}\subseteq A_{x,x}$ and $B_{x,y} \subseteq B_{y,y}$, it follows that $1^{m-1}0 \in A_{x,x}\cup B_{y,y}$, so Alice and Bob output the incorrect answer 0 on either $(x,x)$ or $(y,y)$.

Each $S_{x,x}$ is a subset of $\{0,1\}^{m+1}$ , so there are at most $2^{2^{m+1}}$ choices for $S_{x,x}$. Given that the sets $S_{x,x}$ must be distinct for distinct choices of $x$, it follows that $2^{2^{m+1}} \geq 2^n$ , so $m \geq \log n - 1$.

Answer by John Watrous for Minimize The k-th Largest Element under Linear Constraints

2010-07-15T23:16:36Z

The problem is NP-hard, unless there is more to it than what is stated, and one cannot hope for an efficient approximation to any reasonable degree unless P = NP.

One way to show this is by a reduction from vertex cover, which may be established as follows. For any undirected graph $G = (V,E)$, let $M\in\mathbb{R}^{E\times V}$ be the incidence matrix of $G$, and let $K$ be the cone of vectors $x\in\mathbb{R}^V$ such that $Mx \geq 0$ (or $-Mx \leq 0$, as the question statement would prefer). If $G$ has a vertex cover of size $k$, then $\inf_{x\in K} F_{k+1}(x) = -\infty$. If not, $\inf_{x\in K} F_{k+1}(x) = 0$. Without further assumptions, this would seem to rule out the existence of an efficient approximation algorithm of any sort.

The same general idea, with simple modifications, will establish a reduction if $x$ is constrained to the nonnegative orthant.

It should also be noted that the problem does not become easier under the assumption $x\in\mathbb{Z}^n$, counter to what the question suggests.

Comment by John Watrous

2010-07-28T11:08:27Z

Stephen Jordan's Quantum Algorithm Zoo (its.caltech.edu/~sjordan/zoo.html) lists many known quantum algorithms. It might be helpful for identifying gaps in your classification scheme.

Comment by John Watrous

2010-07-23T01:09:00Z

Thanks, Igor, that reference is a good lead. It doesn't necessarily answer the question because the maximum distance between marked points will not generally be an integer, but it is a start. About the title of the question, by "fast" I am referring to how fast constructed points can move away from one another as a function of the number of moves. My apologies if that caused confusion.