np_definition_reductions (439B)
1 # Np definition reductions 2 3 - usual notion is [many_one_reduction] 4 - with [turing_reduction], the difference between [np] and [coNP] disappears 5 - https://cstheory.stackexchange.com/questions/138/many-one-reductions-vs-turing-reductions-to-define-npc 6 7 - it is open whether [np_complete] problems under [logspace_reductions] and [ptime_reduction] are different 8 - cf https://en.wikipedia.org/wiki/Log-space_reduction 9 10 Up: [np_complete]