complexity of computing polynomials proof

From: Ken (kpayson_at_gmail.com)
Date: 10/16/04

  • Next message: Kent Paul Dolan: "Re: complexity of computing polynomials proof" 
    Date: 15 Oct 2004 22:31:28 -0700

    I'd like a formal proof of the following obvious sounding statement.

    Let C_i be the class of decision problems defined as input <a
    Polynomial Q of degree i, an integer a, an integer t> return true if
    Q(a) = t

    Let A_i be the best possible algorithm for C_i the running time of A_i
    can be written as O(n^f(i))

    Prove that lim i->infinity f(i) = infinity. How is this proved? Does
    this follow from polynomial time hierachy theorems?

    Much Thanks in Advance,
    Ken

  • Next message: Kent Paul Dolan: "Re: complexity of computing polynomials proof"