Most people who are studying or studied computer science have come across the P verse NP problem. It's one of those topics that you are taught in university and will most like promptly forget about when graduation comes around and you start working in the industry. I have honestly not paid much attention to it until recently.

What is P versus NP and why is it important?

The P versus NP problem is an unsolved problem in computer science that tries to determine if an algorithm that can be verified in polynomial time can also be solved in polynomial time.

In this post, I'll give an introduction into P, NP, NP-Hard and NP-Complete and why this is such an important problem. There will also be references to time complexity so I highly recommend reading up on it or checking out the resources I listed in my post Learning Big O notation as a Javascript developer.

P (deterministic polynomial time)

P problems are the set of problems that have been solved and verified in polynomial time (o(n)^k). Examples include linear sort, merge sort, binary search, bubble sort and insertion sort.

Let's take the bubble sort example. The bubble sort algorithm goes through a sortable array of numbers and swaps the adjacent elements if they are in the wrong order.

  const arr = [8, 9, 0, 3, 5, 6, 1]
  const length = arr.length
  let indicator = 1

  for (let i = 0; i < length && indicator == 1; i++) {
    indicator = 0
    for (let j = 0; j < length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j]
        arr[j] = arr[j+1]
        arr[j+1] = temp
        indicator = 1
      }
    }
  }

The above is a variant of the algorithm. The indicator variable will track if any of the elements have been swapped and will also indicate if the array is already sorted. The worst-case scenario is O(n²) if the array is not sorted and O(n) otherwise.

Let's consider another very simple example. We want to calculate the sum of each row in a two-dimensional array and output the sum for each row in an array. We have the algorithm below to do so:

  const arr = [
    [2, 10, 6],
    [1, 0, 9],
    [13, 8, 6],
  ]
  const result = []

  for (let i = 0; i < arr.length; i++) {
    let sum = 0
    for (let j = 0; j < arr[i].length; j++) {
      sum += arr[i][j]
    }
    result.push(sum)
  }

The time complexity of this algorithm is O(n^m) where m is the number of dimensions (2 in this case) and n is the size of each array.

Taking the two examples above, we can easily see that logic used to deduce a solution for the bubble sort can easily be applied to the second problem.

However, there exist a set problems that have only been proven to be solved with an exponential-time algorithm (O(2ⁿ)). These problems are known as NP problems.

Diagram of P ≠ NP (left) and P = NP (right). It is widely believed that P ≠ NP.

NP (non-deterministic polynomial time)

NP problems consist of the set of problems whose solution can be verified in polynomial time but there is no known algorithm that can easily solve them. Examples include 0-1 Knapsack, the traveling salesman, boolean satisfiability problem, and the subset sum problem. P problems were once NP problems proven to be solvable in polynomial time.

NP complexity class of problems can be broken down into three sets: NP, NP-Hard, and NP-Complete.

NP-Hard and NP-Complete

For a problem to belong to the NP set, it has to be a decision problem with solutions of polynomial length.

NP-hardness refers to the set of problems that are at least as hard as the hardest problems in NP. The hardest of these problems are NP-Complete. If you take a look at the diagram above of P ≠ NP, you can see that NP-Hard problems cab be neither NP-Complete nor NP. These problems are difficult or impossible to check if they are decidable (returning a true of false value). An example of an NP is the halting problem. The halting problem tries to verify if given an algorithm, will it halt or continue in an infinite loop. There is no existing algorithm that can prove if a function will halt or run forever.

NP-Complete problems are NP-Hard problems that have been proven to be decidable in polynomial time (NP-Complete is a subset of NP and NP-Hard). A very good is Sudoku. In an NxN grid where N is the number of rows and columns, the number in a cell should be unique for it's row and column. When a Sudoku grid is solved, it's fairly easy to verify the solution:

Here is a quick solution using a nested loop that checks if each row in the grid has a unique value.

  const grid = completeGrid()
  const isSolved = true

  for (let i = grid; i < grid.length; i++) {
    const unique = []

    for (let j = grid; j < grid.length; j++) {
      const cell = grid[i][j]
      
      if (unique.includes(cell)) {
        isSolved = false
        break
      }

      unique.push(cell)
    } 
  }

The time complexity for the alogirithm will alway be O(nⁿ) irrespective of how large the grid is. The question is what is the complexity of the completeGrid function.

This is different when we want to write an algorithm that can solve an NxN sudoku grid where N can be a very large number.

Why is the P versus NP problem important?

If it can be proven to solve just one problem in NP-Complete polynomial time, all NP problems become P problems. That means that problems that we taught were initially hard will become very easy to solve. This will open to a vast improvement and milestones in technology such as in the field of medicine where we can easily find cures to complex diseases and even cancer. However, it would pose a significant negative impact on crytopgraphy, which depends on algorithms that are NP-hard.

Resources

• Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
• P vs. NP and the Computational Complexity Zoo (Youtube video)
• NP-Hard and NP-Complete Problems (Youtube video)
• Explained: P vs. NP