Ученые из Массачусетского технологического института Петр Индык (Piotr Indyk) и Артурс Бэкурс (Arturs Backurs) пришли к выводу, что существующий на сегодняшний день алгоритм, позволяющий сравнивать две произвольных строки символов, является оптимальным, сообщает портал QuantaMagazine. Свою работу ученые представили на 47-ом симпозиуме по теоретической информатике и опубликовали на arxiv.org.
На сегодняшний день для того, чтобы выяснить совпадают ли между собой две произвольные строки, а если отличаются, то насколько сильно, применяется так называемый алгоритм посимвольного сравнения, который — в соответствии с названием — последовательно сравнивает каждый символ предложенных последовательностей. Для проведения этой операции требуется произвести примерно n2 операций, где n — длина исходных строк. Соответственно, чем больше по размеру исходные последовательности, тем больше потребуется времени на выполнения алгоритма. При этом последовательности могут быть очень велики, например, когда необходимо выяснить, насколько отличаются между собой две ДНК. Поэтому при работе с большими последовательностями хотелось бы применять более эффективные алгоритмы. Увы — создать ничего лучше, чем уже существующие алгоритмы, математически невозможно.
Однако, как отмечают сами исследователи, их работа основывается на предположении, что так называемая сильная гипотеза экспоненциального времени (SETH) верна, иными словами, что в худшем случае нельзя узнать, может ли то или иное логическое выражение быть истинным, пока алгоритм не подставит в него все возможные наборы значений переменных. Для выполнения такой задачи потребуется выполнить 2n операций, где n — количество переменных. Обычно это утверждение принимается как истинное, однако оно вполне может оказаться и ложным, как, например, считает Риан Вильямс (Ryan Willams) из Стэндфордского университета. И в этом случае, весьма вероятно, что существует более эффективный алгоритм сравнения двух строк и, значит, возможно ускорить процесс обработки больших данных и поиска только алгоритмическим путем, без изменения количества операций, производимых за единицу времени.
