This proof works also for showing that NP is not equal to SPACE(n).

Artem, I don't understand why it would imply derandomization either, but as Ryan Williams said, it would be a very cool thing to prove. In my view, having that sort of thing would mean, informally, that all roads lead to derandomization of BPP, or that BPP is bound to be derandomized. Not only are some reasonable circuit lower bounds conditions for derandomization, but also the property of having a "syntactic characterization" (whatever that may mean formally)? That seems quite special. Well - this is all just mindsand, of course.

Also, this is not a real answer, but using reasonable complexity assumptions, BPP = P (the result due to Implagiazzo and Wigderson), of course BPP would then be a syntactic class. What would be interesting would be to show that finding a syntactic characterization of BPP would imply derandomization of BPP.

When you say, "we can diagonalize against the class to obtain a separation result..", please clarify. I know we can diagonalize against the class TIME(f(n)) to separate TIME(f) from TIME(g) where g = $\omega(f)$ (up to logarithmic terms), but is there such a diagonalization we can use against P to separate it from something else?

You mean, "The evidence for the former is not as dramatic as that for the latter."

Thanks for the answer - that clarifies much. But, what did you mean by "whereas the same question is in Pi_1" - what same question?

This is a little imprecise, because sets can contain anything, such as other sets, and symbols such as Heart, Elephant, and Galaxy - and I don't mean the string representation of those things, but those actual things. Kolmogorov complexity is about strings only. It is unclear what the Kolmogorov complexity of an Elephant is. If you're talking about sets of finite strings, like Rune states below, those are always countable. If you're talking about sets of infinite strings, it's also unclear what the Kolmogorov complexity of infinite strings are.

Then, based on Pete Clark's comment above, I'm imposing too many conditions on the polynomial for it to exist (in general)?

Ah, I guess I was not clear at all. I'm not looking for a polynomial (because of what you just said), but rather an entire function with 0's at only those places (the $a_i$'s), and 1's at those places (the $b_i$'s). I know I can construct a Weierstrass entire function with the specified zeros, but can I force the entire function to have 1's at only those places?