Timeline for The NP version of Matiyasevich's theorem
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S May 24, 2017 at 16:48 | history | suggested | descenso |
added diophantine tag
|
|
| May 24, 2017 at 16:42 | review | Suggested edits | |||
| S May 24, 2017 at 16:48 | |||||
| Jul 20, 2011 at 23:30 | comment | added | R Hahn | The Adleman and Manders paper was the answer to a related question I asked awhile back: mathoverflow.net/questions/36420/… | |
| Jul 20, 2011 at 16:20 | vote | accept | CommunityBot | moved from User.Id=6976 by developer User.Id=69903 | |
| Jul 20, 2011 at 14:35 | answer | added | François G. Dorais | timeline score: 16 | |
| Jul 20, 2011 at 13:47 | comment | added | Ali Enayat | This question seems seems to have been first posed by Adleman and Manders in 1975, and it is closely connected with unsolved problems in complexity theory; the following paper includes a review of the state of the art in 2003: C. Pollett, On the Bounded Version of Hilbert's Tenth Problem. Archive for Mathematical Logic. Vol. 42. No. 5. 2003. pp. 469--488. You can find a copy on the author's homepage at cs.sjsu.edu/faculty/pollett/papers | |
| Jul 20, 2011 at 13:46 | answer | added | Emil Jeřábek | timeline score: 21 | |
| Jul 20, 2011 at 3:49 | comment | added | François G. Dorais | I vaguely recall that someone did look into this from the computational point of view. The results were not great. I'll see if I can dig this up... | |
| Jul 20, 2011 at 3:23 | comment | added | user6976 | @Gerhard: It cannot be that simple. The conversion from TM to a Diophantine equation is complicated and - at least in Matiyasevich's proof - seems to require exponential slow down. But I may be wrong of course. The proof uses some properties of Pell equations. I wonder if anybody looked at the proof from the complexity point of view. | |
| Jul 20, 2011 at 2:56 | comment | added | Gerhard Paseman | I should say "every instance p of A". Please forgive this and other typos in the previous comment. Gerhard "Ask Me About System Design" Paseman, 2011.07.19 | |
| Jul 20, 2011 at 2:54 | comment | added | Gerhard Paseman | Suppose that, for every instance of p, there was a uniform certificate xbar where the number of components (dimension) of xbar was bounded by a constant. Then it seems to me that the TM that ran the verifier on xbar could be rewritten as your desired polynomial. I do not know how to argue that the certificates have to be uniform in (dimensional) length, although it is clear that the index n is bounded by a polynomial in the bitlength of p. Gerhard "Ask Me About System Design" Paseman, 2011.07.19 | |
| Jul 20, 2011 at 2:39 | history | edited | user6976 | CC BY-SA 3.0 |
added 13 characters in body
|
| Jul 20, 2011 at 2:26 | history | asked | user6976 | CC BY-SA 3.0 |