Re:Interesting NP-complete problem
on
Does P = NP?
·
· Score: 2
Consistent in the sense that the position describes a possible situation. For example an impossible situation is a single covered tile where the rest of the board is empty space and where the single tile is surrounded by 2's. This is impossible because at most there is one bomb under the tile so the 2's should be 1's. This is a trivial example but you probably get the idea now...
--
Isn't this quite simply stating "We have a monopoly because without Windows pre-installed you're running illegally". Isn't this evidence out of MS's own mouth that could be used against them? That really makes me want to take Windows off my machine even without all the drivers I need to run Linux or FreeBSD.
--
Interesting NP-complete problem
on
Does P = NP?
·
· Score: 3
Check out the article in Scientific American this month on that great game minesweeper. Someone has proved that the problem of determining whether a position in the game is consistent is NP-complete and it gives an idea of how the proof goes. Neat!
--
Like IBM or Digital (Compaq). Compaq certainly have a bunch of people trying to keep alive one of each model of computer from their lines. I'd have thought a company could get a little bit of publicity out of a project like this!
--
I use a Vaio 505TX with a quad capacity battery. It easily lasts 6 hours and is great for intercontinental flights. If you're happy with 300MHz you'll easily find one 2nd hand or reconditioned for a good price. The battery costs $500 though and you want that new. Runs Linux, FreeBSD and Windows 2000 with very little difficulty.
--
If you were at SIGGRAPH 2000 you may have seen a shot from this movie running *real time* at HD resolution on a Sony box consisting of 16 PS2's running parallel in one box. It was pretty awesome! The camera was movable by the viewer and the image quality was pretty much the same with wonderful lighting, texturing and hair dynamics.
--
Although physical theories are often hard to test experimentally there is still the standard of internal consistency to a theory. Many fields of inquiry have no such checks.
Consider a new 'toy' physical system that a physicist might come up with. They can ask concrete questions like 'what are the energy levels?'. These questions often have definite answers and it's easy to judge if someone's work on this problem is competent. It's much harder to do that in other fields si I find it very interesting to see a problem posed like this. Physicists are very used to working with 'toy' systems.
I've a feeling you may be wrong in assuming other sciences are like physics. Try reading some psychology papers...
--
Are you saying John Hopfield should be the authorized examiner of neuroscientists?
Absolutely not. Who said anything about athorising anyone? His experiment can be peer reviewed just like any other work.
Time spent working on this problem is time not spent working on the brain directly.
No - but it might be time spent sharpening the skills required for brain research. Then again - maybe not. That's the nature of research.
--
I have a terabyte sitting near my desk. It's about the size of a PC - maybe a bit bigger. It's tiny! Anyone want to take bets on when it will fit into something the size of a compact flash?
--
I think this experiment could be very important for neurobiological research and maybe other typs of research.
There are many fields of science where it is possible to go on forever publishing research without any checks. Obvious areas where this goes on are fields like so-called postmodern literary criticism. But it happens in the sciences too. In behavioural evolutionary biology you can make up just-so stories in paper after paper safe in the knowledge that nobody else can rerun evolution for you and demonstrate that you are wrong. In psychology you can repeatedly perform experiments measuring correlation between this variable and that. By chance one in 20 results are 95% significant and you publish those results as if they are something other than noise.
Hopfield's experiment is going to be a sanity check against this kind of work - a kind of experimental control. Here's a situation where somebody does know the answer and work can be checked. A neural net involving only a few hundred neurons. If researchers are unable to reverse engineer this then should they really have jobs supposedly reverse engineering animal or even human brains? We need to see a few more tests like this in academia. Beyond a certain point - after you've taken your last exam - academics are no longer accountable to anyone. Sure - you get peer reviewed. But what happens when you and your peers all belong to a clique that have a vested interest in promulgating a particular scientific dogma? This experiment is a wonderful way to ensure that researchers still are being tested.
--
Hmmm...
The whole laissez-faire thing you are talking about is a uniquely American phenomenon. The US population is more anti-government than that of any other nation I have known. The whole American constitution is anti-government and however much Americans complain they have less government interference in their lives than most other Western nations. (Eg. in the UK I had to pay the government for health care and yet when I used that health care I was made to feel I was wasting government money that could be spent on someone more needy. At school the default is to be forced into xtian religious services because Britain has a state religion.) Yet the the US has a singularly bad education system (easily demonstrated by recent international surveys). This makes me very unsure that the cause of the state of US education is the excess of government interference.
As an armchair psychologist I'm tempted to blame it on the litigation obsessed culture (you can't criticise a student too badly or you'll get sued) and the whole psychological self-help thread that has run through culture in the US for at least a century (eg. documented by William James) which puts feelings of self-esteem above actually doing anything worthy of esteem. But these latter opinions should be taken with a pinch of salt as I haven't really studied the issue.
--
Does the American education system teach Americans anything other than how to boost their already overactive self-esteems? To judge from the resumes I've read you wouldn't think so. Everyone claims to be a 'straight A student' and yet I see so much mediocrity. Maybe American teachers need to wake up. It's not politically incorrect to find fault in a student's work.
--
What are the differences between running Intel and AMD? I don't mean performance differences. Are there many differences in terms of what software will run? I recently had some Fortran code that I was trying to link to some C code. Running under FreeBSD on an Intel box it worked fine. On an AMD Athlon some floating point flags were set on returning from the Fortran code and the next floating point operation threw a SIGFPE. Should there ever be a difference between the two platforms like that?
--
Are your quantitative agreements true *predictions*? I've seen some
interesting ways results that are already known can feedback into the
simulation without the developers realising. For example if you have
a closely related family of molecules 1 to N with known properties and
N+1 is unknown and you use 1 to N to calibrate your simulation then
you have a good chance of getting N+1 right simply because your complex
looking simulator is doing nothing but simple curve fitting and is simply
interpolating from the properties on 1 to N. Does your simulator work in
entirely new domains? Does it really simulate a priori or do you need
to tune the laws of physics on a per-molecule basis? I know of great
successes with simple inorganic compounds but I'm yet to be convinced
with complex organic molecules. On the other hand my scepticism could
be completely out of place which means that your work is very very cool! But
then I'll launch into my tirade about how the knowing conformations doesn't
help as much as chemists claim. I have
great scepticism about the whole rational drug design thing and think
combinatorial chemistry is the way to go. But that's another discussion...
--
A few years ago I worked in computational chemistry for a pharmaceutical
company. Determining the
conformation of a molecule is a *hard* problem. We're dealing with quantum
mechanics (QM) rather than classical mechanics and many-body QM problems are
notoriously difficult. For example if you have just *two* particles the space
of possible configurations is 6 dimensional (in this simple example you can
use symmetry to simplify things). The wavefunction is a function on a six
dimensional space. For a protein you might want to deal with hundreds or
thousands of nuclei and many more electrons. You might be determining a
wavefunction on a 100,000 dimensional space. Let me give a taste of how big
that is. Imagine we discretise this space so that we only have *ten* steps
along each dimension. Then we have 1 with 100,000 zeros after it discrete
points in the space. That's *big*. So clearly any attempt to solve this
problem on a classical (ie. non-quantum) computer is a gross approximation. I
have serious doubts about our ability to solve this problem today - even with
a billionfold increase in the power of computers.
When I worked in this computational chemistry department all of the molecular
modelling packages had parameters you could tune. A computational chemist
would run a simulation. If the result wasn't to their taste they'd tweak the
parameters and run it again. Then they'd run it a few more times. As X-ray
data came in they'd fine tune their parameters to make their simulated model
match. Eventually they'd give a seminar showing how their simulation matched
the real results - when in fact all they'd done is find the set of simulation
parameters that matched reality. These parameters were purely hacks tweaked
to make things look like the experimental results. They had no a
priori worth. If you took these tweaked parameters and tried them on the
next simulation with a different parameter guess what! They wouldn't
work. And this was for relatively simple biologicaly active compounds - not entire proteins. This is a problem that grows exponentially with the number of bodies.
Thankfully some of these people realised that what they were doing was no
better than Voodoo.
So I hope someone can convince me that there have been big improvements before
we collectively build the world's biggest waster of CPU time. Keep your
cycles for SETI@home - at least then they might be useful.
--
A third! Where did you find that published? I'm pretty amazed it's that popular given the lack of experimental success. I personally think string (or M) theory isn't a great *physical* theory but I don't care as I think it's the most beautiful thing to come out of physics ever.
Of course you can't make a clean split between gauge theory and string theory and you can quantise strings as a gauge theory.
True. He got quantisation of non-abelian gauge theory to work. As theoretical physics today seems to be nothing but quantising non-abelian gauge theories (at least that's what almost all the theoretical physicists in my mathematics department did!) it makes him a pretty important guy - which is what I really should have said (ie. he's not a crackpot).
--
Check out recent work by Susskind and 't Hooft (the guy who pretty well invented Gauge Theory) - in particular the stuff on the Holographics Hypothesis (this *isn't* the cheesy holographic universe thing in some popular physics book). Susskind had an article in SciAm about a year ago - otherwise, if you have a physics background, try searching xxx.lanl.gov. They, and others, suggest that the event horizon isn't the well behaved place classical general relativists say it is. You may no the classical result that a black hole has no hair. The opposite seems to hold in quantum gravity - the event horizon actually has lots of quantum information concentrated near it. I am sympathetic towards their controversial outlook (I did black holes and strings for a few years before and during my PhD). Who knows though - *none* of this stuff is founded on anything rigorous.
--
But what is there at the center of the blackhole?
If you go along with general relativity - ignoring quantum mechanics - we have a fairly good mathematical model of the inside of a black hole - at least in terms of its gravitational field. The problem is at the very centre where the mathematics goes a bit haywire and we have a 'singularity'. That's just a way of saying the solution to the equations goes to infinity and the equations aren't valid at this point.
What are the physics like inside?
In principle. Similar to outside. One twist is that time and radial distance are flipped. What this means is that instead of particles taking an inexorable path into the future from the past they take a path that is confined to travelling towards the singularity. (This is for a non-spinning black hole, spinning black holes are more complex but this is a slashdot post not a book on general relativity).
What's it like to fall in?
As you approach the event horizon you're going to have more and more stuff falling in behind you. Much of that stuff is light that whacks in behind you. That light will have been converted to gamma rays by gravitation blue shift. You'd get frazzled before reaching the event horizon.
How many dimensions inside?
Same as outside according to the theory.
What's it feel like to be a blackhole?
Try 'As She Crawled Across The Table' by Jonathan Lethem:-)
Personally I think there's a lot of evidence that ignoring quantum effects is wrong. There is a lot of evidence that interesting quantum effects take place at the event horizon so that the laws of physics we currently have break down well before the singularity. Connecting quantum mechanics and general relativity is the biggest challenge facing theoretical physics right now but I home we see some glimmer of understanding within your lifetime!
I'm missing something. A new cat-shaped scanner being given away to millions of consumers
Why would someone give away scanners to consumers? Why would someone make a scanner shaped like a cat? I use a flatbed scanner which is shaped like a sheet of paper and that's far more convenient. Privacy advocates are investigating the device, known as the CueCat, and its ability to snoop on consumers while swiping bar codes printed in catalogs and magazines
Why would I scan barcodes in magazines? If you don't scan anything you won't get snooped. Simple as that. And why is a scanner connected to the Internet?
So somebody! Please tell me what the hell this article is about. Have I missed some vital part of American culture or something? Does everyone except me scan their barcodes and I'm missing out on something?
--
Did you spot the euler-quaternion converter
on
2001: A Space Laptop
·
· Score: 4
Working in graphics I have endless problems with conversions of rotations between Euler angles and quaternions. It's funny to see that NASA must share these problems and actually have a stand alone tool to do the conversion. Can you imagine the situations where you actually have to type in those number by hand into a GIO like that!
--
It uses Newtonian gravity and the inverse square law with a lame hack to simulate an event horizon. This is no black hole simulator but a cheesy my-first-opengl program (no offence to the author intended - we all wrote our first OpenGL program). It'd be fun if it were a real black hole simulator - you get some interesting orbits in the presence of a black hole that can't be simulated using F=GMm/r^2. It's even more fun to render in the presence of a black hole bending light rays - there are some example images on the web and in Scientific American from some time in the last few years.
If you call for a boycott so that a group of N people refrain from perfoming act X and any one person from the group of N could anonymously carry out X on his or her own then a boycott can't work. It's pretty obvious really. All that will happen is that the $10,000 will go to someone who doesn't care about the boycott.
--
Slashdot Mirror
Consistent in the sense that the position describes a possible situation. For example an impossible situation is a single covered tile where the rest of the board is empty space and where the single tile is surrounded by 2's. This is impossible because at most there is one bomb under the tile so the 2's should be 1's. This is a trivial example but you probably get the idea now...
--
Isn't this quite simply stating "We have a monopoly because without Windows pre-installed you're running illegally". Isn't this evidence out of MS's own mouth that could be used against them? That really makes me want to take Windows off my machine even without all the drivers I need to run Linux or FreeBSD.
--
Check out the article in Scientific American this month on that great game minesweeper. Someone has proved that the problem of determining whether a position in the game is consistent is NP-complete and it gives an idea of how the proof goes. Neat!
--
Like IBM or Digital (Compaq). Compaq certainly have a bunch of people trying to keep alive one of each model of computer from their lines. I'd have thought a company could get a little bit of publicity out of a project like this!
--
I use a Vaio 505TX with a quad capacity battery. It easily lasts 6 hours and is great for intercontinental flights. If you're happy with 300MHz you'll easily find one 2nd hand or reconditioned for a good price. The battery costs $500 though and you want that new. Runs Linux, FreeBSD and Windows 2000 with very little difficulty.
--
If you were at SIGGRAPH 2000 you may have seen a shot from this movie running *real time* at HD resolution on a Sony box consisting of 16 PS2's running parallel in one box. It was pretty awesome! The camera was movable by the viewer and the image quality was pretty much the same with wonderful lighting, texturing and hair dynamics.
--
Although physical theories are often hard to test experimentally there is still the standard of internal consistency to a theory. Many fields of inquiry have no such checks. Consider a new 'toy' physical system that a physicist might come up with. They can ask concrete questions like 'what are the energy levels?'. These questions often have definite answers and it's easy to judge if someone's work on this problem is competent. It's much harder to do that in other fields si I find it very interesting to see a problem posed like this. Physicists are very used to working with 'toy' systems. I've a feeling you may be wrong in assuming other sciences are like physics. Try reading some psychology papers...
--
Are you saying John Hopfield should be the authorized examiner of neuroscientists? Absolutely not. Who said anything about athorising anyone? His experiment can be peer reviewed just like any other work. Time spent working on this problem is time not spent working on the brain directly. No - but it might be time spent sharpening the skills required for brain research. Then again - maybe not. That's the nature of research.
--
I have a terabyte sitting near my desk. It's about the size of a PC - maybe a bit bigger. It's tiny! Anyone want to take bets on when it will fit into something the size of a compact flash?
--
I think this experiment could be very important for neurobiological research and maybe other typs of research. There are many fields of science where it is possible to go on forever publishing research without any checks. Obvious areas where this goes on are fields like so-called postmodern literary criticism. But it happens in the sciences too. In behavioural evolutionary biology you can make up just-so stories in paper after paper safe in the knowledge that nobody else can rerun evolution for you and demonstrate that you are wrong. In psychology you can repeatedly perform experiments measuring correlation between this variable and that. By chance one in 20 results are 95% significant and you publish those results as if they are something other than noise. Hopfield's experiment is going to be a sanity check against this kind of work - a kind of experimental control. Here's a situation where somebody does know the answer and work can be checked. A neural net involving only a few hundred neurons. If researchers are unable to reverse engineer this then should they really have jobs supposedly reverse engineering animal or even human brains? We need to see a few more tests like this in academia. Beyond a certain point - after you've taken your last exam - academics are no longer accountable to anyone. Sure - you get peer reviewed. But what happens when you and your peers all belong to a clique that have a vested interest in promulgating a particular scientific dogma? This experiment is a wonderful way to ensure that researchers still are being tested.
--
Hmmm... The whole laissez-faire thing you are talking about is a uniquely American phenomenon. The US population is more anti-government than that of any other nation I have known. The whole American constitution is anti-government and however much Americans complain they have less government interference in their lives than most other Western nations. (Eg. in the UK I had to pay the government for health care and yet when I used that health care I was made to feel I was wasting government money that could be spent on someone more needy. At school the default is to be forced into xtian religious services because Britain has a state religion.) Yet the the US has a singularly bad education system (easily demonstrated by recent international surveys). This makes me very unsure that the cause of the state of US education is the excess of government interference. As an armchair psychologist I'm tempted to blame it on the litigation obsessed culture (you can't criticise a student too badly or you'll get sued) and the whole psychological self-help thread that has run through culture in the US for at least a century (eg. documented by William James) which puts feelings of self-esteem above actually doing anything worthy of esteem. But these latter opinions should be taken with a pinch of salt as I haven't really studied the issue.
--
Does the American education system teach Americans anything other than how to boost their already overactive self-esteems? To judge from the resumes I've read you wouldn't think so. Everyone claims to be a 'straight A student' and yet I see so much mediocrity. Maybe American teachers need to wake up. It's not politically incorrect to find fault in a student's work.
--
What are the differences between running Intel and AMD? I don't mean performance differences. Are there many differences in terms of what software will run? I recently had some Fortran code that I was trying to link to some C code. Running under FreeBSD on an Intel box it worked fine. On an AMD Athlon some floating point flags were set on returning from the Fortran code and the next floating point operation threw a SIGFPE. Should there ever be a difference between the two platforms like that?
--
Are your quantitative agreements true *predictions*? I've seen some interesting ways results that are already known can feedback into the simulation without the developers realising. For example if you have a closely related family of molecules 1 to N with known properties and N+1 is unknown and you use 1 to N to calibrate your simulation then you have a good chance of getting N+1 right simply because your complex looking simulator is doing nothing but simple curve fitting and is simply interpolating from the properties on 1 to N. Does your simulator work in entirely new domains? Does it really simulate a priori or do you need to tune the laws of physics on a per-molecule basis? I know of great successes with simple inorganic compounds but I'm yet to be convinced with complex organic molecules. On the other hand my scepticism could be completely out of place which means that your work is very very cool! But then I'll launch into my tirade about how the knowing conformations doesn't help as much as chemists claim. I have great scepticism about the whole rational drug design thing and think combinatorial chemistry is the way to go. But that's another discussion...
--
A few years ago I worked in computational chemistry for a pharmaceutical company. Determining the conformation of a molecule is a *hard* problem. We're dealing with quantum mechanics (QM) rather than classical mechanics and many-body QM problems are notoriously difficult. For example if you have just *two* particles the space of possible configurations is 6 dimensional (in this simple example you can use symmetry to simplify things). The wavefunction is a function on a six dimensional space. For a protein you might want to deal with hundreds or thousands of nuclei and many more electrons. You might be determining a wavefunction on a 100,000 dimensional space. Let me give a taste of how big that is. Imagine we discretise this space so that we only have *ten* steps along each dimension. Then we have 1 with 100,000 zeros after it discrete points in the space. That's *big*. So clearly any attempt to solve this problem on a classical (ie. non-quantum) computer is a gross approximation. I have serious doubts about our ability to solve this problem today - even with a billionfold increase in the power of computers. When I worked in this computational chemistry department all of the molecular modelling packages had parameters you could tune. A computational chemist would run a simulation. If the result wasn't to their taste they'd tweak the parameters and run it again. Then they'd run it a few more times. As X-ray data came in they'd fine tune their parameters to make their simulated model match. Eventually they'd give a seminar showing how their simulation matched the real results - when in fact all they'd done is find the set of simulation parameters that matched reality. These parameters were purely hacks tweaked to make things look like the experimental results. They had no a priori worth. If you took these tweaked parameters and tried them on the next simulation with a different parameter guess what! They wouldn't work. And this was for relatively simple biologicaly active compounds - not entire proteins. This is a problem that grows exponentially with the number of bodies. Thankfully some of these people realised that what they were doing was no better than Voodoo. So I hope someone can convince me that there have been big improvements before we collectively build the world's biggest waster of CPU time. Keep your cycles for SETI@home - at least then they might be useful.
--
Render visual effects for cool movies of course!
--
Who's the moron who thinks that 'controversial' means flamebait?
--
Of course you can't make a clean split between gauge theory and string theory and you can quantise strings as a gauge theory.
--True. He got quantisation of non-abelian gauge theory to work. As theoretical physics today seems to be nothing but quantising non-abelian gauge theories (at least that's what almost all the theoretical physicists in my mathematics department did!) it makes him a pretty important guy - which is what I really should have said (ie. he's not a crackpot).
--
Check out recent work by Susskind and 't Hooft (the guy who pretty well invented Gauge Theory) - in particular the stuff on the Holographics Hypothesis (this *isn't* the cheesy holographic universe thing in some popular physics book). Susskind had an article in SciAm about a year ago - otherwise, if you have a physics background, try searching xxx.lanl.gov. They, and others, suggest that the event horizon isn't the well behaved place classical general relativists say it is. You may no the classical result that a black hole has no hair. The opposite seems to hold in quantum gravity - the event horizon actually has lots of quantum information concentrated near it. I am sympathetic towards their controversial outlook (I did black holes and strings for a few years before and during my PhD). Who knows though - *none* of this stuff is founded on anything rigorous.
--
Personally I think there's a lot of evidence that ignoring quantum effects is wrong. There is a lot of evidence that interesting quantum effects take place at the event horizon so that the laws of physics we currently have break down well before the singularity. Connecting quantum mechanics and general relativity is the biggest challenge facing theoretical physics right now but I home we see some glimmer of understanding within your lifetime!
--I'm missing something.
A new cat-shaped scanner being given away to millions of consumers
Why would someone give away scanners to consumers? Why would someone make a scanner shaped like a cat? I use a flatbed scanner which is shaped like a sheet of paper and that's far more convenient.
Privacy advocates are investigating the device, known as the CueCat, and its ability to snoop on consumers while swiping bar codes printed in catalogs and magazines
Why would I scan barcodes in magazines? If you don't scan anything you won't get snooped. Simple as that. And why is a scanner connected to the Internet?
So somebody! Please tell me what the hell this article is about. Have I missed some vital part of American culture or something? Does everyone except me scan their barcodes and I'm missing out on something?
--
Working in graphics I have endless problems with conversions of rotations between Euler angles and quaternions. It's funny to see that NASA must share these problems and actually have a stand alone tool to do the conversion. Can you imagine the situations where you actually have to type in those number by hand into a GIO like that!
--
Why is it a story on Slashdot?
--If you call for a boycott so that a group of N people refrain from perfoming act X and any one person from the group of N could anonymously carry out X on his or her own then a boycott can't work. It's pretty obvious really. All that will happen is that the $10,000 will go to someone who doesn't care about the boycott.
--