Open Problems in Theoretical CS Accessible to Amateurs

Hello,

I was wondering if anyone knows if there any open problems in
theoretical computer science that are thought to be accessible to
amateurs, in the sense that there is a realistic chance that an
amateur might solve such a problem. I previously worked on P vs. NP
for a long time, and while I am a mathematics major in college, it's
pretty clear that I would need to go to graduate school to even
understand how to approach the problem intelligently. I'm wondering,
essentially, if there are any "easier" problems that a student such as
myself might be able to solve.

I understand that my question might be ridiculous, because any open
problem has probably already been attacked by professional
mathematicians without success. However, I was thinking/hoping that
there might be some problem that is thought to be solvable but that
would require either some huge amount of work or some atypical (but
perhaps non-advanced) flash of insight to solve it, or perhaps some
problem that is obscure and hasn't been seriously considered by many
mathematicians.

I apologize in advance if any of my assumptions are naive, and I
appreciate any information anyone can provide.

Thanks,
Phil

In article
<59074ab7-a187-4146-a626-bef37d046463@l42g2000hsc.googlegroups.com>,
cplxphil@gmail.com wrote:

> Hello,
>
> I was wondering if anyone knows if there any open problems in
> theoretical computer science that are thought to be accessible to
> amateurs, in the sense that there is a realistic chance that an
> amateur might solve such a problem. I previously worked on P vs. NP
> for a long time, and while I am a mathematics major in college, it's
> pretty clear that I would need to go to graduate school to even
> understand how to approach the problem intelligently. I'm wondering,
> essentially, if there are any "easier" problems that a student such as
> myself might be able to solve.

Maybe the Collatz conjecture:
<http://en.wikipedia.org/wiki/Collatz_conjecture>.

> I understand that my question might be ridiculous, because any open
> problem has probably already been attacked by professional
> mathematicians without success. However, I was thinking/hoping that
> there might be some problem that is thought to be solvable but that
> would require either some huge amount of work or some atypical (but
> perhaps non-advanced) flash of insight to solve it, or perhaps some
> problem that is obscure and hasn't been seriously considered by many
> mathematicians.
>
> I apologize in advance if any of my assumptions are naive, and I
> appreciate any information anyone can provide.

--
---------------------------
| BBB b \ Barbara at LivingHistory stop co stop uk
| B B aa rrr b |
| BBB a a r bbb | Quidquid latine dictum sit,
| B B a a r b b | altum viditur.
| BBB aa a r bbb |
-----------------------------

On Sep 6, 5:24*pm, cplxp...@gmail.com wrote:
> Hello,
>
> I was wondering if anyone knows if there any open problems in
> theoretical computer science that are thought to be accessible to
> amateurs, in the sense that there is a realistic chance that an
> amateur might solve such a problem.

For a realistic chance, you might take variations of open problems and
solve those. Even partial results on open problems can be useful.

Using "open problems computer science" as a search term will get
you many possibilities, some of which are accessible. One set of
problems I would like to see solved is based on a certain notion of
complexity. Perhaps you would like to try it.

Build a collection of terms recursively as follows: the single
variable
x is a term, if s and t are terms then so are (s+t) and (s*t). The
complexity of a term is the number of occurrences of x in it.

Now interpret x as the number 1, + as addition and * as minus,
and define the 1-complexity of a positive integer n as the smallest
number c(n) which is the complexity of a term s such that, after
doing the interpretation on s, evaluates to n.

(Colloquially, how many 1's does it take to build a number n out
of only 1's , additions, and multiplications, and nothing like 11's or
concatenation allowed?)

The problems are based on computing c(n) efficiently. Logarithmic
approximations are quickly found, but how good an algorithm can
one make to compute c(n) exactly?

As a check, c(7)=6, c(22)=10, and c(23)=11, and a nice upper
bound for c(n) is 3lg(n), where lg(n) is log base 2 of n, or about
4.8lgg(n), where lgg(n) is log base 3 of n. I suspect, and would
like to see proved, that 4lgg(n) is a better upper bound for c(n).
If this were true, then I could improve on my algorithm to compute
c(n). If you are interested in this problem, I can give more
conjectures on it, and references to variations on it.

Gerhard Paseman, 2008.09.06

On Sep 6, 10:09*pm, grpad...@gmail.com wrote:
>
> Now interpret x as the number 1, + as addition and * as minus,

sorry, my fingers said minus, but my head says multiplication.

Gerhard Paseman, 2008.09.06

Dnia 07-09-2008 o 02:24:17 <cplxphil@gmail.com> napisa³(a):

> I understand that my question might be ridiculous, because any open
> problem has probably already been attacked by professional
> mathematicians without success. However, I was thinking/hoping that
> there might be some problem that is thought to be solvable but that
> would require either some huge amount of work or some atypical (but
> perhaps non-advanced) flash of insight to solve it, or perhaps some
> problem that is obscure and hasn't been seriously considered by many
> mathematicians.

http://tlca.di.unito.it/opltlca/

Some of these problems are believed to be moderately easy (suitable for a
Master thesis).


--
Micha³ Przyby³ek

In article <59074ab7-a187-4146-a626-bef37d046463@l42g2000hsc.googlegroups.com>,
<cplxphil@gmail.com> wrote:
>I was wondering if anyone knows if there any open problems in
>theoretical computer science that are thought to be accessible to
>amateurs, in the sense that there is a realistic chance that an
>amateur might solve such a problem.

What you might want to do is to apply to a summer REU. People who run
such programs spend a lot of effort finding problems that are suitable
for undergraduates. Here's one list:

http://www.ams.org/employment/reu.html
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences

Thanks all for the suggestions. I looked extensively at the Collatz
conjecture. It looks very interesting, and very much "my type of
problem," although I quickly became aware that it would be very
difficult to prove.

I'll look at the sites you all recommended over the next several days,
and also at the problem Gerhard suggested.

I would have loved to do an REU, but unfortunately I am graduating
this December. I will still look at the list you provided and see if
there are any interesting problems listed.

Thanks again everyone!

-Phil

In article <66b4dc65-6870-46a5-9f05-ada1802c1a88@p25g2000hsf.googlegroups.com>,
<cplxphil@gmail.com> wrote:
>I would have loved to do an REU, but unfortunately I am graduating
>this December. I will still look at the list you provided and see if
>there are any interesting problems listed.

The one REU-like program that I know of for post-grads is the Graduate
Mathematics Program at the NSA.

http://www.nsa.gov/careers/students_1.cfm

Unfortunately you have to be a U.S. citizen and get a security clearance,
but if that is not an obstacle for you, you still have time to apply (the
deadline is October 15 for the summer of 2009).
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences