which the answer is yes. For example, primality testing can be represented as the infinite set

:L = {2, 3, 5, 7, 11, ...}

Search problem

In a search problem, the answers can be arbitrary strings. For example, factoring is a search problem where the instances are (string representations of) positive integers and the solutions are (string representations of) collections of primes.

A search problem is represented as a relation

1.Previous
3.Next