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.
6
Questions
30
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)
What is undecidable problem? Discuss about Post Correspondence Problem.
MediumTHEORY5 marks2081(TU Final)
Differentiate between Class P and Class NP problem. Mention the transition function of DFA, NFA, and ε-NFA.
MediumTHEORY5 marks2081(TU Final)
Showing 6 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.)
What is undecidable problem? Discuss about Post Correspondence Problem.
Marks: 5Chapter: Unit VII: Undecidability and Intractability (5 Hrs.)
And more questions available on this page.