Timeline for $P=NP$ and provability of family of propositional formulas

Current License: CC BY-SA 3.0

9 events

when toggle format	what		by	license	comment
Jan 13, 2017 at 14:26	comment	added	Erfan Khaniki		@EmilJeřábek: Actually I wanted to write my question in the language of arithmetic $\mathcal{L}_1=\{+,\cdot,S,0,=,<,R \}$. But I thought that language of bounded arithmetic is easier to work with and I forgot the fact that $\Delta_0$ formulas in $\mathcal{L}_1$ are $\Sigma_0^b$ formulas in $\mathcal{L}'$. I edited my post. Thanks.
Jan 13, 2017 at 14:21	history	edited	Erfan Khaniki	CC BY-SA 3.0	added 5 characters in body
Jan 13, 2017 at 8:59	comment	added	Emil Jeřábek		The right-hand side of the equivalence does not really make sense unless $\phi$ is $\Sigma^b_0$ (sharply bounded). If $\phi$ contains a non-sharply bounded quantifier, the length of $\langle\phi(n)\rangle$ is at least polynomial in $n$, hence exponential in the length of $n$. Thus, first, in a theory in which exponentiation is not total, $\langle\phi(n)\rangle$ is not even well-defined unless $n\in\mathit{Log}$, and even then it cannot have a Frege proof with code $t(n)$ (hence length $O(\log n)$) for any sufficiently large $n$, as the length of the proof is at least the length of the formula.
Jan 12, 2017 at 23:37	history	edited	Erfan Khaniki	CC BY-SA 3.0	added 152 characters in body
Jan 12, 2017 at 23:26	history	edited	Erfan Khaniki	CC BY-SA 3.0	edited title
Jan 12, 2017 at 22:19	comment	added	Erfan Khaniki		@EmilJeřábek: You are right. It should be $\leftrightarrow$ instead of $\to$. I edited my post. Thanks a lot
Jan 12, 2017 at 22:18	history	edited	Erfan Khaniki	CC BY-SA 3.0	added 12 characters in body
Jan 12, 2017 at 20:13	comment	added	Emil Jeřábek		The way it is written, e.g. the formula $x=x$ works for $\phi(x)$. Did you forget some conditions?
Jan 12, 2017 at 19:58	history	asked	Erfan Khaniki	CC BY-SA 3.0