Prove that polynomial-time reducibility is transitive: that is, if L1is polynomial-time-reducible to L2, and L2 is polynomial-time-reducible to L3, then L1 is polynomial-time-reducible to L3.
Answer:-------------
If L1 ≤P L2 and L2 ≤P L3 then L1 ≤P L3
Proof.----------
If f is a polynomial time reduction from L1 to
L2 running in time
nk and g is a polynomial time reduction
from L2 to L3 computed in
time nm then g ◦ f is
a reduction from L1 to
L3
and can be computed in time O(nk +
(nk)m ) =
O(nkm).
Hence Proved.
Prove that polynomial-time reducibility is transitive: that is, if L1is polynomial-time-reducible to L2, and L2 is...
Prove that polynomial-time reducibility is transitive: that is, if L1is polynomial-time-reducible to L2, and L2 is polynomial-time-reducible to L3, then L1 is polynomial-time-reducible to L3.
2. (a) Prove the transitive property for polynomial-time mapping reductions (b) Using the transitivity, show that if A Sp B and A is NP-Hard, then B is NP-Hard as well
For Language L1 and L2 prove or disprove (L1 union L2)*=L1* intersection L2*
a) if L1 is recognisable but not decidable, L2 is decidable but not recognisable, then prove L1 U L2 is undecidable? b) if L1 is recognisable but not decidable, L2 is recognisable but not decidable, then prove L1 U L2 is undecidable?
Prove that If L1 is linear and L2 is regular, L1×L2 is a linear Language.
L1 and L2 are lists. L3 = L1 + L2 This is an example of mutation of L is this true or false?
Let L1 = {ω|ω begins with a 1 and ends with a 0}, L2 = {ω|ω has length at least 3 and its third symbol is a 0}, and L3 = {ω| every odd position of ω is a 1} where L1, L2, and L3 are all languages over the alphabet {0, 1}. Draw finite automata (may be NFA) for L1, L2, and L3 and for each of the following (note: L means complement of L): Let L w begins...
Given sigma={a, b} And languages L1, L2 contain in sigma^* I need to prove/disprove the following claim:
Given sigma={a, b} And languages L1, L2 contain in sigma^* I need to prove/disprove the following claim: