15 августа, 2022

zhukvesti

Находите все последние статьи и смотрите телешоу, репортажи и подкасты, связанные с Россией.

Исследователь разрабатывает новый инструмент для понимания сложных и, казалось бы, неразрешимых вычислительных задач.

В некоторых случаях диаметр каждого пика будет намного меньше, чем расстояние между различными пиками. Таким образом, если бы кто-то выбрал любые две точки на этом растянувшемся ландшафте, то есть два возможных «решения», они были бы либо очень близки (если они исходили из одной и той же вершины), либо очень далеко друг от друга (если взяты с разных вершин). . Другими словами, между этими расстояниями будет явный «разрыв» — маленький или большой, но ничего промежуточного. Предоставлено: Дэвид Ямарник и др.

Мысль о том, что некоторые вычислительные задачи в математике и информатике могут быть сложными, не должна вызывать удивления. На самом деле существует целый класс задач, для которых считается невозможным математическое решение. Ниже этой категории находятся несколько «более простых» задач, которые недостаточно хорошо изучены, и они также могут быть неразрешимыми.


Дэвид Джамарник, профессор исследования операций в Школе управления Слоана Массачусетского технологического института и Институте данных, систем и общества, сосредоточивает свое внимание на последней категории менее изученных проблем, которые более актуальны для повседневного мира, поскольку они связаны с Случайный— неотъемлемая черта природных систем. Он и его коллеги разработали мощный инструмент для анализа этих проблем, называемый свойством перекрывающихся пробелов (или OGP). Гамарник описал новую методологию в недавней исследовательской статье в Труды Национальной академии наук.

П НП

Пятьдесят лет назад была сформулирована самая известная проблема теоретической информатики. P ≠ NP спрашивает, существуют ли проблемы, связанные с огромными наборами данных, ответ на которые можно проверить относительно быстро, но решение которых, даже при работе на самых быстрых доступных компьютерах, займет абсурдно много времени.

Гипотеза P ≠ NP остается недоказанной, однако большинство ученых-компьютерщиков считают, что многие знакомые задачи, включая, например, задачу о коммивояжере, попадают в эту невероятно сложную категорию. Задача в примере с продавцом состоит в том, чтобы найти кратчайший маршрут с точки зрения расстояния или времени через N разных городов. С задачей легко справиться, когда N = 4, потому что нужно рассмотреть только шесть возможных путей. Но в 30 городах их более 10.30 возможные способы, и оттуда числа растут в геометрической прогрессии. Самая большая трудность заключается в разработке файла алгоритм Он решает задачу быстро во всех случаях, для всех целых значений N. Компьютерщики уверены, основываясь на теории вычислительной сложности, что такого алгоритма, подтверждающего, что P ≠ NP, не существует.

Есть много других примеров таких неразрешимых проблем. Предположим, например, что у вас есть огромная таблица чисел с тысячами строк и тысячами столбцов. Сможете ли вы найти из всех возможных комбинаций точное расположение десяти строк и 10 столбцов так, чтобы их сто элементов имели наибольшую достижимую сумму? «Мы называем их задачами оптимизации, потому что вы всегда пытаетесь найти самое большое или лучшее — самую большую сумму чисел, лучший маршрут через города и т. д.», — говорит Ямарник.

Ученые-компьютерщики давно поняли, что невозможно создать быстрый алгоритм, который во всех случаях мог бы решать проблемы так же эффективно, как сага о коммивояжерах. «Вероятно, такое было бы невозможно по вполне понятным причинам», — отмечает Ямарник. «Но в реальной жизни природа не создает проблем с враждебной точки зрения. Она не пытается расстроить вас тщательно подобранной, самой сложной проблемой, какую только можно себе представить». На самом деле, люди обычно сталкиваются с проблемами в более случайных и менее управляемых обстоятельствах, и это проблемы, на решение которых направлено Партнерство «Открытое правительство».

Пики и долины

Чтобы понять, что такое Партнерство открытого правительства, может быть полезно сначала увидеть, как возникла эта идея. С 1970-х годов физики изучают спиновое стекло — материалы, обладающие свойствами как жидкостей, так и твердых тел с необычным магнитным поведением. Исследования спиновых стекол породили общую теорию сложных систем, связанную с задачами физики, математики, информатики, материаловедения и других областей. (Эта работа принесла Джорджио Барези Нобелевскую премию по физике 2021 года.)

