TASK VII - DECIDABILITY ISSUES AND LINKS TO COMPLEXITY THEORY
Description
Problems of decidability or complexity arising in model theory are
quite varied, and of significance to logicians, number theorists and
computer scientists.
List of specific problems
VII.1: Finitely generated fields and connections with arithmetic (Hilbert s 10th problem).
a) Investigate existential definition
of the integers in the rationals, or in rings of algebraic integers.
b) Prove Diophantine undecidability of the rationals
VII.2: Algebraic complexity
a) Examine the P=NP problem in important rings.
VII.3: Models of fragments of arithmentic
a) Prove that the residue fields
in models of IΔ_{0} + Ω_{1} are pseudofinite.
b) Prove existence
of infinitely many primes over IΔ_{0}(p), where p(x) counts the primes below
x.
c) Study quadratic forms, local/global results, quadratic
reciprocity, over bounded arithmetic