Is counting maximal cliques in an incomparability graph #P-complete? This question is motivated by a MathOverflow question by Peng Zhang.  Valiant showed that counting maximal cliques in a general graph is #P-complete, but what if we restrict to incomparability graphs (i.e., we want to count maximal antichains in a finite poset)?  This question seems natural enough that I suspect that it has been considered before, but I have not been able to locate it in the literature.

According to this abstract for "The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected" (SIAM J. Comput. 12 (1983), pp. 777-788), counting anti-chains in a partial order is #P-complete. I don't have access to this paper so I can't tell if this result covers maximal anti-chains or not.


Quantum PCP and hardness of simulating of Hamiltonians I have a few questions about Quantum PCP conjecture:

What is the statement of the quantum PCP conjecture?
What implications would Quantum PCP theorem have for simulating of Hamiltonians?
Is it believed adopting Irit Dinur's proof of the classical PCP theorem is likely to lead to a proof of Quantum PCP conjecture?
What background is needed to read articles about the problem?

The copy of the question on MO

As Shor said, there is no QPCP theorem (yet!).  One conjecture (let us call it the QPCP conjecture) is this: consider a graph of N vertices, of degree O(1).  Associate a qudit with each vertex, with Hilbert space dimension O(1).  Let the Hamiltonian be a sum of terms for each edge, each such term acting just on the qudits on the vertices, with operator norm of each such term bounded by O(1), so that the operator norm of the Hamiltonian is O(N).  Then, the conjecture is that there is some epsilon>0 such that it is QMA-hard to approximate the ground state energy of the problem to an accuracy epsilon N.

A slightly stronger conjecture is to consider the case in which each such term acting on an edge is a projector so that the ground state energy is non-negative, and the conjecture is that it is QMA-hard to determine whether the ground state energy is 0 given a promise that if it is not zero then it is at least epsilon N.

There are other versions of the conjecture too, but those are two interesting ones with the most natural relation to physics.  An even stronger conjecture (hence probably an easier one to disprove if you believe that these conjectures are false) is to consider the case in which the Hamiltonian is a sum of commuting projectors.


Is there a continuous version of parallel repetition theorem Raz's Parallel pretition theorem is an important result in PCP, inapproximation, etc. The theorem is fomalized as follows.

A game $G=(\mathcal{S},\mathcal{T},\mathcal{A},\mathcal{B},\pi, V)$, where $\mathcal{S},\mathcal{T},\mathcal{A},\mathcal{B}$ are finite sets, $\pi$ is a distribution on $\mathcal{S}\times\mathcal{T}$, and predicate  $V:\mathcal{S}\times\mathcal{T}\times\mathcal{A}\times\mathcal{B}\rightarrow\{0,1\}$. Define value of the game $$v(G)=\max_{h_A\in\mathcal{H}_A,h_B\in\mathcal{H}_B}\sum_{s,t}\pi(s,t)V(s,t,h_A(s),h_B(t))$$  And $n$-fold game $G^n=(\mathcal{S}^n,\mathcal{T}^n,\mathcal{A}^n,\mathcal{B}^n,\pi^n, V^n)$. The theorem says if $v(G)\leq 1-\epsilon,$ then $v(G^n)\leq (1-\epsilon^c)^{\Omega(\frac{n}{\log\max\{|A|,|B|\}})}$.

My quesion is what happen if the sets are infinite, in a continuous space. Say if $\mathcal{S},\mathcal{T},\mathcal{A},\mathcal{B}$ are subsets of a space, say $R^n$, or more abstract spaces. All the rest are same. Raz's theorem  only gives a trivial upper bound $1$ since the sizes of answer sets are infinite. Obviously $n$-fold value is upper bounded by single copy.  Does exponential decrease also happen in continuous case?  Would it be more interesting to restrict $\mathcal{H}_A,\mathcal{H}_B$ to be collections of continuous functions or $C^{\infty}$ functions or measureable functions?

Does exponential decrease also happen in continuous case?

No.  Feige and Verbitsky [FV02] showed that for every n, there is a game G (with finite sets of questions and answers) such that v(G)≤3/4 and v(Gn)≥1/8.  Because your formulation generalizes games with finite sets of questions and answers of any size, parallel repetition (of any finitely many times) cannot decrease the value of a game from 3/4 to 1/8.

[FV02] Uriel Feige and Oleg Verbitsky.  Error reduction by parallel repetition—A negative result.  Combinatorica, 22(4):461–478, Oct. 2002.  doi:10.1007/s00493-002-0001-0.


Intuition Behind Strict Positivity? I'm wondering if someone can give me the intuition behind why strict positivity of inductive data types guarantees strong normalization.

To be clear, I see how having negative occurrences leads to divergence, i.e. by defining:

data X where Intro : (X->X) -> X

we can write a divergent function.

But I'm wondering, how can we prove that strictly positive inductive types don't allow for divergence? i.e. is there some induction measure that lets us construct a proof of strong-normalization (using logical relations or similar)? And where does such a proof break down for negative occurrences? Are there any good references that show strong normalization for a language with inductive types?

It sounds like you want an overview of normalization arguments for type systems with positive datatypes. I'd recommend Nax Mendler's PhD dissertation: http://www.nuprl.org/documents/Mendler/InductiveDefinition.html.

As the date suggests, this is pretty classic work. The basic intuition is that an ordinal $\lambda$ can be associated to any element of a positive inductive type, e.g. for the data type

Inductive Ord = Zero : Ord | Suc : Ord -> Ord | Lim : (Nat -> Ord) -> Ord

We would get:

$$ \lambda(t) = 0$$
if $t$ is a normal form which is not a constructor
$$ \lambda(\mathrm{Zero}) = 0$$
$$ \lambda(\mathrm{Suc}(o)) = \lambda(o)+1$$
and
$$ \lambda(\mathrm{Lim}(f)) = \sup_n \lambda(f\ n)$$

where $n$ ranges over terms with normal forms. The caveat is that this interpretation is only defined in the 3rd case when $f\ n$ has a normal form as well, which requires some care in the definitions.

One can then define recursive functions by induction over this ordinal.

Note that these data types can be defined already in classical set theory, as indicated in the excellent Inductive Families paper by Dybjer (http://www.cse.chalmers.se/~peterd/papers/Inductive_Families.pdf). However, because the function spaces are so huge, types like Ord require really large ordinals to interpret.


What is the computational complexity of this SAT Variant Given a 3SAT problem. The question being: 'This Problem has exactly K Solutions'?

Now, lets say K=1 (without loss of generality).

If the problem has a exactly 1 solution and the answer is True. So, the partial certificate is that 1 solution. the certificate is partial as it shows there is a solution but without guarantee of exactly 1.
If the answer is False. Then either it has 0 or more than 1 solution.

(a) In case of more than 1 solution, the certificate is any of the 2 or more solutions. This is a complete certificate.

(b) In case of 0 solution, the problem is same as asking does the given SAT have a solution. The certificate being same in 1.

Thus, the problem seems to require a certificate from both NP and co-NP versions. It seems to mean problem lies in NP and co-NP. But then it also is NP-hard. So doesn't that imply NP=co-NP?! What am I missing.

The class ${\bf C_=P}$ is defined to be the set of languagges $L$ such that there exist functions $f \in {\bf \# P}$,$t\in {\bf FP} $ and for all $x, x\in L$ if and only if $f(x)=t(x)$.  Exact-SAT is the standard complete language for ${\bf C_=P}$. Exact-SAT = $\{F, k\} | F$ is a Boolean formula with exactly $k$ satisfying truth assignments.  It is known that ${\bf CoNP} \subseteq {\bf US} \subseteq {\bf C_=P}$  See the paper "On the Power of Deterministic Reductions to ${\bf C_=P}$ " by Frederic Green.


Bipartite matching with degree domination Given an unweighted bipartite graph $G=(V, E)$. Is it true that there always exists a nonempty matching $M\subseteq E$ (not necessarily maximal), such that for every $(i,j)\in E$ with $i$ matched and $j$ unmatched, it holds $\deg(i)>\deg(j)$? Here $(i,j)$ is not ordered, i.e., $i$ can be on either side.

My intuition on why this is true is, when every vertex in $V$ has the same degree, there is always a perfect matching which is the matching we required. For some simple graph structures like trees or unicyclic graphs a maximal matching is desired since the degree of a leaf is always smaller than its parent.

I tried to prove it from Hall's theorem but failed. Part of the complexity of this problem is that the solution is not always a maximal matching. For instance, considering a graph consisting of two 4-cycles $abcd$ and $defg$. Then $M=\{ab,cd\}$ and its symmetrical matchings are the only solutions, which are not maximal.

There does not always exist a matching with your property in a bipartite graph.

Consider for example the graph $G = (V, E)$ where

$V = \{a_1, a_2, a_3, b_1, b_2, b_3, c_1, c_2, d_1, d_2, x\}$ and
$E = \{a_1, a_2\} \times \{c_1, c_2, x\} \cup \{b_1, b_2\} \times \{d_1, d_2, x\} \cup \{(a_3, c_1), (a_3, d_2), (a_3, x), (b_3, d_1), (b_3, c_2), (b_3, x)\}$

This graph is bipartite (with $V_1 = \{a_1, a_2, a_3, b_1, b_2, b_3\}$ as one part and $V_2 = \{c_1, c_2, d_1, d_2, x\}$ as the other). Every vertex in this graph except $x$ has degree $3$. Vertex $x$ has degree $6$.

Suppose, for the sake of contradiction, that a matching $M$ with your property exists. Consider any two adjacent vertices $v_1$ and $v_2$ that have the same degree. It turns out that the conditions on $M$ imply that both of these vertices have the same matched-or-not status (i.e. either both or neither of the vertices must be matched in $M$). This can be proved very simply by contradiction: suppose one vertex (wlog $v_1$) is matched and the other is not; then since there is an edge between them, the given property on $M$ tells us that $deg(v_1) > deg(v_2)$, which is a contradiction.

Thus, the matched-or-not status of adjacent vertices of the same degree is the same. Then if a set of vertices has the property that every vertex has the same degree and the subgraph induced by these vertices is connected, we can apply this rule multiple times to conclude that all vertices in the set must have the same matched-or-not status. In particular, in $G$ the matched-or-not status of every vertex in $V \setminus \{x\}$ must be the same since these vertices all have degree-$3$ and are connected. In other words, either every vertex in $V \setminus\{x\}$ is matched in $M$, or no such vertex is matched in $M$. If the matched-or-not status for these vertices is "matched" then every vertex in the $V_1$ part of the bipartition is matched in $M$; this is impossible since there are more vertices in $V_1$ than in the other part $V_2$. If the matched-or-not status for these vertices is "not matched" then the only vertex in $G$ that can be matched in $M$ is $x$; since a non-empty matching (as $M$ must be) matches at least two vertices, we see that this case is also impossible.

By contradiction, a matching $M$ with the property in question does not exist in $G$.


Why is it important that the secret is at the end when signing with MD5? it is often said that when using the MD5 algorithm to sign some arbitrary information, the shared secret has to be at the end. Why?

See "extension attacks" in the Merkle-Damgard construction. This issue arises in the use of hash functions for message authentication.

In short, putting the secret in the beginning allows the attacker, given a message and its hash, to forge any message which has the given message as a prefix. This is a problem for naive codes but is avoided by well-known codes like HMAC.


what is the real difference between traveling salesman problem (TSP) and vehicle routing problem (VRP)? Both problems are well-known NP-hard problems with great similarities. In fact, I do not see the real difference between these two problems. It seems relatively easy to model TSR in the form of VRP and likewise inversely. So what is the essential point to make VRP a different problem from TSP?

p.s. I cannot find appropriate tags for this question.  I think important problems such as TSP should be tags themselves.

The Vehicle Routing Problem was introduced in G. B. Dantzig and J. H. Ramser, The Truck Dispatching Problem, Management Science Vol. 6, No. 1 (Oct., 1959), pp. 80-91.

The authors underline the differences with TSP in this way:

... The "truck dispatching problem" formulated in this paper may be considered as a generalization of the TSP ...

... The salesman may be required to return to the "terminal point" whenever he has contated $m$ of the $n-1$ remaining points, $m$ being a divisor of $n-1$. For given $n$ and $m$ the problem is to find loops such that all loops have a specified point in common and total loop length is a minimum. Since the loops have one point in commom, this problem may be called the "Clover Leaf Problem"...

... The TSP may also be generalized by imposing the condition that specified deliveries $q_i$ be made at every point $P_i$ (excepting the terminal point). If the capacity of the carrier $C$ is greater than $\sum_i q_i$, the probelm is formally identical with the TSP in its original form since the carrier can serve every delivery point on one trip which links all the points...

In the simplest VRP formulation, all trucks (vehicles) have the same capacity and only one product is to be delivered to each point $P_i$. Other common constraints are: time constraints (or total length of each route), time windows, precedence relations between points.

To summarize: the main difference between a TSP and VRP is that the salesman must return to the starting location after some points have been visited.

For what regards "It seems relatively easy to model TSR in the form of VRP and likewise inversely."; the reduction from TSP to VRP is immediate, the opposite direction VRP $\leq_m^p$ TSP is surely more complex (and probably it requires other intermediate reductions).


Is $L \subset 1NL$ when $L \neq NL$? A log-space Turing machine has a read-only input tape, a write-only output tape and uses at most $O(\log n)$ space in its read-write work tapes. The classes $L$ and $NL$ contain those languages which are decided by deterministic or nondeterministic log-space Turing machines, respectively. The two-way Turing machines may move their head on the input tape into two-way (left and right directions) while the one-way Turing machines are not allowed to move the input head on the input tape to the left.

Hartmanis and Mahaney have investigated the classes $1L$ and $1NL$ of languages recognizable by deterministic one-way log-space Turing machine and nondeterministic one-way log-space Turing machine, respectively. They have shown that $1NL \subseteq L$ if and only if $L=NL$.

See the paper here(it is free to download):

https://ecommons.cornell.edu/handle/1813/6253

I wonder this question:

Is $L \subset 1NL$ when $L \neq NL$?

Moreover, I wonder this another question:

Is there any reference that shows whether at least one of the options $L \subset 1NL$ or $1NL \subset L$ or $L = 1NL$ should be true?

Thanks in advance!!!

Define the language $BACKPOINTER$ to have words of length $n+t\log n$, divided to $1+t$ parts, one of length $n$ and the rest of length $\log n$, by commas such that $BACKPOINTER=\{(x,p_1,\ldots,p_t)\mid x_{p_i}=1 \forall i\}$.
It should follow from some standard one-way communication complexity bound that $BACKPOINTER$ needs at least $t$ bits of memory stored after $x$ is read. So for any $t\gg \log n$, $BACKPOINTER\in L\setminus 1NL$.

ps. Note that $BACKPOINTER\in 1co\text{-}NL$.


Finding a minimum directed cut that splits a weakly connected bipartite graph into two such non-edgeless graphs Consider a directed, weakly connected bipartite graph $G = (U, V, E)$ where $U$ and $V$ are sets comprising the nodes of $G$, and $E \subseteq U \times V$ is the set of edges. The task is to find a minimum directed cut, say $C \subseteq E$, such that the graph $G = (U, V, E - C)$ consists of two disconnected bipartite graphs each of which are (1) not edgeless, and (2) weakly connected. The cut $C$ is directed in the sense that all edges in $C$ originate from the same bipartite subgraph, and minimum in the sense that it has the lowest cardinality possible.

Is this problem studied? If so, what is the computational complexity of the best known algorithm that solves it? If not, original algorithm ideas are more than welcome!

I'll provide a naive approach which give $O(m^2 \cdot max_f)$ running time but shows the problem is P. First turn the graph to undirected graph. Suppose one edge is in first graph and the other in the second graph, contract both of them and name them $s,t$. We can find a minimum edge cut that separates s and t in time max_f which is a running time of best maximum flow algorithm on unit weight graph. We run this algorithm for all possible pair of edges. But why this works? trivially there is no smaller cut and the two sides are not edgeless. On the other hand if a graph G is connected  minimum edge cut C between two vertices s, t always cuts the graph into two connected subgraphs.


Number of edge induced subgraphs with given vertex parity Let $G$ be a graph. Let $O$ be the number of edge induced subgraphs of $G$ having an odd number of vertices.

  Questions

  How hard is to compute $O$?
  How hard is to compute the parity of $O$?

Related questions:

Number of (vertex induced) subgraphs with given edge parity Answer: Tractable.
Number of (edge induced) subgraphs with a given number of nodes Answer: #P-hard.

Update 11/05/2013 18:00

By a reasoning similar to the one in the answer to the first question referenced above, we can create a Holant by placing on each vertex $v$ a constraint $f_v$ which returns $1$ when all the edges incident to $v$ have been assigned $0$, and $-1$ otherwise. For a specific assignment to the edges ($0$ means not selected, $1$ means selected) we get an edge induced subgraph such that the number of its vertices is odd if and only if the product of the Holant returned $-1$. The summation of the Holant is thus equal to the difference $E - O$ between the number of edge induced subgraphs having an even number of vertices and the number of edge induced subgraphs having an odd number of vertices: as $E + O$ is known, we can determine $E$ and $O$.

Now, if I correctly understand the paper A Dichotomy for Real Weighted Holant Problems, the constraint $f_v$ is symmetric (obviously) and affine: by Theorem 3.2 this means that we can compute $E-O$ in polynomial time.

Am I right?

For simplicity, let's restrict ourselves to $k$-regular graphs.

The first part of your update is correct.  Changing notation slightly from what you have introduced, let me define $n_e$ (resp. $n_o$) to be the number even (resp. odd) edge-induced subgraphs of a given graph $G$.  For the (arity $k$) signature $f = [1, -1, -1, \dotsc, -1]$, the Holant problem Holant($f$) does indeed correspond to the problem "Given a graph, compute $n_e - n_o$."  To see this, fix a subset of edges $E'$ (i.e. the subset of edges assigned 1) and consider a vertex $v$.  If none of the incident edges of $v$ are in $E'$, then $v$ is not in the edge-induced subgraph defined by $E'$ and the constraint at $v$ contributes a factor of 1 to the weight of $E'$.  Otherwise, some incident edge of $v$ is in $E'$, then $v$ is in the edge-induced subgraph defined by $E'$ and the constraint at $v$ contributes a $-1$ to the weight of $E'$.  Summing over the weights of all subsets of the edges gives $n_e - n_o$.  Since $n_e + n_o = 2^{|E(G)|}$, we could solve for $n_e$ and $n_o$ if we could knew $n_e - n_o$.

The second part of your update is incorrect.  The $k$-ary signature $f = [1, -1, -1, \dotsc, -1]$ is not affine for $k \ge 3$.  For a (rather explicit) list of the affine signatures, see page 7 of this paper.  For $k \ge 3$, this signature defines a #P-hard Holant problem. To determine the complexity of this problem, notice that $f$ has the tensor rank 2 decomposition $f = 2 [1, 0]^{\otimes k} - [1,1]^{\otimes k}$. Let $\omega_{2k}$ be a $2k$th primitive root of unity. Then $f = [\sqrt[k]{2}, 0]^{\otimes k} + [\omega_{2k},\omega_{2k}]^{\otimes k}$.  Under a holographic transformation by the inverse of $M = \begin{bmatrix} \sqrt[k]{2} & \omega_{2k} \\ 0 & \omega_{2k} \end{bmatrix}$, we have the bipartite Holant problem $\operatorname{Holant}([\sqrt[k]{4}, \omega_{2k} \sqrt[k]{2}, 2 \omega_{2k}^2] | =_k)$.  This problem is #P-hard by Theorem 22 in this paper, even when also restricting to planar graphs.

For $k \le 2$, $f$ is actually affine, so the problem is tractable, but it is also tractable for a much simpler reason as well.  Any Holant problem using only constraints of arity at most 2 is tractable using matrix product and trace.


Different algorithms for longest increasing subsequence The longest increasing subsequence problem has a simple and elegant $O(n \log n)$ time solution via patience sorting.

Such a basic and well-studied problem, however, should have a number of different solutions, just as sorting does.

Are there other distinct $O(n \log n)$ time algorithms for this problem?

There is a $O(n \log \log n)$ time algorithm to solve the longest increasing subsequence problem. You may find this and the paper by Sergei Bespamyatnikh , Michael Segal helpful.


Do we know whether P^#P = NP^#P? I thought the relation between P using a #P-oracle and NP using a #P-oracle is still unknown (or equivalently the relation between P^PP and NP^PP).

Recently, I have read in a journal article that P^#P = NP^#P (citing Toda's publication "PP is as hard as the polynomial time hierarchy"). As far as I remember this relation was posed as an open question in Toda's paper.

I am very confused at the moment and I would be glad if someone could clarify this situation. Thanks a lot.

This is an open question. If it is to be true the consequences would imply the collapse of the ${\bf Counting-Hierarchy}$, ${\bf CH}$ for short. In the paper "On the closure properties of #P in the context of PF o #" by Ogihara, Toda, Watanabe and Thierauf" on proposition 2.1 it is stated that

${\bf NP ^{PP}} \subseteq {\bf P^{\#P^{[1]}}} $ if and only if ${\bf CH} = {\bf P^{\#P^{[1]}}} $ if and only if ${\bf FP ^{CH}} \subseteq {\bf FP^{\#P^{[1]}}} $.


Can a hereditary graph class contain almost all, but not all, n-vertex graphs? Let $Q$ be a hereditary class of graphs. (Hereditary = closed with respect to taking induced subgraphs.) Let $Q_n$ denote the set of $n$-vertex graphs in $Q$. Let us say that $Q$ contains almost all graphs, if the fraction of all $n$-vertex graphs falling in $Q_n$ approaches 1, as $n\rightarrow\infty$.

Question: Is it possible that a hereditary graph class $Q$ contains almost all graphs, but for every $n$ there is at least one graph that is not in $Q_n$?

The answer is no - for a fixed $Q$ let $t$ be the number of vertices in the smallest graph $H$ not in $Q$. Now, consider $n$ much bigger than $t$. For a random graph on $n$ vertices, the probability that the $t$ first vertices induce $H$ depends only on $t$. Partitioning the vertex set into $n/t$ disjoint sets of size $t$ and considering the probability that none of the sets are equal to $H$ shows that the probability of being in $Q$ tends to $0$ as $n$ increases.


Semantic definition of strict positivity for a functor If we consider a definition of recursive type as:

F : Type -> Type;
T = fix F;

It is customary to talk about the functor F needing to be positive or strictly positive in order to avoid non-termination in the recursor.

I'm familiar with the usual syntactic definition of strict positivity, but I'm looking for corresponding semantic definitions, especially ones that can be expressed in the system (rather than being defined at the meta level).

The closest I have found is the work on containers (Abbott et.al., 2005), but it appears to require some "creativity" to come up with a container corresponding to a given functor and then prove equivalence between the two.  I'm looking for something that talks more directly about the properties of F.

One semantic criterion is preservation of $\omega$-colimits, or $\omega$-cocontinuity. AFAIK, initial algebras of such functors correspond to finitary inductive types in type theory. The construction of initial algebras, given by Adámek's theorem, can be formalized inside type theory as well. It's described in this paper and there's a Coq formalization for it. Probably there is a generalization of this to transfinite colimits, which would give us infinitary inductive types, but for this I don't know any formalization.


Reduction from SAT to binary matrix subset problem I'm trying to understand the answer by @Denis on this question, where he showed a way to reduce from SAT to the binary matrix column subset selection problem. The reason I'm having to post a new question is because I have not an account on cstheory.stackexchange before, so I'm unable to ask him directly.

In his explanation of his method in the comments, he mentioned that by the construction of the matrix, one is forced to pick only 1 of the $x_i, \neg x_i$ columns for all $i \in [1,m]$, i.e. forcing an assignment to the CNF (I believe due to the earlier claim that one must choose $m$ out of the $2m$ columns). I am struggling to understand as to why this is the case - I see nothing wrong at the moment with choosing more than $m$ columns or choosing both the columns representing $x_i$ and $\neg x_i$.

The original problem asks for a given $k$ whether there is a solution with this $k$, so we can choose to instantiate $k=m$. This means we are forced to pick $m$ columns.
Then if you choose both $x_i$ and $\neg x_i$, there will be a $j$ so that the line number $j$ is left with only zeros, so this choice cannot be good.


Construct proof systems for common algorithmic task, like equivalence of regular expressions A propositional proof system according to Cook and Reckhow for a language $L \subseteq \Sigma^{\ast}$ is a deterministic polynomial time function $f : \Sigma^{\ast} \to L$ that is onto.

For $y \in L$ a word $x \in \Sigma^{\ast}$ with $f(x) = y$ is called a proof for $y$.

Here is a post on the intuition, but I do not get it when I want to apply it.

For example, if I consider the language
$$
 EQUIV = \{ (u,v) : \mbox{$u$ and $v$ are equivalent regular expressions} \}
$$
then I know an algorithm for this language would be to convert these regular expression into NFA's, determinize them and minimize them and then check if they are isomorphic.

But how would a proof system for $EQUIV$ look like? Would it be a surjective function $f : \Sigma^{\ast} \to EQUIV$ where the arguments somehow codes the regular expression, DFA's for them and an isomorphism between those DFA's? Then $f$ would simply check if the isomorphism is a valid isomorphism between the DFA's, guess this would be a simple task.

But how to check that the regular expression belong to the DFA's, I am not sure if that would be an easy task as it involves computing DFA's for regular expressions, which might take exponential time, or? Or could it code additional DFA's which could easily be composed to REGEXPs with some fixed algorithms (but is it then easy to check that these give isomorphic minimal DFA's as the given ones? I mean that includes to find an isomorphism, which is not easy, so code that again into the input?).

Or am I on the wrong track, might a proof system look totally different?

You have a non-deterministic algorithm deciding the problem.
If you want to think of it as a proof system for $EQUIV$, then
the proof of $(u,v) \in EQUIVE$ is just the string
representing the computation of your algorithm on $(u,v)$.
The proof checker just checks that
the given string is in fact an accepting computation of your algorithm on $(u,v)$.

Use the alternative definition of proof system, it is often easier to think about: an algorithm that gets a formula and a string and checks if the string of a proof of the formula, rather than a function that checks if a given string of is proof and if so outputs the proven formula.


What bounds can be put on counting reachable nodes in a dag? Given is a dag. You want to label each node by how many nodes are reachable from it. $O(V(V+E))$ is a trivial upper bound; $\Omega(V+E)$ is a lower bound (I think). Is there a better algorithm? Is there reason to believe the lower bound can be improved (related: what exactly is known about lower bounds for transitive closure)?

Motivation: I had to do this a couple of times while representing fol formulas as dags.

Edit: Please note that simply doing $c_x=1+\sum_{x\to y}c_y$ counts paths, not reachable nodes. (I added this because apparently many people thought this simple solution would work by the votes I saw on a now-deleted answer.) In fact, this problem appears precisely when you want to do something interesting with 'shared' parts, nodes reachable by more than one path. Also, I say dag, because if they are solved, then solving digraphs is easy.

The transitive closure of a directed graph with $m$ edges and $n$ vertices can be computed
slightly faster than $O(mn)$ time, but not by much. An $O(n^2 + mn/\log n)$ time algorithm is mentioned in a footnote of Chan's 2005 WADS paper on APSP (journal version in Algorithmica 2008). A slight improvement to $O(n^2 + mn \log(n^2/m)/\log^2 n)$ can be found in the ICALP'08 paper "A New Combinatorial Approach for Sparse Graph Problems " by Blelloch, Vassilevska and Williams.
That being said, I don't know whether counting descendents is easier than actually finding them


Finding the shortest path in the presence of negative cycles Given a directed cyclic graph where the weight of each edge may be negative the concept of a "shortest path" only makes sense if there are no negative cycles, and in that case you can apply the Bellman-Ford algorithm.

However, I'm interested in finding the shortest-path between two vertices that doesn't involve cycling (ie. under the constraint that you may not visit the same vertex twice). Is this problem well studied? Can a variant of the Bellman-Ford algorithm be employed, and if not is there another solution?

I'm also interested in the equivalent all-pairs problem, for which I might otherwise apply Floyd–Warshall.

Paths with no repeated vertices are called simple-paths, so you are looking for the shortest simple-path in a graph with negative-cycles.

This can be reduced from the longest-path problem.  If there were a fast solver for your problem, then given a graph with only positive edge-weights, negating all the edge-weights and running your solver would give the longest path in the original graph.

Thus your problem is NP-Hard.


Proof Strategies on P versus BPP Typically to show $P=NP$, one has to show an NP complete problem has a polynomial time solution and to show $P\neq NP$, has to show an NP complete problem has superpolynomial lower bound. These are broadly the general techniques.

For showing $P=BPP$ or $P\neq BPP$ what strategies can be used or used? It is not like there is one problem in BPP that can either be shown to be derandomized or not be derandomized that solves the question.

Although there aren't any problems known to be $\mathsf{BPP}$-complete (and Sipser gave an oracle relative to which $\mathsf{BPP}$ doesn't have complete problems), one topic to look at here is pseudorandom generators. The existence of a good enough pseudorandom generator implies $\mathsf{BPP} = \mathsf{P}$. This isn't $\mathsf{BPP}$-complete, but it does have the feature that a single algorithm could show $\mathsf{BPP}=\mathsf{P}$.

Also, although not $\mathsf{BPP}$-complete, Polynomial Identity Testing is a good single problem in $\mathsf{BPP}$ to focus on derandomizing. Many problems in $\mathsf{BPP}$ are actually in $\mathsf{RP}$ or $\mathsf{coRP}$, often due to the Schwarz-Zippel Lemma (in fact, there are apparently very few known candidates that are known to be in $\mathsf{BPP}$ but not in $\mathsf{RP} \cup \mathsf{coRP}$, see this related question), so derandomizing PIT would derandomize a whole bunch of problems. Furthermore, derandomizing PIT is known to imply strong lower bounds on $\mathsf{NEXP}$.


Constructing uniquely satisfiable formulas Unique SAT ={$\phi$| $\phi$ has unique satisfying assignment } represents an important class of computational problems. I recall reading that P=NP iff Unique SAT is in P (I don't remember where I read it. Notice that Unique SAT is CoNP-hard and Unique SAT= SAT\ Double SAT where Double Sat={$\phi$| $\phi$ has two or more satisfying assignments})

I'm looking  for an efficiently computable function $f(s_n)= \phi$  such that formula $\phi$ is uniquely satisfied by assignment $s_n$ where $n$ is the number of variables.

Also, Can $f$ be made a bijection?

Edit 1: Input is a binary string $s_n$, output is a 3SAT formula in CNF.

Basically, I'm looking for an efficient algorithm that computes $f$. Ideally, such algorithm would allows us to construct hard instances for Unique SAT.

EDIT 2: I'm seeking an algorithm that is able to generate all uniquely staisfiable instances not just the easy cases given so far.

If I understand your question correctly, you're looking for ways to generate lots of non-trivial uniquely satisfiable 3SAT instances.
There's a tension between your desire to find a way to generate all uniquely satisfiable instances and your desire to find a way to generate hard uniquely satisfiable instances.  For the moment let's ignore your uniqueness condition. Then I know there has been some work on this problem, e.g., see Generating satisfiable problem instances by Achlioptas, Gomes, Kautz, and Selman.  You might think that they proceed by generating random clauses and discarding the clauses that are inconsistent with a randomly chosen but fixed assignment.  But although this method will in principle generate every satisfiable instance (with some probability), it tends to produce instances that are easy to solve.  To get hard instances, Achlioptas et al. adopt the approach of picking some known hard problem and generating instances based on that.
I suspect that a similar dilemma will arise for uniquely satisfiable instances.  My guess is that a randomized method that generates every uniquely satisfiable instance with some probability will tend to produce easily solved instances.  If you want hard instances, your best bet is probably to pick some cryptographic problem (where the unique solution is the cryptographic secret, e.g., a factorization) and generate instances based on that.


Nested automatization of type inference of forall elimination Following a previous question about how to automatize the type inference in a forall elimination of an application, now suppose we want to do the same but for a nested forall, say $(\Lambda X_1.\Lambda X_2.\dots.\Lambda X_n.\lambda x:U.t)$ is a function of type $\forall \vec{X}.U\to T$ and we want to apply it to an argument of type $V$. Then we need to find types $W_1,\dots,W_n$ such that $U[\vec{X}/\vec{W}]=V$.

This is clearly another unification problem. Can we solve this problem as easily as the problem with one variable? What is the algorithm for doing this?

This can be solved as easily as the other problem, as in this solution. It's basically unification.

Ensure that the variables $X_1,\ldots,X_n$ do not appear in $V$. Replace
any variables that do by fresh ones and perform appropriate substitution into $W$.
Unify $V$ and $W$ using an algorithm that finds the most general unifier (mgu). The essence of this is in the other algorithm, or, for example, page 10 of this.
The resulting mgu $[\bar{X}/\bar{W}]$ is the subtitution you require.


Commonality of minimal Kolmogorov structure functions A typical $B$ is difficult to define precisely.  Intuitively, it is the sort of bitstring that will be generated most of the time by randomly drawing 0s and 1s.  However, the concept can be clarified by examining properties.  A property $p$ applies to typical $B$s if the proportion of $B$s having that property is greater than or equal to 0.5,
\begin{align*}
\frac{|\{B: p(B)\}|}{|\{B\}|} \geq 0.5.
\end{align*}

For instance, a typical $B$ has the property that $K(B) = \ell(B)$.  In other words, a typical $B$ is not compressible.

Is the minimal Kolomgorov structure function (MKSS) a typical bitstring in some TM encoding?  In other words, is there some TM encoding such that a bitstring generated by randomly drawing 0s and 1s likely to be a MKSS?

I think the answer is no, because incompressible bitstrings do not have a nontrivial MKSS, and most bitstrings are incompressible.

Lemma 1 below shows that with a standard TM encoding, the fraction of strings that are MKSSs is bounded away from both 0 and 1. This answered a question posed in the original post.

Lemma 2 shows that there is a (non-standard) encoding in which almost all strings are MKSSs.  This answers the question in the current post affirmatively.

Lemma 3 shows that there is a (non-standard) encoding in which almost no strings are MKSSs.

Let $\mu(n)$ be the probability that a random string of length $n$ or less is a minimal Kolmogorov structure function, as defined in your previous post.

Lemma 1. For any conventional TM encoding scheme,
$$0 < \liminf_{n\rightarrow\infty} \mu(n) < 1$$

Proof. First we show that $\liminf_{n\rightarrow\infty} \mu(n) < 1$.  For any string $B$, let $P^*_B$ be an MKSS for $B$.  Define $P'_B$ to be the TM obtained from $P^*_B$ by adding a useless state.  Then $|P'_B| \le |P^*_B|+c$ for some fixed constant $c$, and $P'_B$ is not an MKSS.  It follows that, for every $n$, for every string of size at most $n$ that is an MKSS, there is a string of size at most $n+c$ that is not an MKSS.  Hence, among the strings of length at most $n+c$, the number that are not an MKSS is at least the number of strings of length at most $n$ that are an MKSS.  It follows that $1-\mu(n+c) \ge \mu(n)/c'$ for $c'\approx 2^c$.  It follows that $\liminf_{n\rightarrow\infty} \mu(n) \le 1-1/(c'+1) < 1$.

Next we show that $\liminf_{n\rightarrow\infty} \mu(n) > 0$.  For any string $B$, we have that $P^*_B$ is an MKSS, and $$|P^*_B| \le K(B) \le |B| + c_1$$ for some fixed constant $c_1$.  So, for every $n$, the number of strings of length at most $n+c_1$ that are an MKSS is at least the number of strings of length at most $n$.  It follows that $\mu(n+c_1) \ge 1/c_2$ where $c_2\approx 2^{c_2}$. It follows that $\liminf_{n\rightarrow\infty} \mu(n) \ge 1/c_2 > 0$.  $~~\Box$

Next we show that using non-standard TM encoding schemes we can make almost all strings MKSSs.  Fix arbitrarily large constant $k\ge 0$. Given a binary string $B$, if $B=1^kM$ ($k$ ones followed by some string $M$) then $B$ encodes the TM whose standard encoding is $M$.  Otherwise, $B$ encodes a TM that outputs $B$.  (This is a TM encoding scheme in the sense that there is a computable function mapping standard encodings to equivalent non-standard encodings, and vice versa.)

Lemma 2. For this TM encoding scheme, for any $n$, if $B$ is a random string of length at most $n$, then $B$ is an MKSS with probability at least $1-O(1/2^k)$.

Proof.
Let $K'(B)$ and $P'_B$ denote the Kolmogorov complexity and MKSS of $B$ with respect to this non-standard TM encoding scheme.
Let $K(B)$ denote the Kolmogorov complexity of $B$ with respect to the standard TM encoding scheme.
Say that a string $B$ is good if $B$ isn't of the form $1^k M$ for some $M$, and $K(B) \ge |B|-k$.

Consider any good string $B$.  Since $B$ isn't of the form $1^kM$, one (non-standard) encoding of a TM that outputs $B$ is $B$ itself. Further, any other encoding, say $P$ (with this encoding scheme), of a TM that outputs $B$ must be of the form $1^k M$, where $M$ is the standard encoding of a TM that outputs $B$.  Any such encoding $P$ has length at least $K(B)+k \ge |B|$.  Hence, $K'(B) = |B|$.

$B$ has an encoding (namely $B$) of size $K'(B)$ that outputs a set of size 1 containing $B$, so the MKSS $P'_B$ for $B$ has size $|P'_B| \le |B|$.

Now, fix any $n$, and consider any length-$n$ good string $B$ such that $B$ is not an MKSS.  Hence, $|P'_B| < |B|=n$ and $P'_B = 1^k M$ for some standard encoding $M$ such that, on input $n$, $M$ outputs a set $S_B$ containing $B$ such that
$$k+|M| +\log|S_B| = |P'_B| + \log |S_B| \le K'(B) = |B| = n.$$
It follows that $|M|+\log|S_B| \le n - k$.

Now, composing $M$ and the index of $B$ in $S_B$, there exists a TM with standard encoding $M'$ that, on input $n$, outputs $B$, and such that
$$|M'| = |M| + \log |S_B| + O(1) \le n-k+O(1).$$

Since $M'$ uniquely determines $B$ (among strings of length $n$), it follows that there are at most $2^{n-k+O(1)}$ good length-$n$ strings that are not MKSS's.

Now, among all $2^n$ length-$n$ strings $B$:

at most $2^{n-k}$ have $K(B) \le n-k$ (by the standard counting argument), and
at most $2^{n-k}$ have the form $1^k M$ for some $M$.

So, at least $2^n - 2^{n-k + 1}$ are good, and, among those,

at most $2^{n-k+O(1)}$ are not MKSS's (as shown above).

It follows that, for every $n$, among all $2^n$ length-$n$ strings, at least $$2^n - O(2^{n-k+O(1)}) = 2^n(1-O(1/2^k))$$ are MKSS's.  Hence, among all strings of length at most $n$, at least a fraction $1-O(1/2^k)$ are MKSS's. $~~\Box$

Just for fun, here is another non-standard encoding scheme in which almost all strings are not MKSS's.  Use the encoding scheme from Lemma 2, but augment it to make the empty string encode a TM that, on input $n$, outputs all strings of length $n$.

Lemma 3. With this modified encoding scheme, the probability that a random string of length $n$ or less is an MKSS is $O(1/2^k)$.

Proof. Following the proof above, among the strings of length $n$ or less, the fraction that are good is at least $1-O(1/2^k)$.  To finish we show that no good string is an MKSS. For any good string $B$, we have $K'(B)=|B|$.  The empty string $M$ encodes a TM that, on input $n=|B|$, outputs a set $S_B$ of size $2^n$ containing $B$.  Hence $|M| + \log |S_B| = 0 + n = |B| = K'(B)$.  Hence, the empty string is the MKSS for (any good) $B$, and $B$ is not an MKSS. $~~\Box$.


computing the minimal NFA for a DFA Many years ago I heard that computing the minimal NFA (nondeterministic finite automaton) from a DFA (deterministic) was an open question, as opposed to the vice versa direction which has been known for decades and is well researched with an efficient $O(n \lg n)$ algorithm. Has anyone come up with an algorithm?

A quick search gave me this paper that proves that its definitely a hard problem. Apparently, no algorithm is given.

[1] Minimal NFA problems are hard / Tao Jiang and B. Ravikumar

I was reminded of this problem by the following question on the CS.SE site for which a DFA->NFA minimization algorithm would be closely related. This following question seems to me to be research level. I suggested migrating it to TCS and I wrote an answer suggesting a statistical/empirical attack.

[2] What are the conditions for a NFA for its equivalent DFA to be maximal in size?

This is really a stubborn -- and well-studied -- problem. Regarding positive results, an exact algorithm by Kameda and Weiner, a heuristic approach by Polák, and a recent approach using SAT solvers by Geldenhuys et al. come to mind. But there seem to be far more negative results ruling out other possible approaches (e.g. approximation algorithms, special cases, less powerful models of NFAs, ...) See below for some references.

T. Kameda and P. Weiner. On the state minimization of nondeterministic finite automata. IEEE Transactions on Computers, C-19(7):617–627, 1970.

A. Malcher. Minimizing finite automata is computationally hard. Theoretical Computer Science 327:375-390, 2004.

L. Polák. Minimalizations of NFA using the universal automaton. International Journal of Foundations of Computer Science, 16(5):999–1010, 2005.

G. Gramlich and G. Schnitger. Minimizing NFAs and Regular Expressions. Symposium on Theoretical Aspects of Computer Science (STACS 2005), LNCS 3404, pp. 399–411.

H. Gruber and M. Holzer. Inapproximability of nondeterministic state
and transition complexity assuming P <> NP. Developments in Language Theory (DLT 2007), LNCS 4588, pp. 205–216.

H. Gruber and M. Holzer. Computational complexity of NFA minimization for finite and unary languages. Language and Automata Theory and Applications (LATA 2007), pp. 261–272.

H. Björklund and W. Martens. The tractability frontier for NFA minimization. International Colloquium on Automata, Languages and Programming (ICALP 2008), LNCS 5126, pp. 27–38.

J. Geldenhuys, B. van der Merwe, L. van Zijl: Reducing Nondeterministic Finite Automata with SAT Solvers. Finite-State Methods and Natural Language Processing (FSMNLP 2009), LNCS 6062, 81–92.

EDIT (June 8, 2015)

Update: The following paper presents a heuristic algorithm for reducing the size of nondeterministic Büchi automata, along with experiments on random automata. As they state in the conclusion, their method applies to NFAs as well: "While we presented our methods in the context of Büchi automata, most of them trivially carry over to the simpler case of automata over finite words."

Richard Mayr, Lorenzo Clemente. Advanced Automata Minimization. POPL 2013. Extended Technical Report EDI-INF-RR-1414.

Their command-line tool Reduce v1.2 can be invoked with the option "-finite" for reducing a given NFA. The implementation is open source and released under the GNU General Public License.


Inequality for p-norm of probability distributions I want to show the following inequality, which seems like it should have an elementary proof (or even a well-known name).

Suppose $p, q$ are discrete probability distributions. And suppose that $p_i \leq x q_i$ for some $x > 1$. Then I want to show that for $r > 1$ we have the inequality:
$$
\sum p_i^r \leq x^{r-1} \sum q_i^r
$$

If we take away the requirement that $p$ is a probability distribution, then of course we have instead $\sum p_i^r \leq x^r \sum q_i^r$.

EDIT: This is not true. The best inequality one can show is the obvious one $\sum p_i^r \leq x^r \sum q_i^r$.

(Comment --> answer)

The inequality unfortunately fails to hold, a counterexample is
 $$p = (1,0,\dots,0)$$
and
 $$q = \left(\frac{1}{2},\frac{1}{2n},\dots,\frac{1}{2n}\right),$$
where the support size is $n+1$ and $x=2$.

Then $\sum p_i^r = 1$, but $x^{r-1}\sum q_i^r \approx \frac{1}{2}$:
\begin{align}
 \sum q_i^r &= \frac{1}{2^r} + n\left(\frac{1}{2n}\right)^r  \\
  &= \frac{1}{2^r}\left(1 + \frac{1}{n^{r-1}}\right)  \\
  &\to \frac{1}{2^r}
\end{align}
as $n \to \infty$, so $x^{r-1}\sum q_i^r \to \frac{2^{r-1}}{2^r} = \frac{1}{2}$.


Is it still open to determine the complexity of computing the treewidth of planar graphs? For a constant $k \in \mathbb{N}$, one can determine in linear time, given an input graph $G$, whether its treewidth is $\leq k$. However, when both $k$ and $G$ are given as input, the problem is NP-hard. (Source).

However, when the input graph is planar, much less seems to be known about the complexity. The problem was apparently open in 2010, a claim that also appeared in this survey in 2007 and on the Wikipedia page for branch decompositions. Conversely, the problem is claimed NP-hard (without proof of reference) in an earlier version of the previously mentioned survey, but I assume this is an error.

Is it still open to determine the complexity of the problem, given $k \in \mathbb{N}$ and a planar graph $G$, of determining $G$ has treewidth $\leq k$? If it is, was this claimed in a recent paper? Are any partial results known? If it isn't, who solved it?

As far as I know the NP-completeness of computing the treewidth of a planar graph is still open. The most recent reference I know is a survey by Bodlaender from 2012 called `Fixed-Parameter Tractability of Treewidth and Pathwidth' that appeared in the festschrift for Mike Fellows' 65th birthday. The problem is listed in the conclusion of the survey.


Complexity of max problem Consider the problem

$\max_x \;||x||_2\\ x\in P\subseteq \mathbb{R}_{\geq 0}^n$

where $||\cdot||$ is Euclidean 2-norm and $P$ is a polytope in positive orthant of $\mathbb{R}^n$. Is this problem computationally hard?

It depends how the polytope is represented. In the V-polytope presentation (i.e. $P$ is given in terms of its vertices), the problem is trivial, as Tim mentioned in the comments. In the H-polytope presentation (i.e. $P$ is given as an intersection of halfspaces defined by inequalities), Brieden  proved that a constant factor approximation is impossible unless P=NP. You can check that his proof indeed uses a polytope contained in the positive orthant.

As far as approximation algorithms, I believe the best known result is a factor $O(\sqrt{n/\log n})$ approximation ($n$ is dimension). The algorithm only needs a separation oracle, and this is the best possible approximation achievable in the oracle model, even by randomized algorithms. The same factor is achievable if the $\ell_2$ norm is replaced by an $\ell_p$ norm for $1\leq p \leq 2$. A better approximation may be possible for H-polytopes, but I am not aware of any such result.

EDIT: Actually I am now realizing that for the very similar problem of approximating the radius of a centrally symmetric H-polytope with $m$ facets, there is a simple SDP rounding that gives $O(\sqrt{\log m})$ approximation.

Let's say the problem is given as $\max\{\|x\|_2: -b \leq Ax \leq b\}$, where $A$ is an $m\times n$ matrix and $b \geq 0$ is an $m$-dimensional vector. The following vector program, which can be turned into an SDP in the usual way, is a relaxation:

$$
\begin{align}
&\max \sqrt{\sum_{j = 1}^n \|v_j\|_2^2} \text{ s.t.}\\
&\left\|\sum a_{ij} v_j\right\|_2 \leq b_i \ \ \ \ \ \forall 1 \leq i \leq m
\end{align}
$$
where $v_1, \ldots, v_n$ range over $n$-dimensional vectors. A Gaussian projection now gives an approximation. Let $g$ be a standard $n$-dimensional Gaussian, and define a random $x$ by $x_i = \frac{1}{C\sqrt{\log m}} g^Tv_i$ for a big constant $C$. Then $\mathbb{E}\|x\|_2 = \frac{SDP}{C\sqrt{\log m}}$, where $SDP$ is the value of the relaxation, and for $C$ sufficiently big,
$$
\mathbb{E} \max_{i = 1}^m \frac{|(Ax)_i|}{b_i} \leq 1.
$$
The last inequality comes from the fact that $(Ax)_i/b_i$ is a Guassian random variable with variance $(C^2\log m)^{-1}$, and the maximum of $m$ such random variables is no more than 1 in expectation by a standard concentration argument.

I very much doubt that I am the first one to think of this approximation: does anyone know of a reference?


All Pairs Shortest Path - Directed graph with integer weights I don't understand how Distance Product works (or Min Plus Product). If we replace each argument in $A$ from $a_{i,j}$ to $x^{a_{i,j}}$ and each argument in $B$ from $b_{i,j}$ to $x^{b_{i,j}}$ and each and make the polinomial product on each row and column we'll get a matrix $C$ such $c_{i,j}= \sum_{\substack{1<k<n \\}} cx^{a_{i,k}+b_{k,j}})$.

We want the path, not only the distance, and for the path we must know $k$ which gives us the minimum $x^{a_{i,k}+b_{k,j}}$. So how do we extract k from it?
Why does the time of Distance Product is $O(n^{\omega}M)$? (where $\omega$ is the present lowest exponent for matrix multiplication and $M$ is the maximum value in the matrices).

I'll first answer question (2). Let's solve the $(\max,+)$ product problem. The $(\min,+)$ product can be solved analogously by negating entries and adding $M$ to each entry to make all entries positive.

Take $A$ and $B$ whose product $C$ we want to compute, and create matrices $A'$ and $B'$ where $A'[i,j]=(n+1)^{A[i,j]}$ and $B'[i,j]=(n+1)^{B[i,j]}$ for all $i,j$.
Compute the product $C'$ of $A'$ with $B'$. This takes $O(Mn^\omega \log n)$ time since the bit representation of the integers in $A'$ and $B'$ has length $O(M\log n)$.
Consider now $C'[i,j]=\sum_k A'[i,k]B'[k,j]=\sum_k (n+1)^{A[i,k]+B[k,j]}$.
If $\max_k A[i,k]+B[k,j] = z$, then $C'[i,j]\geq (n+1)^z$, and if $\max_k A[i,k]+B[k,j]<z$, then $C'[i,j]\leq n\cdot (n+1)^{z-1} < (n+1)^z$. Thus, $C[i,j]$ is the largest power of $n+1$ that's at most $C'[i,j]$ and hence $C$ is easy to obtain from $C'$.

With respect to question (1), in order to find for each $i,j$, the index $k$ that achieves the minimum (called the witness), one uses a method by Zwick (from Uri Zwick. 2002. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM 49, 3 (May 2002), 289-317.) This method is based on ideas from an earlier paper by Alon, Galil, Margalit and Naor on finding witnesses for Boolean matrix multiplication.

The basic idea is to first figure out a way to extract the witness $k$ for entry $i,j$ provided $k$ is a unique witness for the minimum. Then one uses a carefully chosen, polylogarithmic number of random samples of columns of $A$/rows of $B$ which ensures that $k$ is the unique witness for $i,j$ in one of the samples with high probability. To extract a unique witness, one only needs to do $\log n$ distance products. For each $l=1,\ldots,\log n$, let $K_l$ be the integers whose $l$th bit is $1$, and compute the distance product of $A$ and $B$, restricted to the columns of $A$/rows of $B$ with indices in $K_l$. Then if $k$ is unique such that $C[i,j]=A[i,k]+B[k,j]$, one can compute the the binary representation of $k$ by setting to $1$ only those bits $l$ for which the distance product for $K_l$ had $C[i,j]$ as its $i,j$ entry.


Set cover by alternative of sets I had this question when looking at problem C on this morning's code jam:

Suppose you have a set $S$ and $N$ pairs of subsets $\{S_i^0, S_i^1\}$, $S_i^j\subset S.$

Does there exist a cover of $S$ consisting of (at most) one subset from each pair? Ie, does there exist an $\alpha \in \{0,1\}^N$ with $S=\cup_i S_i^{\alpha_i}$?

Is there a polynomial time algorithm for answering this question? It has a network flow "smell" to it and seems like it's probably a standard problem, but I couldn't find it looking at lists of problems related to set cover.

That is tightly equivalent to CNF-SAT.

CNF-SAT  $\to$  your problem    :

The subscripts are the variables and the superscripts indicate whether the

literal is positive or negative.    If you want to preserve the number of solutions, then insert

clauses of the form  x or not x  for each variable x.    Other than that, the elements are

the clauses, and each set is the set of clauses in which the corresponding literal occurs.

your problem  $\to$  CNF-SAT    :

There is one variable per pair-of-sets, and one clause per element.

For each element x and variable i,        not i  is in x's clause if and only if x is in $S^i_0$

and    (the positive literal) i  is in x's clause if and only if x is in $S^i_1$    .


NP-hard problems on trees Several optimization problems that are known to be NP-hard on general graphs are trivially solvable in polynomial time (some even in linear time) when the input graph is a tree. Examples include minimum vertex cover, maximum independent set, subgraph isomorphism. Name some natural optimization problems that remain NP-hard on trees.

It is NP-complete to determine whether a tree can be embedded into the two-dimensional integer grid, with the tree vertices placed on distinct grid points and the tree edges placed on grid edges.

See e.g. Gregori, IPL 1989.


Algorithm for optimizing decision trees Background
A binary decision tree $T$ is a rooted tree where each internal node (and root) is labeled by an index $j \in \{1,..., n\}$ such that no path from root to leaf repeats an index, the leafs are labeled by outputs in $\{A,B\}$, and each edge is labeled by $0$ for the left child and $1$ for the right child. To apply a tree to an input $x$:

Start at the root
if you are at leaf, you output the leaf label $A$ or $B$ and terminate
Read the label $j$ of your current node, if $x_j = 0$ then move to the left child and if $x_j = 1$ then move to the right child.
jump to step (2)

The tree is used as a way to evaluate a functions, in particular we say a tree $T$ represents a total function $f$ if for each $x \in \{0,1\}^n$ we have $T(x) = f(x)$. The query complexity of a tree is its depth, and the query complexity of a function is the depth of the smallest tree that represents it.

Problem
Given a binary decision tree T output a binary decision tree T' of minimal depth such that T and T' represent the same function.
Question
What is the best known algorithm for this? Are any lower bounds known? What if we know that the $\text{depth}(T') = O(\log \text{depth}(T))$? What about if we only require $T'$ to be of approximately minimal depth?

Naive approach
The naive approach is given $d = \text{depth}(T)$ to recursively enumerate all binary decision trees of depth $d - 1$ while testing if they evaluate to the same thing as $T$. This seems to require $O(\frac{d 2^n n!}{(n - d)!})$ steps (assuming that it takes $d$ steps to check what $T(x)$ evaluates to for an arbitrary $x$). Is there a better approach?
Motivation
This question is motivated by a previous question on the trade off between query complexity and time complexity. In particular, the goal is to bound the time separation for total functions. We can make a tree $T$ from a time optimal algorithm with runtime $t$, and then we would like to convert it to a tree $T'$ for a query optimal algorithm. Unfortunately, if $t \in O(n!/(n - d)!)$ (and often $d \in \Theta(n)$) the bottleneck is the conversion. It would be nice if we could replace $n!/(n - d)!$ by something like $2^d$.

I have 3 answers, all giving somewhat different hardness results.

Let $f: \{0,1\}^n \rightarrow \{0,1\}$ be some function.

Answer 1

Given a decision tree $T$ computing $f$ and a number, it is NP-hard to tell if there exists a decision tree $T'$ computing $f$ of size at most that number. (Zantema and Bodlaender '00)

Answer 2

Given a decision tree $T$ computing $f$, it is NP hard to approximate the smallest decision tree computing $f$ to any constant factor. (Sieling '08)

Answer 3

Let $s$ be the size of the smallest decision tree computing $f$.
Given a decision tree $T$ computing $f$, assuming $NP \subsetneq DTIME(2^{n^\epsilon})$ for some $\epsilon < 1$, one cannot find an equivalent decision tree $T'$ of size $s^k$ for any $k \ge 0$.

I think that this stronger answer (relying on a weaker assumption) can be made from known results in the learning theory of Occam algorithms for decision trees, via the following argument:

Is it possible to find a decision tree on $n$ variables in time
$n^{\log s}$, where $s$ is the smallest decision tree consistent with examples coming from a distribution (PAC model). (Blum '92)
Assuming $NP \subsetneq DTIME(2^{n^\epsilon})$ for some $\epsilon < 1$, we cannot PAC learn size $s$ decision trees by size $s^k$ decision trees for any $k \ge 0$. (Alekhnovich et al. '07)

These two results seem to imply a hardness result for your problem. On the one hand (1), we can find a large decision tree; on the other hand (2), we shouldn't be able to minimize it to get an equivalent "small" one, of size $s^k$, even when one exists of size $s$.


Is there a natural problem in quasi-polynomial time, but not in polynomial time? László Babai recently proved that
the Graph Isomorphism problem is in quasipolynomial time.
See also his
talk at University of Chicago,
note from the talks by Jeremy Kun
GLL post 1,
GLL post 2,
GLL post 3.

According to Ladner’s theorem,
if $P \neq NP$, then $NPI$ is not empty,
i.e. $NP$ contains problems that are neither in $P$ nor $NP$-complete.
However, the language constructed by Ladner is artificial and
not a natural problem.
No natural problem is known to be in $NPI$
even conditionally under $P \neq NP$.
But some problems are believed to be good candidates for $NPI$,
such as Factoring integers and GI.

We may think that with Babai's result,
there might be a polynomial time algorithm for GI.
Many experts believe that $NP \not\subseteq QP = DTIME(n^{poly\log n})$.

There are some problems for which we know quasi-polynomial time algorithms,
but no polynomial time algorithm is known.
Such problems arise in approximation algorithms;
a famous example is the directed Steiner tree problem,
for which there is a quasi-polynomial time approximation algorithm
achieving an approximation ratio of $O(\log^3 n)$
($n$ being the number of vertices).
However, showing the existence of such a polynomial time algorithm
is an open problem.

My question:

  Do we know any natural problems which are in $QP$ but not in $P$?

There has, in fact, been quite a lot of recent works on proving quasi-polynomial running time lower bound for computational problems, mostly based on the exponential time hypothesis. Here are some results for problems that I consider quite natural (all results below are conditional on ETH):

Aaronson, Impagliazzo and Moshkovitz [1] show a quasi-polynomial time lower bound for dense constraint satisfaction problems (CSPs). Note that the way CSP is defined in this paper allows the domain to be polynomially large, as the case where the domain is small is known to have a PTAS.
Braverman, Ko and Weinstein [2] prove a quasi-polynomial time lower bound for finding $\epsilon$-best $\epsilon$-approximate Nash equilibrium, which matches Lipton et al.'s algorithm [3].
Braverman, Ko, Rubinstein and Weinstein [4] show a quasi-polynomial time lower bound for approximating densest $k$-subgraph with perfect completeness (i.e. given a graph that contains a $k$-clique, finds a subgraph of size $k$ that is $(1 - \epsilon)$-dense for some small constant $\epsilon$). Again, there is a quasi-polynomial time algorithm for the problem (Feige and Seltser [5]).

References

AM with multiple Merlins. In Computational Complexity (CCC), 2014 IEEE 29th Conference on, pages 44–55, June 2014.
Mark Braverman, Young Kun Ko, and Omri Weinstein. Approximating the best nash equilibrium in $n^{o(log n)}$-time breaks the exponential time hypothesis. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’15, pages 970–982. SIAM, 2015.
Richard J. Lipton, Evangelos Markakis, and Aranyak Mehta. Playing large games using simple strategies. In Proceedings of the 4th ACM Conference on Electronic Commerce, EC ’03, pages 36–41, New York, NY, USA, 2003. ACM.
Mark Braverman, Young Kun-Ko, Aviad Rubinstein, and Omri Weinstein. ETH hardness for Densest-$k$-Subgraph with perfect completeness. Electronic Colloquium on Computational
Complexity (ECCC), 22:74, 2015.
U. Feige and M. Seltser. On the densest $k$-subgraph problems. Technical report, 1997.


Effect of serial repetition on soundness of a PCP, and what is special with 1/2? As far as I know, following operations convert a $PCP_{1,s}[O(\log n),O(1)]$ , to a  $PCP_{1,s’}[O(\log n),O(1)]$, with following $s’$ :

By constant number of applications of serial repetition: can get every constant s’>=1/2;
By constant number of applications of parallel repetition: can get every constant s’>0;
By $\theta(\log n)$ number of applications of Dinur’s gap amplification transformation: can get some constant $s’\geq1/2$; (see “Gap Amplification Fails Below 1/2”)

My questions:

Could you please correct me if I have made any mistakes?
What is special with ½ in serial repetition or Dinur’s transformation? why not another constant, like 1/3 or else?
Are such a results true for PCPs with imperfect completeness?

remark:
with $PCP_{c,s}$, I mean PCP with completeness c and soundness error s.

Sequential repetition can give you any constant soundness error larger than 0, not just soundness error $\geq 1/2$.
Dinur's approach gives you a constant soundness error which is not only at least half, but, in fact, extremely close to 1, maybe 0.99999.
The note of Andrej Bogdanov that you linked to shows that getting a soundness error smaller than half inherently won't work using Dinur's approach. The reason is specific to this approach, and is explained well in the note.

The soundness amplification results work for imperfect completeness as well. It's pretty straightforward to convince yourself of that in the case of sequential/parallel repetition. Dinur's approach can also be adapted to imperfect completeness.

Remark: Dinur's approach, just like the other two approaches, requires a number of iterations/repetitions that depends on the soundness you start with and the soundness you want to get.
In her case it's $\Theta(\log(\frac{1}{1-s}))$ iterations to get to constant soundness. Irit starts with $s\approx 1-\frac{1}{n}$, and that's why she needs $\Theta(\log n)$ iterations.


Common terminology used for lower/upper bounds Suppose you have developed an upper bound on the number of vertices of a particular graph. This bound is the best possible bound that can be found for any given instance. What do you call such a bound? If it were an optimization problem then I would call it the optimal value or the optimal bound. Do you agree?

I am familiar with the term tight lower/upper bound. According to Wikipedia,

  An upper bound is said to be a tight upper bound, a least upper bound, or a supremum if no smaller value is an upper bound. Similarly a lower bound is said to be a tight lower bound, a greatest lower bound, or an infimum if no greater value is a lower bound.

This definition does not mention whether the bound is achieved by an infinite family of instances or all instances.
I looked up several books on "combinatorics", "algorithms", "graph theory" and "optimization". I could not find a reference that formally defines what a tight bound is.

According to the book Approximation Algorithms by Vijay V. Vazirani:

  An infinite family of instances of this kind, showing that the analysis of an approximation algorithm is tight, will be referred to as a tight example.

So given a bound (e.g., upper bound), an example is tight if it represents an infinite family of instances achieving the bound. However, this bound may not be the best possible bound that can be found for the problem. What if you have the best possible bound (say optimal bound) for the problem and give a tight example corresponding to it? Although the example is still tight (by definition), it is different from other tight examples since its corresponding bound is optimal. So basically the question is, can we call the bound optimal (as I did!) or there is already a definition for such a bound? I have also heard of the phrase "theoretical lower/upper bound" but have no idea when we should use it!

How do you differentiate the above terminologies (preferably by formal definitions)? Are there any other terminologies that are not mentioned here?

The term “tight” has multiple uses, as is mentioned in a comment. However, you seem to be interested in a combinatorial context or on a combinatorial-type problem so I’m going to assume that contexts. Let’s say we are talking about a function, $f(n)$, that bounds $g(n)$. In your case, $g$ is the true number of vertices of the $n^{th}$ graph in your family and $f$ is your bound.

  $f$ is a tight bound for $g$ if there exists an $n$ such that $g(n)=f(n)$.

Notice that $f$ can be tight but still improvable. If you have that $g(n)=n-\epsilon\sin((n-1)/100)$ then $f(n)=n^2$ is a tight bound. It is an upper bound for $g$ and they agree for $n=1$. However, that doesn’t mean it cannot be improved. A better bound might be $f_k(n)=n^{1+k^{-1}}$. This family has the property that $g(n)<f_k(n)<f(n)$ for $n>1$ and $g(1)=f_k(1)+f(1)$.

I am generally not a fan of the term “optimal bound” because it’s usually inaccurate. The optimal bound for a sequence of integers is simply that sequence of integers, so if you have an “optimal bound” you almost always have an expression for the underlying process.

There are contexts in which the previous paragraphs is wrong, however, and you seem to think that you’ve proven that you bound is the best possible. If that’s the case, there aren’t any caveats to that sentence, and what you’ve proven is indeed a bound rather than an expression for the number of vertices in the graph, then “optimal bound” or “best possible bound” is the terminology that I would recommend using.


Why is Feige-Fiat-Shamir not Zero Knowledge without sign bits? In chapter 10 of HAC (10.4.2), we see the well-known Feige-Fiat-Shamir identification protocol based on a zero-knowledge proof using the (presumed) difficulty of extracting square roots modulo a composite that is hard to factor.  I'll give the scheme in my own words (and hopefully get it right).

Let's start with a simpler scheme: let $n$ be a Blum integer (so $n=pq$ and each of $p$ and $q$ is 3 mod 4) of sufficiently large size that factoring is intractible.  Since $n$ is a Blum integer, half of the elements of $Z_n^*$ have Jacobi symbol +1 and the other half have -1.  For the +1 elements, half of those have square roots, and each element having a square root has four of them, exactly one being itself a square.

Now Peggy selects a random element $s$ from $Z_n^*$ and sets $v=s^2$.  She then sends $v$ to Victor.  Next is the protocol: Victor wishes to verify that Peggy knows a square root of $v$ and Peggy wishes to prove it to him without divulging anything about $s$ beyond the fact she knows such an $s$.

Peggy chooses a random $r$ in $Z_n^*$ and sends $r^2$ to Victor.
Victor equiprobably sends $b=0$ or $b=1$ back to Peggy.
Peggy sends $rs^b$ to Victor.

Victor can verify that Peggy has sent the correct answer by squaring what he receives and comparing to the correct result.  Of course, we repeat this interaction to reduce the chance that Peggy is just a lucky guesser. This protocol is claimed to be ZK; a proof can be found in various places (eg, Boaz Barak's lecture notes).

When we extend this protocol to make it more efficient it is called Feige-Fiat-Shamir; it's very similar to the above.  We start Peggy with $k$ random values $s_1\cdots s_k$ and random signs $t_1 = \pm 1, \cdots t_k  = \pm 1$ she publishes their squares as $v_1=t_1s_1^2, \cdots, v_k = t_ks_k^2$. In other words, we randomly negate some of the $v_i$.  Now

Peggy chooses a random $r$ in $Z_n^*$ and sends $r^2$ to Victor.
Victor equiprobably sends $k$ values $b_i$ from $\{0,1\}$ back to Peggy.
Peggy sends $r\Pi_{i=1}^ks_i^{b_i}$ to Victor.

My Question: Why are the $t_i$ sign bits necessary?  In parentheses, HAC notes that they are there as a technical requirement required to prove that no secret information is leaked.  The wikipedia page for Feige-Fiat-Shamir (which gets the protocol wrong) implies that without this a bit is leaked.

I cannot find an attack that extracts anything from Peggy if she omits the signs.

The Feige-Fiat-Shamir (FFS) identification protocol is a proof of knowledge (PoK), in which the prover (Peggy) proves her knowledge the square roots of the given input to the verifier (Victor).

FFS want to discriminate PoK from proofs of language membership, in which Peggy proves that the input has some property (more formally, the input belongs to a certain language).

If we don't use the negative signs, it's possible that the inputs do not possess any square root. For instance, the number 20 does not have any square roots mod 21. Since distinguishing squares and non-squares is a famous hard problem, FFS avoid it by allowing the input to be the plus or minus of some number squared. In their own words (changed a bit):

  By allowing $v_i$ to  be either plus or minus a square modulo a Blum integer, we make sure that $v_i$ can range over all the numbers with Jacobi symbol $+1 \bmod n$ and  thus the $s_i$ exist (from V's point of view) regardless of $v_i$ character, as required in unrestricted input zero-knowledge proofs of knowledge.

By unrestricted input zero-knowledge proofs of knowledge, they mean a ZK PoK whose corresponding proof of language membership is trivial; i.e. V can by himself decide that the input is the plus or minus of some square (by just checking the Jacobi symbol).


Is there a counterexample to this work? Is there a counterexample to this claim https://arxiv.org/abs/1610.00353? They claim a $O(n^6)$ LP model with simulations to support. I think asking validity is not a reasonable problem. However asking for counter examples here might be a reasonable extended formulations problem.

Predecessor versions of this paper have been around for more than 15 years. I remember that there were counter-examples to the first versions, then first revisions, counter-examples to the first revisions, second revisions, new counter-examples, further revisions, further counter-examples, and so on.

It would be much better, if the authors were able to provide a mathematical proof that the given LP formulation indeed yields a full description of the TSP.
From the scientific point of view, it is certainly not enough to just state an LP formulation and to claim that it is correct, as long as nobody is able to explicitly construct a counter-example.

All in all, I would say that it is safe to ignore this paper as long as the authors do not provide supporting arguments for their claims.


Algorithm for Longest Path in Undirected Weighted Graph EDIT Dec 14th 2010
The algorithm is not correct: it's not the case that it always returns the optimal $W$.

While reasoning on this and other similar questions, I've sketched an algorithm that, given an undirect weighted graph $G=(V,E)$ of $n$ vertices and a vertex $v_i \in V$, returns an array $W$ of $n$ weights, where each $W_j$ (with $j \in [1,n]$) is the weight of the path of maximum weight from $v_i$ to $v_j$. Something must be wrong with the algorithm, but so far I couldn't figure out what. The algorithm seems correct at first sight, maybe its flaw is that the labeled tree $T$ it builds (see below) grows exponentially in size (I didn't yet implement it to see what happens).

Other than its input, the algorithm uses two further objects:

A labeled tree $T$, which is initially composed by only one node whose label is $i$ (such node will be $T$'s root)
A relation $R \subseteq D^2$. $D$ is the domain of "paths without repetition", and $R(x,y)$ means "path $x$ removes path $y$". $R$ is initially the empty set.
A relation $Q \subseteq D^2$. $Q$ is built from $R$. $Q$ is initially the empty set.

The algorithm operates as follows:

For each leaf $v_k$ of $T$, add to it one new child node labeled $c$ for each $v_c \in V$ such that $\{ v_k, v_c \} \in E$ and there isn't any node labeled $c$ in the path in $T$ from $v_k$ to the root.
If $T$ changed during Step 1, go to Step 3. Else, go to Step 7.
Given a generic node $v_t$ of $T$, let $p_t$ be the path in $T$ from the root to $v_t$, let $w_t$ be the weight of $p_t$, and let $l_t$ be the label of $v_t$. Let $V(l)$ be the set of nodes of $T$ whose label is $l$. Now for each different label $l_k$ appearing in a leaf of $T$, let $V_2(l_k)$ be the set of all those subsets of $V(l_k)$ having cardinality $2$; for each $\{v_{k_1}, v_{k_2}\} \in V_2(l_k)$, if $w_{k_1} \geq w_{k_2}$ then add $(p_{k_1}, p_{k_2})$ to $R$, else add $(p_{k_2}, p_{k_1})$ to $R$.
Compute the relation $Q$ as follows: $Q$ contains all the couples of $R$, plus those obtained according to the following rule: if $(x, y) \in Q$ and $(z, w) \in Q$ and $y$ is a prefix of $z$, then $(x, w) \in Q$.
For each $y$ such that $\exists x (x, y) \in Q$, if $\not \exists z (z, y) \in Q$ such that $y$ is a prefix of $z$, then remove from $T$ the subtree whose root $r$ has a path from $T$'s root to $r$ equal to $y$.
Set both $R$ and $Q$ equal to the empty set. If $T$ changed during Step 5, then go to Step 3. Else, go to Step 1.
Set $W_j = 0, \forall j \in [1,n]$. Visit the tree $T$: for each visited $v_t$, if $w_t > W_{l_t}$, set $W_{l_t} = w_t$. Return $W$.

  Question(s)

  Is the algorithm correct?
  Where is it flawed?
  Is there an instance such that $T$ has exponentially many leaves?

Apologies in advance if this algorithm turns out to be completely uninteresting and naive.

Two questions where I think you have remained unclear:

Are there any assumptions on the weight function?
What exactly holds if $(x, y) \in R$?

Ad 4: You break your desired invariant for $R$ here since the last node in $x$ does not necessarily occur in $w$ at all. Example: $x = abc, y=adc, z=adce, w=ae$

I believe a worst-case instance might be the complete graph with $w(i,k) = 1$ for $i$ the starting node and all $k\neq i$, and $w(j, k) = 0$ for all $j,k \neq i$. Paths with more nodes will never remove those from earlier iterations so the tree is never shrunk at all, growing up to having $n!$ nodes.


Proof-techniques for the hardness of optimization problems (esp. Polynomial time) I've given an optimization problem for which I want to show that it is solvable in polynomial time.

Now, I have two questions:

Can this be done by formulating a mixed-integer linear program such that the coefficient matrix A has only values of -1, 0 or +1 and show that A is total unimodular? Because solving the relaxation of this problem with appropriate LP-techniques delivers an optimal solution in polynomial time.
What alternatives do I have to show that an optimization problem is solvable in polynomial time? I'm searching for an elegant proof for writing down this result.

EDIT: I reformulated my questions and hope my request becomes clearer.

Regarding question 2, there are at least two other classes of matrices that give integral polehydra: the balanced and totally balanced matrices. When available, these properties are simpler to establish than total unimodularity.

I'm not sure about question 1: your first paragraph seems to contain the answer, but after closer inspection I realize that total unimodularity yields integral polyhedras for arbitrary budget vectors. As Linear Programming is not known to be strongly polynomial, I suspect that you won't get polynomial time with an arbitrary integral budget that is binary-encoded (but it works say for a 0,1-budget vector).

You can find some relevant lecture notes online; some textbooks might be useful too (such as "Combinatorial Optimization" or "Hypergraph Theory: An Introduction").


How to judge the definition of computational complexity of reals is natural or suitable? As we know, definition of computational complexity of algorithm is almost without controversy, but the definition of computational complexity of reals  or the computation models over reals is not in such a case. We know Blum and Smales' model and model in the book Computable Analysis. And seemingly, model in Computable Analysis is consistent with the classic model, but the definition of computational complexity of reals can not transplanted into classic model.

How to judge the definition of computational complexity of reals is natural or suitable?

And how to transplant the definition of computational complexity of reals  into classic model?

I am not exactly sure what the question is here, but I can try to say a bit to clean up possible misunderstandings.

First of all, if we are talking about complexity of a map $f : \mathbb{R} \to \mathbb{R}$, it makes no sense to ask "What is a good representation for $\sqrt{2}$?" Instead, you have to ask "What is a good representation for all inputs of $f$?". Compare the situation with an easier one in discrete math: when you discuss an algorithm which takes a graph as an input, you do not ask "Should we represent the Petersen graph as as an adjancency list or as a binary matrix?" but instead you automatically think of a uniform representation which will work for all graphs.

Another word of warning. By changing the representation of the input data we can always make any problem (including a non-computable one) trivially computable: in order to make $f : A \to B$ computable, represent the elements of $A$ as pairs $(a, f(a))$. Then you can "compute" $f$ by the second projection. This shows that we need clear criteria of what it means to represent data.

I have written on several occasions about what it takes to represent the elements of $\mathbb{R}$. The answer depends on what structure of $\mathbb{R}$ you are trying to capture. If you are trying to capture no structure, then you can represent all reals with the empty list, for example. A reasonable list of conditions for a representation of $\mathbb{R}$ is that it needs to be such that:

The arithmetical operations $+$, $\times$, $-$, $/$ are computable, as well as the absolute value $|{-}|$.
There is a program which takes (the representation of) a real $x$ and $k \in \mathbb{N}$ and outputs integers $p, q$ such that $|x - p/q| \leq 2^{-k}$, i.e., it is possible to compute arbitrarily good rational approximations.
There is a program which takes (representations of) reals $x$ and $y$ and terminates if, and only if, $x < y$, i.e, the strict order is semidecidable.
Given a sequence (of representations of) $(x_n)_n$ such that $|x_{n+1} - x_n| \leq 2^{-n}$ a representation for the limit $\lim_n x_n$ can be computed.

There are old theorems (see introduction to this paper for references) which explain why these conditions are the correct one. These theorems also show that any two such representations of reals are computably isomorphic, that is, we can translate between them with programs. This sets up some criteria for correctness that throw out faulty ideas.

For example, I hear people say things like "rational numbers can be represented by finite information, so let's use that for rational numbers, and the irrational numbers will have to be represented by infinite information". This sort of thing does not work because it breaks the fourth condition above (consider a limit of irrational numbers -- how will you tell that it is converging to a rational?).

Another example which the above conditions eliminate is the Blum-Shub-Smale model because in it you cannot compute limits of sequences. It is better to say that the BSS model works on a discrete ordered subfield of reals (generated by whatever parameters are present), not on the reals themselves.

Among the correct representations of reals some are more efficient than others, although this is a somewhat difficult topic to discuss because real numbers are infinite objects. Matthias Schröder pointed out that for a reasonable theory of complexity one has to pay attention to the topological properties of the representation.

Finally, how should we measure the complexity of a map $f : \mathbb{R} \to \mathbb{R}$, assuming we have a good representation of $\mathbb{R}$? Because $x \in \mathbb{R}$ is represented by a function, or an infinite stream of information, or some such, we should be using one of the higher-type notions of complexity. Which one probably depends on the representation you are using.

The BSS model  is a also a reasonable circuit complexity model in which we count arithmetical operations. It's just good to keep in mind that this model is not about real numbers, but about something else.


Measurability of an $\omega$-regular language It the previous question of mine I put a reference which shows that any $\omega$-regular language over the alphabet $\Sigma$ is a Borel subset of $\Sigma^\omega$. I am not sure whether the reference I am aware of is the first the showed this result, so I wonder whether there are other papers the contain it. Alternatively, I am also interested in textbooks that contain the proof of this fact.

An $\omega$-regular language is actually quite low in the Borel hierarchy (inside $\Delta_3$), a result due to

R. McNaughton, Testing and generating infinite sequences by a finite automaton, Information and Control 9 (1966), 521-530.

For a proof and more details, you can look at Chapter 3 of the following book

D. Perrin et J.-É. Pin, Infinite words, Pure and Applied Mathematics Vol 141, Elsevier, 2004, ISBN 0-12-532111-2.


If machine learning techniques keep improving, what's the role of algorithmics in the future? Let's look at the future some 30 years from now. Let's be optimistic and assume that areas related to machine learning keep developing as quickly as what we have seen in the past 10 years. That would be great, but then what would be the role of traditional algorithmics in such a future?

Here by "traditional algorithmics" I refer to the usual process that we follow in TCS: formalise a well-defined computational problem, design algorithms for solving the problem, and prove formal performance guarantees.

Now what are the application areas in which we must use traditional algorithm design and analysis also in the future, and it is highly unlikely that any advances of machine learning will make traditional algorithmics mostly irrelevant?

At first this may seem like a silly question: Of course we will need to be able to do sorting, searching, indexing, etc. also in the future! Of course we will need to be able to do Fourier transforms efficiently, multiply large matrices, find shortest paths, solve linear optimisation problems!

But then again, once you start looking deeper at the applications in which we traditionally use the algorithms that we design, it is not at all clear that the traditional algorithm design and analysis is the right answer to such problems: In applications related to search, usually we are interested in finding something that is a close match for a human being in some vague ill-defined sense (e.g. semantic similarity), not something that is optimal in some mathematical sense (e.g. minimum edit distance). In applications related to route planning, usually we are interested in finding routes that are good based on examples (e.g. other people prefer it), not routes that are optimal in some mathematical sense (e.g. shortest distance or cheapest price). And once you have some vague, ill-defined human component in the picture, it might be the case that we are better off trying to teach the computer to produce good answers based on examples, instead of trying to let a TCS researcher to come up with a formal computational problem that we can tackle by means of traditional algorithm design and analysis.

So what are the application areas (preferably real and direct industrial applications) in which it is absolutely clear that what we have been doing in algorithmics in past is also going to be the right way (and the only possible way) of making progress in the future?

Algorithms that are used as subroutines in machine learning techniques looks like an obvious future-proof candidate, but this heavily depend on the particular machine learning technique that we use, and as we have seen in the past ten years or so, this might rapidly change.

This is a question that has been haunting me recently, so I am glad you asked it.
However, I am less interested in classifying the application areas for which machine learning will dominate the computational approach than I am in the impact on advancement in the field of (traditional) algorithms.  What kind of "human-crafted algorithms" research will we still be interested in, in 30 years?  Admittedly, this is the harder question to answer in general, because it is the application that determines what quality of result is required.

I think that enumeration algorithms will number among the survivors.  There will continue to be a need to test all inputs to a chip, or conduct an exhaustive search.  The object-specific attention, the finely-tuned design required to generate each object instance exactly (or at least) once; and the running-time amplification of any wasted effort (there may be an exponential number of instances, as a function of the description of the object) -- these factors make me skeptical that a general-purpose automated learning process can match a clever, purpose-designed solution in this area.


Is iszero of the untyped lambda calculus sound and complete? I am using the following definitions in the notation of Haskell. In case it matters, I would like to use only the $\alpha,\beta,\eta$ reductions rather than the Haskell evaluation rules.

-- boolean constants
true = \x y -> x
false = \x y -> y

-- 0 and increment (successor)
zero = \f x -> x
inc n = \f x -> f (n f x)

-- IS THIS iszero SOUND AND COMPLETE?
iszero = \n -> n (\x -> false) true

It seems to me that iszero needs to check if two functions are identical. Since the equivalence of two arbitrary Turing Machines are undecidable, I am wondering if the it really works. In particular,

Soundness: are all functions for which iszero returns true really zero?
Completeness: for any arbitrary function $f$, can iszero correctly determine if $f$ is equal zero?

No, iszero does not have to test whether two functions are equal. It only has to detect a difference between them, i.e., extract enough information to tell whether the given function represents a 0 or not.

You could ask the same question about equality testing. It is possible to implement an equality test eq for numbers (exercise, but implement predecessor first). Isn't it the case that eq is comparing functions for equality? No. First of all, eq does not compare arbitrary functions but only those that happen to encode numbers. Second, even when comparing two function n and m that encode numbers, it does not answer the question "are n and m equal function?" but rather "do n and m encode the same number?" These are two different questions.


Inapproximability of set cover: can I assume m=poly(n)? I am trying to show that a certain problem is inapproximable by a reduction from set cover. My reduction transforms an instance with ground set of size $n$ and $m$ sets into an instance of my problem where a certain parameter $r$ is of size $O(n+m)$. I can then show that an instance of set cover where the cover size is s corresponds to an instance of my problem where the size of the optimal solution is $2s$ (or something like this), and vice versa. I would like to invoke Raz-Safra to conclude that my problem is inapproximable up to a factor of $c  \log{r}$, for some constant $c$. This would work fine if I could assume that $m$ is bounded by a fixed polynomial of $n$. Does anyone know if it is kosher to assume this? This is certainly true for the family of instances used in the standard NP-hardness proof for set cover, but I am not sure if this remains the case for the kind of PCP reductions employed by Raz and Safra.

Yes, the number of sets m in a set-cover instance is polynomial in the number of elements.
By the way -- the state of the art hardness results for Set-Cover are:

With Noga Alon and Muli Safra, we showed how to use the Raz-Safra/Arora-Sudan PCP to get a better constant $c$ in the hardness factor $c\log n$.
http://people.csail.mit.edu/dmoshkov/papers/k-restrictions/k-rest-full.ps

Feige showed how to get the optimal hardness factor $(1-\epsilon)\ln n$, assuming $NP\not\subseteq DTIME(n^{\log\log n})$.
http://www.cs.duke.edu/courses/spring07/cps296.2/papers/p634-feige.pdf

I recently published a note on how to adapt Feige's reduction to an NP-hardness result (i.e., a result based on $P\neq NP$), assuming a plausible conjecture about PCPs (A conjecture I call "The Projection Games Conjecture" - a specialization of the 1993 "Sliding Scale Conjecture" to projection games).
http://eccc.hpi-web.de/report/2011/112/
(I later found out that the reduction gives an optimal tradeoff between $\epsilon$ and the reduction blow-up).


Commutative matrix multiplication algorithms What is known about commutative algorithms like Winograd algorithm and its variants for Matrix Multiplication? Why is there not much study on them? Can they be asymptotically as efficient as Non-commutative algorithms?

Update

Existence of $O(n^\omega)$ non-commutative algorithms for matrix multiplication implies existence of $O(n^\omega)$ commutative algorithms. Does converse statement hold truth?

In answer to the "Update": yes, for any $c$, the existence of an $O(n^c)$ non-commutative algorithm for matrix multiplication is equivalent to the existence of an $O(n^c)$ commutative algorithm for matrix multiplication (I am assuming, here, that all algorithms are algebraic, in the sense of algebraic circuits). This is because any algebraic circuit computing a bilinear map can be converted into a bilinear circuit at the expense of at most a factor of 2 in the size.


Ed. Witten's new paper and the simulation of a quantum field theory Context: Ed. Witten recently wrote a potentially revolutionary paper where he showed that under certain conditions, a Chern-Simons path integral in three
dimensions is equivalent to an N = 4 path integral in four dimensions (this is the standard d=4, N=4 super Yang Mills theory)

Speculation: Witten had shown that the Chern-Simons topological quantum field theory can be solved in terms of Jones polynomials. A quantum computer can simulate a TQFT, and thereby approximate the Jones polynomial. (source: Wikipedia and this paper) Now I haven't completed reading Witten's paper and I wouldn't understand much of it anyways. But the idea is that if a quantum computer can simulate a path integral (or a Chern-Simons TQF) and since now Witten has shown in both of them to be dual descriptions in some sense, a quantum computer, atleast theoritically might be able to simulate a QFT. Also by the extension of that, Maldacena proposed that the specific field theory that Witten is using to be dual to type-II B string theory in AdS/CFT so then it may also be possible (only theoritically) to simulate a string theory.

Question: What are the technical constrains that a quantum or classical computer faces while simulating a QFT? Also my speculations only partially complete, could experts suggest a better description? Thanks!

PS. Also thanks to Mitchell Porter who brought up that paper before.

To complement what Joe wrote, and maybe explain this question a bit more (without answering it!):

The computational complexity of simulating "realistic" quantum field theories has been considered an open problem for a long time.  One of the main problems, as I understand it, is that (3+1)-dimensional QFTs aren't sufficiently well-defined mathematically for it to be clear what model of computation should correspond to them.

But the situation is different for the (2+1)-dimensional QFTs called topological quantum field theories (TQFTs).  For those, there is a rigorous mathematical description based on the Jones polynomial, due to Witten from the 1980s.  It's that description that led to the deep and celebrated result of Freedman, Kitaev, Larsen, and Wang, which showed that simulating TQFTs is indeed BQP-complete, as one would hope and expect (see Aharonov, Jones, and Landau for a more computer-scientist-friendly version).  This remains essentially the only rigorous result we have about the computational complexity of quantum field theory.

Now, the questioner is asking whether some new work by Witten could give a handle on the computational complexity of (3+1)-dimensional QFTs.  I don't know the answer to that, but it seems obvious that whatever it is, it would involve a significant research effort, and probably not fit within the margins of CS Theory StackExchange. :-)

Addendum (Oct. 12, 2013): I just saw this answer again, and I thought I should add a note that, shortly after I posted it, Jordan, Lee, and Preskill released an important paper showing how to simulate "φ4 theory" (a simple interacting quantum field theory) in quantum polynomial time, in any number of spacetime dimensions.  This doesn't directly address the OP's question, but it does render obsolete my comment about Freedman-Kitaev-Larsen-Wang remaining "essentially the only rigorous result we have about the computational complexity of quantum field theory."


Can a det. $k$-counter machine ($k \geq 2$) be simulated by a det. $k'$-counter machine using non-$\epsilon$-moves followed by $\epsilon$-moves? I have a question concerning deterministic $k$-counter machines, for $k \geq 2$. Recall that in this context, the determinism is expressed by the fact that the machine can never face a choice between either reading a (proper) symbol of its input alphabet, or reading $\varepsilon$ (i.e., the empty symbol). In other words, let's call a transition involving a non-empty input symbol a "regular transition", and a transition involving $\varepsilon$ an "$\varepsilon$-transition" (like as usual). The determinism condition simply states that the machine never has to choose between a regular or an $\varepsilon$-transition (cf. Book by Hopcroft, Motwani and Ullman 2001, p.349).

In this context, I would like to know if every $k$-counter machine $\mathcal{C}$, for $k \geq 2$, can be simulated by a $k'$-counter machine $\mathcal{C}'$ which, on every input, always uses regular transitions followed by $\epsilon$-transitions?

For the case of stacks machines with a stack alphabet larger than or equal to the input alphabet, I believe that the answer is yes. The idea would be to consider a machine $\mathcal{C}'$ which always begins by copying its input on a designated stack – using only regular transitions – and then works exclusively by considering this stack as a kind of input tape – using only $\epsilon$-transitions.

What about the case of $k$-counter machines ($k \geq 2$)?

No, that is not possible. There are languages accepted with $\varepsilon$-transitions that cannot be accepted if $\varepsilon$-transitions can only occur at the end (even if you
allow nondeterminism in exchange for restricted $\varepsilon$ usage).

Take, for example, the language $L=\{w\#w \mid w\in\{a,b\}^*\}$.
As a recursively enumerable language, it can be accepted by a
determinisic 2-counter machine. A simple counting argument shows
that this requires interspersed $\varepsilon$-transitions:

If $\varepsilon$-transitions occur only at the end, then
after reading a word $w\#$, the machine can only produce counter
values whose size is linear in $|w|$. In particular, there is
a polynomial $p$ so that after reading a word $w\#$, the machine
can be in at most $p(|w|)$ configurations. Thus, since there
are exponentially many words of a given length, the machine can
be tricked into accepting a word $w\#w'$ with $w'\ne w$.