Wpis z mikrobloga

@MSKM: Problemy algorytmiczne mają złożoność wielomianową jak O(1) czyli czas stały czy O(n^k) gdzie k jest stałe i oczywiście widać że rośnie to o wiele wolniej niż O(k^n) co jest już NP. Alfaredukcja to takie coś co pozwala sprowadzić jeden problem do drugiego. Ogolnie zbadaj temat Problemów milenijnych ( ͡º ͜ʖ͡º)
  • Odpowiedz
@wytrzzeszcz: Gratuluję. Pierwsza rozmowa z gatunku P=NP w której widzę jak ktoś rzeczywiście tłumaczy czym to P=NP jest. Dodam że P bierze się od słowa polynomial, wielomianowy, a np od non-polynomial czyli nie wielomianowy.
Faktycznie te dwa problemy generują podobny typ dyskusji.
  • Odpowiedz
@kolnay1: Może inaczej. Nie chodzi o bicie piany i gramar nazi.
Jak za pomoca podania jednego przykladu (jak rozumiem kontrprzykladu) chcesz udowodnic zbierznosc ciagu.

zlozonosc obliczeniowa to albo wzor, albo po prostu ciag (dla n dostajemy zlozonosc), chcesz udowodnic, ze dany ciag ma sie zmiescic pod ciagiem (cos jak tw. o 3 ciagach ale tylko bierzesz dwa. Problem jest tylko taki, ze mozesz to zrobic na bardzo wiele sposobow.

Stad pytanie
  • Odpowiedz
@li7j00: Jak chcesz użyć takiej analogii, to raczej mowa o udowodnieniu za pomocą przykładu braku zbieżności ciągu.
Może po prostu sobie o tym poczytaj.
  • Odpowiedz
@kolnay1: jestem programistą ;-) wiem o czym mówię i nie moge sobie wyobrazic jak chcesz to udowodnic. To by bylo trudniejsze niz udowodnienie a0 nastepnik 2^a0
  • Odpowiedz