Efficient algorithms for searching a collection of trees I have a large dataset of trees and I would like to search it by specifying a treelet (connected subgraph). The query should return all the occourrences of the treelet in the dataset.

Are there efficient algorithms to do so?

I was thinking of something like suffix arrays, however, naively encoding the trees as strings (by a fixed traversal ordering of their nodes) won't work, since the search treelet can be of any arbitrary shape.

UPDATE:

Some details about the typical instances I expect:

The dataset will consist in at least tens of thousands trees, each consisting in about twenty to thirty nodes.
The trees will not be not binary, but the typical children number per node will be small (usually no larger than four or five, although in some degenerate cases it can reach about thirty). The number of labels will be in the tens of thousands.

I need that for NLP applications: each tree will be the dependency parse of a sentence, each node representing a word occourrence and each label a dictionary word (with some decoration).

Although not specifically aimed at (rooted) trees, I think the G-trie data structure might perform quite well in your setting. It is an adapation of the trie (for searching sets of strings) to graphs.


Computing the Syntactic Congruence The syntactic monoid of a language $L \subseteq X^*$ is defined as the monoid obtained from the congruence relation
$$
 u\ \tilde{}\ v \ \mbox{ iff }\ \forall x,y \in X^* : xuy \in L \leftrightarrow xvy \in L.
$$
How to compute this in general? For regular languages I just know an approach via the minimal automaton, from which you compute the transition monoid. More concretely let $\mathcal A = (X, Q, f, q_0, F)$ a DFA, from the state vector $(q_0, q_1, \ldots, q_n)$ compute the closure with regard to
$$
 (q_0, q_1, \ldots, q_n) \cdot w = (f(q_0,w), f(q_1, w), \ldots, f(q_n,w))
$$
and $w \in X^*$. Then the tupel $(q_0, q_1, \ldots, q_n)$ corresponds to the identity element of the monoid and the tupels $(q_0, q_1, \ldots, q_n) \cdot x$ for $x \in X$ correspond to the generators of the monoid. Each tupel corresponds to a minimal word, the product of two tupels $q, q'$ is defined by taking some word $w$ which represents $q'$ and compute $q\cdot w$ (this works because $[u] = [v]$ iff $f(q,u) = f(q,v)$ for all $q$ in the minimal automata). Or more simple set $f_w(q) := f(q,w)$, then $f_u(f_v(q)) = f_{vu}(q)$, the transition monoid is $\{ f_w : w \in X^* \}$ under functional composition.

Two question:

i) Are there other ways without using an automata as intermediate step to compute the syntactic monoid,

ii) This just works for regular languages, how to proceed for non-regular language? (okay for languages like $\{a^nb^n : n \in \mathbb N\}$ one could imagine an infinite automata and proceed, but that does not works in general)

Question 1. Yes, there are other ways than using automata. Typically, if you already now that your language is recognized by some surjective monoid morphism $\varphi: A^* \to M$, then you know that $M(L)$ (the syntactic monoid of $L$) is a quotient of $M$. For instance if $L = \{ u \in \{a,b\}^* \mid |u|_a \equiv 5 \bmod 13 \text{ and } |u|_a \equiv 6 \bmod 7\}$, then you can prove directly that $M(L) = \mathbb{Z}/91\mathbb{Z}$ without computing the minimal automaton.

Question 2. C. Brand is right. You can still use the minimal automaton, even if it is infinite. You can also just use the definition of the syntactic congruence to get a presentation of the syntactic monoid. You may also just guess a morphism recognizing your language. Three examples:

(1) Let $L = \{u \in \{a,b\}^* \mid |u|_a = |u|_b \}$. Then the morphism $\pi: \{a,b\}^* \to \mathbb{Z}$ defined by $\pi(a) = 1$ and $\pi(b) = -1$ recognizes $L$ since $L = \pi^{-1}(0)$. Thus $M(L)$ is a quotient of $\mathbb{Z}$. But every nontrivial quotient of $\mathbb{Z}$ is finite and cannot be equal to $M(L)$ (otherwise $L$ would be regular). Thus
$M(L) = \mathbb{Z}$.

