As the author of Beamer (the C++ program mentioned), I'll add one comment. The program uses a beam search and produces excellent results for all the tests on the machine I used for development. Unfortunately, that machine has 512MB of RAM, and the contest machine has 256MB. I discovered after the deadline that the priority queue used for generating the set of next candidates in the beam search can grow unreasonably large in some cases. For the last two test cases used, this is enough to start the thing thrashing in 256MB, and then it never finishes. A hard limit on the queue size wouldn't have affected the quality of the results, but hindsight is 20/20. Given the oversight, Beamer clearly didn't deserve to win. Lesson: set a reasonable data size limit when developing:-).
I'd second that. Most of the professional numerical analysists that I have known at Bell Labs had a generally low opinion about the actual code in the book. You can get an idea of a lot of the things that can be solved, but when you want to actually do something, you're usually better off getting stuff from netlib or a similar source.
In my experience using various debuggers over a number of different projects, none of them are particularly useful with multithreaded programs. Almost any of them are good enough to get stack dumps of the various threads and to print data values when an assertion fails, but they don't help much beyond that.
The best way to get a parallel program working is discipline and understanding. Think about how the threads will interface with each other. Design those interfaces using appropriate known and proven synchronization methodologies. Adhere rigorously to those designs. If you're tempted to leave out a lock in some place, you'd better be able to prove that it can be done safely.
If necessary, write wrappers around your synchronization primitives for better observability and controllability. For example, when the program crashes, you want to be able to see which threads are holding which locks, which are waiting for what conditions, etc. Being able to log the sequence of synchronization actions to a file and to force a replay of those actions in the same order will help in reproducing bugs that otherwise would manifest themselves only once every hundred runs.
Have manual inspections of the code with a coworker. Play a game where either of you can propose a failing scenario and the other must explain using the code why that can't happen. If neither of you can explain why it can't happen, it probably can.
Your basic philosophy should be that it's impossible to convince yourself of the correctness of the synchronization through testing. If you can't prove that your synchronization is right, it's most likely wrong. And if it's not wrong, it's so complicated that you'll break it later because you don't understand it.
1 nm is indeed 10^-9 m, so the article is wrong there, but the article also says the glass is 200,000 times smaller than a normal glass, and that it's ~2700 nm. Those are consistent, so probably only the article's definition of nm (and micron) are incorrect.
It seems to be a pretty nice language. Nobody here seems to have heard of it. Why?
Maybe it suffers from the same curse that (unfortunately) afflicts Smalltalk...
Re: This is a bad idea.
on
3Dwm Updates
·
· Score: 1
My fondest wish is for a window manager that could nest windows rather than using the "virtual desktop" approach. Sort of like the Xnest X server, but lighter weight. Instead of switching to a different portion of a desktop that won't fit on the screen, you'd make a new (blank) window. An application started in that window would create all of its subwindows in the same window, so, e.g., the whole batch could be iconified and moved around as a group. Actually, I don't know enough about the X protocol to even tell if this is possible, but I can always dream. If anyone is thinking about writing X window manager #1734...
Finding nontrivial factors is in NP, so you could use an algorithm for an NP-complete problem.
If I give you a O(n^10^100) algorithm...
In practice, P-time essentially means efficient. Once you understand the structure of a (non-artificial) problem well enough to provide a P-time algorithm, usually the complexity can be rapidly pushed down until it's in the cubic or quadratic range. The worst I've ever seen for a real problem (finding a minimal cycle basis for a graph) was O(n^6).
But for every Wiles, there are thousands of crackpots, and also a few intelligent types who made a very subtle mistake. The point of skepticism is to keep you from swallowing malarky. In the case of something like a claimed algorithm for an NP-complete problem, the person making the claim has a relatively easy way to demonstrate credibility: just implement the thing and use it solve some hard problems such as the RSA factoring challenges. Anyone unwilling or unable to make such efforts almost certainly is making a bogus claim, either intentionally or because they just don't understand what they're doing.
Anyone who thinks they have a polynomial time algorithm for an NP-complete problem has a relatively easy way to tell. Just write your program, take any of the well known collections of, e.g., hard satisfiability problems, reduce the instances to instances of the problem that you claim to solve, and run the program. When your program runs for a few years without producing an answer (or when it produces a wrong answer), you have an example to debug with. Of course, if it solves all the instances quickly and correctly, you may be on to something:-).
Re:In practice, useful NP hard problems can be sol
on
Does P = NP?
·
· Score: 2
Graph isomorphism is no worse than NP-complete, and it's not even known to be that hard; you likely mean subgraph isomorphism. Further, electrical networks have particular characteristics, and they are not designed so as to give rise to hard isomorphism problems.
This is a general characteristic. It's true that useful heuristics exist for many hard problems. For example, "random" boolean satisfiability problems are almost always easy to solve using simple search methods. But the hardest instances of satisfiability are totally intractable using these methods. And for applications like factoring, reduction to a problem such as satisfiability yields very hard instances.
Re:Implications to Cryptography
on
Does P = NP?
·
· Score: 1
Of course the paper is almost certainly bogus, but if it turned out to be legitimate, it would lead to algorithms with practical complexity. Take a few thousand smart computer scientists, get them pointed in the right direction on a problem of immense practical importance, and the order will probably drop quickly into the O(n^2) or O(n^3) range.
Of course, the BeOS people might say the same thing in regard to efforts to provide a free version of UNIX. Not that anyone would attempt such an ill-advised feat:-)...
Optical tends to go up by factors of four as well. 10 Gbps is the fastest version currently being widely deployed, 40 is coming, and 160 is in the R&D stage.
I think you mean insertion sort. For example, with the input 2, 3,..., n, 1, insertion sort will take O(n) steps while bubble sort will take O(n^2). The problem with bubble sort is that once any swap occurs during a pass, it will make at least one more pass over all the data. In this example, it takes O(n) passes for the 1 to bubble all the way to the front.
Slashdot Mirror
Here's a link to the tarball I submitted, with the source and a README that describes the program in a little more detail.
I wrote Beamer; for an explanation of what went wrong, see here.
As the author of Beamer (the C++ program mentioned), I'll add one comment. The program uses a beam search and produces excellent results for all the tests on the machine I used for development. Unfortunately, that machine has 512MB of RAM, and the contest machine has 256MB. I discovered after the deadline that the priority queue used for generating the set of next candidates in the beam search can grow unreasonably large in some cases. For the last two test cases used, this is enough to start the thing thrashing in 256MB, and then it never finishes. A hard limit on the queue size wouldn't have affected the quality of the results, but hindsight is 20/20. Given the oversight, Beamer clearly didn't deserve to win. Lesson: set a reasonable data size limit when developing :-).
I'd second that. Most of the professional numerical analysists that I have known at Bell Labs had a generally low opinion about the actual code in the book. You can get an idea of a lot of the things that can be solved, but when you want to actually do something, you're usually better off getting stuff from netlib or a similar source.
I notice that the date on the listing is from after the Apollo 11 landing. Perhaps it represents version 1.1 and the bug has been fixed :-).
In my experience using various debuggers over a number of different projects, none of them are particularly useful with multithreaded programs. Almost any of them are good enough to get stack dumps of the various threads and to print data values when an assertion fails, but they don't help much beyond that.
The best way to get a parallel program working is discipline and understanding. Think about how the threads will interface with each other. Design those interfaces using appropriate known and proven synchronization methodologies. Adhere rigorously to those designs. If you're tempted to leave out a lock in some place, you'd better be able to prove that it can be done safely.
If necessary, write wrappers around your synchronization primitives for better observability and controllability. For example, when the program crashes, you want to be able to see which threads are holding which locks, which are waiting for what conditions, etc. Being able to log the sequence of synchronization actions to a file and to force a replay of those actions in the same order will help in reproducing bugs that otherwise would manifest themselves only once every hundred runs.
Have manual inspections of the code with a coworker. Play a game where either of you can propose a failing scenario and the other must explain using the code why that can't happen. If neither of you can explain why it can't happen, it probably can.
Your basic philosophy should be that it's impossible to convince yourself of the correctness of the synchronization through testing. If you can't prove that your synchronization is right, it's most likely wrong. And if it's not wrong, it's so complicated that you'll break it later because you don't understand it.
Give 'em a little slop; it's the right order of magnitude. You've heard of a yard of ale, yes :-)?
1 nm is indeed 10^-9 m, so the article is wrong there, but the article also says the glass is 200,000 times smaller than a normal glass, and that it's ~2700 nm. Those are consistent, so probably only the article's definition of nm (and micron) are incorrect.
I meant that Smalltalk is the best language under the sun, but that the people promoting it don't know how to market 1/100th as well as the Sun.
My fondest wish is for a window manager that could nest windows rather than using the "virtual desktop" approach. Sort of like the Xnest X server, but lighter weight. Instead of switching to a different portion of a desktop that won't fit on the screen, you'd make a new (blank) window. An application started in that window would create all of its subwindows in the same window, so, e.g., the whole batch could be iconified and moved around as a group. Actually, I don't know enough about the X protocol to even tell if this is possible, but I can always dream. If anyone is thinking about writing X window manager #1734...
First, factoring is not in NP-complete
Finding nontrivial factors is in NP, so you could use an algorithm for an NP-complete problem.
If I give you a O(n^10^100) algorithm...
In practice, P-time essentially means efficient. Once you understand the structure of a (non-artificial) problem well enough to provide a P-time algorithm, usually the complexity can be rapidly pushed down until it's in the cubic or quadratic range. The worst I've ever seen for a real problem (finding a minimal cycle basis for a graph) was O(n^6).
But for every Wiles, there are thousands of crackpots, and also a few intelligent types who made a very subtle mistake. The point of skepticism is to keep you from swallowing malarky. In the case of something like a claimed algorithm for an NP-complete problem, the person making the claim has a relatively easy way to demonstrate credibility: just implement the thing and use it solve some hard problems such as the RSA factoring challenges. Anyone unwilling or unable to make such efforts almost certainly is making a bogus claim, either intentionally or because they just don't understand what they're doing.
Anyone who thinks they have a polynomial time algorithm for an NP-complete problem has a relatively easy way to tell. Just write your program, take any of the well known collections of, e.g., hard satisfiability problems, reduce the instances to instances of the problem that you claim to solve, and run the program. When your program runs for a few years without producing an answer (or when it produces a wrong answer), you have an example to debug with. Of course, if it solves all the instances quickly and correctly, you may be on to something :-).
Graph isomorphism is no worse than NP-complete, and it's not even known to be that hard; you likely mean subgraph isomorphism. Further, electrical networks have particular characteristics, and they are not designed so as to give rise to hard isomorphism problems.
This is a general characteristic. It's true that useful heuristics exist for many hard problems. For example, "random" boolean satisfiability problems are almost always easy to solve using simple search methods. But the hardest instances of satisfiability are totally intractable using these methods. And for applications like factoring, reduction to a problem such as satisfiability yields very hard instances.
Of course the paper is almost certainly bogus, but if it turned out to be legitimate, it would lead to algorithms with practical complexity. Take a few thousand smart computer scientists, get them pointed in the right direction on a problem of immense practical importance, and the order will probably drop quickly into the O(n^2) or O(n^3) range.
Maybe Taco didn't quite close the security hole after all :-)?
My own opinion is that, other things being equal, Smalltalk is the language that needs the fewest comments to be understandable.
They've revised the web page to remove them since this story was posted.
Presumably as a result of the flaming here, they've removed that statement from the web page.
:-)...
TWM forever
I'd consider supporting him only if he used Emacs.
Of course, the BeOS people might say the same thing in regard to efforts to provide a free version of UNIX. Not that anyone would attempt such an ill-advised feat :-)...
Optical tends to go up by factors of four as well. 10 Gbps is the fastest version currently being widely deployed, 40 is coming, and 160 is in the R&D stage.
I think you mean insertion sort. For example, with the input 2, 3, ..., n, 1, insertion sort will take O(n) steps while bubble sort will take O(n^2). The problem with bubble sort is that once any swap occurs during a pass, it will make at least one more pass over all the data. In this example, it takes O(n) passes for the 1 to bubble all the way to the front.