KTU BBA & BCA UPDATES

Your trusted community for KTU BBA & BCA notes,

question papers and university updates.

Join our WhatsApp Community

Click here to join

NOTES | SYLLABUS | ANNOUNCEMENTS | QUESTION BANKS |

TIMETABLES | STUDY RESOURCES

🌐Website
[Link]

Contact us
✉︎ ktubbabcaupdates@[Link]
✆ 9544136946
BACKTRACKING:CONTROL ABSTRACTION,
N-QUEENS PROBLEM,SUM OF SUBSETS PROBLEM

BACKTRACKING
 It is one of the problem solving/algorithm design strategy.
 Backtracking is an algorithm technique to solve a problem by incremental way.
 It was a recursive approach to solve a problem.
Backtracking algorithms are like problem-solving strategies that help explore different
options to find the best solution. They work by trying out different paths and if one doesn't
work, they backtrack and try another until they find the right one.
In backtracking, problem can be categorized into three:
1. Decision problem: here we find whether there is any feasible solution.
2. Optimization problem: here we find whether there exist any best solution.
3. Enumeration problem: here we find all possible feasible solution.
Application of backtracking:
1. N-queen problem
2. Graph colouring
3. Hamiltonian cycle
4. Sum of subsets
5. 0/1 knapsack

Working of backtracking:

2boys
3 Students And 3 chairs
1 girl

Problem : How many ways we can arrange them?

Solution : 3! Ways
=3*2*1=6 ways
We can represent solution in form of State Space tree.
State space tree is like a diagram ,used to rtepresent all possible states or choices in problem
while searching for a solution.
Constraints:
Girls should not sit in middle

Bounding function – is needed to kill some live nodes without actually

expanding them.
N-QUEENS PROBLEM
N Queens problem is to place n-queens in such a manner or an N*N chessboard that no
queens attacks each other by being in:
 Same row
 Same column
 Same diagonal
Find all possible distinct arrangements of the queens on the board that satisfy these
conditions.

Steps:

1. Start in the leftmost column.

2. If all queens are placed,
→ Print the board (solution found) and return true.
3. Try placing the queen in the current column (col):
For each row i from 0 to n-1:
o Check if placing a queen at (i, col) is safe (i.e., no other queen in the same
row, upper diagonal, or lower diagonal).
4. If safe:
o Place the queen at (i, col).
o Recursively place the rest of the queens (solve(col + 1)).
5. If recursion returns true, return true (solution found).
6. If placing queen in (i, col) leads to no solution:
o Remove the queen (Backtrack) and try the next row.
7. If all rows are tried and no place is found, return false.

Here we consider 4 queen problem

We have to place 4 queen such as Q1,Q2,Q3,Q4

Here, we can’t place Q3 in third column ,so backtrack
Remove the last placed queen and find new place for it ,by incrementing row

Place Q3 on next column

Place Q4 on next column

Here, we can’t place Q4 in fourth column ,so backtrack

Remove Q3,increment row, can’t place(same diagonal)

Increment row,can’t place(same row),no more row,so again backtrack

Remove Q2,no more row increments

So again backtrack

Remove Q1,increment row

 Now all queens are placed in different columns ,different rows and without diagonal.

Below is the recursive tree of the above approach:

SUM OF SUBSETS
Given a set[ ] of non-negative integers and value sum, the task is to print the subset of given set
whose sum is equal to given sum.
Eg:
W[1:6]={5,10,12,13,15,18}
Sum M=30
We will write solution in array which contains 0 or 1 as values
Xi=0/1
State space tree is time consuming and complexity is 2^n.
If we apply backtracking we have to kill nodes by applying bounding function.

Steps:

1. Start with an empty knapsack (weight = 0, profit = 0).

2. For each item i (from 1 to n):
o Include the item (xi = 1) if it doesn’t exceed capacity.
o Recurse to check the next item.
o Exclude the item (xi = 0) and recurse again.
3. If the total weight exceeds capacity → backtrack (discard that path).
4. If all items are considered → record total profit.
5. Compare and keep track of the maximum profit among all valid combinations.
6. Repeat until all possible combinations are explored.
7. Return the combination with the highest profit within the capacity limit.
TRAVELING SALESMAN PROBLEM
Problem Definition
Given a set of cities and the distance between every pair of cities, the objective is to find the shortest
possible route that visits each city exactly once and returns to the starting city.

