Home
Researchers
Meetings and other events
Positions
Publications
Research
Reports
Newsletter
Useful links

I
II
III
IV
V
VI
VII
VIII

MODNET
Research Training Network in Model 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