Uma obstrução como a ETH

Sabemos sob $ETH$ que não pode resolver $K$ -sum em $f(K)poly(nK)$ tempo sob qualquer função $f(K)$ (geralmente $2^{O(K)}$ ).

Existe alguma conjectura que impeça uma complexidade $(\log n)^{O(K)}$ (isso é totalmente consistente com a possibilidade, pois $K=\Omega(n)$ precisamos de tempo exponencial para a soma do subconjunto) ou essa possibilidade é permitida?

cc.complexity-theory subset-sum T ....
fonte

Respostas:

O próprio ETH exclui essa possibilidade.

Em https://people.csail.mit.edu/rrw/cnf-sat-feasible.pdf , mostramos que qualquer algoritmo de tempo $n^{O(1)} n^{k/\alpha(k)}$ para k-SUM, para qualquer número monótono não decrescente sem limites função $\alpha$ , implicaria que ETH é falso.

Ryan Williams
fonte

α

$\alpha$

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

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

Adicionado "ilimitado" :)

Ryan Williams

@ Brout Note que (log (n)) ^ k é uma função do FPT, então sim, o ETH exclui isso. Com conselhos de tamanho de polietileno, significaria circuitos de tamanho subexponencial para 3sat. Com um oráculo PPAD parece implicar que ETH implica PPAD não em P. Para mim, isso seria um grande avanço, eu não sei de muita evidência corroborando que PPAD não está na P

Ryan Williams