Предположим, что мы рассматриваем 3-SAT с переменными и c предложениями. Я исследую метод, который, по-видимому, использует O ( v 2 + log c ) время / пространство для решения любой задачи SAT, соответствующей данному описанию, с точностью до ошибки, которую можно скорректировать до произвольной величины. Однако здесь есть одна загвоздка.
Этот метод требует набора предварительно вычисленных значений, после чего он может решить произвольную задачу 3-SAT, соответствующую описанному выше описанию. Предварительно вычисленные значения представляют собой набор величин причем каждое значение занимает пространство O ( 1 ) . Реальная проблема заключается в том, что для вычисления каждого из этих значений может потребоваться время O ( 2 v ) . Есть шанс, что я найду способ ускорить эти вычисления.
Я думаю, что сама оценка превосходит верхнюю оценку, представленную в этом вопросе (для маленькой ). Поэтому мне интересно, есть ли тривиальный способ достижения верхних границ, которые я опишу, если мы допустим предварительные вычисления O ( v 2 + log c ) ?
Я хотел бы продолжить это исследование и, надеюсь, опубликовать свои результаты, если все получится, но сначала я хотел бы знать, есть ли тривиальный способ сделать так же или лучше.
ОБНОВИТЬ
Я изучал связанные проблемы в дополнение к исследованию этого алгоритма. Я задал этот вопрос на сайте ИТ-безопасности StackExchange, касающийся взлома паролей и SAT, если вы заинтересованы. По крайней мере, один из ответов отражает это.
источник
Ответы:
Если бы то, что вы изучаете, сработало, это точно не было бы тривиально.
Что вы подразумеваете под «с точностью до ошибки, которая может быть скорректирована на произвольную величину»? Является ли алгоритм рандомизированным?
источник
Я не знаю, будет ли ваш результат - если он действительным - нетривиальным шагом вперед, но есть одна проблема, на которой вы можете проверить его:
источник