Есть ли такие задачи, в которых можно легко узнать что решение существует, но найти его практически нереально?

Question

И как называется такой комплекс задач?

Answer 1

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

Answer 2

Пока решения не будет, предположение что оно существует может быть ошибочным. В математике недоказанное может быть не правильным. Если что то может быть не правильным, то оно не может быть истинным. В логике нету полуистин.