Decidability of fractal maze A fractal maze is a maze which contains copies of itself. Eg, the following one by Mark J. P. Wolf from this article:

  Begin at the MINUS and make your way to the PLUS. When you enter a smaller copy of the maze, be sure to record the letter name of that copy, as you will have to leave this copy on the way out. You must exit out of each nested copy of the maze that you have entered into, leaving in the reverse order that you entered them in (for example: enter A, enter B, enter C, exit C, exit B, exit A). Think of it as a series of nested boxes. If there is no exit path leaving the nested copy, you have reached a dead end. Color has been added to make the pathways clearer, but it is only decorative.

If a solution exists, breadth-first-search should find a solution. However, suppose there is no solution to the maze - then our search program would run forever going deeper and deeper.

My question is: given a fractal maze, how can we determine if it has a solution or not?

Or alternatively, for a fractal maze of a given size (number of inputs/outputs per copy), is there a bound on the length of the shortest solution? (if there was such a bound, we could exaustively search only that deep)

A quick informal algorithm to prove that the problem is decidable:

suppose that there are $n$ Input/Outputs $I_1,...I_n$;
build a graph $G$ where each $I_i$, the $MINUS$ and the $PLUS$ are nodes, and replace each nested maze $Mj$ with a $K_n$ subgraph (complete graph); add the edges between $I_i, MINUS, PLUS, Mj_{I_k}$ according to the maze; keep "extern" $Mj_{I_i} \rightarrow Mj_{I_k}$ edges distinct from the corresponding "internal" edges $I_i \rightarrow I_k$ of $Mj$ as a complete subgraph;
enumerate all paths from MINUS to PLUS in $G$ (avoiding cycles);
if you find a path that doesn't traverse a nested copy, then it is a solution; otherwise expand each "internal" traversals of the nested mazes $Mj$ of each path:

Suppose that a path in the first enumeration is $MINUS \rightarrow A_{I_i} \rightarrow A_{I_j} \rightarrow B_{I_k} \rightarrow B_{I_h} \rightarrow PLUS$, then the path is a valid solution iif there is a path from $I_i \rightarrow I_j$ and from $I_k \rightarrow I_h$ in the original maze (graph $G$).

So we must expand the $A_{I_i} \rightarrow A_{I_j}$ and $B_{I_k} \rightarrow B_{I_h}$ traversals enumerating all the paths from $I_i$ to $I_k$ and from $I_k$ to $I_h$ in $G$.

Infinite loops are detected when we are enumerating all paths from $I_i$ to $I_k$ in an expansion of a path that in a previous stage already contained $... \rightarrow M_{I_i} \rightarrow M_{I_k} \rightarrow ...$ for some submaze $M$ (there are only $n^2$ possible expansions).

A solution is found if we find a path expansion that contains only inputs/outputs $I_i$; the maze has no solution if we cannot further expand the paths without loops.


Algorithm whose running time depends on P vs. NP Is there a known, explicit example of an algorithm with the property such that if $P\neq NP$ then this algorithm doesn't run in polynomial time and if $P=NP$ then it does run in polynomial time?

If you assume that $P=^?NP$ is provable in PA (or ZFC), a trivial example is the following:

Input: N   (integer in binary format)
For I = 1 to N do
begin
  if I is a valid encoding of a proof of P = NP in PA (or ZFC)
    then halt and accept
End
Reject

Another - less trivial - example that relies on no assumption is the following:

Input: x   (boolean formula)
Find the minimum i such that
  1) |M_i| < log(log(|x|))  [ M_1,M_2,... is a standard fixed TM enumeration]
  2) and  M_i solves SAT correctly
       on all formulas |y| < log(log(|x|))
          halting in no more than |y|^|M_i| steps
          [ checkable in polynomial time w.r.t. |x| ]
  if such i exists simulate M_i on input x
      until it stops and accept/reject according to its output
      or until it reaches 2^|x| steps and in this case reject;
  if such i doesn't exist loop for 2^|x| steps and reject.

If $P =NP$ the algorithm will soon or later - suppose on input $x_0$ - find the index of the polynomial time Turing machine (or a padded version of it) $M_{SAT}$ that solves SAT in $O( |x| ^ { |M_{SAT}| })$ and for all inputs greater than $x_0$ will continue to simulate it and halt in polynomial time (note that step 2 can also be checked in polynomial time). In other words if $P = NP$ the algorithm solves SAT in polynomial time on all but a finite number of instances.

If $P \neq NP$ the algorithm runs in exponential time.


Synchronizing sequences for rubik's cube? Are there any results on the existence of synchronizing sequences for a standard 3x3 rubik's cube? Like a proof that there are none? My google-skills failed me...

Synchronizing sequence over a finite state machine: a sequence of state transitions that leads the machine to a known unique final state independently of the (unknown) initial state.

In the Rubik's cube there are obviously no "self stopping" configurations: every move leads to a new configuration, so you are forced to look at the current configuration in order to decide the next move. This implies that a synchronizing sequence (as usually defined) cannot exist.

A trivial demonstration: suppose that $SSEQ = m_1 m_2 m_3 ... m_n$ is a synchronizing sequence of moves that leads to a solved Rubik's cube independently of the initial configuration. Now pick a wrong configuration and apply the reverse sequence $m^{-1}_n m_{n-1}^{-1} ... m_1^{-1}$ where $m_i^{-1}$ is the inverse of move $m_i$ (and is well defined because if you apply the same move to two different cube configurations you cannot obtain the same configuration). This reverse sequence leads to a unique configuration $c_0$. If you apply sequence $SSEQ$ to $c_0$ you obviously don't end to a solved Rubik's cube.

What you can do is to allow to stop every subsequence looking at the content of a particular cube's coordinate. For example run subsequence 1 until corner at (0,0,0) contains the red+yellow+blue block, then proceed to subsequence 2 (which will correctly position another block, and so on. In this case you can reach a known final configuration running a fixed sequence of moves made of subsequences that can stop looking at the content of a fixed sequence of blocks. This is very similar to what is usually called an homing sequence.

Perhaps another nice question is "What is the shortest sequence of moves and monitored coordinates that leads to a known final configuration in this modified homing version?".

For example to put a known block at monitored coordinate (0,0,0) (asterisk * in the figure), the length of the first trivial subsequence must be 28

F1.rotate, F1.rotate, F1.rotate
R4.shiftL, R6.shiftL, F1.rotate, F1.rotate, F1.rotate
R4.shiftL, R6.shiftL, F1.rotate, F1.rotate, F1.rotate
R4.shiftL, R6.shiftL, F1.rotate, F1.rotate, F1.rotate
C4.shiftDown, C6.shiftDown, F1.rotate, F1.rotate, F1.rotate
C4.shiftDown, C6.shiftDown, F1.rotate, F1.rotate, F1.rotate

EDIT:
Another interesting question (suggested by Tsuyoshi and Kaveh in the comments) arise if we consider the case in which the sequence of moves automatically stops when the cube is solved: if no information is gathered/stored during the moves then we must scan all cube's configurations (similar configurations obtained rotating the whole cube should be grouped in equivalence classes).

But what is the shortest sequence that scans all cube's configurations, or better does the configuration graph of the cube have a Hamiltonian path?.

This is a special case of a more general unsolved problem: for an arbitrary permutation group with a given generating set, is its Cayley graph Hamiltonian?

There are some good info available online, I cite the book: Adventures in Group Theory: Rubik's Cube, Merlin's Machine, and Other Mathematical Toys and the lecture notes by W.D.Joyner: Mathematics of the Rubik's cube (downloadable in pdf format).

Chapter 6 of the lecture notes is devoted to Cayley graphs and God's algorithm.


Derivation of cut rule in sequent calculus I searched internet but could not find any good weblink which shows how the cut rule for sequent calculus can be derived.

I found this paper but it uses implication elimination rule which I cannot find as a standard rule anywhere (see page 2).

Thanks in advance.

The fact that a system is complete for proving valid formulas without the cut rule doesn't mean you can derive the cut rule from other rules.

In fact it is not difficult to construct counter-examples. Consider
$\Rightarrow A \rightarrow B$ and $\Rightarrow A$. From these assumptions it would follow that $\Rightarrow B$. But you cannot derive it without using a cut.


Origins and applications of Theory A vs Theory B? In a couple recent questions (q1 q2), there has been discussion of "Theory A" vs "Theory B", seemingly to capture the divide between the study of logic and programming languages and the study of algorithms and complexity.

This terminology was new to me, and a quick web search didn't come up with any obvious references explaining it.

Does anyone know of a reference or references that explain the origin of this terminology, and what, if any, substantive benefit is intended to be derived from making this distinction?

It comes from the handbook on theoretical computer science, which had two volumes: A was for algorithms and complexity, and B was for logic and semantics.

Jukka, did ICALP predate this ? Or was it in response to this ?

As for benefits, I think there's always some utility in taxonomizing areas based on topics of interest, and forms of study. However, as with all taxonomizations, the problem comes when you forget to "go back up the tree and down the other side" :).

EDIT: as ICALP explicitly states, this division comes from the Elsevier journal Theoretical Computer Science, which itself predates the handbook, so I think that's a more accurate source.

EDIT ++: From the history of the EATCS comes this snippet about TCS, the journal:

  Since that time M. Nivat, who is still
  Editor-in-Chief has reported regularly
  to council and general assembly and
  occasionally in the Bulletin - e.g.
  when the split into sections A
  (automata, algebra und algorithms) and
  B (logic, semantics and related
  topics) was decided upon (Bulletin no.
  45, p.2,3, October 1991);

which yields 1991 as when this first started happening at the journal. However, the Handbook was first published in September 1990 !


Is there fast algorithm for finding min vertex-disjoint path cover of DAG graph of poset of pairs (x, y) where (x, y) < (u, v) iff x < u and y < v Let P is a poset of pairs (x, y) where (x, y) < (u, v) iff x < u and y < v. Let G is a DAG corresponding to poset P. Suppose I want to find some minimum vertex-disjoint path cover of G.

It is known that there is a general algorithm by reduction of this problem to maximal matching. But in this case P may have some specific properties, so may be there is some algorithm for doing this faster than matching.

Thanks in advance.

So if I'm interpreting your question you have a set of points in the Euclidean plane and you want to find a decomposition of the points into as few monotone chains as possible? This is called the "layers of maxima" problem and it is easily solved in time O(n log n) by a plane sweep algorithm that sweeps over the points from left to right, using a binary search tree to maintain the set of intersection points of the monotone chains with the sweep line and assigning each point in sweep order greedily to the highest monotone chain that it can be assigned to. See e.g. Buchsbaum and Goodrich, "Three-Dimensional Layers of Maxima", Algorithmica 2004, for a three-dimensional version that can still be solved in O(n log n) and references to earlier work on the problem.


Is the following restriction of cellular automata / tile assembly / CRN a known model? Consider the following model: we work in the $d$-dimensional grid $\mathbb{N}^d$, and we have an alphabet $\Sigma$.
The initial cell $(0,\ldots,0)\in \mathbb{N}^d$ is marked with some letter $\Sigma$, and from that we mark each cell with a letter from $\Sigma$ according to its immediate predecessors. That is, we have a function $f:\Sigma^d\to \Sigma$, and for each cell $(a_1,\ldots,a_d)$, we mark it with
$f(\sigma_1,\ldots,\sigma_d)$, where $\sigma_i$ is the labeling of the neighbor $(a_1,\ldots,a_i-1,\ldots, a_d)$.
This means that the marking is completely determined by $f$ and the initial symbol.
Note that at the edges, where there are fewer then $d$ neighbors, we ignore the missing values (technically, we can assume that anything outside $\mathbb{N}^d$ has some constant fixed marking).
I want to study certain properties of this model (specifically, I want to show that it is semilinear, in a sense). But I couldn't find any resources on it.
Specifically, I would like to know if this model is Presburger-definable.
However, it is a very natural restriction of several models:

