Given two sequences of numbers, where each has $n$ elements, find the longest common subsequence
Doesn't LCS have a proof it's $\Omega(n^2)$ in the style of the proof that unsorted search is $\Omega(n)$ ?
I have read some papers, which I didn't understand, saying that it can't be $O(n^{2-\epsilon})$ ,assuming the exponential time hypothesis, but I think that version of LCS was with elements being letters of the alphabet.
This paper proves that for comparison-based algorithms (equal-unequal), it is $\Omega(n^2)$.
Could it be that there is an algorithm not based on comparisons that solves it faster? I have this question for sorting as well because we assume in the proof that it's $\Omega(n\log{n})$, that the algorithm is comparison based.