Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.]
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.
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.
Check the publications of people known to consider fun problems and problems for fun. For instance:
Have a look at my (modest) proposal of "fun" problem below. If you work on it, get in touch with me!
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.
