Report writing on NP (hard,complete), NL, POLYLOGSPACE etc -- 2
Budget: ₹1,500 – ₹12,500 INR
Parallel Complexity Theory
This challenge asks you to describe the main part of the parallel computation complexity theory by
considering the relation between P and PLOYLOGSPACE. To do so, you must define the notion of
P-complete problems. A further wrinkle is that the two examples of complete problems presented
earlier feature two complexity classes arranged in a neat hierarchy (one being included in the
other). Here, there is no known relation between P and POLYLOGSPACE, in fact it is widely
believed that the two are not comparable. The concept of a reduction must therefore rely on a
third class that is a subset of both. The first question of this challenge will establish such a class:
Question 1 Prove that NL ⊆ P and NL ⊆ POLYLOGSPACE.
Hint. One of the two inclusions is trivial. For the other one, let π ∈ NL be a decision problem and
let w be some input for π. Consider all the possible contents of the storage plus the current output
4
(which can be true, false, or “not yet determined”) for an algorithm solving π and working on w.
How many such possible “configurations” do we have? Now arrange these configurations in a
graph so that there exists an edge between configuration ci and configuration cj
if any only if cj
can be reached from ci
in a single computation step according to the algorithm that solves π. Will
traversing this graph allow us to obtain the answer to our problem? If so, how much time will the
traversal take?
Now that we have an “inner” class we can proceed with defining a suitable reduction:
Question 2 Define reductions for the purpose of defining complete problems for the class P. Explain carefully how are your reductions closed under functional composition.
Hint. Could it be that your reductions feature space restrictions? If so, it is quite possible that
the allowed space is not enough for storing intermediate results. That is, you cannot just compute
τπ1→π2
(w) and then run τπ2→π3
on the result simply because there is not enough space to store that
result. If this is the case then you need to be creative and compute τπ1→π2
(w) piecemeal instead
of all at once. Note that during this process it is likely that you have no restriction on the running
time (just on space).
Finally, we get to define P-complete problems:
Question 3 Define the class of P-complete problems. Explain carefully how showing that a Pcomplete problem is in PLOYLOGSPACE results in the whole class P being included in
POLYLOGSPACE. Explain the practical consequences of finding that P-complete problems
are or are not in POLYLOGSPACE.
OUTPUT:
Your mission is to write a report that contains these three chapters (the rest of the thesis described above is left as an exercise for the interested reader). The first two are straightforward,
while the third should contain your answer to the three questions from the previous section and
also any additional concepts and results that are related to the topic at hand; it is your responsibility to find those, including but certainly not limited to examples of P-complete problems and
their practical significance.
Ping for more details
This challenge asks you to describe the main part of the parallel computation complexity theory by
considering the relation between P and PLOYLOGSPACE. To do so, you must define the notion of
P-complete problems. A further wrinkle is that the two examples of complete problems presented
earlier feature two complexity classes arranged in a neat hierarchy (one being included in the
other). Here, there is no known relation between P and POLYLOGSPACE, in fact it is widely
believed that the two are not comparable. The concept of a reduction must therefore rely on a
third class that is a subset of both. The first question of this challenge will establish such a class:
Question 1 Prove that NL ⊆ P and NL ⊆ POLYLOGSPACE.
Hint. One of the two inclusions is trivial. For the other one, let π ∈ NL be a decision problem and
let w be some input for π. Consider all the possible contents of the storage plus the current output
4
(which can be true, false, or “not yet determined”) for an algorithm solving π and working on w.
How many such possible “configurations” do we have? Now arrange these configurations in a
graph so that there exists an edge between configuration ci and configuration cj
if any only if cj
can be reached from ci
in a single computation step according to the algorithm that solves π. Will
traversing this graph allow us to obtain the answer to our problem? If so, how much time will the
traversal take?
Now that we have an “inner” class we can proceed with defining a suitable reduction:
Question 2 Define reductions for the purpose of defining complete problems for the class P. Explain carefully how are your reductions closed under functional composition.
Hint. Could it be that your reductions feature space restrictions? If so, it is quite possible that
the allowed space is not enough for storing intermediate results. That is, you cannot just compute
τπ1→π2
(w) and then run τπ2→π3
on the result simply because there is not enough space to store that
result. If this is the case then you need to be creative and compute τπ1→π2
(w) piecemeal instead
of all at once. Note that during this process it is likely that you have no restriction on the running
time (just on space).
Finally, we get to define P-complete problems:
Question 3 Define the class of P-complete problems. Explain carefully how showing that a Pcomplete problem is in PLOYLOGSPACE results in the whole class P being included in
POLYLOGSPACE. Explain the practical consequences of finding that P-complete problems
are or are not in POLYLOGSPACE.
OUTPUT:
Your mission is to write a report that contains these three chapters (the rest of the thesis described above is left as an exercise for the interested reader). The first two are straightforward,
while the third should contain your answer to the three questions from the previous section and
also any additional concepts and results that are related to the topic at hand; it is your responsibility to find those, including but certainly not limited to examples of P-complete problems and
their practical significance.
Ping for more details