Talk:List of unsolved problems in computer science

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Unnecessary definition[edit]

"A problem in computer science is considered unsolved when an expert in the field (i.e, a computer scientist) considers it unsolved or when several experts in the field disagree about a solution to a problem" seems unnecessary, since most of the problems on the list require exact, non-subjective solutions. — Preceding unsigned comment added by 177.82.37.234 (talk) 05:20, 15 September 2016 (UTC)[reply]

Deletion of speedup section[edit]

The original speedup section is posted verbatim in this section below my objections. As stated it appears to confuse the meaning of "speedup" used in the "speedup theorem" (which allows one to achieve a "speedup" by changing the alphabet size -- and potentially causing a combinatorial explosion in the (still finite) number of states in the FSM component of the turing machine) to the notion of "speedup" used by a programmer performing constant-factor optimizations on a fixed-architecture machine.

As stated the problem appears to be fairly close (up to a constant factor) to the problem of finding asymptotic lower bounds to the running time of all correct solutions to a class of problems. The common way to refer to the class of "asymptotic lower bound" problems is to call it "the field of computational complexity thoery." It should be noted that the other (two at the current point!) "open problems in computer science" listed on this page are both from the domain of computational complexity theory, although it would be nice (in addition to having a solution to P vs. NP) to have a general mechanism for finding hard lower bounds on classes of problems, which appears to be what the original "speedup" section was asking for ;).

To what degree can one speed up a computation?

Field
High-performance computing
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.
Conjecture
Amdahl's law is a partial answer to the question. —The preceding unsigned comment was added by Mschures (talk • contribs) 05:54, 20 December 2006 (UTC).[reply]

Simple one way function?[edit]

Wouldn't A = B * C be a simple one-way function? Any functions which takes two inputs and produces only one output is impossible to reverse unless one of the input parameters are known. - Andrew Price

When people on cryptography say one-way function, it is usually implied that it is possible, although difficult, to invert the function. In fact, if you add the assumption that B and C are prime numbers (so that there is only one solution), the problem you describe is a very likely candidate for a real simple one-way function. It is easy to multiply two large numbers, however it is very difficult to factor a large number into its two primes. There are lots of places to read more on this topic. Meekohi 14:35, 7 August 2006 (UTC)[reply]
Just last night I read about the use of the logical OR (inclusive) to destroy any chance of reversability. But I can't remember where I read it. I.e. given a state machine with multiple entries into a state, we cannot retrace how the machine came its current state. But where the hell did I read this? I bet it was Minsky (1967).wvbaileyWvbailey 15:20, 31 August 2006 (UTC)[reply]

One way functions and the P=NP question[edit]

Aren't the P vs. NP and the one-way function problems supposed to be one and the same? Somebody, please explain this to me. Brendan 19:47 GMT, 06 Nov 2004

There is a lot of similarity between the problems but they are different. The P/NP question is whether one can compute in polynomial time what it can verify polynomial time. A one way function is a function the is hard to invert though easy to compute. One way functions pose harder problems. Solutions to many NP-complete problem can be approximated while if one way function exists they cannot be approximated. APH 06:45, 7 Nov 2004 (UTC)
Question: If P is not equal to NP, surely this means that one way functions exist -- since an NP problem would be one way? Am I still missing something?
Thanks. Brendan 07:12, 07 Nov 2004 (UTC)
If P=NP then there are no one way functions. If they are different, one-way function still might not exist. In NP-Complete problems, a small number of hard instances are enough for computational hardness. NP-complete problems might have approximate solutions and so. In one-way function we demand that the function will not be invertible, which is a stronger demand.APH 06:24, 23 Dec 2004 (UTC)
As I understand it, the discrete log problem is already in NP, so if P does not equal NP then the OWFs built using discrete log all work. So unless I'm mistaken then the existance of OWFs and the P=NP problem are equivalent. Someone speak up if I'm wrong about discrete-log being confirmed in NP, because I can't find a source for that offhand. Meekohi 05:59, 30 December 2005 (UTC)[reply]
The discrete log problem is in NP, and that is trivial to prove. (Proof: the discrete log value is the certificate, verifiable in poly time by modular exponentiation, even the naive algorithm for which is poly-time.) However, I think you're confusing "in NP" with "NP-complete." The discrete log problem is not known to be NP-complete, which is what it would have to be in order for "P not equal to NP" to imply "discrete log creates one-way functions." There are also some theoretical arguments suggesting good reasons to think that discrete log isn't NP-complete; for instance, it is random self-reducible, and if any random self-reducible problem were NP-complete then the polynomial hierarchy would collapse, which would be a surprising result of the same general nature as P=NP though perhaps not quite as surprising as P=NP. Bottom line: P not equal to NP doesn't automatically mean OWFs exist, and even if OWFs exist that doesn't mean discrete log OWFs are legitimate OWFs. Of course, this answer is probably too late to be useful to the original asker of the question. 216.75.183.126 (talk) 03:33, 5 March 2008 (UTC)[reply]
See One_way_function#Existance :"It is not known whether one-way functions exist. In fact, their existence would imply P≠NP, resolving the foremost unsolved question of computer science.". Note that though the discrete log is usually used as a one way function but it is not necessarily so. It might be that there are one way function while discrete log is not such. APH 09:28, 1 January 2006 (UTC)[reply]
After thinking about it some more I agree with APH. It seems like it is possible for P=NP, and yet there still be one-way functions. P=NP doesn't mean EVERYTHING is polynomial time, there are still problems outside of NP, and these could potentially be used to make a one-way function. Am I understanding that right? Meekohi 18:33, 1 January 2006 (UTC)[reply]
It is a bit more delicate. For any time bound, there are functions that cannot be computed within it (like the bounded halting function). However, most such function cannot be used as one way function since one way function should be easy to compute (hence in P).APH 09:10, 2 January 2006 (UTC)[reply]

Computability[edit]

I cut this section from the article as it is not an open problem. Since the thesis relates an informal notion ("effective computation") with a formal one it cannot be formalized without removing its contents. So this makes no sense.

