Accions del document
Collaborations
Dr. Carme Alvarez collaboration with us with the"P versus NP" problem.
P versus NP: the beauty of a fundamental question
On May 6th at the Cosmocaixa Auditorium, Dr Avi Wigderson of the Princeton Advanced Studies Institute, gave a lecture entitled “The P vesus NP problem and the limts of knowledge”.
I had great curiosity to listen how a world- renowned researcher as Dr. Wigderson was going to explain an issue as transcendent as “P versus NP” to a general audience, probably composed by people with little or no knowledge about Computing Theory.
To me it was a real pleasure to see how someone could describe in such an intuitive and easy to understand way the central question of Theoretical Computer Science, a question that has been lingering on from more than four decades.
Dr. Widgerson line of discourse focused on illustrating the strong relationship that exists between computation, nature, mathematics, algorithms, beauty and efficiency. His presentation was based on three fundamental ideas: computation is everywhere, algorithms are the language of computation and creativity cannot be automated (which, according to Dr. Widgerson amounts to an intuitive translation of the P is not NP conjecture).
A long standing question was put forth elegantly and with simplicity as only someone with the deepest knowledge of the abilities and limits of computation could. Dr. Widgerson conveyed with enthusiasm the beauty of many concepts of Computational Complexity Theory, concepts that have been introduced in the path towards solving the P versus NP conjecture.
I will try to sum up Dr. Widgerson´s lecture in the following as well as some of the responses that he gave to questions asked by the audience. Although the lecture as addressed to a general public, the questions in the Q & A session showed clearly that many people in the audience had quite a deep knowledge of the problems.
I had great curiosity to listen how a world- renowned researcher as Dr. Wigderson was going to explain an issue as transcendent as “P versus NP” to a general audience, probably composed by people with little or no knowledge about Computing Theory.
To me it was a real pleasure to see how someone could describe in such an intuitive and easy to understand way the central question of Theoretical Computer Science, a question that has been lingering on from more than four decades.
Dr. Widgerson line of discourse focused on illustrating the strong relationship that exists between computation, nature, mathematics, algorithms, beauty and efficiency. His presentation was based on three fundamental ideas: computation is everywhere, algorithms are the language of computation and creativity cannot be automated (which, according to Dr. Widgerson amounts to an intuitive translation of the P is not NP conjecture).
A long standing question was put forth elegantly and with simplicity as only someone with the deepest knowledge of the abilities and limits of computation could. Dr. Widgerson conveyed with enthusiasm the beauty of many concepts of Computational Complexity Theory, concepts that have been introduced in the path towards solving the P versus NP conjecture.
I will try to sum up Dr. Widgerson´s lecture in the following as well as some of the responses that he gave to questions asked by the audience. Although the lecture as addressed to a general public, the questions in the Q & A session showed clearly that many people in the audience had quite a deep knowledge of the problems.
The lecture: a report
Dr. Widgerson started by saying that computation is present everywhere. He said that he could enumerate a long list of natural phenomena and intellectual challenges that have computation as a basic component. From the many examples that he gave I can recall the one of baldness being the result of the natural process of hair falling; the first months of growth of a fetus; the procedure used to obtain the sum numbers with many decimal figures; climate changes, etc. do He asked to himself and to the public: “What all these processes have in common?” Well, in all these processes there is a subject, that we call input, to which some very well defined actions are applied which, in turn, modify the input and resulting in a final product or output. Nature obtains the resulting product of these processes. Now, are we able to define always a procedure to obtain a desired outcome? That is, does computation have any limit? For example, is there any mechanical and effective way to solve equations? Do we have a mechanical procedure to prove theorems? The first thing that we have to do is to define a precise way to describe these procedures or computations.
Algorithms come in
Algorithms constitute the language that describes computation. For example, we are taught in primary school a couple of algorithms to add up and multiply two natural numbers. These algorithms describe step by step how to calculate an addition or a multiplication. Each step is a basic operation on decimal digitals and it is independent of the how many figures the number has.
An algorithm is a finite set of instructions that can be applied to a potentially infinite number of inputs. Algorithms describe calculation procedures.
The Turing Machine was proposed as a formal model of an algorithm. The Turing-Church thesis states that any algorithm can be formally describe by a Turing Machine. This thesis has been around unchallenged for approximately seventy years. With it one can state rigorously which are the limitations of computation. Problems as natural as theorem proving are, in fact, incomputable. That is theorem proving cannot be done automatically.
Back to basic examples
Going back to the addition and multiplication example, Dr Widgerson use them to remark how the number of basic operations that each of them performs depends directly on the number of digits of their two input numbers. Addition performs a constant number of operations per digit while multiplication performs as many basic operations as the longest number in the multiplication times a constant.
There are many other algorithms that behave in a similar way in the sense that they perform a reasonable amount of basic operations in order to reach a solution. They are, for example, the ones used to solve problems like calculating the shortest path between two points; pattern recognition problems o calculating the Fast Fourier Transform. All of them allow you to calculate the desired solutions. They are smart, and elegant algorithms that solve problems that are not trivial at all. All these type of problems are part of the P class, the class of problems that allow for an efficient computation of a solution.
Comparing this problems, Dr. Widgerson, remarked that is easy to verity that 193707721 x 761838257287=147573952589676412927. It is just a matter of performing the multiplication of two long numbers, that’s all. However, if the input number is something like 147573952589676412927 and the problem is to calculate its prime factors, then the procedure that consists in trying all possible factors is anything but efficient. For an input number of n digits, one could need to perform 2^(n/2) tests. In practice we would be unable to see the end of the computation.
These problems are part of the NP Class, the class of problems for which, if a possible solution is given, it is easy to check that it is correct.
After defining the P and NP class in this intuitive way, Dr. Widgerson, went straight to pose the P versus NP question. It seems very clear that any problem that belongs to the P class also belongs to the NP class. If you can compute the solution, than it can be verified. The conjecture is that calculating solutions is much more difficult than verifying the, in other terms, P ≠ NP.
If P = NP than these solutions could be computed in an efficient manner. Besides that, for example, and using as an example the Sudoku example, if we were able to design and algorithm that computed fast, than P=NP. That is any problem in the NP class could be translated to the problem of … solving Sudoku. That same would happen with the problem of proving theorems with lengthy proofs. This intuitive idea that a problem captures all the complexity of the NP class is equivalent to the formal concept of NP-completeness.
In order to complete the argument about the importance of the P=NP conjecture, Dr. Widgerson introduced the following consideration. If it existed an efficient algorithm to solve Sudokus, than prime factorizing would be easy as well. This, in contrast, would have a very negative impact on the security systems for electronic transactions, which would be rendered clearly vulnerable. The “bread and butter” of any researcher in the Theory of Computing is designing efficient algorithms to solve non-trivial problems or, alternatively, to show the impossibility of their existence.
For factorization no one has been able to show any other of these possibilities as yet.
Algorithms as beautiful resources
Efficient algorithms are precious stones. Many problems that previously had been thought to have no solution, have been eventually been solved. Algorithms that compute solutions for all cases are elegant, smart and independent of technology.
P versus NP, what is easier? To verify a solution or to find one? For Widgerson P=NP is a utopia. Were it true, all science could be automated. On the other hand, it may very well be that some day we could see that P≠NP.
I recall two questions in particular. Specially because of the clarity of Dr Widgerson answers and because, again, they exemplified the efforts that are currently being carried on in order to understand the limits of computation.
The first one had to do with the relationship between computation and nature. It went like this “Is it true that nature can solve NP-complete problems?” Dr. Widgerson that although it was true that living creatures are continuously solving problems that we have classified as NP-complete, one has to say that each individual has very particular data that characterize him or her, that define him or her. Then the computed solutions in each case do not have as input data all the possible inputs but each individual calculates a solution for a limited data set. Each individual “solves” his or her “particular” problem and in a very efficient way.
The second question that I think it is worth recalling is this: What impact has had the characterization of NP in terms of PCPs? In trying to answer this question Dr. Widgerson explained first in a very simple way –something that seems almost impossible- what is the meaning of the question “Each NP set has a PCP system”. The name PCP comes from “Probabilistic Checkable Proof” system. Let us imagine for a moment that we have at hand the proof of a theorem, a proof that is 200-page long and we want to check that it is correct. Our first step is to “normalize” it in a very particular way and it becomes a 2000-page proof, a little longer but not very much longer than the original proof. A PCP system is a probabilistic verifier that receives this kind of inputs but… it can only read a small part of this proof (that will be randomly selected). An analogy to this situation could be a reviewer that tries to decide on the correctness of a very long proof by just selecting randomly a few lines of the proof. This method seems very inadequate, how can one that there is some mistake in the proof without actually going through the whole proof? This intuition is only valid, however, when we consider the “natural” way in which proofs are described but it fails when we take into account certain “robust” proof formats (and when it is natural to allow for a little probability of error). These robust proof systems are what we call PCPs. A PCP for a given set S is an efficient probabilistic verifier that can only access a few bits of the assumed proof in robust format. So to speak, the verifier casts a coin and, depending on the result, it accesses a constant number of bits of the assumed proof.
Each element of the S set has to be accepted with probability 1 (given a real proof, codified correctly). It rejects any element that doesn’t belong to S with a probability at least of ½ (irrespectively of the assumed proof in robust format). A famous theorem states that each NP has a PCP system, and, on top of that, there exists an efficient algorithm that translate any possible proof or witness of membership to an NP set into a proof in “robust” format.
According to Dr. Widgerson, the proof of the PCP theorem suggests a new way to write “robust” proofs in which any error (virus) propagates everywhere. If the probability of spotting an error in those little bits is low, then the theorem is correct. To finish up Dr. Widgerson remarked one of the implications of this characterization: “Under the hypothesis that P is different from NP, randomization doesn’t help”.
Press Contact:
alvarez@lsi.upc.edu
ilapuente@lsi.upc.edu
(Back to the Newsletter)
An algorithm is a finite set of instructions that can be applied to a potentially infinite number of inputs. Algorithms describe calculation procedures.
The Turing Machine was proposed as a formal model of an algorithm. The Turing-Church thesis states that any algorithm can be formally describe by a Turing Machine. This thesis has been around unchallenged for approximately seventy years. With it one can state rigorously which are the limitations of computation. Problems as natural as theorem proving are, in fact, incomputable. That is theorem proving cannot be done automatically.
Back to basic examples
There are many other algorithms that behave in a similar way in the sense that they perform a reasonable amount of basic operations in order to reach a solution. They are, for example, the ones used to solve problems like calculating the shortest path between two points; pattern recognition problems o calculating the Fast Fourier Transform. All of them allow you to calculate the desired solutions. They are smart, and elegant algorithms that solve problems that are not trivial at all. All these type of problems are part of the P class, the class of problems that allow for an efficient computation of a solution.
Comparing this problems, Dr. Widgerson, remarked that is easy to verity that 193707721 x 761838257287=147573952589676412927. It is just a matter of performing the multiplication of two long numbers, that’s all. However, if the input number is something like 147573952589676412927 and the problem is to calculate its prime factors, then the procedure that consists in trying all possible factors is anything but efficient. For an input number of n digits, one could need to perform 2^(n/2) tests. In practice we would be unable to see the end of the computation.
NP comes in
Do all practical problems show these features? At that point Dr. Widgerson directly challenged the audience by asking them if the play Sudoku. If they do is it just because they amuse themselves with them or are they aiming to make a contribution to science? As in the previous case, if we played Sudoku of any dimension n x n it would be very different to try to text if a solution is correct than to try to find it. By applying “brute force”, as in the case of prime factorization, the algorithm wouldn’t be practically effective. Well, the same happens when trying to prove theorems that we know do have a proof that is known to be not very long. If we are given the proof, to check that it is correct is easy. These problems are part of the NP Class, the class of problems for which, if a possible solution is given, it is easy to check that it is correct.
After defining the P and NP class in this intuitive way, Dr. Widgerson, went straight to pose the P versus NP question. It seems very clear that any problem that belongs to the P class also belongs to the NP class. If you can compute the solution, than it can be verified. The conjecture is that calculating solutions is much more difficult than verifying the, in other terms, P ≠ NP.
If P = NP than these solutions could be computed in an efficient manner. Besides that, for example, and using as an example the Sudoku example, if we were able to design and algorithm that computed fast, than P=NP. That is any problem in the NP class could be translated to the problem of … solving Sudoku. That same would happen with the problem of proving theorems with lengthy proofs. This intuitive idea that a problem captures all the complexity of the NP class is equivalent to the formal concept of NP-completeness.
In order to complete the argument about the importance of the P=NP conjecture, Dr. Widgerson introduced the following consideration. If it existed an efficient algorithm to solve Sudokus, than prime factorizing would be easy as well. This, in contrast, would have a very negative impact on the security systems for electronic transactions, which would be rendered clearly vulnerable. The “bread and butter” of any researcher in the Theory of Computing is designing efficient algorithms to solve non-trivial problems or, alternatively, to show the impossibility of their existence.
For factorization no one has been able to show any other of these possibilities as yet.
Algorithms as beautiful resources
P versus NP, what is easier? To verify a solution or to find one? For Widgerson P=NP is a utopia. Were it true, all science could be automated. On the other hand, it may very well be that some day we could see that P≠NP.
Q & A
After this grand finale, the questions from the audience started. Dr. Widgerson, in my view, answered every and each one of them in a very intuitive and convincing manner. All questions were focused on the meaning of the P versus NP conjecture for different settings. I recall two questions in particular. Specially because of the clarity of Dr Widgerson answers and because, again, they exemplified the efforts that are currently being carried on in order to understand the limits of computation.
The first one had to do with the relationship between computation and nature. It went like this “Is it true that nature can solve NP-complete problems?” Dr. Widgerson that although it was true that living creatures are continuously solving problems that we have classified as NP-complete, one has to say that each individual has very particular data that characterize him or her, that define him or her. Then the computed solutions in each case do not have as input data all the possible inputs but each individual calculates a solution for a limited data set. Each individual “solves” his or her “particular” problem and in a very efficient way.
The second question that I think it is worth recalling is this: What impact has had the characterization of NP in terms of PCPs? In trying to answer this question Dr. Widgerson explained first in a very simple way –something that seems almost impossible- what is the meaning of the question “Each NP set has a PCP system”. The name PCP comes from “Probabilistic Checkable Proof” system. Let us imagine for a moment that we have at hand the proof of a theorem, a proof that is 200-page long and we want to check that it is correct. Our first step is to “normalize” it in a very particular way and it becomes a 2000-page proof, a little longer but not very much longer than the original proof. A PCP system is a probabilistic verifier that receives this kind of inputs but… it can only read a small part of this proof (that will be randomly selected). An analogy to this situation could be a reviewer that tries to decide on the correctness of a very long proof by just selecting randomly a few lines of the proof. This method seems very inadequate, how can one that there is some mistake in the proof without actually going through the whole proof? This intuition is only valid, however, when we consider the “natural” way in which proofs are described but it fails when we take into account certain “robust” proof formats (and when it is natural to allow for a little probability of error). These robust proof systems are what we call PCPs. A PCP for a given set S is an efficient probabilistic verifier that can only access a few bits of the assumed proof in robust format. So to speak, the verifier casts a coin and, depending on the result, it accesses a constant number of bits of the assumed proof.
Each element of the S set has to be accepted with probability 1 (given a real proof, codified correctly). It rejects any element that doesn’t belong to S with a probability at least of ½ (irrespectively of the assumed proof in robust format). A famous theorem states that each NP has a PCP system, and, on top of that, there exists an efficient algorithm that translate any possible proof or witness of membership to an NP set into a proof in “robust” format.
According to Dr. Widgerson, the proof of the PCP theorem suggests a new way to write “robust” proofs in which any error (virus) propagates everywhere. If the probability of spotting an error in those little bits is low, then the theorem is correct. To finish up Dr. Widgerson remarked one of the implications of this characterization: “Under the hypothesis that P is different from NP, randomization doesn’t help”.
Press Contact:
ilapuente@lsi.upc.edu
(Back to the Newsletter)