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 11:34, 31 December 2010 (→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: Finite structure. Belongs to MT. ...
  2. History: Trachtenbrot, Fagin, ...
  3. Parts: FMT vs MT, Language/ Complexity classification
  4. Applications: databases, descriptive complexity, languages/ modeling
  5. Tools: games, locality, 0-1 laws
  6. 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=405154177"