Well, I'm not sure if you mean factorial or excitement with that exclaimation mark but either way thats much larger than the input size of the number. NOT THE CARDINALITY OF THE NUMBER.
i.e. if a number has n digits it won't be poly to that!
Firstly, you only need to check up to the square root of n as anything larger will not be a prime factor.
Secondly the algo you suggest is MUCH larger than n^k where n is the LENGTH OF THE INPUT NOT THE SIZE OF THE NUMBER!
a Proof is not rigorus if it depends on unproven theorems. There are many examples if theories that were thought to be true and were later proved to be false.
This proof relies on nothing more than a little abastract algebra, some number theory and good ole plain algebra..
So I'm already sensing the level of confusion rising as this is a very confusing topic. Here's a quick review. Note: I'm going to do this on a higher level and not start talking about Formal Languages as this is not the place to teach it.
So in loose terms, Problems that in P are easily solveable. For example, sorting is a problem in p. Proof: I can sort a set of n numbers in no worse than n^2 time using a bubble sort. (Yes - I know there's faster but this is an example). The bubble sort just compares every number to every other number. Assuming you didn't optimize the algorithm you'd compare each number to every other number and they'd be sorted in no worse than n*n = n^2 comparisons.
So what is NP? NP are problems that given a proposed solution we can verify that the solution is correct or not in polynomial time.
An example of this is factoring. (note: it is not known whether factoring is in P). Given current methods we know factoring a big number into its prime factors. But if I was to tell you that p=q*r you could very quickly multiply q*r and see if it is equal to p and "verify" my answer. Another way to think about it is you can try out one branch of computation in polynomial time.
So what is NP-complete? NP complete problems are is follows.
A problem is NP-Complete iff
1) The problem is in NP
2) A solution in polynomial time to this problem would yield a polynomial time solution to all other problems in NP. That is, no other problem in NP is harder than NP-Complete and if one NP-Complete problem is solveable in Polynomial time than all of NP is solveable in polynomail time, P=NP and you will win doctorates and a nobel prize, turing award and a million bucks from the clay institute for proving this.
Sigh - you are probally still confused..:)
On one side this makes sense from their perspective. International bandwidth from what I understand costs a bundle to provide and usually most of this cost is not picked up by the US which is generating most of the content to begin with. Europe I hear has similar problems with paying an arm and a leg for transatlanic traffic, etc. On the other hand this sets dangerous precedent. How can we expect the internet as we know it to stay free with this kind of scheme. The cost for these portals traffic is already built into the wholesale general cost of traffic that ISP's sell each other and eventually to the end user. It seems as if they just want to double dip on this access. Secondly how are content providers who already pay big $$$ for their pipes just to get their material out of their server farms start going to then start paying carrier fees as well. What we are going to end up with is the internet becoming like basic cable. You pay for a few channels here or there but if you want the premium channels you gotta start shelling out. This method of billing breaks the IP protocol as we know it. The net is supposed to be mostly blind to the traffic that it is throwing around. If routers stop universally moving traffic this is going to get ugly very quicky. Good bye univeral routing. hello pay tv internet.
At least when bnetD was sued there was some theoretical idea of a "copy righted" work that was being circumvented. What is HP going to do, claim that there OS's intelectual property is actually being protected by their lack of a bounds check in their buffer overflow? So when the next whole in outlook is discovered and microsoft doesn't want to do anything about if for 6months yet exploits are being found in the wild are they just gonna sue the script kiddies rather than spend the extra $$ to fix the stupid off by one error? This is silly and exactly the kind of abuses that the open source community has been clamoring about since the DMCA's inception!
What it basically comes down to is alot of people think its fun to play with comptuers and be script kiddies. not that many people have the dedication to go out and deal with the 4 years of challenging school work that is the CS degree (at least mine was; I ust graduated from UMass/cs...we have 400 undergrads and 50 grads a year...you do the math)
The one thing the internet has that prevents massive worm penetration is heterogenality. When nimbda came out it was windows boxes. This did not effect apache/*nix boxen. Suppose a virus were to come out next week that was exploited the recent apache bug (which requires a differnt exploit on each of the four operatings systems it was exploited for) this is not going to touch windows boxes. This is just an example but it applies acoss many other fields. He also seems to have little faith in the current measures which are in place. The barriers that are placed by firewalls, NAT/w virtual addresses, VPNs and a good security adminstrator can go a long way to protecting you aganist unknown threats which are lurking out there. None of these are perfect or guarntee security but theorizing that the internet is one virus away from a total meltdown is absurd.
which increases polynomially with respect to the number of points on the graph... classifying it as NP-Complete.
WHAT? This has nothing to do with NP-Completeness. A problem A is NP complete iff it is NP and for all problems B in NP, B can be reduced to to A in polynomial time. (this means you can convert any problem in NP to an NP-Complete problem in polynomial time and the solution to B can be determined by running an input on A)
So unless you can show this your claim about np completeness is complete bull.
>harsh restrictions of the BSD license. It also lacks >the GPLs requirement that anything coded with its >tools becomes property of the FSF.
You have this totally backwards. The GPL only says that if you modify the source code of a GPL program amd redistribute it - you must make the orginal code available to the end user. What you use a GPL'd piece of software for is up to you. Furthermore GPL'd software is NOT property of FSF unless you decide to give them those rights. otherwise the copyright is held by the orginal author.
For everybody who jumped on the bandwagon about the evil in the replacement dll for cydoor I went and did a little research..the code is distributed with the binary and all it is is the Cydoor SDK implemented except all the functions just do nothing or return 1.
(www.cydoor.com/sdk helped them out on this one)...
If your really that worried about this then just recompile the DLL on your own. The source is in www.cexx.com 's ZIP file of cl_clint.dll...
The only thing I've found is that the version of KaZaa I have crashes if I try to use the DLL althought I haven't tried compilig it myself yet...
They refer to this as the "AdWare Condom"
Hey, Why couldn't users contend that we had our computers changed/altered without our permission. The last time I checked that was still illegal. If we're not supposed to breaking into them - they should reciprocate and not break into us. By altering registry setting without asking, they have effectivly broken into my computer. Nothin better than a/. class action suit.
MB
Slashdot Mirror
Well, I'm not sure if you mean factorial or excitement with that exclaimation mark but either way thats much larger than the input size of the number. NOT THE CARDINALITY OF THE NUMBER. i.e. if a number has n digits it won't be poly to that!
Firstly, you only need to check up to the square root of n as anything larger will not be a prime factor. Secondly the algo you suggest is MUCH larger than n^k where n is the LENGTH OF THE INPUT NOT THE SIZE OF THE NUMBER!
a Proof is not rigorus if it depends on unproven theorems. There are many examples if theories that were thought to be true and were later proved to be false. This proof relies on nothing more than a little abastract algebra, some number theory and good ole plain algebra..
So I'm already sensing the level of confusion rising as this is a very confusing topic. Here's a quick review. Note: I'm going to do this on a higher level and not start talking about Formal Languages as this is not the place to teach it. So in loose terms, Problems that in P are easily solveable. For example, sorting is a problem in p. Proof: I can sort a set of n numbers in no worse than n^2 time using a bubble sort. (Yes - I know there's faster but this is an example). The bubble sort just compares every number to every other number. Assuming you didn't optimize the algorithm you'd compare each number to every other number and they'd be sorted in no worse than n*n = n^2 comparisons. So what is NP? NP are problems that given a proposed solution we can verify that the solution is correct or not in polynomial time. An example of this is factoring. (note: it is not known whether factoring is in P). Given current methods we know factoring a big number into its prime factors. But if I was to tell you that p=q*r you could very quickly multiply q*r and see if it is equal to p and "verify" my answer. Another way to think about it is you can try out one branch of computation in polynomial time. So what is NP-complete? NP complete problems are is follows. A problem is NP-Complete iff 1) The problem is in NP 2) A solution in polynomial time to this problem would yield a polynomial time solution to all other problems in NP. That is, no other problem in NP is harder than NP-Complete and if one NP-Complete problem is solveable in Polynomial time than all of NP is solveable in polynomail time, P=NP and you will win doctorates and a nobel prize, turing award and a million bucks from the clay institute for proving this. Sigh - you are probally still confused.. :)
..so fat that she's got smaller fat women in orbit around her.
On one side this makes sense from their perspective. International bandwidth from what I understand costs a bundle to provide and usually most of this cost is not picked up by the US which is generating most of the content to begin with. Europe I hear has similar problems with paying an arm and a leg for transatlanic traffic, etc. On the other hand this sets dangerous precedent. How can we expect the internet as we know it to stay free with this kind of scheme. The cost for these portals traffic is already built into the wholesale general cost of traffic that ISP's sell each other and eventually to the end user. It seems as if they just want to double dip on this access. Secondly how are content providers who already pay big $$$ for their pipes just to get their material out of their server farms start going to then start paying carrier fees as well. What we are going to end up with is the internet becoming like basic cable. You pay for a few channels here or there but if you want the premium channels you gotta start shelling out. This method of billing breaks the IP protocol as we know it. The net is supposed to be mostly blind to the traffic that it is throwing around. If routers stop universally moving traffic this is going to get ugly very quicky. Good bye univeral routing. hello pay tv internet.
At least when bnetD was sued there was some theoretical idea of a "copy righted" work that was being circumvented. What is HP going to do, claim that there OS's intelectual property is actually being protected by their lack of a bounds check in their buffer overflow? So when the next whole in outlook is discovered and microsoft doesn't want to do anything about if for 6months yet exploits are being found in the wild are they just gonna sue the script kiddies rather than spend the extra $$ to fix the stupid off by one error? This is silly and exactly the kind of abuses that the open source community has been clamoring about since the DMCA's inception!
What it basically comes down to is alot of people think its fun to play with comptuers and be script kiddies. not that many people have the dedication to go out and deal with the 4 years of challenging school work that is the CS degree (at least mine was; I ust graduated from UMass/cs...we have 400 undergrads and 50 grads a year...you do the math)
Your right - I never said I could spell. :)
The one thing the internet has that prevents massive worm penetration is heterogenality. When nimbda came out it was windows boxes. This did not effect apache/*nix boxen. Suppose a virus were to come out next week that was exploited the recent apache bug (which requires a differnt exploit on each of the four operatings systems it was exploited for) this is not going to touch windows boxes. This is just an example but it applies acoss many other fields. He also seems to have little faith in the current measures which are in place. The barriers that are placed by firewalls, NAT /w virtual addresses, VPNs and a good security adminstrator can go a long way to protecting you aganist unknown threats which are lurking out there. None of these are perfect or guarntee security but theorizing that the internet is one virus away from a total meltdown is absurd.
which increases polynomially with respect to the number of points on the graph ... classifying it as NP-Complete.
WHAT? This has nothing to do with NP-Completeness. A problem A is NP complete iff it is NP and for all problems B in NP, B can be reduced to to A in polynomial time. (this means you can convert any problem in NP to an NP-Complete problem in polynomial time and the solution to B can be determined by running an input on A)
So unless you can show this your claim about np completeness is complete bull.
>harsh restrictions of the BSD license. It also lacks >the GPLs requirement that anything coded with its >tools becomes property of the FSF. You have this totally backwards. The GPL only says that if you modify the source code of a GPL program amd redistribute it - you must make the orginal code available to the end user. What you use a GPL'd piece of software for is up to you. Furthermore GPL'd software is NOT property of FSF unless you decide to give them those rights. otherwise the copyright is held by the orginal author.
For everybody who jumped on the bandwagon about the evil in the replacement dll for cydoor I went and did a little research..the code is distributed with the binary and all it is is the Cydoor SDK implemented except all the functions just do nothing or return 1. (www.cydoor.com/sdk helped them out on this one)... If your really that worried about this then just recompile the DLL on your own. The source is in www.cexx.com 's ZIP file of cl_clint.dll... The only thing I've found is that the version of KaZaa I have crashes if I try to use the DLL althought I haven't tried compilig it myself yet... They refer to this as the "AdWare Condom"
Providers are protected as "common carriers". Much like the phone company can't be held responsible for a crime thats plotted over their phone lines.
A person who defends himself in court has a fool for a lawyer...
...Or will it get jelous of your wife and axe you to complete its mission? Behold HAL!
Hey, Why couldn't users contend that we had our computers changed/altered without our permission. The last time I checked that was still illegal. If we're not supposed to breaking into them - they should reciprocate and not break into us. By altering registry setting without asking, they have effectivly broken into my computer. Nothin better than a /. class action suit.
MB