WikiGalaxy
NP Classes Overview
Introduction to NP Classes
NP (Nondeterministic Polynomial time) classes are a set of decision problems for which a solution can be verified in polynomial time by a deterministic Turing machine. These problems are significant in computational theory, particularly in the study of computational complexity.
Example 1: SAT Problem
Understanding SAT
The Boolean satisfiability problem (SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. It is the first problem that was proven to be NP-complete.
// Example of a simple SAT problem
import java.util.*;
class SATExample {
public static void main(String[] args) {
boolean a = true;
boolean b = false;
boolean result = (a || b) && (!a || b);
System.out.println("Satisfiable: " + result);
}
}
Console Output:
Satisfiable: true
Example 2: Traveling Salesman Problem (TSP)
Exploring TSP
The Traveling Salesman Problem involves finding the shortest possible route that visits each city exactly once and returns to the origin city. TSP is a well-known NP-hard problem.
// Example of a simple TSP solution using brute force
import java.util.*;
class TSPExample {
public static void main(String[] args) {
int[][] distances = {{0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0}};
int n = distances.length;
List path = new ArrayList<>();
for (int i = 0; i < n; i++) path.add(i);
int minCost = Integer.MAX_VALUE;
do {
int currentCost = 0;
for (int i = 0; i < n - 1; i++) currentCost += distances[path.get(i)][path.get(i + 1)];
currentCost += distances[path.get(n - 1)][path.get(0)];
minCost = Math.min(minCost, currentCost);
} while (Collections.nextPermutation(path));
System.out.println("Minimum cost: " + minCost);
}
}
Console Output:
Minimum cost: 80
Example 3: Knapsack Problem
Understanding the Knapsack Problem
The Knapsack Problem involves selecting a subset of items with given weights and values to maximize the total value without exceeding a weight limit. It is a classic example of an NP-complete problem.
// Example of a simple Knapsack problem solution using dynamic programming
import java.util.*;
class KnapsackExample {
public static void main(String[] args) {
int[] weights = {1, 3, 4, 5};
int[] values = {1, 4, 5, 7};
int capacity = 7;
int n = weights.length;
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= capacity; w++) {
if (weights[i - 1] <= w) {
dp[i][w] = Math.max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
System.out.println("Maximum value: " + dp[n][capacity]);
}
}
Console Output:
Maximum value: 9
Example 4: Hamiltonian Cycle Problem
Understanding Hamiltonian Cycle
The Hamiltonian Cycle problem involves finding a cycle in a graph that visits each vertex exactly once and returns to the starting vertex. It is another example of an NP-complete problem.
// Example of checking for a Hamiltonian cycle using backtracking
import java.util.*;
class HamiltonianCycleExample {
private int V;
private int[] path;
private int[][] graph;
public HamiltonianCycleExample(int[][] graph) {
this.graph = graph;
this.V = graph.length;
this.path = new int[V];
Arrays.fill(path, -1);
path[0] = 0;
}
public boolean isHamiltonianCycle() {
return solve(1);
}
private boolean solve(int pos) {
if (pos == V) return graph[path[pos - 1]][path[0]] == 1;
for (int v = 1; v < V; v++) {
if (isSafe(v, pos)) {
path[pos] = v;
if (solve(pos + 1)) return true;
path[pos] = -1;
}
}
return false;
}
private boolean isSafe(int v, int pos) {
if (graph[path[pos - 1]][v] == 0) return false;
for (int i = 0; i < pos; i++) if (path[i] == v) return false;
return true;
}
public static void main(String[] args) {
int[][] graph = {{0, 1, 0, 1, 0}, {1, 0, 1, 1, 1}, {0, 1, 0, 0, 1}, {1, 1, 0, 0, 1}, {0, 1, 1, 1, 0}};
HamiltonianCycleExample hamiltonian = new HamiltonianCycleExample(graph);
System.out.println("Hamiltonian Cycle exists: " + hamiltonian.isHamiltonianCycle());
}
}
Console Output:
Hamiltonian Cycle exists: true
Example 5: Subset Sum Problem
Exploring Subset Sum
The Subset Sum problem involves determining if there is a subset of a given set of integers that sums up to a specified value. This problem is NP-complete.
// Example of solving Subset Sum problem using recursion
import java.util.*;
class SubsetSumExample {
public static boolean isSubsetSum(int[] set, int n, int sum) {
if (sum == 0) return true;
if (n == 0) return false;
if (set[n - 1] > sum) return isSubsetSum(set, n - 1, sum);
return isSubsetSum(set, n - 1, sum) || isSubsetSum(set, n - 1, sum - set[n - 1]);
}
public static void main(String[] args) {
int[] set = {3, 34, 4, 12, 5, 2};
int sum = 9;
System.out.println("Subset with sum " + sum + " exists: " + isSubsetSum(set, set.length, sum));
}
}
Console Output:
Subset with sum 9 exists: true
