Мне кажется, что если доказать отсутствие алгоритма меньшей сложности можно даже без предъявления алгоритма, то наличие "быстрого алгоритма" предполагает явное описание алгоритма. Без этого можно только высказывать гипотезу о его существовании.
В других областях математики царит неконструктивщина. Почему ж теория алгоритмов исключение? Не берутся за работу в этой области что ли настоящие математики: только программисты, ориентированные исключительно на практику?