time complexity classes are not believed to be closed under complementation; for instance, it is conjectured that NP != co-NP.

LOGSPACE

L or LOGSPACE is the set of problems that can be solved by a deterministic Turing machine using only memory space with regards to input size. Even a single counter that can index the entire -bit input requires space, so LOGSPACE algorithms can maintain only a constant number of counters or other variables of similar bit complexity.

LOGSPACE and other sub-linear

1.Previous
3.Next