**Answer:** When we encounter several similar practical
problems, it is often beneficial not to solve them one by one, but
to find a general algorithm that would enable us to solve all
these problems.

How general should it be? Sometimes, practitioners try to solve the problems in such a generality that no general algorithm is possible -- and, of course, do not succeed. To avoid wasting time on such impossible efforts, it is desirable to know which problem can be algorithmically solved and which cannot. Understanding which problems can be algorithmically solved is one of the main objectives of theory of computation.

In situations when an algorithm is, in principle, possible, sometimes, the only possible algorithms requires so much computation time -- e.g., longer than the lifetime of the Universe -- that they are not practically feasible. It is therefore desirable to know if the given problem can be feasibly solved. This is also one of the main objectives of theory of computation.

Similarly, it may seem reasonable to look for a general algorithm that, given a program that always halts, checks whether this program always produces the correct result -- but theory proves that such algorithms are not possible either.

**Question:** Why do we need to study primitive recursive
functions?

**Answer:** Primitive recursive functions describe for-loops.
The advantage of using only for-loops in a program is that such
programs always halt, never go into an infinite loop. It is
therefore important to analyze whether a given task can be
computed by such a program.

**Question** Why do we need to study decidable and recursively
enumerable (r.e.) sets

For example, in set terms, union and intersection are natural operations. So, we can easily prove results about decidability of union and intersection.

**Question:** Why we do need to study Turing machines?

**Answer:** In many cases, we need to prove that some problem
is not algorithmically solvable. If by algorithm, we mean a Java
program, then, since Java programs can include many different
constructions, it is difficult to prove that none of these
constructions leads to the desired result.

However, it has been proven that what can be computed by a Java program can also be computed on a Turing machine. Thus, to prove that something is not computable, it is sufficient to prove that it is not computable on a Turing machine. Turing machines are much simpler than general programs, so proving that some problem cannot be solved on a Turing machine is often easier.

**Question:** Why is it interesting to study the propositional
satisfiability problem?

**Answer:** To satisfactorily test a program that contains
branching, we need to test both possible branches. In other words,
if we have a conditional statement of the type

if (P) ...
else ...,

we need to find the case when P is true. The
condition P can be a propositional combination of different
propositional variables. In this case, it is important to be able
to find the values of these variables that make P true. This is
exactly propositional satisfiability problem.

**Question:** What do we gain, from the practical viewpoint,
when we prove that a problem is NP-hard?

**Answer:** First, if a problem is NP-hard, then, unless P = NP
(which most computer scientists believe to be impossible), no
feasible algorithm is possible for solving all particular cases of
this problem. Thus, we should not waste time looking for such a
general algorithm.

Second, by definition, the fact that a problem is NP-hard means that every problem from the class NP can be reduced to it. Thus, if we have a good heuristic feasible algorithm for solving some particular cases of this problem, then reduction automatically generates algorithms for solving particular cases of all NP-problems. This reduction has been helpful in many cases.

**Question:** Why do we sometimes need to use probabilistic
methods and heuristic methods that do not always work?

**Answer:** When a problem is NP-hard, then, unless P=NP, no
feasible algorithm is possible that would always solve *all*
the instances of this problem. In this case, we are looking for
feasible algorithms that solve at least *some* instances;
this is why we study heuristic and probabilistic methods.

**Question:** Why is it interesting to study polynomial
hierarchy?

**Answer:** While many practical problems belong to the class
NP, there are many important practical problems which are not in
NP.

For example, the problem of finding an engineering design that
satisfies given specifications is in the class NP, since once a
design is presented, we can feasibly check whether it indeed
satisfies the specifications. So, the problem of checking the
existence of the desired design y takes the form ∃y A(y) for
a feasible predicate A(y), and thus, belongs to the class NP =
Σ_{1}P.

However, if we are looking for an *optimal* design -- e.g.,
the design whose cost is the smallest among all designs that
satisfy specifications -- then it is no longer clear how to check
that a given design in indeed optimal. The only general way to do
it to check that the given design y is better that all possible
designs z, i.e., that ∀z A(y, z) for a feasible property
A(y, z). So, the problem of checking the existence of such optimal
design y takes the form ∃y ∀y A(y, z) and thus,
belongs to the next class Σ_{2}P.

For games, the situation is even more complicated: e.g., if we
want to win in 3 steps, this means that we need to find a move x
such that for every opponent's move y, we will be able to find a
reply z that leads to a win. The existence of such a winning
strategy is equivalent to ∃x ∀y ∃z A(x, y, z),
and thus belongs to the class Σ_{3}P.

For more than 3 steps, we get even more complex formulas.

**Question:** Why do we need to study computing with
oracles?

**Answer:** Traditionally, the computational complexity of an
algorithm is determined by the number of its elementary steps.
This works well if we have written this algorithm from scratch
ourselves. However, in practice, we usually use others' methods as
subroutines. Even if we program in Java, we do not program, e.g.,
sin(x) ourselves: we rely on built-in methods for computing
special functions.

In general, many of these auxiliary methods are proprietary, we can only use them as black boxes -- we input a value, we get a result. Since we do not know how many elementary operations are preformed within this method, we therefore cannot estimate how many computational steps our algorithm takes. What we can do is count the number of our own elementary steps and the number of calls to these auxiliary methods.

Once we fix the list A of such auxiliary methods, we can thus
consider, e.g., the class of all the A-using algorithms for which
the number of our own steps + the number of calls to A is bounded
by a polynomial -- this is what is meant by the class
P^{A}, class of algorithms which are polynomial-time with
respect to the *oracle* A.