Guide to Exam 3

Instructions

Exaam 3 will be held during the finals week on Friday, April 19, 10:30 am - 12:30 pm in 420 SH.

The exam is open book - you may use your notes, homeworks, any handouts and solutions you have worked out, the text (Sipser), and any other paper-based references. You may not use any electronic devices, such as laptops, phones, or tablets.

Write your answers in the blue books provided. Show all your work and indicate your final answers clearly.

General things to know

• Decision problems: decidable vs. undecidable languages

• Turing-recognizable and non-Turing-recognizable languages, co-Turing-recognizability

• Proofs of undecidability or non-Turing-recognizability using mapping reductions

• Time complexity of deterministic and non-deterministic Turing machines; polynomial vs. exponential time

• The language classes P and NP

• Polytime reductions and NP-completeness

Specific things you should know how to do:

• Design a Turing machine (possibly a non-deterministic one), using an informal high-level description to do a high-level task. The TM may include "calls" to other TMs or simulate their operation

• Provide asymptotic time-complexity analysis of a Turing machine, especially to distinguish polynomial running time from super-polynomial (e.g. exponential) running time

The purpose of designing such a TM and/or to provide such time-complexity analysis may be to:

• Prove closure or nonclosure of a specified language class (especially the decidable languages, P, or NP) under certain operations applied to its languages.

• Prove that a given language is: decidable, in P, or in NP

• Prove that a given language is: undecidable, or NP-complete

In addition youshoud have sufficient domain knowledge of Boolean formulas and graphs to be able to construct simple reductions from the standard NP-complete languages like SAT, 3SAT, HAMPATH, VERTEX-COVER, CLIQUE, etc.

Specific things that will definitely appear on the exam:

• You will be required to do at least one of the following:

  • Prove that a given language is decidable

  • Prove that a given language is in NP

  • Prove that a given language is in NP

• You will be required to:

  • Prove that a given language is undecidable

• You will be required to:

  • Prove that a given language is NP-complete

Additional insights into what to expect on the exam:

Where a reduction is required:

• You may be given:

  • the language to reduce it from; and/or

  • a description of the actual function that performs the reduction; or

  • some other hint to guide you in determining the appropriate reduction

• The reduction will be fairly simple and it should be straghtforward to prove it has the correct properties (assuming you understand what these properties are)