Jan Krajicek, Charles University

Extensions of models of bounded arithmetic

I will be concerned with a problem about the existence of extensions of models of a particular bounded arithmetic theory that have certain specific properties related to propositional logic. If such extensions do indeed exists then one can use them to derive from a computational hardness hypothesis that the class NP is not closed under the complement. The hypothesis postulates that no p-time student can solve a particular total search problem in propositional logic in a constant number of rounds in the interactive student-teacher model (the hypothesis follows from the existence of hard one-way permutations).