Здравствуйте, <Аноним>, Вы писали:

А>Ну нигде не могут ответить на этот вопрос.

А>И всё-таки таким уж сложным он мне определённо не кажется. Если сравнить с классикой — оценкой снизу числа сравнений для задачи сортировки — то вроде отличие должно быть незначительным. Уж явно не в категории оценок сложностей арифметических задач...

Цитата из http://www.ime.usp.br/~is/papir/sctp/node2.html

...Then an lcs is just a longest increasing subsequence of the second permutation and this problem is part of a very rich theory of representations of the symmetric group using Young tableaux extensively studied by A. Young, G de B. Robinson, C. E. Schensted and M. P. Schutzenberger. A survey focusing on the computational aspects can be found in Knuth's book [26] from which Fredman [14] extracted an algorithm to solve the longest increasing subsequence problem. His algorithm runs in time O(n*logn) and he also derives n*logn as a lower bound for the problem.

Если недостаточно, то можно попробовать поискать непосредственное доказательство.