Pytania otagowane jako subset-sum

1
Wykrywanie relacji liczb całkowitych dla podzbioru sumy lub NPP?
Czy istnieje sposób na zakodowanie wystąpienia Sumy Podzbioru lub Problemu Podziału Liczby, aby (małe) rozwiązanie relacji liczb całkowitych dało odpowiedź? Jeśli nie zdecydowanie, to w pewnym sensie probabilistycznym? Wiem, że LLL (i być może PSLQ) zostały zastosowane z umiarkowanym sukcesem w rozwiązywaniu problemów sumy częściowej w regionie „niskiej gęstości”, w …
1
Kolejny wariant PARTYCJI
Mam redukcję następującego problemu z partycją do pewnego problemu z planowaniem: Dane wejściowe: lista liczb całkowitych dodatnich w kolejności nie malejącej.a1⩽⋯⩽ana1⩽⋯⩽ana_1\leqslant\cdots\leqslant a_n Pytanie: Czy istnieje wektor taki, że(x1,…,xn)∈{−1,1}n(x1,…,xn)∈{−1,1}n(x_1,\ldots,x_n)\in\{-1,1\}^n ∑i=1naixi=0and∑i=1naixi=0and\sum_{i=1}^na_ix_i=0\qquad\text{and} ∑i=1kaixi⩾0for all k∈{1,…,n}∑i=1kaixi⩾0for all k∈{1,…,n}\sum_{i=1}^ka_ix_i\geqslant 0\quad\text{for all }k\in\{1,\ldots,n\} Bez drugiego warunku jest to po prostu PARTYCJA, a więc NP-twardy. Ale drugi …
1
Przeszkoda taka jak ETH
Wiemy, że pod miT.H.ETHETH nie możemy rozwiązać K.KK sumy w czasie fa( K) p o l y( n K.)f(K)poly(nK)f(K)poly(nK) ramach dowolnej funkcji fa( K)f(K)f(K) (zwykle 2)O ( K)2O(K)2^{O(K)} ). Czy istnieje przypuszczenie, które zapobiega złożoności ( logn )O ( K)(log⁡n)O(K)(\log n)^{O(K)} (jest to całkowicie zgodne z możliwością, ponieważ K.= Ω …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.