tag:blogger.com,1999:blog-7985671399824336935.post5583323585060710049..comments2010-02-19T09:01:20.605+01:00Comments on devBlogi: Twoje ulubione oszustwo związane z NP-zupełnościąImmortalhttp://www.blogger.com/profile/00891731290064764143noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-7985671399824336935.post-33061030279621882832010-02-19T09:01:20.605+01:002010-02-19T09:01:20.605+01:00Nie ma rzeczy niemożliwych. Są tylko rzeczy nieopł...Nie ma rzeczy niemożliwych. Są tylko rzeczy nieopłacalne.<br />Dobrego programistę pozna się po tym, że nie będzie ślepo brnął w problem, tylko znajdzie jego obejście. Innymi słowy, oszuka.batmanhttp://www.blogger.com/profile/16188070551224125152noreply@blogger.comtag:blogger.com,1999:blog-7985671399824336935.post-53623310456924989752010-02-18T10:34:36.396+01:002010-02-18T10:34:36.396+01:00Chciałeś pewnie powiedzieć o redukcjach wielomiano...Chciałeś pewnie powiedzieć o redukcjach wielomianowych (a dokładniej o rodzinie redukcji wielomianowych obliczalnych na deterministycznej maszynie Turinga w czasie wielomianowym). Redukcje wielomianowe mają następującą własność: jeśli problem K1 jest redukowalny wielomianowo do problemu K2 oraz K2 należy do klasy P, to K1 również należy do klasy P. Używa się tego zazwyczaj do ustalania, że jakiś rafekhttp://www.blogger.com/profile/00520088707660144870noreply@blogger.comtag:blogger.com,1999:blog-7985671399824336935.post-7901365888696424432010-02-18T10:17:28.791+01:002010-02-18T10:17:28.791+01:00Hm, zapewne metoda branch & bound dla problemu kom...Hm, zapewne metoda branch & bound dla problemu komiwojażera - mam jakąś słabość do drzew.<br /><br />Z tego co pamiętam z pierwszych wykładów na studiach, rozwiązanie jednego, dowolnego problemu NP-zupełnego rozwiązywałoby wszystkie problemy NP-zupełne. Nigdy nie potrafiłem sobie tego wyobrazić, ale to jedno zapadło mi w pamięć.Konradzikhttp://www.blogger.com/profile/08077255793432073218noreply@blogger.com