Logo
Unionpedia
Komunikacja
pobierz z Google Play
Nowy! Pobierz Unionpedia na urządzeniu z systemem Android™!
Darmowy
Szybszy dostęp niż przeglądarce!
 

Problem NP-zupełny

Indeks Problem NP-zupełny

Problem NP-zupełny (NPC) – problem zupełny w klasie NP, ze względu na redukcje wielomianowe, to problem, który należy do klasy NP oraz dowolny problem należący do NP może być do niego zredukowany w czasie wielomianowym.

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 »

Przekierowuje tutaj:

Klasa NPC, NP-zupełność, Problem NP zupełny.

TowarzyskiPrzybywający
Hej! Jesteśmy na Facebooku teraz! »