Input: A distance matrix D where D[i][j] represents the distance from city i to city j

Output: A tour that visits all cities exactly once with minimum total cost

Approaches to Solve TSP

1. Brute Force
Generate all possible permutations of cities and select the tour with minimum cost.

Time Complexity: O(n!)

Problem: Computationally infeasible for large n

2. Branch and Bound Approach

An intelligent search technique that explores the solution space while pruning branches that cannot lead
to optimal solutions.

Branch and Bound Method

Types of Nodes
1. Live Node: A node generated but whose children have not yet been generated

2. E-node: A live node whose children are currently being explored

3. Dead Node: A node that will not be expanded further (pruned or fully explored)
Cost Function
C(X) = g(X) + h(X)

Where:

g(X) = Cost of reaching current node from root (actual cost so far)

h(X) = Lower bound estimate of cost to complete the tour

Lower Bound Calculation:

Uses Cost Matrix Reduction:

1. Row Reduction: For each row, subtract the minimum value from all elements

2. Column Reduction: For each column, subtract the minimum value from all elements

3. Lower Bound = Sum of all values subtracted

This works because every tour must leave each city once (row) and enter each city once (column).

Complete Algorithm

Algorithm TSP_BranchAndBound(cost_matrix, n)
{
// n = number of cities
// cost_matrix[i][j] = distance from city i to city j

// Step 1: Initialize root node

[Link] = [0]
root.reduced_matrix = cost_matrix
[Link] = reduce_matrix(root.reduced_matrix)
[Link] = 0
root.current_city = 0
min_cost = INFINITY
final_path = []

// Priority queue to store live nodes (min-heap based on cost)

PriorityQueue Q
[Link](root)

// Step 2: Explore state space tree

while Q is not empty do
{
// Get node with minimum cost (E-node)
E = [Link]()

// Prune if cost exceeds current best

if [Link] >= min_cost then
continue

// Check if leaf node (all cities visited)

if [Link] == n-1 then
{
// Add return cost to starting city
total = [Link] + cost_matrix[E.current_city][0]

if total < min_cost then

{
min_cost = total
final_path = [Link] + [0]
}
continue
}

// Generate child nodes for unvisited cities

for each unvisited city i do
{
child = new Node
 [Link] = [Link] + [i]
[Link] = [Link] + 1
child.current_city = i

// Create reduced matrix for child

child.reduced_matrix = copy(E.reduced_matrix)

// Set row and column to infinity

set row E.current_city to INFINITY
set column i to INFINITY
child.reduced_matrix[i][0] = INFINITY

// Calculate child cost

edge_cost = E.reduced_matrix[E.current_city][i]
reduction_cost = reduce_matrix(child.reduced_matrix)
[Link] = [Link] + edge_cost + reduction_cost

// Add to queue if promising

if [Link] < min_cost then
[Link](child)
}
}

return final_path, min_cost

}

Function reduce_matrix(matrix)
{
reduction = 0

// Row reduction
for each row i do
{
min_val = minimum value in row i (excluding INFINITY)
if min_val > 0 then
 {
subtract min_val from all elements in row i
reduction += min_val
}
}

// Column reduction
for each column j do
{
min_val = minimum value in column j (excluding INFINITY)
if min_val > 0 then
{
subtract min_val from all elements in column j
reduction += min_val
}
}

return reduction
}

Complete Example Solution

Given: 4 cities (0, 1, 2, 3) with cost matrix:

0 1 2 3
┌───────────────┐
0 │ ∞ 10 15 20 │
1 │ 10 ∞ 35 25 │
2 │ 15 35 ∞ 30 │
3 │ 20 25 30 ∞ │
└───────────────┘
Step 1: Create Root Node (Starting at City 0)

Original Matrix:

0 1 2 3
┌───────────────┐
0 │ ∞ 10 15 20 │
1 │ 10 ∞ 35 25 │
2 │ 15 35 ∞ 30 │
3 │ 20 25 30 ∞ │
└───────────────┘

Row Reduction:

Row 0: min = 10, subtract 10 → Reduction cost = 10

Row 1: min = 10, subtract 10 → Reduction cost = 10

Row 2: min = 15, subtract 15 → Reduction cost = 15

Row 3: min = 20, subtract 20 → Reduction cost = 20

After Row Reduction:

0 1 2 3
┌───────────────┐
0 │ ∞ 0 5 10 │
1 │ 0 ∞ 25 15 │
2 │ 0 20 ∞ 15 │
3 │ 0 5 10 ∞ │
└───────────────┘

Column Reduction:

All columns already have 0, no reduction needed

Total Reduction Cost = 10 + 10 + 15 + 20 = 55

Root Node:

Path: [0]

Cost: 55

Level: 0

Step 2: Expand Root Node (E-node = Root)

Generate children for cities 1, 2, 3

Child 1: Going to City 1 (0→1)

Edge Cost: 0 (from reduced matrix[0][1])

Modify Matrix:

Set row 0 = ∞

Set column 1 = ∞

Set matrix[1][0] = ∞ (prevent premature return)

Matrix after modification:

0 1 2 3
┌───────────────┐
0 │∞ ∞ ∞ ∞│
1 │ ∞ ∞ 25 15 │
2 │ ∞ ∞ ∞ 15 │
3 │ ∞ ∞ 10 ∞ │
└───────────────┘

Row Reduction: All rows have 0 or all ∞, no reduction Column Reduction: All columns have 0 or all
∞, no reduction Reduction Cost = 0
Node 1:

Path: [0, 1]

Cost: 55 + 0 + 0 = 55

Level: 1

Child 2: Going to City 2 (0→2)

Edge Cost: 5 (from reduced matrix[0][2])

Modify Matrix:

Set row 0 = ∞

Set column 2 = ∞

Set matrix[2][0] = ∞

Matrix after modification:

0 1 2 3
┌───────────────┐
0 │∞ ∞ ∞ ∞│
1 │ 0 ∞ ∞ 15 │
2 │ ∞ 20 ∞ ∞ │
3 │0 5 ∞ ∞│
└───────────────┘

Row Reduction: All rows have 0, no reduction Column Reduction: All columns have 0, no reduction
Reduction Cost = 0

Node 2:

Path: [0, 2]
 Cost: 55 + 5 + 0 = 60

Level: 1

Child 3: Going to City 3 (0→3)

Edge Cost: 10 (from reduced matrix[0][3])

Modify Matrix:

Set row 0 = ∞

Set column 3 = ∞

Set matrix[3][0] = ∞

Matrix after modification:

0 1 2 3
┌───────────────┐
0 │∞ ∞ ∞ ∞│
1 │ 0 ∞ 25 ∞ │
2 │ 0 20 ∞ ∞ │
3 │ ∞ 5 10 ∞ │
└───────────────┘

Row Reduction: All rows have 0, no reduction Column Reduction: All columns have 0, no reduction
Reduction Cost = 0

Node 3:

Path: [0, 3]

Cost: 55 + 10 + 0 = 65

Level: 1
Priority Queue after Step 2: [Node 1 (55), Node 2 (60), Node 3 (65)]

Step 3: Expand Node 1 (0→1, Cost = 55)

E-node = Node 1, Unvisited cities: 2, 3

Child 4: Going to City 2 (0→1→2)

Edge Cost: 25

Matrix operations and reduction:

Set row 1 = ∞, column 2 = ∞, matrix[2][0] = ∞

After reduction: Reduction Cost = 0

Node 4:

Path: [0, 1, 2]

Cost: 55 + 25 + 0 = 80

Level: 2

Child 5: Going to City 3 (0→1→3)

Edge Cost: 15

Matrix operations and reduction:

Set row 1 = ∞, column 3 = ∞, matrix[3][0] = ∞

After reduction: Reduction Cost = 0

Node 5:

Path: [0, 1, 3]
 Cost: 55 + 15 + 0 = 70

Level: 2

Priority Queue: [Node 2 (60), Node 3 (65), Node 5 (70), Node 4 (80)]

Step 4: Expand Node 2 (0→2, Cost = 60)

E-node = Node 2, Unvisited cities: 1, 3

Child 6: Going to City 1 (0→2→1)

Edge Cost: 20

Node 6:

