Являются ли схемы квазиполиномиального размера для 3-SAT тривиальными?

10

Предположим, что мы рассматриваем 3-SAT с переменными и c предложениями. Я исследую метод, который, по-видимому, использует O ( v 2 + log c ) время / пространство для решения любой задачи SAT, соответствующей данному описанию, с точностью до ошибки, которую можно скорректировать до произвольной величины. Однако здесь есть одна загвоздка.vcO(v2+logc)

Этот метод требует набора предварительно вычисленных значений, после чего он может решить произвольную задачу 3-SAT, соответствующую описанному выше описанию. Предварительно вычисленные значения представляют собой набор величин причем каждое значение занимает пространство O ( 1 ) . Реальная проблема заключается в том, что для вычисления каждого из этих значений может потребоваться время O ( 2 v ) . Есть шанс, что я найду способ ускорить эти вычисления.O(v2+logc)O(1)O(2v)

Я думаю, что сама оценка превосходит верхнюю оценку, представленную в этом вопросе (для маленькой ). Поэтому мне интересно, есть ли тривиальный способ достижения верхних границ, которые я опишу, если мы допустим предварительные вычисления O ( v 2 + log c ) ?cO(v2+logc)

Я хотел бы продолжить это исследование и, надеюсь, опубликовать свои результаты, если все получится, но сначала я хотел бы знать, есть ли тривиальный способ сделать так же или лучше.


ОБНОВИТЬ

Я изучал связанные проблемы в дополнение к исследованию этого алгоритма. Я задал этот вопрос на сайте ИТ-безопасности StackExchange, касающийся взлома паролей и SAT, если вы заинтересованы. По крайней мере, один из ответов отражает это.

Мэтт Грофф
источник
Вы говорите, что это занимает O (N ^ 2 + logc) время / пространство ... Так что это не в PSPACE? Но в QSPACE (квазипространстве)?
Тайфун платят
O(v(2+logc))p(p1)/p
Нужно ли O (N ^ (2 + log (c))) SPACE?
Tayfun Pay
@Tayfun Pay: Да. Я еще не нашел способ уменьшить космические соображения.
Мэтт Грофф
1
Я бы предложил изменить название на более подходящее. Текущий заголовок не выглядит привлекательным, в то время как сам вопрос выглядит так.
Ёсио Окамото

Ответы:

16

Если бы то, что вы изучаете, сработало, это точно не было бы тривиально.

nO(logn)NPnO(logcn)

22n2O(log2n)n2O(log2n)

Что вы подразумеваете под «с точностью до ошибки, которая может быть скорректирована на произвольную величину»? Является ли алгоритм рандомизированным?

Райан Уильямс
источник
x1/(2x)
3
Как алгоритм не может быть рандомизирован, но вы можете запустить его несколько раз, чтобы уменьшить ошибку? Я думаю, что вам, вероятно, придется дать хотя бы еще несколько деталей, чтобы понять ваш вопрос.
Райан Уильямс
2
pp(p1)/pp
pn
BPPP/poly3/4100n2O(log2n)1/2n
Райан Уильямс
3

Я не знаю, будет ли ваш результат - если он действительным - нетривиальным шагом вперед, но есть одна проблема, на которой вы можете проверить его:

f:{0,1}n{0,1}ny{0,1}nx{0,1}nf(x)=y

f

f2n22n/322n/3xy22n/322n/3STST=2nff

f

DW
источник