clang trunk стал ругаться на разыменование nullptr в compile time!
а 21-ый не ругается

починили, получается

UPD: нашел старый issue в списке фиксов к clang 22: https://github.com/llvm/llvm-project/issues/48665

Только что оглушил себя на несколько секунд тем, что слишком агрессивно куснул редиску

Ладно...

Видимо, теперь у меня +1 причина поехать на дальний восток

Я всё понял

Черный квадрат – это вид сверху на черную табуретку

Кто-нибудь

Пожалуйста

ГДЕ В МОЕМ ГИТХАБ ПРОФИЛЕ ВООБЩЕ УПОМИНАЕТСЯ JAVA???

Поставил

Настроил максимальный уровень сложности

Открываю ТГ

Меня просят перемножить два четырехзначных числа

Я на ходу

Думаю, "скучно и нерешаемо"

Удалил

А ведь идея была хорошая...

Покра, которую мы заслужили

https://www.openssh.com/pq.html

To encourage migration to these stronger algorithms, OpenSSH 10.1 will warn the user when a non post-quantum key agreement scheme is selected, with the following message:

** WARNING: connection is not using a post-quantum key exchange algorithm.
** This session may be vulnerable to "store now, decrypt later" attacks.
** The server may need to be upgraded. See https://openssh.com/pq.html

Весело...

С Рождеством?..

Обстановка на покре:

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

Пусть есть семейство схем Cₙ, разрешающих какой-то язык L. Cₙ — это схема, которая определяет принадлежность L слов длины n. Т.е. на каждую длину у нас отдельная схема. Вроде логично. Но иногда можно, в некотором смысле, лучше.

Скажем, есть проверка на равенство. В некотором смысле схема, которая умеет проверять две строки на равенство, умеет это делать для всех схем меньшего размера. Формальнее, можно сделать семейство схем Eₘ(n, x, y) размера O(m), принимающая длину входа n ≤ m и две строки длины n на сравнение, дополныных до длины m чем угодно (скажем, 0). Такая схема в некотором смысле комбинирует вычислительную мощность всех Сₙ при n ≤ m, и при этом асиммтотически имеет размер порядка O(|Cₘ|). При этом, если просто скомбинировать схемы Cₙ (+ какой-то dispatch по размеру, но это линейно от длины входа), то будет размер ∑|Cₙ| по n ≤ m. При |Cₙ| = O(n) (у нас случай проверки на равенство) это будет O(m²).

Теперь в общем случае, пусть есть язык L. Будет говорить, что семейство схем Tₙ с 2n (или log₂ n + n, не имеет значения) входами сильно распознает язык L, если x ∈ L ⟺ ∀ n ≥ |x|: Tₙ(|x|, x0...0) = 1, и Tₙ(|x|, x0...0) согласованы для всех n ≥ |x|. (UPD)

Если семейство схем сильно располнает язык, то можно семейтсво схем сколь угодно сильно "проредить", т.е. оставить только подпоследовательность схем, а для определения того, лежит ли x в L, брать любую из оставленных схем размера ≥ x. Скажем, имеет смысл делать экспоненциальное прореживание, оставляя только схемы Tₙ с n = 2ᵐ. Тогда для каждого x в оставленной подпоследовательности будет схема индекса O(|x|). Если Tₙ были полиномиального размера, то размер этой минимальной оставленной схемы, умеющей распознавать x, тоже будет полиномом от |x|, причем той же степени.

Как было замечено выше, если имеется семейство схем Cₙ, распознающая язык в обычном смысле, то, комбинируя эти схемы в одну, можно получить семейство Tₙ, распознающее L в сильном смысле, причем |Tₘ| = ∑ Cₙ + O(n) (на линию от n можно забить). Если Сₙ имеют полиномиальных размер O(nᵏ), то таким образом построенная Tₘ будет иметь размер O(nᵏ⁺¹). При этом очевидно, что если Cₙ были схемами минимального размера, то любое семейство, распознающее язык в сильном смысле, будет иметь размер не меньше, чем |Cₙ|.

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

Дальше у меня мысли такие:
- Кажется, что для полиномиально разрешимых задач зазор должен быть небольшой (какой-нибудь логарифм; для задач типа проверки на равенство/выполнения арифметических операций зазор O(1)), но я пока не понимаю, как это в общем случае объяснять.
- Можно вспомнить, что полиномиальные схемы эквивалентны полиномиальным алгоритмам со строкой-подсказкой (см. P/poly). Возможность проредить последовательность схем, сильно распознающих язык, видимо должна быть связана с возможностью сжатия последовательности строк-подсказок.

Как же приятно заполнить СОП и поставить "1" в вопросах типа "позелность курса" на психологии, вы б знали...

Радио:

До нового года осталось... 22 дня! Спонсор обратного отсчёта – ПАО <...>банк.

Поезд в метро, посвященный РУДН

Студент сегодня, выпускник завтра.

Ясно, понятно...

Я почему-то стал чаще ставить точки в конце предпожений. Это очень странно, я не понимаю, почему я это делаю.