Topological sorting of a DAG where special vertices have to come in even groups Consider the following problem. The input is a directed acyclic graph (DAG) $G = (V, E)$, and a subset $V' \subseteq V$ of vertices, which we call special vertices. The question is to determine whether $G$ has a topological sort $v_1 < \cdots < v_n$ having the following property: when the sort is enumerating special vertices, then it must always enumerate an even number of them consecutively. In other words, at every step of the sort, we can either take one normal vertex, or take two special vertices one after the other, and we repeat this. Formally, for any contiguous subword $v_i, \ldots, v_{j-1}$ of $v_1, \ldots, v_n$ where all vertices are special, and which is maximal (either $i=1$ or $v_{i-1}$ is not special; and either $j = n-1$ or $v_j$ is not special), then we require that $j-i$ is even.

Is this decision problem NP-hard, or is it in PTIME?

Of course, a necessary condition is that there is an even number of special vertices. But this is not sufficient: the totally ordered graph $w_1 < v_2 < w_3$ with $w_1$ and $w_3$ special is a negative instance, as its only topological sort does not satisfy the condition. In general, the idea is that we can always freely consume non-special vertices, but we must be careful in which special vertices we consume to avoid getting stuck with an odd number of special vertices that block the rest of the graph from being enumerated. Consider for instance a DAG defined by $w_1 < v < w_2$ and $w_3 < w_4$ with the $w_i$ being special and $v$ non-special, then the topological sort $w_1 < w_3 < v < w_2 < w_4$ satisfies the condition, but if we want to start a topological sort by $w_3 < w_4$ then we are "stuck".

[This relates to work on mine about constrained topological sorting. It is listed as an open problem here (search for "Open problem: Is the same true of the CTS problem?"). We have a PTIME algorithm (Proposition 4.6 of the paper) for the much easier problem where $G$ is a disjoint union of chains (total orders), which is a rather intuitive but not entirely trivial greedy algorithm.]

Update (thanks @Louis): The problem presented here is related to another variant of topological sort, which seems unknown but pretty natural, which I'd call "two by two" or "pairwise" topological sorting. This is the problem where you are given a DAG $G = (V, E)$ with an even number of vertices, and you want to decide if there exists a topological sort $v_1 < \cdots < v_n$ where we take vertices two by two (with the second vertex already being available before having taken the first vertex), formally we add the condition that for all $0 \leq k < (n/2)-1$, the vertices $v_{2k+1}$ and $v_{2k+2}$ are incomparable. I do not know the complexity of this problem, either. This problem reduces to the problem asked in my question (make all vertices special, and add a non-special vertex at the middle of every edge), in fact my problem is equivalent to a generalization of this problem.

I also don't know the complexity of the variant where we replace two by some other constant $k$, i.e., my problem where special vertices must be taken in groups of multiples of $k$, or the "$k$ by $k$" topological sorting problem. Any insights about their complexity are also welcome.

The problem you are calling "two-by-two" topological sorting is the Two Processor Scheduling Problem (unit-length jobs, under precedence constraints given by a partial order on the jobs -- i.e., the DAG).  The partial order on the jobs constrains them so that if x<y then job y cannot be started until job x is completed.  Shelling the vertices of the DAG in pairs is like taking two unit-length jobs at a time to schedule on the two identical processors; a schedule with makespan n/2 is possible only if the DAG can be shelled in incomparable pairs, as required in your problem.

It is solvable in linear time, i.e., O(n+m) where n, m are number of, respectively, vertices and edges of the DAG. (Gabow, Gabow and Tarjan).  Earlier work by Coffman and Graham is a simpler but asymptotically not quite as fast algorithm; and Fujii, Kasami and Ninomiya also provide a poly-time algorithm. The Gabow and Tarjan algorithm has the advantage that you don't have to find the transitive reduction or transitive closure of the DAG first -- you can use it directly on the DAG.

I don't know the status of your original problem, though, where the distinguished vertices must be scheduled in blocks of even size.


Proof Haar matrices satisfy JL lemma The Johnson-Lindenstrauss lemma says roughly that for any collection $S$ of $n$ points in $\mathbb{R}^d$, there exists a linear map $f:\mathbb{R}^d \rightarrow \mathbb{R}^k$ where $k = O(\log n/\epsilon^2)$ such that for all $x, y \in S$:
$$(1-\epsilon)\|x-y\|_2 \leq \|f(x)-f(y)\|_2 \leq (1+\epsilon)\|x-y\|_2$$

I've been trying to prove that the inequality above is satisfied if $f$ is picked using
the Haar Transform as follows. Let D be a random $n\times n$ diagonal matrix with each diagonal element drawn uniformly and independently from $\{-1, 1\}$ (i.e. diagonal entries of $D$ are Rademacher random variables). Let $H$ be the standard $n\times n$ Haar matrix. Let finally $M$ be a random $k \times n$ binary matrix, such that each row $i$ has a single entry $M_{ij}$ equal to $1$ for $j$ picked uniformly at random from $\{1, \ldots, n\}$, and $M_{ij} = 0$ for all other $j$. In other words, $MH$ is equal to a random $k\times n$ matrix each of whose rows is a uniformly random row of $H$. Then the transform is defined as

$$
f(y) = MHDx
$$

When $f$ is picked as above, what is the probability that it satisfies the Johnson-Lindenstrauss condition for a fixed pair $x,y$ (when $f$ is given by a an appropriately scaled Gaussian matrix, the probability is $1 - \frac{1}{n^2}$)?

Your construction does not work in general for the value of $k$ given.

Say $x = 0$ and $y= (1, 0, \ldots, 0)$ (or any other standard basis vector). Then $f(x) = 0$ and $HDy$ is a vector with $1 + \log_2 d$ nonzero entries. We have

$$
Pr[f(y) = 0] = \left(1 - \frac{1 + \log_2 d}{d}\right)^k \approx 1-O\left(\frac{k\log d}{d}\right),
$$
for $k \ll d$. Of course, in this case $\|f(y) - f(x)\|_2 = 0$ is a very bad approximation for $\|x - y\|_2 = 1$. So you almost certainly get infinite error.

This is why the Fast J-L Transform of Ailon and Chazelle uses a Walsh matrix rather than a Haar matrix: $WDx$, for $D$ picked as in your setup, is likely to have a lot of non-zero entries. This is related to the Uncertainty Principle. See also this CACM exposition.

More generally, Krahmer and Ward showed that if $M$ is a (possibly random) matrix that satisfies the restricted isometry property for submatrices of size at most $k$ (with sufficiently high probability), and $D$ is picked as above, then $f(x) = MDx$ satisfies the J-L condition for any $x, y$ with probability at least $1 - 2^{-\Omega(k)}$. This is in some sense a tight connection: a random matrix that satisfies the J-L condition for any $x, y$ with probability $1 - 2^{\Omega(k \log (n/k))}$, also satisfies the RIP property for submatrices of size up to $k$.

For more on this subject check out the lecture notes from Jelani Nelson's course. In particular, lecture 17 contains the Krahmer-Ward theorem. Lectures 9-12 introduce the JL lemma with the sparse and fast variants.


Precise definition of syntatic categories / syntatic domains in abstract syntax I have read the introductory parts of a couple of books on programming language semantics (Gordon, Winskel, Nielson & Nielson, Allison, Stump, Schmidt), and while I do understand what they mean by syntactic categories, or syntactic domains, I didn't find a rigorous and straightforward definition of those. Is there a standard definition, maybe in earlier works?

Most people avoid giving precise descriptions of what a syntactic category is, because if you do it properly with all the details, the ratio of insight to necessary mathematical sophistication ends up being very, very low. John Reynolds' book Theories of Programming Languages has one of the more comprehensive explanations in its chapter 1, as does Robert Harper's Practical Foundations of Programming Languages.

The intuition you should have is that a syntactic category is the set of trees generated by a context free grammar. Given such a definition for a set of trees, you can define functions on this set using structural recursion, and prove properties about them using structural induction: i.e., by case-analyzing all the different ways that a tree could be constructed.

For example, suppose that we have a language of arithmetic operations given by the following grammar:

e ::= zero | succ(e)| add(e, e)

Then, we can define an interpretation function eval which takes a term and gives you an integer, by cases on the ways we can construct a term:

eval : Expr -> Int
eval zero     = 0
eval succ(e)  = 1 + eval e
eval add(e, e') = eval e + eval e'*

Note that we have completely defined this function by giving one clause for each possible way we could have generated an expression from the grammar. The fact that this is a complete definition of a function is called the principle of structural recursion.

We can also prove properties about this function by using structural induction -- by doing an inductive analysis for each case. For example, we can prove that for every e, eval e ≥ 0.

Proof. By structural induction on e.
- Case e = zero:
  By the definition of eval, eval zero = 0.
  We know 0 ≥ 0 by reflexivity of ≥.

- Case e = succ(e'):
  By induction, we know that eval e' ≥ 0
  So we also know that 1 + eval e' ≥ eval e'.
  By transitivity, 1 + eval e' ≥ 0.
  But eval succ(e') = 1 + eval e'.
  So eval succ(e') ≥ 0.

- Case e = add(e', e'').
  By induction, we know that eval e' ≥ 0.
  By induction, we know that eval e'' ≥ 0.
  By properties of addition, we know that eval e' + eval e'' ≥ 0.
  By the definition of eval, eval add(e',e'') = eval e' + eval e''.
  So eval add(e',e'') ≥ 0.

The fact that considering just the cases for how expressions could be formed constitutes a proof is called the principle of structural induction.

Now, it's a fact that one can define functions by structural recursion and prove properties by structural induction for any grammar. However, proving this rigorously requires a certain amount of category theory; you need to formalize syntactic categories as initial algebras of a certain class of functors, and then prove that such initial algebras always exist for that class.

This is really heavyweight tooling for proving such an "obvious" result, and so I recommend just trusting your intuition about how structural definitions work, and then only bothering with their detailed semantics if you decide to become a professional logician.


Is optimally solving the n×n×n Rubik's Cube NP-hard? Consider the obvious $n\times n\times n$ generalization of the Rubik's Cube.  Is it NP-hard to compute the shortest sequence of moves that solves a given scrambled cube, or is there a polynomial-time algorithm?

[Some related results are described in my recent blog post.]

A new paper by Demaine, Demaine, Eisenstat, Lubiw, and Winslow makes partial progress on this question---it gives a polynomial-time algorithm for optimally solving $n \times O(1) \times O(1)$ cubes, and shows $\mathsf{NP}$-hardness for optimally solving what you might call "partially-colored" cubes.
It also shows that the $n \times n \times n$ cube's configuration space has diameter $\Theta(n^2/\log n)$.

Sweet!

One possible next question that their work seems to suggest: is there a fixed family of partially-colored $n \times n \times n$ cubes, one for each value of $n$, such that optimally solving from a given configuration is $\mathsf{NP}$-hard?


Graph layout algorithm I have an undirected graph on matris by vertex adjacency relations like that;

/*    a  b  c  d
 * a -1  0  1  1
 * b  0 -1  1  1
 * c  1  1 -1  1
 * d  1  1  1 -1
 *
 */

I want to draw this graph on cordinate system. What's the algorithm that gives each vertex position (x,y) by any method(force-directed, spring vs) with no intersection between edges or minimum intersection?
Thanks.

This question may not have been phrased to make it look research-level, but trying to compute the minimum number of crossings in a layout of a given graph is definitely a research-level problem.

One complication is that there is more than one definition of the number of crossings: see Pach, "Which crossing number is it, anyway?", FOCS 1998.

If you allow a drawing with curved edges, and count the number of intersection points of edges, then the problem is fixed-parameter tractable: it can be solved in time linear in the number of vertices in the graph, but exponential or worse in the number of crossings. See Kawarabayashi and Reed, "Computing crossing number in linear time", STOC 2007, as well as several previous related papers cited by them.

I don't think the Kawarabayashi-Reed algorithm is practical, but if you restrict attention to drawings with straight line segment edges (giving a different crossing number) there are more practical (though still exponential) approaches based on integer programming. See e.g. Jünger et al, "A polyhedral approach to the multi-layer crossing minimization problem", Graph Drawing 1997, and Buchheim et al, "A branch-and-cut approach to the crossingnumber problem", Discrete Optimization 2008.

If you want to test if there are no crossings at all (i.e. is the graph planar), then theoretically it has been known for decades that it can be solved in linear time, so this is no longer research-level. But finding a linear time algorithm that is also easy to implement and run in practice is not entirely a solved problem.


What is the minimal extension of FO that captures the class of regular languages? Context: relations between logic and automata

Büchi's Theorem states that Monadic Second Order logic over strings (MSO) captures the class of regular languages. The proof actually shows that existential MSO ($\exists\text{MSO}$ or EMSO) over strings is enough to capture regular languages. This might be a bit surprising, since, over general structures, MSO is strictly more expressive than $\exists\text{MSO}$.

My (original) question: a minimal logic for regular languages?

  Is there a logic which, over general structures, is strictly less expressive than $\exists\text{MSO}$, but that still captures the class of regular languages when considered over strings?

In particular, I'd like to know what fragment of the regular languages is captured by FO over strings when extended with a least-fixed point operator (FO+LFP). It seems like a natural candidate for what I'm looking for (if it is not $\exists\text{MSO}$).

A first answer

As per @makoto-kanazawa's answer, both FO(LFP) and FO(TC) capture more than regular languages, where TC is an operator of transitive closure of binary relations. It remains to be seen whether TC can be replaced by another operator or set of operators in such a way that the extension captures exactly the class of regular languages, and no others.

First-order logic alone, as we know, is not enough, since it captures star-free languages, a proper subclass of the regular languages. As a classical example, the language Parity$\;\;=(aa)^*$ cannot be expressed using a FO sentence.

Updated question

Here is a new wording of my question, which remains unanswered.

  What is the minimal extension of first-order logic such that FO + this extension, when taken over strings, captures exactly the class of regular languages?

Here, an extension is minimal if it is the least expressive (when taken over general structures) among all extensions that capture the class of regular languages (when taken over strings).

FO(LFP) captures PTIME on ordered structures, and strings are ordered structures.  So the languages definable by FO(LFP) include all regular languages and much much more.
http://dx.doi.org/10.1016/S0019-9958(86)80029-8

Ebbinghaus and Flum's textbook contains an exercise that asks to show FO(TC^1) (first-order logic extended with transitive closures of binary relations) is equivalent to MSO on strings. In the same exercise, $\{ a^n b^n \mid n \geq 1 \}$ is used as an example to show FO(TC^2) is more expressive than MSO on strings.  All FO(TC) formulas are clearly equivalent to FO(LFP) formulas.


Number of k-expressions of graph (clique Width) The clique-width of a graph $G$ is the minimum number of labels needed to construct G by means of the following 4 operations.
The Construction of a graph $G$ using the four operations is represented by an algebraic expression called $k$-$expression$, Where
$k$ is the number of labels used in expression.
For example, $K_4$(complete graph with four vertices) can be constructed by
$$\rho_{2\rightarrow 1}(\eta_{1,2}(\rho_{2\rightarrow 1}(\eta_{1,2}(\rho_{2\rightarrow 1}(\eta_{1,2}(a(1)\oplus b(2)))\oplus c(2))) \oplus d(2))).$$

Question--> How many k-expressions for bounded clique width graph?
Any particular graph classes known for this question?

Cographs have clique width 2, and the number of cographs of size $n$ is asymptotically equal to $3.56^n$.

See https://mathoverflow.net/questions/37875/bound-on-the-number-of-unlabeled-cographs-on-n-vertices.

I am not sure how many graphs with a given clique-width $k$ exist.


Consequences of UP equals NP EDIT at 2011/02/08:
After some references finding and reading, I decided to separate the original question into two separate ones. Here's the part concerning UP vs NP, for the syntactic and semantic classes part please see Benefits for syntactic and semantic classes.

$\mathsf{UP}$ (the unambiguous polynomial time, see wiki and the zoo for references) is defined as languages decided by $\mathsf{NP}$-machines with an additional constrain that

There is at most one accepting computation path on any input.

The precise relations between $\mathsf{P}$ vs $\mathsf{UP}$ and $\mathsf{UP}$ vs $\mathsf{NP}$ are still open. We know that worst-case one-way functions exist if and only if $\mathsf{P} \neq \mathsf{UP}$, and there are oracles relative to all possibilities of the inclusions $\mathsf{P} \subseteq \mathsf{UP} \subseteq \mathsf{NP}$.

I'm interested in why $\mathsf{UP}$ vs $\mathsf{NP}$ is an important question. People tend to believe (at least in literature) that these two classes are different, and my problem is:

  If $\mathsf{UP} = \mathsf{NP}$, are there any "bad" consequences happened?

There is a related post on complexity blog in 2003. And if my understanding is correct, the result by Hemaspaandra, Naik, Ogiwara and Selman shows that if

There is an $\mathsf{NP}$ language $L$ such that for each satisfiable formula $\phi$ there is a unique satisfying assignment $x$ with $(\phi,x)$ in $L$,

then the polynomial hierarchy collapses to the second level. No such implication is known if $\mathsf{UP} = \mathsf{NP}$ holds.

It is known that $\mathsf{UP= NP}$ implies $\mathsf{SpanP = \#P}$ since Kobler, Schoning, and Toran proved that $\mathsf{UP= NP}$ if and only if $\mathsf{SpanP = \#P}$. It is easy to see that $\mathsf {\#P}$ is contained in $\mathsf {SpanP}$.

A function $f : Σ^* →\mathbb N$ is in $\mathsf{SpanP}$ if there is an $\mathsf {NP}$ Turing machine transducer $M$ such that for all $x$, $f(x)$ is the number of distinct outputs of $M$ on input $x$.

J. Kobler, U. Schoning, and J. Toran. On counting and approximation, Acta Informatica,
26:363-379, 1989.


Is it possible to prove stronger bounds for the deterministic communication complexity compared to nondeterministic communication complexity? Inspired by the questions Nondeterministic communication complexity of set disjointness?, I was wondering about the following:

  Is there an example of a function $f$ where the nondeterministic communication complexity $N(f)$ is asymptotically smaller than the deterministic communication complexity $D(f)$.

When $f$ is the Equality problem or the Set Disjointness problem, we seem to have $D(f) = N(f)$ and, as far as I can tell, the common techniques for showing lower bounds for deterministic protocols (fooling sets and the rank method) work just as well for nondeterministic protocols.

  Are there any known techniques that yield stronger lower bounds for deterministic protocols compared to nondeterministic protocols?

It seems to me that there is some incoherency in the question. What do you mean by better?
Are you looking for a function where $N(f) \ll D(f)$ or a function where $D(f) \ll N(f)$?

Deterministic protocols are a special case of nondeterministic protocols, so we always have $N(f) \leq D(f)$.

For examples of functions where $N(f) \ll D(f)$ have a look at the Nisan and Kushilevitz's book.


Graphs whose maximal clique intersection graph has bounded chromatic number In general,
The chromatic number of the clique intersection graph a graph can again be arbitrarily high.
For example, take $n$ maximal cliques of size $n$ such that every pair of maximal cliques has a vertex in common.

So, for which non-trivial graphs the clique intersection graphs has bounded chromatic number even if the graph can have arbitrarily high chromatic number?

Any reference to surveys in this area is welcome.
I welcome any reference relating the graphs with bounded degree and to the chromatic number of its clique intersection graph.
Let the independent neighborhood of a vertex $v$ in a graph is the maximum independent set with every vertex having a common neighbor as $v$.
Let for a graph family $F$, we have a constant $C(F)$, such that for any graph in the family $F$, the size of independent neighborhood of a vertex $v$ in the graph is bounded by $C(F)$. Are there any studies which relate the chromatic number of the clique intersection graph family of $F$ with the above notion.

Edit:

In the clique intersection graph $C(G)$ of a graph $G$, the nodes are maximal cliques of $G$ and there is an edge whenever they share a vertex.

Note: This is different from the definition of clique-separator graph for chordal graphs (Which is a tree).

For (2), any maximal clique $C$ of $G$ has size at most $\Delta+1$ and each vertex $v \in C$ participates in at most $2^{|N(v)|} \leq 2^\Delta$ maximal cliques. So the degree of $C$ in the clique intersection graph is at most $|C| \cdot 2^{|N(v)|} \leq (\Delta + 1) \cdot 2^\Delta$. Thus the clique intersection graph can be $(\Delta + 1) \cdot 2^\Delta+1$ colored.

The bound can be tightened to  $(\Delta + 1) \cdot 3^{\Delta/3}+1$ by using the Moon Moser bound for the number of maximal cliques.


Simplest Machine Model for a langauge $ L = \{(w\# )^{k}\;|\; w\in \Sigma^{*},\;k\in \mathbb{N}\}$ What is the simplest machine model accepting the following language?

$$ L = \{(w\# )^{k}\;|\; w\in \Sigma^{*},\;k\in \mathbb{N}\}$$

In other words, $L$ is obtained by taking each string $w$ in $\Sigma^*$,
and then creating the strings $w\#\;,\; w\#w\#\;,\; w\#w\#w\#\;,...$

Here $\#$ is a separator symbol which is not in $\Sigma$.

The simplest I could think of was queue automata with $2$-queues. But these are already Turing complete. Is there some well studied class of machines that is not Turing complete and accepts $L$?

Just to refine Abuzer's answer, the language can also be recognized by a
Stateless 2-head 1-way DFA which is usually defined in this way [Ibarra et al., On stateless multihead automata: hierarchies and the emptiness problem (2010)]:

For an input string $w \in \Sigma$, machines work on a tape containing $\text{^} w \$$ and
start with all heads on the left end marker. At every step of the computation,
the symbols $a_1,..., a_k$ currently scanned by all $k$ heads are considered, any
corresponding transition $a_1,...,a_k \to d_1,...,d_k \in \delta, a_i \in \Sigma \cup \{\text{^}, \$\}$ is chosen, and each $i$-th heads is moved according to $d_i \in \{ Stay, Right \}$. If no such transition exists, the automaton rejects. If any of the heads falls off the tape, the automaton rejects as well.
If the transition instructs all heads to Stay, the automaton halts and accepts. The string is accepted if there exists a computation resulting in acceptance.

If $\Sigma = \{0,1,\#\}$, then your language is recognized by the following Stateless 2-head 1-way DFA:

   ^   ,  ^   -> S , R
   ^   ,{0,1} -> S , R
   ^   ,  #   -> R , R
   0   ,  0   -> R , R
   1   ,  1   -> R , R
   #   ,  #   -> R , R
{0,1,#},  $   -> S , S


Does Wikipedia assume a solution to the halting problem in their description of universal one way functions? (As for the question in the title: the answer must be no, but then I don't understand what is intended.)

The Wikipedia page on one way functions states:

  Goldreich gives one construction of a universal one-way function, which is denoted by $f_{univ}$ here.

  $f_{univ} (desc(M), x) := (desc(M), M(x))$,
  where $desc(M)$ is the description of Turing machine $M$, and $x$ is an input string. $M(x)$ is defined as the output of machine $M$ given $x$ as input if the running time is at most quadratic on the length of $x$, and otherwise, $M(x) := x$. This definition of $M(x)$ guarantees $f_{univ}$ can be efficiently computed within polynomial time.

The point of $f_{univ}$ is that whenever there exists one way functions that run in quadratic time, then $f_{univ}$ is a one-way function as well. (And the Goldreich reference proves that whenever one-way functions of any running time exist, they can be used to create one way functions that run in quadratic time, hence obtaining the result that the 'concrete' function $f_{univ}$ is a one way function if and only if one way functions exist at all.)

I am, however, not convinced that the last statement from the quote is obvious.

As I understand it, a computer wanting to compute $M(x)$ needs to do two things:

1) Decide whether or not the running time of machine $M$ given $x$ as input is "at most quadratic on the length of $x$"

2) Either return $x$ or let $M$ run on input $x$ and return the output

Now it is clear that step 2) takes at most quadratic time in the length of $x$ and hence certainly in the length of the total input of $f_{univ}$. What is not clear is that step 1) can be carried out in polynomial time.

To be clear: I can think of an algorithm that tests in polynomial time (even time $|x|^2$) whether or not $M$ runs for at most $|x|^2$ steps on $x$. I can also think up an algorithm that test in polynomial time (even time $1000|x|^2$) whether or not $M$ runs for at most $1000|x|^2$ steps. Etc etc etc. However the term 'quadratic' gives us no information on how big or small the implied constant is.

It seems that whenever I make the definition of $f_{univ}$ concrete as in the example above (so output the output of $M$ on $x$ whenever it can be computed in less than $1000 |x|^2$ steps and otherwise output $x$), there might be a world imaginable where quadratic time one way functions exist but all of them take time longer than 1000 times their input length squared and $f_{univ}$ is not one way at all. The only way I can think of to avoid this is for the computer to somehow decide if $M$ halts on $x$ at all but that is known to be a hard problem.

What am I missing?

UPDATE: I see another way out of this: when the proof that any one-way function $f$ can be transformed into a one way function $g$ that runs in quadratic time does in fact give that $g$ runs in time $< cn^2$ for a very concrete $c$. However here it is crucially important that $c$ does not depend on the unkonwn function $f$. This is not clear from me from the Goldreich notes Wikipedia links to. (The proof is in section 2.4.2.) Any help clarifying this is appreciated!

You don't need to know whether it is quadratic on all $x$, only on the particular $x$ that is given as input. And it's easy to decide whether a machine runs in a given time bound on a fixed input $x$. Just simulate it for that many steps and check whether it stops before the time bound runs out.

Here, "at most quadratic" is a little sloppy. It should be read as meaning "at most $|x|^2$ steps", so that there is a concrete time bound to check against. But one should keep in mind that there is a tradeoff between writing that is perfectly rigorous, and writing that can easily be understood by non-specialists, and Wikipedia generally aims for the latter — see https://en.wikipedia.org/wiki/Wikipedia:Make_technical_articles_understandable and its specific guidance to "explain formulae in English".


NP-hard problems on cographs This question is similar to NP-hard problems on trees:

There is a large number of NP-complete problems that are tractable on cographs. Are there any known problems that remain NP-complete when restricted to cographs?

To be more precise I am interested in examples where the input consists solely of an undirected, unweighted cograph.

Two remarks:

For weighted cographs such a problem is mentioned here - TSP with two travellers
Cographs are the "base class" of clique-width such as trees are the base class for tree-width.

UPDATE

Some further thoughts (I am not quite sure about):
If the input is really just a cograph, the question has to be of the sort "Does the cograph have property X?". It would be enough if such a problem existed for trees, since then the question could be "Does the cotree of the cograph have property X?".

Perhaps my favorite open problem is of interest: the edge clique-cover problem on cographs. In the edge clique-cover problem, you want to cover the edges of the cograph with a minimal number of cliques. It is unknown if this problem is NP-complete.

To illustrate that the problem is probably hard, let $K_n^m$ be the complete multipartite graph with $m$ partite sets each of size $n$. This is a cograph. There exist $m - 2$ pairwise orthogonal Latin squares of order $n$ if and only if the edge clique-cover of $K_n^m$ is $n^2$. This was shown by Park, Kim and
 Sano. This is a formula for the "cocktail party graph", that is, the case where $n = 2$.


Packing sets to maximize overlap For a set of sets $A$, let $\cup A := \cup_{S \in A} S$.

Consider the following problem:

Input:

a list of $m$ weights $w = (w_1, \ldots, w_m)$,
a list of $n$ distinct subsets $T = (S_1, \ldots, S_n)$ such that $\bigcup_{S\in T} S = [m]$,
an integer $k$.

Let $P$ be a partition of $T$.
We say $P$ is a $k$-good partition when
the size of each part is at most $k$:
$\forall p \in P \ |p| \leq k$.
The cost of $P$ is defined as
the sum of weight of items counted once for each part they appear in, i.e.
$$cost(P) := \sum_{p\in P} \ \sum_{x\in \cup p} w_x $$

Output: a $k$-good partition of $P$ of $T$ minimizing $cost(P)$.

  What is the complexity of this problem?
  Is it NP-hard or is there a polynomial-time algorithm?

Example:
$m = 7$, $w=(2,2,3,4,1,2,2)$,
$n = 3$, $T=(S_1=\{1,2,3\}, S_2=\{3,4,5\}, S_3=\{5,6,7\})$
$k=2$

In this case, since $k<|T|$,
it is obvious that more than one partition is needed.
Moreover,  $S_1$ and $S_2$ should be packed together in the same configuration because of their heavy overlap ($S_1 \cap S_2$ gives the biggest overlap in our example - we pay 3 less cost units). So the optimal $P$ is $\{S_1, S_2\}, \{S_3\}$ with the total cost 12+5=17.

The unweighted version (when the weights of the elements are all 1)
is also very interesting to me.

I believe it's NP-hard, by a reduction from min-balanced cut.  Given a graph $G=(V,E)$ and integer $\ell$, min-balanced cut asks whether there is a cut that is balanced (has $|V|/2$ vertices on each side), and cuts at most $\ell$ edges.  Given $G$ and $\ell$, construct the following instance of your problem.  For each vertex $v$, create a set $S_v$ containing the edges incident to $v$.  Take $k=|V|/2$.  Then the (minimal) $k$-good partitions are partitions of the sets into two equal-size groups, corresponding to the balanced cuts of $G$, and your (unweighted) cost for such a solution equals $|E|$ plus the number of edges cut.  Unless I'm mistaken :-).

EDIT: Similarly you can reduce the following problem to yours: given a graph $G=(V,E)$ and integer $\ell$, color the vertices of $G$ so that each color class has at most $k$ vertices, minimizing the number of edges whose two endpoints have the same color.  (The reduction: make a set $S_v$ for each vertex $v\in V$, containing the pairs $\{v,w\}$ not in $E$.)


Algorithm to find a polyhedral embedding A polyhedral embedding of a graph on a surface is an embedding without edge crossings such that all the faces are bounded by simple cycles, and any two faces share a common vertex, share a common edge, or do not intersect at all.

I need an algorithm that, given a graph, finds a polyhedral embedding if the graph admits it. I have been looking around but haven't found it. I also need to know the time order of the algorithm.

Deciding whether a graph admits a polyhedral embedding is NP-complete (proved here: B. Mohar, Existence of polyhedral embeddings of graphs, Combinatorica 21 (2001), 395–401, http://www.fmf.uni-lj.si/~mohar/Papers/Fw3npc.pdf). I don't expect an efficient algorithm, just something that works.

Note: I should mention that I am only interested in the combinatorial aspect of this problem. An embedding of a graph can be described by specifying the cyclic orderings of the edges incident on any vertex, and a signature for each edge, which is +1 or -1 according to whether the cyclic orderings of the two vertices on this edge are consistent along this edge. A face-walk is a walk in the graph where at all vertices the next edge is the leftmost edge according to the cyclic ordering on the vertex. A polyhedral embedding is an embedding where all the face-walks are simple cycles. The problem is then to find a circular ordering of edges around each edge and a signature for each edge such that all face-walks are simple cycles.

Doesn't this give you what you want?  Because you only care about the combinatorics, your problem is to embed a graph in a surface, I gather a surface of genus zero.

  Bojan Mohar, "Embedding graphs in an arbitrary surface in linear time," STOC 1996 (ACM link).


Remove specific edge from ST (link-cut) tree ST (or link cut) trees are a special kind of trees used for dynamic graph algorithms. They support the following operations in logarithmic time:

CUT(v) Deletes the edge from v to its parent
JOIN(v, w) Where v is a root vertex, assigns parent(v) ← w (makes v a child of w)
FIND_ROOT(v) Returns the root of the tree containing v

My question here is how to delete an arbitrary edge (u, v) from the tree, and what would be its complexity? If it is too complex or unfeasible to do that, can you point me to an algorithm ((pseudo)code) for the fully dynamic unweighted undirected graph connectivity problem. If it is of any help, the degree of every edge is guaranteed to be at most 2 at any point of the algorithm.

I've read quite a few papers on the topic but in almost all of them the authors only give us very high level descriptions of these structures, in the form of theorems.

For any edge $(u,v)$ either $u$ is $v$'s parent or vice versa. So you just call CUT for "deeper" vertex.

UPD: To determine which vertex is deeper you can use Access($v$). If after this operation $u$ is a rightmost node of $v$'s left (path)subtree, then $u$ is $v$'s parent and you can call CUT($v$) (or just $\mbox{left}(v) \gets \mbox{Null}$ because Access($v$) was called before). Else you call CUT($u$).


A sorting algorithm that uses the minimum comparasions possible I'm looking for a sorting algorithm that minimizes comparisons instead of time complexity.
The algorithm shouldn't compare any two elements for which the relation between them can be derived from comparisons previously made. For example, given three elements $A$, $B$, and $C$ such that $A<B<C$, the algorithm shouldn't attempt to compare $A$ to $C$ if it already compared $A$ to $B$ and $B$ to $C$. (Of course, if the algorithm compared $A$ to $B$ and then $A$ to $C$, it would then also need to compare $B$ to $C$. That's okay.)
Since sorting algorithms have been studied for decades, I'm guessing there already exists an algorithm for this.
My use case is allowing a user to sort things by preference by showing two of those things side-by-side.

Using simple methods, it can be shown that any comparison-based algorithm must perform at least $n\log{n}-o(nlogn)$ comparisons. This bound is obtained (up to lower terms) by the binary insertion sort algorithm (see e.g. [1] for a good introduction on the topic). There are also many other algorithms which obtain this bound asymptotically up to a constant factor, e.g quicksort (in expectation) and heapsort.
That said, for practical purposes I suggest you use the sorting algorithm already implemented in your prefered programming language, as it is most likely been highly optimized, and would work faster than if you implement it yourself, unless you have a very specially structured input.
[1] https://epubs.siam.org/doi/pdf/10.1137/1.9781611975482.79


Is $\mathsf{P} = \mathsf{NP}$ relative to a universal predictor? Consider any language $L$. Define $s(L) \in {\lbrace 0, 1 \rbrace}^\omega$ (an infinite sequence of bits) by the recursive formula

$$s(L)_n=\chi_L(s(L)_{<n})$$

Here $\chi_L$ is the characteristic function of $L$ i.e. $\chi_L(w)=1$ for $w \in L$, $\chi_L(w)=0$ for $w \notin L$

A language $U$ is called a "universal (closed) predictor" when

$$\forall L \in \mathsf{P} \, \forall n>>0:s(L)_n=\chi_U(s(L)_{<n})$$

It is easy to see $U \notin \mathsf{P}$ by considering $L = U^c$. However, $U$ can be recursive. To give an example, consider the language decided by the following algorithm $A$. Given input $w$, $A$ runs all possible programs in shortlex order, allowing each to execute for time $t(|w|)$ where $t$ is a function of superpolynomial growth. Once it reaches a program $R$ that outputs $w$ plus one or more bits and doesn't halt, $A$ outputs the first bit $R$ outputted after $w$. It easy easy to see that (under mild conditions on $t$) $A$ always halts and the language it decides is a universal predictor. $A's$ time complexity is approximately $2^nt(n)$

Given $a \in {\lbrace 0, 1 \rbrace}^\omega$, define $s(L, a)$ by

$$s(L, a)_{2n} = \chi_L(s(L, a)_{<2n})$$
$$s(L, a)_{2n + 1} = a_n$$

A language $V$ is called a "universal open predictor" when

$\forall w \in V : |w|$ is even
$\forall L \in \mathsf{P}, a \in {\lbrace 0, 1 \rbrace}^\omega \, \forall n>>0:s(L, a)_{2n}=\chi_V(s(L, a)_{<2n})$

[I am using 0-based indices so $|s_{<2n}| = 2n$]

Again it is easy to see $V \notin \mathsf{P}$ but $V$ can be in $\mathsf{E}$

  Is there $V$ a universal open predictor s.t. $\mathsf{P}^V=\mathsf{NP}^V$?

I'm especially interested in having either a specific example of such $V$ or a proof such $V$ doesn't exist under reasonable assumptions such as $\mathsf{P} \ne \mathsf{NP}$

The question might seem strange, so I'll briefly outline my motivation for it. I'm interested in AIXI-like models of aritifical intelligence. Here $L$ plays the role of the environment, which I assume to be efficiently computable, and $a$ plays the role of the actions of the agent itself. Given a positive answer for my question, it is possible to construct an agent efficiently computable relative to $V$ which optimizes a given efficiently computable utility function $u$ by choosing its future actions s.t. $u$ is maximized assuming the environment behaves according to the prediction of $V$

I am not familiar with the notion of universal predictor, and I did not follow everything you wrote; in particular, I did not follow your sketch of the proof of existence of a universal predictor in E.  But assuming that there exists a universal open predictor that belongs to E, the answer to your question is positive.  And I am afraid that you will probably be disappointed by the reason.

Edit in revision 2: I changed the construction in response to the added restriction in revision 2 of the question, but the general idea is the same: mix a hard language into a universal open predictor in such a way that the definition of universal open predictor does not notice the difference.

Let T = {0|x|11x: x∈{0,1}*}.  Note that every word in T has an even length.  An important property of T is that no word in T is a proper prefix of another word in T.  This implies that if the symmetric difference between two languages V and W is contained in T, then for every infinite sequence s∈{0,1}ω, there is at most one n such that χV(s<2n)≠χW(s<2n), and in particular V is a universal open predictor if and only if W is a universal open predictor.

It is easy to see that there exists an EXPSPACE-complete language which is a subset of T.  Let L be such a language.  Let V be a universal open predictor that belongs to E, and hence also to EXPSPACE.  Define a language W = L ∪ (V∖T).  Because V is a universal open predictor and the symmetric difference between V and W is contained in T, W is also a universal open predictor.  It is easy to see that W is EXPSPACE-complete, and therefore PW = NPW = EXPSPACE.  This concludes that W satisfies the desired property.


Boolean function with specific ОBDD representation I am looking for a class of boolean functions on $n$ variables with the following property:

When represented by read twice palindromic ordered bdd (i.e. the order is 1..n n..1) the size of the OBDD is polynomial in $n$
Read once polynomial size OBDD doesn't exist for the boolean function.

I did some experiments with the CUDD package to no success.

Any ideas how to find an instance of such function?

(There is a chance such functions don't exist but I would not bet much money on this).

Fix $k=\log n$ and define the following function on $n$ bits: take the first $k^2$ bits and view them as $k$ numbers in the range $1..2^k$: $p_1 ... p_k$.  Now take the $p_1$'st bit, $p_2$'nd bit ... $p_k$'th bits of the input and view them as a $k$ bit number $p$.  The output is the value of the $p$'th bit of the input.

A palindromic OBDD of size $exp(k^2)$ can solve it by first reading and remembering  $p_1 ... p_k$, then reading these $k$ bits, on the first pass, and remembering $p$ and then reading the $p$'th bit on the 2nd pass.

Look at a single pass OBDD and let us restrict the function by dictating that $p_1 ... p_k$ will be equal to the last $k$ indices of the input, and thus $p$ is specified by the last $k$ bits of the input.  It is easy to see that $\Omega(n)$ bits need to be remembered about the first $n-k^2-k$ non-restricted bits of the input in order for the value of the $p$'th bit to be recovered (this is the Index function in communication complexity -- see example 4.18 in Communication Complexity book, page 49).

This gives a gap $n^{\log n}$ vs. $exp(n)$ -- to get poly vs non-poly just use $N=n^{\log n}$ bits and ignore all but the first $n$.


Smoothed analysis to compare algorithms Has there been any research using smoothed analysis to compare approximation algorithms that have the same approximation ratio?

Any research that compares algorithms using smoothed analysis would be interesting (e.g. algorithms that have the same worst-case time complexity).

As far as I am aware, a comparison of approximation algorithms has not been done so far with respect to smoothed analysis. There are only a few papers on smoothed analysis of approximation ratios in the first place.

Maybe only loosely related: bijective analysis has been used to directly compare the competitive ratio of online algorithms (Angelopoulos, Schweitzer, "Paging and List Update under Bijective Analysis", J. ACM, 2013).

See also here for more about smoothed analysis of approximation algorithms: "Smoothed analysis of approximation algorithms".


Bin Packing with uniform size constraints Consider the following version of the Bin Packing problem:
We are given $k$ unit-size bins and $n$ items with sizes $\epsilon < a_i \le 1$ for $1 \le i \le n$. Is it possible to pack items in bins?

Here is two simple observations:

When $\epsilon \le \frac{1}{4}$, this problem is strongly NP hard by a reduction from the 3-partition problem (Garey and Johnson: SP15).
When $\epsilon \ge \frac{1}{3}$, this problem is in P: place each item with size greater than $\frac{1}{2}$ in a separate bin. Assign maximum number of items left to non-empty bins. Arbitrarily, pair items still unassigned. If the number of these pairs is not more than the number of empty bins, assign these pairs to empty bins. Otherwise, it's impossible to pack the items in $k$ bins. It's not hard to see that you can generalized this even to the case that $\frac{1}{3} \le a_i$.

Is there any complexity result for the case that $\frac{1}{4} < \epsilon < \frac{1}{3}$?

As Peter pointed out, the 3-partition problem is NP-hard even when the sizes are between $1/3-\delta$ and $1/3+\delta$ for any constant $\delta>0$. Therefore, by a simple reduction from the 3-partition problem, for any constant $\delta>0$, the Bin Packing problem is NP-hard when $1/3-\delta < a_i$ for all $i$.


List of number theoretic or algebraic problems in various complexity classes I am looking for a list about the known or unknown complexity of various number theoretic  /algebraic problems. For example,

GCD in $NC^1$ is open,
factoring in $P$ is open,
computing sheaf cohomology is $\#P$-hard,
Arora and Barak state that a variant of factoring is $NP$-complete (though this is not clear based on the discussion at An NP-complete variant of factoring.),
Barbulescu et al's breakthrough work on discrete logarithms.

Adleman once published a list focused on $P$ and $NP$ but it seems outdated. Mumford has a paper on what is computable in algebraic geometry without regard to complexity.

Does anyone know a list of (major) discoveries since these lists were published?

  What are some problems of a number theoretic/algebraic flavor whose complexity classes are possibly already known (since the above lists were published), unknown but conjectured, or unknown and not conjectured?

Some avenues of problems could be interpolation problems (univariate or multivariate, over various fields), Chinese remainder theorem, complexity of point counting over curves, etc.

Algebraic geometry

Noether's Normalization Lemma (NNL) for explicit varieties is currently only known to be in $\mathsf{EXPSPACE}$ (like general NNL), but is conjectured to be in $\mathsf{P}$ (and is in $\mathsf{P}$ assuming that PIT can be black-box derandomized). Update 4/18/18: It was recently shown that for the variety $\overline{\mathsf{VP}}$ it is in $\mathsf{PSPACE}$ over the rationals (Forbes & Shpilka) and then over arbitrary fields (Guo, Saxena, & Sinhababu).
Testing whether a given set of polynomials has an algebraic dependence. This problem was recently shown to be in $\mathsf{AM} \cap \mathsf{coAM}$ by  Guo, Saxena, & Sinhababu (improving the previous upper bound of $\mathsf{NP}^{\mathsf{\# P}}$ due to Mittmann, Saxena, & Scheblechner, also on the arXiv).
There are several (arXiv) new algorithms for computing topological invariants of complex varieties (with various restrictions like smoothness, etc.). I believe for most of these the optimal upper bound is still open.
Hilbert's Nullstellensatz (HN): given integer polynomials, decide if they have a common complex solution, is in $\mathsf{AM}$ assuming GRH (Koiran). It is unknown if it is in $\mathsf{NP}$.
Algorithms for resolution of singularities of algebraic varieties in characteristic zero. The current best time upper bound, due to Bierstone, Grigoriev, Milman, and Włodarczyk is $\mathcal{E}^{d+3}$ where $d$ is the dimension of the variety and $\mathcal{E}^{\bullet}$ is the Grzegorczyk hierarchy of primitive recursive functions. There aren't particularly good (any?) lower bounds on this problem, but for a seemingly much simpler problems related lower bounds are known, namely: There are ideals in $n$ variables generated in degree at most $n$ that require $\mathcal{E}^{n+1}$ such generators. So the current upper bound for resolution of singularities may not be far from the truth, but little is really known.

Isomorphism problems

Many problems on permutation groups - such as coset intersection, permutation group isomorphism, etc. - are in $\mathsf{NP} \cap \mathsf{coAM}$, but it is unknown if they are in $\mathsf{NP} \cap \mathsf{coNP}$, and it is suspected that they are not in $\mathsf{P}$. Graph Isomorphism reduces to most of those problems, so a better upper bound on them implies a better upper bound on GI.
In particular, for permutation group isomorphism, the current best upper bound is $2^{O(n)}|G|$, and it is open if it can be done in $2^{O(n)}$ time (depending only on the degree of the permutation group and not on its order), let alone quasi-poly time like GI and coset intersection.
Group Isomorphism where groups are given by multiplication tables is known to be in $\mathsf{TIME}(n^{O(\log n)})$, but is suspected to be in $\mathsf{P}$. Known to be in $\mathsf{P}$ for several classes of groups (update 4/18/18: and a couple (arXiv) more (arXiv)), but not in general.

Other

Update 4/18/18: Tensor rank over any field $\mathbb{F}$ is $\exists \mathbb{F}$-complete (Schaefer & Stefankovic). Is tensor rank over $\mathbb{Q}$ in $\mathsf{NP}$? It is known to be $\mathsf{NP}$-hard (Håstad), and over finite fields it is in $\mathsf{NP}$.
More generally, many problems on tensors over $\mathbb{Q}$ are $\mathsf{NP}$-hard but not known to be in $\mathsf{NP}$ (Hillar and Lim, also on the arXiv).

It would (somewhat sadly) seem that the Adleman-McCurley survey, despite being 21 years old, is pretty up to date in terms of number-theoretic problems, with the exception of the fact that we now know that $\mathsf{PRIMES}$ is in $\mathsf{P}$...


Arthur-Merlin protocol with BQP power Context: Aaronson raised the following question:

  Let f be a black-box function, which is promised either to satisfy the
  Simon promise or to be one-to-one.  Can a prover with the power of BQP
  convince a BPP verifier that f is one-to-one?

Speculation: Let's take Arthur-Merlin protocols (I actually don't know in much depth about these protocols so please pardon any inconsistencies that may arise) where one can restrict Merlin's power to BQP instead of unbounded resources and Arthur has BPP resources. Now I realize that there are probabilities to:

  A problem is considered to be solvable by this protocol if whenever
  the answer is "yes", Merlin has some series of responses which will
  cause Arthur to accept at least 2/3 of the time, and if whenever the
  answer is "no", Arthur will never accept more than 1/3 of the time.

source: Wikipedia.

Now consider the following, this paper gives an algorithm where one can check in quantum polynomial time whether a function satisfies Simon's promise. Merlin can therefore check this, for Arthur we don't know, let's assume it can't.

Question: Given the above mentioned conjecture, if Arthur sends (through a message) Merlin the function to be computed/checked in the first pass, Merlin can check whether the function satisfies Simon's promise or not, if yes, then we know the answer, if no, then is checking whether a function one-to-one in polynomial time? Also if Arthur can't check whether the function satisfies Simon's promise can the probabilities above mentioned change, since Merlin knows the answer already?

I also think this question might remain open until we know whether BPP != BQP, are there any indirect techniques that can let one evade having to rely on conjectural support in my argument? Thanks!

I'm glad you're interested in my IP with BQP prover problem!

Unfortunately, I'm not sure I understand your question.  If the function $f$ satisfies the Simon promise, then Merlin can easily convince Arthur of that by telling him the secret string $s$.  If, on the other hand, $f$ is one-to-one, then Merlin can convince himself of that (by using Simon's algorithm to look for $s$ and not finding anything), but the question is how he can convince Arthur.  It clearly won't do for Merlin to say, "Arthur, I looked for $s$, but I found nuthin'!"  For how would Arthur know that Merlin wasn't lying?

Now, it's a known theorem that, if Merlin wasn't around, then Arthur would need to make at least ~$2^{n/2}$ black-box queries to $f$, in order to decide with high probability whether $f$ was one-to-one or satisfied the Simon promise.

It's also known that, if Merlin had unbounded computational power (not just the power of BQP), then there is an interactive protocol by which Merlin could convince Arthur that $f$ is one-to-one.  Namely, Arthur picks a random $x$, evaluates $f(x)$, sends $f(x)$ to Merlin, and asks Merlin to tell him what $x$ was.  If $f$ is one-to-one, then Merlin---provided he has NP search powers---can always answer such challenges correctly.  But if $f$ is two-to-one, then Merlin must be wrong with probability at least $1/2$.

The case I asked about---the one where Merlin has BQP powers, but no more than that---is still open.

To answer your last question: no, one would not need to prove BPP≠BQP in order to solve this problem.  The reason is that this problem only concerns the relativized setting: the setting where the function $f$ is a black box, which Arthur and Merlin can learn about only by querying it.  And in the relativized setting---unlike the "real," unrelativized one---we can often prove unconditional separations between complexity classes!  Indeed, I already mentioned one example above: it's known that any classical randomized algorithm to solve Simon's problem has to make exponentially many queries to $f$.  That fact implies the existence of an oracle separating BPP from BQP.


Vehicle routing problem over Manhattan distances I am looking for references to the variant of the vehicle routing problem over Manhattan distance metric where the aim is to optimize the number of tours starting at the depot.

Is the following problem NP-hard

Problem :The distance constrained version of the vehicle routing problems over Manhattan distance metric considering an complete $N\times N$  grid or a grid where some edges are missing  ?
The grid graph is a weighted one.

The Hamiltonian cycle problem on grid graphs (a node induced subgraph of the infinite grid) is NP-complete.

To prove NP-hardness of $VRP$ on grid graphs you can use a direct reduction: given a grid graph $G = (V, E)$ with $|V|= n$ nodes, it easy to see that it has an hamiltonian cycle if and only if the corresponding Vehicle Routing Problem on grid graphs (all edges have cost 1) has a solution with total cost $\leq n$. The weighted edges case is a generalization, so the reduction is immediate:

HAM CYCLE on grid graphs (NP-complete) $\leq$ VRP on grid graphs with cost 1 edges $\leq$ VRP on grid graphs with weighted edges.

EDIT:
Other stuff: Euclidian (planar) TSP is NP-complete (see Hamilton paths in grid graphs), from this result it follows that TSP with distances measured in Manhattan norm is NP-complete, too (see for example this survey). VRP on grid graphs with weighted edegs is a generalization of it.

But if we consider VRP on solid grid graphs (no holes allowed) I suspect that the problem is open because it is directly connected to this: "Problem 54: Traveling Salesman Problem in Solid Grid Graphs"


Shuffling of tokens on a graph using local swaps Let $G= (V, E)$ be a non-regular connected graph whose degree is bounded. Suppose that each node contain a unique token.

I want to uniformly shuffle the tokens amongst the graph using only local swaps (i.e. exchange of the tokens between two adjacent nodes) ? Is there a lower bound known for this problem ?

The only idea I had is to use a random walk result, then to see how much swaps I need to "simulate" the effect of random walks transporting tokens on the graph.

Suppose your graph was a path.  I think then this problem becomes equivalent to sorting a random sequence of numbers in an array by swapping adjacent entries.  Even of all nodes are topology aware, you get a n^2 lower bound on the number of swaps (cannot do better than bubble sort which is n^2 even on a random input).


Is it possible to model maximization in a petri net without using inhibitor arcs? Creating a petri-net that models the minimum function is quite simple:

 -----     -----
   |         |
   |         |
   O         O
   |         |
   v         v
  -------------

If a tokens arrive via source 1 and b tokens arrive via source 2, min(a, b) tokens will eventually end up in the sink.

Now I would like to model the maximum function. I found a solution, but it requires the use of inhibitor arcs. Question: Is is possible to model the maximum function without the use of inhibitor arcs?

I know almost nothing about Petri nets, so watch out for any mistakes.  The terminology in this answer follows Wikipedia.

Theorem.  There is no Petri net with two distinguished source transitions S1 and S2 and one distinguished sink transition T such that if S1 fires a times and S2 fires b times, then T fires max{a,b} times eventually but T cannot fire more than max{a,b} times.

Proof.  Suppose that there is such a Petri net, and let M0 be the initial marking.  Let n be the number of places in this Petri net.  A marking can be viewed as an element in ℕn, where ℕ={0,1,2.…}.

Define markings M1, M2, … recursively as follows.  Starting with Ma (a=0,1,…), let S1 fire once, and wait for T to fire.  Let Ma+1 be the marking after T fires.

By Dickson’s lemma, there exist indices i<j such that Mi≤Mj.  Consider the following scenario.  Starting with Mi, let S2 fire i+1 times.  Counting from the beginning, S1, S2 and T have fired i times, i+1 times and i times, respectively.  Therefore, from this situation, T will eventually fire.  Now consider another scenario.  Starting with Mj, let S2 fire i+1 times.  Then there exists a firing sequence which leads to T firing because Mi≤Mj (and the Petri net does not have inhibitor arcs), but this contradicts the assumption because counting from the beginning, S1, S2 and T have fired j times, i+1 times and j+1 times, respectively, and j+1>max{j, i+1}.  QED.

Edit: The proof in revision 1 contained an error, which was pointed out by mweerden in a comment.  Now it is fixed.  Thanks, mweerden!


Intermediate/Coding representation for Levenshtein Distance The phrases:

  The quick brown fox jumps over the lazy dog [A]

and

  The uick brown fox jumps oower the lazy dog [B]

can be compared using Levenshtein Distance algorithm to determine similarity by calculating the minimum number of single character additions, deletions, or replacements are necessary to transform A into B.

I'm interested to know if there is an intermediate representation, or possibly a coding scheme for the Levenshtein Distance.  Not for use between two phrases, but just a coding applied to a single phrase such that character index does not affect comparisons.

In B, the 'q' is missing compared to A.  A normal string comparison would match 'The ' and then fail at 'uick brown fox...' merely because of a single character offset.  The Levenshtein Distance could be used to compare it to the original phrase A for a more forgiving comparison, but in my case, I won't have two phrases, just one.

So, I'm looking for some way of unambiguously coding a sentence in packets of information, little atoms of truth (I'm thinking one packet per character?) that maintain a local ordering and so-on, but if some of the packets are wrong, it doesn't affect later characters.

Each unique phrase should map to one and only one unique encoding/intermediate representation, Sets A' and B'.  Computing the Levenshtein Distance of A and B would then be the same as computing the intersection of sets A' = B'.

Alternatively - if this problem does not have a solution (and this sure maps to a well-trodden area of research, I wouldn't be surprised), some convincing argument/proof for its unsolvability.

There's indeed some research in this vein for the edit distance with some positive and some negative results. (I might not be understanding the question precisely, so I'll try to answer questions I know to answer.)

Here's one interpretation: (I1) you want to compute, for each string A a set f(A) such that, for any two strings A,B, the edit distance ed(A,B) is equal to the symmetric difference between f(A) and f(B) (in some sense the opposite of intersection of the two sets). This question has been well-studied (though by far is not solved), and is known as the question of embedding edit distance into Hamming distance ($\ell_1$). In particular, achieving (I1) precisely is not possible, but is possible up to some approximation (i.e., we approximate ed(A,B) up to some factor):

Krauthgamer and Rabani prove that $\Omega(\log n)$ approximation is required ($n$ is the length of the strings);
Ostrovsky and Rabani prove that $2^{O(\sqrt{\log n\log\log n})}$ approximation is achievable.

Here's a slightly more liberal interpretation: (I2) we produce some sketch f(A) for each string A, and we estimate the distance ed(A,B) via some calculation on f(A), f(B) (i.e., not necessarily by taking the symmetric difference).  The question is to have f(A) to be much shorter than the length of the original string, $n$ (otherwise, one has a trivial solution by f(A)=A). This interpretation (I2) is more general than (I1) (=easier to achieve), though we do not know of any strictly better solutions. There's some partial progress, where the estimation of ed(A,B) is done from f(A) and B (i.e., one string, say B, is fully known).

There's surely more literature in this vein, but let me know first if this is anywhere close to what you meant.


Hardness of $k$-Plex Definition. Given an undirected graph $G = (V,E)$, a $k$-plex is a subgraph $G'$ of $G$ such that each vertex in $G'$ is connected to at least $s - k$ other vertices in $G'$, where $s$ is the # of vertices in $G'$.

Computing the maximum $k$-plex is NP-hard since a clique is just a $1$-plex. In my understanding, such a reduction only shows the hardness of computing the maximum $1$-plex. Moreover, when $k=|V|$, the problem becomes trivial because any subgraph of $G$ is a $k$-plex then.

  Question. Is the maximum $2$-plex still NP-hard to be computed? Or more generally, given a graph $G = (V,E)$, what is the maximum $k$ such that the maximum $1$-plex, the maximum $2$-plex, $\cdots$ and the maximum $k$-plex are all NP-hard to be computed?

This question seems interesting but I did not come up with a reduction from any other NP-complete problem, even from the MaxClique.

Lemma. If a graph has a $k$-plex on $m$ vertices, then it has a clique on $\frac m{k+1}$ vertices.

Proof. Greedily pick the vertices of the clique from the $k$-plex.

Since a clique on $m$ vertices is also a $k$-plex on $m$ vertices (for any $k$), we get that the size of the maximum $k$-plex is a $k$-approximation of the size of the maximum clique.
Since clique is hard to approximate with an $O(n^{1-\epsilon})$ factor, determining the largest $k$-plex is also hard for any $k=O(n^{1-\epsilon})$.


Quantum proofs of classical theorems I'm interested in examples of problems where a theorem which seemingly has nothing to do with quantum mechanics/information (e.g. states something about purely classical objects) can nevertheless be proved using quantum tools. A survey Quantum Proofs for Classical Theorems (A. Drucker, R. Wolf) gives a nice list of such problems, but surely there are many more.

Particularly interesting would be examples where a quantum proof is not only possible, but also "more illuminating", in analogy with real and complex analysis, where putting a real problem in the complex setting often makes it more natural (e.g. geometry is simpler since $\mathbb{C}$ is algebraically closed etc.); in other words, classical problems for which quantum world is their "natural habitat".

(I'm not defining "quantumness" here in any precise sense and one could argue that all such arguments eventually boil down to linear algebra; well, one can also translate any argument using complex numbers to use only pairs of reals - but so what?)

There is a recent paper from  Scott Aaronson which provides a new proof that the permanent is #P-hard. This proof is based on the model of linear-optical quantum computing and is more intuitive than that of Leslie Valiant.


Arithmetic Analogues of P versus BPP In the arithmetic hierarchy, is there an analog of $P$ versus $BPP$? Particularly is there a notion of randomness there?

If there is no such analogy, why is randomness in the resource bounded case special? Any references will be great.

There are several notions of randomness in computability theory (/the arithmetic hierarchy; lookup "Martin-Lof randomness", "Kurtz random", "Schnorr random", ...), but I think the ones that are analogous to $\mathsf{BPP}$ become trivial in the setting of the arithmetic hierarchy. The reason is essentially that a randomized Turing machine with bounded error can be simulated by a deterministic one: the deterministic one simulates the random one with all settings of the randomness and then takes the majority vote. If the original machine took time $t(n)$ then the new machine takes time $2^{t(n)}$, which is why this trick tends not to work in the resource-bounded case.

(Though of course it works for any deterministic time-bounded class where if time bound $t(n)$ is allowed in the class then so is $2^{t(n)}$. In particular, this trick works in $\mathsf{DTIME}(\mathcal{E}^4)$, where $\mathcal{E}^4$ is the fourth level of the Grzegorczyk hierarchy of primitive recursive functions. But that's still a pretty big class.)


Finding min-max vertex-disjoint paths with a common source on planar graphs Given a planar unweighted graph, and a collection of vertex pairs $(s,t_1),\dots,(s,t_k)$ ($k\ge2$ is a constant), find $k$ vertex-disjoint (except source) paths from $s$ to $t_i$ such that the length of the longest path is minimized.

Question: Is there a polynomial-time algorithm for the problem?

Some related results:

if $k$ is not fixed the problem is NP-hard even if $t_1=\dots=t_k$;
if the input graph is weighted and sources of paths do not coincide, i.e. paths are $(s_1,t_1),\dots,(s_k,t_k)$ the problem is NP-hard even for $k=2$;
a problem with different objective, namely minimizing the sum of path lengths, is

solvable with the minimum cost flow algorithm for coinciding sources;
NP-hard for non-coinciding sources and general $k$;
open for non-coinciding sources and constant $k$.

This is not exactly what you asked, but the problem is NP-complete if k is not a constant but part of the input.

This follows from the proof of Theorem 1 in van der Holst and de Pina [HP02], which says: given a planar graph G, distinct vertices s and t in G, and positive integers k and b, it is NP-complete to decide whether there are k pairwise internally vertex-disjoint paths between s and t each of length at most b.

Note that the problem in the statement of Theorem 1 is different from yours in two respects.  One difference is, as I mentioned, that k is given as part of the input.  The other is that the problem in [HP02] is about paths with common endpoints instead of paths with a common source and different sinks.  I do not know how to fix the first difference; the difference is so large that it is likely that we will need a completely different proof to fix k.  But I know at least how to fix the second difference.

The proof of Theorem 1 in [HP02] gives a reduction from 3SAT.  This reduction has the following property: in the instance (G, s, t, k, b) constructed by the reduction, the degree of vertex t is always equal to k.  Let t1, …, tk be the k neighbors of t.  Then instead of asking whether there are k pairwise internally vertex-disjoint paths between s and t each of length at most b, we can equally ask whether there are pairwise vertex-disjoint-except-source paths P1, …, Pk such that each Pi is a path between s and ti of length at most b−1.

[HP02] H. van der Holst and J. C. de Pina.  Length-bounded disjoint paths in planar graphs.  Discrete Applied Mathematics, 120(1–3):251–261, Aug. 2002.  http://dx.doi.org/10.1016/S0166-218X%2801%2900294-3


Are there decidable problems for which for no algorithm we can give time bounds? Are there decidable problems such that for no algorithm which solves the problem we can give a time bound as a function of the length n of the input instance?

I arrived at this question because I was thinking about the following:

Assume we
have a recursively enumerable, but undecidable problem. Assume further that I is
a "yes"-instance of the problem. Then for no algorithm which identifies the
"yes"-instances of the problem we can give a time bound in terms of the size n
of I. For if we could give such a time bound, we could decide the problem, as we
could simply conclude that I is a "no"-instance when the time bound is exceeded.

Since we cannot give a time bound for recursively enumerable, undecidable
problems (for the computation time for "yes"-instances), I was wondering if there are decidable problems as well for which we
cannot give a time bound.

For every algorithm $A$ that terminates on a class of inputs $\mathsf{In}$, we can define the function of its running times:
$$
f(n)=\max_{i\in \mathsf{In(n)}}~~ \mathsf{time}(A(i)),
$$
where $\mathsf{In}(n)$ is the class of inputs of length $n$ and $\mathsf{time}(A(i))$ is the time algorithm $A$ requires to terminate on $i$. Of course, this definition is unsatisfying as it relates to the algorithm, but it shows the existence of such a function.
The question that remains is whether there exists a concise representation (and I believe that this was what you were asking for).

If we use simple algebraic terms (without recursion of any sort) as definition of concise, then I think the answer is no: There are problems which can be decided but whose complexity is nonelementary. That is, there does not exist a stack of the form $2^{2^{2^{2^{\dots^n}}}}$ that bounds the execution time of an algorithm for a problem of size n.

I hope I understood your question in the right way.


"Almost sorting" integers in linear time I am interested in sorting an array of positive integer values $L = v_1, \ldots, v_n$ in linear time (in the RAM model with uniform cost measure, i.e., integers can have up to logarithmic size but arithmetic operations on them are assumed to take unit time). Of course, this is impossible with comparison-based sorting algorithms, so I am interested in computing an "approximate" sort, i.e., computing some permutation $v_{\sigma(1)}, \ldots, v_{\sigma(n)}$ of $L$ which is not really sorted in general but a "good approximation" of the sorted version of $L$. I will assume that we are sorting the integers in decreasing order because it makes the sequel a bit more pleasant to state, but of course one could phrase the problem the other way round.

One possible criterion for an approximate sort is the following (*): letting $N$ be $\sum_i v_i$, for every $1 \leq i \leq n$, we require that $v_{\sigma(i)} \leq N/i$ (i.e., the "quasi-sorted" list is bounded from above by the decreasing function $i \mapsto N/i$). It is easy to see that the actual sort satisfies this: $v_{\sigma(2)}$ must be no greater than $v_{\sigma(1)}$ so it is at most $(v_{\sigma(1)} + v_{\sigma(2)})/2$ which is $\leq N/2$, and in general $v_{\sigma(i)}$ must be no greater than $(\sum_{j \leq i} v_{\sigma(i)})/i$ which is $\leq N/i$.

For instance, requirement (*) can be achieved by the algorithm below (suggested by @Louis). My question is: Is there existing work on this task of "almost sorting" integers in linear time, by imposing some requirement like (*) that the real sort would satisfy? Does the algorithm below, or some variant of it, have an established name?

Edit: fixed the algorithm and added more explanations

Algorithm:

INPUT: V an array of size n containing positive integers
OUTPUT: T

N = Σ_{i<n} V[i]
Create n buckets indexed by 1..n
For i in 1..n
| Add V[i] into the bucket min(floor(N/V[i]),n)
+

For bucket 1 to bucket n
| For each element in the bucket
| | Append element to T
| +
+

This algorithm works as intended for the following reasons:

If an element $v$ is in the bucket $j$ then $v ≤ N/j$.

  $v$ is put into the bucket $j=\min(N/v,n)$, thus $j ≤ \lfloor N/v\rfloor ≤ N/v$

If an element $v$ is in the bucket $j$ then either $N/(j+1) < v$ or $j=n$.

  $v$ is put into the bucket $j=\min(N/v,n)$, thus $j = \lfloor N/v \rfloor$ or $j=n$. In the first case $j=\lfloor N/v\rfloor$ which means $j ≤ N/v < j+1$ and thus $N/(j+1) < v$.

For $j<n$, there are, at most, $j$ elements in the buckets from 1 to $j$.

  Let $j<n$ and let $k$ be the total number of elements in one of the
  buckets 1..j. By 2. we have that every element $v$ in a bucket $i$ (with $i ≤ j$) is such that $N/(j+1)≤N/(i+1)<v$. Therefore the sum $K$ of all elements in the buckets from $1$ to $j$ is greater than $k×N/(J+1)$. But this sum $K$ is also less than $N$ thus $k×N/(j+1) < K ≤ N$ and thus  $k/(j+1) < 1$ which gives us $k<j+1$ or $k≤j$.

$T$ satisfies (*) i.e. the $j$-th element of $T$ is such that $T[j] ≤ N/j$

  By 3. we have that $T[j]$, the $j$-th element of $T$, comes from a bucket $i$ with $i ≥ j$ therefore $T[j] ≤ N/i ≤ N/j$.

This algorithm takes linear time.

  The computation of $N$ takes linear time. Buckets can be implemented with a linked-list which has $O(1)$ insertion and iteration. The nested loop runs as many times as there are elements (i.e. $n$ times).

This sounds a lot like the ASort algorithm. See this article by Giesen et. al.:

https://www.inf.ethz.ch/personal/smilos/asort3.pdf

Unfortunately, the running time is not quite linear. The article above proves that any comparison-based randomized algorithm ranking $n$ items within $n^2/\nu(n)$ has a lower bound of $n*log (\nu(n))$ (assuming $\nu(n) < n$).

EDIT, in response to the clarifications in the question:

What you're doing is simply a bucket sort. However, the algorithm for bucket sort isn't linear in this case. The problem: you have to sum the natural numbers and then perform division on each one of them. Since the numbers are unbounded in size, $N/V[i]$ is no longer a constant-time operation. It will take longer to perform the more numbers you need to sum.

How much longer? Division depends on the number of digits, so it's $lg(n)$, times $n$ division operations. That probably sounds familiar. :)


Complexity of Hidden Subgroup problems Has anyone classified the (non-quantum) complexity of the hidden subgroup problem for finite Abelian groups? Is it known to be in any classical (not quantum) complexity classes?

If $G=\mathbb{Z}_{2}^{n}$ and the hidden subgroup $H$ has order $2$, then finding the hidden subgroup is equivalent to finding two elements in the same coset of $H$. The latter is in turn a birthday paradox-type problem, so should require $\Theta(\sqrt{|G|})$ queries for a randomized algorithm and $\Theta(|G|)$ queries for a deterministic algorithm. Note that $|G|=2^{n}$ is exponential in the input size.


Max Non-overlapping Path in Weighted Graph I have a sparse weighted graph, and I want to find the longest path from a given vertex to any other vertex which does not go through the same vertex twice. You can think of it as, I am here, and I want to take the longest walk possible in my graph without walking through the same place twice. Where ever that ends me up, I don't care, and I don't necessarily have to travel through every point on the graph, if those points do not lie on the longest path.  All edges have positive weights.

Can anyone describe an algorithm for this that is not a complete enumeration of all paths?

Yes, the Bellman-Held-Karp algorithm is not a complete enumeration and can be modified easily enough to solve your problem.

However, it still takes something over $2^n$ time (see question for details), and something exponential like that seems unavoidable since this is a variant of the traveling salesman problem.


Is there any triangle-free, star-cutset-free, circle graph, with more than n edges? I'm trying to find a graph with those properties for my studies, but unfortunately I can't find such graph.

Does anyone know if there is that graph, or why is it impossible to exist?

Suppose $G$ is a triangle-free star-cutset-free circle graph.
I will show that $G$ contains no vertex with degree more than 2. Therefore, $G$ has at most $n$ edges.

Consider a circle representation $C$ of $G$. A set of chords is parallel if no two of them cross but there is a line crossing all the chords.

Property 1: $C$ has no 3 parallel chords.

Proof. Suppose $C$ has 3 parallel chords. Condider the vertex $v$ corresponding to the middle chord. Then, $N[v]$ is a cutset. This proves the property.

For the sake of contradiction, assume $G$ has a vertex $v$ of degree at least 3. Then, the chord corresponding to $v$ intersects 3 other chords. Since these 3 chords intersect one line, they are either parallel or two of them intersect. Due to Property 1, two of them intersect, which means their vertices form a triangle with $v$, which contradicts $G$ being triangle-free.


About using smoothness of the Hessian for getting to approximate criticality of a non-convex objective Is there any algorithm which shows that under the assumption of Lipschitz smoothness of the Hessian of a non-convex function one can get to its critical point faster?

Yes, there are some papers. The most relevant one to your question might be: https://arxiv.org/pdf/1611.00756.pdf


Complexity of SAT parameterized by treewidth Many papers state that Boolean satisfiability is in FPT when parameterized by primal, dual, or incidence treewidth. What are the best known time complexities of these parameterized algorithms? In particular, I would expect something like $O(2^{tw} nm)$ time complexity for at least primal treewidth, but I cannot find a reference for it.

Also, how about (weighted) Max-SAT and #SAT?

FPT results

The complexity of SAT, #SAT and MaxSAT parametrized by primal and incidence treewidth is FPT for all cases and of the form $2^{ck}\|F\|^d$ where $\|F\|=\sum_{C \in F} |var(C)|$ is the size of a reasonable encoding of a CNF $F$, $k$ is the (primal/incidence) treewidth and $c$ and $d$ are constants.

In this answer, I will denote by SAT(ptw) the problem SAT parametrized by primal treewidth. Same notations for #SAT(ptw), MaxSAT(ptw) and SAT(itw) for incidence treewidth.

For SAT(ptw), it is hard to pinpoint the exact first reference as their are many works going in this direction and proving similar results without being exactly stated this way. I would thus point to [1] where Alekhnovich and Razborov proves that SAT parametrized by branch-width is FPT. They also observe that branch-width is similar to treewidth up to a constant factor. I also advice to read the introduction of this paper to have a good overview of the previous literature on similar results.

For SAT(itw) and #SAT(itw), it is a consequence of Courcelle's Theorem that was first observed in [4], but, as observed by Szeider in [2], the hidden constants may be very high. For #SAT(ptw), an observation that exhaustive DPLL would run in FPT time with reasonable constant has been made in [3] by Bacchus, Shannon and Pitassi but without formally proving this. Explicit algorithms with better complexity bounds are given by Szeider and Samer in [5] for #SAT(itw) and #SAT(ptw).

For MaxSAT(ptw) and MaxSAT(itw), I do not know any reference doing it directly. I suspect the community to be aware of the fact that easy modifications in the algorithm for #SAT and thus too straightforward to be published anywhere. An notable exception is, that appeared much later, [6] where Sæther, Telle and Vatshelle give an algorithm for MaxSAT(ps-width), a parameter more general than treewidth. They also observe that it is roughly the same algorithm for #SAT and weighted MaxSAT.

All algorithms mentioned above can also be transformed into algorithms for weighted versions of our problems. One uniform way of seeing this is through the spectrum of Knowledge Compilation. Basically, what you can observe it that all these algorithms are implicitly rewriting, in FPT time, the CNF formula into a very restricted Boolean circuit (known in the literature of knowledge compilation as d-DNNF) computing the same Boolean function, see [7] where it is proven for a very general parameter. The catch is that many problems are tractable on this new representation such as (weighted) model counting, enumeration or finding a model with minimal Hamming weight, etc. Thus, everything that is ptime on d-DNNF becomes FPT on bounded treewidth CNF for free: change the representation in FPT time and solve it on the new circuit (that is also of FPT size).

This encompasses SAT, #SAT, weighted #SAT and also MaxSAT by working a bit more. Indeed, changing the representation of an UNSAT formula is quite easy: just output the 0 circuit. So it will not help you. However, compiling $F' = \bigwedge_{C \in F} s_C \vee C$ where you add in each clause of $F$ a fresh selector variable $s_C$ is more interesting. $F'$ has the same treewidth as $F$ (+ constant) and is of course satisfiable (set $s_C=1$ for every $C$). Now, solving MaxSAT($F$) is equivalent to finding the solution of $F'$ setting the smallest number of $s_C$ to $1$, something that can be done in polynomial time for d-DNNF. A proof of this can be found in my thesis, Section 3.2.2 [8].

Best complexity

In [5], the complexity bounds are given very explicitly. For #SAT(ptw) (and thus for SAT(ptw) as well), the complexity is $O(2^{k}kNd)$ where $N$ is the number of variables and $d$ is the maximal number of occurrence of a variable in the formula. Not that $Nd$ may not be linear in $\|F\|$ but is very close from it. A linear time (in the formula size) compilation algorithm can be found in the appendix of [9] which gives also a linear time algorithm for SAT, #SAT, maxSAT etc. The complexity is of the form $O(2^{ck}\|F\|)$ but the exact value of $c$ is not discussed here as it was not really necessary in this paper. I would say that a thorough analysis would give $c=1$ but I have not checked it carefully.

For SAT(itw), [5] gives a complexity of $O(2^k k (l+2^k) \|F\|)$ where $l$ is the size of the longest clause of $F$. If one wants linear time in $\|F\|$, one can rewrite $F$ as an equivalent 3-CNF without changing its incidence treewidth as shown by Lampel, Mengel and Mitsou in [10], which thus gives an equivalent 3-CNF which thus has primal treewidth at most $3k$ and now use the algorithm for primal treewith but it would spoil the constant in the exponent.

These are the best explicitly stated/known complexity upper bounds. I would not be surprised if they can still be improved, especially going from $4^k$ to $2^{k+O(1)}$ for incidence treewidth. This can be explained by the fact that these results are mostly interesting in theory where the precise constant is not important and the work to get it down is not really worth it. Friedrich Slivovsky mentioned in personal communication that there may be some algebraic trick in the algorithm of [5] for itw to get a better complexity bound but as far as I know, it has never been written formally.

References

[1] M.Alekhnovich and A.A.Razborov, Satisability, branch-width and Tseitin tautologies. In 43rd Annual IEEE Symposiumon Foundations of ComputerScience (FOCS'02)

[2] On fixed-parameter tractable parameterizations of SAT, Stefan Szeider, Theory and Applications of Satisfiability, 6th International Conference, SAT 2003

[3] Bacchus, Fahiem, Shannon Dalmao, and Toniann Pitassi. "Solving #SAT and Bayesian inference with backtracking search." Journal of Artificial Intelligence Research 34 (2009).

[4] Courcelle, Bruno, Johann A. Makowsky, and Udi Rotics. "On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic." Discrete Applied Mathematics 108.1-2 (2001).

[5] Samer, Marko, and Stefan Szeider. "Algorithms for propositional model counting." Journal of Discrete Algorithms 8.1 (2010): 50-64.

[6] Sæther, Sigve Hortemo, Jan Arne Telle, and Martin Vatshelle. "Solving# SAT and MAXSAT by dynamic programming." Journal of Artificial Intelligence Research 54 (2015): 59-82.

[7] Bova, Simone, Florent Capelli, Stefan Mengel, and Friedrich Slivovsky. "On compiling CNFs into structured deterministic DNNFs." In International Conference on Theory and Applications of Satisfiability Testing, pp. 199-214. Springer, Cham, 2015.

[8] Structural restriction of CNF-formulas: application to model counting and knowledge compilation, Thèse de Doctorat, 2016.

[9] Capelli, Florent, and Stefan Mengel. "Knowledge compilation, width and quantification." arXiv preprint arXiv:1807.04263 (2018).

[10] Lampis, Michael, Stefan Mengel, and Valia Mitsou. "QBF as an Alternative to Courcelle’s Theorem." International Conference on Theory and Applications of Satisfiability Testing. Springer, Cham, 2018.


Edit distance between two partitions I have two partitions of $[1 \ldots n]$ and am looking for the edit distance between them.

By this, I want to find the minimal number of single transitions of a node into a different group that are necessary to go from partition A to partition B.

For example the distance from {0 1} {2 3} {4} into {0} {1} {2 3 4} would be two

After searching I came across this paper, but a) I am not sure if they are taking into account the ordering of the groups (something I don't care about) in their distance b) I am not sure how it works and c) There are no references.

Any help appreciated

This problem can be transformed into the assignment problem, also known as maximum weighted bipartite matching problem.

Note first that the edit distance equals the number of elements which need to change from one set to another.  This equals the total number of elements minus the number of elements which do not need to change.  So finding the minimum number of elements which do not change is equivalent to finding the maximum number of vertices that do not change.

Let $A = \{ A_1, A_2, ..., A_k \}$ and $B = \{ B_1, B_2, ..., B_l \}$ be partitions of $[1, 2, ..., n]$.  Also, without loss of generality, let $k \ge l$ (allowed because $edit(A, B) = edit(B, A)$).  Then let $B_{l+1}$, $B_{l+2}$, ..., $B_k$ all be the empty set.  Then the maximum number of vertices that do not change is:

$\max_f \sum_{i=1}^k |A_i \cap B_{f(i)} |$

where $f$ is a permutation of $[1, 2, ..., k]$.

This is exactly the assignment problem where the vertices are $A_1$, ..., $A_k$, $B_1$, ..., $B_k$ and the edges are pairs $(A_i, B_j)$ with weight $|A_i \cap B_j|$.  This can be solved in $O(|V|^2 \log |V| + |V||E|)$ time.


Formal theory about explaining algorithms There is a lot of algorithms written in formal languages, but I have never seen any formal system which target is to explain or give a rationale behind an algorithm. It seems that when constructing examples, authors have to create both interesting, somewhat random, and small samples. I think this task could be formalized to some degree.
I wonder if there is such theory or maybe attempts to formalize explanations?
Edit: I was looking for a theory that describes how to teach other people an algorithm. As mentioned by jmite, it is possible to create a self-explaining algorithm using dependent types to solve this problem.

This might not be what you're looking for, but I think this is somewhat covered by the theory of dependent types, specifically intrinsically typed data structures.
The idea is that, instead of having an algorithm along with a proof of correctness, you start with a type that describes the properties of a solution. Then you simply write a program of that type, and you are guaranteed that it is correct.
Does this mean that you get correctness for free? Certainly not. But now the "why" at each stage is clear. The presentation of the algorithm and the explanation are one and the same. The notion of of correctness is formalized, and baked into the language itself.
For intros on this, see:

https://cs.ru.nl/~wouters/Publications/ThePowerOfPi.pdf
http://homepages.inf.ed.ac.uk/wadler/papers/propositions-as-types/propositions-as-types.pdf
https://www.manning.com/books/type-driven-development-with-idris
https://mitpress.mit.edu/books/little-typer


How to prove the existence of a pure Nash equilibrium? I have a game as given by the table below. I would like to prove that the game has always at least one pure Nash equilibrium (NE). I used a computer program and in fact the game has a pure NE. So, I am claiming the existence of at least one pure NE.

I looked in the internet but most of the paper that I read are talking about general games.

I need to know what do I need to know and to do in order to prove my claim? I do not want to give me the whole answer (if you have any), just give the tools and some hints and that would be appreciated. Also, can you give, in general, situation, how to prove the existence of a pure NE? Thank you.

Here is the game:

$$\begin{array}{c|c|c|c|}
P1\backslash P2 & \text{$a_1$} & \text{$a_2$} & \text{$a_3$} \\ \hline
\text{$a_1$} & (-1, -1) & (p, q)   & (r, 0) \\ \hline
\text{$a_2$} & (s, t)   & (-1, -1) & (x, 0) \\ \hline
\text{$a_3$} & (0, y)   & (0, z)   & (0, 0) \\ \hline
\end{array}$$

You can see that it is a 2 players ($P1$ is the row player and $P2$ is the column player) game where each player has the action space $\{a_1, a_2, a_3\}$. Here $p,q,r,s,t,x,y,z$ are integers in the set $\{-1, 1\}$ which are related to each others by:

If p == 1 then r = 1
If s == 1 then x = 1
If q == 1 then z = 1
If t == 1 then y = 1

My algorithm that I used is a brute force one that search for all possible values of $p,q,r,s,t,x,y,z$ and then see for each possible value if there is a pure NE or not.

If p=q=s=t=−1, then it is easy to see that a pure NE can be reached by local search starting from (a3, a3).  So in the rest of the proof, assume that at least one of p, q, s, and t is equal to 1.

If p=q=1, then (a1, a2) is a pure NE.  Similarly, if s=t=1, then (a2, a1) is a pure NE.

In the remaining cases, at least one of the pairs (p, q), (q, p), (s, t), and (t, s) is equal to (1, −1).  By symmetry, we may assume without loss of generality that p=1 and q=−1.  By assumption, r=1.  Then (a1, a3) is a pure NE.


Graph isomorphism problem with invertible adjacency matrices This question is supplementary to the question asked here.

One of the answers give a class of graphs for which the adjacency matrices are invertible which is defined as follows.

  Given a permutation $\pi$ of a finite set $V$, form its cycle graph
  $G$ as follows: the vertex set is $V$ and the edges are pairs $(v,w)$
  for which $\pi(v)=w$. (This is a simple directed graph.) The adjacency
  matrix will in fact be the permutation matrix corresponding to $\pi$,
  which is invertible.

Let's consider a class of graph isomorphism problems where it is promised that both of the input graphs will be from the class defined above.

Can the graph isomorphism problems from this class be solved efficiently?

Isn't this graph just a collection of cycles? So we only need to compare that all the lengths in the two graphs match (which can be done by sorting the lengths).


A Combinatorial Problem on Extremal Set Theory Given a ground set $[n]$, under what condition of parameters $a,b,c$ does a family of subsets $\mathcal{F}\subseteq 2^{[n]}$ with the following property exist?

(i) $\forall S\in \mathcal{F}$, $|S|=a$.

(ii) $\forall S_1,S_2\in \mathcal{F}$, $|S_1\triangle S_2|\ge b$, where $S_1\triangle S_2$ means the symmetric difference between two sets.

(iii) $\forall T \subseteq [n], |T|\ge c$, $\exists S\in \mathcal{F}$, such that $|S\cap T|\ge 0.5a$.

As mentioned below by Aryeh, a trivial case can be $\mathcal{F}=\{S_1,S_2\}$ with $S_1=[n/2]$ and $S_2=[n]-S_1$, where we have $a=c=n/2$ and $b=n$. Basically the problem asks under what condition of $a,b$ we can get $c=o(n)$.

Any known results or related ideas about nontrivial sufficient (no need to be necessary of course) condition of $a,b,c$ is appreciated.

This combinatorial problem rises from a communication game, and may have concrete connection with error-correcting codes.

Did you want some condition to make $\mathcal{F}$ a large collection? Because the current definition allows for the following, presumably trivial, case. Consider $\mathcal{F}=\{S_1,S_2\}$, where $S_1=[n/2]$ and $S_2=[n]\setminus S_1$. Then we can take $a=n/2$, $b=n$, $c=n/2$.


Where and how did computers help prove a theorem? The purposes of this question is to collect examples from theoretical computer science where the systematic use of computers was helpful

in building a conjecture that lead to a theorem,
falsifying a conjecture or proof approach,
constructing/verifying (parts of) a proof.

If you have a specific example, please describe how it was done. Perhaps this will help others use computers more effectively in their daily research (which still seems to be a fairly uncommon practice in TCS as of today).

(Flagged as community wiki, since there is no single "correct" answer.)

A very well-known example is the Four Color Theorem, originally proven by exhaustive checking.


Results showing existence/non-existence of finite graphs with specific computable properties imply certain complexity results Are there any known results showing that existence (or non-existence) of finite graphs with specific computable properties imply certain complexity results (such as P = NP)?

Here's one completely hypothetical result: If a finite graph exists with distingushed edges A, B, C and D such that all maximum matchings either contain all of A, B, C, and D, or contain none of A, B, C and D, then P = NP.

One result of this kind was proved by Lipton "On proving that a graph has no large clique: A connection with Ramsey theory". He connects lower bound conjectures with purely graph theoretic results, showing that if $NP$ is not contained in $coNTIME(n^{O(\log n)})/(\log \log n)$, then the inapproximability of $MAX-CLIQUE$ implies that there are graphs with neat Ramsey-theoretic properties. (See the paper for definitions.) I have no idea if any progress has been made on proving whether or not such graphs actually exist.


Understanding the "gap theorem" in geometric spanners I am reading the book "Geometric Spanner Networks" by G. Narasimhan and M. Smid. At page 109, there is the following definition:

  Intuitively: A set of directed edges satisfies the gap property, if the sources of any two distinct edges are "far" apart (relative to the shorter of the two edges)
  The gap property: Let $w \geq 0$ be a real number, and let $E$ be a set of directed edges in $\mathbb{R}^{d}$.
  We way that $E$ satisfies the $w-gap\ property$ if for any two distinct edges $(p,q)$ and $(r, s)$ in $E$, we have : $|pr| > w \cdot min(|pq|, |rs|)$

Then (at the same page) comes the following Theorem:

  Let $S$ be a set of $n$ points in $\mathbb{R}^{d}$, and let $E \in S \times S$ be a set of directed edges that satisfies the $w-gap\ property$.
  1. If $w \geq 0$, then each points of $S$ is the source of at most one edge if $E$.
  2. if $w>0$, then $wt(E)<(1+2/w) \cdot wt(MST(S))\log n$ (where $MST(S)$ denotes a minimum spanning tree of $S$.
  3. [not relevant for the question]

Background and context

In the proof of the second claim, there is inner claim that there exists a set $E' \subseteq E$ that is of size $m/2$ such that $wt(E')<(1+2/w) \cdot wt(MST(S))$.
Then comes an induction on $m$ in which the claim  $wt(E)<(1+2/w) \cdot wt(MST(S))\log m$ for any set $E$ that has less that $m$ edges. (Note: $n$ can be replaced by $m$ because $m \leq n$ in every graph that satisfies the $w-gap\ property$). The main point of the induction is relaying on the existence of an subset $E'$ of $E$ which has at least $m/2$ edges, and weight $(1+2/w) \cdot wt(MST(S))$. Then any set $E$ can be partitioned into 2 sets

$E'$ of weight $<(1+2/w) \cdot wt(MST(S))$. (whose existence was proofed before)
$E \setminus E'$ of weight $<(1+2/w) \cdot wt(MST(S)) \cdot \log m$. (according to the induction claim)

My question

Why is there the $\log m$? It seems to me that if the induction claim was "For every $E$ with less that $m$ edges $wt(E)<(1+2/w) \cdot wt(MST(S))$". The same proof would get a better bound (without the $\log m$)

Let's write $C = (1+2/w) wt(MST(S))$. The set $E$ satisfies the $w$-gap property and has $m$ edges. It can be partitioned into 2 sets:

One set is $E'$, which is a special subset of $E$. It is chosen such that we can easily prove that its weight is at most $C$.

The other set $E''$ (which is $E \setminus E'$) has $m/2$ edges; we only know that it satisfies the $w$-gap property. By the induction hypothesis, the weight of $E''$ is at most $C \log(m/2)$.

From this, it follows that the set $E$ has weight at most $C + C \log(m/2) = C \log m$.


Decompose a complete graph into smaller cliques The following exercise problem is from the book of D.B.West which i could solve:

If a complete graph can be decomposed into triangles then $n-1$ or $n-3$ is divisible by 6.

So my questions are the following,

If a complete graph of $n$ vertices can be decomposed into cliques of size $p$ with $p\leq n$ then what should be the relation between $n$ and $p$.

What is the official name of this problem in the literature ?

Any links/hints would be helpful.

If you want to decompose a complete graph into triangles then look for "steiner triple system" (STS). You will find some there: http://steinertriples.fr/

If you want to decompose a complete graph into cliques of size p, the generalization of STS that you want are "Balanced Incomplete Block Designs". If you want to know more about that, try to find the book from Douglas Stinson named "Combinatorial designs: construction and analysis".

Finally, if you want to build some BIBD, we've been sweating a lot over combinatorial designs code in Sage recently. It can build a (v,k,1)-BIBD whenever one exists for k<=5, and as for larger values of k, well, it depends.

Either way, if you find a combinatorial design that it cannot build come tell us about it ! :-P

Nathann


On the provability of P versus NP First of all, my understanding on Gödel's incompleteness theorem (and formal logic in general) is very naive, also is my knowledge on theoretical computer science (meaning only one graduate course taken while I'm still an undergraduate), so this question may be very naive.

As far as I could find, the provability of P versus NP is an open problem.

Now:

Gödel's first incompleness theorem states that there may be statements that are true but not provable nor disprovable.
If a polynomial solution is found for an NP-complete problem, it proves that P = NP.

So, suppose that P=NP is not provable:
This means that no example of a polynomial solution for an NP-complete problem can be found (otherwise, this would be a proof).
But if no example of a polynomial solution for an NP-complete problem can be found, this means that P=NP is false (proving it, meaning the statement is provable), which leads to a contradiction, therefore P=NP should be provable.

This sounds like a proof of the provability of P=NP to me, but I think it's extremely likely that it is due to my lack of understanding of the logic topics involved. Could anyone please help me understand what is wrong with this?

If P=NP, there must be polynomial-time algorithms for NP-complete problems.  However, there might not be any algorithm that provably solves an NP-complete problem and provably runs in polynomial time.