AI Solves The P Versus NP Problem

Author(s): Andrea Berdondini

Originally published on Towards AI.

AI Solves The P Versus NP Problem

I want to start this article by asking the following question: what is the most important open problem? The problem that would most likely win would be P Vs NP problem[1][2]. This problem is considered the most important unsolved problem in the field of theoretical computer science.

PVsNP problem is a question regarding the resolution times of a problem. The term NP (nondeterministic polynomial time) indicates problems in which the correctness of the solution found is easy to verify, therefore requiring polynomial time. Instead, the term P refers to problems that have polynomial resolution times (easy to solve) and represent a subclass of the set NP.

Within the class of NP problems there is a very important subclass NP-C (NP-complete) made up of problems that have non-polynomial resolution times (difficult to solve). The PVsNP problem concerns precisely this class of problems and is stated as follows:

if the solution of a problem can be verified quickly (polynomial calculation time) then it is also possible to solve the problem quickly (P=NP).

In simpler terms, if I can verify the solution to a problem quickly, then I can also solve it quickly.

We are living in a time where artificial intelligence is applied in many different situations [3][4]. To understand the new method that exploits artificial intelligence, we need to reformulate the problem from the point of view of information theory.

Let’s start by asking the following question: what does non-polynomial computation time mean?

It means the computation time is exponential, but what does an exponential computation time mean?

It means that we must consider every solution and therefore, it is not possible a priori to discriminate some solutions. This means that we do not have any useful information that can be used to discriminate some solutions and, therefore, reduce the set of solutions.

Using this simple concept, we can reformulate the definition ofNP-C problem as follows: a problem is NP-C if there is not enough information to significantly reduce the set of solutions.

So, in other words, an NP-C problem is a problem that we don’t understand and therefore we are forced to iteratively work out all the solutions.

With these simple concepts let’s rephrase the PVsNP problem:

If there is a set of information that allows us to verify the correctness of a solution to a problem quickly then there is a set of information that allows us to solve it quickly.

I love this definition because, in just a few lines, it makes us fully understand the problem.

In fact, from this definition, we immediately understand that the main element in order to solve this problem is the search for information that can allow us to understand and therefore solve the problem quickly.

Now, let’s ask ourselves the following question: what type of characteristics must the information we are looking for have?

This question is important because not all information is “useful” for our purpose. Indeed, the calculation of information such as a statistical indicator (mean, variance, etc.) requires a number of calculations.

Therefore, for our purpose, we are only interested in “efficient” information that reduces the problem resolution times by a greater amount than the calculation times used to obtain the information itself.

Searching for this particular type of “efficient” information is almost impossible to do without the use of an automated method that can also “evaluate” the information.

And, it is precisely in this fundamental step (search for efficient information) that artificial intelligence comes into play through the development of artificial neural networks. The fundamental aspect of artificial intelligence is to be able to evaluate the information given; this aspect is fundamental. Indeed, the characteristic of neural networks that exploit reinforcement learning is that they reward the parameters (information) that are most efficient (fewer number of steps) in solving the problem.

Before, the arrival of these methods, the computer always and only had a supporting role, it never entered actively into the development of logical processes, which were instead always developed by man.

If this type of information found by artificial intelligence is implemented in an algorithm, we can say that the logical process, which led to the development of the algorithm, is of a hybrid type; partly generated by AI and partly generated by man.

With this method, it is possible to create algorithms that represent real collections of this efficient information. Therefore, they are algorithms with a level of complexity and abstraction much greater than those normally developed by humans.

This method has proven capable of finding this “efficient” information; however, this is not enough. Indeed, to go from an exponential to a polynomial calculation time, the efficient information must reduce the set of solutions to a fraction of the initial set.

In other words, to solve a problem quickly, there must be a high understanding of the problem; having only some efficient information can help us optimize the problem, which, however, can always remain with an exponential calculation time.

The step that still needs to be done is to understand, if we can generate such a large amount of efficient information capable of leading us to a full understanding of the problem.

Until now, we have always talked about solving a problem and we have never talked about mathematical proof, so it may come naturally to ask ourselves: how can this method give a definitive answer regarding the P Vs Np problem?

On this aspect, there is good news because the NP-C problems have the following characteristics: we just need to solve one of them, and we are sure that there is a fast way to solve all the other Np problems [5][6]. In fact, it has been shown that any NP problem can be reformulated as any NP-C problem.

