Бинарный поиск наверх

[Профессор Снэйп]

Вот есть у нас вычислимое отношение $R(n,x)$. И доказано (безо всякого намёка на поиск, чисто от противного), что $\forall x \exists n R(n,x)$. Как его лучше искать? Допустим, есть дополнительный вычислимый предикат $S(n,x)$, истинный тогда и только тогда, когда существует $m \leqslant n$, такой что $R(m,x)$. Всё равно мало помогает...

[dvorkin_sacha]

Профессор Снэйп

Тоже решили Зиммерманом "побаловаться"?.

[Circiter]

2Профессор Снэйп
Наверное, можно так. Фиксируем $x$. В цикле выбираем $n$ случайно и проверяем $S(n,\ x)$. Как только условие выполнилось, присваиваем $x\gets n$ и повторяем все сначала, прямо с цикла. Если $R$ транзитивно, то мы (вроде-бы) будем приближаться к искомому $n$. Последовательность значений, которые присваивались к $x$ должна сходиться (или нет :) ).

Бред, не иначе... :)

[venco]

Профессор Снэйп в сообщении #395483 писал(а):

Вот есть у нас вычислимое отношение $R(n,x)$. И доказано (безо всякого намёка на поиск, чисто от противного), что $\forall x \exists n R(n,x)$. Как его лучше искать? Допустим, есть дополнительный вычислимый предикат $S(n,x)$, истинный тогда и только тогда, когда существует $m \leqslant n$, такой что $R(m,x)$. Всё равно мало помогает...

Сначала умножаем $n$ на два, пока не получим $S(n,x)$, а потом бинарным поиском вниз.

[Профессор Снэйп]

venco в сообщении #395694 писал(а):

Сначала умножаем $n$ на два, пока не получим $S(n,x)$, а потом бинарным поиском вниз.

А почему именно на два?

[venco]

Оптимум где-то около $2^{\sqrt{2\log_2 n}}$, но разница небольшая. Наверно лучше умножать на большее число, например 10.