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

Kevin Wampler <wam### [at] uwashingtonedu> 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

Kevin Wampler <wam### [at] uwashingtonedu> 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

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

Invisible <voi### [at] devnull> 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

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

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

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

Invisible <voi### [at] devnull> 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

Kevin Wampler <wam### [at] uwashingtonedu> 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

Neeum Zawan wrote:

> I hate you.

Oh good. Join the back of the queue. It's long enough. :-/

Post a reply to this message

On 2010-08-10 01:27, Warp wrote:
>    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.

You mean 'certain that no algorithm can brute-force *all combinations* 
of an NP encryption in polynomial time.'  Merely cracking is somewhat 
more trivial, since you (usually) don't need to go through every 
possibility.

-- 
Tim Cook
http://empyrean.freesitespace.net

Post a reply to this message

Tim Cook <z99### [at] gmailcom> wrote:
> On 2010-08-10 01:27, Warp wrote:
> >    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.

> You mean 'certain that no algorithm can brute-force *all combinations* 
> of an NP encryption in polynomial time.'  Merely cracking is somewhat 
> more trivial, since you (usually) don't need to go through every 
> possibility.

  If P != NP, then there can't exist an algorithm which takes any given
input and solves a provably NP problem on that input in polynomial time.

  Of course that doesn't mean that *no* inputs can be solved in polynomial
time (it's rather easy to give trivial individual examples of any NP problem
which can be solved very fast). It means that you can't write a program
which cracks all files encrypted with a certain algorithm in polynomial
time. (And in fact, due to the nature of most NP problems, it won't be
able to crack almost *any* such problem in polynomial time, except for
extremely trivial situations.)

  (Of course we have to remember what the 'N' stands for in "NP". It
doesn't stand for "non", as many people erroneously think. It stands for
"non-deterministic". This means that a non-deterministic algorithm can
solve the problem in polynomial time. Of course implementing this would
need some new physics to be discovered. Quantum computing is the most
promising one, but might not lead anywhere.)

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:

>   If P != NP, then there can't exist an algorithm which takes any given
> input and solves a provably NP problem on that input in polynomial time.
> 
>   Of course that doesn't mean that *no* inputs can be solved in polynomial
> time (it's rather easy to give trivial individual examples of any NP problem
> which can be solved very fast). It means that you can't write a program
> which cracks all files encrypted with a certain algorithm in polynomial
> time. (And in fact, due to the nature of most NP problems, it won't be
> able to crack almost *any* such problem in polynomial time, except for
> extremely trivial situations.)

Is it not also true that although, for example, factorising numbers is 
an NP problem, factorising the product of two Mersenne primes might turn 
out to have a polynomial-time algorithm?

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> factorising numbers is an NP problem

  It's actually not that simple.

  NP problems are decision problems, where the answer is "yes" or "no".
Obviously "what are the factors of this number?" is not such a problem.
The integer factorization problem is an so-called function problem. It
trivially falls into FNP (the function-problem equivalent of NP), but it's
not known if it's also in FP (the function-problem equivalent of P).

  You can make integer factorization into a decision problem by posing it
as "does n have a factor which is smaller tham m?" (posing it like this
is theoretically rational and useful because if you found an algorithm
to solve that problem quickly, you could use it to factorize the number
quickly by using binary search). Again, it's not known which complexity
class this decision version of the problem falls into either.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   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.

Technically, I don't think this is true.  Symmetric cyphers aren't based on 
NP problems.  DH is based on discrete log which I think is NP, but RSA is 
based on an NP problem *with* a trap door, yes? Otherwise it would be hard 
for everyone.  I was pretty sure most of the algorithms involve something 
that *would* be NP if it weren't for trap doors, but again maybe I'm 
misremembering. This isn't really my domain.

>   (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.)

There's always that. It's only NP for Turing machines.

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

Warp wrote:
> 
>   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.
> 

I was sort of asking if you actually had any specific examples of 
commonly used encryption algorithms which are believed to be NP-hard to 
crack, because the ones I can think of aren't and thus wouldn't 
necessarily be safe even if P!=NP.

Post a reply to this message

Kevin Wampler wrote:
> commonly used encryption algorithms which are believed to be NP-hard to 

Diffie Hellman is based on discrete log. Isn't that NP?

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

Darren New wrote:
> Kevin Wampler wrote:
>> commonly used encryption algorithms which are believed to be NP-hard to 
> 
> Diffie Hellman is based on discrete log. Isn't that NP?
> 

Yes, although not in the way that you mean.  It's trivially shown to be 
in NP in the sense that many things are in NP which are not NP-hard (for 
instance anything in P is also in NP).  Although that's a common 
misconception, both discrete log and integer factorization are not 
believed to be NP-hard problems.  Hence the worry that quantum computers 
would break these cryptographic methods despite the face that very few 
people believe that they'd be able to solve NP-complete problems in 
polynomial time.

