6. Theory of computing. (8 points) You are in the final round of a job interview at a post-factual political-tech startup. Your interviewer asks you to classify various claims made by different companies as - old news (known to be mathematically true) - alternative fact (known to be mathematically false) - truthiness (implies that P=NP ) - fake news (implies that the Church-Turing thesis is false) For each claim, choose the best-matching letter on the right. B Adobe publishes 2+2=5. A. True (old news) Twitter tweetstorms a poly-time algorithm for TsP. B. False (alternative fact) Facebook posts that SAT is NP-complete. C. Implies that P=NP (truthiness) Tumblr blogs an exponential-time algorithm for SAT. D. Implies that the ChurchTuring thesis is false (fake news) YouTube broadcasts that SorTING poly-time reduces to SAT. Google advertises that SAT poly-time reduces to SorTING. WikiLeaks reveals a formal language that can be described by some regular expression but cannot be recognized by any DFA. Apple releases a poly-time algorithm that solves the halting problem. This revolutionary algorithm runs only on OS X. SpaceX touts a physically realizable computing device that harnesses the power of black holes to solve the halting