Bounds on this Strategy for Separating Words Question
Given binary string $z \in \{0,1\}^n$, let $f(z)$ be the smallest integer $k$ such that there exists a DFA with $k$ states, such that reading $z$ from a specific starting state, we end at a state $t$ where either reading a $0$ or a $1$ at $t$ takes us to a new state. (i.e. a state which has not been reached in the path we took when reading $z$)
Then, defining $F(n) = \max\{f(z):z \in \{0,1\}^n\}$, I was wondering if any bounds are known for $F$. Clearly, we have $F(n) \le n+1$.
Motivation
Generally, the word separator problem about given distinct binary strings, $x,y \in \{0,1\}^n, x \neq y$, to find the smallest DFA such that accepts $x$ but not $y$.
I was wondering if there have been results on this particular method:
Since $x\neq y$, let $z$ be the longest common prefix of $x$ and $y$. (example: if $x = 1101101,y=1100110$, then $z = 110$ because $x,y$ differ on their fourth letter)
WLOG, lets assume $x= z|0|x', y=z|1|y'$, where $|$ denotes concatenation and $x',y'$ are arbitrary. If there exists a DFA of length $k$ such reading $z|0$ or $z|1$ ends at a state $s'$ not visited by reading $z$, then there is a DFA of length $k +O(\log(n))$ separating $x$ and $y$. (because $x,y$ will reach $s'$ at different times, it reduces to unary word separation, which is know to take $O(\log(n))$ states by prime number theorem)
Rough Ideas
Currently this strategy has stuck out to me: we have that $f(z) \le g(z_m)+F(n-m)$ where $z_m$ is the subword consisting of the first $m$ letters in $z$, and $g(w)$ is the smallest integer $k$ such that there is DFA on $k$ states, such that reading $w$ at a specific starting state, we end at a new state $t$. For upper bounding $g(w)$, for any integers $k,i$, and any $w' \in \{0,1\}^k$, there exists an DFA on $2k$ states such that when reading a word $w$, we reach the state $t$ iff $w'$ appears as a factor/substring whose first letter is the $qk+i$-th letter of $w$. (i.e. the first letter is the $m$-th letter of $w$ where $m$ has the same residue as $i$ modulo $k$)
Of course, if $z$ is a string of only 1's, then $g(z_m) = m$ for all $m$, thus we need to combine this with a second idea to handle the cases when $z$ is periodic or otherwise not quasi-random in some sense, to get a sublinear bound.

The second section of Robson's "Separating strings with small automata" proves $F(n) = O((n \log n)^{1/2})$. The string sequence $(10^n)^n$ gives a lower bound of $\Omega(n^{1/2})$. If the automaton has $<n$ states then both of the sequences $\delta_0^{\circ m} (\delta_{(10^n)^{n-1}1}(q_0))$ and $\delta_{10^n}^{\circ m}(q_0)$ will reach a cycle before $m=n$.


Axioms necessary for theoretical computer science This question is inspired by a similar question about applied mathematics on mathoverflow, and that nagging thought that important questions of TCS such as P vs. NP might be independent of ZFC (or other systems). As a little background, reverse mathematics is the project of finding the axioms necessary to prove certain important theorems. In other words, we start at a set of theorems we expect to be true and try to derive the minimal set of 'natural' axioms that make them so.

I was wondering if the reverse mathematics approach has been applied to any important theorems of TCS. In particular to complexity theory. With deadlock on many open questions in TCS it seems natural to ask "what axioms have we not tried using?". Alternatively, have any important questions in TCS been shown to be independent of certain simple subsystems of second-order arithmetic?

Yes, the topic has been studied in proof complexity. It is called Bounded Reverse Mathematics. You can find a table containing some reverse mathematics results on page 8 of Cook and Nguyen's book, "Logical Foundations of Proof Complexity",  2010. Some of Steve Cook's previous students have worked on similar topics, e.g. Nguyen's thesis, "Bounded Reverse Mathematics", University of Toronto, 2008.

Alexander Razborov (also other proof complexity theorists) has some results on the weak theories needed to formalize the circuit complexity techniques and prove circuit complexity lowerbounds. He obtains some unprovability results for weak theories, but the theories are considered too weak.

