|
Titlul: Problema NP? Scris de: Filip Cristian Buruiana din Februarie 16, 2006, 21:22:09 Postez urmatoarea problema care mi-a venit in minte acum ceva timp si nu am reusit sa imi dau seama daca admite o rezolvare polinomiala. Voi ce credeti? Se poate rezolva polinomial sau e NP?
Citat Se dau N numere naturale. Care este numarul maxim de numere din cele N care pot fi selectate astfel incat produsul lor sa fie patrat perfect? Numerele sunt naturale <= 10 000. [/b][/color]Eu am scos cel mai bine O(N * 2^D), unde D e numarul divizorilor primi din toate numerele. Titlul: Problema NP? Scris de: Tiberiu-Lucian Florea din Februarie 16, 2006, 22:27:33 Nu e NP, ti-am lasat un mesaj ca ma gandesc s-o punem pe infoarena la arhiva, asa ca nu mai dau alte sugestii aici pana nu vedem daca o punem sau nu.
|