Computational Complexity and Computability
Lecture 10 – Some More Decidable & Undecidable Problems
Koushik Pal
University of Toronto
February 10, 2021
Kolmogorov Complexity
Definition
Let x ∈ {,}∗.
The minimal description of x, denoted d(x), is the lexicographically shortest string ⟨M,w⟩ such that M is a TM that on input w halts with only x on its tape.
The descriptive complexity (also known as Kolmogorov complexity) of x, denoted K(x), is the length of the minimal description of x, i.e.,
K(x) = |d(x)|.
Incompressible Strings Definition
A binary string x is incompressible if K(x) ≥ |x|.
Theorem
Foralln≥,thereisanx∈{,}n suchthatK(x)≥n. (Incompressible strings of every length exist.)
Proof.
Since each description is itself a binary string, the number of descriptions of length less than n is at most the sum of the number of strings of each length up to n − , i.e.,
i =++++···+n− =n −. ≤i≤n−
But the total number of binary strings of length n is n. Hence, at least one string of length n is incompressible.
Incompressible Strings
Definition
Let INCOMP = {x ∈ {,}∗ | K(x) ≥ |x|} be the set of incompressible strings.
Theorem
INCOMP is undecidable.
Intuition: If INCOMP were decidable, we could design an algorithm that prints the first incompressible string of length n. But then such a string could be succinctly described by giving the algorithm and n in binary.
Berry’s Paradox: “The smallest integer that cannot be defined in less than thirteen words.”
Incompressible Strings
Proof.
Assume, for a contradiction, that M is a decider for INCOMP. Define a new TM M′ as follows:
On input ⟨n⟩:
Generate strings s of length n lexicographically
Simulate M on s; if M accepts s, halt with s on the
tape.
Let sn ∈ {, }n be the output of M ′ on ⟨n⟩. Then, M accepts sn. Hence, K(sn) ≥ n.
Conversely, ⟨M′,⟨n⟩⟩ is a description of sn. Hence,
K (sn ) ≤ |⟨M ′ , ⟨n⟩⟩| ≤ |⟨M ′ ⟩| + ⌈log n⌉ + ≤ log n + c,
where c = |⟨M′⟩| + is a constant.
Choosing n large enough so that log n + c < n yields the required contradiction.
Exercise: INCOMP ∈ coSD.
Incompressible Strings
Theorem
INCOMP does not contain any infinite subset that is Turing recognizable.
Theorem
The function K is not computable.
So we have no way to obtain long incompressible strings, and no way to determine whether a given string is incompressible.
A super quick introduction to Mathematical Logic
A first order language L consists of
Variables, e.g., x, x, . . .
Constants, e.g., c, . . . , cn
Relation Symbols, e.g., R, . . . , Rk
Function Symbols, e.g., f, . . . , fl
Boolean operators, e.g., ∧, ∨, ¬, =⇒ Quantifiers, e.g., ∀, ∃
Using these, one can inductively define L-formulas and L-sentences (L-formulas without free variables).
An L-theory T is simply a set of L-sentences.
By Th(M,c,...,cn,R,...,Rk,f,...,fl) we mean the set of
L-sentences that hold true in the universe M. For example, ∀x∃y(x + x ≤ y) ∈ T h(N, ≤, +).
List of decidable problems
Th(Q,<)
T h(N, , , +) (Presburger arithmetic) Th(Q,,+)
Th(R,,,+,×)
Th(C,,,+,×)
List of
undecidable problems
Th(N,,,+,×)(TrueArithmetic)
Hilbert’s Tenth Problem: Given a Diophantine equation (multivariable polynomial equation with integer coefficients), is there an algorithm to decide if it has a solution in integers? Post Correspondance Problem: Given a collection of dominos
P =a,...,ak,isthereanalgorithmtodecideif b bk
there is a match, i.e., a sequence i, . . . , il such that
ai ···ail = bi ···bil?
Wang Tiling Problem: Given a set of square tiles with a color on each side, is there an algorithm to decide whether they can tile the whole plane, where tiling requires that the tiles cannot be rotated or reflected and two adjacent tiles must have matching colors?
Matrix Mortality Problem: Given a finite set of n × n matrices with integer entries, is there an algorithm to decide if they can be multiplied in some order, possibly with repetition, to yield the zero matrix?
PhD Thesis
Theorem (Pal, 2011)
Let K = (K, Γ, k; v, π, s, σ) be a multiplicative valued difference field. The theory of K is decidable (in a 3-sorted language Lvdfs) if and only if the theories of Γ and k are decidable.