加载中…
Motivated by the theory of proof complexity generators we consider the following search problem determined by a propositional proof system : given a -proof of a disjunction , no two having an atom in common, find such that . We formulate a hypothesis (ST) that for some strong proof system the problem is not solvable in the student-teacher model with a -time student and a constant number of rounds. The hypothesis follows from the existence of hard one-way permutations. We prove, using a model-theoretic assumption, that (ST) implies . The assumption concerns the existence of extensions of models of a bounded arithmetic theory and it is open at present if it holds.

生成讲解博客的中文版本

生成AI智能校验的中文版本