Złożoność obliczeniowa

Teoria złożoności obliczeniowej to dział teorii obliczeń. Głównym jej celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów. Za twórców tej teorii uważani są Juris Hartmanis i Richard Stearns. Jako przykłady problemów t.z.o. można podać: problem spełnialności, problem najkrótszej ścieżki, problem faktoryzacji oraz wiele innych o których wiadomo że są obliczalne. Kwestią obliczalności zajmuje się teoria obliczalności, będąca drugą ważną gałęzią teorii obliczeń.

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. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów.

Twierdzenie Cooka-Levina – jedno z najważniejszych twierdzeń teorii złożoności obliczeniowej. Podaje ono pierwszy znany problem NP-zupełny. Od momentu jego udowodnienia można było stosować transformacje wielomianowe do dowodzenia NP-zupełności innych problemów decyzyjnych.

L-redukcja – transformacja problemów optymalizacyjnych, która zachowuje własności aproksymacyjne. L-redukcje odgrywają podobną rolę w badaniach nad aproksymowalnością problemów optymalizacyjnych, jak transformacje wielomianowe w badaniach nad złożonością obliczeniową problemów decyzyjnych.

Problem Collatza (znany też jako problem 3x+1, problem Ulama) – nierozstrzygnięty dotychczas (i nie wiadomo, czy w ogóle rozstrzygalny) problem o wyjątkowo prostym – jak wiele innych problemów teorii liczb – sformułowaniu. Nazwa pochodzi od nazwiska niemieckiego matematyka Lothara Collatza (1937). Zagadnienie to było również rozpatrywane przez polskiego matematyka Stanisława Ulama.

Transformacja pseudowielomianowa – pojęcie wykorzystywane w teorii złożoności obliczeniowej do dowodzenia silnej NP-zupełności problemów decyzyjnych podobnie do zastosowania transformacji wielomianowej przy dowodzeniu NP-zupełności.

Problem P (ang. deterministic polynomial - deterministycznie wielomianowy) to problem decyzyjny, dla którego rozwiązanie można znaleźć w czasie wielomianowym.

W teorii złożoności obliczeniowej transformacją Turinga problemu A do problemu B nazywamy (na cześć Alana Turinga) redukcję pozwalającą "łatwo" rozwiązać problem A przy założeniu, że znamy rozwiązanie problemu B.

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. Istnienie certyfikatów pierwszości dowiodło, że problem znajdowania liczb pierwszych leży w klasie NP: problemów których rozwiązania można sprawdzić w czasie wielomianowym.

Problem najkrótszej ścieżki jest zagadnieniem szczególnie istotnym w informatyce. Polega on na znalezieniu w grafie ważonym najkrótszego połączenia pomiędzy danymi wierzchołkami. Szczególnymi przypadkami tego problemu są problem najkrótszej ścieżki od jednego wierzchołka do wszystkich innych oraz problem najkrótszej ścieżki pomiędzy wszystkimi parami wierzchołków.

Problem monopoli magnetycznych (ang. the magnetic monopole problem) – jeden z kilku problemów teoretycznych nie dających się wyjaśnić w ramach teorii wielkiej unifikacji. Rozwiązanie problemu monopoli magnetycznych przynosi wprowadzenie inflacji kosmologicznej.

W teorii złożoności obliczeniowej, problem izomorfizmu podgrafu jest przykładem NP-zupełnego problemu decyzyjnego. Formalna definicja tego problemu wygląda następująco:

Simple assembly line balancing - podstawowy problem decyzyjny w planowaniu konfiguracji w swojej najbardziej podstawowej wersji. Spośród rodziny problemów Assembly Line Balancing jest on najlepiej znany i najlepiej zbadany. Mimo iż może on być zbyt uproszczony by oddać złożoność rzeczywistych problemów balansowania to uchwyca on główne aspekty. Wiele odmian bardziej ogólnych problemów są bezpośrednimi rozszerzeniami SALB lub przynajmniej wymagają rozwiązania problemu SALB w jakiejś postaci.

Problem pokrycia wierzchołkowego – zagadnienie znajdowania w danym grafie pokrycia wierzchołkowego o najmniejszym rozmiarze, tj. zawierającego możliwie najmniejszą liczbę wierzchołków. Tak zdefiniowany problem pokrycia wierzchołkowego jest problemem optymalizacyjnym. W teorii złożoności obliczeniowej częściej rozważa się problemy decyzyjne. Decyzyjna wersja problemu pokrycia wierzchołkowego to problem stwierdzania czy w danym grafie istnieje pokrycie wierzchołkowe o danym rozmiarze k.

Problem zbioru wierzchołków rozrywających cykle (ang. Feedback vertex set problem) jest to zagadnienie z teorii grafów, polegające na znalezieniu podgrafu X, w grafie G, takiego, że co najmniej k jego wierzchołków i krawędzi nie tworzy cyklu. Był pierwszym problemem wobec którego udowodniono, że jest to problem NP-zupełny.

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.

Wielomianowy schemat aproksymacji (ang. Polynomial-time approximation scheme, w skrócie PTAS) to algorytm aproksymacyjny, który pozwala na uzyskanie dowolnie dobrego rozwiązania przybliżonego danego problemu optymalizacyjnego, i którego złożoność czasowa jest wielomianowa dla każdej żądanej dokładności.

W statystyce, teorii decyzji i teorii gier, problem sekretarki (znany także jako problem wyboru najlepszego obiektu lub problem łowcy posagu) to zagadnienie optymalnej selekcji najlepszej propozycji ze skończonego zbioru takich propozycji, prezentowanych sekwencyjnie w losowej kolejności. Przyjmuje się przy tym, że propozycje są istotnie różne. Zagadnienie sprowadza się od optymalnego zatrzymania pewnego ciągu losowego czyli wyboru optymalnego momentu zatrzymania dla tego ciągu.

W pełni wielomianowy schemat aproksymacji (ang. Fully polynomial-time approximation scheme, w skrócie FPTAS) to algorytm aproksymacyjny, który pozwala na uzyskanie dowolnie dobrego rozwiązania przybliżonego danego problemu optymalizacyjnego, i którego złożoność czasowa jest wielomianowa względem rozmiaru instancji rozwiązywanego problemu i rośnie wielomianowo w miarę wzrostu żądanej dokładności.

       na podstawie Wikipedii, otwartej encyklopedii : licencje: GFDL, oraz CC-BY-SA 3.0 + autorzy, historia
edycja