Please type your solution very clearly
- Theory Of Computation Please Type Your Solution Very Clearly 1 (81.58 KiB) Viewed 63 times
Theory of Computation. Please type your solution very clearly
-
answerhappygod
- Site Admin
- Posts: 899603
- Joined: Mon Aug 02, 2021 8:13 am
Theory of Computation. Please type your solution very clearly
Theory of Computation.
Please type your solution very clearly
For two numbers a and b, the least common multiple (lcm) is the smallest number m such that both a and b are factors of m. For example lcm(18, 12) = 36 because it's the smallest number that has both 18 and 12 as factors. Formally, we will work with the following decision problem LCM = {{a,b, k)|lcm(a, b) = k} Note that a, b, k are all represented in binary. (a) (5 points) Explain why the following algorithm to decide L does not run in polynomial time 1. Check if k is a multiple of both a and b; if it's not, reject (a, b, k) 2. For i = 1, 2, ... k – 1 do the following: a. If i is a multiple of both a and b, we've found a smaller multiple. Reject (a, b, k) 3. If we reach finish the loop without finding a smaller multiple, accept (a, b, k) a. 6 (b) (10 points) Prove that LCM EP. You may use without proof the fact that lcm(a,b) gcd(a,b)
Please type your solution very clearly
For two numbers a and b, the least common multiple (lcm) is the smallest number m such that both a and b are factors of m. For example lcm(18, 12) = 36 because it's the smallest number that has both 18 and 12 as factors. Formally, we will work with the following decision problem LCM = {{a,b, k)|lcm(a, b) = k} Note that a, b, k are all represented in binary. (a) (5 points) Explain why the following algorithm to decide L does not run in polynomial time 1. Check if k is a multiple of both a and b; if it's not, reject (a, b, k) 2. For i = 1, 2, ... k – 1 do the following: a. If i is a multiple of both a and b, we've found a smaller multiple. Reject (a, b, k) 3. If we reach finish the loop without finding a smaller multiple, accept (a, b, k) a. 6 (b) (10 points) Prove that LCM EP. You may use without proof the fact that lcm(a,b) gcd(a,b)