Subset Sum Problem using Backtracking

The Backtracking approach for solving the Subset Sum Problem systematically explores all subsets of
a given set to find if any subset sums to the target value. If a solution is not valid at any point, the
algorithm "backtracks" by undoing the last step and exploring other possibilities.

Process

1. Start from the first element of the set.

2. Two choices at each step:

o Include the current element in the subset and reduce the target sum by its value.

o Exclude the current element and move to the next.

3. Base Cases:

o If the target becomes 000: A subset is found, return true.

o If the target is non-zero but no elements are left: Return false.

Algorithm

1. Input: A set SSS, target sum TTT, current index iii.

2. Recursively explore both possibilities (include or exclude the element at index iii).

3. If a valid subset is found during recursion, return true.

4. Backtrack by undoing the inclusion of the current element if it does not lead to a solution.

Pseudo-code

plaintext

Copy code

subsetSumBacktracking(S, n, T):

if T == 0:

return true // Subset found

if n == 0 or T < 0:

return false // No subset found

// Include the current element in the subset

if subsetSumBacktracking(S, n-1, T - S[n-1]):

return true
 // Exclude the current element from the subset

return subsetSumBacktracking(S, n-1, T)

Time Complexity

 Worst Case: O(2n)

o Each element has two choices: to be included or excluded.

 Space Complexity: O(n)

o Due to the recursion stack.

Example

Problem Statement:

Set S={3,34,4,12,5,2}S = \{3, 34, 4, 12, 5, 2\}S={3,34,4,12,5,2}, Target T=9

Backtracking Steps:

Current Set Target Include S[i]S[i]S[i]? Remaining Target Status

{3, 34, 4, 12, 5, 2} 9 Yes 6 Continue

{34, 4, 12, 5, 2} 6 No 6 Continue

{4, 12, 5, 2} 6 Yes 2 Continue

{12, 5, 2} 2 No 2 Continue

{5, 2} 2 Yes -3 (invalid) Backtrack

{5, 2} 2 No 2 Continue

{2} 2 Yes 0 Success

Real-Life Applications

1. Resource Allocation: Allocate tasks or items to meet a specific resource constraint.

2. Finance: Selecting a subset of investments to achieve a target value.

3. Cryptography: Forming hard-to-solve knapsack problems for secure encryption.

4. Gaming: Choosing subsets of tools or powers to meet specific game objectives.

5. Example
Input:
Set S={3,34,4,12,5,2}S = \{3, 34, 4, 12, 5, 2\}S={3,34,4,12,5,2},
 Target T=9

Output: Yes (because {4,5}\{4, 5\}{4,5} is a subset that sums to 9).

6. Dynamic Programming Table:

Element ↓ \ Target → 0 1 2 3 4 5 6 7 8 9
{} true false false false false false false false false false
{3} true false false true false false false false false false
{3, 34} true false false true false false false false false false
{3, 34, 4} true false false true true false false true false false
{3, 34, 4, 12} true false false true true false false true false false
{3, 34, 4, 12, 5} true false false true true true false true true true
{3, 34, 4, 12, 5, 2} true false true true true true true true true true

7. Result: dp[6][9]=true

Why is it Used?

The Subset Sum Problem has practical and theoretical significance:

1. Practical Applications:

o Resource allocation problems where resources must be combined to meet a specific

requirement.

o Financial portfolio management to achieve a target value.

o Cryptographic systems, particularly in knapsack-based cryptography.

o Decision-making in fields like operations research and logistics.

2. Theoretical Importance:

o It is a foundational problem in computer science and mathematics.

o It is a special case of the 0/1 Knapsack Problem.

o Subset Sum is a NP-complete problem, which means solving it efficiently for large
inputs is unlikely unless P=NPP = NPP=NP.

Process of Solving Subset Sum

Approaches:

1. Recursive Solution:

o Use a recursive function to explore all subsets of the given set.

o For each element, decide whether to include it in the subset or not.

