P vs NP | Importance of Mathematics

Computers have changed the world in innumerable ways, from making it possible for us to interact with individuals on the other side of the globe to giving us instant access to massive amounts of knowledge. Computers are lightning-quick and can quickly find solutions to a wide variety of complicated issues. But even with all of their computing power, some issues still take too long to resolve. How come?

To understand this problem, let’s consider a simple example. Take the problem of multiplying two numbers, say 7 and 13. The answer is 91, of course. But what if we reverse the problem and try to find the factors of 91? The answer is 7 and 13, but if we look at a bigger problem,

Computer will give this solution in a blink

but hey well if you do this

Now this problem take a computer a little longer to find the answer. In fact, it took 20 years of computer effort to solve one such problem.

I was so amazed by this and then again he gave another example where they are offering $30,000 to factor a problem, well if i had those big computers that are used to mine bitcoins i would have done it !

But why would someone pay $20,000 to solve a problem like this? Well, mathematicians do it because they love math. But there is another reason why solving such problems is so important. It comes from a company called RSA, which is a leader in cryptography. The factoring of large numbers is an ingredient in modern cryptography, and if someone is able to factor numbers quickly, it could be a problem for codes that rely on prime numbers.

The reason why factoring takes a long time is that brute force search is very slow when the search is huge. It will go through every possible pattern to find the factors, and this process is mindless. But the question is, is searching necessary?

What is a clique problem ?
Well, its a group of nodes that are connected by a line we call it a clique. Now the example he gave was very good he said suppose we have people in office and we are trying to find which of them are friends and mutual friends now this is a real world clique problem.

Now finding the circles which are connected to each other mutually are mutual friends.We have to go through every possibility and see if they are mutually connected or not. These are some smaller examples but what if we have a large clique and we have to find a bigger clique? finding the largest clique in 100s of nodes may take a lot a lot of time maybe centuries.

Now finding it in a large nodes is similar to finding a needle in a haystack.

Surely it will take you alot of time. But what if you have a magnet. Now the magnet is the solution right. But in the another scenaorio mathematically is there any magnet that we can use to avoid searching ? Nobody knows

Well there is the P vs NP question

The P vs NP problem is a fundamental question in computer science and mathematics that asks whether certain problems can be solved quickly (in polynomial time) by a computer. The P stands for polynomial time, which means quickly solvable problems. The NP stands for nondeterministic polynomial time, which means quickly checkable problems. This includes search problems that might involve searching through a haystack to find a needle.

Can we solve search problems without searching

That is a poetry there how can you search without searching.

Both P and NP are classes of computational problems, and the mathematical question is whether these two classes are the same. If they are the same, then any problem that can be solved by searching can also be solved without searching. But if they are not the same, then there are some problems that will require searching, and nobody knows if there is a fast possible way to solve them.

The History

The history of the P vs NP problem goes back to the 1960s, at the dawn of complexity theory. The problem was first introduced in 1971 by Cook, Levin, and Karp, who showed that certain problems were NP-complete, meaning that they were at least as hard as any other problem in NP. This was a significant discovery that laid the foundation for modern complexity theory.

But the problem of P vs NP goes back even further than that. In 1956, Gödel wrote a remarkable letter to von Neumann that foreshadowed the P vs NP problem. Gödel was one of the greatest logicians of the 20th century, and his letter was a significant contribution to the field of computer science. In the letter, Gödel discussed the idea of a machine that could tell whether a mathematical statement has a proof of length n for some specified n, and he asked how much time the machine would need to solve this problem.

This question is a classic search problem, and the question is how fast p(n) grows for an optimal machine. If p(n) grows polynomially, then the problem is in P. If it grows more than polynomially, then the problem is not in P. This is essentially the P vs NP problem in its earliest form, and Gödel’s letter inspired many subsequent researchers to study the problem in more depth.”

And I was so amazed by this that even when there was no such technology at that time they were able to think about such a big problem which is still to date unsolvable. And it just shows how imagination is the mother of inventions and discoveries.

The P vs NP problem is not just an abstract mathematical puzzle; it has important practical implications as well. Many important real-world problems, such as scheduling, optimization, and logistics, are known to be NP-complete, which means that finding efficient solutions for them is extremely difficult. If the P vs NP problem were resolved, it could have a profound impact on fields such as cryptography, computer science, and operations research.

Well after 50 years or so P vs NP problem with a mythic status in the field. It is often referred to as the holy grail of computer science due to its potential to unlock solutions to many other computational problems. The P vs NP problem is just one of the ten unsolved problems in mathematics known as the Clay Millennium Problems, which include the Poincare Conjecture, the Riemann Hypothesis, the Birch and Swinnerton-Dyer Conjecture, the Hodge Conjecture, and the Yang-Mills Theory.

The Poincare Conjecture was one of the most notable problems on the list, but it was solved by Russian mathematician Grigori Perelman in 2002. The P vs NP problem, however, continues to elude researchers. The problem is essentially about searching for solutions in large sets of data. The question is whether this search can be done efficiently, or whether it will take exponentially long to find a solution.

One might think that the solution to the P vs NP problem is obvious, that we must search for solutions. However, sometimes it is possible to avoid searching altogether, as in the case of testing for primality. A simple theorem states that if a number is prime, then for any number a less than the prime number p, a^(p-1) will be congruent to 1 mod p. For example, if we take p=7 and a=2, then 2⁶ = 64 = 1 (mod 7). However, if p is not prime, such as in the case of p=15, then 2¹⁴ = 16384 = 4 (mod 15), which is not equal to 1. This can test for primality without searching, as it is essentially a search problem.

