MODNET
Research Training Network in Model Theory
Research > Task VII: Decidability issues and links to complexity theory

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.


Progress

Years 1 and 2, Years 3 and 4.

Last updated: September 9 2009 15:54 Please send your corrections to: