The biggest computer of dreams

Will a messiah computer appear in our world, and what problems will it help to solve?

  Boston. On page 112 of Douglas Adams' book "The Hitchhiker's Guide to the Galaxy" (translated by Mati Wengrik and Dana Lederer, "Ketar" publishing house) there is a strange debate between a mouse and a giant computer concerning a wonderful future machine: the skeptical Fok is a member of a mouse culture that sought to find the answer "to the secret of life, The universe and everything else" and for this purpose established the computer "Deep Reflection", which is the size of a small city. On the day the two talk, a "deep reflection" begins to imply to Fook and his companions that the task is beyond his capacity, and that the computer that can provide them with this information will have to be the size of a planet - "a computer of infinite complexity" that will take millions of years to build.

"Fuck began to lose his patience. He pushed his notebook in front of him and muttered, 'The whole business is becoming too messianic, for my taste.'

"'You don't know anything about the future,' declared 'Deep Reflection,' 'but I can navigate the endless delta currents of future probability among circular congestion and prove the commitment of the appearance of a computer, although I am not worthy to even calculate the performance parameters His, it will be my job, in the end, to plan it.''

Outside the pages of the "Hitchhiker's Guide" humanity is already desperate to try and find answers to existential questions on flashing monitors (something that is not said in those searching for meaning on the websites of religious classes and similar chats). Not only that, but it even casts doubt on the computer's ability to solve seemingly simple mathematical problems. The discussion of this aspect of the flexibility of computers is one of the main puzzles in mathematics today. This issue is becoming more complex as humanity's demands from the machines it has created multiply and as the concept of "computer" expands and takes on forms that until now seemed purely fictional.

Contemporary computer science recognizes several levels of complexity in mathematical problems. There are problems that have been proven beyond any doubt that computers have no ability to solve, as well as problems that can be solved with the help of existing computers, in a reasonable amount of time - or "polynomial" (P). Different from these and these are NP problems - problems for which, given the solution, it will be possible to verify the correctness of the solution in a reasonable time. However, for now, any attempt to solve them from scratch - by reviewing all the possible solutions that exist for them and choosing the right one - will require an exponential (exponential) time. Such a period of time is by no means reasonable: it is billions upon billions of years.

At the head of these are NPC problems - non-deterministically polynomial complete) which are complex NP problems. If the algorithm is found that will allow the solution of one of these in polynomial time, the obstacle will be removed and it will be possible to solve all the NP problems in such an acceptable time. The discussion of these problems also has quite a few practical consequences: from simplifying the encryption of codes and their cracking to contributing to attempts to save fabric in the production of upholstery for airplane seats.

A conversation very similar to the one conducted by Fock and "deep reflection" has been going on for years in the corridors of mathematics and computer science departments in universities and in the offices of companies that strive to develop future computer hardware. This, in an attempt to find a solution to one of the most disturbing mathematical problems of all time: the issue of plausibility; How will future computers be able to solve NPC problems in polynomial time - or, in the language of algebra, solve the question of whether P=NP?

Behind the pure mathematical question hides a controversy concerning faith in technology. Will the computer as we know it be able to crack this riddle, or do we have to wait for a completely different technology? Will a messiah computer appear in our world? Is such a computer necessary? Developments of these days, including the development of quantum computers that operate according to a completely different physical principle than the computers of our time, challenge Fock's skepticism.

Science fiction is used to such original ideas. Already in the XNUMXs, the author Isaac Asimov invented the "positronic brain" - a semi-organic mechanism that allowed the robots starring in his futuristic novels to think and behave almost like humans. The superiority of the positronic brain is not limited to being more sophisticated than the electrical circuits that guide the operation of traditional robots. It is a real brain, a system driven not by the principle of calculation but by the principle of thinking. The literary possibilities that such a mechanism conjured up for Asimov were limitless. It is possible that such imaginary calculating machines will also perform tasks that mathematicians now consider impossible. On the other hand, they may not be needed.

