Complexity theory uses a large number of unproven conjectures. There are several hardness conjectures in David Johnson's NP-Completeness Column 25. What are the other major conjectures not mentioned in the above article? Did we achieve some progress towards proving one of these conjectures? Which conjecture do you think would require completely different techniques from the currently known ones?
Major conjectures used to prove complexity lower bounds?
cc.complexity theory;lower bounds