Main Results Covered in the Theory of Computation Course

1. There exists a computable function which is not primitive recursive.

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 ≥ Tseq(n), then its parallel computation requires time Tpar(n) at least const * (Tseq(n))1/4:
Tpar(n) ≥ const * (Tseq(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.