Какую известную задачу в распределенных вычислениях можно использовать в качестве примера, где вычисление решения может занимать длительное время, но проверка этого решения будет быстрой?
Да, существует задача на распределенные вычисления, которая легко поддается проверке - это задача факторизации больших чисел. Примером известной задачи в распределенных вычислениях, где вычисление решения может занимать длительное время, но проверка этого решения будет быстрой, является задача поиска простых чисел в криптографии. Например, задача факторизации больших чисел используется в криптографии для создания безопасных шифров. В данной задаче вычисление всех простых множителей числа может занимать значительное время, но проверка правильности факторизации числа выполняется быстро.
Попробуйте алгоритмы факторизации чисел. Их проверка всегда занимает линейное время (по количеству множителей).
Там есть ряд алгоритмов, которые можно параллелить, типа решета числового поля (NFS) или квадратичного решета (QS)
На СИ?
Попробуйте распределенную компиляцию, например icecc, distcc
Даже считать не нужно
Алгоритмы майнинга криптовалют, любой, тот же биткоин изучен и разложен по полочкам вдоль и поперек.
У всех у них это свойство - сложно считать но легко проверить.
По факту это хеширование строки с изменяемой частью (в нее сериализуется число - задача подобрать число чтобы хеш строки с этим числом имел заранее оговоренные свойства, например количество младших нулевых битов хеша).
Так как у тебя академическая задача, тебе не нужно повторять именно тот самый алгоритм и настраивать инфраструктуру, просто реши задачу поиска хеша от байтового представления числа. Т.е. задача в организаци процесса - управление рабочими потоками/нодами, с раздачей заданий (интервалов в пределах которых каждый воркер будет перебирать хеши) и сбор результатов, включая обработку ошибок.