List of open problems in computer science

From Wikipedia, the free encyclopedia

 This article may require cleanup to meet Wikipedia's quality standards.
Please improve this article if you can. (February 2007)

This article is a list of open 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.

Contents

[edit] P=NP?

Main article: P and NP
Field 
Theory of computation
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 found in polynomial time with a non-deterministic algorithm or, equivalently, whose solution (if it exists) can be deterministically verified in polynomial time. Naturally, any problem in P is also in NP. The P versus NP question is whether NP is also a subset of P, and hence whether 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.
Conjecture 
Though the question is far from being settled, most experts believe that the classes are different.[1]

[edit] The existence of one-way functions

Main article: One-way function
Field 
Cryptography
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 easy to compute but hard to invert. Although there are several candidates for which no good (ie quick) reverse algorithms are currently known, it hasn't yet been proven that any function exists for which no such reverse algorithms exist.
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≠NP.
Conjecture 
It is assumed but unproven that they do exist. Several encryption systems are based on the assumption that modular exponentiation is a one-way function.

[edit] Formalize (axiomatize) the Church-Turing thesis so that it can be proved or disproved

Source:

  • Nachum Dershowitz and Yuri Gurevich 2007, “A Natural axiomization of Church’s Thesis”. It appears on Gurevich’s website at http://research.microsoft.com/~gurevich. Observe not only the title, but the very first lines of the paper -- a quote from Shoenfield:
”We can write down some axioms about computable functions which most people would agree are evidently true. It might be possible to prove Church’s Thesis from such axioms – Joseph Shoenfield (1993)” (Dershowitz and Gurevich, 2007:1)
Dershowitz and Gurevich deliver their thesis in a nutshell:
”Hence, it remains of real importance to provide a small number of convincing postulates in support of Church’s Thesis. Indeed, Gödel has been reported (by Church in a letter to Kleene cited by Davis in [18] [18: Martin Davis, “Why Gödel didn’t have Church’s thesis”, ‘’Information and Control’’, vol. 54, pp. 3-24, July/August 1982] ) to have believed “that it might be possible . . . to state a set of axioms which would embody the generally accepted properties of [effective calculability], and do something on that basis.”
”[Georg] Kriesel described the discovery of “evident axioms about constructive functions” as “one of the really important open problems [40] [40: Georg Kreisel, “Mathematical logic,” in T. L. Sasty, ed., Lectures in Modern Mathematics III, Wiley and Sons, New York, pp. 95-195, 1965 ] and “one of the more feasible problems at the present time” [41] [41: Georg Kreisel, “Mathematical logic: what has it done for the philosophy of mathematics”, in Ralph Schoenman, ed., Bertrand Russell: Philosopher of the Century, Allen & Unwin, London, pp. 201-272, 1967.]
”We propose just such an axiomatization in the sections that follow. We demonstrate that, under certain very natural hypotheses regarding algorithmic activity . . . Church’s Thesis is in fact provable.” (Dershowitz and Gurevich 2007:4)
  • Samual R. Buss, Alexander S. Kechris, Anand Pillay, and Richard A. Shore, June 2000, “The Prospects for Mathematical Logic in the Twenty-first Century”. This paper came from a panel discussion of the Association for Symbolic Logic held in Urbana-Champain. Shore stated the following three problems under the heading “Computer Science”:
”1. “Prove the Church-Turing thesis by finding intuitively obvious or at least clearly acceptable properties of computation that suffice to guarantee that any function so computed is recursive . . .. Perhaps the question is whether we can be sufficiently precise about what we mean by computation without reference to the method of carrying out the computation so as to give a more general or more convincing argument independent of the physical or logical implementation.
”2. What does physics have to say about computability (and provability or logic)? Do physical restrictions on the one hand, or quantum computing on the other, mean that we should modify our understanding of computability or at least study other notions?
”3. Find, and argue conclusively for, a formal definition of algorithm and the appropriate analog of the Church-Turing thesis. . ..Thus we want a definition that will up to some precise equivalence relation capture the notion that two algorithms are the same as opposed to just computing the same function.” (p. 7-8)

Description:

The thesis states that "effective computation" (calculation) or algorithm can be carried out by a Turing machine (or an equivalent abstract computational device), for example, a deterministic, discrete-state, sequential, space-time limited (i.e. "bounded") process/method. But since such notions of “effective computation” are not well-enough defined and not presented as a small collection of axioms (Gödel's proposal), the thesis cannot be proven; rather, as was done by Kleene (who proposed the thesis) it must either be accepted as a conjecture based on "intuition" i.e. heuristics and empirical methods (observation and accumulation of evidence), or perhaps presented as a "definition" (the approach taken by Church and hotly criticized by Post), or else deemed a "natural law" requiring "continual verification" (Post's proposal hotly criticized by Church).

Importance:

Acceptable axioms and a proof of the thesis will show that any behavior that can be called "computational" can be done by a Turing machine or equivalent. To show that the thesis is wrong will demonstrate or lead to new kinds of problems that are not computable and/or new methods that compute what cannot otherwise be computed by a Turing machine (or equivalent).

Current conjecture:

”We propose just such an axiomatization in the sections that follow. We demonstrate that, under certain very natural hypotheses regarding algorithmic activity . . . Church’s Thesis is in fact provable.” (Dershowitz and Gurevich 2007:4)

[edit] Design a skilled Go-playing program

Main article: Computer Go

Field:

Artificial intelligence

Source:

  • Zobrist, Albert L. A model of visual organisation for the game Go. In Proceedings of the Spring Joint Computer Conference, volume 34, pages 103 - 112, 1969.
  • Zobrist, Albert L. Feature Extractions and Representation for Pattern Recognition and the Game of Go. Phd, Graduate School of the University of Wisconsin-Madison, August 1970.

Description:

Go has long been considered a difficult challenge in the field of AI and has not yielded as easily as Chess. The first Go program was written by Albert Zobrist in 1968 as part of his thesis on pattern recognition. It introduced an influence function to estimate territory and Zobrist hashing to detect ko. Recent developments have brought the best programs close to shodan level on the small 9x9 board; however, it is not yet clear to what extent the success of the techniques used there will transfer to the case of the standard boardsize.
Currently, even mediocre players find it easy to beat the best Go programs. Some strong players have even beaten computer programs at handicaps of 25-30 stones, an enormous handicap that few human players would ever take. There is a case where the winning program in the 1994 World Computer Go Championship, Go Intellect, lost all 3 games against the youth players on a 15 stone handicap.[2] Strong players have not shown much interest in computer Go programs as serious opponents in contrast to examples such as the Chess match between Garry Kasparov and Deep Blue.

Importance:

Go is unlike chess, where the massive computing power of modern computer systems (and in particular dedicated chess machines like Hydra) together with relatively simple search and evaluation heuristics have proven marginally superior to the best human players. It is possible that techniques learned in the course of developing a strong Go program would transfer to more general problems in artificial intelligence to a greater degree than has been the case with chess.[3]

[edit] See also

[edit] References

  1. ^ Gasarch, William (2002). "The P=?NP Poll" (PDF). SIGACT News 33 (2): 34-47. ACM Press. ISSN: 0163-5700. 
  2. ^ See http://www.itee.uq.edu.au/~janetw/Computer%20Go/CS-TR-339.html#6.2
  3. ^ Read this article for more explanations on why computer go is so hard to write