o Base Cases:
  If T=0T = 0T=0, return true (we've found a subset that sums to TTT).

 If n=0n = 0n=0 and T>0T > 0T>0, return false (no more elements to include).

Pseudo-code:

plaintext

Copy code

isSubsetSum(S, n, T):

if T == 0:

return true

if n == 0:

return false

if S[n-1] > T:

return isSubsetSum(S, n-1, T)

return isSubsetSum(S, n-1, T) OR isSubsetSum(S, n-1, T - S[n-1])

2. Dynamic Programming Solution:

o Solve the problem using a bottom-up approach to avoid redundant calculations

(overlapping subproblems).

o Use a 2D array dp[i][j] where:

 dp[i][j]dp[i][j]dp[i][j] = true if there exists a subset of the first iii items that
sums to jjj, otherwise false.

Steps:

o Initialize dp[0][0]=truedp[0][0] = truedp[0][0]=true (sum T=0T = 0T=0 is possible with

an empty set).

o Fill the table for all subsets and sums incrementally.

o Result will be stored in dp[n][T]dp[n][T]dp[n][T].

Pseudo-code:

plaintext

Copy code

isSubsetSum(S, n, T):

Create a dp[n+1][T+1]

Initialize dp[i][0] = true for all i

Initialize dp[0][j] = false for all j > 0

 for i = 1 to n:

for j = 1 to T:

if S[i-1] > j:

dp[i][j] = dp[i-1][j]

else:

dp[i][j] = dp[i-1][j] OR dp[i-1][j - S[i-1]]

return dp[n][T]

Time Complexity

1. Recursive Approach:

o Time Complexity: O(2n)O(2^n)O(2n) (since every element has two choices: include
or exclude).

o Space Complexity: O(n)O(n)O(n) (for the recursion stack).

2. Dynamic Programming Approach:

o Time Complexity: O(n×T)O(n \times T)O(n×T), where nnn is the size of the set and
TTT is the target sum.

o Space Complexity: O(n×T)O(n \times T)O(n×T).

Hamiltonian Circuit Problem

What is the Hamiltonian Circuit Problem?

The Hamiltonian Circuit Problem is a classic graph theory problem that asks:

"Is there a cycle (closed loop) in a graph that visits every vertex exactly once?"

Formal Definition:

 Graph: A set of vertices VVV and edges EEE.

 Hamiltonian Circuit: A cycle that visits every vertex in VVV exactly once and returns to the
starting vertex.
Difference from Eulerian Circuit:

 Hamiltonian Circuit focuses on visiting all vertices exactly once.

 Eulerian Circuit focuses on traversing all edges exactly once.

Why is it Used?

1. Practical Applications:

o Route optimization (e.g., logistics, delivery routes, or travel planning).

o Network topology design (e.g., circuit design, communication networks).

o Problems related to scheduling or sequencing tasks.

2. Theoretical Importance:

o It is a foundational problem in graph theory and combinatorics.

o The Hamiltonian Circuit Problem is NP-complete, meaning it is computationally hard

to solve for large graphs.

Process of Solving the Hamiltonian Circuit Problem

Backtracking Approach:

Backtracking is one of the simplest methods to solve the Hamiltonian Circuit problem. It
systematically explores all possible vertex sequences to find a valid Hamiltonian Circuit.

Steps:

1. Start at an arbitrary vertex v1v_1v1.

2. Recursively try to build a path by visiting unvisited vertices:

o Include a vertex in the path if:

 It is adjacent to the current vertex.

 It has not been visited yet.

o Backtrack if the inclusion violates constraints.

3. If all vertices are visited and there is an edge back to the starting vertex, the Hamiltonian
Circuit is found.

4. If no circuit is found after exploring all possibilities, return false.

Pseudo-code

plaintext

Copy code

hamiltonianCircuit(graph, path, pos):

if pos == len(graph): // All vertices visited

if path[0] is adjacent to path[pos-1]:

return true // Hamiltonian Circuit found

else:

return false // No valid circuit

for vertex in graph:

if isValid(vertex, graph, path, pos): // Check constraints

path[pos] = vertex

if hamiltonianCircuit(graph, path, pos + 1):

return true

path[pos] = -1 // Backtrack

return false

isValid(vertex, graph, path, pos):

if vertex is not adjacent to path[pos-1]:

return false

if vertex is already in path:

return false

return true

Time Complexity

 Worst Case: O(N!)O(N!)O(N!), where NNN is the number of vertices.

o Since there are N!N!N! permutations of vertices to check.

 Space Complexity: O(N)O(N)O(N), due to recursion stack and path array

 Example
  Problem Statement:
 Graph GGG:
Vertices: {A,B,C,D}\{A, B, C, D\}{A,B,C,D}.
Edges: {(A,B),(A,C),(B,C),(C,D),(D,A)}\{(A, B), (A, C), (B, C), (C, D), (D, A)\}
{(A,B),(A,C),(B,C),(C,D),(D,A)}.
 Step-by-Step Backtracking:

Step Path So Far Action Status

1 [A] Start at A Continue
2 [A, B] Move to B Continue
3 [A, B, C] Move to C Continue
4 [A, B, C, D] Move to D Check
5 [A, B, C, D, A] Back to A, Circuit Found! Success

Applications of Hamiltonian Circuits

1. Traveling Salesman Problem (TSP): Finding the shortest Hamiltonian Circuit.

2. Routing Problems: Optimizing delivery or transportation networks.

3. Game Design: Creating puzzles like the Knight’s Tour in chess.

4. Biology: Modeling circular DNA structures or protein folding paths.

N-Queens Problem via Backtracking

What is the N-Queens Problem?

The N-Queens Problem is a classic combinatorial problem where you must place NNN queens on an
N×NN \times NN×N chessboard such that:

1. No two queens attack each other.

o Queens can attack any other queen in the same row, column, or diagonal.
Why is it Used?

1. Theoretical Importance:

o A classic example of constraint satisfaction problems.

o Demonstrates the use of backtracking to find solutions.

2. Applications:

o Robotics and AI: Solving constraint satisfaction problems.

o Game design and simulations.

Approach: Backtracking

We attempt to place one queen per row, checking if the placement is valid:

1. Valid placement criteria:

o No queen exists in the same column.

o No queen exists on the left or right diagonal.

2. Backtracking:

o If a row cannot be completed, backtrack to the previous row and try the next
column.

Steps in Backtracking

1. Start with an empty chessboard.

 Place a queen in the first column of the first row.

2. Move to the next row.

 Try placing a queen in each column of the row.

 If a valid placement is found, place the queen and move to the next row.

 If no valid placement exists, backtrack to the previous row and try the next column.

3. Repeat until all queens are placed.

 If all queens are placed, print the solution.

 If no solution exists for a placement, backtrack.

Pseudo-Code

plaintext
Copy code

placeQueens(row, board, n):

if row == n: // Base case: all queens placed

print board

return

for col in range(n): // Try each column in the current row

if isValid(row, col, board, n): // Check constraints

board[row][col] = 1 // Place the queen

placeQueens(row + 1, board, n) // Recur to place the next queen

board[row][col] = 0 // Backtrack if needed

isValid(row, col, board, n):

for i in range(row): // Check column

if board[i][col] == 1:

return False

for i, j in upperLeftDiagonal(row, col): // Check left diagonal

if board[i][j] == 1:

return False

for i, j in upperRightDiagonal(row, col): // Check right diagonal

if board[i][j] == 1:

return False

return True

Python Implementation

python

Copy code

def is_valid(board, row, col, n):

# Check for a queen in the same column

for i in range(row):

if board[i][col] == 1:
 return False

# Check for a queen in the left diagonal

i, j = row, col

while i >= 0 and j >= 0:

if board[i][j] == 1:

return False

i -= 1

j -= 1

# Check for a queen in the right diagonal

i, j = row, col

while i >= 0 and j < n:

if board[i][j] == 1:

return False

i -= 1

j += 1

return True

def solve_n_queens(board, row, n):

# Base case: If all queens are placed, print the solution

if row == n:

for line in board:

print(line)

print()

return

# Try placing the queen in all columns of the current row

for col in range(n):

if is_valid(board, row, col, n):

 board[row][col] = 1 # Place the queen

solve_n_queens(board, row + 1, n) # Recur for the next row

board[row][col] = 0 # Backtrack

# Initialize board and solve

def n_queens(n):

board = [[0] * n for _ in range(n)]

solve_n_queens(board, 0, n)

# Example: Solve for 4-Queens

n_queens(4)

Output

For N=4N = 4N=4, the solutions are:

csharp

Copy code

[0, 0, 1, 0]

[1, 0, 0, 0]

[0, 0, 0, 1]

[0, 1, 0, 0]

[0, 1, 0, 0]

[0, 0, 0, 1]

[1, 0, 0, 0]

[0, 0, 1, 0]

Visualization of Backtracking for 4-Queens

1. Start with the board:

csharp

Copy code

[0, 0, 0, 0]
[0, 0, 0, 0]

[0, 0, 0, 0]

[0, 0, 0, 0]

2. Place queen in the first row:

csharp

Copy code

[1, 0, 0, 0]

[0, 0, 0, 0]

[0, 0, 0, 0]

[0, 0, 0, 0]

3. Move to the second row. Try placing a queen in each column:

o (2,1)(2, 1)(2,1): Invalid (same column as row 1).

o (2,2)(2, 2)(2,2): Invalid (same diagonal as row 1).

o (2,3)(2, 3)(2,3): Valid.

csharp

Copy code

[1, 0, 0, 0]

[0, 0, 1, 0]

[0, 0, 0, 0]

[0, 0, 0, 0]

4. Repeat the process for the next rows, backtracking when no valid placement exists.

Time Complexity

1. Worst Case: O(N!)O(N!)O(N!), as there are N!N!N! possible ways to place NNN queens.

2. Space Complexity: O(N2)O(N^2)O(N2), for the chessboard representation.

What is the Travelling Salesman Problem?

The Travelling Salesman Problem (TSP) is a classic optimization problem where:

1. A salesman must visit all cities exactly once and return to the starting city.

2. The goal is to minimize the total distance (or cost) of travel.

It is an NP-hard problem, meaning there is no efficient algorithm to solve it for all cases, and solving
it becomes increasingly difficult as the number of cities grows.

Why is TSP Used?

1. Logistics and Routing:

o Optimizing delivery routes for trucks, drones, or couriers.

2. Manufacturing:

o Sequencing drilling or cutting operations in factories.

3. Network Design:

o Planning efficient layouts for circuits, wiring, or data networks.

Backtracking Approach to Solve TSP

Backtracking is one way to solve TSP, but it is not efficient for large inputs. The idea is to:

1. Explore all possible permutations of the cities.

2. Calculate the cost of visiting them in a specific order.

3. Track the minimum cost path.

Steps for Backtracking in TSP

1. Start at the first city:

o Mark it as visited.

2. Try all possible next cities:

o Choose a city not yet visited.

o Add the cost of traveling to this city.

o Recur to find the next city.

3. Terminate when all cities are visited:

o Add the cost of returning to the starting city.

4. Backtrack:

o Undo the current choice and try another city.

Pseudo-Code

plaintext
Copy code

tsp(graph, visited, currentCity, n, count, cost, minCost):

if count == n and graph[currentCity][0] > 0: // All cities visited

minCost = min(minCost, cost + graph[currentCity][0])

return minCost

for nextCity in range(n):

if not visited[nextCity] and graph[currentCity][nextCity] > 0:

visited[nextCity] = True

minCost = tsp(graph, visited, nextCity, n, count + 1, cost + graph[currentCity][nextCity],

minCost)

visited[nextCity] = False // Backtrack

return minCost

Python Implementation

python

Copy code

import sys

def tsp(graph, visited, currentCity, n, count, cost, minCost):

# Base case: All cities visited, return to the starting city

if count == n and graph[currentCity][0] > 0:

return min(minCost, cost + graph[currentCity][0])

# Explore all possible cities

for nextCity in range(n):

if not visited[nextCity] and graph[currentCity][nextCity] > 0:

# Mark the city as visited

visited[nextCity] = True

# Recur for the next city

 minCost = tsp(graph, visited, nextCity, n, count + 1, cost + graph[currentCity][nextCity],
minCost)

# Backtrack: Unmark the city

visited[nextCity] = False

return minCost

def solve_tsp(graph):

n = len(graph)

visited = [False] * n

visited[0] = True # Start at city 0

minCost = sys.maxsize

return tsp(graph, visited, 0, n, 1, 0, minCost)

# Example graph (adjacency matrix)

graph = [

[0, 10, 15, 20],

[10, 0, 35, 25],

[15, 35, 0, 30],

[20, 25, 30, 0]

# Solve TSP

result = solve_tsp(graph)

print("Minimum cost to visit all cities:", result)

Input Example

Graph (adjacency matrix):

A B C D

A 0 10 15 20

B 10 0 35 25
 A B C D

C 15 35 0 30

D 20 25 30 0

Output

css

Copy code

Minimum cost to visit all cities: 80

Visualization of the Backtracking Process

1. Start at City A.

2. Explore paths:

o A→B→C→D→Ato B to C to D to AA→B→C→D→A: Cost = 10+35+30+20=9510 + 35 +

30 + 20 = 9510+35+30+20=95

o A→B→D→C→AA \to B to D to C to AA→B→D→C→A: Cost = 10+25+30+15=8010 +

25 + 30 + 15 = 8010+25+30+15=80

o ...

3. Track the minimum cost.

Time Complexity

1. Worst Case: O(n!)

o All permutations of nnn cities are explored.

2. Space Complexity: O(n)O(n)O(n)

o For the recursion stack and visited array.

Optimized Approaches

1. Dynamic Programming (Held-Karp Algorithm):

o Reduces time complexity to O(n2⋅2n)

o Uses bitmasking to represent visited cities.

2. Heuristic Algorithms:

o Greedy or Nearest Neighbor: Finds approximate solutions efficiently.

 o Genetic Algorithms and Simulated Annealing: For large-scale problems

Reducibility, NP-Completeness, NP-Hard, and Problem Classification

1. Reducibility

What is Reducibility?

 Reducibility is a concept where one problem can be transformed into another problem.

 If problem AAA can be reduced to problem BBB, solving BBB automatically solves AAA.

Why is it Important?

 It is used to classify the complexity of problems.

 Helps prove that a problem is NP-complete.

How Does it Work?

 A problem AAA is polynomial-time reducible to a problem BBB (denoted as A≤pBA \leq_p

BA≤pB) if:

1. There exists a polynomial-time algorithm to transform any instance of AAA into BBB.

2. A solution to BBB can be used to solve AAA.

Example:

 Reducing the 3SAT problem to the Clique problem to prove that the Clique problem is NP-
complete.

2. NP-Completeness

What is NP-Completeness?

 NP-Complete problems are the hardest problems in the class NP.

 They satisfy two conditions:

1. Belong to NP: A solution can be verified in polynomial time.

2. NP-Hard: Every problem in NP can be reduced to it in polynomial time.

Why is it Important?

 If any NP-complete problem is solved in polynomial time, then P=NPP = NPP=NP, meaning all
NP problems can be solved efficiently.

Steps to Prove NP-Completeness:

1. Show the problem belongs to NP.

2. Reduce a known NP-complete problem to the given problem in polynomial time.

Examples of NP-Complete Problems:

 SAT (Satisfiability): Is there a truth assignment that satisfies a boolean formula?

 3SAT: A special case of SAT where each clause has exactly 3 literals.

 Vertex Cover: Finding a minimum set of vertices that cover all edges in a graph.

3. NP-Hard

What is NP-Hard?

 Problems that are at least as hard as the hardest problems in NP.

 NP-Hard problems do not need to be in NP (i.e., their solutions may not be verifiable in
polynomial time).

Difference Between NP-Complete and NP-Hard:

 NP-Complete: Problems are both in NP and NP-Hard.

 NP-Hard: Problems may or may not belong to NP.

Examples:

 Halting Problem: Undecidable problem, not in NP but NP-Hard.

 Travelling Salesman Problem (TSP): Finding the shortest route that visits all cities.

4. Problem Classification: P, NP, NP-Complete, and NP-Hard

Class Definition Example Problems

P Solvable in polynomial time. Sorting, Binary Search

NP Verifiable in polynomial time. Subset-Sum, SAT

NP-Complete Hardest problems in NP; both in NP and NP-Hard. SAT, 3SAT, Vertex Cover

NP-Hard As hard as NP-Complete, but not necessarily in NP. TSP, Halting Problem

5. Circuit Satisfiability Problem

What is Circuit Satisfiability?

 Given a boolean circuit with AND, OR, and NOT gates, determine if there is an input that
makes the circuit output true.

Why is it Important?

 It was the first problem proved to be NP-complete (Cook’s Theorem).

How Does it Work?

 1. Represent the circuit as a graph.

2. Check if there exists a truth assignment that satisfies the circuit.

Complexity:

 NP-complete.

Use Case:

 Circuit design and testing in electrical engineering.

6. 3SAT Problem

What is 3SAT?

 A specific version of the SAT problem where each clause has exactly 3 literals.

Why is it Important?

 Used to prove that other problems are NP-complete (reduction).

Example:

 Formula: (A∨¬B∨C)∧(¬A∨B∨D)(A \lor \neg B \lor C) \land (\neg A \lor B \lor D)

(A∨¬B∨C)∧(¬A∨B∨D).

 Check if there is a truth assignment that satisfies this formula.

Complexity:

 NP-complete.

Use Case:

 AI for decision-making and logic circuit design.

7. Vertex Cover Problem

What is Vertex Cover?

 A set of vertices in a graph such that every edge is incident to at least one vertex in the set.

Why is it Important?

 Useful in network security and resource allocation.

Example:

 Graph: A−B,A−C,B−DA-B, A-C, B-DA−B,A−C,B−D.

 Vertex cover: {A,B}\{A, B\}{A,B} (covers all edges).

Complexity:

 NP-complete.
8. Clique Problem

What is a Clique?

 A subset of vertices in a graph where every two vertices are connected.

Why is it Important?

 Relevant in social network analysis and bioinformatics.

Example:

 Graph: A−B,B−C,C−A,D−EA-B, B-C, C-A, D-EA−B,B−C,C−A,D−E.

 Clique: {A,B,C}\{A, B, C\}{A,B,C} (fully connected).

Complexity:

 NP-complete.

9. Cook's Theorem

What is Cook’s Theorem?

 States that the SAT problem is NP-complete.

Why is it Important?

 It was the first theorem to prove the existence of NP-complete problems, establishing the
foundation of complexity theory.

Proof Outline:

1. Show that SAT is in NP.

2. Reduce any problem in NP to SAT.

Use Case:

 Basis for reductions and NP-completeness proofs.

Complexity Comparison of Problems

Problem Class Complexity

Circuit Satisfiability NP-complete O(2n)O(2^n)O(2n)

3SAT NP-complete O(2n)O(2^n)O(2n)

Vertex Cover NP-complete O(2n)O(2^n)O(2n)

Clique NP-complete O(2n)O(2^n)O(2n)

Algorithmic Approach for NP-Complete Problems

1. Backtracking:

o Explore all possible solutions exhaustively.

o Example: Solving 3SAT or Vertex Cover.

2. Branch and Bound:

o Prune unnecessary branches to optimize search.

o Example: TSP.

3. Heuristics and Approximation:

o Provide near-optimal solutions in reasonable time.

o Example: Greedy algorithm for Vertex Cover.

4. Reduction:

o Transform the problem into a known solvable problem.

Introduction to Computability, Polynomial-time Verification, and NP-Completeness

Introduction to Computability

What is Computability?

 Computability is a branch of theoretical computer science that deals with whether a

problem can be solved by a computational model, such as a Turing Machine.

 A problem is computable if there exists an algorithm that can provide a solution in a finite
number of steps.

Key Concepts in Computability:

1. Decidability:

o A problem is decidable if an algorithm exists that provides a "yes" or "no" answer for
every possible input in a finite time.

o Example: Checking if a number is prime.

2. Undecidability:

o A problem is undecidable if no algorithm can solve it for all possible inputs.

o Example: The Halting Problem, which determines if a program will halt or run
forever.

3. Reduction:

o A method used to prove the undecidability of problems by transforming one

problem into another.

Why Study Computability?

  It helps us understand the limits of what can be solved using computers.

 Allows the classification of problems into decidable and undecidable categories.

Polynomial-time Verification

What is Polynomial-time Verification?

 A problem is said to have polynomial-time verification if:

1. A solution (certificate) to the problem can be verified in polynomial time.

2. Verification involves checking whether the provided solution satisfies the problem's
constraints.

Example:

 Problem: Is there a subset of numbers from a given set that sums to SSS?

 Given a solution (subset), verifying whether it sums to SSS can be done in polynomial time.

Why is Polynomial-time Verification Important?

 It allows us to classify problems into complexity classes, particularly NP (nondeterministic

polynomial time).

Classes of Problems:

1. P (Polynomial Time):

o Problems that can be solved in polynomial time.

o Example: Sorting a list.

2. NP (Nondeterministic Polynomial Time):

o Problems for which a solution can be verified in polynomial time.

o Example: Subset-Sum Problem.

NP-Completeness

What is NP-Completeness?

 A problem is NP-complete if:

1. It is in NP (its solution can be verified in polynomial time).

2. Every other problem in NP can be reduced to it in polynomial time.

Importance of NP-Complete Problems:

 They represent the hardest problems in NP.

 If any NP-complete problem can be solved in polynomial time, then all NP problems can also
be solved in polynomial time (i.e., P=NPP = NPP=NP).
Key Properties of NP-Complete Problems

1. Reduction:

o If a problem AAA is reducible to another problem BBB in polynomial time and BBB is
solvable, then AAA is also solvable.

o Reduction is used to prove NP-completeness.

2. First NP-complete Problem:

o The Satisfiability (SAT) Problem was the first problem proven to be NP-complete
(Cook-Levin Theorem).

3. Common NP-complete Problems:

o Travelling Salesman Problem (TSP).

o Knapsack Problem.

o Graph Coloring Problem.

o Hamiltonian Cycle Problem.

Steps to Prove a Problem is NP-Complete

1. Prove the Problem is in NP:

o Show that a solution can be verified in polynomial time.

2. Reduction:

o Select a known NP-complete problem.

o Show that the known NP-complete problem can be reduced to the new problem in
polynomial time.

Real-life Applications

1. Cryptography:

o Many encryption schemes rely on problems in NP (e.g., Integer Factorization).

2. Operations Research:

o Optimization problems like TSP and job scheduling.

3. Artificial Intelligence:

o Problems like planning and game theory involve NP-complete problems.

4. Network Design:

o Optimizing routes in networks and data centers.

Comparison of Complexity Classes

Class Definition Example Problems

P Solvable in polynomial time Sorting, Binary Search

NP Verifiable in polynomial time Subset-Sum

NP-Complete Hardest problems in NP SAT, TSP

NP-Hard As hard as NP-complete but not in NP Halting Problem

Example: SAT Problem

Problem Description:

 Given a boolean formula, is there an assignment of variables that makes the formula true?

Time Complexity of NP-complete Problems

 Worst-case: Exponential O(2^n)

 Optimized algorithms or heuristics (e.g., Branch and Bound, Approximation) are used for
practical purposes.

1. Reducibility

Problem: Reduce 3SAT to the Clique Problem.

Solution:

1. What is the 3SAT Problem?

o A 3SAT problem has a boolean formula in conjunctive normal form (CNF) where each
clause has exactly 3 literals.

o Example: (A∨¬B∨C)∧(¬A∨B∨D)∧(¬C∨¬D∨E)(A \lor \neg B \lor C) \land (\neg A \

lor B \lor D) \land (\neg C \lor \neg D \lor E)(A∨¬B∨C)∧(¬A∨B∨D)∧(¬C∨¬D∨E)

2. What is the Clique Problem?

o A clique is a subset of vertices in a graph such that every two vertices are connected
by an edge.

o The Clique Problem asks whether a graph contains a clique of size kkk.

3. Reduction Steps:

o Construct a graph GGG where:

 Each literal in the 3SAT formula corresponds to a vertex.

  Add edges between two vertices if their literals are not contradictory (e.g.,
AAA and ¬A\neg A¬A).

o Set k=k =k= number of clauses in the 3SAT formula.

o Check if GGG has a clique of size kkk.

4. Result:

o If GGG has a clique of size kkk, the 3SAT formula is satisfiable.

2. Circuit Satisfiability (Circuit SAT)

Problem: Determine if a given boolean circuit can output TRUE for some input combination.

Solution:

1. Boolean Circuit Representation:

o A circuit is composed of gates like AND, OR, and NOT.

o Example:

css

Copy code

A → AND → B

NOT ← OR → C

2. Steps:

o Convert the circuit into a CNF formula.

o Use a SAT solver to check if the formula is satisfiable.

o If satisfiable, the circuit outputs TRUE for some input.

3. Complexity:

o Circuit SAT is NP-complete since it generalizes the SAT problem.

3. 3SAT

Problem: Determine if a 3CNF formula is satisfiable.

Solution:

1. Example:

o Formula: (A∨¬B∨C)∧(¬A∨B∨D)∧(¬C∨¬D∨E)(A \lor \neg B \lor C) \land (\neg A \

lor B \lor D) \land (\neg C \lor \neg D \lor E)(A∨¬B∨C)∧(¬A∨B∨D)∧(¬C∨¬D∨E).

2. Backtracking Algorithm:
 o Assign truth values to variables iteratively.

o If a clause is unsatisfied, backtrack and try a different assignment.

o Continue until a satisfying assignment is found or all possibilities are exhausted.

3. Result:

o If a satisfying assignment exists, return it. Otherwise, the formula is unsatisfiable.

4. Vertex Cover

Problem: Find the minimum set of vertices that cover all edges in a graph.

Solution:

1. Graph Example:

o Edges: (A,B),(A,C),(B,D)(A, B), (A, C), (B, D)(A,B),(A,C),(B,D).

o Graph:

css

Copy code

A—B

| |

C D

2. Steps:

o Use a brute-force method to test all subsets of vertices.

o Check if each subset covers all edges.

o Return the smallest subset that does.

3. Result:

o Minimum Vertex Cover: {A,B}\{A, B\}{A,B}.

4. Approximation Algorithm:

o Pick any edge, add both endpoints to the cover, and remove all adjacent edges.

o Repeat until no edges remain.

5. Clique

Problem: Find the largest clique in a graph.

Solution:

1. Graph Example:
 o Edges: (A,B),(B,C),(C,A),(D,E)(A, B), (B, C), (C, A), (D, E)(A,B),(B,C),(C,A),(D,E).

o Graph:

mathematica

Copy code

A—B

\ |

C D—E

2. Steps:

o Generate all subsets of vertices.

o Check which subsets are fully connected (cliques).

o Return the largest subset.

3. Result:

o Maximum Clique: {A,B,C}\{A, B, C\}{A,B,C}.

4. Real-Life Use Case:

o Social Networks: Finding groups where everyone knows each other.

6. Cook's Theorem

Problem: Prove that SAT is NP-complete.

Solution:

1. Belongs to NP:

o A satisfying assignment can be verified in polynomial time.

2. Reduction:

o Reduce any NP problem to SAT in polynomial time.

o For a Turing machine, encode the computation as a SAT formula.

3. Result:

o Cook’s Theorem established that SAT is NP-complete, forming the basis for NP-
completeness proofs.

7. Travelling Salesman Problem (TSP)

Problem: Find the shortest route that visits all cities and returns to the starting city.

Solution:
 1. Input:

o Distance matrix:

css

Copy code

A B C

A 0 1 2

B 1 0 3

C 2 3 0

2. Exact Algorithm:

o Brute-force all permutations of cities.

o Compute the total distance for each permutation.

o Return the permutation with the smallest distance.

3. Approximation Algorithm:

o Nearest Neighbor:

 Start at a random city.

 Visit the nearest unvisited city.

 Repeat until all cities are visited.

4. Result:

o Optimal path: A→B→C→AA \to B \to C \to AA→B→C→A.

5. Complexity:

o Exact: O(n!)O(n!)O(n!).

o Approximation: Polynomial time.

8. Problem Classification: P, NP, NP-Complete, NP-Hard

Classification Examples:

Class Example Problems

P Sorting, Matrix Multiplication

NP Subset-Sum, 3SAT

NP-Complete SAT, Vertex Cover, Clique

NP-Hard TSP, Halting Problem

Key Differences:
  PPP: Problems solvable in polynomial time.

 NPNPNP: Solutions verifiable in polynomial time.

 NP−CompleteNP-CompleteNP−Complete: Problems in NP and as hard as the hardest in NP.

 NP−HardNP-HardNP−Hard: As hard as NP problems but may not be verifiable.

9. Complexity Comparison

Problem Class Complexity

Circuit Satisfiability NP-complete (2^n)

3SAT NP-complete O(2^n)

Vertex Cover NP-complete O(2^n)

Clique NP-complete O(2^n)