П.Ц. "Нерешаемость" естественно существует, но нерешаемость (с т.з. матлогики) проблемы сама по себе является конечным результатом познания. NP-полные задачи интересны именно решаемостью и вместе с тем неспособностью решить их в заданное время. Потому что про проблему остановки и иные практически значимые нерешаемые проблемы я знаю, но еще никто не пытался аргументировать, что материализм не стоит того из-за выявленной нерешаемости матзадач.

А вот NP-полными задачами и "сложностью" щеголяли, помнится, и креационисты некоторые, но меня всегда это вводило в легкий ступор - а что ж они будут делать, если такие задачи будут разрешены неким общим квантовым алогитмом - типа алгоритма Гровера (или набором подобранных оптимальных КА типа алгоритма Шора, хотя сомневаюсь, что люди будут подбирать оптимальный КА для каждой проблемы, если смогут решать их в общем)...