Одна запутанная проблема, с которой столкнулись физики, — это попытка предсказать энергетическое состояние, особенно конфигурации с наименьшей энергией, различных вращающихся стеклянных структур. Ситуация иногда изображается в виде «пейзажа» бесчисленных горных вершин, разделенных долинами, где цель состоит в том, чтобы найти самую высокую вершину. В этом случае самый высокий пик фактически представляет состояние с самой низкой энергией (хотя вместо этого можно было бы перевернуть изображение и найти самую глубокую дыру). Это оказывается проблемой оптимизации, похожей по форме на дилемму коммивояжера, поясняет Ямарник: «У вас есть этот огромный набор гор, и кажется, что единственный способ найти выше — это взобраться на каждую из них» — тщетная рутинная работа, похожая на найти иголку в стоге сена.

Физики показали, что вы можете упростить эту картину и сделать шаг к решению, срезая горы до определенной заданной высоты и игнорируя все, что ниже этого уровня отсечения. Затем вы оставите группу выдающихся пиков над однородным слоем облаков, где каждая точка в этих пиках представляет потенциальное решение исходной проблемы.

В исследовательской работе 2014 года Ямарник и его коллеги отмечают то, что ранее упускалось из виду. В некоторых случаях они поняли, что диаметр каждого пика будет намного меньше, чем расстояние между разными пиками. Таким образом, если бы кто-то выбрал любые две точки на этом растянувшемся ландшафте, то есть два возможных «решения», они были бы либо очень близки (если они исходили из одной и той же вершины), либо очень далеко друг от друга (если взяты с разных вершин). . Другими словами, между этими расстояниями будет явный «разрыв» — маленький или большой, но ничего промежуточного. Ямарник и его коллеги предположили, что система в данном случае характеризуется OGP.

«Мы обнаружили, что все известные задачи вычислительно сложной случайной природы имеют версию этого свойства» — то есть диаметр горы в схематической модели намного меньше, чем расстояние между горами, — утверждает Ямарник. «Это обеспечивает более точную оценку надежности алгоритма».

Раскрытие секретов сложности алгоритма

Появление OGP может помочь исследователям оценить сложность создания быстрых алгоритмов для решения конкретных задач. Это уже позволило им «математически [and] Он решительно исключил большой класс алгоритмов как потенциальных конкурентов», — говорит Ямарник. В частности, мы узнали, что стабильные алгоритмы — те, чьи выходные данные не сильно изменятся, если входные данные изменятся лишь незначительно, — не смогут решить такого рода задачи оптимизации. «Этот отрицательный результат относится не только к классическим компьютерам, но и к квантовым компьютерам, в частности, к так называемым «алгоритмам оптимизации с квантовым приближением» (QAOA), которые, как надеялись некоторые исследователи, решат те же проблемы оптимизации. Теперь, учитывая результаты Ямарника и выводы соавторов, эти надежды умеряются признанием того, что для успеха алгоритмов типа QAOA потребуется много уровней операций, что может быть технически сложным.

«Хорошие это новости или плохие, зависит от вашей точки зрения», — говорит он. «Я думаю, что это хорошая новость в том смысле, что она помогает нам раскрыть секреты алгоритмической сложности и расширяет наши знания о том, что находится в области вероятности, а что нет. Плохая новость в том смысле, что она говорит нам, что эти проблемы сложно, даже если их производит природа, и даже если они генерируются случайным образом». Он добавляет, что в новостях нет ничего удивительного. «Многие из нас ожидали этого с самого начала, но теперь у нас есть гораздо более прочная основа для такого утверждения».

Это все еще оставляет исследователей в световых годах от возможности доказать, что не существует быстрых алгоритмов, которые могут решать эти задачи оптимизации в случайных условиях. Наличие таких доказательств дало бы окончательный ответ на проблему P NP. Он говорит: «Если мы сможем доказать, что у нас не может быть алгоритма, который работает большую часть времени, это говорит нам, что у нас определенно не может быть алгоритма, который работает все время».

Предсказание того, сколько времени пройдет, прежде чем проблема P NP будет решена, само по себе кажется неразрешимой проблемой. Скорее всего, придется подняться на множество пиков и пересечь долины, прежде чем исследователи получат более четкое представление о ситуации.


Решайте «большие проблемы» с помощью алгоритмов, улучшенных с помощью 2D-материалов


Дополнительная информация:
Дэвид Джамарник, Свойство вложенного разрыва: топологический барьер для оптимизации стохастических структур, Труды Национальной академии наук (2021). DOI: 10.1073/pnas.2108492118

цитата: исследователь разрабатывает новый инструмент для понимания сложных и, казалось бы, неразрешимых вычислительных задач (10 января 2022 г.). Получено 11 января 2022 г. с https://phys.org/news/2022-01-tool-hard-problems-intractable.html.

Этот документ защищен авторским правом. Несмотря на любые добросовестные отношения с целью частного изучения или исследования, никакая часть не может быть воспроизведена без письменного разрешения. Контент предоставляется только в ознакомительных целях.

READ  Подтверждено еще 2 случая - NECN