[FOM] P vs NP undecidability/independence update

V.Z. Nuri vznuri at yahoo.com
Thu Oct 30 12:29:05 EST 2003

hi all, its been awhile since Ive posted here but
just wanted to tip you off on some interesting new
papers related to the possibility of unprovability/undecidability/
independence of the P vs NP question.

there was an interesting thread here on FOM on
the subject in approx july/august 2001 and other

this is a recent survey paper by scott aaronson on the subject from
october of this year written in an at-times humorous style.
written from the point of view of a complexity theorist
more than a logicist. at the very end he cites FOM and
a msg by s.cook asking/speculating about links between P vs NP and
large cardinals. heavy citation of online papers/refs.


some ideas by daCosta & doria which I alerted readers
to here quite awhile ago have finally twisted & turned
their way past the review process & into publication.

N. C. A. da Costa and F. A. Doria, ``Consequences of
an exotic definition for P=NP,'' Applied Mathematics
and Computation, vol. 145, 655-665 (2003).

this is a recent paper by okamoto & kashima that has some
unprovability ideas relating to P vs NP via a goedelian
type reduction. a very long& technical paper, so far
reactions in the complexity theory community seem to be

> >
> > http://eprint.iacr.org/2003/187/
> > Cryptology ePrint Archive: Report 2003/187
> >
> > Resource Bounded Unprovability of Computational Lower Bounds
> >
> > Tatsuaki Okamoto and Ryo Kashima

Do you Yahoo!?
Exclusive Video Premiere - Britney Spears

More information about the FOM mailing list