Talk:List of open problems in computer science

From Wikipedia, the free encyclopedia

You have new messages (last change).
 This article is within the scope of WikiProject Computer science.
??? This article has not yet received a rating on the assessment scale.
??? This article has not yet received an importance rating on the assessment scale.

Contents

[edit] Deletion of speedup section

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).

[edit] Simple one way function?

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)
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)

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

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)
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)
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)
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)

[edit] Computability

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)

[edit] Removal

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)
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)

[edit] Overall

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)
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)

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

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)

[edit] Church-Turing thesis?

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)

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)
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)
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)

[edit] Need many more entries

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)

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)

[edit] Style, categories, qualifications

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)

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)

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)

Retrieved from "http://en.wikipedia.org../../../l/i/s/Talk%7EList_of_open_problems_in_computer_science_a669.html"