I'm not quite sure I follow all of your logic here. If you have shown that you have a polynomial algorithm that solves an NP-complete problem you have proven that P=NP. Your algorithm is the proof. P=NP iff there exists a polynomial time algorithm to solve an np-complete problem in polynomial time. There may be a way to prove it that doesn't imply an algorithm, but I'd be impressed if I saw it...
A problem is NP-complete iff it is in NP, and all problems in NP are polynomial reducable to it. Thus is you solve one NP-complete problem, you have polynomial solved any problem in NP. Now, the coefficients may be very large, especially when you start multiplying things together as you do reductions, and you're also probably increasing the size considerably (think of the reduction from 3-SAT, to 3 coloring), so it's not necessarily very convenient to do this.
P=NP, or P!=NP is an important theoretical result, as much as it is a practical one. In fact, it's probably very unlikely that we'd be able to find efficient algorithms to solve any of the NP-complete problems any time soon even if P=NP were proven. However it would mean that we not only have a polynomial solution to these problems, but also to the optomization versions -- the NP-Hard problems, which is more what we're worried about when we talk about things such as factoring numbers, or finding set-partitions. NP-complete problems are just decision (yes, no) problems. .
As far as proving it -- if you do it, go ahead and publish! It's an important theoretical result, probably far more important in theory than it is in practice for now. If people just hoarded their discoveries we'd never have seen the advancement in the area. Heck, if Cook hadn't released his work, we'd probably not be arguing about this now. . .
Technically you are confusing NP-complete problems and NP-Hard problems. An NP-Complete problem is a problem such that it given a solution it is polynomially variable, and all other problems in the class NP reduce polynomially to it. An NP complete problem is a decision problem -- we are looking at whether a clique of size k exists in a graph -- and looking for a yes/no answer. An NP-hard problem is the optomization part of that problem, actually finding the clique in the graph.
A polynomial solution to an NP-Hard problem, obviously implies a polynomial solution to an NP-Complete problem (eg. finding polynomially a set of variables that satisfy 3-SAT, solves 3-SAT), and similary a polynomial number of aplications of a solution to an NP-complete problem can solve a polynomial problem.
Yes, this assumes base 10. A more general, and easily provable (although I'm not going to include a proof here) rule is that in base b, b-1 divides the number iff b-1 divides the sum of the digits. If another number n divides b-1 then, n divides the sum of the digits as well. Similiary, b+1 divides the number iff if divides the alternating sum of the digits (in other words, in base 10 - 132 = 2-3+1 = 0, which is divisible by 11, so 132 is divisible by 11). Similary, numbers that divide b+1 have a similar property.
>How many revisions has even the stable kernel >gone through...
Both 3.9.16 and 2.2.12 were released in late august. That would mean that, what, 1 stable kernel has been released in that time? That's not all that much. Theres a lot being done in XF86 4.0, I'd prefer that it's done right -- even if it means waiting a bit longer.
Although, I have *really* wanted to see another snapshot of it, it's not been something that's bothered me.
Disturbing, but somewhat amusing. I have a friend who actually got a barcode tattoo. It didn't actually *scan* to anything, but he claimed, and convinced some rather gullible people, that it scanned to a box of tampons at walmart. It would be rather bizzarre to have actual information tattoed on you -- but considering some of the people who are out there some of them will probably want it done.
Or maybe mothers will get it done on their kids. You know, scan them to get their address in case they are lost.
Well, as some of the other RPI freshemen commented, we got one of these lovely models. I too strugled to get my network card working, and although it didn't take me as long to get it working as some were commenting, it wasn't a piece of cake, made for begginers, linux install. I'm glad I had a couple of years of linux experience coming in to this.
If IBM really does want this to work, they need to figure out someway to get the modem to work. That's really rather disgusting that it is a winmodem. I'm not sure how they can do it, but if they can, and they release there driver source, that'd go a long way of convincing me of their intentions. As it is, it seems like they are jumping on the word linux. I'm sure they intend for their computer to work on all linuxes, but they think that (RedHat == Linux) which it certainly isn't. While I have to dislike their misthought here, perhaps it will be the intention that counts.
Infact, in the end it will be the intention that counts. If they are latching on to this 'Linux' buzzword thing, then they will be remembered for that. If they are really wanting to help, that will show too. I certainly hope they do help. The instalation guide looked pretty decent, a lot like what mine looked like when I wrote one after getting it working on mine (so I could help my friends) but there is enough wrong with these laptops, that I worry about what IBM can do.
It sounds to me like a case of Microsoft trying to muscle linux (and other unixes) out of their network positions, as opposed to being a real 'Microsoft technical innovation.' MS is betting that they have the muscle and influence to push linux out of the small server operating system market, killing it before it really catches on as a desktop operating system.
Since use as servers happens to be Linux's big market niche, MS probably figures that if they can get rid of it there, it can be stopped from being an even more major threat to Microsofts larger home market in the future.
I got the feeling from reading all of the various help things with various kernel options when I was compiling my kernel that this was possible, through use of modprobe (and a kernel switch, somewhere.) Of course, I may be wrong as I'm not at my linux box now, and can't really check, but I *think* that this is possible.
The catch is, I'm not quite sure how. I'd start by going through the kernel module documentations, and maybe the man pages for modprode and the like. Of course, I could be way off here, so it's probably a good idea to see what other people have to say.
2.2.1 is by far the least stable kernel I've ever used. In the year I've run linux, it's crashed once -- and that was while using 2.2.1. Of course, that was probably because it was the first kernel I ever bothered to compile, and I'm pretty sure I managed to screw some option up somewhere.
I'm wondering if I should upgrade this time though. I usually have a nice t1 to download things on, but I only have a modem right now. I feel so technologically inferior. *sigh*
Slashdot Mirror
I'm not quite sure I follow all of your logic here. If you have shown that you have a polynomial algorithm that solves an NP-complete problem you have proven that P=NP. Your algorithm is the proof. P=NP iff there exists a polynomial time algorithm to solve an np-complete problem in polynomial time. There may be a way to prove it that doesn't imply an algorithm, but I'd be impressed if I saw it...
A problem is NP-complete iff it is in NP, and all problems in NP are polynomial reducable to it. Thus is you solve one NP-complete problem, you have polynomial solved any problem in NP. Now, the coefficients may be very large, especially when you start multiplying things together as you do reductions, and you're also probably increasing the size considerably (think of the reduction from 3-SAT, to 3 coloring), so it's not necessarily very convenient to do this.
P=NP, or P!=NP is an important theoretical result, as much as it is a practical one. In fact, it's probably very unlikely that we'd be able to find efficient algorithms to solve any of the NP-complete problems any time soon even if P=NP were proven. However it would mean that we not only have a polynomial solution to these problems, but also to the optomization versions -- the NP-Hard problems, which is more what we're worried about when we talk about things such as factoring numbers, or finding set-partitions. NP-complete problems are just decision (yes, no) problems. .
As far as proving it -- if you do it, go ahead and publish! It's an important theoretical result, probably far more important in theory than it is in practice for now. If people just hoarded their discoveries we'd never have seen the advancement in the area. Heck, if Cook hadn't released his work, we'd probably not be arguing about this now. . .
Technically you are confusing NP-complete problems and NP-Hard problems. An NP-Complete problem is a problem such that it given a solution it is polynomially variable, and all other problems in the class NP reduce polynomially to it. An NP complete problem is a decision problem -- we are looking at whether a clique of size k exists in a graph -- and looking for a yes/no answer. An NP-hard problem is the optomization part of that problem, actually finding the clique in the graph.
A polynomial solution to an NP-Hard problem, obviously implies a polynomial solution to an NP-Complete problem (eg. finding polynomially a set of variables that satisfy 3-SAT, solves 3-SAT), and similary a polynomial number of aplications of a solution to an NP-complete problem can solve a polynomial problem.
Yes, this assumes base 10. A more general, and easily provable (although I'm not going to include a proof here) rule is that in base b, b-1 divides the number iff b-1 divides the sum of the digits. If another number n divides b-1 then, n divides the sum of the digits as well. Similiary, b+1 divides the number iff if divides the alternating sum of the digits (in other words, in base 10 - 132 = 2-3+1 = 0, which is divisible by 11, so 132 is divisible by 11). Similary, numbers that divide b+1 have a similar property.
but I may be wrong. I do remember playing Catacombs, though. It was programmed by JC, just before id.
I think.
>How many revisions has even the stable kernel >gone through...
Both 3.9.16 and 2.2.12 were released in late august. That would mean that, what, 1 stable kernel has been released in that time? That's not all that much. Theres a lot being done in XF86 4.0, I'd prefer that it's done right -- even if it means waiting a bit longer.
Although, I have *really* wanted to see another snapshot of it, it's not been something that's bothered me.
Or maybe mothers will get it done on their kids. You know, scan them to get their address in case they are lost.
'If lost, send to ***TAMPON 24PK***'...
The future scares me.
If IBM really does want this to work, they need to figure out someway to get the modem to work. That's really rather disgusting that it is a winmodem. I'm not sure how they can do it, but if they can, and they release there driver source, that'd go a long way of convincing me of their intentions. As it is, it seems like they are jumping on the word linux. I'm sure they intend for their computer to work on all linuxes, but they think that (RedHat == Linux) which it certainly isn't. While I have to dislike their misthought here, perhaps it will be the intention that counts.
Infact, in the end it will be the intention that counts. If they are latching on to this 'Linux' buzzword thing, then they will be remembered for that. If they are really wanting to help, that will show too. I certainly hope they do help. The instalation guide looked pretty decent, a lot like what mine looked like when I wrote one after getting it working on mine (so I could help my friends) but there is enough wrong with these laptops, that I worry about what IBM can do.
Good luck, IBM. You're going to need it....
linuxy
hornp@rpi.edu
Since use as servers happens to be Linux's big market niche, MS probably figures that if they can get rid of it there, it can be stopped from being an even more major threat to Microsofts larger home market in the future.
Hopefully this will not work.
I got the feeling from reading all of the various help things with various kernel options when I was compiling my kernel that this was possible, through use of modprobe (and a kernel switch, somewhere.) Of course, I may be wrong as I'm not at my linux box now, and can't really check, but I *think* that this is possible.
The catch is, I'm not quite sure how. I'd start by going through the kernel module documentations, and maybe the man pages for modprode and the like. Of course, I could be way off here, so it's probably a good idea to see what other people have to say.
Hope that was a help...
Actually, there were a few scenes in The Little Mermaid. . .
But if that happened, it'd be an awfully short show. Intentional gaps of logic are part of what makes things like this funny.
2.2.1 is by far the least stable kernel I've ever used. In the year I've run linux, it's crashed once -- and that was while using 2.2.1. Of course, that was probably because it was the first kernel I ever bothered to compile, and I'm pretty sure I managed to screw some option up somewhere.
I'm wondering if I should upgrade this time though. I usually have a nice t1 to download things on, but I only have a modem right now. I feel so technologically inferior. *sigh*