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.

Filter by
Sorted by
Tagged with
3 votes
2 answers
329 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 ...
10 votes
2 answers
352 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 ...
sparusaurata's user avatar
10 votes
0 answers
220 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 ...
Lê Thành Dũng 'Tito' Nguyễn's user avatar
3 votes
0 answers
118 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. ...
Mark S's user avatar
  • 1,083
4 votes
1 answer
192 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 ...
Nathan BeDell's user avatar
3 votes
1 answer
392 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 ...
user777's user avatar
  • 171
8 votes
0 answers
256 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 ...
William Hoza's user avatar
  • 1,733
2 votes
0 answers
88 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 ...
Mike Izbicki's user avatar
  • 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,...
TedThomson's user avatar
11 votes
1 answer
297 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?
Jérôme Verstrynge's user avatar
2 votes
1 answer
232 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) $...
Cyriac Antony's user avatar
4 votes
0 answers
76 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 ...
ohhisara's user avatar
17 votes
6 answers
777 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 - ...
Rob Simmons's user avatar
8 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 ...
Robert's user avatar
  • 181
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 ...
Mark S's user avatar
  • 1,083
5 votes
0 answers
158 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, ...
Zargles's user avatar
  • 151
17 votes
0 answers
706 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 ...
dreizehnutters's user avatar
5 votes
1 answer
307 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 ...
Rajat De's user avatar
9 votes
1 answer
244 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.
Alejandro DC's user avatar
1 vote
1 answer
84 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 ...
kombinatorix's user avatar
7 votes
0 answers
305 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 ...
Noam Zeilberger's user avatar
19 votes
0 answers
803 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 ...
Vince Vatter's user avatar
8 votes
1 answer
251 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.
Ralff's user avatar
  • 191
11 votes
1 answer
286 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 ...
Frank's user avatar
  • 213
4 votes
2 answers
267 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 ...
Antonio E. Porreca's user avatar
13 votes
1 answer
864 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 ...
Kaveh's user avatar
  • 21.6k
14 votes
0 answers
257 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 ...
Noam Zeilberger's user avatar
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 (...
Denis's user avatar
  • 8,843
20 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 "...
user avatar
9 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 ...
jsguy's user avatar
  • 209
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-...
PhD's user avatar
  • 5,305
4 votes
3 answers
675 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 ...
PhD's user avatar
  • 5,305
15 votes
1 answer
672 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 ...
PhD's user avatar
  • 5,305
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 ...
PhD's user avatar
  • 5,305
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 ...
PhD's user avatar
  • 5,305
41 votes
1 answer
653 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 ...
András Salamon's user avatar
28 votes
3 answers
3k 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 ...
vzn's user avatar
  • 11k
-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 ?
Kishore Vignesh's user avatar
89 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 ...
user avatar
8 votes
0 answers
696 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 ...
Mohammad Al-Turkistany's user avatar
26 votes
1 answer
738 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 ...
David Eppstein's user avatar
20 votes
2 answers
680 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 ...
Andras Farago's user avatar
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 ...
Hamid's user avatar
  • 381
94 votes
7 answers
30k 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/...
PhD's user avatar
  • 5,305
22 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 ...
Max's user avatar
  • 1,561
12 votes
2 answers
409 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,\...
Hsien-Chih Chang 張顯之's user avatar
7 votes
1 answer
300 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 ...
SBF's user avatar
  • 407
2 votes
0 answers
304 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 ...
Phil's user avatar
  • 116
3 votes
0 answers
246 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 \...
C.E.Sally's user avatar
  • 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 ...
Artem Kaznatcheev's user avatar