The NP vs P issue


Question mark on a blackboard

By McDonald, T. | Last updated: 7/9/2017

We face problems every day; subsequently, we spend a lot of time attempting to find a reasonable solution even if we do not realise it.  Solving problems is a big part of computer science.  In fact, problems are so important that computer science separates them into different classes including P, NP, NP-complete and NP-hard, but what does it all mean and can NP =P?

Computer scientists have developed a way of measuring how long it takes to compute a problem. This is not as easy as it sounds since we cannot just time how long it takes.  Think about it for a minute, if timing an algorithm by looking at the clock, the timing run on different computers would be different each time because different computers could have different hardware such as processors and memory.  Even if running the same algorithm several times on the same computer, the time spent running the algorithm would depend on the other operations the computer was running at the time. Consequently, computer science needed some other way to time an algorithm.  Big O is a way of stating an algorithms complexity or performance so it can be compared to other algorithms for large data sets.  It works by counting all the steps in an algorithm such as assignments and loops.  An assignment obviously counts as one step, but loops are different because each loop will run n number of steps and a nested loop will run n times n number of steps. For instance, if we have an algorithm with four assignments and two separate loops, the algorithm’s complexity will have a big O of 4+n+n or 2n+4. We shorten this to (O)n because the assignments and the coefficient will not count for much with huge inputs.  If we have an algorithm with three assignments and one nested for loop, one loop inside the other, the complexity will be 3+n^2, which gives (O)n^2 since only the higher degree of the polynomial is important.  Furthermore, other algorithms may have logarithmic, linear, log linear, quadratic, cubic, exponential or some other complexity.   This gives programmers a way of comparing algorithms and their performance when using huge inputs.  Polynomial timing is what we call this kind of measuring.

The classes of NP, non-deterministic polynomial time, problems depend on the algorithms complexity.  The higher the complexity the harder the problem is to solve in terms of polynomial time.  P, polynomial time, is a subset of NP and these problems will compute in polynomial time and will check in polynomial time.  NP problems will solve in polynomial time, but may not check in polynomial time.  In addition, there is NP-complete, which are at the hard end of NP problems, they have a higher complexity and at the higher-level still of complexity are the NP-Hard problems.  Some people have speculated that solving NP-complete and NP problems in polynomial time may be possible in the future; however, this looks more and more unlikely since some problems will always have very high complexity; thus, we will never be able to move NP-complete and NP into the P subset.  Nowadays, almost everyone believes some NP problems will never equal P problems. Therefore, NP= P is out!

In conclusion, an algorithms performance is measured in complexity, its big O and different complexities will place a problem in either P, NP, NP-complete or NP-hard classes. NP = P is never likely to happen although some NP or NP-complete problems my find their way into the P subset.

Comments

  1. Hello, all the time i used to check web site
    posts here in the early hours in the daylight,
    for thhe reason that i love to learn more and more.

    ReplyDelete

Post a Comment

Popular Posts