"The most important question in all of computer science and one of the most important in mathematics" (Lance Fortnow).
"A gift to the mathematics of computer science" (Steve Smale).
The P vs. NP Problem
The theory of computational complexity
Computational complexity theory studies the complexity associated with problems that are solved computationally. To do so, it studies all the possible algorithms that can be used and also classifies problems according to the computational resources required, which are basically of two types:
The time required to solve the problem, which is proportional (or directly related) to the number of elementary steps or operations.
The space or memory required.
We speak of time and space complexity, respectively. Other measures of computational complexity that can be considered, depending on the type of problem, are: the number of processors, the amount of communication data, the number of logic gates, etc.
Computational complexity theory differs from other related theories and concepts:
Algorithmic analysis. It analyzes the amount of resources required for a particular algorithm to solve a problem.
Algorithmic complexity. It is defined as the length of the shortest program needed to generate a mathematical entity.
Computability theory. It deals with the specification of algorithms at a purely theoretical level, without considering the resources needed at the practical level.
Decidable and undecidable problems
A decidable problem is a problem whose outcome is one between two possible values: "yes" or "no", 0 or 1, true or false, and so on. For example, the problem of finding out whether or not a number is prime is decidable.
An undecidable problem is a problem whose solution would in principle also have two possible values, but which is impossible to know. The paradigmatic example is the famous problem of stopping a Turing machine: given a Turing machine M and an input w, determine whether M will eventually stop after a finite number of steps. Alan Turing proved that this problem is undecidable. Another example is Gödel's incompleteness (or undecidability) theorem: in a formal axiomatic system involving the natural numbers, there are statements that cannot be proved true or false.
Hartmanis & Stearn [1965] proved the existence of decidable problems with arbitrarily high computational complexity. They used for this purpose a diagonalization method, a method that goes back to Cantor, who used it to prove the non-numerability of the real numbers.
Types of computational problems
According to the time required to solve them (time complexity), computational problems that depend on a variable x, associated with the magnitude of the time complexity of the problem (usually, the size of the input), can be divided into two classes:
Computational problems that are solved in polynomial time, i.e., the time required to reach the solution or result is of the type c·xk, or more generally, of the type c0 + c1 ·x + c2·x2 + . .. + ck·xk, where the ci are constants. Time complexity, in general, is usually expressed as O(xr), where r is a real number (only the power of greatest exponent is specified and where the letter "O" means "of the order of"). The simplest problems are of the type O(x), i.e., of computational time proportional to x. Polynomial-time algorithms are also called "tractable" or "feasible". Examples:
The sum of two natural numbers of length n is solved in polynomial time, in particular in time proportional to 2n: O(n).
The product of two numbers of n digits requires a time proportional to n2: On2). There is an optimized method that requires only O(n1,585).
Given a natural number n, find out if it is prime. Its time complexity is O(n).
Ordering a set of n elements has time complexity O(n2), although there are also optimized methods that lower the exponent.
Searching over a sequence of ordered elements (e.g., a dictionary), is of time complexity O(ln n).
Problems that need an exponential time to be solved, that is, a time of the type k·cx, where k and c are real numbers. This function can grow extraordinarily fast as x increases. The time complexity is O(cx). Combinatorial type problems usually have this type of complexity. Exponential time algorithms are also called "intractable" or "infeasible."
Examples of this second type are:
The subset sum problem (Subset Sum Problem).
This is a decision problem that nicely illustrates the issue of exponential time complexity. One has a set C of integers. One must determine whether there exists any subset whose elements sum to zero (it could be any other number). For example, if C={13, 17, −4, −9, 25}, the answer is yes because in the subset {−4, −9, 13} its elements sum to zero.
If the set C is of length n, the number of subsets is 2n−1 (excluding the empty set). Therefore, its time complexity is O(2n). It corresponds to the "brute force" method: each of the subsets is successively generated and its elements are added. If at any time zero is obtained as a result, the answer is "Yes" and the process stops. If the end is reached, then the result is "No". With n=64 (the number of squares on the chessboard), we have a whopping 264−1 ≃ 8,4·1037. Assuming that we have a computer that executes 109 operations per second, the time required for its resolution would be on the order of 1010 trillions of years (the age of the universe is on the order of 14 billion years).
Although faster methods than brute force exist for this problem, no efficient algorithm, i.e., one that solves the problem in polynomial time, has yet been discovered.
This particular problem has the following feature. If we are given a hypothetical solution to the problem, i.e., a given set of numbers D of length m, we can verify in polynomial time whether or not it is indeed a solution. It would only be necessary to: 1) verify that its elements belong to the original set C; 2) add its elements and verify that their sum is zero. To do this, indeed, we need n·m comparisons (to see if the elements of < i>D in C), and other m−1 steps to perform the sum of the elements of D.
The traveler's problem.
A traveler has to visit n cities. Only some cities are connected to each other, but there is always a way to go from one city to another (the network is connected). One must find a cyclic path (which is called "Hamiltonian") to, starting from an initial city, visit the rest of the cities and return to the starting point, traveling a path of total length less than a given value D. You cannot pass through each city more than once. Assuming that all cities are connected, the total possible number of paths is n!, which corresponds to the number of permutations of the n cities. For 100 cities, even the fastest computer in the world would have to spend billions of years to find the answer.
The box fitting problem.
The problem is to fit a set of boxes, of known dimensions, into a given space (e.g. the trunk of a car).
The factorization problem.
It is the decomposition of a natural number n into its prime factors. It requires a time that increases exponentially with the number of digits, namely 2 raised to the cube root of n: 2n1/3. Many cryptographic methods are based precisely on the difficulty of this decomposition. The RSA algorithm uses a public key that is the product of two prime numbers.
The graph isomorphism problem.
We have two graphs with the same number of vertices and arcs. The goal is to find a bijective application between the vertex sets of both graphs that preserves the structure, i.e., if A and B are two adjacent vertices in one graph, they are also adjacent in the other. No efficient algorithm is known for the general case. If the graphs are trees, there are not very complex algorithms that solve it.
The discrete logarithm problem.
The discrete logarithm of x in base a modulo n is a number y such that x = ay (mod. n).
The logical satisfiability problem (SAT).
One has a set of logical expressions of n Boolean variables (expressed only with the logical operators conjunction, disjunction and negation). The aim is to obtain the values of these n variables that satisfy or verify these logical expressions. The space of possible solutions is 2n, so its time complexity is O(2n).
The problem of coloring the vertices of a graph with only three colors, with no two adjacent vertices of the same color.
The classes P and NP
The class of problems that can be solved in polynomial time is called the "P class".
The class of problems whose solution can be verified in polynomial time is called "class NP".
According to these two definitions, P is a subset of NP (P ⊂ NP), because if it is possible to solve a problem in polynomial time, the solution obtained can also be verified in polynomial time.
It may happen that for certain P problems, the verification time is the same as the solution time. For example, verifying the sum of two numbers requires performing the sum itself. So, paradoxically, it is sometimes easier to verify the solution of a complex problem than that of a simple problem.
Within the NP class there are easy problems (NP-easy or NP-easy), those that are solved in polynomial time, and hard problems (NP-hard or NP-hard), those that require exponential time. According to this definition, NP-hard = P.
The question P vs. NP
The problem that arises is whether P = NP or whether P ≠ NP, i.e., whether all problems whose possible solutions can be computed in polynomial time, is equal to or different from the problems that can be verified in polynomial time.
For example, the subset sum problem is of type NP, but since an efficient algorithm that solves the problem in polynomial time has not yet been found, we do not know whether it is of type P or not.
The question P =? NP is both profound and basic. It is one of the most important open questions in computer science, because of its large theoretical, practical, and even philosophical implications, and it raises several questions:
Is it possible that all NP problems possess efficient algorithms, and is it simply the case that we have not yet discovered them?
Is there a universal method to discover an efficient solution of every NP-problem. If there is such a method, since solving problems of high time complexity requires creativity, perhaps what is really being asked is whether or not creativity can be automated.
One possible way to show that P ≠ NP is to try to find a problem or a class of problems in NP−P, i.e. that is NP but not P.
In any case, whether P and NP are the same or not, trying to find the relationship between P and NP is fundamental to understanding the deep nature of computation.
The NP-complete class
The subset sum problem, the commuter problem, and the box-box problem are combinatorial problems that share an interesting property: essentially, at bottom, "they are all the same problem," in the sense that, if an efficient algorithm exists for one of them, efficient algorithms would also exist for the others. This class of problems is called "NP-complete" and they are the most difficult problems of the NP-class. No efficient algorithm has yet been found for any of these problems. If an efficient algorithm were found for an NP-complete problem, it would imply that P = NP.
The discovery of the NP-complete class constitutes a milestone of enormous importance, for several reasons:
Because it is a universal class, a standard category where difficult problems are located, both theoretically and practically.
Because it clarifies the structure of the NP-class, by establishing two opposite categories in complexity: the classes of lower complexity (P) and higher complexity (NP-complete).
Because natural phenomena and processes are mostly in the P or NP-complete classes.
Apart from the above three problems, other NP-complete problems are:
The logical satisfiability problem (SAT). It was the first problem to be detected as NP-complete. It was proved by Stephen Cook in his paper of [1971] (Cook's theorem), where the concept of NP-completeness was formalized. The SAT remains NP-complete, even with only three logical variables (3SAT problem). Most NP-complete problems are reduced, by efficient processes, to the SAT problem, thus making them equivalent in time complexity. In fact, many problems are solved more efficiently by a "SAT solver" (SAT solver) than by a specialized algorithm.
Cook's theorem states the following, "The Boolean satisfiability problem (SAT) is NP-complete." This theorem is also called the Cook-Levin theorem because it was also proved independently by Leonid Levin around the same time....
The problem of coloring the vertices of a graph with only 3 colors, with no two adjacent vertices of the same color.
The Clique (gang) problem. Given a graph and an integer k, are there k vertices with all mutually adjacent pairs.
The problem of factoring a natural number, the graph isomorphism problem, and the discrete logarithm problem are NP-problems, but they have not yet been proved to be NP-complete.
Non-NP problems
In the subset sum problem, if only one subset that sums to zero is asked for, it is very easy to verify that it is a solution. If all subsets that verify this property are asked for, verification requires repeating the process again to see if all solutions have been included. In this case, the (exponential) solution time and the verification time are the same, as is normally the case with P problems.
And the same is true for the commuter problem. If we are only required a path that runs through all the cities with a total length less than a certain given length D, it is enough to check that the path is cyclic, that all the cities are there and that the sum of distances is less than D. But if we are asked for the minimum cyclic path, the verification requires repeating the resolution process.
These types of problems, which require exponential time in both solving and verification, are not NP problems, so they are called non-NP problems.
General scheme of problem types
Resolution
Verification
Type of problem
Polynomial
Polynomial
NP-easy = P
Exponential
Polynomial
NP-hard ⊃NP-complete
Exponential
Non-NP
The two alternatives (P vs. NP) and their consequences
If P ≠ NP, then:
There exist problems that are neither P nor NP-complete. They are called NP-intermediate problems. The factorization problem, the graph isomorphism problem and the discrete logarithm problem, if they belong to neither the P-class nor the NP-complete class, then they would belong to the NP-intermediate class.
If P = NP, then the consequences would be very important, among them:
Exponential time complexity problems would be reduced to simple polynomial time complexity problems. This could mean that the simple and the complex are united, that they are the same thing, that complexity does not really exist, that everything can be reduced to the simple.
I could answer positively the general philosophical question about whether human creativity can be automated.
Many optimization problems would have an efficient solution (commuter problem, production processes, logistics, electronic chip design, operational research, etc.).
It would transform mathematics, since it would allow a computer to find, in polynomial time, a formal proof of almost any theorem.
Improved prediction of weather, earthquakes, tsunamis and other natural phenomena.
Automatic translation, speech recognition and object recognition would be almost perfect.
Artificial intelligence would be easier to develop and apply.
It would speed up the performance of the Internet and many network problems could be addressed with great ease.
It would affect descriptive complexity theory. Ron Fagin showed that the complexity of the NP class of problems is the same as the class of problems described in second-order predicate logic. [see MENTAL Properties, a Simple Language Foundation of Complexity].
It would adversely affect cryptography, as the encryption would be easy to discover, since it usually uses the method of factoring a large natural number.
Some thoughts and opinions on the question P vs. NP
It is clear that, as it stands, this is a decision problem. But perhaps this question is undecidable. We would then find ourselves in a situation similar to the problem of the stopping of a Turing machine or Gödel's incompleteness or undecidability theorem.
In general, the majority view of complexity theorists is that P ≠ NP, for three main reasons:
There are many combinatorial problems of class NP to which no polynomial complexity algorithms have been found, and that is because P ≠ NP is most likely.
Most efforts on the subject of P vs. NP have been directed at proving that P NP.
There are many quasi-empirical indications that P ≠ NP.
The term "quasi-empirical" was created by Imre Lakatos to refer to mathematical method that requires support by experimentation. A paradigmatic case is that of Goldbach's conjecture (every even number greater than 2 is the sum of two prime numbers). This conjecture has been proven to be true up to 1024 with the help of powerful computers.
For Razborov & Rudich [1997], it is possible that this question is so difficult to prove precisely because P NP and because the problem of proving it is of class P.
"Solving the P vs. NP question may require a paradigm shift" (Bhupinder Singh Anand).
Scott Aaronson [2003] is perhaps the author who raises the most questions regarding this issue:
He wonders whether P vs. NP could be independent of the formal axiomatic system of set theory (such as ZF theory), as is the case with certain mathematical problems (such as the continuum hypothesis). Considering that the P vs. NP question ultimately boils down to whether there is an efficient algorithm for the SAT problem (which is the paradigmatic NP-complete problem), there are two possibilities:
If there were no efficient algorithm for SAT, it would be impossible to prove that P vs. NP is in ZF.
If such an efficient algorithm existed, it would be impossible to prove that it is efficient.
"The problem P vs. NP is perhaps self-referential, for posing the question P vs. NP is surely an example of an NP-hard problem."
"If we believe that P ≠ NP, there remains only one hope for solving NP-complete problems in polynomial time, namely, to generalize what we mean by 'computer'."
"It is clear that a proof of P ≠ NP, if it exists, would require entirely new techniques."
"Investigating the truth or falsity of P ≠ NP is a practically impossible task without first investigating the means of investigation."
"Is P vs. NP really a question of logic or of combinatorics?".
The Ways to Decrease Computational Complexity
There are two ways to try to decrease the computational complexity of problems: the practical way and the theoretical way.
The practical way tries to overcome the limitations of current digital computers by using alternative physical computational models, such as the following:
Analog computing.
An example of a complex computational problem that can be solved by a physical process is the STP problem (Steiner Tree Problem) [Garey & Johnson, 1979]. This is an NP-complete problem that consists of connecting all the points of a graph in such a way that the total length of the arcs is minimal. It can be solved quickly with analog computation, by the following physical process: 1) Two square parallel plates are taken and joined only on one side; 2) Pins connecting the two plates are placed n. The pins represent the points of the graph; 3) The structure is immersed in a soap solution and then removed. The soapy film connecting the pins is the solution to the problem, because nature always follows the principle of maximum economy.
Quantum computing.
The first example of a quantum algorithm capable of solving a complex computational problem was developed by Peter Shor [1996]. He showed that a hypothetical quantum computer might be able to factor a number of n digits with time complexity O((log n)3) and space complexity O(log n).
Molecular computation.
Leonard Adleman [1999], the pioneer in this area, performed an experiment with DNA molecules in the laboratory with which he solved a small example of the commuter problem. For the SAT problem, an analog algorithm implemented with DNA molecules has been presented [Takenaka & Hashimoto, 2002].
Membrane computing (P-systems).
P-systems are parallel systems that could solve NP-complete problems efficiently using active membranes capable of producing an exponential workspace in exponential time.
The theoretical way tries to use special efficient algorithms, such as the following:
Divide and conquer algorithms.
It refers to a popular saying and consists of a top-down process in which a complex problem is recursively divided into simpler subproblems (of the same or related types), as many times as necessary, until the solution is obvious. The solution of the main problem is constructed, in an inverse process (bottom-up) from the simple solutions found.
It is one of the most important algorithmic paradigms as it is the foundation of many efficient algorithms such as: sorting (Quicksort and Mergesort), large number multiplication, matrix multiplication, top-down parsing and the fast Fourier transform. This algorithm has been known since Euclid, who applied it to obtain the greatest common divisor of two numbers, and represents the natural tendency to search for the simplicity hidden in the apparently complex.
Quicksort was invented by Tony Hoare in 1962. It is a very simple algorithm for sorting a numerical or alphabetical list. Its average efficiency is O(n·log n), where n is the length of the list. It consists of taking a pivot element (the first one in the list) and separating the rest in two lists, formed by the elements smaller and larger than the pivot, respectively. In the two lists the process is repeated again until arriving at lists of only one element.
Mergesort is an algorithm invented by John von Neumann in 1945 to sort a list. Its time complexity is also O(n·log n). It consists of the following: 1) If the list is of length zero or one, the list is already sorted; 2) Split the list into two sublists of approximately the same size: 3) Sort each sublist recursively by applying Mergesort; 4) Merge the two sorted sublists into a single sorted list.
Large number multiplication was invented by Anatoli A. Karatsuba in 1960. It reduces the time complexity from O(n2) to O(n^log23) = O(n1,585).
Volker Strassen's algorithm for matrix multiplication, invented in 1969, is faster than the standard algorithm. It consists of dividing matrices into submatrices until one arrives at single-element matrices, whose multiplication is obvious. This algorithm encouraged the search for even faster algorithms, such as the Coppersmith-Winograd algorithm (published in 1987).
The fast Fourier transform was invented by James W. Cooley and John W. Tukey in 1965. It is one of the most widely used algorithms in mathematics. It reduces the time complexity from O(n2) to O(n·log n).
Non-deterministic algorithms.
They are based on the relationships between the probabilistic characteristics of certain stochastic processes and the solutions of some given problems. The advantage of this method is that its margin of error does not depend on the number of variables in the problem, so it is applicable to complex problems with many degrees of freedom. But the main limitation of this non-deterministic approach is the generation of random numbers, as the generators are usually slow and not always reliable. In general, nondeterministic polynomial-time algorithms are more powerful than deterministic ones.
The most representative example is the famous Monte Carlo method, invented by Nicholas C. Metropolis, Stanislaw M. Ulam and John von Neumann in 1946.
Feynman [1982] showed that the problem of exponential complexity expressed by calculated probabilities can be reduced to a polynomial problem expressed by simulated probabilities.
Holographic algorithms.
They are a family of algorithms invented by Leslie Valiant that can achieve exponential speeds in a certain class of problems. They are of great interest because they are considered relevant in the P vs. NP problem. They are also called "accidental algorithms" because of their capricious and unpredictable quality. These algorithms have no relation to holography, except metaphorically. Although they have certain similarities with quantum computation, they use classical computation. Their efficiency comes from the mutual cancellation of many addends, which evokes the interference patterns of a hologram and quantum superposition.
Holographic algorithms are mainly used to optimize graph problems, such as the minimum vertex cover problem (vertex cover). A vertex cover of a graph is a set of vertices such that each arc of the graph is incident to at least one vertex in the set. The problem of finding the minimum vertex cover is an NP-complete problem and is included in Karp's list of 21 NP-complete problems.
The P vs. NP Problem from the MENTAL Paradigm
General Issues
The philosophical question.
From a philosophical point of view, there is a universal principle that states that at a deep level there are no differences, that borders disappear and that everything is connected and unified. The problem then boils down to finding or identifying that deep level, in this case, the deep computational level. But if MENTAL represents the highest possible level of abstraction, from the paradigm of this language, the P and NP classes must be seen as manifestations of something deeper and more unified.
Common sense.
Common sense tells us that, in general, calculating a solution to a problem is more difficult than verifying it, even though both processes are polynomial time (since they may have different exponents). According to this point of view, P ≠ NP.
Formalism vs. intuitionism.
The P vs. NP problem is too abstract and generic to be solved at a strictly formal level. A generic problem can only be answered conceptually/intuitively.
A purely formal or constructive proof would require a formal definition of the sets P and NP, but traditional mathematics is not capable of this, since it cannot express the properties of these sets. A completely new formal language would be needed. According to this view, if we cannot state the problem formally, we cannot answer it at this same level either.
The proof of P vs. NP, if it exists, has to be very different from the normal mathematical proofs. It should be creative, intuitive, beyond the usual analytical and sequential demonstrations. The old methods do not work. It is necessary to look at the problem from a higher point of view. As Einstein said: "No problem can be solved from the same level of consciousness that created it".
Metamathematics.
The P vs. NP problem is a metamathematical problem. It is curious that we need a mathematical proof to demonstrate the limits of computation. It happens as with Gödel's theorem, which uses mathematics to prove the limits of mathematics (in this case, the limitations of formal axiomatic systems). Being a metamathematical type of problem, it is not strange to suppose that the known mathematical tools are insufficient to solve it.
Operational vs. descriptive.
Perhaps NP-hard problems can be solved not operationally or computationally, but descriptively, or a mixture of both systems. For example, Gödel's famous sentence G "I am indemonstrable" is not computable, it is inaccessible, but it is describable and represents a fractal expression. In MENTAL: (G =: G/I), which represents the fractal expression ((((G/I)/I)/I)..., being I the predicate "indemonstrable".
Sequential and parallel algorithms.
The problem with traditional algorithms is that they are usually sequential. In the case of the subset sum problem, it requires successively generating and analyzing each of the subsets. A solution, if possible, would be to generate all the subsets in parallel and verify their sum in parallel. Then the solution would be immediate. The problem is that this method would require an enormous amount of memory, and also the computer architecture is not ready for this task, since parallelism requires as many processors as parallel processes. However, all that exists are parallel systems that evolve in parallel (society, nature, etc.). Computer engineering must tend towards the development of generic computational parallelism, for data and processes. Therefore, if memory were not limited, the "P vs. NP" problem would be reduced to the "sequential vs. parallel" problem.
If we do not have sufficient memory, we can tackle exponential time complexity problems using mixed sequential-parallel algorithms. For example, in the subset sum problem, by dividing the process into n phases. In the first phase we select the 1-element subsets, in the second the 2-element subsets, etc., until we reach the phase n in which we select all the elements. In each of these phases we apply a parallel process.
The question of the two modes of consciousness
The P vs. NP question is, once again, a particular case of the universal bipolarity, represented or symbolized by the characteristics of the two modes of consciousness of the cerebral hemispheres. In this case, the poles are the NP-easy and NP-difficult computational problems. In effect:
NP-easy (polynomial-time) problems can be associated with practical, concrete, simple, compressed, conscious, feasible, certain, exact, efficient, direct, linear, rational.
NP-difficult (exponential time) problems can be associated with the theoretical, the abstract, the complex, the expanded, the unconscious, the possible, the approximate, the fuzzy, the recursive, the cyclical, the intuitive, the creative.
There is a continuous gradation, there is no concrete boundary between the two, but a diffuse one. Indeed, the NP-easy vs. NP-difficult problem is fuzzy if posed in terms of efficiency, since it makes efficient and polynomial time equivalent. But polynomial-time algorithms are not always feasible or tractable. For example, an algorithm requiring n100 steps could not be executed in reasonable time, even with a value of n small (e.g., 10), because the resulting number (10100) is larger than the number of atoms in the universe (1077). And not every exponential time algorithm is intractable. The boundary, then, between polynomial time and exponential time is somewhat fuzzy.
To find an efficient algorithm for a problem is to bring it to consciousness. But you have to gain ground on the unconscious. This is the process of science, consciousness and evolution. If an NP-hard problem cannot be solved as NP-easy, we must try to optimize it, lowering as much as possible its degree of time complexity.
For easy problems (those of polynomial time) it is sufficient to use the ratio. Difficult problems (those of exponential time) lead us to wide spaces, of many possibilities, that overflow our normal capacity of analysis, so we must contemplate them from a higher point of view and use creativity, intuition and imagination, applying for example heuristic type rules that generate understanding. Brute force is searching blindly, aimlessly, without awareness. When there is a heuristic, the search for solutions is simplified, there is direction, more awareness of the problem, because in the heuristic the objective is encoded.
Therefore, the P vs. NP problematic is nothing more than the universal problematic of the two modes of consciousness. The meeting point of both modes is to be found in the primary archetypes, in the universal semantic primitives that represent the supreme level of abstraction.
The question of the computational model
The Turing machine is the computational model commonly used as a reference in the P vs. NP question. This model, introduced by Alan Turing in 1936, is theoretical and was introduced before the first digital computers were built. The Turing machine does not consider the aspect of computational complexity; only if algorithms can be implemented that are capable of producing a result, without limit of time or space (the unlimited tape of the machine). The Turing machine sets the limits of computation, and no alternative computational model can exceed this limit.
However, this model is superficial, low-level, detail-oriented. It is not conducive to creativity, so necessary for solving NP-hard problems. The alternative is MENTAL, a language that provides a new computational model based on degrees of freedom, flexible, open and creative. Maximum creativity emerges from the deep, from the level of supreme abstraction. From this model, all problems are simpler, everything is clarified and simplified because everything is contemplated from the gates of consciousness: the universal semantic primitives. MENTAL brings a new paradigm, a unifying paradigm that allows us to see with new eyes old problems, in particular the P vs. NP problem.
MENTAL is a conceptual, theoretical, ideal language (like the Turing machine), which is independent of the available physical resources. For example, if certain resources (such as parallelism of expressions) do not exist, they must be simulated. It is, in short, the problem of competence (or theoretical computational power) versus efficiency (practical computational power with the available resources).
With MENTAL you can create more efficient and creative algorithms than traditional ones thanks to its flexible high-level computational resources, among which we can highlight:
Parallelism.
It is both spatial and temporal. Parallel evaluation of an expression is an implementer problem that does not necessarily imply that there must be as many processors as there are elements to be evaluated in parallel.
Generic expressions.
Generic expressions (parameterized or not) allow to define virtual, linked, shared, etc) expressions. They allow working with patterns instead of data or concrete expressions. Data can be parameterized. Non-local relationships can be established. These expressions can be manipulated, transformed (into particular expressions, into generic expressions of higher order, etc.).
Representation.
Representation (potential substitution) makes it possible to describe all types of expressions, including those of infinite type. This implies that it is not necessary to generate all detail expressions.
Sharing.
Shared expressions save space, since they belong simultaneously to several expressions. Sharing is all the more effective the larger the elements to be shared.
Partial evaluation.
Avoids having to evaluate a complete expression. Can be applied to all types of expressions, including generic ones.
Higher order expressions (meta-rules, virtual expressions of virtual expressions, shared expressions of shared expressions, etc.).
Dynamic expressions.
They allow to implement algorithms that self-modify during execution. In this way the algorithms are protean objects, able to transform themselves during their execution.
Imaginary, recursive, fractal and paradoxical expressions.
Metaprogramming.
It is the dynamic generation of sub-algorithms (or processes in general) with interrelation between them through the environment.
Symbolic or generic executions.
These are executions with generic arguments, which can be monitored in turn by other generic expressions to count computational steps, perform shortcuts, etc. in order to draw conclusions about the complexity of the algorithms.
Thanks to these resources, computational complexity should decrease, in the sense of requiring fewer temporal and spatial resources.
Conclusions
P is not equal to NP, because NP-easy and NP-difficult are two poles or extremes of complexity. But both kinds of complexity share the same computational essence, the same primal archetypes, the universal semantic primitives.
The true nature of computation arises not from solving the P vs. NP problem, but from identifying the deep, high-level abstraction resources that are the universal semantic primitives.
The P vs. NP issue is independent of the ZF axiomatics of set theory. But there is a certain analogy, for universal semantic primitives play a role analogous to that of the axioms of set theory. They are semantic axioms.
With MENTAL we do not obtain all the expected benefits if it were true that P = NP, but we do obtain the following:
It reveals which are the computational degrees of freedom, which are those that define the limits of what is computable (and describable) and which represent the true essence of computation.
Complexity decreases. Everything is easier, everything is simplified and clearer.
It provides a privileged point of view, of maximum awareness, from which to contemplate computation. In fact, computation is a manifestation of the archetypes of consciousness.
Creativity is encouraged. Creativity cannot be automated but can be programmed. Creativity is inherent in the orthogonal combinatorial nature of primitives.
It provides a universal paradigm from which all kinds of specific paradigms can be implemented.
Operational and descriptive complexity are united in the same conceptual framework (they are two aspects of the language).
Algorithms are very compact (their algorithmic complexity is lower).
Artificial intelligence is simpler to develop.
It is valid for all problems, whether NP or non-NP. It is universal. We see all problems with the same "glasses", which provide us with the maximum computational resources available. It is up to us to combine those resources in a creative way to optimize as much as possible each problem posed. The greater the complexity of the problem, the greater the degree of creativity required to solve it.
Ultimately, the problem of complexity is the problem of finding computational simplicity, simplicity that is achieved with the archetypes of consciousness. Paradoxically, computational complexity theory is the theory of computational simplicity.
Addenda
The Clay Institute Award
On May 24, 2000, the Clay Institute of Mathematics (based in Cambridge, Massachusetts), on the occasion of a conference in Paris, offered a prize of one million dollars to the person who solves one of the "7 millennium problems", problems that the mathematical community considers both important and difficult to solve. The year 2000 was declared "World Mathematics Year" by Unesco, one hundred years after Hilbert enunciated his famous 23 problems at the International Congress of Mathematicians, also held in Paris.
In 2003, the Russian mathematician Grigori Perelman solved one of them: the Poincaré conjecture (now turned into a theorem). The other 6 remain unsolved. One of them is precisely the P vs. NP problem. But it is believed that if this problem were solved, the others would probably be solved as well.
A little history
In 1965, Jack Edmonds proposed a formal definition of "efficient computation": execution in a number of steps bounded by a polynomial of a variable associated with the complexity of the problem, related to the input data. He gave the first example of how to avoid brute force in finding solutions by discovering an efficient algorithm for solving the "maximun general matching" problem, with time complexity O(n4).
The problem "maximun general matching" is one of the central questions in combinatorial mathematics. The problem is, for example, the following. It involves housing students in a residence hall. There are 400 students and 100 double rooms available. There is a list of incompatible pairs of students to share a room. You need to calculate the maximum number of possible pairs of students.
The origin of the question P vs. NP seems to go back to a letter Gödel wrote to Von Neumann in 1956, in which he stated the problem clearly and which shows that he was aware of its importance. He wondered how to improve the brute-force method in general for solving combinatorial problems, especially the proof of formulas of the predicate calculus. Apparently, Gödel saw the problem as analogous to Hilbert's Entscheidungsproblem, but of finite type. It is not known whether von Neumann (who was then dying of cancer) pondered this problem or answered him. The original handwritten letter and its English translation can be found in the appendix of [Sipser, 1992].
The Entscheidungsproblem (decision problem) is the problem of finding a general algorithm that would decide whether a formula of the first-order predicate calculus is a (universally valid) theorem or not. In 1936, Church (with the lambda calculus) and Turing (with the ideal machine bearing his name) independently formalized the concept of algorithm and proved that such a task was impossible, that the problem was undecidable.
Stephen Cook [1971] was the first scientist to formally pose the P vs. NP question in his 1971 paper entitled "The complexity of theorem proving procedures", where he posed the SAT (logical satisfiability) problem that gave rise to the concept of the NP-complete class and the P vs. NP question. Stephen Cook is also the author of the official paper on this problem done for the Clay Institute [Cook, 2000].
Richard Karp's paper "Reductibility among combinatorial problems" [1972] sparked renewed interest in Cook's paper. In his paper, Karp provided a list of 21 NP-complete problems. Karp proved that these problems were NP-complete by reducing (or transforming) them to another problem that had already been shown to be NP-complete: the SAT problem. Cook and Karp received the Turing Award in 1982 and 1985, respectively, for their contributions to computational complexity theory.
Leonid Levin [1973] showed 6 universal sequential search problems, which were NP-complete. His work provided a possible way to find an efficient algorithm, which would imply that there would also be an efficient algorithm for every NP-complete problem, and therefore, that P = NP.
Garey & Johnson [1979] collected more than 300 NP-complete problems. Today there are thousands of problems of this complexity class.
Deolalikar's proof of P ≠ NP
Vinay Deolalikar, an Indian mathematician working at HP Research Labs in Palo Alto (California), published a paper on 6 August 2010 in which he claimed to have proved that P ≠ NP. His proof is based on the fact that if certain problems, which are known to be NP-complete, were also in P, then they would have impossible statistical properties. Deolalikar's paper, which has been updated several times to correct some errors that have been detected in it, is very complex (it is 102 pages long) and it will take some time for his proof to be fully verified and accepted.
What is interesting about the article is that the author uses a new research method, as he combines two different approaches: logic and statistical physics. He moved the computational problem P vs. NP to the world of formal logic, using the "finite model theory". He focused on a SAT problem (Boolean satisfiability) from the following perspective: if k is the number of logical expressions of n Boolean variables and a number of n binary digits are chosen at random, what is the probability that this number satisfies these logical expressions? If k is very large and the number of possible solutions is small, there will never be correct solutions, no matter how much time is spent. If k is small and n is large, there will always be solutions. At a certain intermediate point between the two extremes there are solutions and a rich structure of probability distributions. According to the author, since the constraints of polynomial-time algorithms are too large to produce this rich structure, he deduces that P ≠ NP.
Bibliography
Aaronson, Scott. Los límites de la computación cuántica. Investigación y Ciencia, Mayo 2008, pp. 62-69.
Aaronson, Scott. Is P versus NP formally independent?. Bulletin of the European Association for Theorical Computer Science, 81, October 2003. Disponible en Internet.
Adleman, Leonard Max. Molecular Computation of Solutions to Combinatorial Problems. Science, 226, Nov. 1999, pp. 1021-1024.
Arora, Sanjeev; Barak, Boaz. Computational Complexity. Cambridge University Press, 2009.
Baker, Theodore; Gill, John; Solovay, Robert. Relativizations of the P =? NP question. SIAM J. Comput. 4(4), 431-442, 1975.
Clay Mathematics Institute. Millenium prize problems. http://www.claymath.org/ millennium/
Cook, Stephen A. The P versus NP Problem. Clay Mathematics Institute, Cambridge, Massachusetts, 2000. Disponible en Internet.
Cook, Stephen A. The complexity of theorem proving procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computation (STOC´71), pp. 151-158. ACM Press, 1971. Disponible en Internet.
Edmonds, Jack. Minimum partition of a matroid into independents subsets. Journal of Research of the National Bureau of Standards, 69: 67-72, 1965.
Feynman, Richard P. Simulating Physics with Computers. International Journal of Theoretical Physics, vol. 21. no. 6/7, 1982.
Fortnow, Lance. The Status of the P Versus NP problem. Communications of the ACM, vol. 52, no. 9, pp. 78-86, 2009. Disponible en Internet.
Garey, Michael R.; Johnson, David S. Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979.
Gasarch, W. The P =? NP problem. SIGACT News, 33(2):34-47, June 2002.
Goldreich, Oded. P, NP, and NP-Completeness. The Basics of Computational Complexity. Cambrige University Press, 2010.
Hartmanis, J; Stearns, R.E. On the computational complexity of algorithms. Transactions of the AMS 117, 285-306, 1965.
Horowitz, Ellis; Sahni, Sartaj. Computing Partitions with Applications to the Knapsack Problem. JACM, 21(2):277-292, April 1974.
Karp, Richard M. Reductibility among combinatorial problems. En Raymond E. Miller & James W. Thatcher (eds.) Complexity of Computer Computations, Plenum, pp. 85-103, 1972.
Levin, Leonid A. Universal Sequential Search Problems. Problems of Information Transmission, 9(3), 265-266, 1973.
Lipton, Richard J. The P=NP Question and Gödel´s Lost Letter. Springer, 2010.
Rayo, Agustín. Problemas del milenio. Investigación y Ciencia, Abril 2010, pp. 92-93.
Razborov, A.A; Rudich, S. Natural Proofs. Journal of Computer Systems Science, 55:24-35, 1997.
Schöning, Uwe. A uniform approach to obtain diagonal sets in complexity classes. Theoretical Computer Science, 18(1): 95-103, 1982.
Shor, Peter W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. 1996. Disponible en Internet (arXiv).
Sipser, Michael. The History and Status of the P vs. NP Question. Proceedings of the 24th annual ACM Symposium on Theory of Computing, pp. 603-618, 1992. Disponible en Internet.
Takenaka, Yoichi; Hashimoto, Akihiro. An Analog Algorithm for Satisfiability Problem. Fifth International Symposium on Theory and Applications of Satisfiability Testing (SAT2002), pp. 70-77, (Cincinnati, Ohio, USA), 9th, May, 2002. Disponible en Internet.
Wigderson, Avi. P, NP, and Mathematics. A Computational Complexity Perspective. Proceedings of the ICM 06 (Madrid), 1, pp. 665-712, 2006. Disponible en Internet.
