Unsolved problems in computer science


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


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Computer science — or computing science (abbreviated CS) is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems. Computer scientists invent algorithmic… …   Wikipedia

  • Unsolved problems in philosophy — This article deals mainly with unsolved problems in analytic philosophy. For other schools of philosophy, this concept is not well defined. Philosophical problems are unlike scientific or mathematical problems in that problems in philosophy are… …   Wikipedia

  • List of unsolved problems — A list of unsolved problems may refer to several conjectures or open problems in various fields. The problems are listed below:* Unsolved problems in chemistry * Unsolved problems in cognitive science * Unsolved problems in computer science *… …   Wikipedia

  • Theoretical computer science — is the collection of topics of computer science that focuses on the more abstract, logical and mathematical aspects of computing, such as the theory of computation, analysis of algorithms, and semantics of programming languages. Although not… …   Wikipedia

  • List of unsolved problems in physics — This is a list of some of the major unsolved problems in physics. Some of these problems are theoretical, meaning that existing theories seem incapable of explaining a certain observed phenomenon or experimental result. The others are… …   Wikipedia

  • List of unsolved problems in mathematics — This article lists some unsolved problems in mathematics. See individual articles for details and sources. Contents 1 Millennium Prize Problems 2 Other still unsolved problems 2.1 Additive number theory …   Wikipedia

  • List of unsolved problems in economics — This is a list of some of the major unsolved problems, puzzles, or questions in economics. Some of these are theoretical in origin and some of them concern the inability of standard economic theory to explain an empirical observation. Contents 1… …   Wikipedia

  • Computer-aided production engineering — CAPE International Conference logo Computer aided production engineering (CAPE) is a relatively new and significant branch of engineering. Global manufacturing has changed the environment in which goods are produced. Meanwhile, the rapid… …   Wikipedia

  • science, philosophy of — Branch of philosophy that attempts to elucidate the nature of scientific inquiry observational procedures, patterns of argument, methods of representation and calculation, metaphysical presuppositions and evaluate the grounds of their validity… …   Universalium

  • List of problems — *List of undecidable problems *List of unsolved problems *List of open problems in computer science *List of NP complete problems *List of PSPACE complete problems *List of problems solved by MacGyver …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.