Bjørn Kjos-Hanssen
Moderator
  • Member for 11 years, 3 months
  • Last seen this week
Chomsky-Schutzenberg Hierarchies explained for physicist (general)
3 votes

$\Sigma$ is the alphabet of the grammar and so $\Sigma^k$ is the set of words of length $k$ from that alphabet. Finally $L\cap\Sigma^k$ is then the set of such words that are in $L$, i.e., that are ...

View answer
What type of mathematical problems interesting for TCS researchers?
3 votes

Let us say I am able to give an algorithm which classifies all modules (algebraic structure) of some rank. Will that be interesting to TCS researchers? Roughly speaking... It will be interesting to ...

View answer
Is Murphy's Law of Complexity Theory consistent? What separations/collapses does it imply?
3 votes

A counterexample to this Murphy's Law could actually be the famous paper Baker, Theodore; Gill, John; Solovay, Robert, Relativizations of the $\cal P=?\cal N\cal P$ question, SIAM J. Comput. 4, 431-...

View answer
Can boolean algebra be expressed in simply typed lambda caclulus?
3 votes

The OP wrote above that the question is answered by a post on @AndrejBauer's blog.

View answer
What is conjunctive truth table reduction?
Accepted answer
3 votes

In the binary case they are two of the seven truth-table reducibilities $$m, btt(1), c, d, p, \ell, tt$$ based on polynomial clones. See Figure 1 in Culver's paper https://link.springer.com/article/10....

View answer
Under what conditions is the Dining Philosophers Problem unsolvable?
3 votes

Well, if the philosophers are following the exact same strategy and there is nothing to distinguish them (like who is closest to the door etc.) then they will do exactly the same and deadlock must ...

View answer
Naive shuffle algorithm
3 votes

Consider the case $n=3$. There are 27 possible runs of the algorithm. Let's see where the first vector ends up ($X_1$) in each case, and where the 2nd ends up ($X_2$). $$ \text{Format:}\quad\sigma_1\...

View answer
When studying the computational complexity of functions $\{0, 1\}^\ast \to \{0, 1\}^\ast$, is it enough to restrict to $\{0, 1\}^\ast \to \{0, 1\}$?
3 votes

Since the article seems to be an effort at popularization of science, it probably made sense to the author to not discuss the details of that point. It seems analogous to defining uniform continuity ...

View answer
Can any c.e. language with infinite words be decomposed into infinite CFLs with infinite words?
Accepted answer
3 votes

No, we get counterexamples by considering resource-bounded randomness. In fact the gap between c.e. and $\mathsf{CFL}$ is wide. Let $R$ be exponential-time random. Then $R$ is $\mathsf{NP}$-immune, i....

View answer
Is the relation decidable?
Accepted answer
3 votes

Yes, that's the Ideal Membership Problem and it is solved using Gröbner bases.

View answer
One Generalization of Graph Isomorphism Problem
3 votes

I wasn't able to figure out whether $\mathrm{GI}(1/2)\in\mathsf P$, but here is a weaker result: The languages $\mathrm{GI}(1/2)$ and $\mathrm{GI}$ are not $\mathsf P$-inseparable. Proof: It suffices ...

View answer
Are there (N-1)! ways to order joins?
Accepted answer
3 votes

I guess $((AB)(CD))$ is actually two ways, because you could do either $(AB)$ or $(CD)$ first.

View answer
Turing degree of Solomonoff semi-measure
Accepted answer
3 votes

Note that from $ m (0) $ you can compute a version of Chaitin's $\Omega $. Moreover $ m (x) $ is left-c.e. uniformly in $ x $. So $ m $ has Turing degree $0'$.

View answer
Definition of a monotone machine.
3 votes

