I am generally interested in the forcing method used by Baker-Gill-Solovay and Cohen. I am looking for as many sources as I can get my hands on concerning either the technique itself or its use. Does anyone have suggestions?
For more uses of forcing (via so-called generic oracles) in complexity theory, see The Oracle Builder's Toolkit (freely available from Fortnow's homepage) by Fenner, Fortnow, Kurtz, and Li. They give a general theory of generic oracles, and show its many applications in complexity.
If you're interested in how oracles in complexity are like independence proofs in set theory, you might be interested in the following papers:
Arora, Impagliazzo, Vazirani. Relativizing versus Nonrelativizing Techniques: the Role of Local Checkability.
Impagliazzo, Kabanets, Kolokolova. An Axiomatic Approach to Algebrization. (full version freely available from Kabanets's homepage)
For the uses of forcing in set theory, see the book Set Theory (Set Theory on Amazon) by Jech, especially Parts II and III of the book (not to be confused with "Introduction to Set Theory" by Hrbáček and Jech).
For uses of forcing like techniques in proof complexity you might want to look at:
M. Ajtai. The complexity of the pigeonhole principle. In Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, White Plains, NY, 1988, pp. 346–355; and
M. Ajtai. The complexity of the pigeonhole principle. Combinatorica 14 (1994), no. 4, 417–433.
The method of proof is an arithmetical analogue of forcing (of a kind already used by Paris and Wilkie). More combinatorial (and improved lower bounds) are in J. Krajıcek, P. Pudlak, and A. Woods, Exponential lower bounds to the size of bounded depth Frege proofs of the pigeonhole principle, Random Structures Algorithms, 7 (1995), pp. 15–39. and T. Pitassi, P. W. Beame, and R. Impagliazzo, Exponential lower bounds for the pigeonhole principle, Comput. Complexity, 3 (1993), pp. 97–140.
Miklos Ajtai. The Independence of the modulo $ p$ Counting Principles. ECCC 1994.
Soren Riis. Finitisation in Bounded Arithmetic. 1994, BRICS, Department of Computer Science University of Aarhus.
Recently, Jan Krajicek published a book unifying these forcing techniques:
- J. Krajicek. Forcing with Random Variables and Proof Complexity. Cambridge University Press, Dec. 2010. (Draft available from Krajicek's homepage)
see also Forcing in proof theory by Avigad, 30pp, 2004. he cites BGS75 but not in detail. there is some reference to Scott/Solovay as a rephrasing of forcing into boolean-valued models.
Ideas in forcing have been influential in computational complexity; for example, the separation of complexity classes relavitized to an oracle (e.g., as in BGS75) can often be viewed as resource-bounded versions of forcing.