Saturday, February 16, 2008
in theory moves
We ring in the year of the rat with a move to wordpress, and to its superior handling of latex.
Please update your bookmarks, your RSS readers, and your blogrolls, to
http://lucatrevisan.wordpress.com/
While all old posts and comments are there, the move has broken the latex hacks, the videos, and the cross-links between posts. This will be taken care of in the "near" future.
Please update your bookmarks, your RSS readers, and your blogrolls, to
http://lucatrevisan.wordpress.com/
While all old posts and comments are there, the move has broken the latex hacks, the videos, and the cross-links between posts. This will be taken care of in the "near" future.
posted by Luca at 11:15 PM 0 comments
Wednesday, February 06, 2008
Sunday, January 27, 2008
Overheard in San Francisco
Young Homeless Guy is sitting on the floor with a cardboard sign. Another guy walks by, holding what look like large leftover bags from a restaurant.
Guy With Bags: [stops and offers the bags] would you like something to eat?
Young Homeless Guy: is there garlic or avocado in it?
GWB: I don't think so, why?
YHG: I am allergic to both. Especially avocado: when I eat it, my throat gets all scratchy.
Guy With Bags: [stops and offers the bags] would you like something to eat?
Young Homeless Guy: is there garlic or avocado in it?
GWB: I don't think so, why?
YHG: I am allergic to both. Especially avocado: when I eat it, my throat gets all scratchy.
posted by Luca at 11:23 PM 4 comments
Saturday, January 26, 2008
An Unusual Recruiting Pitch
Women in their sophomore or junior year of college who are thinking about doing research and going to graduate school should read this article (via Andrew Sullivan). Living the life of the mind is very rewarding, and, apparently, the chances of dating male models are not bad either. (If the author could get some mileage out of being an undergrad at Harvard, just imagine what it can do for you to be a grad student at Berkeley!)
posted by Luca at 6:56 PM 4 comments
Thursday, January 24, 2008
Finally!
After a hiatus of almost four year, the graduate computational complexity course returns to Berkeley.
To get started, I proved Cook's non-deterministic hierarchy theorem, a 1970s result with a beautifully clever proof, which I first learned from Sanjeev Arora. (And that is not very well known.)
Though the full result is more general, say we want to prove that there is a language in NP that cannot be solved by non-deterministic Turing machines in time $o(n^3)$.
(If one does not want to talk about non-deterministic Turing machines, the same proof will apply to other quantitative restrictions on NP, such as bounding the length of the witness and the running time of the verification.)
In the deterministic case, where we want to find a language in P not solvable in time $o(n^3),ドル it's very simple. We define the language $L$ that contains all pairs $(\langle T\rangle,x)$ where: (i) $T$ is a Turing machine, (ii) $x$ is a binary string, (iii) $T$ rejects the input $(\langle T\rangle,x)$ within $|(\langle T\rangle,x)|^3$ steps, where $|z|$ denotes the length of a string $z$.
It's easy to see that $L$ is in P, and it is also easy to see that if a machine $M$ could decide this problem in time $\leq n^3$ on all sufficiently large inputs, then the behavior of $M$ on input $\langle M\rangle,x,ドル for every $x$ long enough, leads to a contradiction.
We could try the same with NP, and define $L$ to contain pairs $(\langle T\rangle,x)$ such that $T$ is a non-deterministic Turing machine that has no accepting path of length $\leq |\langle T\rangle,x|^3$ on input $(\langle T\rangle,x)$. It would be easy to see that $L$ cannot be solved non-deterministically in time $o(n^3),ドル but it's hopeless to prove that $L$ is in NP, because in order to solve $L$ we need to decide whether a given non-deterministic Turing machine rejects, which is, in general, a coNP-complete problem.
Here is Cook's argument. Define the function $f(k)$ as follows: $f(1):=2,ドル $f(k):= 2^{(1+f(k-1))^3}$. Hence, $f(k)$ is a tower of exponentials of height $k$. Now define the language $L$ as follows.
Now let's see that $L$ is in NP. When we are given an input $\langle T\rangle,0^t$ we can first check if there is a $k$ such that $f(k)=t$.
In either case, we are correctly deciding the language.
Finally, suppose that $L$ could be decided by a non-deterministic Turing machine $M$ running in time $o(n^3)$. In particular, for all sufficiently large $t,ドル the machine runs in time $\leq t^3$ on input $\langle M\rangle,0^t$.
Choose $k$ to be sufficiently large so that for every $t$ in the interval 1ドル+f(k-1),...,f(k)$ the above property is true.
Now we can see that $M$ accepts $(\langle M\rangle,0^{f(k-1)+1})$ if and only if $M$ accepts $(\langle M\rangle,0^{f(k-1)+2})$ if and only if ... if and only if $M$ accepts $(\langle M\rangle,0^{f(k)})$ if and only if $M$ rejects $(\langle M\rangle,0^{f(k-1)+1}),ドル and we have our contradiction.
To get started, I proved Cook's non-deterministic hierarchy theorem, a 1970s result with a beautifully clever proof, which I first learned from Sanjeev Arora. (And that is not very well known.)
Though the full result is more general, say we want to prove that there is a language in NP that cannot be solved by non-deterministic Turing machines in time $o(n^3)$.
(If one does not want to talk about non-deterministic Turing machines, the same proof will apply to other quantitative restrictions on NP, such as bounding the length of the witness and the running time of the verification.)
In the deterministic case, where we want to find a language in P not solvable in time $o(n^3),ドル it's very simple. We define the language $L$ that contains all pairs $(\langle T\rangle,x)$ where: (i) $T$ is a Turing machine, (ii) $x$ is a binary string, (iii) $T$ rejects the input $(\langle T\rangle,x)$ within $|(\langle T\rangle,x)|^3$ steps, where $|z|$ denotes the length of a string $z$.
It's easy to see that $L$ is in P, and it is also easy to see that if a machine $M$ could decide this problem in time $\leq n^3$ on all sufficiently large inputs, then the behavior of $M$ on input $\langle M\rangle,x,ドル for every $x$ long enough, leads to a contradiction.
We could try the same with NP, and define $L$ to contain pairs $(\langle T\rangle,x)$ such that $T$ is a non-deterministic Turing machine that has no accepting path of length $\leq |\langle T\rangle,x|^3$ on input $(\langle T\rangle,x)$. It would be easy to see that $L$ cannot be solved non-deterministically in time $o(n^3),ドル but it's hopeless to prove that $L$ is in NP, because in order to solve $L$ we need to decide whether a given non-deterministic Turing machine rejects, which is, in general, a coNP-complete problem.
Here is Cook's argument. Define the function $f(k)$ as follows: $f(1):=2,ドル $f(k):= 2^{(1+f(k-1))^3}$. Hence, $f(k)$ is a tower of exponentials of height $k$. Now define the language $L$ as follows.
$L$ contains all pairs $\langleT \rangle,0^t$ where $\langle T\rangle$ is a non-deterministic Turing machine and 0ドル^t$ is a sequence of $t$ zeroes such that one of the following conditions is satisfied
- There is a $k$ such that $f(k)=t,ドル and $T$ has no accepting computation on input $\langle T\rangle,0^{1+f(k-1)}$ of running time $\leq (1+(f(k-1))^3$;
- $t$ is not of the form $f(k)$ for any $k,ドル and $T$ has an accepting computation on input $\langle T\rangle,0^{1+t}$ of running time $\leq (t+1)^3$.
Now let's see that $L$ is in NP. When we are given an input $\langle T\rangle,0^t$ we can first check if there is a $k$ such that $f(k)=t$.
- If there is, we can compute $t':=f(k-1)$ and deterministically simulate all computations of $T$ on inputs $\langle T\rangle,0^{t'}$ up to running time $t'^3$. This takes time 2ドル^{O(t'^3)}$ which is polynomial in $t$.
- Otherwise, we non-deterministically simulate $T$ on input $\langle T\rangle,0^{t+1}$ for up to $(t+1)^3$ steps. (And reject after time-out.)
In either case, we are correctly deciding the language.
Finally, suppose that $L$ could be decided by a non-deterministic Turing machine $M$ running in time $o(n^3)$. In particular, for all sufficiently large $t,ドル the machine runs in time $\leq t^3$ on input $\langle M\rangle,0^t$.
Choose $k$ to be sufficiently large so that for every $t$ in the interval 1ドル+f(k-1),...,f(k)$ the above property is true.
Now we can see that $M$ accepts $(\langle M\rangle,0^{f(k-1)+1})$ if and only if $M$ accepts $(\langle M\rangle,0^{f(k-1)+2})$ if and only if ... if and only if $M$ accepts $(\langle M\rangle,0^{f(k)})$ if and only if $M$ rejects $(\langle M\rangle,0^{f(k-1)+1}),ドル and we have our contradiction.
posted by Luca at 5:58 PM 0 comments
