15
\$\begingroup\$

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?

\$\endgroup\$
6
  • 3
    \$\begingroup\$ 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.) \$\endgroup\$
    – Martin Ender
    Dec 25, 2016 at 21:06
  • \$\begingroup\$ Simply remove the restriction, and change it to: Lowest time complexity wins. Tiebreaker goes to the original winning criterion. \$\endgroup\$
    – jimmy23013
    Dec 25, 2016 at 22:42
  • 1
    \$\begingroup\$ @jimmy23013 That just sidesteps the issue for restricted complexity challenges. Martin gave other examples that aren't so easily resolved. \$\endgroup\$
    – user45941
    Dec 25, 2016 at 22:44
  • \$\begingroup\$ If in question, the asker should provide a baseline algorithm solving the task. No idea about source-layout. \$\endgroup\$
    – jimmy23013
    Dec 25, 2016 at 23:00
  • \$\begingroup\$ Out of curiosity, are strictly unsolvable (e.g. entscheidungs problem) already considered off topic? \$\endgroup\$
    – Wheat Wizard Mod
    Dec 27, 2016 at 5:04
  • \$\begingroup\$ 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. \$\endgroup\$
    – kasperd
    Jan 8, 2017 at 11:09

1 Answer 1

Reset to default
16
\$\begingroup\$

Yes, assuming that the challenge hasn't had significant work on it already

The truly difficult tasks can be very interesting to work on, and you won't know whether they're impossible unless you post them. If it turns out to be impossible, or nobody answers, no real harm is done. If it turns out to be possible, we have a very impressive solution, and everyone benefits. So the potential downsides are small, and the potential upsides are large. (The best example of this happening in the past is probably this question; when it was posted, there was doubt as to whether it was possible, but it turned out that it was, and apparently 442 users (at the time of writing) were interested to see the result.)

On the other hand, the challenges should be ones where it's reasonable to consider that someone would actually work on the problem because of PPCG. "Prove P=NP" would, if worded in the form of a challenge (like in the OP), be ontopic at PPCG. "Find a counterexample to the Riemann Hypothesis" would probably be ontopic at Puzzling. However, both challenges are very well-known (and have very large cash prizes), so it's implausible to think that people would work on the challenges because of PPCG; there's little point in posting them here, as a solution would be major news that went well beyond the boundaries of Stack Exchange.

So in other words, potentially impossible challenges are reasonable, but we should stick to within the scope of what PPCG is reasonably likely to be able to accomplish. In other words, the challenge should be "I'm not sure this is possible, I wonder if anyone else at PPCG has ideas" rather than "I'm not sure this is possible, because a large team of mathematicians has failed to accomplish it for years".

\$\endgroup\$

You must log in to answer this question.