Post a reply to this message

Kevin Wampler wrote:
> Darren New wrote:
>> Kevin Wampler wrote:
>>> commonly used encryption algorithms which are believed to be NP-hard to 
>>
>> Diffie Hellman is based on discrete log. Isn't that NP?
>>
> 
> Yes, although not in the way that you mean.  It's trivially shown to be 
> in NP in the sense that many things are in NP which are not NP-hard (for 
> instance anything in P is also in NP). 

Well, obviously that's what I meant. I just wasn't being pedantic.

> Although that's a common 
> misconception, both discrete log and integer factorization are not 
> believed to be NP-hard problems.  

OK. That's what I wasn't sure of.  I thought discrete log was proven NP-hard.

So, no, I don't know of any crypto algorithms that depend on p!=np.

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

Darren New wrote:
>>> Diffie Hellman is based on discrete log. Isn't that NP?
>>>
>>
>> Yes, although not in the way that you mean.  It's trivially shown to 
>> be in NP in the sense that many things are in NP which are not NP-hard 
>> (for instance anything in P is also in NP). 
> 
> Well, obviously that's what I meant. I just wasn't being pedantic.

I figured, I commented on it more for the benefit of other people who 
might be following along and who are less familiar with the area :)


> So, no, I don't know of any crypto algorithms that depend on p!=np.

I wonder why this is.  It seems like it would be (relatively) 
straightforward to construct an encryption method which would be NO-hard 
to crack, so there must be a reason why this doesn't seem to be done. 
Perhaps instances of NP-hard problems tend to be much harder to analyze 
and predict the properties of, and thus it's easier to get an encryption 
algorithm which is susceptible to attacks in practice, despite the 
appearance of stronger theoretical guarantees.

Post a reply to this message

Kevin Wampler wrote:
> straightforward to construct an encryption method which would be NO-hard 
> to crack, so there must be a reason why this doesn't seem to be done. 

It is. The problem is that you don't want it to be NP-hard for *everyone*.

You only want it NP-hard for people who don't know the key.

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

Darren New <dne### [at] sanrrcom> wrote:
> It is. The problem is that you don't want it to be NP-hard for *everyone*.

> You only want it NP-hard for people who don't know the key.

  Well, by definition an answer to an NP problem can be verified in
polynomial time.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> It is. The problem is that you don't want it to be NP-hard for *everyone*.
> 
>> You only want it NP-hard for people who don't know the key.
> 
>   Well, by definition an answer to an NP problem can be verified in
> polynomial time.

Right. But here what you want is that people can verify it in polynomial 
time *with* the key, but can't verify it in polynomial time *without* the 
key.  "Verifying" would be "decrypting the message and getting something 
reasonable" for example.

I imagine it can be done. I just don't imagine it's easy to come up with a 
system like that, nor that it's easy to prove a mathematical problem is easy 
with the key and NP-hard without.

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

Darren New <dne### [at] sanrrcom> wrote:
> I imagine it can be done. I just don't imagine it's easy to come up with a 
> system like that, nor that it's easy to prove a mathematical problem is easy 
> with the key and NP-hard without.

  One thing is certain: Creating a truly secure encryption system based on
an NP-hard algorithm is far from trivial. For example, all of these are
based on known NP-hard problems, yet can be cracked in a matter of weeks
with some hundreds of computers:

http://en.wikipedia.org/wiki/McEliece_cryptosystem
http://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem
http://en.wikipedia.org/wiki/Naccache%E2%80%93Stern_knapsack_cryptosystem

  It seems that research on "future-proof" encryption systems which cannot
be cracked quickly even by a quantum computer is a hot topic of research,
and cryptosystems based on NP-hard problems is one line of study, but it's
actually surprisingly hard to come up with an actual cryptosystem which
cannot be cracked even with regular computers (much less quantum computers).

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> I imagine it can be done. I just don't imagine it's easy to come up with a 
>> system like that, nor that it's easy to prove a mathematical problem is easy 
>> with the key and NP-hard without.
> 
>   One thing is certain: Creating a truly secure encryption system based on
> an NP-hard algorithm is far from trivial. For example, all of these are
> based on known NP-hard problems, yet can be cracked in a matter of weeks
> with some hundreds of computers:

Yeah. The basic problem is you *want* them to be crackable by someone with 
the key.  It's easy to make a system that can't be broken. It's hard to make 
a system that can't be broken *unless* you know some relatively small number 
of bits.

NP-Hard isn't difficult. NP-Hard with a private/public key is difficult. :-)

-- 
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'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
>
>    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).

http://en.wikipedia.org/wiki/P_versus_NP_problem#Claimed_solutions

...so I guess not then. :-(

Post a reply to this message