NP is the set of all decision problems where a "yes" answer permits a certificate (proof) that can be verified in polynomial time. For instance, factoring is in NP, because the question "does Q have at most n factors" can be checked in polynomial time by simply multiplying primes together. The certificate, in this case, would be "yes" and a list of prime factors. Very simple problems can also be in NP: for instance, the problem "does there exist an Y for a given X so that X + Y has exactly ten digits in base 10?" is in NP; a yes certificate just gives Y.
A problem in NP does not need to have a polynomial time verifiable certificate for "no" answers. Consider satisfiability: if a circuit can be satisfied (i.e. there are inputs that makes the output true), then there's a certificate: the input itself. On the other hand, if the circuit can't be satisfied (there is no input that makes the output true), it's not very clear how one would make a certificate showing this.
NP-hard is the set of all problems that are at least as hard as the worst problems in NP. To take a very easy example, the halting problem is NP-hard, but it is not in NP.
"At least as hard" has a specific meaning: it means that if you had a machine that could solve the problem in question, you could also solve all problems in NP by transforming the latter into the former in polynomial time. For the halting problem, this is easy: make a Turing machine that halts iff it finds a "yes" certificate for the NP problem instance in question. I think the chess problem is NP-hard as well.
Given the above, NP-complete is simply the intersection of NP and NP-hard. An NP-complete problem, like subset sum or 3-CNF-SAT, is in NP (you can prove an affirmative answer in polynomial time), and it is NP-hard (as hard as all the problems in NP). Thus, if you had a magical machine that would solve an NP-complete problem, you could solve all problems in NP. A corollary of this is that you can turn any instance of an NP-complete problem into an instance of another NP-complete problem. Such a reduction is usually employed to prove that some given problem X is NP-complete: one says "I can turn any and all SAT problem instances into instances of X, therefore if I could solve X I could solve SAT, therefore X is NP-complete".
To answer your question: no. NP-Complete is a subset of NP-hard, but NP-hard is not a subset of NP. It's actually the other way around. NP is a subset of NP-hard. The Wikipedia article on NP-hard has a good diagram showing the relation: http://en.wikipedia.org/wiki/File:P_np_np-complete_np-hard.svg
Perhaps it could be done for three viewers using polarization: horizontal, vertical, and circular.
Or since we're talking about science fiction tech, get out that 1MHz refresh rate monitor and equally sensitive shutter glasses; 16384 distinct viewers should be enough for everyone:p
An "ordinary" quantum computer is no more powerful than a Turing machine. It probably can't even solve NP-complete problems quickly because there's no way of directing the observation step (where you pull the answer out of the numerous universes) in such a way as to make the right answer show up often enough. This is, technically speaking, an open problem (just like P vs NP), but most believe the answer is a negative (just like P != NP).
I said "ordinary" quantum computer because there have been attempts at making quantum hypercomputers (i.e. computers more powerful than a Turing machine). The best known is Kieu's adiabatic quantum hypercomputation scheme, but that appears to havebeen refuted. Quantum adiabatic algorithms can be useful (they're a bit like genetic algorithms, only on the quantum level), but apparently they can't bring quantum computers above Turing power; a bit like the Brownian ratchet in this manner, in that it's not as powerful as thought, but still useful.
To sum all of that up: it's unknown whether it's possible to make a quantum computer solve NP-complete in polytime, but most think it's unlikely. It's unknown whether it's possible to make a quantum hypercomputer as well, but most think it's even less likely (although if consciousness would disprove this, that would be... interesting).
Then consider a decision problem like: "given this initial chess setup, with White to move, can White force a win?". That's yes/no, and because it's at least as hard as other problems in NP, it's NP-hard. Yet, if this was NP-complete (as you say it would be, because it's NP-hard and a yes/no problem), then one could make a perfect chess AI if one could solve SAT. Given that chess itself is EXPTIME-complete, I think that would come as a surprise to most people.
You may then say that "of course that problem isn't NP-complete - NP-complete problems can have polytime verifiable proof certificates of a 'yes' solution whereas for the hypothetical chess problem above, that's not true". However, that would merely be a restatement of NP, as a problem is in NP if there's a verifier that executes in polynomial time.
The minesweeper decision problem is actually: "Given these mine hints, is there any possible way mines could be set on the field so that you would get these hints when uncovering these squares?". It's a reduction from SAT. It's NP because given an answer, you can check if the mine hints would be what the problem states. It's NP-hard because SAT is. Together, NP and NP-hard makes NP-complete.
Note that NP-hardness isn't about the average case, it's about the worst case. Many proofs of puzzles being NP-hard essentially go: "I can make a playing field so that the puzzle is only solvable if a related Boolean circuit can be satisfied, and I can transform any Boolean circuit into a playing field in this manner". Such a proof only tells you that these "gadget puzzles" (transformed circuits) are as hard as SAT, it says nothing about the average puzzle.
As another example, consider a problem where the input is either 0, an integer, and a number of integers; or 1, and a number of integers. Then the decision problem is defined as "if the first number is 0, then true if the second is the sum of all the subsequent integers of the input; if the first number is 1, then true if the circuit defined (in some given format) by the subsequent integers can be satisfied". Obviously, this problem is NP-complete because you can turn any SAT problem into an instance of this problem; but if the first number is 0, the problem is trivially decided.
Incidentally, that's part of the reason why cryptosystems based on NP-hard problems have done so badly: while the cryptosystem might be hard to crack, worst case, it usually turns out most instances of encryption can be broken.
As far as I understand, the kind of filtering China is doing here is based on URLs, so that the firewalls don't have to be too stateful. That's why people in China can contact Google HK just fine, but when they try to search for "tiananmen" or "tank man", boom, timeout.
However, when using SSL, the URLs aren't actually transmitted in plaintext; it would take China a CPU-intensive man-in-the-middle attack to break it. So why can't Google just retaliate by redirecting http://google.com.hk/ to a special https://google.com.hk/ or something to that effect? Further blocking would become cat-and-mouse, and would require China to block Google outright.
We could re-use those byproducts, or drastically reduce their amount, if we built breeder reactors.
I think experiments into subcritical reactors would be valuable. Since they "burn" the fuel using an external beam, they can also force fission or transmutation in substances where that doesn't happen naturally. In other words, they can reduce nuclear waste like breeders do, but further, and the output is too mixed to be used for bomb-making purposes - for instance, the plutonium contains Pu-240 which makes a bomb fizzle. They're also less choosy - can use uranium, plutonium, or thorium.
If that's true, how can black holes grow at all? The time dilation effect would seem to suggest that nothing ever reaches the event horizon, because time slows down so it falls increasingly slowly towards the hole. Something must be wrong, because black holes can grow -- but what is it?
Please excuse my stupidity, but why can you not agree in advance (eg, before lift-off of the Mars mission) which techniques/measurements to use for this, and negate the need for light-speed communication at all?
Because adding energy to the particles alters their state randomly. You have to send the outcome of that random transformation to the other end before he can do anything. Consider it like a cryptosystem: upon adding energy, it's "encrypted" with a random key, and the key is given to you. The other end has one shot at putting in the right "key" (and the costs are so that he doesn't gain anything if he just guesses). You have to use ordinary, slower than light communications to get the right key over to whoever is at the other end.
Entanglement-based communications work the same way: after "decryption", the system scrambles itself, and there's no way to measure without decrypting (no-cloning theorem). Therefore, you have to send the "key" to the other end, classically or the message is lost.
Ermm... what is application level encryption? Either a machine you don't trust is decrypting your data or it isn't. By definition of not trusting the machine, you aren't 100% sure what the application does, even if you've run what appears to be the same application on a machine you do trust.
Application level encryption is like a password on your document or RAR file. Open up the program, enter password. If the app has been hacked, so what, the adversary only got access to that particular document (assuming you didn't do anything stupid like assign the same password to all the files on the disk).
That sounds complex. It's more likely that people can't tell whether the crypto is secure or not, so there's no real incentive to use good cryptography. Adding a simple "CALL is_proper, JNE bad_boy" scheme (hello NOPs!) is much easier than having to go through the hassle of using proper cryptography in the proper words, having to check for various attack scenarios and attacks and proof against them, and so on; and the customer isn't going to tell real AES from braindead AES anyway.
Of course, like in "The Market for Lemons", the result is that everybody knows it's impossible to properly secure a USB drive. The lemons drive out the cherries until the market collapses. The usual way of handling that sort of asymmetry failure is through certification, but it seems NIST fell short of the mark here (if the drives were truly certified).
Crazy loner sets off home made firecracker on plane and lights pants on fire. Angry at being thwarted, loner claims al'Qaeda connection and watches the TSA/DHS scorpion sting itself to death yet again.
The problem with all the Single Santa hypotheses is that the one unique Santa can't be in all places at once. So how about this? The mall Santas are all part of a Santa Claus hive mind! Suddenly, we can explain why "Santa" looks so different depending on where you meet him - it's not the same node of the hive. Yet they all dress the same, so they can show how they're part of the same mind: their identity demonstrated by their clothing and the way they act.
Hold on... I am Locutus of Santa. Resistance is futile.
1. Create some incident, or wait for one to happen.
2. Blame it on [insert group here]. It's better if you can find evidence to this effect, but not critical.
3. Propose countermeasures against said group in particular, and more strict authority in general, to solve #2.
4. If someone objects, discredit them with accusations of being one of them, and/or distract the public.
5. Profit!^W Power!
If I'm reading the summary right, that's basically a reactionless drive: a device that can accelerate in space without having to throw anything out the back.
A reactionless drive would be nifty because it can gather kinetic energy very easily (that's what makes travel so cheap with one). However, there's a darker side to that coin. If you can accelerate a ship to near-c with little difficulty, there's not much stopping you from extorting the Earth by threatening to drop the ship (or for that matter, a bunch of tungsten telephone poles traveling at.99c) on them.
Any propulsion system can be used as a weapon. Thus, the good news of the reactionless drive is that one can easily move about in space. The bad news is that one will have to.
I wonder: if a gray hat were to make a worm that contained KP, would that be a good or bad thing? On the one hand, everybody would have KP so the law would be unenforcable. On the other, the authorities might just use it as leverage: okay, everybody has KP, now if we find a crimethinker we just can't convict by any other means, we can get him for possession of KP.
Slashdot Mirror
... after which the paranoid TSA/DHS will mandate SAM sites around every office building in town.
NP is the set of all decision problems where a "yes" answer permits a certificate (proof) that can be verified in polynomial time. For instance, factoring is in NP, because the question "does Q have at most n factors" can be checked in polynomial time by simply multiplying primes together. The certificate, in this case, would be "yes" and a list of prime factors. Very simple problems can also be in NP: for instance, the problem "does there exist an Y for a given X so that X + Y has exactly ten digits in base 10?" is in NP; a yes certificate just gives Y.
A problem in NP does not need to have a polynomial time verifiable certificate for "no" answers. Consider satisfiability: if a circuit can be satisfied (i.e. there are inputs that makes the output true), then there's a certificate: the input itself. On the other hand, if the circuit can't be satisfied (there is no input that makes the output true), it's not very clear how one would make a certificate showing this.
NP-hard is the set of all problems that are at least as hard as the worst problems in NP. To take a very easy example, the halting problem is NP-hard, but it is not in NP.
"At least as hard" has a specific meaning: it means that if you had a machine that could solve the problem in question, you could also solve all problems in NP by transforming the latter into the former in polynomial time. For the halting problem, this is easy: make a Turing machine that halts iff it finds a "yes" certificate for the NP problem instance in question. I think the chess problem is NP-hard as well.
Given the above, NP-complete is simply the intersection of NP and NP-hard. An NP-complete problem, like subset sum or 3-CNF-SAT, is in NP (you can prove an affirmative answer in polynomial time), and it is NP-hard (as hard as all the problems in NP). Thus, if you had a magical machine that would solve an NP-complete problem, you could solve all problems in NP. A corollary of this is that you can turn any instance of an NP-complete problem into an instance of another NP-complete problem. Such a reduction is usually employed to prove that some given problem X is NP-complete: one says "I can turn any and all SAT problem instances into instances of X, therefore if I could solve X I could solve SAT, therefore X is NP-complete".
To answer your question: no. NP-Complete is a subset of NP-hard, but NP-hard is not a subset of NP. It's actually the other way around. NP is a subset of NP-hard. The Wikipedia article on NP-hard has a good diagram showing the relation: http://en.wikipedia.org/wiki/File:P_np_np-complete_np-hard.svg
Perhaps it could be done for three viewers using polarization: horizontal, vertical, and circular.
:p
Or since we're talking about science fiction tech, get out that 1MHz refresh rate monitor and equally sensitive shutter glasses; 16384 distinct viewers should be enough for everyone
An "ordinary" quantum computer is no more powerful than a Turing machine. It probably can't even solve NP-complete problems quickly because there's no way of directing the observation step (where you pull the answer out of the numerous universes) in such a way as to make the right answer show up often enough. This is, technically speaking, an open problem (just like P vs NP), but most believe the answer is a negative (just like P != NP).
I said "ordinary" quantum computer because there have been attempts at making quantum hypercomputers (i.e. computers more powerful than a Turing machine). The best known is Kieu's adiabatic quantum hypercomputation scheme, but that appears to have been refuted. Quantum adiabatic algorithms can be useful (they're a bit like genetic algorithms, only on the quantum level), but apparently they can't bring quantum computers above Turing power; a bit like the Brownian ratchet in this manner, in that it's not as powerful as thought, but still useful.
To sum all of that up: it's unknown whether it's possible to make a quantum computer solve NP-complete in polytime, but most think it's unlikely. It's unknown whether it's possible to make a quantum hypercomputer as well, but most think it's even less likely (although if consciousness would disprove this, that would be... interesting).
Then consider a decision problem like: "given this initial chess setup, with White to move, can White force a win?". That's yes/no, and because it's at least as hard as other problems in NP, it's NP-hard. Yet, if this was NP-complete (as you say it would be, because it's NP-hard and a yes/no problem), then one could make a perfect chess AI if one could solve SAT. Given that chess itself is EXPTIME-complete, I think that would come as a surprise to most people.
You may then say that "of course that problem isn't NP-complete - NP-complete problems can have polytime verifiable proof certificates of a 'yes' solution whereas for the hypothetical chess problem above, that's not true". However, that would merely be a restatement of NP, as a problem is in NP if there's a verifier that executes in polynomial time.
The minesweeper decision problem is actually: "Given these mine hints, is there any possible way mines could be set on the field so that you would get these hints when uncovering these squares?". It's a reduction from SAT. It's NP because given an answer, you can check if the mine hints would be what the problem states. It's NP-hard because SAT is. Together, NP and NP-hard makes NP-complete.
Note that NP-hardness isn't about the average case, it's about the worst case. Many proofs of puzzles being NP-hard essentially go: "I can make a playing field so that the puzzle is only solvable if a related Boolean circuit can be satisfied, and I can transform any Boolean circuit into a playing field in this manner". Such a proof only tells you that these "gadget puzzles" (transformed circuits) are as hard as SAT, it says nothing about the average puzzle.
As another example, consider a problem where the input is either 0, an integer, and a number of integers; or 1, and a number of integers. Then the decision problem is defined as "if the first number is 0, then true if the second is the sum of all the subsequent integers of the input; if the first number is 1, then true if the circuit defined (in some given format) by the subsequent integers can be satisfied". Obviously, this problem is NP-complete because you can turn any SAT problem into an instance of this problem; but if the first number is 0, the problem is trivially decided.
Incidentally, that's part of the reason why cryptosystems based on NP-hard problems have done so badly: while the cryptosystem might be hard to crack, worst case, it usually turns out most instances of encryption can be broken.
I always liked using the plugin architecture for applications that provide it.
And for those that don't, there's always IDA and Olly.
As far as I understand, the kind of filtering China is doing here is based on URLs, so that the firewalls don't have to be too stateful. That's why people in China can contact Google HK just fine, but when they try to search for "tiananmen" or "tank man", boom, timeout.
However, when using SSL, the URLs aren't actually transmitted in plaintext; it would take China a CPU-intensive man-in-the-middle attack to break it. So why can't Google just retaliate by redirecting http://google.com.hk/ to a special https://google.com.hk/ or something to that effect? Further blocking would become cat-and-mouse, and would require China to block Google outright.
It didn't originate with Bismarck, per se, but it did start in Prussia, which is where Bismarck first governed. See http://www.johntaylorgatto.com/chapters/7a.htm for instance.
And just like time bombs, it's nothing a little usage of IDA won't fix.
We could re-use those byproducts, or drastically reduce their amount, if we built breeder reactors.
I think experiments into subcritical reactors would be valuable. Since they "burn" the fuel using an external beam, they can also force fission or transmutation in substances where that doesn't happen naturally. In other words, they can reduce nuclear waste like breeders do, but further, and the output is too mixed to be used for bomb-making purposes - for instance, the plutonium contains Pu-240 which makes a bomb fizzle. They're also less choosy - can use uranium, plutonium, or thorium.
If that's true, how can black holes grow at all? The time dilation effect would seem to suggest that nothing ever reaches the event horizon, because time slows down so it falls increasingly slowly towards the hole. Something must be wrong, because black holes can grow -- but what is it?
It's just proving its own point.
The games weren't, but altering reality was. Everything is equally real... or equally fake.
Please excuse my stupidity, but why can you not agree in advance (eg, before lift-off of the Mars mission) which techniques/measurements to use for this, and negate the need for light-speed communication at all?
Because adding energy to the particles alters their state randomly. You have to send the outcome of that random transformation to the other end before he can do anything. Consider it like a cryptosystem: upon adding energy, it's "encrypted" with a random key, and the key is given to you. The other end has one shot at putting in the right "key" (and the costs are so that he doesn't gain anything if he just guesses). You have to use ordinary, slower than light communications to get the right key over to whoever is at the other end.
Entanglement-based communications work the same way: after "decryption", the system scrambles itself, and there's no way to measure without decrypting (no-cloning theorem). Therefore, you have to send the "key" to the other end, classically or the message is lost.
If everything is easy, what is worthwhile?
Yay for a hive mind, perhaps?
Ermm... what is application level encryption? Either a machine you don't trust is decrypting your data or it isn't. By definition of not trusting the machine, you aren't 100% sure what the application does, even if you've run what appears to be the same application on a machine you do trust.
Application level encryption is like a password on your document or RAR file. Open up the program, enter password. If the app has been hacked, so what, the adversary only got access to that particular document (assuming you didn't do anything stupid like assign the same password to all the files on the disk).
That sounds complex. It's more likely that people can't tell whether the crypto is secure or not, so there's no real incentive to use good cryptography. Adding a simple "CALL is_proper, JNE bad_boy" scheme (hello NOPs!) is much easier than having to go through the hassle of using proper cryptography in the proper words, having to check for various attack scenarios and attacks and proof against them, and so on; and the customer isn't going to tell real AES from braindead AES anyway.
Of course, like in "The Market for Lemons", the result is that everybody knows it's impossible to properly secure a USB drive. The lemons drive out the cherries until the market collapses. The usual way of handling that sort of asymmetry failure is through certification, but it seems NIST fell short of the mark here (if the drives were truly certified).
More like:
Crazy loner sets off home made firecracker on plane and lights pants on fire. Angry at being thwarted, loner claims al'Qaeda connection and watches the TSA/DHS scorpion sting itself to death yet again.
The problem with all the Single Santa hypotheses is that the one unique Santa can't be in all places at once. So how about this? The mall Santas are all part of a Santa Claus hive mind! Suddenly, we can explain why "Santa" looks so different depending on where you meet him - it's not the same node of the hive. Yet they all dress the same, so they can show how they're part of the same mind: their identity demonstrated by their clothing and the way they act.
Hold on... I am Locutus of Santa. Resistance is futile.
But Santa uses a ZPM!
It's more general than that:
1. Create some incident, or wait for one to happen.
2. Blame it on [insert group here]. It's better if you can find evidence to this effect, but not critical.
3. Propose countermeasures against said group in particular, and more strict authority in general, to solve #2.
4. If someone objects, discredit them with accusations of being one of them, and/or distract the public. 5. Profit!^W Power!
If I'm reading the summary right, that's basically a reactionless drive: a device that can accelerate in space without having to throw anything out the back.
.99c) on them.
A reactionless drive would be nifty because it can gather kinetic energy very easily (that's what makes travel so cheap with one). However, there's a darker side to that coin. If you can accelerate a ship to near-c with little difficulty, there's not much stopping you from extorting the Earth by threatening to drop the ship (or for that matter, a bunch of tungsten telephone poles traveling at
Any propulsion system can be used as a weapon. Thus, the good news of the reactionless drive is that one can easily move about in space. The bad news is that one will have to.
I wonder: if a gray hat were to make a worm that contained KP, would that be a good or bad thing? On the one hand, everybody would have KP so the law would be unenforcable. On the other, the authorities might just use it as leverage: okay, everybody has KP, now if we find a crimethinker we just can't convict by any other means, we can get him for possession of KP.