Are there any problems whose best known algorithm has run time $O\left(\frac{f(n)}{\log n}\right)$ I've never seen an algorithm with a log in the denominator before, and I'm wondering if there are any actually useful algorithms with this form?

I understand lots of things that might cause a log factor to be multiplied in the run time, e.g. sorting or tree based algorithms, but what could cause you to divide by a log factor?

The usual answer to "what could cause you to divide by a log?" is a combination of two things:

a model of computation in which constant time arithmetic operations on word-sized integers are allowed, but in which you want to be conservative about how long the words are, so you assume $O(\log n)$ bits per word (because any fewer than that and you couldn't even address all of memory, and also because algorithms that use table lookups would take too much time to set up the tables if the words were longer), and
an algorithm that compresses the data by packing bits into words and then operates on the words.

I think there are many examples, but the classic example is the Four Russians Algorithm
for longest common subsequences etc. It actually ends up being $O(n^2/\log^2 n)$, because it uses the bit-packing idea but then saves a second log factor using another idea: replacing blocks of $O(\log^2 n)$ bit operations by a single table lookup.

somewhat similar to JG's answer & "thinking outside the box", this seems like a related/relevant/apropos/fundamental negative result. based on diagonalization with a universal TM, there exists a $O(f(n))$ DTIME language that cannot run in $O\left({f(n)\over{\log f(n)}}\right)$ DTIME, due to the time hierarchy theorem. so this applies to a linear DTIME algorithm that exists, $f(n)=n$, that runs impossibly in $O\left(n \over {\log n} \right)$ DTIME.


How to compute Integer Hash of a string Is it possible to convert a string to a unique number.

Similar to any hashing algorithm (MD5, SHA-1 and SHA-2), I want to compute a unique integer value for an arbitrary length string, which should be collusion resistant, hard to invert, and easy to compute.

Can you name the technique to compute it, so that I can dig into the theory of it.

Some useful criteria for evaluating string hashing functions are discussed here:

Performance in Practice of String Hashing Functions
Choosing Best Hashing Strategies and Hash Functions
Evaluating Hash Functions
Hash Function properties

There's an empirical comparison of some popular string hashing functions here which looks at some of the criteria you mentioned. The appropriateness of various hashes would depend on the application and data characteristics. Uniformity and efficiency are usually the major concerns.

If you know the input set in advance, you can generate a perfect hash function that is collision-free. Something like CMPH or gperf can automatically generate a PHF for a set of strings.

If the input isn't known in advance, it still might be biased toward a particular distribution that makes one hash more favorable than other. Benchmarking can be useful.

For a cryptographically secure hash, you'd want something that has good avalanche effect characteristics.

Bernstein's hash is often used in string dictionary data structure implementations, but of course there are many to choose from. (Also MurmurHash.)

I misunderstood the question - this is for integers that are word-sized. For a secure crypto hash like SHA-2, see Kaveh's comments.

SHA-2 (http://en.wikipedia.org/wiki/SHA-512) is collision resistant and the output (32 or 64 bytes) can be easily converted to a (big) integer.

In Java you can easily do it with:

BigInteger number = new BigInteger(1,messageDigest);

(Java has a whole integrated cryptography API)

A SHA-256 Java example:

import java.security.MessageDigest;
public class SHAHashingExample {
public static void main(String[] args)throws Exception {
    String password = "YOUR FAVOURITE STRING HERE";
    MessageDigest md = MessageDigest.getInstance("SHA-256");
    md.update(password.getBytes());
    byte byteData[] = md.digest();
    BigInteger number = new BigInteger(1,byteData);
    System.out.println("Your integer : " + number.toString());
}
}


Optimizing multiplication in a partly commutative semigroup Let us say I have a semigroup M and its basis B. I know which elements of B commute.

What is the most efficient way to do multiplication in such a semigroup?

Essentially, this is a question of how to reduce "ABAAAXBCAAB" to "AAAABXAABBC" knowing that A, B and C commute with each other but not with X (after such a transform I can, for example, compute AAAA as (A^2)^2, or even store pre-computed powers of each element of B).

Okay, I've given it a bit of thought and I see that the algorithm is very easy.

Example: Let % denote "commutes". Let A % B, A % C, B % C, B % X.

Compute ABAAXCBA:

Let us keep a "result", an "active multiset" and a "remaining suffix". Let us append a special "$" symbol that commutes with noone onto the string.

Invariant: the product of "result", active multiset and the remaining suffix equals the product of original string.

Invariant: all items in the active multiset commute.

At each new element of the suffix, drop elements from the active multiset that don't commute with it into the product, and insert the element into the multiset.

(1, {}, ABAAXCBA$) ->
(1, {A:1}, BAAXCBA$) ->
(1, {A:1, B:1}, AAXCBA$) ->
(1, {A:2, B:1}, AXCBA$) ->
(1, {A:3, B:1}, XCBA$) -> (drop A^3)
(A^3, {B:1, X:1}, CBA$) ->
(A^3 X, {B:1, C:1}, BA$) ->
(A^3 X, {B:2, C:1}, A$) ->
(A^3 X, {B:2, C:1, A:1}, $) ->
(A^3 X B^2 C A, {$}, )

This version has at most O(|A|) (size of alphabet) overhead per input symbol and it does an optimal number of multiplications.


Is an NP-hardness proof of an NP-hard problem considered a contribution? I am solving a problem that is claimed to be NP-hard elsewhere, say in the paper [XYZ]. The NP-hardness provided in [XYZ] is complicated and uses advanced techniques. After some research and work, I succeeded to give a simple and clear proof of the NP-hardness. I am wondering if this is considered as a contribution or not? I am trying to motivate my work but I didn't find a similar path.

I don't know if this is the right place to ask or should I go to academia?

There are venues that are interested by elegant proofs of existing results, see for instance the Symposium on Simplicity in Algorithms.

So yes, in some cases an elegant proof can be considered as a contribution, especially if it offers new insights.

Depends which NP hard problem. A famous one (e.g., 3SAT) would be a nice contribution. A random one of the 15k NP-hard problems would be less so.


Complexity of computing the parity of read-twice opposite CNF formula ($\oplus\text{Rtw-Opp-CNF}$) In a read-twice opposite CNF formula each variable appears twice, once positive and once negative.

I'm interested in the $\oplus\text{Rtw-Opp-CNF}$ problem, which consists in computing the parity of the number of satisfying assignments of a read-twice opposite CNF formula.

I was unable to find any reference about the complexity of such problem. The closest I was able to find is that the counting version $\#\text{Rtw-Opp-CNF}$ is $\#\text{P}$-complete (see section 6.3 in this paper).

Thanks in advance for your help.

Update 10th April 2016

In this paper, the $\oplus\text{Rtw-Opp-SAT}$ problem is shown to be $\oplus\text{P}$-complete, however the formula produced by reduction from $3\text{SAT}$ is not in CNF, and as soon as you try to convert it back into CNF you get a read-thrice formula.
The monotone version $\oplus\text{Rtw-Mon-CNF}$ is shown to be $\oplus\text{P}$-complete in this paper. In such paper, $\oplus\text{Rtw-Opp-CNF}$ is quickly mentioned at the end of section 4: Valiant says it is degenerate. It is not clear to me what being degenerate exactly means, nor what does it imply in terms of hardness.

Update 12th April 2016

It would be also very interesting to know if anyone has ever studied the complexity of the $\Delta\text{Rtw-Opp-CNF}$ problem. Given a read-twice opposite CNF formula, such problem asks to compute the difference between the number of satisfying assignments having an odd number of variables set to true and the number of satisfying assignments having an even number of variables set to true. I've not found any literature about it.

Update 29th May 2016

As pointed out by Emil Jeřábek in his comment, it is not true that Valiant said that the problem $\oplus\text{Rtw-Opp-CNF}$ is degenerate. He only said that a more restricted version of such problem, $\oplus\text{Pl-Rtw-Opp-3CNF}$, is degenerate. In the meanwhile, I continue to not know what degenerate exactly means, but at least now it seems clear that it is a synonym of lack of expressive power.

It turns out that every opposite-read-twice formula has an even number of satisfying assignments. Here's a nice proof of it, though one could probably eliminate the graph-theoretic terminology.

Let $\phi$ be an opposite-read-twice CNF formula. Without loss of generality, no clause contains both a variable and its negation.

Consider the graph $G$ whose vertex set is the clauses of $\phi$, and for each variable $x$, we add an (undirected) edge that is incident on the two clauses containing $x$. Our WLOG assumption in $\phi$ says this graph has no self-loops. Moreover, think of labeling each edge by the variable defining it; this way we can distinguish between parallel edges.

An orientation of $G$ is a directed graph whose edges are formed by assigning a direction to each edge in $G$. Call an orientation of $G$ admissible if every vertex of $G$ has an outgoing edge. It's easy to see that satisfying assignments to $\phi$ are in bijective correspondence with admissible orientations of $G$.

Now I claim that the number of admissible orientations of $G$ is even. The argument is "by involution": I construct a map $\Phi$ with the following properties:

$\Phi$ is totally defined (every admissible orientation is mapped somewhere)
$\Phi$ sends admissible orientations to admissible orientations
$\Phi$ is an involution ($\Phi \circ \Phi$ is the identity)
$\Phi$ has no fixed points

Once these are established, we can observe that the orbits of $\Phi$ have size 2 and partition the admissible orientations of $G$. It follows that the number of admissible orientations is even.

To define $\Phi$, let $\vec{G}$ be an admissible orientation, and consider breaking $\vec{G}$ into it's strongly connected components. $\Phi$ then sends $\vec{G}$ to the orientation formed by reversing all the edges within the strongly connected components. The properties are then straightforwardly checked:

Every directed graph can be partitioned into strongly connected components.
Consider the "DAG of strongly connected components" in $\vec G$; call it the quotient graph. Note that $\Phi(\vec G)$ will have the same quotient structure, since $\Phi$ doesn't affect the edges between SCCs, and strongly connected graphs remain strongly connected when reversing all their edges. Additionally, if a SCC has more than one vertex, then all its constituent vertices have an incoming edge. If an SCC has just a single vertex and isn't a source in the quotient, then all its constituent vertices have an incoming edge. So to show $\Phi(\vec G)$ is admissible, it suffices to show that the SCCs which are sources in the quotient have multiple vertices. But this follows by the fact that every vertex in the component has an incoming edge, which must come from another vertex in the component since $G$ has no self-loops and the component is a source in the quotient.
This follows from the fact that the quotient structure of $\Phi(\vec G)$ coincides with the quotient structure of $\vec G$.
By admissibility, $\vec G$ has a cycle, and hence some SCC with an edge inside it.

sorry for big delay. Until now probably the problem was solved. If not, I will present my polynomial algorithm for solving $\oplus\text{Rtw-Opp-CNF}$.
First let's try to calculate number of solutions modulo 2 of this equation:
${f(X)}\oplus{g(X)}$ .
Where f and g are logic functions and X is a vector of variables.
Common part, $f(X) \wedge g(X)$, occurs two times (one time in f(X) and one time in g(X)). So in modulo 2 common part is not important. We can calculate number of solutions modulo 2 of $f(X)$ and number of solutions modulo 2 of $g(X)$ and then sum this results modulo 2.
Now let's assume that function is presented in this form:

$i_0\oplus{i_1}\oplus{i_2}\oplus{...}\oplus{i_{n-1}}$,

where $i_j$ is an implicant (I mean variables connected by AND operator; for example: $x_0\wedge{x_1}\wedge{\neg{x_2}}$).

To calculate number of solutions of this function modulo 2 we can simply calc number of solutions each implicant modulo 2 and sum all results modulo 2.
If we have vector of variables X and in implicant there is no all variables from this vector, then we know that number of solutions modulo 2 for this implicant is 0, because there is $2^k$ solutions, where k is number of missing variables.
If implicant has all variables, then number of solutions is 1 (k = 0).
So calculating number of solutions modulo 2 of $i_0\oplus{i_1}\oplus{i_2}\oplus{...}\oplus{i_{n-1}}$ is easy.
Now let's consider:

$i_0\vee{i_1}\vee{i_2}\vee{...}\vee{i_{n-1}}$.

We know that $a\vee{b} = a\oplus{b}\oplus({a\wedge{b}})$.
In general, OR operation can be replaced by XOR of every subset of implicants connected by AND operator.
And this is important step: we are interested in only those subsets that:

1) has all variables,

2) every variable occurs exacly one (if variable occurs two times, then we have positive and negative in one implicant, so this will give as 0).

