The history behind the topics: where their name comes from, who discovered them, when they were first proved, how they evolved during the years.

learn more… | top users | synonyms

36
votes
2answers
4k 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 ...
7
votes
0answers
449 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 ...
25
votes
1answer
485 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 ...
17
votes
2answers
312 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 ...
25
votes
2answers
659 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 ...
57
votes
6answers
20k 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 ...
17
votes
1answer
930 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 ...
12
votes
2answers
179 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 ...
7
votes
1answer
165 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 ...
2
votes
0answers
184 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 ...
1
vote
0answers
132 views

Providence of pumping lemmas for regular languages

I'm looking to track down who discovered the following pumping lemmas for regualar languages. (where $p$ is the pumping constant.) Reg($L) \rightarrow \exists p\forall w(\in L) \forall u_1u_2v(\in ...
16
votes
5answers
1k 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 ...
28
votes
2answers
3k views

Reference for NP-hardness of 3-colouring?

I have a historical question. I’m trying to determine the reference for the fact that 3-colourability of graphs (alternatively, $k$-colourability for given $k\geq 3$) is NP-hard. The tempting answer ...
4
votes
1answer
139 views

Lambda: The Ultimate Imperative - who is Jensen?

One of the notes in the classical paper LAMBDA: The Ultimate Imperative says: {Jensensdevice} The technique of repeatedly modifying a variable passed call-by-name in order to produce side ...
-1
votes
2answers
139 views

iterations of a $\epsilon$-FSM transducer on a tape as equivalent to a TM computation

