# Tag Info

Accepted

### Who introduced nondeterministic computation?

I have always seen the notion of nondeterminism in computation attributed to Michael Rabin and Dana Scott. They defined nondeterministic finite automata in their famous paper Finite Automata and Their ...
• 18.1k
Accepted

### Impact of Grothendieck's program on TCS

Grothendieck's inequality, from his days in functional analysis, was initially proved to relate fundamental norms on tensor product spaces. Grothendieck called the inequality "the fundamental theorem ...
• 18.1k
Accepted

### What was the original intent for the creation of Lambda calculus?

He wanted to create a formal system for the foundations of logic and mathematics that was simpler than Russell's type theory and Zermelo's set theory. The basic idea was to add a constant $\Xi$ to ...
Accepted

### Why was there a need for Martin-Löf to create intuitionistic type theory?

Very briefly: the simply-typed $\lambda$-calculus does not have dependent types. Dependent types were proposed by de Bruijn and Howard who wanted to extend the Curry-Howard correspondence from ...
• 10.5k

### When have we found better bounds for known algorithms?

The Union-Find algorithm, which Tarjan1 showed had complexity $n \alpha(n)$, where $\alpha(n)$ is the inverse Ackermann function, had been analyzed previously by several people. According to Wikipedia,...
• 23.9k
Accepted

### How exactly does lambda calculus capture the intuitive notion of computability?

You're in good company. Kurt Gödel criticized $\lambda$-calculus (as well as his own theory of general recursive functions) as not being a satisfactory notion of computability on the grounds that it ...
• 27k

### Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient

Computing a generating set of invariants (sometimes called the computational problem of "Noether's Normalization Lemma") for the action of $SL_3$ on an $n$-dimensional vector space $V$. (You ...
• 36.1k

### Impact of Grothendieck's program on TCS

Grothendieck's impact can be felt in type theory and logic. For instance, Bart Jacobs' 700+ page volume Categorical Logic and Type Theory gives a uniform treatment of various type theories ($X$-type ...
• 16.6k
Accepted

### Did Stephen Cook see the significance of showing that SAT is NP-Hard before actually proving it?

First of all, Cook actually showed that the problem of whether a logical expression is a tautology is $\mathbb{NP}$-complete under Cook reductions. The proof however works by replacing them with Karp ...
• 3,741
Accepted

### Why was Schönfinkel's work on eliminating "bound variables" in logic so crucial?

TL;DR. The metamathematics of binding are subtle: they seem trivial but aren't — whether you deal with (higher-order) logics or 𝜆-calculus. They're so subtle that binding representations form an open ...
• 2,029
Accepted

### Entscheidungsproblem vs. Unvollständigkeitssatz (soft question)

The two words do not refer to the same thing. Hilbert's Entscheidungsproblem was the question whether there is an algorithm that decides the universal truth of first-order logical sentences, which was ...
• 4,511

### Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient

The task of unification went from an exponential solution to linear time in the timespan of about a decade. The original exponential algorithm was a corner-stone for symbolic AI approaches and enabled ...
• 271
Accepted

### Are Turing machines still useful as model of computation?

I think the issue is that, you're misunderstanding the purpose of the Turing Machine model. Turing Machines are not meant to be programmed in. If you're writing code, you absolutely should not be ...
• 2,754
Accepted

### Rabin's "degree of difficulty of computing a function, and a partial ordering of recursive sets"

There are two loanable copies at The National Library of Israel. Here is a scanned copy.
• 14.2k
Accepted

### When was co-NP introduced for the first time?

Albert R. Meyer and Larry J. Stockmeyer introduced the polynomial hierarchy in 1972 with their paper "the equivalence problem for regular expressions with squaring requires exponential space"...
• 5,504

### Impact of Grothendieck's program on TCS

Any applications of $p$-adic cohomology, etale cohomology in point counting formulas for algebraic varieties has roots in his work. I am guessing Mulmuley's vision of generalization of Riemann ...
• 12.6k

• 778

### Who introduced nondeterministic computation?

Rabin and Scott introduced the nondeterministic finite automata with their research paper published in IBM journal, April 1959. In the paper they mentioned: we have adopted an even simpler form of ...

### Are there any intersections between Theory A and Theory B?

One cool example of work that straddles things that are typically considered theory A and things typically considered theory B are the lower bounds on the running time of the simplex algorithm with ...
• 18.1k