Teoria złożoności strukturalnej
W teorii złożoności obliczeniowej informatyki teoria złożoności strukturalnej lub po prostu złożoność strukturalna to badanie klas złożoności , a nie złożoności obliczeniowej poszczególnych problemów i algorytmów. Polega ona na badaniu zarówno struktur wewnętrznych różnych klas złożoności, jak i relacji między różnymi klasami złożoności.
Historia
Teoria powstała w wyniku (wciąż nieudanych) prób rozwiązania pierwszego i wciąż najważniejszego tego rodzaju zagadnienia, problemu P = NP . Większość badań opiera się na założeniu, że P nie jest równe NP oraz na bardziej daleko idącym przypuszczeniu, że wielomianowa czasowa hierarchia klas złożoności jest nieskończona.
Ważne wyniki
Twierdzenie o kompresji
Twierdzenie o kompresji jest ważnym twierdzeniem o złożoności funkcji obliczalnych .
Twierdzenie to stwierdza, że nie istnieje największa klasa złożoności z obliczalną granicą, która zawierałaby wszystkie obliczalne funkcje.
Twierdzenia o hierarchii przestrzennej
o hierarchii przestrzennej są wynikami separacji, które pokazują, że zarówno deterministyczne, jak i niedeterministyczne maszyny mogą rozwiązywać więcej problemów w (asymptotycznie) większej przestrzeni, z zastrzeżeniem pewnych warunków. Na przykład deterministyczna maszyna Turinga może rozwiązać więcej problemów decyzyjnych w przestrzeni n log n niż w przestrzeni n . Nieco słabszymi analogicznymi twierdzeniami dotyczącymi czasu są twierdzenia o hierarchii czasu .
Twierdzenia o hierarchii czasu
Twierdzenia o hierarchii czasu są ważnymi stwierdzeniami dotyczącymi obliczeń ograniczonych w czasie na maszynach Turinga . Nieformalnie te twierdzenia mówią, że mając więcej czasu, maszyna Turinga może rozwiązać więcej problemów. Na przykład istnieją problemy, które można rozwiązać za pomocą n 2 , ale nie czasu n .
Twierdzenie Valianta-Vaziraniego
Valianta – Vaziraniego jest twierdzeniem z teorii złożoności obliczeniowej . Udowodnili to Leslie Valiant i Vijay Vazirani w artykule zatytułowanym NP jest tak łatwy, jak wykrywanie unikalnych rozwiązań, opublikowanym w 1986 roku. Twierdzenie stwierdza, że jeśli istnieje algorytm czasu wielomianowego dla Unambiguous-SAT , to NP = RP . Dowód opiera się na lemacie o izolacji Mulmuleya-Vaziraniego , który był następnie używany do wielu ważnych zastosowań w informatyka teoretyczna .
Twierdzenie Sipsera – Lautemanna
Twierdzenie Sipsera-Lautemanna lub twierdzenie Sipsera-Gácsa-Lautemanna stwierdza, że czas wielomianu probabilistycznego z ograniczonym błędem (BPP) jest zawarty w wielomianowej hierarchii czasu , a dokładniej Σ 2 ∩ Π 2 .
Twierdzenie Savitcha
Twierdzenie Savitcha , udowodnione przez Waltera Savitcha w 1970 r., podaje związek między deterministyczną i niedeterministyczną złożonością przestrzeni . Stwierdza, że dla dowolnej funkcji }
Twierdzenie Tody
Twierdzenie Tody jest wynikiem, który został udowodniony przez Seinosuke Toda w jego artykule „PP jest tak trudny jak hierarchia wielomianu czasu” (1991) i otrzymał nagrodę Gödla w 1998 roku . Twierdzenie stwierdza, że cała hierarchia wielomianów PH jest zawarta w P PP ; implikuje to ściśle powiązane stwierdzenie, że PH jest zawarte w P #P .
Twierdzenie Immermana-Szelepcsényiego
Immermana – Szelepcsényi zostało udowodnione niezależnie przez Neila Immermana i Róberta Szelepcsényi w 1987 r., Za co w 1995 r. Podzielili się nagrodą Gödla . W swojej ogólnej postaci twierdzenie stwierdza, że NPRZESTRZEŃ ( s ( n )) = co-NPRZESTRZEŃ ( s ( n )) dla dowolnej funkcji s ( n ) ≥ log n . Wynik jest równoważnie podany jako NL = co-NL; chociaż jest to szczególny przypadek, gdy s ( n ) = log n , implikuje twierdzenie ogólne przez standardowy argument uzupełniający [ potrzebne źródło ] . Wynik rozwiązał drugi problem LBA .
Tematy badawcze
Główne kierunki badań w tym obszarze to:
- badanie implikacji wynikających z różnych nierozwiązanych problemów dotyczących klas złożoności
- redukcji ograniczonych zasobami i odpowiadających im kompletnych języków
- badanie konsekwencji różnych ograniczeń i mechanizmów przechowywania i dostępu do danych