Группа ученых из Гарвардского университета под руководством профессора Джорджа Уайтсайдза (George Whitesides) недавно опубликовала в трудах Национальной Академии наук США статью, заставившую поволноваться многих специалистов. В статье было предложено устройство, способное быстро решать задачу перебора - одну из труднейших нерешенных задач теории алгоритмов. Его экспериментальный экземпляр представляет собой пластиковый чип, размером с почтовую марку, для решения NP-полной задачи о максимальной клике для любого графа с шестью вершинами. В задаче о максимальной клике требуется найти на карте наибольшую группу городов, каждый из которых напрямую соединен дорогой со всеми городами этой группы. Для ее решения неизвестен алгоритм лучше, чем прямая проверка всех возможных групп городов. Их количество - 2n - быстро растет с увеличением числа городов - n. Это делает невозможным решение задач этого типа на любом современном компьютере при больших n. В прозрачном пластиковом чипе в трех измерениях проделаны микроканалы, в которые заливается жидкость с флуоресцирующими микрочастицами. Каналы организованы таким образом, что наибольшее количество задержанных фильтром частиц собирается в вертикальном колодце, который соответствует максимальной клике. Его можно обнаружить с помощью фотоэлементов по яркости свечения частиц. Авторы утверждают, что как время изготовления чипа, так и длительность процесса решения задачи растут лишь степенным образом с ростом количества городов. Если бы жидкий компьютер можно было создать для графа с несколькими сотнями или тысячами вершин, это произвело бы революцию в компьютерной науке. Более того, это привело бы к фатальным последствиям для современных методов шифрования информации. К сожалению или к счастью, предложенная технология не имеет будущего. Весьма сомнительны и другие попытки создания классических аналоговых устройств для решения проблемы перебора. Подробнее об этом читайте в статье Галактиона Андреева «Жидкая логика» (Часть 1 и Часть 2). Источник новости: Nature technology Liquid logic