Most people have incorrect misconceptions about NP/NP-completeness since this often isn't covered in many CS degree programs. Let me clear up a few things people seem to consistently post incorrectly about.
First of all, what is meant (most likely) is that some NP-complete language can be recognized in polynomial time. The complete in NP-complete means that EVERY language in NP can be reduced (in polynomial time) to this particular NP-complete language. So P=NP.
NP is the class of guess and check languages. For example, we can see that determining if a number is composite is 'in NP' by guessing a factor. We can check by seeing if our guess divides the original number. If the total time for the guessing and doing the check is polynomial in the input length, then the language is NP.
P is a subset of NP. So when you say a particular problem is 'in NP,' this doesn't necessarily equate with an (even potentially) intractable solution.
There are only a few problems which are in NP that are not either known to be NP-complete or known to be in P. One of these is factoring of integers and forms the basis for RSA. Another is the Discrete Log which forms the basis for Elliptic Curve cryptosystems. Both would be essentially broken if P=NP, but so would most other things.
One of the biggest consequences of P=NP is that P=PSPACE. This means that many problems thought 'harder' than NP are also solvable in polynomial time. For example, the level of 'GO'-playing computers would increase. Just about every computational problem imaginable is within PSPACE, so if you are wondering would 'xxx' be affected, the answer is probably yes.
It is believed that recognizing whether a number is prime or composite is already solvable in polynomial time (in the input length) (ERH). However it isn't certain if ERH is true, so recognizing if a number is prime is technically NOT (necessarily) in P.
In practice, it is possible to make the decision with arbitrarily high probability. The fact that it is still sometimes difficult to factor is what makes the problem useful for cryptography.
I hope this clears things up some. Maybe people will stop wishing for O(n) solutions for NP-complete problems...
A good (more or less) solution would go something like this:
CFoo & CFoo::operator=(CFoo &that)
{
if(this == &that) return *this;//x=x check
CBar *bar1 = 0;
CBar *bar2 = 0;
try {
bar1 = new CBar( *(that.m_bar1) );
bar2 = new CBar( *(that.m_bar2) );
CSuperFoo::operator=(that);
}
catch(...)
{
delete bar1;
delete bar2;
throw;
}
delete m_bar1;
m_bar1 = bar1;
delete m_bar2;
m_bar2 = bar2;
return *this;
}
The keys being that you have to check for exceptions from new and also the superclass constructor. If an exception is encountered, then memory should be freed and you should recover.
Also, the operation should be atomic: so assigning directly to m_bar is bad as long as it is followed by an expression which could throw an exception. If this is the case then it should be possible to bail out completely. Either all of the assignment happened or none of it happened. So if you assign to m_bar1 and the assignment to m_bar2 throws and exception, you'll end up with incorrect values in your class. Also its assumed your destructors wont throw exceptions, which is considered bad practice, etc.
A simpler solution can be crafted by using autoptr's.
The problem is that "programming" per se is often not taught in Universities, but its hoped that you will just majickly "pick it up". I read an article recently (can't remember the source) that proposed the following programmer "litmus test". It's just a basic task that one should be expected to know how to do if you use C++ at all.
Try it!
Given a class CFoo, subclassed from a base class CSuperFoo, write the copy assignment operator. The only members of CFoo are two pointers to instances of a monomorphic class CBar.
A possible declaration might contain
class CFoo : public CSuperFoo
{
private:
CBar *m_bar1;
CBar *m_bar2;
//...
};
You may assume the other classes are implemented fully and properly. Also, the pointers have "own" semantics not "alias" semantics.
When you think about it, any C++ programmer should be able to do this. Everytime you make an object, you might need to copy it. And its often the case that a structure such as this can occur in C++ programs.
Have a crack, reply below with an answer. Don't feel bad if its incorrect though, in the article they mentioned that no one they interviewed could give a correct answer.
Makes me wonder is a problem with programmers, the language, or our education system?
This article is clearly written by a QC "expert". I'm no "expert" but I've had plenty of undergrad QM and done some work with reversible computing and simulations of QM/QC.
First, let me debunk a couple of statements throughout the article:
Not only can quantum computers run one billion times faster than typical silicon-based computers
I'll just leave this one alone...
they can run and consume no energy
Although in theory, thermodynamically reversible computers can run and consume no energy, this is only the case as the time of a computation tends to infinity. If you don't mind that your calculation of 2+2 takes millions of years, you can get away with using freakishly small amounts of power. (Consequently, since no one lives forever, no computation, even a reversible one, can take ZERO power.) Also QC is not simply a thermodynamically reversible machine, you need error corrrection and you need to measure the outputs at the end of your computation. Each of these steps also takes power.
Consequently, silicon chip and computer manufacturers, the U.S. government, and Japan are directing huge sums of money for quantum computer research.
I'm not sure about the Japanese, but USG has stopped dumping the tons and tons of money into QC as it has in the past. This is because those wonderful results you hear about such as Shor's alg. and Grover's search alg. are about the only real uses determined in the last 20 years for QC. They've had many of the top scientists in the world looking at the algorithmic problem, and have about 3 favorable results.
What they come up with instead is a great many results that say we CAN'T make it go faster. No matter how hard we try! The key to QC (it is hoped) is the idea that we can achieve an exponential speedup in the running time of many classical algorithms. It was once hoped that this could allow NP problems to be solved as fast as P problems. But no one's shown anything like this yet. It is ASSUMED that factoring numbers is NP hard, but this is not necessarily true. (No one knows...) However the best classical algorithms run exponentially slower than QC algorithms, so a speedup is a big result here. Unfortunately this isn't the end of cryptography as we know it, there's a multitude of ways to encrypt that don't depend on factoring. The key algorithm was Rabin's, which has been shown to only be as "hard" as factoring. But RSA and other methods (elliptic curve, etc.) have no known reduction to factorization.
Subexponential speedups are still possible, but the killer of classical computation is the inability to deal with NP problems. If QC doesn't help in this regard, it may not be of much practical use.
Incidentally, reversibility also means that the inputs of a quantum computer can be implied from the outputs; the program can be run backward to get the inputs.
There was some confusion over this statement in/. people seemed to think that this was an error. It isn't but it implies the wrong thing. Reversible computing entails programs that run and do not destroy information. Someone proprosed a program which multiplies x by zero and gives the output as zero. Then if the program is run in reverse, how is x to be determined?
The answer is that the "output" of a program is said to be all information necessary to recover the inputs. So in this case the output would be "x, 0" so that we don't lose any information. While it seems that this can be a bit restrictive, it is possible to create useful programs that don't continually create more and more memory as they are run reversibly. A simple example is a circle drawing program:
x += CONSTANT * y;
y -= CONSTANT * x;
Let (x, y) initially equal (1,0). Now run this in a loop and after each step draw (x, y); you'll see a circle drawn if the constants are small enough. (Think about it.) The key in making this program run reversibly is to use integer mathematics which does not lose information (unlike floating point which rounds, etc.).
If these two instructions produce a result (taking no additional space) then the following instructions would UNDO that result:
y += CONSTANT * x;
x -= CONSTANT * y;
So to 'reverse' the program we'd run the loop in reverse. Got it? No additional space for outputs, the entire state of the system is (x,y). (Incidentally change X,Y to be arrays and "CONSTANT" to be an approximation of the second derivative across those arrays and you have a quantum mechanics simulation that runs reversibly.)
Why this is misleading in the article is that QC (so far) have been hardcoded to solve their particular problems. Thus although the inputs could be determined from the outputs (before measurement) you would need a separate machine to do so. Also, once you measure the outputs, forget trying to recover the inputs. Measurement "collapses" the state.
2.4 New Applications
Most of the stuff in this section, I've already mentioned. Cryptography isn't dead yet, only certain algorithms are, and not the most popular ones today even. Molecular simulations are not usually done on the quantum level, they are done by mixing QM and Classical M, to produce an approximate result. The sheer memory required to do a full QM simulation of a complex system is overwhelming, even today. Maybe by the time QC is built there will be a use for it. True randomness is available on almost any PC we use today. The chipsets support calls which generate very good random numbers based on thermal noise. No patterns.
NMR computing also appears to be a dead end. People believe there is an upper limit on the number of qubits one can get in an NMR machine (and that upper limit is very small...). Which leaves physicists searching for the next qubit representation, comp sci's searching for an application, and/.ers searching for a new article to read.
For example, there is some interesting research being done on the limits of quantum computation. Perhaps quantum computers will be able to solve a larger class of problems. That might disprove the Church-Turing-Tarski thesis.
It has been shown that classical computers' PSPACE and quantum computers' PSPACE are equivalent so there isn't a tremendous amount of hope left in this whole QC thing.
People have still found ways to achieve subexponential speedups however with these problems.
And I haven't even mentioned intractability - the gigantic class of problems that we don't know how to solve quickly when the problem gets large. For example, many optimization problems seem easy on paper when you have a set of 2 or 3 objects. You code up a little demo program that can handle 10 to 20 objects. It seems a little slow, but you figure you can optimize it and find a better algorithm, and use a faster computer. Meanwhile Marketing is promising people that you will be able to solve the problem with 1000 objects.
I was under the impression most algorithmics work today is being done in the NP domain. Pretty much 'acceptable' solutions are found for most P problems. CS PhD's are working on ways to make intractable problems tractable. Of course nothing can 'solve' these, but for specific applications there may be solutions that are 'good enough'. So you see many approximate solutions that you can run in subexponential time.
Of course every application has subtle differences in what is acceptable and what is not. This was of course designed by the CS PhD's so that they would never be out of a job.
It would be like trying to find a solution to the equation "n * 0 = 100".
Slashdot Mirror
The issue here isn't that the Ph.D. program is 'helping' in any sense, but almost all good schools will offer a Ph.D. program.
When you restrict your list to those schools which don't offer a Ph.D., then you are eliminating some of the best schools from consideration.
I wonder has anyone used the name 'shallow hal' for a chessplaying program/machine?
You are right; I meant P=PH, not P=PSPACE.
Most people have incorrect misconceptions about NP/NP-completeness since this often isn't covered in many CS degree programs. Let me clear up a few things people seem to consistently post incorrectly about.
First of all, what is meant (most likely) is that some NP-complete language can be recognized in polynomial time. The complete in NP-complete means that EVERY language in NP can be reduced (in polynomial time) to this particular NP-complete language. So P=NP.
NP is the class of guess and check languages. For example, we can see that determining if a number is composite is 'in NP' by guessing a factor. We can check by seeing if our guess divides the original number. If the total time for the guessing and doing the check is polynomial in the input length, then the language is NP.
P is a subset of NP. So when you say a particular problem is 'in NP,' this doesn't necessarily equate with an (even potentially) intractable solution.
There are only a few problems which are in NP that are not either known to be NP-complete or known to be in P. One of these is factoring of integers and forms the basis for RSA. Another is the Discrete Log which forms the basis for Elliptic Curve cryptosystems. Both would be essentially broken if P=NP, but so would most other things.
One of the biggest consequences of P=NP is that P=PSPACE. This means that many problems thought 'harder' than NP are also solvable in polynomial time. For example, the level of 'GO'-playing computers would increase. Just about every computational problem imaginable is within PSPACE, so if you are wondering would 'xxx' be affected, the answer is probably yes.
It is believed that recognizing whether a number is prime or composite is already solvable in polynomial time (in the input length) (ERH). However it isn't certain if ERH is true, so recognizing if a number is prime is technically NOT (necessarily) in P.
In practice, it is possible to make the decision with arbitrarily high probability. The fact that it is still sometimes difficult to factor is what makes the problem useful for cryptography.
I hope this clears things up some. Maybe people will stop wishing for O(n) solutions for NP-complete problems...
But does she compile???
CFoo & CFoo::operator=(CFoo &that)
{
if(this == &that) return *this;//x=x check
CBar *bar1 = 0;
CBar *bar2 = 0;
try {
bar1 = new CBar( *(that.m_bar1) );
bar2 = new CBar( *(that.m_bar2) );
CSuperFoo::operator=(that);
}
catch(...)
{
delete bar1;
delete bar2;
throw;
}
delete m_bar1;
m_bar1 = bar1;
delete m_bar2;
m_bar2 = bar2;
return *this;
}
The keys being that you have to check for exceptions from new and also the superclass constructor. If an exception is encountered, then memory should be freed and you should recover.
Also, the operation should be atomic: so assigning directly to m_bar is bad as long as it is followed by an expression which could throw an exception. If this is the case then it should be possible to bail out completely. Either all of the assignment happened or none of it happened. So if you assign to m_bar1 and the assignment to m_bar2 throws and exception, you'll end up with incorrect values in your class. Also its assumed your destructors wont throw exceptions, which is considered bad practice, etc.
A simpler solution can be crafted by using autoptr's.
Test-based coding is great, but "thought" based coding works even better...
The problem is that "programming" per se is often not taught in Universities, but its hoped that you will just majickly "pick it up". I read an article recently (can't remember the source) that proposed the following programmer "litmus test". It's just a basic task that one should be expected to know how to do if you use C++ at all.
Try it!
Given a class CFoo, subclassed from a base class CSuperFoo, write the copy assignment operator. The only members of CFoo are two pointers to instances of a monomorphic class CBar.
A possible declaration might contain
class CFoo : public CSuperFoo
{
private:
CBar *m_bar1;
CBar *m_bar2;
};
You may assume the other classes are implemented fully and properly. Also, the pointers have "own" semantics not "alias" semantics.
When you think about it, any C++ programmer should be able to do this. Everytime you make an object, you might need to copy it. And its often the case that a structure such as this can occur in C++ programs. Have a crack, reply below with an answer. Don't feel bad if its incorrect though, in the article they mentioned that no one they interviewed could give a correct answer.
Makes me wonder is a problem with programmers, the language, or our education system?
First, let me debunk a couple of statements throughout the article:
Not only can quantum computers run one billion times faster than typical silicon-based computers
I'll just leave this one alone...
they can run and consume no energy
Although in theory, thermodynamically reversible computers can run and consume no energy, this is only the case as the time of a computation tends to infinity. If you don't mind that your calculation of 2+2 takes millions of years, you can get away with using freakishly small amounts of power. (Consequently, since no one lives forever, no computation, even a reversible one, can take ZERO power.) Also QC is not simply a thermodynamically reversible machine, you need error corrrection and you need to measure the outputs at the end of your computation. Each of these steps also takes power.
Consequently, silicon chip and computer manufacturers, the U.S. government, and Japan are directing huge sums of money for quantum computer research.
I'm not sure about the Japanese, but USG has stopped dumping the tons and tons of money into QC as it has in the past. This is because those wonderful results you hear about such as Shor's alg. and Grover's search alg. are about the only real uses determined in the last 20 years for QC. They've had many of the top scientists in the world looking at the algorithmic problem, and have about 3 favorable results.
What they come up with instead is a great many results that say we CAN'T make it go faster. No matter how hard we try! The key to QC (it is hoped) is the idea that we can achieve an exponential speedup in the running time of many classical algorithms. It was once hoped that this could allow NP problems to be solved as fast as P problems. But no one's shown anything like this yet. It is ASSUMED that factoring numbers is NP hard, but this is not necessarily true. (No one knows...) However the best classical algorithms run exponentially slower than QC algorithms, so a speedup is a big result here. Unfortunately this isn't the end of cryptography as we know it, there's a multitude of ways to encrypt that don't depend on factoring. The key algorithm was Rabin's, which has been shown to only be as "hard" as factoring. But RSA and other methods (elliptic curve, etc.) have no known reduction to factorization.
Subexponential speedups are still possible, but the killer of classical computation is the inability to deal with NP problems. If QC doesn't help in this regard, it may not be of much practical use.
Incidentally, reversibility also means that the inputs of a quantum computer can be implied from the outputs; the program can be run backward to get the inputs.
There was some confusion over this statement in /. people seemed to think that this was an error. It isn't but it implies the wrong thing. Reversible computing entails programs that run and do not destroy information. Someone proprosed a program which multiplies x by zero and gives the output as zero. Then if the program is run in reverse, how is x to be determined?
The answer is that the "output" of a program is said to be all information necessary to recover the inputs. So in this case the output would be "x, 0" so that we don't lose any information. While it seems that this can be a bit restrictive, it is possible to create useful programs that don't continually create more and more memory as they are run reversibly. A simple example is a circle drawing program:
x += CONSTANT * y;
y -= CONSTANT * x;
Let (x, y) initially equal (1,0). Now run this in a loop and after each step draw (x, y); you'll see a circle drawn if the constants are small enough. (Think about it.) The key in making this program run reversibly is to use integer mathematics which does not lose information (unlike floating point which rounds, etc.).
If these two instructions produce a result (taking no additional space) then the following instructions would UNDO that result:
y += CONSTANT * x;
x -= CONSTANT * y;
So to 'reverse' the program we'd run the loop in reverse. Got it? No additional space for outputs, the entire state of the system is (x,y). (Incidentally change X,Y to be arrays and "CONSTANT" to be an approximation of the second derivative across those arrays and you have a quantum mechanics simulation that runs reversibly.)
Why this is misleading in the article is that QC (so far) have been hardcoded to solve their particular problems. Thus although the inputs could be determined from the outputs (before measurement) you would need a separate machine to do so. Also, once you measure the outputs, forget trying to recover the inputs. Measurement "collapses" the state.
2.4 New Applications
Most of the stuff in this section, I've already mentioned. Cryptography isn't dead yet, only certain algorithms are, and not the most popular ones today even. Molecular simulations are not usually done on the quantum level, they are done by mixing QM and Classical M, to produce an approximate result. The sheer memory required to do a full QM simulation of a complex system is overwhelming, even today. Maybe by the time QC is built there will be a use for it. True randomness is available on almost any PC we use today. The chipsets support calls which generate very good random numbers based on thermal noise. No patterns.
NMR computing also appears to be a dead end. People believe there is an upper limit on the number of qubits one can get in an NMR machine (and that upper limit is very small...). Which leaves physicists searching for the next qubit representation, comp sci's searching for an application, and /.ers searching for a new article to read.
For example, there is some interesting research being done on the limits of quantum computation. Perhaps quantum computers will be able to solve a larger class of problems. That might disprove the Church-Turing-Tarski thesis.
It has been shown that classical computers' PSPACE and quantum computers' PSPACE are equivalent so there isn't a tremendous amount of hope left in this whole QC thing.
People have still found ways to achieve subexponential speedups however with these problems.
And I haven't even mentioned intractability - the gigantic class of problems that we don't know how to solve quickly when the problem gets large. For example, many optimization problems seem easy on paper when you have a set of 2 or 3 objects. You code up a little demo program that can handle 10 to 20 objects. It seems a little slow, but you figure you can optimize it and find a better algorithm, and use a faster computer. Meanwhile Marketing is promising people that you will be able to solve the problem with 1000 objects.
I was under the impression most algorithmics work today is being done in the NP domain. Pretty much 'acceptable' solutions are found for most P problems. CS PhD's are working on ways to make intractable problems tractable. Of course nothing can 'solve' these, but for specific applications there may be solutions that are 'good enough'. So you see many approximate solutions that you can run in subexponential time.
Of course every application has subtle differences in what is acceptable and what is not. This was of course designed by the CS PhD's so that they would never be out of a job.
It would be like trying to find a solution to the equation "n * 0 = 100".
This has solutions for very small values of 100.