Computational complexity of logical theories of one successor and another unary function
From MaRDI portal
Publication:868664
DOI10.1007/s00153-006-0031-1zbMath1110.03025MaRDI QIDQ868664
Publication date: 6 March 2007
Published in: Archive for Mathematical Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00153-006-0031-1
03B25: Decidability of theories and sets of sentences
03D15: Complexity of computation (including implicit computational complexity)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Cites Work
- Unnamed Item
- Unnamed Item
- Simplifying the solution of Ljunggren's equation \(x^ 2+1=2y^ 4\)
- Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories
- A uniform method for proving lower bounds on the computational complexity of logical theories
- On the computational complexity of the theory of Abelian groups
- The complexity of logical theories
- Complexity of logical theories involving coprimality
- The computational complexity of logical theories
- A new solution of the diophantine equation \(X^ 2+1=2Y^ 4\)
- An application of games to the completeness problem for formalized theories
- LOGICAL THEORIES OF ONE-PLACE FUNCTIONS ON THE SET OF NATURAL NUMBERS
- A note on undecidable extensions of monadic second order successor arithmetic
- Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
- A list of arithmetical structures complete with respect to the first-order definability
