275 -The Laplacian in polar coordinates

October 7, 2008

In many situations in which symmetries are involved, it is useful to write the equations describing the physical objects under study with respect to frames related to said symmetries. For situations involving rotational symmetry, polar (or cylindrical) coordinates are particularly useful.

For this reason, it is a good exercise to see how to transform something like Laplace equation into polar coordinates.

Remember that the Laplacian of f(x,y) is \displaystyle \nabla\cdot\nabla f=\frac{\partial^2 f}{\partial x^2}+\frac{\partial^2 f}{\partial y^2}. If we write f in polar coordinates as g(r,\theta)=f(r\cos\theta,r\sin\theta), we then need to write the Laplacian directly in terms of derivatives with respect to r and \theta.

Following a common abuse of notation, I will write f_r, etc, for what one should more precisely write g_r, etc, with g as above.

Read the rest of this entry »

5 Comments | 275: Calculus III | Tagged: | Permalink
Posted by andrescaicedo

Separating computational classes and independence

October 7, 2008

In the spirit of a previous posting of his to the Foundations of Mathematics list that I quoted before in this blog, Timothy Chow has posted a nice observation, this time indicating how the truth of some widely believed statements about computational classes could actually lead to their unprovability in certain formal systems, via the identification of fast growing functions. I quote his message below:

[FOM] If “NP is not in P/poly” is barely true, then it is unprovable

Thursday, October 2, 2008 12:53 PM
From: Timothy Y. Chow

Here is a simple observation which is probably not new, but which I have not seen explicitly written down anywhere.  Thanks to Andreas Blass for sanity-checking the argument.

Recall that \mathsf{P}/\mathsf{poly} is the non-uniform analogue of \mathsf{P}: It is the class of Boolean functions computable by polynomial-size Boolean circuits.  It is widely believed that

(*) \mathsf{NP} is not contained in \mathsf{P}/\mathsf{poly}.

Conjecture (*) is a somewhat stronger conjecture than \mathsf{P}\ne\mathsf{NP}, but weaker than the conjecture that the polynomial hierarchy does not collapse.

Suppose that (*) is indeed true, but only “barely true,” i.e., there exists some function f(n) that is just barely superpolynomial, such that there exist Boolean circuits of size f(n) that correctly solve an \mathsf{NP}-complete problem.  Then the promised “simple observation” is that (*) is then unprovable.

To see this, fix some way of encoding \mathsf{SAT} instances.  Let n_0(d) be the smallest integer n such that no Boolean circuit with n inputs and n^d gates correctly solves every instance of \mathsf{SAT} (of the appropriate size). If there is no such n then n_0(d) is undefined.  Then (*) asserts that n_0 is total.

The point is that if (*) is barely true, then n_0 grows very fast.  As Andreas puts it, f(n_0(d)) > (n_0(d))^d because the left side is enough gates to solve n_0(d)-sized instances of \mathsf{SAT} while the right side isn’t. Then for k = g(d) (and therefore also for k not of this form with just a minor change in the estimates) f(k) > k^{n_0^{-1}(k)}.  Now if f is just barely superpolynomial, then the exponent here, n_0^{-1}(k), must be just barely above constant, and so n_0 grows very fast.  If it grows fast enough then your favorite formal system won’t be able to prove that it is total.

Tim

It turns out that Chow’s observation had been done before, in “On the independence of \mathsf{P} versus \mathsf{NP},” by Ben-David and Halevi, a technical report from 1991 available here as of this writing. 

Let \mathsf{PA}_1 denote \mathsf{PA}+\mathrm{Th}_{\Pi^0_1}({\mathbb N}), \mathsf{PA} augmented with all true \Pi^0_1 statements. In their report, Ben-David and Halevi prove:

Theorem. \mathsf{PA}_1\vdash \mathsf{P}\ne \mathsf{NP} if and only if there some \alpha<\epsilon_0 such that the function F_\alpha of the Wainer hierarchy dominates the approximation rate of \mathsf{SAT} to \mathsf{P}.

Here, the approximation rate R^{\mathsf{SAT}}_{\mathsf{P}} is defined by fixing a (canonical) enumeration of the class \mathsf{SAT}, say M_1,M_2,\dots, and setting R^{\mathsf{SAT}}_{\mathsf{P}}(i)=\max_{j\le i}\min\{|x|:\mathsf{P}(x)\ne M_j(x)\}. This function only depends superficially on the specific enumeration being considered, and it is a total function under the assumption that \mathsf{SAT} is not in \mathsf{P}.

Scott Aaronson has a survey on the question of logical independence of “\mathsf{P}=\mathsf{NP},” Is \mathsf{P} Versus \mathsf{NP} Formally Independent?, Bulletin of the EATCS 81, October 2003, as of this writing available at his website. Aaronson’s survey is not really aimed at logicians, but it is self contained and nicely written.

Leave a Comment » | Computational complexity | Permalink
Posted by andrescaicedo

175, 275 -Homework 6

October 7, 2008

Homework 6 is due Tuesday, October 14, at the beginning of lecture. Same remarks as before apply.

175: Section 7.2, exercises 24, 32, 38, 42.
Section 7.3, exercises 4, 11 32, 39.
Section 7.4, exercises 4, 8, 12, 16, 26, 38, 46.
Each exercise is worth 1 point.

275: Section 12.3, exercises 63, 66, 68, 74-77.
Section 12.4, exercises 4, 10, 32, 42-44, 48, 50.
This homework will be graded out of 10 points. Each exercise is worth 1 point. You can turn in as many exercises as you want. Indicate the ones you want to be extra credit problems. Of those, 2 will be chosen randomly to be graded, so you can have up to 2 extra credit points.

4 Comments | 175: Calculus II, 275: Calculus III | Permalink
Posted by andrescaicedo