Unresolved problem in computer science

List of open problems in computer science

Computational complexity theory

P versus NP

Description:
P is the class of problems whose solution
can be found in polynomial time. NP 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.


Cryptography

Do one-way functions exist?

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?

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 cluster of N nodes?


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.


What is an optimal UET scheduling algorithm for 3
processors with precedence constraints?

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

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.



------------------------------------------------------------------------
--------

Unsolved problems in software engineering

There is not a canonical list of unsolved problems
in software engineering; however, there are the
following issues:

Software Engineering Project Management

* List of antipatterns, which might be thought of
as statements of poor practice, in contradistinction
to the list of design patterns
* Poorly predictable relationship of project
duration to program functionality
* Systematic detection of software defects
* Statistical tendency of project to run behind
schedule and over-budget
* Adding additional manpower to a lagging software
project (especially in later parts of the project) may
actually cause further schedule slippage due to
overhead experienced during the integration of new
employees. See The Mythical Man-Month.


Programming Complexity

* Current complexity of most programming
languages, in general
* Current complexity of most applications, to the
extent that companies fail when programmers leave, if
those companies have no one else who understands what
the programmers have done.


Standards (software)

* Non-standard implementation of standards or
specifications by multiple organizations result in a
requirement for implementation specific code and
special case exceptions as a necessity for
cross-platform interoperability. Notable modern
examples include web browser compatibility and
web-services interoperability.
* Arbitrariness of most software concepts, which
is related to historical hardware and software
implementation, lack of common standards worldwide,
and economic pressures.