wiki_research

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

turing_reduction (389B)

      1 # Turing reduction
      2 
      3 [reduction] which uses target problem as [oracle]
      4 
      5 - "Cook reduction" : Turing reduction which is [ptime_reduction]
      6 
      7 Not always very different from [many_one_reduction] for [counting_problem], cf argument https://dbt.zulipchat.com/#narrow/stream/417238-Dagstuhl-24032/topic/Open.20problems/near/425331364
      8 
      9 Up: [reduction]
     10 
     11 See also: [alan_turing], [many_one_reduction]