Recall that primality testing was proved to be in P, O(n^6) via the AKS primality test, but in practice it's much too slow. So if something interesting is in P, but it's O(n^100), what good is that?
With a bit of luck you might also be able to come up with a scheme to generate optimal nonuniform circuits for smaller problem sizes, which would ammortize nicely if you had enough of the smaller instances to solve.
As an example, the knapsack problem with n objects and weight W is solvable in O(n*W) time, but it's known to be NP-hard. This doesn't prove P=NP, because W is exponential in its length. This is called a pseudopolynomial algorithm.
Coincidental too since I just read about the AKS algorithm on Terrence Tao's blog. http://terrytao.wordpress.com/2009/08/11/the-aks-primality-t...