Tractable vs Intractable Problems | Problem Complexity | Class 11 Computer Science | Ch 3 | Lec 4

3.3.2 Tractable vs. Intractable Problems
Once a problem is determined to be solvable, the next consideration is its computational complexity—how efficiently it can be solved. Problems are categorized as tractable or intractable based on the resources required (time and space) to solve them.
Tractable Problems: A problem is considered tractable if it can be solved in polynomial time, denoted as P. Polynomial time means that the time taken to solve the problem increases at a manageable rate (as a polynomial function) relative to the size of the input. Tractable problems are considered "efficiently solvable."
Example: Sorting a list of numbers using algorithms like Merge Sort or Quick Sort is attractable problem because these algorithms have a polynomial time complexity of O (nlog n), where n is the number of elements in the list.
Intractable Problems: Intractable problems are those that require super-polynomial time to solve, often growing exponentially with the size of the input. These problems are impractical to solve for large inputs because the time required becomes unmanageable.

#Digital Education
#DigitalEducationLatestNews
#DigitalEducationShahbazAli


#11thComputerScience
#Class11CS
#ComputerScience11
#CSClass11
#Class11ComputerScience
#ComputerScienceFundamentals
#CS11th
#LearnComputerScience
#DigitalEducationCS

#DigitalEducation #11thComputerScience #ProblemComplexity #TractableProblems #IntractableProblems #PolynomialTime #ComputationalComplexity #Class11CS #ComputerScience

Computer Science 11th class
Lecturer of Computer Science
By Sir Shahbaz Ali
For any query or private tutoring contact (0309-0334424)
[email protected]