P≠NC over the p-adic numbers

✍ Scribed by Michael Maller; Jennifer Whitehead

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 130 KB
• Volume: 19
• Category: Article
• ISSN: 0885-064X
• DOI: 10.1016/s0885-064x(02)00002-x

✦ Synopsis

We show that in the Blum-Shub-Smale model of computation, over the p-adic numbers Q p ; the class NC Q p is strictly contained in the class P Q p : That is, there exist sets of p-adic numbers which can be recognized in sequential polynomial time, but which cannot be recognized in polylogarithmic parallel time. We use the sets ðx 1 ; x 2 ; y;

We also show that the inclusion PAR Q p CEXP Q p is strict. These results extend previous work of Cucker, and of Blum, Cucker, Shub and Smale in the real case.