Продолжение. Начало тут 👆.

Как работает AIXI?

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

Почему AIXI не существует на практике?

Главная проблема — невычислимость. Соломоновская индукция, лежащая в основе AIXI, теоретически оптимальна, но невозможно вычислить её точно на реальном компьютере. Это связано с тем, что поиск по всем возможным программам бесконечен и слишком затратен по ресурсам — ни один компьютер не сможет просмотреть и оценить все варианты.

Это можно сравнить с задачей поиска иголки в бесконечном стоге сена.

В результате, AIXI — это идеал, математическая модель, к которой стремятся многие алгоритмы ИИ, но которую невозможно реализовать полностью.

Зачем тогда изучать AIXI?

Потому что он задаёт эталон, к которому можно стремиться. Современные алгоритмы машинного обучения и ИИ — это приближения к AIXI. Чем больше у них ресурсов, тем лучше они могут выбирать модели и делать прогнозы.

Понимание AIXI помогает понять фундаментальные ограничения и возможности искусственного интеллекта и понять, что значит интеллект в принципе.

🧠 И вот где прикол:
Число 10 — это логичное продолжение самой простой гипотезы: шаг +2.

Но! Также можно построить много других гипотез, например:

Полином 𝑎(𝑘)=2𝑘⁴ − 20𝑘³ + 70𝑘² − 98𝑘 + 48. Он тоже даёт значения: 2, 4, 6, 8 при 𝑘=1,2,3,4, но на 𝑘=5 даёт 58.

AIXI не "предпочитает" 58, он говорит: все гипотезы возможны, но каждая имеет свою вероятность.

❓Так кто умнее?
Человек, отвечая "10", опирается на контекст и социальное ожидание от задачи.

AGI, построенный по принципу AIXI, не имеет контекста, он математически оценивает вероятности всех гипотез — и выдаёт взвешенное предсказание на основе всех возможных алгоритмов, в том числе и "неинтуитивных".

@easy_about_complex

#AGI #AIXI #Solomonoff

Продолжем выкладывать нарезки стрима „Complexity Theory meets Neuroscience“ от 11.05.2025.

Начало краткого неформального введения в теорию сложности, для тех, кто не совсем понял о чём тут говорят Дмитрий и Владимир.

Продолжение следует! Stay tuned 🧠⚡

#LiveStream #Complexity #Introduction #PvsNP

1/3
При дворе короля Артура жили 150 рыцарей и 150 дам.

«Почему бы не создать 150 супружеских пар?» — размышлял король, и мысль немедленно была претворена в действие. Он поручил Королевскому Секретному Агенту (Royal Secret Agent = RSA) составить диаграмму, включающую все 300 имён, указывая красной линией взаимный интерес между дамой и рыцарем, а при его отсутствии — синей линией. Диаграмма с 150² = 22 500 цветными линиями выглядела довольно запутанно, но не настолько, чтобы запутать Мерлина, придворного мага, которому Артур передал её с чётким приказом: найти совершенное соответствие между дамами и рыцарями (по взаимной любви).

Мерлин удалился, посмотрел на диаграмму и,благодаря своему безграничному интеллекту, мгновенно понял, что ни одна из 150!(≈5×10^262) возможных пар не даёт полностью красного соответствия. Он быстро перебрал все 5×10^262 диаграмм, выделив в каждой ошибочную линию, и приказал слугам отнести их в тронный зал как доказательство того, что Артур потребовал невозможного.
Продолжение👇

2/3. Начало тут 👆

Разумеется, даже малая часть этих диаграмм не могла поместиться в зале, но Артур не стал даже дожидаться, пока зал наполнится. Он отклонил метод Мерлина («очевидно, ты что-то упустил») и приказал ему вернуться с решением на следующий день. Дневники Артура раскрывают ещё одну мысль, которая его тогда занимала:
«Жизни Вселенной не хватит, чтобы проверить всю эту ерунду. Старый лис хочет обмануть меня.»

Мерлин знал, что прав, и также знал, что Артур — человек разумный. Всё, что ему оставалось — убедить его за пять минут, что решения не существует.

