Is it countable?
Sigma Star!
Yes!
k-COL = {(G, k) | G is a k-colorable graph}
Yep!
Is this decidable?
EMPTY-HALTS = {(M) : M is a TM that halts on the empty string}
Undecidable!
What variable are we inducting over in structural induction?
The number of recursive rule calls
Turkish (the set of any text in Turkish)
Countable! It's a subset of sigma star...
CVP = {(C, I) : C is a boolean circuit, I is an input, and C(I) true}
This is actually P-complete! So not NP-complete...
Is this decidable?
Entscheidungsproblem
This is a classic old-timey example of an undecidable language.
If f(n) = O(g(n)), then does g(n) = Omega(f(n))?
Yep! These are the same definition.
The set of all infinite length unary (one character) strings.
{0}^infinity
Yes! This has one element:
000000000000...
Prime factorization
Nope! The decision problem version of prime factorization has not been proven to be NP-hard.
Cryptography is scary...
Is this semi-decidable?
L = {M : M is a Turing machine that runs in more than 100 steps on some inputs}
Yep! Have a Turing Machine simulate every string iteratively on 101 steps, it will accept eventually for any TM (encoding) in the language.
What're the two conditions of an augmenting path?
1 - Alternating path
2 - Vertices on each end not in the matching
The set of all irregular (non-regular) languages
Nope! The set of all regular languages is countable, so for the set of all languages to be uncountable the non-regular languages must be uncountable.
2-SAT
Nope -- the 2-SAT problem is in P!
L = {x : x is a semantically valid sentence in the English language}
Undecidable! A (bad) proof of this here: https://blogs.perl.org/users/jeffrey_kegler/2012/03/the-syntax-of-english-is-undecidable.html
Has to do with understanding semantics.
What's the difference between a path and a walk in graphs?
A path is a walk without repeated vertices.
The set of ways to cut a pizza into even slices, given an infinitely precise pizza cutter.
Countable! This can be injected to the rationals (as there's always a rational fraction of the pizza per slice!)
n-Queens Completion Problem: "Given an n × n chessboard on which some queens are already placed, can you place a queen in every remaining row so that no two queens attack each other?"
This is NP-complete! It's been shown with a sequence of complicated reductions here: https://www-users.cs.york.ac.uk/pwn503/n-queens-jair.pdf
Name an incomputable function (a function which cannot be computed by any TM!). No decision problems allowed!
f(x) = max no. steps any TM of x states runs on the empty string, without running forever
What are 2 things we prove via diagonalization in the textbook?
- Cantor's Theorem
- Irrational numbers are uncountable
- Finding explicit undecidable language