views:

1591

answers:

15

Hi everyone,

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

+6  A: 

What about the bin packing problem? 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

Chris Dennett
+18  A: 

This recent article discusses the Post correspondence principle.

deinst
I said to my self at the middle of the article no way this one must have a solution! Nice problem.
AraK
+2  A: 

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

Vatine
+3  A: 

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:

alt text

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

Luther Blissett
+9  A: 

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.

Edward Leno
Especially good if you like graph theory. This has got to be the problem that would make you the most money if you managed to solve it :)
Richard
@Richard: If you can solve any NP-complete program in polynomial time, you can solve all of them, and a whole lot of them would have great economic impact. TSP is just one of them, and arguably not the most important.
David Thornley
+6  A: 

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

belisarius
See also http://mathworld.wolfram.com/ChromaticNumber.html
Daniel Trebbien
+2  A: 

3SUM Hard problems.

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

Moron
I'm not sure I would call that a problem "understandable by a child."
Michael Blackburn
@Micheal: I don't see "understandable by a child" anywhere in the question. I only see average CS student/programmer.
Moron
+4  A: 

A now solved, easy to understand but tough to solve problem is the PRIMES is in P 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

Moron
+3  A: 

I think the most interesting problem is writing a program to pass the Turing test, because

  • it requires a computer (as opposed to possibly being solved with just paper and pencil, like many proposed exercises that are really math problems),
  • it's simple to state but has to be posed in prose (as opposed to being formulated in math terms),
  • a solution would have tremendous consequences and applications,
  • it includes many philosophical and not just practical hurdles,
  • it's easy to pose but difficult to solve,
  • many "toy" sub-solutions are available to experiment with,
  • laypeople understand the problem (although maybe not why it's hard to solve) and can even test the solution,
  • it's a problem that at first seems solvable but that quickly explodes in complexity as a solution is attempted,
  • it's easy to restrict the domain (eg, only blocks on a table) to create a more-manageable subproblem,
  • it's one of the oldest computer problems,
  • it requires understanding of our own human nature and abilities,
  • it's created tremendous debate for decades,
  • there's actual money (Kapor/Kurzweil) riding on the problem.
joe snyder
But it's becoming less important, I think. There's a growing feeling that passing the Turing test is not that useful any more.
mtc06
Moreover, it takes a great deal of work and resources to get anywhere close. You can fiddle with an NP-complete problem whenever. You can hold a clear idea of the problem in your head in the shower. This is far beyond professors of AI to understand in full.
David Thornley
@mtc06: not useful? a program capable of intelligent conversation would be the most useful software suggested. i'd put it to work taking my calls, handling my emails, scanning stackoverflow...
joe snyder
+4  A: 

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:

  • The ropes are of different length and you don't know how long they are.
  • Each rope burns in precisely 1 hour.
  • Each rope has a non-uniform density, meaning it is thicker at some points than others. Consequently, burning half a rope cannot be guaranteed to take 30 minutes.

It is more logical than anything else, I "heard" it was one of Microsoft recruitment question.

Lobsterm
(http://www.rot13.com/): Jryy vs jr fgneg oheavat obgu raqf bs bar ebcr ng gur fnzr gvzr, gura gur jubyr ebcr jvyy ohea hc nsgre rknpgyl bar-unys ubhe. Fb, vs jr fgneg oheavat BAR raq bs gur frpbaq ebcr jura jr fgneg oheavat obgu raqf bs gur svefg, gura jura gur svefg ebcr oheaf hc gur frpbaq jvyy unir rknpgyl unys-na-ubhe yrsg; fb vs jr fgneg gur BGURE raq bs gur frpbaq ebcr oheavat ng gung gvzr, vg jvyy ohea hc nsgre rknpgyl 15 zber zvahgrf.
BlueRaja - Danny Pflughoeft
+1  A: 

If 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?

brian
Assuming that's the only definition given, then it would take 2 shuffles. Once to shuffle it, and then once to shuffle it the other way, putting it back into its original state. Assuming you can't go backwards in shuffle direction, then it would take 52 shuffles.
drharris
If you start with 8 cards labeled 1 and 2 (just for brevity) and started with this order: 11112222, on the first shuffle, you'd shuffle 1111 into 2222 and get: 12121212, the second shuffle you would shuffle 1212 into 1212 and get: 112211221122, etc.
brian
For a deck with n cards, it takes http://oeis.org/classic/A024222 (n) perfect shuffles to return the deck to its original state. For n = 52, this is 8 shuffles. With the jokers, it takes 52 shuffles.
Charles
A: 

I find the integer factoring problem quite interesting. Very simple to state and very difficult to solve.

Jus12
+1  A: 

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

William
Nice. Sadly, they will never get the money.
chronos
+1  A: 

The undecidability of the halting problem. 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.

polygenelubricants