Czy istnieją problemy „pełne (O)”?

Wiele klas złożoności ma „kompletne” problemy. Czy istnieją kompletne problemy dla klasy złożoności problemów, które można rozwiązać$O(1)$ czas?

Komplikacja polega na tym, że klasa ta zależy od modelu obliczeniowego; problem można rozwiązać$O(1)$czas w jednym rozsądnym modelu obliczeniowym, ale nie w innym, biorąc pod uwagę, że „rozsądny” zwykle oznacza równoważność czasu wielomianowego z maszyną Turinga. Jednak nadal można go opracować dla konkretnych rozsądnych modeli.

Myślę, że najbardziej sensowne jest patrzenie na wielokrotne redukcje w jednym czasie. Jestem jednak otwarty na inne rozsądne redukcje, jeśli jest na nie literatura.

Czy coś takiego istnieje lub zostało zbadane dla jakiegokolwiek modelu obliczeniowego?

Ponieważ odczyt danych wejściowych jest niezbędny dla prawie wszystkich problemów, potrzebujemy przynajmniej $\Omega(n)$ czas na prawie wszystkie problemy, gdzie $n$to rozmiar danych wejściowych. Dlatego możesz pomyśleć o klasie problemów z czasem liniowym, która jest już zdefiniowana.

Jednak nadal nie znamy żadnych $O(n)$-kompletne lub $O(n^2)$-kompletny problem. W dziedzinie drobnoziarnistej złożoności pojawiają się nowe wyniki w tym obszarze, ale klasy są oparte na problemach (na przykład APSP jest równoważne z Promieniem, Trójkątem Negatywnym, ...).

Myślę, że dla $O(1)$ problemy, wszystkie języki są kompletne w ramach „stałych redukcji czasu”, z wyjątkiem $L = \Sigma^*$ i $L = \emptyset$

Przypuszczam, że $L, L' \in O(1)$ i $L \neq 0, L \neq \Sigma^*$

Pozwolić $x_Y \in L, x_N \notin L$

Jest to redukcja czasu stałego od $L'$ do $L$:

• dany $x$ rozwiązać $L'$ w $O(1)$ czas
• gdyby $x \in L'$ następnie wyjście $x_Y$, w przeciwnym razie wyjście $x_N$

Więc $L$ jest gotowy na $O(1)$ (... leniwa redukcja, leniwy wynik :-)).