Advogato is on the slow end of a DSL. I was hoping that when it got slashdotted, somebody would put up a mirror. Oh well. I'll see what I can do to nurse the machine through the day.
$1,040,000,000 for this? News for crackpots, stuff that really doesn't matter at all.
I want something better. I've got the domain "cluedot.{org,net,com}". I've got collaborative filtering technology, implemented on Advogato that might just solve the problem of miniscule S/N ratios. I just don't have the time myself to put it into production right now, as I'm too busy developing free software projects. Anyone?
Yes, yes, I know. Troll, Offtopic, Flamebait, whatever. Karma be damned, I'm pissed off to see a site that used to be my kind of news site indulge in such stupid crap.
This should be "clients can drive the parsing process instead of the parser taking control." This is really cool when you're trying to parse XML and HTML streams from potentially blocking input streams, such as the network. Props to DV for doing this!
Yes, the trick of using shift-and-add to do multiplies is well known. Yes, using it in the context of a FFT (or DCT, as in this case) is obvious. But that's not what they've done here.
It looks to me like they've invented (or discovered) a new transform which is similar to the DCT, and shares many properties with the DCT, but is not simply an approximate DCT. In other words, you'd use this for designing a new video coder in which high processing speed is more important than compression ratio (they take about a 1dB hit in compression, my brain is too fuzzy convert this into percent right now).
The transform has some other interesting properties, such as the fact that the transform and its inverse are in fact exact even when you use limited-precision arithmetic, unlike DCT. This would seem to imply that repeatedly compressing and decompressing aren't going to lead to any quality degradation. Also, it might make for a more efficient lossless coder. Neither of these is a very big deal, but still interesting.
So it looks like what we have is something new, interesting, and primarily useful for video compression in hardware. I don't see a compelling reason why it shouldn't be patentable, and it certainly seems well within the scope of what the current patent system allows. Believe me, I've seen far worse in issued patents.
Lest you think I'm defending the patent system, I'm not. It's badly in need of reform. A very large fraction of issued software patents are simply bad patents. I actually believe that no software patents at all would be better than the current system, although I'm idealistic enough to hope that fixing the patent system to prevent abuses would be even better. I'm just saying that if you're going to pick on an invention, choose a better scapegoat than this one.
Finally, a shameless plug: since the discussion of patents and intellectual property on Slashdot seems to be as misinformed as it is lively, one of the explicit goals for my new site, Advogato is to host intelligent discussion of these issues. From the discussion so far, I have reason to be encouraged.
From this quote in the S-1, it looks like there's going to be another friends and family program for open source developers. Kudos to them for being upfront and stating clearly that 5% is set aside for this.
Directed Share Program. At our request, the underwriters have reserved for sale, at the initial public offering price, up to ten percent of the shares of common stock offered in this offering under a directed share program. We currently expect that approximately half of these shares will be offered to directors, officers, employees, business associates, and related persons of Caldera Systems pursuant to a directed share program being administered by FleetBoston Robertson Stephens Inc., and that approximately half of these shares, pursuant to a directed share program being administered by Wit Capital Corporation, will be offered to open source software developers and other persons that we believe have contributed to the success of the open source software community and to the growth of Caldera Systems. We cannot assure you that any of the reserved shares will be so purchased. The number of shares of common stock available for sale to the general public in this offering will be reduced by the number of reserved shares sold. Any reserved shares not purchased will be offered to the general public on the same basis as the other shares offered in this offering.
Roblimo, if I understand what you're saying, you understood that this piece was stupid and wrong when you posted it, but you posted it anyway, possibly in the hope of stirring up controversy?
It seems to me that Slashdot quite frequently posts articles with a controversy-inducing spin. The Gnome Napster article was one such case where I was involved. The hydrino one was another. "Crank or earth-shattering science?" How about just another scam artist who is good at exploiting people's desire to believe.
I've noticed that wrong and stupid posts often get a lot more response than well-written, balanced ones. In the former case, people have a great urge to write in and correct the original post. Some of these corrections are sensible, but by Sturgeon's Law, most are themselves pretty bogus. Presto! Instant controversy. After a well written article, people tend to be content.
So I think there is a danger that interesting and important stories are getting lost in the noise. I like the volume and rough-and-tumble nature of slashdot, but I for one would prefer a forum in which accuracy and footwork counted for something.
ObOnTopic: anyone know the status of the Linux port to the PlayStation II?
There's an enlightening discussion of JPEG2000 in the gimp-devel archives. See the or iginal question posted 9 Dec 1999, as well as the followup, particularly th is reply by Nick Lamb.
I nominate Advogato for best open source advocate. While the better-known open source advocates have been racking up major publicity points for themselves and doing the impossibly hard work of selling big business the idea of software that doesn't cost them anything, Advogato has been working for the most part quietly to help the community of open source developers, the people who actually write all this code the rest of you are so fond of evangelizing.
P.S. The rules said nothing about nominations not being allowed to be self-serving:)
Since the comparison in the EE times article is so useless, I decided to do my own testing. I started with the JPEG2000 applet on the NexImage site, and the example they gave there.
I found that the comparison on their site was biased rather strongly in favor of JPEG2000, in two ways. First, their JPEG encoding for comparison was notably inferior to libjpeg 6b with Huffman table optimization. Second, the comparison at very high compression ratios is not particularly meaningful. When compressing at 96:1, there is virtually no image detail present above half the original image resolution. Thus, scaling the original image down prior to compression (the usual practice with JPEG images) produces good results with standard JPEG.
When these biases are removed, the quality gap between JPEG2000 and JPEG narrows substantially. JPEG2000 is somewhat better, most noticeably in its relative lack of chroma bleeding, but the margin is quite slim. My recommendation is to make up the difference by using a little more bandwidth and/or storage.
I've prepared a summary of these results, with example images, on a comparison page. The page is on the slow side of a DSL, so please be gentle:)
The comparison in the EE times article is rigged to the point of almost being faked.
Basically, what they did is take a high resolution image and compress the shit out of it with both original JPEG and JPEG2000. Yes, JPEG does poorly at such high compression ratios.
What they neglected to point out, however, is that you can get excellent results from just shrinking the image. From what I can tell, the test image is displayed as a GIF shrunk 3x from the original "3 MB" image. A very reasonable thing to do, if you want a 19k target file size, would be to first shrink the image 3x, then compress it 17:1 using plain JPEG. I tried this, and got results entirely comparable to the JPEG2000 example (the problem with my informal test is that the GIF dithering artifacts are noticeably softened, which is basically a problem with the fact that they presented the image as a GIF instead of true color).
So the bottom line is that JPEG2000 performs a lot better if you're doing something stupid with it, but take the claims of dramatically better compression with a grain of salt.
Here's a relevant quote from the slashdot discussion on April 23, posted by Frank Warmerdam:
Folks... I contacted Tom Lane of the Indpendent JPEG Group and he says:
Nothing is happening within IJG; we are waiting to see what emerges from the ISO JPEG committee, and in particular whether it is (a) patent-free and (b) enough better than JPEG-1 to be worth a universal upgrade cycle.
On point (a), I have made my views quite clear to the JPEG committee, but I dunno whether they are listening. There will not be an IJG implementation of JPEG-2000 unless it is freely distributable and freely usable under essentially the same restrictions (ie, none to speak of) as our current code. Patent licenses are a show-stopper. But from what I've heard, all the proposals before the committee have some amount of patent encrustation.
On point (b), the poor track record of progressive JPEG has left me unenthused about pushing incompatible standards that offer only marginal or special-purpose improvements. JPEG-1 took the world by storm because it was an order of magnitude better than anything else available. Unless JPEG-2000 is that much better again, it faces at best an agonizing uphill fight; the world might be better off without the ensuing confusion. (I have not heard anything about what performance improvements they actually expect to get... but I am suspicious that we are going to see percentage points, not integer factors.)
So, I'm waiting and watching.
Maybe I'm just being too cynical, but I think that one of the major points of the JPEG2000 effort is to fix the "bug" in the original JPEG (or at least the universally implemented arithmetic coding-free subset) is patent free.
And basically, I agree with Tom's assessment here. While JPEG is far from perfect, it is "good enough" for photographic images, and the massive increases in bandwidth and storage capacity kinda make high compression ratios irrelevant.
Finally, a 200:1 compression ration is pretty meaningless without some kind of context. A much more meaningful comparison is how many bytes are required to get the same quality image as some other compression standard, such as the original JPEG. The figure itself reminds me of when Triada was hyping their 200:1 lossless compression. Joe Bugajski gave a talk on this at Berkeley, and started waxing raphsodic on the incredible stuff that the Library of Congress had in their collection. Books and audio materials were fine, but when he got to the Stradivarius violins, my fellow grad students just broke up laughing. It's not hard to imagine 200:1 compression of that, but uncompression is tricky at best:)
It doesn't take any deep knowledge of physics to come to the conclusion that this is a fraud. If it were real, it would be really fucking obvious. I can think of a few really clean experiments just off the top of my head (I mean, don't you'd think you'd be able to notice if the hydrino gas failed to react with oxygen?).
One of the more interesting things are the "independent" results that blacklightpower got done for them. Anyone else reminded of Mindcraft?
Re:english translation of the interview
on
RMS The Coder
·
· Score: 2
And "substantiate" should have been "instantiate".
Ok, this comment has a lot of inaccuracies. Let me try to clarify.
NP stands for "nondeterministic polynomial", and is probably most easily understood as the class of problems for which the solution can be verified in polynomial time. It includes P, the class of problems that can be solved in polynomial time.
A nice example of a problem that is in NP but not known to be in P is satisfiability. This problem is given as a list of predicates of the form (x1 or x2 or not x3). The problem is finding a set of xi such that all of the predicates are satisfied.
So, it should be obvious that you can verify a solution in polynomial time - just start with the values of xi and check that all the predicates turn out true. However, there is no known general technique for solving this problem than enumerating all the possibilities, which takes exponential time.
NP-completeness takes this idea one step further. It is a large an interesting class of problems that are basically equivalent in difficulty. If you solve one, you've solved them all. Thus, if a problem is NP-complete, there's no known efficient algorithm.
The way people analyze NP completeness is do define reductions, ie show how instances of one problem can be reduced into instances of another NP-complete problem, and vice versa. Maybe this takes "highly advanced skills," but it's actually fairly routine for algorithmicists.
The class of NP-complete problems includes the travelling salesman problem, the Hamiltonian path problem, the knapsack problem, determining collisions of 3D objects, and many others.
NP-hardness is when you can reduce an NP-complete problem into the NP-hard problem, but not necessarily vice versa. Many integer optimization problems are NP-hard.
Factoring is clearly NP, but is not known to be NP-hard. It's entirely plausible that someone (Arjen Lenstra, for example) will come up with a polynomial factoring algorithm, but leave the rest of the NP pantheon untouched.
There are some crypto algorithms that are based on NP-completeness, but NP-completeness is not in and of itself enough for strong crypto. Even if the problem is hard in general, a specific instance may be easy to solve. Unless you can prove that this never happens, you're hosed. IBM has done some excellent work in this direction with randomized self-reductions for their lattice-based crypto algorithm.
Complexity theory is one of the most beautiful areas in computer science, and NP-completeness is one of the most striking results, as it illuminates a fundamental unity across many seemingly disparate subfields of computer science. It is indeed a shame that this book skimps on its coverage of NP-completeness.
I am one of the Gnomers who has been following this issue, and was also present at one of the irc conversations with the Napster people. I've done a little writeup of the events, which I'm hoping will help set the record straight.
The writeup is here, posted on Advogato. As usual, anyone can read, but posting is restricting to free software developers.
First, let me add my voice to those who say that Slashdot's patent stories could use a clue or two. These sensationalistic headlines don't help anybody. I'll be adding a patent section to Advogato soon, and it's my hope that this will become a good place for informed discussion of patents relating to free software.
When you analyze a patent, the most important thing to look at is the claims. The abstract has little or no legal force, it's just there to help people searching (it's on the front page of paper patents, which was important back in the days when people searched through stacks of them:). The language of the claims has to be read in the context of the disclosure of the patent, and to really do it right, you have to read the file history too.
That said, this is another example of the US Patent and Trademark Office screwing up royally. Claim 1 covers a pretty generic computation load-sharing system - a central computer keeping track of a bunch of tasks, sending a start message to a remote computer to ask it to take the task, and the remote computer sending a complete message back to the server.
The problem here is that there is prior art up the wazoo. I'm sure experts in the field could come up with more, but just about any operating system with process migration, such as Sprite should do. The main work on this project was all done in the early '90s, plenty of time to serve as prior art.
The disclosure doesn't help the case. It talks about the types of tasks to be distributed in extraordinarily vague terms, so much so as to not make much sense. Compressing MPEG's remotely? Are they on crack? Even a 320x200 at 30fps is over 5 megabytes per second of raw data. And of course serving up web pages is fraught with problems, such as latency, security, admin costs, reliability, and so on. The patent does not so much as mention these problems, let alone propose a reasonable method of dealing with them.
So what do you do when you have such a crappy patent? I think a reasonable thing for free software authors to do is ignore it. In theory, Intel could bring suit against a free software project for violating this patent. However, in that case it seems likely to me that we'd be able to get a good pro bono legal team together, and the patent would almost certainly be overturned.
In the meantime, I think our best option is to keep well informed about patents in general, and about specific patents that may be relevant. Shallow, "golly gee-whiz, look at the patent they just got on breathing" stories don't help much.
They do plan to open-source the tools used to build the site. From their FAQ:
If you just like our tools so much that you want to use them, then go ahead. We'll be releasing many of them as Open Source soon. If this prospect overwhelms you, then contact VA Linux Professional Services, they'll be glad to help you. (Shameless plug for our sponsors.)
This is in response to a question about whether the site can be used for non-open source projects.
While we're on the subject of free resources for open source/free software developers, I would like ot take this opportunity to shamelessly plug Advogato, a new site I'm launching.
Advogato is an advocate for free software developers, as opposed to free software users or free software businesses. The main features now are a Slashdot-style news flow and a cool diary server.
One of the central features is an implementation of the peer certification work I'm doing for my PhD research. The site uses a group trust metric to determine membership in the community of free software developers. Only members can post, which is my crack at the S/N problem.
If you are a free software developer, you are warmly invited to join, poke around, and participate. Others are welcome to poke around.
ObOnTopic: From a look over their site, SourceForge looks impressive as hell. With VA's backing, they inspire quite a bit of confidence that they'll be able to handle the load. This can only be of benefit to Linux, free software in general, and of course VA.
This week's editorial on Advogato has some more discussion of Linus's talk, from the specific viewpoint of free software developers.
Everyone is welcome to read, but Advogato limits posting to members of the free software development community. It's my hope that this will make Advogato a more useful resource for developers.
I am not a lawyer, although I've been known to play one in my consulting fees.
Slashdot ran an excellent article on the basics of patent law a few weeks ago. It's reposted on Advogato, the new community site I'm starting for free software developers. I'm hoping to collect a solid set of patent resources at Advogato over time, among other things.
Wow, thanks very much. Slashdot really came through for me, and it was even an Anonymous Coward! All you AC-dissers, put that in your pipe and smoke it.
I was thinking that the theme is a little difficult for young kids. My son is 3.5 now, it will probably be a while before I recommend it to him.
Offtopicish: seeking books from my childhood
on
5 Novels
·
· Score: 1
Reading this, I am reminded of a low-intensity quest of mine, which is seeking two books that I remember reading as a child, but which nobody seems to know about today. Perhaps posting this query on Slashdot will finally bring a resolution to the quest.
The first book is about a boy named "Stark" who is sent to live with his uncle. The book is full of Xanth-like puns (when I first came across the Xanth books, I thought I might have found it), such as a pomegrenade tree that you really don't want to sit under, as the fruits have a tendency to blow up. I don't remember much of the plot, but if you've read the book, hopefully you can recognize it from this.
The second book is about two brothers who die early in the book and spend most of the book exploring two afterlife worlds. I recall that the older boy dies first while cushioning the fall of the younger one. Again, I don't remember much of the plot of the book, but the landscapes portrayed in the book were quite compelling.
I think I was eight or so when I read these. Any help tracking them down would be appreciated.
Strangely, I found out about this yesterday, when I followed the lwn link to the FreeGIS web site newly created by Jan-Oliver Wagner in Germany.
This site has links to a number of other interesting free software GIS packages, as well as a couple of sources of data.
It is my hope that a real free GIS community will develop. I have a personal interest in this, as I think my libart 2D graphics rendering library has the potential to render maps at a much higher quality than most proprietary GIS packages today (i.e. antialiasing, semi-transparent layers, combining vector with image data). If there's anyone who's interested in integrating libart's cool rendering capabilities with the cool free software GIS apps, both current and future, please get in touch.
Slashdot Mirror
Advogato is on the slow end of a DSL. I was hoping that when it got slashdotted, somebody would put up a mirror. Oh well. I'll see what I can do to nurse the machine through the day.
$1,040,000,000 for this? News for crackpots, stuff that really doesn't matter at all.
I want something better. I've got the domain "cluedot.{org,net,com}". I've got collaborative filtering technology, implemented on Advogato that might just solve the problem of miniscule S/N ratios. I just don't have the time myself to put it into production right now, as I'm too busy developing free software projects. Anyone?
Yes, yes, I know. Troll, Offtopic, Flamebait, whatever. Karma be damned, I'm pissed off to see a site that used to be my kind of news site indulge in such stupid crap.
2^n++ * 0.01 cents for you.
This should be "clients can drive the parsing process instead of the parser taking control." This is really cool when you're trying to parse XML and HTML streams from potentially blocking input streams, such as the network. Props to DV for doing this!
This looks like a case of yas/.spa.
Yes, the trick of using shift-and-add to do multiplies is well known. Yes, using it in the context of a FFT (or DCT, as in this case) is obvious. But that's not what they've done here.
It looks to me like they've invented (or discovered) a new transform which is similar to the DCT, and shares many properties with the DCT, but is not simply an approximate DCT. In other words, you'd use this for designing a new video coder in which high processing speed is more important than compression ratio (they take about a 1dB hit in compression, my brain is too fuzzy convert this into percent right now).
The transform has some other interesting properties, such as the fact that the transform and its inverse are in fact exact even when you use limited-precision arithmetic, unlike DCT. This would seem to imply that repeatedly compressing and decompressing aren't going to lead to any quality degradation. Also, it might make for a more efficient lossless coder. Neither of these is a very big deal, but still interesting.
So it looks like what we have is something new, interesting, and primarily useful for video compression in hardware. I don't see a compelling reason why it shouldn't be patentable, and it certainly seems well within the scope of what the current patent system allows. Believe me, I've seen far worse in issued patents.
Lest you think I'm defending the patent system, I'm not. It's badly in need of reform. A very large fraction of issued software patents are simply bad patents. I actually believe that no software patents at all would be better than the current system, although I'm idealistic enough to hope that fixing the patent system to prevent abuses would be even better. I'm just saying that if you're going to pick on an invention, choose a better scapegoat than this one.
Finally, a shameless plug: since the discussion of patents and intellectual property on Slashdot seems to be as misinformed as it is lively, one of the explicit goals for my new site, Advogato is to host intelligent discussion of these issues. From the discussion so far, I have reason to be encouraged.
Roblimo, if I understand what you're saying, you understood that this piece was stupid and wrong when you posted it, but you posted it anyway, possibly in the hope of stirring up controversy?
It seems to me that Slashdot quite frequently posts articles with a controversy-inducing spin. The Gnome Napster article was one such case where I was involved. The hydrino one was another. "Crank or earth-shattering science?" How about just another scam artist who is good at exploiting people's desire to believe.
I've noticed that wrong and stupid posts often get a lot more response than well-written, balanced ones. In the former case, people have a great urge to write in and correct the original post. Some of these corrections are sensible, but by Sturgeon's Law, most are themselves pretty bogus. Presto! Instant controversy. After a well written article, people tend to be content.
So I think there is a danger that interesting and important stories are getting lost in the noise. I like the volume and rough-and-tumble nature of slashdot, but I for one would prefer a forum in which accuracy and footwork counted for something.
ObOnTopic: anyone know the status of the Linux port to the PlayStation II?
There's an enlightening discussion of JPEG2000 in the gimp-devel archives. See the or iginal question posted 9 Dec 1999, as well as the followup, particularly th is reply by Nick Lamb.
I nominate Advogato for best open source advocate. While the better-known open source advocates have been racking up major publicity points for themselves and doing the impossibly hard work of selling big business the idea of software that doesn't cost them anything, Advogato has been working for the most part quietly to help the community of open source developers, the people who actually write all this code the rest of you are so fond of evangelizing.
:)
P.S. The rules said nothing about nominations not being allowed to be self-serving
Since the comparison in the EE times article is so useless, I decided to do my own testing. I started with the JPEG2000 applet on the NexImage site, and the example they gave there.
:)
I found that the comparison on their site was biased rather strongly in favor of JPEG2000, in two ways. First, their JPEG encoding for comparison was notably inferior to libjpeg 6b with Huffman table optimization. Second, the comparison at very high compression ratios is not particularly meaningful. When compressing at 96:1, there is virtually no image detail present above half the original image resolution. Thus, scaling the original image down prior to compression (the usual practice with JPEG images) produces good results with standard JPEG.
When these biases are removed, the quality gap between JPEG2000 and JPEG narrows substantially. JPEG2000 is somewhat better, most noticeably in its relative lack of chroma bleeding, but the margin is quite slim. My recommendation is to make up the difference by using a little more bandwidth and/or storage.
I've prepared a summary of these results, with example images, on a comparison page. The page is on the slow side of a DSL, so please be gentle
The comparison in the EE times article is rigged to the point of almost being faked.
Basically, what they did is take a high resolution image and compress the shit out of it with both original JPEG and JPEG2000. Yes, JPEG does poorly at such high compression ratios.
What they neglected to point out, however, is that you can get excellent results from just shrinking the image. From what I can tell, the test image is displayed as a GIF shrunk 3x from the original "3 MB" image. A very reasonable thing to do, if you want a 19k target file size, would be to first shrink the image 3x, then compress it 17:1 using plain JPEG. I tried this, and got results entirely comparable to the JPEG2000 example (the problem with my informal test is that the GIF dithering artifacts are noticeably softened, which is basically a problem with the fact that they presented the image as a GIF instead of true color).
So the bottom line is that JPEG2000 performs a lot better if you're doing something stupid with it, but take the claims of dramatically better compression with a grain of salt.
Maybe I'm just being too cynical, but I think that one of the major points of the JPEG2000 effort is to fix the "bug" in the original JPEG (or at least the universally implemented arithmetic coding-free subset) is patent free.
And basically, I agree with Tom's assessment here. While JPEG is far from perfect, it is "good enough" for photographic images, and the massive increases in bandwidth and storage capacity kinda make high compression ratios irrelevant.
Finally, a 200:1 compression ration is pretty meaningless without some kind of context. A much more meaningful comparison is how many bytes are required to get the same quality image as some other compression standard, such as the original JPEG. The figure itself reminds me of when Triada was hyping their 200:1 lossless compression. Joe Bugajski gave a talk on this at Berkeley, and started waxing raphsodic on the incredible stuff that the Library of Congress had in their collection. Books and audio materials were fine, but when he got to the Stradivarius violins, my fellow grad students just broke up laughing. It's not hard to imagine 200:1 compression of that, but uncompression is tricky at best
An interview with Dr. Mills ran on the McLibel web site last February:
Parts 1 2 3
It doesn't take any deep knowledge of physics to come to the conclusion that this is a fraud. If it were real, it would be really fucking obvious. I can think of a few really clean experiments just off the top of my head (I mean, don't you'd think you'd be able to notice if the hydrino gas failed to react with oxygen?).
One of the more interesting things are the "independent" results that blacklightpower got done for them. Anyone else reminded of Mindcraft?
And "substantiate" should have been "instantiate".
Ok, this comment has a lot of inaccuracies. Let me try to clarify.
NP stands for "nondeterministic polynomial", and is probably most easily understood as the class of problems for which the solution can be verified in polynomial time. It includes P, the class of problems that can be solved in polynomial time.
A nice example of a problem that is in NP but not known to be in P is satisfiability. This problem is given as a list of predicates of the form (x1 or x2 or not x3). The problem is finding a set of xi such that all of the predicates are satisfied.
So, it should be obvious that you can verify a solution in polynomial time - just start with the values of xi and check that all the predicates turn out true. However, there is no known general technique for solving this problem than enumerating all the possibilities, which takes exponential time.
NP-completeness takes this idea one step further. It is a large an interesting class of problems that are basically equivalent in difficulty. If you solve one, you've solved them all. Thus, if a problem is NP-complete, there's no known efficient algorithm.
The way people analyze NP completeness is do define reductions, ie show how instances of one problem can be reduced into instances of another NP-complete problem, and vice versa. Maybe this takes "highly advanced skills," but it's actually fairly routine for algorithmicists.
The class of NP-complete problems includes the travelling salesman problem, the Hamiltonian path problem, the knapsack problem, determining collisions of 3D objects, and many others.
NP-hardness is when you can reduce an NP-complete problem into the NP-hard problem, but not necessarily vice versa. Many integer optimization problems are NP-hard.
Factoring is clearly NP, but is not known to be NP-hard. It's entirely plausible that someone (Arjen Lenstra, for example) will come up with a polynomial factoring algorithm, but leave the rest
of the NP pantheon untouched.
There are some crypto algorithms that are based on NP-completeness, but NP-completeness is not in and of itself enough for strong crypto. Even if the problem is hard in general, a specific instance may be easy to solve. Unless you can prove that this never happens, you're hosed. IBM has done some excellent work in this direction with randomized self-reductions for their lattice-based crypto algorithm.
Complexity theory is one of the most beautiful areas in computer science, and NP-completeness is one of the most striking results, as it illuminates a fundamental unity across many seemingly disparate subfields of computer science. It is indeed a shame that this book skimps on its coverage of NP-completeness.
Frankly, I don't think you can beat The Xiphophorus Company.
Not only that, but what they do absolutely rocks. A patent-free GPL'd next generation audio codec? Mmmmmmmm.
I am one of the Gnomers who has been following this issue, and was also present at one of the irc conversations with the Napster people. I've done a little writeup of the events, which I'm hoping will help set the record straight.
The writeup is here, posted on Advogato. As usual, anyone can read, but posting is restricting to free software developers.
First, let me add my voice to those who say that Slashdot's patent stories could use a clue or two. These sensationalistic headlines don't help anybody. I'll be adding a patent section to Advogato soon, and it's my hope that this will become a good place for informed discussion of patents relating to free software.
:). The language of the claims has to be read in the context of the disclosure of the patent, and to really do it right, you have to read the file history too.
When you analyze a patent, the most important thing to look at is the claims. The abstract has little or no legal force, it's just there to help people searching (it's on the front page of paper patents, which was important back in the days when people searched through stacks of them
That said, this is another example of the US Patent and Trademark Office screwing up royally. Claim 1 covers a pretty generic computation load-sharing system - a central computer keeping track of a bunch of tasks, sending a start message to a remote computer to ask it to take the task, and the remote computer sending a complete message back to the server.
The problem here is that there is prior art up the wazoo. I'm sure experts in the field could come up with more, but just about any operating system with process migration, such as Sprite should do. The main work on this project was all done in the early '90s, plenty of time to serve as prior art.
The disclosure doesn't help the case. It talks about the types of tasks to be distributed in extraordinarily vague terms, so much so as to not make much sense. Compressing MPEG's remotely? Are they on crack? Even a 320x200 at 30fps is over 5 megabytes per second of raw data. And of course serving up web pages is fraught with problems, such as latency, security, admin costs, reliability, and so on. The patent does not so much as mention these problems, let alone propose a reasonable method of dealing with them.
So what do you do when you have such a crappy patent? I think a reasonable thing for free software authors to do is ignore it. In theory, Intel could bring suit against a free software project for violating this patent. However, in that case it seems likely to me that we'd be able to get a good pro bono legal team together, and the patent would almost certainly be overturned.
In the meantime, I think our best option is to keep well informed about patents in general, and about specific patents that may be relevant. Shallow, "golly gee-whiz, look at the patent they just got on breathing" stories don't help much.
This is in response to a question about whether the site can be used for non-open source projects.
While we're on the subject of free resources for open source/free software developers, I would like ot take this opportunity to shamelessly plug Advogato, a new site I'm launching.
Advogato is an advocate for free software developers, as opposed to free software users or free software businesses. The main features now are a Slashdot-style news flow and a cool diary server.
One of the central features is an implementation of the peer certification work I'm doing for my PhD research. The site uses a group trust metric to determine membership in the community of free software developers. Only members can post, which is my crack at the S/N problem.
If you are a free software developer, you are warmly invited to join, poke around, and participate. Others are welcome to poke around.
ObOnTopic: From a look over their site, SourceForge looks impressive as hell. With VA's backing, they inspire quite a bit of confidence that they'll be able to handle the load. This can only be of benefit to Linux, free software in general, and of course VA.
This week's editorial on Advogato has some more discussion of Linus's talk, from the specific viewpoint of free software developers.
Everyone is welcome to read, but Advogato limits posting to members of the free software development community. It's my hope that this will make Advogato a more useful resource for developers.
I am not a lawyer, although I've been known to play one in my consulting fees.
Slashdot ran an excellent article on the basics of patent law a few weeks ago. It's reposted on Advogato, the new community site I'm starting for free software developers. I'm hoping to collect a solid set of patent resources at Advogato over time, among other things.
Hope this helps!
Wow, thanks very much. Slashdot really came through for me, and it was even an Anonymous Coward! All you AC-dissers, put that in your pipe and smoke it.
I was thinking that the theme is a little difficult for young kids. My son is 3.5 now, it will probably be a while before I recommend it to him.
Reading this, I am reminded of a low-intensity quest of mine, which is seeking two books that I remember reading as a child, but which nobody seems to know about today. Perhaps posting this query on Slashdot will finally bring a resolution to the quest.
The first book is about a boy named "Stark" who is sent to live with his uncle. The book is full of Xanth-like puns (when I first came across the Xanth books, I thought I might have found it), such as a pomegrenade tree that you really don't want to sit under, as the fruits have a tendency to blow up. I don't remember much of the plot, but if you've read the book, hopefully you can recognize it from this.
The second book is about two brothers who die early in the book and spend most of the book exploring two afterlife worlds. I recall that the older boy dies first while cushioning the fall of the younger one. Again, I don't remember much of the plot of the book, but the landscapes portrayed in the book were quite compelling.
I think I was eight or so when I read these. Any help tracking them down would be appreciated.
Gimp has gif code written by the venerable Adam D. Moss, who just so happens to be in the UK, out of reach of the LZW patent.
It's probably the best gif code in the world. Adam has also contributed to the gif handling in Mozilla.
Strangely, I found out about this yesterday, when I followed the lwn link to the FreeGIS web site newly created by Jan-Oliver Wagner in Germany.
This site has links to a number of other interesting free software GIS packages, as well as a couple of sources of data.
It is my hope that a real free GIS community will develop. I have a personal interest in this, as I think my libart 2D graphics rendering library has the potential to render maps at a much higher quality than most proprietary GIS packages today (i.e. antialiasing, semi-transparent layers, combining vector with image data). If there's anyone who's interested in integrating libart's cool rendering capabilities with the cool free software GIS apps, both current and future, please get in touch.