What can be a possible open ended research topics in Computational Complexity (or something equally fun), for an undergraduate to think about?

[I am planning to take up something fun, however my objective is not to publish a paper, but just to think about it for the joy of the subject :) , but of course, if a paper comes along, that might be fun as well...

P.S. I have taken basic courses in Theory of Computing, Algorithms, Advanced Algorithms, Advanced DS and Discrete Mathematics among others.]

  • $\begingroup$ This depends on your strengths/weaknesses and interests. $\endgroup$ – András Salamon Aug 22 '13 at 8:18
  • $\begingroup$ cstheory policy on project topic questions. Also see tour and help center. $\endgroup$ – Kaveh Aug 22 '13 at 14:47
  • $\begingroup$ @Kaveh My Apologies :) I did not realize this would be against the policies of the forum, However in my defense, I would like to state that this was asked not in the lines of pursuing a research project but in the spirit of learning something new and think about ideas . If you still think this is wrong, I would be more careful in the future :) $\endgroup$ – Subhayan Aug 22 '13 at 14:58
  • 1
    $\begingroup$ "I want something to think about" is not a suitable question for this site, the questions should be more focused. $\endgroup$ – Kaveh Aug 22 '13 at 16:47
  • $\begingroup$ well, I thought I was asking for a list of open ended problems accessible for undergraduates (something like this ), anyway I trust your judgement, so sure, i'll be more careful from next time :) $\endgroup$ – Subhayan Aug 23 '13 at 1:55

Of course, for us in academia, most problems are fun anyway: we would not be there otherwise ;) But I understand that you might be more interested in problems which do not require much background and/or which are related to mundane topics like social games. Note that it might be harder (and more important) for you to find someone willing to comment on your solution and help you to improve it than to find a fun problem itself. For this reason, asking a professor in your department might be a better starting point. That said, here are some suggestions as to where to find ideas, and a modest proposal of mine.

  1. Have a look at the proceedings of the conference "Fun with Algorithms": they should provide you with a good selection of "Fun" problems to work on, and a venue where to submit your results for feedback.

  2. Check the publications of people known to consider fun problems and problems for fun. For instance:

  3. Have a look at my (modest) proposal of "fun" problem below. If you work on it, get in touch with me!

Levitating Towers

As an undergraduate, you probably know the problem of the Hanoi Tower. If you want to "have fun", you might consider simple variants of it. Here is a very simple variant you might be interested in, which I designed for an assignment while I was a TA for an algorithm course, but never gave to students because I found it too hard for undergraduate (at least too hard for a marked assignment).

Consider the case where you insert and remove disks always in the middle of the tower (defined in a symmetric way when the number of disks is even, so that you always remove the last disk that you inserted), while keeping at all time the constraint that no disk stands upon a smaller one. In how many moves can you move a tower of $n$ disks from one peg to another?

The exact answer is not known. I obtained at the time a complicated upper bound of $2^{n/2}$ via a combination of 3 recursive functions. The graph of all possible states and transitions (a classical way to study the original Hanoi tower problem) is fragmented. I believe there should be a reduction to the original problem but did not find it when I played with it.

Play with it. An example of the difficulty of the analysis (say, for symmetric rules removing the lower middle disk when the number of disks on a peg is even, and inserting below the center disk when the number of disk is odd) is the case where there is $1$ small disk (e.g. $1$) on the destination peg and $2$ larger ones (e.g. $8,9$) on the source peg. This particular sub-tower of height $2$ can be moved without any intermediate peg in $2$ moves (as opposed to $3$ moves and one intermediate peg in the traditional Hanoi tower): the removal order of the source peg is the same as the insertion order of the destination peg.

  • $\begingroup$ Thanks @jeremy :). The TOH variant seems interesting enough.. And by 'fun', i meant 'any other' open ended problems from the domain of Theory, not necessarily about games.. theory is pretty much interesting by itself ;) More suggestions are still welcomed :) $\endgroup$ – Subhayan Aug 22 '13 at 11:55
  • $\begingroup$ Please see the policy on project topic questions. $\endgroup$ – Kaveh Aug 22 '13 at 14:48

Not the answer you're looking for? Browse other questions tagged or ask your own question.