Consider the following example challenge:
Given a set of integers, output a truthy value if there is a non-empty subset whose sum equals 0, or a falsey value if no such subset exists. Solutions must have worst-case polynomial time complexity or better.
This is the subset sum problem, which is NP-complete. Thus, the existence or non-existence of a polynomial-time solution depends on the answer to the P versus NP problem.
Another example that doesn't depend on P versus NP is this:
Given two strings, compute their edit distance. Solutions must have sub-quadratic worst-case time complexity.
It's an open question in computer science whether or not a sub-quadratic algorithm for computing the edit distance exists.
Here are a few more examples, suggested by Martin:
- A language-specific challenge where it's unknown if it's possible to solve the challenge in that language (e.g. non-Turing-complete languages)
- Solving a puzzle where it is not known if there is a solution
Are challenges of this nature within the scope of PPCG?