What's relation between Kolmogorov complexity and pseudorandomness?
The standard notion of pseudorandomness is about a process.  You can say that the process (the pseudorandom generator) is pseudorandom, or not.  The notion of pseudorandomness of a single string is not defined; that's not something you can talk about.

Kolmogorov randomness is a property of a bit-string.  You can say that a particular bit-string (sequence) is Kolmogorov-random, or not.  Effectively, a bit-string is Kolmogorov-random if it has high Kolmogorov complexity, i.e., there's no program that outputs that string that's shorter than the string itself.

If you have a pseudorandom generator, then the strings it outputs are never Kolmogorov-random.  Any output from the pseudorandom generator can always be generated by a short program (a program that hardcodes the seed to the pseudorandom generator, as well as the code of the pseudorandom generator itself), so isn't Kolmogorov-random.

That's the relationship.



Incidentally, Kolmogorov-random is not about knowledge of a program to generate the string.   Knowledge is irrelevant.  What matters is existence: whether or not exists a program that generates the string.  If there exists a short program that generates the string, then the string is not Kolmogorov-random -- and this remains true even if you don't know the program, or even if it would be difficult to find the program.



You asked about compressibility.  Let $G$ be a pseudorandom generator (in the standard cryptographic sense, i.e., computationally indistinguishable from true-random).  There is a sense in which outputs of $G$ are compressible, and a sense in which they are not.

The outputs of $G$ are compressible, if you don't care how long the compression algorithm takes to run.  Given $G$, we can construct a compression algorithm $C$ that compresses outputs from $G$ to something much shorter.  The catch is that $C$ takes a very long time to run: it takes exponential time.  In particular, $C$ works by exhaustively trying all possible seeds to see which is correct, and outputting the correct one.  This isn't of much relevance in practice -- an algorithm whose running time exceeds the predicted lifetime of the solar system isn't of much engineering relevance -- but it does demonstrate that the outputs of $G$ are Kolmogorov-compressible and thus aren't Kolmogorov-random.

Outputs of $G$ are not compressible (with high probability), if you limit the compression algorithm's running time to something reasonable.  For instance, suppose we limit $C$ to run in polynomial time, but allow $C$ to be otherwise unrestricted; then with high probability, running $C$ on the output of $G$ will not lead to any appreciable compression.  (Why?  Truly random bit-strings are, with high probability, not compressible by $C$.  If pseudorandom outputs from $G$ were compressible, then you would obtain a polynomial-time algorithm for distinguishing outputs of $G$ from truly-random strings, which is exactly what the definition of pseudorandomness promises cannot happen.)  So in practice, outputs of a pseudorandom generator are not compressible.

Maybe this helps enlighten the connection and contrast between standard pseudorandomness and Kolmogorov-randomness.  Standard pseudorandomness is about fooling a fast distinguisher (say, one that runs in polynomial time).  Kolmogorov-randomness is about fooling a short distinguisher (one whose source code is shorter than the pseudorandom string).  "Fast" is largely orthogonal to "short"; you can have a short program that is very slow (e.g., exponential running time), and you can have a long program that is still fairly efficient (its source code is longer than the input string, but its running time is at most polynomial in the length of that string).