Member-only story
The Biggest Unsolved Problems in Computer Science
Programmers solved many challenging engineering problems except these mysteries.
The theoretical fundamentals of computer science are being used to solve various sorts of challenging real-world problems. Every technical solution has underlying computer science fundamentals. For example, the Git distributed version control system was built with the help of theories such as graph theory, data structures, and cryptography. Surprisingly, there are very challenging problems inside each theory too.
Most theoretical challenges have been solved already by great computer scientists. For example, quicksort and mergesort like algorithms were invented as more efficient sorting algorithms for quite larger lists. However, like any other field of study, computer science also has its mysteries. Many computer scientists tried to find solutions for these mysteries. But, these problems still exist as unresolved because scientists couldn’t prove their answers correctly, and also their answers were not accepted by the majority of other computer scientists.
P vs NP
Computers can solve various sorts of computational problems. In theoretical computer science, computational problems are divided into several categories such as NL, P, NP, PSPACE, etc. P-class refers to problems that can be solved in a deterministic Turing machine using polynomial time. Here, a deterministic Turing machine is an abstract computer that can execute instructions in a linear order. In simple words, P-class problems have reasonably fast algorithms on physical computers. For example, sorting a list of integers is a P-class problem since efficient sorting algorithms have O(n²) time complexity, not an exponential time complexity.
On the other hand, NP-class refers to problems that need a non-deterministic Turing machine if we need to solve them using polynomial time. Here, a non-deterministic Turing machine is an abstract computer that can execute instructions and decisions simultaneously. In simple words, NP-class problems have very slow algorithms compared to P-class problems. For example, the traveling salesman problem has very slow algorithms which are having exponential time complexities. Importantly, there is a polynomial-time…