Formalize Church-Turing thesis so it can be proved or disproved
Source: See Origins of the thesis
Description: The thesis states that every effective computation or algorithm can be carried out by a Turing machine. Since the term computation is not well defined, the thesis cannot be evaluated.
Importance: The proof of the thesis will show that Turing machine is indeed a universal computation device. Showing that the thesis is wrong will lead to a new kind of problems that are not computable.
Current conjecture: Turing machines were shown to be able to compute in computation possible in many computation models. It is conjectured that the thesis is true.

If you want to restore this section, please give references for experts in the field who consider it an open problem. Gdr 19:34, 2004 Nov 7 (UTC)

Formalize (axiomitize) 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 nutsell:
”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.” (p. 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:
Axiomatization is possible and the thesis is true.


I’ve rewritten the above to more closely represent the question, as I understand it. The following paper, just newly placed on Gurevich’s website, should satisfactorily appease the questioner above, as it quotes from both Paul Schoenfield, Georg Kreisel and Kurt Gödel as well as the authors themselves. Actually, the problem is well known, and I’m surprised someone took issue with it. After the appearance of Turing’s machines, Gödel in particular had not much use for general recursion and lamda-definability as foundations for the notion of “effective computability”; I know of two Gödel-quotes to substantiate this. See much more history at Talk:Church-Turing thesis.
The paper, by Nachum Dershowitz and Yuri Gurevich, is titled “A Natural axiomization of Church’s Thesis”, and 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 nutsell:
”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.” (p. 4)
Clearly from this, an open problem exists, or existed at the time when Godel, Kreisel and Schoenfield didn’t have an answer. Nowadays, Blass (another Gurevich collaborator) Dershowitz, Gurevich, Moschovakis (a dissenter re his article “What is an Algorithm?” (2001) ), myself, and CMummert, (cf long discussion at Talk:Algorithm ) have not seen an adequate axiomitization and proof. So therefore either the problem is presently open, or some folks out there in wikiland know something that Blass, Dershowitz, Gurevich, Moschovakis, CMummert and myself are unaware of.
I would say, given the demonstrated quotations above, that the burden of proof is now on the questioner(s) to show that an axiomization of premises leading to and subsequent proof (or disproof) of Church’s thesis has been successful. wvbaileyWvbailey 15:39, 31 July 2007 (UTC)[reply]
Other mathematicians presently involved in this are Robert Soare, and in particular Wilfried Sieg (cf Wilfried Sieg, June 1997, "Step by Recursive Step: Church's Analysis of Effective Calculability", The Bulletin of Symbolic Logic Vol. 3, No. 2, also available on the web). Another important contributor was Robin Gandy. wvbaileyWvbailey 15:18, 2 August 2007 (UTC)[reply]
I just found a fantastic article at http://math.ucsd.edu/~sbuss/ResearchWeb/FutureOfLogic/paper.pdf (cited in a 2007 Dershowitz-Gurevich paper):
Samual R. Buss, Alexander S. Kechris, Anand Pillay, and Richard A. Shore, “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, June 2000. In particular, under the heading “Computer Science” Shore stated the following three problems for 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)

There is more from the other authors, including Sam Buss’s question about artificial intelligence, “logic for computer science”, etc. I highly recommend reading this article if someone is interested in expanding this wiki-article. wvbailey

Removal[edit]

I removed the following because a)it's an engineering problem, not a CS problem, and b)it's not a problem at all in non-consumer hardware.

How can one deal with the memory wall?

Source:
Description: In today's computers memory access is becoming very slow when compared to CPU cycles. Hence, the memory access, like hard disk access, might become the term that bounds computation speed.
Importance: This is another important bound on fast computations.
Current conjecture:
a) Well, I actually heard about the problem from a cs researcher doing a post doc on it. I don't think that he will be happy if I'll use his name but I'll see.
The border between cs and engineering is quite unclear. Since you can deal with this problem in a completely theoretic model, I think that it can be considered as cs.
b) I didn't understand your intention in non-consumer hardware. This problem raise when dealing with high performance computing and indeed not in personal computers. So what? The P=NP question doesn't disturbs most computer users too.
I have a feeling that I didn’t understand your reasoning.
Please explain it a bit more.
Thanks, APH 15:56, 24 May 2005 (UTC)[reply]
My thought is that the 'memory wall' doesn't qualify as an open problem in terms of this page, because 1) there are already work-around solutions in place and 2) solving this problem would not have a 'major' impact on the field at the level of P=NP or disproving one-way functions (which would break public key cryptography). These requirements are not well spelled out on the main page, but the 'open problems' list seems to be for fundamental problems. --Sgorton 15:34, 13 February 2007 (UTC)[reply]
I agree that disproving one-way functions (especially if it was a "constructive proof" that could be immediately applied to break public-key cryptography) would have wider-ranging and longer-term effects than a slightly better work-around for the "memory wall" than the ones we already use.
However, since Wikipedia is not paper (WP:NOTPAPER), I think this page should list all open problems in computer science that are notable enough to deserve a Wikipedia article, and perhaps even some problems that don't have a Wikipedia article (yet), even though they may be far less "important".
You might be able to persuade me that some other "open problem" page would be a better place to list problems like the "memory wall" that are more engineering than science.
Yes, there are work-around "solutions" in place, but the memory wall is still described as a "growing problem". The fact that there are heuristic work-around "solutions" to the traveling salesman problem and other NP-hard problems, such as ant colony optimization algorithms, doesn't make the traveling salesman problem a solved problem. --DavidCary (talk) 13:18, 1 August 2011 (UTC)[reply]

Overall[edit]

This page needs a major rewrite. The problems seem randomly chosen, and there seem to be few factual errors: a) "If one-way functions exist then public key cryptography is possible." This is simply wrong; as far as we know OWFs do not imply public key encryption (they do imply signatures, though). b) "the speedup theorem from computability theory shows that any computation can be sped up by any desired constant degree". This is also wrong. That is not at all what the speedup theorem shows.

