[one2remember]

I'm looking for interesting open questions in complexity theory that someone with an undergraduate degree in math and comp/sci could theoretically tackle. I have strong interest in the polynomial hierarchy, and the study of probabilistic classes like RP, co-RP, ZPP, BPP, and also their logarithmic counterparts. I also have some interest in quantum computing complexity theory, but I'm afraid my knowledge of quantum isn't that strong. (Only the basics from my modern physics class, which included some quantum). Important: must be new research or new expansion on previous research, a question that either hasn't been asked or hasn't been answered successfully that I might be able to say something interesting about, even if I don't ultimately solve it. I'm willing to learn any necessary programming languages/programs/methods/etc to the end of answering this question (or trying to)!

Note: this is for a senior year undergraduate thesis in math / comp sci.

Thanks for any suggestions!

[tarmizi_adam2005]

Hi,

This is why "Literature Review" is an important part in your thesis. Those open problems would be visible to you once you do a very good "literature review/survey".

[one2remember]

Thank you for the advice. Do you know of any good (free) resources I could use to find CS literature (relevant to the topics I mentioned) that I could begin surveying?

[jon.kiparsky]

I don't want to be a downer, but if you don't know the problem space well enough to find a few candidate problems, what are the odds you're ever going to solve a problem that someone hands you?

[tarmizi_adam2005]

Well I don't really know about complexity theory up to an advance level. But, a good start is for you to find a supervisor (academic faculty member) so that you can start do discuss with.

Another way you can do is to find a related bachelors thesis from your seniors. Find a thesis that is related to what you want to do. Read around its abstract and conclusion. If that interests you, read the introduction chapter of that thesis. Also, a thesis usually has a separate chapter on "Future Works". This chapter would be a good start for you.

[ishkabible]

here is a wonderful list filled to the brim with unsolved problems in complexity theory. It is actually a list of unsolved problems in computer science but most of them wind up being in complexity theory. Complexity theory is really really hard and yet hugely important to our understanding. So a lot of people study it and a lot of people just keep asking more questions than we have answers to. Also if you solved one of these problems you would probably solve a lot of the others too! For instance the existence of one way functions is tied with random number generation, encryption, PvsNP and integer factorization.

Another big area nowadays is quantum computing. Can quantum computers solve NP problems efficiently? Most complexity theorists think not.

Here are some really big, and all highly related problems in complexity theory that I have read a tinny bit about:

Is integer factorization NP-complete?
Is Integer factorization a one-way function?
Does P=NP? Most think not (and after you look at it I don't see how you could think otherwise)
Can quantum computers efficiently solve NP-complete problems?
Does P = BPP? This one is a bit split actually. without a clear indication of which way this will go.
Does BPP = BQP? Most think not but there are at least a hefty number of people that think so.

This post has been edited by ishkabible: 25 October 2015 - 02:03 PM

[macosxnerd101]

Anytime you have a problem, placing it in a complexity class is an open problem. If you have a hard problem for a given class, what tools do you have for approximating a solution (such as approximation algorithms for NP-Hard)? How parallelizable is the problem?

These are on top of the obvious difficult problems like P = NP.