[FOM] P vs NP undecidability/independence update
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