Most Popular
1500 questions
21
votes
5 answers
About properties of adjacency matrix when a graph is planar
1- Is there any specific properties for adjacency matrix when a graph is planar?
2- Is there any thing special for computing the permanent of adjacency matrix when a graph is planar?
marjoonjan
- 747
- 4
- 12
21
votes
1 answer
"Almost easy" NP-complete problems
Let us say that a language $L$ is P-density-close if there is a polynomial time algorithm that correctly decides $L$ on almost all inputs.
In other words, there is an $A\in$ P, such that $L\Delta A$ is vanishing, which means…
Andras Farago
- 11,396
- 37
- 70
21
votes
3 answers
Generalizations of Brzozowski's method of derivatives of regular expressions to grammars?
Brzozowski's method of derivatives is a very pretty technique for building deterministic automata from regular expressions in a nicely algebraic way. I've worked out some cute generalizations of this technique to handle some larger classes of…
Neel Krishnaswami
- 32,528
- 1
- 100
- 165
21
votes
3 answers
Smallest possible universal combinator
I am looking for the smallest possible universal combinator, measured by the number of abstractions and applications required to specify such a combinator in the lambda calculus. Examples of universal combinators include:
size 23:…
user76284
- 662
- 3
- 14
21
votes
1 answer
Number of distinct differences of $\omega(\sqrt{n})$ integers chosen from $[n]$
I encountered the following result during my research.
$$\lim\limits_{n\to \infty} \mathbb{E}\left[
\frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n}
\right] = 1$$
where $m=\omega(\sqrt n)$ and $a_1,\cdots,a_m$ are chosen at random from $[n]$.
I am…
Zhu Cao
- 313
- 1
- 4
21
votes
1 answer
Why it's impossible to declare an induction principle for Church numerals
Imagine, we defined natural numbers in dependently typed lambda calculus as Church numerals. They might be defined in the following way:
SimpleNat = (R : Set) → R → (R → R) → R
zero : SimpleNat
zero = λ R z _ → z
suc : SimpleNat → SimpleNat
suc sn…
Konstantin Solomatov
- 1,762
- 11
- 20
21
votes
5 answers
Can a computer simulate itself as part of a simulated world?
Let's say you build a computer that will calculate the state of all atoms in the Universe at certain future point in time. Because the Universe is, by definition, everything that exists (and anything that interacts with the rest), it also includes…
mojuba
- 319
- 2
- 5
21
votes
1 answer
Arithmetic circuits with just one threshold gate
When restricted to $0$-$1$ inputs, every $\{+,\times\}$-circuit $F(x_1,\ldots,x_n)$ computes some
function $F:\{0,1\}^n\to \mathbb{N}$. To obtain a boolean function, we can just add
one fanin-1 threshold gate as the output gate. On input…
Stasys
- 6,765
- 29
- 54
21
votes
4 answers
DNA-algorithms and NP-completeness
What is the relationship between DNA-algorithms and the complexity classes defined using Turing machines? What do the complexity measures like time and space correspond to in DNA-algorithms? Can they be used to solve instances of NP-complete…
Aadita Mehra
- 283
- 2
- 9
21
votes
4 answers
Examples of hardness phase transitions
Suppose we have a problem parameterized by a real-valued parameter p which is "easy" to solve when $p=p_0$ and "hard" when $p=p_1$ for some values $p_0$, $p_1$.
One example is counting spin configurations on graphs. Counting weighted proper…
Yaroslav Bulatov
- 4,701
- 1
- 25
- 39
21
votes
4 answers
What is the minimum size of a circuit that computes PARITY?
It is a classic result that every fan-in 2 AND-OR-NOT circuit that computes PARITY from the input variables has size at least $3(n-1)$ and this is sharp.
(We define size as the number of AND and OR gates.)
The proof is by gate-elimination and it…
domotorp
- 13,931
- 37
- 93
21
votes
2 answers
For a random oracle R, does BPP equal the set of computable languages in P^R?
Well, the title pretty much says it all. The interesting question above was asked by commenter Jay on my blog (see here and here). I'm guessing both that the answer is yes and that there's a relatively simple proof, but I couldn't see it offhand. …
Scott Aaronson
- 13,733
- 2
- 62
- 68
21
votes
2 answers
A total language that only a Turing complete language can interpret
Any language which is not Turing complete can not write an interpreter for it self. I have no clue where I read that but I have seen it used a number of times. It seems like this gives rise to a kind of "ultimate" non Turing complete language; the…
Jake
- 1,203
- 7
- 20
21
votes
1 answer
A flowchart for concentration bounds
When I teach tail bounds, I use the usual progression:
If your r.v is positive, you can apply Markov's inequality
If you have independence and also bounded variance, you can apply Chebyshev's inequality
If each independent r.v also has all moments…
Suresh Venkat
- 32,071
- 4
- 95
- 271
21
votes
5 answers
What notable automaton models have polynomially-decidable containment?
I'm trying to solve a particular problem, and I thought I might be able to solve it using automata theory. I'm wondering, what models of automata have containment decidable in polynomial time? i.e. if you have machines $M_1, M_2$ you can test if…
Joey Eremondi
- 2,832
- 15
- 29