Problem NP

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
Diagram Eulera dla problemów P, NP, NP-zupełnych i NP-trudnych. Istnienie problemów wewnątrz NP, ale nie należących ani do P, ani do NP-zupełnych, przy założeniu, że P≠NP, zostało udowodnione przez Ladnera.

Problem NP (ang. nondeterministic polynomial, niedeterministycznie wielomianowy) – problem decyzyjny, dla którego rozwiązanie można zweryfikować w czasie wielomianowym. Równoważna definicja mówi, że problem jest w klasie NP, jeśli może być rozwiązany w wielomianowym czasie na niedeterministycznej maszynie Turinga.

Wielomian – wyrażenie algebraiczne złożone ze zmiennych i stałych połączonych działaniami dodawania, odejmowania, mnożenia i podnoszenia do potęgi o stałym wykładniku naturalnym.Formuła logiczna to określenie dozwolonego wyrażenia w wielu systemach logicznych, m.in. w rachunku kwantyfikatorów oraz w rachunku zdań.

Różnica pomiędzy problemami P i NP polega na tym, że w przypadku P znalezienie rozwiązania ma mieć złożoność wielomianową, podczas gdy dla NP sprawdzenie podanego z zewnątrz rozwiązania ma mieć taką złożoność.

Przykładowy problem: Czy jakikolwiek niepusty podzbiór zadanego zbioru (np. ) sumuje się do zera?

Trudno znaleźć rozwiązanie tego zagadnienia w czasie wielomianowym. Nasuwający się algorytm sprawdzenia wszystkich możliwych podzbiorów ma złożoność wykładniczą ze względu na liczebność zbioru. Nie wiadomo zatem, czy problem ten jest klasy P. Na pewno natomiast uzyskawszy z zewnątrz kandydata na rozwiązanie (np. ) możemy w liniowym (a zatem wielomianowym) czasie sprawdzić, czy sumuje się do zera. Jest to zatem problem NP.

Test pierwszości to algorytm określający, czy dana liczba jest pierwsza, czy złożona. Nie jest to równoważne znalezieniu jej rozkładu na czynniki pierwsze. W obecnej chwili (2011 rok) nie są znane efektywne algorytmy rozkładu na czynniki pierwsze, natomiast testy pierwszości można przeprowadzać bardzo szybko.Algorytmika to nauka o algorytmach. Jest działem informatyki, cybernetyki, a także, dla większości nauk matematyczno-przyrodniczych, ekonomii i techniki. Algorytmika zajmuje się badaniem algorytmów. Częścią algorytmiki jest algorytmizacja, czyli proces budowy konkretnego algorytmu.

W szczególności wszystkie problemy klasy PNP, ponieważ można je sprawdzić w czasie wielomianowym. Innymi słowy, klasa P zawiera się nieostro w NP Nie wiadomo natomiast czy istnieje problem NP, który nie jest w klasie P (czyli, czy P różni się od NP lub inaczej albo ). Jest to jeden z problemów milenijnych.

Izomorfizm grafów – Grafy G jest izomorficzny z grafem F, jeśli istnieje takie, różnowartościowe i na, przyporządkowanie (bijekcja) wierzchołków grafu H wierzchołkom grafu G , ż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ź.Liczby całkowite – liczby naturalne dodatnie N + = { 1 , 2 , 3 , … } {displaystyle mathbb {N} _{+}={1,2,3,dots }} oraz liczby przeciwne do nich { − 1 , − 2 , − 3 , … } {displaystyle {-1,-2,-3,dots }} , a także liczba zero. Uogólnieniem liczb całkowitych są liczby wymierne i tym samym liczby rzeczywiste, szczególnym przypadkiem liczb całkowitych są: liczby naturalne.

W 2000 roku Buss przewidywał, że zostanie potwierdzone w ciągu 20 lat. W 2001 roku 40 spośród 97 ekspertów było przekonanych, że problem ten zostanie rozwiązany do 2039 roku, a 57, że do roku 2070. Według New Scientist z 2010 roku istnieje 50% szans na rozwiązanie problemu przed 2024 rokiem, gdyż 9 spośród 18 badanych hipotez udowodniono, zanim upłynęły 54 lata od ich postawienia. W 2012 roku analiza 144 hipotez matematycznych (w tym tych nieudowodnionych) uwzględniająca wzrost liczby matematyków oraz coraz lepszy przepływ wiedzy pomiędzy nimi wykazała, że szansa na rozwiązanie problemu przed 2024 rokiem to 41%. Zgodnie z ankietą z 2011 roku wśród 152 ekspertów 53% z nich uważa, iż problem zostanie rozwiązany przed 2100 rokiem, a 41%, że po nim.

Definicja intuicyjna: Maszyna Turinga stanowi najprostszy, wyidealizowany matematyczny model komputera, zbudowany z taśmy, na której zapisuje się dane i poruszającej się wzdłuż niej „głowicy”, wykonującej proste operacje na zapisanych na taśmie wartościach.Dopełnienie zbioru – intuicyjnie, zbiór wszystkich elementów (pewnego ustalonego nadzbioru), które do danego zbioru nie należą. W niektórych pozycjach można spotkać się również z alternatywną nazwą uzupełnienie zbioru.

Definicja formalna[ | edytuj kod]

Klasa złożoności NP może być zdefiniowana w kategorii klas NTIME(f(n)) w następujący sposób:

Algorytm wielomianowy – algorytm, którego czas działania ograniczony jest przez wielomian od rozmiaru danych wejściowych. Problemy, dla których istnieje algorytm wielomianowy nazywane są łatwymi do rozwiązania, w przeciwieństwie do problemów uważanych za trudne.Klasa co-NP jest klasą dopełniającą dla problemów decyzyjnych NP. Np. dopełnieniem problemu typu "czy wszystkie elementy zbioru X spełniają warunek Y" jest "czy istnieje element zbioru X nie spełniający warunku Y".

Alternatywnie, klasę NP można zdefiniować w kontekście deterministycznych maszyn Turinga. Powiemy, że język L należy do NP wtedy i tylko wtedy, gdy istnieją wielomiany p i q, oraz deterministyczna maszyna Turinga M, taka że:

