Complexity of the theory of p-adic numbers

Risultato della ricerca: Capitolo in libro/report/atti di convegnoContributo a conferenzapeer review

Abstract

This paper addresses the question of the complexity of the decision problem for the theory Th(Qp) of p-adic numbers. The best known lower bound for the theory is double exponential alternating time with a linear number of alternations. I have designed an algorithm that determines the truth value of sentences of the theory requiring double exponential space. My algorithm is based on techniques used by Collins for the theory Th(R) of the reals, and on Denef's work on semi-algebraic sets and cell decomposition for p-adic fields. No elementary upper bound had been previously established.

Lingua originaleInglese
Titolo della pubblicazione ospiteAnnual Symposium on Foundatons of Computer Science (Proceedings)
Editor Anon
EditorePubl by IEEE
Pagine412-421
Numero di pagine10
ISBN (stampa)0818643706
Stato di pubblicazionePubblicato - 1993
Pubblicato esternamente
EventoProceedings of the 34th Annual Symposium on Foundations of Computer Science - Palo Alto, CA, USA
Durata: 3 nov 19935 nov 1993

Serie di pubblicazioni

NomeAnnual Symposium on Foundatons of Computer Science (Proceedings)
ISSN (stampa)0272-5428

???event.eventtypes.event.conference???

???event.eventtypes.event.conference???Proceedings of the 34th Annual Symposium on Foundations of Computer Science
CittàPalo Alto, CA, USA
Periodo3/11/935/11/93

Fingerprint

Entra nei temi di ricerca di 'Complexity of the theory of p-adic numbers'. Insieme formano una fingerprint unica.

Cita questo