Feel free to make edits; one should be bold here. --Mgreenbe 11:18, 30 January 2006 (UTC)[reply]
I know i can make edits. But even if I invest the time to fix the errors here, I still would think that this page should rather be deleted. A random collection of some open problems is worth less than no collection at all, in my opinion.

I am sorry, but I do not have the time required to make this a good page.[unsigned, undated]

I think this is a fun and useful page, kind of in the spirit of Hilbert's problems. Read the talk page of Turing machine re the problem of what is and is not "computable" by what, i.e. analog vs digital/logistic computation. The page just needs more input.wvbaileyWvbailey 20:33, 16 August 2006 (UTC)[reply]

Add "definition of algorithm" to the list[edit]

One would think that "algorithm" is a perfectly-understood word. I too was surprised. Not so: in the same way the Church-Turing thesis is unresolved we see the need for a definition of what an algorithm really truly is/is not. For example see the work of Blass and Gurevich (2003) Algorithms: A Quest for Absolute Defintions (exact reference to be found at algorithm -- can be gotten off the microsoft website). I will add this after a while if no one objects.wvbaileyWvbailey 20:33, 16 August 2006 (UTC)[reply]

Church-Turing thesis?[edit]

Calling this an "open problem" is a bit of a stretch. Calling it a "problem" at all is a stretch. It's not a statement which needs to or can be proved or disproved mathematically. You could say it's a philosophical conundrum, but it's not an open problem in the usual (mathematical) sense. Staecker 00:24, 31 August 2006 (UTC)[reply]

All that we need to refute the thesis is a single counter-example. Perhaps the study of "mind" will yield non-algorithmic "methods" i.e. not Church-Turing equivalent but nevertheless effective at calculating more numbers that can be "calculated" by any Turing machine/algorithmic method. My guess is: this remains in the realm of "Hilbert's 20 questions" and continues to drive mathematics foundations. Now whether or not it is driving computer science is another question. I suspect it is: hence, "quantum computation/hypercomputers", etc. I vote it stays on the list: it provokes exactly this sort of interesting (and perhaps useful) dialog.wvbaileyWvbailey 15:12, 31 August 2006 (UTC)[reply]
We need a single counter-example, but what exactly would that mean? According to the statement in the article, that would require a process satisfying "an intuitive idea of computation" which cannot be modeled by a Turing machine. But such a statement cannot possibly made mathematically rigorous- using phrases like "intuitive idea" is a dead giveaway for metamathematical content. Since it's not mathematical, I don't think we can call it an "open problem". Perhaps philosophical interest in the thesis drives some research today, but that doesn't make it an open problem. Staecker 16:56, 31 August 2006 (UTC)[reply]
Kleene (re his (1952) Introduction to Metamathematics) would disagree that metamathematics isn't a topic for mathematics. But Minsky (1967) seems to agree with you, never mind he's not too convincing with his "intuitive argument" using appeals to "intuitive arguments". In his discussion of "an effective procedure a.k.a. algorithm" (his definition, in fact) he says the matter is subjective:
"Different people may not agree on whether a certain procedure should be called effective. Perhaps there are processes, we might suppose, which simply cannot be described in any formal language, but which can nevertheless be carried out, e.g., by minds. One might even argue that those important, but still mysterious, functions which make minds superior to all presently known mechanical processes must, by their intuitive nature, escape any systematic description.
"Turing discusses some of these issues in his brilliant article, 'Computing Machines and Intelligence' [1950] .. they amount, in my view, to a satisfactory refutation of many such objections." (p. 107)
Minsky goes on to state:
"One cannot expect to prove Turing's [his name for the Church-Turing] thesis, since the term 'naturally' relates rather to human dispositions than to any precisely defined quality of a process. Support must come from intuitive arguments..." (p.108)
Boolos and Jeffrey (1974, 1999) are more constructive:
"Although this thesis ('Church's thesis') is unprovable, it is refutable, if false. For if it is false, there will be some function which is computable in the intuitive sense, but not in our sense. To show that such a function is computable in the intuitive sense, it would be sufficient to give instructions for computing its values for all (arbitrary) arguments, and to see that these instructions are indeed effective....To show that such a function is not computable in our sense, one would have to survey all possible Turing machines and verify (by giving a suitable proof) that none of them compute that function.... Then if Church's thesis is false, it is refutable by finding a counterexample; and the more experience of computation we have without finding a counterexample, the better confirmed the thesis becomes." (italics in original, p. 20)
"Thus, the sun always rises because the sun has always risen." Truth by enumeration: animal logic. Bertrand Russell would have a field-day. At least Boolos and Jeffrey offer us a "road map" of how to go about approaching the problem. But they fall into the same trap: they are asserting that if a computational procedure isn't mechanical then it must be intuitive. Say what? that the world of computation is divided into two mutually-exclusive sets: "the intuitive" and "the mechanical"? Sure sounds like dualism to me ... intuitive 'minds' with 'souls' vs 'brains'made of gooey mechanical stuff ... interesting... most (but not all) philosphers of mind have given up on 'souls' ... maybe here is how one disproves or proves dualism? To wit:
What would be interesting would be if someone could prove that the truth of the Thesis is formally undecidable in any construct whatever, "intuitive or otherwise"-- forever unknowable to man or machine or God. One little [dualism] difficulty: what the hell does 'intuitive' really mean? [maybe that God is punching holes through the 5th dimension into our 4-D space-time, and is seeding minds with "notions" (but not mechanically altering them in the process)?]
I would call this sort of discussion a 'foundations of mathematics' debate, and therefore an open topic in some domain or other. Whether its 'philosophy' or 'foundations of mathematics' I don't know. I think they are the same. wvbaileyWvbailey 19:06, 31 August 2006 (UTC)[reply]

