Reference no: EM132294362
Problem 1 - Tjuring machine running time
Let's look at the computational problem L: L(x) = 1, if input date x is in the form y#z, where y and z are strings of the same length. The strings consist of the symbols a and b. This Tjuring machine works as follows:
Repeats the sequence of actions:
i. If first symbol is #, then move one symbol to the right. If there is blank, then accepts word, else reject word.
ii. If first symbol is blank, reject word.
iii. If first symbol is a or b, then:
a. clears this symbol and replaces it by blank;
b. move to the right until reach blank after end of the word;
c. move one symbol to the left. If there is a or b, clear it, replacing by blank;
d. move to the left until reach blank symbol;
e. move one step to the right (thus reaching the first non-cleared symbol of the word).
Let's evaluate working time of Tjuring machine. It is enough with evaluation "Time is O(f(n))", where f(n) is a function of some complexity (for example f(n)=n or n^2), bet it must be justified.
Problem 2 - CUT
Let's look at graph problem 3-CUT (maximum slit), where given graph G and number k. It is necessary to determine if it is possible to divide graph vertices into three sets A, B and C. Facets uv have one destination u, that belongs to one set, but second destination v belongs to another set. Facets uv must to be at least k.
Let's look at naive algorithm for this problem, which works as follows (Let n be the number of vertices, but v1,...,vn to be vertices):
For every x1 ∈ {1,2,3}, x2 ∈ {1,2,3}, . . . , xn ∈ {1,2,3}:
- take the division, where set A includes vertices vi, where xi=1, set B includes vertices vi, where xi=2 and set C includes vertices vi, where xi=3;
- m=0;
- for each facet uv: if u and v are in different sets, then m=m+1;
- if ≥k, then issues answer "yes".
If division A, B, C, where m ≥ k not found, then issues answer "No".
Let's evaluate working time of this algorithm in the form "Time is O(f(n))". Computing model: let's perceive one pseudo-code line as one action.