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

Back to All Chapters

1

Explain the term Intractability. Is SAT problem is intractable? Justify

MediumTHEORY5 marks2078(TU Final)

2

Explain about the complexity classes p, NP and NP-Complete.

MediumTHEORY5 marks2079(TU Final)

3

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)

4

How abstract, decision and optimization problems are different from each other?

MediumTHEORY5 marks2080(TU Final)

5

What is undecidable problem? Discuss about Post Correspondence Problem.

MediumTHEORY5 marks2081(TU Final)

6

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 the term Intractability. Is SAT problem is intractable? Justify

Marks: 5Chapter: Unit VII: Undecidability and Intractability (5 Hrs.)

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.