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.
30. Linear programming is P-complete.
Comment: this result is presented without proof.
31. If we take into account communication time, then a
problem whose sequential computation requires time ≥
Tseq(n), then its parallel computation requires time
Tpar(n) at least const
* (Tseq(n))1/4:
Tpar(n) ≥ const
* (Tseq(n))1/4.
32. (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.
33. Kolmogorov complexity is not computable.
34. 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.
35. 4-coloring problem is NP-hard.
36. There exists a polynomial-time algorithm for checking satisfiability of 2-SAT formulas.