<p><strong>What is the computational complexity of integer multiplication?</strong>  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 <strong>1650 BC</strong>, but claims to be a copy of a significantly older document.</p>

<p>Admittedly, the Rhind papyrus did not explicitly consider the complexity of is algorithm.  So maybe a better answer is <strong>What is the complexity of solving systems of linear equations?</strong>  Research into efficient algorithms for solving linear systems dates back at least to Liu Hui's commentary, published in <strong>263 AD</strong>, on <em>The Nine Chapters on the Mathematical Art</em>.  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.</p>

<p>Both of these questions are still targets of active research.</p>

CC BY-SA 3.0
2015-01-14T16:20:29.077Z
This question has been partially resolved for online integer multiplication. http://arxiv.org/abs/1101.0768
Simd
CC BY-SA 2.5
2010-10-04T06:02:29.623Z
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.
Jeffε
CC BY-SA 2.5
2010-10-04T06:25:06.557Z
"By modern standards of rigor, Euclid was just some handwaving Greek dude": that's my next .sig :)
Suresh Venkat
CC BY-SA 2.5
2010-10-04T12:20:14.420Z
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.
Robin Kothari
CC BY-SA 2.5
2010-10-04T05:59:47.030Z
2010-10-04T05:59:47.030Z
Jeffε
<p>The search for an efficient algorithm for factoring seems to date back to at least Gauss.  Article 329 of Gauss' <em>Disquitiones Arithmeticae</em> (1801) had the following quote (<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.81.407&amp;rep=rep1&amp;type=pdf">source</a>):</p>

<p><code>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.</code></p>

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

CC BY-SA 2.5
2010-10-04T12:22:04.370Z
Very nice quote. It's great how Gauss was clear that the current factoring algorithms were "laborious and prolix"!
Robin Kothari
CC BY-SA 2.5
2010-10-04T01:33:41.913Z
2010-10-04T01:33:41.913Z
arnab
<p>The following, quoted from</p>

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

<p>Refers to another problem dating back to Gauss' Disquitiones Arithmeticae (1801):</p>

<p>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 <strong>four algorithmic problems</strong> 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 <a href="http://dx.doi.org/10.1109/SFCS.1980.28" rel="noreferrer">Adleman</a>.</p>

<p><strong>PS:</strong> By now, we know two of the <em>four algorithmic problems</em>:</p>

<ol>
<li>Factoring (as mentioned by arnab);</li>
<li>Deciding quadratic residousity.</li>
</ol>

<p>what are the remaining two problems described by Gauss?</p>

CC BY-SA 2.5
2010-10-04T02:50:38.813Z
2010-10-06T07:42:42.393Z
2010-10-06T07:42:42.393Z
Sadeq Dousti
<p>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.</p>

<p>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.</p>

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

<p><code>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."</code></p>

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

<p>Here's two list of TCS open-problems on the web:</p>

<ul>
<li><a href="http://www.c2.com/cgi/wiki?OpenProblemsInComputerScience">http://www.c2.com/cgi/wiki?OpenProblemsInComputerScience</a></li>
<li><a href="http://garden.irmacs.sfu.ca/?q=category/theoretical_computer_science">http://garden.irmacs.sfu.ca/?q=category/theoretical_computer_science</a></li>
</ul>

<p>We also have such a list here on CSTheory.</p>

