## Definitions Used in Theory of Computations Course

Church-Turing thesis: anything that can be computed on any computational device can also be computed on a Turing machine.

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(n1, ..., nk) and h(n1, ..., nk, m, f), we can construct a new function f(n1, ..., nk, m) as follows:
f(n1, ..., nk, 0) = g(n1, ..., nk);
f(n1, ..., nk, m + 1) = h(n1, ..., nk, m, f(n1, ..., nk, 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 πki by using composition and primitive recursion.

Comment: 0, σ, and πki denote the following functions:

• 0(n1, ..., nk) = 0;
• σ(n) = n + 1;
• πki(n1, ..., ni-1, ni, ni+1, ..., nk) = ni.

Predicate: a function f(n1, ..., nk) 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, n1, ..., nk), we can define a new function
f(n1, ..., nk) = μm.P(m, n1, ..., nk)
meaning the smallest natural number m for which the predicate P(m, n1, ..., nk) is true.

μ-recursive function: A function is called μ-recursive if it can be obtained from 0, σ, and πki 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 tA(x) of A on any inputs x is bounded by P(len(x)):
tA(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, Pl), 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
• Pl is a polynomial.
By an instance of this problem, we mean the following problem:
• given x,
• find y for which C(x,y) is true and len(y) ≤ Pl(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 C1 & ... & Cm, where each Ci 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:

• U1 from x to x',
• U2 from y' to y, and
• U3 from y to y'
• if C'(U1(x), y') is true then C(x, U2(y')) is true;
• if C(x, y) is true, then C'(U1(x), U3(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: a subgraph in which every two vertices are connected by an edge.

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 s1, ..., sn, and S, find a subset of the n-numbers set whose sum is S.

Subset sum problem, equivalent formulation: given natural numbers s1, ..., sn, and S, find values x1, ..., xn from {0, 1} for which x1 * s1 + ... + xn * sn = S.

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

Ali-Baba problem: given:

• natural numbers w1, ..., wn, and W, and
• natural numbers v1, ..., vn, and V,
find values x1, ..., xn from {0, 1} for which the following two inequalities hold:
• x1 * w1 + ... + xn * wn ≤ W;
• x1 * v1 + ... + xn * vn ≥ V.

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

Interval computations problem: Given:

• a polynomial f(x1, ..., xn), and
• n rational-valued intervals [xi, x+i],
compute the endpoints y and y+ of the range
[y, y+] = {f(x1, ..., xn): xi is in [xi, x+i] for all 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 tA(x) of the algorithm A on the input x is bounded by P(ln(len(x)):
tA(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 aij and bj, find the values x1, ..., xn for which the following inequalities hold:
a11 * x1 + ... + a1n * xn ≤ b1
a21 * x1 + ... + a2n * xn ≤ b2
...
ai1 * x1 + ... + ain * xn ≤ bi
...
am1 * x1 + ... + amn * xn ≤ bm

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 Ui are feasible, we require that the corresponding algorithms Ui 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 C1 & ... & Cm, where each Ci has the form a \/ b, and a, b, c are literals.

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

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

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