W teorii obliczeń jednym z podstawowych nierozstrzygalnych problemów jest problem stopu: decydowanie, czy deterministyczna maszyna Turinga rozwiązująca problem się zatrzyma. Jednym z najbardziej podstawowych problemów z EXPTIME-zupełnych jest jego prostsza wersja, która pyta, czy deterministyczna maszyna Turinga zatrzymuje się po co najwyżej k krokach. Odbywa się to w EXPTIME czasie, ponieważ trywialna symulacja wymaga czasu O(k), a wejście k jest kodowane za pomocą bitów O(log k), co powoduje wykładniczą liczbę symulacji. Jest on ukończony w trybie EXPTIME-zupełnym, ponieważ z grubsza możemy go użyć do ustalenia, czy maszyna rozwiązująca problem stopu akceptuje wykładniczą liczbę kroków; nie zużyje więcej przestrzeni. Ten sam problem z liczbą kroków zapisanych w systemie unarnym jest P-zupełny.
Inne przykłady problemów EXPTIME-zupełnych obejmują problem oceny pozycji w szachach, warcabach lub Go (z japońskimi regułami ko). Te gry mają szansę na EXPTIME-zupełność, ponieważ mogą one trwać ilość ruchów, która jest wykładnicza w stosunku do wielkości planszy. W przykładzie Go japońska zasada ko jest na tyle trudna, aby sugerować EXPTIME-zupełność, ale nie wiadomo, czy bardziej przystępne amerykańskie lub chińskie reguły gry są EXPTIME-zupełne.
Natomiast gry, które mogą trwać przez wiele ruchów wielomianowych pod względem wielkości planszy, są często PSPACE-kompletne.
Przypisy
Kategoria:Klasy złożoności