(2) Let $L = \{u \in \{a,b\}^* \mid |u|_a \geqslant |u|_b \}$. This context-free language generated by the grammar $S \to SS + aSb + 1$. Its syntactic monoid is also equal to $\mathbb{Z}$, since $L = \pi^{-1}([0, + \infty[)$.

Update following Stefan's comment

(3) Let $D$ be the Dyck language (see Stefan's comment). Its syntactic monoid is the bicyclic monoid, which is the monoid presented by $<a,b \mid ab = 1>$.

(4) Let $L = \{a^nb^n \mid n \geqslant 0 \}$. Its syntactic monoid is the monoid with zero presented by $<a,b \mid ba = 0>$.


Successful application of branch-and-bound methods for NP-hard problems Branch and bound is an effective heuristic for search problems, and Wikipedia lists a number of hard problems where branch-and-bound has been used. However, I haven't been able to find references to suggest that it's more than just "one method" for solving these problems.

Anecdotally, I've heard that some of the best heuristics for SAT and integer programming come from branch and bound, so my question is:

  Can someone point me to any references detailing effective uses of
  branch and bound for NP-hard problems ?

For TSP, checkout this book...
http://www.tsp.gatech.edu/book/index.html

My understanding is that there is no one tool to kill them all. Arguably any recursive solution deploying backtracking and some scoring function is using branch and bound. As such, a large fraction of solvers to NP hard problems use some form of branch and bound.


Modern distributed computing book Lynch's Distributed Algorithms book is a classic but it is from 1996 and rather out of date. Are there any recent distributed computing books that can be used as textbooks for a graduate distributed computing and algorithms course?

You can refer Roger Wattenhofer's Lecture note on PODC.

Here I mentioned some other courses on distributed algorithms.


Slowest many-one reduction? When we want to prove that an $L\in \bf NP$ is $\bf NP$-complete, then the standard approach is to exhibit a polynomial time computable many-one reduction of a known $\bf NP$-complete problem to $L$. In this context we do not need a tight bound on the running time of the reduction. It suffices to have any polynomial bound, allowing that it may possibly have a very high degree.

Nevertheless, for natural problems, the bound is typically a low degree polynomial (let us define low as something in the single digits). I do not claim that this must always be the case, but I am not aware of a counterexample.

Question: Is there a counterexample? That would be a polytime computable many-one reduction between two natural $NP$-complete problems, such that no no faster reduction is known for the same case, and the best known polynomial running time bound  is a high degree polynomial.

Note: Large, or even huge, exponents are occasionally needed for natural problems in $P$, see
Polynomial-time algorithms with huge exponent/constant. I wonder if the same also occurs in reductions among natural problems?

Allender suggests the answer is no:

  There seems to be no pair of natural NP-complete problems A and B known, where a reduction from A to B is known to require more than linear time (even under the assumption that P $\ne$ NP)

Reference:

E. Allender and M. Koucký, Amplifying lower bounds by means of self-reducibility. Journal of the ACM 57, 3, Article 14 (March 2010).


Does one player best responding to sample from a mixed strategy, and the other player minimizing regret converge to a Nash eq in a zero sum game? It is well-known that in a $2$-player zero sum game if one player plays a regret minimizing mixed strategy, and the other player best-responds at each round to that mixed strategy, we are guaranteed convergence to an approximate Nash Equilibrium in poly-time. See e.g. (https://theory.stanford.edu/~tim/f13/l/l17.pdf). My question is suppose that one player is playing a no-regret strategy, and the other play best-responds to a sample from the mixed strategy of her opponent, rather than to the mixed strategy. Is it still true that the empirical average of both strategies will converge to Nash in poly-time?

No, it's not true. Consider this game where the row player's actions are A,B,C and column's are D,E (shown are the row player's payoffs):

    D     E
A   1     0
B   0     1
C  0.6   0.6

I think that in any equilibrium, the row player plays only C.

But now if the column player uses a no-regret algorithm, every sample will either be action D or E, and the row player's best response will always be either A or B. So the row player will never play C in the entire empirical history.


Is there any known CCC closed under a probabilistic powerdomain operation? Equivalently, is there a known denotational semantics for probabilistic higher-order functional programming languages? Specifically, is there a domain model of pure untyped $\lambda$-calculus extended by a symmetric random binary choice operation.

Motivation

Cartesian closed categories provide a semantics to higher-order $\lambda$-calculi. Probabilistic powerdomains provide semantics to stochastic programs. A CCC closed under a probabilistic powerdomain operation would provide a semantics to a stochastic higher-order functional programming language.

Related Work

Tix, Keimel, and Plotkin (2004) [1] give modern constructions of the lower-, upper-, and convex- powerdomain operations, but remark that

  It still is an open problem whether there is a cartesian closed category of continuous domains which is closed under the construction of probabilistic powerdomains.

Mislove (2013) [2,3] gives semantics for continuous random variables in a first-order language, but remarks that

  Even though the probabilistic power domain leaves the CCC of directed complete posets (dcpos, for short) and Scott-continuous maps invariant, there is no Cartesian closed category of domains – dcpos that satisfy the usual approximation assumption – that is known to be invariant under this construct. The best that is known is that the category of coherent domains is invariant under the probabilistic choice monad [4], but this category is not Cartesian closed.

References

Regina Tix, Klaus Keimel, and Gordon Plotkin (2004)
"Semantic domains for combining probability and non-determinism".
Michael Mislove (2013)
"Anatomy of a domain of continuous random variables I"
Michael Mislove (2013)
"Anatomy of a domain of continuous random variables II"
Jung, A. and R. Tix (1998)
"The troublesome probabilistic powerdomain"

The following is an extended comment, it does not answer your question in the terms you posed it but does give a semantics for higher-order probabilistic calculi which you may find of interest.

In the past few years there has been a very active line of research around so-called quantitative denotational semantics of linear logic, based on the idea (originally due to Girard [1]) that higher-order programs may be modeled by power series.  In the probabilistic case, this takes the form of so-called probabilistic coherence spaces (PCS), also introduced by Girard [2] and studied in depth by Danos and Ehrhard [3].  PCS yield models of both typed and untyped probabilistic calculi which are of a very different nature than power domains and other monad-related models.  In particular, PCS give what is thus far the only known fully abstract model of probabilistic PCF [4], which is notoriously difficult and seemingly impossible to achieve with power domains (cf. the work of Jean Goubault-Larrecq).

Apart from Ehrhard, quantitative semantics is now actively developed by Michele Pagani and coauthors, I suggest you look at his web page for additional references.

[1] Jean-Yves Girard, Normal functors, power series and $\lambda$-calculus. Annals of Pure and Applied Logic 37 (2):129-177, 1988.

[2] Jean-Yves Girard, Between logic and quantic: a tract. In Linear logic in computer science, CUP, 2004.

[3] Vincent Danos and Thomas Ehrhard, Probabilistic coherence spaces as a model of higher-order probabilistic computation. Information and Computation 209(6): 966-991, 2011.

[4] Thomas Ehrhard, Michele Pagani and Christine Tasson, Probabilistic coherence spaces are fully abstract for probabilistic PCF. In Proceedings of POPL, pp. 309-320, 2014.


"Smallest" path that visits a given set of vertices I use smallest rather than shortest to distinguish between the shortest path problem. The problem is as follows:

  Given a directed graph $G=(V,E)$, two vertices $s$ and $t$, and a set of $p$ vertices $x_1,x_2,\ldots, x_p$. The goal is to find a $s-t$ path  which visits all of $x_1,\ldots, x_p$, such that the size of the set of visited vertices is minimized. Here we can assume $p$ is a constant, and the path needs not to be simple.

At first I thought this is the same as "shortest path that visits a certain set of vertices" problem, and I know this problem can be reduced to the TSP problem. Since $p$ is a constant, I can enumerate all possible visiting orders of $x_1,\ldots,x_p$ and compute the union of the shortest paths between consecutive vertices in each order.

However, because we don't require the path to be simple, I'm not sure whether the shortest path is equivalent to the smallest path desired by the problem. I feel that it's possible to find a path which is long in the sense that some vertices of it are visited many times, but small in the sense that the number of all unique vertices are small. But till now I don't find such an example.

Although I don't have an algorithm, I believe the problem is polytime solvable. Any suggestions?

So you want to find the smallest set $S$ of vertices that can be used for a walk containing $s$, $t$, and the vertices $x_i$, from $s$ to $t$. In the undirected case this can be simplified to: you want to find the smallest set $S$ of vertices containing $s$, $t$, and $x_i$ such that $S$ is connected.

This is the graph Steiner tree problem and is NP-hard. You are looking at the directed case, but making this problem directed cannot make it easier, so it remains NP-hard. The reduction from the undirected case is: replace each undirected edge by two directed edges, one in each direction.


Which $SIZE$-$DEPTH(s, d)$ classes with $log(s(n))^{d(n) - 1} = o(n)$ can we not separate by known methods? Define $SIZE$-$DEPTH(s, d)$ to be the functions which are computed by circuit families of size $O(s(n))$ and less than depth $d(n)$.

We know from Boppana's 1997 paper on the average sensitivity of low depth circuits that if we have functions $s, d, s', d' : \mathbb{N} \rightarrow \mathbb{N}$, where

$log(s(n))^{d(n)-1} = o(n)$,

$log(s'(n))^{d'(n) - 1} = o(log(s(n))^{d(n) - 1}$,

we know that $SIZE$-$DEPTH(s, d) \neq SIZE$-$DEPTH(s', d')$.

This is true because in $SIZE$-$DEPTH(s, d)$ we can compute $PARITY$ on a larger number of bits than in its $s', d'$ defined counterpart. This separates a large number of low complexity classes, most interesting to me being $qAC^0 \neq FOLL$. On the other hand, when

$log(s(n))^{d(n) - 1} = \Theta(log(s'(n))^{d'(n) - 1})$,

I don't know of a method to separate them. Obviously there are the degenerate cases where $s(n) = \Theta(s'(n)), d = \Theta(d')$, but I tried to compute the limit and get some constraints on $s, d, s', d'$ but it is seriously gnarly and it doesn't seem to give me anything good. If $d$ is constant you can do something but it doesn't give me much intuition. Can anybody come up with interesting examples, perhaps illustrating the size-depth tradeoffs that you'd imagine would be present, of $s, d, s', d'$ for which the respective classes cannot be separated by Boppana? If so, can you show a separation between these two classes in another way? Is there some reason I'm missing that all such cases are degenerate?

Lets say that we have $s, d$ where $log(s(n))^{d(n) - 1} = o(n)$. Let $d'(n)$ be arbitrary and $s'(n) = 2^{\sqrt[d'(n) - 1]{log(s(n))^{d(n) - 1}}}$. Then we have that $log(s(n))^{d(n) - 1} = log(s'(n))^{d'(n) - 1}$. Thus, we have a question, for various interesting ranges of $s, d, s'$, which is not seemingly answered by Boppana:

$SIZE$-$DEPTH(s, d) =_? SIZE$-$DEPTH(2^{\sqrt[d'(n) - 1]{log(s(n))^{d(n) - 1}}}, d'(n))$

Thinking about the limit was overcomplicating this clearly and this is easy to see. It shows the size-depth tradeoff I expected, as well, where the new size goes up as the depth goes down, making the circuit "harder to beat" in both directions. I think, speaking of this, that you will be able to show that these classes are incomparable. Does anybody else have any thoughts on the relationship between the two classes and can you prove something about it?


Exact version of matroid, given the input weight is in unary. Is the following problem in P?

We are given a matroid M. Each element in M has a weight encoded using some unary notation.
We are also give an integer K also encoded in unary bits.
The question is whether there is a base of M that has weight EXACTLY K.

I know the exact spanning tree is in P.

Thanks a lot.

This problem appears to be considered in "Random pseudo-polynomial algorithms for exact matroid problems", P. M. Camerini, G. Galbiati and F. Maffioli, Journal of Algorithms
Volume 13, Issue 2, June 1992, Pages 258-273.

They give a randomized polynomial time for the problem, but they seem to be assuming that the input matroid is representable over the reals, rather than allowing arbitrary matroids. They also state that it is unknown whether it is solvable in P.

However, if all elements of M have weight 0 or 1, then it is easy to solve as a matroid intersection problem.


Assigning edge weights under shortest path constraints We are given a graph $G = (V,E)$ and we need to find an assignment of non-negative edge weights (You must give every edge a non-negative weight). We are also given a set $R\subseteq V$ and mapping $c_{a,b}: R\times R \rightarrow \mathbb{R^+}$ where $\mathbb{R}^+$ is all positive ($> 0$) reals ($c_{a,b} = c_{b,a}$ for all $a,b$ and $c_{a,a} = 0$ for all $a$ ). Our edge weight assignment is constrained by the requirement that for all vertex pairs $(a,b)\in R\times R$, all paths from $a$ to $b$ need to have at least weight $c_{a,b}$  where the weight of the path is the sum of all edge weights on that path.

Now assume that there exists an assignment that satisfies all of the constraints and such that for all vertex pairs $(a,b)\in R \times R $ there exists at least one path from $a$ to $b$ whose weight is exactly equal to $c_{a,b}$.

Now consider the assignment of edge weights (*) that satisfies the constraints and minimizes the total sum of edge weights. Is it true that for all vertex pairs $(a,b)\in R \times R$ there will exist at least one path from $a$ to $b$ whose weight is exactly equal to $c_{a,b}$ ?

Yes.

Consider an exact assignment as described in your second paragraph.

If any edge has a weight $w_{a,b} > c_{a,b}$ there must be an indirect path with total path weight $c_{a,b}$, This means the direct edge $ab$ will not be part of any minimal path.  We can lower the weight to $w_{a,b} = c_{a,b}$ without changing this.

Therefore, if an exact assignment exists, $w_{a,b} = c_{a,b}$ (for all a,b) will be an exact assignment.

It is clear that this is the unique assignment with minimal total weight.


GA puzzle solver stuck at local maximum I have a jigsaw type problem with 192 pieces which I am trying to find solutions to.  I have written a GA which starts from a random allocation then 'crosses' by taking rectangular blocks  from one solution then filling in from another then 'mutates' by switching pieces at random.  Through a complex procedure I can evaluate a solution and calculate a score.

I have a population size of 1000 and take 40% of the first parent in the cross and mutate up to 4% of the pieces in each solution generation.  I select the parents with a weighted selection and do not allow any exact duplicates in my population.

The problem I am having is that the algorithm gets stuck at about 70% score, with (I assume) a population full of near identical solutions.

What can I do to improve the performance of the algorithm, am I making any glaring mistakes?
Should I be mutating more, or directing the mutation more towards poor scoring pieces?
Should I have a larger population, or run several populations in parallel and share high scoring solutions between them?

Update

I have replaced my roulette with a tournament selection (with 4 solutions picked at random and the best selected) and implemented mutations up to 4 times on each new child in the generation.  I rearranged the process so that I cull half the population, then add some new random results then repopulate with crossovers.

Unfortunately, I seem to get a marginal performance increase, but I still seem to be converging at around 70% score.

Does anyone have any other ideas of things I can tweak to try and break through this barrier?

1000 individuals is typically a fairly large population, so lacking further information, you're probably fine there.

You don't say how quickly your algorithm is converging or exactly you calculate the weights for weighted selection, but if you're doing the typical roulette-wheel or fitness-proportionate selection, it's known that that method produces a large amount of selection pressure, particularly early in the run. What happens is that most early solutions are terrible, so the first mediocre thing it finds gets a much higher proportion of the total fitness than it really deserves and quickly swamps the population. The easiest way to avoid that is to use something with a more controllable selection pressure, like binary tournament selection or rank-biased selection.

For mutation, the general rule of thumb has always been to mutate each allele independently with probability 1/n. Like any heuristic, that's only a starting point, and you should let experiment guide you in making any adjustments, but if I'm understanding you correctly, you have 192 alleles, so a 4% mutation rate gives an expectation of about 8 mutations per individual, which I would guess is too high.

Or do you mean you make a single mutation to 4% of the generated offspring? If that's the case, it's probably too low. I'd start with a method that mutates every single individual by a randomly selected amount, with the expected amount being one flip. Some individuals will get two or three flips, others will not be altered at all.

The third idea, having multiple populations and sharing between them goes by the name of "island model" GAs, and has been known to work pretty well for some problems. However, I think in your case there are some issues with the way the underlying algorithm is working that need to be addressed before moving to a parallel model that will only make it more difficult to tease out the dynamics of what's going on.

Without more details about exactly how you're encoding your solutions, how your crossover and mutation operators work, etc., we're kind of limited to general statements such as those I just made. Feel free to post any clarifications though and I'll take another run at helping understand what might be going on.


Clique-Percolation Algorithm's "corner cases" I'm programming an implementation of the Clique-Percolation algorithm, but I have many doubts about some corner cases.

Imagine we want to find the communities of a graph using $k=4$. We are lucky and every node in the graph belongs at least to one k-clique (with $k \geq 4$). So it's trivial to apply the algorithm by hand (slow, but trivial).

Now imagine we add three more nodes to the graph, creating a 3-clique, and connecting this clique to the previous existing nodes with only 1 edge.

It's here where I have problems to understand what's expected of the Clique Percolation algorithm.

I have to add a new community for each new node? Only a new non-overlapping community matching the 3-clique? Nothing (not considering the new nodes in any community)?

Example initial graph:
$$
A \leftrightarrow B \\
A \leftrightarrow C \\
A \leftrightarrow D \\
B \leftrightarrow C \\
B \leftrightarrow D \\
C \leftrightarrow D \\
$$

Modified graph:
$$
A \leftrightarrow B \\
A \leftrightarrow C \\
A \leftrightarrow D \\
B \leftrightarrow C \\
B \leftrightarrow D \\
C \leftrightarrow D \\
D \leftrightarrow E \\
E \leftrightarrow F \\
E \leftrightarrow G \\
F \leftrightarrow G
$$

thanks for your time.

Finally, I've found that the answer is that exists the possibility of leaving out many nodes out of any resulting community. There isn't any specified way in the original CPM algorithm to deal with them.

For anyone interested on a possible way to handle the left out nodes, there is an interesting article explaining an extension of CPM to do that:

Extended Clique percolation method to detect overlapping community structure : http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6968420&pageNumber%3D33268%26rowsPerPage%3D100

It seems that the modularity score obtained with this extension is usually better than the produced by the original CPM, but it comes with a price: it's slower.


How to start learning formal language theory I sincerely apologize if this is not appropriate in this stack Q&A, though it seemed the most fitting.

I want to learn formal language theory, as well as generating grammars etc. The purpose is primarily from a programming perspective (and from pure interest), not from academic requirements. My current state of knowledge includes basic college-level math (very far from good skills sadly), and of course programming skills.
Which math and logic fields should I explore. What is the best way to learn it (other than majoring in mathematics)?
Specific resources are welcome (as is general direction I should follow).

Also - what are skill requirements to properly learn the topic and understand it to the degree it may be useful in programming?

EDIT: my interest in this branch of mathematics started once I learned regular expressions and wanted to "delve deeper"

Theory of computation by M. Sipser is interesting per se. For introduction you have to practice and go in following sequence.

Regular language and automata
Context free grammar and expressions
Pushdown automata
Non context free grammar
Lr(k) grammar
Turing Machines

If interest level drops keep reading a fun book
https://en.wikipedia.org/wiki/A_New_Kind_of_Science


Yao's Minimax Principle on Monte Carlo Algorithms The celebrated Yao's Minimax Principle states the relation between distributional complexity and randomized complexity. Let $P$ be a problem with a finite set $\mathcal{X}$ of inputs and a finite set $\mathcal{A}$ of deterministic algorithm to solve $P$.
Also let $\mathcal{D}$ denote the input distribution and let $\mathcal{R}$ denote the probability distribution on $\mathcal{A}$.
Then the principle states
$$\min_{A\in\mathcal{A}}\quad\mathbb{E} cost(A,\mathcal{D}) \leq \max_{x\in\mathcal{X}}\quad\mathbb{E} cost(\mathcal{R},x) \quad\quad\text{for all $\mathcal{D}$ and $\mathcal{R}$}.$$
This proof directly follows from von Neumann's minimax theorem for zero-sum games.

Mostly Yao's principle deals with Las Vegas algorithms only, but it can be generalized to Monte Carlo algorithms as follows.
$$\frac12 \min_{A\in\mathcal{A}}\quad\mathbb{E} cost_{2\epsilon}(A,\mathcal{D}) \leq \max_{x\in\mathcal{X}}\quad\mathbb{E} cost_{\epsilon}(\mathcal{R},x)\quad\quad\text{for all $\mathcal{D}$, $\mathcal{R}$ and $\epsilon\in [0,1/2]$}$$
where $cost_\epsilon(\cdot,\cdot)$ denotes the cost of Monte Carlo algorithms that errs probability at most $\epsilon$.

In Yao's original paper, the relation for Monte Carlo algorithms is given at Theorem 3 without proof. Any hint for proving it?

I'll give it a try on this. I'm going to use Yao's original notation. This way it will be easier to contrast with his paper and his definitions.

Let $\mathcal{I}$ be a finite set of inputs, and let $\mathcal{A}_0$ be a finite set of deterministic algorithms that may fail to give a correct answer for some inputs. Let also $\epsilon(A,x)=0$ if $A$ gives the correct answer for $x$, and $\epsilon(A,x)=1$ otherwise. Also denote by $r(A,x)$ the number of queries made by $A$ on input $x$, or equivalently, the depth of $A$'s decision tree.

  Average Cost: Given a probability distribution $d$ on $\mathcal{I}$, the average cost of an algorithm $A\in \mathcal{A}_0$ is $C(A,d)=\sum_{x\in\mathcal{I}} d(x)\cdot r(A,x)$.

  Distributional Complexity: Let $\lambda\in[0,1]$. For any distribution $d$ on the inputs, let $\beta(\lambda)$ be the subset of $\mathcal{A}_0$ given by $\beta(\lambda)=\{A : A\in \mathcal{A}_0, \sum_{x\in\mathcal{I}} d(x)\cdot \epsilon(A,x)\leq \lambda\}$. The distributional complexity with error $\lambda$ for a computational problem $P$ is defined as $F_{1,\lambda}(P)=\max_{d} \min_{A\in \beta(\lambda)} C(A,d)$.

  $\lambda$-tolerance: A distribution $q$ on the family $\mathcal{A}_0$ is $\lambda$-tolerant if $\max_{x\in \mathcal{I}} \sum_{A\in\mathcal{A}_0} q(A)\cdot \epsilon(A,x)\leq \lambda$.

  Expected Cost: For a randomized algorithm $R$, let $q$ be a probability distribution that is $\lambda$-tolerant on $\mathcal{A}_0$. The expected cost of $R$ for a given input $x$ is $E(R,x)=\sum_{A\in \mathcal{A}_0} q(A)\cdot r(A,x)$.

  Randomized Complexity: Let $\lambda\in[0,1]$. The randomized complexity with error $\lambda$ is $F_{2,\lambda}=\min_R \max_{x\in\mathcal{I}} E(R,x)$.

Now we are ready to go into business. What we want to prove is given a distribution $d$ on the inputs and a randomized algorithm $R$ (i.e., a distribution $q$ on $\mathcal{A}_0$)

  Yao's Minimax Principle for Montecarlo Algorithms \begin{equation}\max_{x\in\mathcal{I}} E(R,x)\geq \frac{1}{2}\min_{A\in \beta(2\lambda)} C(A,d) \end{equation}
  for $\lambda\in[0,1/2]$.

I will follow an approach given by Fich, Meyer auf der Heide, Ragde and Wigderson (see Lemma 4). Their approach does not yield a characterization for Las Vegas algorithms (only the lower bound), but it is sufficient for our purposes. From their proof, it easy to see that for any $\mathcal{A}_0$ and $\mathcal{I}$

Claim 1. $\max_{x\in \mathcal{I}} E(R,x)\geq \min_{A\in \mathcal{A}_0} C(A,d)$.

To get the correct numbers there, we'll do something similar. Given that the probability distribution $q$ given by the randomized algorithm $R$ is $\lambda$-tolerant on $\mathcal{A}_0$ we have that
\begin{align*}
\lambda &\geq \max_{x\in \mathcal{I}}\left\{ \sum_{A\in\mathcal{A}_0} q(A)\cdot \epsilon(A,x) \right\}\\
  &\geq \sum_{x\in\mathcal{I}} d(x) \sum_{A\in \mathcal{A}_0} q(a)\cdot \epsilon(A,x)\\
  &= \sum_{A\in \mathcal{A}_0} q(a)\sum_{x\in\mathcal{I}} d(x) \cdot \epsilon(A,x)\\
  &\geq \min_{A\in \mathcal{A}_0}\left\{ \sum_{x\in\mathcal{I}} d(x) \cdot \epsilon(A,x) \right\}.
\end{align*}
If we replace the family $\mathcal{A}_0$ with $\beta(2\lambda)$ we see that

\begin{align*}
\lambda &\geq \max_{x\in \mathcal{I}}\left\{ \sum_{A\in\mathcal{A}_0} q(A)\cdot \epsilon(A,x) \right\}\\
     &\geq \max_{x\in \mathcal{I}}\left\{ \sum_{A\in\beta(2\lambda)} q(A)\cdot \epsilon(A,x) \right\}\\
     &\geq \sum_{x\in\mathcal{I}} d(x) \sum_{A\in \beta(2\lambda)} q(a)\cdot \epsilon(A,x)\\ &= \sum_{A\in \beta(2\lambda)} q(a)\sum_{x\in\mathcal{I}} d(x) \cdot \epsilon(A,x)\\
     &\geq \min_{A\in \beta(2\lambda)}\left\{ \frac{1}{2}\sum_{x\in\mathcal{I}} d(x) \cdot \epsilon(A,x) \right\},
\end{align*}

where the second inequality follows because $\beta(2\lambda) \subseteq \mathcal{A}_0$, and the last inequality is given by the definition of $\beta(2\lambda)$ where the summation divided by 2 cannot be greater than $\lambda$. Hence,
\begin{equation}\max_{x\in \mathcal{I}}\left\{ \sum_{A\in\mathcal{A}_0} q(A)\cdot \epsilon(A,x) \right\}\geq\frac{1}{2} \min_{A\in \beta(2\lambda)}\left\{ \sum_{x\in\mathcal{I}} d(x) \cdot \epsilon(A,x) \right\}. \end{equation}

By noting that $\epsilon$ maps to $\{0,1\}$ and $r$ maps to $\mathbb{N}$ and Claim 1 above, now we can safely replace the function $\epsilon$ in the inequality above by $r(A,x)$ to obtain the desired inequality.


Is PARITY in QAC_0 (if that even makes sense) As is well known PARITY cannot be done in poly-sized constant-depth circuits, and in
fact const-dept circuits require EXP number of gates.

What about QUANTUM circuits?

a) Can PARITY be done with a quantum circuit that has constant depth and poly number of gates?

b) Does my question even make sense?

The question makes sense, and the short answer is that it's an open problem.

Here's the long answer: Depending on how you define constant-depth unbounded-fanin quantum circuits, you might get different classes. QAC0 is usually defined to have unbounded fanin Toffoli gates and single-qubit gates. QAC0wf is the class where we also allow a "fanout" gate, which copies an input bit to many outputs. (It implements |a>|0>...|0> --> |a>|a>...|a>) This class is really powerful since it contains, besides PARITY and AC0, also ACC0 and TC0.

So the obvious question to ask is whether PARITY is contained in QAC0, and this is an open problem. It is equivalent to asking whether QAC0 = QAC0wf. I guess that the belief is that PARITY is not in QAC0. Further information can be found in the survey Small depth quantum circuits by Bera, Green and Homer.


Assume that $\mathsf{NP} \subseteq \mathsf{P}/\text{log(n)}$, does it imply that $\mathsf{P} = \mathsf{NP}$? I am trying to either prove or refute the claim mentioned in the title.
Any ideas ?

Yes. All advice strings of length log n can be cycled though in polynomial time.
The polynomial time algorithm for SAT would be:
For each of the polynomially many advice strings, try to use it to produce a satisfying assignment for SAT (using self-reducibility) in polynomial time. I would guess this is in the original Karp Lipton paper.


Separation result for proper learning under the uniform vs. adversarial distributions? Does anyone know of a concept class known to be (1) efficiently learnable under the uniform distribution but (1) NP-hard to learn under arbitrary [adversarial] distributions? I mean "learning" in the proper PAC sense.

Here is an example that may not be exactly what you want, but is still emblematic of a general class of problems. In this instance, the hardness is only for agnostic learning, and only for "proper" learning in the sense that the representation class is restricted, and the easyness over the uniform distribution is for trivial reasons.

Width-k conjunctions are NP hard to learn using halfspaces (and in particular using conjunctions) over arbitrary distributions, even for $k > \log(n)$: http://www.cs.cmu.edu/~yiwu/paper/mono.pdf

On the other hand, for $k \gg \log n$, width $k$ conjunctions are trivial to learn over the uniform distribution over examples using conjunctions, since every width-k conjunction will label a $1-1/2^k$ fraction of examples "0", so every width-k conjunction is a good hypothesis.

I would guess that there are similar examples that hold more broadly. Notice that easyness of learning over the uniform distribution holds for any "unbalanced" function, for the same trivial reason. Take a class of functions that is hard to learn even non-agnostically (poly-sized circuits, say). I would think that you could modify the lower-bound proof to hold even if you modify the circuits to be unbalanced: to evaluate to $1$ only on an $\epsilon$ fraction of random inputs. Meanwhile the hard distribution could still be one in which $\Pr[A(x) = 1] = 1/2$.


Is every countable, finite-branching LTS bisimilar to a tree? Let $L$ be a finite set of labels, and let $\mathcal{C}$ be the set of finitely-branching transition systems labeled by $L$ and with a countable set of states.  Let $\sim$ denote the bisimulation relation, and let $\mathcal{C} / \sim$ denote the set of bisimulation equivalence classes of LTS's in $\mathcal{C}$.

Q1:  Does every bisimilarity equivalence class $\alpha \in \mathcal{C} / \sim$ have a tree model?

Let $L\mu$ denote the set of closed formulas in modal $\mu$-calculus.

Q2:  True or false:  $\forall \alpha \in \mathcal{C} / \sim$, $\exists F \in L\mu$ such that models$(F) \cap \mathcal{C} = \alpha$.  Or in plain English, every bisimilarity class of countable and finitely-branching LTS's over $L$ is exactly the set of countable and finitely-branching models of some modal $\mu$-calculus formula.

An answer to either would be helpful, and answers to both would be sublime :)

Q1: Yes, every LTS is bisimilar to its unfolding, which is a tree.
Q2: No, by a cardinality argument. For instance take infinite binary trees with $L=\{a,b\}$. Each tree has countable set of states and is finitely-branching, but you have uncountably many such trees, even up to bisimilarity. However you have only countably many $\mu$-calculus formulas, so some bisimilarity classes are not captured by formulas.
Actually in this setting, a bisimilarity class can be exactly captured by a $L_\mu$ formula if and only if it is the bisimilarity class of a finite structure. The unfolding of a finite structure is called a regular tree. Any formula accepting a non-regular tree must also accept a regular tree, which is not bisimilar to it. See for instance [1] for more details.
[1] The mu-calculus and model checking.
J Bradfield, I Walukiewicz.
Handbook of Model Checking, 871-919


Can any c.e. language with infinite words be decomposed into infinite CFLs with infinite words? Suppose $L$ is a computably enumerable language, can it be decompose into  infinite CFLs with infinite words ?
$$L=\bigcup_{L_i\in CFL }^{\infty}L_i$$

Second question: if it is possible that every $L$ , computably enumerable language with infinity words be decompose into  finite/infinite CFLs with infinite words, can it be be decompose into  finite/infinite unabiguous CFLs with infinite words?

UpDate: Third question, is it possible that every $L$ , computably enumerable language with infinity words be formed by union,complement,intersection,product  (finite/infinite) of unabiguous CFLs with infinite words?

No, we get counterexamples by considering resource-bounded randomness. In fact the gap between c.e. and $\mathsf{CFL}$ is wide.

Let $R$ be exponential-time random. Then $R$ is $\mathsf{NP}$-immune, i.e., it has no infinite subset in $\mathsf{NP}$. In particular it has no infinite subset that is a context-free language.


Counting the number of Hamiltonian cycles in cubic Hamiltonian graphs? It is $NP$-hard to find a constant factor approximation of longest cycle in cubic Hamiltonian graphs. Cubic Hamiltonian graphs have at least two Hamiltonian cycles.

  What are the best known upper bound and lower bound on the number of Hamiltonian cycles in cubic Hamiltonian graphs? Given a cubic Hamiltonian graph, What is the complexity of finding the number of Hamiltonian cycles? Is it #$P$-hard?

In my paper "The traveling salesman problem for cubic graphs" (J. Graph Algorithms and Applications 11(1):61-81, 2007) I proved an upper bound of $2^{3n/8}$ on the number of Hamiltonian cycles, conjectured that the bound could be improved to $2^{n/3}$, and found a family of graphs that have exactly $2^{n/3}$ showing that, if true, the conjectured bound would be tight. Heidi Gebauer ("On the Number of Hamilton Cycles in Bounded Degree Graphs", ANALCO 2008) improved the upper bound to $1.276^n$.

If one allows multigraphs then a cycle that alternates between single and double bonds has $2^{n/2}$ Hamiltonian cycles, and this is tight.


Is there a difference between incompleteness and unknowable? Godel proved that there are statements that are true but not provable. Unproven conjectures such "Twin Primes" might fall into such a class, as I understand. If so, does it mean that we will never know if it's true or false? If true would it only be in the sense that some infinitely large and infinitely fast computer determined so by brute force? Or might it be that the conjecture (or another conjecture) could be neither true nor false and instead forever indeterminate?

Yes, there is a difference.

Incompleteness is a property of a formal system logic. Given a formal system $L$, we say that it is incomplete if there is a sentence $S$ such that $L$ does not prove $S$ and $L$ does not prove $\lnot S$.

Knowing is an activity of an agent, such as a human, or a robot which holds beliefs about its environment. To say that an agent knows a statement $S$ means that the agent correctly believes $S$ is the case.

So the first thing to make clear is that incompleteness and knowing are two very different sorts of things. It makes no sense to say that a formal system of logic "knows" that $S$ holds. And knowledge may be obtained by many different means, some of which are not related to logic. (For instance, I know that it is sunny outside at the moment through direct observation.)

There is a relation though: if an agent uses a sound formal system $F$ to prove a sentence $S$, then it will know $S$. This is what mathematicians do: they prove things so that they can correctly believe them. In that sense, your question may be understood as follows:

  Given the incompleteness of formal systems, are there some mathematical facts which we will never know? What if we give ourselves infinite time to exhaustively search through all proofs?

The answer is this: for a fixed formal system $F$, such as first-order logic with Zermelo-Fraenkel set theory (which is proclaimed by many to be the "official" formal system of mathematics), there is always a sentence $S$ such that $F$ neither disproves nor proves $S$. Even if we had infinite time so that we could check all proofs of $F$, we still would not be able to prove $S$, nor would we be able to disprove $S$ using $F$. There just isn't a proof, and it doesn't matter how much time we have. Consequently, we cannot acquire knowledge of $S$ by using the formal system $F$. This does not mean that $S$ is uknowlable. It just means that $F$ is not helping us determine whether $S$ is true, but there might be another formal system $F'$ which does.

Mathematicians are not forced to use a single formal system $F$ all the time. Mathematical activity and knowing by mathematicians is not the same as a fixed formal system. For instance, mathematicians might agree to add another axiom to set theory, and thus some previously undecidable sentences will become decidable (and therefore knowable). In fact, such changes do occur in the history of mathematics, although it is difficult to track them back in time because mathematicians did not know what a formal system of logic was before the work of the modern logicians (Peano, Frege, Russell, and others).

How, why, and whether mathematicians should change the underlying rules of mathematics is a question for a different day, and a different forum.

Supplemental: Let me address the question in the comments about the Twin Primes. I am going to take the formal system of Peano arithmetic $PA$, but any other formal system would do. Recall that:

$PA$ is consistent if it does not prove a contradiction.
$PA$ is sound if, for any sentence $\phi$, if $PA$ proves $\phi$ then $\phi$ is actually true.

Here we take truth with respect to the intended model, i.e., our mathematical reality (I am not going to get into a discussion of what that might be, the OP is presuming one.) A sound formal system is consistent, but a consistent formal system need not be sound.

Another point of importance is this: truth and provability are different! Do not confuse "we cannot prove something" with "it is neither true nor false". By definition truth is always determined, i.e., a statement must have a truth value, but it need not have a proof.

Let $TP$ be the statement of the Twin Primes conjecture. Here are the possibilities, assuming Peano arithmetic is sound:

If Twin Primes conjecture is true, then there is a sound formal system which proves it, namely Peano arithmetic extended with the axiom stating $TP$.
If Twin Primes conjecture is false, then there is a sound formal system which proves it, namely Peano arithmetic extended with the axiom stating $\lnot TP$.

We can also look at the other side:

If Peano arithmetic proves $TP$ then the Twin Primes conjecture is true.
If Peano arithmetic proves $\lnot TP$ then the Twin Primes conjecture is false.
If Peano arithmetic does not prove $TP$ and does not prove $\lnot TP$, then we may extend it at will with either $TP$ or $\lnot TP$. We will obtain a consistent formal system in either case, but it might be unsound.


Does the System F with pairs have the strong normalisation and subject reduction properties? It is easy to look in a lot of textbooks the proofs of subject reduction and strong normalisation for System F, also, sometimes there are definitions of System F with pairs, where (t,r) is a term, not only an encoding. The question is, what would be the reference for this system?

The treatment of pairs given by encoding, such as that in Proofs and Types, isn't what you usually want since they aren't "surjective pairs", i.e., there is no eta rule.  Let's call surjective pairs, products.

An extension of system F with products and unit is given in: Di Cosmo, 1995,  Isomorphisms of types: from lambda-calculus to information retrieval and language design,  Birkhauser: Basel.


Can interaction combinators implement any interaction net efficiently? It is widely known that interaction combinators can implement any interaction net. My question is, can they do so efficiently? I.e., is it possible to prove that there is no interaction net system that can't be emulated on interaction combinators with the same number of reductions up to a finite constant?

The answer is yes.  It is an immediate consequence of the definition of translation used by Lafont in his paper introducing the interaction combinators.

A Lafont translation $\Phi$ from an interaction net system to another is an arity-preserving map from the symbols (i.e. the atomic agents) of the first system to principal nets of the other.  Basically, a principal net of arity $n$ is a "tree" of agents with some leaves connected to each other and with exactly $n$ free leaves.  In particular, it has exactly one free principal port and $n$ free auxiliary ports, so it may be seen as a "macro-agent".  See Lafont's paper for the exact definition.

A translation $\Phi$ must also satisfy the following simulation property: for all symbols (i.e. agents) $\alpha,\beta$ of the source system,

$$\alpha\bowtie\beta\to\nu\qquad\text{implies}\qquad\Phi(\alpha)\bowtie\Phi(\beta)\to^\ast\Phi(\nu)$$

where the notation $\alpha\bowtie\beta$ stands for an active pair, and $\Phi(\alpha)\bowtie\Phi(\beta)=\Phi(\alpha\bowtie\beta)$ for its translation.

Now, let $M$ be the longest simulating reduction $\Phi(\alpha)\bowtie\Phi(\beta)\to^\ast\Phi(\nu)$ (such $M$ exists because the number of possible active pairs is finite).  It is clear that, if $\mu\to^\ast\mu'$ in $n$ steps the source system, then $\Phi(\mu)\to^\ast\Phi(\mu')$ in at most $M\cdot n$ steps in the target system.  This is stated as Proposition 4 in Lafont's paper.  So the simulation is efficient according to the notion of efficiency given in the question.

The interaction combinators are universal in the sense that every system of interaction nets may be translated in the interaction combinators, in the above sense.  Hence the claim.


Explaining Applicative functor in categorical terms - monoidal functors I'd like to understand Applicative in terms of category theory.

The documentation for Applicative says that it's a strong lax monoidal functor.

First, Wikipedia page about monoidal functors says that a monoidal functor is either lax or strong. So it seems to me that either one of the sources is wrong, or they use the terms differently. Can anybody explain that?

Second, what are the monoidal categories of which Applicative are monoidal functors? I assume that the functors are endo-functors on the standard Haskell category (objects = types, morphisms = functions), but I have no idea what is the monoidal structure on this category.

Thanks for help.

There are actually two uses of the word "strength" in play here.

A strong endofunctor $F : C \to C$ over a monoidal category $(C, \otimes, I)$ is one which comes with a natural transformation $\sigma : A \otimes F(B) \to F(A \otimes B)$, satisfying some coherence conditions with respect to the associator which I will gloss over. This condition is sometimes also pronounced "$F$ has a strength".
A lax monoidal functor $F : C \to D$ is a functor between two monoidal categories $(C, \otimes, I)$ and $(D, \oplus, J)$ with natural transformations $\phi : F(A) \oplus F(B) \to F(A \otimes B)$ and $i : J \to F(I)$, again satisfying a coherence condition with respect to the associators.
A strong monoidal functor $F : C \to D$ is one in which $\phi$ and $i$ are natural isomorphisms. That is, $F(A \otimes B) \simeq F(A) \oplus F(B)$, with $\phi$ and its inverse describing the isomorphism.

An applicative functor, in the sense of Haskell programs, is a lax monoidal endofunctor with a strength, with the monoidal structure in question being the Cartesian products. So this is why you get the paradoxical-sounding term "strong lax monoidal functor".

As an aside, in a Cartesian closed category, $F$ having a strength is equivalent to the existence of a natural transformation $\mathrm{map} : (A \Rightarrow B) \to (F(A) \Rightarrow F(B))$. That is, having a strength means that the functorial action is definable as a higher-order function in the programming language.

Finally, if you're interested in the type theory of Haskell-style applicative functors, I've just blogged about it.


Would derandomizing the reduction from SAT to Unique SAT imply $NP$ and $coNP$ are in $\oplus P$? The Unambiguous SAT problem (USAT) is to determine whether a
given formula has a satisfying assignment, when we are
guaranteed that it has at most one satisfying assignment.

By a theorem Valiant-Vazirani there is probabilistic
reduction from 3SAT to USAT. Given 3SAT formula $\phi$,
over $n$ variables, the algorithm produces $n+2$ formulas
$\phi_i$ with the properties:  if $\phi$ is UNSAT, all $\phi_i$
are UNSAT. Otherwise the probability that $\phi_i$ has exactly
one solution is $\ge \frac18$.

$\oplus P$ is the class of decision problems solvable by a nondeterministic Turing machine in polynomial time, where the acceptance condition is that the number of accepting computation paths is odd.

Since USAT has zero or one solution, $\oplus P$ solves USAT.

  Would derandomizing the reduction SAT to USAT imply $NP$ and $coNP$ are in  $\oplus P$?

This looks plausible to me, though Wikipedia claims
"there is a relativized universe (see oracle machine) where P = ⊕P ≠ NP = PP = EXPTIME" and $P^{\oplus P}$ is not known to even contain $NP$.

Even it can't be derandomized the reduction to USAT appears
very good in practice given $\oplus P$ oracle.

The standard meaning of "derandomized Valiant-Vazirani theorem" is the following.

  There exists a deterministic polynomial time algorithm that, given a 3CNF formula $\phi$, outputs formulas $\psi_1, \ldots, \psi_k$ such that

  If $\phi$ is not satisfiable, then none of the $\psi_i$ are.
  If $\phi$ is satisfiable, at least one of the $\psi_i$ has a unique satisfying assignment.

Indeed, if the above is true, $\mathsf{NP} \subseteq \mathsf{P}^{\oplus \mathsf{P}}$ (a  comment by Joro suggests that this is what he actually meant). Since $\mathsf{P}^{\oplus \mathsf{P}}$ is closed under complement, it follows that $\mathsf{coNP} \subseteq \mathsf{P}^{\oplus \mathsf{P}}$ holds as well.

If a derandomized Valiant-Vazirani theorem holds relative to $\oplus P$, i.e. with the 3CNF formulas augmented by $\oplus P$ predicates, then, using Fortnow's argument in his simplified proof of Toda's theorem, we would get $\mathsf{PH} \subseteq \mathsf{P}^{\oplus \mathsf{P}}$. The usual randomized Valiant-Vazirani theorem implies a randomized version of this: $\mathsf{PH} \subseteq \mathsf{BPP}^{\oplus \mathsf{P}}$. This is one of the lemmas used by Toda.

Note: My original answer had a bug, thanks to Emil Jeřábek for pointing it out.


Is there a quantum NC algorithm for computing GCD? From the comments on one of my questions on MathOverflow
I get the feeling that the question regarding GCD being in $\mathsf{NC}$ vs. $\mathsf{P}$ is akin to the question regarding Integer Factorization being in $\mathsf{P}$ vs. $\mathsf{NP}$.

Is there something like a "quantum $\mathsf{NC}$" algorithm for GCD as there is a quantum polynomial time ($\mathsf{BQP}$) algorithm for Integer Factorization?

Related question: complexity of greatest common divisor (gcd)

First of all, there is a formal definition of "quantum-NC", see QNC on the zoo.

GCD is indeed a good candidate for a problem that could be shown to be in QNC, but it's not known to be in NC. However, finding a QNC algorithm for GCD is still an open problem.

The feeling for which this is believed to be true comes from the fact that the Quantum Fourier Transform can be done in QNC.

Reference: Conclusion section of "R. Cleve and J. Watrous, Fast parallel circuits for the quantum Fourier transform", arXiv:quant-ph/0006004


Is any QMA-intermediate problem known? Similar to the class of classical NP-intermediate problems (e.g. Graph Isomorphism), is there any "QMA-intermediate" problem known, that is in QMA but not known to be QMA-complete? Has this been studied systematically before?

An example would be the computation of ground state energy of the Ising model with transverse magnetic fields, as described by [Cubitt+Montenaro-2013]. From the abstract:

  In this work we characterise the complexity of [the calculation of ground-state energies of 2-body Hamiltonians on qubits with terms restricted to some fixed set S]. Depending on the subset S, the problem falls into one of the following categories: in P; NP-complete; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA-complete. The third of these classes contains NP and is contained within StoqMA.


Computable function $f = \Theta(g)$ with $g$ uncomputable This question most likely has a simple answer; however, I do not see it.

Let $g:\mathbb{N} \rightarrow \mathbb{N}$ be an uncomputable function and $c$ a positive real number. Can there be a computable function $f : \mathbb{N} \rightarrow \mathbb{N}$ such that, for all $n$ large enough: $g(n) \leq f(n) \leq c \cdot g(n)$ (that is $f(n) = \Theta(g(n)$)?

Sure: just take g(n) = n + halt(n) (where halt(n)=1 if TM number n halts, and 0 ow).


How is the iteration space of a nested for-loop containing two sequential nested loops represented? In a general for loop of the form:

for (i = 0, i <= n, i++) {
    for (j = i, j <= n, j++)
        ...
    for (k = i, k <= n, k++)
        ...
}

What form do the inequalities representing the iteration space take? Or what convex polyhedron represents this?

Background
I am looking at the Dragon Book's chapter on parallelisation. This talks in detail of nested loops of the form:

for (i = 0, i <= n, i++) {
    for (j = i, j <= n, j++)
       ...
}

but not of the form described at the top.

The iteration space of d-deep nested loops can be represented as:
$$
\{ i \in \mathbb{Z}^d \mid Bi + b \geq 0 \}
$$

where B is a $d \times d $ integer matrix and b is a vector of length $d$

My question is basically do I have to do anything different when a loop contains multiple inner loops not nested within each other?

This isn't really my area, but I think you want to Google for "the polytope model" or "the polyhedral model", and specifically for "affine-by-statement scheduling". The basic idea is that iterations in a loop nested $d$ deep are turned into a $d$-dimensional polytope, and that each iteration is a point within the polytope. You can then look at data dependencies between the iterations to figure out how to parallelize code (which turn out to correspond to affine transformations of the polytope).


Can one prove the discovery of a P versus NP solution without actually revealing it? Suppose a person has proved that P≠NP. He wants to let the world know that he has solved the P versus NP problem but does not want to reveal that he has proved P≠NP as opposed to P=NP.

Is there any purely theoretical way to do so?

Also any practical evidence he can show to back his claim? (I'm not sure it this part is on-topic)

Or Meir’s comment is almost but not quite right, since it would be satisfied by a proof that P vs. NP is not independent even if the prover didn’t know which. A corrected version is “X is either the hash of a proof that P = NP or the hash of a proof that P $\ne$ NP”, where hash is SHA256, say.  Running that statement through a zero knowledge proof system gives the desired evidence.

However, if I was given such a proof, I would assign higher probability to someone having found a bug in the logical system being used.  It would be quite difficult to surmount that qualification in practice, since bugs in proof systems are fairly common.


Convex Body with minimum expected l2 norm Consider a convex body $K$ centered at origin and symmetric (i.e. if $x\in K$ then $-x\in K$). I desire to find a different convex body $L$ such that $K\subseteq L$ and the following measure is minimized:

$f(L)=\mathbb{E}(\sqrt{x^T \cdot x})$, where $x$ is a point chosen uniformly at random from L.

I am ok with constant factor approximation to the measure.

Some notes - The first intuitive guess that $K$ itself is the answer is wrong. For example consider $K$ to be a thin cylinder in very high dimension. Then we can get $L$ such that $f(L)<f(K)$ by letting $L$ have more volume close to origin.

If we restrict $K$ and $L$ to be both ellipsoids, then your problem can be solved to any accuracy with an SDP. I know this is not what you asked originally, but it seems we have no solution even for this restricted case, and maybe it can help in general.

So let's say $E$ is the input ellipsoid and we are looking to find an optimal enclosing ellipsoid $J$. There exists a linear map $F$ s.t. $E = FB_2$ and a map $G$ s.t. $J = GB_2$, where $B_2$ is the unit ball. Then $\mathbb{E}_{x \sim J}[\|x\|_2^2] = \frac{1}{n}\mathsf{Tr}(G^TG)$. Also $E  \subseteq J \Leftrightarrow J^\circ \subseteq E^\circ$, where $E^\circ$ is the polar body of $E$. Conveniently, $E^\circ = \{x: x^TF^TFx \leq 1\}$ and $J^\circ = \{x: x^TG^TGx \leq 1\}$. It follows that $J^\circ \subseteq E^\circ$ (and therefore $E  \subseteq J$) if and only if $G^TG - F^TF$ is a positive semidefinite matrix.

So the SDP is defined by: given a symmetric PSD matrix $M$, find a symmetric PSD matrix $N$ s.t. $N - M$ is PSD and $\mathsf{Tr}(N)$ is minimized. $N$ can be found by solving the SDP and then an SVD will give the axes and axes lengths of $J$.


Who introduced nondeterministic M-automata, and proved that the finite ones recognize the rational sets over M? Let $M$ be a monoid. The family $\operatorname{RAT}(M)$ of rational sets over $M$ is defined inductively:

If $L$ is a finite subset of $M$, then $L\in\operatorname{RAT}(M)$.
If $K,L\in\operatorname{RAT}(M)$, then $K\cup L\in\operatorname{RAT}(M)$ and $KL\in\operatorname{RAT}(M)$.
If $L\in\operatorname{RAT}(M)$, then $L^*\in\operatorname{RAT}(M)$.

A similar definition can be found in "J.-E. Pin, Mathematical Foundations of Automata Theory", and already "S. Eilenberg, Automata, Languages, and Machines" defines rational sets.

A nondeterministic $M$-automaton $\mathcal A = (Q,\delta,I,F)$ consists of a set of states $Q$, a transition relation $\delta\subset Q\times M\times Q$, a set of initial states $I\subset Q$, and a set of final states $F\subset Q$. If $\delta$ is a finte set, then we say that $\mathcal A$ is finite. A run on $\mathcal A$ is a sequence of the form $$r=q_1u_1q_2\dots u_nq_{n+1}$$ with $(q_iu_iq_{i+1})\in\delta$ for all $1\leq i\leq n$. If $q_1\in I$ and $q_{n+1}\in F$, then we say that it accepts $u=u_1\dots u_n$. The set accepted by $\mathcal A$ is defined as $$L(\mathcal A):=\{u\in M|\mathcal A \text{ has a run } r \text{ that accepts }u\}$$

I found this definition in chapter 7 Automatentheorie of the German text book "Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger: Diskrete algebraische Methoden: Arithmetik, Kryptographie, Automaten und Gruppen”. There we also find the following theorem:

Theorem 7.15 Let $M$ be a monoid and $L\subset M$. Then the following are equivalent:

$L$ is rational, i.e. $L\in\operatorname{RAT}(M)$.
$L$ is accepted by a nondeterministic finite $M$-automaton.
$L$ is accepted by a "spelling" nondeterministic finite $M$-automaton with a single initial state.
$L$ is accpected by a nondeterministic finite $M$-automaton with "rational labels".

I omitted the definitions for "spelling" and "rational labels", because I only want to know who first introduced nondeterministic M-automata, and proved the equivalence of (1) and (2).

According to J. Sakarovich, Elements of Automata Theory, p. 372,

  It seems that the result appears for the first time in [1]; hidden in a footnote of this seminal but difficult article, it was then given many statements, usually in special cases.

[1] C. C. Elgot and J. E. Mezei, On relations defined by generalized finite automata, IBM J. Res. and Develop., vol. 9 (1965), 47–68.

A full proof was also given in S. Eilenberg, Automata, Languages and Machines, vol. A, Academic Press, 1974.


Composition in explicit substitutions In the classical λσ calculus of explicit substitutions, there is the following rewrite rule:

(a[s])[t]  ==>  a[s ∘ t]

where a[s] denotes the application of substitution s to term a.

This seems backward/counterintuitive to me: if we consider substitutions as sorts of functions, then (a[s])[t] can be thought of as t(s(a)), which we could write as (t ∘ s)(a) aka a[t ∘ s] and not a[s ∘ t].

What is the reasoning behind this notation?

Substitutions form a monoid and they act on terms. We have a choice of writing them as either left or right actions. Sometime in the previous millenium someone decided they act on the right (page 5). A right action should satisfy $a [s \circ t] = (a[s])[t]$, so it makes sense to define the operation $\circ$ that conforms to action on the right. That's all.

You could do entirely the same thing with functions and write them as $x \mathbin{//} f$ (as Mathematica does) in which case you would be seriously tempted to define $x \mathbin{//} (f \circ g) = (x \mathbin{//} f) \mathbin{//} g$. In essence you'd move from the category of sets to its opposite.


Should we consider $\mathsf{P} \neq \mathsf{NP}$ a law of nature? Many experts believe that the $\mathsf{P} \neq \mathsf{NP}$ conjecture is true and use it in their results. My concern is that the complexity strongly depends on the $\mathsf{P} \neq \mathsf{NP}$ conjecture.
So my question is:

As long as the $\mathsf{P}\neq\mathsf{NP}$ conjecture is not proven, can/should one consider it as a law of nature, as indicated in the quote from Strassen?
Or should we treat it as a mathematical conjecture
that maybe proved or disproved someday?

Quote:

"The evidence in favor of Cook's and Valiant's hypotheses is so overwhelming, and the consequences of their failure are so grotesque, that
their status may perhaps be compared to that of physical laws rather than that of ordinary mathematical conjectures."
[Volker Strassen's laudation
to the Nevanlinna Prize winner, Leslie G. Valian, in 1986]

I ask this question when reading the post Physics results in TCS?.
It is perhaps interesting to note that computational complexity has some similarities to (theoretical) physic: many important complexity results
have been proved by assuming $\mathsf{P} \neq \mathsf{NP}$, while in theoretical physic results are proven by assuming some physical laws.
In this sense, $\mathsf{P} \neq \mathsf{NP}$ can be considered something like $E = mc^2$.
Back to Physics results in TCS?:

Could (part of) TCS be a branch of natural sciences?

Clarification:
(c.f. Suresh's answer below)

Is it legitimate to say that the $\mathsf{P}\neq\mathsf{NP}$ conjecture in complexity theory is as fundamental as a physical laws in theoretical physics (as Strassen said)?

Strassen's statement needs to be put into context. This was an address to an audience of mathematicians in 1986, a time when many mathematicians did not have a high opinion of theoretical computer science. The complete statement is

  For some of you it may seem that the theories discussed here rest on weak foundations. They do not. The evidence in favor of Cook's and Valiant's hypotheses is so overwhelming, and the consequences of their failure is so grotesque, that their status may perhaps be compared to that of physical laws rather than that of ordinary mathematical conjectures.

I am sure that Strassen had had conversations with pure mathematicians who said something along the lines of

  "You're basing the whole of complexity theory on a house of cards. What if P=NP? Then all your theorems will be meaningless. Why don't you just put forth a little effort and prove that P$\neq$NP, rather than keep building a theory on such weak foundations."

In 2013, when P$\neq$NP has been a Clay prize problem for a dozen years, it may seem difficult to believe that any mathematicians actually had such attitudes; however, I can personally vouch that some did.

Strassen continues by saying that we should not give up looking for a proof of P$\neq$NP (thus indirectly implying that it is indeed a mathematical conjecture):

  Nevertheless, a traditional proof would be of great interest, and it seems to me that Valiant's hypothesis may be easier to confirm than Cook's...

so maybe I would label it as a "working hypothesis" rather than a "physical law".

Let me finally note that mathematicians also use such working hypotheses. There are a large number of mathematics papers proving theorems whose statements run "Assuming the Riemann hypothesis is true, then ...".


A possible error in the semantic chapter of the ISO standard for the Z specification notation I may have found an error in the ISO standards document for the Z specification notation, namely ISO/IEC 13568:2002, "Information technology — Z formal specification notation — Syntax, type system and semantics".
The possible error is in chapter 15 "Semantic relations". This chapter describes the formal semantics of the Z notation. More specifically, the problem is in the following equation appearing in section 15.2.5.1 "Reference expression" on p. 75 that is meant to describe the meaning of a reference expression $i$, where $i$ is a variable name:
$$
[[i]]^{\mathcal{E}} = \lambda M : \text{Model} \bullet M\ i.
$$
This function is defined for every model $M$. But for those models whose domains don't contain the name $i$ the expression $M\ i$ is undefined.
Is this, in fact, an error, or do I overlook something? I'd appreciate an authoritative answer; I too can make speculations.

Firstly, in addition to the Standard from 2002, there is also Technical Corrigendum 1 (TC1) from 2007 which fixes a number of issues.  I don't know of any combined document.  Both documents are available free of charge and links to them are available on the Z notation Wikipedia page.  However, for this particular question, TC1 is not relevant.
Section 15 states that "only sentences of concern here are ones that are already known to be well-formed syntactically and well-typed.".  In a well-typed specification, the semantics in section 15.2.5.1 should not depend on $M$ applied outside its domain.  (Can a well-typed specification be written whose semantics depends on $M$ applied outside its domain?)  I believe this is the thrust of the comment about $\mathit{Model}$ in Table 27 that states "They are applied only to names in their domains, as guaranteed by well-typedness."


Special cases of Graphic TSP In Graphic TSP, you are given an unweighted undirected graph $G$ and the goal is to find a shortest tour in $G$ that visits every vertex at least once. Note that this is NOT same as finding a hamiltonian circuit in $G$. My questions are :

  What is the complexity of Graphic TSP on bounded treewidth graphs ?

Are there any special cases of Graphic TSP with non-trivial polynomial-time algorithms ?

As far as I know, dynamic programming does the trick

Klein's paper on TSP for planar graphs has the details for planar graphs with bounded tree-width.
If the graph is not planar, the dynamic program is slower (dependency on the tree-width is worse).

Philip N. Klein: A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights. SIAM J. Comput. 37(6): 1926-1952 (2008)
(PDF on Philip Klein's website)

Dynamic programming is also used to obtain a PTAS for bounded-genus and minor-free graphs (but as far as I remember the authors do not specify the details of the DP).

Erik D. Demaine, MohammadTaghi Hajiaghayi, Bojan Mohar: Approximation algorithms via contraction decomposition. Combinatorica 30(5): 533-552 (2010)
(Paper on Erik Demaine's website)

Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi: Contraction decomposition in H-minor-free graphs and algorithmic applications. STOC 2011: 441-450

For videos on these PTAS constructions, see Planar TSP and Minor-free TSP (again not focussing on the tree-width part).


Correctness proofs of classic Paxos and Fast Paxos I am reading the "Fast Paxos" paper by Leslie Lamport and get stuck with the correctness proofs of both classic Paxos and Fast Paxos.

For consistency, the value $v$ picked by the coordinator in phase $2a$ in round $i$ should satisfy

  $CP(v,i):$ For any round $j < i$, no value other than $v$ has been or might yet be chosen in round $j$.

For classic Paxos, the proof (Page 8) is split into three cases: $k < j < i$, $j = k$, and $j < k$, where $k$ is largest round number in which some acceptor has reported to the coordinator by phase $1b$ message. I failed to understand the argument for the third case:

  Case $j < k$. We can assume by induction that property $CP$ held when acceptor $a_0$ voted for $v$ in round $k$. This implies that no value other than $v$ has been or might yet be chosen in round $j$.

My question is:

  Why can we assume that property $CP$ held when acceptor $a_0$ voted for $v$ in round $k$?

  It seems that we are using mathematical induction, therefore, what are the basis, inductive hypothesis, and inductive steps?

For Fast Paxos, the same argument (Page 18) goes on. It says,

  Case $j < k$. For any $v$ in $V$, no value other than $v$ has been or might yet be chosen in round $j$.

My question is:

  How is this obtained? In particular, why is "For any $v$ in $V$" here?

  In my opinion, the correctness proof of the case $j < k$ relies (recursively) on those of cases of $k < j < i$ and $j = k$.

  Therefore, how can we conclude the case $j < k$ without first proving $j = k$ completely (namely, missing the subcase of $j = k$ where $V$ contains more than one value)?

Why can we assume that property CP held when acceptor a0 voted for v in round k? It seems that we are using mathematical induction, therefore, what are the basis, inductive hypothesis, and inductive steps?

You're looking at an instance of strong induction. In simple induction you assume the property holds for $n=m$ and prove it holds for $n=m+1$. In strong induction you assume the property holds for $\forall n: n<m$ and prove it holds for $n=m+1$.

Basis (I believe): $j = 0$. That is, the null round (since rounds start at 1). This is trivially true, which is probably why it was not stated explicitly.

Inductive step: Assume $\forall n, n \le j : CP(v; n)$; prove $CP(v; j+1)$ where $j < i$.

Believe it or not, this is only a proof sketch. The real proof is in the Part Time Parliament paper. (Some consider the paper cryptic, others consider it humorous.)

  How is this obtained?

  In my opinion, the correctness proof of the case $j<k$ relies (recursively) on those of cases of $k<j<i$ and $j=k$.

  Therefore, how can we conclude the case $j<k$ without first proving $j=k$ completely (namely, missing the subcase of $j=k$ where $V$ contains more than one value)?

This is again strong induction, so the case $j<k$ does rely on the cases of $k<j$ and $j=k$, but through the induction hypothesis, namely from the previous Paxos round.

General tips for Lamport's proofs.

Lamport uses a technique of hierarchical proofs. For example, the structure of the proof on pages 7-8 looks somewhat like this:

Assume $\forall n, n \le j : CP(v; n)$; prove $CP(v; j+1)$ where $j < i$.

Observation 1
Observation 2
Observation 3
$k = argmax (...)$
case k = 0
case k > 0

case k < j
case k = j
case j < k

Lamport tends to use another type of hierarchy. He'll prove a simpler algorithm, and then prove that a more complex algorithm maps onto (or "extends") the simpler algorithm. This doesn't seem to be happening on page 18, but it is something to look out for. (The proof on page 18 appears to be a modification of the proof a pages 7-8; not an extension of it.)

Lamport relies heavily on strong induction; he also tends to think in terms of sets instead of numbers. So you may get empty sets where others would have zeros or nulls; or set unions where others would have addition.

Proving correctness of asynchronous message-passing systems needs an omniscient view of the system with respect to time. For example, when considering actions in round $i$, keep in mind that the actions for some round $j < i$ may not have happened temporally!. And yet Lamport states these potentially future events in past tense.

Lamports systems and proofs tend to have a variable or set of variables that are only allowed to go in one direction; only incrementing numbers and only adding to sets. This is used extensively in his proofs. For example, on page 8 Lamport shows how he neutered the future ability of $a$ to cast another vote:

  ...Since it set $rnd[a]$ to $i$ upon sending a message, $a$ could not subsequently have cast a vote in any round numbered less than $i$....

It's definitely a brain-stretcher to prove these kinds of systems.

(update): List out the invariants; Lamport uses a lot of invariants when developing and his proofs. They are sometimes scattered throughout the proofs; sometimes they are only present in the machine-checked proof. Reason about each invariant; why is it there? How does it interact with the other invariants? How does each step in the system keep this invariant?

Full disclosure: I hadn't read Fast Paxos until I was asked to answer this question; and only looked at the pages cited. I'm an engineer and not a mathematician; my brush with Lamport's work is based purely on the need to correctly invent and maintain large-scale distributed systems.

My answer relies heavily on my experience with Lamport's work. I have read several of Lamport's protocols and proofs; I professionally maintain a paxos-based system; I have written and proven a high-throughput consensus protocol, and again professionally maintain a system based on it (I'm trying to get my company to allow me to publish a paper). I have collaborated on an insignificant paper with Lamport, in which I met with him thrice (the paper is still pending peer review.)


A partition problem with order constraints In the OrderedPartition problem, the input is two sequences of $n$ positive integers, $(a_i)_{i\in [n]}$ and $(b_i)_{i\in [n]}$.
The output is a partition of the indices $[n]$ into two disjoint subsets, $I$ and $J$, such that:

$\sum_{i\in I} a_i = \sum_{j\in J} a_i$
For all $i\in I$ and for all $j\in J$: $b_i\leq b_j$.

In other words, we have to first order the indices on a line such that the $b_i$ are weakly increasing, and then cut the line such that the sum of the $a_i$ in both sides is the same.

If all $b_i$ are the same, then condition 2 is irrelevant and we have an instance of the NP-hard Partition problem.
On the other hand, if all $b_i$ are different, then condition 2 imposes a single ordering on the indices, so there are only $n-1$ options to check, and the problem becomes polynomial. What happens in between these cases?

To formalize the question, define by OrderedPartition[n,d], for $1\leq d\leq n$,
the problem restricted to instances of size $n$, in which the largest subset of identical $b_i$-s is of size $d$. So the easy case,  when all $b_i$-s are different, is OrderedPartition[n,1], and the hard case, when all $b_i$-s are identical, is OrderedPartition[n,n].

More generally, For any $n$ and $d$, in any OrderedPartition[n,d] instance, the number of possible partitions respecting condition 2 is $O(n 2^d)$. Hence, if $d\in O(\log{n})$, then OrderedPartition[n,d] is still polynomial in $n$.

On the other hand, for any $n$ and $d$, we can reduce from a Partition problem with $d$ integers to OrderedPartition[n,d]. Let $p_1,\ldots,p_d$ be an instance of Partition. Define an instance of OrderedPartition[n,d] by:

For each $i\in \{1,\ldots,d\}$, let $a_i := 2n\cdot p_i$ and $b_i := 1$.
For each $i\in \{d+1,\ldots,n\}$, let $a_i := 1$ and $b_i := i$
[if $n-d$ is odd, make $a_n:=2$ such that the sum will be even].

Hence, if $d\in\Omega(n^{1/k})$, for any integer $k\geq 1$, then OrderedPartition[n,d] is NP-hard.

QUESTION: What happens in the intermediate cases, in which $d$ is super-logarithmic but sub-polynomial in $n$?

Intuitively, the intermediate cases should be neither in P, nor NP-hard.  Perhaps it depends exactly on what we mean by "intermediate case".  Here is one interpretation for which we can prove something.

Note: The Exponential-Time Hypothesis, or ETH, is that it is not the case that, for every constant $\epsilon>0$, SAT has an algorithm running in time $2^{n^{\epsilon}}$.  See also this cs.stackexchange discussion.  As far as we know, ETH is true.

Define OP$_c$ to be the restriction of the OrderedPartition problem to instances where $d \le \log^c n$.  Equivalently, to instances where $n \ge 2^{d^{1/c}}$.  Here we intend OP$_c$ to capture what the post means by "intermediate instances".  We show that these instances are not likely to be in P, nor NP-hard.

Lemma 1. If OP$_c$ is in P for all $c$, then ETH fails.

Proof.  Suppose OP$_c$ is in P for all $c$.  That is, for some function $f$, OP$_c$ has an algorithm running in time $n^{f(c)}$. SAT inputs of size $n$ reduce (via Partition as described in the post) to OrderedPartition$[2^{n^{b/c}}, n^b]$, for some constant $b$ and any constant $c>0$.  So, SAT inputs of size $n$ reduce to OP$_c$ instances of size $2^{n^{b/c}}$, which can be solved in time $2^{f(c)n^{b/c}}$ via the algorithm for OP$_c$.  For any $\epsilon>0$, taking, say, $c=2b/\epsilon$, SAT can be solved in time $2^{c' n^{\epsilon/2}} \le 2^{n^{\epsilon}}$ (for large $n$), violating ETH.$~~~~\Box$

Note: It seems likely to me that even OP$_2$ is not in P, but showing something like that would be similar to showing, say, that SAT has no algorithm running in time $2^{\sqrt n}$.

Lemma 2. If OP$_c$ is NP-hard for some $c$, then ETH fails.

Proof.  Suppose OP$_c$ is NP-hard for some $c$.  Then SAT inputs of size $n$ reduce to OP$_c$ in time $O(n^b)$ for some $b$.  That is, to instances of OrdereredPartition$[n^b, d]$ where $d\le \log^c (n^b)$.  As observed in the post such instances can be solved in time
$n^{O(1)} 2^d = n^{O(1)} 2^{\log^c (n^b)}$, (strongly!) violating ETH.$~~~~\Box$

Probably something cleaner or stronger can be shown.  If I had to guess, I'd define NP$_{d(n)}$ to be the complexity class comprised of those languages that have a non-deterministic poly-time algorithm that, on any input of size $n$, uses at most $d(n)$ non-deterministic guesses.  (Here $d$ could be any function.)  Then OrderedPartition$[n, d(n)]$ is in NP$_{d(n)}$.  Perhaps it is complete for that class under poly-time reductions?  A natural guess for a problem that should be complete for the class would be: given a circuit of size $n$ with $d$ input gates, is there an input that makes the circuit output True?  Or something like that.  (I wonder how this compares to, say, defining SAT$_{p(n)}$ to consist of SAT instances, padded with $p(n)$ useless bits to make the input larger.  When $p(n)$ is super-polynomial but sub-exponential, the problem should be neither NP-hard nor in P.)

p.s. See also Consequences of sub-exponential proofs/algorithms for SAT .


Finding max of two elements in linear time with restriction I have a matrix in the following form:

ID | # Counts for ID | ID's Within Range.
1  | 5               | 1,2,3
2  | 3               | 1,2
3  | 2               | 1,3
....

The idea is that I want to find the 2 id's that when you sum the have the highest count. However, you must first exclude the pairs that overlap. For instance, id's 1 and 2 have the highest count but you can't use them since 1 has 2 within range and 2 has 1 within range. Thus from the table above you would use 2,3 as the sum since they don't overlap.

I would like to do this in O(n) or O(nlogn) time and O(n) storage. It's trivial to do if I first make all ID pairs but that gives me O(n^2). I can also do 2 forloops after sorting the list but that would also be at worst O(n^2) although usually much faster... Any help would be greatly appreciated! THanks!

Ok, so as I understand it, you are given as input an undirected graph (representing the "within range" restrictions) with weights on its vertices, and you want to find a non-adjacent pair of vertices that has maximum total weight. I'm going to interpret linear time as being linear in the number of edges in the input graph, not just the number of vertices, because otherwise it doesn't make sense — you need to have enough time to be able to look at the whole input.

Here's an $O(m+n)$ time solution (simplifying an earlier solution I posted here):

Assume for simplicity that $n$ is a power of two (if not round up).
Find the median of the vertex weights, the median of the highest $n/2$ vertex weights, the median of the highest $n/4$ vertex weights, etc. These median computations take a total of $O(n)$ time, and once completed they give you the set of $2^i$ largest weights for every choice of an integer $i$
For each vertex $v$ with degree $d_v$, let $i_v=\lceil\log_2(d_v+1)\rceil$. Form the pairs $(v,w)$ where $w$ is in the set of $2^{i_v}$ largest vertex weights found during the median calculations.
From the sets of pairs found in the previous step, remove the pairs that correspond to adjacent pairs of vertices (either by using a hash table of edges for fast adjacency lookup, or by using two passes of bucket sort to make a sorted list of both pairs and input edges).
The remaining pairs for each vertex $v$ necessarily include the heaviest nonadjacent neighbor of $v$. In particular the heaviest nonadjacent pair in the whole graph is somewhere in this list of pairs. Compute the weight for each pair and choose the max.


How to do organize papers, urls and other TCS related resources? This question is a try of making
Do you use any article organizers? question suitable for TCS (as suggested in meta answer https://cstheory.meta.stackexchange.com/a/359/6133 )

Question similar -> about organizers, but ...

What organizer do you use, know that are possible to handle TCS related meta-information ?

We organize our knowledge in many ways.

Some of them are hierarchical, as complexity zoo.
Others more like graph -> let's take algorithms as vertices and how they are related with each other as edges
As another extreme, some knowledge we organize like sets and think about it in terms of sets intersections - to be more specific conjunction of criteria, just like flat tags.

I would love to see tool that combines many approaches and enables collaboration between researches, even better, if between strangers (possibly with crowdsourcing).

Above might relate to Academia in general.

What I mean is that TCS people have more CS skills, knowledge and are able to apply it in organizing their own information.

I believe our approach in organizing information is different, partially because we use concepts of graphs, sets, ontology in our job, so they are natural to us and we are able to handle complex models of organizing information, which might use or even might all of mentioned. On the other hand, people from non scientific fields (especially not math related), might have problems with using such models and I believe that's the reason why almost all tools have so much simplified models.

I use "hacks", "tips&tricks" to extend them, but it's not comfortable and not build-in. I even run sometimes analysis tools on my own collections of data - but again, in hacky, why. I would love to see really flexible tools, suitable for CS / TCS people.

I am old school and just use files and folders to organize everything. I have it in Dropbox and I share it with my professors or other students. I think using files and folders although it isn't very fancy but it works well. I have tried special organizers but never used them.


How to prove that a circular prop is uninhabited? Consider the following inductive definition of "ElProp" in coq:

Inductive El : Set :=
  | R1 : El
  | R2 : El
  | R3 : El.

Inductive ElProp : El -> Prop :=
  | C1 : ElProp R1 -> ElProp R2
  | C2 : ElProp R2 -> ElProp R1
  | C3 : ElProp R3.

Observing that "(ElProp R1)" is uninhabited, I state the following theorem:

Theorem excircular : ElProp R1 -> 1>2.

I expect the theorem to be valid, much like the following theorem:

Theorem exfalso : False -> 1>2.

Since there are no inhabitants in "False", inverting "False" is enough to prove "exfalso". But how do I prove "excircular"? In general, how can we prove that circular propositions are uninhabited?

You should use False instead of 1>2 in the conclusion of the theorem. Using indirect ways of denoting an impossible proposition is an unnecessary complication. False is the impossible proposition used in the standard library.

In order to prove that ElProp R1 is uninhabited, you need to prove that ElProp R2 is uninhabited, and vice versa. You need induction over ElProp. The inductive property is that there is inhabitant of ElProp R1 or ElProp R2. (You can also work on proving that there is no way to construct an object with C1 or C2, but this is harder because they have different types.)

~(ElProp R1 \/ ElProp R2)

In order to perform induction over ElProp, you need to work in a generic inhabitant of ElProp. It has the type ElProp R for some R : El. What we want to prove is that for such an inhabitant, R cannot be R1 or R2. Here's a way to state this:

Lemma excircular : forall R, (R = R1 \/ R = R2) -> ~ElProp R.

Now let's prove the lemma. First, expand the ~ abbreviation for fun A => A -> False.

unfold not; intros.

We have a hypothesis of type ElProp R, perfect for induction.

induction H0.

First the C1 case; it's an inductive case: the property we're working on works for an ElProp R1 because it works for the parameter (which is of type ElProp R2), putting it all together with some straightforward first-order logic. We have a hypothesis of type R2 = R1 \/ R2 = R2; once we've applied IHElProp, the goal becomes R1 = R1 \/ R1 = R2. I'll leave doing that manually as an exercise. The built-in tactic tauto makes short work of this case, as well as the symmetric case for C2.

tauto.
tauto.

For the C3 case, we need to show that the hypotheses are contradictory. We have a single hypothesis R3 = R1 \/ R3 = R2. Each branch of the disjunction is an impossible equality because the constructors R1, R2 and R3 are distinct.

destruct H. discriminate. discriminate.
Qed.

Here's a shorter way of proving this lemma. All the intelligence we really need to provide is to use induction on the proper hypothesis, Coq can figure out the rest with some general hints.

Lemma excircular : forall R, (R = R1 \/ R = R2) -> ~ElProp R.
Proof.
  unfold not; intros.
  induction H0; firstorder discriminate.
Qed.

Now we can prove the desired goal. Expand out the ~ abbreviation, apply excircular and let Coq fill in the details.

Theorem excircular1 : ~ElProp R1.
Proof.
  intro. eapply excircular; eauto.
Qed.


On $NP$, $\oplus P$ and $PP$? We know $\oplus P^{\oplus P}=\oplus P$, $PP^{\oplus P}\subseteq P^{PP}$ and $NP\subseteq PP$.

Is $\oplus P^{PP}=PP$?
Why is it difficult to show $NP^{NP}\subseteq PP$?
What is the smallest known class $\mathcal C$ such that $PP\subseteq \oplus P^\mathcal C$ holds? Is there any class smaller than $PP$?

Concerning 3, I believe $\mathrm{PP\subseteq\oplus P^{C_=P}}$, as there are at least $a$ numbers $x<2^n$ satisfying $P(x)$ if and only if the number of $y<2^n$ such that $P(y)\land|\{x\le y:P(x)\}|=a$ is odd. (Note that there is always at most one such $y$. That is, the argument actually shows $\mathrm{PP\subseteq UP^{C_=P}}$. (In fact, it even shows $\mathrm{UP^{PP}=UP^{C_=P}=UP^{C_=P[1]}}$.))


Determine if a structure is a model of an inductively defined predicate My setting is first-order logic. As an example, consider an inductive definition of a linked list:

  $List(l)$ = $Null(l)$  $\vee~(Node(l) \wedge \exists sublist.   List(sublist) \wedge next(l,sublist))$

This is straightforward, a list is a node connected to a sublist. Consider the following structure:

  $Node(A)$, $Node(B)$, $Node(C)$, $Not\_A\_Node(D)$
  $next(A,B)$, $next(B,C)$, $next(C,D)$
  where $A, B, C, D$ are constants.

How do I determine if $A$ is a list? If there is no numerical operator in the predicate, this is very similar to parsing context-free grammar, and I can use either bottom up or top down algorithm. But how to do in the general case?

I'm asking for an automatic method.

If this is not a research-level question, please move it to an appropriate site. Thank you.

@Alessander Botti Benevides: Thanks for your reply. The first equation is the definition. FOL with inductive definitions is described, for example, in this paper:

Cyclic Proofs for First-Order Logic with Inductive Definitions.James Brotherston. TABLEAUX 2005.
http://www0.cs.ucl.ac.uk/staff/J.Brotherston/TABLEAUX05/cyclic_proofs_folind.pdf

What do you mean by the equality in your first formula? In first-order logic (FOL) with equality, one can only apply the equality operator to a couple of terms, not to formulae. Also, your use of equality cannot be considered a case of definition (what could be better depicted by $\triangleq$) since the predicate List appears on both sides of the equality. When creating a definition, the definiendum (in the left side of $\triangleq$) should not be mentioned in the definiens (right side of the $\triangleq$).

By FOL, are you referring to the so-called "first order programming logic" (a formal system specially designed for expressing recursive functions)? Since FOL cannot express transitive closure, I cannot think of a way to properly express recursion in FOL.


Minimum Tree-width of circuit for MAJORITY What is the minimum tree-width of a circuit over $\{\wedge,\vee,\neg\}$ for computing MAJ?

Here MAJ $:\{0,1\}^n \rightarrow \{0,1\}$ outputs 1 iff at least half of its inputs are $1$.

I care only about the size of the circuit (ought to be polynomial) and that an input should be read only once though the fan-out of an input gate can be arbitrary (this crucially affects the tree-width of the circuit - the branching programs obtained from Barrington's theorem from the MAJ $\in$ $\mathsf{NC}^1$, interpreted as skew circuits, do not help). And of course the tree-width is the most crucial thing. I do not care about the depth or any other parameter.

Some of the common circuits for MAJ include:

Wallace tree circuits (e.g.Theorem 8.9 here) which use the 3-to-2 trick to place MAJ in $\mathsf{NC}^1$?
Valiant's monotone $\mathsf{NC}^1$ circuits for MAJ (e.g. Theorem 4 here)
$\log^{O(1)}{n}$ depth sorting network such as Batcher sort
AKS sorting network

  Do any of them have bounded or even polylogarithmic tree-width?

Or in fact,

  Are there reasons to believe that there are no bounded tree-width circuits for
  MAJ?

Notice that every function computed by a bounded tree-width circuit can be computed by an $\mathsf{NC}^1$ circuit even when there is no read-once stipulation via JansenSarma. Thus the implausibility of such a circuit family would indicate
that this bound can be tightened further in the case of read-once circuits.

Answering half of Samir's question.

Let $G=(V,E)$ be a DAG and $V_1,V_2\subseteq V$ be two subsets of vertices of $G$. We denote by $E(V_1,V_2)$ the set of all edges in $G$ with one endpoint in $V_1$ and other endpoint in $V_2$. If $\omega = (v_1,...,v_n)$ is a total ordering of the vertices of $G$ then we let
$$\mathbf{ow}(G,\omega) =
\max_{i}\; |E(\{v_1,...,v_i\},\{v_{i+1},...,v_n\}|$$
denote the width of $\omega$. The online width of $G$ is defined as
$$\mathbf{ow}(G) = \min_{\omega}\; \mathbf{ow}(G,\omega),$$
where the minimum is taken over all topological orderings of the vertices of $G$. Note that the traditional notion of cutwidth of $G$, $\mathbf{cw}(G)$ is defined analogously, except that the minimum is taken over all possible orderings of $G$, irrespectively of whether the ordering is topological or not.
We have the following sequence of inequalities:
$$\mathbf{tw}(G) \leq \mathbf{pw}(G) \leq \mathbf{cw}(G)\leq \mathbf{ow}(G),$$ where $\mathbf{pw}(G)$ and $\mathbf{tw}(G)$ are respectively the pathwidth and the treewidth of $G$.

We claim that MAJORITY of $n$ bits can be computed in online-width $O(\log n)$, and therefore in treewidth $O(\log n)$. The circuit simulates an online algorithm that reads one input bit $b$ at a time and adds $b$ to a counter with $O(\log n)$ bits if and only if $b=1$. At the beggining, the counter is initialized to $0$. At the end the circuit accepts if and only if the value of the counter is greater than n/2. It is easy to see that the gates of a circuit ADD that adds one to the counter register can be topologically-ordered in such a way that it has constant online width, since this circuits just need to implement an carry on operation. The total circuit is a sequence of circuits $C=(ADD_1,ADD_2,...,ADD_n,COMP)$  where the output of $ADD_i$ is plugged to the input of $ADD_{i+1}$, and the output of $ADD_n$ is plugged to the input of COMP. Now if we topologically-order the total circuit $C$ in such a way that all gates of $ADD_i$ appear before the gates of $ADD_{i+1}$ and all gates of $ADD_n$ appear before the gates of COMP, then this topological order has online width $O(\log n)$. This construction is illustrated in Figure 1 of a paper of mine to show that probability amplification can be done in logarithmic online width.

Obs: The depth of the circuit C is $O(n)$.