Computational complexity of logical theories of one successor and another unary function
type: Item
instance of: scholarly article
title: Computational complexity of logical theories of one successor and another unary function
zbMATH Open document ID: 1110.03025
author: Pascal Michel
published in: Archive for Mathematical Logic
publication date: 2007-03-06T00:00:00Z
review text: This paper studies the set of natural numbers as a universe equipped with equality as the unique relation and simple, usual unary, functions as basic operations. The logic theory derived from the above is proven to be complete for some choices of the unary function. In particular, it is known that this is the case for the unary functions \(x+1\), \(2x\), \(x^2\) and \(2^x\), where equality is the only relation assumed. The author extends the result to the first-order logical theory derived by the function \(x+1\) combined with the functions \(c^x\) and \(x^c\). The article begins with an overview of the necessary definitions and other preliminaries, which is then followed with an extensive series of theorems, lemmas and corollaries with complete proofs. Completeness is assumed for the class ATIME-ALT\((2^{O(n)},O(n))\) throughout this article. The paper concludes with a list of relevant articles.
reviewed by: Efstratios Rappos
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5131234
zbMATH Keywords: computational complexity
zbMATH Keywords: logical theories
zbMATH Keywords: Ehrenfeucht-Fraïssé games
MaRDI profile type: Publication
full work available at URL: s00153-006-0031-1
OpenAlex ID: W2160473480
cites work: Q3996675
cites work: The complexity of logical theories
cites work: A uniform method for proving lower bounds on the computational complexity of logical theories
cites work: An application of games to the completeness problem for formalized theories
cites work: Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
cites work: The computational complexity of logical theories
cites work: Q3666827
cites work: A new solution of the diophantine equation \(X^ 2+1=2Y^ 4\)
cites work: A list of arithmetical structures complete with respect to the first-order definability
cites work: On the computational complexity of the theory of Abelian groups
cites work: Complexity of logical theories involving coprimality
cites work: LOGICAL THEORIES OF ONE-PLACE FUNCTIONS ON THE SET OF NATURAL NUMBERS
cites work: Simplifying the solution of Ljunggren's equation \(x^ 2+1=2y^ 4\)
cites work: A note on undecidable extensions of monadic second order successor arithmetic
cites work: Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories
DOI: 10.1007/S00153-006-0031-1
description: scientific article; zbMATH DE number 5131234