CC BY-SA 3.0
2011-05-08T07:59:06.680Z
I agree with Robin: this is indeed an observation of life which has multiple formulations in computational complexity, but it does not refer to **FP** versus **FNP**, nor to any prototypes of these classes, nor is it even a proposal to solve some sort of problem (it doesn't *ask* whether it is harder to solve riddles than to verify them).
Niel de Beaudrap
CC BY-SA 2.5
2010-10-03T15:31:19.300Z
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.
Robin Kothari
CC BY-SA 2.5
2010-10-03T19:01:29.223Z
@Robin: You may not ask for old, formalized TCS open problems, if there were not even computers in the old ages! :)
Sadeq Dousti
CC BY-SA 2.5
2010-10-03T20:32:12.917Z
@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.
Robin Kothari
CC BY-SA 2.5
2010-10-03T21:18:27.343Z
What year was this problem formulated in?
Dave Clarke
CC BY-SA 2.5
2010-10-03T21:28:54.920Z
@Dave: As I said, I think it's as old as the first "riddle." Yet it's been formulated rigorously 30 (or maybe 40) years ago.
Sadeq Dousti
CC BY-SA 2.5
2010-10-03T22:08:57.723Z
@Robin: People often believe that solving problems from scratch is harder than verifying the solution. I don't call this "a computational question in disguise."
Sadeq Dousti
CC BY-SA 2.5
2010-10-03T22:20:04.000Z
@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.
Robin Kothari
CC BY-SA 2.5
2010-10-04T02:35:35.667Z
@Robin: How about stating it as "search using nondeterministic vs. deterministic machines, given limited resources"? While a common belief, there are still people who doubt it. (see http://www.cs.umd.edu/~gasarch/papers/poll.pdf)
Sadeq Dousti
CC BY-SA 2.5
2010-10-04T03:13:15.570Z
@Sadeq: I see what you're saying, but I specifically restricted to rigorous formulations to avoid such problems. I want to know the oldest formally stated open problem.
Robin Kothari
CC BY-SA 2.5
2010-10-03T09:21:18.517Z
2010-10-03T09:29:25.197Z
2010-10-03T09:29:25.197Z
Sadeq Dousti
<p>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:</p>

<ul>
<li><p>are there any odd perfect numbers? [possibly considered by euclid]</p></li>
<li><p>are there an infinite number of twin primes?</p></li>
</ul>

<p>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?</p>

<p>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.</p>

<p>arguably new research is showing  the collatz conjecture, once considered a number theory curiosity, has deep liinks to computability theory,  &amp; <a href="https://cstheory.stackexchange.com/a/11614/7884">may lie right at the boundary</a> between undecidable and decidable problems. also the example you cite of hilberts 10th problem shows a very  fundamental link between number  theory and TCS.</p>

<p>two other ancient algorithmic questions:</p>

<ul>
<li><p>what is an efficient, or most efficient algorithm for computing gcd, greatest common divisor?</p></li>
<li><p>what is an efficient, or most efficient algorithm for computing primes?</p></li>
</ul>

<p>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.</p>

<p>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]</p>

<p>until euclids algorithm is proven optimal, arguably efficient computation of gcd is still open.</p>

CC BY-SA 3.0
2012-06-02T18:28:19.020Z
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
Sasho Nikolov
CC BY-SA 3.0
2012-06-04T12:18:57.940Z
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.
cody
CC BY-SA 3.0
2012-06-02T16:57:47.993Z
2012-06-02T16:57:47.993Z
2017-04-13T12:32:28.743Z
vzn
<p>Not sure how serious this answer is, but....</p>

<p>It really depends how widely you are willing to define your question.</p>

<p>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...)</p>

<p>A natural reference to a search for an intelligent machine would be the Golem... 
<a href="http://en.wikipedia.org/wiki/Golem#History" rel="nofollow">http://en.wikipedia.org/wiki/Golem#History</a></p>

CC BY-SA 3.0
2012-06-03T02:51:56.697Z
2012-06-03T02:51:56.697Z
Sariel Har-Peled
<p>I can answer your question with 100% certainty for a time period. If we consider the period from <a href="http://www.ams.org/journals/tran/1965-117-00/S0002-9947-1965-0170805-7/S0002-9947-1965-0170805-7.pdf" rel="nofollow">the seminal paper of Hartmanis and Stearns</a> to any point in the future, the oldest problem in TCS which is still open is:</p>

<blockquote>
  <p>What is the minimum overhead needed for the simulation of deterministic TMs?</p>
</blockquote>

<p>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 <a href="http://dl.acm.org/citation.cfm?id=321362" rel="nofollow">Hennie and Stearns</a> to $\log T(n)$, which is the best current answer to the best of my knowledge.</p>

<p>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.</p>

