2
\$\begingroup\$

Challenges like this are a little difficult to judge because they're effectively asking us to write a program that solves an unsolved mathematical problem. Until such a time as there is verified proof of a solution to the underlying mathematical problems, we cannot know for certain what the upper limits of these programs need to be or what their output should be once that limit is reached.

Most currently unsolved mathematical problems cannot be simply solved by brute force - if they could, people with larger brains, more money, and bigger computers would probably have cracked them by now. So, essentially these are impossible questions. Sure, we can validate that the program is written in a way that it should produce the expected output. But until we know for certain what the answer to the underlying mathematical problem is, we have no way of authoritatively testing this.

Should questions like these be allowed? What should be some guidelines for posting and judging them?

\$\endgroup\$
3
\$\begingroup\$

It's true that we can't realistically test submissions to the linked questions or similar ones to see whether they give the correct result, but I don't think that this is inherently bad. Nabbs' winning answer to Shamir secret sharing is also untestable in practical terms: code golf is about being as short as possible, so if the question doesn't place runtime limits then people should exploit that. If the submission includes a sketch proof of correctness, and even better if it can be tested on smaller test-cases (I tested Nabbs' code with a much smaller finite field), I think that's sufficient.

However, I agree that one needs to be careful when wording questions relating to open problems. Personally I much prefer questions along the lines of Collatz conjecture which take input and test to see whether it's a counterexample, ideally providing some kind of certificate. This is trivially changed into a brute force counterexample checker (it just takes a loop), but can be tested without necessarily understanding the code.

\$\endgroup\$
0
\$\begingroup\$

I think that these solutions should not be allowed, the same as questions requesting the most concise C++ IDE would not be allowed.

If these questions are allowed, the accepted answer should be code that produces the result that is closest to the estimated correct answer within an acceptable range. Shortest code of the qualifying answers wins.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .