Efficiently computable by a "simple" algorithm? I am interested in the relation between "program complexity" and "computational complexity".

In particular, I was wondering

What is known about the minimal length a program must have to solve a given problem (efficiently)?

Is there such thing as "program complexity-bounded" computational complexity classes?

Any information related to the topic is much appreciated.
Is this an active research area? What are open problems?
References to textbooks, research articles? etc.

(Googling this, all I find is "resource-bounded Kolmogorov complexity" etc., but that seems to be the exact opposite of what I am looking for...)

EDIT:
Some context: In the field I am working in the argument "simple algorithms cannot possibly perform as good as complex ones", is often quoted to motivate unnecessarily complex approaches. While this is by itself an insufficient argument, I can understand that some problems indeed might require a minimal complexity to be solved (efficiently?). However, I was wondering whether there were any general theoretical results supporting this notion, or research being performed in this direction.

Elaborating on my comment as suggested by OP:

Let us start by giving definitions to the two definitions for program complexity as suggested by the other commenters and me.

Definition (Kolmogorov complexity of $L$): Let $L$ be some language. We define the Kolmogorov complexity $K(L)$ of $L$ to be the (description) length of the smallest program which decides $L$ (using some fixed programming language) or $\infty$ if no such program exists.

Definition (State complexity of $L$): Let $L$ be some language. We define the state complexity $S(L)$ of $L$ to be the minimal number of states a TM which decides $L$ needs to have or $\infty$ if no such TM exists.

The first observation we make is that there are only finitely many programs of length $n$ (and the same holds for Turing machines if we fix the alphabets and state names). It follows that any infinite class $\mathcal C$ of languages and any $m \in \mathbb N$, there is some language in $\mathcal C$ which has a Kolmorogov complexity which is at least $m$ (and the same holds for state complexity).

Indeed, this means that even problems which can be decided in constant time can have an arbitrarily large program complexity, which makes me pessimistic about the existence of results that imply that a large program complexity incurs a large runtime complexity. What about the converse statement?

The same argument from above yields directly that if we have two (infinite) decidable complexity classes $\mathcal{C}_1$ and $\mathcal{C}_2$, then for any $L_1 \in \mathcal{C}_1$ there must exist some $L_2 \in \mathcal{C}_2$ with $K(L_2) > K(L_1)$ (and the same result holds for state complexity) as $K(L_1)$ is finite (by decidability) and he program complexity for any infinite complexity class is unbounded. Even stronger, it follows that there exist infinitely many such $L_2$ and the difference in program complexity can be arbitrarily large (again by the first observation). In particular, one can deduce that for any decidable language, there exist infinitely many languages with (arbitrarily) larger program complexity but constant time complexity.


Is an algorithm with an approximation factor of 4000 useful? A paper published in SODA this year (2019) proposed a constant approximation algorithm for the lower bounded facility location problem with general lower bounds.

To my surprise, when reading the paper, I verified that its constant approximation factor is 4000.

Therefore, I was left wondering if this algorithm is really useful for something.
Like, do you know, a solution that is 4000 times worse than the optimal solution can be anything, and probably a solution given by a simple polynomial-time greedy algorithm will be better than that of given by this more complex approximation algorithm.

A very good question! While I think a feasible solution which is 4000 times worse than the optimum is often not very practical, if you have several approximation algorithms to choose from, I would rather implement the one with a better performance guarantee. Well, maybe not always. At the very least, the feasible solutions found are often of much better quality than the guarantee. That is, if an algorithm performs better than terribly in the worst case, it often performs very well in practice. At least I've read something along those lines.

Apart from that, you can think of the result as a mathematical theorem, which may be of interest in its own right. Citing the wikipedia article on approximation algorithm:

  The desire to understand hard optimization problems from the perspective of approximability is motivated by the discovery of surprising mathematical connections and broadly applicable techniques to design algorithms for hard optimization problems. One well-known example of the former is the Goemans-Williamson algorithm for Maximum Cut which solves a graph theoretic problem using high dimensional geometry.


Time complexity with irrational exponent? Is there any natural problem in P for which the best known running time bound is of the form $O(n^\alpha)$, where $\alpha$ is an irrational constant?

While admittedly I haven't done the analysis, and this is not strictly a decision problem, I am willing to wager the best known matrix multiplication algorithms (by Coppersmith, Winograd, Stothers, Williams, et al) have irrational exponent.

This can be seen more clearly in the simple case of Strassen's algorithm, which has running time $O(n^{\log_2 7})$.

And, this is not precisely what you asked, but Ryan Williams has shown that all algorithms that solve SAT in space $n^{o(1)}$ require time $n^{2 \cos(\pi/7) - o(1)}$, which is another interesting and unusual appearance of an irrational constant in TCS.


Bi-criteria combinatorial approximation algorithms for min k-vertex cover Min k-vertex cover: Given a graph $G = (V,E)$, the goal of the min k-vertex cover problem is to output $k$ vertices from $V$ such that the number of uncovered edges in $E$ is minimized.

It is easy to see that this problem is inapproximable unless studied in a bi-criteria setting. We know a very simple LP-rounding algorithm for this problem that is a $(3,3)$ bi-criteria approximation.

Q. Has this problem been studied in the literature elsewhere, perhaps with a different name? Are there any known combinatorial approximation algorithms for this problem?

Clarification: The objective of this problem is to output a set of vertices $S$ that minimize the number of uncovered edges in $G = (V,E)$. The number of uncovered edges is equal to the number of edges in $E$ that have neither end point in $S$.

Partial Vertex Cover (PVC) solves the problem without the need for bi-criteria. In PVC the input is a graph $G=(V,E)$ and an integer $m' \le |E|$ and the goal is to find a minimum cardinality subset $S$ of vertices such that they cover at least $m'$ edges. Hence, if $m' = |E|$ we have the usual Vertex Cover problem. A $2$-approximation is known for PVC. To solve the OP's question, if we know the number of edges that are not covered by an optimum solution consisting of $k$ vertices (which we can guess), say $\ell$, we set $m' = |E| - \ell$ and run the approximation algorithm for PVC. We will obtain a set $S \subseteq V$ of cardinalty at most $2k$ such that no more than $\ell$ edges are uncovered.


Decidability of rank-k polymorphism vs. System F There's a paper by Kfoury from 1992, "Type Reconstruction in Finite Rank Fragments of
the Second-Order $\lambda$-Calculus", that proves that type inference for Curry-style rank-$k$ polymorphic lambda calculus is undecidable if $k \ge 3$. My thought was that since there must be terms that can be typed in rank-3 but not rank-2, and since System F is rank-$n$ (i.e. the union of all finite rank-$k$), surely this implies that Curry-style System F type inference is undecidable as well. However, its undecidability isn't proven until 1996 by Wells in "Typability and Type Checking in the Second-Order $\lambda$-Calculus Are Equivalent and Undecidable", which explicitly mentions Kfoury's paper (along with others) and states that decidability of both type inference and type checking have not yet been proven until then.

So given that rank-3 polymorphic lambda calculus is a fragment of System F, why doesn't the former's undecidability imply the undecidability of the latter?

The conclusion of [Kfoury & Tiuryn 1992] says (emphasis mine):

  We prove that [...] for every $k\ge 3$ there is a typing of constants
  that assigns types in $S(1)$ such that the type reconstruction problem
  for $\Lambda_k$ extended by this typing is undecidable.
  Unfortunately, this result does not give any clue as to whether type
  reconstruction for $F_2$, with or without constants, is decidable.
  Our decidability/undecidability proofs use in an essential way the apriori information about the rank of types.

