A report on List of unsolved problems in computer science

List of notable unsolved problems in computer science.

- List of unsolved problems in computer science

3 related topics with Alpha

Overall
Euler diagram for P, NP, NP-complete, and NP-hard set of problems (excluding the empty language and its complement, which belong to P but are not NP-complete)

P versus NP problem

1 links

Euler diagram for P, NP, NP-complete, and NP-hard set of problems (excluding the empty language and its complement, which belong to P but are not NP-complete)
The graph shows the running time vs. problem size for a knapsack problem of a state-of-the-art, specialized algorithm. The quadratic fit suggests that the algorithmic complexity of the problem is O((log(n))2).
Diagram of complexity classes provided that P ≠ NP. The existence of problems within NP but outside both P and NP-complete, under that assumption, was established by Ladner's theorem.

The P versus NP problem is a major unsolved problem in theoretical computer science.

Charles Babbage, sometimes referred to as the "father of computing".

Computer science

1 links

Study of computation, automation, and information.

Study of computation, automation, and information.

Charles Babbage, sometimes referred to as the "father of computing".
Ada Lovelace published the first algorithm intended for processing on a computer.

What is the lower bound on the complexity of fast Fourier transform algorithms? is one of unsolved problems in theoretical computer science.

NL (complexity)

0 links

Complexity class containing decision problems that can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space.

Complexity class containing decision problems that can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space.

Like much of complexity theory, many important questions about NL are still open (see Unsolved problems in computer science).