What is the oldest open problem in TCS?

Question

This problem is inspired by this MO question, which I thought was very interesting.

What is the oldest open problem in TCS?

Clearly this question needs some clarification.

First, what is TCS? I think the existence of odd perfect numbers is not TCS. I would say that Hilbert's tenth problem is TCS. I think problems like "Can we construct X with a ruler and compass" are also TCS, since they are asking for an algorithm in a restricted model of computation. There may be no rigorous way to define what a TCS problem is, but use your judgment. Perhaps one test is "If this gets solved, would it most likely appear in STOC/FOCS? Would the researcher who solved it most likely be a theoretical computer scientist?"

Second, what is "oldest"? I mean oldest by date. The stated date should also be verifiable, but I don't think this should be too hard.

Third, what is an "open problem"? By "open problem", I mean a problem that was specifically considered open at some time. Perhaps it appeared at the end of a paper in the open problems section, or maybe there is evidence that some people worked on it and failed, or maybe there are incorrect proofs in the literature, which suggest that it has been studied. An example of something that doesn't fit this criteria: "The greeks studied objects X and Y. Z is clearly an intermediate object, surely they wondered if it can be constructed." If there's no literature on Z from that time period, then it is not an open problem from that time period.

Fourth, what do I mean by "problem"? I mean a specific "yes/no" question, and not something like "Characterize all the objects X with property Y", because such questions often do not have a satisfactory answer. Quite often there will be disagreement as to whether the question has been resolved. Let's not get into such questions here. If it is not a yes/no question, but it is clear that it is really open, that's fine too. (In case this isn't clear, by "problem" I mean a formally stated problem. Please do not convert some folk legend about gambling in the 16th century to a question about BPP and PSPACE.)

Lastly, since this is not a big-list question, please post an answer only if you think it is older than the answers already posted (or if you think the answers posted do not satisfy some other condition -- like they are not TCS, or they are not open). This isn't an indiscriminate collection of old open problems.

Answer 1

What is the computational complexity of integer multiplication? Arguably, this question dates back at least to the the 'duplation and mediation' algorithm for integer multiplication described in the Rhind Mathematical Papyrus, which was written circa 1650 BC, but claims to be a copy of a significantly older document.

Admittedly, the Rhind papyrus did not explicitly consider the complexity of is algorithm. So maybe a better answer is What is the complexity of solving systems of linear equations? Research into efficient algorithms for solving linear systems dates back at least to Liu Hui's commentary, published in 263 AD, on The Nine Chapters on the Mathematical Art. Specifically, Liu Hui compares two variants of what is now recognized as Gaussian elimination, and counts the number of arithmetic operations used by each, with the explicit goal of finding the more efficient method.

Both of these questions are still targets of active research.

Answer 2

The search for an efficient algorithm for factoring seems to date back to at least Gauss. Article 329 of Gauss' Disquitiones Arithmeticae (1801) had the following quote (source):

The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic. It has engaged the industry and wisdom of ancient and modern geometers to such an extent that it would be superfluous to discuss the problem at length. ... Further, the dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated.

Of course, it's true that Gauss didn't formally define exactly what he desired out of the factoring algorithm. He did talk in the same article though about the fact that all primality testing algorithms known at that time were very "laborious and prolix".

Answer 3

The following, quoted from

• Goldwasser, S. and Micali, S. 1982. Probabilistic encryption & how to play mental poker keeping secret all partial information. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing (San Francisco, California, United States, May 05 - 07, 1982). STOC '82. ACM, New York, NY, 365-377. DOI= http://doi.acm.org/10.1145/800070.802212

Refers to another problem dating back to Gauss' Disquitiones Arithmeticae (1801):

If the factorization of N is not known and $(\frac{q}{N})=1$, where $(\frac{q}{N})$ denotes the Jacobi symbol, then there is no known procedure for deciding whether q is a quadratic residue mod N. This decision problem is well known to be hard in Number Theory. It is one of the main four algorithmic problems discussed by Gauss in his "Disquisitiones Arithmeticae" (1801). A polynomial solution for it would imply a polynomial solution to other open problems in Number Theory, such as deciding whether a composite N, whose factorization is not known, is the product of 2 or 3 primes; see open problems 9 and 15 in Adleman.

PS: By now, we know two of the four algorithmic problems:

1. Factoring (as mentioned by arnab);
2. Deciding quadratic residousity.

what are the remaining two problems described by Gauss?

Answer 4

In our country's literature, there's a saying, which I literally translate as "The riddle becomes easy when it is solved." Though not a good translation, it refers to the fact that when you have the solution, you can easily verify it; yet before that, the riddle seems very hard.

This refers to the now-famous "FP vs. FNP" problem: If FNP=FP, verification of the answer to the riddle is as easy as finding it. Yet if FNP≠FP, then there exists "riddles" for which finding a solution is much harder than verifying the solution.

I believe this problem is the oldest TCS open problem, yet it's rigorous formulation dates back to just about 30 years ago!

There seems to be a similar (yet somehow different!) proverb in the English language: "It's easy to be wise after the event" or "It's easy to be smart after the fact."

EDIT: "Can we factor numbers in poly-time" is another TCS open-problem, yet I think it is younger than the problem mentioned above.

Here's two list of TCS open-problems on the web:

• http://www.c2.com/cgi/wiki?OpenProblemsInComputerScience
• http://garden.irmacs.sfu.ca/?q=category/theoretical_computer_science

We also have such a list here on CSTheory.

Answer 5

I question your excluding number theory involving questions of whether some number theoretic sets are finite or infinite as part of TCS and would definitely argue otherwise. the greeks questioned whether:

• are there any odd perfect numbers? [possibly considered by euclid]

• are there an infinite number of twin primes?

these can easily be rephrased as computability theory questions based on the strong correspondence between questions about specific TM halting and most number theory questions. in the 1st case build a $TM_x$ that searches for odd perfect numbers, counting upwards and halts if it finds one. in the 2nd case build a machine $TM_y$ that uses a large upper bound in a search of a twin prime found after a prior twin prime pair. does it halt?

so arguably these are two ancient algorithmic problems and the greeks pioneered the earliest TCS mainly in the form of number theory and early number theory problems are just special cases of Turings halting problem, and early circumstantial evidence for its difficulty. and there is a close relation between asking about/finding/searching for proofs and undecidability theory.

arguably new research is showing the collatz conjecture, once considered a number theory curiosity, has deep liinks to computability theory, & may lie right at the boundary between undecidable and decidable problems. also the example you cite of hilberts 10th problem shows a very fundamental link between number theory and TCS.

two other ancient algorithmic questions:

• what is an efficient, or most efficient algorithm for computing gcd, greatest common divisor?

• what is an efficient, or most efficient algorithm for computing primes?

agreed the 2nd question is quite closely related to factoring, but its not quite the same of course. it was considered by eratosthenes' sieve and euclid. of course it was recenttly shown to be in P by AKS, but even then the algorithm is not proven totally optimal.

there is very modern TCS research into euclids gcd algorithm (ie 20th century) that showed that fibonacci numbers give it the worst case performance. [not sure who 1st showed this]

until euclids algorithm is proven optimal, arguably efficient computation of gcd is still open.

Answer 6

Not sure how serious this answer is, but....

It really depends how widely you are willing to define your question.

Surely "can one build an intelligent machine?" is the oldest open question in CS that started computer science, but is probably old by a millinium or two than CS. No? (It is a theory question, since it asks for an answer - not for the machine itself...)

A natural reference to a search for an intelligent machine would be the Golem... http://en.wikipedia.org/wiki/Golem#History

Answer 7

I can answer your question with 100% certainty for a time period. If we consider the period from the seminal paper of Hartmanis and Stearns to any point in the future, the oldest problem in TCS which is still open is:

What is the minimum overhead needed for the simulation of deterministic TMs?

The first answer was $T^{2}(n)$ , where $T(n)$ is the running time of the TM being simulated, with an improvement quickly provided by Hennie and Stearns to $\log T(n)$, which is the best current answer to the best of my knowledge.

This problem is still open and an improvement to it would improve many results, with the most important perhaps being the gap in the deterministic time hierarchy. However, research on the subject suggests that the $\log T(n)$ gap is necessary.