wiki_research

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

pseudo_polynomial_time (380B)

      1 # Pseudo polynomial time
      2 
      3 https://en.wikipedia.org/wiki/Pseudo-polynomial_time
      4 
      5 There is an [algorithm] running in [PTIME] in the number of input integers and in the value of the greatest integer
      6 
      7 So it is not really a [PTIME] algorithm in the size of the input integers
      8 
      9 See also: [ptime], [np_complete], [strongly_np_complete], [quasipolynomial]
     10 
     11 Up: [computational_complexity]