# Are challenges that may not be solvable on-topic for PPCG?

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?

• Some examples that don't involve restricted complexity: Language-specific code golf in a language whose Turing-completeness isn't known. Fastest-code for a puzzle solver where it's not known whether the puzzle has a solution. A very restrictive source-layout or restricted-code challenge where it's not clear whether any language's syntax admits a solution. (Just to show that the scope of this discussion is a bit broader than presented above.) – Martin Ender Dec 25 '16 at 21:06
• Simply remove the restriction, and change it to: Lowest time complexity wins. Tiebreaker goes to the original winning criterion. – jimmy23013 Dec 25 '16 at 22:42
• @jimmy23013 That just sidesteps the issue for restricted complexity challenges. Martin gave other examples that aren't so easily resolved. – Mego Dec 25 '16 at 22:44
• If in question, the asker should provide a baseline algorithm solving the task. No idea about source-layout. – jimmy23013 Dec 25 '16 at 23:00
• Out of curiosity, are strictly unsolvable (e.g. entscheidungs problem) already considered off topic? – Post Rock Garf Hunter Dec 27 '16 at 5:04
• Most of those can be turned into a problem known to have a solution by changing one of the solution criteria into a scoring criteria, such as: best complexity wins. In that case a polynomial time answer to a NP problem would beat all the previous answers and be the one to be accepted. – kasperd Jan 8 '17 at 11:09