Even if I had fifty pears reviewing my code bugs are going to slip in because they don't fully understand what I am writing.
Well, that's because pears can't code worth a darn. You should be using oranges. I know some people will hold out for bananas, but I've never had good luck with them; they're too fickle. Oranges will get the job done every time.
You can analyze the probability of an algorithm's success without knowing the answer it'll produce. This is a well-known technique even outside the realm of quantum computing. Here's a simple example: I have a number between 1 and 100; try to guess it. Of course, there's the standard O(log n) technique (which is probably the best one in this case!), but you could also just guess randomly until you find the number. In this case, you have a certain chance of finding the answer within, say, 200 steps (can't remember offhand but it should be fairly high). If you decide to arbitrarily terminate the search at this point, you can calculate the probability of the algorithm succeeding. Standard practice is to just prove that you have at least a 50% chance of success (at which point you can achieve an arbitrarily high chance of success by iterating the algorithm enough times) -- of course, 50% is an arbitrary number; any number above 0% would work from a theoretical point of view.
An example of a real algorithm that works this way is primality testing. There's an easy test that returns "false" for all primes, and returns "false" or "true" with equal probability for composites. (search for "Solovay-Strassen") Since the probability of a false negative is 50% (when you have a composite) if you pick enough samples and they all fail, you can say that there's a "high probability" that the number is prime. (for instance, 256 tests will get you odds of 1/(2^256) that the answer is wrong)
I don't pretend to understand quantum computing, but I do know that the basic processes are probabilistic, so it's not surprising that you end up with a probability of finding the right answer. Also bear in mind that there are only two (last time I checked, anyway) known algorithms for quantum computers, or at least only two that are significantly faster than the "standard" version, so it's not like QC is claimed to solve every open problem in computer science (despite what some guy above was saying).
Hm, I would never place Anthony at the level of Pratchett, but there is one similarity that I can think of -- both of them crank out huge volumes of books that rely way too heavily on self-reference and in-jokes. I read all of the early Discworld books with great enthusiasm, but somehow I just don't enjoy PTerry's latest offerings the same way...they've gotten too formulaic and predictable for my taste. My favorite book in the series remains "Small Gods", maybe partly because it doesn't substitute references to the rest of the series for actual new content.
Unfortunately, acting ability doesn't pass quite so easily. The trailer actually didn't look that bad, considering -- until the actors opened their mouths. *cringe* If that's the best line they could find in the movie...well, I'm not sure I want to see the worst.
If you can hack around this, more power to you, but MS is under no legal or ethical obligation to support your efforts.
Of course, there's a difference between not supporting your efforts, "accidentally" breaking your efforts, and actively trying to stop your efforts from working. This appears to be a pretty clear case of the third item in that list.
"I don't belong to any organized political party: I am a Democrat." -- forget who said this, but too true (and once you start talking about liberals it gets even worse)
For instance, if QC were to become real, one can always brute-force an algorithm.
Only if you can find a fast quantum algorithm for every hard problem. I haven't studied quantum computing much, but my understanding is that it's at least an open question whether you can even get fast solutions to all of NP, leaning towards the negative. eg: for what it's worth, Wikipedia says that "BQP is suspected to be disjoint from NP-complete and a strict superset of P, but that is not known... There is a common misconception that quantum computers can solve NP-complete problems in polynomial time. That is not known to be true, and is generally suspected to be false."
My complexity theory may be rusty, but I could swear that the factorization problem is only conjectured to be NP-complete.
Ok, I checked Wikipedia: if the entry is right, factorization is known (of course) to be in NP and coNP. It is not, however, known to be NP-complete or coNP-complete, and in fact it's conjectured to be neither (if it was NP-complete or coNP-complete, we would get NP=coNP, which is thought to be false). As you pointed out, it's also conjectured to be outside P, mainly because no-one can seem to find a polynomial-time algorithm for it.
Let me ask you, when someone comes up to you and says "I work at Microsoft" , what is your first reaction?
Well, unless I happen to be visiting Redmond/Bellevue (or near a campus "career fair"), I hardly ever run into Microsoft employees. So most of the time my reaction would be a puzzled look and the query "really?"
On the other hand, even if I do expect to possibly run into a Microsoft employee or two, I think that anyone who walks up to complete strangers and introduces themselves by announcing their place of employment (at least under any normal circumstance) is either a practical jokester or has some personal issues they need to look at, and so I guess I would react by giving them a puzzled look, saying "That's nice," and hoping they go bother someone else.
Nice try, but that's almost comprehensible;-). Maybe we could start with something like this...continuations, macros (although I think it could use more of them), and a pointless application of basic number theory to top it off. Wacky indentation courtesy of/.'s spamfilters.
(I thought about doing something totally ridiculous, like having the-msg be a red-black tree indexed by the Nth prime number, but then I realized that would be totally ridiculous)
I think programmers with Unix experience won't need this, but I read a similar book when I started writing Linux software, and it was incredibly helpful. There are a lot of things about the Linux environment that experienced programmers take for granted, but that you have to learn somewhere. Having it all in one place and presented in a logical fashion is a great time-saver. You could probably learn how UNIX processes work, for instance, by reading the manpages for fork(2), exec(2), and so on, but I doubt that's how most people do it.
Not to mention that some shortcuts are all-too-easy to hit. After one too many accidental exits, I rebound the "quit" command to "C-c f10". (for unbelievers: the default is C-x C-c; for comparison, "save" is C-x C-s and "load" is C-x C-f)
The act of creating a whole world from art, sounds, abstract personalities, key events, etc, and all the interactions involved is NOT yet an act people will just do on their own, even for a large group working together....
Otherwise, we'll get a lot more abstract puzzle games, but the real power of developer imagination may be lost to complexity.
Honestly, I prefer simple puzzle and arcade games. The other type takes far too much time and work for a *game*. If I want a story I'll go read a book.
I know I'm not typical of the market, I just had to wedge in a curmudgeonly rant.:-)
Slashdot Mirror
Penguins are evil!
All too true.
Daniel
Apparently the IRS isn't allowed to do this because it would compete with private tax software providers. Go figure.
Daniel
Even if I had fifty pears reviewing my code bugs are going to slip in because they don't fully understand what I am writing.
Well, that's because pears can't code worth a darn. You should be using oranges. I know some people will hold out for bananas, but I've never had good luck with them; they're too fickle. Oranges will get the job done every time.
Daniel
I guess there isn't a moderation for "self-referentially ironic".
Daniel
If you use TeX, infinity is 10000, so they only have two orders of magnitude to go!
Daniel
Needless to say, to say people are sceptical of Kieu's ideas is an understatement...
;-)
Given that you have to start by throwing out the Church-Turing thesis, I'd think that's hardly surprising.
The halting problem for arbitrary Turing machines, with all that that would imply.
The Riemann hypothesis.
Goldbach's conjecture
So.....is he planning to do this before or after he proves that integer mathematics is logically consistent?
Daniel
You can analyze the probability of an algorithm's success without knowing the answer it'll produce. This is a well-known technique even outside the realm of quantum computing. Here's a simple example: I have a number between 1 and 100; try to guess it. Of course, there's the standard O(log n) technique (which is probably the best one in this case!), but you could also just guess randomly until you find the number. In this case, you have a certain chance of finding the answer within, say, 200 steps (can't remember offhand but it should be fairly high). If you decide to arbitrarily terminate the search at this point, you can calculate the probability of the algorithm succeeding. Standard practice is to just prove that you have at least a 50% chance of success (at which point you can achieve an arbitrarily high chance of success by iterating the algorithm enough times) -- of course, 50% is an arbitrary number; any number above 0% would work from a theoretical point of view.
An example of a real algorithm that works this way is primality testing. There's an easy test that returns "false" for all primes, and returns "false" or "true" with equal probability for composites. (search for "Solovay-Strassen") Since the probability of a false negative is 50% (when you have a composite) if you pick enough samples and they all fail, you can say that there's a "high probability" that the number is prime. (for instance, 256 tests will get you odds of 1/(2^256) that the answer is wrong)
I don't pretend to understand quantum computing, but I do know that the basic processes are probabilistic, so it's not surprising that you end up with a probability of finding the right answer. Also bear in mind that there are only two (last time I checked, anyway) known algorithms for quantum computers, or at least only two that are significantly faster than the "standard" version, so it's not like QC is claimed to solve every open problem in computer science (despite what some guy above was saying).
Daniel
Hm, I would never place Anthony at the level of Pratchett, but there is one similarity that I can think of -- both of them crank out huge volumes of books that rely way too heavily on self-reference and in-jokes. I read all of the early Discworld books with great enthusiasm, but somehow I just don't enjoy PTerry's latest offerings the same way...they've gotten too formulaic and predictable for my taste. My favorite book in the series remains "Small Gods", maybe partly because it doesn't substitute references to the rest of the series for actual new content.
Daniel
Unfortunately, acting ability doesn't pass quite so easily. The trailer actually didn't look that bad, considering -- until the actors opened their mouths. *cringe* If that's the best line they could find in the movie...well, I'm not sure I want to see the worst.
Daniel
From reading his post, I think it's quite clear: by "left" he means "evil" and by "right" he means "good". :-)
Daniel
If you can hack around this, more power to you, but MS is under no legal or ethical obligation to support your efforts.
Of course, there's a difference between not supporting your efforts, "accidentally" breaking your efforts, and actively trying to stop your efforts from working. This appears to be a pretty clear case of the third item in that list.
Daniel
But not totally awake, evidently. As I quoted, the article says BQP is disjoint from NP-complete, not NP. There's an important distinction there...
Danieil
Yeah, that's a lot more obvious now that I'm awake :P
Daniel
"I don't belong to any organized political party: I am a Democrat." -- forget who said this, but too true (and once you start talking about liberals it gets even worse)
For instance, if QC were to become real, one can always brute-force an algorithm.
Only if you can find a fast quantum algorithm for every hard problem. I haven't studied quantum computing much, but my understanding is that it's at least an open question whether you can even get fast solutions to all of NP, leaning towards the negative. eg: for what it's worth, Wikipedia says that "BQP is suspected to be disjoint from NP-complete and a strict superset of P, but that is not known... There is a common misconception that quantum computers can solve NP-complete problems in polynomial time. That is not known to be true, and is generally suspected to be false."
Daniel
My complexity theory may be rusty, but I could swear that the factorization problem is only conjectured to be NP-complete.
Ok, I checked Wikipedia: if the entry is right, factorization is known (of course) to be in NP and coNP. It is not, however, known to be NP-complete or coNP-complete, and in fact it's conjectured to be neither (if it was NP-complete or coNP-complete, we would get NP=coNP, which is thought to be false). As you pointed out, it's also conjectured to be outside P, mainly because no-one can seem to find a polynomial-time algorithm for it.
Daniel
Let me ask you, when someone comes up to you and says "I work at Microsoft" , what is your first reaction?
Well, unless I happen to be visiting Redmond/Bellevue (or near a campus "career fair"), I hardly ever run into Microsoft employees. So most of the time my reaction would be a puzzled look and the query "really?"
On the other hand, even if I do expect to possibly run into a Microsoft employee or two, I think that anyone who walks up to complete strangers and introduces themselves by announcing their place of employment (at least under any normal circumstance) is either a practical jokester or has some personal issues they need to look at, and so I guess I would react by giving them a puzzled look, saying "That's nice," and hoping they go bother someone else.
Daniel
(I thought about doing something totally ridiculous, like having the-msg be a red-black tree indexed by the Nth prime number, but then I realized that would be totally ridiculous)
I think programmers with Unix experience won't need this, but I read a similar book when I started writing Linux software, and it was incredibly helpful. There are a lot of things about the Linux environment that experienced programmers take for granted, but that you have to learn somewhere. Having it all in one place and presented in a logical fashion is a great time-saver. You could probably learn how UNIX processes work, for instance, by reading the manpages for fork(2), exec(2), and so on, but I doubt that's how most people do it.
Daniel
If the user is downloading and running malicious executables, stealth Firefox extensions are the least of their worries.
Daniel
Of course, one reason the Hurd has encountered so much trouble is that it deviates wildly from the traditional Unix kernel design.
Daniel
That doesn't help if your graphics driver has crashed the kernel.
Daniel
Not to mention that some shortcuts are all-too-easy to hit. After one too many accidental exits, I rebound the "quit" command to "C-c f10". (for unbelievers: the default is C-x C-c; for comparison, "save" is C-x C-s and "load" is C-x C-f)
Daniel
The act of creating a whole world from art, sounds, abstract personalities, key events, etc, and all the interactions involved is NOT yet an act people will just do on their own, even for a large group working together. ...
:-)
Otherwise, we'll get a lot more abstract puzzle games, but the real power of developer imagination may be lost to complexity.
Honestly, I prefer simple puzzle and arcade games. The other type takes far too much time and work for a *game*. If I want a story I'll go read a book.
I know I'm not typical of the market, I just had to wedge in a curmudgeonly rant.
Daniel