I agree with Staecker, calling this an open problem in CS is bogus. I think it should be removed from the list. Computability was axiomatized 3 different independent ways in the 1920's-30's, by Herbrand (recursive functions), Turing (Turing machines), and Church (lambda calculus). Then all three were proved equivalent and that mostly sealed the deal (Gödel had concern about whether recursive undecidability really precluded any other decision procedure, but seeing the equivalence of recursion and Turing machines convinced him). OK, Gurevich and Blass have yet another equivalent axiomitization. If some Church-Turing skeptic comes along who isn't convinced by the three older axiomitizations, they won't be convinced by the new one either. I'm not a CT skeptic myself, but come on, there are mathematical realists out there (I mean today, right now, 40 years after Cohen) who think the most important problem in set theory is to determine whether the continuum hypothesis is true or false, who believe that large cardinal axioms have a truth value, etc. Postulating that CT is false is fairly wimpy compared to that. 76.197.56.242 (talk) 15:44, 11 August 2008 (UTC)[reply]

Need many more entries[edit]

At one time there were more entries focused on technique and simulation and the practive of computer science. Now the page has devolved into a mathamatical discussion. I would much prefer a list like the unresolved problems in physics list. Ggb667 14:40, 31 August 2006 (UTC)[reply]

I agree that the list doesn't seem fully representative of known problems in computer science. I'd recommend the INFOSEC Research Council's Hard Problems list at http://www.infosec-research.org/docs_public/20051130-IRC-HPL-FINAL.pdf for a source of unresolved open problems in the computer security domain. I have to believe there are lists of known problems in other domains, particularly software engineering. --Sgorton 05:12, 5 February 2007 (UTC)[reply]
Agreed. It paints a depressing picture of the field that these are the only problems significant enough to make it to this list. If this were truly the case, all computer scientists could pool efforts on P=NP, declare computer science solved, and go find something else to do! I'd add some myself, but the problems I'm currently working on are far more esoteric (and far less important) than the ones listed here. Metasquares 18:44, 29 July 2007 (UTC)[reply]
I would like to suggest bold edits. Any problem whose resolution is a publishable result belongs to this page. If the list becomes to long, we merely create relevant subpages and categorize properly. If only so much work is intended, obviously entries that cover more important, well-known, many et.c. problems are more valuable, i.e. it is more valuable to write an article on BPP=NP? than something less popular such as E=AM?, or even better Deciding relationship between Complexity Classes. C. lorenz (talk) 12:55, 26 January 2008 (UTC)[reply]

Style, categories, qualifications[edit]

I've placed some of the categories - those relating to specific problems - against the section heading rather than at the end of the article which would be in accord with the WP:MOS. The reason is to make the article easier to maintain. As problems are added and removed the categories will change and if they're not associated with a particular problem then we'll end up with the article being in inappropriate categories. Placing the category entries in the corresponding section is the simplest way to do this. It's not essential, but clean. -- JDX 05:19, 29 September 2006 (UTC)[reply]

What qualifies a problem to be included? P=NP is obvious, but the others aren't. Challengelist is the only list I can find. I propose removing the UET and Relay Channel problems, and that problems shouldn't be included unless there's an external source justifying it and a separate article about the problem. -- JDX 05:19, 29 September 2006 (UTC)[reply]

These two problems have been removed:

  • What is an optimal UET scheduling algorithm for 3 processors with precedence constraints?
  • Capacity of the Relay Channel

The article version with them is: 2006-11-27 The reason is that there's no justification for them as major problems. Perhaps someone familiar with the issues could write articles giving more details on these problems, and then reinstate them. -- JDX 03:26, 27 November 2006 (UTC)[reply]

Computer go[edit]

Computer go is absolutely not an open problem in computer science. The reasoning is similar to the Church-Turing thesis above but much stronger. It is trivial to write an O(1) algorithm to play perfect go on a board of a particular size, just as solving chess was a trivial problem, just computationally infeasible. The question of whether an "efficient enough" algorithm may be written to defeat a "proficient amateur" in "reasonable" time on "realistic hardware" cannot be formalized. It is interesting, but belongs in the intersection of engineering and algorithms, not computer science. NTK 14:15, 13 April 2007 (UTC)[reply]

When considering a board of variable size n, GO is a PSpace-complete problem. There are attempt to cope with such problems not by always solving them but by finding randomized solutions, approximate solutions, etc. Maybe we should keep the problem but change its formalization. APH 06:42, 15 April 2007 (UTC)[reply]
There is no formalization, this is fairly meaningless in the context of Computer versus Human. Neither a human nor a computer can play Go on an infinite board. For very large n it would be easy for the computer to beat a human with a simple strategy based on sheer memory and endurance. For bounded n, the problem is again O(1). Clearly computer go in practice is a very hard, interesting, and unsolved engineering problem involving all the techniques you describe and more, but this is not a theoretical problem of computer science.
In any event, if you can actually formalize what a human go player is in the language of computer science, you will have accomplished something a lot bigger than computer go. NTK 01:34, 18 April 2007 (UTC)[reply]
Go is a PSpace Complete problem. You will get O(1) problems only if you don't restrict memory or build a special program for every n. Note That if you allow constructing a special program for every n you become so problem that you can solve problems like the halting problems. Coping with problems of high complexity class (even like just NP-Complte) happens a lot in practice. A solution that will be able to cope with the well (e.g., Showing P=NP)or proofing that one cannot cope with the problem is very interesting theory question. Again, I agree that the problem definition should be changed. On the other hand I think we should keep the problem. APH 05:35, 18 April 2007 (UTC)[reply]

Artificial Intelligence[edit]

Source:

In the article "Prospects for Mathematical Logic in the Twenty-First Century", Sam Buss suggests a "three-fold view of proof theory" (his Table 1, p. 9) that includes in column 1, "Constructive analysis of second-order and stronger theories", in column 2, "Central problem is P vs. NP and related questions", and in column 3, "Central problem is the "AI" problem of developing "true" artificial intelligence" (Buss, Kechris, Pillay, Shore 2000:4).

"I wish to avoid philosophical issues about consciousness, self-awareness and what it means to have a soul, etc., and instead seek a purely operational approach to articial intelligence. Thus, I define artificial intelligence as being constructed systems which can reason and interact both syntactically and semantically. To stress the last word in the last sentence, I mean that a true artifical intelligence system should be able to take the meaning of statements into account, or at least act as if it takes the meaning into account." (Buss on p. 4-5)

