UVA CS 3120 Theory of Computation (Wei-Kai Lin)

This is the course website of CS 3120 (also called Discrete Mathematics and Theory 2), instructed by Prof. Lin. The meetings are Tuesdays and Thursdays at 12:30 - 1:45pm Spring 2025 and in Rice Hall 130. (Clarification: the course of Prof. Floryan is different.)

Another section of the same course: Prof. Floryan also teaches this course in Spring 2025. The two sections use different textbooks and proceed with slightly different topics although the overall goals are similar. The workload of this section shall be similar to the other section, but it is up to the staff’s discretion.

Recent Announcements

Class 27: Reductions, Review, and Gödel’s Incompleteness

We reviewed the template of reductions by showing the reduction from 3SAT to Maximum Independent Set. We also birefly reviewed the big ideas in this course: counting, reductions, code as data. We wrapped up this course with Gödel’s Incompleteness Theorem.

Slides are here.

Apr 29, 2025

Class 26: Cook-Levin Theorem

We proved Cook-Levin Theorem by reducing from any problem in NP to CircuitSAT and by recuding from CircuitSAT to 3SAT. We also talked about some other NP-Complete problems and about the need for P \(\neq\) NP in cryptography.

Thanks to Abhishek for pointing out a bug in my slides: BinPacking is easy and computable in polynomial time when there is only one bin. However, for two or more bins of the same size, it becomes NP-Complete to compute whether we can pack all items into the bins. See this note for the definition and reduction.

Slides are here.

Apr 24, 2025

Class 25: P vs NP vs EXP, NP-Complete

We compared class NP to the two classes P and EXP, with a brief definition of class co-NP. We then defined the class of NP-Complete (functions), a first step when human got to understand P vs NP. In the coming Thursday, we will prove Cook-Levin Theorem, which gives the first NP-Complete problem.

Slides are here.

Apr 22, 2025

Class 24: Reductions, and class NP

We introduced some hard problems, including LonggestPath, CircuitSAT, and 3-SAT. Then, we defined the complexity class NP, and we showed that the mentioned hard problems are in NP. The class NP is a big idea in CS. Instead of grouping problems by their computation time, NP groups problems by their verification time. At very high level, problems in NP are those “easy to verify” when the instance holds. That includes many problems we know of, and the concept opened many areas in CS.

Slides are here.

Mikhail asked about the complement of problems in NP. That is defined as the class co-NP: \(co-NP = \{F : F \text{ is a Boolean function and } NOT(F(x)) \in NP \}.\) We have \(P \subseteq NP\) and \(P \subseteq co-NP\), but it is a long open question whether \(NP = co-NP\).

Apr 17, 2025

Class 23: Complexity, and class P

We introduced time complexity of Turing machines, and then we defined the class of polynomial-time computable functions. Slides are here.

Problem Set 10 is now released. You can find the Overlead link in the PDF.

Apr 15, 2025

Older announcements:

Tentative syllabus posted

The enrollment is starting soon. Please take a look at the syllabus if you have any questions (and be forgiving if something changes later).

Oct 27, 2024.