Questions tagged [ho.history-overview]
The history behind the topics: where their name comes from, who discovered them, when they were first proved, how they evolved during the years.
87 questions
18
votes
6
answers
877
views
When have we found better bounds for known algorithms?
Are there interesting instances of algorithms that have been published with proven bounds, and where strictly better bounds have later been published? Not better algorithms with better bounds - ...
- 10.9k
64
votes
12
answers
5k
views
If you could rename dynamic programming...
If you could rename dynamic programming, what would you call it?
- 244
3
votes
2
answers
365
views
What are some "who ordered that?" moments in theoretical computer science?
I was recently listening to Sean Carroll's interview with Scott Aaronson, and the two of them briefly talked about surprises in their respective fields (theoretical and particle physics, and ...
- 6,795
11
votes
2
answers
405
views
What are pertinent references to cite on Scott domains?
Scott domains are often presented as having been introduced in 1969. However, the first (but numerous!) papers are from the 1970s, so it is not easy to know what the pertinent references are. My two ...
- 509
5
votes
1
answer
313
views
Problems complete for non-deterministic PSPACE
Savitch's theorem, i.e. the fact that $NSPACE(f(n)^2) \subseteq DSPACE(f(n)^2)$ implies PSPACE = NPSPACE.
Using the idea of Savitch, Sipser proves in his lectures that TQBF is PSPACE-complete.
What ...
- 6,795
27
votes
2
answers
2k
views
Why are Ramanujan graphs named after Ramanujan?
I recently taught expanders, and introduced the notion of Ramanujan graphs.
Michael Forbes asked why they are called this way, and I had to admit I don't know.
Anyone?
- 29.5k
10
votes
0
answers
247
views
True origin story of linear logic?
When I was a master's student in Paris I was exposed to the following standard narrative: "J.-Y. Girard invented coherence spaces, then he noticed the decomposition $A \to B~=~!A \multimap B$ and ...
3
votes
0
answers
125
views
Is there a name for the class of languages based on reversible circuits, as studied by the physicists of the late 70's/early 80's?
I'm interested in the (pre)history of quantum computing, especially in light of the work of physicists and engineers who studied reversible computing in the 60's through the late 70's/early 80's. ...
- 1,145
19
votes
0
answers
831
views
Why is the Pumping Lemma sometimes called Bar-Hillel's Lemma?
There are several papers in the literature that refer to the Pumping Lemma for context free languages as Bar-Hillel's Lemma (for example, here, here, and on the Wikipedia page). However, the first ...
- 6,795
4
votes
1
answer
203
views
Is Barbara Liskov's claim that CLU was the first implemented language to provide linguistic support for data abstraction accurate?
According to this paper by Barbara Liskov, CLU was "The first implemented programming language to provide direct linguistic support for data abstraction".
She then defines "data ...
- 186
4
votes
0
answers
77
views
When was the dynamic array first used as an example for amortized analysis?
I'm writing a report on amortized analysis, and I'm using the example of a dynamic array to explain each method. I think it would be nice to add a reference to when this example was first used, as it ...
- 6,795
3
votes
1
answer
435
views
Are there two definitions of Cobham's thesis?
In wikipedia, Cobham's thesis (or Cobham-Edmonds thesis) states:
computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time
So ...
10
votes
0
answers
293
views
Where is Yao's original proof that distinguishers imply next-bit-predictors?
In the theory of pseudorandomness, there is a well-known lemma that says roughly the following. Let $X$ be a probability distribution over $\{0, 1\}^n$. Suppose there is an efficient algorithm that ...
- 12.4k
2
votes
0
answers
89
views
When did self-balancing binary search trees become known outside the soviet union?
According to wikipedia, the AVL tree was first published in 1962 by Soviet scientists Adelson-Velsky and Landis. The earliest self-balancing binary search tree I can find by a non-soviet block ...
- 1,073
33
votes
12
answers
5k
views
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
This is somewhat of a meta-cstheory question, and is more historical in nature. What are some good examples of problems for which the literature followed the develpment below:
The original algorithms,...
- 101
11
votes
1
answer
305
views
When was co-NP introduced for the first time?
My best finding is Pratt's 1975 article. Is there any earlier mention of co-NP?
- 6,795
2
votes
1
answer
302
views
Who proved that a triangulation is 3-colourable implies its dual is bipartite
Let $G$ be a maximal planar graph (also called a triangulation); i.e, $G$ is a planar graph every face of which is a triangle. It is well known that the following three statements are equivalent:
(i) $...
- 1,869
9
votes
3
answers
2k
views
Are there any intersections between Theory A and Theory B?
In the following two questions Origins and applications of Theory A vs Theory B? and Solid applications of category theory in TCS?, many people shared their knowledge and opinions about the division ...
- 38.5k
3
votes
1
answer
1k
views
Are Turing machines still useful as model of computation?
Often when I hear "Turing machine," my mind's eye pictures a quaint infinite ticker-tape with a small little machine writing and erasing $0$'s and $1$'s.
But when I'm forced to think about a Turing ...
- 2,962
5
votes
0
answers
161
views
Why is the Toffoli Gate named after Toffoli?
I was reading the following paper:
Rolf Landauer, Irreversibility and Heat Generation in the Computing Process, IBM Journal of Research and Development, Volume 5, Issue 3, July 1961.
On page 4, ...
71
votes
5
answers
7k
views
The origin of the notion of treewidth
My question today is (as usual) a bit silly; but I would request you to kindly consider it.
I wanted to know about the genesis and/or motivation behind the treewidth concept. I sure understand that ...
- 359
17
votes
0
answers
770
views
Did von Neumann answer to Gödel's letter?
On 20 March 1956, Kurt Gödel wrote a famous letter to John von Neumann, in which he formulated the P versus NP question.
Here is a link to that letter: [pdf of letter]
I cant seem to find John von ...
- 5,792
9
votes
1
answer
269
views
System F and System T names
Does anyone know where do the names System "F" and System "T" comes from? I am not asking who introduced those names (Girard System F, and Gödel System T), but what the "F" and the "T" means.
- 32.9k
1
vote
1
answer
85
views
Searching for the original definition of online algorithms
I'm currently searching for the original formal definition of online algorithms. The earliest mentions of online algorithms that I found are from the mid 80s. But none of these papers seem to be the ...
- 1,671
7
votes
0
answers
338
views
reference clarification: Whitney's theorem on unique embeddability of 3-connected planar graphs?
This is a question about the correct reference for a result that seems to appear frequently in the literature on planar graph isomorphism. In "A $V \log V$ Algorithm for Isomorphism of Triconnected ...
- 4,831
95
votes
7
answers
31k
views
What is the contribution of lambda calculus to the field of theory of computation?
I'm just reading up on lambda calculus to "get to know it". I see it as an alternate form of computation as opposed to the Turing Machine. It's an interesting way of doing things with functions/...
- 3,103
42
votes
1
answer
661
views
Does Rabin/Yao exist (at least in a form that can be cited)?
In Andrew Chi-Chih Yao's classic 1979 paper he references "M. O. Rabin and A. C. Yao, in preparation". This is for the result that the bounded-error communication complexity of the equality function ...
- 19.2k
8
votes
1
answer
262
views
Was counting complexity first introduced by Valiant in 1979?
Was #P first introduced in [1]?
[1] Valiant, Leslie G. "The complexity of computing the permanent."
Theoretical computer science 8.2 (1979): 189-201.
- 184
12
votes
1
answer
294
views
Entscheidungsproblem vs. Unvollständigkeitssatz (soft question)
The first term is used by Hilbert in his 1928 work, but in Gödel's later work, the same thing is referred to as Unvollständigkeitssatz ("incompleteness theorem"). For today's German CS researchers, it ...
- 4,765
3
votes
0
answers
247
views
Providence of pumping lemmas for regular languages
I'm looking to track down who discovered the following pumping lemmas for regular languages.
(where $p$ is the pumping constant.)
Reg($L) \rightarrow \exists p\forall w(\in L) \forall u_1u_2v(\in \...
- 6,795
4
votes
2
answers
275
views
Characterisation of P in terms of register machines
It is a well-known result that Turing machines and random access machines (RAMs) can simulate each other with a polynomial slowdown.
It is relatively straightforward to prove that indirect addressing ...
13
votes
1
answer
875
views
Rabin's "degree of difficulty of computing a function, and a partial ordering of recursive sets"
I am looking for:
Michael O. Rabin, "Degree of difficulty of computing a function, and a partial ordering of recursive sets", Hebrew University, Jerusalem, 1960
Summary:
“We attempt to measure ...
- 21.8k
29
votes
1
answer
2k
views
Why are regular languages called "regular"?
Why are regular languages (and from that regular expressions) called "regular"? There is lot of regularity also in context-free languages other types of languages.
I suppose that, in the beginning, ...
CommunityBot
- 1
77
votes
14
answers
21k
views
Applications of topology to computer science
I'd like to write a survey on the applications of Topology in Computer
Science. I plan to cover the history of topological ideas in Computer
Science and also highlight a few current developments. It ...
- 119
23
votes
2
answers
3k
views
Why did Kolmogorov publish Karatsuba's algorithm?
Karatsuba's algorithm for fast multiplication was first published in A. Karatsuba and Yu. Ofman (1962), "Multiplication of Many-Digital Numbers by Automatic Computers", Proceedings of the USSR Academy ...
- 101
14
votes
0
answers
259
views
historical question: earliest description of beta-normal terms together with "neutral" terms in lambda calculus?
A bit of "folklore" in lambda calculus is the idea of characterizing the class of $\beta$-normal terms inductively as a syntactic category ($R$) defined in mutual induction with an auxiliary syntactic ...
- 4,831
15
votes
5
answers
5k
views
History of recursion
Who introduced the idea of recursion?
Can someone explain where it came from and how it impacted computer science?
CommunityBot
- 1
3
votes
0
answers
105
views
Advances in complexity by studying particular problems
When we are trying to figure out in which complexity class a problem lies, we usually try simultaneously to come up with the best algorithm for it, together with the best hardness reduction, until (...
- 9,018
21
votes
3
answers
2k
views
Who introduced nondeterministic computation?
I have two historical questions:
Who first described nondeterministic computation?
I know that Cook described NP-complete problems, and
that Edmonds proposed that P algorithms are "efficient" or "...
- 105
90
votes
2
answers
13k
views
Was the reduction in Shor's algorithm originally discovered by Shor?
This is a "historical question" more than it is a research question, but was the classical reduction to order-finding in Shor's algorithm for factorization initially discovered by Peter Shor, or was ...
- 25k
10
votes
1
answer
2k
views
Did Stephen Cook see the significance of showing that SAT is NP-Hard before actually proving it?
If I understand correctly, to prove that problem $A$ is NP hard, you need to pick all possible problems $B_{i}$ that are in NP and then prove that they reduce to $A$ by using a polynomial time ...
- 14.1k
14
votes
1
answer
2k
views
Why was there a need for Martin-Löf to create intuitionistic type theory?
I've been reading up on Intuitionistic Type Theory (ITT) and it does make sense. But what I'm struggling to understand is "why" was it created in the first place?
Intuitionistic Logic (IL) and Simply-...
- 11.6k
4
votes
3
answers
693
views
Why is lambda calculus so "function" oriented?
I've always had this question nagging at me subconsciously but have never been able to intuitively grasp it. Why does $\lambda$-calculus have a functional notation? Why is everything a function?
It ...
- 454
13
votes
2
answers
1k
views
How exactly does lambda calculus capture the intuitive notion of computability?
I've been trying to wrap my head around the what, why and how of $\lambda$-calculus but I'm unable to come to grips with "why does it work"?
"Intuitively" I get the computability model of Turing ...
- 5,143
15
votes
1
answer
682
views
Why was Schönfinkel's work on eliminating "bound variables" in logic so crucial?
AFAIK, The first evidence of using higher order functions goes back to Schönfinkel's 1924 paper: "On the Building Blocks of Mathematical Logic" - where he allowed one to pass functions as ...
- 2,099
23
votes
2
answers
2k
views
What was the original intent for the creation of Lambda calculus?
I've read that initially Church proposed the $\lambda$-calculus as part of his Postulates of Logic paper (which is a dense read). But Kleene proved his "system" inconsistent after which, Church ...
- 103
36
votes
8
answers
11k
views
Alan Turing's Contributions to Computer Science
Alan Turing, one of the pioneers of (theoretical) computer science, made many seminal scientific contributions to our field, including defining Turing machines, the Church-Turing thesis, ...
CommunityBot
- 1
13
votes
4
answers
2k
views
Alan Turing Documentaries
To celebrate Alan Turing 100th birthday, I want to watch a documentary about his life. However, there are several documentaries to choose from.
Which documentary about Alan Turing is your favorite?
...
CommunityBot
- 1
28
votes
3
answers
4k
views
Impact of Grothendieck's program on TCS
Grothendieck has passed away. He had massive impact on 20th century mathematics continuing into the 21st century. This question is asked somewhat in the style/spirit, for example, of Alan Turing's ...
CommunityBot
- 1
-2
votes
1
answer
204
views
who found out Theory of Computer Science? [closed]
who first started to analyse computers theoretically ?
who gave birth to Theory of Computation ?
- 7,788