Wikipedia:Reference desk/Archives/Mathematics/2018 October 30

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 30

RSA type challenges other than factoring

The RSA numbers proved useful to determine what size number can be feasibly factored and to spur research into the problem. I was wondering if there were sets of challenges related to other computationally difficult problems. For example is there a set of increasingly large instances of the Traveling Salesman Problem somewhere whose answers are known, but only the problem data and not the solution are available to the public? I guess to have the same spirit as RSA the instances should have the following properties:

• A range of sizes starting with estimated computation time a few days on a PC.
• Each instance should provably reduce to a finite, if very lengthy, computation.
• Each instance is to a large extent randomly generated for the given size.
• It should be easy to check if a proposed solution is correct.
• Cash prizes a plus.

--RDBury (talk) 17:19, 30 October 2018 (UTC)

An anonymous user pointed out [1], an annual competition of SAT solvers. It's interesting to me that, while all the RSA numbers fit comfortably on a single Wikipedia page, the test files for the contest are in the megabyte range. This seems somewhat ironic since integer factorization is thought not to be NP-complete and therefore 'easier' in some sense than SAT. It looks like one reason for RSA type challenges for NP-complete problems being hard to find is that problem data files must be very large to even give modern heuristic-based algorithms a good workout. --RDBury (talk) 04:44, 2 November 2018 (UTC)