Path: [0, 2, 1]

Cost: 60 + 20 + 0 = 80

Level: 2

Child 7: Going to City 3 (0→2→3)

Edge Cost: 15

Node 7:

Path: [0, 2, 3]

Cost: 60 + 15 + 0 = 75

Level: 2

Priority Queue: [Node 3 (65), Node 5 (70), Node 7 (75), Node 4 (80), Node 6 (80)]
Step 5: Expand Node 3 (0→3, Cost = 65)
E-node = Node 3, Unvisited cities: 1, 2

Child 8: Going to City 1 (0→3→1)

Edge Cost: 5

Node 8:

Path: [0, 3, 1]

Cost: 65 + 5 + 0 = 70

Level: 2

Child 9: Going to City 2 (0→3→2)

Edge Cost: 10

Node 9:

Path: [0, 3, 2]

Cost: 65 + 10 + 0 = 75

Level: 2

Priority Queue: [Node 5 (70), Node 8 (70), Node 7 (75), Node 9 (75), Node 4 (80), Node 6 (80)]

Step 6: Expand Node 5 (0→1→3, Cost = 70)

E-node = Node 5, Unvisited city: 2 (Level 2, next is leaf)

Child 10: Going to City 2 (0→1→3→2)

Edge Cost: 10
Node 10:

Path: [0, 1, 3, 2]

Level: 3 (Leaf node - all cities visited)

Complete tour: 0→1→3→2→0 Return cost: matrix[2][0] = 15 Total Cost: 70 + 10 + 15 = 95

Current Best Solution: Cost = 95, Path = [0, 1, 3, 2, 0]

Step 7: Expand Node 8 (0→3→1, Cost = 70)

E-node = Node 8, Unvisited city: 2

Child 11: Going to City 2 (0→3→1→2)

Node 11:

Path: [0, 3, 1, 2]

Level: 3 (Leaf node)

Complete tour: 0→3→1→2→0 Return cost: matrix[2][0] = 15 Total Cost: 70 + 25 + 15 = 110

Not better than current best (95), discard.

Step 8: Expand Node 7 (0→2→3, Cost = 75)

E-node = Node 7, Unvisited city: 1

Child 12: Going to City 1 (0→2→3→1)

Node 12:

Path: [0, 2, 3, 1]

Level: 3 (Leaf node)

Complete tour: 0→2→3→1→0 Return cost: matrix[1][0] = 10 Total Cost: 75 + 25 + 10 = 110

Not better than current best (95), discard.

Step 9: Continue expanding remaining nodes

All remaining nodes in queue have cost ≥ 75, and when completed, none yield a tour better than 95.

Pruning occurs: Nodes with cost ≥ 95 are not expanded further.

Final Solution:
Optimal Tour: 0 → 1 → 3 → 2 → 0

Tour Cost Breakdown:

0 → 1: 10

1 → 3: 25

3 → 2: 30

2 → 0: 15

Total: 80

Wait, let me recalculate from original matrix:

0 → 1: 10

1 → 3: 25

3 → 2: 30

2 → 0: 15

Total = 80

Minimum Cost: 80
State Space Tree Visualization

Root [0]
Cost = 55
/ | \
/ | \
/ | \
[0,1] [0,2] [0,3]
C=55 C=60 C=65
/ \ / \ / \
[0,1,2] [0,1,3] [0,2,1] [0,2,3] [0,3,1] [0,3,2]
C=80 C=70 C=80 C=75 C=70 C=75
| | | | | |
[0,1,2,3] [0,1,3,2] [0,2,1,3] [0,2,3,1] [0,3,1,2] [0,3,2,1]
LEAF LEAF LEAF LEAF LEAF LEAF
Total=95 Total=80✓ Total=110 Total=110 Total=110 Total=95

Legend:
✓ = Optimal solution found
C = Cost (lower bound)
Nodes with costs ≥ current best are pruned (not shown in detail)

Path followed by algorithm:

1. Start at Root [0]

2. Expand to [0,1] (lowest cost = 55)

3. Expand to [0,2] (next lowest = 60)

4. Expand to [0,3] (next lowest = 65)

5. Expand [0,1,3] (cost = 70)

 6. Reach leaf [0,1,3,2,0] with total = 80 ✓

7. Continue checking other promising nodes

8. Prune branches with cost ≥ 80

9. Final answer: 0→1→3→2→0 with cost 80

Complexity Analysis

Time Complexity:
Best Case: O(n²) when optimal solution found early with effective pruning

Average Case: Much better than O(n!) due to pruning (typically O(n² × 2ⁿ))

Worst Case: O(n!) when minimal pruning occurs

Space Complexity:
O(n²) for storing cost matrices

O(n!) for priority queue in worst case

Practical: Much better due to pruning

Why it's better than Brute Force:

1. Pruning: Eliminates branches with cost ≥ current best solution

2. Bounding: Lower bound estimation avoids exploring unpromising paths

3. Intelligent Search: Priority queue ensures exploring most promising nodes first

4. Practical Performance: In this example, explored ~12 nodes instead of 4! = 24 permutations

Comparison
Method Time Complexity Optimal Solution

Brute Force O(n!) Yes

Branch & Bound O(n!) worst, better average Yes

Dynamic Programming O(n² × 2ⁿ) Yes

Greedy/Heuristics O(n²) No
 

Key Points
1. Branch and Bound guarantees optimal solution

2. Uses lower bound (reduced cost matrix) to prune unpromising branches

3. Priority queue ensures best-first search

4. Practical for small to medium instances (n ≤ 20-25)

5. Explores far fewer nodes than brute force in practice

Complexity Classes: Tractable and Intractable Problems
1. Introduction to Tractable and Intractable Problems
1.1 Tractable Problems

Definition: A problem is considered tractable if it can be solved in polynomial time, i.e., there exists an algorithm that solves the problem in O(n^k) time for some constant k, where n is the
input size.

Characteristics:

Solvable efficiently even for large inputs

Running time grows at a reasonable rate
Practical and feasible for real-world applications
Examples: O(n), O(n log n), O(n²), O(n³)

Examples of Tractable Problems:

1. Sorting: Merge Sort, Quick Sort - O(n log n)

2. Searching: Binary Search - O(log n)
3. Shortest Path: Dijkstra's Algorithm - O(V² or E log V)
4. Minimum Spanning Tree: Prim's, Kruskal's - O(E log V)
5. Matrix Multiplication: O(n³) or better

1.2 Intractable Problems

Definition: A problem is intractable if no polynomial-time algorithm exists to solve it. The running time grows exponentially or worse with input size.

Characteristics:

Require exponential time: O(2^n), O(n!)

Infeasible for large inputs
May require years or centuries to solve for moderate-sized inputs
Often require approximation or heuristic approaches

Examples of Intractable Problems:

1. Travelling Salesman Problem (TSP) - O(n!)

2. Hamiltonian Cycle Problem
3. Graph Coloring Problem
4. Knapsack Problem (0/1)
5. Boolean Satisfiability (SAT)
1.3 Comparison Table

Aspect Tractable Intractable

Time Complexity Polynomial: O(n^k) Exponential: O(2^n), O(n!)
Scalability Handles large inputs Limited to small inputs
Practicality Feasible for real-world use Often requires approximation
Examples Sorting, Searching TSP, SAT, Hamiltonian Cycle

2. Complexity Classes
Complexity classes categorize computational problems based on the resources (time, space) required to solve them.

2.1 Class P (Polynomial Time)

Definition: P is the class of decision problems that can be solved by a deterministic Turing machine in polynomial time.

Formal Definition:

P = {L | L is decidable in polynomial time}

Characteristics:

Problems have efficient algorithms

Solution can be found quickly
All problems in P are tractable
P represents "easy" problems

Examples:

1. Linear Search
Problem: Find an element in an array
Algorithm: Sequential scan
Time Complexity: O(n)
Why in P: Direct polynomial-time solution exists
2. Sorting
Problem: Arrange elements in order
Algorithm: Merge Sort, Quick Sort
Time Complexity: O(n log n)
 Why in P: Efficient polynomial-time algorithms available