He goes on to mention the use of neural nets (i.e. analog-like computation that seems to not use logic -- I don't agree with him here: logic is used in the simulations of neural nets -- but that's the point -- this stuff is open). Morever, can I am not sure that Buss can eliminate "consciousness" from the discussion? Or is consciousness a necessary ingredient for an AI?

Description:

Mary Shelley's Frankenstein) and some of the stories of Edgar Allen Poe (e.g. The Tell-Tale Heart) opened the question. Since the 1950's the use of the Turing Test has been a measure of success or failure of a purported AI. But is this a fair test? [quote here?] (Turing, Alan, 1950, Computing Machinery and Intelligence, Mind, 59, 433-460. http://www.loebner.net/Prizef/TuringArticle.html

A problem statement requires both a definition of "intelligence" and a decision as whether it is necessary to, or if so how much to, fold "consciousness" into the debate.

> Philosphers of Mind call an intelligence without a mind is a zombie (cf Dennett, Daniel 1991, Consciousness Explained, Little, Brown and Company, Boston, ISBN 0-316-180066 Parameter error in {{ISBN}}: checksum-1 (pb) ):

A philospher's zomie, you will recall, is behaviorally indistinguishable from a normal human being, but is not conscious. There is nothing it is like to be a zombie; it just seems that way to observers (including itself, as we saw in the previous chapter). (italics added or emphasis)" (Dennett loc cit:405)

Can an artificial, mindless zombie be truly an AI? No says Searle:

"Information processing is typically in the mind of an observer . . . the addition in the calculator is not intrinsic to the circuit, the addition in me is intrinsic to my mental life.... Therefore, we cannot explain the notion of consciouness in terms of information processing and symbol manipulations" (Searle 2002:34). "Nothing is intrinsically computational. computation exists only relative to some agent or observer who imposes a computational interpretation on some phenomenon" (Searle 2002:17).

Yes says Dennett:

"There is another way to address the possibility of zombies, and in some regards I think it is more satisfying. Are zombies possible? They're not just possible, they're actual. We're all zombies [Footnote 6 warns not to quote out of context here]. Nobody is conscious -- not in the systematically mysterious way that supports such doctrines as epiphenomenalism!"((Dennett 1991:406)

> Gandy 1980 throws around the word "free will". For him it seems an undefined concept, interpreted by some (Sieg?) to mean something on the order of "Randomness put to work in an effectively-infinite computational evironment" as opposed to "deterministic" or "nondeterministic" both in a finite computational environment (e.g. a computer).

>Godel's quote: "...the term "finite proceedure" ... is understood to mean "mechanical procedure". concept of a formal system whose essence it is that reasoning is completely replaced by mechanical operations on formulas" ... [but] the reuslts mentioned in this postscript do not establish any bounds for the powers of human reason, but rather for the potentialities of pure formalism in mathematics."(Godel 1964 in Undecidable:72)

Importance:

> AC (artificial consciousness, an AI with a feeling mind) would no less than an upheavel in human affairs

> AI as helper or scourage or both (robot warriors)

> Philosophy: nature of "man", "man versus machine", how would man's world change with AI's (robots)? Will it be good or an evil act to create a conscious AI? What will it be like to be an AI? (cf Nagel, Thomas 1974, What Is It Like to be a Bat? from Philosophical Review 83:435-50. Reprinted on p. 219ff in Chalmers, David J. 2002, Philosophy of Mind: Classsical and Contemporary Readings, Oxford University Press, New York ISBN 0-19-514581-X.)

> Law: If conscious, does the AI have rights? What would be those rights?

Current Conjecture:

An AI is feasible/possible and will appear within this century.

This outline is just throwing down stuff. Suggestions are welcome. wvbaileyWvbailey 16:13, 6 September 2007 (UTC)[reply]

The central question for computer science is: Can every aspect of intelligence be simulated by a machine? (See the rewrite in progress of philosophy of artificial intelligence) ---- CharlesGillingham 08:59, 10 October 2007 (UTC)[reply]

Quantum Computers and Classical Computers[edit]

What does everyone think about adding the following problem to this list: "Are quantum computers more powerful than classical computers?" Or, in other words, "Is BQP a subset of P?" For example, the best known algorithm for integer factorization on a quantum computer is polynomial-time, while the best known algorithm for factorization on a classical computer is slower than polynomial time. However, it has never been proven that a classical polynomial-time factorization algorithm could not exist. See number 3 on this page: http://www.scottaaronson.com/writings/qchallenge.html. Also see Integer_factorization#Difficulty_and_complexity. I didn't want to immediately add this problem to the list without discussing it, considering the debate about other problems on this talk page. Also, I'm not even close to being an expert on quantum computing or complexity theory. :) --Navigatr85 17:37, 13 August 2007 (UTC)

This comes up in the paper by Buss, Kechris, Pillay and Shore (see the Church-Turing question). They specifically ask:
"What are the relationships among the classes P, NP, PP, BPP and so on?"
On page 12 of the article is a drawing that shows "Quantum computing" under "probabilistic computation". The name "Deutsch" seems to appear again and again: e.g. a couple references in the paper, including D. Deutsch, "Quantum theory, the Church-Turing principle and the universal quantum computer", Proceedings of the Royal Society A 400(1985) 97-117. I am not familiar with any of this other than (very) cursorily, but the question of "the power" of "analog computation" as well as "quantum computation" seems to come up again and again. Does this fall under the Church-Turing Thesis question? I dunno; I don't think it should necessarily. My guess is this is a decent question if you can figure out how to frame it properly and support it with sources. Don't be shy. The critics on this discussion page have been too picky and fussy, in my opinion. wvbaileyWvbailey 03:45, 14 August 2007 (UTC)[reply]
The infinite-resource quantum computer is Turing complete. However, research in Quantum finite automata has shown that certain classes of QFAs are more complex than DFAs, which represent our limited-resource classical computers (they can parse certain context-free languages and context-sensitive languages). SamuelRiv (talk) 09:19, 21 November 2007 (UTC)[reply]

Algorithm: what is such a beast?[edit]

This is a holding place for the following. The intent is not to push this or any other point of view, but to make the question evident. A number of epistomologic and mathematical issues bubble up from this:

from https://research.microsoft.com/~gurevich/
[164] Andreas Blass and Yuri Gurevich
"Algorithms: A Quest for Absolute Definitions"
Bulletin of the European Association for Theoretical Computer Science
Number 81 (October 2003), pages 195-225.
Reprinted in Chapter on Logic in Computer Science
Current Trends in Theoretical Computer Science
World Scientific, 2004, pages 283-311
Reprinted in Church's Thesis After 70 Years
Ontos Verlag, 2006, 24-57
See more details here
What is an algorithm? The interest in this foundational problem is not only theoretical; applications include specification, validation and verification of software and hardware systems. We describe the quest to understand and define the notion of algorithm. We start with the Church-Turing thesis and contrast Church's and Turing's approaches, and we finish with some recent investigations.
wvbaileyWvbailey 00:48, 5 September 2007 (UTC)[reply]

Interesting. The problem could be stated as "when are two algorithms equivalent?". Seems worth adding, and less bogus than trying to prove the Church-Turing thesis. 76.197.56.242 (talk) 15:49, 11 August 2008 (UTC)[reply]

Cleanup ideas[edit]

I think this article should be similar to the Unsolved problems in mathematics article. Obviously computer science doesn't just have 4 open problems, and listing all of them in detail would take up too much space. As handled in the math article, I think this article should just be a list of open problems with links to their articles. We could also split it up into sections, such as complexity theory, artificial intelligence, computational geometry and so on. --Robin (talk) 16:39, 20 August 2009 (UTC)[reply]

For years this article has been waiting for someone to list some of these "open problems" but no one has been able to do so. The one I listed came from a paper re open problems for the 21st century, but listed no other problems as "open" or at least significant enough to mention. So I suppose, if you know of some problems, then the thing to do (rather than worry about the article getting too large) is first simply list them e.g. in a table with a tiny commentary for each one (a reference would be nice too), and then let's see what happens from there. BillWvbailey (talk) 21:02, 20 August 2009 (UTC)[reply]
I could list 10+ open problems which are considered notable in theory/algorithms, which are the fields I understand. However, the reason I posted this is that I can't decide what is notable right now. If we're just going to have 5 problems, then the only notable problem in theory is the P vs NP problem. If we're going to have lots of problems, like the math article, then there are many interesting open problems which can be listed. But I see your point, maybe I should just go ahead and list all the problems I think are notable, and then let's see what to do. --Robin (talk) 21:47, 20 August 2009 (UTC)[reply]
What if we first tried to populate Category:Unsolved problems in computer science? If an open problem has a Wikipedia article, then it is likely that it is notable, too. — Miym (talk) 12:26, 25 August 2009 (UTC)[reply]
True, but I don't think most problems have their own page. Take, for instance, one of the oldest problems in algorithms -- matrix multiplication. The fast known algorithm has complexity O(N^2.376), whereas the conjectured complexity is near N^2. This is a huge open problem, but it doesn't really have its own page. There are several pages devoted to fast matrix multiplication algorithms though. --Robin (talk) 14:27, 25 August 2009 (UTC)[reply]
But it is such an important problem that it could have its own page... So I created Computational complexity of matrix multiplication which redirects to Matrix multiplication#Algorithms for efficient matrix multiplication. I tagged it with {{R with possibilities}}, and added it to Category:Unsolved problems in computer science. (Also Computational complexity of mathematical operations#Matrix algebra seems to have some relevant content.) — Miym (talk) 14:49, 25 August 2009 (UTC)[reply]

How do you feel about adding Scott Aaronson's challenge: Can you define Quantum Gravity Polynomial-Time? on page 13, in NP-complete Problems and Physical Reality. Pcap ping 03:19, 14 September 2009 (UTC)[reply]

I'm not sure how big an open problem it is though. There are bigger open problems (by bigger I mean more people have tried to solve it and have failed).
Do we agree on how to structure this article though? For instance, say I want to add the following open problem: Is P = PSPACE? There's no Wiki article about the problem, yet it is a fairly fundamental problem in Complexity theory. Other examples of such problems: Is P = BPP? Is NP = co-NP? Does the Polynomial Hierarchy collapse? Is P = NC? Since these problems don't have their own pages, even though P, NC, BPP, etc. do have their own pages, we can't present the problems the way the Math article does. --Robin (talk) 04:29, 14 September 2009 (UTC)[reply]
Those are generally good ideas. The threshold for inclusion here is less than WP:GNG because no separate article is being written. I would prefer a section like "other open problems in complexity", because this article would get really dry if we listed a lot of FOO =? BAR problems each with its own repetitive formatting/headings, even though I agree that a fair number of them are important. Pcap ping 04:49, 14 September 2009 (UTC)[reply]
I created the redirects P = PSPACE problem, P = BPP problem, NP = co-NP problem, and NC = P problem, and I added them to Category:Unsolved problems in computer science. (Some content needs to be added to the target pages, but each of them at least mentions that the problem is open.) Now we have some placeholders that we can put on this page, and we can follow the approach of the math article if it seems like a good idea. Let's not add too many of these, though; we can refer to the zoo for more examples of open problems in complexity. — Miym (talk) 07:33, 14 September 2009 (UTC)[reply]
One more idea for expanding the article: Linear programming#Open problems and recent work. Regarding the structure, I might try something like 1–2 paragraphs of text per problem, with references. — Miym (talk) 08:01, 14 September 2009 (UTC)[reply]
And more brainstorming:
— Miym (talk) 16:33, 14 September 2009 (UTC)[reply]

Church-Turing[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] Kreisel 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)

Removed[edit]

I have removed the above section because the idea that this is a problem appears to be a minority view; the consensus view appears to be that Turing's property is a reasonable formalization of a vague common language idea; as is not uncommon. See logical implication for a similar formalization of the natural language word if.

This may belong under Church-Turing thesis - but not here. Septentrionalis PMAnderson 23:42, 13 September 2009 (UTC)[reply]

Wrong. You may not agree with it, but your disagreement is not of much interest here. The issue is supported by the references. Bill Wvbailey (talk) 00:29, 14 September 2009 (UTC)[reply]
Well, I don't agree with it either. It is a minority view. None of the textbooks I have read share this view of the CT thesis. --Robin (talk) 00:35, 14 September 2009 (UTC)[reply]

I left some comments at Wikipedia_talk:WikiProject_Mathematics#Church-Turing_thesis_as_.22unsolved_problem.22. — Carl (CBM · talk) 01:27, 14 September 2009 (UTC)[reply]

It's an interesting line of research, but few pursue it. I agree with User:Pmanderson and User:RobinK; also User:Miym had a similar opinion. This is indeed a valid topic at the CTT article, but it's not even considered a formalizable problem by most to include it here as an open problem. Pcap ping 02:49, 14 September 2009 (UTC)[reply]
There seems to be a failure of communication here. Your personal opinions are not of interest. The sourced quotations are the matter of interest. If there's dissent, you need to produce the beef -- a quotation, in print, in a quotation here on this page. Bill Wvbailey (talk) 03:33, 14 September 2009 (UTC)[reply]
Requested citations from books: [4] [5] [6] [7]. Let's put it the other way around too: can you cite a non-WP:PRIMARY source, e.g. a book, saying that formalizing the CTT is feasible or an important open problem? Pcap ping 04:59, 14 September 2009 (UTC)[reply]
Besides, Dershowitz and Gurevich claim they have actually proved CTT [8] from their axioms on page 306, so how can you claim it is still unsolved based on their paper? Pcap ping 05:25, 14 September 2009 (UTC)[reply]
I saw nothing in your tertiary references that have anything to do with axiomatizing the notion of computation so the CTT can be proved or disproved. All I saw was a discussion of the thesis. Hell I can come up with dozens of those discussions. You know the strange thing is, this all started with Goedel who suggested it to Church. But anyway, as the statment of the problem actually says (you might want to re-read it), Dershowitz and Gurevich do claim their axiomatization. But this is a primary source, is it not? So it's okay for you to quote from one, and not okay for me? Interesting. I don't understand your aversion to primary sources, especially when bound into reviewed volumes. Quite often they contain secondary source material in the way of comments, and observations, criticism, references etc. You're way off base with regards to their use, and from what I could gather at the chatter, others agree with me. As I'm certain I'm not going to pursuade you, this discussion is closed as far as I'm concerned. I've got better things to do with my time. Wvbailey (talk) 12:37, 14 September 2009 (UTC)[reply]
Pcap is not alone; caution in using primary sources - especially, as here, on whether they represent a consensus position - is policy. Septentrionalis PMAnderson 16:41, 14 September 2009 (UTC)[reply]
Forget about subtle balancing of opinions from different sources. Just using a paper that clearly says that we've solved it to claim that it's an open problem is basically WTF?! to me. Pcap ping 17:31, 14 September 2009 (UTC)[reply]

scope[edit]

Does the scope of this article include recursion theory? I could add a handful of the most important problems from that area, if it is relevant here. — Carl (CBM · talk) 11:04, 14 September 2009 (UTC)[reply]

This poor article . . . its history shows that the same three problems "Prove or disprove the Church-Turing thesis", "P-NP", and "One way functions", have been there since 25 Oct 2004 (and it wasn't me who put them there -- I started editing in January 2006). And that's it. I remember seeing Go and a few others, but they've been deleted. Probably its scope should be expanded if it is going to survive as an article. Maybe "Unsolved problems in computatibility" or something of that sort. My favorite is the Collatz Conjecture, but can we argue that that is a computer science problem? I would call it a recursion/computability problem, and a gnarly one at that (the last significant result I saw was Liesbeth De Mol's Tag systems and Collatz-like functions but that was from a couple years ago when I was working on it). Bill Wvbailey (talk) 13:14, 14 September 2009 (UTC)[reply]
Feel free to add open problems related to recursion theory and computability. Collatz conjecture sounds like a good addition to me, especially as we already have a Wikipedia article about it. I don't mind if there is some overlap between this page and Unsolved problems in mathematics. Please don't rename; "Unsolved problems in computability" is much more narrow than "Unsolved problems in computer science", cf. Outline of computer science. — Miym (talk) 13:47, 14 September 2009 (UTC)[reply]
The Collatz conjecture can be settled by computation only if it is false and the minimal counterexample is not of unreasonable magnitude; even then, its applicability to computer science is unclear. I would be extremely cautious of adding it here. Septentrionalis PMAnderson 16:45, 14 September 2009 (UTC)[reply]
A proof would probably not proceed by exhaustive search -- this has been done, with the surprising result that most of the "bad action" is in the lower numbers, e.g. 27, where "3n+1" almost explodes, but doesn't quite -- things get more orderly with larger numbers. (Other coefficients such as 5n+3 are fair game, and some cofficient'assignments cause "explosions", and some lapse into loops. Also negative coefficients are fair game. An absolutely fascinating problem; BTW this is all in the literature). A proof may follow along the lines of De Mol. To quote her: "a method will be described to reduce the 3n+1-problem to a tag system which is surprisingly small . . . these result will be related to some findings concerning the reducibility of Collatz-like functions to Turing machines studied in the context of the boundaries of solvability in Turing machines." Goedelization such as used by Minsky 1967 text in his proofs is possible, I've worked with counter machines, etc etc. I should think that efforts in this regard could fall into the realm of "theoretical" as opposed to "applied" computer science (De Mol wrote this from "The Centre for Logic and Philosphy of Science" in Gent, Belgium). Bill Wvbailey (talk) 12:47, 15 September 2009 (UTC)[reply]

