11
votes
Accepted
To what extent is my interpretation of computable numbers correct?
This is exactly the incorrect interpretation of "computable", resulting of trying to replace the precise definition with (possibly misplaced) intuition.
$\pi$ or any other irrational number also has ...
- 13.3k
8
votes
Accepted
Elimination rule for the equality type aka J axiom
A complete understanding of what J was actually saying and why has only come fairly recently. This blog post discusses it. While thinking in terms of homotopy and ...
6
votes
How to tell if a language is recognizable, co-recognizable or decidable?
L is recognizable
A language $L$ is recognizable if and only if there exists a verifier for $L$, where a verifier is a Turing machine that halts on all inputs and for all $w \in \Sigma^*$, $w \in L \...
- 1,148
6
votes
Accepted
What does it mean for a problem to be both NP hard and coNP hard
A language $L$ is NP-hard if for every language $R$ in NP there exists a function $f$ computable in polynomial time such that for all $x$, $x \in R$ iff $f(x) \in L$.
A language $L$ is coNP-hard if ...
- 275k
6
votes
Accepted
Is the following intuition valid for understanding $k$-wise independent hash functions?
Your intuition is exactly right. Yes, that's equivalent to choosing a random polynomial over $\mathbb{F}_p$. The reason why it works is exactly the interpolation theorem for finite fields.
$k$-wise ...
D.W.♦
- 156k
5
votes
What does it mean for a problem to be both NP hard and coNP hard
When a problem is NP-complete, it is hard to find out whether the answer is yes or no but if the answer is yes, there are short witnesses that are easy to check (but not easy to find).
For example ...
- 851
5
votes
Why don't integer multiplication algorithms use lookup tables?
If you want to use lookup tables, and you have 4GB of memory, you'll only be able to use a lookup table with about $2^{32}$ entries or fewer, so you'll only be able to handle multiplication of numbers ...
D.W.♦
- 156k
4
votes
Accepted
Why don't integer multiplication algorithms use lookup tables?
Some integer multiplication algorithms do use lookup tables.
The IBM 1620 Model I "CADET" lacked a conventional ALU:
addition and subtraction used a 100 digit table; multiplication used a ...
- 886
4
votes
Seeking an "intuitive" proof
Since the $y_i$ are non-negative, you can think of $y_1,\ldots,y_n$ as specifying a probability distribution. One way to sample from this distribution is via the partition
$$
[0,1) = [0,y_1) \cup [y_1,...
- 275k
3
votes
Bellman-Ford algorithm intuition
I can give you the intuition behind Bellman-Ford. It is beautiful! I'm going to do it in an indirect way. I want to share a warm-up puzzle that might seem unrelated, but stay with me.
Suppose we ...
D.W.♦
- 156k
3
votes
To what extent is my interpretation of computable numbers correct?
First off, I'm not sure what the intuition you're proposing is, so I'll make some general remarks.
In the comic, the problem given to the robot was ill-posed; the interpretation of the request is not ...
- 72k
3
votes
Accepted
Of monotone formulas and same ones satisfying certain properties
Spira's result uses the technique of formula balancing. For simplicity, I describe the non-monotone case, the monotone case being similar.
Let $\phi$ be a formula of size $n$. We can think of $\phi$ ...
- 275k
3
votes
What does it mean for a problem to be both NP hard and coNP hard
When wikipedia says the complement, that's literally what it means:
A problem $L$ is in NP if there's a non-deterministic Turing Machine $M$ that, for every word $w \in L$, that accepts $w$ in ...
- 29.7k
3
votes
How to tell if a language is recognizable, co-recognizable or decidable?
Main ideas
Being recognizable means you can build an automatic process (we'll get back to that later) that takes a word as a parameter such that
If the automatic process ends, it returns either YES ...
- 362
2
votes
Algorithmic intuition for logarithmic complexity
The intuition is how many times you can halve a number, say n, before it is reduced to 1 is O(lg n).
For visualizing, try drawing it as a binary tree and count the number of levels by solving this ...
- 61
2
votes
Accepted
An intuitive explanation for LR grammars?
A language is $LR(k)$ if looking at the right side of a production, and looking $k$ symbols ahead, one can determine the left hand side of the production. This is quite incomplete, but intuitively ...
- 13.9k
2
votes
Accepted
What is the simplest/smallest subset an OOP language like C#/JavaScript that is Turing-complete?
It takes very little to obtain Turing completeness. For example the While programming language and Counter Machines are Turing complete and are easily recognized as a subset (up to syntax) of all ...
- 2,214
2
votes
Accepted
Intuition behind straight-line programs
A straight-line program is one with no branches, no loops, no conditional statements, no comparisons -- just a sequence of basic operations.
A straight-line program for a finite group $G$ is a ...
D.W.♦
- 156k
1
vote
Accepted
Eulerian Path and Circuit Algorithm - How does it work?
The algorithm you linked is (or is closely related to) Hierholzer's algorithm. While Fleury's algorithm stops to make sure no one is left out of the path (the "making decisions" part that ...
- 209
1
vote
To what extent is my interpretation of computable numbers correct?
I think there are too many kinds of sort-of uncomputability involved here:
Uncomputable because ill-defined. "The smallest rational larger than 1.0" would be an example.
Uncomputable because of ...
- 111
1
vote
Is the following intuition valid for understanding $k$-wise independent hash functions?
You can explicitly teach this for small $k$. For example, when $k=1$ you can take the random hash function $h(x) = c_0$, where $c_0 \in \mathbb{Z}_p$ is chosen randomly; for each individual $x$, this ...
- 275k
1
vote
Google's Deep Dreamer
Simply put, you:
Pick a layer
Forward propagate to that layer
Set the gradient at that layer to the activation at that layer.
Backpropagate to update the image
The general idea is that you want that ...
1
vote
Google's Deep Dreamer
So far nothing's been said about technical details of DeepDream. I'll fill the blank.
The procedure is the following: pick some layer from the network (usually a convolutional layer), pass the ...
- 640
1
vote
Why is $L= \{ 0^n 1^n | n \geq 1 \}$ not regular language?
Simple rule: Regular expressions can't count. That said, sometimes you are given languages that look like they need counting, but it turns out they actually don't. An example is that language over (0, ...
- 28.4k
Only top scored, non community-wiki answers of a minimum length are eligible