3. Shortest Path (Single Source)
Problem: Find shortest path from source to all vertices
Algorithm: Dijkstra's Algorithm
Time Complexity: O(V² or E log V)
Why in P: Polynomial-time solution exists
4. Primality Testing
Problem: Determine if a number is prime
Algorithm: AKS primality test
Time Complexity: O((log n)^6)
Why in P: Polynomial-time algorithm (AKS) exists
5. Matrix Multiplication
Problem: Multiply two n×n matrices
Algorithm: Standard or Strassen's algorithm
Time Complexity: O(n³) or O(n^2.807)
Why in P: Polynomial-time solutions available

2.2 Class NP (Nondeterministic Polynomial Time)

Definition: NP is the class of decision problems for which a proposed solution can be verified in polynomial time by a deterministic Turing machine.

Formal Definition:

NP = {L | L is verifiable in polynomial time}

Characteristics:

Solution can be verified quickly (polynomial time)

Finding solution may be hard
All P problems are in NP (P ⊆ NP)
NP represents "verifiable" problems

Key Point:

Solving a problem may be hard

Verifying a given solution is easy

Examples:

1. Subset Sum Problem

 Problem: Given a set of integers and target T, does any subset sum to T?
Verification: Given a subset, add elements and check if sum = T
Time to verify: O(n)
Why in NP: Easy to verify, hard to find
2. Hamiltonian Cycle
Problem: Does a graph have a cycle visiting each vertex exactly once?
Verification: Given a cycle, check if it visits all vertices once
Time to verify: O(V)
Why in NP: Verification is polynomial, finding is hard
3. Graph Coloring
Problem: Can graph be colored with k colors such that no adjacent vertices have same color?
Verification: Check each edge to ensure endpoints have different colors
Time to verify: O(E)
Why in NP: Easy to verify coloring, hard to find minimum colors
4. Boolean Satisfiability (SAT)
Problem: Given a boolean formula, does an assignment make it true?
Verification: Substitute values and evaluate formula
Time to verify: O(n)
Why in NP: Easy to verify assignment, hard to find
5. Clique Problem
Problem: Does graph have a clique of size k?
Verification: Check if given k vertices form a complete subgraph
Time to verify: O(k²)
Why in NP: Easy to verify clique exists, hard to find

2.3 Class NP-Complete

Definition: A problem is NP-Complete if:

1. It is in NP (solution verifiable in polynomial time)

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

Formal Definition:

A problem X is NP-Complete if:

1. X ∈ NP
2. For every Y ∈ NP, Y ≤p X (polynomial-time reducible)

Characteristics:
 Hardest problems in NP
If any NP-Complete problem has polynomial solution, then P = NP
All NP-Complete problems are equally hard
No polynomial-time algorithm known

Historical Note:

