List of open problems in computer science |
This is a list of unsolved problems in computer science.
A solution to the problems in this list will have a major impact of the field of study to which they belong.
=Computational complexity theory=
Complexity classes P and NP
:Source:
*Stephen Cook
Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (1971), pp. 151--158.
:Description: P (complexity) is the class of problems whose solution can be found in polynomial time. NP (complexity) is the class of problems whose solution can be verified in polynomial time. Naturally, any problem in P is also in NP. The P versus NP question is whether NP is in P, hence the classes are equal. One can see the question as a specific case of the problem in proving lower bounds for computational problems.
:Importance: If the classes are equal then we can solve many problems that are currently considered intractable. If they are not, then NP-complete problems are problems that are provably hard.
:Current conjecture: Though the question is far from being settled, it seems that the classes are different.
Do one-way functions exist
:Source:
*Whitfield Diffie, Martin Hellman
IEEE Trans. Inform. Theory , IT-22, 6, 1976, pp.644-654
*[
http://citeseer.ist.psu.edu/340126.html Online copy (HTML)]
:Description: One-way functions are functions that are easy to compute but hard to invert. Some people conjecture that computing discrete logarithm and inverting RSA are one-way functions.
:Importance: If one-way functions exist then public key cryptography is possible. Their existence would also imply that many complexity classes are not learnable, and that P is not NP.
:Current conjecture: Most researchers conjecture that one-way functions exist but haven t yet proven it...
=High performance computing=
To what degree can one speed up a computation
:Source:
:Description: Although the speedup theorem from computability theory shows that any computation can be sped up by any desired constant degree, there is no feasible method of gaining such a speedup. It is needed to know what are the techniques and bounds on speedup in various architectures - a single processor, grid, distributed network, etc.
:Importance: The speed of computation is the limit to the problems that we can solve.
:Current conjecture: Amdahl s law is a partial answer to the question.
How can one build a Computer cluster of N nodes
:Source:
:Description: As the number of computers in a cluster rises, the probability of failure in some of the computers rises too. At some point, the mean time between failures is shorter than the recovery and checkpoint times. In such a case, different algorithms and architectures might be needed in order to gain more computing power. It is possible that the higher probability of failure will bound the rate of increased power.
:Importance: Clusters are a powerful method of gaining computation power. Therefore, bounds on the cluster size are currently bounds on computational power.
:Current conjecture:
What is an optimal UET scheduling algorithm for 3 processors with precedence constraints
:Source:
*Marc Chardon, Aziz Moukrim
The Coffman--Graham Algorithm Optimally Solves UET Task Systems with Overinterval Orders , SIAM J. Discrete Math, Volume 19 (2005), Number 1 pp. 109-121.
:Description: A unit-execution-time (UET) scheduling problem contains tasks all with identical length. When there are precedence constraints then there is a directed graph of dependencies between the UET tasks. To start a task all its direct predecessors must first be completed. Two optimal algorithms are known for UET task systems on 2 processors [CoffmanGraham72] [GareyJohnson76].
:Importance: This problem is fundamentally equivalent to scheduling instructions in a superscaler computer, and to scheduling parallel tasks systems optimally in a multiprocessor with 3 processors. The problem is NP-complete for arbitrary m, but complexity for fixed m > 2 is unknown.
:Current conjecture:
= See also =
List of publications in computer science