A
Ну, не более строгое, а которое исчёрпывает больше чем количество алгоритмов до размера N
Size: a a a
2021 January 16
A
A
Не знаю как ещё выразиться
A
Aycon
Примем за аксиому, что сложность задачи оценивается как f(x, y), где x - это асимптотика расхода памяти, y - асимптотика действий процессора
Мне проще думать, что f = x×y
A
Дальше
A
Чтобы найти решения ряда задач необходимо найти целое число от 1 до N
A
Где N - некоторая функция от входных данных
A
В случае факторизации N не превышает корня от входного числа
A
Таким образом в зависимости от конкретного входного числа алгоритм должен дать ответ от 1 до N , т. е. покрыть эту область
A
Т. Е. Он должен иметь потенциальную возможность найти любое число из этого диапазона которое требует число исходных данных
A
Таким образом, нужно доказать что алгоритм заданного размера (1 кб в форме исходника брейнфака * 1 кб оперативки используемой алгоритмом например) не может покрыть весь этот диапазон при N > К.
A
Где K - граница недостижимости алгоритмом решения
A
Прошу прощения, не 1 кб исходника брейнфака, а 1000 тактов процессора
A
Тогда нужно перебирать не все алгоритмы, а только те, которые выполняются за 1000 тактов
A
Ну и взять не 1000 тактов, а 2log(N) (здесь N - уже входные данные, прошу прощения за путаницу)
DP
даже в брейнфаке 8 команд
считаем что команды перемещения назад в коде мы отключаем. и весь код линейный
1к команд, хотя бы 4 штуки, это 4^1000 вариантов
солнце сгорит за 2^256
считаем что команды перемещения назад в коде мы отключаем. и весь код линейный
1к команд, хотя бы 4 штуки, это 4^1000 вариантов
солнце сгорит за 2^256
A
Aycon
Тогда нужно перебирать не все алгоритмы, а только те, которые выполняются за 1000 тактов
И занимают не больше 1 кб памяти
DP
т.е. даже для брейнфака ты ограничен что-то около 100 командами. которых очевидно не хватит
A
даже в брейнфаке 8 команд
считаем что команды перемещения назад в коде мы отключаем. и весь код линейный
1к команд, хотя бы 4 штуки, это 4^1000 вариантов
солнце сгорит за 2^256
считаем что команды перемещения назад в коде мы отключаем. и весь код линейный
1к команд, хотя бы 4 штуки, это 4^1000 вариантов
солнце сгорит за 2^256
Да, но это лучше чем перебор всех алгоритмов ибо их всё равно больше)
A
Это пока лучшее что я придумал.. (