[FOM] P vs NP undecidability/independence update

[V.Z. Nuri]

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
times.

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.

http://people.cs.uchicago.edu/~fortnow/beatcs/column81.pdf


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
mixed.

> >
> > 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
http://launch.yahoo.com/promos/britneyspears/