FOM: theory-edge mailing list, tautologies

[JoeShipman@aol.com]

I just looked at this "theory-edge" mailing list.  It has a high noise ratio but enough thought-provoking posts to be worth checking out periodically.

Answers to Nuri's questions:

- do you know of any good survey articles on 
large cardinal hypotheses, the "standard model", 
& the relationship 
to complexity theory, computation etcetera

For large cardinal hypotheses, the place to start is Jech's book on Set Theory; I can't think of a good survey article offhand that is not highly technical.  I saw the post on the theory-edge list which mentioned "the standard model" -- this was a response to a confused query about whether a proof showing that P=NP required a large cardinal hypothesis to settle would mean that we would be free to assume either side of the question.  The reference to "the standard model" in that response was simply pointing out that P=NP is equivalent to a statement about integers which is either true or false in the standard model of the integers consisting of the set N={0,1,2,...} together with the usual operations of addition and multiplication as standardly defined in higher mathematics.

- if anyone has an opinion on whether P=?NP
is provable relative to PA or ZFC, I would
be interested to hear.

In my opinion P?=NP is unlikely to be independent of ZFC or related to large cardinals, but I would not be surprised if it was independent of Peano arithmetic.  I'm currently thinking about the relationship between the NP?=co-NP question and the question whether all tautologies have short proofs.  Does anyone know of any results on the lengths of derivations of tautologies from a finite set of basic schemas?  (I know that standard schemas allow all tautologies to be derived in derivations of exponential length, but I'd like to see a result of the form "from this set of schemas, some tautologies have derivations but do not have polynomial length derivations".   It seems possible to define a powerful enough set of schemas to simulate computation efficiently, and getting such a result for that set this would be the same as proving NPnot=co-NP, but the interesting thing would be to find a set of schemas weak enough that you COULD get a result of this form.  Such a set would necess!
arily be incomplete, since the l
engths of derivations from any two complete sets of schemas are obviously polynomially related.)

- also, I have been wondering a long time if
there is some result in computational complexity theory
related to the continuum hypothesis. any
ideas along those lines?

This is impossible.  The Continuum Hypothesis or its negation cannot have anything to say about computational complexity theory or any other set of mathematical statements which can be formulated arithmetically.  This is very different from the situation with large cardinal hypotheses, which have immediate consequences in the theory of the integers.

-- Joe Shipman