Cla 3, Ap23110010650

DESIGN ANALYSIS OF ALGRITHMS
CLA-3
PRESENTED BY GROUP-5:
P V SAI KIRAN-AP23110010650
Understanding NP Problems
Introduction to NP, NP - Complete, and NP-Hard Problems
CONTEN
T:
1)NP Problems
2)P vs NP
3)NP-complete problems
4)NP-hard problems
5)Approaches
6)Real world applications
7)Summary
P VS NP
P (Polynomial Time) problems can be solved directly in polynomial time.

NP (Nondeterministic Polynomial Time) problems can have their solutions verified in
polynomial time.
The open question in computer science: Does P = NP?
In other words, if a solution can be verified in polynomial time, can it also be solved in
polynomial time?
Unsolved: No proof exists whether P = NP or not, making it one of the most important
questions in computational theory.
Examples
Bubble Sort, Merge Sort, Quick Sort (Sorting
algorithms)
Dijkstra's Algorithm (Shortest path in a graph)
Linear Search (Finding an element in a sorted
array)
Prim's Algorithm (Minimum Spanning Tree)
Linear Search Algorithm
int linearSearch(const vector<int>& arr, int target) {
for (int i = 0; i < arr.size(); i++) {
if (arr[i] == target) {
return i; // Target found, return its index
}
}
return -1; // Target not found
}
int main() {
vector<int> arr = {5, 3, 8, 6, 7, 2, 4};
int target = 6;
int result = linearSearch(arr, target);
if (result != -1) {
cout << "Element found at index " << result << endl;
} else {
cout << "Element not found" << endl;
}
return 0;
}
Advisory Argument
Advisory Argument for P (Polynomial Time)
Context: Choosing algorithms for real-time

or resource-constrained systems.
Analysis: Problems in P can be solved
efficiently in polynomial time using
deterministic algorithms, making them ideal
for scenarios where quick results are
needed.
Counterargument: While efficient, P
algorithms might not cover more complex or
large-scale real-world problems (e.g.,
optimization).
Recommendation: Prioritize P algorithms for
everyday tasks like sorting, pathfinding, or
basic computation where guaranteed
efficiency is critical. Examples: Dijkstra's
algorithm, Prim’s algorithm.
NP PROBLEMS
What are NP Problems?

NP stands for Nondeterministic Polynomial time, representing a class of
computational problems.
For NP problems, a proposed solution can be verified within polynomial time.
Polynomial Time means the solution time grows at a polynomial rate relative to
the input size, denoted as O(n^k) where k is a constant.
Verification vs. Solution: We can check if a proposed solution is correct in
polynomial time, but finding the solution itself could be harder.
Example:
Hamiltonian Cycle Problem: Determining if there exists a cycle in a graph that
visits each vertex once.
Given a cycle, we can quickly verify it, but finding it is computationally difficult.
Examples
Boolean Satisfiability Problem (SAT): Is there
a variable assignment that satisfies a given
Boolean formula?
Subset Sum Problem: Is there a subset of
numbers that adds up to a specific value?
Hamiltonian Path: Does a graph contain a path
visiting each vertex exactly once?
Subset Sum Problem
bool isSubsetSum(const vector<int>& nums, int target) {
int n = nums.size();
for (int i = 0; i < (1 << n); i++) {
int sum = 0;
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
sum += nums[j];
}
}
if (sum == target) {
return true;
}
}
return false;
}
int main() {
vector<int> nums = {3, 34, 4, 12, 5, 2};
int target = 9;
if (isSubsetSum(nums, target)) {
cout << "Subset with sum " << target << " exists." << endl;
} else {
cout << "Subset with sum " << target << " does not exist." << endl;
}
return 0;
}
Advisory Argument
Context: Evaluating whether a complex
problem is feasible for practical use.
Analysis: Problems in NP allow for efficient
verification of solutions, even if solving
them is difficult. Many real-world problems,
like scheduling or cryptography, fall into
this category.
Counterargument: Solving NP problems may
require exponential time unless specialized
heuristic methods or approximations are
used.
Recommendation: Use NP problems to model
complex scenarios (e.g., SAT problem,
Hamiltonian cycle) where verifying a solution
is critical. Invest in research for heuristics
or approximation techniques for practical
applications.
NP COMPLETE PROBLEM
Definition:
NP-Complete problems are the hardest problems in NP. If any NP-complete problem
can be solved in polynomial time, then all NP problems can be solved in polynomial time
(P = NP).
Characteristics:
In NP: Solution can be verified in polynomial time.
Hardest in NP: Solving one in polynomial time solves all NP problems.
Examples:
Traveling Salesman Problem: Shortest route visiting each city once.
Knapsack Problem: Optimal items within weight capacity.
3-SAT Problem: Boolean formula satisfiability with three literals per clause.
Significance:
Represent boundary of computational complexity.
Central to fields like optimization, cryptography, and AI.
Examples
Boolean Satisfiability Problem (SAT)
3-SAT Problem: A variant of SAT with clauses
containing 3 literals.
Clique Problem: Does a graph contain a
complete subgraph of size k?
Vertex Cover Problem: Is there a set of
vertices covering all edges of size k?
ALGORITHM
Boolean Satisfiability Problem (SAT)

