P vs NP Problem

The Kissing Number Problem
➖➖➖➖➖➖➖➖➖➖
In geometry, the kissing number of a mathematical space is defined as the greatest number of non-overlapping unit spheres that can be arranged in that space such that they each touch a common unit sphere. For a given sphere packing (arrangement of spheres) in a given space, a kissing number can also be defined for each individual sphere as the number of spheres it touches. For a lattice packing the kissing number is the same for every sphere, but for an arbitrary sphere packing the kissing number may vary from one sphere to another.
When a bunch of spheres are packed in some region, each sphere has a Kissing Number, which is the number of other spheres it’s touching; if you’re touching 6 neighboring spheres, then your kissing number is 6. Nothing tricky.

(check the images on the comment to be clear.)
✅In one dimension, the kissing number is 2
✅In two dimensions, the kissing number is 6
✅In three dimensions, the kissing number is 12
✅In four dimensions, it was known for some time that the answer was either 24 or 25
✔️The kissing number in n dimensions is unknown for n > 4, except for n = 8 (where the kissing number is 240), and n = 24 (where it is 196,560).
There are several hurdles to a full solution, including computational limitations. So expect incremental progress on this problem for years to come.

𝐓𝐰𝐢𝐧 𝐏𝐫𝐢𝐦𝐞 𝐂𝐨𝐧𝐣𝐞𝐜𝐭𝐮𝐫𝐞
➖➖➖➖➖➖➖➖➖
Twin Prime Conjecture is the most famous in Number Theory or the study of natural numbers and their properties, frequently involving prime numbers. Since you've known these numbers since grade school, stating the conjectures is easy.

When two primes have a difference of 2, they're called twin primes. So 11 and 13 are twin primes, as are 599 and 601. Now, it's a Day 1 Number Theory fact that there are infinitely many prime numbers. So, are there infinitely many twin primes? The Twin Prime Conjecture says yes.
Let's go a bit deeper. The first in a pair of twin primes is, with one exception, always 1 less than a multiple of 6. And so the second twin prime is always 1 more than a multiple of 6. You can understand why, if you're ready to follow a bit of heady Number Theory.

All primes after 2 are odd. Even numbers are always 0, 2, or 4 more than a multiple of 6, while odd numbers are always 1, 3, or 5 more than a multiple of 6. Well, one of those three possibilities for odd numbers causes an issue. If a number is 3 more than a multiple of 6, then it has a factor of 3. Having a factor of 3 means a number isn't prime (with the sole exception of 3 itself). And that's why every third odd number can't be prime.

How's your head after that paragraph? Now imagine the headaches of everyone who has tried to solve this problem in the last 170 years.

The good news is that we've made some promising progress in the last decade. Mathematicians have managed to tackle closer and closer versions of the Twin Prime Conjecture. This was their idea: Trouble proving there are infinitely many primes with a difference of 2? How about proving there are infinitely many primes with a difference of 70,000,000? That was cleverly proven in 2013 by Yitang Zhang at the University of New Hampshire.

For the last six years, mathematicians have been improving that number in Zhang's proof, from millions down to hundreds. Taking it down all the way to 2 will be the solution to the Twin Prime Conjecture. The closest we've come—given some subtle technical assumptions—is 6. Time will tell if the last step from 6 to 2 is right around the corner, or if that last part will challenge mathematicians for decades longer.

Goldbach’s Conjecture
➖➖➖➖➖➖➖➖➖➖➖➖➖➖
One of the greatest unsolved mysteries in math is also very easy to write. Goldbach's Conjecture is, "Every even number (greater than two) is the sum of two primes." You check this in your head for small numbers: 18 is 13+5, and 42 is 23+19. Computers have checked the Conjecture for numbers up to some magnitude. But we need proof for all natural numbers.

Goldbach's Conjecture precipitated from letters in 1742 between German mathematician Christian Goldbach and legendary Swiss mathematician Leonhard Euler, considered one of the greatest in math history. As Euler put it, "I regard [it] as a completely certain theorem, although I cannot prove it."

Euler may have sensed what makes this problem counterintuitively hard to solve. When you look at larger numbers, they have more ways of being written as sums of primes, not less. Like how 3+5 is the only way to break 8 into two primes, but 42 can broken into 5+37, 11+31, 13+29, and 19+23. So it feels like Goldbach's Conjecture is an understatement for very large numbers.

Still, a proof of the conjecture for all numbers eludes mathematicians to this day. It stands as one of the oldest open questions in all of math.

Travelling salesman problem (TSP)
--------------------------------------------------------
TSP asks "from given list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" it is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.

For example: what is the shortest possible route to start from City A and visit each city once and come back to city A?

- To solve this 6 cities symmetric TSP problem with brute force (try each path), it takes (n-1)!/2. then 5!/2 =60 possibilities. if we increase the number of cities the path possibilities increase exponentially. you may solve TSP with small number of cities with brute force, but when the number of cities become over 150 it may take many years to solve even with computers. that is why we call it np hard problems.
Of course there are some algorithms to solve TSP with approximation. but there is no exact algorithm for TSP yet. current TSP algorithms works well for small number of cities. but when the number of cities increase they start to approximate.
Can you find efficient algorithm for TSP?
-------------------------------------------------------------------
Try to solve this 6 cities symmetric TSP.

Why does P vs NP problems matter?
_____________________________________
Another way to ask whether P = NP is to ask whether every hard problem actually contains an easy, but hidden, solution.
Are these two flavor of problems irrevocably separate from one another? Are some problems simply complex by their fundamental nature?

If P does equal NP, then it would have some major implications for our way of life.
One major benefit is that many NP problems are referred to as being NP-complete, which means that their solutions can be quickly adapted to any other NP-complete problem.
So, developing a way to quickly solve one NP-complete problem would make significant strides towards completing all other NP-complete problems.

What are some examples of NP problems? Many researchers focus on one major concern.
The majority of modern cryptography relies on codes that are hard to crack but easy to check. As an example, consider the passwords or PINs to your various accounts.
Checking that they are correct is straightforward, but brute-force guessing every permutation of letters and numbers would take forever.
The encryption behind securing your credit card number when ordering something on Amazon, too, is an example of NP cryptography. If P = NP,
then cracking nearly every kind of encryption would suddenly become much, much easier.

While losing any semblance of internet security would be disastrous, there would be many beneficial consequences if P = NP.
Lance Fortnow, a computer scientist and author of The Golden Ticket: P, NP and the Search for the Impossible,
summed up some of the major consequences in an article for Communications of the ACM:

Transportation of all forms will be scheduled optimally to move people and goods around quicker and cheaper.
Manufacturers can improve their production to increase speed and create less waste. And I'm just scratching the surface.