CC BY-SA 3.0
2012-06-03T15:57:24.450Z
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"
Sasho Nikolov
CC BY-SA 3.0
2012-06-04T07:45:37.260Z
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.
chazisop
CC BY-SA 3.0
2012-06-04T09:02:19.367Z
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?
funkstar
CC BY-SA 3.0
2012-06-04T19:34:22.470Z
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.
chazisop
CC BY-SA 3.0
2012-06-04T21:42:11.260Z
AFAIK people don't consider it an important/interesting problem. Do you know anyone who has seriously worked on improving it in the last few years?
Kaveh
CC BY-SA 3.0
2012-06-06T12:00:23.363Z
If I remember correctly, some special cases were considered in the early 90's. Although for me the importance of a problem does not always correlate with attention from the community, the main criterion here was the "age" of the problem as well as if it's still open. Actually, I would argue that this is an important problem, since improving it affects a vast amount of results, although it is considered "closed but not proven" by most people, who would rather work on other, fresher areas.
chazisop
CC BY-SA 3.0
2012-06-06T17:01:23.917Z
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.)
funkstar
CC BY-SA 3.0
2012-06-03T06:34:37.317Z
2012-06-04T07:44:17.307Z
2012-06-04T07:44:17.307Z
chazisop
<p>This problem is inspired by <a href="https://mathoverflow.net/questions/27075/what-is-the-oldest-open-problem-in-mathematics">this MO question</a>, which I thought was very interesting.</p>

<blockquote>
  <p>What is the oldest open problem in TCS? </p>
</blockquote>

<p>Clearly this question needs some clarification. </p>

<p>First, what is TCS?  I think the existence of odd perfect numbers is not TCS. I would say that <a href="http://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem" rel="nofollow noreferrer">Hilbert's tenth problem</a> 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?"</p>

<p>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. </p>

<p>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.</p>

<p>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.)</p>

<p>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. </p>

