9. (10 pts) Prove or disprove that for any language Lut S, 3SAT and 3SAT S, L. Lis XP-complete, Justify your answer 10.

[answerhappygod]

9 10 Pts Prove Or Disprove That For Any Language Lut S 3sat And 3sat S L Lis Xp Complete Justify Your Answer 10 1 (34.16 KiB) Viewed 50 times

9. (10 pts) Prove or disprove that for any language Lut S, 3SAT and 3SAT S, L. Lis XP-complete, Justify your answer 10. (10 pts) Let L = { € (0.1}{whas the same number of O's and 1's). Consider the fol- lowing algorithm that decides L. AT = "In input 1. Scan across the tape until a 0 or 1 is found. 2. If none is found. accept. 3. If one is found, continue scanning until a matching 1 or 0 is found. If none is found, reject. 5. Otherwise, cross off that symbol and repeat." Using the Big-O notation, state the time complexity of each step of M, and the overall time complexity of M.