Publication:4286756
From MaRDI portal
zbMath0790.03008MaRDI QIDQ4286756
Publication date: 10 April 1994
primality; exponentiation; exercises; diophantine complexity; bounded universal quantifiers; diophantine coding; Four-Color Problem; recursive unsolvability of Hilbert's Tenth Problem; universal diophantine equations; implications of negative solution to Hilbert's Tenth problem
11U05: Decidability (number-theoretic aspects)
12L05: Decidability and field theory
11-02: Research exposition (monographs, survey articles) pertaining to number theory
03-02: Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations
03B25: Decidability of theories and sets of sentences
11D99: Diophantine equations
Related Items
Size-based termination of higher-order rewriting, Unnamed Item, Unnamed Item, Unnamed Item, Diophantine questions in the class of finitely generated nilpotent groups, Quasi-interpretations. A way to control resources, Diophantine equations and the generalized Riemann hypothesis, Authentication schemes from actions on graphs, groups, or rings, \(\text{NP}\not={co}\)-NP and models of arithmetic, P, NP, Co-NP and weak systems of arithmetic, Uncomputability and undecidability in economic theory, Diophantine undecidability of holomorphy rings of function fields of characteristic 0, Metafinite model theory, On the computability of Nash equilibria, Frontier between decidability and undecidability: A survey, The complexity of computation and approximation of the \(t\)-ratio over one-dimensional interval data, Semi-Galois categories. II: An arithmetic analogue of Christol's theorem, Hintikka's independence-friendly logic meets Nelson's realizability, A computational glimpse at the Leibniz and Frege hierarchies, Liouville closed \(H\)-fields, Normal forms for second-order logic over finite structures, and classification of NP optimization problems, Turing reducibility in the fine hierarchy, Symmetry of eigenvalues of Sylvester matrices and tensors, Padovan-like sequences and Bell polynomials, Definability and decidability in infinite algebraic extensions, The computational power of enzymatic numerical P systems working in the sequential mode, Extendability of continuous maps is undecidable, Diophantine sets of representations, Isomorphisms of scattered automatic linear orders, Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups, On certain biquadratic equations, II, Unnamed Item, Extensions of Hilbert’s Tenth Problem: Definability and Decidability in Number Theory, Theories of orders on the set of words, Decidability of Univariate Real Algebra with Predicates for Rational and Integer Powers, Tree Automata for Non-linear Arithmetic