CC BY-SA 3.0
2012-06-03T06:16:04.360Z
@SarielHar-Peled I have a semi-formal proof that proving the inexistence of an all-powerful God (like most of them?) is impossible. To prevent the flame war, this is a mathematical statement and not a religious one. The proof idea is this: Since we are living in a universe manipulated by an entity that can alter it to its liking, any fact that disproves its existence could have been "planted" by it. This includes classic arguments like the "heavy rock", since this entity makes the rules of the game and is not constrained by them. Can similar historic arguments be considered TCS?
chazisop
CC BY-SA 3.0
2012-06-03T06:19:14.090Z
A famous example would be Pascal's Wager (see http://en.wikipedia.org/wiki/Pascal%27s_Wager ). As mentioned "Historically, Pascal's Wager was groundbreaking because it charted new territory in probability theory, marked the first formal use of decision theory"
chazisop
CC BY-SA 2.5
2010-10-03T05:21:01.583Z
Is there a fast procedure to factor integers?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-10-03T05:28:07.057Z
Since you allow ruler and compass constructions as TCS, would some of the open problems on Fermat primes qualify? The regular n-gon is constructible iff n is a product of a power of 2 and any number of distinct Fermat primes. The powers of 2 correspond to trivial doubling symmetries, so the open problem of whether there are infinitely many Fermat primes is here asking whether there are infinitely many regular n-gons that are constructible yet essentially different (not just doublings). I mention this problem because it sure doesn't feel like TCS to me, though it seems to fit your definition.
Per Vognsen
CC BY-SA 2.5
2010-10-03T05:30:47.050Z
"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 ;-))
Daniel Apon
CC BY-SA 2.5
2010-10-03T06:59:59.533Z
Is there a god? Could be a TCS problem if it can be solved by computers.
Sariel Har-Peled
CC BY-SA 2.5
2010-10-03T07:08:12.017Z
@Daniel, 'what's the best way to cut a cake' is an actual TCS question !!!
Suresh Venkat
CC BY-SA 2.5
2010-10-03T10:16:19.740Z
Nice question, but I think it should be community wiki.
Dave Clarke
CC BY-SA 2.5
2010-10-03T15:25:22.693Z
@Per: Yes, it doesn't feel like a TCS question. That's why I said use your judgment.. I don't know how to make that formal.  @Sariel: I'm not so sure about that. A physics question perhaps, but not TCS, in my opinion. :-) @supercooldave: Yeah, I thought about that, and hesitated, due to the "don't-CW-too-quickly" rule, and the fact that this question was not CW on MO.
Robin Kothari
CC BY-SA 2.5
2010-10-03T15:52:27.167Z
Voted to close for “subjective and argumentative.”  As stated in the question, it is unclear whether a problem is in theoretical computer science or not.  Also it is often unclear when a problem was stated with enough formulation.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-03T16:26:53.310Z
@Tsuyoshi: I think we should relax our requirements for soft questions and CW questions. But this should be discussed on meta. I'd also like to point out that the question was not closed on MO and it got 35+ votes despite not being a CW question.
Robin Kothari
CC BY-SA 2.5
2010-10-03T21:15:43.013Z
I'm now inclined to think that this question is of little merit (except for votes). I agree with the assessment that it is subjective and argumentative, as it may come down to judging where the boundary of TCS lies. Are open problems in model theory on the table? Of recursion theory? Of logic? Of (some branches of) mathematics? What about cooking? Or religion?
Dave Clarke
CC BY-SA 2.5
2010-10-03T21:33:56.640Z
#offtopic: nice to see that supercooldave now has a name :)
Suresh Venkat
CC BY-SA 2.5
2010-10-03T21:34:34.407Z
#offtopic reply: I'm phasing it in gradually.
Dave Clarke
CC BY-SA 2.5
2010-10-03T22:21:52.077Z
#offtopic @Dave: your website link seems to be down.
András Salamon
CC BY-SA 2.5
2010-10-04T13:12:00.663Z
I found a book titled "A History of Algorithms: From the Pebble to the Microchip" (http://www.amazon.com/dp/3540633693). It might be helpful in finding a decent history on (new and old) algorithms.
Sadeq Dousti
<soft-question><open-problem><ho.history-overview>
What is the oldest open problem in TCS?
Robin Kothari
# What is the oldest open problem in TCS?

(Asked by: username_0 on 2010-10-03)

This problem is inspired by [this MO question](https://mathoverflow.net/questions/27075/what-is-the-oldest-open-problem-in-mathematics), 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](http://en.wikipedia.org/wiki/Hilbert%27s_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.

**Tags:** soft-question, open-problem, ho.history-overview

> **Comments:**
> **username_2**: Is there a fast procedure to factor integers?  
> **username_3**: Since you allow ruler and compass constructions as TCS, would some of the open problems on Fermat primes qualify? The regular n-gon is constructible iff n is a product of a power of 2 and any number of distinct Fermat primes. The powers of 2 correspond to trivial doubling symmetries, so the open problem of whether there are infinitely many Fermat primes is here asking whether there are infinitely many regular n-gons that are constructible yet essentially different (not just doublings). I mention this problem because it sure doesn't feel like TCS to me, though it seems to fit your definition.  
> **username_4**: "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 ;-))  
> **username_5**: Is there a god? Could be a TCS problem if it can be solved by computers.  
> **username_6**: @Daniel, 'what's the best way to cut a cake' is an actual TCS question !!!  
> **username_7**: Nice question, but I think it should be community wiki.  
> **username_0**: @Per: Yes, it doesn't feel like a TCS question. That's why I said use your judgment.. I don't know how to make that formal.  @Sariel: I'm not so sure about that. A physics question perhaps, but not TCS, in my opinion. :-) @supercooldave: Yeah, I thought about that, and hesitated, due to the "don't-CW-too-quickly" rule, and the fact that this question was not CW on MO.  
> **username_8**: Voted to close for “subjective and argumentative.”  As stated in the question, it is unclear whether a problem is in theoretical computer science or not.  Also it is often unclear when a problem was stated with enough formulation.  
> **username_0**: @Tsuyoshi: I think we should relax our requirements for soft questions and CW questions. But this should be discussed on meta. I'd also like to point out that the question was not closed on MO and it got 35+ votes despite not being a CW question.  
> **username_7**: I'm now inclined to think that this question is of little merit (except for votes). I agree with the assessment that it is subjective and argumentative, as it may come down to judging where the boundary of TCS lies. Are open problems in model theory on the table? Of recursion theory? Of logic? Of (some branches of) mathematics? What about cooking? Or religion?  
> **username_6**: #offtopic: nice to see that supercooldave now has a name :)  
> **username_7**: #offtopic reply: I'm phasing it in gradually.  
> **username_9**: #offtopic @Dave: your website link seems to be down.  
> **username_10**: I found a book titled "A History of Algorithms: From the Pebble to the Microchip" (http://www.amazon.com/dp/3540633693). It might be helpful in finding a decent history on (new and old) algorithms.  
> **username_1**: @SarielHar-Peled I have a semi-formal proof that proving the inexistence of an all-powerful God (like most of them?) is impossible. To prevent the flame war, this is a mathematical statement and not a religious one. The proof idea is this: Since we are living in a universe manipulated by an entity that can alter it to its liking, any fact that disproves its existence could have been "planted" by it. This includes classic arguments like the "heavy rock", since this entity makes the rules of the game and is not constrained by them. Can similar historic arguments be considered TCS?  
> **username_1**: A famous example would be Pascal's Wager (see http://en.wikipedia.org/wiki/Pascal%27s_Wager ). As mentioned "Historically, Pascal's Wager was groundbreaking because it charted new territory in probability theory, marked the first formal use of decision theory"  

---

## 7 answers

### Answer by username_11 on 2010-10-04. Score: 41

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

> **Comments:**
> **username_11**: 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.  
> **username_6**: "By modern standards of rigor, Euclid was just some handwaving Greek dude": that's my next .sig :)  
> **username_0**: 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.  
> **username_12**: This question has been partially resolved for online integer multiplication. http://arxiv.org/abs/1101.0768  

---

### Answer by username_13 on 2010-10-04. Score: 24

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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.81.407&rep=rep1&type=pdf)):

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