SAT was the first problem proven NP-Complete (Cook's Theorem, 1971)
Other problems proven NP-Complete by reduction from SAT

Examples:

1. Boolean Satisfiability (SAT)

Problem: Given boolean formula in CNF, is there an assignment making it true?
Example: (A ∨ B) ∧ (¬A ∨ C) ∧ (¬B ∨ ¬C)
Why NP-Complete: First proven NP-Complete problem (Cook-Levin theorem)
Application: Circuit design, AI planning
2. 3-SAT
Problem: SAT with exactly 3 literals per clause
Example: (A ∨ B ∨ C) ∧ (¬A ∨ D ∨ E)
Why NP-Complete: Reduced from SAT
Application: Logic verification, theorem proving
3. Vertex Cover
Problem: Find k vertices covering all edges
Example: In a graph, select minimum vertices such that every edge has at least one endpoint in the set
Why NP-Complete: Reduced from 3-SAT
Application: Network monitoring, bioinformatics
4. Hamiltonian Cycle
Problem: Find cycle visiting each vertex exactly once
Example: In a graph with n vertices, find a cycle of length n
Why NP-Complete: Reduced from Vertex Cover
Application: Route planning, DNA sequencing
5. Travelling Salesman Problem (Decision Version)
Problem: Is there a tour of length ≤ k visiting all cities?
Example: Given cities and distances, can you complete tour under budget?
Why NP-Complete: Reduced from Hamiltonian Cycle
Application: Logistics, circuit board drilling
6. Graph Coloring (k-coloring)
Problem: Can graph be colored with k colors?
Example: Can you color map with 3 colors so no adjacent regions match?
Why NP-Complete: Reduced from 3-SAT
Application: Register allocation, scheduling
7. Clique Problem
Problem: Does graph have complete subgraph of size k?
Example: In a social network, is there a group where everyone knows everyone?
Why NP-Complete: Reduced from 3-SAT
 Application: Social network analysis, bioinformatics
8. Subset Sum
Problem: Does subset of numbers sum to target?
Example: Given {3, 34, 4, 12, 5, 2}, is there subset summing to 9? (Yes: 4+5)
Why NP-Complete: Reduced from Vertex Cover
Application: Cryptography, resource allocation

2.4 Class NP-Hard

Definition: A problem is NP-Hard if every problem in NP can be reduced to it in polynomial time. NP-Hard problems are at least as hard as NP-Complete problems.

Formal Definition:

A problem X is NP-Hard if:

For every Y ∈ NP, Y ≤p X

Key Difference from NP-Complete:

NP-Complete = NP-Hard ∩ NP
NP-Hard problems may not be in NP (may not be decision problems)
NP-Hard problems may be optimization problems

Characteristics:

At least as hard as NP-Complete problems

May not have verifiable solutions in polynomial time
No polynomial-time algorithm known
Often optimization versions of NP-Complete problems

Examples:

1. Travelling Salesman Problem (Optimization)

Problem: Find shortest tour visiting all cities
Type: Optimization (not decision)
Why NP-Hard: Harder than decision version (which is NP-Complete)
Application: Route optimization, logistics
2. Knapsack Problem (Optimization)
Problem: Maximize value of items within weight limit
Example: Given items with weights and values, fill knapsack optimally
Why NP-Hard: Optimization version of decision problem
 Application: Resource allocation, investment
3. Halting Problem
Problem: Determine if a program will halt on given input
Why NP-Hard: Undecidable (harder than NP-Complete)
Not in NP: Cannot verify solution in polynomial time
Application: Program verification
4. Vertex Cover (Optimization)
Problem: Find minimum vertex cover
Why NP-Hard: Finding minimum is harder than decision version
Application: Network design
5. Graph Coloring (Chromatic Number)
Problem: Find minimum number of colors needed
Example: What's the minimum colors to color a map?
Why NP-Hard: Optimization version
Application: Scheduling, register allocation
6. Set Cover Problem
Problem: Find minimum number of sets covering all elements
Example: Minimum number of guards to watch all rooms
Why NP-Hard: Generalization of Vertex Cover
Application: Facility location, resource allocation

3. Relationship Between Complexity Classes

3.1 Venn Diagram Representation
 ┌─────────────────────────────────────┐
│ NP-HARD │
│ ┌──────────────────────────────┐ │
│ │ NP │ │
│ │ ┌──────────────────────┐ │ │
│ │ │ P │ │ │
│ │ │ │ │ │
│ │ │ (Tractable) │ │ │
│ │ │ │ │ │
│ │ └──────────────────────┘ │ │
│ │ │ │
│ │ ┌──────────────────┐ │ │
│ │ │ NP-Complete │ │ │
│ │ │ (Intersection) │ │ │
│ │ └──────────────────┘ │ │
│ └──────────────────────────────┘ │
│ │
│ (Problems not in NP, │
│ like Halting Problem) │
└─────────────────────────────────────┘

3.2 Key Relationships

1. P ⊆ NP
Every problem solvable in polynomial time is also verifiable in polynomial time
If you can solve it quickly, you can verify it quickly
2. NP-Complete ⊆ NP
All NP-Complete problems are in NP
They are verifiable in polynomial time
3. NP-Complete ⊆ NP-Hard
All NP-Complete problems are NP-Hard
But not all NP-Hard problems are NP-Complete
4. P = NP ? (Unsolved)
Million-dollar question in computer science
If P = NP, then P = NP = NP-Complete
Most believe P ≠ NP
4. Summary Table
Class Definition Key Property Examples
P Solvable in polynomial time Can solve quickly Sorting, Shortest Path, MST
NP Verifiable in polynomial time Can verify quickly Subset Sum, Hamiltonian Cycle
NP-Complete Hardest in NP; NP-Hard ∩ NP Equally hard problems SAT, TSP (decision), Vertex Cover
NP-Hard At least as hard as NP-Complete May not be in NP TSP (optimization), Halting Problem