This leads us to the concept of NP-completeness. The idea is that problems in NP (i.e. problems that can be solved by searching and then verified) are linked to each other. If we can find a way to solve one problem in NP without searching, then we can convert any other NP problem into that problem, and solve it without searching. For example, if we can solve the clique problem without searching, then we can convert the factoring problem into a clique problem, and then solve it without searching. If we can solve any NP problem by converting it into a clique problem, and if we can solve the clique problem in polynomial time, then P=NP.

However, many problems do require searching, and it is hard to prove whether P=NP or not. Computer algorithms can operate in unforeseen ways, and even in the case of primality testing, there are many devilish ways to solve the problem.

One approach to solving the P vs NP problem is to limit the capabilities of the machine. By using a limited machine, it is easier to prove that we can only solve the problem by searching. We can then remove the limitations step by step until we arrive at a solution that can be solved by a normal machine.

Despite numerous attempts by mathematicians and computer scientists, the P vs NP problem has yet to be solved. In the mid-1970s he and Lan Adleman, a researcher at RSA code, boldly claimed that the problem would be resolved by the year 2000. He even bet an ounce of gold on his prediction, stating that he got lucky because the price of gold back then was around $700 per ounce. However, when he paid off the bet, the price of gold had dropped to $250 per ounce, making him even luckier. Despite his confident prediction, the P vs NP problem remains one of the most significant open questions in computer science and mathematics today.

In conclusion, the P vs NP problem is a mythical problem in computer science that has the potential to unlock solutions to many other computational problems. It is still an open problem that researchers are actively trying to solve. While some problems can be solved without searching, many others require searching, making it difficult to prove whether P=NP or not

In conclusion, the P vs NP problem is one of the most important and challenging problems in computer science and mathematics. Its resolution could have far-reaching implications for our understanding of computation and for many practical applications. But even if the problem remains unsolved, the search for a solution has spurred advances in many other areas of research and has inspired generations of mathematicians and computer scientists to explore the boundaries of human knowledge.

In addition to this while attending this lecture i also had a question in my mind as we are in a time where we have quantum computers which works in very different way compared to our normal computer, a quantum computer is like a very special kind of computer that can do some things really, really fast. It uses tiny particles called “quantum bits” or “qubits” instead of the usual “bits” that regular computers use.

Imagine you have a toy box with a bunch of toys inside. If you want to find a specific toy, you would have to look through the box one toy at a time until you find the one you want. That can take a while if you have a lot of toys! But with a quantum computer, it’s like you can look through the whole box all at once and find the toy you want much faster.

A quantum computer is like a magical toy box that can do lots of calculations all at the same time. It’s different from regular computers because it can use something called qubits, which are like really special toys that can be in lots of different states all at once. But even with this superpower, we still don’t know if quantum computers can solve the p vs np problem yet. This is important because lots of secret codes we use to protect our information are based on the idea that p vs np is really hard to solve. If quantum computers can solve it, they might be able to reveal our secret codes!

Importance of Mathematics

Timothy Gowers

As they stand in front of a crowd in Paris to deliver a keynote address on the value of mathematics, he starts their speech with a sense of disbelief. They are grateful for the opportunity to speak on this topic, but they also recognise the responsibility that comes with it because they are aware that their words will have an effect on both the mathematical community and Mr. Clay, whose generosity made the event possible.

He recognizes that to the general population, mathematics may not seem particularly important, with only a small percentage being able to accurately state a mathematical theorem from the last 50 years, excluding Fermat’s Last Theorem. When mathematicians are asked to explain their work, it is often met with a sheepish grin, as it is not easy to summarize complex work in a short time. The practical applications of mathematics are also questioned, with some mathematicians arguing that the criterion for mathematical worth is beauty, while others work in more practical areas such as financial mathematics or statistics.

He points out that many mathematicians lie somewhere in the middle of the spectrum when it comes to their attitude towards applications. They would be pleased if their work proved useful outside mathematics, but they do not actively seek to do so. However, they would feel awkward if nobody worked on practical problems. He also notes that a great deal of research in even the so-called practical areas is not practical at all, but this is a natural and desirable consequence of what it means to view the world mathematically.

As the speech progresses, He delves deeper into the nature of mathematics and how it is a two-stage process. Rather than studying the world directly, mathematicians create models of the world and study them. This applies even to the simplest mathematics. The example of addition, which is not studied by actually combining groups of objects and counting them but instead using an abstract mathematical construction or model known as the positive integers.

He then goes on to say that even basic geometry is studied through models, such as idealized worlds that contain things that do not exist in everyday life, like infinitely thin lines that stretch away to infinity or absolutely perfect circles. These models do not contain worldly things like chairs, humans, or hamburgers. He argues that if one works in a practical area of mathematics, then there is often a need to use models that are more closely tied to the real world. However, these models are still not the same as the real world.

He acknowledges that mathematics is a complex subject that is often misunderstood by the general population. The models that mathematicians create are not the same as the real world, but they allow us to study it in a way that is not possible otherwise. The practical applications of mathematics are not always immediately apparent, but they are there, and the beauty of mathematics is that it has the potential to transform our understanding of the world in ways that we cannot yet imagine.

Content Source and credit :