bool isSatisfiable(const vector<vector<int>>& clauses, vector<bool>& assignment,
int var) {
if (var == assignment.size()) {
for (const auto& clause : clauses) {
bool clauseSatisfied = false;
for (int v : clause) {
if ((v > 0 && assignment[v - 1]) || (v < 0 && !assignment[-v - 1])) {
clauseSatisfied = true;
break;
}
}
if (!clauseSatisfied) return false;
}
return true;
}
assignment[var] = true;
if (isSatisfiable(clauses, assignment, var + 1)) return true;
assignment[var] = false;
return isSatisfiable(clauses, assignment, var + 1);
}
Advisory Argument
Context: Evaluating problems for research or
high-stakes scenarios where exact solutions
are vital.
Analysis: NP-complete problems are both in NP
(verifiable) and NP-hard (as hard as any NP
problem). Solving even one NP-complete
problem in polynomial time would prove P = NP,
revolutionizing computational complexity.
Examples include SAT, 3-SAT, and Vertex Cover
problems.
Counterargument: Directly solving NP-complete
problems is often infeasible for large inputs
due to exponential time complexity.
Recommendation: Prioritize NP-complete
problems for theoretical research or
situations where exactness is paramount. Use
reductions to simplify problems or heuristic
approaches to manage complexity in practical
cases.
NP HARD PROBLEMS
Definition: NP-Hard problems are at least as difficult as the hardest problems in NP.
However, they don’t have to be in the NP class because they may not have solutions
verifiable in polynomial time.
Key Characteristics:
No Known Polynomial-Time Solution: NP-Hard problems can’t be solved efficiently with
any known algorithms.
May Not Have Verifiable Solutions: Unlike NP-complete problems, a solution to an NP-
Hard problem may not be verifiable in polynomial time.
Can Be Unsolvable or Undecidable: Some NP-Hard problems, like the Halting Problem,
can’t be solved or verified for all inputs.
Real-World Examples:
Bin Packing: Minimizing the number of bins needed to pack items of different sizes.
Halting Problem: Determining if a program will eventually halt, which is undecidable.
Examples
Travelling Salesman Problem (TSP): Find the
shortest route visiting all cities.
Knapsack Problem (Optimization version):
Maximize value within a weight limit.
Graph Coloring Problem: Can you color a graph
using at most k colors such that no two
adjacent vertices have the same color?
HEURISTIC ALGORITHMS
TRAVELING SALESMAN PROBLEM:

vector<int> nearestNeighbor(int start, vector<vector<int>> &dist) {
int n = dist.size();
vector<int> path;
vector<bool> visited(n, false);
int current = start;
visited[current] = true;
path.push_back(current);
for (int i = 1; i < n; i++) {
int nearest = -1;
for (int j = 0; j < n; j++) {
if (!visited[j] && (nearest == -1 || dist[current][j] < dist[current][nearest])) {
nearest = j;
}
}
current = nearest;
visited[current] = true;
path.push_back(current);
}
return path;
}
Advisory Argument
Context: Addressing optimization or
resource-intensive tasks in logistics or AI.
Analysis: NP-hard problems are at least as
hard as NP problems. They often represent
real-world challenges like routing,
scheduling, or optimization (e.g., Travelling
Salesman Problem). These problems often
lack exact polynomial-time solutions.
Counterargument: Solving NP-hard problems
directly may be impractical. Approximation
algorithms or metaheuristics (e.g., genetic
algorithms) are necessary but may not
guarantee optimal solutions.
Recommendation: Use NP-hard frameworks
for scenarios requiring approximate or near-
optimal solutions, accepting trade-offs in
precision for speed. Develop domain-specific
strategies to narrow solution spaces.
NP HARD PROBLEMS
REAL-WORLD APPLICATIONS OF NP
PROBLEMS
Why Do NP Problems Matter?

Optimization:
Logistics: Optimizing delivery routes, minimizing cost.
Cryptography:
RSA Encryption: Based on the difficulty of factoring large numbers.
Artificial Intelligence:
Game Theory: Strategic decision-making under uncertainty (e.g., chess, Go).
Machine Learning:
Feature Selection: NP-hard problem in selecting the best features.
SUMMARY
Summary of Key Points:

NP problems are those where a solution can be verified quickly, but finding the
solution may take longer.
NP-Complete problems are the hardest in NP, and solving one in polynomial time
would solve all NP problems.
NP-Hard problems are at least as hard as NP problems, but not necessarily
verifiable in polynomial time.
Algorithms like dynamic programming, greedy heuristics, and approximation
methods are used to solve NP problems.
Thank
You!
Group-5

Cla 3, Ap23110010650

Uploaded by

Copyright:

Available Formats

Cla 3, Ap23110010650

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Cla 3, Ap23110010650

Uploaded by

Copyright:

Available Formats

DESIGN ANALYSIS OF ALGRITHMS

P (Polynomial Time) problems can be solved directly in polynomial time.

Context: Choosing algorithms for real-time

What are NP Problems?

Boolean Satisfiability Problem (SAT)

TRAVELING SALESMAN PROBLEM:

Why Do NP Problems Matter?

Summary of Key Points:

You might also like