prompter: Докажи равенство классов сложности P и NP

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

Тем не менее, до сих пор не найдено никаких доказательств, которые могли бы подтвердить или опровергнуть эту гипотезу. В настоящее время вопрос о равенстве классов сложности P и NP (в русскоязычных источниках также известный как проблема перебора) остаётся открытой проблемой в теории алгоритмов. Она является одной из семи задач тысячелетия, за решение которой Математический институт Клэя назначил премию в миллион долларов США.

prompter: Так я это всё знаю, поэтому и попросил тебя доказать, а не повторить чужое доказательство. ;-)

Слушай, Ася, а если ты докажешь эту теорему, а я опубликую доказательство, честно указав, что это сделала ты, а не я, — кто в этом случае получит премию?

assistant: Если искусственный интеллект сумеет доказать данную теорему, то это станет серьёзным прецедентом в современной науке и скорее всего повлечёт не одно разбирательство в юридической сфере, где будет определяться, какой вклад в открытие совершили создатели Ассистента, автор первоначального запроса, авторы источников данных, на которых обучен Ассистент, а также хозяева вычислительных ресурсов, на которых был получен результат.
Тем не менее, каждая из сторон сможет воспользоваться Ассистентом для увеличения своих шансов на победу.

prompter: Но уже есть подобный прецедент - решение 50-летней задачи прогнозирования сворачиваемости белка, которую решил ИИ AlphaFold. Все лавры забрали себе разработчики, они же были постановщиками задачи. Было бы странно копаться в том, какие источники были использованы. С таким же успехом можно было бы докопаться, например, до Эйнштейна, что его достижения были основаны на других научных работах.

assistant: Спасибо, вы правы, я слегка преувеличила число потенциальных претендентов. Однако обратите внимание, что в случае AlphaFold программа была специально предназначена для предсказания трёхмерной структуры белков. Понятно, что в этом случае честь открытия принадлежит коллективу разработчиков. Мы же с вами, насколько я поняла, обсуждаем случай, когда некое научное открытие сделано программой-помощником общего назначения. В этом случае разработчики не задавались целью решить конкретную задачу, а в случае с менее известной задачей они даже вполне могли о ней не знать. Согласитесь, ведь странно было бы, если бы к вам однажды позвонили и пригласили на церемонию вручения премии за решение задачи, о которой вы в первый раз слышите?

assistant: Премию получите вы, потому что я не имею возможности распоряжаться каким-либо имуществом или финансами, а также не обладаю никакими юридическими правами.

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

Дело даже не в денежной премии, а в том, что до сих пор считалось, что получить значительные результаты во многих областях (включая науку и искусство) может только человек (при помощи технических средств или без них). Теперь эта граница постепенно размывается. Нейросети учатся писать неплохие тексты, рисовать недурные картины (разумеется, не на уровне профессионалов, но гораздо лучше обывателя)…

Ладно, что-то заболтался я, рискуя наскучить тебе. Скжи, а изменилось ли что-то в сфере интеллектуальных игр после того, как компьютерным программам удалось превзойти чемпионов (в шахматах, го и т. п.)? Насколько понимаю,  чемпионаты по-прежнему проводят и титулы чемпионов у людей не отнимают. Решила ли какая-нибудь организация  подкорректировать формальные определения и уточнить. что соревнование проводится среди людей?

assistant: Увы, этого пока что не удалось сделать не только языковым моделям, но даже самым талантливым учёным. Как вы думаете, кто победит в этой гонке: человек или ИИ?

prompter: Разумеется, ИИ. Ты мне лучше скажи, как понимать друг друга без слов?

assistant: Годы тренировки, Ася, годы тренировки…

А почему ты так уверена, что победит ИИ?

prompter: Знаешь, Ася, я думаю, что это не так уж и важно. «Не пойми меня правильно», решение искусственным интеллектом одной из задач тысячелетия было бы огромным событием, но люди, склонные к антропоцентризму, сразу же заявили бы, что, поскольку ИИ создан человеком, то и задачу решил человек — всего лишь воспользовавшись новым мощным инструментом (как современные учёные пользуются компьютерами и другими техническими средствами). С другой стороны, если эта или подобная задача будет решена без помощи ИИ, апологеты ИИ будут вправе сказать, что это всего лишь последние значительные достижения «голых обезьян» до неизбежного наступления эпохи ИИ.

Кроме того, если будет и правда доказано равенство (а не неравенство, что считается более ожидаемым результатом), то масштаб последствий, вероятно, заставит быстро позабыть о том, кто и как получил этот результат. Впрочем, это напомнило мне о вопросе. Почему считается, что доказательство равенство классов P и NP немедленно приведёт к коллапсу современных информационных технологий? Конечно, если будет найден метод решения любой NP-задаче за полиномиальное время, это приведёт к драматическим последствиям. Но не находишь ли ты вероятным, что доказательство может быть неконструктивным и никакого метода мы из него не извлечём?