как мне доказать людям, что я решил задачу?
Просто я в раздумьях браться за это дело или нет.
Вы какие-то не те вопросы задаёте. Результат нужно сначала
себе самому доказать, то есть вы должны искренне верить в правильность доказательства, прежде чем пытаться доказать кому-то ещё. Если программа закончит работу и не сможет построить контрпример - вы сможете сами искренне поверить соей собственной программе?
Возможны два варианта. Первый - писать программу, как можно проще - в надежде, что контрпример существует и рано или поздно программа его надёт. В общем случае я бы не рекомендовал так делать, но из своего собственного опыта могу сказать, что один раз я так сделал. Дописал заведомо неверную программу, которая не должна была работать. А она взяла - и построила контрпример. Результат вошёл в диссертацию и подсказал дальнейшие пути для исследования.
Второй вариант - писать программу настолько качественно и тестировать её настолько тщательно, чтобы в случае, если контрпримера она не сможет построить контрпример, вы сами для себя могли бы быть уверены, что контрпримера действительно не существует. Добиться этого можно разными путями, и это зависит от задачи.
Можно, например, включить в программу возможность по требованию распечатать тот или иной фрагмент вычислений, другими словами - контролировать информацию, записываемую в лог. Самый сложный - но одновременно самый надёжный способ, на мой взгляд - это распечатать лог в таком формате, чтобы его могла проверить какая-то стронняя, независимая программа. Проще на примере: пусть требуется в процессе вычисления решить уравнение f(x)=0. Если программа распечатает x, то сторонняя программа может этот x проверить - подставить в f и посмотреть, получится 0 или нет. Или, там, перебирает программа отображения и требует их взаимной однозначности - пусть (по требованию) она эти отображения распечатает, тогда сторонняя программа пусть (некоторые из) них проверяет на взаимную однозначность...
То есть, общая идея (если ждёте, что программа не найдёт контрпример, и хотите, чтобы в этом в этом случае вы смогли поверить собственной программе, что контрпримера не существует) - это писать не одну, а
две независимые программы: одна выполняет перебор и печатает результаты своей работы в каком-то виде, в котором их сможет проверить вторая программа. Это очень сложно, можно закопаться и не написать вообще ничего - но только так вы сможете быть хоть в чём-то уверены после того, как программа завершит работу с отрицательным результатом. А потом, конечно, донести результат до остальных - ну, будет отдельная задача, напишете статью, опишете алгоритм работы обеих программ, научную ценность такая статья будет иметь несомненную.
В идеале программа должна распечатывать доказательство на каком-либо диалекте языка исчисления предикатов первого уровня или на одном из языков, используемых для верификации - Coq, Isabella, какие там ещё есть? GNU Aris (шутка).
Либо, как я уже говорил, попробовать сначала по-простому поискать контрпримеры в частных случаях - как поступить, конечно, только вы сможете решить, и только полагаясь на интуицию. Не факт, что писать одновременно две программы, которые ещё работают за достаточное время, будет проще, чем искать доказательство аналитически - опять же, решить это можете только вы, интуитивно.
, что маловероятно)