Википедия [1] утверждает, что наиболее известная нижняя оценка размера доказательств Фреге является квадратичной, и что нет известных суперлинейных нижних оценок для числа линий доказательств Фреге.
Вопросов:
1) Какова наиболее известная нижняя граница для числа строк расширенных доказательств Фреге?
2) Каков наиболее известный нижний предел для размера расширенных доказательств Фреге? Это все еще квадратично, как во Фреге?
3) Древовидный Extended Frege может имитировать DAG-подобный Extended Frege за полиномиальное количество шагов. Существуют ли суперлинейные нижние оценки для размера / числа линий на древовидном расширенном Фреге?
4) Какие тавтологии приводят к линейной нижней границе числа строк и к квадратичной нижней границе размера в доказательствах Фреге, как указано в википедии?
Obs: Мне известно о том факте, что для постоянной глубины Фреге у нас есть размер нижних границ порядка , Но я действительно заинтересован в полной мощности Фреге и Расширенного Фреге.
источник