Explain the term Intractability. Is SAT problem is intractable? Justify
Marks: 5Chapter: Unit VII: Undecidability and Intractability (5 Hrs.)
Chapter Study
Bsc CSIT Semester 4 – Theory of Computation – Unit VII: Undecidability and Intractability (5 Hrs.)
Comprehensive questions and detailed answers for Unit VII: Undecidability and Intractability (5 Hrs.). Perfect for exam preparation and concept clarity.
4
Questions
20
Marks
Explain the term Intractability. Is SAT problem is intractable? Justify
MediumTHEORY5 marks2078(TU Final)
Explain about the complexity classes p, NP and NP-Complete.
MediumTHEORY5 marks2079(TU Final)
Write short notes ( Any two ) :
a) Big Oh, Big Omega and Big Theta
b) Tractable and Intractable Problems
c) Chomsky Hierarchy
MediumTHEORY5 marks2079(TU Final)
How abstract, decision and optimization problems are different from each other?
MediumTHEORY5 marks2080(TU Final)
Showing 4 questions
Sample Questions
Explain about the complexity classes p, NP and NP-Complete.
Marks: 5Chapter: Unit VII: Undecidability and Intractability (5 Hrs.)
Write short notes ( Any two ) : a) Big Oh, Big Omega and Big Theta b) Tractable and Intractable Problems c) Chomsky Hierarchy
Marks: 5Chapter: Unit VII: Undecidability and Intractability (5 Hrs.)
How abstract, decision and optimization problems are different from each other?
Marks: 5Chapter: Unit VII: Undecidability and Intractability (5 Hrs.)