Przeszkoda taka jak ETH

Wiemy, że pod $ETH$ nie możemy rozwiązać $K$ sumy w czasie $f(K)poly(nK)$ ramach dowolnej funkcji $f(K)$ (zwykle $2^{O(K)}$ ).

Czy istnieje przypuszczenie, które zapobiega złożoności $(\log n)^{O(K)}$ (jest to całkowicie zgodne z możliwością, ponieważ $K=\Omega(n)$ potrzebujemy czasu wykładniczego dla sumy podzbioru) lub czy taka możliwość jest dozwolona?

cc.complexity-theory subset-sum T ....
źródło

Odpowiedzi:

Sam ETH wyklucza tę możliwość.

W https://people.csail.mit.edu/rrw/cnf-sat-feasible.pdf pokazujemy, że dowolny algorytm czasowy $n^{O(1)} n^{k/\alpha(k)}$ dla k-SUM, dla dowolnego monotonicznego, nieokreślającego, nieograniczonego funkcja $\alpha$ , oznaczałoby, że ETH jest fałszem.

Ryan Williams
źródło

Czy masz na myśli, że

rośnie ściśle, a przynajmniej idzie w nieskończoność?

α

$\alpha$

Sasho Nikolov

@RyanWilliams Podobny w duchu do ETH jak niedrożność. Czy jest coś, co mogłoby zapobiec złożoności

dzięki wielomianowej poradzie dotyczącej wielkości lub wyroczni PPAD?

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

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

T ....

Dodano „niezwiązany” :)

Ryan Williams

@Brout Zauważ, że (log (n)) ^ k jest funkcją FPT, więc tak, ETH ją wyklucza. W przypadku wielowymiarowej porady dotyczącej wielkości oznaczałoby to obwody podwykładnicze dla 3sat. Z wyrocznią PPAD wydaje się, że sugeruje, że ETH sugeruje, że PPAD nie jest w P. Dla mnie byłby to przełom, nie znam wielu potwierdzających dowodów, że PPAD nie jest w P

Ryan Williams