P==NP[edit]

Lets assume, for the purpose of argument, or in order to prove a contradiction that I have reduced a broad category of NP problems to P problems in P time.

and I assert that I have solved it for NP problems.

What should I do? Have I already done it, here today? If not why? Mathiastck (talk) 17:07, 31 January 2010 (UTC)[reply]

I am not sure quite what you mean. P itself is a broad category of NP problems, and every one of them can be reduced to P in P-time. — Carl (CBM · talk) 23:11, 31 January 2010 (UTC)[reply]
Yeah I totally don't even know what I was thinking then either. Nevermind! Mathiastck (talk) 23:14, 11 February 2010 (UTC)[reply]


P = NP?[edit]

I remember seeing a news article recently saying that this problem has been solved and that the result was bad news for computing speed. Is that the case? Abyssal (talk) 02:24, 16 August 2010 (UTC)[reply]

Take a look at P_versus_NP_problem#Claimed_solutions - looks like it's not solved yet. -pinkgothic (talk) 15:42, 3 September 2010 (UTC)[reply]
How about this:? http://kafcsn.org.ua/lang/en-us/anatoly-d-plotnikov-professor-department-computer-systems-and-networks-east-ukrainian-national-university-solved-the-problem-p-vs-np.html ? "See also" User_talk:David_Eppstein#Explanation_Re_edit_to_.22P_vs._NP.22_article and User_talk:Yellowdesk#Explanation_Re_edit_to_.22P_vs._NP.22_article . ...Thank you, --Mike Schwartz (talk) 22:50, 24 September 2012 (UTC)[reply]

