![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
I'm sure you've already heard about this if you've been anywhere near
the internet today, but there's apparently a new claim at a proof of
P!=NP which at least looks pretty worth taking seriously:
http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf
It'll be interesting to hear what people have to say about it as they
have time to review it in detail. At worst case, it seems there'll be
an interesting failure at a proof, which is still something sort of cool
IMHO.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Kevin Wampler <wam### [at] u washington edu> wrote:
> I'm sure you've already heard about this if you've been anywhere near
> the internet today, but there's apparently a new claim at a proof of
> P!=NP which at least looks pretty worth taking seriously:
> http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf
> It'll be interesting to hear what people have to say about it as they
> have time to review it in detail. At worst case, it seems there'll be
> an interesting failure at a proof, which is still something sort of cool
> IMHO.
If the proof results to be correct, I think a *lot* of people out there
are going to sigh in relief (because an enormous amount of math and
practical computer code out there rely on the assumption that P != NP).
--
- Warp
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Kevin Wampler <wam### [at] u washington edu> wrote:
> It'll be interesting to hear what people have to say about it as they
> have time to review it in detail.
You can find some preliminary opinions at these places:
http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/
http://news.ycombinator.com/item?id=1585850
--
- Warp
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Warp wrote:
> You can find some preliminary opinions at these places:
...which leads, among other things, to
http://www.scottaaronson.com/blog/?p=304
Apparently, any mathematical breakthrough not written using TeX is
probably bogus. Go figure.
(It's a good thing I write all my math using TeX, eh?)
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible <voi### [at] dev null> wrote:
> Warp wrote:
>
> > You can find some preliminary opinions at these places:
>
> ...which leads, among other things, to
>
> http://www.scottaaronson.com/blog/?p=304
>
> Apparently, any mathematical breakthrough not written using TeX is
> probably bogus. Go figure.
>
> (It's a good thing I write all my math using TeX, eh?)
I'm with Scott - though I think LaTeX will do.
I don't ever expect to write a breakthrough paper but I've spent long enough
butting my head against various word processing systems that don't really do
maths (or other formallly structured text, like computer science or music
notation) so well to have embraced TeX (actually LaTeX with a few bits of TeX)
with love as a document preparation system that acts as an aid to logical
thought rather than an incitement to keyboard/mouse vandalism.
If someone is sufficiently brighter than me to be able to write a breakthrough
paper, I'd think they would be bright enough to come to a similar conclusion
about TeX.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>> Apparently, any mathematical breakthrough not written using TeX is
>> probably bogus. Go figure.
>
> I'm with Scott - though I think LaTeX will do.
Well, yeah, by "TeX" I presume he means generically any TeX-powered
macro system. (LaTeX, ConTeX, pdfTeX, the list goes on...)
> I don't ever expect to write a breakthrough paper but I've spent long enough
> butting my head against various word processing systems that don't really do
> maths (or other formallly structured text, like computer science or music
> notation) so well to have embraced TeX (actually LaTeX with a few bits of TeX)
> with love as a document preparation system that acts as an aid to logical
> thought rather than an incitement to keyboard/mouse vandalism.
>
> If someone is sufficiently brighter than me to be able to write a breakthrough
> paper, I'd think they would be bright enough to come to a similar conclusion
> about TeX.
TeX produces very nice output, and it has a nice seperation between
content and presentation.
And that's where the niceness ends. Sadly, TeX is ancient technology
now. It doesn't handle colour properly. It doesn't handle graphics
properly. It doesn't handle Unicode properly. And the entire
infrastructure of it is based around low-level text substitution and
macro expension. This makes even utterly trivial tasks like displaying
symbols which are meaningful to TeX itself excruciatingly tricky,
involving black magic with catcodes and the like. (You say \verb, I say
"fragile!")
Worst of all, TeX seperates content from style, but then makes it
jaw-droppingly intractible to change even the most miniscule aspects of
the default styling. You know a TeX document when you see one, because
they're all 100% identical, because it's just far too hard to change any
of the style parameters.
Also, TeX (or is it LaTeX?) is a perculiar *insistence* on putting page
breaks in the wrong place. It will _not_ put page breaks between
paragraphics, only in the middle of them. (Or between the paragraph and
the figure it's talking about.)
I see it all the time: I fill up a paragraph, and it just about fits on
the current page. I write the next paragraph, and BAM! The existing one,
which used to fit on one page, gets broken across two pages. WHY?! >_<
I keep promising myself someday I'll take the TeX formatting engine -
which is excellent - and wire it up to a control language that normal
humans can actaully do useful work with. But, alas, the program source
code is written in some obscure dialect of Pascal, and does baroque
things like testing whether you're using ASCII or EBCDIC. (NO, I'M NOT
KIDDING!)
By contrast, HTML is delightfully easy to style using CSS. It's just a
shame the end result looks so bland and ugly.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible wrote:
> (Or between the paragraph and the figure it's talking about.)
"Because Leslie likes it that way."
--
Darren New, San Diego CA, USA (PST)
C# - a language whose greatest drawback
is that its best implementation comes
from a company that doesn't hate Microsoft.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Warp wrote:
>
> If the proof results to be correct, I think a *lot* of people out there
> are going to sigh in relief (because an enormous amount of math and
> practical computer code out there rely on the assumption that P != NP).
>
This is not to argue with your point, which I imagine is correct, but
were you thinking of any particular example of useful code which P!=NP
would ensure the applicability/correctness of? I can certainly think of
many things that P=NP would mess up, but nothing comes to mind which
couldn't still be messed up despite P!=NP holding. Or were you more
just saying that P!=NP at least removes one possible way that, for
instance, modern cryptography could be broken?
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible <voi### [at] dev null> writes:
> And that's where the niceness ends. Sadly, TeX is ancient technology
> now. It doesn't handle colour properly. It doesn't handle graphics
> properly. It doesn't handle Unicode properly. And the entire
And thankfully, mostly irrelevant to writing a mathematics paper.
> By contrast, HTML is delightfully easy to style using CSS. It's just a
I hate you.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Kevin Wampler <wam### [at] u washington edu> wrote:
> Warp wrote:
> >
> > If the proof results to be correct, I think a *lot* of people out there
> > are going to sigh in relief (because an enormous amount of math and
> > practical computer code out there rely on the assumption that P != NP).
> >
> This is not to argue with your point, which I imagine is correct, but
> were you thinking of any particular example of useful code which P!=NP
> would ensure the applicability/correctness of? I can certainly think of
> many things that P=NP would mess up, but nothing comes to mind which
> couldn't still be messed up despite P!=NP holding. Or were you more
> just saying that P!=NP at least removes one possible way that, for
> instance, modern cryptography could be broken?
The vast majority of modern cryptography uses algorithms which have been
proven to be NP, and their security relies on the assumption that P != NP.
If P != NP indeed is correct, then it's certain that no algorithm can
exist that cracks an NP encryption in polynomial time. Not now, nor any
time in the future.
Thus future-proofing an encryption algorithm becomes (relatively) simple:
1) Prove mathematically that your encryption algorithm is NP.
2) Add enough bits to the keys to last forever.
(Of course there's still the possibility that a new discovered physical
phenomenon can be used to solve NP problems fast with enormously massive
parallelism or other weirdness.)
--
- Warp
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |