Zupełność w informatyce Dla algorytmów zupełność oznacza że dany algorytm znajduje rozwiązanie jeśli takowe istnieją, a w przeciwnym razie wskazuje brak istnienia rozwiązania. W obliczeniowej teorii złożoności, problem P jest zupełny dla klasy złożoności C, pod pewnym rodzajem redukcji, jeśli P leży w C, i każdy problem z C da się sprowadzić do P używając danej redukcji. Na przykład każdy problem z klasy NP-zupełne jest zupełny dla klasy NP, jeśli jest redukowalny wielu-do-jednego w czasie wielomianowym.
Przypisy
Linki zewnętrzne Logika matematyczna , Andrzej Mostowski niesprzeczność
Kategoria:Logika