Задача о решении диофантовых уравнений является неразрешимой - в Вики есть например (статья "Десятая проблема Гильбарта").
Неограниченная задача ("Имеет ли данное диофантово уравнение целое решение?") является неразрешимой, но не принадлежит

. Ограниченная задача ("Имеет ли данное диофантово уравнение целое решение, длина которого ограничена числом

, где

--- длина записи уравнения") принадлежит

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