Nondeterminism

Register Machines

Iteration 

Closure

Zero Space

Minimization

First-order logic

Logic

Infinite Words

Groups

Polya Counting

Feedback Shift Registers

Coding Theory

Effective Resistance

Hypercomputation

Decidability

Computation & Discrete Math

Primitive Recursion

Orbits

Automata

Determinization

Finite Fields

15-354 Computation & Discrete Math Carnegie Mellon University Spring 2021 This advanced course reexamines traditional concepts of discrete mathematics (relations, functions, logic, graphs, algebra, automata) in the context of computation and algorithms, necessitating a strong background in discrete math. In a nutshell, the main idea behind this course is that the development of the digital computer, together with the theory of computation, is also one of the most important developments in mathematics in the 20th century. Consequently, this course takes a fresh look at some of the standard concepts of discrete mathematics (relations, functions, logic, graphs, algebra, automata), with strong and consistent emphasis on computation and algorithms. Another key concern is knowledge transfer: we need to realign traditional mathematical concepts with our new computational universe and find ways to apply ideas from one realm to the other. We begin with a brief introduction to computability and computational complexity. Other topics may include: iteration, orbits and fixed points; order and equivalence relations; transition systems; groups and actions; finite fields, randomness; propositional logic and satisfiability testing.

To get a better impression, take a look at some of the homework problems that were used in previous versions of this course: [CDM Assignments](https://www.cs.cmu.edu/~sutner/CDM/notes/hw-master-nosol.pdf). A few pictures can be found here: [CDM Gallery](https://www.cs.cmu.edu/~sutner/CDM/bilder.html) (challenge: figure out what these pictures mean, for as many as you can manage). A slightly dated paper outlining the course philosophy can be found at [Jeric](http://www.cs.cmu.edu/~sutner/papers/JERIC05.pdf).

Needless to say, a solid background in discrete math is necessary for this course. You should feel very much at home with all the 15-251 material.   

15-354 Computation & Discrete Math

Mathematical Foundations

Fundamental Results

Polynomial Time

Cook-Levin Theorem

Smalll Space

Polynomial Hierarchy

Probabilistic Classes

Reversible Computation

Turing Machines

Completeness

Ladner's Theorem

Counting

Randomness

Circuit Complexity

Complexity Theory

Hardness

Satisfiabilty

Karp's List

Polynomial Space

Kolmogorov complexity

Interactive Proofs

Computability

Time Complexity

P/NP

Space Complexity

Immerman–Szelepcsényi theorem

Randomized Algorithms

Descriptive complexity theory

15-455 Undergraduate Complexity Theory Carnegie Mellon University Spring 2023 This course provides an initial dive into complexity theory, exploring computations bound by resources like time, space, and energy. Emphasis is placed on low complexity classes.  This course provides a gentle introduction into complexity theory, the theory of computations that are restricted by various resource bounds (time, space, energy, ...). We start with a brief tour of the computational universe at large and then home in on the low complexity classes that are most relevant in theoretical computer science such as P, NP, PSPACE. LOG,NLOG, BPP, RP and circuit-based classes.   

15-455 Undergraduate Complexity Theory

Theoretical Computer Science

Nondeterminism

2 courses cover this concept

15-354 Computation & Discrete Math

15-455 Undergraduate Complexity Theory