All of these results are provable in $RCA_0$ (Simpson's base theory for Reverse Mathematics), so AFAIK we don't have independence results from strong theories (and in fact such independence results would have strong consequences as Neel has mentioned, see Ben-David's work (and related results) on independence of $\mathbf{P} vs. \mathbf{NP}$ from $PA_1$ where $PA_1$ is an extension of $PA$).


Nontrivial algorithm for computing a sliding window median I need to calculate the running median:

Input: $n$, $k$, vector $(x_1, x_2, \dotsc, x_n)$.
Output: vector $(y_1, y_2, \dotsc, y_{n-k+1})$, where $y_i$ is the median of $(x_i, x_{i+1}, \dotsc, x_{i+k-1})$.

(No cheating with approximations; I would like to have exact solutions. Elements $x_i$ are large integers.)

There is a trivial algorithm that maintains a search tree of size $k$; the total running time is $O(n \log k)$. (Here a "search tree" refers to some efficient data structure that supports insertions, deletions, and median queries in logarithmic time.)

However, this seems a bit stupid to me. We will effectively learn all order statistics within all windows of size $k$, not just the medians. Moreover, this is not too attractive in practice, especially if $k$ is large (large search trees tend to be slow, overhead in memory consumption is non-trivial, cache-efficiency is often poor, etc.).

Can we do anything substantially better?

Are there any lower bounds (e.g., is the trivial algorithm asymptotically optimal for the comparison model)?

Edit: David Eppstein gave a nice lower bound for the comparison model! I wonder if it is nevertheless possible to do something slightly more clever than the trivial algorithm?

For example, could we do something along these lines: divide the input vector to parts of size $k$; sort each part (keeping track of the original positions of each element); and then use the piecewise sorted vector to find the running medians efficiently without any auxiliary data structures? Of course this would still be $O(n \log k)$, but in practice sorting arrays tends to be much faster than maintaining search trees.

Edit 2: Saeed wanted to see some reasons why I think sorting is faster than search tree operations. Here are very quick benchmarks, for $k = 10^7$, $n = 10^8$:

≈ 8s: sorting $n/k$ vectors with $k$ elements each
≈ 10s: sorting a vector with $n$ elements
≈ 80s: $n$ insertions & deletions in a hash table of size $k$
≈ 390s: $n$ insertions & deletions in a balanced search tree of size $k$

The hash table is there just for comparison; it is of no direct use in this application.

In summary, we have almost a factor 50 difference in the performance of sorting vs. balanced search tree operations. And things get much worse if we increase $k$.

(Technical details: Data = random 32-bit integers. Computer = a typical modern laptop. The test code was written in C++, using the standard library routines (std::sort) and data structures (std::multiset, std::unsorted_multiset). I used two different C++ compilers (GCC and Clang), and two different implementations of the standard library (libstdc++ and libc++). Traditionally, std::multiset has been implemented as a highly optimised red-black tree.)

Here's a lower bound from sorting. Given an input set $S$ of length $n$ to be sorted, create an input to your running median problem consisting of $n-1$ copies of a number smaller than the minimum of $S$, then $S$ itself, then $n-1$ copies of a number larger than the maximum of $S$, and set $k=2n-1$. The running medians of this input are the same as the sorted order of $S$.

So in a comparison model of computation, $\Omega(n\log n)$ time is required. Possibly if your inputs are integers and you use integer sorting algorithms you can do better.


Why do constructivists not seem to care too much about call/cc So a little while back I first had someone tell me that call/cc could allow proof objects for classical proofs by implementing Peirce's law. I did some thinking about the topic recently and I can't seem to find a flaw with it. However I can't really seem to see anyone else talking about it. It seems void of discussion. What gives?

It seems to me that if you have a construction like $f : \neg(\neg P)$ in some context then 1 of two things is true. Either you have access to an instance $\bot$ somehow in the current context in which case control flow would never reach here and we are safe to assume whatever OR given that $f : \neg(\neg P)$ means $f : (P \to \bot) \to \bot$ the only way $f$ can return $\bot$ is by constructing an instance of $P$ and applying it two it's argument (an instance of $P \to \bot)$. In such a case there was already SOME way of constructing an instance of $P$; it seems reasonable for call/cc to pull this construction out for me. My reasoning here seems somewhat suspect to me but my confusion still stands. If call/cc isn't just creating an instance of $P$ out of thin air (I don't see how it is) then what is the issue?

Do some well typed terms not containing call/cc not have normal forms? Is there some other property of such expressions that causes them to be suspect? Is there any noted reason why a constructivist shouldn't like call/cc?

Constructive mathematics is not just a formal system but rather an understanding of what mathematics is about. Or to put it differently, not every kind of semantics is accepted by a constructive mathematician.

To a constructive mathematician call/cc looks like cheating. Consider how we witness $p \lor \lnot p$ using call/cc:

We provide a function $f$ which allegedly proves $\lnot p$. In reality $f$ is a bag of tricks.
If anyone ever applies $f$ to a proof of $p$, then $f$ unleashes call/cc to roll back time, and with a proof of $p$ in hand, changes its mind about $p \lor \lnot p$: this time claiming that it is a proof of $p$.

The constructive understanding of disjunction is algorithmic decidability, but the above is hardly making any decisions. As a test, a constructive mathematician might ask you how call/cc helps prove that every Turing machine halts or diverges. And what is the program witnessing this fact? (It ought to be the Halting Oracle.)


A combinatorial problem I have a finite graph with vertices $V$.

The sets $A_i, i=1,\ldots,N$ are non-empty disjoint subsets of $V$.

I want to find out if there is some way of selecting $a_i, i=1,\ldots,N$ such that

$a_i \in A_i$ for all $i$.
For any $i$ and $j$ such that $i\ne j$ there is no edge connecting
$a_i$ and $a_j$ in the given graph

I know that I can set this up as a boolean satisfiability problem. But I was wondering if there is anything in the structure of this particular problem which will allow for a more efficient approach?

No, you can't do much better than encoding your problem as a satisfiability problem, as it is NP-complete. Here is an example reduction to 3SAT to your problem:

For every clause, instantiate three vertices (one for every literal), which form one of your sets A_i. Chosing a vertex means that your 3SAT-solution should satisfy the clause by satisfying the respective literal. Then, add an edge between a node $x$ and $\neg x$ between of any clause for all variables $x$ in order to enforce that solutions are consistent. A solution to your problem for this graph then almost represents a 3SAT solution. I am writing "almost" as some variables may not occur in a chosen literal. These can have any value, however.


Trade off between time and query complexity for total functions This is a continuation of an earlier question on the trade off between time and query complexity. By a trade off we consider the following two types of algorithms:

The best query algorithm: this algorithm uses the minimal number of queries and then optimizes to reduce total time, while preserving queries (this has query complexity $Q_1$ and time complexity $T_1$).
The best time algorithm: this algorithm uses the minimal amount of time and then optimized to reduce total queries, while preserving time (this has query complexity $Q_2$ and time complexity $T_2$).

We saw that for partial functions, we can have arbitrarily large seperations between $T_1$ and $T_2$ and $Q_1$ and $Q_2$. However, this approach only works for partial functions.

For total functions, we can use the approach in this question to show that $T_1 \in O(n!2^n T_2)$ and for queries we can show $Q_2 \in O(2^{Q_1})$. Thus for total functions there seems to be a bound on the total separation. Can we improve it? Or come up with total functions with provable separations?

(We have a potential candidate for a separation in this answer but no provable results)

Here is a sketch of an attempt at partial separation. I was trying to improve this over the past two weeks into a full answer, but haven't made much progress. Hopefully someone else knows how to extend it.

Let

\[f_{n,m}: \{0,1\}^n \times \{0,1\}^{{m \choose 2}} \rightarrow \{0,1\}\]

So we have a total function on tuples.

$f_{n,m}(x,y)$ returns $1$ if $x = 1^n$ and if $y$ interpreted as the edges of a graph has a clique or independent graph of size $n$. Otherwise, it returns $0$.

Thus if $R_n$ is the $n$-th diagonal Ramsey number then for $m \geq R_n$ and all $y \in \{0,1\}^{{m \choose 2}}$ we have $f(1^n,y) = 1$. Thus, if we can compute $R_n$ on an input of $1^n$ then we don't have to read the bits of $y$ if $m$ is large enough, and the query complexity of the query-optimal algorithm drops to $n$.

However, $R_n$ is harder to compute on an input of $1^n$ than it is to check if a graph given by edges $y$ has a clique of independent set of size $n$ on input $(1^n,y)$. Thus, a time-optimal algorithm can't afford to compute $R_n$. It could, instead use some approximation $\tilde{R}_n > R_n$. For $m < \tilde{R}_n$ a time-optimal algorithm will read at least some bits of $y$.

Thus, for $R_n \leq m < \tilde{R}_n$ the query-optimal algorithm will use more time to make fewer queries than the time-optimal algorithm.

This approach can be made slightly less hand-wavy (or generalized to other Ramsey-like problems) but I think even the more rigorous attempt doesn't fully answer the question.


Fixed points in dependent type theories Most dependent type theories aim for some notion of correctness in two respects:

The type system must be decidable.
The type system must be consistent. e.g. $\forall \tau. \tau$ should not be provable.

The first is a topic that has been debated a bit. You could relax this requirement to semi-decidability. The second has not been debated as a desirable property but many have mentioned that $Type : Type$ would be useful for "practical" programming languages. I've become interested in what such a "practical" programming language might look like. In this question, I'll use "practical" to mean "computationally complete and not directly intended to be used for any kind of proof". The debate over whether that is a fitting definition is another topic. For instance the calculus of constructions equipped with a fixed pointer operator of type $\Pi A : Type. (A \to A) \to A$ would qualify as such a "practical" programming language. Such a language would be inconsistent but would (I think) still be type safe and computationally complete.

Additionally, most type systems have a third property, generally called "type safety." This property ensures that well-typed programs "don't get stuck" (not sure who I got that quote from). In actual practice, there is generally a way to violate type safety but I'll include in my definiton of "practical" that the language must be type safe. For such "practical" programming languages consistency is generally moot, but type safety is still a desirable property and the main property trying to be achieved in systems like System-F for instance. In such systems, the range of allowed well-typed terms is expanded as far as possible while type safety is still met. You can generally make these systems computationally complete by adding a fixed point term to the theory.

Dependent type theory almost completely blurs the line between types and terms. The remaining distinction between the two is just what types are just terms $\tau$ such that $\tau : \mathcal{U}$ where $\mathcal{U}$ is some distinguished term in the theory (or cumulative hierarchy or such). This uniformity is a very aesthetically pleasing property.

There is an analogue of fixed points over terms for types often just known as a fixed point type or $\mu$-type. Such types generally come with a "wrap" and "unwrap" terms to manipulate terms of these fixed point types. This diverges from the term level equivalent of fixed points. This, however, seems somewhat unavoidable as if you consider adding a fixed point term in a system with $Type : Type$ it doesn't actually let you make useful types like the natural numbers (but you can use it to make type familes like $Fin$ by recursion over non-type terms). The expected result there is just your type checker infinitely looping. As an example consider the type $fix \,\, Type \,\, (\lambda A : Type. 1 + A)$ as an attempt at defining the natural numbers. Unless there is some clever trick I'm missing it doesn't seem like this terminates or produces a useful type. The thought springs to my mind that if types were evaluated lazily somehow that this would be fine but I don't have a clear picture on how that should work.

Are there any works that consider semi-decidable type systems that have $Type : Type$ and allow for fixed point types to be used? Can fixed point terms and fixed point types be unified? How would one account for least and greatest fixed points of types in such a case? In a nutshell is there any literature on type safe "practical" programming languages? Ideally I'd like to see this in the case of $Type : Type$

I think the idea of unifying type and term-level fixpoints is natural, though I have to admit I'm not sure that reducing the number of constructions of a system is not always a recipe for conceptual simplicity.

One source I have for a system that takes this approach is the $\Pi\Sigma$ system:

$\Pi\Sigma$: Dependent Types Without the Sugar, Altenkirch, Danielsson, Löh and Oury.

You might also want to look at these slides by Khulmann on equi-recursive types versus iso-recursive types: equi-recursive types embody the kind of type-level recursion you are interested in (iso-recursive types have explicit folding and unfolding). As you suspect, type-checking with equi-recursive types is tougher (but not impossible!).

As a final remark, adding equi-recursive types to an otherwise consistent system does not make it inconsistent, if positivity constraints are respected.


Fixed point theorems for constructive metric spaces? Banach's fixed point theorem says that if we have a nonempty complete metric space $A$, then any uniformly contractive function $f : A \to A$ it has a unique fixed point $\mu(f)$. However, the proof of this theorem requires the axiom of choice -- we need to choose an arbitrary element $a \in A$ to start iterating $f$ from, to get the Cauchy sequence $a, f(a), f^2(a), f^3(a), \ldots$.

How are fixed point theorems stated in constructive analysis?
Also, are there any concise references to constructive metric spaces?

The reason I ask is that I want to construct a model of System F in which the types additionally carry metric structure (among other things). It's rather useful that in constructive set theory, we can cook up a family of sets $U$, such that $U$ is closed under products, exponentials, and $U$-indexed families, which makes it easy to give a model of System F.

It would be very nice if I could cook up a similar family of constructive ultrametric spaces. But since adding choice to constructive set theory makes it classical, obviously I need to be more careful about fixed point theorems, and probably other stuff too.

The axiom of choice is used when there is a collection of "things" and you choose one element for each "thing". If there is just one thing in the collection, that's not the axiom of choice. In our case we only have one metric space and we are "choosing" a point in it. So that's not the axiom of choice but elimination of existential quantifiers, i.e., we have a hypothesis $\exists x \in A . \phi(x)$ and we say "let $x \in A$ be such that $\phi(x)$". Unfortunately, people often say "choose $x \in A$ such that $\phi(x)$", which then looks like application of the axiom of choice.

For reference, here is a constructive proof of Banach's fixed point theorem.

Theorem: A contraction on an inhabited complete metric space has a unique fixed point.

Proof. Suppose $(M,d)$ is an inhabited complete metric space and $f : M \to M$ is a contraction. Because $f$ is a contraction there exists $\alpha$ such that $0 < \alpha < 1$ and $d(f(x), f(y)) \leq \alpha \cdot d(x,y)$ for all $x, y \in M$.

Suppose $u$ and $v$ are fixed point of $f$. Then we have $$d(u,v) = d(f(u), f(v)) \leq \alpha d(u,v)$$ from which it follows that $0 \leq d(u,v) \leq (\alpha - 1) d(u,v) \leq 0$, hence $d(u,v) = 0$ and $u = v$. This proves that $f$ has at most one fixed point.

It remains to prove the existence of a fixed point. Because $M$ is inhabited there exists $x_0 \in M$. Define the sequence $(x_i)$ recursively by $$x_{i+1} = f(x_i).$$ We can prove by induction that $d(x_i, x_{i+1}) \leq \alpha^i \cdot d(x_0, x_1)$. From this it follows that $(x_i)$ is a Cauchy sequence. Because $M$ is complete, the sequence has a limit $y = \lim_i x_i$. Since $f$ is a contraction, it is uniformly continuous and so it commutes with limits of sequences: $$f(y) = f(\lim_i x_i) = \lim_i f(x_i) = \lim_i x_{i+1} = \lim_i x_i = y.$$
Thus $y$ is a fixed point of $f$. QED

Remarks:

I was careful not to say "choose $\alpha$" and "choose $x_0$". It is common to say such things, and they just add to the confusion that prevents ordinary mathematicians from being able to tell what is and isn't the axiom of choice.
In the uniqeness part of the proof people often assume unnecessarily that there are two different fixed points and derive a contradiction. This way they have only managed to prove that if $u$ and $v$ are fixed points of $f$ then $\lnot\lnot (u = v)$. So now they need excluded middle to get to $u = v$. Even for classical mathematics this is suboptimal and just shows that the author of the proof does not exercise good logical hygiene.
In the existence part of the proof, the sequence $(x_i)$ depends on the existential witness $x_0$ we get from eliminating the assumption $\exists x \in M . \top$. There is nothing wrong with that. We do that sort of thing all the time. We did not choose anything. Think of it this way: someone else gave us a witness $x_0$ for inhabitedness of $M$, and we are free to do something with it.
Classically, "$M$ is inhabited" ($\exists x \in M . \top$) and "$M$ is non-empty" ($\lnot\forall x \in M . \bot$) are equivalent. Constructively, the former makes more sense and is useful.
Because we showed uniqueness of fixed points we actually get a fixed-point operator $\mathrm{fix}_M$ from contractions on $M$ to points of $M$, rather than just a $\forall\exists$ statement.
Finally, the following fixed-point theorems have constructive versions:

Knaster-Tarski fixed-point theorem for monotone maps on complete lattices
Banach's fixed-point theorem for contractions on a complete metric space
Knaster-Tarski fixed-point theorem for monotone maps on dcpos (proved by Pataraia)
Various fixed-point theorems in domain theory usually have constructive proofs
Recursion theorem is a form of fixed-point theorem and it has a constructive proof
I proved that Knaster-Tarski fixed-point theorem for monotone maps on chain-complete posets does not have a constructive proof. Similarly, the Bourbaki-Witt fixed-point theorem for progressive maps on chain-complete posets fails constructively. The counter-example for the later one comes from the effective topos: in the effective topos ordinals (suitably defined) form a set and the successor maps is progressive and has no fixed points. By the way, the successor map on the ordinals is not monotone in the effective topos.

Now that's rather more information than you asked for.


Massive online collaboration for solving open problem in theoretical computer science In Polymath projects a large group work on an open problem.

What kind of problems seem to work best in this framework?
Are there any good candidates for a polymath project in theoretical computer science?
Are there any obstacles that make Polymath projects less likely to succeed in theoretical computer science in comparison to other areas of mathematics?

Polymath projects seems to succeed when a breakthrough happens, and one is trying to optimize the result of the breakthrough or come up with simpler or better proof. See https://en.wikipedia.org/wiki/Polymath_Project#Problems_solved. As such, you would have to pick a problem of this nature in CS. The only one that comes immediately to mind is improving the constant in matrix multiplication https://en.wikipedia.org/wiki/Matrix_multiplication#Algorithms_for_efficient_matrix_multiplication, which is currently at 2.4... But frankly, I am not sure enough people care about it enough to work on it...

Questions for which I would expect polymath to fail miserably: P=NP, online optimality, UGC, etc.


Parameterized complexity of graph intersection number What if anything is known about the parameterized complexity of computing the intersection number of a graph (the smallest number of cliques needed to cover all its edges)?

It has long been known to be NP-complete, and it's obviously FPT because it has a kernel: if you can cover a graph with $k$ cliques then there are at most $2^k$ different closed neighborhoods of vertices (two vertices have the same neighborhoods if they belong to the same set of cliques), and you might as well keep only one vertex per neighborhood. Is this observation in the literature somewhere? What kind of dependence on $k$ is known?

The problem has been studied under the name Edge Clique Cover, and the observations you make regarding data reduction have been used to get a kernel with 2^k vertices. It is a long standing open problem whether a polynomial kernel exists. I don't know about good bounds on the running time, see http://theinf1.informatik.uni-jena.de/publications/clique-cover-jea07.pdf


Permutation phrases with LR parsing A permutation phrase is an extension to the standard (E)BNF context free grammar definitions: a permutation phrase $\{ A_1, \dots, A_n \}$ contains $n$ productions (or equivalently, nonterminals) $A_1$ through $A_n$. At the position of the permutation phrase, we'd like to see every one of these productions exactly once, but we are not interested in the ordering of these nonterminals.

For example:

S <- X { A, B, C } Y

is equivalent to:

S <- X  A B C  Y
S <- X  A C B  Y
S <- X  B A C  Y
S <- X  B C A  Y
S <- X  C A B  Y
S <- X  C B A  Y

The concept seems to be introduced in "Extending context-free grammars with permutation phrases". Therein it is also described how to parse these phrases in linear time using an LL(1) parser.

The paper "Parsing permutation phrases" describes a method for parsing permutation phrases using parser combinators. These are the only two papers I've found that talk about permutation phrases and how to parse them.

Seeing that we can easily parse these kinds of permutation phrases with LL(1) based parsers, my guess would be that we can do the same with LR(1) style parsers. My question is therefore:

  Can a grammar containing permutation phrases be parsed in time linear in the input string size using LR(1) machinery while maintaining a reasonably sized table?

Permutation phrases do not extend the power of context-free languages: as in my example above one can simply enumerate all possible permutations. However, the grammar then explodes as the resulting grammar can be of size $O(|G|!)$. This allows linear time parsing, but the size of the grammar becomes way too large.

The above approach works for any parsing algorithm (although it is not useful), so maybe we can do better for specific algorithms. We can reduce the blowup to 'merely' exponential ($O(2^{|G|})$) by encoding the phrases into the LR table: we can have LR items encode which productions have yet to be seen, and therefore reduce the blowup to all subsets of the permutation phrases.

Although this is better, it is of course not good enough - having a permutation phrase of 30 items would make the grammar unusable. There is still one part of LR parsing we haven't touched yet, and that is the actual stack-based procedure used for parsing. I imagine storing counters on the stack may be able to solve the problem, but I'm not sure how to do that.

I'm currently implementing a parser generator, and in the problem domain permutation phrases would be a gift from heaven. As I'm using LR(1) machinery, the above question followed.

Have you considered converting this into a semantic problem?  Instead of grammar rules for all permutations of nonterminals { A, B, C }, simply have one rule to recognize (A | B | C)^3 together with special internal code that makes sure only one of each is recognized, otherwise it declares an error.  I would insert an empty production before the above clause, whose reduction triggers initialization of whatever you are using to count A's, B's, and C's, and one after, whose reduction triggers the counter check and (if necessary) asserts the error.  (of course this could get a bit tricky if the grammar is recursive through A, B, and/or C)


Parallel Dynamic Search Is there a natural parallel analog to red-black trees with similar or even not-terribly-worse properties for updates while being reasonably work-efficient ?

More generally, what's the best we can do for parallel search with updates ?

From what I can tell, strategies involve relaxing balance conditions, then performing rebalancing updates in bursts.  Here is a paper from Hanke et al., 1997 [PDF], which I think focuses on their technique of aggregating and resolving update operations so that they can be performed concurrently.


Algorithm for converting very large NFA to DFA I have really large Non-deterministic finite automaton and I need to convert it to the DFA.

By large I mean 40 000+ states.
So far I have done some experiments and programmed the default algorithm that searches through table (as described here), but even after optimization is quite slow and very memory consuming. I am aware of the fact, that the number of states can grow exponentially, but after minimization, the resulting DFA has about 9 000 states and that is bearable.

So my question is, is there some algorithm, that would be faster or more memory friendly?

Have you tried Brzozowski's algorithm?  It's worst-case running time is exponential, but I see some references suggesting that it often performs very well, especially when starting with a NFA that you want to convert to a DFA and minimize.

The following paper seems relevant:

On the performance of automata minimization algorithms, Marco Almeida, Nelma Moreira, Rogerio Reis.

It evaluates a number of different algorithms for DFA minimization, including their application to your situation where we start with a NFA and want to convert it to a DFA and minimize it.

What does the strongly connected components (SCC) decomposition of your NFA (considering it as a directed graph) look like?  Does it have many components, where none of the components is too large?  If so, I wonder if it might be possible to devise a divide-and-conquer algorithm, where you take a single component, convert it from NFA to DFA and then minimize it, and then replace the original with the new determinized version.  This should be possible for single-entry components (where all edges into that component lead to a single vertex, the entry vertex).  I don't immediately see whether it would be possible to do something like this for arbitrary NFAs, but if you check what the structure of the SCC looks like, then you might be able to determine whether this sort of direction is worth exploring or not.


Consequences of $NP=coNP$ and $P\ne NP$? We know that if $P=NP$ then the whole PH collapses.
What if the polynomial hierarchy collapses partially ? (Or how to understand that PH could collapse above a certain point and not below ?)

In shorter words, what would be the consequences of $NP=coNP$ and $P\ne NP$ ?

To me, one of the most basic and surprising consequences of $\mathsf{NP}=\mathsf{coNP}$ is the existence of short proofs for a whole host of problems where it is very difficult to see why they should have short proofs. (This is sort of taking a step back from "What other complexity implications does this collapse have?" to "What are the very basic, down-to-earth reasons this collapse would be surprising?")

For example, if $\mathsf{NP}=\mathsf{coNP}$, then for every graph that is not Hamiltonian, there is a short proof of that fact. Similarly for graphs that are not 3-colorable. Similarly for pairs of graphs that are not isomorphic. Similarly for any propositional tautology.

In a world where $\mathsf{P} \neq \mathsf{NP} = \mathsf{coNP}$, the difficulty in proving propositional tautologies isn't that some short tautologies have long proofs - because in such a world every tautology has a polynomially short proof - but rather that there is some other reason that we are unable to find those proofs efficiently.


Complexity of generically inverting a class of near linear monotonic functions Given a monotonic increasing function $f(\mathbb{N}) \rightarrow \mathbb{N}$ and a slack function  $a(\mathbb{N})\rightarrow \mathbb{N}$, where $f(n) = n \pm O(a(n))$;  how many calls to $f$ do we need to brute force $f^{-1}$ as a function of $a$ and $n$?

This problem comes up regularly when you have a near linear monotonic increasing sequence on OEIS which you have a good complexity algorithm to compute it, and need a generic algorithm to get an upper bound on the complexity of computing the inverse.

A simple variant of binary search takes $O(\log a(n))$ time assuming $a(n) = O(n)$ is monotonic.  To compute $f^{-1}(n)$, find $k$ s.t.
$$f(n-2^k) \le n \le f(n+2^k)$$
by trying $k = 0, 1, 2, \ldots$ until the bound holds.  This takes $O(\log a(n))$ steps and produces a window of size $O(a(n))$ which can be finished off with binary search.

Unfortunately, this is the best you can do without a stronger condition on $f(n)$.  Proof sketch: assume that after $O(1)$ queries we've reduced to an interval $[a,b]$ s.t.
$$\begin{aligned}
b-a &\ge c a(n) \\
f(b)-f(a) &= \Theta(a(n))
\end{aligned}$$
Then $f(n)$ within $[a,b]$ is an arbitrary monotonic function subject to the end constraints, and we can adversarily choose $f$ to make $\Theta(\log a(n))$ optimal.


Quantum Money where not even the Bank can counterfeit The Quantum Money system proposed in "Quantum Copy-Protection and Quantum Money" has the following properties:

The bank can produce bank notes in the form of quantum states.
Anyone can verify that one of these quantum states is a valid bank note without destroying the quantum state.
No one except the bank can produce more bank notes, even if they already have some.

All assuming that the actors only have polynomial time quantum computers.

My question is if you can take this step further and make it so that even the bank is unable to forge bills.

What do I mean by this? The quantum money protocol I am looking for would have an integer parameter $k$, and the bank could only create $k$ valid bank notes.

(This might seem impossible since the bank could just run the protocol again to get $k$ more bank notes. A way to prevent this would be to require it to produce a random classical string $s$ of bits that it releases publicly, such that it can not run the protocol again and produce the same $s$ with non-negligible probability.)

There are proposals for quantum money where it appears that not even the bank can produce two copies of a quantum money state with the same serial number. See

Farhi et al's paper Quantum Money from Knots,
Mark Zhandry's paper Quantum Lightning Never Strikes the Same State Twice,
Daniel Kane's paper Quantum Money from Modular Forms.

In order to make sure that the bank can only produce $k$ banknotes, one would need to have the bank publish the serial numbers of exactly $k$ banknotes in some secure location. Otherwise it could make as many bank notes as it wants (although they would all have different serial numbers).


How to determine whether there is exactly one simple path between two nodes in a graph Given an undirected sparse graph G and a list of queries (each query consisting of two nodes), how to determine if there exists exactly one simple path between them (for each query) ? I have a (trivial) solution based on a breadth-first search (for each query the complexity would be O(V+E)) but is there a more efficient way to answer the queries?

You don't have to find the actual simple path, just answer each query with a True/False answer.

This question was asked as part of the Latin American regional competition of the 2011 ACM International Collegiate Programming Contest.

Ok, now that you've revealed the motivation: there is exactly one simple path between two nodes iff there is a path in which every edge is a bridge of the graph. So find all the bridges (standard linear time by depth first search) and compute the connected components of the subgraph they form. Two vertices have a unique simple path iff they belong to the same component.


Complexity of Haemers' minimum rank In 1978 Willem H. Haemmers published "An upper bound on the Shannon capacity of a graph".

Tims has a survey of more recent results his thesis.

What is the computational complexity of computing Haemmer's minimum rank function?

Computing min rank is NP-hard:

Rene Peeters, "Orthogonal Representation over Finite Fields and the Chromic Numbr of Graphs", 1996.
Salim Y. El Rouayheb, Mohammad Asad R. Chaudhry, Alex Sprintson, "On the Minimum Number of Transmissions in Single-Hop Wireless Coding Networks", 2007.


What is the reverse of greedy algorithm for setcover? A common approach to approximating SETCOVER is the greedy algorithm (Algorithm 2.2 Vazirani). This algorithm greedily picks the most cost-effective subset at each iteration, removes covered elements, until there are no more uncovered elements.

However, one can go from the other end. Start with the full set, and iteratively remove the subset that is least cost-effective, and will not cause any elements to be uncovered, until there are no more such subsets.

In some sense, the second algorithm may be better because there wont be any redundant subsets in the solution. My question is, what is the name of this algorithm? Does it have the same runtime complexity and approximation ratio as the first one? I could not find any mention of this algorithm after a few hours of searching.

(Please include unweighted SETCOVER for comparison)

Edit: I see that the number of steps can in fact be as large as $(n-1)$ where $n$ is the number of subsets.

The approximation guarantee will be significantly worse.

Assume you want to cover the set $U=\{1,\ldots,2n\}$.
For every $i=1,\ldots,n$ define a set with n+1 elements by $S_i=\{i,n+1,\ldots,2n\}$.
Assume we want to cover U with the sets
$C=\{S_1,\ldots,S_n,U\}$, where $c(U)=2, c(S_i)=1$.

We would now start with $C$ ans see that the effectivity of the sets $S_i$ is
$$\rho(S_i)=\frac{|S_i|}{c(S_i)}=\frac{n+1}{1}=n+1.$$

In contrast to this the effectivity of $U$ is
$$\rho(U)=\frac{|U|}{c(U)}=\frac{2n}{2}=n<n+1.$$

Thus the reverse greedy would throw out the less effective $U$ leaving us with a solution of cost $n$ while there is a solution of cost $2$.


When does a set of infixes determine a set of ($\omega$-) words If a have a set of finite infixes of a specific length, which $\omega$-languages are determined by them, and furthermore, when does a set of infixes determine a $\omega$-word uniquely. For example for the set $W = \{ 0, 1 \}$ all words in $X^* \setminus \{ 0^\omega, 1^{\omega} \}$ have it as infixes, and if I have $V = \{ 011, 110, 101 \}$ it determines the three words
$$
 011011011011\ldots, \quad
 110110110110\ldots, \quad
 101101101101\ldots.
$$
What could be said about the relations about infix-sets and $\omega$-languages, are there any results or articles on this topic?

There are several interesting subquestions in your question:

Which $\omega$-languages are determined by a set of finite infixes of a specific length?
When does a set of infixes determine a $\omega$-word uniquely?
What could be said about the relations about infix-sets and $\omega$-languages?
Are there any results or articles on this topic?

Let $A$ be a finite alphabet, let $n$ be a positive integer and let $F$ be a subset of $A^n$.
Given an $\omega$-word $u$, let $F_n(u)$ be the set of its factors (= infixes) of length $n$.

Question 1. It can be restated as follows: What is the $\omega$-language
$$
  L(F) = \{ u \in A^\omega \mid  F_n(u) = F \}?
$$
The answer is
$$
  L(F) = \bigcap_{x \in F}A^*xA^\omega \setminus \bigcup_{x \in A^n \setminus F}A^*xA^\omega
$$
which shows that $L(F)$ is $\omega$-regular (it actually belongs to a much smaller class of $\omega$-languages than the regular ones, see below).

Question 2. I only have a weak answer to this question. Given $F$, one can effectively compute $L(F)$ (say, by a finite Büchi automaton) and then one can effectively decide whether $L(F)$ contains a single $\omega$-word (which has to be ultimately periodic). I also tried the other way around: given an ultimately periodic word $uv^\omega$, is the language $\{uv^\omega\}$ of the form $L(F)$ for some $F$? This question is again decidable, but they might be some simple combinatorial characterization on the pair $(u, v)$. Unfortunately, I only got some partial results in this direction.

Question 3. I know of several topics in which infix-sets and $\omega$-languages are related.

Locally testable $\omega$-languages (the notion of locally testable languages was originally introduced for finite words and later extended to infinite words [2]). The language $L(F)$ is an example.
Factors of biinfinite words [1].
First order logic of one successor [3].
Sophic shifts and subshifts of finite type in symbolic dynamics [4].

Question 4. A few references:

[1] D. Beauquier and M. Nivat, About rational sets of factors of a bi-infinite word, LNCS 194, (1985) 33-42.
[2] J.P. Pécuchet Étude syntaxique des parties reconnaissables de mots infinis, Theoret. Comput. Sci. 56 (1988) 231-248.
[3] The expressive power of existential first order sentences of Büchi's sequential calculus.
[4] M.P. Béal and D. Perrin, Symbolic Dynamics and Finite Automata.


Constructively efficient algorithms without efficient correctness and efficiency proof I am looking for natural examples of efficient algorithms (i.e. in polynomial time) s.t.

their correctness and efficiency can be proven constructively (e.g. in $PRA$ or $HA$), but
no proof using only efficient concepts is known (i.e. we don't know how to prove their correctness and efficiency in $TV^0$ or $S^1_2$).

I can make artificial examples myself. However I want interesting natural examples, i.e. algorithms studied for their own sake, not created just to answer this type of questions.

This is the same idea as Andrej's answer but with more details.

Krajicek and Pudlak [LNCS 960, 1995, pp. 210-220] have shown that if $P(x)$ is a $\Sigma^b_1$-property that defines primes in the standard model and $$S^1_2 \vdash \lnot P(x) \to (\exists y_1,y_2)(1 < y_1, y_2 < x \land x = y_1y_2)$$ then there is a polynomial time factoring algorithm. This gives a bunch of examples since any NP algorithm for primality testing basically yields such a $\Sigma^b_1$ formula. In particular, the AKS primality test gives such a formula (when appropriately recast in the language of $S^1_2$). The paper by Krajicek and Pudlak gives more cryptography related examples of this kind but predates AKS and related advances by a few years.


Lower bounds on the size of CFGs for specific finite languages Consider the following natural question: Given a finite language $L$, what is the smallest context-free grammar generating $L$?

We can make the question more interesting by specifying a sequence of languages $L_n$, for example $L_n$ is the set of all permutations of $\{1,\ldots,n\}$: intuitively, a CFG for $L_n$ would "need" to have size $\Omega(n!)$. So we're interested in the asymptotic size of the smallest CFGs for the languages.

Similar questions have been dealt with in several papers:

Charikar et al. ("Approximating the Smallest Grammar: Kolmogorov Complexity in Natural Models") consider how difficult it is to approximate the size of the smallest CFG generating a given word.
More work in that direction is Arpe and Reischuk, "On the Complexity of Optimal Grammar-Based Compression".
Peter Asveld has several papers on the subject (e.g. "Generating All Permutations by Context-Free Grammars in Chomsky Normal Form"). He's trying to optimize some parameters on specific types of grammars generating the set of all permutations, specifically Chomsky and Greibach normal forms.

However, so far I haven't been able to find any paper trying to prove a bound of $\Omega(n!)$ on the size of a CFG generating $L_n$.

  Are there papers providing lower bounds for the size of context-free grammars for specific finite languages?

In response to several questions on this site as well as on math.stackexchange, I came up with a simple method able to prove exponential lower bounds on CFGs for specific languages, for example $L_n$. Are these results new? I find that hard to believe, and I'll be glad to get any literature pointers.

A kind reviewer sent me a paper which proves exactly the same lower bound I do, in exactly the same way. The paper is

  K. Ellul, B. Krawetz, J. Shallit, M.-w. Wang, Regular expressions: new results and open problems, J. Autom. Lang. Comb. 10 (2005), 407–432.

The result is Theorem 30 in the paper.


How to prove fooling set problem to be NP-hard I read in a paper showing that it can be implemented by reducing induced matching problem on bipartite graphs to fooling set. But the proof was omitted in that paper and I cannot find answer by myself.

Thank you.

Edit: The fooling set technique is defined by the following theorem:

The proof is given in Section 6 the full version of the paper. I bring an excerpt, since there was originally much confusion about what "fooling set" means.

Basically, the notion of fooling set was introduced by Jean-Camille Birget in Intersection and union of regular languages and state complexity.

To prove that fooling set problem (as defined below) is NP-hard, the authors reduced the NP-complete induced matching problem on bipartite graphs to it.

Here's an excerpt of the paper, which defines the problem and proves the theorem.


"Directed" problems that are easier than their "undirected" variant. I was presenting a lecture on pancake sorting, and mentioned that:

Sorting by reversals is NP-hard
"signed" sorting by reversals is in P.

Which got me thinking. There is a sense in which "signed" sorting is "directed" - you can view the sign as a direction (and indeed, this is the motivation from evolutionary biology). But it's an easier problem ! This is unusual because generally (at least on graphs) directed problems are harder (or at least as hard) as their undirected counterparts.

  Assuming a generous definition of "directed", are there any examples
  of directed problems that are easier than their undirected
  counterparts ?

Counting Eulerian circuits for directed graphs is doable in polynomial time using the BEST theorem, while apparently, the same problem for undirected graphs is #P-complete.


Counting the number of satisfying assignments in a POSITIVE CNF-SAT We know the problem of counting the number of satisfying assignment in a given general boolean formula (CNF-SAT), a given DNF formula, or even a given 2SAT formula is a #P-complete problem.

Now, consider a CNF-SAT with no negative literal (no $\neg A$, always $A$). The decision problem is very easy (set all of the variables to TRUE and check if the assignment is satisfying the formula), but what about counting the number of satisfying assignments? Does this have a polynomial time algorithm? Or it's a #P-complete problem.

This is still #P-complete [1]. This problem is usually referred to as montone (#)SAT. Monotone #2-SAT is already #P-complete (this is equivalent to counting vertex covers of a graph).

[1] Roth, Dan. "On the hardness of approximate reasoning." Artificial Intelligence 82.1-2 (1996): 273-302.


How to iterate over vectors in order of probability in small space Consider an $n$ dimensional vector $v$ where $v_i \in \{0,1\}$.  For each $i$ we know $p_i = P(v_i = 1)$ and let us assume the $v_i$ are independent.  Using these probabilities, is there an efficient way to iterate over binary $n$ dimensional vectors in order from most likely to least likely (with arbitrary choices for ties) using space sublinear in the output size?

Take for example $p = \{0.8, 0.3, 0.6\}$. The most likely vector is $(1,0,1)$ and the least likely is $\{0,1,0\}$.

For very small $n$ we could label each of the $2^n$ vectors with its probability and simply sort but this would of course still not use sublinear space.

A close variant of this question was previously asked at https://cs.stackexchange.com/questions/24123/how-to-iterate-over-vectors-in-order-of-probability .

The following gives an algorithm that uses approximately $2^n$ time and $2^{n/2}$ space.

First, let's look at the problem of sorting the sums of all subsets of $n$ items.

Consider this subproblem: you have two sorted lists of length $m$, and you would like to create a sorted list of the pairwise sums of the numbers in the lists. You would like to do this in roughly $O(m^2)$ time (the output size), but sublinear space. We can achieve $O(m)$ space. We keep a priority queue, and pull the sums out of the priority queue in increasing order.

Let the lists be $a_1 \ldots a_m$ and $b_1 \ldots b_m$, sorted in increasing order. We take the $m$ sums $a_i + b_1$, $i = 1 \ldots m$, and put them in a priority queue.

Now, when we pull the smallest remaining sum $a_i + b_j$ out of the priority queue, if $j < m$ we then put the sum $a_i + b_{j+1}$ into the priority queue. The space is dominated by the priority queue, which always contains at most $m$ sums. And the time is $O(m^2 \log m)$, since we use $O(\log m)$ for each priority queue operation. This shows we can do the subproblem in $O(m^2 \log m)$ time and $O(m)$ space.

Now, to sort the sums of all subsets of $n$ numbers, we just use this subroutine where the list $a_i$ is the set of sums of subsets of the first half of the items, and the list $b_i$ is the set of sums of subsets of the second half of the items. We can find these lists recursively with the same algorithm.

We will now consider the original problem.  Let $S_0$ be the set of coordinates which are $0$, and $S_1$ be the set of coordinates which are $1$. Then
\begin{eqnarray*}\prod_{i \in S_0} p(v_i=0) \prod_{i \in S_1} p(v_i=1) &=& \prod_{1\leq i \leq n} p(v_i=0)   \prod_{i \in S_1} \frac{p(v_i=1)}{p(v_i=0)} \\ &=& \prod_{1\leq i \leq n} p(v_i=0) \exp\,\left(\sum_{i \in S_1} \log \frac{p(v_i=1)}{p(v_i = 0)}\right).\end{eqnarray*}

Sorting these numbers is the same as sorting the numbers $\sum_{i\in S_1}\log p(v_i=1) - \log p(v_i=0)$, so we have reduced the problem to sorting the sums of subsets of $n$ items.


Proof of undecidability not by reduction from the halting problem The usual way of proving undecidability is by reduction from a RE-complete problem such as the halting problem, validity in first order logic, satisfiability of Diophantine equations, etc.

It is known that there are recursively enumerable, but undecidable problems that are not RE-complete, but these are artificial constructions (that is, sets that have been defined just for showing this "density" result).

How would one tackle proving undecidability without reduction from a RE-complete problem? Diagonalization?

One can show fairly directly that Kolmogorov complexity is not computable, see e.g. Sipser, 3rd edition, problem  6.23.


FSMs with finite memory Consider an FSM and a finite set of variables. The FSM has the special property that each state contains a set of commands, with each command taking the form of "variable = expr(variable, ...)" e.g., x = y + z + 2. The commands are "activated" whenever the FSM transitions into the containing state.

My question is what class of problems are computable in this model? Perhaps more specifically, say M(k) is one of these state machines with k variables.

Perhaps the only claim that seems obvious to me about this construction is that all computable problems for M(k+1) is strictly larger than for M(k).

Please pardon me if my question is not well formed, or if I'm misusing some terminology. Thanks in advance.

Edit: Suppose also we add the additional constraint that each 'variable' has some range [-r, r].

Edit2: Thanks Martin Schwartz. I don't have the "street cred" yet to upvote or respond to your answer. Thanks!

Let your original state machine $M(k)$ have $n$ states and transition relation $t(s,s')$, where each transition $t(s,s')$ updates the global variables $x_1,...,x_k$ by applying function
$(x'_1,...,x'_k) = f_{t(s,s')} (x_1,...,x_k)$.
Then $M(k)$ is equivalent to a standard FSM with $n(2r+1)^k$ states, where each state encodes a tuple $(s,x_1,...,x_k)$ with each $x_i$ encoding one fixed value in $[-r,r]$, and new transition relation $t'$

$t'( (s,x_1,...,x_k), (s',x'_1,...,x'_k)) \Leftrightarrow t(s,s') \wedge [(x'_1,...,x'_k) = f_{t(s,s')} (x_1,...,x_k)]$.


Proof that Entanglement Cannot Increase the Capacity of a Noiseless Classical Channel I am aware that quantum entanglement cannot increase the asymptotic capacity of a noiseless classical channel. However, can anyone provide some type of reference in the literature that contains a proof of this particular feature of quantum communication? Very much appreciated.

Thanks.

It follows directly from our formula for entanglement-assisted capacity. An alternate proof uses the classical reverse Shannon theorem and the fact that entanglement does not increase the capacity of a noiseless classical channel. This last fact can be proved by showing that if it did, you could use entanglement to transmit information with no communication. I don't remember whether the alternate proof is in the linked reference or not.


Does a weighted graph have a path with weight zero? Given a weighted digraph $G=(V,E)$, where each edge is associated with a weight (could be positive, negative, or zero). We define the weight of a path to be the sum of the weights along this path.

The question: given two vertices $s,t$, decide whether there is a (not necessarily simple) path from $s$ to $t$ such that the weight of the path is 0.

It is not very difficult to see that this problem is in NP. I am wondering whether there is a polynomial time algorithm, or it is NP-hard.

You can reduce Subset Sum to your problem.

Rough idea: Connect s,t with chain of double edges corresponding to weights and zero. A path from s to t picks a subset.
These double edges can be expanded with dummy nodes to make a normal graph. To ensure non-empty subset make n chains to t with initial single edge corresponding to weight.


Is there any efficient algorithm for computing all semigroups of order n? Is there any efficient algorithm for computing all semigroups of order n?

I found the following paper which solves a bit different problem.

Veronique Froidure and Jean-Eric Pin, "Algorithms for computing finite semigroups"

You asked the same question here
and I answered it. Jean-Eric's algorithm is for computing the elements (among other things) of a semigroup defined by a generating set, and is not related to your question.


Unique $k$-SAT benchmarks This question is probably on the border line between on-topic and off-topic, however I've seen similar questions here, therefore I'll ask it.

I'm implementing a Unique $k$-SAT solver, whose input is a $k$-CNF formula having at most $1$ satisfying assignment. To test its practical behaviour, I need a set of such formulas. I've searched for them on the web, and found nothing (while, on the other hand, it is very easy to find suites of ordinary $k$-CNF formulas).

  Where can I find Unique $k$-SAT instances?

Alternatively, I would be content also to know any procedure to generate uniquely satisfiable instances. The only approach I'm aware of goes under the name of planted SAT instance generation: you randomly generate an assignment of $n$ variables, then you generate only those clauses which agree with such assignment. This approach is unsatisfactory for my purposes, for the following reasons:

The obtained formula may have further undesired satisfying assignments.
To be sure that the formula is satisfied uniquely by the desired assignment, you should introduce all the possible clauses that agree with it. This would produce formulas with too many clauses, which will probably be easy to solve and therefore not representative of the worst case behaviour of the solver. It is not obvious to me how we can efficiently force uniqueness while keeping the number of clauses reasonable.

  How can we generate uniquely satisfiable formulas with a reasonable number of clauses? By reasonable I mean far from the maximum $2^k \cdot {n \choose k}$.

Here is one way to generate a Unique $k$-SAT instance, given a SAT instance $\varphi$ that you know is satisfiable.  Consider the formula $\psi(x)$ given by

$$\varphi(x) \land h(x)=y,$$

where $h$ is a hash function that maps an assignment $x$ to a $k$-bit value (for some small value of $k$), and $y$ is a random $k$-bit value.  If $\varphi$ has about $2^k$ satisfying assignments, then (heuristically) we assume that $\psi$ will have exactly one satisfying assignment (with constant probability).  We can test whether this is the case using a SAT solver (namely, test whether $\psi$ is satisfiable; if it is, and $x_0$ is one satisfying assignment, test whether $\psi(x) \land x \ne x_0$ is satisfiable).  If $k$ is not known, you can find $k$ using binary search or just by iterating over each candidate value $k=1,2,\dots,n$ (where $n$ is the number of boolean variables in $x$).

You can choose the hash function freely.  You'll probably want to make it as simple as possible.  One extremely simple construction is to have $h$ pick out a random subset of $k$ bits from $x$.  A slightly more sophisticated construction is to have the $i$th bit of $h(x)$ be the xor of two randomly chosen bits from $x$ (choosing a separate pair of bit positions for each $i$, independently).  Keeping $h$ simple will keep $\psi$ relatively simple.

This kind of transformation is sometimes used/suggested, as part of a scheme for estimating the number of satisfying assignments to a formula $\varphi$; I've adapted it for your particular need.

You can find many testbeds of SAT instances on the Internet, and you could apply this transformation to all of them, to obtain a collection of Unique $k$-SAT instances.

Another possibility would be to generate Unique $k$-SAT instances from cryptography.  For instance, suppose $f:\{0,1\}^n \to \{0,1\}^n$ is a cryptographic one-way permutation.  Let $x$ be a randomly chosen element of $\{0,1\}^n$, and let $y=f(x)$.  Then the formula $\varphi(x)$ given by $f(x)=y$ is a Unique $k$-SAT instance.  As another example, pick two large prime numbers $p,q$ randomly, and let $n=pq$.  Then the formula $\varphi(x,y)$ given by $x \cdot y = n \land x>1 \land y>1 \land x \le y$ (with the obvious correspondence between bit-strings and integers) is a Unique $k$-SAT instance.  However, these constructions do not seem like a useful way to benchmark or optimize your solver.  They all have a special structure, and there is no reason to believe that this structure is representative of real-world problems.  In particular, SAT instances drawn from cryptographic problems are known to be extremely hard, much harder than SAT instances drawn from many other real-world applications of SAT solvers, so they aren't a very good basis for benchmarking your solver.

In general, all of the techniques mentioned in this answer have the drawback that they generate Unique $k$-SAT instances with a particular structure, so they might not be what you are looking for -- or, at least, you might not want to rely solely upon formulae generated in this way.  A better approach would be to identify applications of Unique $k$-SAT (who do you think is going to use your solver, and for what purpose?), and then try to obtain some realistic examples from those application domains.

For a related topic, see also Generating interesting combinatorial optimization problems


Does focused proof search ever have to backtrack across the choice of focus formula? There are a lot of different "focused" sequent calculi for lots of different logics, but my understanding is that many or most of them have the following flavor.  First one divides the connectives into "left-asynchronous / positive" (e.g. $\vee$, $\oplus$, $\otimes$, $\exists$), whose left rules are invertible, and "right-asynchronous / negative" (e.g. $\wedge$, $\Rightarrow$, $\multimap$, $\forall$), whose right rules are invertible.  Then the focused proof search (i.e. building a sequent calculus proof bottom-up) has two phases.  First we apply all the asynchronous/invertible rules, in any order.  Second, we focus on some formula and apply all of its synchronous rules, keeping focus on the formulas thereby generated and immediately applying any applicable asynchronous rules (or, equivalently, reverting to phase one in all generated subgoals), until we reach an atomic formula.  At that point we can either finish the proof with an identity rule, or re-focus on a different formula.
At least some systems require the proof to finish as soon as the focus formula becomes atomic, which I believe means that if you chose the wrong formula to focus on in the first place you may have to backtrack.  My question is rather about what happens if we allow the proof to re-focus on a different formula when it reaches an atomic one.  In that case, is it possible to "choose the wrong formula" to focus on and have to backtrack?  In other words, is it ever possible that there are synchronous formulas that must not be decomposed in a proof, or that must be decomposed in a particular order?
It's easy to come up with examples where you can get in trouble if you try to apply synchronous rules before asynchronous ones, e.g. $p\vee q \vdash q\vee p$.  But the focused method requires all asynchronous rules to happen immediately, so this sort of problem doesn't arise.
Note also that there is another unrelated source of backtracking that this says nothing about, involved in individual synchronous rules.  For instance, there are two $\& L$ rules that we have to choose between, and in a rule like $\otimes R$ we have to decide how to split the context between the two premises, and it's certainly always possible to make wrong choices there and have to backtrack.  That's not what I'm asking about.
I've phrased this as a general question about all focused sequent calculi, but of course it's possible that the answer depends on the logic or on the details of the calculus.  In that case I would be interested to know what properties of a logic or calculus lead to different behavior.

Yes, backtracking in focused proof search may be necessary due to a wrong choice of focus formula.  Consider the provable sequent
$$\vdash p\otimes q, (p^\bot\mathrel{\wp} q^\bot)\otimes r, r^\bot.$$
Choosing to focus on $p\otimes q$ leads to a dead end, because however you "split" the context you end up with an atom ($p$ or $q$) without matching dual.  So $(p^\bot\mathrel{\wp} q^\bot)\otimes r$ must be decomposed first.

A side remark, not directly related to the question but which gives some  further context: the formula $p\otimes q$ above is known to proof net connoisseurs as a "non-splitting tensor".  When showing that proof nets (in the sense of suitably labelled graphs satisfying certain connectivity and acyclicity conditions) correspond to sequent calculus proofs (the sequentialization theorem) one must at some point prove the non-trivial "splitting lemma": if the conclusions of a proof net come only from axiom or tensor nodes, then there is one such tensor node which is "splitting", in the sense that removing it decomposes the proof net into two connected components which are themselves proof nets (this allows sequentialization to be proved inductively).  One of course may wonder whether all tensors are always splitting, and the above is the minimal counterexample.
In terms of proof nets, focusing strengthens the splitting lemma by adding that there always exists a "hereditarily splitting tensor", in the sense that there is a tensor node such that all tensor nodes directly above it have the splitting property.


The motivation for using Karp-reductions in the theory of $\mathcal{NP}$-completeness The notion of polynomial time reductions (Cook reductions) is an abstraction of a very intuitive concept: efficiently solving a problem by using an algorithm for a different problem.

However, in the theory of $\mathcal{NP}$-completeness, the notion of $\mathcal{NP}$-hardness is captured via mapping reductions (Karp reductions). This concept of "restricted" reductions is much-less intuitive (at least to me). It even seems a bit contrived, as it creates a somewhat less intuitive notion of hardness; by that I'm referring to the fact that $\mathcal{NP}$ does not trivially contains $co-\mathcal{NP}$. Although in complexity theory we are very used to the concept that being able to solve a problem such as $\mathsf{SAT}$ does not imply that we can solve $\overline{\mathsf{SAT}}$, in natural settings (which are captured by Cook reductions), assuming we have an algorithm for solving $\mathsf{SAT}$, we can solve $\overline{\mathsf{SAT}}$ just by running the algorithm for $\mathsf{SAT}$ and returning the opposite.

My question is why should we use Karp reductions for the theory of $\mathcal{NP}$-completeness? What intuitive notion does it capture? How does it relates to the way we understand "hardness of computation" in the real world?

Like Turing reductions, many-one reductions came into complexity theory from computability/recursion theory literature. Cook and Karp reductions are natural complexity theoretic versions of similar existing reductions in computability.

There is a intuitive way of explaining many-one reductions: it is a restriction of Turing reductions where we can ask only a single question from the oracle and the oracle's answer will be our answer.

Now the question is why would we need to study this (and any other kind of reductions like truth-table, weak-truth-table, etc.)?

These reductions give a finer picture than Turing reductions. Turing reductions are too powerful to distinguish between many concepts. A very large portion of computability theory is devoted to the study of c.e./r.e. degrees. The notion of an c.e. set is central. We can have TM machine that can enumerate an infinite set, we may not be able to enumerate its complement. If you want to study c.e. sets then Turing reduction is too strong since c.e. sets are not closed under it. So many-one reductions are a (and maybe the) natural way of defining reductions for this purpose.

Other types of reductions are defined for similar reasons. If you are interested I would suggest checking Piergiorgio Odifreddi's "Classical Recursion Theory". It has a quite comprehensive chapter on different reductions and their relations.

Now for complexity theory the argument is similar. If you accept that $\mathsf{NP}$ is a extremely natural class of problems and you want to study $\mathsf{NP}$, then Cook reductions are too strong. The natural choice is a weaker reduction such that $\mathsf{NP}$ is closed under it and we can prove existence of a complete problem w.r.t. to those reduction for $\mathsf{NP}$. Karp reductions are the natural choice for this purpose.


Binary search generalizations for posets? Suppose I have a poset "S" and a monotonic predicate "P" on S.
I want to find one or all maximal elements of S satisfying P.

EDIT: I'm interested in minimizing the number of evaluations of P.

What algorithms do there exist for this problem and what properties and additional operations do they require on S?

What about important special cases, such as:

 S is a linear order - then regular binary search works, as long as you have a "find middle" operation
 S is a lattice
 S is a subset lattice
 S is a multiset lattice
 ...

The two latter cases seem particularly important e.g. for experiment design - you have a set of boolean or real parameters, and you wish to find the smallest possible combination of them that reproduces a particular pattern (e.g. a failing test).

I have not thought this through very much, so please correct me if I am wrong.

Say $w$ is the width of the poset.

For the poset which is the union of $w$ disjoint chains you need at least $w\log n$ evaluations of $P$ by just applying the standard lower bound on the query complexity of binary search to each chain.
Since you give comparisons for free, you can compute a chain decomposition of the poset into $w$ chains for free. Do binary search on each chain to identify the first element that satisfies $P$. Then go over the identified elements and remove any dominated ones. Number of evaluations of $P$ is $O(w\log n)$. This identifies all maximal elements, as there can be at most one maximal element per chain.

ADDED: Actually I am seeing a simple recursive algorithm to do much better ($O(n)$) for the lattice of subsets $2^{[n]}$ (EDIT: domotor described the general strategy in his answer). Here I am assuming $P$ is monotonic downwards (i.e. the subsets $\{X: P(X) = 1\}$ form a lower set), which is I think what you mean. So, here is the algorithm to find a member of the lower set:

a) Test $P(\emptyset)$. If 0, then stop.

b) Test $P(\{n\})$.

b.i) If 0, then recurse on $2^{[n-1]}$ (OK, since no set containing $n$ can be in the lower set).

b.ii) If 1, then there exists a member of the lower set in the sublattice $\{X: n \in X\}$. This sublattice is isomorphic to $2^{[n-1]}$ so once again we can recurse. More precisely, we can run the algorithm for $2^{[n-1]}$, but when the algorithm asks to evaluate $P(Y)$, we evaluate $P(X)$ where $X = Y \cup \{n\}$.

So in each step we recurse on a sublattice which is half the size of original one. Overall, we need to evaluate $P$ at most $2n$ times (in fact you can implement the algorithm to evaluate the predicate $n+1$ times as Yoshio points out, since you only need to check $\emptyset$ once).


direct connection between gradient descent and follow the (perturbed) leader algorithm or weighted majority? Is there a direct conversion between gradient descent ([1], Alg 1 )
and any of the following algorithms?

1) Weighted Majority: http://onlineprediction.net/?n=Main.WeightedMajorityAlgorithm

2) Follow the Leader:  http://people.cs.uchicago.edu/~kalai/papers/onlineopt/onlineopt.pdf
I keep seeing these together, but I don't see the direct conversion.

[1] http://moodle.technion.ac.il/pluginfile.php/195968/mod_resource/content/0/OCP_ICML03.pdf

