24/4/08
Neutrino Unbound
Pure logical thinking cannot yield us any knowledge of the empirical world; all knowledge of reality starts from experience and ends in it. A. Einstein (1933)
http://www.nu.to.infn.it/ Sphere: Related Content
http://www.nu.to.infn.it/ Sphere: Related Content
23/4/08
FOM: Smale's list of mathematical problems for the next century
In the Spring 1998 Mathematical Intelligencer, Steve Smale (responding to a query by V.I. Arnold on behalf of the International Mathematical Union) listsSphere: Related Content
18 important "mathematical problems" for the next century. This provides a good set of examples for my project to classify open problems by logical type
Smale's list is not intended to encompass all areas of math, but rather areas he is acquainted with; presumably Arnold will collate responses from a number
of mathematicians to arrive at broad list worthy of being compared with Hilbert's famous list of 1900. (Is there any mathematician alive today who
even approaches the breadth of Hilbert and Poincare? Can anyone name someone who has made significant contributions to more than two mathematical areas?)
Remark: It is not necessary for a problem to be precisely stated in the formal language of mathematics for it to be a good and important problem;
Hilbert's 10th problem is one of several on his list which did not admit precise formulations at the time.
The first three problems on Smale's list are the Riemann Hypothesis, the Poincare Conjecture, and the P=?NP question. As I observed last month,
these are provably equivalent to sentences which are pi^0_1, pi^0_2, and pi^0_2. Interestingly, Smale's versions of the statements are of much higher
logical type. He states the Riemann Hypothesis in terms of the zeta function defined by analytic continuation from the series 1^(-s)+2^(-s)+... which is at
least 3 levels of powerset above arithmetic (analytic continuation involves sets of functions of complex numbers -- I don't regard the passage from
reals to complex numbers (pairs of reals) as going up in type). His version of the Poincare conjecture involves the differentiable category rather than
the topological, PL, or simplicial categories, which is also at least 3 levels up. The theorems that these categories are all equivalent in dimension 3
(by the way, who proved these equivalences?) reduce the statement to a combinatorial one. Finally, Smale even states Pnot=NP in a version that
requires real numbers ("There is no polynomial-time algorithm for deciding the Hilbert Nullstellensatz over C"). This requires defining "computation
over C" and Smale cites his papers with Blum, Shub, and Cucker which develop this theory. Here at least Smale remarks that replacing C with Z2
gives a provable equivalent to the classic conjecture Pnot=NP.
I won't attempt to classify all of Smale's 18 here; but I will discuss the ones which in my opinion are the most interesting. Nearly all of the 18
involve computation theory, dynamical systems, or both.
5: Can the set of solvable 2-variable diophantine equations be decided in time O(2^(s^c)) for some constant c, where s is the input size (sum over all
coefficients a of (1+log(|a|+1)))?
8. Extend the mathematical model of general equilibrium theory to include price adjustments. (This one is imprecise, and I would regard it as too far
out to be in such a list, unlike the problems of mathematical physics. But the flaws in the current model are clear enough and this problem could
conceivably be solved in a useful way.)
9. Is there a polynomial-time algorithm over the real numbers which decides the feasibility of the linear system of inequalities Ax>=b? (I can't get
excited about this one given the solution of the analogous, more famous problem over Q by Khachian and its practical implementation by Karmarkar).
13. Hilbert's 16th problem: dx/dt=P(x,y) dy/dt=Q(x,y) diff eq on |R^2.Is there a bound K on the number of limit cycles of the form K <= d^q,
where d=max(deg P, deg Q) and q is a universal constant?
15. Do the Navier-Stokes equations on a 3-dimensional domain in |R^3 have a unique smooth solution for all time?
16. The Jacobian Conjecture: Must every polynomial map from |C^n to |C^n whose derivative at each point is non-singular be injective? (This very nice
problem is the only one on Smale's list I would add to my own list.)
18. "What are the limits of intelligence, both artificial and human?"
This at first looks ridiculously imprecise, but mathematics could conceivably have something important to say here. Godel's Incompleteness Theorem is
relevant, and physical "Theories of Everything" could have nontrivial implications regarding what we could theoretically come to know.
I suspect all of the precisely stated problems in Smale's list can be rendered in second-order arithmetic by the usual methods of coding for functions on
complete separable metric spaces--can Steve or Harvey confirm this? Can we apply Absoluteness theorems like Shoenfield's to conclude that Smale's 16
precisely stated problems are absolute in some useful sense (e.g. true in V if true in L)?
My favorite problem that Smale left off is the Invariant Subspace Conjecture("every bounded operator on Hilbert space has a nontrivial invariant subspace").
It is equivalent by straightforward coding to a pi^1_2 sentence (use the representation of Hilbert space as l2(|R), the set of square-summable
sequences).
Can anyone out there suggest some more problems? I'd like to end up with four classes, in order of decreasing definiteness:
1) Problems equivalent to arithmetical statements
2) Problems not in 1) which are still absolute (and can someone please suggest a good sense of "absolute" to use here; if I can't find a fully
satisfactory one I'll replace "absolute" with "equivalent to statements of second-order arithmetic").
3) Problems equivalent to statements in the language of set theory
4) Imprecisely stated problems.
Of course, a problem in category 4 could end up being regarded as much more definite than one in category 3, as the examples of Hilbert's 1st and 10th
problems prove!
-- Joe Shipman shipman@dgprn3.bloomberg.com
http://www.cs.nyu.edu/pipermail/fom/1998-May/001868.html
21/4/08
truly truths
truly great friends are hard to find, difficult to leave,and impossible to forget."(G.Randolf)
Sphere: Related Content
20/4/08
Suscribirse a:
Entradas (Atom)
+18.20.50.png)
