Exercise 4 (1 pt for each correct answer). For each statement indicate whether i
ID: 3704564 • Letter: E
Question
Exercise 4 (1 pt for each correct answer). For each statement indicate whether it is true, 1. There exists a polynomial-time algorithm that determines whether a given integer is 2. There exists a polynomial-time algorithm that for each integer n, finds two prime false, or unknown. prime or not. True? False? Unknown? numbers p and q such that n p. True? False? Unknown? 3. If one-way functions exist, then there exists a polynomial-time algorithm that deter- mines whether a given Boolean formula is satisfiable or not. True? False? Unknown? Computationally Merlin can convince polynomially bounded unlimited Arthur that a given Boolean formula is unsatisfiable. Or, more formally, there exists an interactive proof system for the set of all unsatisfiable Boolean formulas. True False? Unknown?Explanation / Answer
1. True, there exists a polynomial time algorithm
2. True, there exists a polynomial time algorithm
3.true, there exists a polynomial time algorithm
4. False no there does not exist a polynomial time algorithm
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.