removal of POPLmark?[edit]

Is there any real sense in which the POPLmark challenge is still an "unsolved problem"? If nobody objects, I'm going to delete it.Erniecohen (talk) 03:42, 14 April 2017 (UTC)[reply]

Computers and Unsolved Problems[edit]

          Computers are the devices which manipulate, operate, analyse, and does other tasks at the same time as multitasking, including storing information. But, do we know that the things invented by humans will have definitely some standard errors? And so computers have! How can a computer verify and solve a problem in the same polynomial time? can we solve and verify a problem in the same polynomial time? Bringing a solution and verification to a problem depends on the size of the problem, speed taken by the object(including humans and computers) in the problem, length of the problem, efficiency of the object in the problem, its power usage, its memory usage, number of ways in the problem, external factors like input and output factors and its capacity, often as energy. One should not think that an object can solve and verify a problem at the same polynomial time, because, no object can do anything with 100% efficiency. And so, like us, computers also cannot solve and verify a problem at the same polynomial time due to this. And so, I can say that always P≠NP in this same way.

Note : Since I am young, studying higher secondary second year, please refer this, and if this gives any clue regarding mysteries, try to spread with this and even try to research about this, my dear brothers. For any purposes regarding this, send via email ID as follows : msusendran@gmail.com, email ID of publisher of this topic.2409:4072:6116:6893:4D30:D4F8:E2BE:8B34 (talk) 17:10, 17 July 2018 (UTC)[reply]

