🔍 What are NP Problems?

NP stands for Nondeterministic Polynomial time.

âś… Definition:

A problem is in NP if:

  • Given a candidate solution, we can verify its correctness in polynomial time.

This doesn’t mean we can find the solution quickly, only that we can check one quickly.

🧠 Think of it this way:

  • P problems: You can solve them quickly (in polynomial time).
  • NP problems: You may not be able to solve them quickly, but if someone gives you a solution, you can check if it’s correct quickly.

📦 Example: Subset Sum

Given a set of numbers and a target sum, does any subset add up to the target?

  • Hard to solve: You might need to try many combinations.
  • Easy to verify: If someone gives you a subset, you can add the numbers and check the sum.

So, Subset Sum is in NP.

🕵️ Why “Nondeterministic”?

Imagine a computer that can “magically guess” the right answer (nondeterminism). If there exists a correct solution, it can guess it and verify it quickly.

In theory:

  • An NP machine guesses a solution.
  • Then verifies it in polynomial time.

Summary:

Term Meaning
P Problems solvable in polynomial time
NP Problems verifiable in polynomial time
NP-Complete Hardest problems in NP; if you solve one quickly, you solve all NP problems quickly

âś… What is an NP-Complete Problem?

An NP-Complete (NPC) problem satisfies two key conditions:

  1. Belongs to NP: The problem can be verified in polynomial time. That is, if someone gives you a candidate solution, you can check whether it’s correct efficiently (in polynomial time).

  2. NP-Hard: Every problem in NP can be reduced to it in polynomial time. This means if we can solve this problem efficiently, we can solve all NP problems efficiently.

In essence, NP-Complete problems are the “hardest” problems in NP. If any NP-Complete problem can be solved in polynomial time, then P = NP.

🧭 Why the Traveling Salesman Problem (TSP - Decision Version) is NP-Complete

Let’s look at the decision version of TSP (not the optimization one):

Given a complete graph with distances and a number k, is there a tour that visits each city once, returns to the start, and has total distance ≤ k?

1. It’s in NP

If someone gives you a proposed tour (sequence of cities), you can:

  • Check if all cities are visited exactly once
  • Verify if the total distance is ≤ k All of this can be done in polynomial time ⇒ in NP.

2. It’s NP-Hard

We can reduce other known NP-Complete problems to TSP. One common approach:

  • Reduce Hamiltonian Cycle (which is NP-Complete) to TSP.
  • Construct a graph where the TSP tour corresponds to a Hamiltonian cycle with edge weights set cleverly (e.g., 1 for original edges, a large number for non-edges).

Thus, since:

  • TSP (Decision) is in NP
  • Hamiltonian Cycle ≤p TSP ⇒ TSP (Decision) is NP-Complete

Here are some interesting NP-Complete problems that are accessible and relevant to computer engineers:

  1. Traveling Salesman Problem (Decision Version) Given a list of cities and distances between each pair, is there a route shorter than a given value that visits each city exactly once and returns to the start?

  2. Knapsack Problem (0/1 version) Given a set of items, each with a weight and a value, can you select a subset of items that fit within a given weight limit and reach at least a certain total value?

  3. Boolean Satisfiability Problem (SAT) Given a Boolean formula, is there an assignment of true/false values to variables that makes the formula true?

  4. Graph Coloring (k-coloring) Can the nodes of a graph be colored using at most k colors such that no two adjacent nodes have the same color?

  5. Vertex Cover Given a graph and a number k, is there a set of k or fewer vertices such that every edge in the graph has at least one endpoint in that set?

  6. Subset Sum Given a set of integers, is there a subset whose sum equals a target number?

  7. Job Scheduling (with deadlines and profits) Given a set of jobs with deadlines and profits, can you select a subset to schedule so that you don’t miss deadlines and maximize total profit?

  8. Hamiltonian Cycle Does a given graph contain a cycle that visits every vertex exactly once and returns to the starting point?

  9. 3-Partition Problem Can a multiset of integers be partitioned into triples that all sum to the same value?

  10. Bin Packing Given items of different sizes and a fixed bin size, can you pack all items using at most a certain number of bins?