[FOM] Reply to Chow's message
sbuss at math.ucsd.edu
Wed Mar 3 18:36:48 EST 2004
Tim Chow asked about Brower's fixedpoint theorem and resolution proof
For some related work, that has appeared since Papadimitriou's papers,
you might check the following references:
Beame, Cook, Edmonds, Impagliazzo, Pitassi,
"The relative complexity of NP search problems"
J. Computer and System Sciences 57 (1998) 3-19.
Joshua Buresh-Oppenheim, Tsuyoshi Morioka
"Relativized NP Search Problems and Propositional Proof Systems"
ECCC Report TR03-084, Dec. 2003.
And, a preprint of mine:
"Polynomial-Size Frege and Resolution Proofs of
st-Connectivity and Hex Tautologies", available at
The last paper has upper and lower bounds on proofs of some tautologies
related to the Papadimitriou PPAD classes.
-- Sam Buss
More information about the FOM