WikiGalaxy
NP Complete Problems
Understanding NP-Completeness:
NP-complete problems are a class of decision problems for which no efficient solving algorithm is known. These problems are significant in computational theory as they help us understand the boundaries of what can be computed efficiently.
Example 1: Traveling Salesman Problem (TSP)
Traveling Salesman Problem:
The TSP asks whether a salesman can visit a set of cities, each once, and return to the starting point, within a given distance. This problem is NP-complete because finding the shortest possible route is computationally intensive.
// Pseudo-code for TSP using Dynamic Programming
int tsp(int mask, int pos) {
if (mask == visitedAll) return dist[pos][0];
if (dp[mask][pos] != -1) return dp[mask][pos];
int ans = Integer.MAX_VALUE;
for (int city = 0; city < n; city++) {
if ((mask & (1 << city)) == 0) {
int newAns = dist[pos][city] + tsp(mask | (1 << city), city);
ans = Math.min(ans, newAns);
}
}
return dp[mask][pos] = ans;
}
Example 2: Knapsack Problem
Knapsack Problem:
The Knapsack Problem involves selecting items with given weights and values to maximize value without exceeding a weight limit. It is NP-complete because the number of combinations grows exponentially with the number of items.
// Pseudo-code for 0/1 Knapsack Problem
int knapSack(int W, int wt[], int val[], int n) {
int K[][] = new int[n+1][W+1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i==0 || w==0)
K[i][w] = 0;
else if (wt[i-1] <= w)
K[i][w] = Math.max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
else
K[i][w] = K[i-1][w];
}
}
return K[n][W];
}
Example 3: Boolean Satisfiability Problem (SAT)
Boolean Satisfiability Problem:
SAT is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. It was the first problem proven to be NP-complete, highlighting its foundational role in computational complexity.
// Pseudo-code for SAT Solver using DPLL Algorithm
boolean dpll(Formula formula) {
if (formula.isSatisfied()) return true;
if (formula.hasContradiction()) return false;
Literal literal = formula.chooseLiteral();
return dpll(formula.assign(literal, true)) || dpll(formula.assign(literal, false));
}
Example 4: Hamiltonian Cycle Problem
Hamiltonian Cycle Problem:
The Hamiltonian Cycle problem asks whether a given graph contains a cycle that visits each vertex exactly once. This problem is NP-complete because verifying a solution is easy, but finding one is complex.
// Pseudo-code for Hamiltonian Cycle using Backtracking
boolean hamiltonianCycle(int graph[][], int path[], int pos) {
if (pos == graph.length) return graph[path[pos-1]][path[0]] == 1;
for (int v = 1; v < graph.length; v++) {
if (isSafe(v, graph, path, pos)) {
path[pos] = v;
if (hamiltonianCycle(graph, path, pos+1)) return true;
path[pos] = -1;
}
}
return false;
}
Example 5: Vertex Cover Problem
Vertex Cover Problem:
The Vertex Cover problem involves finding the smallest set of vertices such that each edge in the graph is incident to at least one vertex in the set. It's NP-complete because the problem grows exponentially with the graph size.
// Pseudo-code for Vertex Cover using Approximation Algorithm
Set vertexCover(Graph graph) {
Set cover = new HashSet<>();
while (graph.hasEdges()) {
Edge e = graph.getRandomEdge();
cover.add(e.u);
cover.add(e.v);
graph.removeEdges(e.u);
graph.removeEdges(e.v);
}
return cover;
}
