wiki_research

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

many_one_reduction (346B)

      1 # Many-one reduction
      2 
      3 [reduction] that transforms an instance of A into an instance of B and answer in the same way
      4 
      5 Called "Karp reduction" when it is [ptime_reduction]
      6 
      7 - restriction "one-one" when the reduction function is injective ; aussi notion "recursively isomorphic"
      8 
      9 Up: [reduction]
     10 
     11 See also: [turing_reduction], [weihrauch_reduction]