6 ms·
List of unsolved problems in computer science
- sauravt 14y agoList of unsolved problem in Mathematics http://en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics http://en.wikipedia.org/wiki/List_of_unsolved_problems_in_ma...
- MojoJolo 13y agoWhat is the fastest algorithm for multiplication of two n-digit numbers? What is the fastest algorithm for matrix multiplication? I think those "What is the fastest" questions are relative. In my opinion, they are not unsolved problem. There are already solutions for them. And in those current solutions, there is of course the fastest. When a faster algorithm is formulated, a time will come where another algorithm will perform much better. EDIT: Now I get it. That "fastest" is in terms of time complexity. Thanks guys. :)
- ginko 13y agoI believe fastest in this context means that it has been proven that there can be no faster algorithm.
- MojoJolo 13y agoIs it really possible? I believe the "fastness" of something is infinite because of numbers being endless.
- olalonde 13y agoThe "fast" here refers to the complexity of the algorithm. http://en.wikipedia.org/wiki/Computational_complexity_theory http://en.wikipedia.org/wiki/Computational_complexity_theory
- wlievens 13y agoIndeed, in terms of complexity theory I would guess, not in terms of milliseconds.
- jd007 13y agoRead http://en.wikipedia.org/wiki/Big_O_notation http://en.wikipedia.org/wiki/Big_O_notation Basically it's talking about time complexity, or how fast does the time it takes to compute the solution grow as the input grows in size.
- ginko 13y agoAn Algorithm with a lower time complexity will always take a shorter amount of time once the problem size grows large enough. You could run one algorithm on a modern cpu, utilizing Simd and tune for cache coherency and the other in QBASIC on an old 386 and the O(n log n) algorithm would still terminate earlier than the O(n^2) one past a certain n.
- fractalsea 13y agoWith regards to matrix multiplication[1]: I think the hidden subtext here is that many people believe there exists a O(n^2) algorithm for matrix multiplication, but it has not been discovered yet. [1] Wouldn't be surprised if this is the case for the other problem too, although I don't know much about it.
- amund 13y agoRan Raz proved that Matrix Inversion is O(n^2 lg n), ref: Ran Raz. On the Complexity of Matrix Product. SIAM Journal on Computing, 32(5):1356–1369, 2003. Based on that I deduced that Matrix Multiplication is O(n^2 lg n), http://amundtveit.info/publications/2003/ComplexityOfMatrixInversion.pdf http://amundtveit.info/publications/2003/ComplexityOfMatrixI... Regarding even faster operations, it has been hypothetized that all matrices are Toeplitz or Hankel (which have O(n lg n) algorithms), ref: D. S. Mackey, N. Mackey, and S. Petrovic. Is Every Matrix Similar to a Toeplitz Matrix. Linear Algebra & its Applications, 297:87105, 1999. But that was proved to not be the case: T. Amdeberhan and G. Heinig - http://www-math.mit.edu/~tewodros/georgmemoriam.pdf http://www-math.mit.edu/~tewodros/georgmemoriam.pdf
- jd007 13y agoIt's talking about big O time complexity, which means you have to prove that there can be no faster algorithm. For example comparison sort (so no radix) can be no faster than O(nlogn).
- fractalsea 13y agoIt would be nice to see more. I'm sure there are. Having said that I suppose most problems we face in this field boil down to mathematical problems at the fundamental level. At least that's the conclusion I came to when I tried to think of unsolved AI problems.
- k__ 13y agoI like how the POPLmark sounds like popel-mark in german. Which would mean something like booger-money in english.
- deleted 13y ago[deleted]
- nawitus 13y agoFactoring can be polynomial even if P!=NP.
- oggy 13y agoInteger factoring is not (known to be) NP hard, i.e. we don't know whether we can reduce any NP problem to integer factoring (we suspect we cannot). On the other hand, it's in the intersection of NP and Co-NP, because you can give an effectively checkable proof of both primality and compositeness. If you're interested to learn more about these things, Scott Aaronson has an equivalent of a complexity course stuffed into one lecture here ;) http://www.scottaaronson.com/democritus/lec6.html http://www.scottaaronson.com/democritus/lec6.html
- gbog 13y agoI'd like to see some more general unsolved problems concerning big code bases, programming languages, etc. Examples: - Object-relational impedance mismatch - MVC (solves only half of the problem) - Global state - Schema vs schemaless data stores - Raising exceptions vs returning error codes A good sign of an unsolved problem in this regard is that programmers go back and forth between solutions, forgetting the downsides of the previous flavour while enduring the downsides of the current flavour. Very often, one new solution pretends it will get rid of complexity, but the actual complexity is just moved a bit further behind the carpet.
- dbaupp 13y agoGenuine question: wouldn't those be better suited to a "Unsolved problems in software engineering" list?
- gbog 13y agoYes.
- chongli 13y ago>Object-relational impedance mismatch This one is easy: don't do it! If you're talking to a database, you should be using a powerful and declarative language for building your queries. >Global state This is a solved problem from a computer science perspective. The rest of the work is getting programmers to understand how and change their habits accordingly. >Raising exceptions vs returning error codes Option/Either types are a very strong middle ground. They don't require the boilerplate of checking error codes and they don't have the unpredictability of exceptions (particularly in the case of asynchronous code). >Very often, one new solution pretends it will get rid of complexity, but the actual complexity is just moved a bit further behind the carpet. I know what you mean. A lot of solutions end up "punting" the complexity to some other structure. The real answer (if there can be one) is to find ways to eliminate this complexity altogether. One major way to do that is to work with values and compose pure functions to build them. Pure functions dramatically improve one's ability to reason about their properties in isolation.
- larsberg 13y agoPOPLmark seems to generally be considered solved. There are multiple good solutions using different tools for all of those problems, I believe. And the real goal has largely been reached. At this point, if you're proposing new PL theory and you don't have a mechanised proof of it, the entire work is viewed with considerable skepticism. That said, reuse and productivity are still not much better than that of real-world software. My peers who do that sort of thing are in very high demand for post-doc positions on projects funded by various governments/militaries to "prove the X property about software system Y."
- gerhardi 13y agoHow about a list of greatest problems in computer science that have been solved? Would make a nice list to study and to gain general knowledge!
- aaron695 13y agoI don't know, I consider them more unsolved mathematics problems in the non academic world. I know tomato tomato, but to me in computer science it's more important to know if they have been solved for most cases (Or alternatively considered probably to hard in RL) Getting to caught up in perfect solutions can be more a hindrance.
- tel 13y agoI'm going to bicker about language, but that sounds more like a software engineering mindset. Most of the most fundamental problems in computer science have exactly that kind of mathematical nature. Works well enough gets a paycheck, but doesn't impact the field.
- gcr 13y agoThe name you're looking for is "Unsolved problems in computer engineering." I agree; there should be an article for that, but it should be kept separate from this one.