It is hardly news when yet another game is shown to be NP-hard. Consider that mindless solitaire game played with Mah Jong tiles called "Shang hai", where you can remove pairs of tiles that match and have exposed left or right edges. Even if there's only one layer of tiles, so you can see the entire state of the game at the start, determining whether it is possible to remove all the tiles is NP-complete.
True, but the number they factored was 15. Even *I* can do that. The problem with quantum computing is scaling it up, which is very difficult to do. I suspect it will happen, but not anytime soon.
Actually the largest strip mine imaginable would probably be dwarfed by an average sized crater. You won't be able to see it with the unaided eye.
I'd rather see a dead rock get strip mined than a living planet. Although in reality it is so uneconomical to mine the moon that it won't happen in your lifetime or mine.
OBD-2 covers only the engine management and emissions related parts of your car. But pretty much every manufacturer adds proprietary extensions to deal with everything from ABS brakes to the door locks. For my Volkswagen, I use the VAG-COM software from Ross Tech, which understands the proprietary stuff. That's because Uwe Ross reverse engineered the Volkswagen diagnostic tool. You may or may not be able to find similar software for other makes.
Actually changing the fuel maps and timing (rather than simply diagnosing problems) is another matter entirely. That requires the ability to change the programming of the electronic control unit, and only a handful of guys have figured out how to do that. They're the ones selling the aftermarket "chips". For the home hotrodder, it is much easier to bypass the factory ECU entirely and install a programmable aftermarket engine management system (there are several different brands). Any car modified in this way will no longer be street legal, unless you undergo the expensive and time consuming process of getting a CARB exemption, or its equivalent for your state.
>The problem is that you are creating "a work >based on the Program". The "Program", here, is >KDE. By compiling it, you create a "work based >on the Program" - namely, the combination of KDE >and Qt. And this is more than a mere >aggregation, because if you remove Qt, KDE stops >working. > >In this sense, Qt becomes "a part" of KDE when >it's compiled, in that KDE won't work without >it.
The problem is that you are creating "a work based on the Program". The "Program", here, is KDE. By compiling it, you create a "work based on the Program" - namely, the combination of KDE and the C library. And this is more than a mere aggregation, because if you remove the C library, KDE stops working.
In this sense, the C library becomes "a part" of KDE when it's compiled, in that KDE won't work without it.
So by your brilliant reasoning we must conclude that neither KDE nor any other GPLed program can be ported to a Unix system with proprietary C libraries.
Of course this is bullshit. The GPL explicitly allows you to link against libraries that are normally available as part of the operating system. On almost every non-Debian distribution, Qt is considered to be a standard part of the operating sytem.
>If we don't make that leap soon, humans might forever be doomed to exploring >only cyberspace. (I seriously don't mind that but, then when the population >reaches the point that where earth cannot any longer sustain it, we are going >to have a problem)
It is a mistake to think that expansion into space is any sort of long term solution to human population growth. Let us make two wildly optimistic assumptions:
1. The sphere of human civilization grows at the speed of light. 2. Every atom encountered along the way can be converted to human biomass.
Now assume a modest population growth of only 0.5% a year. That is much less than the current world average, and about half the current rate of US population growth.
Can this continue indefinately?
The total mass of all humans is
H(t) = mN(1+r)^t, where
m = the mass of an average person (about 60 kg) N = the initial number of people (6e9) r = the rate of growth (assumed to be.005). t = the time in years
The total mass within the sphere of civilization at time t is
C(t) = (4/3 pi)d(ct)^3, where
c = the speed of light, in meters per year (9.46e15) d = the densitity of the galaxy, in kg/m^3.
A *very* rough estimate for d: Approximate the galaxy as a flattened cylinder with a height of 20 kpc, a radius of 40 kpc, and a total mass of 6e11 solar masses. Then d = 1e-21 kg/m^3.
How long before H(t) > C(t)? Less than 13100 years.
The sphere of civilation will have a radius of slightly over 4 kiloparsecs, so the crunch will occur well before we even reach the galactic center. Thus the use of the galactic density (rather than of the universe overall) was justified. Different assumptions about the value of d won't change the answer much.
So even a low but positive rate of population growth isn't sustainable, no matter what technical fixes you throw at it. There is no alternative to stabilizing the population, and if we do that it doesn't much matter whether we can settle Jupiter's moons (although it might just be fun to do).
RMS has never boycotted a company merely for copyrighting its sofware or for making money (and Amazon isn't *making* any money). All boycotts he has called for are due either to interface copyrights that make it impossible to make software compatible with other software, or to software patents.
If you object to software patents and are a programmer you should do what I did. I actually read my employee agreement, and insisted that they delete the clauses that enabled them (or me) to get patents on my work. Remember that employee agreements are boilerplate cooked up by lawyers and if you are any good the suits will agree to this change if you make it clear that you're not going to take the job otherwise. After all, most software companies don't make any money on patents.
A few corrections are required here. Cuthalion says "factoring... seems to be in a class of problems which we call NP". In fact, factoring *is* in NP. Contrary to popular belief, NP doesn't necessarily mean hard. All deterministic polynomial time algorithms (the kind you actually use) are in NP, by definition. NP just means that there are short, easy to verify proofs of the correct answer. For example, if you claim than x is a factor of y, I can simply divide x into y to verify that your claim is true. Some problems in NP *seem* to be hard. The hardest problems in NP are the NP-complete problems. No one has ever shown that factoring is NP-complete. It might be NP-intermediate (hard but not NP-complete). Also,no one has shown that quantum computers can solve NP-complete problems. Contrary to what appears to be a popular belief among slashdot readers, quantum computers can not do arbitrary exponential parallelism. (If they could, they could easily solve NP-complete problems just by trying all solutions at once.) Indeed, Shor's algorithm would be trivial (and not have the justified fame that it has) if it was simply a matter of trying all possible factors at once. Quantum computations have to be describable by a Hermitian operator, at it is non-obvious just what you can do with such operators.
Re:While it may be nice there is still an issue
on
KDE 2.0 in Action
·
· Score: 1
QT is free for use in open source programs that allow free redistribution. The license fee applies if you want to produce commercial software, with a conventional fee-per-copy type of license. Troll Tech charges $1550 for a Unix/Linux only or a Windows only license, or $2390 for both. (This is per programmer seat, there is no run time license.) If you have a commercial app that's not going to be feasible to sell because of that license fee, it was never viable in the first place. One good experienced programmer can easily cost $100,000/year or more, after all payroll taxes and support expenses are taken into account. If QT makes that programmer 2% more productive it pays for itself in a year. In any case it's small beer in the overall costs of a software company.
Any free software fan who thinks that $2400 is an outrageous fee for a GUI library should be delighted that Troll Tech is providing such a powerful economic incentive for programmers to open up their source and make it freely redistributable. After all RMS is now advocating the use of the GPL, rather than the LGPL, for libraries, so as to effectively make the closed source license fee infinity (non-free apps can't legally link to GPLed libraries). Troll Tech is simply providing a less draconian incentive for open source.
My only gripe is that the free license doesn't apply to the Windows version of QT -- you can't make a free open source Windows program using QT. But then Gnome doesn't work on Windows at all.
Re:While it may be nice there is still an issue
on
KDE 2.0 in Action
·
· Score: 0
QT is free for use in open source programs that allow free redistribution. The license fee applies if you want to produce commercial software, with a conventional fee-per-copy type of license. Troll Tech charges $1550 for a Unix/Linux only or a Windows only license, or $2390 for both. (This is per programmer seat, there is no run time license.) If you have a commercial app that's not going to be feasible to sell because of that license fee, it was never viable in the first place. One good experienced programmer can easily cost $100,000/year or more, after all payroll taxes and support expenses are taken into account. If QT makes that programmer 2% more productive it pays for itself in a year. In any case it's small beer in the overall costs of a software company.
Any free software fan who thinks that $2400 is an outrageous fee for a GUI library should be delighted that Troll Tech is providing such a powerful economic incentive for programmers to open up their source and make it freely redistributable. After all RMS is now advocating the use of the GPL, rather than the LGPL, for libraries, so as to effectively make the closed source license fee infinity (non-free apps can't legally link to GPLed libraries). Troll Tech is simply providing a less draconian incentive for open source.
Diamonds are a terrible "investment" right now. If you buy a diamond and then immediately try to sell it, you'll do well to get a third of what you paid.
I've had carpal tunnel syndrome for several years. There are several types of repetitive stress injuries that can hurt your hands and you really have to go to a doctor to get a proper diagnosis. Surgery should be a last resort, it can help or it can make things much worse.
The one keyboard I've found that really helps is the Datahand (www.datahand.com). It's the strangest of the "alternative keyboards", and takes a couple of weeks to get used to, but it greatly reduces the stretching and finger motion you have to do.
Quantum computers can *not* do arbitrary nondeterministic computations. If they could, the factoring algorithm would be trivial (just guess the factors and verify that their product is the number you want to factor). Instead, Peter Shor had to devise a very clever scheme based on estimating the period of a long sequence. Quantum computers are restricted to operations that are definable by a unitary matrix. So while they can effectively get exponential amounts of parallelism, the kind of things they can do in parallel is severely restricted.
Certainly. NP-complete problems are pretty far down the complexity hierarchy, there are lots of harder problems. There are PSPACE-complete problems, EXPTIME-complete problems, NEXPTIME-complete problems, etc. The game of go, generalized to an n x n board, is EXPTIME-complete. That means that, given an arbitrary configuration on an n x n go board, determining if there is a win for black *provably* takes exponential time in n (no assumptions like P != NP required, since it is known that EXPTIME != P by diagonalization).
A lot of the sort of decision problems for various mathematical theories that you'd like your AI expert system to solve are PSPACE-complete or worse. And of course there are the problems that can't be computed at all, such as determining if a multivariate polynomial has integer values for its variable that make it equal to 0.
You are correct that when and if quantum computers become practical, RSA will be dead (as will any other cryptographic scheme that relies upon the assumption that factoring is hard).
However, this is not the same as proving P=NP. So far no one has found a way to use quantum computing to solve NP-complete problems quickly, and it's likely that NP-hard problems will remain intractable even for quantum computers.
Quantum computing does not disprove the Church-Turing thesis. Quantum computers can be simulated by Turing Machines, albeit with an exponential slowdown.
I will say that for many years many theorists believed a "strong" form of the Church-Turing thesis, to wit, that any realizable model of computation can be simulated by a TM with only a polynomial slowdown. This strong form of the Church-Turing thesis does seem likely to be disproved by QC. I say "likely" because it's possible (though improbable) that some one tomorrow might show how to simulate a QC on a classical computer with only a polynomial slowdown. (That would give a fast *non-quantum* algorithm for factoring.)
My understanding is that Dolly's genes have shorter telomeres than would be normal for a sheep of her age, which could explain the more rapid aging. But I'd guess that her offspring would not have this problem (babies don't inherit their parents' shorter telomeres). So even if a cloned bird has a shorter life, its offspring might not.
While I think it would be cool to resurrect some extinct species by cloning, that will never be as effective as stopping species from becoming extinct in the first place.
Slashdot Mirror
It is hardly news when yet another game is shown to be NP-hard. Consider that mindless solitaire game played with Mah Jong tiles called "Shang hai", where you can remove pairs of tiles that match and have exposed left or right edges. Even if there's only one layer of tiles, so you can see the entire state of the game at the start, determining whether it is possible to remove all the tiles is NP-complete.
An easy exercise for the bored nerd.
True, but the number they factored was 15.
Even *I* can do that. The problem with quantum computing is scaling it up, which is very difficult to do. I suspect it will happen, but not anytime soon.
Actually the largest strip mine imaginable would probably be dwarfed by an average sized crater.
You won't be able to see it with the unaided eye.
I'd rather see a dead rock get strip mined than a living planet. Although in reality it is so uneconomical to mine the moon that it won't happen in your lifetime or mine.
OBD-2 covers only the engine management and emissions related parts of your car. But pretty much every manufacturer adds proprietary extensions to deal with everything from ABS brakes to the door locks. For my Volkswagen, I use the VAG-COM software from Ross Tech, which understands the proprietary stuff. That's because Uwe Ross reverse engineered the Volkswagen diagnostic tool. You may or may not be able to find similar software for other makes.
Actually changing the fuel maps and timing (rather than simply diagnosing problems) is another matter entirely. That requires the ability to change the programming of the electronic control unit, and only a handful of guys have figured out how to do that. They're the ones selling the aftermarket "chips". For the home hotrodder, it is much easier to bypass the factory ECU entirely and install a programmable aftermarket engine management system (there are several different brands). Any car modified in this way will no longer be street legal, unless you undergo the expensive and time consuming process of getting a CARB exemption, or its equivalent for your state.
>The problem is that you are creating "a work
>based on the Program". The "Program", here, is
>KDE. By compiling it, you create a "work based
>on the Program" - namely, the combination of KDE
>and Qt. And this is more than a mere
>aggregation, because if you remove Qt, KDE stops
>working.
>
>In this sense, Qt becomes "a part" of KDE when
>it's compiled, in that KDE won't work without
>it.
The problem is that you are creating "a work based on the Program". The "Program", here, is KDE. By compiling it, you create a "work based on the Program" - namely, the combination of KDE and the C library. And this is more than a mere aggregation, because if you remove the C library, KDE stops working.
In this sense, the C library becomes "a part" of KDE when it's compiled, in that KDE won't work without it.
So by your brilliant reasoning we must conclude that neither KDE nor any other GPLed program can be ported to a Unix system with proprietary C libraries.
Of course this is bullshit. The GPL explicitly allows you to link against libraries that are normally available as part of the operating system. On almost every non-Debian distribution, Qt is considered to be a standard part of the operating sytem.
>If we don't make that leap soon, humans might forever be doomed to exploring
.005).
>only cyberspace. (I seriously don't mind that but, then when the population
>reaches the point that where earth cannot any longer sustain it, we are going
>to have a problem)
It is a mistake to think that expansion into space is any sort of long term solution to human population growth. Let us make two wildly optimistic assumptions:
1. The sphere of human civilization grows at the speed of light.
2. Every atom encountered along the way can be converted to human biomass.
Now assume a modest population growth of only 0.5% a year. That is much less than the current world average, and about half the current rate of US population growth.
Can this continue indefinately?
The total mass of all humans is
H(t) = mN(1+r)^t, where
m = the mass of an average person (about 60 kg)
N = the initial number of people (6e9)
r = the rate of growth (assumed to be
t = the time in years
The total mass within the sphere of civilization at time t is
C(t) = (4/3 pi)d(ct)^3, where
c = the speed of light, in meters per year (9.46e15)
d = the densitity of the galaxy, in kg/m^3.
A *very* rough estimate for d: Approximate the galaxy as a flattened cylinder with a height of 20 kpc, a radius of 40 kpc, and a total mass of 6e11 solar masses. Then d = 1e-21 kg/m^3.
How long before H(t) > C(t)? Less than 13100 years.
The sphere of civilation will have a radius of slightly over 4 kiloparsecs, so the crunch will occur well before we even reach the galactic center. Thus the use of the galactic density (rather than of the universe overall) was justified. Different assumptions about the value of d won't change the answer much.
So even a low but positive rate of population growth isn't sustainable, no matter what technical fixes you throw at it. There is no alternative to stabilizing the population, and if we do that it doesn't much matter whether we can settle Jupiter's moons (although it might just be fun to do).
RMS has never boycotted a company merely for copyrighting its sofware or for making money (and Amazon isn't *making* any money). All boycotts he has called for are due either to interface copyrights that make it impossible to make software compatible with other software, or to software patents.
If you object to software patents and are a programmer you should do what I did. I actually read my employee agreement, and insisted that they delete the clauses that enabled them (or me) to get patents on my work. Remember that employee agreements are boilerplate cooked up by lawyers and if you are any good the suits will agree to this change if you make it clear that you're not going to take the job otherwise. After all, most software companies don't make any money on patents.
A few corrections are required here. Cuthalion says "factoring ... seems to be in a class of problems which we call NP". In fact, factoring *is* in NP. Contrary to popular belief, NP doesn't necessarily mean hard. All deterministic polynomial time algorithms (the kind you actually use) are in NP, by definition. NP just means that there are short, easy to verify proofs of the correct answer. For example, if you claim than x is a factor of y, I can simply divide x into y to verify that your claim is true. Some problems in NP *seem* to be hard. The hardest problems in NP are the NP-complete problems. No one has ever shown that factoring is NP-complete. It might be NP-intermediate (hard but not NP-complete). Also,no one has shown that quantum computers can solve NP-complete problems. Contrary to what appears to be a popular belief among slashdot readers, quantum computers can not do arbitrary exponential parallelism. (If they could, they could easily solve NP-complete problems just by trying all solutions at once.) Indeed, Shor's algorithm would be trivial (and not have the justified fame that it has) if it was simply a matter of trying all possible factors at once. Quantum computations have to be describable by a Hermitian operator, at it is non-obvious just what you can do with such operators.
QT is free for use in open source programs that allow free redistribution. The license fee applies if you want to produce commercial software, with a conventional fee-per-copy type of license. Troll Tech charges $1550 for a Unix/Linux only or a Windows only license, or $2390 for both. (This is per programmer seat, there is no run time license.) If you have a commercial app that's not going to be feasible to sell because of that license fee, it was never viable in the first place. One good experienced programmer can easily cost $100,000/year or more, after all payroll taxes and support expenses are taken into account. If QT makes that programmer 2% more productive it pays for itself in a year. In any case it's small beer in the overall costs of a software company.
Any free software fan who thinks that $2400 is an outrageous fee for a GUI library should be delighted that Troll Tech is providing such a powerful economic incentive for programmers to open up their source and make it freely redistributable. After all RMS is now advocating the use of the GPL, rather than the LGPL, for libraries, so as to effectively make the closed source license fee infinity (non-free apps can't legally link to GPLed libraries). Troll Tech is simply providing a less draconian incentive for open source.
My only gripe is that the free license doesn't apply to the Windows version of QT -- you can't make a free open source Windows program using QT. But then Gnome doesn't work on Windows at all.
QT is free for use in open source programs that allow free redistribution. The license fee applies if you want to produce commercial software, with a conventional fee-per-copy type of license. Troll Tech charges $1550 for a Unix/Linux only or a Windows only license, or $2390 for both. (This is per programmer seat, there is no run time license.) If you have a commercial app that's not going to be feasible to sell because of that license fee, it was never viable in the first place. One good experienced programmer can easily cost $100,000/year or more, after all payroll taxes and support expenses are taken into account. If QT makes that programmer 2% more productive it pays for itself in a year. In any case it's small beer in the overall costs of a software company.
Any free software fan who thinks that $2400 is an outrageous fee for a GUI library should be delighted that Troll Tech is providing such a powerful economic incentive for programmers to open up their source and make it freely redistributable. After all RMS is now advocating the use of the GPL, rather than the LGPL, for libraries, so as to effectively make the closed source license fee infinity (non-free apps can't legally link to GPLed libraries). Troll Tech is simply providing a less draconian incentive for open source.
Diamonds are a terrible "investment" right now. If you buy a diamond and then immediately try to sell it, you'll do well to get a third of what you paid.
I've had carpal tunnel syndrome for several years. There are several types of repetitive stress injuries that can hurt your hands and you really have to go to a doctor to get a proper diagnosis. Surgery should be a last resort, it can help or it can make things much worse.
The one keyboard I've found that really helps is the Datahand (www.datahand.com). It's the strangest of the "alternative keyboards", and takes a couple of weeks to get used to, but it greatly reduces the stretching and finger motion you have to do.
Quantum computers can *not* do arbitrary nondeterministic computations. If they could, the factoring algorithm would be trivial (just guess the factors and verify that their product is the number you want to factor). Instead, Peter Shor had to devise a very clever scheme based on estimating the period of a long sequence. Quantum computers are restricted to operations that are definable by a unitary matrix. So while they can effectively get exponential amounts of parallelism, the kind of things they can do in parallel is severely restricted.
Certainly. NP-complete problems are pretty far down the complexity hierarchy, there are lots of harder problems. There are PSPACE-complete problems, EXPTIME-complete problems, NEXPTIME-complete problems, etc. The game of go, generalized to an n x n board, is EXPTIME-complete. That means that, given an arbitrary configuration on an n x n go board, determining if there is a win for black *provably* takes exponential time in n (no assumptions like P != NP required, since it is known that EXPTIME != P by diagonalization).
A lot of the sort of decision problems for various mathematical theories that you'd like your AI expert system to solve are PSPACE-complete or worse. And of course there are the problems that can't be computed at all, such as determining if a multivariate polynomial has integer values for its variable that make it equal to 0.
You are correct that when and if quantum computers become practical, RSA will be dead (as will any other cryptographic scheme that relies upon the assumption that factoring is hard).
However, this is not the same as proving P=NP. So far no one has found a way to use quantum computing to solve NP-complete problems quickly, and it's likely that NP-hard problems will remain intractable even for quantum computers.
Quantum computing does not disprove the Church-Turing thesis. Quantum computers can be simulated by Turing Machines, albeit with an exponential slowdown.
I will say that for many years many theorists believed a "strong" form of the Church-Turing thesis, to wit, that any realizable model of computation can be simulated by a TM with only a polynomial slowdown. This strong form of the Church-Turing thesis does seem likely to be disproved by QC. I say "likely" because it's possible (though improbable) that some one tomorrow might show how to simulate a QC on a classical computer with only a polynomial slowdown. (That would give a fast *non-quantum* algorithm for factoring.)
My understanding is that Dolly's genes have shorter telomeres than would be normal for a sheep of her age, which could explain the more rapid aging. But I'd guess that her offspring would not have this problem (babies don't inherit their parents' shorter telomeres). So even if a cloned bird has a shorter life, its offspring might not.
While I think it would be cool to resurrect some extinct species by cloning, that will never be as effective as stopping species from becoming extinct in the first place.