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_{1}, ...,
n_{k}) and h(n_{1}, ..., n_{k}, m, f), we
can construct a new function f(n_{1}, ..., n_{k},
m) as follows:
f(n_{1}, ..., n_{k}, 0) = g(n_{1}, ...,
n_{k});
f(n_{1}, ..., n_{k}, m + 1) =
h(n_{1}, ..., n_{k}, m, f(n_{1}, ...,
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:
Predicate: a function f(n_{1}, ..., 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_{1}, ...,
n_{k}), we can define a new function
f(n_{1}, ...,
n_{k}) = μm.P(m, n_{1}, ..., n_{k})
meaning
the smallest natural number m for which the predicate P(m,
n_{1}, ..., 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:
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_{1} & ... & 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:
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 s_{1}, ..., 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_{1}, ..., s_{n}, and S, find values x_{1}, ..., x_{n} from {0, 1} for which x_{1} * s_{1} + ... + x_{n} * s_{n} = S.
Comment: the subset sum problem is also known as the exact change problem.
Ali-Baba problem: given:
Comment: the Ali-Baba problem is also known as the knapsack problem.
Interval computations problem: Given:
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_{1},
..., x_{n} for which the following inequalities hold:
a_{11} * x_{1} + ... + a_{1n} *
x_{n} ≤ b_{1}
a_{21} *
x_{1} + ... + a_{2n} * x_{n} ≤
b_{2}
...
a_{i1} * x_{1} + ... +
a_{in} * x_{n} ≤ b_{i}
...
a_{m1} * x_{1} + ... + 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_{1} & ... & C_{m}, where each C_{i} has the form a \/ b, and a, b, c are literals.
Σ_{n}P: the class of all deciding problems of the type ∃x_{1} ∀x_{2} A(x_{1}, x_{2}, ...), where xi are strings of polynomial length, we have n quantifiers, and A(x_{1}, x_{2}, ...) is a feasible predicate.
Π_{n}P: the class of all deciding problems of the type ∀x_{1} ∃x_{2} A(x_{1}, x_{2}, ...), where xi are strings of polynomial length, we have n quantifiers, and A(x_{1}, x_{2}, ...) is a feasible predicate.
Computing with an oracle A: computations in which any call to A is counted as just one step.