Cellular automata: it can be thought of a single-state cellular automaton, that can only change the value of a cell once (i.e., a cellular transducer).
Tile Self-assembly: where the glue relations allow only a deterministic assembly, but the model is not two-dimensional.
Multidimensional subshifts: it's not really a shift, but it does have the same flavour of finite rules.
Chemical-reaction networks: I'm actually not sure if this is a restriction, but it seems somewhat related.

I'd appreciate any leads on this.

If you partition $\mathbb{Z}^d$ into the $(d-1)$-dimensional slices $S(n) := \{ \vec v | \sum_{k=1}^d \vec v_k = n \}$, then your model is essentially a spacetime diagram of the $(d-1)$-dimensional cellular automaton that maps $x|_{S(n)}$ to $x|_{S(n+1)}$. The initial configuration $x|_{S(0)}$ has a special quiescent state everywhere except at the origin. If the CA is linear over a field of characteristic $p$, then these diagrams are $p$-automatic; if not, they can be quite complex, since you don't restrict $f$ in any way. They are not necessarily semilinear in either case. For example, it's pretty easy to embed a computation history of an arbitrary Turing machine in the configuration.


Minimum ($\ell_1$ or $\ell_2$) norm of sum of edge length in multigraph over linear ordering of vertices Suppose we have a multigraph with vertex set $V$ where for each $v \in V$, $d_v > 0$ is the diameter of the vertex. We want to put a linear ordering on the set of vertices such it minimizes ($L_1$ or $L_2$ norm of) the sum of edge length when vertices are drawn on a line (according to that linear ordering). The vertices are non overlapping circles with diameter $d_v$ and each edge can start anywhere in the respective circles as long as it is confined to the boundary of the given circles and all the other edges start at the same position.

A physical interpretation of this would be that there are N balls connected with ropes (the rope can start anywhere inside the ball but every rope connected to that same ball must start from the same place too) We want to place the balls on a line such that the total length of the ropes used in minimized.

Is there any efficient algorithm known for this type of problem? How about approximation algorithms?

The $L_1$ problem with $d_v=1$ for all $v$ is a variant of the classical NP-hard minimum linear arrangement problem.   Charikar et al [SODA 2006] and independently Feige and Lee [IPL 2007] described polynomial-time $O(\sqrt{\log n} \log \log n)$-approximation algorithms via semidefinite programming.  Devanur et al [STOC 2006] proved an $\Omega(\log\log n)$ integrality gap for the semidefinite relaxation.


Does P = NP imply NP being a strict subset of PSPACE? Does $\textbf{P} = \textbf {NP}$ imply that $\textbf{NP} \subsetneq \textbf{PSPACE}$? Or, for a slightly stronger result, does it imply that $\textbf{NL} = \textbf P$?

No.  It is possible (as far as we know) that $\textbf{P} = \textbf{NP} = \textbf{PSPACE}$.

If $\textbf{P} = \textbf{NP}$, the polynomial hierarchy collapses, i.e., $\textbf{P} = \textbf{PH}$.  See also Can one amplify P=NP beyond P=PH? for an attempt to understand the limits of the implications of $\textbf{P} = \textbf{NP}$, and see Why doesn't P=NP imply P=AP (i.e. P=PSPACE)? for information about why it seems hard to derive the implication $\textbf{P} = \textbf{PSPACE}$.


Graph isomorphism with equivalence relation on the vertex set A colored graph can be described as tuple $(G,c)$ where $G$ is a graph and $c : V(G) \rightarrow \mathbb{N}$ is the coloring. Two colored graphs $(G,c)$ and $(H,d)$ are said to be isomorphic if there exists an isomorphism $\pi : V(G) \rightarrow V(H)$ such that the coloring is obeyed, i.e. $c(v) = d(\pi(v))$ for all $v \in V(G)$.

This notion captures the isomorphism of colored graphs in a very strict sense. Consider the case where you have two political maps of the same region but they use different color sets. If one asks if they are colored in the same fashion one would assume this to mean whether there exists a bijective mapping between the two color sets such that the colors of both maps coincide via this mapping. This notion can be formalized by describing colored graphs as tuple $(G,\sim)$ where $\sim$ is an equivalence relation on the vertex set of $G$. We can then say two such graphs $(G,\sim_1)$ and $(H,\sim_2)$ are isomorphic if there exists an isomorphism $\pi : V(G) \rightarrow V(H)$ such that for all pairs $v_1,v_2 \in V(G)$ it holds that
$$v_1 \sim_1 v_2 \text{ iff } \pi(v_1) \sim_2 \pi(v_2)$$

My question is whether this concept has been studied previously w.r.t. finding canonical forms etc. and if so under what name it is known?

The problem you describe has definitely been considered (I remember discussing it in grad school, and at the time already it had been discussed long before then), though I can't point to any particular references in the literature. Possibly because it is linearly equivalent to uncolored graph isomorphism, as follows (this is true even for canonical forms). Call the problem you describe EQ-GI.

GI is just the special case of EQ-GI where each graph has just one equivalence class consisting of all vertices.

In the other direction, to reduce EQ-GI to GI, let $(G, \sim_G)$ be a graph with equivalence relation with $n$ vertices, $m$ edges, and $c$ equivalence classes. Construct a graph $G'$ whose vertex set consists of the vertices of $G$, together with new vertices $v_1, \dotsc, v_c$, one for each equivalence class in $=_G$, as well as $n+c+1$ new vertices $w_0, \dotsc, w_{n+c}$. Connect the $w_i$'s in a path $w_0 - w_1 - w_2 - \dotsb - w_{n+c}$, connect each $v_i$ to $w_0$, and for every vertex in $G$, connect it to the corresponding equivalence class vertex $v_i$. Then $G'$ has at most $n + 2c + n +1 \leq O(n)$ vertices and can be constructed in essentially the same time bound. (It also has at most $m + n + c + (n+c+1) \leq m + 4n + 1 \leq O(m+n)$ edges - which is $O(m)$ for connected graphs - but that's somewhat less relevant since most GI algorithms have running times that essentially only depend on $n$.)

Update: Since there was some confusion in the comments, I'm adding here a sketch of the correctness of the above argument. Given $(G_1, \sim_1)$ and $(G_2, \sim_2)$, let $G_1'$ and $G_2'$ be the graphs constructed as above; let $v_{i,1}$ denote the vertex $v_i$ from above in $G_1'$, and $v_{i,2}$ the one in $G_2'$, and similarly for $w_{i,1}$ and $w_{i,2}$. If there is an isomorphism $G_1' \cong G_2'$, it must send $w_{i,1}$ to $w_{i,2}$ for all $i$, since in each graph $w_{n+c}$ is the unique vertex that is the endpoint of any path of length at least $n+c+1$. In particular, $w_{0,1}$ maps to $w_{0,2}$. Since the neighbors of $w_0$ that aren't $w_1$ are exactly the $v_i$, the isomorphism must map the set $\{v_{1,1},\dotsc,v_{c,1}\}$ to the set $\{v_{1,2},\dotsc,v_{c,2}\}$ (and in particular both $\sim_1$ and $\sim_2$ must have the same number, $c$, of equivalence classes). Note that the isomorphism need not send $v_{i,1}$ to $v_{i,2}$ for all $i$, but is allowed to permute the indices of the $v$'s so long as the corresponding equivalence classes can be mapped to one another. Conversely, based on this description of how isomorphisms between $G_1'$ and $G_2'$ can look, it is easy to see that if $(G_1, \sim_1) \cong (G_2, \sim_2)$ then this gives an isomorphism $G_1' \cong G_2'$.


Can Quarter-Subset Membership be decided space-efficiently? Consider the following decision problem.
Let $q = \sum_{i=0}^{n/4} \binom{n}{i}$ and let $(C_0^n, C_1^n,\dots,C_{q-1}^n)$ be a suitable enumeration of those subsets of $\{0,1,\dots,n-1\}$ that have at most $n/4$ elements.

  Quarter-Subset Membership
  Input: tuple of non-negative integers $(i,j,n)$ represented in binary
  Question: is $i \in C_j^n$?

By picking a "nice" enumeration $(C_i^n)$, can Quarter-Subset Membership be decided by a deterministic Turing machine using no more than $(0.99)n$ bits of workspace, for all large enough $n$?

Discussion

Let $\log x = \log_2 x$.
It is easy to enumerate all subsets of at most $k$ elements chosen out of $n$ by keeping track of $k$ indices of size $\lceil \log n \rceil$ bits each.
(See also the discussion in Knuth's TAOCP section 7.2.1.3.)
When $k$ is constant this is just $O(\log n)$ bits.
However, if we let $k = cn$ for some constant $c \le 1/4$, then such enumeration schemes use $\Omega(n\log n)$ space.
One can also use an $n$-bit characteristic vector together with a check for the number of bits set.
I'm interested in schemes that beat $n$ bits.

A closely related question is then:

  For positive $c$ satisfying the inequality $c\log(e(1+c)/c) < 1$, is there a code representing subsets of at most $cn$ elements chosen from $n$ that uses $dn$ bits for some constant $d < 1$, and can be decoded efficiently?

Note that for large enough $n$,
$$\sum_{i=0}^k\binom{n}{i} \le \left(\binom{n}{k}\right) = \binom{n+k-1}{k},$$
and since
$$\log\binom{n+k-1}{k} \le \log[(e(n+k-1)/k)^k],$$
when $k = cn$ then information-theoretically it follows that $d \le c\log(e(1+c)/c)$ would be achieved with a perfect code.
(This is less than $1$ if $0 < c \le 0.2728$.)
I am therefore looking for a reasonably clean code that can be manipulated without using lots of space.

To obtain a perfect code, one could pick some enumeration of the subsets, run an index through the enumeration in increasing order, and then obtain each combination by decoding the index.
However, decoding such a code when $k \ge \Omega(n/\log n)$ seems to require using at least $n$ bits of space for the enumerations I have looked at, such as via characteristic vectors ordered by increasing Hamming weight and then lexicographically, or via Gray codes.

There might be a way to do this with $o(n)$ space, but I think $(1-\varepsilon)n$ is more likely to be feasible.
Note that since $\log \binom{n}{cn} \ge cn\log(1/c)$, the information-theoretic lower bound is already $\Omega(n)$ bits, so this really is about whether $(1-\varepsilon)n$ can be achieved for some $\varepsilon > 0$.
A code that is nice enough (but not necessarily perfect) would seem to be enough to answer my question in the affirmative.
It might also be the case that Quarter-Subset Membership can be decided efficiently without explicitly constructing a code.
On the other hand, such an enumeration may not exist: for instance, every sequence of enumerations for values of $n$ might be inherently non-uniform, or it might be the case that any $(1-\varepsilon)n$-bit bound must be breached infinitely often.

I assume from the discussion that you are not actually interested in work space as claimed, but in total space including the size of the input. (Otherwise the trivial $n$-bit encoding scheme can be decoded in logarithmic space.)

Let $k$ be a sufficiently large constant, and consider the following encoding scheme for $X\subseteq\{0,\dots,n-1\}$. Split $\{0,\dots,n-1\}$ into $k$ blocks $B_u$, $u<k$, of size $n/k$ each, and put $X_u=X\cap B_u$. The encoding of $X$ consists of the sequence of the following numbers (written in binary) for each $u<k$:

the size $s_u=|X_u|$;
the number corresponding to $X_u$ in the combinatorial number system for $s_u$-size subsets.

As for the size of the encoding, assume $|X|\le n/4$. The numbers $s_u$ take $O(k\log(n/k))$ bits, which will be negligible. We have $s_u\le n/(3k)$ for at least $k/4$ of the $u$'s, in which case the encoding of $X_u$ takes about $H(1/3)\tfrac nk\approx0{.}92n/k$ bits; the remaining $X_u$ take at most $n/k$ bits each. The total is at most $0{.}98n$ bits.

Decoding amounts to deciding which block $i$ goes into, and then figuring out $X_u$; the latter be done easily in space $n/k+O(\log n)$, and one can reuse the space occupied by encodings of the remaining blocks (as long as the total space is at least $2n/k$, which is OK for $k$ large enough).

A better analysis shows that this scheme achieves space essentially $H(1/4)n\approx0{.}812n$: let $p_u=s_u/(n/k)$. Since $|X|/n\le1/4$, the average of $p_u$ over $u<k$ is at most $1/4$. The encoding of $X_u$ takes about $H(p_u)n/k$ bits. Now, the entropy function is concave, hence the average of $H(p_u)$ over $u<k$ is at most $H(1/4)$, and the total space is $H(1/4)n+O(\log n)$. This is optimal up to the $O(\log n)$.

There is of course nothing special about $1/4$. The same argument shows that for any constant $0<c<1/2$, there is an encoding scheme for $\le cn$-size subsets of $\{0,\dots,n-1\}$ that takes $H(c)n+O(\log n)$ bits, and can be decoded in-place. To some extent, it can even be used for $\le s(n)$-size subsets where $s(n)\ll n$, by taking a non-constant number of blocks ($k\ge 2/H(s(n)/n)$ or so), but then the $O(k\log(n/k))$ overhead gets more pronounced, and overtakes the main term when $s(n)$ drops below roughly $\sqrt n$.


Does “Second X is NP-complete” imply “X is NP-complete”? "Second $X$" problem is the problem of deciding the existence of another solution different from some given solution for problem instance.

For some $NP$-complete problems, the second solution version is $NP$-complete (deciding the existence of another solution for the partial Latin square completion problem) while for others it is either trivial (Second NAE SAT) or it can not be $NP$-complete (Second Hamiltonian cycle in cubic graphs) under widely believed complexity conjecture. I am interested in the opposite direction.

We assume a natural $NP$ problem $X$ where there is natural efficient verifier that verifies a natural interesting relation $(x, c)$ where $x$ is an input instance and $c$ is a short witness of membership of $x$ in $X$. All witnesses are indistinguishable to the verifier. The validity of witnesses must be decided by running the natural verifier and it does not have any knowledge of any correct witness ( both examples in the comments are solutions by definition).

  Does “Second $X$ is NP-complete” imply “$X$ is NP-complete” for all "natural" problems $X$?

In other words, Are there any "natural" problem $X$ where this implication fails?. Or equivalently,

  Is there any "natural" problem $X$ in $NP$ and not known to be $NP$-complete but its Second $X$ problem is $NP$-complete?

EDIT: Thanks to Marzio's comments, I am not interested in contrived counter-examples. I am only interested in natural and interesting counter-examples for NP-complete problems $X$ similar to the ones above. An acceptable answer is either a proof of the above implication or a counter-example "Second X problem" which is defined for natural, interesting, and well known $NP$ problem $X$.

EDIT 2: Thanks to the fruitful discussion with David Richerby, I have edited the question to emphasis that my interest is only in natural problems $X$.

EDIT 3: Motivation: First, the existence of such implication may simplify the $NP$-completeness proofs of many $NP$ problems. Secondly, the existence of the implication links the complexity of deciding the uniqueness of solution to the problem of deciding existence of a solution for $NP$ problems.

No,

Consider the problem "Find a subset of a set of integers S which sums to 0".

This problem is trivial, as one can return the empty set.

However, finding a second solution after returning the empty set is the well-known subset sum problem, which is known to be NP-complete.


What are some examples of secret sharing schemes actually being used in real-world applications? The concept of a secret sharing scheme is often attributed to Shamir (A. Shamir, How to share a secret, Comm. ACM, 22 (1979), pp. 612-613.) and Blakey (G. R. Blakey, Safeguarding cryptographic keys, in Proc. NCC, vol. 48, 1979, pp. 313-317.).

The overall idea is that some secret S is hidden from the participants who instead each receive a share si.  If every participant decides to cooperate, they each submit their share to a combiner, who reconstructs S from the shares si.

Papers on secret sharing schemes often refer to real-world applications (such as bank safes).  But I suspect, these are hypothetical "real-world" applications (i.e. the next floor down in the ivory tower) and very much doubt that they could actually name a bank (or any other company) that actually uses a secret sharing scheme.  Question:  What are some actual real-world examples?

Ideally, I would like an answer to contain:  At company X they use secret sharing scheme Y to safeguard Z (see ABC for more details).

(Almost) Every modern HSM (hardware secure module, for cryptographic applications) uses Shamir secret sharing. So, no, secret sharing use is wide spread.


Best upper bound on rate for q-ary codes Among the many upper bounds for families of codes in $\mathbb F _2 ^n$, the best known bound is the one by McEliece, Rodemich, Rumsey and Welch (derived through a linear programming relaxation approach) which states that the rate $R(\delta)$ corresponding to a relative distance of $\delta$ is such that:
\begin{equation*}R(\delta) \leq H_2(\frac{1}{2}-\sqrt{\delta(1-\delta)}) \end{equation*}
where H is the (binary) entropy function.
(A slight improvement of the above exists in the binary case, but within the same framework)
In the case of q-ary codes, i.e. codes over $\mathbb F _q ^n$, the above bound is generalized to:
\begin{equation*}R(\delta) \leq H_q(\frac{1}{q}(q-1-(q-2)\delta-2\sqrt{(q-1)\delta(1-\delta)})) \end{equation*}
My question is as follows:
For larger alphabet size q, the above bound seems to weaken significantly. In fact, observing the growth of the above bound as $q \rightarrow \infty$, we see that:
\begin{equation*} R(\delta) \leq 1-\delta+\mathcal{O}(\frac{1}{\log{q}})  \end{equation*}
Thus, it seems to get worse than even the Singleton bound $R(\delta) \leq 1-\delta$.

So which is the best bound for large alphabet size $q$? Or am I wrong in the above conclusion that the MRRW bound is worse than even the Singleton bound for larger $q$?
Also, could someone direct me to references for comparisons of different upper bounds for larger $q$? I am able to find reliable comparisons only for $q=2$.

This is not the best bound even for $q=2$; in fact, this is not the best bound derived from the Delsarte linear program; see the paper "On the optimum of Delsarte's linear program" by Samorodnitsky (1998).

Thus, a better analysis of the linear program is likely to improve the bounds over larger $q$.  Even for $q=2$, this is a complicated analysis, so I don't know whether anybody has performed it for larger $q$.


Complexity of optimization over unitary group What is the computational complexity of optimizing various functions over the unitary group $\mathcal{U}(n)$?

A typical task, arising often in quantum information theory, would be maximizing a quantity of type $\mathrm{Tr}AUBU^{\dagger}$ (or higher order polynomials in $U$) over all unitary matrices $U$. Is this type of optimization efficiently (perhaps approximately) computable, or is it NP-hard? (maybe this is well known, but I've been unable to find any general references)

Sorry I'm late!  In quantum computing theory, there are lots of examples of optimization problems over the unitary group that, surprisingly (at least to me), are solvable in (classical) polynomial time by reduction to semidefinite programming.

Here was an early example: solving a problem of mine from 2000, in 2003 Barnum, Saks, and Szegedy showed that Q(f), the quantum query complexity of a Boolean function f:{0,1}n→{0,1}, can be computed in time polynomial in 2n (i.e., the size of f's truth table).  I had thought about this but couldn't see how to do it, since one needs to optimize the success probability over all possible quantum query algorithms, each one with its own set of (possibly 2n-sized) unitary matrices.  Barnum et al. reduced to SDP by exploiting a "duality" between unitary matrices and positive semidefinite matrices, the so-called Choi-Jamiolkowski isomorphism.  For a more recent and simpler SDP characterizing Q(f), see Reichardt's 2010 paper showing that the negative-weight adversary method is optimal.

Another important case where this trick has been exploited is in quantum interactive proof systems.  While it's not intuitively obvious, in 2000 Kitaev and Watrous proved that QIP ⊆ EXP. by reducing the problem of optimizing over the exponential-sized unitary matrices that arise in a 3-round quantum interactive proof system, to solving a singly-exponential-sized SDP (again, I think, using the Choi-Jamiolkowski isomorphism between mixed states and unitary matrices).  The recent QIP=PSPACE breakthrough came from showing that that particular SDP could be approximately solved even better, in NC (i.e., by log-depth circuits).

So, whatever your specific optimization problem involving the unitary group, my guess is that it can be solved faster than you think -- if not in some even simpler way, then by reduction to SDP!


Hierarchies in regular languages Is there any known "nice" hierarchy $L_0 \subseteq L_1 \subseteq L_2 \subseteq \dots$ (may be finite) inside the class of regular languages $L$? By nice here, the classes in each hierarchy capture different expressiveness / power / complexity. Also, the membership of each class is "nicely" demonstrated by some elements (unlike star height problem that may be problematic).

Thank you!

Here is a list of several hierarchies of interest, some of which were already mentioned in other answers.

Concatenation hierarchies

A language $L$ is a marked product of $L_0, L_1, \ldots, L_n$ if
$L = L_0a_1L_1 \cdots a_nL_n$ for some letters $a_1, \ldots, a_n$.
Concatenation hierarchies are defined by alternating Boolean operations and polynomial operations (= union and marked product).
The Straubing-Thérien hierarchy (starting point $\{\emptyset, A^*\})\ $ and the dot-depth hierarchy (starting point $\{\emptyset, \{1\}, A^+, A^*\})\ $ are of this type, but you can take other starting points, notably the group languages (languages accepted by a permutation automaton).

Star-height hierarchies

The general pattern is to count the minimal number of nested stars needed to express a language starting from the letters, but several variants are possible, depending on the basic operators you allow. If you only allow union and product, you define the restricted star-height, if you allow union, complement and product, you define the (generalised) star-height and if you allow union, intersection and product you define the intermediate star-height. There are languages of restricted star $n$ for every $n$ and on can effectively compute the star-height of a given regular language. For the star-height, star-height $0$ is decidable (star-free languages), there exist languages of star-height $1$, but no language of star-height $2$ is known! No result is known on the intermediate star-height. See this paper for an overview.

Logical hierarchies

There are many of them, but one of the most important one is the so-called $\Sigma_n$ hierarchy. A formula is said to be a $\Sigma_n$-formula if it is equivalent to a formula of the form $Q(x_1,...,x_k)\varphi$ where $\varphi$ is quantifier free and $Q(x_1,...,x_k)$ is a sequence of $n$ blocks of quantifiers such that the first block contains only existential quantifiers (note that this first block may be empty), the second block universal quantifiers, etc. Similarly, if $Q(x_1,...,x_k)$ is formed of $n$ alternating blocks of quantifiers beginning with a block of universal quantifiers (which again might be empty), we say that $\varphi$ is a $\Pi_n$-formula. Denote by $\Sigma_n$ (resp. $\Pi_n$) the class of languages which can be defined by a $\Sigma_n$-formula (resp. a $\Pi_n$-formula) and by $\mathcal{B}\Sigma_n$ the Boolean closure of $\Sigma_n$-languages. Finally, let $\Delta_n = \Sigma_n \cap \Pi_n$.
The general picture looks like this

One needs of course to specify the signature. There is usually a predicate $\mathbf{a}$ for each letter (and $\mathbf{a}x$ means there is a letter $a$ in position $x$ in the word). Then one can add a binary symbol $<$ (the corresponding hierarchy is the Straubing-Thérien hierarchy) and also a successor symbol (the corresponding hierarchy is the dot-depth hierarchy). Other possibilities include a $Mod$ predicate, to count modulo $n$, etc. See again this paper for an overview.

Boolean hierarchies

The general pattern (which is not specific to regular languages) is due to Hausdorff. Let $\mathcal{L}$ be a class of languages containing the empty set and the full set, and closed under finite intersection and finite union. Let
$\mathcal{D}_n(\mathcal{L})$ be the class of all languages of the form
\begin{equation}
   X = X_1 - X_2 + \cdots \pm X_n
\end{equation}
where $X_i\in \mathcal{L}$ and $X_1 \supseteq X_2\supseteq X_3 \supseteq \cdots \supseteq X_n$. Since $\mathcal{D}_n(\mathcal{L}) \subseteq \mathcal{D}_{n+1}(\mathcal{L})$, the classes $\mathcal{D}_n(\mathcal{L})$
define a hierarchy and their union is the Boolean closure of $\mathcal{L}$. Again, various starting points are possible.

Group complexity

A result of Krohn-Rhodes (1966) states that every DFA can be simulated by a cascade of reset (also called flip-flop) automata and automata whose transitions semigroups are finite groups.
The group complexity of a language is the least number of groups involved in such a decomposition of the minimal DFA of the language. Languages of complexity $0$ are exactly the star-free languages and there exist languages of any complexity. However, no effective characterisation of the languages of complexity $1$ is known.

Hierarchies inherited from circuit complexity

The starting point is the nice article $[1]$ which show in particular that the class $AC^0 \cap Reg$ is decidable. Let $ACC(q) = \{ L \subseteq \{0,1\}^* \mid L \leqslant_{AC^0} MOD_q\}$, where $MOD_q = \{u \in \{0,1\}^* \mid |u|_1 \equiv 0 \bmod q\}$. If $q$ divides $q'$, then $ACC(q) \subseteq ACC(q')$. An interesting question is to know whether $ACC(q) \cap Reg$ is decidable for any $q$.

$[1]$ Barrington, David A. Mix; Compton, Kevin; Straubing, Howard; Thérien, Denis. Regular languages in $NC^1$. J. Comput. System Sci. 44 (1992)


Is there an $\mathcal{L}$-theory and a formula $\phi$ for which Kolmogorov(proof($\phi$)) $<$ Kolmogorov($\phi$)? Are there a complete decidable $\mathcal{L}$-theory, a formula $\phi$ and a proof of $\phi$ for which the Kolmogorov complexity of the proof of $\phi$ is less than the Kolmogorov complexity of $\phi$?

Proofs in the proof systems I have seen so far are of the form:

mathematical reasoning
therefore $\phi$

Hence our intuition tells us that the Kolmogorov complexity of the proof has to be at least the Kolmogorov complexity of $\phi$. But this intuition does not prove any statement formally and it does not exclude the possibility of having a proof system where $p$ would be a proof of $\phi$ while Kolmogorov($p$) < Kolmogorov($\phi$) or even Kolmogorov(mathematical reasoning concatenate $\phi$) < Kolmogorov($\phi$).

In most "standard" proof systems, the formula $\varphi$ being proved is usually part of the proof itself by definition of the proof system, in which case for all $\varphi$, $K(\varphi) \leq K(\text{proof}) + O(1)$ (the extra constant is for the part of the program which says, basically, "extract the last line of the proof" - anyways, additive $O(1)$ errors are the best one can hope for in Kolmogorov complexity).

Even in a proof system where all that is required is that the formula $\varphi$ appear somewhere amongst the lines of the proof $\pi$, one can still get $K(\varphi) \leq K(\pi) + O(\log|\pi|)$, where here the extra $\log|\pi|$ bits are used to describe the index $i$ of the line of the proof that corresponds to $\varphi$.

In the much more general Cook-Reckhow style of proof system (or its computable analog) - that is, a polynomial-time computable function $f$ (resp., just a computable function $f$) whose range is exactly the set of true sentences of your theory - again, $K(\varphi) \leq K(\text{proof}) + O(1)$, where here the $O(1)$ extra bits describe the function $f$.

(Note that the trick of hard-coding certain tautologies into your proof system, pointed out by Kaveh, is handled by this latter case, as the hard-coded tautologies must be encoded directly into $f$, so they contribute to/are handled by the $O(1)$.)


Applying Expectation Propagation to Factor Graph Expectation Propagation(EP) is now quite a standard technique to approximate marginal in graphical model. Moreover, EP can replace sum-product algorithm in factor graph. For this reason, I try to understand it by using very simple model but because of my limitation of knowledge, the result could not be reached. So would you please revise my progress to show me my errors?

My problem is simple. $x_1$ is the variable which is followed Gaussian distribution with the mean $\alpha$ and variance $\beta$. $x_2$ is the variable which satisfies $x_1 = x_2$. So the factor graph can be represented by

Gaussian ---$x_1$ ---- $f(x_1, x_2) $--- $x_2$

f is the factor function in factor graph and it is Dirac delta function.

$f(x_1, x_2) = \delta(x_1 - x_2)$

Based on the properties of factor graph, we have:

$p(x_1, x_2) = g(x_1) f(x_1, x_2)$

with $g(x_1)$ is the Gaussian distribution. When we take the integral over the variable $x_1$ of $p(x_1, x_2)$, we get that the marginal of $x_2$ is the Gaussian distribution with the same parameters with $x_1$.

However, I want to use EP technique to solve this problem. First of all, I will separate $f$ here like in Tom Minka's thesis

Gaussian ----- $x_1$ ------ $\tilde{f}_1(x_1)$  $\tilde{f}_2(x_2)$ ----- $x_2$

Now, I want to find the function $q(x)$ that is

$q(x_1, x_2) = g(x_1) \tilde{f}_1(x_1) \tilde{f}_2(x_2)$

$q$ is the approximate function of $p(x_1, x_2)$

I want to refine the function $\tilde{f}(x_1, x_2) = \tilde{f}_1(x_1)\tilde{f}_2(x_2)$, environment without $f$ is calculated

$q^{\f}(x_1, x_2) = g(x_1)$

so

$\hat{p}(x_1, x_2) = q^{\f}(x_1, x_2) f(x_1, x_2) = g(x_1) f(x_1, x_2)$

$\hat{p}(x_1) = g(x_1) \int_{x_2} f(x_1, x_2) dx_2$

$\hat{p}(x_2) = \int_{x_1} f(x_1, x_2) dx_1$

$q^{new} (x_1, x_2) = \hat{p}(x_1) \hat{p}(x_2)$

then

$\tilde{f}(x_1, x_2) = \frac{q^{new}(x_1, x_2)}{q^{\f}} = \int_{x_1} f(x_1, x_2) dx_1 \int_{x_2} f(x_1, x_2) dx_2$

so

$\tilde{f}_1(x_1) = \int_{x_2} f(x_1, x_2) dx_2$

$\tilde{f}_2(x_2) = \int_{x_1} f(x_1, x_2) dx_1$

Then I guess $\tilde{f}_1$ and $\tilde{f}_2$ are convergence, so

$q(x_1, x_2) = g(x_1) \int_{x_1} f(x_1, x_2) dx_1 \int_{x_2} f(x_1, x_2) dx_2$

Hence, I get stuck at this point. Would you please show me, what wrong did I do?

Thank you and looking forward to seeing your helps

The way you are doing is not quite correct. Take a look at these tutorials
 -  http://homepages.inf.ed.ac.uk/csutton/publications/ep-tutorial.pdf
 -  http://web.engr.illinois.edu/~khashab2/learn/ep.pdf

Go over the algorithms which show the EP procedures. Also note the way they explain the projection of the distributions using KL projection.


Is there an example of a non context-sensitive language? I know $CSL\subset UL$ can be demonstrated by reduction to the absurd, but I've been trying to find a language that is in Type 0 ($UL$) and not in Context-Sensitive Languages ($CSL$).

Is there any language with such restrictions that isn't a Context-Sensitive language?

Type 0 grammars denote exactly recursively enumerable languages, and CSL = NSPACE[$n$] (e.g., Wikipedia).  Thus, your favorite proof of the Space Hierarchy Theorem gives an explicit language in, say, NSPACE[$n^2$] \ NSPACE[$n$], thus in UL \ CSL.


Humanifying computer-generated or computer assisted proofs I remember reading a blog post displaying two versions of the same proof, one written by a human and the other by a machine, and asked the readers to tell which is which. Trying to google the post again, I can't seem to find the right keywords; most things just direct me to pages on computer generated or computer assisted proofs.

So I'm wondering if anyone else remembers such a post, or better yet, can direct me to some surveys or other materials on this subject.

You are probably thinking of Gower's work with Ganesalingam, based on the latter's MSc dissertation (1). Gowers blogged about this in (2) and other places, and they've written a paper on the subject (3).

There is other work in that direction, for example from the interactive proof assistant community. The most well-known example here might be the Isar language (4). This is quite an active area of research, see e.g. (5). I know that this is also pursued by more linguistics oriented researchers, but I don't have references handy.

M. Ganesalingam, A Language for Mathematics.
W. T. Gowers, An experiment concerning mathematical writing.
M. Ganesalingam, W. T. Gowers, A fully automatic problem solver with human-style output.
M. Wenzel, Isabelle/Isar - a versatile environment for human-readable formal proof documents.
F. Wiedijk, A Synthesis Of The Procedural And Declarative Styles Of Interactive Theorem Proving.


Max-sum graph-partition for maximizing intra-edge weights? I would like to know if the following problem has already been studied, and if so how is it called. In particular I'm interested in approximability results.

Input: A graph G with negative or non-negative integer weights on edges.

Output: A partition $P=\{P_1, ..., P_K\}$ of $V(G)$

Measure (to maximize): The sum of the weights for the edges with both endpoints in the same set of P, i.e.:

$$
M(P)=\sum_{i=1}^k \sum_{u,v\in P_i} w\left( u,v \right)
$$

where $w$ is the edge-weight function.

Thanks in advance for any suggestion.

I will consider the case of non-negative weights only. As I mentioned in the comment the problem is related to the minimum k-way cut problem where the goal is to partition a given graph G into k non-trivial components to minimize the number (or weight in the weighted case) of edges crossing the partition. This is the same as maximizing the number of edges in the partitions. Since k-way cut is NP-Hard the maximization problem is also NP-Hard. However, for fixed $k$, $k$-way cut can be solved in polynomial time. In terms of approximation here is an idea to get a simple $(1-2(k-1)/n)$-approximation which is good if $k$ is small compared to $n$. To see this, simply take the partition to be the $k-1$ smallest degree vertices and the rest of the vertices. In terms of the k-way cut the # of edges cut by this partition is at most $2(k-1)/n \cdot |E|$. Thus the number of edges remaining inside the large piece is at least $(1- 2(k-1)/n) |E|$.

Update: If the weights can be negative then I believe the problem is inapproximable via a reduction from k-coloring. Given a graph $G$, set each edge's weight to be $-1$. Thus we are seeking a $k$-partition to minimize the number of edges inside the parts. If $G$ is k-colorable then we can achieve 0, otherwise it will be at least 1. In terms of the negative weights the max value will be 0 if $G$ is k-colorable, otherwise no more than -1.


Max-cut equivalence with most likely assignment to an Ising model Ising Model

$$
Pr(x; \lambda) = \frac{1}{Z(\lambda)} \exp \left( \sum_{ij \in E} \lambda_{ij} x_{ij} \right)
$$

In which $\lambda_{ij} \in \mathbb{R}$, and
$$
x_{ij} =
\begin{cases}
1 & x_i = x_j\\
-1 & x_i \neq x_j
\end{cases}
$$

and we are looking for

$$
x^* = \arg\max_x Pr(x; \lambda)
$$

This is proven to be NP-Complete.

Max Cut

Given the graph $G(V,E)$ and non-negative weights $w_{ij} \in E $ the goal is to find the set of vertices $S$ such that we maximize the the weight of edges in the cut $(S, V \setminus S)$ (the edges with the start-point in $S$ and end-point in $V\setminus S$).
More formally, by assuming $w_{ij} = 0, \forall e_{ij} \notin E $, we dote the weight of the cut by $w(S, V \setminus S) = \sum_{i \in S, j \in V \setminus S} w_{i,j}$

This is proven to be NP-Complete.

Min Cut

Exactly like Max-Cut, but the goal is to minimize the weight of the cut.

The problem could be solved in polynomial time using its max-flow formulation.

Problem Statement

In [1] (Page 16, last paragraph) it is mentioned that "finding the most likely assignment in an Ising model is equivalent to a cut problem. For example, if  $\mu \leq 0$, then the MAP assignment for graph $G = (V; E)$ corresponds to the maximum cut of $G$ with edge weights $\lambda$."

I am looking for the direct conversion between the two problems. The 2nd sentences (Started by "For example") also doesn't make sense to me.

On the other hand in Page 20 of [1] (Second paragraph), it is mentioned that:

"In the positive side, MAP inference in Ising models with ferromagnetic potentials, or
positive edge weights, is equivalent to the minimum cut problem, which can be solved in
nearly linear time (Karger, 2000)"

I'd interpret this as, Min Cut (which is Poly-time) is special case of MAP inference. Again, this is a little vague.

[1] http://cs.nyu.edu/~dsontag/papers/sontag_phd_thesis.pdf

Finding the most likely assignment in the Ising model is equivalent to maximum cut, so forget about minimum cut for a minute.

In the formulation you give for the Ising model, we are trying to maximize $\sum_{ij\in E}\lambda_{ij}x_{ij}$, where $x_{ij}=1$ if $x_i=x_j$ and $x_{ij}=-1$ otherwise.  In maximum cut, we take each edge weight $w$ and try to maximize $\sum_{ij\in E}w_{ij}(-x_{ij})$ -- this is equivalent to maximizing the weight of the cut because the total weight remaining is completely determined by the cut.  So we just want to set $w_{ij}=\lambda_{ij}$ to make an equivalent formulation.

For minimum cut, the problem doesn't make any sense unless you have fields in the Ising model, either local or global.


An example of a totally computable function that is not definable in system T? Could you give me an example of a totally computable function of type N × N → N that is not definable in System T? Thanks.

Interpreters for T are not definable in T, thanks to the incompleteness theorem.

Concretely, fix a Godel encoding, and then let $f$ be the function which takes a pair consisting of a Godel-encoding of a closed term of type $\mathbb{N} \to \mathbb{N}$, and a natural number in $\mathbb{N}$, and returns the value of the application. This function is not definable in T. It's a worthwhile exercise to work out how you can use a self-interpreter to define an infinitely looping program.


Test set and benchmarks for linear programming I am searching for test instances and benchmarks for linear programming, in particular, when solved by a simplex method and implemented with floating-point arithmetic.

This includes test suites, to verify my implementation of the simplex method, and benchmarks to measure the performance. The performance measure relevant for me is the number of steps on the vertex graph, rather than absolute clock time. Therefore medium size instances that do not induce to much ill-conditioning would suit me best.

The standard reference is probably Hans Mittelmann's page. Note, however, that the number of simplex iterations performed will depend on the pivoting rule and how the code deals with degeneracy.


Inapproximability of $(\alpha, \beta)$ bi-criteria approximation An $(\alpha, \beta)$ bi-criteria approximation algorithm for $k$-center is defined as an algorithm that returns a solution whose value is $\beta \cdot OPT$ ($OPT$ being the optimal solution for the $k$-center instance) using at most $\alpha \cdot k$ centers.

My question is: Given that finding a $(1,1)$bi-criteria approximation (which is basically just the optimal solution to the $k$-center problem, known to be $NP$-hard) is $NP$-hard, is it also true that finding a $(c, 1)$ bi-criteria approximation is $NP$-hard, where $c$ is a positive constant?

I've found that it is possible to have a $(\log k, 1)$ approximation for $k$-center, but not seen any negative results for a $(c, 1)$ bi-criteria approximation. I would appreciate if I can get pointers to a reference that I may have missed, or an outline of the proof sketch if its something trivial.

This problem generalizes dominating set: given an unweighted graph, there exists a set of k centers such that all other vertices are at distance 1 from them if and only if there exists a dominating set of size k.

Dominating set is hard to approximate with a ratio better than $\ln n$. In the above observation the optimal value for the k-center problem is either 1 or at least 2. Let $A$ be a $(c,2-\epsilon)$ bi-criteria approximation for $k$-center for some $c < \ln n$. If a dominating set of size $k$ exists, then the corresponding $k$-center problem would have optimum cost of 1, and $A$ would return a solution of cost at most $2-\epsilon$ using at most $k \ln n$ centers. Thus, $A$ can be used to find a $\ln n$ approximation for dominating set, which is known to be not possible. Therefore, I think that no $(c,2-\epsilon)$ bi-criteria approximation can exist for $c<\ln n$.


Bounds on the size of NFA for $r$-skip $k$-distinct language This question is about an extension of a language discussed in this question.

We define the $r$-skip $k$-distinct language as follows:

$$L_{r,k}=\{\sigma_1\sigma_2\cdots \sigma_{rk}\in\Sigma^{rk} | \forall i\neq j\in [rk],i=j \mod r\implies \sigma_i \neq\sigma_j\}$$

That is, the set of letters whose distance is a multiplication of $r$ are different.

This language is finite and therefore regular. Specifically, if $|\Sigma|=n$, then $|L_{r,k}|=$$({n\choose{k}}\cdot k!)^r$.

For $r=1$ we get the language $L_{k-distinct}$ defined in the linked question.

A natural NFA build for $L_{r,k}$ uses the color coding scheme and for a $(|\Sigma|,k)$-perfect hashing family $\mathcal F$ (i.e. mapping the letters into $k$ indices) selects a hash function $f\in \mathcal F$ by an epsilon transition and then verifies that each set of letters $\Sigma_i = \{\sigma_j|i=j \mod r\}$ is distinct.

Such perfect hashing family build of size $O(e^{k+\log^3 k}\cdot n\log n)$ is known

The resulting automaton is of size $O((2e)^{r(k+O(\log^3 k))}\cdot n\ \text{polylog}\ n)$, which is the same as we would get for $L_{1,rk}$ (which is $L_{rk-distinct}$) by using the same approach.
(The reason for this size, at least in a naive build, is that the automaton state have to encode which of the $k$ colors we've seen for each of the $r$ letter sets).

A more careful build would give $O(4^{r(k+O(\log^2 k))}\cdot n\ \text{polylog}\ n)$ sized automaton (same goes for $L_{1,rk}$).

This sounds wasteful, as a lot fewer comparison are needed as $r$ grows larger (and $rk$ is constant).

What is the smallest automaton we can build for $L_{r,k}$?

I detail the comment below, as you could be interested in this answer.
I don't know about NFA, but if your goal is to represent this language with a small automaton,  you could use the model of alternating automata, or AFA.

Intuitively, DFA are with $0$ player: the run is updated automatically, NFA are with $1$ player who has to choose a good run, and AFA are played by two players: one tries to accept, the other to reject. The word is in the language if the "good" player (who wants to accept) has a winning strategy on this word. This does not increase the expressive power of automata.

Here, you have an AFA with essentially $kr (\log n)^k$ states:
At one point the opposite player can guess that some letter with same position modulo $r$ will be equal to the current one.
Then the "good" player guesses $k$ bit positions of the current letter (this requires $(\log n)^k$ memory) : one which will be different for each later equivalent position. Then we just have to check that one of these bits is indeed different every $r$ positions.


Some consequences of the Roychowdhury-Orlitsky-Siu result from 1994 This pertains to the proof of theorem 1.1 in this paper, http://dl.acm.org/citation.cfm?id=2897636

So Roychowdhury-Orlitsky-Siu had shown that the number of depth $2$ linear threshold gate circuits mapping $\{0,1\}^n \rightarrow \{0,1\}$ and of size $s \geq n$ is $2^{O(n^2s)}$. I think I do understand the proof of this theorem but its not clear to me as to how the following two corollaries seem to be immediately following from this,

That for all $\epsilon >> \sqrt{\frac{n}{2^n}}$ with probability at least $1-\epsilon$ a uniformly at random chosen $n-$bit Boolean function is such that it cannot be matched on more than $(\frac{1}{2} + \epsilon)$ fraction of the inputs by a depth $2$ linear threshold circuit of size $s \leq o(\frac{\epsilon^2 2^n}{n^2})$
That for all $\epsilon >> \sqrt{\frac{\log n}{n}}$ there exists a constant $c$ small enough such that with probability at least $1-\frac{\epsilon}{3}$ a uniformly at random chosen $\lfloor \log (\frac {n}{2} )\rfloor-$bit Boolean function is such that on $(\frac{1}{2}+\frac {\epsilon}{3})-$fraction of the inputs it is not matched by any depth $2$ linear threshold circuit of size $s \leq \frac{c \epsilon^2 n }{\log ^2 n}$

Can someone kindly put in an explanatory proof for the above two statements?

Apparently the second of the above statements is either equivalent to or implies that if the $\lfloor \log (\frac {n}{2} )\rfloor-$bit Boolean function picked is such that it indeed cannot be matched on $(\frac{1}{2}+\frac {\epsilon}{3})-$fraction of the inputs by any depth $2$ linear threshold circuit of size $s \leq \frac{c \epsilon^3 n^{\frac {3}{2}} }{\log ^3 n}$ then with probability at least $1-\frac {\epsilon}{3}$ this function's truth table is the same as an $\frac{n}{2}$-bit string picked uniformly at random. I don't understand why!

Let $f\colon \{0,1\}^n \to \{0,1\}$, and let $g\colon \{0,1\}^n \to \{0,1\}$ be chosen uniformly. Then $\Pr[f=g] \sim 2^{-n}\mathrm{Bin}(2^n,1/2)$, and so a Chernoff bound shows that
$$
\Pr_g[\Pr[f=g] \geq \tfrac{1}{2}+\epsilon] \leq e^{-2\epsilon^2 2^n}.
$$
Now suppose that $f$ goes over all $2^{O(n^2s)}$ circuits of size $s$. The probability that one of them has correlation at least $\frac{1}{2}+\epsilon$ with $g$ is at most $e^{O(n^2s) - \Omega(\epsilon^2 2^n)}$. If $s = o(\frac{\epsilon^22^n}{n^2})$ then this probability is $e^{-\Omega(\epsilon^2 2^n)}$, which is smaller than $\epsilon$ for $\epsilon = \omega (\sqrt{n/2^n})$. We obtain $\sqrt{n/2^n}$ by approximately solving $e^{-\epsilon^2 2^n} = \epsilon$: rearranging, we get $\frac{\epsilon^2}{\log(1/\epsilon)} = 2^{-n}$, which shows that $\epsilon \approx 2^{-n/2}$ and so $\log(1/\epsilon) \approx n$. Plugging in the approximation for $\log(1/\epsilon)$, we see that $\epsilon \approx \sqrt{\log(1/\epsilon) 2^{-n}} \approx \sqrt{n/2^n}$.

This proves the first corollary. For the second corollary, substitute $n := \log (n/2)$.


How do I get started in theoretical CS ? I'm a freshmen studying computer science and I already know that I want to go into academia with focus of theoretical comp sci. I already read some of papers referenced in this question and this question convinced me further.

What should I be doing now, as an undergrad, to get involved in the field? What can I do to prepare for research in the field?

Let me provide an answer from the other side. I've had a few undergraduate student researchers work with me. The experience has been mixed: with some, I have published papers and have work in progress, and with others, we never really got off to any kind of start.

It's great that you know what you want to do. As an undergraduate, here's what you should be focusing on:

Building the mathematical "muscles" that will help you when you start working on problems in earnest
Exploring different aspects of theoretical CS to get a sense of the area and figure out what kinds of problems/areas you find interesting
(depending on the area) working out some puzzles, maybe solving some exercises, and working your way up to a research question.

Find a professor to guide you, and PUT IN THE TIME ! The hardest thing you'll face is creating the open time to think about problems in the midst of classwork, assignments and exams. But you need to reserve blocks of time for your independent study and research otherwise it will be very hard to make any kind of progress. How you do this is upto you: maybe you can find a professor to meet with you once a week and set intermediate goals for you, or maybe you can set a long term goal (working through X exercises from a text) and work steadily on that.


multi-party Communication complexity of "Set Partition problem" In an application I'm considering, I need to know the communication complexity of the following problem:

Given $n$, let $S$ be the set of integers from $1$ to $n$. Alice, Bob, and Carol each receives a subset of $S$, denoted by $A$, $B$, and $C$, respectively. They want to check whether $A$, $B$ and $C$ form a partition of $S$, i.e., they are disjoint and their union is $S$.

I'm particularly interested in the case of 3 parties but other cases would be interesting as well.  Note that for the case of 2 parties, the problem is equivalent to EQUALITY problem so it has $\Omega(n)$ lower bound for deterministic protocols but $O(\log n)$ upper bound for randomized protocols.

My question is whether this problem is known before. If you know any problems that might be related, I would be interested to know as well.

A linear lower bound on deterministic CC follows by fixing one of the sets to be empty.

For a randomized logarithmic upper bound, first note that this problem can be reduced to the problem asking whether the sum of three $3n$-bit numbers is exactly $2^{3n}-1$.  This one can be solved in $O(\log n)$ randomized communication by the players operating mod a random $O(\log n)$-bit prime.


For what c is division by c in AC0? Suppose that our input is a binary $x$ and we have to output $\lfloor x/c \rfloor$, where $c$ is some constant integer.
This is just a shift if $c$ is a power of two, but what about other numbers?
Can we do it with a constant depth circuit for every $c$?
What about $c=3$?

ps. I know that computing $x\bmod c$ is hard, but this seems unrelated.

Addition and subtraction of binary numbers are in $\mathsf{AC^0}$.

For any constant number $c$,
$x \bmod c$ is $\mathsf{AC^0}$ reducible to division by $c$ ($\lfloor x/c \rfloor$):
$$x \bmod c = x -
(\overbrace{\lfloor x/c \rfloor + \cdots + \lfloor x/c \rfloor}^{c \text{ times}}) $$

It is known that $x \bmod c$ is hard for $\mathsf{AC^0}$ for any $c$
which is not a power of $2$.
Thus $\lfloor x/c \rfloor$ is hard for $\mathsf{AC^0}$ for any $c$
which is not a power of $2$.

As noted by Emil in the comments there is an easy reduction for odd prime $c$
from $\mathit{MOD}_c$ (that is, $\sum_ix_i\bmod c$ with $x_i\in\{0,1\}$) to
$x\bmod c$ with binary input:
we use only input bits which are multiples of $p-1$ and use FLT ($2^{(p-1)i} \bmod p = 1$).


Uses of algebraic structures in theoretical computer science I'm a software practitioner and I'm writing a survey on algebraic structures for personal research and am trying to produce examples of how these structures are used in theoretical computer science (and to a lesser degree, other sub-fields of computer science).

Under group theory I've come across syntactic monoids for formal languages and trace and history monoids for parallel/concurrent computing.

From a ring theory standpoint, I've come across semiring frameworks for graph processing and semiring based parsing.

I have yet to find any uses of algebraic structures from module theory in my research (and would like to).

I'm assuming that there are further examples and that I'm just not looking in the right place to find them.

What are some other examples of algebraic structures from the domains listed above that are commonly found in theoretical computer science (and other sub-fields of computer science)? Alternatively, what journals or other resources can you recommend that might cover these topics?

My impression is that, by and large, traditional algebra is rather too specific for use in Computer Science.  So Computer Scientists either use weaker (and, hence, more general) structures, or generalize the traditional structures so that they can fit them to their needs.  We also use category theory a lot, which mathematicians don't think of as being part of algebra, but we don't see why not.  We find the regimentation of traditional mathematics into "algebra" and "topology" as separate branches inconvenient, even pointless, because algebra is generally first-order whereas topology has a chance of dealing with higher-order aspects.  So, the structures used in Computer Science have algebra and topology mixed in.  In fact, I would say they tend more towards topology than algebra.  Regimentation of reasoning into "algebra" and "logic" is another pointless division from our point of view, because algebra deals with equational properties whereas logic deals with all other kinds of properties as well.

Coming back to your question, semigroups and monoids are used quite intensely in automata theory.  Eilenberg has written a 2-volume collection, the second of which is almost entirely algebra.  I am told that he was planning four volumes but his age did not allow the project to be finished.  Jean-Eric Pin has a modernized version of a lot of this content in an online book.  Automata are "monoid modules" (also called monoid actions or "acts"), which are at the right level of generality for Computer Science.  Traditional ring modules are probably too specific.

Lattice theory was a major force in the development of denotational semantics.  Topology was mixed into lattice theory when Computer Scientists, jointly with mathematicians, developed continuous lattices and then generalized them to domains.  I would say that domain theory is Computer Scientists' own mathematics, which traditional mathematics has no knowledge of.

Universal algebra is used for defining algebraic specifications of data types.  Having gotten there, Computer Scientists immediately found the need to deal with more general properties: conditional equations (also called equational Horn clauses) and first-order logic properties, still using the same ideas of universal algebra.  As you would note, algebra now merges into model theory.

Category theory is the foundation for type theory.  As Computer Scientists keep inventing new structures to deal with various computational phenomena, category theory is a very comforting framework in which to place all these ideas.  We also use structures that are enabled by category theory, which don't have existence in "traditional" mathematics, such as functor categories.  Also, algebra comes back into the picture from a categorical point of view in the use of monads and algebraic theories of effects.  Coalgebras, which are the duals of algebras, also find a lot of application.

So, there is a wide-ranging application of "algebra" in Computer Science, but it is not the kind of algebra found in traditional algebra textbooks.

Additional note: There is a concrete sense in which category theory is algebra.  Monoid is a fundamental structure in algebra.  It consists of a binary "multiplication" operator that is associative and has an identity.  Category theory generalizes this by associating "types" to the elements of the monoid, $a : X \rightarrow Y$.  You can "multiply" the elements only when the types match: if $a : X \rightarrow Y$ and $b : Y \to Z$ then $ab : X \to Z$.  For example, $n \times n$ matrices have a multiplication operation making them a monoid.  However, $m \times n$ matrices (where $m$ and $n$ could be different) form a category.  Monoids are thus special cases of categories that have a single type.  Rings are special cases of additive categories that have a single type.  Modules are special cases of functors where the source and target categories have a single type.  So on.  Category theory is typed algebra whose types make it infinitely more applicable than traditional algebra.


Algorithm for identifying unprovable statements I understand that this may depend on the specific set of axioms, but is there a general way (algorithm) for automatically detecting unprovable statements within a set of axioms?

For example: If there is some conjecture that I am trying to prove, but might not be provable, can I know it in advance by some automatic method?

If this is generally undecidable, can 'some' (maybe not all) conjectures be ruled out automatically? Can this be done at least partially?

I am mainly concerned about complexity class relations. Are there any known unprovable relations in this field? If there are, how where they achieved?

In addition, can the "undecidability of proof existence" for some complexity class relation conjectures be proved?

A more specific example: It was proved that IP = PSPACE. Could we have proven that this can be proved (i.e. prove that either IP=PSPACE or IP not equal to PSPACE actually have a proof) without having a proof either way? Or at least, could we decide that a proof exists?

I don't know much about complexity theory, but I can answer your first questions.

If the set of axioms is strong enough to encode Peano arithmetic, then you can construct unprovable statements by Gödel's first incompleteness theorem. You can easily construct infinitely many such statements, or equivalently, "detect" statements that are constructed like this. However…
Some statements are unprovable, but you cannot prove that they are unprovable. Using the same basic diagonalization as in the proof of Gödel's incompleteness theorems, you can e.g. consider a statement P that says "P is unprovable or false". P can't be proven true (otherwise it is false), nor proven false (otherwise it is true), nor proven unprovable (otherwise it is proven true). So, it is unprovable, but you can't prove it.
You can enumerate all provable statements, but not all unprovable ones — otherwise, you could just run both enumerators in parallel for long enough and that would give you a way to test whether a statement is true or provable, for any statement. I don't think there's a way to do strictly better than this "naive" enumeration.
Your last question is a bit vague — you're asking whether you could show that a proof of a statement exists in some non-constructive way; but what is "show" here? If you prove that the proof of a statement exists in the language of whatever axiomatic system you're using, then it "counts" as a valid proof within this system, so you actually constructed a proof…

I don't think you will spontaneously find statements like the ones described in this answer in complexity theory. This other question seems to indicate that this would require "radically new ideas". You might be able to fit weird provability theory statements into the language of complexity theory somehow, but it would probably be more of an artificial curiosity rather than a natural way of doing things.


Is contextual equivalence of a language with `quote`-`eval` trivial or not? In [1], Mitchell Wand demonstrated that adding fexprs to the pure lambda calculus trivializes the theory of contextual equivalence, meaning two terms are contextually equivalent iff they are $\alpha$-congruent.  When exploring related work, he went "our result extends an old observation of Albert Meyer [2] that evaland quote render contextual equivalence trivial".  But referring to [2], what could be found is only the following statement by Meyer:

  I ﬁrst thought that in languages with a quote-eval feature such as LISP [3] there was no type distinction between syntactic and executable objects.  In fact quote-eval seems safe enough in LISP because, although quote syntactically looks like a bona ﬁde operator, like say cond, it really doesn’t behave like one (it only has behavior at parse time, not run time, e.g., one can't pass quote as a parameter to a procedure).  Still, I have yet to see convincing examples where the quote-eval feature was worthwhile.

Regardless of one minor flaw in these comments that may mislead the reader to infer that cond could be passed as a parameter to a procedure.  If I understand correctly, what Meyer said "quote-eval seems safe enough" means that quote-eval may not trivialize the equational theory, although he did not offer a proof.

EDIT:

As suggested by Martin, since all the three papers cited dealing with LISP family languages, let's put the question under this same setting.  Is contextual equivalence of a language with quote-eval, in particular LISP, on earth trivial or not?

[1] Mitchell Wand, The Theory of Fexprs Is Trivial.  Lisp and Symbolic Computation 10(3): 189-199 (1998).

[2] Albert Meyer, Puzzles in Programming Logic  Workshop on Formal
Software Development. 1984

[3] John McCarthy, Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. Communications of the ACM in April 1960.

First, this entirely depends on what you take to be your set of contexts.  If (quote []) is a context, then contextual equivalence is syntactic equivalence.

Traditionally, contexts for contextual equivalence are taken to be contexts in which "expressions", in whatever meaning that has in the language, can appear. This rules out contexts like "[]", where the context places its argument inside a string literal. These kinds of contexts were also, IIRC, ruled out by Quine when he originally described referential transparency.

From this perspective, I think (quote []) is also not a context. Instead, the contexts are the places where expression evaluation could potentially happen, such as in the body of a function or in the argument of an application.

Potentially problematically, this means that in a Lisp program with macros (or a Racket or Scheme program) you don't know what the contexts are until you run the potentially-nonterminating macro expansion process, because you don't even know where the expressions are. Whether you think this is a problem or not is mostly a philosophical question rather than a technical one.


Searching for matching queries Suppose you have a large set of queries (could be in SQL form, but conceivably the same problem exists for search engine query strings or Lucene expressions, etc...) stored and you want to know which of these queries matches a specific object X: is there a general approach to this problem?

Naive implementation would of course be to iterate over all queries, execute them and see if object X is an element of the results found. I expect that a solution would consist of using the indexes that are useful for the operation "query -> results" to perform the "result -> queries" search to find a small superset of the correct set of queries.

Create a new table with only one object i.e. object X
Execute all the queries on it.
Discard those which return nothing.
Remaining queries are the queries that match your object X.

This will be faster than searching in a big table.


An analog of DP for the second level of the polynomial hierarchy The complexity class DP can be defined as the set of all languages that are the intersection of an NP language with a coNP language.

I have a language for which I wish to determine the exact complexity class. I know that the language is:

It is $\Sigma_2^P$-hard
It is $\Pi_2^P$-hard
It can be represented as the intersection of a $\Sigma_2^P$ and a $\Pi_2^P$ languages.

Here $\Sigma_2^P$ and $\Pi_2^P$ are the second-level classes in the polynomial hierarchy.

It seems that what I know about my language indicates that it is complete in a complexity class which is analogous to DP, but where DP corresponds to the first level of PH, my class corresponds to the second level.

My questions:

Am I correct in deducing the completeness of my language? It seems plausible but I can't find a proof.
What is the usual name of "my" complexity class? Where has it been studied so far? Is it interesting? Are there known (non-artificial) complete problems for it?

Thanks.

The definition of the class that you are referring to is interesting.

Originally, the definition of the class $D^P$, as the class of the languages that are the intersection of an $NP$ language and a co-$NP$ language, appeared in [1].
Then, the idea behind $D^P$ was generalized to the Boolean Hierarchy ($BH$) [2], which is a hierarchy between $NP$ and $\Delta^P_2$, and $D^P$ is at the second level of $BH$, i.e, $D^P = BH(2)$.
The definition of $BH$ was subsequently extended to the "Boolean Hierarchy over $\Sigma^P_2$" ($BH_3$) [3], which is a hierarchy similar to $BH$ but located between $\Sigma^P_2$ and $\Delta^P_3$.
In $BH_3$, at the second level, there is the class that you are mentioning.
Hence, in the literature, this class is sometimes denoted by $BH_3(2)$.
However, for the similarity between the definitions of $BH_3(2)$ and $BH(2) = D^P$, pretty soon, in the literature, the notation $D^P_k$ was used to denote the generalization of $D^P$ to upper levels in the polynomial hierarchy, even before a formal definition of it was given.
Therefore, the class you are referring to is usally denoted by $D^P_2$.

Regarding the $D^P_k$-hardness of languages, similarly to other definitions, a language $L$ is $D^P_k$-hard if, for every language $L'\in D^P_k$, there is a polynomial reduction from $L'$ to $L$.
Unfortunately, showing that a language $L$ is $\Sigma^P_k$-hard and $\Pi^P_k$-hard is not enough to show that $L$ is $D^P_k$-hard.
However, if there is a reduction from a $D^P_k$-hard language $L'$ to $L$, then $L$ is $D^P_k$-hard as well.
In this respect, it is helpful what it is said in a comment to the initial question.
In fact, a problem $L$ can be shown to be hard for $D^P_k$ if there is a polynomial reduction to $L$ from the task of recognizing pairs of "yes"-instances of two languages, one $\Sigma^P_k$-hard and the other $\Pi^P_k$-hard.
More formally, given two languages $L_1$ and $L_2$, which are $\Sigma^P_k$-hard and $\Pi^P_k$-hard, respectively, if there is a polynomial reduction $h$ such that $\langle s_1,s_2\rangle\in L_1\times L_2 \Leftrightarrow h(\langle s_1,s_2\rangle)\in L$, then $L$ is $D^P_k$-hard [4, by a generalization of the argument in the proof of Theorem 17.1].

[1] C. H. Papadimitriou and M. Yannakakis. The complexity of facets (and some facets of complexity). Journal of Computer and System Sciences, 28(2):244–259, 1984. DOI: 10.1016/0022-0000(84)90068-0

[2] J.-Y. Cai, T. Gundermann, J. Hartmanis, L. A. Hemachandra, V. Sewelson, K. W. Wagner, and G. Wechsung. The boolean hierarchy I: Structural properties. SIAM Journal on Computing, 17(6):1232–1252, 1988. DOI: 10.1137/0217078.

[3] R. Chang and J. Kadin. The boolean hierarchy and the polynomial hierarchy: A closer connection. SIAM Journal on Computing, 25(2):340–354, 1996. DOI: S0097539790178069.

[4] C. H. Papadimitriou. Computational Complexity. Addison Wesley, Reading, MA, USA, 1994.


For a language to be programmable, is it mandatory that it be based on a context free grammar Practically, for a language that can eventually be compiled/transformed into system level instructions, is it necessary that it be a context free grammar?

ex: Are all programming/scripting languages context free grammars? Java is based on CFGs, but is it actually the case that all programming languages are based on CFGs?

It does not seem mandatory, but there are gaps in my understanding.

Some context for the question: I was looking at Java language specification, which also provides the grammar rules. This made me think about this question.

Two times no.

First, most HPLs are not context free. While they usually have syntax based on a CFG, they also have what people call static semantics (which is also often included in the term syntax). This can include names and types which have to check out for a correct program. For instance,

class A {
  String a = "a";
  int b = a + d;
}

is a syntactically correct Java program but will not compile because d is not defined and a does not have a fitting type.

Secondly, you can parse languages that are not context-free (as obviously proven by the existence of compilers). It is only that CFGs can be parsed efficiently, while CSGs can not, in general. However, you can add certain non-context-free features while remaining efficient.

Compilers often run in phases: first tokenization (regular), then context-free parsing, then name and type analysis (context-sensitive, sometimes even harder). You can observe that behaviour by the kind of error messages you get.


Degree sets for linear extension graphs A linear extension $L$ of a poset $\mathcal{P}$ is a linear order on the
elements of $\mathcal{P}$, such that $x \leq y$ in $\mathcal{P}$ implies $x \leq y$ in $L$ for all $x,y\in\mathcal{P}$.

A linear extension graph is a graph on the set of linear extensions of a poset, where two linear extensions are adjacent exactly if they diﬀer in one adjacent swap of elements.

On the following picture there is the poset known as $N$-poset, and its linear extension graph, where $a=1234, b=2134, c=1243, d=2143, e=2413$.

(This figure is taken from the work.)

When you study linear extension graphs (LEG) you can come up with an idea (conjecture) that if  $\Delta$ - maximal degree of a LEG, $\delta$ - respecrively, minimal degree, then the degree set of any LEG consists of $\Delta,\delta$ and each natural number between them. For example, let's take a poset, known as chevron, then in its LEG $\mathcal{G}$ with $\Delta(\mathcal{G})=5$ and $\delta(\mathcal{G})=2$, and also, according to our conjecture, vertices with the degrees 4 and 3 are contained in the graph. So, the question is can we prove or disprove this conjecture?

About LEGs and how do they look like one can read in the dissertation of Mareike Massow here. Chevron and its LEG can be seen on the page 23 of the dissertation.

On the degree sets there is the classical paper "Degree sets for graphs" by Kapoor S.F. et al.

I think I proved it yesterday. Thus here goes the sketch of the proof.
At first, the following lemma is proved.

Lemma. Let $\mathcal{P}$ - a partial order, $G(\mathcal{P})$ - its linear extension graph and $v_1,v_2$ - two adjacent vertices of $G(\mathcal{P})$. Then $|deg(v_1)-deg(v_2)|\leq 2$.

The sketch of the proof.

At the same time, $v_1,v_2$ are linear extensions of $\mathcal{P}$ such that one of them, say $v_1$, can be transformed into $v_2$ by one transposition of adjacent elements (adjacent transposition). It is easy to see (consider, for instance, $d$ and $e$ from the above figure) that any element $x_i$ of any linear extension $L=x_1x_2\dots x_n$ can change the number of incomparable adjacent elements on at most two:

If $x_i$ can be transposed at all then at least one its neighbor, say $x_{i+1}$, is incomparable to it ($x_i\parallel x_{i+1}$, if comparable then $x_i\perp x_{i+1}$). Note: before transposing we have $L_1=\dots x_{i-1}x_ix_{i+1}x_{i+2}\dots$ and immediately after - $L_2=\dots x_{i-1}x_{i+1}x_{i}x_{i+2}\dots$.
Let us consider how the number of incomparabilities (degree of the linear extension as the vertex in $G(\mathcal{P})$) in $L$ could change. We consider at first the pair $x_ix_{i+2}$. For $x_{i-1}x_{i+1}$ the same conclusion follows by symmetry.

If $x_{i+1}\parallel(\perp) x_{i+2}\land x_{i}\parallel(\perp) x_{i+2}$, then $deg(L)$ doesn't change.
If $x_{i+1}\perp(\parallel) x_{i+2}\land x_{i}\parallel(\perp) x_{i+2}$, then $deg(L)$ increases (decreases) by one.The sketch of the proof is completed.

Theorem. Let $G(\mathcal{P})$ - a linear extension graph. If $G(\mathcal{P})$ contains vertices $v_1,v_2$ with $deg(v_1)=k,deg(v_2)=k+2$, then there is $v_3\in G(\mathcal{P})$ such that $deg(v_3)=k+1$.

The sketch of the proof.

Suppose $v_1,v_2,deg(v_1)=k,deg(v_2)=k+2$ are adjacent in $G(\mathcal{P})$, otherwise any vertex with degree $k$ in $G(\mathcal{P})$ is adjacent with some vertex if such exists with degree $k+1$.

Let us consider the case where we have $L_1,L_2$ from the previous lemma such that

$$x_{i+1}\perp x_{i+2}\land x_{i}\parallel x_{i+2},$$
and
$$x_{i-1}\perp x_{i}\land x_{i-1}\parallel x_{i+1},$$

Thus $deg(L_2)=deg(L_1)+2$.

Let us now start transpose $x_{i+1}$ in the direction of $x_1$. It is easy to see that eventually we could stop at the position where

$$x_{j}\perp x_{i+1}\land x_{i+1}\parallel x_{j+1},$$ for some $j<i-1$.
The sketch of the proof is completed.


Any resources describing an OS assigning process priority via distance to HD head? During the introductory computer organization class I recently took, the professor described the limitations of seek time in reading or writing to the disk. He suggested a solution whereby the operating system would prioritize the process whose sectors were then closest to the head. In that case, it could move smoothly back and forth rather than jerking to an arbitrary track where the process' data lies. (I guess this assumes a full drive or an even distribution.)

Warford's Computer Systems doesn't mention anything similar and the professor is on vacation. I am curious whether this is just a thought experiment (like bogo sort) or has someone attempted this strategy? Any resource welcome; thanks

That would be pragmatically challenging under most OSes due to the abstraction layers and difference in subsystems. Vista offers I/O priority, which is as close as I've ever seen to anything like that.. And it isn't very close. All theory here... also won't matter soon as we go to SSDs that have no seek time.


How can theoretical modelling be converted into viable product? Many a times modelling is just for the sake of modelling like exploring some properties of materials which does not help in converting the theoretical modelling into a viable product that can serve humanity.

How one can become expert enough or which areas one should focus to model such problems and materials which can eventually result in some useful product.

Like we have solar cells but every other day we see a research article being published just by tweaking the parameters which does not result in better or greater product.

I want to see modelling and theory becoming useful sooner than we normally see.

I'm assuming that you're really asking, "how do I do something useful with modelling and theory."

The easiest answer is to work in a modelling and simulation field that makes useful products. Computational Electromagnetics is used a lot in RF, Finite Element Analysis is used in mechanical product design.

The broken part of your reasoning is that "more expertise = more practically useful." This is wrong. Usefulness is an instrinsic property of a task. A task is either useful or not useful. Expertise is only important in as much it allows you to perform a task. Therefore, you need to:

Pick a useful task
Have enough expertise to perform that task.

Sounds obvious, but perhaps it isn't.


Do 'reflexive' hash algorithms exist? Is there a class of hash algorithms, whether theoretical or practical, such that an algorithm in the class might be considered 'reflexive' according a definition given below:

hash1 = algo1 ( "input text 1" )
hash1 = algo1 ( "input text 1" + hash1 )

The + operator might be concatenation or any other specified operation to combine the output (hash1) back into the input ("input text 1") so that the algorithm (algo1) will produce exactly the same result. i.e. collision on input and input+output. The + operator must combine the entirety of both inputs and the algo may not discard part of the input.

The algorithm must produce high entropy in the output. It may, but need not, be cryptographically hard to reverse the output back to one or both possible inputs.

I am not a mathematician, but a good answer might include a proof of why such a class of algorithms cannot exist. This is not an abstract question, however. I am genuinely interested in using such an algorithm in my system, if one does exist.

This is a duplicate of a question that was first posted at https://stackoverflow.com/questions/4823680/reflexive-hash

I give a trivial construction which satisfies the requirement. I provide it to merely answer the existence of "reflexive" hash function.

Let $G$ be any hash function producing high entropy in the output. Assume that $G$ hashes arbitrary-length binary strings to $k$-bit binary strings, where $k$ is any positive integer. Let $+$ denote the concatenation operator, and let $|x|$ denote the length of the binary string $x$.

Define the hash function $H$ on input $x$ as follows:

If $|x| \le k$, then $H(x) \overset{\text{def}}{=} G(x)$.
If $|x| > k$, let $L$ and $R$ be the $(|x|-k)$-bit prefix and $k$-bit suffix of $x$, respectively. That is, $x = L + R$ and $|R|=k$. If $R = H(L)$ (where $H(L)$ is computed recursively), then $H(x) \overset{\text{def}}{=} R$; otherwise, $H(x) \overset{\text{def}}{=} G(x)$.

As I said, this is a trivial construction. It can be applied to any hash function, practical (such as MD5, SHA-1, ...) or theoretical.


Are there problems that can be solved in time $2^{n-q^c}$ with $q$ qubits? This is another attempt to formalize my former question on the topic.

I'm looking for a problem for which all known classical algorithms take exponential time, but given ANY number of few qubits (think around 53), we can achieve a speed-up that is exponential in their number.
So if the problem requires time $2^n$ on a classic computer, then I would hope for a hybrid quantum-classical algorithm that uses $q$ qubits and takes $2^{n-q^c}$ time for some constant $c$.
Here $c$ is independent of $q$, which can be any number, up to $n^{1/c}$ or so by when the problem becomes polynomial on the quantum computer.
Are there such problems?

I think the scaling $2^{n/q^c}$ is too much to ask for. Even $poly(q) 2^{O(n-q)}$ would represent an exponential speedup for each additional qubit.

And indeed, such a problem is known: simulating a quantum circuit of $n$ logical qubits on a small hybrid quantum-classical computer with only few (perfect) physical qubits $q\leq n$ has this scaling. See: https://arxiv.org/abs/1506.01396


Geometric Interpretation of Computation Being from Physics, I have been trained to look into a lot of problems from a geometrical point of view. For example the differential geometry of manifolds in dynamical systems etc. When I read the foundations of computer science, I always try to find geometric interpretations. Like a plausible geometric interpretation of recursively enumerable sets (I worked on a part where I tried to connect them with Algebraic Geometry by exploiting equivalence with Diophantine Sets but the connection seemed forced and I could not find a "natural" expression of the facts in that formulation) or a beautiful geometric result for a simple algorithm for sorting numbers. Though I am not an expert I have read surveys on Geometric Complexity Theory and it is surely an interesting program but I am more interested in having a geometric view of extremely fundamental concepts like the dynamics of a Turing Machine, Lambda Calculus or the structure of (un)computable sets (rather than specific problems). Is it a hopeless job to find geometrical structure in these objects or can one expect some intricate results? Is there any formulation of TCS which treats it geometrically?

The semantics of computer programs can be understood geometrically in three distinct (and apparently incompatible) ways.

The oldest approach is via domain theory. The intuition behind domain theory arises from the asymmetry behind termination and nontermination.

When treating programs extensionally (ie, only looking at their I/O behavior, and not their internal structure), it is always possible to confirm in finite time that a program halts -- you just wait until it stops. However, it's not possible to confirm that a program doesn't halt, because no matter how long you wait, there is always a halting program that will run for a few more steps than you waited.

As a result, halting and looping can be viewed as forming a topological space (the  Sierpiński space). This lifts to richer notions of observation (via the Scott topology), and you can thereby interpret programs as elements of  topological spaces. These spaces are generally quite surprising from a traditional point of view -- domains are generally not Hausdorff.

The best topological introduction I know to these ideas is Steve Vickers' short and extremely accessible Topology via Logic. It can be understood as a sort of warm-up for Peter Johnstone's significantly more formidable Stone Spaces.

If you are looking for online lecture notes, let me suggest Martin Escardo's Synthetic Topology of Data Types and Classical Spaces.
Another view arises from concurrency theory. A concurrent program can be understood as having multiple valid executions (sequences of states), depending on how races are resolved. Then, the set of executions can be viewed as a space, with each possible sequence of states understood as a path through this space. Then, methods from algebraic topology and homotopy theory can be applied to derive invariants about the program execution.

Nir Shavit and Maurice Herlihy uses this idea to prove the impossibility of certain distributed algorithms, for which they won the 2004 Gödel prize. (See The Topological Structure of Asynchronous Computation.) Eric Goubault has a survey paper explaining the relevant ideas in Some Geometric Perspectives in Concurrency Theory.
Most recently, it has been observed that the structure of the identity type in dependent type theory corresponds very closely with the notion of homotopy type in homotopy theory -- so closely, in fact, that dependent type theory can actually be seen as a sort of "synthetic homotopty theory"! (Vladimir Voevodsky has joked that he spent several years developing a new calculus for homotopy theory, only to discover that his colleagues in the CS department were already teaching it to undergraduates.)

See cody's link above to the homotopy type theory book.

Interestingly, these three views seem incompatible with each other, or at least very difficult to reconcile. Dependent type theory is a total language, so nontermination (and the Scott topology) does not arise in it. It is also confluent, so the view of computations-as-spaces doesn't arise either. Similarly, formulating concurrency in terms of domain theory has proved ferociously difficult, and a completely satisfactory account is still an open problem.


How does Camerini's algorithm for minimum-bottleneck-spanning-tree run in linear time? I'm having a difficult time understanding Camerini's algorithm because there are very few clear explanations online. The goal is to find a minimum-bottleneck spanning tree in linear time.

Camerini's algorithm does this by splitting the edges by weight into heavy and light halves in O(|E|) time, then building a maximal forest from the light edges. If there is only one tree, then it recurses on the lighter half of edges, but if there are multiple trees, it reduces each tree to a super-vertex, then recurses with the new set of vertices and the heavy edges.

I don't understand how this can run in linear time. If the forest-finding runs in O(|V|+|E|) time, and |V| is not guaranteed to decrease in any predictable fashion, then the algorithm should be bounded by O(|V| log |V| + |E|).

What do I misunderstand about this algorithm?

First, after each stage throw away any isolated vertices. With these vertices removed (even when the graph is disconnected) the number of vertices in the next stage will be at most twice the number of edges.

Next, use the fact that (with isolated vertices removed, in each stage after the first) $|V|\le 2|E|$ to simplify the time bound in each stage (after the first) from $O(|V|+|E|)$ to $O(|E|)$.

Finally, observe that at each stage $|E|$ goes down by a factor of two, so all these $O(|E|)$ bounds add in a geometric series to be linear in the size of the original graph.


Why semi-gradient is used instead of the true gradient in Q-learning? In reinforcement learning, with function approximation, a popular cost function is the Mean value error.

This involves a target value V_pi and a current value estimate V_hat.
When deriving the update rule for gradient descent learning, people just ignore V_pi-s dependence on the parameters, using a semi-gradient instead of the true gradient.
Why is this? Is it difficult to calculate the true gradient?

The problem does not come from the above equation but from the bootstrapping method. Sutton's reinforcement learning book (2nd) gave a pretty good explanation to the problem in Chapter 9.3.
The idea here is you cannot obtain the true value for $V_\pi$, but you want to approximate it. My understand is that when bootstrapping, like with the TD method, $V_\pi$ depends on $w$. This breaks the assumption that $V_\pi$ is independent of $w$ and thus the gradient is not the true gradient and we call it semi-gradient. However, if you are not bootstrapping, as with Monte Carlo methods, $V_\pi$ will be unbiased and the above will be guaranteed to converge to a local minimal.