**2.** Functions computable on Turing machines are exactly
μ-recursive functions.

**3.** No algorithm is possible that, given a program p and input d,
checks whether p halts on d.

**4.** No algorithm is possible that, given a program p that always
halts, checks whether this program always returns 0.

**5.** For any computable function f(n), no algorithm is possible
that, given a program p that always halts, checks whether this
program always returns f(n).

**6.** Empty set and the set N of all natural numbers are
decidable.

**7.** Every finite set is decidable.

**8.** Union of two decidable sets is decidable.

**9.** Intersection of two decidable sets is decidable.

**10.** A complement to a decidable set is decidable.

**11.** Every decidable set is r.e.

**12.** Empty set and the set N of all natural numbers are r.e.

**13.** Every finite set is r.e.

**14.** Union of two r.e. sets is r.e.

**15.** Intersection of two r.e. sets is r.e.

**16.** If a set and its complement are both r.e. that this set is
decidable.

**17.** There exists a r.e. set which is not decidable.

**18.** There exists a r.e. set whose complement is not r.e.

**19.** Propositional satisfiability is NP-hard.

**20.** 3-SAT is NP-hard.

**21.** 3-coloring problem is NP-hard.

**22.** Clique problem is NP-hard.

**23.** Subset sum problem is NP-hard.

**24.** The knapsack problem is NP-hard.

**25.** Interval computation problem is NP-hard.

**26.** Addition of n numbers is in NC.

**27.** Computation of a dot produce is in NC

**28.** Matrix multiplication is in NC.

**29.** The class NC is a subset of the class P.

**20.** Linear programming is P-complete.

*Comment:* this result is presented without proof.

**21.** If we take into account communication time, then a
problem whose sequential computation requires time ≥
T_{seq}(n), then its parallel computation requires time
T_{par}(n) at least const
* (T_{seq}(n))^{1/4}:

T_{par}(n) ≥ const
* (T_{seq}(n))^{1/4}.

**22.** (If we take into account communication time.) If a
problem can be solved in polynomial time on a parallel computer,
then it can also be solved in polynomial time on a sequential
computer.

**23.** Kolmogorov complexity is not computable.

**24.** There exists a quantum algorithm that can check whether
a bit-valued function f(x) of a 1-bit variable x is constant or
not.

**25.** 4-coloring problem is NP-hard.