|
This is a list of unsolved problems in computer science. A solution to the problems in this list will have a major impact on the field of study to which they belong. This is a list of lists of unsolved problems in various subjects: Unsolved problems in biology Unsolved problems in chemistry Unsolved problems in cognitive science Unsolved problems in computer science Unsolved problems in economics Unsolved problems in Egyptology Unsolved problems in governance Unsolved problems in mathematics Unsolved problems in medicine...
Computer science is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...
P versus NP In computer science, computational complexity theory is the branch of the theory of computation that studies the resources, or cost, of the computation required to solve a given problem. ...
Diagram of complexity classes provided that P ≠NP. If P = NP, then all three classes are equal. ...
- Source:
- S. A. Cook and Leonid Levin
- Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (1971), pp. 151--158.
- 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.
Stephen A. Cook is a noted computer scientist. ...
Leonid Levin (born 1948, USSR) is a computer scientist. ...
In computational complexity theory, P is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. ...
In computational complexity theory, polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ...
In computational complexity theory, NP (Non-deterministic Polynomial time) is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. ...
In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...
In computational complexity theory, NP-hard (Non-deterministic Polynomial-time hard) refers to the class of decision problems that contains all problems H such that for all decision problems L in NP there is a polynomial-time many-one reduction to H. Informally this class can be described as containing...
Do one-way functions exist? The German Lorenz cipher machine Cryptography or cryptology is a field of mathematics and computer science concerned with information security and related issues, particularly encryption and authentication. ...
Unsolved problems in computer science: Do one-way functions exist? A one-way function is a function that is easy to calculate but hard to invert — it is difficult to calculate the input to the function given its output. ...
- Source:
- W.Diffie, M.E.Hellman
- IEEE Trans. Inform. Theory, IT-22, 6, 1976, pp.644-654
- 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 do not exist then public key cryptography is impossible. Their existence would imply that many complexity classes are not learnable, and that P is not NP.
- Current conjecture: It is assumed but unproven that they do exist.
Whitfield Diffie Bailey Whitfield Whit Diffie (born June 5, 1944) is a US cryptographer and one of the pioneers of public-key cryptography. ...
Martin Hellman - Wikipedia, the free encyclopedia /**/ @import /skins-1. ...
In abstract algebra and its applications, the discrete logarithms are defined in group theory in analogy to ordinary logarithms. ...
In cryptography, RSA is an algorithm for public-key encryption. ...
Public key cryptography is a form of cryptography which generally allows users to communicate securely without having prior access to a shared secret key, by using a pair of cryptographic keys, designated as public key and private key, which are related mathematically. ...
High performance computing To what degree can one speed up a computation? The field of high performance computing (HPC) comprises computing applications on (parallel) supercomputers and computer clusters. ...
- 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 cluster of N nodes? In computational complexity theory, a speedup theorem is a theorem that considers some algorithm solving a problem and demonstrates the existence of a faster algorithm solving the same problem (or more generally, an algorithm using less of any resource, not just time). ...
Computation can be defined as finding a solution to a problem from given inputs by means of an algorithm. ...
Amdahls law, named after computer architect Gene Amdahl, is used to find the maximum expected improvement to an overall system when only part of the system is improved. ...
Linux Cluster at Purdue University. ...
- 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? In engineering and telecommunication, the mean time between failures (MTBF) is the average time a system will operate without a failure. ...
Recovery is the first e-book and seventh installment of The New Jedi Order series set in the Star Wars galaxy. ...
The term checkpoint may refer to: A place at which vehicles or pedestrians are stopped in order to enforce laws or security measures. ...
- 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 superscalar 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 |
Feeds |
Contact