Yes -- both gradient descent and the randomized weighted majority algorithm (often called multiplicative weights these days) are instantiations of the "Follow the regularized leader" framework. Gradient descent is what comes out if you regularize with the euclidean norm, and multiplicative weights is what comes out if you regularize with Shannon entropy.

See e.g. here (http://www.jennwv.com/courses/F11/lecture11.pdf) for a derivation of the weighted majority algorithm from this framework.


Code in Academic Papers In my academic career, I've read quite a few academic papers on various computer science topics.  Many of which involve an implementation and some assessment of that implementation, yet I have found that very few of them actually publish the code they used.

To me, the benefits of including the actual implementation would be significant, namely:

Extension of trust or reproducability (just test it yourself!)
Clarification of ambiguities (particularly for papers written by non-native speakers)
Reuse of code for applications

So why is it that so few papers actually include any code?

I suppose that it might be the intention of the organization behind the paper to utilize the implementation in their own applications, and thus would not want to release it, but if that's the case, why even write the paper?

Here is a well argued article by David Donoho and Jonathan Buckheit that I read in grad school which touches on exactly this topic from the point of view of wavelet researchers:

"WaveLab and Reproducible Research"

Their idea was even more ambitious, to provide code for reproducing all the figures in their papers in a convenient Matlab package.

I really like their idea but I think the issues are obvious.

(1) It is extra work (cleaning up the code, making at least a rudimentary user interface, writing some documentation, providing some support when people inevitably run into problems)

(2) It is not really required/expected by most conferences/reviewers

But I can't help but feel that the CS research community would benefit if there was an expectation of making the code and data used in any publication publicly available in a usable format. I admit that I haven't done so myself even when the amount of work involved would have been manageable. I think it is just hard to make yourself put in the extra effort when there is no external push.


Distribution of variable sized images/boxes(only aspect ratio given) on a 2D area I'm trying to find a solution for the following problem.
You have a set of pictures or let us assume they are just boxes with a given aspect ratio. And you have a two-dimensional area with width and height.
The boxes can vary in size only their aspect ratio is fixed, BUT they can have also have a max/min size (optional).

I'm looking for an optimal distribution of the boxes in this area, so that the remaining area is minimal.

Is there a solution to this problem, or a best practice to deal with it? Or are there any papers published on that topic?
(some toolkit for javascript dealing with this problem would be brilliant)

What I already found during my short research? Similar problem:
https://stackoverflow.com/questions/5129221/treemapping-with-a-given-aspect-ratio

I have also thought about a mathematical solution to this problem and what I came up with so far was:

x1+...+xn <= x_dimension            | x1..xn (box width)
a1*x1+...+an*xn <= y_dimension      | a1..an (aspect ratio)

of course there are multiple solution to this problem so what you then need to do is to find out which is the best. So you need to find:

min(x_remainder*y_remainder)

whereas

(x1+...+xn) - x_dimension = x_remainder
(a1*x1+...+an*xn) - y_dimension  = y_remainder

I'm not even sure if I'm on the right path with this approach, so I would also be grateful, if someone could provide me with some food for thought.

As mentioned in the comments, the problem is called the (2-dimensional) packing problem. Your problem (Rectangle packing) is NP-complete. It can be shown with a reduction from the Bin Packing problem. See for example this paper Richard E. Korf: Optimal Rectangle Packing: Initial Results. Here's a link that describes an algorithm (the same basic idea as in the paper) in quite a bit of detail. In addition, the paper mentions the problem can be modeled as a constraint satisfaction problem (CSP), so you might be interested in using a CSP-solver if you need to solve the problem in practice. One such solver I have used is MINION.


The complexity of the permanent of low rank matrices I know that for an arbitrary $n \times n$ matrix, Ryser's algorithm can compute the permanent in $\mathcal{O}(2^n n^2)$ time. I'm interested in computing the permanent of $n \times n$ matrices of rank $m$. A few sources told me that this algorithm is exponential in $m$. The algorithm must also depend on $n$, so what is the $\mathcal{O}$-notation for this? $\mathcal{O}(2^m n^2)$? $\mathcal{O}(n^m)$?

The paper "Two algorithmic results for the traveling salesman problem" by Barvinok describes an $n^{\mathcal{O}(m)}$ algorithm for computing the permanent of a rank-m matrix. I don't know whether this can be improved to $\mathrm{poly}(n) 2^{\mathcal{O}(m)}$.

(I originally posted this as a comment. I post it as an answer by lack of any other answers.)


Parallel programming languages which look deterministic? Are there any programming languages where the system parallelizes the program without any noticeable differences for the programmer?

That is, the programmer writes a linear, deterministic program, without any additional tags or meta-data, and the underlying system parallelizes all of the work.

I'm not sure about the "without any additional tags or meta-data" part, but I know that recent versions of Matlab make it pretty easy to parallelize your code by simply adding the "par" keyword to your for loops (see the Matlab help for more info).

This is as close to having no "noticeable differences for the programmer" that I'm aware of.


Is approximating Exact Set Cover NP-hard for constant approximation factor? ETH hard? It is known that Exact Set Cover is an NP-hard problem (Reduction from 3-SAT and 3-Coloring). Also, my minor analysis one can realize that this problem is also ETH-hard, i.e. this cannot be solved in less than $2^{\epsilon n}$ time, unless the Exponential Time Hypothesis(ETH) is false. I want to know whether something can be said about the approximation of Exact Set Cover.

For concreteness, I will define the approximate version of the problem below.

Let $\mathcal{U}$ be the universe and $\mathcal{S}$ be the collection of subsets. Then, an instance of Exact set-cover($\mathcal{U}$,$\mathcal{S}$,$d$) is a yes instance, if there is a collection $\mathcal{S'} \subseteq \mathcal{S}$ with $|\mathcal{S'}| \leq \eta d \quad (\eta <1)$ that exactly covers $\mathcal{U}$ (that is each element of the universe appears in exactly one set in $\mathcal{S'}$). The input instance is a no-instance if there are no exact covers, or all exact covers need more than $d$ subsets. Here $\eta$ (or rather $1/\eta$) is the approximation factor.

Yes, because you made the approximation irrelevant.  Reduce from k-SAT:

Each variable contributes one element to $\mathcal{U}$ and each clause

contributes k+1 elements to $\mathcal{U}$, one for each literal and one more.

Each literal contributes one set to $\mathcal{S}$  -  The elements are [[the element of $\mathcal{U}$ from

the literal's variable] and [the [elements from the clauses] which are [for that literal]]].

Each clause contributes  2k-1  sets to $\mathcal{S}$    -    One for each non-full subset of the set of literals,

but the other element from the clause must be in each of those  2k-1  elements of $\mathcal{S}$.

For a subset of $\mathcal{S}$ to be pairwise disjoint, it cannot have sets from opposite literals and

cannot have more than one set from any given clause.  For a subset of $\mathcal{S}$ to cover $\mathcal{U}$,

it must have at least one set from each variable and at least one set from each clause.

Thus exact covers must have exactly one set from each variable and from each clause.

Each element of $\mathcal{S}$ is from

[[no clauses and exactly one variable] or [no variables and exactly one clause]],

so all exact covers have exactly    number of variables  +  number of clauses    elements of $\mathcal{S}$.

For any assignment which does not satisfy the k-SAT formula, the subset of $\mathcal{S}$ induced by that assignment is disjoint from at least one clause's set of k+1 elements of $\mathcal{U}$, no other clauses' sets intersect any of those sets of k+1 elements of $\mathcal{U}$, and no single element of $\mathcal{S}$ covers all of those k+1 elements of $\mathcal{U}$.  Thus non-satisfying assignments have zero extensions to exact covers.

For any assignment which does satisfy the k-SAT formula, each clause has exactly one element

of $\mathcal{S}$ from the set of that clause's literals which are false, one can trivially find the set of those elements of $\mathcal{S}$, and using that set to extend [the subset of $\mathcal{S}$ induced by the assignment]

gives an exact cover.  Since elements of $\mathcal{S}$ from clauses do not have any elements of $\mathcal{U}$

from other clauses, satisfying assignments have no other extensions to exact covers.

Therefore your problem is ETH-hard under strongly parsimonious reductions.


Efficient update of reachable set of a node in a digraph Given a digraph $G = (V, E)$ and a set of vertices $S$, which does not change over the whole process, the goal is to compute the set of vertices, $R_{reach}$, reachable from $S$ and the set of nodes , $R_{ret}$, from which I can return to $S$.

The issue I have now, is that I need to add and remove edges. I can keep track of the changes in the graph. Note that these changes to the graph only happen locally, i.e. within a given range/distance around a vertex I know.

I have successfully been localizing the update of $R_{reach}$ and $R_{ret}$ for the edges I add to the graph. However, when I remove an edge from the graph one issue arises, that this edge might cut off a subgraph in term of reachability/returnability. I am not sure if it is possible to keep the update of $R_{reach}$ and $R_{ret}$ still local around the known vertex and the given update distance or if it is faster to simply recompute $R_{reach}$ and $R_{ret}$ for the whole graph again using BFS.

You can check the Dynamic Transitive Closure Problem of a Digraph. The transitive closure (or reachability) problem in a digraph $G=(V,E)$ consists in finding
whether there is a directed path between any two vertices in $G=(V,E)$. The general idea
is to maintain some kind of structure in order to quickly respond to queries of the form:

is there a path connecting u and v? Now add/delete an edge $e \in E$: is there a path connecting u and v?

Some algorithms respond in $O(1)$ time but need $O(n^2)$ space. Some respond yes/no and some also give you an actual path though I do not remember the exact complexity to get the path.

For your case you have to check all nodes of $S$ against all other nodes $V-S$.

The easiest way to do it is to run BFS every time for every node in $S$. It depends on the application.

Take a look in the bibliography below:

D. Yellin, Speeding up dynamic transitive closure, Acta Informatica 30 (1993), pp.369-384.
[I86] G. Italiano, Amortized Efficiency of a Path Retrieval Data Structure, Theoretical Computer Science, 48 (1986), pp. 273-281.
[I88] G. Italiano, Finding Paths and Deleting Edges in Directed Acyclic Graphs, Information Processing Letters, 28 (1988), pp. 5-11.

Hope this helps!


Reference: Cancellability of the Dyck congruence I consider the Dyck congruence $\equiv$ on a parenthesis alphabet $\Sigma = \{a, \bar a, b, \bar b\}$, i.e. the least congruence on $\Sigma^*$ such that $a \bar a \equiv \varepsilon $ and $b \bar b \equiv \varepsilon$.

It appears that $\equiv$ can be cancelled, i.e. for every $v$, $w_1$, $w_2 \in \Sigma^*$, if $vw_1 \equiv vw_2$, then $w_1 \equiv w_2$ (and analogously for cancellation from the right).

Does someone know a literature reference for this property?  I wasn't able to find anything along those lines.

Your assertion is wrong, the congruence $\equiv$ is not cancellable from the right: for instance $\bar a a \bar a \equiv \bar a$, but $\bar a a \not\equiv 1$.

By the way the quotient $\Sigma^*/{\equiv}$ is not a group, but a monoid, called the polycyclic monoid, first introduced in [1].

[1] M. Nivat and J-F. Perrot, Une généralisation du monoïde bicyclique, Comptes Rendus de l'Academie des Sciences de Paris 271 (1970), 824-827.


Difference between statically and dynamically typed languages When writing a course on computer science where students get an introduction to both Python and OCaml, I was on the verge of saying that Python is dynamically typed and OCaml is statically typed. I imagine that we all agree this is true even if nobody seems to agree on what exactly is a dynamically typed language. I came across several definitions which don't suit me :

Some of them talks about type errors detection at compile time and at run time. As C can be compiled but also interpreted (well, this is very unusual, but it can be), I don't like this definition as it relies much more on the implementation of a language rather than on its semantics.
Some ask that types should be attached to variables and not to values for a type system to be static. For instance, in C one can assign an int to a given variable : int n =1. But one cannot assign a double to this variable later. That would make the C language statically typed (well it is, but for other reasons). I don't like this definition as it seems it would not be too difficult to turn any statically typed language into a dynamic one.
Many other definition which turned out to be wrong

I now believe that static/dynamic typed languages are not correctly defined as most serious books seems to be reluctant to define it. In "Types and programming languages" by B. Pierce, the author seems to imply that a language that can write:

if cond then 1 else "one"

should be dynamically typed. I've also seen the definition: "A statically typed language is a language where expression have types, whereas a dynamically typed language is one where values have a type". I am not quite sure to understand what it means. But my feeling is the following : a static language is a language where we can infer the type of an expression from the types of all its functions and its values. That would be a language where only functions whose output type is known from its input types are allowed. Julia people call it "type stable functions".

So my question is the following: Are statically typed languages, those who only allow "type stable functions"?

The question is subtle and simple at the same time, hence deep. Let me give you
a simplifying answer.

First you need to realise there there three somewhat orthogonal distinctions which are often mixed up, leading to confusion:

Typed vs untyped languages
Type-checking vs type-inference
Static vs dynamic typing

Types are simply an algorithmic technique to define and decide
language subsets (think: if a program is typable, it's in the
subset). Typically subset decided by types are somehow well-behaved, and we consider programs not in the subset to be somehow bad
or in error, think programs like "hello" * 17 are rejected).
The essence of this algorithmic technique is that you have a second language (that of types) which gives a second version on the program in question. Typically the language of types is  simpler than the ambient programming language.

Type-checking vs type-inference is about a detail of this algorithmic technique: in
type-checking a program is compared against user-specified types: are
the two in 'harmony', while in type-inference the internal consistency
of a program with itself is checked. In practise no programming
language is fully type-checked, instead at least some parts of programs are
 inferred, e.g. you don't have  to write

((3 : int) (+ : (int, int) -> int) (4 : int)) : int

or some monstrosity like this, instead,
you can get away with

3 + 4

even in Java.

Finally statically vs dynamically typed is about when programs are
accepted or rejected.  With dynamic typing that happens during
execution. With static typing, there is a distinct phase (sometime called semantic analysis) before
execution, typically during compilation. If the program fails semantic analysis, compilation or interpretation is abandoned, hence no execution.


Compatible partial permutations Please, correct my terminology as I am not a combinatorician
(I am using http://en.wikipedia.org/wiki/Partial_permutation). Please, refer me to the solution if this is a solved problem.

Let $P_k$ be partial permutations of the set $\{1, 2, \ldots, n\}$, e.g. $n=5$, $P_1=(1,\cdot,3,2,\cdot)$, and $P_2=(\cdot,2,3,1,5)$. Let $T_k$ be permutations from the same set, e.g. $T_1=(1,3,4,2,5)$.  I will write $P_1[4]=2$, $P_2[4]=1$, and $T_1[4]=2$.  I will say, that $P_1[2]$, $P_1[5]$, and $P_2[1]$ do not exist.

Let define that a given partial permutation $P$ is included in the given permutation $T$ if for all $i,j$ for which $P[i]$ and $P[j]$ exist: if $P[i] < P[j]$ then $T[i] < T[j]$. For example, the given $P_1$ and $P_2$ are both included in the given $T_1$.

Let define that two given partial permutations are compatible if there exists a permutation such that both partial permutations are included in it. For example, the given $P_1$ and $P_2$ are compatible, because they are both included in $T_1$.

QUESTION: Propose an algorithm to check if two given partial permutations are compatible. Please propose also the proper data structure for representing partial orders which will allow your (efficient) algorithm.

(I am tagging this question with BDD because the solution may help me to represent BDDs with different variable ordering more concisely)

We can reduce it to the following problem:

  Given a directed graph on vertex set $\{1,2,\dots,n\}$, we want to know if there exists a permutation $T$ such that for each edge $(i,j)$ in the graph, $T[i]<T[j]$.

The reduction: add an edge to the graph for each pair $i,j$ where both $P_b[i]$ and $P_b[j]$ exist for some $b \in \{0,1\}$; the orientation of the edge is determined by whether $P_b[i]<P_b[j]$ or not.  This yields a directed graph that contains the union of edges from $P_0$ plus edges from $P_1$.

Conveniently, the new problem is easy.  Of course, if there are any cycles in the graph, then there is no such permutation $T$ (i.e., the two permutations $P_0,P_1$ are not compatible).  Conversely, if there are no cycles in the graph, then there is such a permutation $T$ (i.e., the permutations $P_0,P_1$ are compatible).  Do you see why?  We can simply apply a topological sort to the graph and use it to construct an example of such a permutation $T$, where we assign $T[i]=j$ if vertex $i$ is the $j$th vertex to be visited in the topologically sorted order.

I'm not sure what BDDs have to do with it.  This does not seem like a research-level question.


Poly-time approximation scheme for problems with pseudo-polynomial time algorithms The question is: Does a poly-time approximation scheme always exist for NP-complete problems that have pseudo-polynomial time algorithms (like knapsack for example)?

The short answer is NO. Petra Schuurman and Gerhard Woeginger have written about this in their tutorial. See Example 0.6.3 on p.46 in their paper when there's no FPTAS while problem has pseudopolynomial algorithm. What concerns an example when there's no PTAS while problem has pseudopolynomial algorithm I suggest Binary Paint Shop Problem (discussed also here, definition can be found in the first answer).

Also there is good picture in tutorial on p.5 on relations between approximation classes and Pseudo-Polynomial Time.


weighted directed Walk in a graph I have a problem in graph theory and search the name and the complexity of the following problem :

Let $G = (V,A)$ be a directed graph, $p : A \rightarrow \mathbb{N}$ be a weight on the arcs of $G$ and $k_1, k_2\in \mathbb{N}$.

Is there a walk $w$ of $G$ of length $k_1$ ($w = (v_{i_1} \ldots v_{i_{k_1}})$) such that $\sum_{j = 1}^{n-1}p((v_{i_j},v_{i_{j+1}})) \leq k_2$ ?

Can you help to find the name and the complexity of this problem ?
Anybody has ever read something on this?

This problem is PP-hard under Turing reductions when your weights are encoded in binary. The lower bound follows by a reduction from the $K$-th largest subset problem. Given a set $S\subseteq \{ s_1,\ldots,s_n \}\subseteq \mathbb{N}$ and $B, K\in \mathbb{N}$, this problem asks whether
\begin{align*}
\# \{ S'\subseteq S : \sum_{s\in S'} s \le B \} \ge K.
\end{align*}
It has recently been shown that this problem is PP-complete under polynomial-time Turing reductions. It's easily seen how to encode this problem into yours (and see Proposition 4 in here in case you need some inspiration).

If $k_1$ is given in unary then your problem is PP-complete. If $k_1$ is given in binary then your problem is in PEXP, I cannot say if it is PEXP-complete.

In general, you often see this kind of problems in the setting of quantitative verification of (stochastic) systems.


Algorithms to classify the geometrical relationship of two 3D-geometries I have multiple 3D volumes which are represented by their boundaries (set of polygons each represented as a list of 3D-coordinates). I am now looking for algorithms to decide if

volume A is inside volume A
volume B is disjoint of volume B

Also I am interested in the dimension of the intersection of A and B if they aren't disjoint.

Specific ideas for algorithms would be just as helpful as references to useful books or papers.

I'm assuming you mean

volume A is inside volume B
volume A is disjoint of volume B

Then it's really simple. Pick the volume you expect to be a superset, or $A$. Each polygon defines a plane. Use these points to solve for $ax+by+cz+d=0$, for every polygon of $A$.
Then it would help if you had a point that you know is inside a volume.
find the closest polygon to your inner point, and check whether that point is greater or less than the plane. let that number be $k_{P_n}$ (either 1 or -1).
take a polygon that is next to your initial polygon. find the folding edge of the two.
take a point of the new polygon that is not on the folding edge ($l$).
extend a point from the folding edge orthogonal to the initial plane above the initial plane ($a$). second point on the initial plane, but outside of the line of intersection ($c$). (above with respect to your k of the initial plane)
if $l$ is on the initial plane, then adjust your new k so that $a$ is above the new plane.
if $l$ is above (with respect to the the initial k) the initial plane, then adjust your new k so that $c$ is below the new plane.
if $l$ is below (with respect to the the initial k) the initial plane, then adjust your new k so that $c$ is above the new plane.
keep doing that until you have your complete shell mapped for k. if you have more than one shell (like a hollow object) you need to track all unmapped polygons and do the same thing for them.
then you can compare your volumes.
take any point from B, and find the closest polygon from A, and check whether your B point is above the plane of the A polygon. do this for every point in B.
you also need to check whether any A point is in B, for the special case in which a sharp spike from one volume penetrates the other.
If all points of $B$ are inside $A$, and no points of $A$ are inside $B$, then $B$ is inside $A$
If some but not all points of $B$ are inside $A$, then $A$ and $B$ intersect.
If no points of $B$ are inside $A$, and no points of $A$ are inside $B$, then $A$ and $B$ are disjoint.
Further reading:
Look at computing volume of convex polytopes. Alternatively to the above, you can look at the union volume to draw your conclusions. if $V_U=V_A$, then $A\subset B$. if $V_U<V_A \wedge V_U<V_B \wedge V_U \neq 0 $ then $A$ intersects $B$. If $A_U=0$ then they don't intersect.


Robustness to non-uniform randomness vs. one-sidedness Consider any problem where, fixing two (disjoint) subsets $\mathcal{Y},\mathcal{N}\subseteq \{0,1\}^n$ of the input space, the goal is to obtain a randomized algorithm $D$ which, given a uniformly random bit string $r$, and on input $x\in \{0,1\}^n$, with probability at least $2/3$ over $r$,

outputs $\mathsf{yes}$ if $x\in\mathcal{Y}$;
outputs $\mathsf{no}$ if $x\in\mathcal{N}$.

Call any such $D$ a decider for $(\mathcal{Y},\mathcal{N})$.

(A natural example is property testing.) If further the first item (completeness) holds with probability one, then $D$ is one-sided.

Clearly, if $D$ is one-sided, then (1) holds even if $r$ comes from an arbitrary distribution, possibly chosen adversarially, instead of being uniform.

Let us say a decider for $(\mathcal{Y},\mathcal{N})$ is robust to bad coins if completeness (first item) degrades gracefully as the distribution $R$ of $r$ gets far from uniform. For instance, the probability that completeness holds only goes down linearly, as $2/3-c\operatorname{d_{TV}}(R,U)$ for some $c\in[0,1)$ .

My question is then:

  Is the class of one-sided deciders a strict subset of deciders robust to bad coins? And has this been studied in some form?

(Also, the definition of robustness is quite open.. I went with total variation, but maybe something like min-entropy of $R$ makes more sense?)

Only one-sided deciders are robust to bad coins, under your definition; no other decider can be robust to bad coins.  Let $D$ be a decider that is not one-sided.  For $x \in \mathcal{Y}$, let $\mathcal{W}_x = \{r \in \{0,1\}^m : D(x,r)=\textsf{no}\}$ be the set of random strings $r$ such that $D$ outputs the wrong answer.  Consider a distribution $R$ that, with probability $1/3+\epsilon$, picks $r$ uniformly at random from $\mathcal{W}_x$, and with probability $2/3-\epsilon$, picks $r$ uniformly at random from its complement.  Then the decider is correct on $x$ with probability $2/3 - \epsilon$ when $r$ is chosen from $R$; yet $d_{TV}(R,U) = \epsilon$.  So, there is no $c \in [0,1)$ with the desired property; you'd need to take $c=1$.

If you relax your definition to allow $c \in [0,1]$, so that (non-one-sided) deciders robust to bad coins exist, then the answer to your question is yes, it is a strict subset.  It is not hard to come up with trivial examples.  For instance, suppose that $D$ is correct for all choices of $r$ except for a single bad value $r_\text{bad}$; if $r=r_\text{bad}$, then $D$ is incorrect.  This decider is robust to bad coins but is not a one-sided decider.

Moreover: with such an adjusted definition, every decider is robust to bad coins. By the definition of total variation distance and the definition of a decider,

$$\Pr_{r \in R}[\mathcal{W}_x] \le \Pr_{r \in U}[\mathcal{W}_x] + d_{TV}(R,U) \le 1/3 + d_{TV}(R,U),$$

so the probability that (1) holds is at least $2/3 - d_{TV}(R,U)$.  Thus, $D$ is robust to bad coins with $c = 1$.

So, I think you need to re-consider your definition of "robust to bad coins".  With your original formulation ($c \in [0,1)$), only one-sided deciders can ever meet it; with an adjusted formulation ($c \in [0,1]$), every decider meets it.  In both cases, it collapses to be equivalent to some other existing notion.  This suggests that we need a different definition.