> **Comments:**
> **username_0**: Very nice quote. It's great how Gauss was clear that the current factoring algorithms were "laborious and prolix"!  

---

### Answer by username_10 on 2010-10-04. Score: 11

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](http://dx.doi.org/10.1109/SFCS.1980.28).

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

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

what are the remaining two problems described by Gauss?


---

### Answer by username_10 on 2010-10-03. Score: 9

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.

> **Comments:**
> **username_0**: 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.  
> **username_10**: @Robin: You may not ask for old, formalized TCS open problems, if there were not even computers in the old ages! :)  
> **username_0**: @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.  
> **username_7**: What year was this problem formulated in?  
> **username_10**: @Dave: As I said, I think it's as old as the first "riddle." Yet it's been formulated rigorously 30 (or maybe 40) years ago.  
> **username_10**: @Robin: People often believe that solving problems from scratch is harder than verifying the solution. I don't call this "a computational question in disguise."  
> **username_0**: @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.  
> **username_10**: @Robin: How about stating it as "search using nondeterministic vs. deterministic machines, given limited resources"? While a common belief, there are still people who doubt it. (see http://www.cs.umd.edu/~gasarch/papers/poll.pdf)  
> **username_0**: @Sadeq: I see what you're saying, but I specifically restricted to rigorous formulations to avoid such problems. I want to know the oldest formally stated open problem.  
> **username_14**: I agree with Robin: this is indeed an observation of life which has multiple formulations in computational complexity, but it does not refer to **FP** versus **FNP**, nor to any prototypes of these classes, nor is it even a proposal to solve some sort of problem (it doesn't *ask* whether it is harder to solve riddles than to verify them).  

---

### Answer by username_15 on 2012-06-02. Score: 3

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](https://cstheory.stackexchange.com/a/11614/7884) 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.

> **Comments:**
> **username_16**: 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  
> **username_17**: 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.  

---

### Answer by username_5 on 2012-06-03. Score: 2

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 by username_1 on 2012-06-03. Score: 1

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](http://www.ams.org/journals/tran/1965-117-00/S0002-9947-1965-0170805-7/S0002-9947-1965-0170805-7.pdf) 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](http://dl.acm.org/citation.cfm?id=321362) 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.

> **Comments:**
> **username_16**: 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"  
> **username_1**: 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.  
> **username_18**: 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?  
> **username_1**: 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.  
> **username_19**: AFAIK people don't consider it an important/interesting problem. Do you know anyone who has seriously worked on improving it in the last few years?  
> **username_1**: If I remember correctly, some special cases were considered in the early 90's. Although for me the importance of a problem does not always correlate with attention from the community, the main criterion here was the "age" of the problem as well as if it's still open. Actually, I would argue that this is an important problem, since improving it affects a vast amount of results, although it is considered "closed but not proven" by most people, who would rather work on other, fresher areas.  
> **username_18**: 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.)  

---

