We consider tautologies formed from a pseudo-random number generator. We explain a strategy of proving their hardness for Extended Frege systems via a conjecture about bounded arithmetic. Further we give a purely finitary statement, in the form of a hardness condition imposed on a function, equivalent to the conjecture.
We consider tautologies formed from a pseudo-random number generator. We explain a strategy of proving their hardness for Extended Frege systems via a conjecture about bounded arithmetic. Further we give a purely finitary statement, in the form of a hardness condition imposed on a function, equivalent to the conjecture. (en)