• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

P vs NP - o co w tym chodzi?

VPS Starter Arubacloud
0 głosów
739 wizyt
pytanie zadane 26 listopada 2019 w Matematyka, fizyka, logika przez Karpik Użytkownik (680 p.)

Czy mógłby mi ktoś to przetłumaczyć na prostrzy język? :) (z wikipedii)

 

P vs NP: czy istnieją pytania, na które odpowiedź – jeśli się ją zna – można szybko zweryfikować, lecz których rozwiązanie – bez znajomości odpowiedzi – zabierze więcej czasu (mierzonego poprzez złożoność obliczeniową)?

2 odpowiedzi

+1 głos
odpowiedź 29 listopada 2019 przez mmarszik Mądrala (7,390 p.)
edycja 30 listopada 2019 przez mmarszik

Na jakim poziomie jesteś obecnie? Zadałeś pytanie z działu złożoności obliczeniowej. To jest znacznie trudniejszy dział infomratyki niż algorytmika.

https://pl.wikipedia.org/wiki/Z%C5%82o%C5%BCono%C5%9B%C4%87_obliczeniowa

[
Stosujemy też szersze pojęcia takie jak klasa P, czy NP mając odpowiednio na uwadze decyzyjne problemy wielomianowe i decyzyjne problemy podlegające wielomianowej weryfikacji, jeśli odpowiedź jest twierdząca.
]

Tu link do chyba najbardziej klasycznego przypadku:

https://pl.wikipedia.org/wiki/Problem_spe%C5%82nialno%C5%9Bci

Pisząc kolokwialnie, jak masz zestaw wartościowania zmiennych to możesz szybko (w czasie P - polynomial,wielomianowym) sprawdzić czy to wartościowanie spełnia czy nie spełnia daną formułę. Natomiast gdy nie masz i musisz szukać, to potrzeba (o ile P != NP) czasu wykładniczego (NP - non-polynominal).

Jeśli można sprawdzać łatwo (w czasie P), to ludzie zaczęli żywić nadzieję, że także istnieje sposób aby szybko (też w czasie P) szukać. Wiele problemów jest problemami NP i wszystkie te problemy są sobie równoważne. Równoważność oznacza, że jak uda się jeden z  tych problemów rozwiązać (znaczy wyszukiwać) w czasie P, to uda się też dla wszystkich innych problemów z tej klasy (z klasy NP). Wydaje się nieprawdopodobne udowodnienie że klasa P jest równoważna NP, ponieważ dla wielu problemów nagle udałoby się zastosować szybki algorytm, którego do tej pory nikt nie odkrykł.

Kiedyś czytałem, że jakiś facio z HawletPackarda napisał pracę udowadniającą iż P != NP - na ile jego pracę potraktowano poważnie - nie wiem. Czy były inne poważne prace od tamtej pory - też nie wiem. Poczytaj pod linkami, może tam są jakieś nowe informacje i dalsze linki do ciekawych informacji.

Pozdrawiam

 

 

 

0 głosów
odpowiedź 29 listopada 2019 przez profesorek96 Szeryf (91,420 p.)
Po prostu są takie problemy zwane NP-zupełnymi których nie potrafimy rozwiązać w skończonym czasie. Innymi słowy, istnieją algorytmy na ich rozwiązanie, jednak aby taki algorytm wykonać i otrzymać wynik trzeba czasu kilku dziesięciu lat ponieważ jest tyle możliwości i kombinacji do sprawdzenia.

Przykładami takich problemów są np:

problem cyklu Hamiltona

kolorowanie grafu

problem spełnialności

Podobne pytania

0 głosów
1 odpowiedź 168 wizyt
pytanie zadane 29 lipca 2022 w Matematyka, fizyka, logika przez YNK3 Nowicjusz (120 p.)
0 głosów
1 odpowiedź 232 wizyt
pytanie zadane 24 maja 2022 w Matematyka, fizyka, logika przez Oryctes Nowicjusz (210 p.)
+1 głos
0 odpowiedzi 493 wizyt

92,455 zapytań

141,263 odpowiedzi

319,100 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...