wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

descriptive_complexity (437B)

      1 # Descriptive complexity
      2 
      3 ## [Theorems]
      4 
      5 - [Abiteboul_Vianu_theorem]
      6 - [immerman_vardi_theorem] : [first_order] with [least_fixpoint], or [datalog], is [ptime] on [ordered_structures]
      7   - cf [order_invariance]
      8 
      9 ## [Open_problems]
     10 
     11 - [logic_to_capture_ptime]
     12 
     13 ## Subfields
     14 
     15 - [description_logics_descriptive_complexity]
     16 
     17 ## Meta
     18 
     19 - Less active field nowadays: https://eccc.weizmann.ac.il//report/2011/151/
     20 
     21 Up: [computational_complexity]