Let's say that we have positive $x_0$ in implicant $i_0$ and negative $x_0$ in implicant $i_1$. Then we can write and equation:

${j_0}\oplus{j_1} = 1$.

In this equation variables ${j_0}$ and ${j_1}$ corresponds with implicants $i_0$ and $i_1$. I mean if, for example, implicant $i_0$ occurs in subset, then $j_0$ = 1. Otherwise $j_0$ = 0.
If we make this for all variables, we will get set of XOR equations and we have to calculate number of solutions of this set. This problem is easy. Number of soltions if always $2^l$, when l is some value to find.
That's all. I know that this is not formal proof, but I hope it is understandable.


What are some problems where we know we have an optimal algorithm? What are some non-trivial problems where we know the current algorithm we have is the asymptotically optimal one? (For turing machines)

And how is this proved?

Any algorithm which takes linear time and has to read its whole input must be asymptotically optimal. Similarly, as Raphael comments, any algorithm whose runtime is of the same order as output size is optimal.

Many sublinear time algorithms have upper bounds matching their lower bounds.


Examples where insight from geometry was useful for solving something completely non-geometric One of the nice things about having evolved in a universe with three spatial dimensions is that we have developed problem solving skills pertaining to objects in space. Thus, for example, we can think of a triplet of numbers as a point in 3-d and hence computation about triplets of numbers as computation about points in 3-d, which can then be solved using our intuition about space. This seems to suggest that it should be possible at times to solve a completely non-geometric problem using techniques from geometry. Does anyone know of such examples?

Of course, the terms 'geometric' and 'non-geometric' are slightly vague here. One can argue that any geometric problem is actually non-geometric if you replace all points with their co-ordinates. But intuitively, the definition is clear. Let's just say that we call something geometric if we would consider sending a paper about it to SoCG.

A few more examples:

Sleator, Thurston and Tarjan used a geometric representation of trees as partitions of polygons, and hyperbolic geometry, to prove lower bounds for binary tree rotation. (Also, I believe the history of a dynamic binary search tree can be represented as a tetrahedralization.)

The reduction of least common ancestor to range minimum queries, due to Berkman and Vishkin, relates a data structures problem on trees to an arguably-geometric problem. (and thanks for the article David)

The reduction of a scheduling problem to max weight independent set of axis-parallel rectangles [1] or the reduction of a different scheduling problem to geometric set cover [2] might qualify.

