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