I think pascal_cuoq's argument still works though. As I understood it, his construction was Given an instance x of some NP relation R: 1. Enumerate all (T

I think pascal_cuoq's argument still works though. As I understood it, his construction was Given an instance x of some NP relation R: 1. Enumerate all (TM, π) pairs until we encounter a π which proves that TM is a correct polynomial time solution to R. 2. Simulate TM on the given instance x. The first step depends only on R, not x, so it takes constant time with respect to the instance size.