Timeline for Collapsing the Linear Time Hierarchy and finite axiomatizability of bounded arithmetic
Current License: CC BY-SA 3.0
12 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
Dec 2, 2016 at 18:40 | comment | added | Erfan Khaniki | @EmilJeřábek: You are right. I forgot to define oracle in theory. I edited my post. | |
Dec 2, 2016 at 18:40 | history | edited | Erfan Khaniki | CC BY-SA 3.0 |
added 165 characters in body
|
Dec 2, 2016 at 17:19 | comment | added | Emil Jeřábek | The new question does not make sense to me. I think you misunderstand how relativization works in bounded arithmetic. $I\Delta_0(\alpha)$ is not a family of theories parameterized by subsets of $\mathbb N$ or such, it is a single theory involving an uninterpreted predicate $\alpha(x)$. This $\alpha$ is just a symbol, it does not denote any particular oracle. Rather, witnessing theorems for relativized bounded arithmetic yield uniformly oracle algorithms that can be specialized to whatever oracle one needs. $I\Delta_0(\alpha)$ is not finitely axiomatizable, because $T_2(\alpha)$ is not. | |
Dec 2, 2016 at 16:57 | history | edited | Erfan Khaniki | CC BY-SA 3.0 |
added 191 characters in body
|
Dec 2, 2016 at 16:50 | history | edited | Erfan Khaniki | CC BY-SA 3.0 |
added 191 characters in body
|
Dec 2, 2016 at 16:43 | comment | added | Erfan Khaniki | @EmilJeřábek: Thank you very much for your explanation and papers. I updated my post with a new related question. | |
Dec 2, 2016 at 14:49 | comment | added | Emil Jeřábek | ... An exception is Buss’s paper math.ucsd.edu/~sbuss/ResearchWeb/collapseBAPH/index.html , which uses a more light-weight argument to get a weaker collapse. On a quick look in the paper, I didn’t notice anything that would require genuinely polynomial growth, so there is a nontrivial chance it may actually be adapted to $I\Delta_0$ and the linear hierarchy, but the devil is in the detail. | |
Dec 2, 2016 at 14:44 | comment | added | Emil Jeřábek | Well, the main problem with the original Krajíček–Pudlák–Takeuti argument is Lemma 4.43: even if all the input data is linear, the function with polynomial advice constructed near the end of the proof has superlinear (quadratic) advice, hence it cannot be used in the linear hierarchy setting. There have been several improvements of the result, but most of the proofs elaborate the original argument, hence they suffer from the same problem (this includes the currently best results: Thm. 4.6 and Cor. 4.7 from my paper users.math.cas.cz/~jerabek/papers/hash.pdf ). ... | |
Dec 2, 2016 at 7:44 | history | edited | Erfan Khaniki | CC BY-SA 3.0 |
added 330 characters in body
|
Nov 22, 2016 at 13:24 | comment | added | Erfan Khaniki | @AJ.: See corollary 4.39 in chapter V of metamathematics of first order arithmetic. Notations are explained in that chapter. | |
Nov 22, 2016 at 11:59 | comment | added | user94040 | what is the reference for notations? what is the reference for this result? | |
Nov 22, 2016 at 8:44 | history | asked | Erfan Khaniki | CC BY-SA 3.0 |