Inspired by a previous (now deleted) post:

We do not know if every even natural number (at least four) is a sum of two primes [Goldbach, 1742]. However, there is a simple algorithm that decides if a given even number (at least four) is a sum of two primes.

Similarly but differently, we do not know if every even natural number is a difference of two primes [Maillet, 1905]. Here there is no (known) algorithm that decides if a given even number is a difference of two primes.

These are the examples given in Godel, Escher, Bach to teach the reader about the difference between bounded and unbounded search.

After a few searches, ending here, I found that there are more difficult, and earlier, versions of Maillet's question. Kronecker [1901] asks if every even natural number is the difference of two primes in infinitely many ways. Polignac [1849] asks if every even natural number is the difference of infinitely many pairs of consecutive primes. These two conjectures have their related decision problems. However, now the unbounded search is much worse...

Inspired by a previous (now deleted) post:

We do not know if every even natural number (at least four) is a sum of two primes [Goldbach, 1742]. However, there is a simple algorithm that decides if a given even number (at least four) is a sum of two primes.

Similarly but differently, we do not know if every even natural number is a difference of two primes [Maillet, 1905]. Here there is no (known) algorithm that decides if a given even number is a difference of two primes.

These are the examples given in Gödel, Escher, Bach to teach the reader about the difference between bounded and unbounded search.

After a few searches, ending here, I found that there are more difficult, and earlier, versions of Maillet's question. Kronecker [1901] asks if every even natural number is the difference of two primes in infinitely many ways. Polignac [1849] asks if every even natural number is the difference of infinitely many pairs of consecutive primes. These two conjectures have their related decision problems. However, now the unbounded search is much worse...

Inspired by a previous (now deleted) post:

We do not know if every even natural number (at least four) is a sum of two primes. However, there is a simple algorithm that decides if a given even number (at least four) is a sum of two primes.

Similarly but differently, we do not know if every even natural number is a difference of primes. Here there is no (known) algorithm that decides if a given even number is a difference of two primes.

These are the examples given in Godel, Escher, Bach to teach the reader about the difference between bounded and unbounded search.

Inspired by a previous (now deleted) post:

We do not know if every even natural number (at least four) is a sum of two primes [Goldbach, 1742]. However, there is a simple algorithm that decides if a given even number (at least four) is a sum of two primes.

Similarly but differently, we do not know if every even natural number is a difference of two primes [Maillet, 1905]. Here there is no (known) algorithm that decides if a given even number is a difference of two primes.

These are the examples given in Godel, Escher, Bach to teach the reader about the difference between bounded and unbounded search.

After a few searches, ending here, I found that there are more difficult, and earlier, versions of Maillet's question. Kronecker [1901] asks if every even natural number is the difference of two primes in infinitely many ways. Polignac [1849] asks if every even natural number is the difference of infinitely many pairs of consecutive primes. These two conjectures have their related decision problems. However, now the unbounded search is much worse...