Therefore, we don’t need a mathematical proof, we just to concentrate our forces on a single NP-C problem to be able to definitively solve P Vs NP problem.

The most famous example of an NP-C problem is the partial sum problem in which, given a set of numbers, we must search for subsets of numbers whose sum is equal to a constant value.

Now, let’s return to the P Vs NP problem and see some consequences of its possible resolution.

Case 1) P=NP it is possible to quickly solve an NP-C problem. This result implies that the condition of fast verification of the result is a sufficient condition to generate a non-random structure between the parameters that constitute the problem. In simpler words, parameters can be seen as variables dependent on each other. Therefore, it is possible to exploit this dependence, through the use of the efficient information described previously, to reduce the solution space significantly, making the problem solvable quickly.

Case 2) P≠NP it is not possible to quickly solve an NP-C problem. This result implies that the condition of fast verification of the result is a condition that is not sufficient to generate a non-random structure between the parameters that constitute the problem. Thus, the parameters can be viewed as independent random variables. Consequently, we cannot do anything other than take into account all possible combinations of these parameters (exponential calculation time).

In conclusion, solving this problem means knowing whether intrinsically random problems exist. Looking at this problem from this point of view, we notice some similarities with Godel’s incompleteness theorem [7], in which it is shown that there exist unprovable theorems. Therefore, just as there are unprovable theorems, there may be intrinsically random problems, in which it is not possible to define a logical scheme useful in helping us solve the problem quickly.

So, solving the PVsNP problem allows us to understand the nature of problems, and since problems are the elements that underlie human evolution, we can immediately understand why this problem is defined as the most important unsolved problem.

Like any unsolved problem, there are people who think that the case P=NP is true and others who think the case P≠NP is true. Since an algorithm capable of quickly solving an NP-C problem has never been found, supporters of the P≠NP case have always been in the majority. However, in recent times, supporters of the P=NP case have increased. Because the awareness is growing that NP-C problems are difficult to solve not because of their intrinsic randomness but because they require a level of complexity and abstraction that is difficult to understand for the human mind. Difficulty that can be overcome with the development of hybrid logical models, partly developed by man and partly developed by AI. In this dispute, I also, as a good gambler, want to make a bet on this problem and I bet on the P=NP case.

Bibliography:

1. Cook, Stephen (April 2000). “The P versus NP Problem” (PDF). Clay Mathematics Institute. Archived (PDF) from the original on 16 December 2013. Retrieved 18 October 2006.
2. Fortnow, Lance (2009). “The status of the P versus NP problem” (PDF). Communications of the ACM. 52 (9): 78–86. CiteSeerX 10.1.1.156.767. doi:10.1145/1562164.1562186. S2CID 5969255. Archived from the original (PDF) on 24 February 2011. Retrieved 26 January 2010.
3. Wang, H., Fu, T., Du, Y., Gao, W., Huang, K., Liu, Z., Chandak, P., Liu, S., Van Katwyk, P., Deac, A., Anandkumar, A., Bergen, K., Gomes, C. P., Ho, S., Kohli, P., Lasenby, J., Leskovec, J., Liu, T.-Y., Manrai, A., Marks, D., Ramsundar, B., Song, L., Sun, J., Tang, J., Veliˇckovi´c, P., Welling, M., Zhang, L., Coley, C. W., Bengio, Y., and Zitnik, M. (2023). Scientific discovery in the age of artificial intelligence. Nature, 620(7972):47–60
4. Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T. L., Cao, Y., and Narasimhan, K. (2023). Tree of thoughts: Deliberate problem solving with large language models. arXiv preprint arXiv:2305.10601.
5. Fortune, S. (1979). “A Note on Sparse Complete Sets” (PDF). SIAM Journal on Computing. 8 (3): 431–433. doi:10.1137/0208034. hdl:1813/7473.
6. Arora, Sanjeev; Barak, Boaz (2009). Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978–0–521–42426–4.
7. Adrian William Moore, 2022. Gödel´s Theorem: A Very Short Introduction. Oxford University Press, Oxford, 2022.

Join thousands of data leaders on the AI newsletter. Join over 80,000 subscribers and keep up to date with the latest developments in AI. From research to projects and ideas. If you are building an AI startup, an AI-related product, or a service, we invite you to consider becoming a sponsor.

Published via Towards AI