Turing Reducibility

- Natural & Formal Sciences -
Mathematics & Logic Dictionary
A relation between decision problems (sets) A and B where A is Turing reducible to B if there exists a Turing machine that decides membership in A given an oracle for B; equivalently, A is computable relative to B.