DLOGTIME

DLOGTIME is the complexity class of all computational problems solvable in a logarithmic amount of computation time on a deterministic Turing machine. It is the smallest nontrivial class using the resource of deterministic time.^{[citation needed]} It must be defined on a random-access Turing machine, since otherwise the machine does not have time to read the entire input tape.

DLOGTIME-uniformity is important in circuit complexity.

The problem of testing the length of the input string can be solved in DLOGTIME, by binary searching for possible input sizes.

P ≟ NP

This theoretical computer science-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Complexity classes Theoretical computer science stubs Wikimedia Foundation. 2010. Игры ⚽ Нужно решить контрольную? Henri Dentz Ronald Stordahl Look at other dictionaries: L (complexity) — In computational complexity theory, L (also known as LSPACE) is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space. Logarithmic space is sufficient to …   Wikipedia Computational complexity theory — is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other. In this context, a… …   Wikipedia NP (complexity) — Diagram of complexity classes provided that P ≠ NP. The existence of problems outside both P and NP complete in this case was established by Ladner.[1] In computational complexity theory, NP is one of the most fundamental complexity classes. The… …   Wikipedia NC (complexity) — Unsolved problems in computer science Is NC = P ? In complexity theory, the class NC (for Nick s Class ) is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. In… …   Wikipedia Oracle machine — In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision… …   Wikipedia Sharp-P — The correct title of this article is #P. The substitution or omission of the # sign is because of technical restrictions. In computational complexity theory, the complexity class #P (pronounced number P or, sometimes sharp P or hash P ) is the… …   Wikipedia Sharp-P-complete — The correct title of this article is #P complete. The substitution or omission of the # sign is because of technical restrictions. #P complete, pronounced sharp P complete or number P complete is a complexity class in computational complexity… …   Wikipedia PSPACE — Unsolved problems in computer science Is P = PSPACE ? PSPACE …   Wikipedia NP-complete — Euler diagram for P, NP, NP complete, and NP hard set of problems In computational complexity theory, the complexity class NP complete (abbreviated NP C or NPC) is a class of decision problems. A decision problem L is NP complete if it is in the… …   Wikipedia NP-hard — For a gentler introduction, see P versus NP problem. Euler diagram for P, NP, NP complete, and NP hard set of problems NP hard (non deterministic polynomial time hard), in computational complexity theory, is a class of problems that are,… …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”