When we say that a monotone machine is a set $L$ of pairs of strings $(x,y)$, the first component $x$ is the part of the input tape being read in order to produce the output $y$. This set is c.e. (...

View answer
How to know if X and Y have coauthored?
3 votes

There is also Microsoft Academic Search if you're looking for graphical display of coauthor graphs, although it does not appear to be a finished product content-wise.

View answer
Entropy-like quantity
Accepted answer
2 votes

It's the $\alpha^{\mathrm{th}}$ moment of the Tribus surprisal. This generalizes the statement that entropy = expected surprisal. Or in Ross's textbook, "expected surprise".

View answer
Are string palindrome questions practically interesting?
Accepted answer
2 votes

I had a use for palindromes as follows: A string of length $n$ and its reversal have the same complexity. Thus, when studying complexity of strings you can identify a string with its reversal. Now ...

View answer
Which monotone Boolean functions are representable as thresholds on sums?
Accepted answer
2 votes

It was mentioned in the comments that these are the positive threshold functions. As for other characterizations, I found the following to be interesting. Suppose we have a positive threshold ...

View answer
Confusion about a formal definition of PRAM consistency
2 votes

When they define PRAM (page 11 of the arxiv preprint) they actually state that vis is a partial order (in particular, transitive): We define PRAM consistency by requiring the visibility partial ...

View answer
Visualizing the parse structure of a range concatenation grammar
Accepted answer
2 votes

Edit: answer obeying the "spirit" of the question: Let's use the rules $$S(xy)\to A(x,y)$$ $$A(x,ayb)\to A(x,x)A(y,y)$$ $$A(x,x)\to\epsilon$$ Then we can derive $S(aabb)\to A(a,abb)\to A(a,a)A(b,b)\...

View answer
Properties of toroidal graph
2 votes

Regarding (3), yes, if a graph $M$ has two vertex disjoint non-planar induced subgraphs $G$ and $H$, then $G\cup H$ (and hence $M$) is not toroidal. I don't know a reference but here's a proof ...

View answer
Is there any notion of sensitivity for probabilistic Boolean functions?
2 votes

This should work fine inasmuch as if $f$ is now a random function, then you just get the expected sensitivity: $$\mathbb E s(f, x) = \sum_{y \in N(x)} \mathbb E I(f(x) \neq f(y)) = \sum_{y \in N(x)} \...

View answer
What is the relation between P-immune languages and NP-complete languages?
Accepted answer
2 votes

Assuming that pseudorandom generators and secure one‐way permutations exist, it follows that $\mathsf{NP}$‐complete sets are not $\mathsf P$‐immune. Christian Glaßer, A. Pavan, Alan L. Selman, and ...

View answer
Reasonable estimate of an asymptotic limit notion of Kolmogorov complexity
2 votes

As commenters @Lwins and @SashaNikolov have already stated, it is non-computably hard to compute a function as slow-growing as $f$. (So no really humanly comprehensible rate can be given.) Namely, ...

View answer
Compressing information about the halting problem for oracle Turing machines
2 votes

Let $J^A(e)$ be the output of the $e$th Turing machine equipped with oracle $A$, on input $e$. Here $J$ stands for "jump". (In case of non-halting, $J^A(e)$ is undefined.) An oracle $A$ is jump-...

View answer
The Complexity of Advice in Computational Indistinguishability
Accepted answer
2 votes

Case 1. The distributions $U_n$ and $V_n$ are computable in the sense that we can eventually tell if your displayed inequality is violated, for fixed $n$ and $z$. It seems the answer to the first ...

View answer
Is the unbounded fan-in model realistic?
1 votes

Don't forget that even though the fan-in is unbounded, the number of gates is polynomially bounded in the number of variables $n$ (in the definition of $\mathsf{AC}$ for instance) .

View answer
Does $\exists\mathbb{R}=\mathbf{PSPACE}$?
Accepted answer
1 votes

The issue may be whether or not Schwartz and Sharir show that motion plan existence is many-one polynomial time reducible to $\exists\mathbb R$. If they need several queries to $\exists\mathbb R$ for ...

View answer
Irreducible languages
Accepted answer
1 votes

Here's a counterexample to this: call a language L "reducible" if it can be written as $L = A \cdot B$ with $A \cap B = \emptyset$ and $|A|,|B|>1$, otherwise call the language "irreducible". ...

View answer
Validity of a modal argument about "vagueness"
Accepted answer
1 votes

How about just a blanket statement with no assumptions: A and B may be the same part of C This would seem to be valid by the same reasoning! However it is only so if "may" ranges over all models ...

View answer