What is actually the NPC problem (a term formulated separately, in 1971, by the mathematicians Leonid Levin and Steven Cook)? The Clay Institute - an American organization operating from the city of Boston whose goal is to spread mathematical knowledge among the general public - illustrates this with the example of the dilemma faced by a boarding school supervisor, when he must choose which one hundred out of four hundred students will be assigned to live together in a certain building. The director of the boarding school provided the supervisor of the dormitory with a list of all the students who do not get along with each other and it is strictly forbidden to house them together. The list does not recommend successful mergers, and it is likely that even mergers that are not included in it carry the risk of faces painted with toothpaste and loud conversations into the night.

If he had stood by the unfortunate supervisor from an older supervisor, and offered him a list of students who maintain comfortable friendships, it would have been easy to compare this list with the boarding school director's list and find the perfect combinations. In the absence of such support, the attempt to create a random list of names that might guarantee peace and tranquility is quite unnecessary: ​​the number of possible combinations of a hundred out of the four hundred is about 10 to the power of 96 - a number with 96 zeros. The number of such lists exceeds the number of atoms in the universe known to us.

It is therefore impossible for a computer to exist that could crack the problem through an exhaustive search (that is, creating all the possible lists one after the other) in less than many billions of years, without a doubt when things are supposed to be in the computers of our generation. A Pentium 4 computer, with a 2.4 GB processor, performs 10 to the power of 9 operations per second. If each operation reviews one list of students, then the computer checks 10 to the power of 9 lists per second, or 10 to the power of 16 lists per year.

If Bill Gates' vision comes true and every person on earth owns a Pentium 4 computer equipped with "Windows" software, and if all the inhabitants of the world work on the lists and do nothing else - even then it will be possible to check about 10 to 25 lists per year. That is, it will then be necessary to wait 10 to the power of 71 years (or billions of billions of billions of billions of billions of billions of years) until the work is completed.

It is therefore understandable why the Clay Institute concludes that no future civilization will produce a supercomputer that will solve the problem by "direct power, that is, reviewing all possible combinations of a hundred students". But the people of the institute hasten to add: "Perhaps the culprit is the lack of imagination of the programmers." I mean, maybe it is still possible to solve the P=NP puzzle with the help of the existing computers, but no ordinary person has yet come up with this path. The institute is offering a million dollar prize online to anyone who solves the problem.

It's worth being precise: when the people of the Clay Institute make a sweeping statement about the computers of some future civilization, they mean a limited definition of "computer". All existing computers are based on a mechanical principle formulated by the English mathematician Alan Turing in 1936 (long before a real computer was created). When it is said that probably no future computer will be able to crack NPC questions easily, it means computers in their narrow sense - those that operate according to the existing principle. If a calculating machine is invented that works according to a completely different principle - everything, of course, will be open. But to what extent is it appropriate to believe in the possibility of the existence of computers of a different type, and how much time and resources should be devoted to their development, as long as it is not proven beyond any doubt that a solution to NPC problems is not possible even within the framework of a Turing machine?

The position of the observer, in this case, is related to the way he sees technologies that do not exist yet. The computer scientist Dor Zhorevski, for example, deals with the problem as a hobby. He even donated operating time of his personal computer to the NASA program as an aid in cracking complex polynomial problems related to decoding radio signals from space. However, he puts his trust in quantum computers, which he sees as a breaking point that may catapult research to new levels. "Those who see it differently think linearly, and that's their mistake," he says.

On the other hand, for Tal Hasner, a doctoral student at the Weizmann Institute, who lectures on this very topic to undergraduate students, the problem of P and NP is a worthy challenge for the thinking minds of our generation. To him and to many in his field, even if it is proven that a solution is impossible, it is a shame to leave the pleasure of proof to future facilities that may never be invented. While being careful not to be mistaken for misplaced optimism, Hesner emphasizes that the question of P and NP is three decades old in total, and there have already been those who have found surprising solutions to problems that are three hundred years old.

Until a proof is formulated here or there, it is better for those waiting for the first quantum computer to remember the miracles that mathematicians did without the aid of miracle machines. For others, who treat their technological dreams with limited liability and trust in an enterprising computer guy, who will save billions upon billions of electricity bills with his resourcefulness - a surprise may be expected before long. After all, until a few decades ago the Turing Principle was also seen as fictional, and like it the pocket calculator. 
 
 
Yuval Ben Ami, Haaretz.