25
For a general audience you have to stick to things that they can see. As soon as you start theorizing they'll start up their mobile phones.
Here are some ideas which could be worked out to complete examples:
There is a surface which has only one side.
A curve may fill an entire square.
There are constant width curves other than a circle.
It is possible to ...
21
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 is not intuitive, or that it does not sufficiently explain what is going on. In contrast, he found Turing's analysis of computability and the ensuing notion of ...
17
One idea is something simple from streaming algorithms. Probably the best candidate is the majority algorithm. Say you see a stream of numbers $s_1, \ldots, s_n$, one after the other, and you know one number occurs more than half the time, but you don't know which one. How can you find the majority number if you can only remember two numbers at a time? The ...
17
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 research field, with a competition (the POPLmark challenge) some years ago. There are even jokes by people in the field about the complexity of approaches to ...
16
How do you decide what the "wrong way" is?
Take the first wrong-way swap gate, and interchange the two wires going out of it (including all their associated gates) so that it's correct. This doesn't change the fundamental circuit. It may introduce more wrong-way swap gates, but they're all later in the circuit.
Now, you can keep doing this until you've ...
14
Type theories in which every type is inhabited are far from being useless. True enough, through the eyes of logic they are inconsistent, but there are other things in life apart from logic.
A general purpose programming language has general recursion. This allows it to populate every type, but we would not conclude from this fact that programming is a ...
13
How to come up with sum-of-logs potential
Let's consider the BST algorithm $A$ that for each access for element $x$, it rearranges only elements in the search path $P$ of $x$ called before-path, into some tree called after-tree. For any element $a$, let $s(a)$ and $s'(a)$ be the size of subtree rooted at $a$ before and after the rearrangement respectively. ...
13
The volume of a unit sphere of dimension $n$ first grows as $n$ grows ($2,\pi,4\pi/3,\dots$) but starts decreasing for $n=6$ and eventually converges to $0$ as $n\to\infty$.
10
A counter intuitive result from complexity theory is the PCP theorem:
Informally, states that for every $NP$ problem $A$, there is an efficient randomized Turing machine that can verify proof correctness (proof of membership in $A$) using logarithmic number of random bits and reading only constant number of bits from the proof. The constant can be reduced ...
answered May 27 '15 at 10:19
Mohammad Al-Turkistany
19.5k4 gold badges51 silver badges134 bronze badges
9
One thing that proves to be counterintuitive for CS undergraduates, is the fact that one can select the $i$-th order statistics from an unsorted array of $n$ elements in $O(n)$ time. All of the students think they must first necessarily sort the array (in $O(n~lg ~n)$ time).
7
building on MdBs answer/ angle, a classic result of something counterintuitive at the time of discovery in TCS at its foundations is the existence of (un)decidability itself. at the turn of the 20th century Hilbert, mirroring the thinking of other leading mathematicians of the time, thought that mathematics could be systematized (somewhat in the form of what ...
6
The idea of how to 'mechanize mathematical proof' was a hot topic at the time; more specifically, Hilbert posed the Entscheidungsproblem - could we have a machine in some factory somewhere that takes mathematical statements in, and outputs proofs of the truth or falseness of those statements, as easily as machines might weave cotton or drill holes in steel?
...
6
I don't understand exactly what you are looking for, I'll try to explain the Curry-Howard correspondence in a nutshell, you'll let me know if it helps.
The Curry-Howard correspondence (or isomorphism, if you wish) definitely links the three objects you mention: it actually tells that two of them, IL and $\lambda$c, are the same thing. The term is used ...
6
You program in it! Take a look at church encodings. You can see how pretty much all arithmetic can be performed which should probably convince you that it is extremely powerful. I like to look at operations on lists however. You can define most any data structure in terms of a function that does the most important operation on it.
For instance an encoding ...
6
The way I remember it is that you also get a lower bound on the expected cost in the embedding. Namely for any two points $x$, $y$ at distance $d(x,y)$ in the original metric, their distance $d'(x,y)$ in the embedding satisfies $d(x,y) \leq d'(x,y)$. If I'm not mistaken, the first lecture mentions that too.
Then, everything is straightforward.
Look ...
6
It seems obvious, but from personal experience, the idea that you can estimate the median of a collection of items using a constant number of operations is a little shocking. And if that seems a little too technical, you can always convert it into a statement about polls an elections (you need 1300 people to get a sample with 3% error, regardless of the ...
5
Perhaps a good example (not directly related to computational complexity) is the Turing universality of simple computational models.
For example the rule 110 is efficiently (weakly) universal:
Given an (infinite) array of 0-1 (white-black) cells properly initialized and the simple substitution rules:
we have a "working computer"! :-)
For the definition ...
4
Below I expand a little bit on the point in Peter's answer by trying to carry out the quantifier removal for more than constant number of steps to see where it fails and if anything can be salvaged from such an attempt.
Let's try to amplify $\mathsf{P}=\mathsf{NP}$ for more than constant number times.
Assume that $\mathsf{P}=\mathsf{NP}$. Therefore there ...
4
Simple summary:
Typed $\lambda$-calculi are a way of presenting intuitionistic
logics.
Combinatory logic is a presentation of logic (propositional, first-order, higher-order, intuitionistic or otherwise) without binders.
Typed $\lambda$-calculi can easily be translated into combinatory logic. Some combinatory logics can easily be translated to typed
$\...
3
A few good candidates off the top of my head:
Every NFA has an equivalent DFA
There exists a finite field of size $p$ or $p^i$ where $i \in \mathbb{N}$ and $i > 0$.
Public key cryptography
Calling to a function with encrypted arguments and receiving the desired result without revealing information about your inputs
RSA encrpytion
Reed-Solomon codes
...
3
I do not know of a source that would allow me to state why Church went for functions. All I can state with confidence is that the concept of a function was of significant interest and controversy at the time. This was, recall, before Gödel proved it impossible to formalize mathematics completely, and a lot of effort was poured in developing a consistent and ...
3
Let me offer the simple, intuitive way that I think about this.
If you restrict yourself to closed lambda expressions, you have an equivalent of the combinatory logic. In fact with just a few simple closed lambda expressions you can generate all the others.
Closed lambda expressions give you the equivalent of implications where any conclusion/output you ...
3
PCPs are very often used to construct ZKPs, especially for NP-complete languages. The idea is simple: you commit to every bit of PCP separately, and then the prover makes random queries to the PCP. Given the query and committed bit, you prove in ZK that the bits in concrete locations would make the prover to accept. Since the number of queries is small, the ...
2
I don't think one can make a blanket statement on whether primal decomposition methods or dual decomposition methods are more efficient. The efficiency is dictated by the structure of the problem; primal decomposition and dual decomposition are ways of exploiting this structure to develop efficient algorithms.
The key aspect in making a choice between these ...
2
There is a very nice metaphor on decidable languages in the book Gödel, Escher, Bach by Douglas Hofstadter.
He uses drawings as an analogy for recursively enumerable languages.
Every time you draw something on a sheet of paper, the part of the sheet that is not used by your drawing can be viewed as the "complement" of your drawing.
The artist M.C. Escher ...
2
B-Trees, N-ary Trees, Autocracy and Democracy
http://rkvsraman.blogspot.in/2008/08/b-trees-n-ary-trees-autocracy-and.html
1
This is just a very long comment to Joe Babel answer above.
As said above Church invented $\lambda$-calculus to approach the Entscheidungsproblem (i.e. the decision problem for first-order logic)
which asked whether it was possible to provide an effective (i.e. computable) method that for a given input formula can either prove or disprove the formula.
In ...
1
There is a classical paper of Feige and Killian Zero Knowledge and the Chromatic Number that uses the ideas from Zero Knowledge Proofs in order to construct PCPs with certain "ZKP-type" properties. Using these properties they prove that it is NP-hard to color a $N^{0.01}$-colorable graph with $N^{0.99}$-colors.
It should be noted that their result does not ...
1
Water filling algorithm for channel allocation
http://en.wikipedia.org/wiki/Water_filling_algorithm
1
In my own case, most TCS concepts I feel like I have any intuition about are those I backed into via practical results. If I find myself evolving and using the same model or algorithm successfully for years, it tends to increasingly drive me to distraction until I can figure out why the algorithm's been successful. This is particularly true if it's time ...
Only top voted, non community-wiki answers of a minimum length are eligible
