Skip to content

DA7. NP-Problem

Statement

Describe in your own words what a NP complete problem is and why a NP complete program is considered to be ‘hard.’

Include one or two examples to explain your thought process to show what is occurring and how the methodology works. Use APA citations and references for any sources used.

Answer

A decision problem is a problem whose output is a single boolean value: YES or NO. Polynomial time refers to a time complexity of the form O(n^c) for some constant c, where n is the size of the input. Problems are efficient if they can be solved within polynomial time. P problems are those efficient problems that can be solved in polynomial time (Shaffer, 2011).

The issue with solving problems with time complexity that exceeds polynomial time (e.g., O(2^n) or O(n!)) is that they are not efficient; that is, the time required to solve the problem grows in a very fast manner as the size of the problem increases slightly to the point where the solution becomes impossible within the limitations of computational resources.

Verifying a problem solution means that given a solution, it can be checked to determine if it is correct. NP problems are those that could be solved in polynomial time; that is, they are sometimes solvable and sometimes not, but there is no guarantee that they will be. NP problems are non-deterministic problems, meaning they could give different results each time they are run with the same input. NP problems are those that can be verified in polynomial time where the answer is YES (UoPeople, 2025).

NP-hard problems are those that are at least as hard as the hardest problems in NP. They are harder than NP problems; meaning no one has been able to solve them in polynomial time. NP-complete problems are those that are both in NP and NP-Hard; that is, there is no fast solution to them and they may be verifiable or not.

It is important to spot NP-complete problems so that we don’t waste time trying to solve them with algorithms that are not efficient. One approach that is taken to come up with a solution to NP-complete problems is to use techniques of approximation and reduction.

For example, the problem of pairing two lists of integers involves pairing the smallest from the first set with the smallest from the second set, and then next smallest, and so on. The problem is complex on its own, and the brute force solution is of exponential time complexity, hence it is an NP-hard problem. However, giving a possible solution we can check if it is correct in polynomial time, hence it is an NP problem. The problem is NP-complete because it is both in NP and NP-Hard.

The problem of pairing lists can be reduced to a sorting problem; that is, sort each list separately and then start pairing each two elements with the same index. Using a good sorting algorithm with complexity of O(n^2) at max, the problem can be solved efficiently and is now considered a P problem.

Another example is the circuit satisfiability problem is a decision problem that asks what set of specific gates can be connected in a way that the output is 1. The brute force solution to this problem is to try all possible assignments of the inputs, which is O(2^n). The circuit satisfiability problem is NP-hard because it is not solvable within polynomial time. But, given a specific assignment, it easily veryfiable in polynomial time, hence it is an NP problem.

References