Computational Intractability in DAA

Learn Computational Intractability in DAA, including P, NP, NP-Complete, and NP-Hard problems. Understand why some problems require exponential time and how approximation and heuristic methods help.

Computational Intractability in DAA

Introduction

Some problems are such that:

• They can be solved on a computer, but
• They cannot be solved within a reasonable amount of time

Such problems are known as Computationally Intractable Problems.

What is Computational Intractability?

If the time or resources (time/space) required to solve a problem
increase very rapidly with the size of the input,
then the problem is said to be computationally intractable.

In general, the time complexity of such problems is
exponential or factorial in nature.

Characteristics of Intractable Problems

• Polynomial-time solutions are not available
• Worst-case execution time is extremely high
• Finding an exact solution is very difficult
• Such problems are often NP-Complete or NP-Hard

Complexity Classes

Class P (Polynomial Time)

• Problems that can be solved in polynomial time
• Examples:
  • Sorting
  • Searching
  • BFS, DFS

Class NP (Nondeterministic Polynomial Time)

• Problems whose solutions can be verified in polynomial time
• Examples:
  • Hamiltonian Cycle
  • Vertex Cover

NP-Complete

• The hardest problems in class NP
• If one NP-Complete problem is solved in polynomial time, then all NP problems can be solved
• Examples:
  • Travelling Salesman Problem
  • Vertex Cover
  • N-Queen Problem
  • Subset Sum Problem

Why Does Computational Intractability Arise?

1. Large size of the problem
2. Need to check all possible solutions
3. Presence of many constraints
4. NP-Complete or NP-Hard nature of the problem

Methods to Deal with Intractable Problems

1. Backtracking – Provides exact solutions but is time-consuming
2. Branch and Bound – More efficient than backtracking
3. Approximation Algorithms – Provide near-optimal solutions
4. Heuristic Algorithms – Use experience-based or rule-based approaches

Examples of Computationally Intractable Problems

Limitations

• Exact solutions are impractical for large inputs
• Require large amounts of time and space
• Difficult to use in real-time applications

Conclusion

Computational Intractability highlights the limitations of algorithmic power.
Not all problems can be solved efficiently using exact algorithms.
Therefore, in many cases, approximation or heuristic solutions must be adopted.

Some More: 

• POP- Introduction to Programming Using ‘C’
• DS – Data structure Using C
• OOP – Object Oriented Programming 
• Java Programming
• DBMS – Database Management System
• RDBMS – Relational Database Management System
• https://defineinfoloop.blogspot.com/?m=1