The second they perfect this, they will be able to try all the keys at once and the right one will be solved instantly. All of our current generation of encryption relies on n-p complete algorithms and will become worthless
There is a lot wrong with this.
First of all, quantum computers cannot as far as we know solve NP-complete problems efficiently. There's no known way for that to happen, and most experts expect they cannot. What they can do, is solve specific classes of problems more efficiently than classical computers. The most obvious example of this is factoring integers, which seems to be very difficult for a classical machine, but which can be done quickly by a quantum computer using Shor's algorithm. http://en.wikipedia.org/wiki/Shor's_algorithm
Second, none of these algorithms are instantaneous or even remotely so, but rather scale wit the size of the input, generally with a polynomial.
Third, while many forms of crypto would be vulnerable, including RSA and elliptic curve cryptography, not all forms of cryptography have known vulnerabilities. This connects with the earlier issue of NP completeness. No form of crypto relies at this point on an NP complete problem. Factoring for example is in NP (which means roughly that one can easily convince someone that one actually has the factorization), but it is likely not NP complete. A problem is NP complete if (roughly speaking) it lives in NP, and if you have access to a black box that solves the problem then you can solve all NP problems. At this point, factoring is strongly suspected not to be NP complete, because that would lead to the collapse of the polynomial hierarchy http://en.wikipedia.org/wiki/Polynomial_hierarchy, which is strongly conjectured to occur.
Quantum computers will likely have real world consequences if we ever get them to work on a large scale, and some of those consequences will be cryptographic. But thinking that they'll somehow blow up all cryptography is just hype. If you want to read a good book, without hype, that does a good job of explaining how quantum computing actually works, I recommend "Quantum Computing Since Democritus" by Scott Aaaronson. The book does assume some slight comfort with linear algebra, a very tiny amount of group theory, and some calculus, but that's it. It is aimed at people in technical fields other than quantum computing to understand what it is about. It is highly readable, and I strongly recommend it.
Somalia is the result of a failed state, what was formerly known as the Somali Democratic Republic, which was governed under a single-party, Socialist rule. The resulting mayhem has nothing to do with libertarian or anarchist principles,
What does it even mean to talk about a "failed state" if you don't even want state actors with police power?
In any case, what actually gives you a functional civilization is a large number of individuals trading voluntarily amongst themselves to better their own situations; profit is not merely the transfer of wealth, but rather the creation of wealth.
Which utterly ignores the basic issues of public goods and externalities that have already been brought up. Yes, markets and trade is important. But we have theorems and empirical data about when markets work and when they don't. High transaction costs with large externalities (either positive or negative) or with public goods aren't those circumstances. There's no way to do large-scale medical research in a way that doesn't benefit everyone. This is stuff you'd learn if you took an actual intro econ class at any university.
Ah yes, the old fire and police argument. Guess who runs those? Hint: unless you live on a military base or in DC, it's not the federal government.
The response about police, and fire was in regards to mfwitten's essentially anarchist claim, not a general defense of a federal government (different government systems work). But you'll note that my comment listed three things, police, fire and military. Moreover, the federal government is heavily involved in police activities: the FBI is one of many examples that functions doing what amounts to police work. Whether the specific matter discussed by TFA is a good idea or not is a *distinct* issue which could be discussed and an actual discussion of that might be interesting, but it has nothing to do with mfwitten's points or my own.
If you don't like living a government at all, then go be an anarchist elsewhere. Living in a country where we have these things is what makes this a functional civilization and not chaos. As long as you are here, please pay your share. If you'd like to opt-out go to Somalia.
Because you can say that for every government thing, fire departments, police departments, military defense. These all benefit everyone in a society, so there's no easy way to prevent you from benefiting. This is related to what economists call a "public good." And the only way to make sure public goods get funded is for everyone to pay a tiny amount. If you don't think something is a public good that justifies such a situation, then you should talk to your congressmen. Of course, if you think that you shouldn't pay for any of them, then that's your problem.
There is a lot of dislike of Obama due to his race. There's no question about that. But that doesn't lesson the seriousness of legitimate criticism. For that matter, even if someone is motivated by racism to make a specific criticism it doesn't impact the validity of that criticism. To go full-Godwin, if Hitler said that 1+1=2 as part of an argument to kill all the Jews, it doesn't make 1+1=2 less true.
Please don't get confuse by a nickname that a particle happens to have. In this context, the "God Particle" is a pleasant PG-rated version of the original nickname "the Goddamn Particle." Your claim makes about as much sense as for example someone claiming that general relativity somehow supports moral relativism. Similar sounding words aren't automatically connected.
The standard conjecture actually is that BQP and NP are mutually incomparable (that is neither contains the other). So it is likely that there are computations one can do on a quantum computer which have no way of being checked efficiently on a classical computer.
Saying that it exists somewhere in NP-Hard may be technically true, in that NP-Hard encompasses all classes NP-Complete and harder (and UNDECIDABLE is definitely harder).
So part of the neat thing is that this isn't actually true. There are undecidable languages that are *not* NP-hard. Consider for example some computable listing of Turing machines. Now consider the language L that accepts iff L is a string of n 1s where n=Ackermann(m) for some m such that the mth Turing machine halts on the blank tape. This language is undecidable and is also not NP-hard. That is, if you have an oracle L, then one can show that P = NP if and only P^L = NP^L. And one can do some even stranger, things like, instead of using L, one could use a similarly defined language K where one insists that that the mth machine halt on all tape inputs. This language is actually *harder* than the halting problem in that there is a Turing machine that with a K oracle can solve the halting problem but there's no Turing machine that can decide K even when given access to a halting oracle.
But if such an oracle could exist, it would mean P=NP simultaneous with P != NP, and that's just for starters -- a short list of the contradictions that would be forced to be true if any hypercomputational oracle existed is the sort of thing that will give mathematicians nightmares.
You are either confused or are using "exists" in a highly non-standard fashion. In the formal definition of an oracle, one isn't talking about whether it is a Turing machine or not. Formally speaking, an oracle is just a language, and that can be any language. All oracles exist. Whether one finds a given oracle type interesting is a different issue. Note that your imprecise statement above is precisely why we have the ^ notation, so we can talk about things like P^O and NP^O for some oracle. And here's part of the important point: a hypercomputation oracle exists just as much as an NP or a PSPACE oracle "exists". If you mean exists in the sense of there being a Turing machine then, likely none of them exist. If you mean exist in the sense that I can talk about them mathematically, then yes they do. If it helps, it may help you to realize that we can actually construct computable oracles X and Y such that P^X=NP^X and P^Y != NP^Y. That's not a contradiction, yet it seems that you think that would be a contradiction. Or am I misunderstanding you?
And no, Davis is not condemning people trying to do real hypercomputation. He's condemning the entire field of hypercomputation as a discipline.
I'd be interested in the original context of his quote then, rather than your second-hand, paraphrase,
Countries prepare war games involving invasions to or from nearby countries all the time. This just isn't that big a deal. The US likely has plans to invade Canada if necessary (although at least publicly the last one was canceled in the 1930s http://en.wikipedia.org/wiki/War_Plan_Red), and almost certainly has plans to invade Mexico. The Swiss have made their entire foreign policy center around a combination of neutrality and being prepared to repulse any invader, so this shouldn't be at all surprising.
No. The Halting Problem belongs to class UNDECIDABLE, not class NP-Hard. I admire your attempt at rationalizing it, but Alan Turing proved this to the world's satisfaction. If you wish to prove the Halting Problem does not belong to UNDECIDABLE then you're going to have an uphill road to hoe.
Yes, the Hatlting problem is undecidable. That doesn't stop it from being NP-hard also. This isn't that complicated: nothing in the standard definition of NP-hard assumes we are talking about a decidable language.
Your argument involving an oracle that solves the Halting Problem is absurd because you're assuming the existence of hypercomputation -- and if such an oracle could exist, then we would simultaneously have P=NP and P != NP. Martin Davis [wikipedia.org] has gone so far as to declare hypercomputation both "a myth" and "a nonexistent discipline." Those are strong words coming from one of the brightest lights in the field of computational theory and computational complexity.
It's a bedrock principle of logic that if you start from a false proposition anything can be proven. You assume the existence of an oracle that can solve the Halting Problem. This is a false proposition. Anything can be proven once you make oracular assumptions.
Assuming one has an oracle is not the same thing as assuming one has a Turing machine that does something. That's in fact part of the entire point of why we speak about oracles instead of assuming one has a Turing machine that does stuff. So if it turns out that one doesn't have such a Turing machine, one can still talk about the results in a way that isn't vacuous. And no, adding in oracles that a Turing machine can't do is a pretty standard thing. For example, the entire polynomial hierarchy is defined by a series of steps where new class allows an oracle from the previous class http://en.wikipedia.org/wiki/Polynomial_hierarchy. Note that this involves using an NP complete oracle at the lowest level and we can talk about this even though there's (very likely) no Turing machine that acts like such an oracle.
We can also talk about which theorems do and do not go through when one has an arbitrary oracle. This leads to the notion of relativising proofs. Thus for example, if one has a PSPACE complete oracle X, then one has that P^X=NP^X, Of course, what makes this noteworthy is that many classes of arguments do in fact go through for all oracles. Thus for example, naive diagonolization which shows that P is not equal to EXP, and this goes through for any oracle you please, P^Y != EXP^Y, and that applies to any oracle. This was one of the things that showed that P ?= NP was a genuinely difficult problem.
As to Davis's point, I presume he's talking about people trying to do hypercomputation in the real world, such as by doing ridiculous tricks with black holes. It is extremely unlikely that in our physical universe we can have any access to any form of hypercomputation. But that doesn't make the oracle notion not useful, and indeed there are many papers talking about all sorts of oracle types (for example, there's been a recent bit of interest in the class ZPP^NP which is turning out to show up in a surprisingly large class of natural contexts). And note that in fact, something much stronger is likely true than a lack of hypercomputation in our universe. Pick your favorite computable very fast growing function, like say the Ackermann function. It is highly likely that say whether A(1000) +1 has an even or odd number of distinct prime factors is a question that cannot be answered given the computational resources of our universe, even though from a computability perspective this is trivial, and describing the question itself requires only a very short statement in ZFC. But that situation doesn't reduce all ability to talk about the Ackermann function or use it.
I fail to see why you are insisting on going out of your way to interpret everything people say in a way that maximizes the stupidity of their statements or to label people you apparently can't communicate with as being trolls.
The Halting Problem is UNDECIDABLE -- it exists in a complexity class considerably beyond what is normally thought of as 'NP-Hard'.
One is completely capable of talking about undecidable problems being NP-hard or not. In fact, one neat thing is that one can have a problem that is equivalent to the Halting problem in the computability sense that is not NP-hard, even though the Halting problem itself is NP-hard. This follows from a padding argument. But the normal version of the Halting problem is NP-hard. Slightly more formally, let A be an oracle that solves the halting problem, then, NP is contained in P^A. In fact, one can talk about the complexity classes with uncomputable oracles, and this is actually something done quite frequently, since many common constructions involve random oracles and a random oracle is with high probability undecidable (and onestandard example of oracle separations between P and NP uses such a random oracle). So talking about computational complexity is something we are more than capable of doing with undecidable languages involved, and we can actually get interesting results.
And if you don't understand my parenthetical remark, well... that should be taken as a sign that your computational theory is seriously lacking. The meaning is quite clear to someone who has a proper understanding of what complexity class NP-Hard is about.
It may help to reread what I wrote, or maybe English isn't your first language? I didn't say I didn't "understand" the sentence, I said I failed to see the point you were making, because " since no one has claimed that being able to solve some NP hard problem lets you solve all NP hard problems." Observing that your true sentence has nothing to do with what is being discussed isn't the same as not understanding your sentence. Frankly, it looks like you've become unnecessarily emotionally involved in this discussion: I suggest you wait a day or two and then reread it.
If you can solve it in polynomial time, then it's in P. Even under your revised definition, you're implicitly arguing that P=NP, because that's the only way you can solve an NP-Hard problem in polynomial time. (And even then, you would only be able to solve the NP-Complete subset of NP-Hard.)
What? No. Notice I didn't say anything about how you could solve the NP hard problem. If one has an oracle that can solve the problem then that's fine for this purpose phrasing things in terms of oracles is a pretty standard approach. Also, I fail to see the point of your parenthetical remark since no one has claimed that being able to solve some NP hard problem lets you solve all NP hard problems. That would just be stupid given that the standard version of the halting problem is NP-hard and obviously not in NP.
Um, so you are correct in that my statement wasn't quite correct- I should have said instead of " A class of problems is NP hard if being able to solve it allows one to solve all NP problems in polynomial time" that " A class of problems is NP hard if being able to solve it in polynomial time allows one to solve all NP problems in polynomial time." But the person I was replying to is still wrong. Talking about being NP hard in one direction and not the other is just nonsense. I suppose if you wanted to really stretch things you could try to interpret that as a distinction between solution and verification, but that doesn't make sense since they would still be wrong to talk about NP-hard when they mean NP problems; There are a lot of NP hard problems which are not themselves in NP, and factoring is almost certainly not NP hard (if it were the polynomial hierarchy would exhibit massive collapse since factoring is in co-NP intersect NP).
Many problems are NP-hard in one direction, but not the other way around.
This statement is at best confused, and is essentially wrong. A class of problem is in NP if when the answer is yes, they have a polynomial length proofs that can be checked in polynomial time. A class of problems is NP hard if being able to solve it allows one to solve all NP problems in polynomial time. It does not make sense to talk about being NP-hard in any direction. What you are talking about are problems like factoring but not because they are NP hard, but because they are likely intermediate in difficulty between the NP-hard problems and things that can be solved in polynomial time. It is unlikely that any NP hard problem can be solved in polynomial time on a quantum computer (formally speaking, the standard conjecture is that NP is not contained in BQP).
Right now, computational complexity classes for quantum computing fall into a variety of different categories. BQP is the set of problems where a quantum computer can efficiently solve them with high probability , but we don't have a good way of verifying that a given solution is correct. It is suspected that this class is strictly larger than the set of problems which can be easily solved on a quantum computer and the solution can be checked on a classical computer, which is ZBQP https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Z#zbqp. (There are some slight technical issue here in terms of distinguishing programs which just answer yes or no and programs which can give more than 1 bit of data out.) So for example, factoring, is in ZBQP because a classical computer can verify the result by just multiplying the factors together (as well as checking that they are prime, which can be done in polynomial time).
t this point, we can't prove that P != BQP, let alone that P!=ZBQP or that ZBQP!=BQP (since P is contained in ZBQP which is contained in BQP, either of the second two statements would imply the third). Worse, we can't even prove the much weaker statement that P != PSPACE (essentially that there are things you can do with polynomial memory that you can't do in polynomial time).
What this work does is suggests is that thinking in terms of ZBQP may not be that important in practice, since it may be easy to verify quantum computations with other quantum computers in a reliable fashion.
I strongly recommend that people interested in this subject first read Scott Aaronson's book "Quantum Comptuing Since Democritus" which discusses a lot of the relevant issues and provides a decent primer on the subject. (Assuming only some decent familiarity with linear algebra and a little calculus). Note that TFA like many articles about quantum computing for the popular press has statements that are not strictly speaking true to the point where they border on being wrong. The most egregious error in TFA (which is a very common one) is the claim that "Because each qubit can embody so many different states, quantum computers could compute certain classes of problems dramatically faster than regular computers by running through every combination of possibilities at once." - This is wrong. Quantum computers don't work by checking every combination at once- if they could they'd be able to handle a lot of problems they (probably) can't.
This is wrong. The density of twin primes has basically nothing to do with RSA or factoring. The vast majority of primes aren't twin primes, and the vast majority of primes don't have a prime near them (that is within o(log p)), and actual RSA keys avoid very close primes anyhow. That's before we get to the fact that work like Zhang's is basically non-constructive. There are possible serious issues with factoring, and some people like Henry Cohn have expressed skepticism about claims that factoring is genuinely hard http://research.microsoft.com/en-us/um/people/cohn/Thoughts/factoring.html, but none of this has anything to do with Yitang Zhang's work.
The paper in question has specific predictions about what we should expect to see when we examine pulsars that are near black holes and moreover those predictions look like they should be testable with only slightly more advanced technology than we have now if we take the time to make the long-term observations necessary. That's the primary difference: testable, predictable results. In contrast, religion generally either fails at making novel predictions at all, or makes novel predictions generally about eschatological issues (that is end of the world) that always turn out to be wrong.
People say this about almost all new technologies. People worried that the internet would divide the world into haves and have-nots. What happened? It became so ubiquitous that even people in low income brackets have internet access in many forms. As something becomes more used, the cost goes down, and then more people can afford it, and then it goes down even more. Cars, computers, internet, laptops, cell phones, TVs, etc. If this works, it won't take long before it is available to everyone.
That quantum encryption system that we weren't using, weren't evaluating, and weren't even capable of implementing, has been saved!
The development of quantum crypto is happening and there's a lot of work on it. Moreover, the claim that we aren't capable of implementing is false. There are even commercial implementations. See http://en.wikipedia.org/wiki/Quantum_key_distribution#Commercial for a list. Computer networks using secure quantum crypto have also been made (scroll just a bit further in that Wikipedia article).
Is quantum entanglement the only physical resource that allows for such strong encryption?
The original quantum crypto protocol BB84 http://en.wikipedia.org/wiki/BB84 does not require entanglement, and is secure if one is still sending single photons at a time.
Very little. You don't generally get paid for papers. The money from the journals in almost all fields goes to the publishers, not anyone in the field.
Yes, it sometimes takes a while to get access unfortunately. There are two main causes: 1) Lack of time to inform the team. This most frequently occurs when the person has taken a sudden turn for the worse in their medical condition. 2) Uncooperative doctors and nurses. Some hospital personnel don't cooperate with the cryo prep teams, which can lead to critical delays. So this situation is by no means fool proof.
Slashdot Mirror
The second they perfect this, they will be able to try all the keys at once and the right one will be solved instantly. All of our current generation of encryption relies on n-p complete algorithms and will become worthless
There is a lot wrong with this.
First of all, quantum computers cannot as far as we know solve NP-complete problems efficiently. There's no known way for that to happen, and most experts expect they cannot. What they can do, is solve specific classes of problems more efficiently than classical computers. The most obvious example of this is factoring integers, which seems to be very difficult for a classical machine, but which can be done quickly by a quantum computer using Shor's algorithm. http://en.wikipedia.org/wiki/Shor's_algorithm
Second, none of these algorithms are instantaneous or even remotely so, but rather scale wit the size of the input, generally with a polynomial.
Third, while many forms of crypto would be vulnerable, including RSA and elliptic curve cryptography, not all forms of cryptography have known vulnerabilities. This connects with the earlier issue of NP completeness. No form of crypto relies at this point on an NP complete problem. Factoring for example is in NP (which means roughly that one can easily convince someone that one actually has the factorization), but it is likely not NP complete. A problem is NP complete if (roughly speaking) it lives in NP, and if you have access to a black box that solves the problem then you can solve all NP problems. At this point, factoring is strongly suspected not to be NP complete, because that would lead to the collapse of the polynomial hierarchy http://en.wikipedia.org/wiki/Polynomial_hierarchy, which is strongly conjectured to occur.
Quantum computers will likely have real world consequences if we ever get them to work on a large scale, and some of those consequences will be cryptographic. But thinking that they'll somehow blow up all cryptography is just hype. If you want to read a good book, without hype, that does a good job of explaining how quantum computing actually works, I recommend "Quantum Computing Since Democritus" by Scott Aaaronson. The book does assume some slight comfort with linear algebra, a very tiny amount of group theory, and some calculus, but that's it. It is aimed at people in technical fields other than quantum computing to understand what it is about. It is highly readable, and I strongly recommend it.
This is sort of amusing since PopSci decided to stop having comments. They did so because of evidence that comments really are a net negative. See http://www.sciencemag.org/content/339/6115/40.summary?sid=9b37fd35-5bb4-4bbe-89e7-b1054f5ecdd1 and http://news.yahoo.com/blogs/sideshow/popular-science-ends-reader-comments--says-practice-is-bad-for-science-002245622.html.
Your signature seems surprisingly accurate in this particular instance.
Somalia is the result of a failed state, what was formerly known as the Somali Democratic Republic, which was governed under a single-party, Socialist rule. The resulting mayhem has nothing to do with libertarian or anarchist principles,
What does it even mean to talk about a "failed state" if you don't even want state actors with police power?
In any case, what actually gives you a functional civilization is a large number of individuals trading voluntarily amongst themselves to better their own situations; profit is not merely the transfer of wealth, but rather the creation of wealth.
Which utterly ignores the basic issues of public goods and externalities that have already been brought up. Yes, markets and trade is important. But we have theorems and empirical data about when markets work and when they don't. High transaction costs with large externalities (either positive or negative) or with public goods aren't those circumstances. There's no way to do large-scale medical research in a way that doesn't benefit everyone. This is stuff you'd learn if you took an actual intro econ class at any university.
Ah yes, the old fire and police argument. Guess who runs those? Hint: unless you live on a military base or in DC, it's not the federal government.
The response about police, and fire was in regards to mfwitten's essentially anarchist claim, not a general defense of a federal government (different government systems work). But you'll note that my comment listed three things, police, fire and military. Moreover, the federal government is heavily involved in police activities: the FBI is one of many examples that functions doing what amounts to police work. Whether the specific matter discussed by TFA is a good idea or not is a *distinct* issue which could be discussed and an actual discussion of that might be interesting, but it has nothing to do with mfwitten's points or my own.
If you don't like living a government at all, then go be an anarchist elsewhere. Living in a country where we have these things is what makes this a functional civilization and not chaos. As long as you are here, please pay your share. If you'd like to opt-out go to Somalia.
Because you can say that for every government thing, fire departments, police departments, military defense. These all benefit everyone in a society, so there's no easy way to prevent you from benefiting. This is related to what economists call a "public good." And the only way to make sure public goods get funded is for everyone to pay a tiny amount. If you don't think something is a public good that justifies such a situation, then you should talk to your congressmen. Of course, if you think that you shouldn't pay for any of them, then that's your problem.
There is a lot of dislike of Obama due to his race. There's no question about that. But that doesn't lesson the seriousness of legitimate criticism. For that matter, even if someone is motivated by racism to make a specific criticism it doesn't impact the validity of that criticism. To go full-Godwin, if Hitler said that 1+1=2 as part of an argument to kill all the Jews, it doesn't make 1+1=2 less true.
Please don't get confuse by a nickname that a particle happens to have. In this context, the "God Particle" is a pleasant PG-rated version of the original nickname "the Goddamn Particle." Your claim makes about as much sense as for example someone claiming that general relativity somehow supports moral relativism. Similar sounding words aren't automatically connected.
The standard conjecture actually is that BQP and NP are mutually incomparable (that is neither contains the other). So it is likely that there are computations one can do on a quantum computer which have no way of being checked efficiently on a classical computer.
Saying that it exists somewhere in NP-Hard may be technically true, in that NP-Hard encompasses all classes NP-Complete and harder (and UNDECIDABLE is definitely harder).
So part of the neat thing is that this isn't actually true. There are undecidable languages that are *not* NP-hard. Consider for example some computable listing of Turing machines. Now consider the language L that accepts iff L is a string of n 1s where n=Ackermann(m) for some m such that the mth Turing machine halts on the blank tape. This language is undecidable and is also not NP-hard. That is, if you have an oracle L, then one can show that P = NP if and only P^L = NP^L. And one can do some even stranger, things like, instead of using L, one could use a similarly defined language K where one insists that that the mth machine halt on all tape inputs. This language is actually *harder* than the halting problem in that there is a Turing machine that with a K oracle can solve the halting problem but there's no Turing machine that can decide K even when given access to a halting oracle.
But if such an oracle could exist, it would mean P=NP simultaneous with P != NP, and that's just for starters -- a short list of the contradictions that would be forced to be true if any hypercomputational oracle existed is the sort of thing that will give mathematicians nightmares.
You are either confused or are using "exists" in a highly non-standard fashion. In the formal definition of an oracle, one isn't talking about whether it is a Turing machine or not. Formally speaking, an oracle is just a language, and that can be any language. All oracles exist. Whether one finds a given oracle type interesting is a different issue. Note that your imprecise statement above is precisely why we have the ^ notation, so we can talk about things like P^O and NP^O for some oracle. And here's part of the important point: a hypercomputation oracle exists just as much as an NP or a PSPACE oracle "exists". If you mean exists in the sense of there being a Turing machine then, likely none of them exist. If you mean exist in the sense that I can talk about them mathematically, then yes they do. If it helps, it may help you to realize that we can actually construct computable oracles X and Y such that P^X=NP^X and P^Y != NP^Y. That's not a contradiction, yet it seems that you think that would be a contradiction. Or am I misunderstanding you?
And no, Davis is not condemning people trying to do real hypercomputation. He's condemning the entire field of hypercomputation as a discipline.
I'd be interested in the original context of his quote then, rather than your second-hand, paraphrase,
Countries prepare war games involving invasions to or from nearby countries all the time. This just isn't that big a deal. The US likely has plans to invade Canada if necessary (although at least publicly the last one was canceled in the 1930s http://en.wikipedia.org/wiki/War_Plan_Red), and almost certainly has plans to invade Mexico. The Swiss have made their entire foreign policy center around a combination of neutrality and being prepared to repulse any invader, so this shouldn't be at all surprising.
No. The Halting Problem belongs to class UNDECIDABLE, not class NP-Hard. I admire your attempt at rationalizing it, but Alan Turing proved this to the world's satisfaction. If you wish to prove the Halting Problem does not belong to UNDECIDABLE then you're going to have an uphill road to hoe.
Yes, the Hatlting problem is undecidable. That doesn't stop it from being NP-hard also. This isn't that complicated: nothing in the standard definition of NP-hard assumes we are talking about a decidable language.
Your argument involving an oracle that solves the Halting Problem is absurd because you're assuming the existence of hypercomputation -- and if such an oracle could exist, then we would simultaneously have P=NP and P != NP. Martin Davis [wikipedia.org] has gone so far as to declare hypercomputation both "a myth" and "a nonexistent discipline." Those are strong words coming from one of the brightest lights in the field of computational theory and computational complexity.
It's a bedrock principle of logic that if you start from a false proposition anything can be proven. You assume the existence of an oracle that can solve the Halting Problem. This is a false proposition. Anything can be proven once you make oracular assumptions.
Assuming one has an oracle is not the same thing as assuming one has a Turing machine that does something. That's in fact part of the entire point of why we speak about oracles instead of assuming one has a Turing machine that does stuff. So if it turns out that one doesn't have such a Turing machine, one can still talk about the results in a way that isn't vacuous. And no, adding in oracles that a Turing machine can't do is a pretty standard thing. For example, the entire polynomial hierarchy is defined by a series of steps where new class allows an oracle from the previous class http://en.wikipedia.org/wiki/Polynomial_hierarchy. Note that this involves using an NP complete oracle at the lowest level and we can talk about this even though there's (very likely) no Turing machine that acts like such an oracle.
We can also talk about which theorems do and do not go through when one has an arbitrary oracle. This leads to the notion of relativising proofs. Thus for example, if one has a PSPACE complete oracle X, then one has that P^X=NP^X, Of course, what makes this noteworthy is that many classes of arguments do in fact go through for all oracles. Thus for example, naive diagonolization which shows that P is not equal to EXP, and this goes through for any oracle you please, P^Y != EXP^Y, and that applies to any oracle. This was one of the things that showed that P ?= NP was a genuinely difficult problem. As to Davis's point, I presume he's talking about people trying to do hypercomputation in the real world, such as by doing ridiculous tricks with black holes. It is extremely unlikely that in our physical universe we can have any access to any form of hypercomputation. But that doesn't make the oracle notion not useful, and indeed there are many papers talking about all sorts of oracle types (for example, there's been a recent bit of interest in the class ZPP^NP which is turning out to show up in a surprisingly large class of natural contexts). And note that in fact, something much stronger is likely true than a lack of hypercomputation in our universe. Pick your favorite computable very fast growing function, like say the Ackermann function. It is highly likely that say whether A(1000) +1 has an even or odd number of distinct prime factors is a question that cannot be answered given the computational resources of our universe, even though from a computability perspective this is trivial, and describing the question itself requires only a very short statement in ZFC. But that situation doesn't reduce all ability to talk about the Ackermann function or use it.
The Halting Problem is UNDECIDABLE -- it exists in a complexity class considerably beyond what is normally thought of as 'NP-Hard'.
One is completely capable of talking about undecidable problems being NP-hard or not. In fact, one neat thing is that one can have a problem that is equivalent to the Halting problem in the computability sense that is not NP-hard, even though the Halting problem itself is NP-hard. This follows from a padding argument. But the normal version of the Halting problem is NP-hard. Slightly more formally, let A be an oracle that solves the halting problem, then, NP is contained in P^A. In fact, one can talk about the complexity classes with uncomputable oracles, and this is actually something done quite frequently, since many common constructions involve random oracles and a random oracle is with high probability undecidable (and onestandard example of oracle separations between P and NP uses such a random oracle). So talking about computational complexity is something we are more than capable of doing with undecidable languages involved, and we can actually get interesting results.
And if you don't understand my parenthetical remark, well... that should be taken as a sign that your computational theory is seriously lacking. The meaning is quite clear to someone who has a proper understanding of what complexity class NP-Hard is about.
It may help to reread what I wrote, or maybe English isn't your first language? I didn't say I didn't "understand" the sentence, I said I failed to see the point you were making, because " since no one has claimed that being able to solve some NP hard problem lets you solve all NP hard problems." Observing that your true sentence has nothing to do with what is being discussed isn't the same as not understanding your sentence. Frankly, it looks like you've become unnecessarily emotionally involved in this discussion: I suggest you wait a day or two and then reread it.
If you can solve it in polynomial time, then it's in P. Even under your revised definition, you're implicitly arguing that P=NP, because that's the only way you can solve an NP-Hard problem in polynomial time. (And even then, you would only be able to solve the NP-Complete subset of NP-Hard.)
What? No. Notice I didn't say anything about how you could solve the NP hard problem. If one has an oracle that can solve the problem then that's fine for this purpose phrasing things in terms of oracles is a pretty standard approach. Also, I fail to see the point of your parenthetical remark since no one has claimed that being able to solve some NP hard problem lets you solve all NP hard problems. That would just be stupid given that the standard version of the halting problem is NP-hard and obviously not in NP.
Um, so you are correct in that my statement wasn't quite correct- I should have said instead of " A class of problems is NP hard if being able to solve it allows one to solve all NP problems in polynomial time" that " A class of problems is NP hard if being able to solve it in polynomial time allows one to solve all NP problems in polynomial time." But the person I was replying to is still wrong. Talking about being NP hard in one direction and not the other is just nonsense. I suppose if you wanted to really stretch things you could try to interpret that as a distinction between solution and verification, but that doesn't make sense since they would still be wrong to talk about NP-hard when they mean NP problems; There are a lot of NP hard problems which are not themselves in NP, and factoring is almost certainly not NP hard (if it were the polynomial hierarchy would exhibit massive collapse since factoring is in co-NP intersect NP).
Many problems are NP-hard in one direction, but not the other way around.
This statement is at best confused, and is essentially wrong. A class of problem is in NP if when the answer is yes, they have a polynomial length proofs that can be checked in polynomial time. A class of problems is NP hard if being able to solve it allows one to solve all NP problems in polynomial time. It does not make sense to talk about being NP-hard in any direction. What you are talking about are problems like factoring but not because they are NP hard, but because they are likely intermediate in difficulty between the NP-hard problems and things that can be solved in polynomial time. It is unlikely that any NP hard problem can be solved in polynomial time on a quantum computer (formally speaking, the standard conjecture is that NP is not contained in BQP).
Right now, computational complexity classes for quantum computing fall into a variety of different categories. BQP is the set of problems where a quantum computer can efficiently solve them with high probability , but we don't have a good way of verifying that a given solution is correct. It is suspected that this class is strictly larger than the set of problems which can be easily solved on a quantum computer and the solution can be checked on a classical computer, which is ZBQP https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Z#zbqp. (There are some slight technical issue here in terms of distinguishing programs which just answer yes or no and programs which can give more than 1 bit of data out.) So for example, factoring, is in ZBQP because a classical computer can verify the result by just multiplying the factors together (as well as checking that they are prime, which can be done in polynomial time).
t this point, we can't prove that P != BQP, let alone that P!=ZBQP or that ZBQP!=BQP (since P is contained in ZBQP which is contained in BQP, either of the second two statements would imply the third). Worse, we can't even prove the much weaker statement that P != PSPACE (essentially that there are things you can do with polynomial memory that you can't do in polynomial time).
What this work does is suggests is that thinking in terms of ZBQP may not be that important in practice, since it may be easy to verify quantum computations with other quantum computers in a reliable fashion.
I strongly recommend that people interested in this subject first read Scott Aaronson's book "Quantum Comptuing Since Democritus" which discusses a lot of the relevant issues and provides a decent primer on the subject. (Assuming only some decent familiarity with linear algebra and a little calculus). Note that TFA like many articles about quantum computing for the popular press has statements that are not strictly speaking true to the point where they border on being wrong. The most egregious error in TFA (which is a very common one) is the claim that "Because each qubit can embody so many different states, quantum computers could compute certain classes of problems dramatically faster than regular computers by running through every combination of possibilities at once." - This is wrong. Quantum computers don't work by checking every combination at once- if they could they'd be able to handle a lot of problems they (probably) can't.
This is wrong. The density of twin primes has basically nothing to do with RSA or factoring. The vast majority of primes aren't twin primes, and the vast majority of primes don't have a prime near them (that is within o(log p)), and actual RSA keys avoid very close primes anyhow. That's before we get to the fact that work like Zhang's is basically non-constructive. There are possible serious issues with factoring, and some people like Henry Cohn have expressed skepticism about claims that factoring is genuinely hard http://research.microsoft.com/en-us/um/people/cohn/Thoughts/factoring.html, but none of this has anything to do with Yitang Zhang's work.
The paper in question has specific predictions about what we should expect to see when we examine pulsars that are near black holes and moreover those predictions look like they should be testable with only slightly more advanced technology than we have now if we take the time to make the long-term observations necessary. That's the primary difference: testable, predictable results. In contrast, religion generally either fails at making novel predictions at all, or makes novel predictions generally about eschatological issues (that is end of the world) that always turn out to be wrong.
People say this about almost all new technologies. People worried that the internet would divide the world into haves and have-nots. What happened? It became so ubiquitous that even people in low income brackets have internet access in many forms. As something becomes more used, the cost goes down, and then more people can afford it, and then it goes down even more. Cars, computers, internet, laptops, cell phones, TVs, etc. If this works, it won't take long before it is available to everyone.
That quantum encryption system that we weren't using, weren't evaluating, and weren't even capable of implementing, has been saved!
The development of quantum crypto is happening and there's a lot of work on it. Moreover, the claim that we aren't capable of implementing is false. There are even commercial implementations. See http://en.wikipedia.org/wiki/Quantum_key_distribution#Commercial for a list. Computer networks using secure quantum crypto have also been made (scroll just a bit further in that Wikipedia article).
Is quantum entanglement the only physical resource that allows for such strong encryption?
The original quantum crypto protocol BB84 http://en.wikipedia.org/wiki/BB84 does not require entanglement, and is secure if one is still sending single photons at a time.
Very little. You don't generally get paid for papers. The money from the journals in almost all fields goes to the publishers, not anyone in the field.
Yes, it sometimes takes a while to get access unfortunately. There are two main causes: 1) Lack of time to inform the team. This most frequently occurs when the person has taken a sudden turn for the worse in their medical condition. 2) Uncooperative doctors and nurses. Some hospital personnel don't cooperate with the cryo prep teams, which can lead to critical delays. So this situation is by no means fool proof.