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