wiki_research

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

time_hierarchy_theorem (187B)

      1 # Time hierarchy theorem
      2 
      3 https://en.wikipedia.org/wiki/Time_hierarchy_theorem
      4 
      5 For each c>1, there are problems solvable in O(n^c) but not O(n^{c-eps})
      6 
      7 Up: [theorem], [time_complexity]