Months ago, I was reading about unsolved problems in Computer Science to this day. I took a look at some of the problems, and clearly it is not enjoying to challenge your self to try some problem for fun unless you understand what the problem is. I would say, I couldn't make head from tail with the knowledge I have reached so far. Yet, one interesting problem which is Collatz conjecture [1] made me smile. How could such a "simple" problem be unsolved for years and years. I could have explained it to a child, and still he would understand the problem clearly. I spent hours and hours trying to find a solution or a proof, but I reached nothing. Obviously, finding a solution would make anyone a super-star scientist at the moment of solving the problem. It is not that "lying" thinking that I would find a solution, but the process of thinking and discovering surprising results that I am looking for out of such "simple to understand - super hard or not yet solved problems."
What is the problem you find the most interesting in Computer Science, yet an average CS student or programmer can understand?
Please, one problem per answer.
Thanks,
This recent article discusses the Post correspondence [1] principle.
[1] http://www.loopycode.com/a-surprisingly-hard-problem-post-correspondence/I always liked the traveling salesman problem. I heard about this as a kid and more recently worked with a dispatch system that tried to solve this. The concepts are easy, but the solution is virtually infinite (given enough points). http://en.wikipedia.org/wiki/Travelling_salesman_problem.
What about the bin packing problem [1]? This problem is NP-hard, but it is is relatively easy to work out why this is the case. Think about a lorry or truck with boxes that must be put in to make the best use of the available space. Is it possible to find an optimal solution to this problem without resorting to brute force?
Here's a Stack Overflow question relating to it too: http://stackoverflow.com/questions/1170478/how-to-create-an-optimized-packaging-function-in-python
[1] http://en.wikipedia.org/wiki/Bin_packing_problemOne interesting now-solved problem is the "four color theorem". It remained unproved from 1852 to 1976, and the remarkable fact was that it was THE FIRST theorem solved with computer help.
The statement is (veeery simple) "four colours is enough to paint a map in the plane such that no two bordering nations share the same color".
The article in Wikipedia is here http://en.wikipedia.org/wiki/Four_color_theorem
For sure it's not the answer you are looking for, but I think it is historically relevant.
You are equipped with two ropes and some matches.
Your goal is by burning the rope(s), to identify when exactly 45 minutes has passed. All you know about the ropes is:
It is more logical than anything else, I "heard" it was one of Microsoft recruitment question.
Sorting networks is a good one, IMHO. The concept of a sorting network is simple: You connect inputs which you want to compare and swap if one is bigger than the other, and what you want is to connect these inputs in such a way that the inputs are getting sorted with the least number of compares:
This turns out to be difficult, with some deep theory involved. For example, we don't know optimal networks with more than only 8 inputs! On the other hand, having these sort networks is a great thing because you can specialize a sorting algorithm for known array sizes into a optimal ladder of compares and swaps or build fast hardware sorter.
http://en.wikipedia.org/wiki/Sorting_network
A now solved, easy to understand but tough to solve problem is the PRIMES is in P [1] problem.
The problem: Is there a polynomial time algorithm to detect if a number is prime?
This was recently answered in the affirmative by the following paper: http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf
[1] http://members.cox.net/mathmistakes/primes.htmI think the most interesting problem is writing a program to pass the Turing test [1], because
Don't know if it is more mathematics or CS, but...
You have N boxes. In these boxes, you place the integers from 1 up, one at a time. You cannot put an integer in a box, if two integers in that box sum to it.
Now, find a closed formula for the first number that cannot be put in a box (or, if you prefer, the highest number that can be put into a box, before no other number can be added).
3SUM Hard problems [1].
Easy to understand:
Given three integer arrays A,B,C is there a better than quadratic (i.e sub-quadratic) algorithm which tells you if there are some a,b,c (a in A, etc) such that a+b=c?
A lot of problems in computational geometry have been shown to be 3SUM Hard, so it is not just interesting, but an important open problem. Check out the survey paper: http://www.cs.mcgill.ca/~jking/papers/3sumhard.pdf
[1] http://maven.smith.edu/~orourke/TOPP/P11.htmlI found this following question/riddle fascinating: seemingly impossible, but surprisingly simple when applying simple logic.
Two prisoners are called up by the king to play a game. Each of them will have a coin stuck on their forehead, so that each person can see the other's coin, but not their own. They are now each given one chance to guess what side the coin on their own head is.
If both of them get it right, they will be set free along with 1000 golds each.
If one of them gets it right, they will be both freed, but no gold will be given.
If no one gets it right, both will be executed.
What strategy should they use?
(answer is provided below the line)
The answer: person A says the side of coin on person B, and person B say the opposite side of coin on person A. They will always get one right, hence they are guaranteed to be freed.
The undecidability [1] of the halting problem [2]. That is, it's IMPOSSIBLE to construct an algorithm to tell if any given algorithm will eventually stop or will just run forever.
Understanding this is a very humbling enlightenment. Most people initially thought that this must be possible at first.
[1] http://en.wikipedia.org/wiki/Undecidable_problemIf you could shuffle a deck perfectly (so the resulting deck is exactly half of the original deck interleaved into the other half 1-by-1), how many shuffles would it take to get the deck back to its original state?
I find the integer factoring problem [1] quite interesting. Very simple to state and very difficult to solve.
[1] http://en.wikipedia.org/wiki/Integer_factorization