38
$\begingroup$

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.

$\endgroup$
16
  • 15
    $\begingroup$ "What's the best way to cook meat?" Under a campfire model of computation, what's the best algorithm for preparing food? -- relevant many thousands of years ago, still relevant now! Plus there's a great deal of literature on the problem! (Sorry, I couldn't resist ;-)) $\endgroup$ Oct 3, 2010 at 5:30
  • 3
    $\begingroup$ Is there a god? Could be a TCS problem if it can be solved by computers. $\endgroup$ Oct 3, 2010 at 6:59
  • 10
    $\begingroup$ @Daniel, 'what's the best way to cut a cake' is an actual TCS question !!! $\endgroup$ Oct 3, 2010 at 7:08
  • 3
    $\begingroup$ #offtopic: nice to see that supercooldave now has a name :) $\endgroup$ Oct 3, 2010 at 21:33
  • 5
    $\begingroup$ I found a book titled "A History of Algorithms: From the Pebble to the Microchip" (amazon.com/dp/3540633693). It might be helpful in finding a decent history on (new and old) algorithms. $\endgroup$ Oct 4, 2010 at 13:12

7 Answers 7

41
$\begingroup$

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.

$\endgroup$
4
  • 11
    $\begingroup$ Unlike Robin, I don't think it's reasonable to insist on the question having been posed in its modern form. That's like holding historical proofs to contemporary standards of rigor. By that standard, axiomatic geometry started with Klein, and Euclid was just some hand-waving Greek dude. $\endgroup$
    – Jeffε
    Oct 4, 2010 at 6:02
  • 7
    $\begingroup$ "By modern standards of rigor, Euclid was just some handwaving Greek dude": that's my next .sig :) $\endgroup$ Oct 4, 2010 at 6:25
  • 3
    $\begingroup$ I think such examples are fine. What I wanted to avoid is what happened on math overflow: There was an argument about whether the Greeks considered some problem just because they had studied some related problem. The other thing I want to avoid is philosophical questions like "Is the universe deterministic" being converted into the P versus BPP problem. You've given a specific problem which was considered as a computational problem by the people who posed it, and that's perfectly acceptable. $\endgroup$ Oct 4, 2010 at 12:20
  • $\begingroup$ This question has been partially resolved for online integer multiplication. arxiv.org/abs/1101.0768 $\endgroup$
    – Simd
    Jan 14, 2015 at 16:20
24
$\begingroup$

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".

$\endgroup$
1
  • 2
    $\begingroup$ Very nice quote. It's great how Gauss was clear that the current factoring algorithms were "laborious and prolix"! $\endgroup$ Oct 4, 2010 at 12:22
11
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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:

We also have such a list here on CSTheory.

$\endgroup$
10
  • 1
    $\begingroup$ Since I'm restricting it to rigorous formulations of problems, I would guess that the question of factoring and FP=FNP can only be formalized once we have Turing machines, and polynomial time, etc. $\endgroup$ Oct 3, 2010 at 15:31
  • $\begingroup$ @Robin: You may not ask for old, formalized TCS open problems, if there were not even computers in the old ages! :) $\endgroup$ Oct 3, 2010 at 19:01
  • 1
    $\begingroup$ @Sadeq: I don't mind if the oldest question turns out to be a question asked in 1922. I insist on rigorously stated questions because otherwise people will quote 4000-year-old texts claiming that some sentence about the universe was a computational question in disguise. $\endgroup$ Oct 3, 2010 at 20:32
  • $\begingroup$ What year was this problem formulated in? $\endgroup$ Oct 3, 2010 at 21:18
  • 3
    $\begingroup$ @Sadeq: True, but that's not the P versus NP question unless someone formalizes the model, etc. I mean it could equally well represent some other question (say L versus NL, or P/poly versus NP/poly, or some question in a different field). Secondly, that's a commonly held belief, not something considered to be an open problem. It's not something that requires proof, in its original formulation: it's just an observation about life. $\endgroup$ Oct 3, 2010 at 22:20
3
$\begingroup$

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.

$\endgroup$
2
  • 8
    $\begingroup$ i disagree with most of what you say (the fact that you can construct all kinds of Turing machines that halt if some conjectured objects exist does not make these existence problems computability questions). but at the end you have a good point: deterministically generating a prime in some range is a reasonable modern version of the old quest to find a "formula for primes". i would upvote if you write a focused answer along these lines $\endgroup$ Jun 2, 2012 at 18:28
  • 1
    $\begingroup$ I agree with the above comment: the Poincare conjecture can be formulated as a halting problem for Turing machines as well, but no progress has been made using techniques specifically from the CS community. The same can be said for such number theoretical problems, computationally relevant as they may be. $\endgroup$
    – cody
    Jun 4, 2012 at 12:18
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ these two statements seem contradictory to me: "This problem is still open" and "research on the subject shows that the $\log T(n)$ gap is necessary" $\endgroup$ Jun 3, 2012 at 15:57
  • 1
    $\begingroup$ Ah thank you @SashoNikolov . A really bad choice of words. Corrected it to "suggests" , which is true, since the problem is really open. It's like $\mathbb{P}$ vs $\mathbb{NP}$ problem which is of course open, but most believe the two classes are not equal. $\endgroup$
    – chazisop
    Jun 4, 2012 at 7:45
  • 1
    $\begingroup$ This could use some clarification, for the benefit of those who do not know those papers in detail: What type of TM is being simulated? What type of machine is doing the simulation? $\endgroup$
    – funkstar
    Jun 4, 2012 at 9:02
  • $\begingroup$ I don't believe a clarification is necessary. That the model being used in the first paper is the multitape TM is a well known fact, since it contains some of the core definitions of TCS, plus it is explicitly mentioned in the title of the Hennie and Stearns paper. $\endgroup$
    – chazisop
    Jun 4, 2012 at 19:34
  • 1
    $\begingroup$ Your formulation of the open question is still too vague, in my opinion. Even though it is well known in the ToC community that Hartmanis, Hennie and Stearns work with multitape TMs, that merely makes your answer unhelpful to those in the many other fields of TCS. You should consider at least adding the qualifier "multitape" to the question. (And even then, you have the problem that Hartmanis and Stearns' simulation uses a 1-tape TM, whereas Hennie and Stearns' simulation uses a 2-tape TM.) $\endgroup$
    – funkstar
    Jun 6, 2012 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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