Język formalny – jest to podzbiór zbioru wszystkich słów nad skończonym alfabetem. Język formalny jest kluczowym pojęciem w informatyce, logice matematycznej i językoznawstwie. Język formalny nie jest uściśleniem pojęcia języka naturalnego i nie powinien być z nim mylony.Informatyka – dyscyplina nauki zaliczana do nauk ścisłych oraz techniki zajmująca się przetwarzaniem informacji, w tym również technologiami przetwarzania informacji oraz technologiami wytwarzania systemów przetwarzających informację. Początkowo stanowiła część matematyki, później rozwinęła się do odrębnej dyscypliny – pozostaje jednak nadal w ścisłej relacji z matematyką, która dostarcza informatyce podstaw teoretycznych.
  • dla dowolnych x i y, maszyna M, mając podaną na wejściu parę (x, y), kończy działanie w nie więcej niż p(x) krokach,
  • dla dowolnego x należącego do L, istnieje słowo y długości nie większej niż q(x), takie że maszyna M akceptuje słowo wejściowe (x, y),
  • dla dowolnego x nienależącego do L oraz dowolnego y o długości nie większej niż q(x), maszyna M odrzuca słowo wejściowe (x, y).
  • Wprowadzenie[ | edytuj kod]

    Wiele naturalnych problemów algorytmicznych znajduje się w klasie złożoności NP. W szczególności, decyzyjne wersje wielu interesujących problemów przeszukiwania oraz problemów optymalizacyjnych należą do NP.

    Problem komiwojażera (TSP - ang. travelling salesman problem) jest to zagadnienie optymalizacyjne, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym.Problem P (ang. deterministic polynomial - deterministycznie wielomianowy) to problem decyzyjny, dla którego rozwiązanie można znaleźć w czasie wielomianowym.

    Definicja bazująca na weryfikatorach[ | edytuj kod]

    W celu wyjaśnienia definicji klasy NP bazującej na weryfikatorach przeanalizujemy problem sumy podzbioru: Mając dany skończony zbiór składający się wyłącznie z liczb całkowitych (na przykład {−7, −3, −2, 5, 8}), rozstrzygnąć, czy istnieje taki jego niepusty podzbiór, którego elementy sumują się do zera (w naszym przykładzie odpowiedź jest pozytywna, gdyż podzbiorowi {-3, -2, 5} odpowiada suma (−3) + (−2) + 5 = 0).

    Moglibyśmy zaproponować algorytm rozwiązujący powyższy problem, a bazujący na sprawdzaniu wszystkich możliwych podzbiorów. Niestety, liczba podzbiorów, a tym samym czas obliczeń, rośnie wykładniczo w stosunku do rozmiaru podanego zbioru. Zauważmy jednak, że mając podany pewien podzbiór, możemy łatwo sprawdzić, czy suma jego elementów wynosi zero. Jeśli tak jest, mówimy że dany zbiór jest świadkiem faktu, że odpowiedź na zadany problem jest pozytywna. Algorytm sprawdzający, czy elementy zadanego zbioru sumują się do zera, nazywamy natomiast weryfikatorem.

    W teorii obliczeń problem optymalizacyjny jest to problem obliczeniowy, którego rozwiązanie polega na znalezieniu największej bądź najmniejszej wartości pewnego parametru problemu, która spełnia pewną własność. Parametr, którego największej bądź najmniejszej wartości szukamy nazywa się funkcją kosztu (funkcja celu). Problem optymalizacyjny nazywa się problemem maksymalizacyjnym jeśli polega on na znalezieniu największej wartości funkcji kosztu i minimalizacyjnym jeśli szukana jest najmniejsza wartość funkcji kosztu.Europejskie Obserwatorium Południowe (ang. European Southern Observatory - ESO) – międzynarodowa organizacja zrzeszająca europejskie kraje, powołana w 1962 roku w celu budowy i utrzymywania obserwatoriów astronomicznych na półkuli południowej.

    Bardziej ogólnie, mówimy że problem obliczeniowy należy do NP jeśli istnieje dla niego weryfikator V. Mając dowolny egzemplarz I problemu P, dla którego odpowiedź jest pozytywna, musi istnieć świadek S, taki że V akceptuje słowo wejściowe (I, S) w czasie wielomianowym. Co więcej, jeśli odpowiedź na I jest negatywna, weryfikator V odrzuci słowo (I, S) dla wszystkich możliwych S. Zauważ, że weryfikator może odrzucić wejście nawet gdy odpowiedź jest pozytywna, jeśli tylko S nie jest poprawnym świadkiem. Dla przykładu, w przypadku problemu sumy podzbioru, jeśli istnieje podzbiór, którego elementy sumują się do zera, ale jako świadek S wybrany zostanie inny podzbiór, dla którego nie jest to prawdą, weryfikator odrzuci słowo wejściowe. Jeśli jednak nie istnieje podzbiór o zerowej sumie, weryfikator będzie odrzucał wejście niezależnie od wyboru świadka. Ponadto w przypadku tego problemu, weryfikator działa w czasie wielomianowym (potrzeba jedynie sprawdzić, czy S faktycznie jest podzbiorem I oraz czy suma jego elementów jest zerowa), a zatem problem sumy podzbioru należy do klasy NP.

    W teorii złożoności obliczeniowej problem NP-trudny (NPH) to taki problem obliczeniowy, którego rozwiązanie jest co najmniej tak trudne jak rozwiązanie każdego problemu z klasy NP.Wyszukiwanie binarne jest algorytmem opierającym się na metodzie dziel i zwyciężaj, który w czasie logarytmicznym stwierdza, czy szukany element znajduje się w uporządkowanej tablicy i jeśli się znajduje, podaje jego indeks. Np. jeśli tablica zawiera milion elementów, wyszukiwanie binarne musi sprawdzić maksymalnie 20 elementów ( log 2 ⁡ 1 000 000 ≈ 20 {displaystyle log _{2}{1,000,000}approx 20} ) w celu znalezienia żądanej wartości. Dla porównania wyszukiwanie liniowe wymaga w najgorszym przypadku przejrzenia wszystkich elementów tablicy.

    Dopełnienie przytoczonego problemu obliczeniowego może zostać sformułowane w następujący sposób: Mając dany skończony zbiór liczb całkowitych rozstrzygnąć, czy dowolny jego niepusty podzbiór ma niezerową sumę.

    Definicja bazująca na weryfikatorach nie wymaga istnienia żadnego łatwego do zweryfikowania świadka dla odpowiedzi negatywnej. Klasę problemów obliczeniowych z takimi świadkami nazywamy co-NP. Problemem otwartym jest czy dla dowolnego problemu obliczeniowego w klasie NP istnieją świadkowie odpowiedzi negatywnych, a zatem czy zawierają się one w co-NP.

    Problem spełnialności to pytanie rachunku zdań - czy dla danej formuły logicznej istnieje takie podstawienie (wartościowanie) zmiennych zdaniowych, żeby formuła była prawdziwa. Jest równoważne negacji odpowiedzi na pytanie czy "negacja tej formuły jest tautologią".Problem decyzyjny – pytanie sformułowane w systemie formalnym, na które możliwe są odpowiedzi tak i nie. Przykładowo problem "Dla danych liczb x i y, czy x jest dzielnikiem y?" jest problemem decyzyjnym. Odpowiedzią może być tak lub nie w zależności od wartości x i y.

    Definicja bazująca na maszynach Turinga[ | edytuj kod]

    Następująca definicja jest równoważna definicji bazującej na weryfikatorach: Klasa złożoności NP jest zbiorem problemów decyzyjnych rozpoznawanych przez niedeterministyczną maszynę Turinga działającą w czasie wielomianowym (oznacza to, że jeśli słowo należy do języka to istnieje przebieg akceptujący – klasa co-NP jest zdefiniowana analogicznie w kategorii ścieżek odrzucających).

    Równoważność powyższej definicji z tą bazującą na weryfikatorach opiera się na fakcie, że niedeterministyczna maszyna Turinga można rozwiązać problem z klasy NP w czasie wielomianowym poprzez niedeterministyczny wybór świadka oraz symulację na nim weryfikatora. Z drugiej strony, jeśli istnieje niedeterministyczna maszyna M rozwiązująca pewien problem z NP, możemy łatwo skonstruować weryfikator dla tego problemu. Będzie on w deterministyczny sposób symulował pewien przebieg maszyny M, korzystając ze świadka za każdym razem, gdy należy dokonać niedeterministycznego wyboru.

    Algorytmy aproksymacyjne – algorytmy służące do znajdowania przybliżonych rozwiązań problemów optymalizacyjnych. Stosuje się je zwykle do rozwiązywania problemów, dla których nie są znane szybkie algorytmy znajdujące rozwiązanie dokładne, na przykład dla problemów NP-zupełnych.Problem obliczeniowy, zadanie obliczeniowe – zadanie, które może być rozwiązane za pomocą komputera lub innej maszyny liczącej. Na opis p.o. składają się: zbiór danych wejściowych (ang. input) oraz warunki, jakie ma spełniać wynik, czyli dane wyjściowe (ang. output). Bardziej formalnie przez p.o. możemy rozmumieć funkcję, która przekształca zbiór danych wejściowych na zbiór danych wyjściowych. Pojęcie problemu obliczeniowego leży u podstaw informatyki rozumianej jako nauki zajmującej się przetwarzaniem informacji, gdyż praktycznie każde zadanie informatyczne można rozważać jako p.o.

    Przykłady[ | edytuj kod]

    Poniżej znajduje się niekompletna lista problemów znajdujących się w klasie NP.

  • Wszystkie problemy z klasy P (Dla dowolnego świadka weryfikator może go zignorować i rozwiązać problem w czasie wielomianowym. Alternatywnie, deterministyczna maszyna Turinga jest jednocześnie przypadkiem szczególnym maszyny niedeterministycznej.)
  • Wersja decyzyjna problemu faktoryzacji: mając dane liczby naturalne n oraz k rozstrzygnąć, czy istnieje dzielnik d liczby n, taki że 1 < d < k.
  • Problem izomorfizmu grafów.
  • Wszystkie problemy NP-zupełne, między innymi:
  • Problem komiwojażera, polegający na znalezieniu cyklu o minimalnej sumie wag, zawierającego wszystkie wierzchołki grafu
  • Problem spełnialności: mając daną formułę logiczną, rozstrzygnąć, czy istnieje takie wartościowanie zmiennych zdaniowych, żeby formuła była prawdziwa.
  • Zmienna zdaniowa – bezargumentowy symbol w rachunku zdań. Zmiennym zdaniowym, w procesie zwanym wartościowaniem, przyporządkowywane są wartości prawda lub fałsz.W teorii obliczeń klasa złożoności to zbiór problemów obliczeniowych o podobnej złożoności obliczeniowej. Najbardziej pospolitą definicją klasy złożoności jest:


    Podstrony: 1 [2] [3] [4] [5]




    Warto wiedzieć że... beta

    Problem decyzyjny – pojęcie z zakresu teorii decyzji, oznaczające sytuację problemową, w której podmiot (decydent) staje przed koniecznością wyboru jednego z przynajmniej dwóch możliwych wariantów działania.
    Problem NP-zupełny (NPC) czyli 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. Czasami zamiast redukcji w czasie wielomianowym używa się redukcji w pamięci logarytmicznej. Pytanie, czy są to definicje równoważne pozostaje pytaniem otwartym. Taka definicja problemów NP-zupełnych implikuje fakt, że jeśli tylko potrafimy rozwiązać jakikolwiek problem NP-zupełny w czasie wielomianowym, to potrafimy rozwiązać w czasie wielomianowym wszystkie problemy NP. Problemy NP-zupełne można więc traktować jako najtrudniejsze problemy klasy NP (z punktu widzenia wielomianowej rozwiązywalności).
    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. Do dziś rozwiązano tylko jeden problem: hipoteza Poincarégo została potwierdzona w 2006 roku przez rosyjskiego matematyka Grigorija Perelmana.
    Część wspólna zbiorów A i B (przekrój, iloczyn mnogościowy, przecięcie zbiorów) – zbiór, który zawiera te i tylko te elementy, które należą jednocześnie do zbioru A i do zbioru B. Część wspólną definiuje się także dla dowolnych niepustych rodzin zbiorów.
    Niedeterministyczna maszyna Turinga – teoretyczny model rozważany w teorii obliczeń w celu badania problemów decyzyjnych. Niedeterministyczna maszyna Turinga jest zdefiniowana tak samo jak deterministyczna maszyna Turinga z jedyną różnicą dotyczącą postaci funkcji przejścia, która w przypadku maszyn niedeterministycznych zwraca zbiór możliwych działań maszyny.

    Reklama