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
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 ...
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
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
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 ...
- 603
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 ...
- 171
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 ...
- 1,763
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,...
- 331
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?
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
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 ...
- 41
18
votes
6
answers
876
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 - ...
- 351
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 ...
- 191
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 ...
- 1,145
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, ...
- 151
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 ...
- 171
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 ...
- 94
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.
- 701
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 ...
- 31
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
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 ...
- 319
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.
- 191
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 ...
- 223
4
votes
2
answers
274
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
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
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 "...
user1338
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 ...
- 219
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-...
- 5,385
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 ...
- 5,385
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 ...
- 5,385
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 ...
- 5,385
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,385
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
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 ...
- 11.1k
-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 ?
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 ...
user1338
8
votes
0
answers
709
views
Why is single authorship so common among breakthrough papers in computer science?
Looking at the list of important papers in computer science one notices that the majority are authored by a single author. Those include classic papers of Turing, Shannon, Karp and Cook. Cook's solo ...
- 21.1k
26
votes
1
answer
741
views
Rabin–Karp vs Karp–Rabin
The wise other editors at Wikipedia have declined my request to move the Wikipedia article on the Rabin–Karp algorithm to what I think it should be called, the Karp–Rabin algorithm, on the basis that ...
- 51.2k
20
votes
2
answers
731
views
Arguments for/against Kolmogorov's conjecture about the circuit complexity of P
According to (unverified) historical account, Kolmogorov thought that every language in $\mathsf{P}$ has linear circuit complexity. (See the earlier question Kolmogorov's conjecture that $P$ has ...
- 11.4k
28
votes
2
answers
1k
views
Kolmogorov's conjecture that $P$ has linear-size circuits
In his book, Boolean Function Complexity, Stasys Jukna mentions (page 564) that Kolmogorov believed that every language in P has circuits of linear size. No reference is mentioned and I couldn't find ...
- 381
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/...
- 5,385
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 ...
- 1,571
12
votes
2
answers
458
views
Reference for Dyck languages being $\mathsf{TC}_0$-complete
Dyck languages $\mathsf{Dyck}(k)$ is defined by the following grammar
$$
S \rightarrow SS \,|\, (_1 S )_1 \,|\, \ldots \,|\, (_k S )_k \,|\, \epsilon
$$
over the set of symbols $\{(_1,\ldots,(_k,)_1,\...
- 7,668
7
votes
1
answer
305
views
Measurability of an $\omega$-regular language
It the previous question of mine I put a reference which shows that any $\omega$-regular language over the alphabet $\Sigma$ is a Borel subset of $\Sigma^\omega$. I am not sure whether the reference I ...
- 407
2
votes
0
answers
312
views
Unary subset sum
Who can be attributed with the discovery or invention of the unary subset sum algorithm which is known to have polynomial time complexity but exponential space complexity.
I am currently writing a ...
- 116
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 \...
- 313
18
votes
5
answers
2k
views
Why economists should care about computational complexity
When trying to convince economists of the relevance of complexity theory in print, is there a standard reference to cite? I am familiar with Noam Nisan's blog post, Tim Roughgarden's survey, and ...
- 10.3k