Unsolved problems in computer science

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.

=P = 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 probably hard.;Conjecture : Though the question is far from being settled, most experts believe that the classes are different.cite journal
last = Gasarch
first = William
title = The P=?NP Poll
journal = SIGACT News
volume = 33
issue = 2
pages = 34–47
date = 2002
publisher = ACM Press
url = http://www.cs.umd.edu/~gasarch/papers/poll.pdf
format = PDF
id = ISSN: 0163-5700
accessdate = 2007-06-12
doi = 10.1145/564585.564599 ]

The existence of one-way functions

;Field : Cryptography;Source : W. Diffie, M. E. 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 easy to compute but hard to invert. Although there are several candidates for which no good (i.e. 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.

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)

Design a skilled go-playing program

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 human 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. [See http://www.itee.uq.edu.au/~janetw/Computer%20Go/CS-TR-339.html#6.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. [Read this article for more explanations on [http://www.intelligentgo.org/en/computer-go/overview.html why computer go is so hard to write] ]

See also

*Church-Turing thesis
*Turing test
*List of publications in computer science
*AI-complete
*Grand Challenge problem

References

* [http://garden.irmacs.sfu.ca/?q=category/theoretical_computer_science Theoretical Computer Science at Open Problem Garden] The collection of open problems in mathematics and Computer Science build on the principle of user editable ("wiki") site