Turing reduction Created 2026-10-05 Updated 2026-10-06
A set is Turing-reducible to when an oracle machine with membership oracle computes the characteristic function of . Unlike a many-one reduction, it may make adaptive queries and reverse or combine oracle answers.