1. 3-SAT is SAT with the input instances restricted to Boolean expres- sions in clause form with at most 3 variables in each clause. Show that for 3-SAT the exhaustive search algorithm will take "expo- nential" time in the size of the input expression 2. The Tribonacci numbers satisfy the recurrence with the initial conditions to = 0, t1 = 1, t2 = 1. (a) Cite a Theorem to show that tn-6( ") where is the positive real root of z32 -r -1. (b) Draw a sketch of - 2 - z -1 d) What should you use as a starting point for your Newton compu tation? (Refer to your sketch.) (e) Compare the asymptotic growth rate of the Fibonacci numbers and the Tribonacci numbers. 1. 3-SAT is SAT with the input instances restricted to Boolean expres- sions in clause form with at most 3 variables in each clause. Show that for 3-SAT the exhaustive search algorithm will take "expo- nential" time in the size of the input expression 2. The Tribonacci numbers satisfy the recurrence with the initial conditions to = 0, t1 = 1, t2 = 1. (a) Cite a Theorem to show that tn-6( ") where is the positive real root of z32 -r -1. (b) Draw a sketch of - 2 - z -1 d) What should you use as a starting point for your Newton compu tation? (Refer to your sketch.) (e) Compare the asymptotic growth rate of the Fibonacci numbers and the Tribonacci numbers