Друзья, накидывайте темы и направления на следующие стримы. Вот один вариант предложенный Никитой 👇👇👇

Видео этого стрима будет в нарезках по темам через какое-то количество дней. Но уже думаем над следующими стримами. Кому интересно что-то рассказать, представить, узнать, обсудить - пишите!

Вводная статья об AIXI - определение "универсального интеллекта" в theorethical computer science:
https://arxiv.org/abs/0712.3329v1

Для чего это нужно?
Условно закрыть философский гештальт: «а что такое интеллект в самом общем смысле?»

Сегодня на стриме Дмитрий, в частности, показал, что RNN могут в теории эмулировать произвольную машину Тьюринга. Я вижу, конечно, с этим проблему в том, что на практике вы никогда не получите веса связей из множества Кантора с желаемой точностью. Результат интересный, но для практического описания реальных возможностей ИИ не подходит.

Популярно об AIXI еще можно почитать в книге Сбербанка, смотрите комментарий к посту)

🎥 Начинаем выкладывать по маленьким кусочкам записи стрима от 11 мая — "Complexity Theory meets Neuroscience".

Если пропустили в прямом эфире или хотите пересмотреть отдельные моменты — самое время!

Самое начало стрима 👆👆👆

Stay tuned 🧠⚡

#LiveStream #PureMath #AppliedMath #Complexity #Neurscience

🎥 Хайлайты лайв-стрима от 11 мая — "Complexity Theory meets Neuroscience".

Дима очень кратко и чётко рассказывает о своём видении решения задачи тысячелетия: P ≠ (?) NP. Владимир вносит несколько важных уточнений касаемо практической значимости строгого математического доказательства этой фундаментальной проблемы. Завязывается дискуссия и дебаты, но в итоге ребята приходят к консенсусу! Так же затронута тема квантовых вычислений и мостик между квантовыми алгоритмами и классической теорией сложности алгоритмов.👆👆👆

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

#LiveStream #Complexity #PvsNP #QuantumComputing

Кто не все понял в этом видео 👆 - не расстраивайтесь. Скоро будут нарезки из стрима с введением в эти темы.

AIXI - гипотетический идеал Искусственного Общего Интеллекта (Artificial General Intelligence - AGI).

❓Кто умнее — вы или AGI?

Представьте, что вы проходите тест на IQ и вам нужно продолжить числовой ряд: 2, 4, 6, 8, …

Первый инстинкт — ответить «10». Но что, если я скажу, что этот ряд также удовлетворяет сложному полиному:
2k⁴ − 20k³ + 70k² − 98k + 48, согласно которому следующее число в последовательности 58, а не 10!

Как же понять, какое продолжение правильное?

Вот тут на помощь приходит принцип бритвы Оккама из философии — выбор самого простого и краткого объяснения (или алгоритма), которое описывает данные.

Теория Соломонова формализует этот принцип с помощью понятия колмогоровской сложности — длины кратчайшей программы, которая может сгенерировать данный ряд чисел.

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

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

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

Как работает 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, но приближает нас к такому доказательству.

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