wiki_research

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

polynomial_hierarchy (350B)

      1 # Polynomial hierarchy (PH)
      2 
      3 - first levels: [nptime], [conptime]
      4   - see also [np_cap_conp]
      5 - second level: [pi2], [sigma2]
      6   - see also [pi2_cap_sigma2]
      7 - [delta2p] = [ptime] with an [nptime] [oracle]
      8   - https://complexityzoo.net/Complexity_Zoo:D#delta2p
      9   - contains [boolean_hierarchy]
     10 
     11 Up: [complexity_hierarchy]
     12 
     13 See also: [boolean_hierarchy]