Jump to content

Talk:Finite model theory

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Sterling (talk | contribs) at 17:39, 15 January 2011 (→Outline). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
WikiProject iconMathematics Start‑class Mid‑priority
WikiProject iconThis article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
StartThis article has been rated as Start-class on Wikipedia's content assessment scale.
MidThis article has been rated as Mid-priority on the project's priority scale.

Perhaps we could mention that finite model theory might help us resolve P vs. NP? (See http://www2.ing.puc.cl/~jabaier/iic2212/poll-1.pdf for instance). My understanding is that several finite model theorists are in that field in hopes of conquering this major problem. Any thoughts?

Outline

  1. Character 1: Finite structure. Belongs to MT. relationship between a formal language and its interpretations. ...
  2. History: 1. Trakhtenbrot 1950, 2. Fagin, 3. databases ...
  3. Character 2: Discrimination of structures
  4. Parts: FMT vs MT, Language/ Complexity classification
  5. Applications: databases, descriptive complexity, languages/ modeling
  6. Tools: games, locality, 0-1 laws
  7. Objects of study: FO, extensions of FO/ restrictions of SO, sub-FO

--Sterling (talk) 11:34, 31 December 2010 (UTC)[reply]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Finite_model_theory&oldid=408049980"