P versus NP problem

By

Millennium Prize Problems are seven problems in mathematics that were stated by Clay Mathematics Institute in 2000

Out of the 7 problems, one (Poincare conjecture)  problem has been solved

If some one solves any of the problem, he is awarded with US $1,000,000 prize

Poincare conjecture problem was solved by Grigori Perelman on year 2010,  but he declined  to receive the prize.

The seven problems are:
  1. P versus NP problem
  2. Hodge conjecture
  3. Poincare conjecture (solved)
  1. Riemann hypothesis
  1. Yang-Mills existence and mass gap
  2. Navier-Stokes existence and smoothness
  3. Birch and Swinnertori-Dyer conjecture


P versus NP Problem

What is P?

This class of problem are easy to solve. We can have algorithm to solve this type of problem within a reasonable amount of time.

e.g. Check whether a particular number exists in a list.
The simplest solution would be "linear search" algorithm, we check each number in turn until we find the right one.

If the list has n numbers- the "size" of the problem- the algorithm takes at most n steps to search it, so its complexity is proportional to n.

Similarly to do things like manual multiplication of two n-digit numbers, which takes about n2 steps.

Any problem of size n whose solution requires n to the power of something (nx) steps is relatively quick to crack. It is said to be solvable in "polynomial time" and is denoted P.

What is NP?

Not all problems are as easy as P problems.

In some cases, as the size of the problem grows, computing time increases not polynomially as nx, but exponentially as Xn - a much steeper increase.

Imagine, for example, an algorithm to list out all possible ways to arrange the numbers from 1 to n.
Even proving a problem belongs to this non-polynomial class can be difficult, because you have hate to show that absolutely no polynomial-time algorithm exists to solve it.

That does not mean we have to give up on hard problems. With some problems that are difficult to solve in a reasonable time, inspired guesswork might still lead you to an answer whose correctness is easy to verify.

Think of a sudoku puzzle. Working out a solution can be difficult, even for a computer, but presented with completed puzzle, it is easy to check that it fulfills the criteria for being a valid answer.

Problems whose solutions are hard to come by but can be verified in polynomial time make up NP class

Solving a sudoku puzzle is an example of classic NP problem. Process such as using formal logic to check software for errors and deciphering the action of gene regulatory networks are also NP problems



What is P=NP?

All problems in the set P are also in the set NP: if you can easily find a solution, you can easily verify it. But is the reverse true? If you can easily verify the solution to a problem, can we also easily solve it- is every problem in the set NP also in P?

Comments

Post a Comment

Popular posts from this blog

If all content (subject matter) are alike, how can we expect innovation?

By
Image
Problems with alike content: 1) Homogenization of skills When a finished product reaches the market, the product development cycle goes through the touch of many divergent skilled peoples. A product can have many components which require different skill sets of different people. For example, Website Development: When you begin to develop a website, you start with designing a prototype of how it will look, which requires the expertise of graphic designers, you need the skill of programmer to code for the website, you need to be a webmaster to host your website. If you look into the depth, there is much more complexity to it. Each website has its own requirements. A prototype can be designed by using different software, such as Inkscape, illustrator and many others. Each software requires a different kind of learning and experience. Similarly, from programmer side, which language you will be using, which framework, based upon your website requirements such as speed of development, scalab
Read more

No blackboard teaching please during Covid-19 shut down

By
Image
Coronavirus has created a major challenge in our education system. Schools are closed for many months, and teachers are finding ways to teach students remotely. But many are hopelessly failing at it, some think that it doesn’t work as there is limited evidence in support of remote learning in case of kids while others are trying to make it work.  Remote learning requires a different set of tools and different ways of handling students, but the first principles of pedagogy remains the same.  Old habits die hard. Many teachers started blackboard teaching through lecturing remotely through the zoom app or other apps like skype.  What is blackboard teaching? Blackboard teaching is when communication is one-sided with little student engagement. The teacher lectures the content and students listen. But there are serious problems with it.  Here are some of the compilation about patterns of bad teaching: Patterns for bad practices of teaching Remember, a well-designed video is many times super
Read more

The Competitive Collaboration Algorithm

By
Image
Competitive Collaboration Algorithm: It's a decentralized network where you compete to collaborate. Edge weight represents difficulty to get connected. Difficulty depends on factors such as distance, location, quality, price. We need to choose subgraph containing all the required nodes (e.g. nodes containing a,b,c,d ) that has a minimum weight or optimal weight. a,b,c,d can represent different services, whereas a1, a2 represents the same services from a different service provider. For example, 'a' can represent a student, 'b' can represent a teacher, 'c' can represent content provider such as a biology textbook and 'd' can represent a classroom or building. Similarly  'b1' represents teacher1, 'b2' represents teacher2, etc. So, For student1 (a1), the optimum subgraph or subgraph with minimum weight containing all the required services are a1,b1,c2, d2 with weight 0.5+2.3+4.2 . Usefulness of the model: 1) Prediction: One can make a pr
Read more