A problem L is NP-hard if any polynomial algorithm for L can be used to solve all problems in *NP* with only a polynomial slowdown. That is the definition of NP-hard. NP-complete problems are NP-hard and have extra property that they are in NP as well.
So, solving any NP-hard (and hence any NP-complete problem) in polynomial time is as good as solving *all* problems in NP in polynomial time. P is just the class of problems solvable in polynomial time.
Hence, polynomial algorithm for *any* NP-complete problem => (P=NP)
I saw three "In Soviet Russia.." comments to this story. One modded "funny", another one "insightful" and yet another "troll". They all basically say "the internet reads/browses/controls you". Now, if some moderators are smoking stuff, I would like some it too.
If you RTFA, you would see that he reread his paper and found many errors that no one else had found yet. He retracted the paper because of the errors. Of course he might have other motives but that is anybody's guess
Turing machines are abstractions of what it means to compute.
Consider the problem of sorting n numbers. In terms of computing, one is interested in computing a sequence of integers formed by rearranging given numbers that satisfy some (here monotonicity) property. Now, if one is given 5 numbers to sort one could do one thing to sort them and given 10 numbers to sort, something else. Existence of a Turing machine for sorting means that one could follow only one set of rules and sort any number of input numbers.
The general Turing machine has a tape to write on, on which one (the head) can move left and right and depending on the state of tape decide to change symbols and finally halt at some specific state. The number of states q and number of symbols s define a (q,s) Turing machine.
This notion obviously creates many different Turing machines for different problems. The natural question then is whether there is a Turing machine that simulates all other Turing machines by just reading the encoding of the given Turing machine (M) and its input (n) and simulating the steps on M on input n. If such a machine exists (and they do more or less), then if one were to create computing devices one would just need to implement the one Universal Turing Machine (UMT) and leave it to the programmer to code any other machine on top of it. That is how most computers work. They are essentially UMTs (of course you have to pretend that they have infinite memory in terms of possibility of adding more.)
So if you wanted a really tiny UMT, how tiny can it get? The result mentioned in the story says that you just need 2 states of the machine and 5 symbols on the tape, hence (2,5) UMT. The hope here is maybe someday we will actually implement these very small UMTs on nano-scale (maybe to program the http://en.wikipedia.org/wiki/Self-replicating_spacecraft van-neumann probe?)
If this machine had turned out to be a non-UTM then you would have needed a bigger computer to simulate all other computers. With this discovery we now know that everything that one can (reasonably) hope to compute algorithmically can be done by a pretty dumb rule. The controller of a real computer can be as small as requiring just 1 bit to store its state and just 3 bits to encode its symbols. Even though (maybe ) not for any practical use, the result sounds extremely interesting (and perhaps humbling). On the practical side, I can imagine this machine requiring very large tape for running relatively simple algorithms.
I have used Vista a couple of times to "check it out". I am pretty sure you can make it remember that this particular program be allowed to run in the future without asking for confirmation, the first time you have to confirm.
I see both subversion and tomcat in Ubuntu repositories. Most of the softwares are available in.deb format anyway. Can you tell me which specific program was giving you troubles?
If you think that "a particular organization of logic gates" should be patentable then pretty much all the constructive proofs of mathematics might as well be patentable.
Also, if you think about it, algorithms are nothing but properly encoded proofs of theorems (and vice-versa) and I am sure you would agree that patenting mathematics is bound to do more evil than good to the society.
I have seen people using comma or parentheses excessively, including myself, but you beat them all with your generous (and improper) usage of full stop.
But how much quantity does it take to make it reasonable? That does not even need to have a reasonable answer. How many hairs distinguish a bald guy from a non-bald guy? 1 hair is clearly bad. A hundred thousand is clearly not bald. Asking for a sharp boundary is quite unreasonable and so is claiming that there is no boundary at all.
All one could do is tell that the amount is clearly reasonable in some instances and clearly not reasonable in some other. IMHO the amount of GNU components in any GNU/Linux distribution out there is high enough to make the naming reasonable. Your mileage may ofcourse vary.
Slashdot Mirror
A problem L is NP-hard if any polynomial algorithm for L can be used to solve all problems in *NP* with only a polynomial slowdown. That is the definition of NP-hard. NP-complete problems are NP-hard and have extra property that they are in NP as well.
So, solving any NP-hard (and hence any NP-complete problem) in polynomial time is as good as solving *all* problems in NP in polynomial time. P is just the class of problems solvable in polynomial time.
Hence, polynomial algorithm for *any* NP-complete problem => (P=NP)
"cornerstone used to create a proof of P=NP".. errm, what?
The very fact that a polynomial algorithm for some NP-complete problem exists *will prove* P=NP. No extra nuts and bolts would be needed.
I saw three "In Soviet Russia.." comments to this story. One modded "funny", another one "insightful" and yet another "troll". They all basically say "the internet reads/browses/controls you". Now, if some moderators are smoking stuff, I would like some it too.
If you RTFA, you would see that he reread his paper and found many errors that no one else had found yet. He retracted the paper because of the errors. Of course he might have other motives but that is anybody's guess
In the above post (2,5) should be (2,3)
Turing machines are abstractions of what it means to compute.
Consider the problem of sorting n numbers. In terms of computing, one is interested in computing a sequence of integers formed by rearranging given numbers that satisfy some (here monotonicity) property. Now, if one is given 5 numbers to sort one could do one thing to sort them and given 10 numbers to sort, something else. Existence of a Turing machine for sorting means that one could follow only one set of rules and sort any number of input numbers.
The general Turing machine has a tape to write on, on which one (the head) can move left and right and depending on the state of tape decide to change symbols and finally halt at some specific state. The number of states q and number of symbols s define a (q,s) Turing machine.
This notion obviously creates many different Turing machines for different problems. The natural question then is whether there is a Turing machine that simulates all other Turing machines by just reading the encoding of the given Turing machine (M) and its input (n) and simulating the steps on M on input n. If such a machine exists (and they do more or less), then if one were to create computing devices one would just need to implement the one Universal Turing Machine (UMT) and leave it to the programmer to code any other machine on top of it. That is how most computers work. They are essentially UMTs (of course you have to pretend that they have infinite memory in terms of possibility of adding more.)
So if you wanted a really tiny UMT, how tiny can it get? The result mentioned in the story says that you just need 2 states of the machine and 5 symbols on the tape, hence (2,5) UMT. The hope here is maybe someday we will actually implement these very small UMTs on nano-scale (maybe to program the http://en.wikipedia.org/wiki/Self-replicating_spacecraft van-neumann probe?)
If this machine had turned out to be a non-UTM then you would have needed a bigger computer to simulate all other computers. With this discovery we now know that everything that one can (reasonably) hope to compute algorithmically can be done by a pretty dumb rule. The controller of a real computer can be as small as requiring just 1 bit to store its state and just 3 bits to encode its symbols. Even though (maybe ) not for any practical use, the result sounds extremely interesting (and perhaps humbling). On the practical side, I can imagine this machine requiring very large tape for running relatively simple algorithms.
I have used Vista a couple of times to "check it out". I am pretty sure you can make it remember that this particular program be allowed to run in the future without asking for confirmation, the first time you have to confirm.
I see both subversion and tomcat in Ubuntu repositories. Most of the softwares are available in .deb format anyway. Can you tell me which specific program was giving you troubles?
Depends on your perspective.
If you think that "a particular organization of logic gates" should be patentable then pretty much all the constructive proofs of mathematics might as well be patentable.
Also, if you think about it, algorithms are nothing but properly encoded proofs of theorems (and vice-versa) and I am sure you would agree that patenting mathematics is bound to do more evil than good to the society.
An Engineer is one who, when asked what is 3 times 4, takes out a slide rule, fiddles around for a while and replies "Approximately 12"
I have seen people using comma or parentheses excessively, including myself, but you beat them all with your generous (and improper) usage of full stop.
All one could do is tell that the amount is clearly reasonable in some instances and clearly not reasonable in some other. IMHO the amount of GNU components in any GNU/Linux distribution out there is high enough to make the naming reasonable. Your mileage may ofcourse vary.
There IS a word in Hindi for privacy - Gopaniyata
It also translates to secrecy though.