wiki_research

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

second_order_logic (617B)

      1 # SO
      2 
      3 [descriptive_complexity]: corresponds to the [polynomial_hierarchy]
      4 
      5 Restrictions:
      6 
      7 - [existential_second_order_logic] corresponds to [NP] by [Fagin's_theorem]
      8 - [universal_second_order_logic] corresponds to [coNP]
      9 - [quantifier_prefix]
     10 - [monadic_second_order_logic]
     11 
     12 Extensions:
     13 
     14 - [second_order_transitive_closure] SO(TC) [ferrarotti2018expressivity]
     15   - corresponds to [pspace]
     16   - can express [hamiltonian_cycle]
     17     - which is known not to be expressible in [monadic_second_order_logic]
     18   - restrictions: [monadic_second_order_logic_transitive_closure] MSO(TC)
     19 
     20 See also: [first_order_logic]
     21 
     22 Aliases: SO