The reduction of the largest common subsequence problem to finding layers of maxima is well-known (meaning, I'm too lazy to look up who actually thought of it).

[1] (Liane Lewin-Eytan, Joseph Seffi Naor and Ariel Orda)

[2] Nikhil Bansal, Kirk Pruhs. The Geometry of Scheduling, FOCS 2010.

[later edit] A couple more cases where a "geometric" view seemed surprising (though the "submission to SoCG" or "makes something to visualize" standards are probably not met):

algebraic topology applied to lower bounds for distributed computing

incorporating computability into Hausdorff dimension

defining a notion of distance for groups, then volume, then growth of volume as a function of distance, then using "polynomial growth"

A Definite Integral of a function can be represented as the signed area of the region bounded by its graph.


If SAT is in PCP, for some constant q, then P = NP I have seen this statement before, but I haven't really seen a proof of it:

If $SAT\in PCP_{1,2^{−q}}[\log(n),q]$, for some constant $q$, then $P = NP$.

Now, if $SAT\in PCP_{1,2^{−q}}[\log(n),q]$, then SAT reduces to $GAP-q-CSP[1,2^{-q}]$. So to show $P = NP$, how do we show then that $GAP-q-CSP[1,2^{-q}]$ is in $P$?

Given a CSP where all constraints have arity at most $q$ we want to distinguish between the case where everything is satisfiable and the case where at most $1/2^q$ fraction of the constraints are satisfiable, in polynomial time. Here is how this can be done.

First, all predicates used in the CSP must have at least one satisfying assignment (otherwise we know that the instance is not perfectly satisfiable and we are done). If a used predicate has two or more satisfying assignments, then, if we take a random assignment for all variables some constraint is satisfied with probability at least $2/2^q>1/2^q$. Since all other constraints are satisfied with probability at least $1/2^q$, by linearity of expectations there exists an assignment that satisfies strictly more than $1/2^q$ fraction of the constraints and we are done in this case.

Finally, suppose that all predicates used have exactly one satisfying assignment. Then the CSP is an instance of DNF-SAT, which can be decided in polynomial time (we only need to check if any two constraints have a conflict).

along these lines a property relating PCP and NP can be found in the following citation p63 from P vs NP by Mayordomo (2004):

  The best known result [2] is that NP is exactly the class of problems
  that can be solved by probabilistic verifiers using a constant number of certiﬁcate bits
  (that is, the same number of bits for all inputs and certiﬁcates) and a logarithmic number
  of random bits, this is the complexity class PCP(log n, 1).

the ref is:

[2] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof veriﬁcation and the
hardness of approximation problems. Journal of the ACM, 45(3):501–555, 1998.


Given a B-Tree, determine the order keys were inserted Given a B-tree, determine what order the keys were inserted in.  There may be multiple answers: I'd like to generate them all.

Is there any known method for this?  Or similar problems?

Clarification: As the comments mentioned, enumerating them all may be intractable.  I'd like to do two things:

Create a partial ordering. Node 7 was inserted before Node 4, but cannot be compared to Node 20.  (I've done this successfully for a binary search tree, and am wondering if this can be applied to B-tree as well. For BSTs, it seems to be simple: Node A < Node B iff Node A is an ancestor of Node B, assuming no deletions.)
Create what I call a probabilistic partial ordering.  For example: Out of x possible orderings, y have Node 4 inserted before Node 20, and 1 - y have Node 4 after Node 20.  I still am working on this even for binary search trees, so perhaps it's better to ask this question there first.

I'm also working on expanding the model to include deletions (probablisticly), but that will come later.

Simple... keep two pointers, a next and a previous.


Complexity of optimization over unitary group What is the computational complexity of optimizing various functions over the unitary group $\mathcal{U}(n)$?

A typical task, arising often in quantum information theory, would be maximizing a quantity of type $\mathrm{Tr}AUBU^{\dagger}$ (or higher order polynomials in $U$) over all unitary matrices $U$. Is this type of optimization efficiently (perhaps approximately) computable, or is it NP-hard? (maybe this is well known, but I've been unable to find any general references)

Sorry I'm late!  In quantum computing theory, there are lots of examples of optimization problems over the unitary group that, surprisingly (at least to me), are solvable in (classical) polynomial time by reduction to semidefinite programming.

Here was an early example: solving a problem of mine from 2000, in 2003 Barnum, Saks, and Szegedy showed that Q(f), the quantum query complexity of a Boolean function f:{0,1}n→{0,1}, can be computed in time polynomial in 2n (i.e., the size of f's truth table).  I had thought about this but couldn't see how to do it, since one needs to optimize the success probability over all possible quantum query algorithms, each one with its own set of (possibly 2n-sized) unitary matrices.  Barnum et al. reduced to SDP by exploiting a "duality" between unitary matrices and positive semidefinite matrices, the so-called Choi-Jamiolkowski isomorphism.  For a more recent and simpler SDP characterizing Q(f), see Reichardt's 2010 paper showing that the negative-weight adversary method is optimal.

Another important case where this trick has been exploited is in quantum interactive proof systems.  While it's not intuitively obvious, in 2000 Kitaev and Watrous proved that QIP ⊆ EXP. by reducing the problem of optimizing over the exponential-sized unitary matrices that arise in a 3-round quantum interactive proof system, to solving a singly-exponential-sized SDP (again, I think, using the Choi-Jamiolkowski isomorphism between mixed states and unitary matrices).  The recent QIP=PSPACE breakthrough came from showing that that particular SDP could be approximately solved even better, in NC (i.e., by log-depth circuits).

So, whatever your specific optimization problem involving the unitary group, my guess is that it can be solved faster than you think -- if not in some even simpler way, then by reduction to SDP!

Determining whether two Hadamard matrices are equivalent is a Graph Isomorphism (GI) complete problem. Brendon McKay has a paper on this topic. See B. D. McKay, Hadamard equivalence via graph isomorphism, Discrete Mathematics, 27 (1979) 213-216.


Joining lists with some common elements in average case What are some ways of commutatively combining a pair of lists to produce a list comprised of elements from the pair of inputs, with no duplicates, with time complexity better than $O(n \log(n))$? Suppose we have the following inputs

$a = [5, 1, 6, 8]$

$b = [8, 4, 5, 2, 10]$

We would like to commutatively combine $a$ and $b$ to produce a list with no duplicate elements (i.e. if F denotes a function that satisfies the aforementioned criteria, then $\forall x, y \quad F(x, y) = F(y, x)$). One possible valid output is $c = [1, 2, 4, 5, 6, 8, 10]$ - since the output doesn't have to be sorted, any permutation of $c$ is just as valid (although consistency would be nice). The most obvious naïve algorithm concatenates the two lists, then removes duplicates, then sorts the result in $O(n \log(n))$ time.

Is there a commonly used name for this kind of problem, and where can I find literature about it?

Yes and no.

Set interaction is one of the problems specifically studied in Ben-Or's seminal paper on lower bounds for algebraic decision and computation trees.  The problem is formally defined as follows: Given two sets of n numbers, is their intersection empty? Equivelently, does their union have exactly 2n elements?  Ben-or proves a lower bound of Ω(n log n) for this problem.  If the sets have diffent sizes n>m, the lower bound becomes Ω(n log m), but this only beats the naive O(n log n) bound if m is subpolynomial in n.

On the other hand, if your list elements are integers, you can solve the problem in o(n log n) time using fast integer-RAM sorting algorithms.  For reasonable word sizes, I believe the fastest integer sorting algorithm runs in $O(n \sqrt{\log \log n})$ expected time [Han and Thorup, FOCS 2002].

def F(a,b):
    M = max(max(a),max(b))
    C = BitArray of size M
    FOR x in a:
         C[x] = 1
    FOR y in b:
         C[y] = 1
    FOR z in range(0,M):
        IF C[z] == 1:
          c.append(z)
    return c

Nice qualities:

This function is $O(n)$.
It preserves order.

Non-nice qualities:

If input is $a = [100000000000], b=[0]$ you will regret using it.

So if numbers in the lists are uniformly and densely distributed between $0$ and $M$ then this will work fine otherwise not using it will be wise.

But again the complexity is $O(n)$ and this is theoretical cs website.


Subset-sum-difference problem Consider the following problem:

SUBSET-SUM-DIFFERENCE: Let $S=\{s_1,\dots,s_n\}$ be a set of $n$ integers and $t$ be a "target" integer. Are there two disjoint subsets of $S$ (call them subsets $I$ and $J$) such that $\sum_{i \in I}s_i - \sum_{j \in J} s_j=t$.

The Meet-in-the-Middle algorithm will solve this problem in $\Theta(3^{n/2})$ time. Is there an exact and deterministic algorithm which solves this problem in $o(3^{n/2})$ time?

Maybe.

Becker, Coron, and Joux [EUROCRYPT 2011 describe an algorithm to solve random hard instances of Subset Sum (in fact, the more general Knapsack problem) in $\tilde{O}(2^{0.291n})$ time, beating the "meet in the middle" time bound $\tilde{O}(2^{n/2})$ by Shamir and Schroeppel [SICOMP 1981].  (Here, $\tilde{O}(f(n))$ is standard shorthand for $O(f(n)\operatorname{polylog} f(n))$.)

More recently, Dinur, Dunkelman, Keller, and Shamir [Crypto 2012], which establish better time-space tradeoffs (but do not improve worst-case running times) for a general class of cryptography problems that includes Knapsack.  Becker's techniques rely crucially on the observation that addition is both commutative and associative, but Dinur's techniques do not; for example, they also derive faster algorithms for solving random hard instances of permutation puzzles like the Rubik's cube.

It seems likely that Dinur's techniques would imply faster algorithms for (at least random hard instances of) your problem.

When I posted the question, I thought there might be an algorithm, but now I think the answer is no.

If it were possible to solve this problem in $o(3^{n/2})$ time in the worst-case scenario via a deterministic algorithm, it would be possible to manipulate the equation $\sum_{i \in I}s_i - \sum_{j \in J} s_j=t$ so that there are $L$ possible expressions on the left-hand-side and $R$ possible expressions on the right-hand-side, where $L+R=o(3^{n/2})$. But this appears to be impossible.

The best you can do is manipulate the equation to get $\Theta(3^{n/2})$ possible expressions on the left-hand-side and get $\Theta(3^{n/2})$ possible expressions on the right-hand-side, as follows:

$\sum_{i \in I^+}s_i - \sum_{j \in J^+} s_j=t-(\sum_{i \in I^-}s_i - \sum_{j \in J^-} s_j)$,

where $I^+ =\{1,\dots,[n/2]\} \cap I$, $I^- =\{[n/2]+1,\dots,n\} \cap I$, $J^+ =\{1,\dots,[n/2]\} \cap J$, and $J^- =\{[n/2]+1,\dots,n\} \cap J$. This allows one to apply the Meet-in-the-Middle algorithm. I don't think anyone will find any algorithm that beats the Meet-in-the-Middle for this problem.

Added in 2019: this paper came out, which gives a probabilistic algorithm and also has a better name for the problem, "equal subset-sum".  https://arxiv.org/abs/1905.02424


Evidence that matrix multiplication can be done in quadratic time? It is widely conjectured that $\omega$, the optimal exponent for matrix multiplication, is in fact equal to 2. My question is simple:

  What reasons do we have for believing that $\omega = 2$?

I'm aware of fast algorithms like Coppersmith-Winograd, but I don't know why these might be considered evidence for $\omega = 2$.

Naively, it seems to me like a classic example where a community just hopes that a result is true purely for aesthetic reasons. I would love to know if that's essentially the case here.

I don't know about others but I can tell you why I tend to believe that $\omega=2$. When you read through the history and development of fast matrix multiplication algorithms, I think that it is hard not to get feeling that all that we need is just a slightly better basic algorithm from which, even using known techniques, $\omega=2$ will follow. Basically, all algorithms today (including group theoretic ones) start with some "simple" construction that is then amplified. Those constructions are clever but they give the reader some sort of an "ad-hoc" feeling. I don't see a reason to believe that we cannot come up with better simple constructions.

More likely that it is $O(n^{2} log(n^2))$. Having $\omega = 2$ seems fanciful as constant factor book-keeping doesn't seem like it could scale.


Random 3-SAT: What is the consensus experimental range of the threshold? The critical ratio of clauses to variables for random 3-SAT is more than 3 and less than 6, and seems to be commonly described as "around 4.2" or "around 4.25".  Mezard, Parisi, and Zecchina prove (in the physics sense) that the critical ratio is 4.256, whereas the first and third authors prove that it is 4.267.

What is the range of values that the critical ratio could possibly take?

The motivation for me asking this question is that if the ratio could be $2+\sqrt{5} \approx 4.236$, then the standard reduction of 3-SAT to NAE-3-SAT (transforming $m$ clauses and $n$ variables into $2m$ clauses and $m+n+1$ variables) gives a ratio of $\phi$, which seems unlikely but would be pretty cool.

In light of the Ding--Sly--Sun verification of the 1-step Replica Symmetry Breaking picture for kSAT (when k is large enough) I think experts would now be pretty surprised if the MPZ/MMZ-conjectured formula for the 3SAT satisfiability threshold (approximate value: 4.2667) is incorrect.

From the engeneering point of view, when not allowing any irrationalities like the golden ratio, the practical thershold should be 4,109890672858455 the exact one as long you don't consider any theoretical 1 million variables formulas or such.


Is there a non Turing-complete model of computation whose halting problem is undecidable? I cannot think of any such model, maybe some form of typed lambda calculus? some elementary cellular automaton?

This would almost disprove Wolfram's "Principle of Computational Equivalence":

  Almost all processes that are not obviously simple can be viewed as computations of equivalent sophistication

You can easily build artificial models which are not Turing complete but the halting problem for them is undecidable. E.g. take all TMs that do not halt on anything but $0$.
Regarding the statement:
You cannot disprove a statement that is not precise enough. Almost none of the words in the statement is well-defined (please provide the definition for them if this is not the case).

Probably.   There are many mathematical problems which probably include some among
them, that are undecidable, i.e. answer is "yes" but no proof of that exists.
For example the Collatz 3x+1 problem springs to mind as a candidate.
Or the question of whether pi contains arbitrarily long strings of consecutive 9s.
Any such problem could be regarded as a "model of computation" presumably much
less powerful than a UTM, but it still would be undecidable whether it "halts"
or whether it "always halts."


Partially Ordered CFG I'm looking for work about partially ordered context-free grammars. I've found one paper, which seems to simplify the problem too much (in addition to some technical mistakes, as far as I can tell). It defines the language of a  pom-CFG by reduction to a normal context-free grammar, which excludes some (otherwise) possible words from the language, I think.

Thus I'm looking for other work.

What I mean by partially ordered CFG

The production rules don't produce linear strings of symbols but partially ordered (multi) sets of symbols. Thus the "words" of the generated language are also partially ordered multi-sets of symbols. For example this:

  b-c
 /   \
a     d-a
 \   /
  a--

The possible linearizations of this partially ordered word are aabcda, abacda, abcada.

The described concept is known as graph grammars and dates back into the 1970ies. Searching for this yields a sufficient amount of references. The terms "Graph Transformation" and "Graph Rewriting" are also used. See e.g. Wikipedia on Graph Rewriting.

You may be interested in trace theory.

There has also been research on (fully) commutative languages.

Not having studied either, I can't give you any more specific references, but Google can.


Enumerating topological sorts of a vertex-labeled DAG Let $G = (V, E)$ be a directed acyclic graph, and let $\lambda$ be a labeling function mapping each vertex $v \in V$ to a label $\lambda(v)$ in some finite alphabet $L$. Writing $n := |V|$, a topological sort of $G$ is a bijection $\sigma$ from $\{1, \ldots, n\}$ to $V$ (i.e., an ordering of $V$ in a sequence) such that whenever $(v, v') \in E$ then $\sigma^{-1}(v) < \sigma^{-1}(v')$ (i.e., if there is an edge from $v$ to $v'$ then $v$ occurs before $v'$ in the sequence). The label of $\sigma$ is the word $\sigma(1) \cdots \sigma(n)$ in $L^n$.

Given $(G, \lambda)$, I would like to enumerate the labels of topological sorts of $G$ efficiently. What is the complexity of enumerating the labels of topological sorts? Of course, as there can be exponentially many, I want to study complexity as a function of the size of the output, or in terms of delay. In particular, can enumeration be performed with polynomial delay? (or even constant delay?)

In the case where all vertices of $G$ carry distinct labels (or, equivalently, the vertices are $\{1, \ldots, n\}$ labeled by themselves), I know that labels can be enumerated in constant amortized time, by this result on enumerating linear extensions of posets (which is the same thing as enumerating topological sorts of a DAG). However, when vertices are labeled arbitrarily, it could be the case that a very large number of topological sorts have the same label, so you can't just enumerate topological sorts of $G$ and compute their labels to get an efficient way to enumerate the labels. In poset terminology, the labeled DAG $(G, \lambda)$ can be seen as a labeled poset, and I couldn't find enumeration results about those.

I already know the hardness of some related problems thanks to answers to my other questions here. In particular, I know that finding the lexicographically minimal label is NP-hard. I also know that deciding whether a given label can be achieved by some topological sort is NP-hard (from the hardness of this problem: given a candidate label sequence $s$, ask for a topological sort of $G$ where each vertex must occur at a position where the right label occurs in $s$). However, I don't think that any of this implies hardness for enumeration, as you may enumerate in any order you like (not necessarily lexicographic), and an enumeration algorithm can't be used to decide efficiently whether a label is achievable, even with constant delay (as there may be exponentially many sequences to enumerate first).

Note that, it is obviously easy to enumerate a first label $s$ (just take any topological sort). To enumerate another label than $s$, you can proceed by imposing that some element $v$ of $V$ gets enumerated at some position $i \in \{1, \ldots, n\}$ where $s_i \neq \lambda(v)$: try out every $v$ and $i$, and check if $G$ has a topological sort where $v$ is at position $i$, which can clearly be done in PTIME. But as you output more and more labels, I'm not sure of how to generalize this approach.

One of the simplest way to compute topological ordering is performing a Depth First Search on the given DAG. Different topological orderings can be generated by exploiting the flexibility of choosing the next vertex $v$ to be traversed from the unvisited neighbours of the current vertex $u$.
Since, it is a recursive procedure enumerating all possible traversals (and hence topological orders) would be simple, by choosing different orders in which unvisited neighbours of $u$ are traversed.

Now, in order to limit repeating the same traversal because of similar labels, one can compare the unvisited neighbours $v_1,v_2,...,v_k$ of $u$ having similar labels. Consider two vertices $v_i$ and $v_j$ that have the same unvisited neighbours when the traversal reaches $u$. Surely choosing either of them first would generate the same DFS tree and hence any one of them can be avoided.

Now, comparing the neighbours of all $v_1,...,v_k$ would lead to an overhead of $O(n^2)$ on the total time, but can be performed more efficiently in $\tilde{O}(n)$ by using appropriate data structures.


Pairwise independent gaussians Given $X_1,\ldots,X_k$ (i.i.d. gaussians with mean $0$ and variance $1$), is it possible (how?) to sample (for $m=k^2$) $Y_1, \ldots, Y_m$ such that
$Y_i$'s are pairwise independent gaussians with mean $0$ and variance $1$.

The posting on MathOverflow tells how to go from a small number of independent Uniform[0,1] random variables to a larger number of pairwise-independent Uniform[0,1] random variables. You can of course go back and forth between Uniform[0,1] and Gaussian by inverting the CDF. But that requires numerical analysis as the CDF is not closed-form.

However, there is a simpler way to from Gaussian to uniform. Given two independent Gaussians $X_1, X_2$, the angle $\arctan(X_1/X_2)$  is uniform in the range $[0,2 \pi]$.

Similarly, the Box-Muller method transforms two independent Uniform[0,1] variables into two independent Gaussian random variables.

Using these two transformations, you consume two Gaussians to produce a uniform or two uniforms to produce a Gaussian. So there is only a factor of $O(1)$ in the sampling efficiency. Furthermore, no inversion of the Normal cdf is required.

This construction does NOT give pairwise independent variables (indeed, $|Y_{i,j}| = |Y_{i,j'}|$ below) as asked by Anindya, but it gives pairwise uncorrelated variables which is enough for getting good concentration bounds for the sum through Chebyshev's inequality (and this is many times the end goal).

For each distinct pair $(i,j) \in {[k] \choose 2}$, let $Y_{i,j} = |X_i| \cdot \sigma(X_i X_j)$, where $\sigma(\cdot)$ is the sign function. It's clear that each $Y_{i,j}$ is a normal variable with mean 0 and variance 1. To see that they are orthogonal, for $(i,j) \neq (i',j')$, note that $$\mathbb{E}[Y_{i,j}Y_{i',j'}] = \mathbb{E}[|X_i X_{i'}| \cdot \sigma(X_i X_{i'} X_j X_{j'})]$$
which can be easily checked to equal 0 by looking at the various cases of possible equalities between $i,i',j,j'$.

P.S.: A previous version falsely claimed pairwise independence.


How many sets of vectors can be represented as the solutions of a Horn-SAT instance? Let the solution space of a SAT instance be the set of Boolean vectors of satisfying assignments of $\{0,1\}$ to the variables (that result in the formula evaluating to TRUE).
In other words, a solution space represents all the solutions of an instance.
There are at most $2^n$ solutions, so $n$-variable SAT (denoted here by SAT$_n$) can represent at most $2^{2^n}$ different solution spaces.
Moreover, it is easy to see that this number can actually be reached, by considering instances where every clause contains all $n$ variables.

We know that Horn-SAT is less expressive than SAT, for instance there is no Horn-SAT$_2$ representation of the solution space of $a \lor b$, which contains the 3 vectors $01, 10, 11$.
Hence Horn-SAT$_n$ must be able to represent fewer than $2^{2^n}$ solution spaces.

  What is the number of solution spaces of a Horn-SAT$_n$ instance?

For completeness, recall that a literal is either a variable or its negation,
and that $n$-variable SAT consists of formulas built from at most $n$ variables (we can fix the set of variable names, e.g. $\{1,2,\dots,n\}$), in conjunctive normal form (a conjunction of disjunctions), where each disjunction of literals is known as a clause.
Horn-SAT$_n$ is the fragment of $n$-variable SAT where each clause in an input formula contains at most one non-negated variable.

An equivalent counting formulation of the question is: how many different values can #Horn-SAT$_n$ have?
However, note that I am not interested here in the complexity of #Horn-SAT, just its range of values for each number of variables.

If one tries to work syntactically, then one faces the same challenge as for SAT.
Suppose one tries to count the number of different SAT instances syntactically.
There are $2^{3^n}$ different ways to write down a SAT instance with $n$ variables and no repeated clauses (if the variable order is fixed and no variable may appear more than once in a clause), so one has to find the equivalence classes of syntactically different instances that lead to the same solution space, to retrieve the $2^{2^n}$ number.
One then needs to similarly take the quotient of the set of different Horn-SAT instances with $n$ variables to obtain the correct value of the number of different solution spaces.
It is not clear to me how to take quotients for SAT, let alone how to do so for Horn-SAT.

$\def\pw{\mathcal P}$
It is an easy exercise to show that if we identify Boolean assignments to $n$ variables with subsets of $[n]=\{0,\dots,n-1\}$, then the solution sets of Horn CNFs are exactly the families $S\subseteq\pw([n])$ that are closed under nonempty intersections.

The picture is a little nicer for conjunctions of clauses each of which contains exactly one positive literal. Their solution sets are families closed under arbitrary intersections (where in particular the empty intersection is the full set), also known as closure systems or Moore families. These are in 1–1 correspondence with closure operators (functions $C\colon\pw([n])\to\pw([n])$ satisfying $X\subseteq C(Y)\iff C(X)\subseteq C(Y)$), consequence relations (relations ${\vdash}\subseteq\pw([n])\times[n]$ satisfying a handful of natural conditions), and I guess there are more similar combinatorial characterizations (https://oeis.org/A102896 or https://oeis.org/A102897 mention semilattices).

These two numbers only differ by a factor of two (given a closure system $S$, we may either retain $[n]\in S$ or throw it out without affecting anything else).

Alekseev proved that the number $\alpha(n)$ of closure systems on an $n$-element set satisfies

$$2^{\binom{n}{\lfloor n/2\rfloor}}\le\alpha(n)\le2^{\binom{n}{\lfloor n/2\rfloor}(1+o(1))}.$$

See http://www.renyi.hu/~ohkatona/paper_72.pdf for related information.

(I was going to add a quick comment, but I'm not being allowed to.)

If you take into account equi-satisfiability, then you can get lots more Horn formulas.  For example, considering $\phi \equiv (p \lor q)$, there is a reduction from $\phi$ to a Horn formula.  See my answer under Translating SAT to HornSAT.

If you try using the above technique to reduce an arbitrary 3-SAT formula to a Horn formula, you cannot do it in poly time -- since two 3-clauses resolve to a 4-clause, two 4-clauses resolve to a 6-clause, and so on... the result is an exponential number of clauses.. but I digress.. I'm going off-topic, so let me stop here.


Finding the two shortest paths while minimizing the number of nearby/common edges The shortest path problem between 2 arbitrary nodes is one that has been covered extensively and the solution is well-known. Consider the edge costs to be arbitrary.

Consider the following variant:

Find the two shortest paths between 2 pairs of arbitrary nodes, however  the cost is considered to be the length of the path and in addition the number of nearby/common edges in the two paths. This cost is $|P_1| + |P_2| + |P_1 \cap P_2|$ when considering only common edges. More generally we can state the cost as $|P_1| + |P_2| + f(P_1, P_2)$ where it can generalize to consider both penalizing common edges or nearby edges.

Has this problem been addressed before?

If the cost is $|P_1|+|P_2|+|P_1∩P_2|$, then a simple reduction to the shortest pair edge disjoint paths gives us a polynomial time solution. For each edge $e=(u,v)$ add two edges $(u,uv)$ and $(uv,v)$ each of them with same edge weight as $e$. The shortest pair edge disjoint paths in the new graph corresponds to the required solution in the original graph.

The algorithm for shortest pair edge disjoint paths is known as Suurballe's algorithm.

https://en.m.wikipedia.org/wiki/Suurballe%27s_algorithm

If the cost is some arbitrary function the problem can be NP-complete.
e.g assuming edge weights one, let the cost function be as $|P_1| + |P_2| + |P_1∩P_2| + 2\cdot |G-P_1\cup P_2|$.
Then the cost is always $ \ge |G|+2$ (if source and terminal are distinct vertices). The equality holds iff the graph has a Hamiltonian cycle.

Let $P_{1}$, $P_{2}$ be two paths in a undirected unweighted graph $G=(V,E)$. We want to minimize the following quantity:

$ C = min_{P_{1},P_{2} \; paths \; in \; G} \{ |P_{1}| + |P_{2}| + |P_{1} \cap P_{2}| \}$.

Also suppose $L$ is the length of the shortest path in $G$, i.e. $L = min_{P \; path \; in \; G} \{ |P| \}$

Clearly, $2L \leq C \leq 3L$, since even if there is no overlap, the second shortest path cannot have length less than $L$ and in the worst case, we can pick two times the same path, which maximizes overlap.

This simple algorithm should solve your problem:

Calculate the shortest path using your favourite algorithm.
Subdivide all edges on the shortest path.
Run your algorithm again on the new graph $G'$ and obtain a second path.
Output the path from 1 and 3 as output, taking care to replace any subdivided edge in it with the original edge.

The running time is asymptotically the same for the usual algorithms,since  $G'$ has at most $|E|+|V|$ edges and $|V|$ nodes and $|E|$ is almost always the dominating term of the runtime. This can be ignored however to always have the same running time (see below).

Correctness lies on the correctness of the original algorithm, as well as the fact that by subdividing we minimize according to the quantity $ |P_{2}| + |P_{1} \cap P_{2}| $, as desired.

Finally, note that most algorithms may work with weights from $\mathbb{N}$ with no additional cost, so instead of subdividing one may simply double the weight of the edges along the shortest path. This method is more general and shows that the algorithm works equally well on weighted variants of the problem.

Note that it is not necessary for the shortest path to be part of the optimal solution. See the comments for a discussion on this and thus why my proposed algorithm does not guarantee optimality.


Does bisimulation or the approximation lemma work for monadic streams? For ordinary streams $S_A := \nu X. A \times X$, there is a bisimulation lemma. It says that two streams are equal if there exists a bisimulation between them. A bisimulation is a relation $\sim$ on streams defined like this:
$s_1 \sim s_2 \iff \operatorname{head} s_1 = \operatorname{head} s_2 \wedge \operatorname{tail} s_1 \sim \operatorname{tail} s_2$.

Now, let $M$ be a monad. We'll define the type of "monadic streams" $S^M_A := \nu X. M (A \times X)$. Intuitively, if $M$ corresponds to a side effect, every time I retrieve the head from the stream I have to perform the side effect. I can define $\operatorname{head}^M: S^M_A \to M A$ and $\operatorname{tail}^M: S^M_A \to M S^M_A$ (using functoriality of $M$).

My question is now: Is there anything similar to bisimulation for monadic streams? Can I prove equality of monadic streams in the same way, using $\operatorname{head}^M$ and $\operatorname{tail}^M$? If not, what are proof methods that work on this coinductive type? Maybe the approximation lemma?

Edit: Maybe there has to be a restriction on the monad, like being completely positive?

Here's a well written piece explaining what the proper definition of a stream monad should be: Proper Definition of the Stream Monad

The resumption and reactive resumption monads are similar to the stream monad:Resumption Monad Transformers


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

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

Quote:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

You can do a lots of experiments on speeds and velocities, and you will obtain overwhelming evidence to validate Newton's laws. Of course, you will see some very strange things in very particular experiments, like the speed of light in moving water, or some astronomical events. But your overwhelming pieces of evidence will say to you : Newton is right and those laws are what you need

Of course, Newton "is not right", and Einstein came after him.

For P=NP, we can see a lots of example where it seems P≠NP. But in some particular cases, we have strange things. If P≠NP, there are an infinite number of classes between them, so we should find some problems in NP that are not in P, but are not NP-complete. We don't know any of them, and most candidates were proven to be in P.

What you think about this problem depends on where you want to look at. I would not be surprised if P=NP.


Programming Language Theory and Abstract Algebra Are there any applications of Abstract Algebra to Programming Language Theory? Is there anything that would be useful in language design and compiler implementation?

Algebra in the classical sense of the word is used in modeling of computational effects as algebraic operations, see for example these slides by Gordon Plotkin, or you can read real papers and Ph.D. theses, if you actually meant to ask the question.

And to blow my own horn, have a look at Eff and read about it, a language designed around the idea that computational effects are algebraic operations and that handlers are homomorphisms of algebras.

Actually there a software for theorical abstract algebra. This soft allow compute some kinds of things like actions groups, Homomorphism etc...
It is Magma: http://magma.maths.usyd.edu.au/magma/

I hope this can help you.


What are the recent TCS books whose drafts are available online? Following the post What Books Should Everyone Read, I noticed that there are recent books whose drafts are available online.

For instance, the Approximation Algorithms entry of the above post cites a 2011 book (yet to be published) titled The design of approximation algorithms.

I think knowing recent works is really useful for whoever wants to get a taste of TCS trends. When drafts are available, one can check the books before actually buying them.

So,

  What are the recent TCS books whose drafts are available online?

Here, by "recent", I mean something that's no older than ~5 years.

Several TCS books by Now Publishers can be found in drafts:

Foundations of Cryptography– A Primer by Oded Goldreich. This is a summarized version of his famous two-volume book on cryptography. (The draft of the two-volume version can be found in Robin's answer.)
Data Streams: Algorithms and Applications by S. Muthukrishnan.
Mathematical Aspects of Mixing Times in Markov Chains by Montenegro & Tetali.
Pairwise Independence and Derandomization by Luby & Widgerson.
Average-Case Complexity by Bogdanov & Trevisan.
A Survey of Lower Bounds for Satisfiability and Related Problems by Melkebeek.
Algorithms and Data Structures for External Memory by Vitter.
Probabilistic Proof Systems: A Primer by Goldreich. Again, this is a summarized version of a part Goldreich's book Modern Cryptography, Probabilistic Proofs and Pseudorandomness.
The Design of Competitive Online Algorithms via a Primal-Dual Approach by Buchbinder & Naor.
Spectral Algorithms by Kannan & Vempala.
On the Power of Small-Depth Computation by Viola.
Algorithmic and Analysis Techniques in Property Testing by Ron.
Arithmetic Circuits: A Survey of Recent Results and Open Questions
by Amir Shpilka and Amir Yehudayoff (2010), Foundations and Trends® in Theoretical Computer Science: Vol. 5: No. 3–4, pp 207-388. http://dx.doi.org/10.1561/0400000039

In addition, drafts of several Springer books on "Information Security and Cryptography" can be found online:

Cryptography in Constant Parallel Time by Applebaum.
A Study of Statistical Zero-Knowledge Proofs by Vadhan.
Locally Decodable Codes and Private Information Retrieval Schemes by Yekhanin.
Concurrent Zero Knowledge by Rosen.

Foundations of Data Science by John Hopcroft and Ravindran Kannan. It's an amazing book on Algorithms for Big Data Analytics. They call it the 21st century algorithms.


Which algorithms have been proposed to learn the architecture of a deep neural network? Yoshua Benhgio's Learning Deep Architectures for AI book mentions that

  we should [...] strive to develop learning algorithms that use the data to determine the depth of the ﬁnal architecture.

Would anyone know of any algorithms proposed thus far to achieve this?

So far I have come across:

The tiling algorithm for building a feed-forward network to learn a Boolean function. It adds layers as well as units, but Boolean functions aren't too relevant for applied problems.

This predates the start of the "deep learning craze" in the mid-2000s, but for me the cascade correlation algorithm (Fahlman & Lebiere, 1989; pdf) is the build-your-own-topology NN algorithm. I am not sure how popular the algorithm is in ML now-a-days, but it is still popular in cognitive science despite it's unrealistic grounding in biology. If you want intersections with genetic algorithms (like the one @vzn points out with more recent examples) then that has been done with CC as well (Potter, 1992; pdf).

You might also find the following questions on other SEs to be of interest:

Why do neural networks seem to perform better with restrictions placed on their topology?
Dynamically adjusting NN architecture: inventing the unnecessary? (also on MetaOptimize)

here are two other more recent papers that touch on this. as AK cites, cascade correlation algorithms were designed around ~1990 for this purpose of dynamic ANN growth but they seem not to be applied in deep learning experiments so far. the 2nd paper below cites cascade correlation as an inspiration for an incremental/online algorithm that adds feature detectors over time built out of lower-level feature detectors.

Learning Android Control using Growing Neural Networks 2006 Amor et al

  Fixed sized neural networks are a popular technique for learning the adaptive control of non-linear plants. When applied to the complex control of android robots, however, they suffer from serious limitations, such as the moving target problem i.e. the interference between old and newly learned knowledge. To overcome these problems, we propose the use of growing neural networks in a new learning framework based on the process of consolidation.

this paper comes from Deep learning and unsupervised feature learning NIPS workshop 2012. Online Representation Search and
Its Interactions with Unsupervised Learning by Mahmood/Sutton. see fig 4 p4. the network performance vs incremental growth in feature detectors is graphed.

  We consider the problem of finding good hidden units, or features, for use in multilayer neural networks. Solution methods that generate candidate features, evaluate them, and retain the most useful ones (such as cascade correlation and NEAT), we call representation search methods. In this paper, we explore novel representation search methods in an online setting, compare them with two simple unsupervised learning algorithms that also scale online.


Find the remainder of a large fixed polynomial when divided by a small unknown polynomial Assume we operate in a finite field. We are given a large fixed polynomial p(x) (of, say, degree 1000) over this field. This polynomial is known beforehand and we are allowed to do computation using a lot of resources in the "initial phase." These results may be stored in reasonably small look-up tables.

At the end of the "initial phase", we will be given a small unknown polynomial q(x) (of, say, degree 5 or less).

Is there a fast way to compute p(x) mod q(x) given that we are allowed to do some complicated calculations in the "initial phase"? One obvious way is to calculate p(x) mod q(x) for all possible values of q(x). Is there a better way to do this?

The following algorithms works well if the underlying field has a very small order $s$.

Suppose we know $q$ is irreducible, of a fixed degree $d$. Then, mod $q$, we know $x^{s^d} = x$ holds. Hence it suffices to pre-compute $p(x) \mod x^{s^d} - x$.

In general, $q(x)$ may decompose into a product of irreducible polynomials $q = q_1 \dots q_r$. In this case, a similar argument applies to computing $p$ modulo each $q_1, \dots, q_r$ separately, and then piecing the results together. So we really need to compute $p(x) \mod x^{s^{d'}} - x$ for each $d' \leq d$.

See excellent comments about this post below. :)

Preprocessing; input: $p(x)$

Factor $p(x)$ as $p(x)=\prod_{i=0}^{1000} (x_i-r_i)$.
Store this as a table $T$ of distinct roots $r_j$ and their respective
multiplicities $m_j$.

Online phase; input: $q(x)$

Factor $q(x)$ as $q(x)=\prod_{i=0}^5 (x_i-r'_i)$.
Store this as a list $L$ of distinct roots $r'_j$ and their respective
multiplicities $m'_j$.
While $L$ is not empty, remove the next root/multiplicity from $L$ and any like terms in $T$.
Read off $p(x)\bmod{q(x)}$ from the modified table $T$ and output.

Other comments:

Obviously you want to sort the table $T$ and access it with binary search (or a tree).
(Let $d$ be the degree of $p(x)$.) If you want the output $p(x)\bmod{q(x)}$ to be in coefficient representation, you can just do a bunch of FFTs at the end to get $\tilde{O}(d)$ time.
Depending on how you formalize it, you can probably pre-compute a lot of the various ways you'd recombine the terms in $T$ beforehand (dynamic programming style), so that most (or all) of the multiplications are just look-ups. The dominating cost is then the number of look-ups, or roughly $O(\log d)$. If $d=1000$, this is just a handful of concrete, arithmetic operations.


A simple decision problem whose decidability is not known I am preparing for a talk aimed at undergraduate math majors, and as part of it, I am considering discussing the concept of decidability.  I want to give an example of a problem that we do not currently know to be decidable or undecidable.  There are many such problems, but none seem to stand out as nice examples so far.

What is a simple-to-describe decision problem whose decidability is open?

The Matrix Mortality Problem for 2x2 matrices.  I.e., given a finite list of 2x2 integer matrices M1,...,Mk, can the Mi's be multiplied in any order (with arbitrarily many repetitions) to produce the all-0 matrix?

(The 3x3 case is known to be undecidable.  The 1x1 case, of course, is decidable.)

there is a fairly natural way to map most open problems onto questions of (un)decidability. most open problems generally are not known to be provable or unprovable.

on the web there is some informal confusion about the undecidability of the P vs NP problem, which is not strictly a decision problem, therefore to talk about its undecidability is not technically correct. but on the other hand there does seem to be a close/natural link between undecidability and provability as follows.

for example consider

  the language $L$ of binary strings where a string/integer $x$ is in the language iff there exists a $O(n^x)$ DTime TM that solves an NP complete problem

is this language decidable? that is an question about a language with its decidability open that is basically closely tied (even, virtually identical) to the P vs NP problem and its inherent (un?)provability.

as for P vs NP as "simple to describe", it only requires concepts of TMs, Big O runtime notation, nondeterminism which are a fairly simple (some of the most basic concepts of TCS) and taught at the undergraduate level or which a gifted high school student could understand.

in fact NP vs P/Poly is also open, and can be mapped onto an open question about decidability in the same way, and this can be stated as a fairly simple problem about the growth of minimal (monotone?) circuits to recognize NP complete problems (eg cliques).


Deciding whether the sum of independent random variables exceeds a threshold a majority of the time, PP-hard? Say I have $n$ independent Bernoulli random variables, with parameters $p_1,\ldots,p_n$. Say, also, that I wish to decide whether their sum exceeds some given threshold $t$ with probability at least $0.5$. What is the computational complexity of this decision problem, when $p_1,\ldots,p_n$ and $t$ are represented in binary and given as input?

More generally, I'm interested in the generalization of this problem to (non-Bernoulli) discrete distributions. Specifically, there are $n$ independent random variables, each supported on at most $m$ rational numbers, with each variable's probability histogram given explicitly in the input. In this case, also, I want to decide whether the sum of these variables exceeds $t$ with probability at least $0.5$.

I have a feeling this problem is PP-hard, though I can't quite prove it. I wonder what the answer is, and whether it's already known.

Note that I'm not looking for approximation algorithms for this problem. It's clear that monte carlo methods yield positive answers to approximate versions of this decision problem. I'm interested in the exact decision problem as stated above.

The general (non-bernoulli) problem is #P hard, via a reduction from #Knapsack.

#Knapsack is the problem of counting the solutions to an instance of the knapsack problem. This problem is known to be #P complete. An equivalent way to think of the #Knapsack problem is the following: You are given a set of integers $a_1,\ldots,a_n$ and a threshold $t$. Let $x_i$ be a random variable which is either $0$ or $a_i$ with equal probability, and assume those random variables are independent. Compute the probability that $\sum_i x_i \leq t$.

It is not too hard to see that the #Knapsack problem could be equivalently defined as the problem of computing the probability that $\sum_i x_i \geq t$ (simply flip the sign of all the integers and add a large constant). Therefore, had I stated my problem with an arbitrary probability $p$ rather than $0.5$, the problem stated in the question can be interpreted as the decision version of #knapsack. A reduction of #knapsack to its decision version via binary search would then complete the #P hardness proof.

The way I defined the problem, however, fixed a particular threshold 0.5. It's not too hard to see that this doesn't make the problem easier. We can reduce the decision problem with probability $p\leq 0.5$ to the problem with $p=0.5$ by simply adding an additional random variable $x_0$ which is equal to the threshold $t$ with probability $\frac{0.5-p}{1-p}$ and $0$ the rest of the time. For $p > 0.5$, a similar reductions lets $x_0$ be $-M$ for a sufficiently large $M$ with probability $\frac{p-0.5}{p}$ and $0$ otherwise; if you don't like negative numbers, simply shift all random variables and the threshold $t$ up by a suitable constant.

A polynomial time and space algorithm exists for the sum of any discrete independent R.V.
Let $x_1+ ...+ x_n$ be the sum of independent variables.
Working incrementally: $Z_2=X_1+X_2$
Then

$P(Z_2=z)=\sum_{i=-\infty}^{+\infty} P(X_1=i) \cdot P(X_2=z-i) $

This is by definition the convolution of the two distributions (denoted by *)

$P_{z_2}= P_{x_1} * P_{x_2}$

The vectors $P_{x_1} , P_{x_2}$ are zero padded to the length $L$ of the sum of their lengths.

Using the convolution theorem

$ P_{z_2}={\mathcal  {F}}^{{-1}}{\big \{}{\mathcal  {F}}\{P_{x_1}\} \cdot{\mathcal  {F}}\{P_{x_1}\}{\big \}}$

Computing the fourier and inverse  fourier transforms  using FFT is an $O(L log L)$ operation, and the element-wise product requires $L$ operations. all in all, the "combination" of the r.vs into the distribution of their sum takes  $O(L log L)$  time.

Computing the distributions of the sums of n variables is computed iteratively:
Let $Z_k=X_1+...+X_k$. Then

$P_{z_n}=P_{z_{n-1}}*P_{x_n}$

For $n$ variables this takes approximately $O(n^2)$ time.

Given that the pdf is computed, the cdf is a trivial $O(n)$ operation.


Is there a generalization of the GO game that is known to be Turing complete? Is there a generalization of the GO game that is known to be Turing complete?

If no, do you have some suggestions about reasonable (generalization) rules that can be used to try to prove that it is Turing complete?  The obvious one is that the game must be played on an infinite board (positive quadrant). But what about in-game play and end game conditions?

Related:  Rengo Kriegspiel, a blindfolded, team variant of Go, is conjectured to be undecidable.

http://en.wikipedia.org/wiki/Go_variants#Rengo_Kriegspiel

Robert Hearn's thesis (and the corresponding book with Erik Demaine) discuss this problem.  They prove other problems undecidable through "TEAM COMPUTATION GAME", which is reduced directly from Turing machine acceptance on empty input (see Theorem 24 on page 70 of the thesis).  So it seems to me that such a reduction would imply Rengo Kriegspiel is Turing complete.

On the other hand, their discussion says that this reduction would be very difficult (see page 123). So while this is a potential avenue, it appears that it has been looked into previously.

In my patent application - Turing Complete Sets of Game Components with Divinatory Elements - I describe variants for game rules (including games played on a 19x19 Go board) which add a degree of complexity to games like chess and Go allowing for board positions to simulate linear bounded automata for an arbitrarily long period of time. As mentioned in the comments above, Go on an infinite board would introduce some difficulties as far as determining a game winner, since it is a game with a territorial objective, unlike chess. From my application: "Many other Turing complete game embodiments are possible, but I will give just two more brief descriptive examples to illustrate some other possibilities for adapting games to be played as Turing complete variants and then discuss ramifications. Games like Gomoku (SCARNE, p. 537) and Go (SCARNE, pp. 533-7) which are played on a 19×19 grid with two different colors of pieces are also candidates for Turing complete variants with divinatory elements. In the case of these games, Rogozhin's (2,18) UTM is used. This is also the UTM used by Churchill (2012) as cited in the prior art references. In order to create a game variant of this type, we will use coins for our game pieces. Prepare to play the chosen game variant by sorting large quantities of two different coins--pennies and dimes for example--into piles based on the date on their obverse sides. In this case, dates on the coins will be used as a substitute for colors in the context of the UTM instructions. Colors have been used for UTM instructions in the previously described embodiments, but this embodiment illustrates that another attribute of the game components, in this case a number, may be used. In the most general case, I will refer to this potential for substituting another attribute of the game components in place of colors as a use of a subset of the set of game components. Each player should start with 19 stacks of 19 of their chosen coin. Each stack of pennies and dimes should contain only coins with the same date--let's say, for example, 19 pennies dated 1991, 19 dimes dated 1991, 19 pennies dated 1992, etc. through 19 dimes dated 2009. A coin may only be played in the leftmost column of the board if it has a 1991 date, the next column to the right requires a coin with the 1992 date, etc. through to 2009 in the rightmost column. Play a game of Go or Gomoku as normal except for this rule regarding which pieces may be played where. When the (2,18) UTM is initiated based on pre selected game criteria (in a similar manner to that described in other embodiments) the UTM read/write head will read a heads up coin as being in state 1 and a heads down coin as being in state 2. A coin with the date 1991 will be considered an A coin by the UTM, 1992=B, 1993=C, etc. skipping over the year 2000. Coins are replaced by others with different dates according to the UTM instructions. As far as divinatory elements are concerned, there are 360 degrees in the zodiac and 360 intersections surrounding the central intersection on a Go board, so Sabian symbols (ROCHE) are an obvious fit. For more divinatory aspects of a Go board and game, see "The Religious Dimensions of Go" (SCHNEIDER)." Go game scenarios where a pre agreed UTM analysis of a board position might be useful include boards with triple kos and boards with long ko fights.

Is the trade off between adding additional complexity in rules in order to introduce Turing completeness to tabletop games worth the effort? Likely the answer to that question depends on the game and the players, but Magic: the Gathering is an example that in at least some cases the answer to that question is likely to be yes.


Is black box parallel quantum speedup ever nontrivial? Grover's algorithm is not parallelizable, in that $p$ quantum processors searching over $n$ elements can't do better than $O(\sqrt{n/p})$ queries.

Are there any oracle problems where quantum computers see some polynomial speedup over classical, but where the algorithm is nontrivially parallelizable?  Here's one attempt at formalizing this:

Question: Are there any oracle problems such that

The classical complexity is $O(t)$, and achieves perfect parallel speedup to $O(t/p)$.
The quantum complexity is $O(t^\alpha)$ for $\alpha \in [1/4,1)$.
The parallel quantum complexity is $O(t^\alpha / p^\beta)$, with $\beta \in (\alpha,1]$.

Even better, is there a problem where $\beta = 1$ (perfect parallel quantum speedup)?

Methinks, you do not understand the black-box magic of quantum processors.

It shall cover all n elements of a task by its cubits, otherwise, there would not be happen collapse of superposition over all input's elements and you would not even calculate anything.

For example, factorization algorithm: There shall be n + k cubits, where n - is a dimension of input, and k is support engine.

If your processor can not reach this dimension, you are not able to split input in n/p parts and feed p different processors to summarize result after, on exit...

Super-position of sum of p processors will be much lesser then super-position of one big n dimension processor. And quantum magic is exactly hidden in this dimension, means - number of cubits.

E.g. 3 CPU x 3 cubits each; This will give us such fields:

1st 2nd 3rd
000 000 000
001 001 001
010 010 010
011 011 011
100 100 100
101 101 101
110 110 110
111 111 111

This is how superposition will looks like. Three small quantum registers. And this field - is our calculation power here.

But, when you'll take One Big CPU with 9 cubits, this will give you 2^9 dimension = 512 different boolean vectors. And system will be in all of its while in super-position.

The "memory" of such quantum computer in super position will be much bigger:

000000000 000000001 000000010 000000011 000000100 000000101 000000110 000000111
000001000 000001001 000001010 000001011 000001100 000001101 000001110 000001111
000010000 000010001 000010010 000010011 000010100 000010101 000010110 000010111
000011000 000011001 000011010 000011011 000011100 000011101 000011110 000011111
000100000 000100001 000100010 000100011 000100100 000100101 000100110 000100111
000101000 000101001 000101010 000101011 000101100 000101101 000101110 000101111
000110000 000110001 000110010 000110011 000110100 000110101 000110110 000110111
000111000 000111001 000111010 000111011 000111100 000111101 000111110 000111111
001000000 001000001 001000010 001000011 001000100 001000101 001000110 001000111
001001000 001001001 001001010 001001011 001001100 001001101 001001110 001001111
001010000 001010001 001010010 001010011 001010100 001010101 001010110 001010111
001011000 001011001 001011010 001011011 001011100 001011101 001011110 001011111
001100000 001100001 001100010 001100011 001100100 001100101 001100110 001100111
001101000 001101001 001101010 001101011 001101100 001101101 001101110 001101111
001110000 001110001 001110010 001110011 001110100 001110101 001110110 001110111
001111000 001111001 001111010 001111011 001111100 001111101 001111110 001111111
010000000 010000001 010000010 010000011 010000100 010000101 010000110 010000111
010001000 010001001 010001010 010001011 010001100 010001101 010001110 010001111
010010000 010010001 010010010 010010011 010010100 010010101 010010110 010010111
010011000 010011001 010011010 010011011 010011100 010011101 010011110 010011111
010100000 010100001 010100010 010100011 010100100 010100101 010100110 010100111
010101000 010101001 010101010 010101011 010101100 010101101 010101110 010101111
010110000 010110001 010110010 010110011 010110100 010110101 010110110 010110111
010111000 010111001 010111010 010111011 010111100 010111101 010111110 010111111
011000000 011000001 011000010 011000011 011000100 011000101 011000110 011000111
011001000 011001001 011001010 011001011 011001100 011001101 011001110 011001111
011010000 011010001 011010010 011010011 011010100 011010101 011010110 011010111
011011000 011011001 011011010 011011011 011011100 011011101 011011110 011011111
011100000 011100001 011100010 011100011 011100100 011100101 011100110 011100111
011101000 011101001 011101010 011101011 011101100 011101101 011101110 011101111
011110000 011110001 011110010 011110011 011110100 011110101 011110110 011110111
011111000 011111001 011111010 011111011 011111100 011111101 011111110 011111111
100000000 100000001 100000010 100000011 100000100 100000101 100000110 100000111
100001000 100001001 100001010 100001011 100001100 100001101 100001110 100001111
100010000 100010001 100010010 100010011 100010100 100010101 100010110 100010111
100011000 100011001 100011010 100011011 100011100 100011101 100011110 100011111
100100000 100100001 100100010 100100011 100100100 100100101 100100110 100100111
100101000 100101001 100101010 100101011 100101100 100101101 100101110 100101111
100110000 100110001 100110010 100110011 100110100 100110101 100110110 100110111
100111000 100111001 100111010 100111011 100111100 100111101 100111110 100111111
101000000 101000001 101000010 101000011 101000100 101000101 101000110 101000111
101001000 101001001 101001010 101001011 101001100 101001101 101001110 101001111
101010000 101010001 101010010 101010011 101010100 101010101 101010110 101010111
101011000 101011001 101011010 101011011 101011100 101011101 101011110 101011111
101100000 101100001 101100010 101100011 101100100 101100101 101100110 101100111
101101000 101101001 101101010 101101011 101101100 101101101 101101110 101101111
101110000 101110001 101110010 101110011 101110100 101110101 101110110 101110111
101111000 101111001 101111010 101111011 101111100 101111101 101111110 101111111
110000000 110000001 110000010 110000011 110000100 110000101 110000110 110000111
110001000 110001001 110001010 110001011 110001100 110001101 110001110 110001111
110010000 110010001 110010010 110010011 110010100 110010101 110010110 110010111
110011000 110011001 110011010 110011011 110011100 110011101 110011110 110011111
110100000 110100001 110100010 110100011 110100100 110100101 110100110 110100111
110101000 110101001 110101010 110101011 110101100 110101101 110101110 110101111
110110000 110110001 110110010 110110011 110110100 110110101 110110110 110110111
110111000 110111001 110111010 110111011 110111100 110111101 110111110 110111111
111000000 111000001 111000010 111000011 111000100 111000101 111000110 111000111
111001000 111001001 111001010 111001011 111001100 111001101 111001110 111001111
111010000 111010001 111010010 111010011 111010100 111010101 111010110 111010111
111011000 111011001 111011010 111011011 111011100 111011101 111011110 111011111
111100000 111100001 111100010 111100011 111100100 111100101 111100110 111100111
111101000 111101001 111101010 111101011 111101100 111101101 111101110 111101111
111110000 111110001 111110010 111110011 111110100 111110101 111110110 111110111
111111000 111111001 111111010 111111011 111111100 111111101 111111110 111111111

You can factorize number lesser than 2^9, for example 465 on such QCPU, but you can not factorize this number on bunch of little QCPU with 3 cubits per each.

465 - it is 111 010 001. So, how do you plan to split it, to feed by parts to each little QCPU? First will factorize 111, second 010, third 001? And how to sum such result on exit? There is no way.

As you can see, 3 QCPU x 3cubits - is not the same as 1 QCPU x 9cubits.
And each new cubit increase power of QCPU by multiplying its calculation field on two. x2, x2, x2, x2... so, you could fast reach the number of stars in the visible universe or even atoms, or quarks,.. photons... and even exceed it... Simply, knot more and more cubits in superposition. But you can not achieve the same, by printing more and more small quantum computers, because the effect will be linear, not exponential.


Complexity class of this problem? I am trying to understand to which complexity class the following problem belongs:

Exponentiating Polynomial Root Problem (EPRP)

Let $p(x)$ be a polynomial with $\deg(p) \geq 0$ with coefficients drawn from a finite field $GF(q)$ with $q$ a prime number, and $r$ a primitive root for that field. Determine the solutions of:
$$p(x) = r^x $$
(or equivalently, the zeros of $p(x) - r^x$) where $r^x$ means exponentiating $r$.

Note that, when $\deg(p)=0$ (the polynomial is a constant), this problem reverts to the Discrete Logarithm Problem, which is believed to be NP-Intermediate, i.e. it is in NP but neither in P nor NP-complete.

To the best of my knowledge, efficient (polynomial) algorithms to solve this problem  do not exist (Berlekamp and Cantor–Zassenhaus algorithms require exponential time). Finding roots to such equation can be done in two ways:

Try all possible items $x$ in the field, and check whether they
satisfy the equation or not. Clearly, this requires exponential time in the bitsize of the field
modulus;
The exponential $r^x$ can be rewritten in polynomial form, by using
Lagrange interpolation to interpolate the points
$\{(0,r^0),(1,r^1),\ldots,({q-1},r^{q-1})\}$, determining a
polynomial $f(x)$. This polynomial is identical to $r^{x}$ precisely because we are working on a finite field. Then, the difference $p(x) - f(x)$, can be
factored in order to find the roots of the given equation (using
Berlekamp or Cantor–Zassenhaus algorithms) and the roots read off the factors. However, this approach is
even worse than exhaustive search: since, on average, a polynomial
passing by $n$ given points will have $n$ non-null coefficients, even
only the input to Lagrange interpolation will require exponential
space in the field bit size.

Does anyone know if this problem is believed to be NP-intermediate as well or belonging to any other complexity class ? A reference will be greatly appreciated. Thanks.

will take a stab at answering this. there are no refs given in the question but it is given an acronym "EPRP" as if more than one person has studied it. does anyone know if that is the case? the questioner MC seems to have significant bkg in this area but it would help significantly to list some "nearby" refs known/reviewed to understand why they have some gap that doesnt (?) cover this supposedly special case.

it usually helps to find "nearest available refs" and determine how the problem is different or similar. here is a comprehensive ref that seems to consider closely related problem(s). think that the questioner MC should try to locate the nearest case of the problem in this ref, or maybe some other one, and then point out how this case asked about is specifically different than general problem cases given in the ref. the ref has a long list of related refs to also check for nearby/related problem(s). he considers the complexity of the problem and gives efficient P-time algorithms for various cases.

ON SOLVING UNIVARIATE POLYNOMIAL
EQUATIONS OVER FINITE FIELDS
AND SOME RELATED PROBLEMS
Tsz Wo Sze, Doctor of Philosophy, 2007

  ...we present a deterministic polynomial-time algorithm to
  solve polynomial equations over some families of finite fields. Note that polynomial
  equations are powerful constructs. Many problems can be formulated as polynomial
  equations.


Optimization Problem on a Directed Graph I have the following graph optimization problem. In a directed graph $G$, each node $i$ is endowed with a real value $v_i$ (input) that encodes the minimum "activation threshold" of that node. For each node we can compute the "activation value" $a_i$ as a sum of the activation values of the selected predecessor nodes, i.e.:
$$a_i = \sum_{j \in P(i)}x_{ji}a_{j}$$
where $x_{ij} \in \{0,1\}$ are edge selector variables and $P(i)$ is the set of predecessor nodes of $i$. The optimization objective is for each node in the graph to select a set of incoming edges with minimal cost that "activate" that node:

$$\underset{x}{\text{argmin  }}\sum_{i} \sum_{j \in P(i)} a_ix_{ji}$$
$$\text{  such that  }  \sum_{j \in P(i)}x_{ji}a_{j}\ge v_i, \forall{i}$$

We can assume that there exist some leaf nodes in the graph whose activation value is 1, and that each node in the graph can be activated for a large enough subset of incoming edges.

If $G$ is a DAG, then we can solve this with dynamic programming, but I can't seem to figure out if there is a way to do this on a general DG, or if its NP hard.

Any pointers are appreciated. Thanks a lot.

lemma 1. The posted problem (as I understand it) is NP-hard, even on DAGs,

Proof. The proof is by reduction from Subset Sum.  Given a Subset Sum instance with $n$ positive integers $x_1, x_2, \ldots, x_n$ and target $T$, the reduction produces the following instance of your problem.  The instance will have a minimal solution (one with objective equal to the sum of the activation values -- the minimum possible) if and only if some subset of the $x_i$'s sums to $T$.

Let the $x_i$'s be $b$-bit integers for some $b$, so the input instance has size polynomial in $n$ and $b$ and each $x_i$ is an integer in $\{1,2,\ldots, 2^b\}$.

Construct a "tower" gadget with two leaves $u_0, w_0$ with activation 1.  For each $i\in\{1,2,\ldots, b\}$, add two vertices $u_i, w_i$ each with activation threshold $2^i$ and two incoming edges: $(u_{i-1}, u_i)$, $(u_{i-1}, w_{i})$, $(w_{i-1}, u_i)$, $(w_{i-1}, w_i)$.  In any feasible solution to the instance (so far), each such vertex $u_i$ and $w_i$ will have to use both its incoming edges, and will have incoming activation value exactly equal to its activation threshold $2^i$.

Next, for each integer $x_i$ in the given Subset Sum instance, construct a vertex $X_i$ with activation threshold $x_i$, with edges from every $u_j$.  In any minimal solution, each $X_i$ will use just those incoming edges that represent the binary representation of $x_i$, thereby achieving incoming activation value equal to $x_i$ (and this is always possible).

Finally, construct a "root" vertex $R$ with activation value $T$ (the Subset Sum target) and edges from every vertex $X_i$.  There will be a subset of edges into $R$ to use to achieve activation value $T$ if and only if there is a subset of the $x_i$'s that sums to $T$.  $~~~\Box$

What am I missing?  As I understand the problem, showing NP-hardness seems like a nice homework exercise...

Given that Graphman was last active in 2016, perhaps clarification is not to be had.

I haven't thought of a solution, but here's a way of factoring the problem.

I assume $G$ is finite. Every directed graph can be factored into a DAG of strongly connected components (SCCs) by (IIRC) Tarjan's algorithm.

Pick a vertex $v$ in some root SCC $C$ (i.e. $C$ has in-degree 0 in the DAG of SCCs) where $|C| \geq 2$. If $v$ is activated some in-neighbor must also be activated. But it too must have an activated in-neighbor, etc., and this regress is either infinite, contradicting my assumption that $G$ is finite, or form a cycle, which as far as I understand is ruled out.

So any such $C$ can be eliminated: no vertex in it can be activated.

A non-root SCC $D$ can inductively be eliminated if all the SCCs $C_1, \ldots, C_k$ with edges to $D$ have been thus eliminated: it is a root in the reduced graph.

Maybe it's then possible to solve the remaining SCCs one by one, and combining their solutions using dynamic programming on the DAG of SCCs.

Then again, I'm not sure I fully understand the problem.  Given a 3SAT instance, consider the following graph:

Have three vertices per variable, $y_i$, $t_i$, $f_i$, each having activation requirement $0$, with edges $(y_i, t_i)$ and $(y_i, f_i)$.

For each clause, have a vertex $c_j$ with in-edges from $t_i$ for every variable $x_i$ occurring positively in clause $j$ and from $f_i$ for every variable occurring negatively in the clause. Each clause vertex has activation requirement 1.

Have one vertex $\varphi$ for the formula value, with in-edges from every clause and with activation requirement equal to the number of clauses.

This is almost complete: given a 3SAT instance, add a clause $(x_i \lor \lnot x_i)$ for every variable, then perform the above reduction.

This requires either $t_i$ or $f_i$ to be satisfied (uh, activated) for every variable $x_i$. If the 3SAT instance is satisfiable then some such activation plus a choice of edges into clauses and into the formula gives an edge-minimal way of meeting all activation requirements. If it is not satisfiable, some variable has to be both true and false to satisfy the activation requirements.

3SAT can not be solved in polynomial time (with e.g. dynamic programming) unless P = NP, so I don't quite follow what the dynamic programming solution is. But maybe that's because I misunderstood the problem.

Maybe you can add a loop from $\varphi$ to each $y_i$ to make this construction strongly connected, and give each $y_i$ an incoming activation requirement of 1.

Like I said, I don't quite understand the problem but I hope some of these ideas are helpful.


Complexity Classes for Cases Other Than "Worst Case" Do we have complexity classes with respect to, say, average-case complexity? For instance, is there a (named) complexity class for problems which take expected polynomial time to decide?

Another question considers the best case complexity, exemplified below:

Is there a class of (natural) problems whose decision requires at least exponential time?

To clarify, consider some EXP-complete language $L$. Obviously, not all instances of $L$ require exponential time: There are instances which can be decided even in polynomial time. So, the best case complexity of $L$ is not exponential time.

EDIT: Since several ambiguities arose, I want to try to clarify it even more. By "best case" complexity, I mean a complexity class whose problems' complexity is lower bounded by some function. For instance, define BestE as the class of languages which cannot be decided in time less than a some linear exponential. Symbolically, let $M$ denote an arbitrary Turing machine, and $c$, $n_0$, and $n$ be natural numbers:

$L \in \mathbf{BestE} \Leftrightarrow$
$\quad (\exists c)(\forall M)[(L(M) = L) \Rightarrow (\exists {n_0})(\forall n > {n_0})(\forall x \in {\{0,1\}^n})[T(M(x)) \ge {2^{c|x|}}]]$

where $T(M(x))$ denotes the times it takes before $M$ halts on input $x$.

I accept that defining such class of problems is very odd, since we are requiring that, every Turing machine $M$, regardless of its power, cannot decide the language in time less than some linear exponential.

Yet notice that the polynomial-time counterpart (BestP) is natural, since every Turing machine requires time $|x|$ to at least read its input.

PS: Maybe, instead of quantifying as "for all Turing machine $M$," we have to limit it to some pre-specified class of Turing machines, such as polynomial-time Turing machines. That way, we can define classes like $\mathbf{Best(n^2)}$, which is the class of languages requiring at least quadratic time to be decided on polynomial-time Turing machines.

PS2: One can also consider the circuit-complexity counterpart, in which we consider the least circuit size/depth to decide a language.

Although I can't quite parse your definitions, you should know that much stronger time hierarchies are known, in particular "almost everywhere" time hierarchies.

Here is the formal statement: for every time bound $T(n)$, there is a language $L \in TIME[T(n)]$ with the property that every deterministic algorithm that correctly recognizes $L$ must run in time asymptotically greater than $t(n)$ on all but finitely many inputs, for sufficiently small time $t(n)$.

"Sufficiently small" means $t(n) \log t(n) \leq o(T(n))$.

Suppose we choose $T(n)=2^n$ for an example, and obtain a hard language $L$. Then, any algorithm that correctly recognizes $L$ must take at least $2^n/n^2$ time on all inputs past a certain length. This seems to be what you're looking for in your class BestE.

Reference:

  John G. Geske, Dung T. Huynh, Joel I. Seiferas: A Note on Almost-Everywhere-Complex Sets and Separating Deterministic-Time-Complexity Classes Inf. Comput. 92(1): 97-104 (1991)

It seems that every problem has $O(1)$ best case complexity. Consider an algorithm that always outputs the solution to a particular instance. That instance is the best case.


In the neutral zone between polynomial and sub-exponential What are examples of problems that are known to be sub-exponential, but

are known to be non-polynomial, or
are not known to be polynomial?

EDIT. Here is what I mean by sub-exponential (apologies for leaving this open). A function $f:\mathbb{N}\to\mathbb{N}$ is subexponential if $$f(n) = 2^{n^{o(1)}}.$$ (Thanks to Emil Jerabek for his help in the comment section below!)

Graph Isomorphism is known to be in quasipolynomial time but not known to be in polynomial time: https://arxiv.org/abs/1512.03547
You can also come up with synthetic problems by the time hierarchy theorem, which essentially states that there are problems at any (deterministic) time complexity but not below: https://en.wikipedia.org/wiki/Time_hierarchy_theorem

Problems in $NTIME[f(n)]$ where $f(n)=\omega(\log n)$ and $f(n)=o(n)$ are not known to be in $DTIME[n^c]$ at any $c\geq1$ while known to be in $DTIME[2^{o(n)}]$.

Conversely there are problems not known to be in $NTIME[f(n)]$ where $f(n)=\omega(\log n)$ and $f(n)=o(n)$ and also not known to be in $DTIME[n^c]$ at any $c\geq1$ while known to be in $DTIME[2^{o(n)}]$.

Examples of $2$ include factoring and discrete logarithm.