There's a question on SE cstheory site that addresses the more general problem [0]. I wonder if this problem is still open.

[0] https://cstheory.stackexchange.com/questions/5861/asymptotic...