ИСТИНА |
Войти в систему Регистрация |
|
ИСТИНА ИНХС РАН |
||
We have proofed that the special case {\bf B-1} of the problemwhen $d_{max}-d_{min} \leq p_{min}$ is NP-hard in the ordinarysense. We have proposed a polynomial scheme of reduction fromNP-complete {\bf Partition Problem} to the special case {\bf B-1}of the problem $1\mid\,\mid\sum T_j$. For this case apseudo-polynomial algorithm with run time $O(n\sum p_j)$ and exactalgorithm for $p_j \notin Z$ have been constructed. Therefore wecan decide the {\bf Partition Problem} when parameters are notinteger.