По счастливой случайности, в столовой он наткнулся на скромного человека в новеньких синих джинсах. Это был гость из Восточного блока, который скромно представился как Дьенеш Кёниг, номер один среди экспертов по идеальным соответствиям. «Вас, возможно, заинтересует моя мини-макс теория?»
Найдя наконец внимательного слушателя, гость забыл про картошку фри и бесплатный кетчуп, и начал с энтузиазмом читать лекцию о двудольных графах, максимальных соответствиях и минимальных покрытиях. Мерлина ничуть не смущал ни сильный акцент, ни размашистые жесты. Вскоре Мерлин понял, что всё, что ему нужно чтобы убедить Артура в невозможности переженить всех рыцарей и дам по взаимной любви — это найти препятствие Кёнига: множество из k рыцарей, каждый из которых интересуется лишь (k − 1) дамами.

Мерлин тут же увидел, что такое препятствие действительно существует (при k = 79). С помощью не слишком гениального, но довольно надёжного придворного астронома, Артур быстро убедился, что группа из 79 рыцарей действительно представляет собой препятствие Кёнига. Таким образом убедившись в правоте Мерлина, Артур смирился с невозможностью найти совершенное соответствие и начал искать другие пути для улучшения общества.

Продолжение тут 👇

3/3. Предыдущая часть 👆

Летописи свидетельствуют, что Мерлин недолго ждал следующего поручения.

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

Артуру показалось, что манеры за столом можно было бы значительно улучшить с правильной рассадкой рыцарей. Как и прежде, он вызвал RSA (Royal Secret Agent), который составил граф, показывающий, кто с кем сможет сидеть мирно. Задача найти подходящую рассадку (то, что позже назовут гамильтоновым циклом в графе) снова была поручена Мерлину.

Когда Мерлин понял, что решения нет, он больше не стал прибегать к трюку с 150! диаграммами — он просто написал Кёнигу. Но либо почта шла слишком медленна, либо возникло другое препятствие — ответа Кёнига на это письмо так и не поступило. Не сумев представить решение в установленный срок, Мерлин был приговорён к виселице. Однако приговор был немедленно заменён на «вечность в темнице с возможностью условного освобождения после отбытия одной трети срока».

(c) László Babai
🔗 Источник: László Babai "E-mail and the unexpected power of interaction"

Это была наша новая рубрика #ВГостяхУСказки, а так же подводка к следующему посту про класс сложности IP (интерактивные доказательства - маг Мерлин с безграничными интеллектуальными возможностями и полиномиальный король Артур), а так же про удивительное доказательство теоремы IP=PSPACE.

#Complexity #IP #PSPACE #IPvsPSPACE

🏃‍♂️🏞️ 18.05, 14:00, Побегаем в Олимпиапарке, без фанатизма!

Друзья из Мюнхена (и окрестностей), кто хочет размяться и встряхнуться — собираемся завтра 18.05, в воскресенье, 14:00 в Олимпиапарке!

📏 Дистанция — примерно 9-10 км
📈 Перепад высоты — около 140 м (по ощущениям — чуть меньше 😄)
⏱️ Время в пути — ~1 час, но каждый бежит в своём темпе. Можно и пешком, можно и с паузами на болтовню и фоточки 📸

Формат супер-лайтовый! Это не чемпионат и не страдание, а скорее дружеская пробежка с видом на горки и весенний вайб 🌸

Оставьте коммент - договоримся где именно там встретимся.

#running #sport #olympiapark #munich

1/2

🔮 Возвращение Мерлина
IP = PSPACE и освобождение мага

Как вы, дорогие друзья, помните из этого поста, маг Мерлин был приговорён к заточению за то, что не смог за полиномиальное время убедить короля Артура в неразрешимости определённой задачи рассадки рыцарей за круглым столом.

Века шли в сером однообразии. Единственными радостями Мерлина были щебетание птиц у окна и редкие письма по электронной почте. Он продолжал заниматься теорией сложности, читал форумы по TCS и в какой-то момент осознал, что если NP ≠ coNP, то, возможно, он никогда не сможет убедить Артура.

Так было до 26 декабря 1989 года.

Рождество только что закончилось,
был четвертый день Хануки. Мерлин, как обычно, дремал днём, а проснувшись — проверил почту.

💥 На экране мигал заголовок письма из Израиля:

From: shamir%[email protected]
Subject: IP = PSPACE

📜 В этом кратком письме заключалась крутая идея: Ади Шамир показал, что весь класс PSPACE поддаётся проверке с помощью интерактивных доказательств.

Продолжение 👇👇👇

2/2. Продолжение. Начало тут 👆

Почему это важно? Во-первых, этот реультат контр-интуитивный. Считалось, что класс IP это где-то между NP и PSPACE, чуть больше NP, но и близко не дотягивает до PSPACE.

