Препятствие, как ETH

Мы знаем, что в мы не можем решить SUM за время при любой функции (обычно ). $ETH$ $K$ $f(K)poly(nK)$ $f(K)$ $2^{O(K)}$

Существует ли какая-либо гипотеза, которая предотвращает сложность (это полностью согласуется с возможностью, так как нам нужно экспоненциальное время для суммы подмножества), или такая возможность допустима? $(\log n)^{O(K)}$ $K=\Omega(n)$

cc.complexity-theory subset-sum Т ....
источник

Ответы:

Сам ETH исключает такую возможность.

В https://people.csail.mit.edu/rrw/cnf-sat-feasible.pdf мы показываем, что любой $n^{O(1)} n^{k/\alpha(k)}$ временной алгоритм для k-SUM, для любого монотонного неубывающего неограниченного неограничен Функция $\alpha$ будет означать, что ETH является ложным.

Райан Уильямс
источник

Вы имеете в виду, что

строго увеличивается или, по крайней мере, уходит в бесконечность?

α

$\alpha$

Сашо Николов

@RyanWilliams По духу похож на ETH, как препятствие. Есть ли что-нибудь, что могло бы предотвратить сложность

с советом по полиномиальному размеру или оракулом PPAD?

O ((\log n)^{O (k)})

$O((\log n)^{O(k)})$

T ....

Добавлен «неограниченный» :)

Райан Уильямс

@Brout Обратите внимание, что (log (n)) ^ k является функцией FPT, так что да, ETH исключает это. С советом poly size это будет означать субэкспоненциальный размер цепей для 3sat. С оракулом PPAD может показаться, что ETH подразумевает PPAD не в P. Для меня это был бы прорыв, я не знаю много подтверждающих доказательств того, что PPAD не в P

Райан Уильямс