Достаточно одной стратегии, которая ведет к бесконечной игре, чтоб опровергнуть Ваше утверждение. Всего одной.

И никак не доказана эквивалентность тех, что он не делает, тем что он делает.

Тут даже комментировать нечего — какая-то бессмыслица.

Множество стратегий — тоже не доказано, а грозился дать «бесконечное количество».

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

Какое еще «всем известно»? Вы сейчас о чем вообще? Вы привели утверждение, будто ВСЕ игры гомоку — конечны. Я привел ОДНУ из стратегий, которая ведет к бесконечной игре, тем самым опровергая Ваши слова. Иначе говоря — не все игры конечны. Это называется найти контрпример. И это самый распространенный прием в математике, когда тебе надо опровергнуть какое-либо утверждение.

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

Какое еще расхождение числового ряда? Что еще за ряд?! То, что множество стратегий, которые ведут к бесконечным играм — бесконечно, доказывается очень просто. Я, собственно, показал это, когда сказал, что можно делать произвольные отступы между камушками оппонентов. Так что пальцев Вам не хватит их перечислить. Более того, это множество счетно бесконечное, так как каждая стратегия описывается словами из конечного алфавита (пусть это даже будут слова из какого-либо естественного алфавита).

А в чем проблема раскрытия эллиптической кривой? Это никакая не закрытая и не секретная информация. Даже больше, все используют кривые, которые предложил NIST, и которые лежат в открытом доступе. Правда, никто не знает точно почему именно эти кривые были предложены, а потому есть шанс, что NIST все же умеет их ломать. Но это уже другой разговор.

Ну, не хотите на север — пусть будет на восток или на запад, или на юг. Можно даже по диагонали. Или по любой другой траектории, которая уходит в бесконечность. А еще можно камушки класть не друг за другом, а через какие-то промежутки.

Суть в том, что существует бесконечное количество стратегий, которые опровергают Ваши слова, будто есть «интересное доказательство», что все игры в гомоку — конечны. Из-за чего сразу же следует вполне резонный вопрос: зачем Вы обманываете народ, будто бы Вы знаете какое-то доказательство, хотя знать его не можете, так как его просто не существует?

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

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

А почему

квантовое превосходства гугла со вкусом н***ки свежо в памяти

Что именно там не так?

Это оптимальное решение. Если я Вам дам какое-то дерево и зафиксирую две вершины, Вам понадобится в худшем случае Θ(n) времени, чтоб только «изучить» топологию Вашего дерева. Это неизбежный шаг в любом алгоритме. То есть любой алгоритм будет работать на самых худших входных данных не быстрее, чем Ω(n).
А Ваш алгоритм работает за время O(h) = O(n). То есть этот алгоритм в самом худшем случае работает по нижней границе всех возможных алгоритмов. Это оптимум.

А то, что Вас не устраивает алгоритм за время O(h) (который на самом деле O(n)), и вместо этого Вы пытаетесь искать какой-то «оптимальный» алгоритм, который работает за время O(nlog(n)) (то есть медленней) — это вызывает удивление и подозрение, что Вы не очень понимаете, как читать символы Ландау.

У меня есть пару замечаний по поводу LCA:
— Вы должны определиться, какую именно задачу Вы решаете. Ваш алгоритм — это решение для произвольного дерева и произвольных вершин u и v, и Ваш алгоритм является оптимальным в том плане, что нет алгоритма, который решал бы эту задачу быстрей (правда, не очень понятно, зачем искать глубины вершин u и v). Те замечания про более оптимальные алгоритмы в вики — они касаются версии с запросами, когда граф как бы задан и фиксирован, а нас в первую очередь интересует именно время выполнения запроса.

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

О — позначається найгірший випадок...

Θ — середньої кепськості випадок.

Ω — найкращий випадок,

У Вас какая-то очень чудная интерпретация символов Ландау. Они мало имеют отношения к «среднести» случая. Символы Ландау показывают границы порядка роста функций. Так O(f) — это все функции, чей порядок роста ограничен функцией f. Θ(f) — это множество всех функций, которые растут пропорционально f. Ω(f) — это нижняя граница роста.

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

Ω — найкращий випадок, наприклад, хотіли знайти елемент лінійним пошуком, а цей елемент виявився найпершим.

Вы говорите, что у линейного поиска лучший случай — это Ω(1). Оно то так, но эта оценка тривиальная, в том смысле, что все алгоритмы работают не медленней некоторой константы. Поэтому такая оценка бессмысленная, так как не несет никакой полезной информации. Лучше в таком случае все же сказать, что в линейном поиске в лучшем случае Вы затратите Θ(1) времени. А вот это уже сильная оценка и говорит о многом.

Простите, а что значит константа возрастает линейно в ответ на рост объема условий? что такое «объем условий»?

Вы что-то путаете. Транспортная задача очень даже P-задача, так как она решается линейным программированием. А для ЛП есть множество полиномиальных алгоритмов (ну, может, и не множество, но пара штук уж точно найдется).

Все же стоит очень аккуратно выражать свои мысли, чтоб не вводить народ в заблуждение. Либо это я не очень понял, что именно Вы хотели сказать. Так, например:

У теорії обчислень NP-hard (non-deterministic polynomial hardness) або NP-складні задачі мають поліноміальну залежність часу пошуку рішення до кількості змінних у задачі

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

Як видно з формули, час роботи найкращого алгоритму буде зростати доволі швидко (але повільніше, ніж експотенціально), відповідно до ступеня n.

звучит уж очень странно. Также маленькое уточнение. QUBO — это quadratic unconstrained optimization problem, а не quantum unconstrained optimization problem.