Definitions Used in Theory of Computations Course

Equivalent version of Church-Turing thesis: anything that can be computed on any computational device can also be computed by a Java program.

Primitive recursion: once we have functions g(n₁, ..., n_k) and h(n₁, ..., n_k, m, f), we can construct a new function f(n₁, ..., n_k, m) as follows:
f(n₁, ..., n_k, 0) = g(n₁, ..., n_k);
f(n₁, ..., n_k, m + 1) = h(n₁, ..., n_k, m, f(n₁, ..., n_k, m)).
We then say that f is obtained from g and h by primitive recursion and denote it by PR(g, h).

Primitive recursive (p.r.) function: A function is called primitive recursive if it can be obtained from 0, σ, and π^k_i by using composition and primitive recursion.

Comment: 0, σ, and π^k_i denote the following functions:

• 0(n₁, ..., n_k) = 0;
• σ(n) = n + 1;
• π^k_i(n₁, ..., n_i-1, n_i, n_i+1, ..., n_k) = n_i.

Predicate: a function f(n₁, ..., n_k) is called a predicate if for all the inputs, its values are 0 or 1.

Comment: 1 is interpreted as "true", 0 as "false".

μ-recursion: once we have a predicate P(m, n₁, ..., n_k), we can define a new function
f(n₁, ..., n_k) = μm.P(m, n₁, ..., n_k)
meaning the smallest natural number m for which the predicate P(m, n₁, ..., n_k) is true.

μ-recursive function: A function is called μ-recursive if it can be obtained from 0, σ, and π^k_i by using composition, primitive recursion, and μ-recursion.

Decidable set: a set S of natural numbers is called decidable if there exists an algorithm, that, given a natural number n, returns "true" or "false" depending on whether n is in S.

Recursively enumerable (r.e.) set: a set S of natural numbers if called recursively enumerable if there is an algorithm that eventually prints all elements of the set S (and no other elements).

Feasible algorithm: an algorithm A is called feasible if it is polynomial time, i.e., there exists a polynomial P(n) for which the running time t_A(x) of A on any inputs x is bounded by P(len(x)):
t_A(x) ≤ P(len(x)).

Comment: len(x) means the length of x, i.e., the number of bits in the computer representation of x.

NP, informal definition: we say that a problem belongs to the class NP if, once someone presents us with a possible solution, we can check, in polynomial time, whether this is indeed a solution.

Comment: NP stands for Non-deterministic Polynomial.

NP, formal definition: A problem from the class NP is a pair (C, P_l), where:

• C(x,y) is a feasible predicate, i.e., a feasible algorithm that, given two strings x and y, returns 1 or 0 ("true" or 'false"), and
• P_l is a polynomial.

• given x,
• find y for which C(x,y) is true and len(y) ≤ P_l(len(x)).

P: a class of all the problems from the class NP that can be solved in polynomial time.

Comment: P stands for Polynomial-time.

Propositional variable: a variable that can take only two values: true and false.

Literal: a propositional variable or its negation.

Propositional formula: any formula that can be obtained from propositional variables by using propositional connectives &, \/, and negation.

Propositional Satisfiability Problem (SAT): given a propositional formula x, find the values of the variables that make it true.

3-SAT: SAT for formulas of the type C₁ & ... & C_m, where each C_i has the form a \/ b or a \/ b \/ c, and a, b, c are literals.

Reduction: we say that a problem C can be reduced to a problem C' if there exist three feasible algorithms:

• U₁ from x to x',
• U₂ from y' to y, and
• U₃ from y to y'
• if C'(U₁(x), y') is true then C(x, U₂(y')) is true;
• if C(x, y) is true, then C'(U₁(x), U₃(y)) is also true.

NP-hard: a problem is called NP-hard if every problem from the class NP can be reduced to this problem.

NP-complete: a problem is called NP-complete if it is NP-hard and belongs to the class NP.

Graph coloring problem: given a (non-oriented) graph, find a coloring of all its vertices so that vertices connected by an edge have different colors.

3-coloring: the problem of coloring a graph in 3 colors.

A clique problem: give a graph and a natural number k, find a subgraph with k vertices which is a clique.

Subset sum problem: given natural numbers s₁, ..., s_n, and S, find a subset of the n-numbers set whose sum is S.

Subset sum problem, equivalent formulation: given natural numbers s₁, ..., s_n, and S, find values x₁, ..., x_n from {0, 1} for which x₁ * s₁ + ... + x_n * s_n = S.

Comment: the subset sum problem is also known as the exact change problem.

Ali-Baba problem: given:

• natural numbers w₁, ..., w_n, and W, and
• natural numbers v₁, ..., v_n, and V,

• x₁ * w₁ + ... + x_n * w_n ≤ W;
• x₁ * v₁ + ... + x_n * v_n ≥ V.

Comment: the Ali-Baba problem is also known as the knapsack problem.

Interval computations problem: Given:

• a polynomial f(x₁, ..., x_n), and
• n rational-valued intervals [x⁻_i, x⁺_i],

Polylog-time algorithm, informal definition: an algorithm whose computation time is bounded by a polynomial of the logarithm of the input size.

Polylog-time algorithm, formal definition: an algorithm A is called polylog-time if there exists a polynomial P(n) for which, for all inputs x, the computation time t_A(x) of the algorithm A on the input x is bounded by P(ln(len(x)):
t_A(x) ≤ P(ln(len(x)).

NC: the class of all problems that can be solved in polylog time on polynomial number of processors.

Comment: in contrast to meaningful abbreviations P and NP, the abbreviation NC simply stands for "Nick's class".

Linear programming, informal definition: find the values of the variables that make given linear inequalities true.

Linear programming, formal definition: given the values a_ij and b_j, find the values x₁, ..., x_n for which the following inequalities hold:
a₁₁ * x₁ + ... + a_1n * x_n ≤ b₁
a₂₁ * x₁ + ... + a_2n * x_n ≤ b₂
...
a_i1 * x₁ + ... + a_in * x_n ≤ b_i
...
a_m1 * x₁ + ... + a_mn * x_n ≤ b_m

P-hard: a problem is called P-hard if every problem from the class P can be reduced to this problem.

Comment: in this definition, the notion of reduction is similar to the previous definition, the difference is that instead of requiring that the algorithms U_i are feasible, we require that the corresponding algorithms U_i finish in polylog time on polynomial number of processors.

P-complete: a problem is called P-complete if it is P-hard and in the class P.

Kolmogorov complexity K(x) of a string x: the shortest length of the program p that computes x, i.e., K(x) = min{len(p): p computes x}.

2-SAT: SAT for formulas of the type C₁ & ... & C_m, where each C_i has the form a \/ b, and a, b, c are literals.

Σ_nP: the class of all deciding problems of the type ∃x₁ ∀x₂ A(x₁, x₂, ...), where xi are strings of polynomial length, we have n quantifiers, and A(x₁, x₂, ...) is a feasible predicate.

Π_nP: the class of all deciding problems of the type ∀x₁ ∃x₂ A(x₁, x₂, ...), where xi are strings of polynomial length, we have n quantifiers, and A(x₁, x₂, ...) is a feasible predicate.

Computing with an oracle A: computations in which any call to A is counted as just one step.