The problem with the challenge is that one must provides a solution to the problem along with the problem. IOW, you must have a solver that can solve your input problem.
Their challenge is a weaker equivalent to: there is a problem that have two types of example: solvable and unsolvable. Their claim is that their program can solve all, including unsolvable! To disprove our claim, provide an input that is unsolvable, along with its solution, and show that we do not find the given solution. The catch is, a problem that is not solvable has by definition, no solution.
In their case, the issue is not that the problem to be submitted has no solution, but that its solution is NP-hard to find. They are basically asking submitters to first find a solver for a NP-hard problem.
With what budget? P versus NP is our terrible rough estimate for budgeting things like compute time. If you think you have a known NP case where do you even start to plan a budget (for grant proposals if nothing else) on how much computing resources to "just throw at it"?
There is a good chance that the failure mode of the algorithm is to yield an invalid solution, not a suboptimal one, so in that case you do not even need to know the optimal solution. Besides that you are not going to find a counter example by generating random instances, you will be carefully constructing it with spacial properties to make the algorithm fail. Because of the special structure you might just be able to figure out the optimal solution in your head. And I would guess that you can construct a counter example with ten or so cities and you can easily brute force a few million or billion paths. If you need twenty cities however, things look already different but there are solvers that should still easily deal with those cases.
Can't you construct a problem from a known solution? To use an analogy, I can't factor arbitrarily large numbers in polynomial time, I'd doubt anyone else can either. But I can multiply large prime numbers together in polynomial time, so I can give someone a large composite and its factorization, because I started with the primes.
Comments
The problem with the challenge is that one must provides a solution to the problem along with the problem. IOW, you must have a solver that can solve your input problem.
Their challenge is a weaker equivalent to: there is a problem that have two types of example: solvable and unsolvable. Their claim is that their program can solve all, including unsolvable! To disprove our claim, provide an input that is unsolvable, along with its solution, and show that we do not find the given solution. The catch is, a problem that is not solvable has by definition, no solution.
In their case, the issue is not that the problem to be submitted has no solution, but that its solution is NP-hard to find. They are basically asking submitters to first find a solver for a NP-hard problem.
If the counterexample is small can you just throw compute at it and swallow that it wont be solved in polynomial time but it will be solved.
Disclaimer: I don’t fully understand the puzzle yet but I am intrigued!
With what budget? P versus NP is our terrible rough estimate for budgeting things like compute time. If you think you have a known NP case where do you even start to plan a budget (for grant proposals if nothing else) on how much computing resources to "just throw at it"?
There is a good chance that the failure mode of the algorithm is to yield an invalid solution, not a suboptimal one, so in that case you do not even need to know the optimal solution. Besides that you are not going to find a counter example by generating random instances, you will be carefully constructing it with spacial properties to make the algorithm fail. Because of the special structure you might just be able to figure out the optimal solution in your head. And I would guess that you can construct a counter example with ten or so cities and you can easily brute force a few million or billion paths. If you need twenty cities however, things look already different but there are solvers that should still easily deal with those cases.
Can't you construct a problem from a known solution? To use an analogy, I can't factor arbitrarily large numbers in polynomial time, I'd doubt anyone else can either. But I can multiply large prime numbers together in polynomial time, so I can give someone a large composite and its factorization, because I started with the primes.