Physical realization of nonlinear operators for quantum computers. I have read in a paper where nonlinear operators for quantum computers implies the solving of problems in #P time. See http://arxiv.org/pdf/quant-ph/9801041 .
What would be the simplest realization of this? Could you limit its power to solve easy problems in #P Also is this equiavlent to $PostBQP$ or any other complexity class?

Short answer: if you believe quantum mechanics is an accurate description of nature, then since QM is a linear theory, it isn't possible to physically realize nonlinear operations.

As far as we know, the only nonlinear operation in quantum mechanics is that of measurement, but it's of a very restricted kind: measurement only happens at the end of your computation, and it doesn't allow you to amplify exponentially small amplitudes into non-trivial ones (except with negligible probability).

On the other hand, the kinds of nonlinearities discussed by the Abrams and Lloyd paper (as well as others) are generally those that allow you to take a quantum state with exponentially small amplitude, and amplify it to something nontrivial. We don't believe that it is possible to physically realize these nonlinear operations. Why? If it were possible, then you would be able to solve #P problems efficiently! From a complexity point of view, this consequence effectively chucks out the assumption. Being able to solve NP-complete problems efficiently is laughable; to handle #P with ease is a bad joke taken a little too far. The Abrams and Lloyd paper can be understood as an argument against the possibility of nonlinear quantum mechanics.

To try to answer the last part of your question: if there existed nonlinear quantum gates like described in the Abrams and Lloyd paper, then PostBQP could certainly be simulated by their nonlinear quantum computer (because PostBQP = PP by a result of Aaronson, and their nonlinear quantum computer can solve #P-complete problems efficiently).

As the accepted answer implies, Quantum Mechanics is a linear theory. That means that unless there is a deeper theory that supersedes it (just as it & Einstein's General Relativity jointly replaced Newtonian Mechanics), then you cannot have non-linear evolution of quantum systems.

BUT, there is a mighty big catch there: There almost certainly IS a deeper theory that supersedes it, a theory of "quantum gravity". Quantum physics has no model for gravity, and every attempt to add one has caused the whole thing to fall apart. Our best theory for that force, General Relativity, IS nonlinear and is has survived just as much experimental scrutiny as quantum physics.

The upshot is this: For a machine powered purely by known quantum physics, you won't be able to solve NP-complete problems in polynomial time. But that is a far weaker statement than asserting that the laws of physics definitely PRECLUDE solving NP-complete problems efficiently. Start running that quantum computer in a high gravity field and WE DON'T KNOW what will happen. And given that there are plenty of examples in mathematics of conjectures thought to be true for CENTURIES that were later dis-proven, failing to have found any polynomial-time algorithm for solving NP-complete problems (or nonlinear quantum operators) after less than 80 years of searching is more "par for the course" than "hard evidence none exists".


Break text evenly into certain number of lines There is a linear time algorithm for breaking text evenly into lines of maximum width. It uses SMAWK (or Knuth & Plass) and "evenly" means:
http://en.wikipedia.org/wiki/Word_wrap#Minimum_raggedness

Is there an algorithm or a concave cost function for algorithm above which would take into account the number of lines I would like the text break into, instead of the maximum line width? Also in linear time?

In other words, I'm looking for a line breaking (or paragraph formation, or word wrapping) algorithm where the input is the desired number of lines, not the desired line width.

Just to describe a practically unusable approach: There are N words and N-1 spaces in-between each word pair, M is the desired number of lines (M <= N). After each space there might be at most one (possibly zero) line-break. Now, the algorithm would try to place the breaks in each possible combination, calculating the "raggedness" and return the best one. How to do it much faster?

Also, does such a problem have a name? What "family" of problems does it belong to? (E.g. "bin packing") If I wouldn't need the perfectly optimal solution, just a very good one, is it possible to solve it much faster? (some form of heuristics could be usable, if for a given input there were always the same, possibly sub-optimal, solution).

Update

Chandra Chekuri suggested bellow "a problem in Kleinberg and Tardos chapter on dynamic programming". It was a good read but it deals with line breaking based on width rather than line count. It might be adaptable to this problem which is something I'm trying to figure out now. Here is a good link to the solution, they even claim to solve it in linear time:
http://web.media.mit.edu/~dlanman/courses/cs157/HW5.pdf

Also, there is a chapter "8.5 The Partition Problem" in The Algorithm Design Manual by Skiena which seems to be exactly on-topic, I'm still reading it, tough. (Unfortunately, from what I understood it has quadratic time complexity)

If you can compute the raggedness of a line without knowing anything about the other lines, then you can model the problem as finding a minimum-weight $M$-link path in a graph. With concave integer weights for edges, there is an algorithm that solves the problem in $O(N \log U)$ time, where $U$ is the largest absolute edge weight. Another algorithm solves the problem in $N 2^{O(\sqrt{\log M \log \log N})}$ time for any concave edge weights, assuming $M = \Omega(\log N)$. Both algorithms assume that you can compute the weight of an edge in constant time.

You could also use binary search to find a line width such that SMAWK uses $M$ lines with it. In some cases, this algorithm does not guarantee a solution with exactly $M$ lines, however.

I don't know if this helps, but towards the end of this comment someone implements what you want in PHP; maybe you can figure out the algorithm.


Log Rank Conjecture Collaborative Approach Recently a post was made in Mathoverflow seeking possible avenues for collaborative projects.

I made a proposal for Log Rank conjecture in https://mathoverflow.net/questions/219638/proposals-for-polymath-projects/219639#219639 which has been well received so far

I feel that this is a good project for collaborative approach.

I know this is a fundamental open problem in CS.

1. Is there a list of possible avenues of research that could open up if progress comes on this topic? For example, I know there are connections to Matrix Rigidity.

2. Could we have a list of possible impact of Log Rank Conjecture and related research in CS?

it seems researchers might be cautious/ unlikely to conjecture/ speculate solution to this problem would likely/ definitely open up other areas (eg one you list of matrix rigidity is provably nearly equivalent to the extremely hard challenge of proving nontrivial lower bounds on eg circuits etc) but it definitely provably touches many areas. here is a nice recent survey (Jan 2015) by Lovett that lists "many connections" sec 6 along with two other refs that show crosscutting connections/ formulations

Recent advances on the log-rank conjecture in
communication complexity / Lovett

6.1 Randomized protocols vs approximate rank
6.2 Quantum protocols for low-rank matrices
6.3 The structure of low-rank sparse matrices, and matrix rigidity

En Route to the log-rank Conjecture:
New Reductions and Equivalent Formulations / Gavinsky, Lovett
On the "log rank"-Conjecture in Communication Complexity / Raz, Spieker


What would be a complete QC circuit? In classical computing NAND is a complete set (functionally complete) of binary operations, namely any Boolean circuit can be expressed using NAND gates.

Is there an equivalent for quantum computing circuit? It should be possible imho to have such a complete set because any rotation ob Bloch sphere is reducible to Euler angles based rotation matrices: $R=X(\alpha)Y(\beta)Z(\gamma)$.

Are there any universal quantum gates?

Not for single gates.

{NAND} may also be represented as two gates {AND, NOT}, and remains a minimally functionally complete set of classical gates.

The Hadamard gate and Toffoli gate are one minimal set of universal quantum gates.


Testing whether a set of n points in the plane form a convex n polygon in o(nlogn) time Assume that you are given a set of n points in the plane and you want to check whether they form a convex n polygon, i.e., if they all lie on the convex hull. I was wondering if anyone knows how to do this in o(nlogn) time, i.e., without computing the CH.

Thats seems unlikely, at least in the comparison/algebraic tree models. Definition first:

A point set $P$ is in convex position if no point of $P$ can be written as a convex combination of the remaining points of $P$.

Now, deciding if a set of $n$ numbers are all distinct takes $\Omega(n \log n)$ time (this is known as UNIQUENESS). Given such a set of $n$ numbers $X$, map them to the set of points
$$
P = \{ (x, x^2) | x \in X\}.
$$
If there is no repeated number, then the points are in convex position.

If there is a repeated number, then this repeated number corresponds to a point that can be written as a convex combination of the remaining points. Namely, the points are not in convex position.

Namely, deciding if a point set is in convex position is as hard as UNIQUENESS.

If you assume all the points are in the convex hull and you can find a point that is inside the convex hull, then you can find the order of the points in $O(n log n)$ time by taking the angle from the interior point to every point in your set and sorting this.

Once you know the order of the points, the angle from each point to the next point in the sequence should be monotonic. This forms a necessary condition and, I think, a sufficient one.

Getting the interior point is left as an exercise for the reader.

Edit: As a fist pass at a simple demonstration of $O(n log n)$ being a hard bound, to show that a point is/isn't on the convex hull requires knowing the adjoining points (possibly an arbitrary number of them) and finding that requires either sorting all the points or (this is speculation) examining more than a constant number of other points.


Is the Balanced Boolean Formula problem solvable in sublogarithmic space if the input has a tree structure? Suppose that instead of the usual linear work tape the input is given in a binary tree structure with n leaves and log n depth, the initial position being the root. At every node, we can step to its parent, left child or right child.

I am interested in what "tree-languages" can be accepted by what machines. More specifically, take the language where in every non-leaf we have the gate of a boolean circuit (ie. and or not), in the leaves either a constant or a variable (different for each leaf) and such a "tree-word" is in the language if and only if it has a satisfying assignment. Can this language be decided by a turing machine that has an o(log n) space worktape?

Note that it is accepted by a non-deterministic finite state machine and also by a deterministic turing machine with O(log n) space. Similarly, if all the variables are constant, then it can be decided by a deterministic finite state machine. (If there are no constants, then every formula is satisfiable.)

It seems to me that the problem can be solved in constant space.

We perform a recursive procedure, and store only the parity of the number of negation gates seen on the path from the root to the current node.

At a leaf, if we have a variable and have seen an even number of negation gates, we set the variable to be true. Otherwise, if we have seen an odd number of negation gates, we set the variable to be false.

As before, at an AND or OR gate we first call recusively to the left, and then to the right if the value has not been determined.

Now if there exists a satisfying assignment, then the assignment defined above will satisfy the formula.

From the question I assume you are talking about exact algorithms and not approximate ones. Since this is the case, you will have to "write" the entire input, using the same space as before, just using a different structure. Although this might provide a speedup in time, the space used will be at least the same, assuming that you use a reasonably efficient representation (e.g. not a unary one).

Using less tape is usually achieved by space re-use or by carefully selecting which cells to overwrite, so that you can use some information later on the computation. However usually you cannot re-use or overwrite the input, since you need it throughout the process of solving the problem.

Even if the above problems were dealt with, the usual model for space complexity has a separate input tape, which is read only and is not measured as used space , so we can have sublinear space complexities and avoid the problems above. Perhaps you are referring to a different model?


Is there a way to solve or approximate the concave program with separable objective? I would like to solve the following problem:
"minimize $\sum_{i=1}^k \sqrt{x_i}$ subject to some polytope constaints."
Is there a polynomial time algorithm to solve or approximate it?
Thanks.

Jian.

I special cases of this problem are a convex optimization problem. If x_i>0, then the objective is a posynomial. If the polytope can be described using posynomials, then the problem becomes a convex optimization problem.

See the tutorial at http://www.stanford.edu/~boyd/papers/pdf/gp_tutorial.pdf which discusses geometric programming and search for posynomial.

--clarification--

See page 73 of the above link.

If your polytope can be described by a posynomial, then you can solve the polytope as a convex programming problem, by converting the problem into an equivalent form.

    Given:
      Minimize f0(x)
      s.t.
      fi(x)<=0 for all i
      fj(x)=0 for all j

Where f0(x) is your original objective and fi(x) is your polytope.

Let x_k an element in x be equal to exp(y_k).
Now, an equivalent problem is cast as:

      Minimize log(f0(exp(y))
      s.t.
      log(fi(exp(y))<=0 for all i
      log(fj(exp(y))=0 for all j

The restriction here is that the only a subset of all polytopes will work in this formulation. However if you can find a reasonable approximation where the polytope is approximated by a set of posynomial constraints, then you will have a computationally fast solution.

--- additional comments ----

The only other approach which might be faster than solving the primal problem is to use KKT conditions to as implied by Ashwinkumar. You can try solving the dual formed from the KKT conditions. Depending on the structure of the polytope, you might be able to find the answer faster.

See http://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions.


When we are using Random Oracle Model There are protocols which make use of invoking an oracle or submitting queries to an oracle and getting response from that. There are many examples in which oracles are used to define security, like IND-CCA security and there are many examples of using the term oracle to just a procedure accepting input and providing some output, independent of the input, like non-information oracles of Canetti (you can refer to my previous question to read more about non-information oracles). My question is about the Random Oracle, that is an oracle with random output.

  When can we determine that we are using the random oracle model? For example, when we use the random output of a hash function, definitely we are in the random oracle model, but if we use one way property of hash function we are not using random oracle model. Can you provide more examples on this?

Let me clarify my ambiguity through an example. In this article the authors use a new oracle which is relatively unknown called linear oracle bilinear Diffie-Hellman (or in short LO-BDH) and security of their approach lies in the hardness of this assumption. How can I determine that using this assumption, we are not using the random oracle model (the authors claim that they are not in the random oracle). Here is another source of ambiguity:

  They are using commitments over UC framework which are impossible in the plain model thus they are at least using common reference string (CRS) model. How can I make sure that if I use such an oracle (LO-BDH) in the security proof of another protocol, I am still in the plain model or using it does not cause undesired shifting of models?

Edit: I found interesting material on RO methodology in the book Introduction to modern cryptography by Katz and Lindell. the rest is from the mentioned book.

  When defining pseudorandom functions, the authors have considered algorithms having oracle access to a random function. But usage of a random function there is very different from the usage of a random function in the RO methodology. In the pseudorandom functions, a random function is used as a way of defining what it means for a concrete keyed function to be pseudorandom. In the random oracle model, the random function is used as part of the construction of the primitive, so must somehow be instantiated in the real world if we want a concrete realization of the primitive.

BTW, the authors have noted that a random oracle is not a one way function because random oracle is not a fixed function, but in order to implement it in a real world, it must first be instantiated and description of it must be fixed. So a hash function is fixed before executing the protocol.

Let us first step back and say more precisely (mathematically) what "the Random Oracle Model (ROM)" is, because it is fundamentally different from an "assumption" as they are thought of in cryptography.

One way to formalize the ROM is to see it as alternative model of computation.  In particular, algorithms in this model of computation have a extra distinguished state (or subroutine, or circuit gate, whatever), that computes some function $H:\{0,1\}^\ast\to\{0,1\}^n$, where n is the security parameter.  An algorithm A is executed in this model by picking $H$ at random from all possible functions, and then running $A$ with its $H$ subroutine set to compute that function.

When we "analyze a protocol in the ROM", we mean first define the protocol via algorithms that have access to $H$, and then we prove a theorem about the protocol when it is attacked by adversaries that also have access to $H$.  The theorem will say that something happens with high probability, where the probability is over the choice of $H$, amongst other things.

This model of computation is not realistic, however, because we do not all have access to a truly random function.  So instead we take our algorithms (which were defined in the ROM) and set $H$ to something efficiently computable, like SHA-256.  Of course, the theorem does not actually cover such usage, but this approach is remarkably effective for avoiding wide classes of attacks against protocols.  We just hope ("assume") that things will work out for the protocols under consideration, but in general this assumption is false[1].

A cryptographic assumption, on the other hand, say something about the limitations of the "standard model of computation", i.e. Turing machines, circuit families, etc.  A distinguishing feature here is that assumptions might true, but the ROM will never "true".  This holds even for interactive assumptions that involve weird oracles - even a random oracle.

Things brings us to the point of confusion:  When you're sitting down to design a protocol (algorithm) and prove it secure in the standard model under an assumption, you can't assume that your algorithm has access to any oracles, because it needs to be an algorithm in the usual sense.  Even if your assumption has a random oracles represented somewhere in it, you still need to give a well-defined algorithm or protocol.

[1] See "The random oracle methodology, revisited" by Ran Canetti, Oded Goldreich and Shai Halevi.

You can tell that a scheme is using the random oracle model if its proof of security is in the random oracle model.

Contrariwise, if it has a proof of security in the plain model, with no random oracles, then it is not using the random oracle model.

This may seem tautological.  If so, that's because it is.  (In other words: if you are unhappy with a tautological answer, it means that your question was not framed clearly or precisely enough.)


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

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

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

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

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

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

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

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

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

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

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

here is a very detailed history & table of modern computers by By Ulf Schünemann that can help resolve some questions of this type. however its a linear record of facts and in general its very difficult to determine the exact "multidimensional" interconnections between inventors (both theoretical & physical oriented/focused), inventions and ideas; its a big historical project that requires even more deep analysis than just looking at known/written history, and can only inherently partially succeed in definitiveness. see also The Relation between Babbage and von Neumann which emphasizes the similarity between Von Neumann architecture and Babbage differential engine.

conceptually there is clearly a tight cluster between the following work but apparently the exact historical interconnection has never been fully deconstructed (nor may it be possible because recorded history is inherently incomplete and some degree of educated guesswork and opinion is inevitable).

strangely while their ideas are all highly interpenetrating mainly on the theme of what is now identified as Von Neumann architecture, there does not seem to be any strong/known historical evidence (such as citations in papers, notes, letters, etc) they were fully or largely aware of each other. one definitely has to resist the assumption/bias that just because one event happened sooner than another, later researchers were aware  of it.

Babbage (~mid 1800s)
Turing (~1930s)
Von Neumann (~1940s)
Zuse (~1940s)

(esp it is known that Zuse worked very independently.) and to be fair, Leibnitz' calculating machine should be mentioned in this list based on his quotations of imagining more general computations possible than those strictly built into his machine.

one could create a historical graph and try to determine if there are any connections between historical points/events and draw edges if there are. such a resource might be as least as illuminating and valuable as the highly regarded Complexity Zoo. Ulf Schünemann's ref seems to be the closest to this in existence but with the caveat its not directly intended for this purpose. again a history of facts is not the same as a map or graph of interconnections.

theoreticians sometimes say certain ideas are "in the air" and there are many famous cases of the nearly-same [sometimes complex] idea appearing in different, largely independent works at nearly the same time. the invention of computers clearly/strongly exhibits this "synchronicity" even stretching over a century if Babbage is fully/fairly considered.

it seems that the "dream" of a computer is old and perhaps very fundamental to the human race and probably inspired by difficult/tedious mechanical calculations combined with the Newtonian mechanistic shift of the Enlightenment, and the metaphor of the "clockwork universe". especially Babbages analytic engine seems like a highly sophisticated/evolved clockwork mechanism.

as other striking examples of theoretical synchronicity from computer science and independent discovery of complex/fundamental ideas, to underline the phenomenon, its now known from a NSA-declassified letter by John Nash (info by Noam Nisan) that he also came up with some of the ideas underlying computational complexity and codebreaking eg one-way/trap-door systems. this letter was written around the same time as the now-famous lost Godel letter also musing on foundations of complexity theory.

another example is Cook-Levin complexity theory of NP completeness. the Levin results were published in Russian and not "discovered" for years later.

essentially, historical awareness seems to increase over time and we now have a very good/detailed picture of the history of computers as far as a timeline, partly because the subject has such massive historical and economic significance during the Moore transistor miniaturization revolution starting in the 1960s (note that much of the secret military work was still classified in the 1950s!).

but that awareness was not as great in prior eras. so to attribute the same detailed historical awareness to earlier workers is misguided, unless possibly one wants to take it as as one of the foremost cases of a phenomenon of Mathematical Platonism.

the closest book to exploring these "threads" Ive found is from Pebbles to Computers, the Thread by Hans Blohm (1987)


Is there a rule-based implementation of weighted abduction other than the PTTP? Is there an implementation of weighted abduction other than the PT theorem prover? A Google search reveals the PTTP and a few statistical approaches but I'm interested in a rule-based approach. The PTTP is too slow with large knowledge bases. Since I couldn't google up anything useful I guess there's none (maybe statistics is the way to go as abduction is intractable) but maybe someone knows of an alternative in a different branch of logic programming (such as ASP).

I'm not aware of any alternatives but some first-order abductive problems can be recast as evaluation of stable models.


What is the best upper bound on the running time of the graph minor algorithm? A cornerstone of the graph minor theory is an algorithm that, given undirected graphs $G, H$, runs in time $f(|H|)poly(|G|)$, and determines whether $H$ is a minor of $G$ or not. It has been obtained from the famous result of Roberson and Seymour.

This result, as well as other algorithms for minor testing, is always cited with $f$ being some implicit computable function. I wonder what are the best known upper bounds on $f$, e.g., is it elementary?

In this discussion, user @Saeed mentions that $f$ is at most quadruple-exponential but provides no reference for this claim.

My answer was based on the explanation in paper of Adler et al for disjoint paths problem. That running time is not exactly what is in the Robertson and Seymour paper but it is the improved one by Kawarabayashi and Wollan. It’s been a long time ago and I am not sure if this is restricted to specific graph class. You may have a look at the corresponding reference.

https://arxiv.org/pdf/1310.2378.pdf


Physics results in TCS? It seems clear that a number of subfields of theoretical computer science have been significantly impacted by results from theoretical physics. Two examples of this are

Quantum computation
Statistical mechanics results used in complexity analysis/heuristic algorithms.

So my question is are there any major areas I am missing?

My motivation is very simple: I'm a theoretical physicist who has come to TCS via quantum information and I am curious as to other areas where the two areas overlap.

This is a relatively soft question, but I don't mean this to be a big-list type question. I'm looking for areas where the overlap is significant.

The search technique simulated annealing is inspired by the physical process of annealing in metallurgy.

Annealing is a heat treatment where the strength and hardness of the substance being treated can change dramatically. Often this involves heating the substance to an extreme temperature and then allowing it to cool slowly.

Simulated annealing avoids local minima/maxima in search spaces by incorporating a degree of randomness (the temperature) in the search process. As the search process proceeds, the temperature gradually cools, which means that the amount of randomness in the search decreases. Apparently it is quite an effective search technique.

to add/fill in some gap in the current excellent answers/coverage—there seems to be a strong connection between TCS and thermodynamics in various ways that hasnt yet been fully explored but is the frontiers of active research. there is a transition point associated with SAT but it seems possibly there are transition points associated with other (or even all) complexity classes as well. the SAT transition point is associated with a difference between "easy" (P) and "hard" (NP) instances, but arguably all complexity class boundaries must lead to the same transition point-like property.

consider a Turing Machine. it already measures its operation in normally physical dimensions of "time" and "space". but note that it apparently also does one unit of "work" in moving from square to square and making a transition. in physics the unit of work is Joules, which is also a measure of energy. so it appears that complexity classes have some relation to energy levels, boundaries, or regimes.

quantum mechanics theory increasingly sees space and time itself, the universe, as a sort of computing system. it appears it has some "minimal computation units" intrinsic to its nature, probably related to the Plank length. so examination of minimal Turing machines for problems also implies and relates to minimal physical/energy systems or even volumes of space required. [3]

also, the key concept of entropy shows up repeatedly in TCS and physics/thermodynamics and may be a unifying principle with still more active research revealing its underlying nature. [1,2]

[1] entropy in information theory, wikipedia

[2] what is the CS defn of entropy, stackoverflow

[3] What is the Volume of Information? tcs.se


are there fixed context sensitive grammars which are PSPACE complete? wikipedia entry  says without reference that

"There are even some context-sensitive grammars whose fixed grammar recognition problem is PSPACE-complete."

This is stronger than saying that CSG is PSPACE-complete.
But is this proved? where are the references?

$\mathrm{CSL}=\mathrm{NSPACE}(O(n))$. Thus, take your favourite PSPACE-complete problem. If it is decidable in $\mathrm{NSPACE}(O(n))$ (for example, QBF is), you are done. Otherwise, introduce a polynomial amount of padding to make it so.

To draw continued attention, here are some explanatory comments, with a tentative proof based on the idea of universal CSG.
The original quote (in my original post) is from wikipedia entry: Context-sensitive grammar, requote here: "There are even some context-sensitive grammars whose fixed grammar recognition problem is PSPACE-complete."

The statement that the word recognition problem for CSG is PSPACE-complete and the statement that the same kind of problem for some fixed grammar in CSG is PSPACE compelte are different! The former is sometimes called universal recognition problem for CSG, and the latter, well, may be called just fixed CSG grammar recognition problem. Let's refer to the two problems as UCSG and FCSG respectively.

The instances of UCSG are pairs of (G,x) where G can be any CSG, and x can be any strings; whereas those of FCSG for a fixed grammar G', are pairs of (G',x) where G' is fixed, and x can be any string.
Thus to say UCSG is PSPACE complete, it means that there is a polynomial time transformation T such that for any decision problem Q in PSPACE, there is pair (G,x)=T(Q) such that the answer to (G,x) is the answer to Q;
Whereas to say FCSG for a fixed CSG G' is PSPACE complete, it means that there is a polynomial time transformation T' such that for any decision problem Q in PSPACE, there is string x, such that (G',x)=T'(Q) is the equivalent problem to Q.

When the original author states that FCSG is PSPACE complete without giving a reference, he (she) may think that it is kind of obvious or its importance does not justify more detail. But I think a reference or certain hints are valuable here, assuming it is right.

Along this line of thinking, my tentative proof plan for FCSG being PSPACE complete is the following:
Let H be such a special grammar in CSG such that H accepts x if and only if x=u#v where u is the coding (by some coding funciton) of arbitrary grammar G(u) in CSG and G(u) accepts v. Since the condition of H is fulfillable by a LBA (or not so?), by the equivalence of LBA and CSG, such H exists; and any ICSG for such a H is PSPACE complete.
Since this H can simulate any other CSG, we may call it universal CSG.

Are there proofs along this line already, where, or this purported proof plan has flaws?
If the idea of universal CSG is essentially right, we may continue asking what other classes have their own universal instances.


Decidability of equality of CFL's Following problem is decidable:

Given a context-free grammar $G$, is $L(G) = \varnothing$?

Following problem is undecidable:

Given a context-free grammar $G$, is $L(G) = A^{\ast}$?

Is there a characterization of context-free languages $M$ with decidable equality $L(G) = M$?

I am not sure there is any general characterization for equivalence, but the following papers by Hopcroft, and Hunt and Rosenkrantz resp. might be a good start:

John E. Hopcroft, On the equivalence and containment problems for context-free languages, Theory of Computing Systems 3(2):119-124,  doi:10.1007/BF01746517;
Harry B. Hunt, III and Daniel J. Rosenkrantz, On Equivalence and Containment Problems for Formal Languages, Journal of the ACM 24(3):387--396, 1977, doi:10.1145/322017.322020.

Hopcroft shows in particular that, if $M$ is regular, then $L(G)=M$ is decidable iff $M$ is bounded, i.e. there exist $n$ words $w_1,w_2,\ldots,w_n$ s.t. $M\subseteq w_1^\ast w_2^\ast\cdots w_n^\ast$.

Sorry to bring up an old thread.  But here's something that might be relevant.

Let pCFL be the class of permutation-closed CFLs.  The equality problem for pCFL is decidable.

Given $L$ in $\Sigma = \{ \sigma_1 , \dots , \sigma_n \}$, let $W_L = \{ \langle \#_{a_1}(w) , \dots , \#_{a_n}(w) \rangle \mid w \in L\}$. By Parikh's Theorem, $W_L$ is semilinear whenever $L$ is context-free.

Now, if $L$ is in pCFL, we have that $w \in L$ iff $\langle \#_{a_1}(w) , \dots , \#_{a_n}(w) \rangle \in W_L$.  Thus, for $L_1 , L_2$ in pCFL, $L_1 = L_2$ iff $W_{L_1} = W_{L_2}$. But equality of semilinear sets is decidable; see:

Huynh 1980 "The complexity of semilinear sets": http://link.springer.com/chapter/10.1007%2F3-540-10003-2_81#

This raises a question to which I would like to know the answer: is it decidable whether a given context-free language is permutation-closed?


Why is "topological sorting" topological? Why is "topological sorting" called "topological"? Is it just because it determines an order without altering any vertices or edges -- like a doughnut and coffee cup are topologically equivalent? Why is it not called "dependency sort" or something else? Why "topological"? I admit I'm mystified.

The earliest reference I could find for topological sort is from [Lasser61]:

  A network of directed line segments free of circular elements is assumed. The lines are identified by their terminal nodes and the nodes are assumed to be numbered by a non-topological system. Given a list of these lines in numeric order, a simple technique can be used to create at high speed a list in topological order.

I don't have access to this article right now but I would wager that the "topology" in "topological sort" does not come from the mathematical notion of topology (e.g.: open sets, compactness, etc...) but rather from the "network topology" sense.

[Lasser61] Lasser, Daniel J. "Topological ordering of a list of randomly-numbered elements of a network." Communications of the ACM 4, no. 4 (1961): 167-168.

The topology of a set of items is how they are connected. Topological sorting is sorting items based only on their topology.


Split or merge Binary Search Trees in O(log n) We need to have an efficient operation of merging or splitting two binary search trees $S_1$ and $S_2$. There are given the following.

The element with the largest value in $S_1$ is smaller than the element with the smallest value in $S_2$. Abusing the notation $S_1 < S_2$.

We define as merge operation the operation which requires the two trees $S_1$ and $S_2$ and produces a valid binary search tree $S$ containing all of their elements.

Similarly, $S$ is split in two binary search trees $S_1$ and $S_2$ given an element $k$ for which (abusing the terminology again) $S_1 \le k < S_2$.

The best solution I have come up with in order to convince myself that this is possible, is by using splay trees. To merge we put the smallest element of $S_2$ as the root of the new tree with $S_1$ as the left subtree and $S_2$ as the right subtree (alternative we use the largest element of $S_1$ if it smaller). Amortized time $O(\log n)$. Similarly, we split by searching for the element $k$... Amortized time $O(\log n)$ again.

Is there anything better?

(Sorry for the lack of imagination in my question, this is my first post here.)

Treaps support both operations in $O( \log n)$ time with high probability. The trick is to give the splitting element $0$ priority making it the root, splitting the trees, and then reverting its priority to the original value. Merging is done similarly.

I am not expert here . Any way I give a try here

For merge operation
,Find the largest element in $S1$ say $w$ (log(n)), we know that it does not contain right child as it is the largest element. we know that every element in $S2$ is greater than $w2$. surely $root(S1)$ will be >= $w$ so make $right(w)->root(S1)$ which is order of O(1)

For Spit operation
Search the element $k$ in $S$ (logn) we know that. we reach at the node say $y$ we know that all elements in $right(y)$ will give greater than $k$ .$right(y)$ be the new $S2$ tree and $S$ without $right(y)$ will be $S1$

i do not think merge function or split can be done in constant time.

Sorry if it is wrong


Reducing redundant edges from a dependency graph I have a DAG of dependencies that contains lots of redundant edges (see example below). I want a "quick" algorithm (ie. can handle a graph with several thousands of nodes/edges) that finds a minimal sub graph.

For example:

A -> B -> C
A -> C

in words A is prerequisite to B, and B is prerequisite to C, and also A is prerequisite to C. In this case A -> C is redundant (since B is already necessary to reach C, and A is necessary to reach B).

Its been a while since I studied algorithms, and I'm not sure where to start.

By the way, its not critical that the algorithm finds the global minimum, local minimum is fine (the edge reduction is only a runtime optimization for next stage of processing).

Also, I realize this is a CS QA and not programming, but my program is written in Python, so I would be extra happy to learn of a python module or open source for doing this reduction, just in case you know of it.

thanks in advance!

The Transitive Reduction of a Directed Graph
A. V. Aho, M. R. Garey, and J. D. Ullman

According to wikipedia, this algorithm is used by tred which is tool for transitive reduction available in GraphViz package. You can run it on your graph and get reduced graph.

This question is duplicate of this stackoverflow question.

code here graphviz/tools/src/tred.c does use DFS. ;-)

I ended up solving it this way:

My data structure is made of dependends dictionary, from a node id to a list of nodes that depend on it (ie. its followers in the DAG).

I haven't calculated the exact complexity of it, but it swallowed my graph of several thousands in a split second.

_transitive_closure_cache = {}
def transitive_closure(self, node_id):
    """returns a set of all the nodes (ids) reachable from given node(_id)"""
    global _transitive_closure_cache
    if node_id in _transitive_closure_cache:
        return _transitive_closure_cache[node_id]
    c = set(d.id for d in dependents[node_id])
    for d in dependents[node_id]:
        c.update(transitive_closure(d.id))  # for the non-pythonists - update is update self to Union result
    _transitive_closure_cache[node_id] = c
    return c

def can_reduce(self, source_id, dest_id):
    """returns True if the edge (source_id, dest_id) is redundant (can reach from source_id to dest_id without it)"""
    for d in dependents[source_id]:
        if d.id == dest_id:
            continue
        if dest_id in transitive_closure(d.id):
            return True # the dest node can be reached in a less direct path, then this link is redundant
    return False

# Reduce redundant edges:
for node in nodes:
    dependents[node.id] = [d for d in dependents[node.id] if not can_reduce(node.id, d.id)]


Completeness of the extension of first order logic with least fixed point order operator Is there any result about the extension of first order logic with least fixed point operator, being complete (as logic in general on infinite structures too) or not? In other words does the Goedel completeness theorem of first order logic extent to such FO-LFP logic ?

FO-LFP is neither complete (its valid sentences cannot be described by a recursively presented proof system) nor compact (there is an unsatisfiable set of sentences all of whose finite subsets are satisfiable). The basic argument is given in Denis’s answer so I won’t repeat it here, but let me instead point out that as a general principle due to Per Lindström, when extending first-order logic, some important property has to give way.

The setup is that we consider logics given by a satisfaction predicate $M\models\phi$ between ordinary first-order models, and an abstract set of sentences, that satisfy a handful of natural technical conditions.

The first Lindström’s theorem states that no proper extension of FO can simultaneously satisfy

(Löwenheim–Skolem) If a sentence has a model, it has an at most countable model.
(Compacteness) If $T$ is a set of sentences such that every finite subset of $T$ has a model, then $T$ has a model.

The second Lindström’s theorem states that no proper extension of FO with effectively presented syntax can satisfy

The Löwenheim–Skolem property as above.
(Completeness) The set of valid sentences can be described by an effectively axiomatized proof system (i.e., it is recursively enumerable).

For example, FO+TC has the Löwenheim–Skolem property (as it is a fragment of $L_{\omega_1,\omega}$), hence it can be neither complete nor compact, and a fortiori the same applies to all extensions of FO+TC such as fixed-point logics. (This is of course easy to show directly.)

I found a paper here that somehow gives a kind of completeness of the existential part of FO-LFP. This still captures polynomial time complexity in the sense of complete recursive enumerable set of valid statements existential FO-LFP, which of course is not the Gödel completeness of FO.


Gap between $BB(n)$ and "second largest" $BB(n)$ If $HT(n)$ is the set of halting times of $n$-state Turing machines on a binary alphabet with empty initial tape, then $BB(n) = \max HT(n)$.

What can we say about the second largest number in $HT(n)$?  Call this $BB_2(n)$.

$BB_2(n)$ is trivially uncomputable, since it lets one compute $BB(n)$: just wait for one more machine to halt.  Naively, I would expect the gap $BB(n) - BB_2(n)$ to be "busy beaver-like", growing faster than any computable function.  Is this provable?

The number of states is just a notion of complexity of the description of computable functions in a model, you can pick any model of computation and any encoding of them as binary strings and then take the length as n and define BB(n) based on that and all the interesting results about BB(n) would still be true, there is boring special about TM model and number of states.
There is nothing that prevents them from picking any modified model of TMs. Generally the questions which are not invariant under such changes of representation of TMs are not about computability or TMs but about the particular representation (like BB(n) mod 2, etc. ) and unless there is some particular reason for them being interesting they don't worth pursuing imho. They are nice puzzles but not of much value.
l
Note that "BB(n) is not computable" is invariant under change of representations of TMs.
So is this question invariant under change of representation of computable functions? The answer I think is no.

i. Consider a representation where we have two special states 0 and 1 and either 0 is initial and just can transition to 1 or 0 is unreachable and 1 is initial. In this encoding the difference is 1.

ii. Consider another representation where we have a UTM plus a part that writes n bits on tape before transitioning to UTM. So the question becomes max f(x) - 2ndmax f(x) where maxes are over n bits strings and where f is an arbitrary computable function. We only need to find a computable function where this is not computable. I haven't thought about it much but my gut says there is such a computable function.


Computation of reals: floating point vs TTE vs domain theory vs etc Currently, computation of reals in most popular languages is still done via floating point operations. On the other hand, theories like type two effectivity (TTE) and domain theory have long promised exact computation of reals. Clearly, the problem of floating point precision has not dwindled in relevance, so why haven't these theories become more mainstream and why aren't there more conspicuous implementations of them?

For example, are there domains of applications where we don't care much about floating point errors? Are there significant complexity concerns?

I work in real-number computation, and I wish I knew the real answer. But I can speculate. It's a sociological problem, I think.

The community of people who work on exact real arithmetic consists of theoreticians who are not used to developing software. So they usually relegate the task of implementation to students (a notable exception is Norbert Müller's iRRAM), or they have their own toy implementations.

People who do have the necessary programming mojo do not have the necessary theoretical background. Without solid theoretical footing it is difficult to design exact real arithmetic correctly. For instance, it is a mistake to add lots of real numbers in a for loop, as you will get unacceptable performace due to loss of precision. If you want to add lots and lots of reals, you should do it with a tree-like structure, taking into account the magnitudes of the partial sums. Another thing which is difficult to get across is that < and = as total boolean function on the reals simply do not exist (you can have = but it either returns false or it diverges, and < diverges when given two equal reals).

Lastly, it is not clear at all that we know how to implement libraries for exact real arithmetic. They're not the usual pieces of libraries which just define some datatypes and some functions on them. Often exact real arithmetic requires special modes of control. For instance, iRRAM takes over the main execution of the program (it literally hijacks main), as well as standard input and output, so that it can rerun the program when loss of precision occurs. My library for real arithmetic in Haskell happens in a Staged monad (which is essentially the Reader monad). Most people expect the real numbers to be "just another datatype", but I have my doubts about that.

I am hardly an expert, but I have been honing my chops on this over the last few years. The problem is that the "real" numbers simply do not exist in the same way that natrual numbers do. Is there anyone who has an intuitive grasp of "$\pi$-ness"? Essentially the real numbers are defined by various limit processes; many of these limit processes have been given special names, and some of them are special enough that they form significant subsets of the reals (e.g. algebraic numbers)

My point being that if you are going to compute exactly, you have to have placeholders for the special names as well as the familiar names the naturals. At some point you are going to want to approximate the exact value in order to apply it to something in the real world. As it turns out, it is much more efficient to just deal with the whole problem as approximations from the start, unless you have very specialized needs.

Of course, very few working programmers think this way. They mostly say to themselves "Gee, double has more precision than I could possibly ever, might as well use it", and mostly that is the most economical approach. The problem is that most programmers don't know how to spot when they are getting into trouble because the set of double-precision floats is infinitely smaller than $R$...


Computing the Levenshtein distance quickly Given a huge database of allowed words (alphabetically sorted) and a word, find the word from the database that is closest to the given word in terms of Levenshtein distance.

The naive approach is, of course, to simply compute the levenshtein distance between the given word and all the words in the dictionary (we can do a binary search in the database before actually computing the distances).

I wonder if there is a more efficient solution to this problem. Maybe some heuristic that lets us reduce the number of words to search, or optimizations to the levenshtein distance algorithm.

Links to papers on the subject welcome.

What you are asking about is the problem of near-neighbor search under the edit distance. You didn't mention whether you're interested in theoretical results or heuristics, so I'll answer the former.

The edit distance is somewhat nasty to deal with for building near-neighbor search structures. The main problem is that as a metric, it behaves (sort of) like other well known bad metrics like $\ell_1$ for the purpose of dimensionality reduction and approximation. There's a rather vast body of work to read on this topic, and your best source is the set of papers by Alex Andoni: by following pointers backward (for example from his FOCS 2010 paper) you'll get a good set of sources.

One way is to train a machine learning model to map the words to vectors and map the levenshtein distance to the euclidean distance. Then you can build a KDTree out of the vectors for the dictionary you want to use. I created a jupyter notebook that does this here: https://gist.github.com/MichaelSnowden/9b8b1e662c98c514d571f4d5c20c3a03

As per D.W.'s comments:

training procedure = stochastic gradient descent with adaptive gradients
loss function = mean squared error between true edit distance and euclidean distance
training data = random strings between 1 and 32 characters long (could be improved with data that matches an actual distribution of common typos)
quantitative results: After training for roughly 150 epochs with a batch size of 2048 (wall time = approximately one minute), using word embeddings of 512 dimensions, with one hidden layer, the average absolute error between the true edit distance and the predicted edit distance sits at around 0.75, meaning the predicted edit distance is roughly one character off

Summary of the model structure:

Create a learned embedding for each character, including the null character (used later to right-pad text under the character limit)
Pad the right side of the text with the null character until it is at the character limit (32)
Concatenate these embeddings
Run the embeddings through a feed-forward neural net to produce a lower-dimensional word embedding (512-dimensional)
Do this for both words
Find the euclidean distance between the vectors
Set the loss to be the mean squared error between the true Levenshtein distance and the euclidean distance

My training data is just random strings, but I think the results could really improve if the training data was (typo/correct word) pairs. I ended up just using /usr/share/dict/words because it's commonly available.


An easy case of SAT that is not easy for tree resolution Is there a natural class $C$ of CNF formulas - preferably one that has previously been studied in the literature - with the following properties:

$C$ is an easy case of SAT, like e.g. Horn or 2-CNF, i.e., membership in $C$ can be tested in polynomial time, and formulas $F\in C$ can be tested for satisfiability in polynomial time.
Unsatisfiable formulas $F\in C$ are not known to have short (polynomial size) tree-like resolution refutations. Even better would be: there are unsatisfiable formulas in $C$ for which a super-polynomial lower bound for tree-like resolution is known.
On the other hand, unsatisfiable formulas in $C$ are known to have short proofs in some stronger proof system, e.g. in dag-like resolution or some even stronger system.

$C$ should not be too sparse, i.e., contain many formulas with $n$ variables, for every (or at least for most values of) $n\in \mathbb{N}$. It should also be non-trivial, in the sense of containing satisfiable as well as unsatisfiable formulas.

The following approach to solving an arbitrary CNF formula $F$ should be meaningful: find a partial assignment $\alpha$ s.t. the residual formula $F\alpha$ is in $C$, and then apply the polynomial time algorithm for formulas in $C$ to $F\alpha$. Therefore I would like other answers besides the all-different constraints from the currently accepted answer, as I think it is rare that an arbitrary formula will become an all-different constraint after applying a restriction.

It sounds like you are interested in all-different constraints (and your last sentence is on the right track).  These are non-trivial instances of the pigeonhole principle, where the number of pigeons is not necessarily greater than the number of holes, and in addition some pigeons may be barred from some of the holes.

All-different constraints can be decided by matching in low-order polynomial time.

Jean-Charles Régin, A filtering algorithm for constraints of difference in CSPs, AAAI 1994, 362–367.
D. E. Knuth and A. Raghunathan, The problem of compatible representatives, SIAM J. Discrete Math. 5 422–427, 1992.  doi:10.1137/0405033

When all-different constraints are expressed (using one of several encodings) as SAT instances, then conflict-driven clause learning usually quickly finds a solution if it exists.  However, pure resolution for the PHP has to build a superpolynomially large set of clauses to show that the instance is unsatisfiable.  This bound clearly holds for this more general problem.  On the other hand, recall that Cook's encoding of the PHP allows polynomial-sized extended resolution refutations.

S. A. Cook, A short proof of the pigeon hole principle using extended resolution, SIGACT News 8 28–32, 1976.  doi:10.1145/1008335.1008338

Recent work along these lines is Chapter 5 of Sergi Oliva's thesis, which formed the basis of a paper with Alberto Atserias at CCC 2013.

I expect you are aware of Cook's classic result, so perhaps you meant to restrict the power of the proof system in your third condition?

this following paper seems close to what is requested in some ways (if it does not fit maybe JJ can clarify why). the question wants to rule out PHP (pigeonhole) instances based on the lack of both true/false formulas, but (as cited in the other answers) PHP is one of the most well-studied cases/instance generators from the theory side and has always been a generator for both satisfiable/unsatisfiable formulas although the satisfiable formulas are less emphasized/studied.

PHP${^m_n}$ where there are $m$ "pigeons" and $n$ "holes" is unsatisfiable (false) if $m>n$ and satisfiable if $m \leq n$. am not immediately familiar with papers that study both cases but think they exist (would like to hear of any). and some results/analyses that study only the unsatisfiable cases are naturally extended to include the satisfiable case.

Tree-Like Resolution Is Superpolynomially Slower Than DAG-Like Resolution for the Pigeonhole Principle (1999) by Kazuo Iwama , Shuichi Miyazaki

another approach would be to go in a more empirical angle and just generate random instances (presumably around the easy-hard-easy 50% satisfiable transition point) and filter them to fit the criteria stated. one would require implementations of tree resolution/DAG resolution or "stronger systems".


Why is label pruning possible with hub labeling? Hub labeling (HL) computes superlabels using the vertices visited by the forward and reverse Contraction Hierarchies (CH) search. Those labels are then pruned (see HL, sec. 4.2) to generate strict labels.

I don't understand how there can be labels that can be pruned. From my understanding the shortcuts added by CH should make sure that in both forward and reverse searches we will either

reach a node via a shortest path or
not reach a node at all.

How is it possible that we reach some nodes via a path that is longer than the shortest path? Could anyone provide a minimal example?

I have emailed the authors and they kindly supplied me with the following example:

Let the nodes be contracted in alphabetical order then the red edge will be added during contraction.

Now look at the upward search from A (i.e. we can only visit nodes that have been contracted later). A will settle B with distance 1 and D with distance 2. Since we are not allowed to visit C via D (as this is not upward) we must settle C via B with distance 6. However, as can clearly be seen from the non-contracted graph, the A-C distance is 5 (via D).

This means that we now have an incorrect distance label for C at A.

so that means:

1)
creating the forward label of A consists of yopying the upwards graph from A

2)
prune out all vertices from forward Label L(A) where d(s, u) > dist(s, u)
(d() = current distance; dist() = real distance; s = start-vertex; u = another vertex)

2.1)
do a BI-Dijsktra search from s to u and compare the calculated distance = dist(s, u) with the current distance from A's label = d(s, u)
if its greater, than prune C from A's Label L(A)

will this not lead to a many to many query like doing a dijsktra from almost every node to every other node?
Couldnt I then just save all results into an origin-destination matrix?
Is then the whole benefit of hub labeling just a space-better way than creating an OD-matrix?

Unfortunately I was not able to find a description how they do the hub labeling. They say they use the labes from CH searches. Which searches they mean? Do the really do a many to many search and then save the labes as forward and reverse?


What is the minimum number of bits required to store a sudoku puzzle? Note: This is about the standard 9x9 sudoku puzzle. The solution only has to support solved, legal puzzles. So a solution doesn't need to support empty cells and can rely on the properties of a solved sudoku puzzle.

I was wondering this, but I couldn't think of an answer that I was content with. A naive solution would use one byte for each cell (81 cells), totalling 648 bits. A more sophisticated solution would store the entire sudoku puzzle in a base-9 number (one digit per cell) and require $\lceil\log_2(9^{81}))\rceil = 257$ bits.

But it can still be improved, for example, if you know 8 of the 9 numbers in a 3x3 subgrid you can trivially deduce the 9th. You can continue these thoughts to the point where this question boils down to What is the amount of unique solved sudokus? Now you can use a huge lookup table that maps each binary number to a sudoku puzzle, but that wouldn't be an usable solution.

So, my question:

Without using a lookup table, what is the minimum amount of bits required to store a sudoku puzzle and with what algorithm?

Along the same lines as ratchet freak's answer, if you fill in the non-starred cells in the following matrix, a 3x3 box at a time, always choosing the next box to fill in to be one that shares rows or columns with a box you've already filled in, you get a pattern like the following for the number of choices per step (filling in the top middle box first, the top right box next, etc).

In each 3x3 box after the first, once you've filled in one row or column of the box, three of the remaining six digits are localized to a single row. Choose their locations first, and then fill in the remaining three cells. (So the actual order of which cells to fill in might vary depending on what you already know, but the number of choices is never more than what I've shown.)

After you've filled in these cells the stars are all determined.

* * *    9 8 7    6 5 4
* * *    6 5 4    3 3 2
* * *    3 2 1    3 2 1

6 5 4    * * *    6 3 3
3 3 2    * * *    5 3 2
3 2 1    * * *    4 2 1

6 3 3    6 5 4    * * *
5 3 2    3 3 2    * * *
4 2 1    3 2 1    * * *

If I've calculated correctly, this gives 87 bits. There's some additional savings to be had in the last 3x3 block, per the comment by Peter Shor: every value is localized to one of four cells, and every row contains at least one cell with only four possible values, so certainly the factors in that block should start with 4 not 6, but I don't understand the remaining factors in Shor's answer.

That number is different for each Sudoku. One of the rules for Sudoku is that it has exactly one solution.

So if you look at an example, that's the minimum amount of data that you must store.

If you work from the opposite side, you can remove digit by digit and run a solver on the result to see if it still has exactly one solution. If so, you can delete another digit. If not, you must restore this digit and try another. If you can't, you have found a minimum.

Since most puzzles start mostly empty, a run length encoding will probably yield good results.


Are research papers hard to read? This question may not suit to here, but I couldn't find a better place to ask (it was closed in SO).

I find research papers on computer science hard to understand. Of course the subjects are complicated. But after I understand a paper usually I can tell it to someone in simpler terms, and make them understand. If somebody else tells me what is done in that research I understand too.

I think the best example that I can tell here is: I have tried to understand SIFT paper for a long time, and I found a tutorial while googling, in a couple of hours I was ready to implement the algorithm. If I was to understand the algorithm from the paper itself it might have taken a couple of days I think.

My question is: is it only me who finds research papers this hard to understand? If not how do you deal with it? What are your techniques? Can you give tips?

Unfortunately, research conferences generally do not place a premium on writing for readability. In fact, sometimes it seems the opposite is true: papers that explain their results carefully and readably, in a way that makes them easy to understand, are downgraded in the conference reviewing process because they are "too easy" while papers that could be simplified but haven't been are thought to be deep and rated highly because of it. So, if you rephrase your question to add another word, is it not just you who finds some research papers unnecessarily hard to read, then no, it is not. If you can find a survey paper on the same subject, that may be better, both because the point of a survey is to be readable and because the process of re-developing ideas while writing a survey often leads to simplifications.

As for strategies to read papers that you find hard, one of them that I sometimes use is the following: read the introduction to find out what problem they're trying to solve and some of the basic ideas of the solution, then stop reading and think about how you might try to use those ideas to solve the problem, and then go back and compare what you thought they might be doing to what they're actually doing. That way it may become clearer which parts of the paper are just technical but not difficult detail, and which other parts contain the key ideas needed to get through the difficult parts.

Another reason why papers are often hard to read is because the authors have usually just figured out the result and don't have much hindsight or time to digest what they did.

When you write a paper, you are usually presenting a new idea that you have just developed. Usually, you spend some effort simplifying the idea to make it easier to write up, but in most cases you cannot go all the way, as you are still immersed in the idea and can't get a fresh perspective of how to reduce it down to its essence. For this reason, often the paper presents the idea in a form that could be simplified further.

So as an outside reader of the paper, if you can understand what the paper is doing, then as you said you will often be able to rephrase it in a much more synthetic way, just because you are not the original authors and have a new perspective on the problem.

This is one reason why the original papers presenting an idea can be a very difficult read compared to more recent presentations of the same idea (in textbooks, in course notes, or in follow-up papers of the area).


Match a string agains a set of regexes There are several algorithms to match a (simple) string against a regular expression (see here).
But if we have a lot of regexes, can we find one of them that matches the given string faster than checking the string with all of the regexes, one by one?
For example, if we have $k$ regexes, each with a length of $m$ and a string of length $n$, using the $O(mn)$ algorithm to match a string with a regex $k$ times gives us a running time of $O(kmn)$. Can we do better than this?
If you have an answer which requires some assumptions, please explicitly tell them.

Hyperscan is a high-performance multiple regex matching library that uses hybrid automata techniques to allow simultaneous matching of large numbers of regular expressions across streams of data. They explained their approach here:
https://www.hyperscan.io/2015/10/20/match-regular-expressions
Apparently, they didn't find a fast algorithm (in the worst case) for this problem: "We have not found a single, elegant automata approach that handles arbitrary regular expressions in arbitrary number". However, they used a lot of optimization which works well enough in practice.
I also believe that in the worst case, the given regular expressions can be so complex that no better solution exists.

The best strategy would be to simultaneously check the string against all DFA's. This is achieved by adding a new start vertex v0 and adding epsilon edges to the start vertices of all DFA's. Now you have an NFA. You can follow standard algorithms of determinizing it. This is exactly how automated lexer generators (like flex for example) work. Only instead of the input DFA's they have multiple regular expressions.


Graph encoding algorithms that you know of ? Is there any compilation of graph encoding algorithms? I know about Prufer and Huffman encoding. But papers say, prufer is not good enough to represent Minimum Spanning Trees in the sense it may represent different MSTs with the same string.

Update: It would be a very good future reference if every one could mention the graph encoding algorithm they know of. You can also provide a link/url to a paper.

As a start:

Prufer Encoding
Huffman Encoding
Succinct Trees
Ultra-succinct Representation of Ordered Trees

Thanks

If you have a binary encoding of the vertices of the graph you can represent the edges with the characteristic boolean function $\chi_E$ of the edge set $E$, i.e. $\chi_E(x,y) = 1 \Leftrightarrow$ there is an edge between the vertices encoded by $x$ and $y$.
This boolean function can be represented by e.g. Ordered Binary Decision Diagrams.

It is known that this OBDD representation is not larger than classical representations (adjacency matrix or adjacency lists) and for special graph classes (e.g. cographs and interval graphs) the OBDD size is smaller then the explicit representation (Nunkesser,Woelfel: Representation of Graphs by OBDDs). So you can hope that for good structured graphs the implicit representation is better.

In the case of trees I have shown (with the tools from the above paper) that the OBDD size is generally not better than the explicit representation and you can easily construct a tree so that the OBDD size is large.

Algorithms are called symbolic or implicit if they have access to the input graph only by this functional representation and perform functional operations to solve the problem. There is a good PhD thesis from Sawitzki about this topic but it is in german (PDF).

I think this is a kind of heuristical approach because you can't guarantee that there is a good implicit representation of the graph and so a fast symbolic alghorithm. Even if there exist a good implicit representation it is very hard to find this good one.

If your looking for MST encoding go for S&T Encoding


Golden ratio or Pi in the running time There are many places where the numbers $\pi$ and $(1+\sqrt5)/2$ show up. I'm curious to know about algorithms whose running time contains the golden ratio or $\pi$ in the exponent.

It's the base rather than the exponent, but there's an $O(\varphi^k n^2)$ FPT time bound in

"An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization", Vida Dujmovic, Sue Whitesides, Algorithmica 40:15–31, 2004.

Also, it's a lower bound rather than an upper bound, but:

"An $n^{1.618}$ lower bound on the time to simulate one queue or two pushdown stores by one tape", Paul M.B. Vitányi, Inf. Proc. Lett. 21:147–152, 1985.

Finally, the one I was trying to find when I ran across those other two: the ham sandwich tree, a now-obsolete data structure in computational geometry for triangular range queries, has query time $O(n^{\log_2\varphi})\approx O(n^{0.695})$. So the golden ratio is properly in the exponent, but with a log rather than as itself. The data structure is a hierarchical partition of the plane into convex cells, with the overall structure of a binary tree, where each cell and its sibling in the tree are partitioned with a ham sandwich cut. The query time is determined by the recurrence $Q(n)=Q(\frac{n}{2})+Q(\frac{n}{4})+O(\log n)$, which has the above solution. It's described (with a more boring name) by

"Halfplanar range search in linear space and $O(n^{0.695})$ query time", Herbert Edelsbrunner, Emo Welzl, Inf. Proc. Lett. 23:289–293, 1986.

to expand on Martin Bergers comment: the ancient Euclidean GCD algorithm runs in worst case time on two successive elements from the Fibonacci sequence. more details on wikipedia which also states:

  This proof, published by Gabriel Lamé in 1844, represents the beginning of computational complexity theory,[93] and also the first practical application of the Fibonacci numbers.[91]

technically the GCD algorithm runs in logarithmic time $O(\log(n))$ but the golden ratio shows up in the number of steps of the algorithm.

[1] what is the time complexity of Euclids algorithm, math.se


On definition of IP class I'm a little bit lost with the actual definition of IP, some sources define as interaction between algorithms starting with Verifier, another one does not any put restriction on who send the first message. This simple question turn things messy ahead, when take into account  the number of messages on definition of IP(k). Does matter who start the interaction?

In the definition of class IP(k), the interaction always ends with prover’s message.  Otherwise there is no use for the last message (why?).

The situation is different for the definitions of public-coin interactive proof systems (also known as Arthur-Merlin proof systems), where sending a message from the verifier to the prover is the only way for the verifier to generate a random bit string.  In Babai [Bab85], AM(k) is defined by the verifier (or Arthur) sending the first message and MA(k) is defined by the prover (or Merlin) sending the first message.

[Bab85] László Babai.  Trading group theory for randomness.  In Proceedings of the 17th Annual ACM Symposium on Theory of Computing (STOC), pp. 421–429, May 1985.  DOI: 10.1145/22145.22192.

In fact does not matter (the classes of recognized languages are the same) as can be seen here:Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes, László Babai


An algorithm for calculating the probability of a disease spreading through a graph The following problem came up in my undergrad research project: You have some undirected graph. Some nodes are "sick" and some are not. The probability that a neighbour of a sick node becomes sick is (1 - q_i), where q is a number specific to the node under attack, ranging from 0 to 1. If a node succesfully resists an attack from a sick neighbor, it becomes immune and cannot get sick from any other node. What is the probability that any given node will become sick, given a graph A, some initial sick nodes, and a vector of q's characterizing the nodes?

I feel like this problem has been solved, but I'm having trouble finding sources. Any help or references to papers/books will be greatly appreciated.

Immunity seems to make your problem easier in one sense, as it means that infection can be modelled by a process that terminates after a linear number of infection attempts.  The stipulation that the probability of infection does not depend on the neighbours of a vertex also helps.  However, the model does not seem easy to analyse: the immune vertices in effect are removed from the graph, so a vertex may effectively become unreachable.
The infection, immune, and unreachable probabilities depend on the intermediate graphs created by the infection process.

It might be useful to start with cliques, paths, and cycles with a single initially infected vertex.  Cliques are trivial.  For a path with one infected endpoint the probability that the other endpoint becomes infected at some stage is the product of the probabilities of infection of all the intermediate vertices.  For a cycle, the probability depends on both paths; the longer path becomes relevant if an immune vertex appears on the shorter path.  Trees also have a single path between any two vertices, so can be handled as for the path case.

It might then be feasible to extend the analysis to $k$-connected graphs and regular grids, though this already seems quite tricky.

I am not familiar with literature that deals with this specific problem.  Here are some general comments and pointers.

Some relevant keywords are "contagion" (in the context of network models) and "percolation" (in statistical mechanics).  These models tend to focus on the behaviour of randomized processes that behave like the one you suggest.  However, different models focus on different parameters of interest, so you might have to examine several to find one that best matches the specific one you are interested in.

As an example, a lot of post-2008 work has applied contagion models to financial systems, since it has been argued that these models explain well the gridlock experienced at that time by the global financial system.

The Ising model is one of the simplest and earliest models that involve interacting parties in a graph, and has an extensive literature.

From a purely TCS perspective, computing the partition function of spin systems like the Ising model is equivalent to counting the solutions of a constraint satisfaction problem.  The mixing time is also often of interest.

Andrei Bulatov and Martin Grohe, The complexity of partition functions, TCS 348, 2005, 148–186.  doi:10.1016/j.tcs.2005.09.011 (preprint)
Martin Dyer, Leslie Ann Goldberg and Mark Jerrum, Matrix norms and rapid mixing for spin systems, Annals of Applied Probability, 19, 2009, 71–107.
doi:10.1214/08-AAP532

your question indicates you're just starting out on this topic. there is some highly specialized research at this point on this subject of mathematical and computer models for virus spreading. virus spreading behavior has seen to have widespread similarities in different/diverse milieus eg computer viruses, human viruses, animal viruses. havent seen a good scientific survey paper. however here are two refs written by leading computer scientist experts/specialists/discoverers in natural/physical applications of graph theory. full disclosure, they are popular science type books, but they should be sufficient for your query to find further research leads.

Linked: the new science of networks, Barabasi. Ch 10 Viruses and Fads.
Six Degrees: The Science of a Connected Age, Watts. Chapter 6, Epidemics and failures


Major unsolved problems in theoretical computer science? Wikipedia only lists two problems under "unsolved problems in computer science":

P = NP?
The existence of one-way functions

What are other major problems that should be added to this list?

Rules:

Only one problem per answer
Provide a brief description and any relevant links

Can multiplication of $n$ by $n$ matrices be done in $O(n^2)$ operations?

The exponent of the best known upper bound even has a special symbol, $\omega$. Currently $\omega$ is approximately 2.376, by the Coppersmith-Winograd algorithm.  A nice overview of the state of the art is Sara Robinson, Toward an Optimal Algorithm for Matrix Multiplication, SIAM News, 38(9), 2005.

Update: Andrew Stothers (in his 2010 thesis) showed that $\omega < 2.3737$, which was improved by Virginia Vassilevska Williams (in a July 2014 preprint) to $\omega < 2.372873$.  These bounds were both obtained by a careful analysis of the basic Coppersmith-Winograd technique.

Further Update (Jan 30, 2014): François Le Gall has proved that $\omega < 2.3728639$ in a paper published in ISSAC 2014 (arXiv preprint).

Can inductive-recursive types be constructed in univalent models of type theory?

Recently, Hugunin (2019) showed that inductive-inductive types are compatible with univalent models of type theory, and demonstrated how to construct them in cubical type theory. The case for inductive-recursive types, by far, is still unclear.

Some more open problems in type theory here.


Is 0-1 programming with constant number of constraints polynomially solvable? It was shown in the paper "Integer Programming with a Fixed Number of Variables" that integer programmings with constant number of constraints (or variables) are polynomially solvable.

Does this hold for 0-1 programming?

I'm assuming that by "0-1 programming with a constant number of constraints" you mean the following problem:

Maximize some linear function of (x_1, x_2, ..., x_n) subject to the constraints that each x_i is in {0,1} and a constant number of additional linear constraints.

This problem is NP-complete even with 1 additional constraint since 0-1 knapsack can be written in this form.

0-1 integer programming or binary integer programming (BIP) is the special case of integer programming where variables are required to be 0 or 1 (rather than arbitrary integers). This problem is also classified as NP-hard, and in fact the decision version is NP-Complete.


What is the complexity class most closely associated with what the human mind can accomplish quickly? This question is something I've wondered about for a while.

When people describe the P vs. NP problem, they often compare the class NP to creativity.  They note that composing a Mozart-quality symphony (analogous to an NP task) seems much harder than verifying that an already-composed symphony is Mozart-quality (which is analogous to a P task).

But is NP really the "creativity class?"  Aren't there plenty of other candidates?  There's an old saying:  "A poem is never finished, only abandoned."  I'm no poet, but to me, this is reminiscent of the idea of something for which there is no definite right answer that can be verified quickly...it reminds me more of coNP and problems such as TAUTOLOGY than NP or SAT.  I guess what I'm getting at is that it's easy to verify when a poem is "wrong" and needs to be improved, but difficult to verify when a poem is "correct" or "finished."

Indeed, NP reminds me more of logic and left-brained thinking than creativity.  Proofs, engineering problems, Sudoku puzzles, and other stereotypically "left-brained problems" are more NP and easy to verify from a quality standpoint than than poetry or music.

So, my question is:  Which complexity class most precisely captures the totality of what human beings can accomplish with their minds?  I've always wondered idly (and without any scientific evidence to support my speculation) if perhaps the left-brain isn't an approximate SAT-solver, and the right-brain isn't an approximate TAUTOLOGY-solver.  Perhaps the mind is set up to solve PH problems...or perhaps it can even solve PSPACE problems.

I've offered my thoughts above; I'm curious as to whether anyone can offer any better insights into this.  To state my question succinctly:  I am asking which complexity class should be associated with what the human mind can accomplish, and for evidence or an argument supporting your viewpoint.  Or, if my qusetion is ill-posed and it doesn't make sense to compare humans and complexity classes, why is this the case?

Thanks.

Update:  I've left everything but the title intact above, but here's the question that I really meant to ask:  Which complexity class is associated with what the human mind can accomplish quickly?  What is "polynomial human time," if you will?  Obviously, a human can simulate a Turing machine given infinite time and resources.

I suspect that the answer is either PH or PSPACE, but I can't really articulate an intelligent, coherent argument for why this is the case.

Note also:  I am mainly interested in what humans can approximate or "do most of the time."  Obviously, no human can solve hard instances of SAT.  If the mind is an approximate X-solver, and X is complete for class C, that's important.

I don't claim this is a complete answer, but here are some thoughts that are hopefully along the lines of what you're looking for.

NP roughly corresponds to "puzzles" (viz. the NP-completeness of Sudoku, Minesweeper, Free Cell, etc., when these puzzles are suitably generalized to allow $n \to \infty$). PSPACE corresponds to "2-player games" (viz. the PSPACE-completeness of chess, go, etc.). This is not news.

People generally seem to do alright with finite instances of NP-complete puzzles, and yet find them non-trivial enough to be entertaining. The finite instances of PSPACE-complete games that we play are considered some of the more difficult intellectual tasks of this type. This at least suggests that PSPACE is "hitting the upper limits" of our abilities. (Yet our opponents in these PSPACE-complete games are generally other people. Even when the  opponents are computers, the computers aren't perfect opponents. This heads towards the question of the power of interactive proofs when the players are computationally limited. There is also the technicality that some generalizations of these games are EXP-complete instead of PSPACE-complete.)

To an extent, the problem sizes that arise in actual puzzles/games have been calibrated to our abilities. 4x4 Sudoku would be too easy, hence boring. 16x16 Sudoku would take too much time (not more than the lifetime of the universe, but more than people are generally willing to sit to solve a Sudoku puzzle). 9x9 seems to be the "Goldilocks" size for people solving Sudoku. Similarly, playing Free Cell with a deck of 4 suits of 13 cards each and 4 free cells seems to be about the right difficulty to be solvable yet challenging for most people. (On the other hand, one of the smartest people I know is able to solve Free Cell games as though she were just counting natural numbers "1,2,3,4,...") Similarly for the size of Go and Chess boards.

Have you ever tried to compute a 6x6 permanent by hand?

I suppose the point is that if you take natural problems in classes significantly above PSPACE (or EXP), then the only finite instances that people are capable of solving seem to be so small as to be un-interesting. Part of the reason "natural" is necessary here is that one can take a natural problem, then "unnaturally" modify all instances of size $< 10^{10}$ so that for all instances a human would ever try the problem becomes totally intractible, regardless of its asymptotic complexity.

Conversely, for problems in EXP, any problem size below the "heel of the exponential" has a chance of being solvable by most people in reasonable amounts of time.

As to the rest of PH, there aren't many (any?) natural games people play with a fixed number of rounds. This is also somehow related to the fact that we don't know of many natural problems complete for levels of PH above the third.

As mentioned by Serge, FPT has a role to play here, but (I think) mostly in the fact that some problems naturally have more than one "input size" associated with them.

If you give a human a pencil and paper she can solve nearly any problem, by acting like a machine.  So I think this can't be the point.

Imho what makes human thinking is abstraction, i.e. humans don't run things (in the first place), they create views on stuff.  Although, as I must admit, I cannot provide any nearly ready to use theory for abstraction.

|=


Unary languages recognized by two-way deterministic counter automata 2dca's (two-way deterministic one-counter automata) (Petersen, 1994) can recognize the following unary language:
\begin{equation}
\mathtt{POWER} = \lbrace  0^{2^n} \mid n \geq 0 \rbrace.
\end{equation}

Is there any other nontrivial unary language recognized by 2dca's?

Remark that it is still unknown whether 2dca's can recognize $ \mathtt{SQUARE} = \lbrace  0^{n^2} \mid n \geq 0 \rbrace $?

DEFINITION: A 2dca is a two-way deterministic finite automaton with a counter. A 2dca can test whether the value of the counter is zero or not, and increment or decrement the value of the counter by 1 in each step.

This is only an idea that came to my mind while reading Marvin L. Minsky, "Recursive Unsolvability of Post's Problem of Tag and other Topics in Theory of
Turing Machines"; in particular the famous theorem Ia:

Theorem Ia: We can represent any partial recursive function $f(n)$
by a program operating on two integers $S_1$ and $S_2$
using instructions $I_j$ of the forms:
(i) ADD 1 to $S_j$, and go to $I_{j_1}$
(ii) SUBTRACT 1 from $S_j$, if $S_j \neq 0$ and go to $I_{j_1}$, otherwise go to $I_{j_2}$
That is, we can construct such a program that starts with $S_1 = 2^n$ and $S_2 = 0$ and
eventually stops with $S_1 = 2^{f(n)}$ and $S_2 = 0$

If you have a two way DFA with one counter over a (semi)infinite tape where the input is given in unary: $\$1^{2^n}000...$ then the DFA can:

read the unary input (and store it in the counter);
work on the $0^\infty$ part of the tape and use the distance from the $1$s as the second counter.

so it can simulate a Turing complete two counters machine.

Now, if you have a recursive function $f(n)$ that runs in time $T(n)$ on a standard Turing machine, a two way DFA with one counter that starts on the finite tape $\$1^m\$ \;$ (where $m = 2^n3^{T'(n)}$ and $T'(n) \gg T(n)$) can:

read the unary input (and store it in the counter);
return to leftmost symbol;
divide the counter by 3 until the counter contains $2^n$ in this way: go right looping from states $q_{z_0}, q_{z_1}, q_{z_2}$ and subtracting 1; if counter reaches 0 in state $q_{z_0}$ go to leftmost symbol adding +1 and continue the division loop, otherwise add 1 (if in state $q_{z_1}$) or 2 (if in state $q_{z_2}$) and go to leftmost symbol adding +3 (i.e. recover the previous value of the counter not divisible by 3) and proceed with step 4.;
at this point the counter contains $2^n$;
calculate $2^{f(n)}$ using the $T'(n)$ space available on the right as the second counter (the value of the second counter is the distance from the leftmost symbol $\$$).

So with the special input encoding described above that gives it enough space on the finite tape, a two-way DFA with one counter and unary alphabet can compute every recursive function.

If the approach is correct, it would be interesting to reason about how to choose $T'(n) \gg T(n)$ or when it is enough to pick a large odd $k \gg 2$ and encode the input as $1^m$, $m = 2^n k^n$

By non-trivial, I assume you mean a language L that can't be accepted by a 1dca. Here seems to be such a language:

CENTER = { w | w is over {0,1}* and w = x1y for some x, y such that |x| = |y|}

This language can't be accepted by 1dca, but CAN be accepted by 1nca. It can be accepted by a 2dca. Details are left as exercise.


Geometric problems that are NP-complete in $R^3$ but tractable in $R^2$? A number of geometric problems are easy when considered in $R^1$, but are NP-complete in $R^d$ for $d\geq2$ (including one of my favourite problems, unit disk cover).

Does anyone know of a problem which is polytime solvable for $R^1$ and $R^2$, but NP-complete for $R^d,d\geq3$?

More generally, do problems exist which are NP-complete for $R^k$ but polytime solvable for $R^{k-1}$, where $k\geq3$?

It's not quite what you ask, because the 3d version is even harder than NP-complete, but: Finding a shortest path between two points among polygonal obstacles in the plane is in polynomial time (most simply, construct the visibility graph of the two terminals and the polygon vertices and apply Dijkstra; there is also a more complicated O(n log n) algorithm due to Hershberger and Suri, SIAM J. Comput. 1999) but finding a shortest path among polyhedral obstacles in 3d is PSPACE-complete (Canny and Reif, FOCS 1987).

This answer doesn't exactly answer your question, but it does have some smaller ties. Rather than answering for $R^2$ and $R^3$, I show you that this exists in $Z^2$ and $Z^3$.

The 2-SAT problem (Boolean Satisfiability) is solvable in polynomial time. Although it is not necessarily "geometric", there is a corresponding problem known as matching, which is more geometric, in a sense, and maps directly with the 2-SAT problem. The name matching is a more general version of k-dimensional matching, where $k = 2$. To reply to your question, the 3-SAT problem is NP-complete, which maps directly to the 3-dimensional matching problem, which also is NP-complete. Thus, the k-SAT problem (and thus the k-dimensional matching) is another problem that is tractable in $Z^2$ and is NP-complete in $Z^k$ where $k > 2$.


Algorithm for Max Network Flow with lower bounds and its complexity I have built a max network flow graph that carries certain amount of people from a source to a destination. Now, I'd like to attach a lower bound $l_(e_)$ constraint to each edge $e$. But I don't know what algorithm to use and how to analyze its complexity. Here's the graph:

http://jeffe.cs.illinois.edu/teaching/algorithms/notes/25-maxflowext.pdf

There's a very simple reduction from that problem to the maximum flow problem. This is simply called "maximum flow with edge demands".

The formal prolem is called: "Maximum Flows with Edge Demands" and it's available here: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/25-maxflowext.pdf


Is longest common subsequence with bounded occurrences NP-complete? The general longest common subsequence problem (LCS) over a binary alphabet is NP-complete. Does the problem remain NP-complete if each input string has m zeros and n ones, where m and n are constants?

I asked this question on cs.stackexchange and was told, "The problem probably remains NP-complete." However, I was unsuccessful in showing a reduction from the original LCS problem.

This paper by Blin et al. (Hardness of Longest Common Subsequence for Sequences with Bounded Run-Lengths, CPM'12) provides a reduction from independent set to LCS where the Hamming weights of all strings are the same (it is $n-1$ where $n$ is the number of vertices in the independent set instance). Thus, the problem remains NP-complete under this assumption.

I believe the problem was shown to be NP-Hard, as opposed to NP-Complete.  I am not personally familiar with any proof of reducibility of SAT to LCS.  Such a proof is required for a problem to be regarded as NP-Complete.  NP-Complete essentially means that a given problem is at least as hard as SAT.  The reduction of a problem to SAT in P-time and P-space merely shows the problem is itself no harder the SAT.  The LCS problem has a P-time and P-space solution as an answer set problem.


Counting subsets with large sum Suppose that you have a multiset of positive integers $I$.

$I$ is not given, but it is known that the sum over all elements of $I$ = $k$.

(e.g. if $I$={2,5,7} then k=14 is given, but I is unknown).

We are also given another integer $r$.

$S\subseteq I$ will be called $r-minimal-subset$, if $sum(S)>r$,

and for every $x\in S$, $sum(S$\{x}$) \leq r$.

For example, if $I$={1,3,3,5,7,8} and r=10,

then {3,3,5} and {1,3,7} are r-minimal-subset, but {5,7,8} is not (as the subset {7,8} 's sum is 15. {7,8} is a r-minimal-subset).

What is the the best upper bound we can give on the number of $r-minimal-subsets$ of I?

(In this setting, we get is $(r,k)$, while $I$ is being chosen by an adversary).

~~~~~~~~~~~~~~~~~~~~~~~~~~

Edit:
Hmm, sorry for the question.

Obviously the answer is $k \choose r+1$, for I={1,1,..,1}, $|I|=k$.
It doesn't let me answer the question, so you could go ahead :/.

Let me know if I understood the question correctly: you want to count the sets of $n$ positive integers summing exactly $k$, right? This is $\binom{n+k+1}{k}$. If you want for non-negative integers version, add one more number to the count, $\binom{n+k+1}{k+1}$.


Is the concept of the Turing Machine derived from automata? I was just recently having a discussion about Turing Machines when I was asked, "Is the Turing Machine derived from automata, or is it the other way around"?

I didn't know the answer of course, but I'm curious to find out. The Turing Machine is basically a slightly more sophisticated version of a Push-Down Automata. From that I would assume that the Turing Machine was derived from automata, however I have no definitive proof or explanation. I might just be plain wrong... perhaps they were developed in isolation.

Please! Free this mind from everlasting tangents of entanglement.

Neither!

The best way to see this independence is to read the original papers.

Turing's 1936 paper introducing Turing machines does not refer to any simpler type of (abstract) finite automaton.
McCulloch and Pitts' 1943 paper introducing "nerve-nets", the precursors of modern-day finite-state machines, proposed them as simplified models of neural activity, not computation per se.

For an interesting early perspective, see the 1953 survey by Claude Shannon, which has an entire section on Turing machines, but says nothing about finite automata as we would recognize them today (even though he cites Kleene's 1951 report).

Modern finite automata arguably start with a 1956 paper of Kleene, originally published as a RAND technical report in 1951, which defined regular expressions.  Kleene was certainly aware of Turing's results, having published similar results himself (in the language of primitive recursive functions) at almost the same time.  Nevertheless, Kleene's only reference to  Turing is an explanation that Turing machines are not finite automata, because of their unbounded tapes.  It's of course possible that Kleene's thinking was influenced by Turing's abstraction, but Kleene's definitions appear (to me) to be independent.

In the 1956 survey volume edited by Shannon and McCarthy, in which both Kleene's paper on regular experssions and Moore's paper on finite-state transducers were finally published, finite automata and Turing machines were discussed side by side, but almost completely independently.  Moore also cites Turing, but only in a footnote stating that Turing machines aren't finite automata.

(A recent paper of Kline recounts the rather stormy history of this volume and the associated Dartmouth conference, sometimes called the "birthplace of AI".)

(An even earlier version of neural nets is found in Turing's work on "type B machines", as reprinted in the book "The essential Turing", from about 1937 I think.  It seems likely that many people were playing with the idea at the time, as even today many CS undergrads think they have "invented" it at some point in their studies before discovering its history.)

Just for the hell of it:

  Looking back, what would you say was the significance of Turing's 1936
  Entscheidungs-problem paper?

  I always felt people liked to make a song and dance. Something like
  the doctrine of the Trinity involved whereas to an engineer you've
  only got to be told about the stored program idea and you'd say at
  once "That's absolutely first-rate, that's the way to do it." That was
  all there was to know.

  There was no distinction in that paper that had any practical
  significance. He was lucky to get it published at all but I'm very
  glad he did. I mean [Alonzo] Churchl had got the same result by other
  methods.

  I liked Turing; I mean we got on very well together. He liked to lay
  down the law and that didn't endear him to me but he and I got on
  quite well. People sometimes say I didn't get on with Turing but it's
  just not true. But then I was very careful not to get involved.

Maurice Wilkes.
 http://cacm.acm.org/magazines/2009/9/38898-an-interview-with-maurice-wilkes/fulltext