A question partly inspired by a recent question[1] on the utility of FSMs: Years ago noticed the following property of FSM transducers with $\epsilon$-transitions (which allow an "empty" transition ...
3
votes
2answers
825 views

Why were Finite Automata and Turing Machines created?

It seems the creation of Turing Machines and finite automata were apart by at least 2+ decades. That is TMs don't really reference FAs for their working and vice versa; TMs and FAs were developed ...
12
votes
2answers
301 views

Why is the state of a FSM traditionally denoted $q$?

While teaching how to implement FSMs using synchronous logical circuits, I noticed an intriguing coincidence: in both the theoretical CS world, and in the electrical engineering world, "state" is ...
5
votes
6answers
530 views

Was the reason that Computers were invented to solve a philosophical question about the foundations of mathematics?

This guy asserts: I’ll say it — the computer was invented in order to help to clarify … a philosophical question about the foundations of mathematics. (This problem being Entscheidungsproblem - ...
12
votes
0answers
456 views

Looking for a quotation by Edsger Dijkstra

In one of his papers Edgser Dijkstra makes a statement like: "What we consider to be the standard case is one case among many exceptional cases only it occurs more often " or something along such ...
12
votes
0answers
232 views

First use of sans serif for complexity classes

(Apologies for the triviality of this question; nevertheless, it's been bugging me and presumably people here will be able to answer it...) It seems that it has become popular in recent years to ...
14
votes
1answer
433 views

Who introduced the complexity class AC?

I taught $AC^0$ lower bounds today, and one of the students asked about the reason for the name $AC$. The official explanation is that the "A" stands for "Alternation". I vaguely remember being told ...
24
votes
10answers
2k views

Probabilistic (randomized) algorithms before “modern” computer science appeared

Edit: I choice the answer with highest score by December 06, 2012. This is a soft question. The concept of (deterministic) algorithms dates back to BC. What about the probabilistic algorithms? In ...
7
votes
4answers
215 views

Early References for Transition System Semantics of Programs

I am trying to trace back the origins of transition system semantics for imperative programs. I am assuming a transition system is a tuple $(\mathit{States}, \mathit{Trans})$ consisting of a set of ...
24
votes
1answer
1k views

Who first proposed using $x^2+y^2 < 1$ Monte Carlo algorithm to calculate Pi?

I'm sure everybody knows of Buffon's needle experiment in the 18th century, that is one of the first probabilistic algorithms to calculate $\pi$. The implementation of the algorithm in computers ...
27
votes
8answers
5k 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, ...
11
votes
3answers
499 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? ...
7
votes
1answer
197 views

Origin of Church encodings

In which paper did Alonzo Church first describe Church encoding? I can't find any articles that actually cite the paper, but I am interested in reading it.
10
votes
2answers
767 views

The Relation between Babbage and von Neumann

It is well known that Charles Babbage's analytical machine had an architecture strongly ressembling the modern Von Neumann architecture. Also, it's notable that the tables for representing a program ...
12
votes
4answers
400 views

The origin of the terms “efficient” and “feasible” computation/algorithm

I would like to know about the history of these two terms: "efficient", "feasible". Who used them about computation/algorithms the first time? (in modern sense of these terms, i.e. 20th century). ...
13
votes
1answer
190 views

Early history of certain results on space-time tradeoffs?

I'm interested in the early history of published results on general-purpose space-time tradeoffs. In particular, I want to know who first described the following type of algorithm for evaluating a ...
14
votes
3answers
826 views

Is the concept of the Turing Machine derived from automata?

I was just recently having a discussion about Turing Machines when I was asked, "Is the Turing Machine derived from automata, or is it the other way around"? I didn't know the answer of course, but ...
9
votes
2answers
265 views

Early references for discrete optimization

(Apologies if this is misplaced or too broad. I'm open to suggestions on how to reformulate it.) I'm interested in tracing back the "ancient" history of max-flow algorithms, and discrete ...
30
votes
2answers
929 views

“Steve's class”: origin of SC

We "know" that $\mathsf{SC}$ is named for Steve Cook and $\mathsf{NC}$ is named for Nick Pippenger. If I'm not mistaken, Steve Cook named NC in honor of Nick Pippenger, and I was told that the reverse ...
18
votes
1answer
667 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, ...
6
votes
0answers
291 views

Use of calculus of variations

Have results from the calculus of variations been used previously in TCS?
2
votes
1answer
605 views

Why have computer scientists chosen recursor instead of iterator in primitive recursion?

I wonder why computer scientist have chosen recursor instead of iterator (or tail recursor if you like) in primitive recursion, given that function defined in terms of iteration behaves more ...
10
votes
2answers
226 views

Exhibits for a Museum of Computing

All of the computer-related museums and exhibits I'm aware of seem to only cover the history of computing machinery, but nothing on topics of computer science. You are involved in the creation of a ...
36
votes
11answers
2k views

If you could rename dynamic programming…

If you could rename dynamic programming, what would you call it?
36
votes
4answers
2k 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 ...
4
votes
1answer
729 views

Why is the “free store” memory called the “heap”? [closed]

Does it have anything to do with the heap data structure, for example the Buddy blocks implementation, or does it only take the literal English meaning of the word (a big pile)? I know heap memory is ...
2
votes
1answer
284 views

Using compression to improve edit distance computation

I am doing a seminar on a paper titled "Unified Compression-Based Acceleration of Edit-Distance Computation" that uses straight-line programs to improve edit distance computation. It is a common ...
32
votes
5answers
1k views

Historical reasons for adoption of Turing Machine as primary model of computation.

It's my understanding that Turing's model has come to be the "standard" when describing computation. I'm interested to know why this is the case -- that is, why has the TM model become more ...
27
votes
2answers
545 views

Papers to credit for spectral partitioning of graphs

If $G=(V,E)$ is an undirected $d$-regular graph and $S$ is a subset of the vertices of cardinality $\leq |V|/2$, call the edge expansion of $S$ the quantity $\phi(S) := \frac {Edges(S,V-S)}{d\cdot ...
40
votes
14answers
4k 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 ...
23
votes
2answers
912 views

Why Ramanujan graphs are 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?
32
votes
7answers
2k views

What is the oldest open problem in TCS?

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? ...
22
votes
2answers
892 views

Origins and applications of Theory A vs Theory B?

In a couple recent questions (q1 q2), there has been discussion of "Theory A" vs "Theory B", seemingly to capture the divide between the study of logic and programming languages and the study of ...
9
votes
3answers
818 views

About recursion

Where did the idea of recursion originated from? I mean first who thought about it.Can anybody care to explain about the origin of recursion and subsequent impact on the computer science?
11
votes
1answer
398 views

What are the historical roots of Milner's bigraphs?

Robin Milner defined bigraphs as a type of graphical structure with graph-like structure but where the nodes can be nested. They generalise process calculi like CCS and the $\pi$-calculus, but Milner ...