So, if you don't force constants to have certain pre-defined types of known rank, or if you don't have constants at all, the problem may become easier (than undecidable). The proofs rely on having constants that are forced to have certain types. (Of course, as you pointed out, Wells showed that the problem isn't easier.)


Did Alan Turing's student Robin Gandy assert that Charles Babbage had no notion of a universal computing machine? Robin Gandy was a student of Alan Turing.

Gandy did an analysis of Babbage's Analytical Engine (see 'Gandy
- The Confluence of Ideas in 1936' quoted in 'Herken, Rolf - The Universal Turing Machine—A Half-Century Survey. Springer Verlag') - and said it did (cf. p. 52–53):

The arithmetic functions +, −, ×, where − indicates "proper" subtraction x − y = 0 if y ≥ x.
Any sequence of operations is an operation.
Iteration of an operation (repeating n times an operation P).
Conditional iteration (repeating n times an operation P conditional on the "success" of test T).
Conditional transfer (i.e., conditional "goto").

Then he states

  the functions which can be calculated by (1), (2), and (4) are precisely those which are Turing computable.

(p. 53).

Then he states:

  … the emphasis is on programming a fixed iterable sequence of arithmetical operations. The fundamental importance of conditional iteration and conditional transfer for a general theory of calculating machines is not recognized…

Gandy p. 55

I'm assessing the scope of Gandy's claim here. (Whether it is right or wrong). He seems to be stating that although Babbage seems to have stumbled onto a notion of Turing Completeness (can express any program using (1), (2) and (4) - he didn't have a notion of a Computable Function. (Perhaps Gandy was saying that since the work of Babbage was prior to the work of Hilbert and Godel, he didn't have the mathematical tools to tie down the definition of a universal computing machine.)

My question is: Did Alan Turing's student Robin Gandy assert that Charles Babbage had no notion of a universal computing machine?

No, the opposite. This quote of Gandy's is not referring to Babbage, but to some intervening proposals for universal-style computing between Babbage and Turing. Gandy says those proposals did not have Babbage's recognition of the importance of branching and iteration to universal computation.

In "The Confluence of Ideas in 1936" by Gandy, as printed in the book "The Universal Turing Machine - A Half Century Survey", Section 2 is "Babbage and His Followers".

Here Gandy emphasizes that Babbage did understand and respect "conditional iteration" and "conditional transfer", e.g. end of p53 and top of p54

  Although Babbage mentions conditional transfer (67-68), he, with a natural respect for well-structured programming, uses only conditional iteration[....] He states conditional transfer explicitly (240), allowing that a 'go to' instruction may have to be executed by ringing a bell to summon the attendant; he gives an example of its use (241).

(Here Gandy refers to the article by Menabrea 1842 on Babbage's engine, but seems to attribute the ideas to Babbage himself.)

Gandy then quotes Babbage

  That the whole of the development and operations of analysis are now capable of being executed by machinery.

and writes

  Babbage, in his work on general algebra and functional equations, had shown
  his ability to think in abstract terms. If, then, one had led him to speculate (not
  difficult!) on what could be done with an abstract machine, free from limitations on
  its storage, he would surely have assented to a version (based on Sections 2.1.(1)-(5)) of Church's thesis.

Then Gandy goes on to Section 2.3, "Subsequent developments." He writes

  Other authors, concerned
  with more practical machines, referred to Babbage's work. Examples from Ran-
  dell 1982 are: M. d'Ocagne [1922], L. Couffignal [1933], V. Bush 1936, H.H. Aiken
  11964] (which is an unpublished memorandum of 1937). But the emphasis is on
  programming a fixed iterable sequence of arithmetical operations. The fundamental
  importance of conditional iteration and conditional transfer for a general theory of calculating machines is not recognized, though the principles may be used in very particular contexts [....]

Finally, Gandy writes:

  Conclusions. Babbage asserted what was, in effect a version of Church's thesis. His work was never entirely forgotten, but its theoretical importance - its importance, so to speak, as software - was little recognized[....]


What's the difference between proving weak normalization and implementing evaluator? Implementing an normalization (cut elimination) procedure for a type system A in a language with a total type system B, automatically proves cut elimination for type system A since the implementation will be total.

What's the difference between proving weak normalization and implementing the evaluator?

If there is none, is that effect also present in proving consistency of all the mathematical proof systems?

The same question in a strong normalization setting:
If the host language is strongly normalizing does strong normalization of client language follows?

If you implement an evaluator for the terms of a language $A$ in a total system $B$, and you have furthermore proven that your evaluator is correct, that is for every $t$ well-typed in $A$,

$$\mathrm{eval}(t) \simeq_A t $$

where $\simeq_A$ is the equality in $A$, then you have only shown that $\simeq_A$ is decidable.

If furthermore $\simeq_A$ naturally leads to a notion of reduction $\rightarrow_A$, and $\mathrm{eval}(t)$ is always in normal form, then you have proven that every term $t$ in $A$ is equivalent to a term in normal form.

This is enough for consistency of $A$ but is not equivalent to weak normalization, unless $\rightarrow_A$ is furthermore church-rosser!

This is essentially the approach taken by normalization by evaluation.

A proof of weak normalization in a constructive logic naturally leads to an evaluator, as every $\forall\exists$ statement leads to an algorithm (correct by construction).

There is a nice article by Ulrich Berger, Program extraction from normalization proofs, which implements this idea for simply typed $\lambda$-calculus.

For your second question, here is a counter example. Consider the language $A$ to have only two terms, $\Delta$ and $\bot$, with the reduction rules

$$\Delta\rightarrow \Delta $$
$$\Delta\rightarrow \bot $$

Feel free to add types if you like. The computation rules are weakly normalizing and confluent.

In Coq, you might write the eval function thus:

Fixpoint eval (t : A) : A :=
  match t with
     | Delta => Bottom
     | Bottom => Bottom

It's not too hard to prove that if $t\leftrightarrow^* u$ then eval(t) = eval(u). Coq's reduction can be taken to be non-deterministic, in which case you have a counter-example to the SN "inheritance" that you expect.


Finding self-similar homomorphisms of a FSM transducer Consider a special case of homomorphisms of FSM transducers (or "generalized sequential machines" in [1]). Let $F$ be a transducer accepting a language $L$, and let $h(x)$ be a homomorphism function which maps from $\Sigma \to \Sigma^*$. (Here, $h(x)$ is extended in the standard way to strings, $h(\epsilon)=\epsilon, h(x c) = h(x) h(c)$, where $x$ is a string and $c$ is a symbol from $\Sigma$.) Let $f(x)$ be the output of $F$ on $x$.

  Problem: Given $F$, find a non-trivial $h(x)$ such that for all $x \in L$, $h(f(x))$ = $f(h(x))$.

Call this a self similar homomorphism (SSH). Has this been studied anywhere? I'm looking for any (partial) insight, or related or nearby references on the following:

  What is an algorithm for finding an SSH? What is its complexity?
  What are sufficient and/or necessary conditions for a solution?
  Are there any applications?

[1] Introduction to automata theory, languages, and computation / Hopcroft & Ullman

I guess I'm a few years late with this answer but here goes:

Every homomorphism $h:\Sigma\rightarrow\Sigma^{*}$ has a corresponding deterministic transducer with a single state $q$ (which is accepting) such that on each transition $\delta(q,\sigma)=q$, the machine outputs $h(\sigma)$. In this case the machine $F$ implements the total function $h:\Sigma^{*}\rightarrow\Sigma^{*}$.

The other direction does not hold since $F$ may define a partial function $f:\Sigma^{*}\rightharpoonup\Sigma^{*}$. While the set of regular languages is closed under homomorphism, a single language is not necessarily closed under an arbitrary homomorphism, so there is no gaurantee that $h(x)\in L$. Additionally the function $f$ should really be defined as taking two arguments $f(x,q)$ since the output is dependent on the combination of symbol and state. As such, I think $F$ must define a homomorphism for there to exist an $h$ such that $h(f(x))=f(h(x))$ holds, in which case $L=\Sigma^{*}$, or $L$ must be closed under both $h$ and $f$. In the latter case $L$ would have to be captured by some regular expression that is a concatention of some number of sub-expressions of the form $e_{1}^{*}\cdot...\cdot e_{n}^{*}$, where each $e$ is either a single symbol or a disjunction or a concatenation of kleene star terms similar to the top level expression, otherwise the language would not be closed under the given functions.


Why do we need PAP (partial aplication) objects in heap? In the paper “Making a Fast Curry: Push/Enter vs. Eval/Apply for Higher-order Languages” by Simon Marlow and Simon Peyton Jones it is told that a PAP heap object may be created in the push/enter model (Figure 2. “The evaluation rules.” “Rules for push/enter.”). It is created “if there aren’t enough pending arguments on the stack.” I can't figure out an example of a type correct program which execution may lead to such a situation.

Functions can be partially applied, so you can end up with a situation in which a function is called with "not enough" arguments. For example, consider the map functional:

(* map : ∀α,β. (α → β) → list α → list β *)
let rec map f xs =
  match xs with
  | []      -> []
  | x :: xs -> (f x) :: map f xs

This will take a function f as an argument, and then pass it one argument, once for each element of the list. Now, consider a two argument function foo:

(* val foo : int → int → int *)
let foo x y = 2*x + y

Then, if you map foo over a list of integers:

(* val bar : list (int → int → int) *)
let bar = map foo [1; 2; 3]

You get a thunk (because this paper is about lazy evaluation). To force one of these thunks, you need to scrutinize the list to get its head, and then force the evaluation of the head by applying it:

 let baz = match bar with
           | f :: fs -> f 6

Now, scrutinizing bar will get you f bound to THUNK (foo 1), and fs bound to map foo [2;3]. Then, to apply f 6, we first evaluate foo 1. This pushes 1 on the stack, and since foo is really a two-argument function, foo 1 will not evaluate further -- it will return a fresh p, bound to PAP(foo 1).

Now the result is the thunk THUNK(p 6) -- to drive evaluation further, you have to demand this thunk.


Finding largest subgraph that contains a given edge and admits a cycle cover I am wondering whether there exists a fast algorithm for the following problem.

  Given a digraph $G$ possibly with loops (that is edges that begin and
  end at the same vertex) and the choice of an edge $e \in G$, what is
  the largest (in terms of number of vertices) subgraph of $G$ that
  contains $e$ and admits a vertex disjoint cycle cover.

ps: sorry for the crosspost, but I originally posted at at stackoverflow and was directed here for a possibly more appropriate crowd...

Deterministically, you can do it as follows: Give your edge $e$ the weight $n+1$ and add a self-loop of weight zero to each node that does not have one so far. Existing edges get weight one. By removing the weight zero loops,
a maximum weight cycle cover in the new graphs induces a partial cycle cover in the old graph that (1) contains your edge $e$ and (2) has a maximum number of edges. The vertices of the partial cycle cover induce the graph you are looking for. If the cycle cover in the new graph does not contain $e$ at all, then
there is no such subgraph.

You can compute a maximum weight cycle cover by reducing it to maximum weight perfect matching.


What are some efficient algorithms for determining if a system of quadratic multivariate polynomials have a solution? I know that in the general case it isn't efficient. However, I'm wondering if there are any good techniques in the quadratic case over the reals, specifically if there is a polynomial time solution.

This problem is NP-hard, as can be shown by a straightforward reduction from SAT.

It sounds like you are interested in the case of $m$ quadratic equations on $n$ variables (over $\mathbb{R}$).  In practice, the hardness of this problem depends on the relationship between $m$ and $n$:

If $m = \Theta(n)$, this problem is believed to be very hard (say, exponential in $n$).
If $m \ge n^2/2$ (roughly), this problem is easy and can be solved through linearization: replace each quadratic monomial $x_i x_j$ with a new variable $t_{i,j}$, then use Gaussian elimination.
If $m = \Theta(n^2)$, this problem can be solved in polynomial time through relinearization.  Roughly speaking, you linearize as above; then, for each $i,j,k,l$, you add constraints $t_{i,j} t_{k,l} = t_{i,k} t_{j,l} = t_{i,l} t_{j,k}$, which are themselves quadratic equations.  This gives you a new system of quadratic equations in the variables $x_i$, $t_{i,j}$.  Now you can apply linearization (or recursively apply relinearization) to this system of quadratic equations.  For details, see my explanation elsewhere and the reference into the literature there: https://crypto.stackexchange.com/a/3736/351
If $m = \omega(n)$ and $m = o(n^2)$, I don't know what the complexity is.

There are also Grobner basis algorithms, the XL and XSL algorithms, and probably others as well.  I don't know if there are any provable, useful running time bounds for any of them for any useful parameter ranges.

Incidentally, you probably don't want to work over the real numbers (where even testing equality is hard), but over the rationals or the integers or some finite field.


Behaviour of Labelled Markov Processes Labelled Markov Processes (LMP) seem to be a generalization of Probabilistic Automata (PA) studied by Segala to the case of the general state space. Namely, any LMP is given by a be a finite set of labels $A$, a measurable state space $(X,\mathscr B(X))$ and substochastic kernels
$$
  \forall a\in A,\;\tau_a:X\times \mathscr B(X)\to [0,1].
$$
In case $X$ is finite and $\mathscr B(X) = 2^X$, we obtain simply a PA.

The behavior of the PA is clear to me: it is given by trace distributions over the sequences of labels - e.g. in Section 3 here. I would expect the very same definition of the behavior for LMP, but I have never seen it defined formally anywhere. I would appreciate if you can hint upon a source describing the behaviour of a LMP.

Updated: after a short discussion, I have to clarify some details. I am familiar with measure-theoretical approach to probability and stochastic processes, and I think that behavioral semantics of PA extends directly to LMP modulo dealing with Borel or universally measurable transition kernels to characterize an adversary. However, I am not sure whether this is a possible way to define a behavior of LMP, or it is the intended one. For example, it may perhaps be described in the PhD thesis of J. Desharnais (which I do not have an access to).

[Comment space was too short]

I think it depends on what you mean by behaviour. Probabilistic automata follow in the tradition of finite automata, so their behaviour is defined in terms of their language or traces. Labelled Markov Processes follow in the tradition of process algebra, where it is known that processes can be compared using a variety of preorders typically starting with bisimulation. You do have notions of bisimulation defined for LMPs and in that paper. Bisimulation is stronger than trace equivalence, as you may know, so the behaviour you are interested in is the tree unfolding rooted at a given state. Definition 3.1 of the paper you have linked gives approximations of this tree.


Are there "NP-Intermediate-Complete" problems? Assume P $\ne$ NP.

Ladner's Theorem says that there are NP Intermediate problems (problems in NP that are neither in P nor NP-Complete).  I have found some veiled references online that suggest (I think) that there are many "levels" of mutually reducible languages within NPI that definitely do not all collapse into one.

I have some questions about the structure of these levels.

Are there "NP-Intermediate-Complete" problems - that is, NP-Intermediate problems to which every other NP-Intermediate problem is polytime reducible?
Sort NP - P into equivalence classes, where mutual reducibility is the equivalence relation.  Now impose an ordering on these equivalence classes: $A > B$ if the problems in $B$ reduce to problems in $A$ (so clearly the NP-Complete equivalence class is the maximum element).  Is this a total ordering (i.e. the problems are arranged in an infinite descending chain)?  If not, does the "tree structure" of the partial ordering have a finite branching factor?
Are there any other interesting known structural components of NP - P?  Are there any interesting open questions about the underlying structure?

If any of these are currently unknown, I would be interested to hear that as well.

Thanks!

I don't really have references for these results--they aren't hard to prove once you understand Ladner's theorem.

No, for any NP-incomplete set A there is another set B strictly between A and SAT.
These equivalence classes are known as polynomial-many-one degrees. You can embed any finite poset into the degrees below NP. In particular the degrees are not totally ordered or finitely branching.
This all depends on what you mean by "interesting". There is a huge theory of the degree structure of the computable sets (see Soare's book for instance) and many of those questions have not been ported down to polynomial-time sets. For instance, can you have NP sets A and B whose join is equivalent to SAT and whose meet is equivalent to the empty set?


A direct sum theorem for Resolution clause space complexity? Resolution is a scheme to prove unsatisfiability of CNFs.  A proof in resolution is a logical deduction of the empty clause for the initial clauses in of the CNF.  In particular any initial clause can be inferred, and from two clauses $A \lor x$ and $B \lor \neg{x}$ the clause $A \lor B$ can be deduced as well.  A refutation is a sequence of deductions which ends with an empty clause.

If such refutation is implemented, we can consider a procedure that keeps some clauses in memory.  In case a non-initial clause must be used again and it is not in memory anymore, the algorithm should must it again from scratch or from the ones in memory.

Let $Sp(F)$ the smallest number of clauses to be kept in memory to reach the empty clauses. This is called the clause space complexity of $F$. We say say that $Sp(F)=\infty$ is $F$ is satisfiable.

The problem I'm suggesting is this: consider two CNFs $A=\bigwedge_{i=1}^m A_i$ and $B=\bigwedge_{j=1}^n B_j$, and let the CNF

$$A \lor B = \bigwedge_{i=1}^m \bigwedge_{j=1}^n A_i \lor B_j$$

What is the relation of $Sp(A \lor B)$ with $Sp(A)$ and $Sp(B)$?

The obvious upper bound is $Sp(A \lor B) \leq Sp(A) + Sp(B) -1$. Is this tight?

I wanted to post this as a comment, but since I cannot quite figure out the way to do so I guess it will have to be an "answer" instead.

I agree that the question is nice. Of course, the same question can also be asked about the length of resolution refutations (i.e., the number of clauses occurring in the refutation, counted with repetitions) and the width of refutation (i.e., the size of, or number of literals occurring in, the largest clause in the refutation).

In all of these cases there are "obvious" upper bounds, but it is not clear to me whether one should expect matching lower bounds or not. Therefore, I wanted to add one question and one comment.

The question concerns refutation length. It seems reasonable to believe that the bound for length stated in the comment by Massimo is tight, but do we know this?

And the comment concerns width. Note that for this measure, a moment of thought reveals that a direct sum lower bound does not hold. For width, one instead refutes the whole $A$-formula for each clause $B_i$, in width $w_A$, say, plus the width of the $B$-formula, and then one refutes the $B$-formula in width $w_B$. Assuming that both formulas have constant initial width, the width of the refutation of the direct sum will be essentially $\max (w_A, w_B)$.

This is of course an easy observation, but the point is that it might indicate that the question for space could be tricky. This is so since almost all lower bounds on space in refutation we know of go via width lower bounds. (That is, the space lower bounds were derived independently, but with hindsight they all follow as a corollary from the beautiful paper "A Combinatorial Characterization of Resolution Width" by Atserias and Dalmau.) But if there is a direct sum theorem for resolution clause space, it will not follow from width lower bounds but has to be argued directly, which at least so far has seemed to be much harder. But of course there might be some easy argument that I am missing.


Example of R and G when $R \subseteq L(G)$ is undecidable Could anybody provide an example of regular language R and context-free grammar G such that $R \subseteq L(G)$ is undecidable. Of course, if such language could be constructed.

Thanks.

Given an $R$ and a $G$, one can easily construct a TM which outputs whether $R \subseteq L(G)$.

(Consider two TMs, one that just rejects and one that just accepts. If not the first, then the second TM would definitely be correct.)

What is not possible is this: Give a TM that takes as input any $R$ and any $G$ and accepts iff $R \subseteq L(G)$ and rejects otherwise.

Note that the same is true for the halting problem. Given a TM $M$, it is decidable whether $M$ halts or not. (The same two TMs mentioned above would do.) What's undecidable is the general problem of being able to decide whether a TM given as input halts or not. (A single machine that can take any TM as input and be correct on all of them.)


Stable Marriage with incomplete lists and ties - NP-hardness According to [1] finding a weakly stable matching in a stable marriage (or SM) instance with incomplete lists and ties is NP-Hard.

According to [2] a weakly stable matching in a hospital-residents (or HR) instance with ties always exists and one can be found by arbitrarily breaking the ties and applying one of the known algorithms for the HR problem.

Also HR with ties is a generalization of SM with incomplete lists and ties.

Isn't there a conflict here?

[1] K. Iwama, D. Manlove, S. Miyazaki and Y. Morita. Stable Marriage with Incomplete Lists and Ties. Automata, Languages and Programming, Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 1999

[2] R. W. Irving, D. F. Manlove, and S. Scott. The Hospitals/Residents Problem with Ties. Algorithm Theory - SWAT 2000. Lecture Notes in Computer Science. Springer Berlin / Heidelberg

[3] V. Bansal , A. Agrawal , V. S. Malhotra. Polynomial time algorithm for an optimal stable assignment with multiple partners. Theoretical Computer Science 379 (2007) 317–328

[4] D.F. Manlove, R.W. Irving, K. Iwama, S. Miyazaki, and Y. Morita. Hard variants of stable marriage.Theoretical Computer Science 276(1-2):261-279.

The stable marriage instance with ties is solvable in polynomial time, whereas the stable marriage instance with incomplete lists and ties is NP-hard.

The same holds for the Hospitals/Residents problem.  So there is no conflict between [1] and [2].


Was the reason that Computers were invented to solve a philosophical question about the foundations of mathematics? This guy asserts:

  I’ll say it — the computer was invented in order to help to clarify … a philosophical question about the foundations of mathematics.
  (This problem being Entscheidungsproblem - The Decision Problem)

The reference here states that the Church-Turing thesis was attempting to answer this question.

My question is - is it true that modern computers are a byproduct of trying to solve 'The Decision Problem'?

(My intuition told me that modern computers were more a byproduct of trying to break Nazi encryption codes). (perhaps with some pre-war German influence).

Just an extended comment, for those who didn't notice that "This guy" in the question is not the author of the linked blog, but refers to Gregory Chaitin.

The sentence is from the lecture: A Century of Controversy over the Foundations of Mathematics; the transcription can be found here.

It seems interesting (I'm going to read it now)!

...
Okay, I'd like to talk about some crazy stuff. The general idea is that sometimes ideas are very powerful. I'd like to talk about theory, about the computer as a concept, a philosophical concept.

We all know that the computer is a very practical thing out there in the real world! It pays for a lot of our salaries, right? But what people don't remember as much is that really---I'm going to exaggerate, but I'll say it---the computer was invented in order to help to clarify a question about the foundations of mathematics, a philosophical question about the foundations of mathematics.

Now that sounds absurd, but there's some truth in it. There are actually lots of threads that led to the computer, to computer technology, which come from mathematical logic and from philosophical questions about the limits and the power of mathematics....


Can a totality checker be used to guarantee a proof on the calculus of constructions + inductive types is correct? If we extend the Calculus of Constructions with Fix, we gain a lot of expressivity for barely no added complexity. That includes being able to derive induction, perform large eliminations, prove 0 != 1 and so on. This system is, moreover, very user-friendly and comfortable to program in. Sadly, nothing of that because the resulting system becomes inconsistent. Making it consistent again requires, it seems, a lot of added complexity such as, for example, inductive types, or positive recursion checks + constructor-constrained recursive types + lift.

Suppose, though, that someone gives me a term T of type MyTheorem, programmed in that language (CoC + Fix), and that this term successfully pass through a totality checker. Wouldn't I be able to, then, trust, with absolute certainty, that MyTheorem holds? And, if that is true, doesn't that mean that, as long as that totality checker is used, one can just program on that comfortable language instead of dealing with the added complications of induction types and so on?

I'm going to assume that by $\mathrm{Fix}$ you mean a new type constructor

$$\frac{\Gamma\vdash F:*\rightarrow *}{\Gamma\vdash \mathrm{Fix}\ F:*} $$

Along with the conversion rule $\mathrm{Fix}\ F\simeq F\ (\mathrm{Fix}\ F)$. This is often referred to as equi-recursive types as opposed to iso-recursive types, where the conversion rule does not exist, and you need additional $\mathrm{fold}$ and $\mathrm{unfold}$ constructs to use $\mathrm{Fix}$.

I'll ignore the fact that the rule for $\mathrm{Fix}$ is non-terminating on it's own, since this isn't that harmful. You question about terms

$$\Gamma\vdash t:A$$
with
$$\Gamma\vdash A:*$$

when are they sound proofs of the statement $A$?

You suggest using a "totality checker", to sidestep the need for messy rules such as positivity and various other restrictions when dealing with iso-recursive types.

The first remark is that simply checking termination of a term $t$ won't do: we can easily build a proof of $\forall n:\mathbb{N}. n = 0$ which has a normal form, but loops when applied to some natural number! So we really do need to check totality, which involves proving that $t$ will not lead to non-termination when placed in an arbitrary well-typed context.

Sadly, we don't really know how to do this, other than building back in all those nasty restrictions you want to avoid! For positivity for example, taking $\Lambda=\lambda X:*.X\rightarrow X$, then you can type
$$\vdash \lambda x:\mathrm{Fix}\ \Lambda.x\ x:\mathrm{Fix}\ \Lambda $$

which smells like trouble: your totality checker had better reject that as a theorem.

The other restrictions will crop up pretty quickly.

As a side note, if you can prove something using some "reasonable" totality checker (provably correct in HOL) then you can actually "reverse engineer" a proof in CoC + $\forall n. S\ n\neq 0$, by internalizing the totality check. This technique is similar to realizability, where there is a correspondance between provably total functions and $\Pi^0_2$ theorems.

As a side note that came up in the comments, it seems to me that when restricting $\mathrm{Fix}$ to positive type constructors, i.e. type constructors $F$ for which (for each variable $f$) there exists a term $t_f$ such that

$${A:*,B:*,f:A\rightarrow B\vdash t_f:F\ A\rightarrow F\ B} $$

then there is no encoding of $\mathbb{N}$ such that induction over $\mathbb{N}$ holds.

The rough argument for this is to encode $\mathrm{Fix}\ F$ by
$$\forall X, (F\ X\rightarrow X) \rightarrow X$$
which is the usual encoding for positive inductive types in system F, and show that every well typed term in the system with $\mathrm{Fix}$ can be well typed in the CoC without it. Then we can conclude by the fact that CoC doesn't have any inductive definitions of $\mathbb{N}$ itself.

The encoding is a little messy, though, I think. I'd be happy to have a reference for this.


Computing the edge orbits of a graph (and discussing definitions) A (vertex) automorphism in a graph $G=(V,E)$ is a permutation $\sigma$ of the vertices that preserves adjacency, namely $\sigma(u) \sigma(v) \in E$ if and only if $uv \in E$. The automorphisms of a graph induce a partition of the vertices into orbits, where two vertices belong to the same orbit if and only if there exists an automorphism that takes one to the other. Intuitively, the orbits correspond to vertices that are structurally equivalent in the graph (one also says symmetrical). For example, in the left graph $G$ below, there are three orbits: $\{a\}$, $\{b\}$, and $\{c,d\}$.

The present question focuses on the analogue concept for edges. Several definitions of edge automorphisms seem to co-exist, which confuses me. For instance, Wolfram MathWorld
(link) defines an edge automorphism as a permutation of the edges that preserves adjacency among the edges (where two edges are adjacent iff they share an endpoint). Accordingly, the edge automorphism group of a graph is defined as the vertex automorphism group of its line graph.
What troubles me with this definition is that edges such as $ab$ and $cd$ in graph $G$ end up being in the same orbit of the edge automorphism group even though they are not symmetrical, because the corresponding vertices in the line graph $L(G)$ are (see the right-side picture). In fact, this definition seems to clash with that of edge-transitive graphs, where the concept of automorphism relates to symmetry, not adjacency. For the sake of disambiguation, I will subsequently refer to these two versions of edge automorphisms as adjacency-based versus symmetry-based.
Now, my questions:

Is there something wrong with my understanding of edge automorphisms, or is there inherently two different concepts considered in the literature? In the first case, please kindly point me to the mistake.

The actual motivation for posting the present question was to find a way to compute the symmetry-based version of the edge orbits of a given graph. Initially, I was computing them by reducing the problem to computing the vertex orbits of the line graph (as prescribed by the MathWorld definition), then calling standard automorphism routines on existing software like SageMath... until I realize that this was not what I wanted.
Of course, I do not expect an efficient algorithm for this problem, but any conceptually simple algorithm or reduction to another natural question would be much appreciated.

(Bonus question.) In the particular case that the edges are properly colored, are there reasons to believe that there could be an efficient way to compute the symmetry-based, color-preserving edge orbits? In fact, I could not find anything related even to classical automorphisms of properly vertex-colored graphs, so any pointer related to this natural case is also welcome.

It turns out that yes, indeed, there are two possible definitions for edge-automorphisms... but it turns out that they almost always coincide so that it seems that people often get away with not making the distinction.

First, some notation. For a simple graph $G = (V,E)$ we let $\Gamma_V(G)$ define the group of automorpisms over the set of vertices $V$ that preserve $G$'s edge structure. Similarly, we define $\Gamma_E(G)$ to be the group of automorphisms over the set of edges $E$ that preserves $G$'s edge incidence structure.

For any vertex-automorphism $\pi \in \Gamma_V(G)$, we observe that there is a natural edge-automorphism $\pi':E \to E$ induced by $\pi$. Let $\Gamma'_V(G)$ denote the group of such induced edge-automorphisms.

  Theorem: $\Gamma'_V(G)$ is isomorphic to $\Gamma_E(G)$ for all simple, connected $G$ with three or more vertices, with three exceptions: $K_4$, $K_4$ with one edge deleted, and the graph illustrated above within the question.

In other words, the example presented in the question happens to be on one of the very few graphs that make the distinction between $\Gamma_E(G)$ and $\Gamma_V'(G)$ important. Also, it is trivial to observe that this isomorphism does not hold for graphs with two or fewer vertices.

I believe that the canonical reference for this result is [1], though the proof is somewhat complicated with several cases. There are references to some more streamlined proofs of this result in [2], but I haven't tracked those down.

Whitney, Hassler. "Congruent Graphs and the Connectivity of Graphs." American Journal of Mathematics 54.1 (1932): 150-168.
Hemminger, R. L. "On Whitney's line graph theorem." The American Mathematical Monthly 79.4 (1972): 374-378.


Complexity of finding minimal cover of FDs Given a relational database and the problem is to generate some minimal cover (i.e. the minimal (by cardinality) set of functional dependencies that all other FD follows from them by Armstrong rules) in output polynomial time.

It's look like that this problem can not be solved in output polynomial time unless $P=NP$, but I couldn't find any papers about it.

It seems like this problem may be known as the dependency inference problem, as described in this extended abstract of the paper "Dependency Inference" by Mannila and Raiha in VLDB '87:

  Given a relation $r$, find a set of functional dependencies that logically determines all the functional dependencies holding in $r$.

Unfortunately, it seems that this problem is intractably super-polynomial. According to the same extended abstract:

  Theorem 1. For each $n$ there exists a relation over $R$ such that
  $n = |R|$, $|r| = O(n)$, and each cover of $dep(r)$ has $\Omega(2^{n/2})$ dependencies.

In other words, you cannot guarantee that the minimal cover is sub-exponential in the size of the input.

EDIT: However, the asker is asking whether or not an output-polynomial algorithm exists (i.e.: an algorithm that runs in time polynomial in the size of the input and output). The nearest reference I can find is in the paper "Identifying the Minimal Transversals of a Hypergraph and Related Problems", SIAM J. Computing, 1995 (24) by Eiter and Gottlob.
They first define problems AP1 and AP2 where AP2 is the dependency inference problem. Then, they state the following:

  Note that problems AP1 and AP2, which are search problems in terms of complexity theory, are solvable by algorithms in output-polynomial time only if the following decision problem, which we call FD-RELATION EQUIVALENCE, is in P:

  Problem: FD-RELATION EQUIVALENCE
  Instance: A relation $R$ and a set $F$ of FD.
  Question: Does $F_R = F^+$ hold ?

  FD-RELATION EQUIVALENCE is in co-NP, but there is neither a polynomial time algorithm known for this problem nor is it proved co-NP-complete.


Restricting entries of unitary operators to real numbers and universal gate sets In Bernstein and Vazirani's seminal paper "Quantum Complexity Theory", they show that a $d$-dimensional unitary transformation can be efficiently approximated by a product of what they call "near-trivial rotations" and "near-trivial phase shifts".

"Near-trivial rotations" are $d$-dimensional unitary matrices that act as the identity on all but 2 dimensions, but act as a rotation in the plane spanned by those two dimensions (i.e. has a 2x2 submatrix of the form:

$
 \begin{pmatrix}
  \cos{\theta} & -\sin{\theta} \\
  \sin{\theta} & \cos{\theta} \\
 \end{pmatrix}
$

for some $\theta$).

"Near-trivial phase shifts" are $d$-dimensional unitary matrices that act as the identity on all but 1 dimension, but apply a factor of $e^{i\theta}$ for some $\theta$ to that one dimension.

Furthermore, they show that only one rotation angle is needed (for both the rotation and phase shift unitaries), given that the angle is an irrational multiple of $2\pi$ (BV set the angle to $2\pi\sum_{j=1}^{\infty}{2^{-2^j}}$.

Subsequent papers on quantum complexity theory (like that by Adleman et al or Fortnow and Rogers) claim that the B-V result implies that universal quantum computation can be accomplished with unitary operators whose entries are in $\mathbb{R}$.

How does this follow? I can understand that a product of near-trivial rotation matrices will give you a unitary matrix with real entries, but what about the phase shift matrices?

That is: if you are only able perform near-trivial rotations, and phase shift matrices where the entries of the matrix are either $0,\pm 1$, can we efficiently approximate all other phase shift matrices?

I suspect that this implication is not immediately obvious, and the proper proof for it would resemble the proof that Deutsch's Toffoli-like gate is universal - or am I missing something very obvious?

There is A Simple Proof that Toffoli and Hadamard are Quantum Universal by Dorit Aharonov which first shows how complex amplitudes can be simulated by real amplitudes over a larger Hilbert space with one more qubit.

"This is done by adding one extra qubit
to the circuit, the state of which indicates whether
the system’s state is in the real or imaginary part of
the Hilbert space, and replacing each complex gate
$U$ operating on $k$ qubits by its real version, denoted
$\tilde{U}$, which operates on the same $k$ qubits plus the
extra qubit. $\tilde{U}$ is defined by:

$\tilde{U}|i\rangle |0\rangle = [Re(U)|i\rangle]|0\rangle + [Im(U)|i\rangle]|1\rangle$
$\tilde{U}|i\rangle |1\rangle = -[Im(U)|i\rangle]|0\rangle + [Re(U)|i\rangle]|1\rangle$"

Secondly, she proofs the universality of the {Hadamard,Toffoli} gate set, which has only real amplitudes $\{0,1,\pm\frac{1}{\sqrt{2}}\}$.


Optimally listing of subsets Suppose I have a collection of $m$ subsets of $\{1,\dots,n\}$, all of size $k$. I want to list these subsets so that two subsets adjacent to one another in the list are as close to one another as possible in that their intersection is as small in cardinality as possible. Can I do this in $o(m^2)$ time?

Without knowing any further restrictions on the parameters, the problem is NP-hard.

Let $G = (V,E)$ be an undirected graph. For $v \in V$, define the set $S_v = \{ e \mid e \in E \mbox{ is incident to } v\}$. Then $| S_u \cap S_v | = 1$ if $u$ and $v$ are adjacent, and $|S_u \cap S_v| = 0$ otherwise. You can pad out each $S_v$ with distinct junk items until each set has the same size. Then an ordering of $\{ S_v \mid v \in V\}$ in which adjacent sets have "as large an intersection as possible" corresponds to a Hamiltonian path in $G$ (for sensible measures like maximizing $\sum_i |S_i \cap S_{i+1}|$ or maximizing $\min_i |S_i \cap S_{i+1}|$).

If you want adjacent sets to have "as small an intersection as possible", simply complement each of these sets and the same reduction also works.

Your question suggests that you think this problem can be done in $O(m^2)$, and now I'm curious why.


Implementing D* Lite for Path-Planning - How detect Edge Cost Change? I currently try implementing the D* Lite Algorithm for path-planning (see also here) to get a grasp on it. I found two implementations on the web, both for C/C++, but somehow couldn't entirely follow the ideas since they seem to differ more than expected from the pseudo code in the whitepapers. I especially use the following two papers:
Koening,S.;Likhachev,M. - D* Lite, 2002
Koenig & Likkachev, Fast replanning for Navigation in Unknown Terrain, IEEE Transactions on Robotics, Vol. 21, No. 3, June 2005

I tried implementing the optimized version of D* Lite from the first whitepaper (p.5,Fig.4) and for "debugging" I use the example as shown and explained in the second whitepaper (p.6,Fig.6 and Fig.7). All work is done in MatLab (easier for exchanging code with others).

So far I got the code running to find the initial shortest path by running computeShortestPath() once. But now I am stuck at lines {36''} and {37''} of the pseudo-code:

{36”} Scan graph for changed edge costs;
{37”} if any edge costs changed

How do I detect those changes? I somehow don't seem to have a grasp on how this is being detected? In my implementation so far, I mainly used 3 matrices.
One matrix of same size as the grid map containing all rhs-values. One matrix of same size containing similarly all g-values. And one matrix with variable row count for the priority queue with the first two columns being the priority keys and the third and fourth row being the x- and y-coordinates.

Comparing my results, I get the same result for the first run of computeShortestPath() in Step5 as seen in the second whitepaper, p.6 Fig.6. Moving the robot one step also isn't that a problem. But I really have no clue how the next step of scanning for changed edge costs should be implemented.

Thanks for any hint, advice and/or help!!!

In real-world code, you almost never have to "scan the graph for changes."  Your graph only changes when you change it in the code, so you already know exactly when and where it can change!

One common way of implementing this is to have a OnGraphChanged callback in your Graph class, which can be setup to call the OnGraphChanged method in your PathFinder class.  Then anywhere the graph changes in your Graph class, make sure the OnGraphChanged callback is called.


Extended Church's thesis and internal parametricity I am wondering if there is any known relationship between these 2 concepts in intensional MLTT as formulated here.

Does $Internal\ parametricity \implies ECT$ hold?
For forumlation of ECT see https://en.wikipedia.org/wiki/Church%27s_thesis_(constructive_mathematics), also I am wondering about the internal version of it. In particular the formulation as stated in this paper in the form compatible with univalence axiom.

This question is motivated by the results in Parametricity and excluded middle, which shows that failures of parametricity are related to axioms without computational content such as Law of excluded middle and that ECT also implies failure of Law of excluded middle.

By internal parametricity I mean the internalization of this concept ala A computational interpretation of parametricity.

I am quite sure that the opposite direction, doesn't hold. Let me outline my reasons for this
for a function $f:\forall a.a \rightarrow a$, then if internal parametricity fails for this type, $ECT$ might still hold, i.e. if $f$ analyses type of its argument and acts as $\neg$ only for bools and $id$ everywhere else, all functions should still be computable and thus $ECT$ can still be admissible.

Internal parametricity does not entail any version of extended Church's thesis. To see this, consider a presheaf model of internal parametricity, for example this one, and observe that in any presheaf model of type theory the extended Church's thesis fails (both the internal and the external one) because the object $\mathbb{N}^\mathbb{N}$ has uncountably many global points.


Proving running time upper bounds for algorithms in dependent type theory Proof assistants are a valuable tool for verifying
the correctness of proofs of mathematical theorems.

When dealing with proofs of correctness of algorithms,
one is not only interested on showing that the algorithm
indeed works correctly, but also on showing some upper
bound on the execution of the algorithm.

Can proof assistants based on dependent type theory be
used in a natural way to prove upper bounds on the
running time of algorithms (besides of course of
proving their correctness)? What is the standard approach
to do so?

If such assistants are not appropriate, is there some
other kind of proof assistant that can do the job?

Obs: When I say time, I mean the complexity theorist notion
of time, in the sense of number of steps in an idealized RAM machine.
I don't care about formalization of actual hardware and
physical time. Therefore, although Neel Krishnaswami is interesting,
I'm not accepting it because it is far more complicated than what
I'm looking for.

As usual, (a) the high-level conceptual approach is basically the same as it is on paper, but (b) mechanization makes new things reasonable to attempt.

The way you do things is to define a cost semantics for a programming language, where you assign a cost for each of the operations in the language. Next, you define a machine model, with its own cost semantics assigning costs to each of the primitive machine operations. Next, you prove that translating programs into the machine model is cost-preserving, so that the language-level costs correspond to the machine-level costs.

Then, you can take any particular program written in the language and prove things about its running time, memory usage, or whatever other costs your cost semantics tracks. You prove these things with math, the same as on paper. :)

However, once you have a computer checking all the details of all your proofs, new things become possible. For example, it is fairly common in paper proofs to only give the machine cost model, and handwave the language and its cost model (people say "pseudocode" when they don't want to specify the details of the language). But this is only plausible when the language and machine are very close to each other, and when you don't care about constant factors. If you need the compiler to make nontrivial optimizations, or if you need to reason about exact (and not just asymptotic) complexity, then you need to be more precise about the language.

A good example of this is the CerCo project, which did verified compilation from C to microcontroller assembly in a way that enabled source-level reasoning about things like worst-case execution times.


How to generalize a map of type for many operators? I am formalizing the type system for a small language, and thus writing inference rules.

Taking unary - operator for example, its entry may be a number as well as an array of number, thus there is an overloading: $-^1$ and $-^a$. Two of their typing rules are $-^1: \text{Integer} \rightarrow \text{Integer}$, and $-^a: \text{Integer Array} \rightarrow \text{Integer Array}$.

Actually there are a lot of operators like unary - operator, which can take one element as well as an array of elements as entry. I just don't know how to generalize this formalization.

For instance, when I introduce the typing rules for FACT operator, one of its rule is $\text{FACT}^1: \text{Integer} \rightarrow \text{Integer}$. I just would like to say $\text{FACT}^a$ exists, and follows "the map of type" logic as $-^a$. Does anyone know how to formalize that elegantly?

Going further for arithmetic binary operators, one rule is $\text{+}^1: \text{Integer} \rightarrow \text{Integer} \rightarrow \text{Integer}$, how could I say $\text{+}^a$ exists, and follows "a map of type" logic, which implies naturally that $\text{+}^a: \text{Integer Array} \rightarrow \text{Integer Array} \rightarrow \text{Integer Array}$?

The way Haskell solves this problem is through Type Classes (see these papers for an overview). The idea is that it is not the $\_^{-1}$ operation that is special; it is the $\mathrm{\bf Array}$ type! To this end, you can define a (statically) overloaded method $map$ which works on each such type. In Haskell:

class Mappable m where
  map : (a -> b) -> (m a -> m b)

Then you can instantiate this for arrays (in pseudo-Haskell):

instance Mappable Array where
  map f v = [f(v[i]) | i in (index v)]

By the way, this class exists and is widely used in Haskell, it goes by the name Functor (and $map$ is $fmap$ for some reason).

This solves the problem for unary operators. For binary operators, or more generally, $n$-ary operators, things get a tiny bit trickier: in this case, you need to figure out what you mean. Do you want the sum of all pairs of numbers in each array, or just the "fusion" of the arrays by the operation sum? I suspect you mean the latter. The way to solve this problem is by another Type Class named $\mathrm{\bf Applicative}$. The definition is

class Applicative m where
  pure  :: a -> m a
  fusion :: m (a -> b) -> m a -> m b

and

instance Applicative Array where
  pure x = [x]
  fusion fs v = [fs[i](v[i]) | i in index v]

The idea is that you can use map to "build up" arrays of partially applied functions, and then use fusion to apply that array of functions to an array of arguments. In the case of $+$ you can just write

fusion (map + [1;2;3]) [4;5;6]

to get what you want. I agree that this is ugly, which is why Haskell has the notation

+ <$> [1;2;3] <*> [4;5;6]

The beauty is that you can iterate this as many times as you want if your function takes more arguments. For example $\mathrm{rem\_mod}$ that computes the remainder of a number $n$ divided by $m$ modulo $r$ of type

rem_mod : Int -> Int -> Int

can be lifted:

rem_mod <$> [1;2;3] <*> [4;5;6] <*> [7;8;9]

You can find more details here. Finally, I suspect you want to be able to infer the places in which to insert the $\mathrm{pure}$, $\mathrm{map}$ and $\mathrm{fusion}$ methods. It may be possible to adapt the type-class resolution mechanism to your purposes, but I don't guarantee you can do this without additional restrictions.


Can we decide whether a permanent has a unique term? Suppose we are given an n by n matrix, M, with integer entries. Can we decide in P whether there is a permutation $\sigma$ such that for all permutations $\pi\ne\sigma$ we have $\Pi M_{i\sigma(i)}\ne \Pi M_{i\pi(i)}$?

Remarks. One can of course replace the product with a sum, the problem stays the same.

If the matrix can have only 0/1 entries, then we get the Bipartite-UPM problem which is even in NC.

Edit: Deciding whether the smallest term is unique is in P as it is equivalent to the minimum weight matching problem, as pointed out by Neal Young in a (since then removed) comment.

Edit: Similar questions:

In an edge-weighted graph, is there a Hamiltonian-cycle with a unique weight?

If we have a CNF with weights assigned to every variable/satisfying assignmet, is there a unique weight satisfying assignment?

These are of course at least NP-hard. Are these problems equivalent to the original or are they harder?

Nice problem!  It's not hard to give a reduction showing that, if one could solve your problem, then one could also solve the following problem, call it ISOLATED SUBSET SUM:

Given integers a1,...,an, is there a subset S of the ai's whose sum is not shared by any other subset?

The reduction works by first reducing ISOLATED SUBSET SUM to ISOLATED PERFECT MATCHING, where given a weighted bipartite graph G, we want to find a perfect matching whose weight isn't shared by any other perfect matching.  This reduction is simple: for each i, create a 2x2 complete subgraph Gi in G, such that which of the two possible matchings we choose for Gi encodes our choice of whether or not ai is in the set S.

Next, reduce ISOLATED PERFECT MATCHING to your problem as follows:

For all i,j, if the edge (i,j) exists and has weight wij, then set Mij:=exp(wij).  (This turns the sums into products.)
For all i,j, if the edge (i,j) doesn't exist, then set Mij:=0.
Pad M to make sure that there are two or more permutations π such that Π Mi,π(i) = 0.  (This rules out spurious solutions that don't correspond to any perfect matching in G.)

Now, ISOLATED SUBSET SUM certainly feels like it's at least NP-hard, and maybe it's even harder than that (the obvious upper bound is only Σ2P)!  Furthermore, perhaps one could prove that ISOLATED SUBSET SUM is NP-hard using a Valiant-Vazirani-style randomized reduction.  This, however, is a challenge I leave to someone else...


Succinct circuit representation of graphs The complexity class PPAD (e.g. computing various Nash equilibria) can be defined as the set of total search problems polytime reducible to END OF THE LINE:

END OF THE LINE: Given circuits S and P with n input bits and n output bits such that P(0n) = 0n != S(0n), find an input x in {0,1}n such that P(S(x)) != x or S(P(x)) != x != 0n.

Circuits or algorithms such as S and P implicitly define an exponentially large graph that is only revealed on a query-by-query basis (to keep the problem in PSPACE!), e.g. Papadimitrou's paper.

However, I don't understand how one would design a circuit that enables arbitrary graphs (if there is a systematic structure to the graph, it appears much easier to find the circuit). For instance, how would one design a polynomially-sized circuit that represents an exponentially-long directed line, with an all-0 label for the source vertex and randomly assigned binary labels to all other vertices? This seems to be implicit in the PPAD-related papers.

The closest I've come from a search online is Galperin/Widgerson's paper, but the circuit described there takes two vertex labels and returns a Boolean answer to "Are these vertices adjacent?"

So, how would you design a polynomially-sized circuit of an exponentially-sized graph that takes an n-bit input and outputs the n-bit label of its predecessor or successor, respectively? Or even, does someone know of a resource that explains this well?

Your question seems to be asking: how does one represent arbitrary graphs (or even arbitrary path graphs) as a circuit of polynomial size? The answer is, you don't. The number of different path graphs with 2n vertices is (2n)!, far more than the number of different circuits with nc gates (exponential in nc log n). So almost all graphs with this many vertices cannot be represented by a succinct circuit.

Therefore, as you hint, in some sense only graphs that have a high degree of structure can be represented in this way. That's what makes complexity classes like PPAD interesting: despite the structure that we know the input graphs to the EOL problem must have, we don't seem to know how to take advantage of the structure to solve the problem efficiently.

If I'm misunderstanding your question and you're really asking: how does one make a circuit that even meets the input requirements for EOL, for even a very highly structured graph: try the path graph that connects vertex x (considered as a number in binary) to x-1 and x+1, with ends at zero and at 2^n-1. Or if you want something less trivial that seems more difficult to solve EOL for: let E and D be the encryption and decryption functions for a fixed key in your favorite cryptosystem, let the neighbors of x in the graph be E(x) and D(x), and let the ends of the line be 0 and D(0).


Gentle introduction to the algorithmic aspects of tree-depth Treewidth and pathwidth are popular parameters, measuring the closeness of a graph to a tree or a path, respectively. Indeed, it seems treewidth is so popular it is featured in many papers, books, and lecture notes that give (even very gentle) introductions to the algorithmic aspects of treewidth (see e.g. the Downey & Fellows book). Typically, these resources explain how some NP-hard problem (e.g. independent set) is solved in polynomial time through dynamic programming on a tree decomposition.

However, it is sometimes the case a graph problem remains NP-complete for both bounded treewidth and bounded pathwidth graphs. But such hardness results don't imply hardness for bounded tree-depth, which informally measures the closeness to a star.

It seems fair to say tree-depth is not as widely known as treewidth. For someone wanting to learn more about algorithms parameterizing by tree-depth, are there (similarly to treewidth) some nice resources available for learning how such algorithms perhaps typically work?

My favorite resource for this subject is the book Sparsity by Jaroslav Nešetřil and Patrice Ossona de Mendez. It has quite a bit of material specifically about tree-depth, including algorithmic aspects. And for a more brief and quick introduction, there's always the Wikipedia article.


Is there any language for which a perfect optimization is decidable? Is there a programming language L where it is possible to write an optimizer O, that, receiving a program in L and a set of cost for every low-level operation in L, returns the equivalent program with the least total cost possible?

Practical example:

(optimize '(* a a) [['* 2] ['pow 1]])

Should return:

(pow a)

For a hypothetical language where '*' and 'sqrt' are the only primitive operations, as the cost of the 'sqrt' operation (1) is lower than the cost of the '*' operation (2).

Certainly not for a Turing-complete programming language, following up on D.W. and David's comments. Consider a program in this language that simulates a Turing Machine $M$ (where $M$ is hardcoded into the program) and outputs zero if $M$ halts.

When your optimizer receives such a program where $M$ halts, it must output some least-cost program that always returns zero (because the original program always returns zero). If $M$ doesn't halt, then your optimizer can output any program that runs forever (as the original program always runs forever).

OK, now let's show that your optimizer would allow us to solve the halting problem. Suppose that the statement "return zero" has cost $C$. (Thus, we know that any least-cost program that always returns zero has cost at most $C$.) Given a Turing Machine $M$, construct the program that simulates $M$ and outputs zero if $M$ halts. Feed it to the optimizer. Run the output program for up to total cost (time) $C+1$. If it has output zero, then the original program halts. If not, the original program does not halt.

...I agree with user17410's suggestion to look at the primitive recursive functions as they are likely to be able to cover most problems we want to solve practically.


Minimum relevant variables in linear system - additive approximation In the problem Minimum Relevant Variables in Linear System (Min-RVLS), the input is a linear system, e.g.:

$$ A x = b $$

and the goal is to find a solution $x$ with as few nonzero variables as possible.

The problem is known to be NP-hard and hard to approximate to within a constant multiplicative factor (see the wikipedia page for details).

My question is: is anything known about additive approximations? In particular: what is the complexity of finding a solution that has at most $\text{OPT}+d$ nonzero variables, where $\text{OPT}$ is the smallest number of nonzero variables in a solution, and $d$ is some constant?

Unless $P=NP$, there does not exist a polynomial time approximation algorithm that returns solutions of value at most $\text{OPT}+d$.

Suppose otherwise, and consider some fixed $d$ for which there does exist such an  approximation algorithm $A$. We construct a new multiplicative polynomial time approximation algorithm from $A$, that always returns solutions of value at most $2\cdot\text{OPT}$. Hence consider an arbitrary instance $I$ of Min-RVLS:

For all $k=1,\ldots,d$ check whether $I$ has a solution $x$ with $k$ nonzero variables. This can be done by checking every subset $S$ of $k$ Variables: Set all variables outside $S$ to zero, and solve the linear equation system for the remaining variables. Since there are only $O(n^d)$ subsets to be checked, the overall running time is polynomial. (Here we use that $d$ is a fixed integer.)
If the first step does not reveal any feasible solution, we know that $\text{OPT}>d$. We call the additive approximation algorithm $A$ and find in polynomial time a feasible solution of value at most $\text{OPT}+d<2\cdot\text{OPT}$.

As we either detect an optimal solution (first step) or a solutions with value at most twice the optimum (second step), the resulting polynomial time approximation algorithm
has a multiplicative approximation guarantee of $2$.


Is the integer factorization problem harder than RSA factorization: $n = pq$? This is a cross-post from math.stackexchange.

Let FACT denote the integer factoring problem: given $n \in \mathbb{N},$ find primes $p_i \in \mathbb{N},$ and integers $e_i \in \mathbb{N},$ such that $n = \prod_{i=0}^{k} p_{i}^{e_i}.$
Let RSA denote the special case of factoring problem where $n = pq$ and $p,q$ are primes. That is, given $n$ find primes $p,q$ or NONE if there is no such factorization.
Clearly, RSA is an instance of FACT. Is FACT harder than RSA? Given an oracle that solves RSA in polynomial time, could it be used to solve FACT in polynomial time?
(A pointer to literature is much appreciated.)

Edit 1: Added the restriction on computational power to be polynomial time.

Edit 2: As pointed out in the answer by Dan Brumleve, there are papers arguing for and against RSA being harder (or easier) than FACT. I found the following papers so far:

D. Boneh and R. Venkatesan. Breaking RSA may be easier than factoring. EUROCRYPT 1998. http://crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf
D. Brown: Breaking RSA may be as difficult as factoring. Cryptology ePrint Archive, Report 205/380 (2006) http://eprint.iacr.org/2005/380.pdf
G. Leander and A. Rupp. On the Equivalence of RSA and Factoring regarding Generic Ring Algorithms. ASIACRYPT 2006. http://www.iacr.org/archive/asiacrypt2006/42840239/42840239.pdf
D. Aggarwal and U. Maurer. Breaking RSA Generically Is Equivalent to Factoring. EUROCRYPT 2009. http://eprint.iacr.org/2008/260.pdf

I have to go through them and find a conclusion. Is someone aware of these results, who can provide a summary?

As far as I can see, an efficient algorithm for factoring semiprimes (RSA) does not automatically translate into an efficient algorithm for factoring general integers (FACT). However, in practice, semiprimes are the hardest integers to factor. One reason for this is that the maximum size of the smallest prime is dependent on the number of factors. For an integer $N$ with $f$ prime factors, the maximum size of the smallest prime factor is $\lfloor N^\frac{1}{f} \rfloor$, and so (via the prime number theorem) there are approximately $\frac{f N^\frac{1}{f}}{\log(N)}$ possibilities for this. Thus increasing $f$ decreases the number of possibilities for the smallest prime factor. Any algorithm which works be successively reducing this space of probabilities will then work best for large $f$ and worst for $f=2$. This is borne out in practice, as many classical factoring algorithms are much faster when the number being factored has more than 2 prime factors.

Further the General Number Field Sieve, the fastest known classical factoring algorithm, and Shor's algorithm, the polynomial time quantum factoring algorithm, work equally well for non-semiprimes. In general, it seems much more important that the factors by coprime than that they be prime.

I think part of the reason for this is the decision version of factoring co-primes is most naturally described as a promise problem, and any way of removing the promise of the input being semiprime is to either

introduce an indexing on the semiprimes (which in itself I suspect is as hard as factoring them), or
by generalising the problem to include non-semiprimes.

It seems likely that in the latter case the most efficient algorithm would solve FACT as well as RSA, though I have no proof of this. However, a proof is a little to much to ask for, since given an oracle for RSA proving that this cannot efficiently solve FACT amounts to proving that $P\neq NP$.

Lastly it is worth pointing out that RSA (the cryptosystem, not the factoring problem you defined above) trivially generalizes beyond semi-primes.


Is there a name for a hashtable with a tree for each bin instead of a list? It is well-known that the worst case performance for a chaining hashtable, is O(n), where n is the number of objects in the table. The normal assumption is that the hash is either uniform, or secure, however this is not always the case.

One possible solution to this problem would be to use a tree, or other O($\log n$) data structure, instead of the list. This would result in the worst-case performance of O($\log n$) for insertion and retrieval, at the expense of adding an extra constraint on the import data, namely that it would need to be comparable.

Is there a name for such a data structure?

Yes, there is a name for it: Hashtable.

You can have whatever you want for collision bins: Lists, trees, hashtables, whatever you fancy.


Is there a lower bound of number of redundant bits necessary to encode a word with certain Hamming distance? Is there a lower bound (in coding theory or elsewhere) of number of redundant bits necessary to encode a word with certain Hamming distance?

There is some known data for parity checks, CRC, Hamming encoding, but is there a theoretical limit?

As Tsuyoshi points out in the comments, there are a number of such bounds. However, for the sake of actually giving you an answer, let me point you to the Singleton bound, which states that for a $(s,N,d)$-code over $\mathbb{F}_b$ that $N\leq b^{s-d+1}$.


When replacing an edge with a graph gadget preserves graph isomorphism? The transformation replacing an edge by a graph gadget
is widely used in graph theory.

As an example, in an answer Marzio De Biasi subdivided
edges which increases the girth while preserving GI.

A gadget $GA$ is a graph with two distinguished vertices $u,v$.

The transformation $G,GA \to G'$ is:  replace edge $(x,y)$ in
$G$ by a copy of the gadget $GA$ and in the copy set $u=x,v=y$ so
$x,y$ from the original graph are the same in all copies.

  Which gadgets $GA$ preserve isomorphism:  $G \cong H \iff G' \cong H'$

Added to clarify

I am looking for an algorithm given $GA,u,v$ to decide if it preserves isomorphism or not (reductions to GI complete problems are allowed though better be avoided).

Added 2 I am interested when $GA$ is fixed (and possibly small).

Just a summary of my (very informal / wrong?) comments/ideas above:

Every connected gadget $GA$ with two or more nodes, that doesn't introduce an asymmetry between $u$ and $v$ should be fine. In other words suppose $maxdeg(GA)=n$, and that $X$ is a star with a central node $x$ and $n+1$ leaves, $Y$ is a star with a central node $y$ and $n+2$ leaves.

The $GA$ preserves isomorphism if and only if the two graphs $X \cup GA \cup Y$, in which $x$ is replaced with $u$ and $y$ is replaced with $v$, is isomorphic to the graph $Y \cup GA \cup X$ in which $y$ is replaced with $u$ and $x$ is replaced with $v$.

This construction can also be used to check if a small fixed $GA$ preserves isomorphism.

Furthermore, the problem of deciding if $(GA,u,v)$ preserves isomorphism is GI-complete: given two graphs $G_1,G_2$; build the following gadget $GA$: add 4 new nodes $u,x,y,v$ and edges $(u,x),(x,y),(y,v)$, then add an edge from $x$ to all the nodes of $G_1$ and an edge from $y$ to all the nodes of $G_2$. $G_1,G_2$ are isomorphic if and only if $GA$ preserves isomorphism.


Consequences of a quasi-polynomial time algorithm for the graph isomorphism problem The Graph Isomorphism problem (GI) is arguably
the best known candidate for an NP-intermediate problem.
The best known algorithm is sub-exponential algorithm
with run-time $2^{O(\sqrt{n \log n})}$.
It is known that GI is not $\mathsf{NP}$-complete unless
the polynomial hierarchy collapses.

  What would be the complexity theoretic consequences of a quasi-polynomial time algorithm for the Graph Isomorphism problem?
  Would a quasi-polynomial time algorithm for GI refute any famous conjectures in complexity theory?

Other similar problems like
Minimum Dominating Set in Tournaments problem,
Group Isomorphism problem, and
Tournament Isomorphism problem
have quasi-polynomial time (QP) algorithms.
The later two problems are polynomial-time reducible to GI.

  Can we efficiently reduce Minimum Dominating Set in Tournaments problem to GI?
  Is there any conjecture ruling out GI being hard for QP?

Update (2015-12-14): Babai has posted a preliminary draft paper on arXiv for his quasipolynomial-time algorithm for GI.

Update (2017-01-04): Babai retracted the claim that the algorithm is in quasipolynomial time, according to the new analysis the algorithm is in subexponential time $\exp \exp(\tilde{O}(\sqrt{\lg n}))$ which is inside $2^{n^{o(1)}}$.

Update (2017-01-09): Babai reinstated the quasipolynomial time claim, replacing the offending procedure with a more efficient one.

As far as I can tell, if you ask simply about the consequences of the mere fact (as a black box) that GI is in QP, I think the answer is very little. The one thing I can think of, which is not a theorem but a consequence for research directions, is to Group Isomorphism. Since GroupIso reduces to GI and we don't even know if GroupIso is in P, putting GroupIso into P can be seen as an important obstacle to putting GI into P (if you think the latter might be the case).

However, since the trivial algorithm for GroupIso is $n^{\log n + O(1)}$, back when the complexity of GI was up at $2^{\tilde O(\sqrt{n})}$, we had a long way to go in improving the complexity of GI before GroupIso became an immediately relevant obstacle to putting GI into P. But if GI is in QP, then GroupIso becomes a much more relevant obstacle to further improvements in GI. (Of course, the exponent of the exponent in the quasi-polynomial is still a potentially relevant gap, but the gap becomes a lot smaller when GI is in QP.)


Box stacking problem, and variants You are given $n$ boxes and want to stack them to make a tallest possible tower, but you can only stack a box on top of another if the base is smaller in both dimensions.  This is a classic dynamic programming problem, and yet I can't easily find answers online to natural questions:

If the boxes cannot be rotated, what is the complexity of this problem?  A standard dynamic programming algorithm gives $O(n^2)$.  Can you do $O(n \log n)$?  Any conditional lower bounds?
If the boxes can be rotated, what is the complexity?  Note that I do not have $n$ types of boxes and infinite instances of each type, I have $n$ boxes.
What is the complexity in higher dimensions?
What is the complexity if the dimensions are integers from $1$ to $k$?

If you model a box as a point $(b_1,b_2, \ldots, b_d)$, and you define the dominance relationship $p \prec q$  $\iff$ $p_i < q_i$, for all $i$, then you are looking for the longest chain in this partial order. In $d$ dimensions this problem can be solved in $O(n \log^{d} n)$ times, I believe.
I would sketch a somewhat inferior solution, because it is late.
To see how to do it, consider the two dimensional case. For a point $p$, let $||p||_1 = |x(p)| + |y(p)|$. Consider the input points, $p_1, \ldots, p_n$, and observe that $p_i \prec p_j$ only if $||p_i||_1 < ||p_j||_1$. As such, sort the points by their $L_1$ norm, in increasing ordering, and let $p_1,\ldots, p_i$ be the points handled so far, where for each $p_j$, $j=1,\ldots, i$, we computed $\ell(p_j)$ -- the length of the longest path in the relation that ends at $p_j$. We add the extra dimension $\ell(p_j)$ to the point $p_j$, so that this is now its third coordinate.
Now, given a new point $p_{i+1}$, we need to compute the highest point (in the third dimension) that it dominates (in the first two dimensions) -- this is an open quadrant question, and can be solved in $O( \log^{O(1)} n)$ time using orthogonal range searching techniques. Assume you get the point $p_k$ as returned by the query -- we have that $\ell_{i+1} = \ell(p_{i+1}) = \ell(p_k)+1$. We need to insert this new point $(p_{i+1}, \ell_{i+1})$ in the the orthogonal range searching data-structure.
Thus, you can handle each point in $O(\log^{O(1)} n)$ time which readily implies that you can compute the longest chain in $O( n\log^{O(1)} n)$ time. Being more careful about the details, the running time can be improved to $O(n \log n)$ in two dimensions.
I have a paper on a related problem here:
https://arxiv.org/abs/1910.07586
I think a solution for your problem should be readily implied by some previous work.
More maybe later...


Has there been any progress in tightening the exponent in the result that polylog independence fools $AC_0$? Braverman showed that distributions which are $(log \frac{m}{\epsilon})^{O(d^2)}$-wise independent $\epsilon$-fool depth $d$ $AC^0$ circuits of size $m$ by "gluing together" the Smolensky approximation and the Fourier approximation of $AC^0$-computable Boolean functions. The author and those who had conjectured this originally conjecture that the exponent there can be reduced to $O(d)$, and I am curious if progress has been made towards this, as I'd imagine it would involve producing a polynomial which is close in correlation distance as well as actually agreeing with the function on a large number of inputs, and I think it would be a very interesting approximation to find without gluing these two together. Is there some reason to expect that such an approximation must have degree $O(d^2)$ that wasn't known when Braverman wrote his paper in 2010?

Another question about this paper I have is that the original conjecture resembles Boppana's bound on sensitivity, though it was in a paper written prior to this bound. This, of course, isn't a coincidence, as this bound would correspond to the Fourier concentration you can derive from Boppana's bound if the Fourier polynomial worked, but is there any better intuition that you know of than that "if the Fourier polynomial worked, this is what you'd get" one?

In his CCC'17 paper [1], Avishay Tal improved the bound to $$
\left(\log\frac{m}{\varepsilon}\right)^{O(d)}\,. \tag{1}
$$
You may want to check p.15:4 for a discussion. It also refers to (see Footnote 30 to a paper of Harsha and Srinivasan, which improves on (1)) and answers Tal's conjecture: $k$-wise independent, for
$$
k = \left(\log m \right)^{O(d)}\cdot\log\frac{1}{\varepsilon}\,. \tag{2}
$$
suffices to $\varepsilon$-fool size-$m$ depth-$d$ AC0 circuits.

[1] Tight Bounds on the Fourier Spectrum of $\mathsf{AC}_0$, A. Tal. CCC'17.

[2] On polynomial approximations to $\mathsf{AC}_0$, P. Harsha and S. Srinivasan. RANDOM 2016,


Decidability of membership in the fixed point of a rational relation Given a finite alphabet $\Sigma$, a non-deterministic finite-state transducer representing rational a relation $T \subseteq \wp(\Sigma^* \times \Sigma^*)$, a finite state machine representing a regular language $L \subseteq \Sigma^*$, and a word $w \in \Sigma^*$. Let $T(L)$ denote the image of $T$ over $L$, i.e., $\left\{ w' \in \Sigma^* \mid \exists w \in L. (w,w') \in T\right\}$. Let $\mu$ and $\nu$ respectively represent the least and greatest fixed point operators.

Is it decidable whether $w \in \mu Z. L \cup T(Z)$?
Is it decidable whether $w \in \nu Z. L \cap T(Z)$?
If questions 1 or 2 are answered in the negative, does this change in the special case where $T$ is expressible as a finite union of deterministic transducers, i.e., $\mid T\left(\left\{w\right\}\right)\mid$ is finite for all $w$?
Are these results different when dealing with ranked trees rather than words, i.e., $\Sigma$ is a ranked alphabet, $L$ a tree-regular language, and $w$ a ranked tree over $\Sigma$?

The answer to (1) is no, even for deterministic transducers. The reason is that we can encode configurations (tape contents + head position + machine state) of Turing machines into words such that the configuration changes made by any machine $M$ can be represented by a transducer $T_M$, and then decidability of (1) would imply decidability of the halting problem. In some more detail, this is how it works:

For simplicity, I assume that our Turing machines move left or right in each step, i.e. for any machine state $q\in Q$ and tape symbol $a\in \Sigma$, the action $\delta(q,a)$ performed in $q$ upon reading $a$ is either $(q',a',L)$ or $(q',a',R)$ for some $q',a'$. The alphabet $\Sigma$ contains the blank $\_$, and $\Pi:=\Sigma\setminus\{\_\}$. I also assume that the machine erases the tape before halting, and doesn't write any blanks otherwise - this is a straightforward modification to any given machine, and ensures that all halting configurations are encoded as the same word.

The encoding of a configuration is a word in $(\Sigma\cup Q)^*$ of the form $\_uqav\_$, delimited by blanks, where $q\in Q$ is the current state, $a\in\Sigma$ is the content of the cell under the head, and $u,v\in\Pi^*$ are the contents to the left and to the right, respectively. Due to the above restriction, a halting configuration is encoded as $\_q_e\_\_$, where $q_e$ is the halting state.

The transducer $T_M$ operates in several phases, using its state to temporarily store a symbol $b\in\Sigma$:

It reads the leading $\_$ and sets $b:=\_$;
It reads $v = v_1\dots v_k$, in each step outputting $b$ and setting $b$ to the current $v_j$ (if $v$ is empty, then $b$ is still $\_$ after this);
It reads $q$ and $a$. Then if $\delta(q,a) = (q',a',L)$, it outputs $q'ba'$, otherwise ($\delta(q,a) = (q',a',R)$), it outputs $ba'q'$. It also remembers the move direction.
It reads and outputs $w\_$, unless we moved left, $w$ is empty, and $a'=\_$ (to avoid extra trailing $\_$).

Then $T_M^k(\_q_0w\_)$ encodes the configuration of $M$ after $k$ steps on input $w$, and $\_q_e\_\_\in\mu Z.\{\_q_0w\_\}\cup T_M(Z)$ iff $M$ halts on $w$.


Standard/Formal name for the graph Given a connected graph $G =(V_1,V_2,E)$, such that there are no edges among the vertices in set $V_1$, however the other set $V_2$ can have edges in itself. There is actually a restriction for $V_2$, which is that we cannot remove any vertex in $V_2$ such that graph $G$ is still connected. Therefore a minimality constraint is there for $V_2$. Is there a standard name for this graph?

The need for it is because im writing a manuscript which includes a result on such graphs and i need to refer this graph with some name. So, i was wondering if there was some name for it. Obviously i couldn't find it. Any other suggestion/comment is also appreciated.

Well, split graphs correspond to the case where $V_1$ is an independent set and $V_2$ forms a clique, but I'm not aware of another name in the case where $V_2$ has no particular restriction.


Bounds for maximum number of code-words in a ternary error correcting code with length n and distance d? I'm not sure I can find an explicit formula. Wondering if anyone can come up with lower/upper bounds.

The exact answer is unknown in general. One standard upper bound for $q-$ary codes is the Singleton bound, which gives
$$|C|\leq q^{n-d+1},$$ and codes meeting this bound are called MDS.

A lower bound is the Gilbert-Varshamov bound, given by

$$|C|\geq \frac{q^n}{\mathrm{Vol}_q(d-1)}=\frac{q^n}{\sum_{k=0}^{d-1} \binom{n}{k}(q-1)^k}.$$
Using these keywords should get you started, there are many more results.


Classic parallel clustering algorithms I'm starting a research about parallel clustering. I see a ton of articles on this topic, so that I don't know where to start. I'd like to get familiar with classic methods of parallelizing clustering. Are there any "have-to-know" books/papers in this area, that would provide me a good introduction?

I'm interested in shared-nothing architecture, generally something that may be suitable for map-reduce model.

There's been recent work on doing clustering in the MRC model (a formal model for analyzing mapreduce computations). Specifically, you should look at the work by Bahmani et al in VLDB 2012 on k-means$||$ and earlier work by Ene et al in KDD 2011 on the same topic. These papers have some discussion of the general problem of parallelizing $k$-means, which might be a good jumping off point for what you're interested in.


Rigour leading to insight On MathOverflow, Timothy Gowers asked a question titled "Demonstrating that rigour is important".  Most of the discussion there was about cases showing the importance of proof, which people on CSTheory probably do not need to be convinced about.  In my experience proofs need to be more rigorous in theoretical computer science than in many parts of continuous mathematics, because our intuition so often turns out to be wrong for discrete structures, and because the drive to create implementations encourages more detailed arguments.  A mathematician may be content with an existence proof, but a theoretical computer scientist will usually try to find a constructive proof.  The Lovász Local Lemma is a nice example [1].

I would therefore like to know

  are there specific examples in theoretical computer science where a rigorous proof of a believed-to-be-true statement has led to new insight into the nature of the underlying problem?

A recent example that is not directly from algorithms and complexity theory is proof-theoretic synthesis, the automatic derivation of correct and efficient algorithms from pre- and post-conditions [2].

[1] Robin A. Moser and Gábor Tardos, A Constructive Proof of the General Lovász Local Lemma, JACM 57, article 11, 2010. http://doi.acm.org/10.1145/1667053.1667060
[2] Saurabh Srivastava, Sumit Gulwani, and Jeffrey S. Foster, From program verification to program synthesis, ACM SIGPLAN Notices 45, 313–326, 2010. http://doi.acm.org/10.1145/1707801.1706337

Edit: The kind of answer I had in mind is like those by Scott and matus.  As Kaveh suggested, this is a triple of something people wanted to prove (but which wasn't necessarily unexpected by "physics", "handwaving", or "intuitive" arguments), a proof, and consequences for the "underlying problem" that followed from that proof that weren't anticipated (perhaps creating a proof required unexpected new ideas, or naturally leads to an algorithm, or changed the way we think about the area).  Techniques developed while developing proofs are the building blocks of theoretical computer science, so to retain the value of this somewhat subjective question, it would be worth focusing on personal experience, such as provided by Scott, or an argument that is backed up by references, as matus did.  Moreover, I'm trying to avoid arguments about whether something qualifies or not; unfortunately the nature of the question may be intrinsically problematic.

We already have a question about "surprising" results in complexity: Surprising Results in Complexity (Not on the Complexity Blog List) so ideally I am looking for answers that focus on the value of rigorous proof, not necessarily the size of the breakthrough.

András, as you probably know, there are so many examples of what you're talking about that it's almost impossible to know where to start!  However, I think this question can actually be a good one, if people give examples from their own experience where the proof of a widely-believed conjecture in their subarea led to new insights.

When I was an undergrad, the first real TCS problem I tackled was this: what's the fastest quantum algorithm to evaluate an OR of √n ANDs of √n Boolean variables each?  It was painfully obvious to me and everyone else I talked to that the best you could do would be to apply Grover's algorithm recursively, both to the OR and to the ANDs.  This gave an O(√n log(n)) upper bound.  (Actually you can shave off the log factor, but let's ignore that for now.)

To my enormous frustration, though, I was unable to prove any lower bound better than the trivial Ω(n1/4).  "Going physicist" and "handwaving the answer" never looked more appealing! :-D

But then, a few months later, Andris Ambainis came out with his quantum adversary method, whose main application at first was a Ω(√n) lower bound for the OR-of-ANDs.  To prove this result, Andris imagined feeding a quantum algorithm a superposition of different inputs; he then studied how the entanglement between the inputs and the algorithm increased with each query the algorithm made.  He showed how this approach let you lower-bound quantum query complexity even for "messy," non-symmetric problems, by using only very general combinatorial properties of the function f that the quantum algorithm was trying to compute.

Far from just confirming that the quantum query complexity of one annoying problem was what everyone expected it to be, these techniques turned out to represent one of the biggest advances in quantum computing theory since Shor's and Grover's algorithms.  They've since been used to prove dozens of other quantum lower bounds, and were even repurposed to obtain new classical lower bounds.

Of course, this is "just another day in the wonderful world of math and TCS."  Even if everyone "already knows" X is true, proving X very often requires inventing new techniques that then get applied far beyond X, and in particular to problems for which the right answer was much less obvious a priori.


Is every coNP-complete language P-isomorphic to an P-immune coNP-complete language? OR Is there a P-immune coNP-complete language? A set is $\mathsf{P}$-immune iff
it has no non-trivial $\mathsf{P}$ subset.

  Is every $\mathsf{coNP}$-complete language $\mathsf{P}$-isomorphic to
  an $\mathsf{P}$-immune $\mathsf{coNP}$-complete language?

Joshua Grochow's answer to my previous questions shows the answer is negative assuming cryptographic conjectures.
Is it possible to show the answer is negative
only assuming  $\mathsf{P}\neq\mathsf{NP}$?

Or show the answer as positive with  additional assumptions.

As @Kaveh points out based upon a P isomorphism assumption (Bertman-Hartmanis conjecture) one only has to show the existence of one such language.

Josh's answer uses two conjectures and
both of them are considered to be highly likely to be correct by experts
even if not proven yet.
A positive answer means that at least one of the two conjecture is incorrect.
That would be a major very surprising result.
In other words,
it is highly unlikely that the answer to your question is positive, and
even if the answer is positive,
it is not possible to prove it at this time
(otherwise we would have already refuted one of those conjectures).


Counting reversibly using few FullAdders and little work space Given N bits on a reversible computer, I want to compute their Hamming weight (into a binary register) while using a minimal number of FullAdder circuits (takes 3 bits, outputs their sum as 2 bits) and while minimizing work space.

For reference, this is what a reversible FullAdder looks like:

The important thing to notice is that you need an ancilla bit to hold the carry output, and this ancilla bit sticks around until you uncompute the FullAdder. There tends to be a tradeoff between the amount of uncomputation work you do and the maximum number of ancilla you have at any time (see: Pebble Games).

I'm looking for strategies that have interesting tradeoffs between the maximum number of ancillae and the number of FullAdder computations/uncomputations performed, in the context of popcounting a bunch of bits.

Here are three example strategies:

If you simply iteratively merge bits using FullAdders until you're left with a binary register, without ever doing any uncomputation, you compute the total weight using a linear number of FullAdders and ancillae (specifically, between N-lg(N) and N of each).
Divide the input into $\sqrt{N}$ groups of size $\sqrt{N}$. Prepare a result register with $\lg N$ bits. For each group: compute the group's weight using strategy #1, add the group's weight into the result register, then uncompute the group. This uses $\sqrt N + \lg N$ ancillae, but increases the number of FullAdder computations and uncomputations from $N$ to $4N$.
Same as strategy #2, except instead of falling back to strategy #1 when computing the group totals you recurse using the same method. This increases the FullAdder applications to $O(N (\lg N) (\lg \lg N))$, but reduces the ancilla usage to $2 \lg N$.

I am especially interested in whether or not it is possible to reduce the ancilla usage without increasing the number of FullAdder applications by such a large amount. The underlying context is quantum computation, where error corrected FullAdders are billions of times more expensive than classical ones, so I care about the constant factors.

Here is a construction with $3N + O(\lg N)$ adder computations/uncomputations and $2 \lg(N)$ ancilla usage.

Divide the input into $N/\lg N$ groups of size $\lg N$.
Allocate a result register of size $\lg N$.
For each group $g$:

Use the naive strategy to compute $g$'s weight using $\lg N$ adder computations and space.
Add the weight into the result register using $\lg N$ adder computations and uncomputations.
Uncompute $g$'s weight using $\lg N$ adder uncomputations.

The result register now contains the total weight.

The inner loop uses $3 \lg N$ adders, and runs $N / \lg N$ times, for a total of $3N$ adders. Half of the $2 \lg N$ ancilla bits are for the result register, and the other half are for the group weight computations.

Basically, using groups of size $\lg N$ instead of $\sqrt{N}$ gives an exponential improvement in space usage but only a constant factor loss in adders.