Spis treści
29 kontakty: Algorytm genetyczny, Algorytm pseudowielomianowy, Algorytm wielomianowy, Certyfikat pierwszości, Dopełnienie (teoria złożoności), Izomorfizm grafów, Klasa Co-NP, Klasa złożoności, Kryptologia, Kubit pomocniczy, Metaheurystyka, Niedeterministyczna maszyna Turinga, NP, NPC, Problem decyzyjny (teoria obliczeń), Problem kliki, Problem NP-pośredni, Problem NP-trudny, Problem NP-zupełny, Problem P, Problem silnie NP-zupełny, Problem zbioru niezależnego, Problemy milenijne, PSPACE, Shafrira Goldwasser, Teoria rekursji, Test pierwszości, Vaughan Ronald Pratt, Złożoność obliczeniowa.
Algorytm genetyczny
Algorytm genetyczny – rodzaj heurystyki przeszukującej przestrzeń alternatywnych rozwiązań problemu w celu wyszukania najlepszych rozwiązań.
Zobaczyć Problem NP i Algorytm genetyczny
Algorytm pseudowielomianowy
Algorytm pseudowielomianowy – algorytm, którego złożoność obliczeniowa jest pseudowielomianowa.
Zobaczyć Problem NP i Algorytm pseudowielomianowy
Algorytm wielomianowy
Algorytm wielomianowy – algorytm, którego czas działania ograniczony jest przez wielomian od rozmiaru danych wejściowych.
Zobaczyć Problem NP i Algorytm wielomianowy
Certyfikat pierwszości
W teorii liczb, certyfikat pierwszości albo dowód pierwszości to zwięzły formalny dowód, że dana liczba jest pierwsza, który można szybko zweryfikować – w przeciwieństwie do czasochłonnego przeprowadzenia testu pierwszości.
Zobaczyć Problem NP i Certyfikat pierwszości
Dopełnienie (teoria złożoności)
Dopełnienie – problem decyzyjny powstający po zamianie miejscami odpowiedzi tak i nie.
Zobaczyć Problem NP i Dopełnienie (teoria złożoności)
Izomorfizm grafów
Izomorfizm grafów – graf G jest izomorficzny z grafem H, jeśli istnieje bijekcja ("przeetykietowanie") wierzchołków grafu H wierzchołkom grafu G, takie że jeśli jakieś dwa wierzchołki sąpołączone krawędziąw jednym z grafów, to odpowiadające im wierzchołki w drugim grafie również łączy krawędź.
Zobaczyć Problem NP i Izomorfizm grafów
Klasa Co-NP
Klasa Co-NP – klasa złożoności dopełniająca dla problemów decyzyjnych NP.
Zobaczyć Problem NP i Klasa Co-NP
Klasa złożoności
Klasa złożoności – zbiór problemów obliczeniowych o podobnej złożoności obliczeniowej.
Zobaczyć Problem NP i Klasa złożoności
Kryptologia
II wojny światowej do szyfrowania wiadomości sztabowych wysokiego szczebla Kryptologia (z gr. κρυπτός kryptos, „ukryty”, i λόγος logos, „rozum”, „słowo”) – dziedzina wiedzy o przekazywaniu informacji w sposób zabezpieczony przed niepowołanym dostępem.
Zobaczyć Problem NP i Kryptologia
Kubit pomocniczy
Kubit pomocniczy (ang. Ancilla bit) – dodatkowy kubit stosowany w algorytmach kwantowych i zwykle inicjowany stanem standardowym (zwykle |0\rangle lub |1\rangle), którego celem jest zwiększenie wymiaru przestrzeni Hilberta koniecznej do obliczeń.
Zobaczyć Problem NP i Kubit pomocniczy
Metaheurystyka
Metaheurystyka – ogólny algorytm (heurystyka) do rozwiązywania problemów obliczeniowych.
Zobaczyć Problem NP i Metaheurystyka
Niedeterministyczna maszyna Turinga
Drzewo obliczeń niedeterministycznej maszyny Turinga. Niedeterminizm można interpretować jako stworzenie tylu kopii maszyny Turinga ile jest możliwych stanów do których może przejść maszyna, a następnie zastosowanie poszczególnych możliwych ruchów dla każdej kopii.
Zobaczyć Problem NP i Niedeterministyczna maszyna Turinga
NP
* problem NP (ang. nondeterministic polynomial) – problem decyzyjny, dla którego rozwiązanie można zweryfikować w czasie wielomianowym.
Zobaczyć Problem NP i NP
NPC
NPC może oznaczać.
Zobaczyć Problem NP i NPC
Problem decyzyjny (teoria obliczeń)
Problem decyzyjny – pytanie sformułowane w systemie formalnym, na które możliwe sątylko odpowiedzi tak i nie.
Zobaczyć Problem NP i Problem decyzyjny (teoria obliczeń)
Problem kliki
Problem kliki – jeden z pierwszych zidentyfikowanych problemów NP-zupełnych.
Zobaczyć Problem NP i Problem kliki
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.
Zobaczyć Problem NP i Problem NP-pośredni
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).
Zobaczyć Problem NP i Problem NP-trudny
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.
Zobaczyć Problem NP i Problem NP-zupełny
Problem P
Problem P (deterministycznie wielomianowy) – problem decyzyjny, dla którego rozwiązanie można znaleźć w czasie wielomianowym.
Zobaczyć Problem NP i Problem P
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.
Zobaczyć Problem NP i Problem silnie NP-zupełny
Problem zbioru niezależnego
Problem zbioru niezależnego – przykład problemu NP-zupełnego z teorii grafów.
Zobaczyć Problem NP i Problem zbioru niezależnego
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.
Zobaczyć Problem NP i Problemy milenijne
PSPACE
W teorii złożoności obliczeniowej PSPACE jest zbiorem wszystkich problemów decyzyjnych, które można rozwiązać za pomocąmaszyny Turinga wykorzystującej wielomianowąprzestrzeń.
Zobaczyć Problem NP i PSPACE
Shafrira Goldwasser
Shafrira Goldwasser Shafrira Goldwasser (ur. 1958 w Nowym Jorku) – amerykańska profesor informatyki i wykładowca do spraw bezpieczeństwa kryptograficznego w MIT oraz profesor nauk matematycznych w Instytucie Naukowym Weizmana w Izraelu.
Zobaczyć Problem NP i Shafrira Goldwasser
Teoria rekursji
Teoria rekursji – dział logiki matematycznej, którego początki sięgająlat trzydziestych XX wieku.
Zobaczyć Problem NP i Teoria rekursji
Test pierwszości
Test pierwszości – algorytm określający, czy dana liczba jest pierwsza, czy złożona.
Zobaczyć Problem NP i Test pierwszości
Vaughan Ronald Pratt
Vaughan Pratt Vaughan Ronald Pratt (ur. 1944) – emerytowany profesor Uniwersytetu Stanforda, jeden z pionierów informatyki.
Zobaczyć Problem NP i Vaughan Ronald Pratt
Złożoność obliczeniowa
Teoria złożoności obliczeniowej – dział teorii obliczeń, którego głównym celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych.
Zobaczyć Problem NP i Złożoność obliczeniowa
Znany jako Klasa NP.