I don't know, you seem to think factorization is in np-complete while rsa think it is in np-hard. I'm going to go with rsa.
I think no such thing, and neither do they.
Remember how my first response in this thread was that you had your definitions backwards? I'm saying factoring is NP-easy. Nobody who actually knows what they're talking about thinks its NP-hard.
A problem doesn't need to be hard to reduce it to SAT.
I had it exactly right. They cannot use a 3-sat solver on "does N have a nontrivial factor smaller than m?" because the latter is not in np-complete.
You can use a 3-sat solver on any problem in NP. It doesn't have to be NP complete.
An instance of "does N have a nontrivial factor smaller than m?" *trivially* turns into a circuit. The circuit is just a bunch of multipliers and an OR gate!
Next up, a circuit trivially turns into a boolean formula. I hope I don't need to spell out the equivalence.
Third, they take the resulting formula and plug it into the reduction from SAT to 3-SAT.
Fourth they plug said formula into their solver.
Nor can anyone with an np-complete solver trivially do that.
Take above steps, but replace reductions depending on exactly which problem the solver solves.
And yes, of course a legitimate proof implies that every problem in P is NP complete. That's obvious.
That's great. The fact you can use a solver for any problem in NP-complete to solve any problem in NP is even more obvious. It's why NP collapses to P if NP-complete is in P!
But it doesn't screw RSA because RSA security is based on the fact that an efficient algorithm for factoring integers is unknown, not that such doesn't exist
Security by obscurity, eh? Luckily, it's not a problem for a constructive proof that P=NP, since the reductions are all known.
This is one of those extraordinary-claims-require-extraordinary-evidence cases. "I tried random inputs" is not good enough. To take it seriously, those random inputs should correspond to hard problems -- for example, use this supposed 3-SAT solver on reductions from integer factoring to factor an RSA number.
And now for a new challenge, present us with a word with the exact same meaning as this "non-word" that can be swapped with it without altering the grammar, meaning or flow of the sentence.
And if those fans / heatsinks really made economic sense, then every server room in the world (from little offices up to large datacenters) would be using them.
They don't fit. The giant heatsinks and fans popular among overclockers would not fit in a 1U case, whereas noise in server rooms tends not to be a big deal so cases full of small loud fans are the norm.
To some students, it might be. Sadly enough I know someone who chose their undergraduate institution based on the ping times they got to their favorite gaming servers; he actually carried a notebook with him to each school he considered, and wrote down the ping times from each school to his favorite servers.
It's absurd to use it as the only criterion, but quality of internet connection is a perfectly reasonable thing to consider if you're going to be locked in to campus housing.
Encrypted files have maximum entropy, just like absolutely random files
Not true, unless you have a randomly generated key that is as long as the file. You cannot apply any deterministic process to inputs of limited entropy and expect to get output entropy that is strictly speaking (computational complexity wise) higher than the sum of the entropy of the inputs.
Strictly speaking you're correct, at least until you invoke computational complexity.
Distinguishing a string whose Kolmogorov complexity is 512 bits from one which is genuinely random is not possible, unless you have some sort of magic oracle for the halting problem. Even if you relax "deterministic process" to "deterministic polynomial time process" it's still (almost certainly) exponentially difficult.
You can make general purpose quantum computers if you have a working set of "quantum gates" or similar -- much like you can make a general purpose classical computer if you have a working set of classical gates.
I don't drink. But it's not because I'm a tightwad: I just hate the taste of alcohol. I can taste it in seemingly trace amounts in everything other than drinks with ridiculous amounts of sugar.
Yeah. Ethyl alcohol doesn't exactly taste good. That's one reason I prefer liquor when actually trying to get drunk -- you don't have to drink as much liquid with alcohol in it.
To some extent it is an acquired taste.
There is a smaller reason in that I've seen a lot of people, including friends, do... inadvisable things while drunk. The thought of not being in possession of my faculties and not being able to tell scares me.
In my experience it's not that bad. If you're worried I suggest experiments in a controlled setting until you get a good idea of what the effects of alcohol are on you. By golly, by the time I'm even thinking of doing inadvisable things I know I am not in possession of my faculties!
I also know I have a somewhat addictive personality. So on the whole, I think I'll continue to not drink booze.
This isn't a "barrier" like the "sound barrier". There are no special difficulties that start around 1G/sec! It's just a threshold.
Don't get me wrong -- I'm not saying this isn't impressive, but no "barrier" was broken here!
Re:What would the impacts of this be for cryptogra
on
Claimed Proof That P != NP
·
· Score: 2, Informative
I'm being thick here I guess, but why do we know the required simulation of Turing machines to be in NP=P (given assumption), and not EXPTIME or at least PSPACE?
The algorithm is: on iteration N, simulate one (more) step on Turing machines 1 through N. Stop when a machine outputs an answer with a formal proof that answer is correct.
If P = NP, then the M'th Turing Machine does this in P(n) steps. It takes P(n)+M iterations before that happens. Each iteration takes M+i steps, so the run time is O(P(n)^2), which is polynomial! (note that M is an "exponentially large" constant, so this approach wouldn't result in a truly usable algorithm.)
Re:What would the impacts of this be for cryptogra
on
Claimed Proof That P != NP
·
· Score: 2, Informative
If you show P=NP by constructing an algorithm which solves an NP-complete problem in polynomial time, you immediately have a polynomial time algorithm for *any* problem in NP. That's the definition of NP-complete: a language is NP complete if any other language in NP can be reduced to it in polynomial time.
Even if you provide a non-constructive "existence" proof, it turns out you can construct an (incredibly awful!) polynomial time algorithm by, essentially, a brute force simulation of turing machines -- so it's not actually possible to provide a truly non-constructive proof that P=NP.
If this proof holds up, then RSA and ECC become provably secure in a way they weren't before.
Breaking RSA and ECC are very strongly believed to NOT be NP hard. In particular, they are both "easy" enough to be solvable by a quantum computer, but quantum computers are almost certainly not powerful enough to solve NP-hard problems.
Note that Google shows 17.6M results for "just as soon", compared to 869K for "just assume" -- this perversion is perhaps becoming more common, but that's no reason to use it!
It’s short for I’d just assume to forget
Whatever retconning justification you want to apply, the origin of "just assume" is people mishearing "just as soon".
It's a bit of a stretch in any case. "just as soon forget" means "given the choice, I'd forget as soon as I would (whatever)". Assume just doesn't quite mean what it would need to mean for this construct to make sense. (Obviously it's close -- otherwise it wouldn't be common!)
and AFAIK it’s pretty much accepted grammar.
I think you're right to this extent -- if it made any sense to use "assume" here you would drop the "to".
"I'd just as soon [action]" is an idiom, as is "make a mountain out of a molehill"
It's not really a matter of grammar or syntax (although "I'd just assume forget" isn't proper grammar, as far as I can tell) -- it's closer to being an issue of spelling/pronunciation. You're slightly misspelling "I'd just as soon", and you're probably slightly mispronouncing it too.
I confused these two myself for a while -- it's understandable because "as soon [action]" isn't a common construct in modern English aside from this idiom.
Corporate testing as part of a 6 month study involving a large intelligence customer. But if you find Sun's blogs showing > 1GB/s sustained r/w, these blogs don't lie. Performance is confirmed. My guess is the difference lies in NetApp's use of a RAID-4 variant in order to record parity.
C//
Ultimately that sort of throughput number is CPU bound -- if it weren't, it could be improved by adding more disks.
Actually, WAFL's RAID-4/RAID-DP (with parity on separate disks) is just fine in a copy-on-write context. Distributing parity across the disks (ala RAID-5) primarily helps for random-small-write workloads. WAFL style filesystems don't *have* random small writes! Random writes become sequential writes, because the filesystem is free to choose where they go.
Slashdot Mirror
A problem doesn't need to be hard to reduce it to SAT.
And also note that you don't need to be able to reduce SAT to a problem for it to be hard!
Factoring is almost certainly easier than SAT but harder than anything in P.
I don't know, you seem to think factorization is in np-complete while rsa think it is in np-hard. I'm going to go with rsa.
I think no such thing, and neither do they.
Remember how my first response in this thread was that you had your definitions backwards? I'm saying factoring is NP-easy. Nobody who actually knows what they're talking about thinks its NP-hard.
A problem doesn't need to be hard to reduce it to SAT.
I had it exactly right. They cannot use a 3-sat solver on "does N have a nontrivial factor smaller than m?" because the latter is not in np-complete.
You can use a 3-sat solver on any problem in NP. It doesn't have to be NP complete.
An instance of "does N have a nontrivial factor smaller than m?" *trivially* turns into a circuit. The circuit is just a bunch of multipliers and an OR gate!
Next up, a circuit trivially turns into a boolean formula. I hope I don't need to spell out the equivalence.
Third, they take the resulting formula and plug it into the reduction from SAT to 3-SAT.
Fourth they plug said formula into their solver.
Nor can anyone with an np-complete solver trivially do that.
Take above steps, but replace reductions depending on exactly which problem the solver solves.
And yes, of course a legitimate proof implies that every problem in P is NP complete. That's obvious.
That's great. The fact you can use a solver for any problem in NP-complete to solve any problem in NP is even more obvious. It's why NP collapses to P if NP-complete is in P!
But it doesn't screw RSA because RSA security is based on the fact that an efficient algorithm for factoring integers is unknown, not that such doesn't exist
Security by obscurity, eh? Luckily, it's not a problem for a constructive proof that P=NP, since the reductions are all known.
Integer factorization is not (yet) np-complete, so technically no one can do what you are asking
You've got it backwards. A problem being NP-complete means you can reduce any problem in NP to it.
The problem "does N have a nontrivial factor smaller than m?" is in NP. A solver for that can easily be used to factor integers.
even if they have a legitimate proof of p=np.
Technically speaking, a legitimate proof that P=NP implies that every problem in P is NP complete.
What we're talking about is not proofs but rather unproven algorithms which seem to scale because they aren't run on hard inputs.
The proof is that there is no proof.
This is one of those extraordinary-claims-require-extraordinary-evidence cases. "I tried random inputs" is not good enough. To take it seriously, those random inputs should correspond to hard problems -- for example, use this supposed 3-SAT solver on reductions from integer factoring to factor an RSA number.
And now for a new challenge, present us with a word with the exact same meaning as this "non-word" that can be swapped with it without altering the grammar, meaning or flow of the sentence.
Customizability.
There's no realistic way of collecting 30-ish countries, most with a distinct language and culture compared to the rest, as a single nation.
You mean like India?
That works until you actually want to read something -- keeping in mind that modern IMEs make it no harder to enter kanji than to read them.
if I weigh myself in kilos
You just used the very colloquial definition of weight that you've been rallying against.
I would weigh the same number of kilos no matter where I weighed myself in the universe. It isn't so with pounds, practical or not.
The units aren't the issue. The number of pounds necessary to accelerate me 32 feet per second^2 does not depend on my being on Earth's surface!
And if those fans / heatsinks really made economic sense, then every server room in the world (from little offices up to large datacenters) would be using them.
They don't fit. The giant heatsinks and fans popular among overclockers would not fit in a 1U case, whereas noise in server rooms tends not to be a big deal so cases full of small loud fans are the norm.
Cite? What exactly is the difference between "public" and "kernel"?
If all processes see the same 1G the distinction isn't meaningful, especially in this context.
To some students, it might be. Sadly enough I know someone who chose their undergraduate institution based on the ping times they got to their favorite gaming servers; he actually carried a notebook with him to each school he considered, and wrote down the ping times from each school to his favorite servers.
It's absurd to use it as the only criterion, but quality of internet connection is a perfectly reasonable thing to consider if you're going to be locked in to campus housing.
This is news for nerds. We all know what absolute zero is.
To be clear, I'm perfectly aware that there are issues with AES. I was just taking issue with the assertion that no such functions exist!
Encrypted files have maximum entropy, just like absolutely random files
Not true, unless you have a randomly generated key that is as long as the file. You cannot apply any deterministic process to inputs of limited entropy and expect to get output entropy that is strictly speaking (computational complexity wise) higher than the sum of the entropy of the inputs.
Strictly speaking you're correct, at least until you invoke computational complexity.
Distinguishing a string whose Kolmogorov complexity is 512 bits from one which is genuinely random is not possible, unless you have some sort of magic oracle for the halting problem. Even if you relax "deterministic process" to "deterministic polynomial time process" it's still (almost certainly) exponentially difficult.
You can make general purpose quantum computers if you have a working set of "quantum gates" or similar -- much like you can make a general purpose classical computer if you have a working set of classical gates.
I don't drink. But it's not because I'm a tightwad: I just hate the taste of alcohol. I can taste it in seemingly trace amounts in everything other than drinks with ridiculous amounts of sugar.
Yeah. Ethyl alcohol doesn't exactly taste good. That's one reason I prefer liquor when actually trying to get drunk -- you don't have to drink as much liquid with alcohol in it.
To some extent it is an acquired taste.
There is a smaller reason in that I've seen a lot of people, including friends, do... inadvisable things while drunk. The thought of not being in possession of my faculties and not being able to tell scares me.
In my experience it's not that bad. If you're worried I suggest experiments in a controlled setting until you get a good idea of what the effects of alcohol are on you. By golly, by the time I'm even thinking of doing inadvisable things I know I am not in possession of my faculties!
I also know I have a somewhat addictive personality. So on the whole, I think I'll continue to not drink booze.
That might be a good reason.
This isn't a "barrier" like the "sound barrier". There are no special difficulties that start around 1G/sec! It's just a threshold.
Don't get me wrong -- I'm not saying this isn't impressive, but no "barrier" was broken here!
I'm being thick here I guess, but why do we know the required simulation of Turing machines to be in NP=P (given assumption), and not EXPTIME or at least PSPACE?
The algorithm is: on iteration N, simulate one (more) step on Turing machines 1 through N. Stop when a machine outputs an answer with a formal proof that answer is correct.
If P = NP, then the M'th Turing Machine does this in P(n) steps. It takes P(n)+M iterations before that happens. Each iteration takes M+i steps, so the run time is O(P(n)^2), which is polynomial! (note that M is an "exponentially large" constant, so this approach wouldn't result in a truly usable algorithm.)
If you show P=NP by constructing an algorithm which solves an NP-complete problem in polynomial time, you immediately have a polynomial time algorithm for *any* problem in NP. That's the definition of NP-complete: a language is NP complete if any other language in NP can be reduced to it in polynomial time.
Even if you provide a non-constructive "existence" proof, it turns out you can construct an (incredibly awful!) polynomial time algorithm by, essentially, a brute force simulation of turing machines -- so it's not actually possible to provide a truly non-constructive proof that P=NP.
If this proof holds up, then RSA and ECC become provably secure in a way they weren't before.
Breaking RSA and ECC are very strongly believed to NOT be NP hard. In particular, they are both "easy" enough to be solvable by a quantum computer, but quantum computers are almost certainly not powerful enough to solve NP-hard problems.
Note that Google shows 17.6M results for "just as soon", compared to 869K for "just assume" -- this perversion is perhaps becoming more common, but that's no reason to use it!
It’s short for I’d just assume to forget
Whatever retconning justification you want to apply, the origin of "just assume" is people mishearing "just as soon".
It's a bit of a stretch in any case. "just as soon forget" means "given the choice, I'd forget as soon as I would (whatever)". Assume just doesn't quite mean what it would need to mean for this construct to make sense. (Obviously it's close -- otherwise it wouldn't be common!)
and AFAIK it’s pretty much accepted grammar.
I think you're right to this extent -- if it made any sense to use "assume" here you would drop the "to".
"I'd just as soon [action]" is an idiom, as is "make a mountain out of a molehill"
It's not really a matter of grammar or syntax (although "I'd just assume forget" isn't proper grammar, as far as I can tell) -- it's closer to being an issue of spelling/pronunciation. You're slightly misspelling "I'd just as soon", and you're probably slightly mispronouncing it too.
I confused these two myself for a while -- it's understandable because "as soon [action]" isn't a common construct in modern English aside from this idiom.
Corporate testing as part of a 6 month study involving a large intelligence customer. But if you find Sun's blogs showing > 1GB/s sustained r/w, these blogs don't lie. Performance is confirmed. My guess is the difference lies in NetApp's use of a RAID-4 variant in order to record parity.
C//
Ultimately that sort of throughput number is CPU bound -- if it weren't, it could be improved by adding more disks.
Actually, WAFL's RAID-4/RAID-DP (with parity on separate disks) is just fine in a copy-on-write context. Distributing parity across the disks (ala RAID-5) primarily helps for random-small-write workloads. WAFL style filesystems don't *have* random small writes! Random writes become sequential writes, because the filesystem is free to choose where they go.
ZFS has a lot of promise, but does not have nearly the performance that WAFL does
WTF? A 7310, the low end Open Storage appliance, will TOAST a 3170. A 3170 can't even touch it.
C//
[citation needed]