Complexity Theory
- Determine complexity classes (NP complete, NP hard, …) for the following problems. Assume that NP is not equal P.
- For the following code, determine the nearest upper bound of complexity (O) and the nearest lower bound of complexity (Ω), if data is given by the following table. It is known that in the worst case the condition is satisfied in most cases.
- Determine the output of the following LEX/FLEX programs.
Solution
Determine complexity classes (NP complete, NP hard, …) for the following problems. Assume that NP is not equal P.
Solution : 1) It is similar like the traveling salesperson decision problem. Here we can consider city as node and transmission line between two city is edge hence it become complete connected graph GGand a cost kk and a candidate (a cycle that hits every vertex and costs less than or equal to kk) CC, we can quickly verify that CC has the same number of vertices as GG and that its cost is less than or equal to kk. Therefore, the decision version of the problem, TSP-DECIDE, is in NP. And since it's also in NP-Hard, TSP-DECIDE is NP-Complete. Here each edge can be part of transmission line or not hence it is in O(2n) 2) It is similar like shortest path problem which pass from all points mean it become Hamiltonian path and Hamiltonian path is np complete problem. To show that this problem is NP-complete we first need to show that it actually belongs to the class NP and then find a known NP-complete problem that can be reduced to Hamiltonian Path. For a given graph G we can solve Hamiltonian Path by non-deterministically choosing edges from G that are to be included in the path. Then we traverse the path and make sure that we visit each vertex exactly once. This obviously can be done in polynomial time, and hence, the problem belongs to NP. Now we have to an NP-complete problem that can be reduced to Hamiltonian Path. A closely related problem is the problem to determine whether a graph contains a Hamiltonian cycle, that is, a Hamiltonian path that begin and end in the same vertex. Moreover, we know that Hamiltonian Cycle is NP-complete, so we may try to reduce this problem to Hamiltonian Path. 3) Each person should know all other in set hence it is same as largest common point sets, if we consider person as node and relationship as an edge then we need to find largest complete sub graph from graph and finding complete sub graph is NP complete problem.
Solution:
- For the following code, determine the nearest upper bound of complexity (O) and the nearest lower bound of complexity (Ω), if data is given by the following table. It is known that in the worst case the condition is satisfied in most cases.
Solution: For f(g(i) and g(f(i) complexity is : O (nlogn) Outer for loop need O(logn) time and inner for loop need O(n) hence O(nlogn) Total time = O(n3(logn)2) and Omega (n(logn)3)
- Determine the output of the following LEX/FLEX programs.
INPUT: Look. A wizard. Here echo will print all char back to the output screen hence same output will print, same as input Output : Look. A wizard.
INPUT: 10 9 8 7 6 5 4 3 2 1 This is a sentence. OUTPUT: 1 9 8 7 6 5 4 3 2 1 This is a sentence. Here string then digit 0-2 then start Onlydigit then execute printf(“%c”, yytetext[0]) iftupas and hen char set then it will decrement counter and if counter is less than 4 then reject.
.
INPUT: Magna turba in via est.
here derp is start with a-zA-Z then 3 and any number of /
now if pattern match then check if condition else echo the character
here output is same as input
INPUT: This is a text. OUTPUT: : This is a text. Same as above example and output is same as input
INPUT: This is the number 345-567. OUTPUT: T
INPUT: 1 2 3 4 5 6 7 8 9 10 11 12
Here string then digit 0-2 then start only digit then execute printf(“%c”, yytetext[0]) iftupas and hen char set then it will decrement counter and if counter is less than 4 then reject.. . mean not matching then echo the character INPUT:
OUTPUT:
javarezultatjavafunkcija(javaint javaint1, javaint javaint2)
{
//java komentar.
return new javarezultat�nt1int2;
}