DLOGTIME

Această intrare sau secțiune despre matematică și teorii ale computerului nu citează sursele necesare sau cei prezenți sunt insuficienți . Putețiîmbunătăți această intrare adăugând citate din surse de încredere în conformitate cu liniile directoare privind utilizarea surselor . Urmați sfaturile de proiectare de referință .

Această intrare pe subiectele matematicii și teoriilor informaticii este doar o schiță . Contribuiți la îmbunătățirea acestuia în conformitate cu convențiile Wikipedia . Urmați sfaturile de proiectare de referință .

În teoria complexității de calcul, DLOGTIME este clasa de complexitate a tuturor problemelor de calcul care pot fi rezolvate într-o cantitate logaritmică de timp de calcul de către o mașină de Turing deterministă. Este cea mai mică clasă netivială care folosește resursele timpului determinist . ^{[ citație necesară ]} Trebuie definit pe o mașină Turing cu acces aleatoriu, deoarece altfel aparatul nu are timp să citească întreaga bandă de intrare. ^[1]

Uniformitatea DLOGTIME este importantă în complexitatea circuitelor .

Problema verificării lungimii șirului de intrare poate fi rezolvată în DLOGTIME, prin căutarea binară a dimensiunilor posibile ale intrării.

Notă

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică