16 kontakty: Cykl Hamiltona, Klasa Co-NPC, Kolorowanie grafu, Lista problemów NP-zupełnych, Problem kliki, Problem komiwojażera, Problem NP, Problem NP-pośredni, Problem NP-trudny, Problem obliczeniowy, Problem plecakowy, Problem pokrycia wierzchołkowego, Problem silnie NP-zupełny, Problem spełnialności, Problemy milenijne, Stephen Cook.
Cykl Hamiltona
Cykl Hamiltona to taki cykl w grafie, w którym każdy wierzchołek grafu odwiedzany jest dokładnie raz (oprócz pierwszego wierzchołka).
Nowy!!: Problem NP-zupełny i Cykl Hamiltona · Zobacz więcej »
Klasa Co-NPC
Co-NP-zupełność – klasa złożoności zawierająca takie problemy klasy Co-NP, że każdy inny problem klasy Co-NP może zostać do nich zredukowany, analogicznie jak dla problemów NP-zupełnych.
Nowy!!: Problem NP-zupełny i Klasa Co-NPC · Zobacz więcej »
Kolorowanie grafu
Kolorowanie grafu polega w ogólności na przypisaniu określonym elementom składowym grafu (najczęściej wierzchołkom, rzadziej krawędziom lub ścianom) wybranych kolorów według ściśle określonych reguł.
Nowy!!: Problem NP-zupełny i Kolorowanie grafu · Zobacz więcej »
Lista problemów NP-zupełnych
Bez opisu.
Nowy!!: Problem NP-zupełny i Lista problemów NP-zupełnych · Zobacz więcej »
Problem kliki
Problem kliki – jeden z pierwszych zidentyfikowanych problemów NP-zupełnych.
Nowy!!: Problem NP-zupełny i Problem kliki · Zobacz więcej »
Problem komiwojażera
Rozwiązanie przykładowego problemu komiwojażera: najkrótsząścieżkąprzechodzącąprzez wszystkie czerwone punkty jest czarna pętla. Problem komiwojażera – zagadnienie optymalizacyjne, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym.
Nowy!!: Problem NP-zupełny i Problem komiwojażera · Zobacz więcej »
Problem NP
LadneraR.E. Ladner, ''On the structure of polynomial time reducibility'', J.ACM, 22, 1975, s. 151–171. Corollary 1.1. http://portal.acm.org/citation.cfm?id.
Nowy!!: Problem NP-zupełny i Problem NP · Zobacz więcej »
Problem NP-pośredni
Problem NP-pośredni (NPI) – problem decyzyjny należący do klasy NP, który nie należy ani do klasy NPC, ani do klasy P. Jeśli P \neq NP, to klasa NPI zawiera nieskończenie wiele problemów, a jeśli P.
Nowy!!: Problem NP-zupełny i Problem NP-pośredni · Zobacz więcej »
Problem NP-trudny
Problem NP-trudny (NPH) – problem obliczeniowy, którego rozwiązanie jest co najmniej tak trudne, jak rozwiązanie każdego problemu z klasy NP (całej klasy NP).
Nowy!!: Problem NP-zupełny i Problem NP-trudny · Zobacz więcej »
Problem obliczeniowy
Problem obliczeniowy, zadanie obliczeniowe – zadanie, które może być rozwiązane za pomocąkomputera lub innej maszyny liczącej.
Nowy!!: Problem NP-zupełny i Problem obliczeniowy · Zobacz więcej »
Problem plecakowy
Które pudełka powinny być wybrane, aby zmaksymalizować wartość przedmiotów w plecaku i jednocześnie nie zabrać więcej niż 15 kg? Dyskretny problem plecakowy (ang. discrete knapsack problem) – jeden z najczęściej poruszanych problemów optymalizacyjnych.
Nowy!!: Problem NP-zupełny i Problem plecakowy · Zobacz więcej »
Problem pokrycia wierzchołkowego
Problem pokrycia wierzchołkowego – zagadnienie znajdowania w danym grafie G pokrycia wierzchołkowego o najmniejszym rozmiarze, tj.
Nowy!!: Problem NP-zupełny i Problem pokrycia wierzchołkowego · Zobacz więcej »
Problem silnie NP-zupełny
Problem silnie NP-zupełny to taki problem decyzyjny, który nawet przy ograniczeniu maksymalnej wartości występujących w jego opisie liczb pozostaje NP-zupełny.
Nowy!!: Problem NP-zupełny i Problem silnie NP-zupełny · Zobacz więcej »
Problem spełnialności
Problem spełnialności – zagadnienie rachunku zdań, określające czy dla danej formuły logicznej istnieje takie podstawienie (wartościowanie) zmiennych zdaniowych, żeby formuła była prawdziwa.
Nowy!!: Problem NP-zupełny i Problem spełnialności · Zobacz więcej »
Problemy milenijne
Problemy milenijne (ang. Millennium Prize Problems) – zestaw siedmiu zagadnień matematycznych ogłoszonych przez Instytut Matematyczny Claya 24 maja 2000 roku; za rozwiązanie każdego z nich wyznaczono milion dolarów nagrody.
Nowy!!: Problem NP-zupełny i Problemy milenijne · Zobacz więcej »
Stephen Cook
Profesor Stephen Cook Stephen Arthur Cook (ur. 14 grudnia 1939 w Buffalo, Nowy Jork) – amerykański informatyk, za wkład w rozwój teorii złożoności obliczeniowej otrzymał nagrodę Turinga w 1982 roku.
Nowy!!: Problem NP-zupełny i Stephen Cook · Zobacz więcej »