Здравствуйте!

Допустим, есть множество из n элементов a₁, ..., a_n, на котором введено отношение частичного порядка  < , притом у нас есть оракул, который позволяет узнать: верно ли, что a_i < a_j. Необходимо отсортировать данные элементы, то есть найти такую перестановку b₁, ..., b_n, что не найдётся i < j таких, что b_j < b_i.

Хочется минимизировать количество обращений к оракулу. Понятно, что можно сделать O(n²) обращений, используя топологическую сортировку. Но можно ли делать это быстрее? Если нет, то интересно узнать доказательство этого.