Computational complexity of arithmetical sentences

DOI10.1006/inco.1995.1116zbMath0833.03002OpenAlexW1978898417MaRDI QIDQ1898469

Yanyan Li

Publication date: 17 March 1996

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1995.1116

zbMATH Keywords

NP-completepolynomial timedecision problemco-NP-complete\(\exists \forall\) sentence\(\forall \exists\) sentencearithmetical sentence

Mathematics Subject Classification ID

Decidability (number-theoretic aspects) (11U05) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (4)

Algorithms for sentences over integral domains ⋮ Skolem functions of arithmetical sentences. ⋮ Computational complexity of sentences over fields ⋮ Sentences over integral domains and their computational complexities

This page was built for publication: Computational complexity of arithmetical sentences