Teoria programowania - problemy niepodatne.

Question

Czym są problemy niepodatne? (Definicja, ewentualnie przykłady)

Answer 1

W złożoności obliczeniowej to problemy. do których rozwiązania nie istnieją wydajne algorytmy. 

Przykłady:

• Problem komiwojażera
• Problem plecakowy
• Problem spełnialności
• Job scheduling problem

 

Comments

Czy jest na to inne określenie? Bo szukając frazy "problemy niepodatne" można znaleźć wiele ciekawych rzeczy, tylko nie to.

---

problem NP-trudny

---

Dzięki, nie wiedziałem że to synonimy. Nawiasem mówiąc, nazwa "problemy niepodatne" jest odrobinę dziwna, nie uważasz?

---

Wygląda mi to na spolszczenie 'Intractable problem'. Nie wiem czy to synonimy, być może problemy niepodatne są tylko podzbiorem np-trudnych.

Co do nazwy - jak już google nie wie o co chodzi to sprawa jest podejrzana : )

Answer 2

Wpisując w google "Problemy niepodatne" dostałem link do twojego tematu tuaj. :D Na pewno nie chodzi o to: https://pl.wikipedia.org/wiki/Problem_nierozstrzygalny   ?

Comments

Ja jeszcze natrafiłem na pdf z przykładowymi tematami na pracę magisterską, gdzie takie wyrażenie zostało użyte. http://wmii.uwm.edu.pl/tematy/Kislak_Malinowska_tematyka.pdf

Być może należy szukać angielskiej frazy. ;) Chociaż... Powiadają, że studia zaczynają się tam, gdzie kończy się Google. To chyba jeden z takich tematów. :)