Unsolved NLP problems[edit]

This article includes a list of unsolved problems in natural language processing, though the description of these problems is somewhat vague. Is it true that the problems listed in this section are still unsolved? Jarble (talk) 10:48, 29 January 2019 (UTC)[reply]

Entombed maze generation algorithm[edit]

In the article, there's a reference to the game Entombed and the maze generating algorithm it uses.

It looks like, in the meantime, an analysis of the algorithm used was published. It would be nice if someone would have the time to go through that paper and extract the main ideas and present them in a wikipedia page. I would read something like that.

Typing error about fast fourier transform?[edit]

The question Can the fast Fourier transform be computed in o(n log n) time? must be a typing error, as the answer is obviously yes. Presumably the question should instead be Can the fast Fourier transform be computed in faster than o(n log n) time?. — Preceding unsigned comment added by 165.225.80.233 (talk) 16:44, 19 February 2020 (UTC)[reply]

Not a typo. Notice that the o is lowercase. This is little o notation. The question Can this problem be solved faster than Θ(n log n)? is equivalent to Can this problem be solved in o(n log n) time? Rzvhkon (talk) 07:51, 23 December 2020 (UTC)[reply]


bigO of making a 3d model from multiple 2d pics[edit]

Photogrammetry software exists but seems to require alot of compute power or does not update the 3d model in realtime, especially if the 3d objects are moving while new images come in. Augmented reality often only detects position of camera(s) to mount virtual objects into while requiring handheld input devices since the cameras do not detect the Human body precise or fast enough. This may be because more efficient algorithms are not known. 2600:6C5E:1C7F:3889:4887:FFA8:A854:C4CF (talk) 17:23, 12 July 2021 (UTC)[reply]

Answers by computer[edit]

Are computer answers acceptable to add if they solve these questions?

For example While asking the bot at https://huggingface.co/spaces/codellama/codellama-13b-chat

Can integer factorization be done in polynomial time on a classical (non-quantum) computer?

Answer: No, integer factorization cannot be done in polynomial time on a classical (non-quantum) computer. This is because the running time of the algorithm increases exponentially with the size of the input, which is a property of the integer factorization problem. In particular, the integer factorization problem is known to be NP-hard, which means that it is at least as hard as the hardest problems in NP. This means that if a polynomial-time algorithm for integer factorization were discovered, it would immediately solve all problems in NP, which would have profound implications for the field of computer science. There are several reasons why integer factorization cannot be done in polynomial time on a classical computer. One reason is that the running time of the algorithm increases exponentially with the size of the input. For example, if the input is a number with n digits, the running time of the algorithm will be at least O(2^n), which grows exponentially with the size of the input. Another reason is that the integer factorization problem is closely related to the hardness of other problems in NP, such as the decision problem for the group of units of a number field. These problems are known to be NP-hard, which means that they are at least as hard as the hardest problems in NP. This means that if a polynomial-time algorithm for integer factorization were discovered, it would immediately solve all problems in NP, which would have profound implications for the field of computer science. Overall, while it is possible to solve integer factorization problems in practice using algorithms that are not polynomial time, it is not possible to solve them in polynomial time on a classical computer. 31.161.145.232 (talk) 19:44, 5 September 2023 (UTC)[reply]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:List_of_unsolved_problems_in_computer_science&oldid=1203701722"