DLOGTIME - DLOGTIME
W teorii złożoności obliczeniowej , DLOGTIME jest klasa złożoności wszystkich obliczeniowych problemów rozwiązywalnych w logarytmicznej ilości czasu obliczeń na deterministycznej maszyny Turinga . Musi być zdefiniowany na maszynie Turinga o swobodnym dostępie , ponieważ w przeciwnym razie taśma wejściowa jest dłuższa niż zakres komórek, do których maszyna może uzyskać dostęp. Jest to bardzo słaby model złożoności czasowej: żadna maszyna Turinga o swobodnym dostępie z mniejszym deterministycznym ograniczeniem czasowym nie może uzyskać dostępu do całości danych wejściowych.
Przykłady
DLOGTIME zawiera problemy związane z weryfikacją długości wejścia, na przykład problem „ Czy wejście ma parzystą długość? ”, Który można rozwiązać w czasie logarytmicznym za pomocą wyszukiwania binarnego .
Aplikacje
DLOGTIME- jednorodność jest ważna w złożoności obwodów .