IP - это проверяющий с ограниченным полиномиальным временем мышлением, как король Артур (полином от времени/числа шагов и немного рандома) и неограниченный в вычислительных возможностях доказывающий оракул с сверхспособностями, как Мерлин.

Артур может быть убеждён в любых вещах уровня PSPACE (а это мощный класс задач, например, шахматы), если общается с могучим доказывающим (Мерлин). Это радикально изменило понимание того, насколько мощными могут быть системы доказательств, даже с очень ограниченным проверяющим.

С опорой на классическую PSPACE-полноту задачи верификации кванторной булевой формулы (QBF), Шамир дал то, чего Мерлину так не хватало — мощный, вероятностный протокол убеждения. И у Мерлина появился шанс снова оказаться на свободе.

🖨️ Пока старенький принтер печатал короткий документ, Мерлин завершил вычисления и написал письмо Артуру:

Дата: 26 дек 89, 19:42:14 BST
От: merlin@cave
Кому: arthur

Сир,
в отдельном сообщении я отправляю вам
матрицу M порядка 103 680 300 с элементами
из множества {-1, 0, 1, 2, 3}. Со ссылкой на
L.G. Valiant, TCS 8 (1979), стр. 189–201,
вы без труда убедитесь, что перманент
матрицы M равен 2^{43 200 000}, умноженному
на количество гамильтоновых циклов в
«графе рассадки».

Дайте знать, когда у вас будет время
на полиномиальные вычисления.
С вероятностью 1 - 2^{-1000}
я уверю вас, что этот перманент равен нулю.

Освежите свои знания по линейной алгебре, правилу Горнера, и держите игральные кости наготове.

С уважением,
Мерлин

P.S. Спасибо за подключение к сети.
P.P.S. Что касается компенсации — мне хватит позиции в университете Чикаго.

📍Теперь Мерлин держит путь к Новому Свету. Сначала — Йель (он знал кого-то в тех краях), потом — Великие озёра (Great Lakes).

🍀 Пожелаем ему попутного ветра и продуктивных интеракций.

🔗 Источник: László Babai "E-mail and the unexpected power of interaction"

@easy_about_complex

#ВГостяхУСказки #Complexity #IP #PSPACE #IPvsPSPACE

Друзья!

Если вдруг вы всё ещё не в нашей группе на Facebook — срочно исправляйтесь!

Заходите, не стесняйтесь:
👉 https://www.facebook.com/groups/1199204141422687

Будем рады каждому, даже тем, кто зашёл «просто посмотреть» 😉

Кто из Мюнхена: напоминаю, что уже в эту субботу 24-го мая у нас в городе поэтический вечер/концерт Анны Либерт @frauliebert

Я лично пойду.

#Culture #Poetry #Munich

1/3

🧠 Время и пространство в вычислениях: новая перспектива на разделение классов P и PSPACE


В феврале 2025 года Райан Уильямс из MIT представил работу, которая может стать важным шагом в понимании различий между временной и пространственной сложностью алгоритмов.

🧩 Почему P ⊆ PSPACE — это просто, а обратное — сложно?
Интуитивно понятно, что если алгоритм работает за полиномиальное время (класс P), то он не может использовать больше памяти, чем времени, ведь за каждый шаг он может использовать не более одного нового блока памяти. Поэтому P ⊆ PSPACE.

Однако доказать, что PSPACE ⊆ P, крайне трудно. Это связано с тем, что память можно переиспользовать: мы можем записывать данные, удалять их и использовать ту же область памяти снова. Время же — это однонаправленный ресурс: его нельзя "перезаписать" или "переиспользовать". Это делает время более ограниченным ресурсом по сравнению с пространством/памятью.

Продолжение тут 👇

2/3. начало тут 👆

🧠 Что нового в работе Уильямса?
Уильямс показал, что любую многоленточную машину Тьюринга, работающую за время t(n), можно симулировать, используя всего O(√(t log t)) памяти. Это значительное улучшение по сравнению с предыдущим результатом 1975 года, где требовалось O(t / log t) памяти. Ключевым элементом этого достижения стало использование эффективного алгоритма для задачи оценки деревьев, недавно разработанного Куком и Мерцем (2024).

🔍 Почему это важно для P vs PSPACE?
Результат Уильямса - любую задачу, решаемую за время t(n), можно просимулировать, используя всего O(√(t log t)) памяти. Это означает, что временные вычисления можно очень эффективно "перевести" в пространственные, и при этом не требуется много памяти.

Теперь главный момент:

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

Конкретнее:

✳️ Формальное следствие из результата Уильямса (Corollary 1.2) - существуют задачи, которые можно решить с памятью
n, но никакой алгоритм не сможет их решить за время меньше, чем почти n². Это ещё не доказывает, что они вне P,
но приближает нас к такому доказательству.

Результат Уильямса не показывает, что задача из PSPACE не в P (т.е. не опровергает P = PSPACE напрямую),
а показывает, что существуют задачи, решаемые в линейной памяти, которые не могут быть решены за время n^k для любого фиксированного k — то есть не в P, если бы это удалось доказать для всех полиномов.

Но сейчас доказано только, что они не решаются быстрее, чем n².
Это ещё не доказывает, что они вне P, но приближает нас к такому доказательству.

Продолжение тут 👇

3/3. предыдущая часть тут 👆

🧠 Подробно и по шагам:

1. Что показывает Уильямс?
Он доказывает, что любую t(n)-временную многоленточную машину можно симулировать с памятью
O(√(t log t)).

То есть: если алгоритм работает за время t(n), то можно смоделировать его в меньшем объёме памяти, чем раньше считалось возможным.

2. Как это используется для разделения P и PSPACE?
Возьмём задачу, решаемую в линейной памяти (s(n) = O(n)) — то есть она точно лежит в PSPACE.

По теореме Уильямса, если бы она решалась за время t(n),
то должно быть:
√(t(n) log t(n)) ≥ n
⇒ t(n) ≥ n² / log n
⇒ t(n) — как минимум квадратичное.

То есть: существуют линейно-памятные задачи, которые не могут быть решены быстрее, чем примерно n².

3. Почему это приближает нас к P ≠ PSPACE?
Класс P включает задачи, решаемые за время O(n^k) для некоторого фиксированного k.

То есть, если бы все задачи из PSPACE решались за полиномиальное время, то было бы P = PSPACE.

Но результат Уильямса показывает, что существуют задачи, которые:
- находятся в PSPACE (решаются в линейной памяти),
- но не решаются быстрее, чем n².

⚠️ Это ещё не доказательство, что они не решаются за любое полиномиальное время (например, n^10),
но это сдвиг границы — от "возможно, они все почти линейные" → "некоторые требуют уже n² или больше".

📌 Вывод:
- Да, n² — это всё ещё полиномиальное время, но важно, что впервые показано, что задачи в линейной памяти не решаются за линейное время. До этого момента в теории сложности удавалось показать лишь слабые верхние и нижние
оценки времени (O(t(n)/log t(n)), Ω(t(n)log t(n)) для задач, решаемых в в линейной памяти, которые всё ещё почти линейные. Но это недостаточно, чтобы показать разделение классов P и PSPACE.
- Это сужает возможное пересечение P и PSPACE.
- Если бы удалось доказать, что задача требует время больше, чем любое полиномиальное, это дало бы P ≠ PSPACE.

@easy_about_complex

#Complexity #P #PSPACE #PvsPSPACE

#НастроениеПятницы - в Мюнхене на днях

#Munich

В рамках рубрики #НастроениеПятницы девушка, которая подписана на наш канал и моя очень давний и хороший друг прислала такую картинку 👇👇👇

#НастроениеПятницы #черныйЮмор #Entertainment

Был сегодня на поэтическом вечере Анны — 1,5 часа пролетели как 15 минут. Очень классный перформанс, Анна здорово держит сцену и вовлекает. Атмосфера уютная, публика приятная — прямо хорошее время! В завершении была песня, где Анна поёт совместно с ИИ, да-да — необычно и по-своему трогательно.

Весь поэтический вечер реально цепляет и вызывает эмоции. Абсолютно не жалею, что сходил — и с удовольствием сходил бы ещё раз.

Анна сейчас ездит с выступлениями по городам Германии, а скоро будет в Екатеринбурге (привет нашим подписчикам из России). Если снова заглянет в Мюнхен — пойду ещё раз без раздумий.

Рекомендую, особенно если вам важна не только поэзия, но и то, как она подаётся.

#Culture #Poetry #Munich

@frauliebert
https://www.instagram.com/frauliebert/

P.S. Пару видео сейчас добавлю в комментарии

#НастроениеВоскресенья #АйтишныйЮмор