Problems with mixed unary/binary inputs As a mild follow-up to this question on alphabet sizes, let me ask about the other part of the natural numbers, i.e. $\le 2$.

Clearly everyone knows about problems over a binary alphabet. Unary, on the other hand, is most commonly used in input encodings for a problem to a Turing machine (at least, that's the use I'm interested in). But, are there any good examples of problems where the input is encoded with an explicit mix of the two, perhaps in order to make a particular complexity argument? Admittedly, since many classes (like NP) are closed under concatenation, you could just append one such problem's input to another -- but I'm particularly interested in problems where the "natural" form of the problem requires a mix.

What are some problems where their standard input to a Turing machine is a mix of unary and binary encoding? (Bonus points if the only-unary or only-binary encoded versions are meaningful as well!)

P.S. I'm less interested in broad "classes of problems" (not to be confused with complexity classes), such as "any crypto problem" where there is frequently a security parameter of $1^n$ and the rest of the problem is in binary, or as Tsuyoshi points out, "any FPTAS". I'm very interested in specific computational problems that require both a unary and a binary component in the input for the problem to be meaningful (and perhaps, to be meaningful at all).

Knapsack problem. It can be solved in polytime by dynamic programming if you give the target weight in unary.

Similarly other problems which are weekly polynomial time (pseudo-polynomial time) but not strongly polynomial time would need some part of input to be in unary. (You may also want to search for weakly NP-complete.)


Examples of problems where exponential algorithms run faster than polynomial algorithms for practical sizes? Do you know of any problems (preferably at least somewhat well known), where, for a practical problem size, an exponential algorithm runs much faster than a best-known polynomial time counterpart.

For example, suppose a problem has a practical size* of $n = 100$ and there are two known algorithms: One is $2^n$ and the other is $n^c$ for some constant $c$. Clearly for any $c > 15$, the exponential algorithm is preferred.

*I guess practical size would mean something commonly found in the real world. Like the number of trains on a network.

How bout the simplex algorithm for linear programming?
In many occasions it is used in practice.
Edited to add:
I think it's more of a "worse-case exponential algorithm" which runs efficiently on practical instances/distributions rather than runs faster on practical sized adversarial instances.


How do top researchers keep track new results in datastructures Is there any twitter or some feed,which constantly sends new results which are being published to your mail.

You can subscribe to the RSS of ArXiv, and you can keep track of which papers are getting accepted to the relevant conferences.


State transducers for generating permutations Let a finite alphabet $\Sigma$.

Let $\mathcal{Reord_\Sigma}$ be the family of computable partial functions between the strings of this alphabet $r\,:\, \Sigma^*\, \rightarrow \Sigma^*$ with the restriction that the value must be a permutation of the argument.

I'm interested in a class of deterministic abstract machines with finite control that compute all and only the functions of this family. That is, given a string $s \in \Sigma^*$ as input, the machine either doesn't halt or halts returning a permutation of $s$, and every possible mapping of those is realized by some machine in the class.

All the transitions should be local (no random access on a tape), and possibly they should not explicitely name the symbols to be written (they should be 'copy' or 'swap' operations, not 'write symbol "A" ').

Does this class of transducers exist? Has it been researched?

If you allow an auxiliary work tape, then it is easy to customize the Turing machine model to suit your needs. The Turing machine has two tapes: input/output and work. The work tape operates as usual, while on the input/output tape, all you can do is switch two adjacent values. This is enough since the transpositions $(i \quad i+1)$ generate all of $S_n$.

If you don't allow a work tape, then the goal might be impossible. Let $f$ be a recursive function not computable in $O(n\log n)$ space. We can think of $f$ as a reordering function as follows: convert the $n$ input bits into a permutation in $S_{2n}$ conforming to the regular expression $(12+21)(34+43)\cdots$. The output is read, say, from whether the first element is smaller than the second element or vice versa. In many reasonable models, a computation is convertible to a Turing machine computation with space $O(n\log n)$. (Though a "copy" operation might invalidate this.)

Finally, you ask whether this class of transducers has been researched. Since you want this class to encompass all partial recursive reorderings, it is fair to say that recursion theory is the study of these reorderings and their non-recursive generalizations.


Turing Machines and Subroutine Simulation I have been reading Wikipedia as an introduction to Turing machines. I found a reference to John Hopcroft and Jeffrey Ullman, (1979). Introduction to Automata Theory, Languages and Computation (1st ed.), with a note that it is difficult to read. I am working hard with Wikipedia, and fear I will be unable to understand Hopcort and Ullman.

I am curious about how a Turing machine simulates a subroutine. If I understand http://en.wikipedia.org/wiki/Post%E2%80%93Turing_machine correctly, a Turing machine stores the return address and jumps to the subroutine, and jumps back to exit the subroutine, as an IBM360, IBM3* series machine did using BL (branch and link). Of course, modern machines store the return address on a stack and call the subroutine, but the two are similar. Is my assumption about storing the return address and jumping to simulate a subroutine correct?

Furthermore, has anyone simulated a subroutine by adding a symbol to the Turing machine alphabet for each subroutine? Symbols not defined within the machine would merely default to calling/jumping to the address of the subroutine. This technique is not much different from the one described in the paragraph above. I ask, because a machine I once worked on, and SDS 930 had some undefined op-codes that could be used to call subroutines. (Scientific Data Systems (SDS) was purchased by Xerox and renamed XDS).

Martin Davis's book "Computability and Unsolvability" contains a very detailed account of Turing machines. In gory detail. In your particular case Corollary 2.2 on page 37 shows that composition of Turing-computable functions is again Turing-computable. This is just another way of saying that subroutines can be done.


hardness of approximating the chromatic number in graphs with bounded degree I am looking for hardness results on vertex coloring of graphs with bounded degree.

Given a graph $G(V,E)$, we know that for any $\epsilon>0$, it's hard to approximate $\chi(G)$ within a factor of $|V|^{1-\epsilon}$ unless $\textit{NP}=\textit{ZPP}$ [1]. But what if the maximum degree of $G$ is bounded by $d$? Are there any hardness ratios of the form $d^{1-\epsilon}$ (for some $\epsilon$) in this case?

An easier question is: Hardness of approximating the edge-chromatic-number of hypergraphs when their edge size is bounded by $d$. Can we hope for a $d^{1-\epsilon}$ hardness ratio in this case? (say, for any $\epsilon >0$)

Thanks for your attention!

As David pointed out, Khot's paper, "Improved Inapproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring", Theorem 1.6, says it is NP-hard to color $K$-colorable graph with $2^{\Omega((\log K)^2)}$ colors for graphs with degree at most $2^{2^{(\log K)^2}}$, for sufficiently large constant $K$. In other words, for graphs of degree $d$, it is hard to color $2^{\sqrt{\log\log d}}$-colorable graph with $\log d$ colors.

To get better degree bound, you can probably use ideas from Trevisan's paper "Non-approximability results for optimization problems on bounded degree instances". The key observation is that the graph produced by the FGLSS reduction is a union of complete bipartite subgraphs, and one can replace each of them with a bipartite disperser which is much sparser. Similar idea used in many result such as Chan http://eccc.hpi-web.de/report/2012/110/, Theorem 1.4 / Appendix D.

I think this should give you something like for $2^{\sqrt{c\log d}}$-colorable graphs of degree bounded by $d$, it is NP-hard to color it with $d^{c}$ colors for some constant $0<c<1$.

The degree bound in the paper Michael mentioned is similar to Khot's, namely exponential of the soundness case. Of course the above sparsification approach also improves this, but probably won't give better constant for your purpose.


Reversible Logic Circuit Synthesis I am about to choose a project regarding "Reversible logic circuit synthesis". I've studied well about "Switching circuits and Logic design" and I found it very intriguing but I've got no idea about the other topic. Can someone please elaborate it and explain what it refers or point some sources. Thank you guys in advance. :)

I'm not very familiar with the field, but my advisor Shigeru Yamashita is. I recommend you to check his home page. Here are some interesting papers he has:

A transduction-based framework to synthesize RSFQ circuits. Shigeru Yamashita, Katsunori Tanaka, Hideyuki Takada, Koji Obata, Kazuyoshi Takagi. In ASP-DAC 2006.
Transformation rules for designing CNOT-based quantum circuits. Kazuo Iwama, Yahiko Kambayashi, Shigeru Yamashita. DAC 2002.
DDMF: An Efficient Decision Diagram Structure for Design Verification of Quantum Circuits under a Practical Restriction. Shigeru YAMASHITA, Shin-ichi MINATO and D. Michael MILLER. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E91.A (2008) , No. 12 pp.3793-3802.

Other people that you should check their home pages are Igor Markov and Dimitri Maslov.


Automatic theorem prover for first-order logic versus model checker What's the formal difference between a model checker, and an automated theorem prover for first-order logic, i.e. something like Meson/Metis/Sledgehammer/Vampire/E? Link to a clear discussion of the difference is preferred.

To add to the answer in the comments, it might help to first ask what the difference is between a model checker and an automated theorem prover for propositional logic.

Given the statement $$p \wedge q$$ we can ask whether it is true in the model $\{p=\top,q=\bot\}$ (model checking) or we can ask whether it is true in all models (theorem proving). We can also ask whether it is true in some models (satisfiability checking).

The same concepts follow over to first-order logic. For model checking we need a model; for theorem proving we don't.


minimal cycles in undirected graph My initial problem is geometric, but I've reformulated it to a graph:

In the graph above I need to find the set of minimal simple cycles that form the whole graph. The initial problem was to separate the complex figure into the minimal closed regions. In the graph formulation I assume that is suffices to find the set of cycles that represents the whole graph with minimal number of edges in every cycle.

Every vertex is connected to at least two other vertices, i.e. there are no "hanging" vertices. The possible graphs are planar and bridgeless. However, in general the graph may contain multiple connected components (if this is a serious restriction - ignore it). The graph can be considered as both weighted and unweighted, but I think it's better to consider it as unweighted if the goal is to find the cycle basis of minimal closed regions. The graphs in question either have one planar embedding or multiple "equivalent" planar embeddings (e.g. consider the example graph: the parallel edges can be moved, but the simple closed loops will remain the same).

There is some ambiguity possible because of the parallel edges between some pairs of vertices. These multiple solutions are OK if they are equally valid.

I've read in http://en.wikipedia.org/wiki/Spanning_tree about fundamental cycles, but I'm not quite sure that finding the fundamental cycles will solve the problem for every case.

P.S.: See also this question https://stackoverflow.com/questions/13111236/how-to-detect-minimal-cycles-in-a-graph - it contains mine problem formulation, but no real solution. It would really be nice to give more hints than google. And https://stackoverflow.com/questions/16782898/algorithm-for-finding-minimal-cycles-in-a-graph contains some suggestions but without any serious justification.

P.P.S.: Crossposting on CS.SE was removed (the question was deleted), but this question can still be moved to CS.SE if it's better fits there. Sorry for this misunderstanding.

The solution is here, I hope that it helps somebody.. The link given also in the question itself contains a useful pdf from geometrictools.com

Sorry, the question was really not that hard, but it is somehow quite popular and there's still a lot of confusion about "all faces of a planar embedding of a graph"


Directed graph with bounded in-deg can be partitioned in a balanced way I want to prove that for all $n$, there exists a constant $c(n)$ such that if $G=(V,E)$ is a directed graph with in-degree bounded by $n$, it is possible to partition the set of vertices $V$ into two sets $V_1, V_2$ in a way that for each vertex $v\in V_1$ (and the same for every vertex in $V_2$) , if the vertex $v$ has out-degree $d(v) \geq c(n)$ in $G$, then its out degree in the corresponding subgraph will be between $\frac{1}{3}d(v)$ and $\frac{2}{3}d(v)$.

I suspect that it is the kind of statements which can be proved by the probabilistic method, using the local lemma (since there are some similar theorems proven in this way). However I couldn't figure out how to do that, will be glad for help.
(I have also asked this question in math.stackexchange a while ago, but since this is a research question, I believe this forum is more appropriate).

This is a special version of the Beck-Fiala theorem.
Define a set system on the vertices whose sets are the out-neighborhoods of the vertices.
The in-degree condition will give that every element is in at most $n$ sets.
The theorem states that in this case the elements can be colored with red and blue such that the difference of the red and blue elements in any set is at most $2n-1$.
This means that in your digraph the out-degree of each vertex $v$ in the corresponding subgraph is between $d(v)/2-n$ and $d(v)/2+n$, so for your specific question $c(n)\ge 6n$ is sufficient.


Alternative proofs of Schwartz–Zippel lemma I'm only aware of two proofs of Schwartz–Zippel lemma. The first (more common) proof is described in the wikipedia entry. The second proof was discovered by Dana Moshkovitz.

Are there any other proofs which use substantially different ideas?

As a followup to Per Vognsen's answer, Dana Moshkovitz's proof already suggests a really easy proof for only a slightly weaker version of the Schwartz-Zippel Lemma that, I think, suffices for most applications.

Let $f : \mathbb{F}^n \to \mathbb{F}$ be a nonzero polynomial of degree $d$, where $\mathbb{F}$ is a finite field of order $q$, and let $x \in \mathbb{F}^n$ be a point such that $f(x) \neq 0$.  There are $(q^n-1)/(q-1)$ many distinct lines passing through $x$ such that they partition $\mathbb{F}^n-\{x\}$.  The restriction of $f$ to each of these lines is a degree $d$ univariate polynomial, which is nonzero, because it is nonzero at $x$, and so, has at most $d$ zeros.  Thus, the total number of zeros of $f$ is at most $d(q^n-1)/(q-1)$.  Schwartz-Zippel, for comparison, gives the stronger upper bound of $d q^{n-1}$.

Given this proof's easiness, I'm sure it's folklore; if not, it should be :)  I'd appreciate if someone could provide a reference.


Exact formula for the number of spanning trees of a rectangle This blog talks about generating "twisty little mazes" using a computer an enumerating them.  The enumeration can be done using Wilson's algorithm to get the UST, but I don't remember the formula for how many there.

http://strangelyconsistent.org/blog/youre-in-a-space-of-twisty-little-mazes-all-alike

In principle the Matrix Tree Theorem states the number of spanning trees of a graph is equal to the determinant of the Laplacian matrix of the graph.  Let $G= (E,V)$ be the graph and $A$ be the adjacency matrix, $D$ be the degree matrix, then $\Delta = D - A$ with eigenvalues $\lambda$, then:

$$ k(G) = \frac{1}{n} \prod_{k=1}^{n-1} \lambda_k $$

In the case of an $m \times n$ rectangle both $A$ and the eigenvalues should take a particularly simple form, which I can't find.

What is the exact formula (and asymptotics) for the # of spanning trees of an $m \times n$ rectangle?

Here is a pretty example of Wilson's algorithm in action.

According to https://www.cse.ust.hk/~golin/pubs/ANALCO_05.pdf there is no closed-form formula known.

According to http://arxiv.org/pdf/cond-mat/0004341v1.pdf the number is asymptotic (for $n$ and $m$ both large) to
$$\exp (z_{\mathrm{sq}}mn)$$
where
$$z_{\mathrm{sq}}=\frac{4}{\pi}\sum_{i=0}^\infty\frac{(-1)^i}{(2i+1)^2}\approx 1.16624$$
but I'm not sure whether this is a rigorous bound or the result of heuristic physics-based reasoning. The same paper also gives asymptotic formulas of similar type when $m$ is fixed to a small constant and $n$ is large.


Shortest distance/path between two households If you wanted to know the shortest distance/path between two household addresses, which data structure(s) would you use to return the answer efficiently?

Say you are considering the set of all households in the United States (~100 million).

I am struggling to come up with a practical data structure considering the input size is so big. Dijkstra's seems too inefficient, but I'm guessing there is a way to preprocess the paths to make such a query possible.

This problem is well considered and learned in recent decades as every GPS device faces this problem.

In practice (AFAIK), the standard way of facing this problem is by the usage of distance oracles, which usually (or more correctly, used to) approximate the distance between every two nodes by keeping only a $k\times n$ distances tables for a well-selected $k$ vertices.

The lastest result I'm aware of, keep a data structure of size $O(kn^{1+1/k})$, answering queries in $O(1)$ time and giving a stretch (i.e. the return value $\delta$ is promised to suffice $d\leq \delta \leq d\cdot s$). of $2k-1$.

Alternatively, if you're looking for a stretch smaller than 2, I suggest looking at this paper.


Technical lemma about curves used in original proof of PCP theorem I am reading the proof from here and found a technical lemma that seems to be incorrect (its proof is short and very vague). I know this is rather specific and the context is problematic, but I couldn't figure it out myself.

In page 67 (when proving a claim that is used for soundness of local decoding of low degree polynomials procedure), the writers use a "fact" A.9 (regarding "Well   Distribution Lemma in Curves") that is located in page 156.

The proof is very short and I cannot grasp it.

Moreover, the statement seems to be incorrect by the following example:

Let $S=\{x_1\}$, then $\forall$ curve $C\in P(\langle x_1,\dots,x_k\rangle)$ we have $|C\cap S|\geq 1$ as $C$ is a multiset, so
$$\mathbb{E}\left[\frac{|C\cap S|}{|C|}\right]\geq\mathbb{E}\left[\frac{1}{|C|}\right]>\frac{1}{|\mathbb{F}|^m}=\frac{|S|}{|\mathbb{F}|^m}$$
Maybe, I miss something in the statement of the lemma...

I will appreciate any help in understanding this problem.

Notation: Let $P(\langle x_1,\dots,x_k\rangle)$ the set of degree $k$ curves that evaluates to $x_1,\dots,x_k\in\mathbb{F}^m$ at the first $k$ field elements in $\mathbb{F}$ and we will use just $P$ as a shorthand for this set.  Let $S$ be any subset of $ \mathbb{F}^m$. Below, we assume
that multiplicity is taken into account when set cardinalities are computed and for any curve $C\in P$, $|C|:=|\{C(i) : k+1<i\leq \mathbb{F} \}|$.

Claim 1: $\mathbb{E}_{C}\big[ \frac{|C\cap S|}{|C|} \big]=\frac{|S|}{|\mathbb{F}|^m}$ where $C$ is a random curve in $P$.

Proof: $\mathbb{E}_{C}\big[ \frac{|C\cap S|}{|C|} \big]=\sum_{C'\in P}\Pr_{C}\big[C=C' \big]\cdot\Pr_{i}\big[C'(i) \in S\big]= \Pr_{C,i} \big[C(i)\in S \big]= \frac{|S|}{|F|^m} $

Here $C$ is a random curve in $P$ and $i$ is randomly sampled from $\{k+1,\dots,\mathbb{F} \}$. The last line holds because sampling a random curve from $P$ and then evaluating the curve at a random $i$ gives a random element from $\mathbb{F}^m$. To see why this is true consider the bipartite graph on $P\cup \mathbb{F}^m$ where for each $i\in \{k+1,\dots,\mathbb{F}\}$, each curve $C\in P$ has a neighbor $C(i)\in \mathbb{F}^m$. Its easy to check that this is a bi-regular graph. Thus, the distribution that samples a random $C$ and outputs a random neighbor $C(i)\in \mathbb{F}^m$ , is same as the distribution that randomly outputs an element from $\mathbb{F}^m$. The claim follows.

Remark 1: Claim 1 implies  that if $|S|/|\mathbb{F}|^m\leq \delta$ then we must have $\Pr_{c}[\Pr_{i}[~c(i)\in \mathcal{S}] >  \sqrt\delta] \leq \sqrt{\delta}$. This I believe is the claim (from the linked thesis) that OP refers to.

Remark 2: What happens if we just sample a random point $i$ from the entire field $\mathbb{F}$ instead of $\{k+1,\dots,\mathbb{F} \}$. Nothing will change much as it will incur a small(if $k\ll |\mathbb{F}|$) additive error of $k/|\mathbb{F}|$. In [1] below this error is there in the argument in page 38.

[1] https://madhu.seas.harvard.edu/papers/1997/arora-journ.pdf


Efficient Shamir secret sharing reconstruction Shamir's secret sharing scheme is a well known way to convert a secret into a polynomial and distribute points in this polynomial. Some of these points can then be regrouped to reconstruct the original polynomial and subsequently the secret.

The regrouping process can be summarized as finding $p(0)$ in a polynomial knowing only the degree and pairs $(x_i, y_i)$ such that $p(x_i) = y_i$.

My question is: how do I do this efficiently? All implementations I've seen so far are $O(n^2)$ because they recompute the polynomial using Lagrange, with a few optimizations. Are there known faster ways?

Yes. If you choose the evaluation poitns for the polynomial carefully, this problem is the same as correcting erasures in the Reed-Solomon encoding of a message, and there are faster algorithms for that problem.

http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction


What relations and differences are between formal semantics for linguistics and for programming languages? I browsed the table of content of Cann's Formal Semantics, which   reminds me  of the things that I saw in programming language books.
Cann's book is for linguistics, and am I right that it is helpful for computational linguistics and natural language processing, another active research area of computer science? (Side note: it also seems to me that the approaches to NLP have been predominantly based on statistics and machine learning in applications (and maybe also research), which I think is completely unrelated to formal semantics?)
Do formal semantics of linguistics and semantics of programming languages (and the ways of study each of the two) have more common ground than differences?  What are their common ground and what are their differences?  Are books on one helpful to study in the other?
Thanks.

This question is very open-ended and therefore difficult to answer, but I think the short answer is "yes", there is much common ground, the two areas have in fact benefited from interaction in the past, and they have much to gain from further interaction.
Two classical examples of this (respectively from the 1950s and '70s) are Lambek grammar and Montague grammar, which model different aspects of natural language using sequent calculus and lambda calculus (which have become cornerstones of programming language theory, with connections to category theory and type theory).
In relatively more recent history, personally I found Ken Shan's dissertation Linguistic side effects (2005) an inspiring exploration of the thesis that natural languages and programming languages have more common ground than differences.  To quote a bit from the introduction:

This dissertation is about computational linguistics, in two senses. First,we apply insights from computer science, especially programming-language semantics, to the science of natural languages. Second, we apply insights from linguistics, especially natural-language semantics, to the engineering of programming languages. The phrase “computational linguistics” has a popular third sense, which is natural-language processing: teaching computers to listen to, speak, read, and write natural language. That is not our aim, even though the research described here indirectly helps it—by enhancing our understanding of natural and programming languages.

Chris Barker has also written extensively about the concept of continuation from programming languages semantics and how it may be used to illuminate the nature of quantification in natural language, and the two have recently collaborated on a book which explores this topic further.


Proof that the calculus of constructions extended with recursive types isn't strongly normalizing? What is the proof that the calculus of constructions, extended with recursive types (i.e., Fix at the type-level) isn't strongly normalizing?

With general recursive types you can define the type

type T = T -> T

With that type you can type self-application -- and in fact, every term of the untyped lambda calculus, including any of the well-known fixed-point operators. For example, the Y operator:

Y = \f:T. (\x:T. f (x x)) (\x:T. f (x x))


Splitting a graph into minimum number of subpaths I have an ordinary weighted graph. I need to traverse every edge in the graph at least once. BUT I must do it in subpaths of maximum length L. Those subpaths need not be connected to each other. There is no edge greater than L. How to find out the minimum number of paths neccessary and how to find out these paths?

First I thought about Chinese Postman, but it gives one big path, which might not be the optimal solution. I also thought about bin packing problem, but I am not sure how to ensure the edges in every "bin" form a path.

Your problem (as stated) seems to be NP-hard.  Here is a reduction from Partition.

Given an instance of Partition (a collection $x_1,\ldots,x_n$ of positive integers), construct a graph with $n+1$ vertices $v_1,\ldots,v_{n+1}$ and, for each $i$, two edges from $v_i$ to $v_{i+1}$: one of cost zero, one of cost $x_i$.

Suppose the Partition instance is satisfiable. That is, there is a subset $S$ of $[n]$ such that $\sum_{i\in S} x_i = \sum_{i} x_i/2$.  Then there are two paths that together cover all the edges, with each path costing $L=\sum_{i} x_i/2$.

Conversely, if there are two paths each of cost at most $L$ (that cover all the edges), the two paths together must cover each $x_i$ exactly once, and the total weight on each must be exactly $L$. So there must be a subset $S$ such that $\sum_{i\in S} x_i = \sum_i x_i/2$.  That is, the Partition instance is satisfiable.

Perhaps you have further restrictions (e.g. polynomially bounded integer edge weights)?


Can any computational challenge be transformed to proof-of-work? The seemingly pointlessness of cryptocurrency mining raised the question of useful alternatives, see these questions on Bitcoin, CST, MO.
I wonder whether there exists an algorithm that can convert practically any computational challenge $\mathcal C$ (whose solution can be verified efficiently) into another such challenge $\Psi(\mathcal C)$ (which is used for proof-of-work) such that

The function $\Psi$ is randomized, using some (public) random sequence $r$.
Solving $\Psi(\mathcal C)$ is typically as hard as solving $\mathcal C$.
If a solution $x$ is found for $\Psi(\mathcal C)$, then a solution $\Psi^{-1}(x)$ can be efficiently computed for the original challenge $\mathcal C$.
Knowing a solution for $\mathcal C$ does not help in finding a solution for $\Psi(\mathcal C)$.

$\;\:\:$4' (Update). As pointed out by Noah in a comment, the previous condition should be strengthened to requiring that preprocessing $\mathcal C$ should also not give any advantage in solving $\Psi(\mathcal C)$.

This last condition is required so that no one can be put into an advantageous position just because they know a solution of $\mathcal C$.
Using this method, people could submit computational problems that they want solved and a central authority could pick some worthy of solving (like finding aliens vs. breaking passwords).
Note that it doesn't seem to be an issue if the problem takes even a week to solve (I guess those aliens can't be that good in hiding ;), as this could result in a bigger reward for a solution.
Anyways, these topics are not related to the solution of my theoretical problem, but of course I'm happy to discuss them in the comments/on the forum.

A possible solution would be the following: $\Psi$ maps $\mathcal C$ into $(\mathcal C,HASH_r)$, that is, to solving $\mathcal C$ and some other, computationally hard challenge.
One problem with this is that knowing a solution to $\mathcal C$ does make solving $\Psi(\mathcal C)$ somewhat easier (how much easier depends on the difficulty of $HASH_r$).
Another issue is that $\Psi(\mathcal C)$ became more difficult than $\mathcal C$.

(Note:  Andreas Björklund suggested a solution in the comments that I believe is better than the one described below. See http://eprint.iacr.org/2017/203, by Ball, Rosen, Sabin, and Vasudevan. In short, they give proofs of work based on problems like Orthogonal Vectors whose hardness is well understood and to which many problems (e.g., k-SAT) can be reduced relatively efficiently. Their PoW instance $\Psi(\mathcal{C})$ is as hard as a worst-case Orthogonal Vectors, even if the input instance $\mathcal{C}$ is easy, so that they avoid a major drawback of the solution described below.

The solution described below might benefit from its simplicity---it can be described to a non-expert---but it seems to me to be much less interesting theoretically.)

A solution is possible if one makes the strong assumption that "the fastest algorithm for $\mathcal{C}$ is fundamentally randomized" (and if we model a cryptographic hash function as a random oracle). One way to formalize this is to say that

$\mathcal{C} \in \mathsf{TFNP} \setminus \mathsf{FP}$ (otherwise, I guess it's not really a valid challenge);
the fastest randomized algorithm for $\mathcal{C}$ runs in expected time $T$ on a typical instance; and
there exists an efficiently computable function $f$ from $\{0,1\}^k$ to the domain of solutions to $\mathcal{C}$ for $k \approx \log_2 T$ such that there always exists an $s \in \{0,1\}^k$ with $f(s)$ a solution to $\mathcal{C}$.

Notice that the assumption that $k \approx \log_2 T$ implies that brute-force search of $\{0,1\}^k$ is essentially the optimal algorithm for $\mathcal{C}$. So, this is quite a strong assumption. On the other hand, if $\mathcal{C}$ does not satisfy these properties, then it's hard for me to imagine satisfying both your conditions (2) and (4).

Then, given a hash function $H : \{0,1\}^* \to \{0,1\}^k$, which we model as a random oracle, we define $\Psi_H(\mathcal{C}; r)$ as follows, where $r \in \{0,1\}^\ell$ for some $\ell \gg k$ is the random input to $\Psi_H$. The goal is to output $x \in \{0,1\}^*$ such that $f(H(r,x))$ is a solution to $\mathcal{C}$. In other words, $(r,x)$ should hash to "good random coins" for the above algorithm.

Let's see that this satisfies all of your conditions.

"The function $\Psi$ is randomized, using some (public) random sequence $r$." Check!
"Solving $\Psi(\mathcal{C})$ is typically as hard as solving $\mathcal{C}$." Notice that the simple randomized algorithm for $\Psi_H(\mathcal{C},r)$ runs in expected time at most $2^k$ plus polynomial overhead, and by assumption $2^k \approx T$ is essentially the running time of the optimal algorithm for $\mathcal{C}$.
"If a solution $x$ is found for $\Psi(\mathcal{C})$, then a solution $\Psi^{-1}(x)$ can be efficiently computed for the original challenge $\mathcal{C}$." This can be done by computing $f(H(r,x))$, which is a solution to $\mathcal{C}$ by assumption.
"Knowing a solution for $\mathcal{C}$ does not help in finding a solution for $\Psi(\mathcal{C})$." By definition, solving $\Psi_H(\mathcal{C}; r)$ requires finding $x$ such that $f(H(r,x))$ is a solution to $\mathcal{C}$. Since we modeled $H$ as a random oracle, we can lower bound the expected running time of any algorithm that solves this problem by the optimal expected query complexity of the query problem in which $H$ is given by a black box and we are asked to find a solution to the same problem. And, again because $H$ is a random oracle, the expected query complexity is just the inverse of the fraction of elements $x \in \{0,1\}^k$ that are solutions (up to a constant factor). By assumption, the optimal expected running time of any algorithm for $\mathcal{C}$ is $T \approx 2^{k}$, which implies that this fraction cannot be much larger than $2^{-k}$. Since $\ell \gg k$ and $r \in \{0,1\}^\ell$ is chosen uniformly at random, this is even true with preprocessing that is allowed to depend on $H$ and $\mathcal{C}$ (but not $r$), and in particular it is true even if we know a solution to $\mathcal{C}$ in advance.


Where do I turn for help with research/publishing? I have been developing a SAT algorithm for a while, and have reached a point where I'd like to share it.  I don't know many people in computer science, and I'm not sure exactly where to turn.

I'm wondering what resources are available for someone with an algorithm who is considering publishing.  I also need help analyzing the runtime and correctness of my algorithm.

My major problem is in analyzing the runtime.  I need help with a detailed analysis of this.  I'm fairly certain that the algorithm is correct, but it would be helpful if someone would verify this as well.

So is there anyone who would be willing to analyze my algorithm?  Additionally, what resources are available for a task like this?

If your SAT algorithm is meant to be practical, then you should run the SAT competition benchmarks on it.  The SAT solving community is going to take your work much more seriously if you can show that your approach is competitive with existing solvers.  Your solver doesn't have to be faster than every solver, or solve more instances, but it should be a serious competitor.  You don't need a very fast or powerful machine to run the benchmarks; you can simply compare runtime against one of the free SAT solvers like MiniSAT or PicoSAT.  These solvers will also allow you to see what the answers should look like.

If you are working on a practical solver that uses new techniques, and your approach is not yet competitive, I would still suggest trying these benchmarks.  They would help you to understand the kinds of problems that you should be aiming to solve, and the kind of performance you should be aiming for.  You might also want to read some of the key chapters of the Handbook of Satisfiability, or the recent survey

Knot Pipatsrisawat and Adnan Darwiche, On Modern Clause-Learning Satisfiability Solvers, Journal of Automated Reasoning 44 277–301, 2010. (PDF)

to see the kinds of arguments that support the major solvers.  If you have new ideas that are not yet optimized to perform as well as the top solvers, you would need to explain the potential advantages of your approach to someone who knows the long sequence of theoretical reasoning that has led to the current set of "best practice" design decisions.

If your contribution is purely theoretical, then you need to be aware of the many papers in this area, and explain in your paper why your approach is better in at least some way.  Have a look at recent work by for instance Amin Coja-Oghlan or Alan Frieze to get a feel for the state of the art and for useful pointers to important papers.


Why do theoreticians in CS use multiple-letter variables? This is a "dual" question of a popular post on math.se.

Some mathematical objects in computational complexity theory have multiple-letter names.   Complexity classes such as $\mathbf{BPP}$ have an established multiple-letter name.  So do some computational problems, although the naming convension seems to vary.

I am happy with names such as $\mathbf{BPP}$; however, when I write $\mathbf{PromiseBPP}$ on paper or blackboard over and over, I wish its name were more concise (in fact, some authors prefer to write it as $\mathbf{prBPP}$).
In a popular textbook in complexity, a polynomial that appears in the chapter on algebraic complexity of the book is named as $\mathtt{EXACTLY-ONCE}$, which I do not think is a suitable name to write by hand.

Considering the arguments in the original post on math.se, the pros of shorter names seem to apply more to TCS than those of longer names.  After all, what theoreticians do is to work on paper and blackboards, not to write large and complex software with editors that do auto-completion.

Some early literature takes different approach to names.  In Cinderella Book, computational problems have concise names such as $L_{\mathrm h}$ (which stands for the Hamiltonian path problem).

Thus the question is: why do theoreticians in CS use multiple-letter variables?  Or do we have to give long names to objects we are working on?

Because we're computer scientists as well as mathematicians, and from the computer science side of the world we've learned the same thing the software engineers have learned about why not to use single-letter names for things other than the most local of variables: longer and more semantically meaningful names are easier to remember and keep straight, easier for others to read and understand, and using them helps avoid certain common errors such as using $k$ to mean three different things in overlapping parts of a paper.

(Actually, I suspect that for the specific case you had in mind, names of complexity classes, this reason is historically inaccurate. But I still believe it's a good reason for using longer names.)


What is the complexity of this path problem? Instance: An undirected graph $G$ with two distinguished vertices $s\neq t$, and an integer $k\geq 2$.

Question: Does there exist an $s-t$ path in $G$, such that the path touches at most $k$ vertices? (A vertex is touched by the path if the vertex  is either on the path, or has a neighbor on the path.)

This problem was studied in:

Shiri Chechik, Matthew P. Johnson, Merav Parter, David Peleg: Secluded Connectivity Problems. ESA 2013: 301-312.

http://arxiv.org/pdf/1212.6176v1.pdf

They called it secluded path problem. It's indeed NP-hard, and the optimization version has no constant-factor approximation.

The motivation the authors provide is a setting where the information is sent over the path, and only the neighbors and the nodes in the path can see it. The goal is to minimize the exposure.


What is a term of the type $\bot\rightarrow A$? The sentence $\bot\rightarrow A$ is provable in intuitionistic logic for any type $A$. The proof is trivial:

\begin{align}
\bot&\vdash\bot \\
\hline
\bot&\vdash A \\
\hline
&\vdash\bot\rightarrow A
\end{align}
It means there has to be a lambda term with this type (the type has to be inhabited). What is it?

There are several ways of writing such a term, depending on how we write the proof terms for the elimination rule for $\bot$, which is
$$\frac{\quad\bot\quad}{A}$$
The corresponding rule in $\lambda$-calculus is
$$\frac{\Gamma \vdash e : \bot}{\Gamma \vdash \mathtt{absurd}_A(e) : A}.$$
(We call $\mathtt{absurd}_A$ an eliminator.)
Thus, the term of type $\bot \to A$ you seek is simply
$$\lambda x : \bot \,.\, \mathtt{absurd}_A(x).$$
Another way of writing the same thing is with a $\mathtt{match}$ statement. To see how this works, let us first consider a $\mathtt{match}$ statement for disjunctions. The elimination rule for $\lor$ is
$$\frac{A \lor B \qquad {\begin{matrix}A \\ \vdots \\ C\end{matrix}} \qquad {\begin{matrix}B \\ \vdots \\ C\end{matrix}}}{C}$$
The corresponding term constructor for $\lambda$-calculus can be written as
$$\frac{\Gamma \vdash e_1 : A+B \qquad \Gamma, x : A \vdash e_2 : C \qquad \Gamma, y : B \vdash e_3 : C}{\Gamma \vdash (\mathtt{match}\;e_1\;\mathtt{with}\;\mathtt{inl}(x) \to e_2 \mid \mathtt{inr}(y) \to e_3 \; \mathtt{end}) : C}$$
In general, the $\mathtt{match}$ statement which eliminates an $n$-fold sum $A_1 + A_2 + \cdots + A_n$ has $n$ cases.

The empty type $\bot$ is like a nullary sum, so it corresponds to a $\mathtt{match}$ statement with zero cases:
$$\frac{\Gamma \vdash e : \bot}{\Gamma \vdash (\mathtt{match}\;e\;\mathtt{with}\;\mathtt{end}) : C}$$
Indeed, this is how you can do it in Coq:

Definition ex_falso_quodlibet (A : Set) (x : Empty_set) : A :=
    match x with end.


Asymptotic density of ambiguous context-free grammars (CFGs) What is the ratio of ambiguous CFGs to all CFGs?

Since both sets are countably infinite the ratio is not well-defined.
But what about the asymptotic density:

$$\lim_{n \mapsto \infty}\frac
  {\# \text{ ambiguous CFG of size} < n}
  {\# \text{ CFG of size} < n}$$

where terminal and non-terminal symbols come from a fixed countable set.

The size of a grammar is any reasonable notion of size for grammars, e.g.

the total number of occurrences of variables and terminals in the production rules, or
the total number of occurrences of variable, or
the total number of production rules, or
the number of distinct variables.

(I am assuming the definition of size will not affect the answer.)

The question depends on the exact encoding. However, it seems that in many reasonable encodings, as the length tends to infinity, the number of production rules $S\to a$ (for an appropriate interpretation of the starting symbol $S$ and the terminal $a$) will be more than one with high probability; here I literally mean the same terminal $a$. If we consider this as ambiguity, then I expect "most" grammars to be ambiguous. We can also concoct similar situations such as the rules $S\to S$ and $S\to a$ each appearing at least once.

Assuming this general hypothesis, that every (fixed) conceivable rule should appear with high probability as the length tends to infinity, we find that "most" grammars generate $\Sigma^*$ in an ambiguous manner.

As an example, consider the following encoding for grammars over $\Sigma = \{0,1\}$. The grammar alphabet consists of the symbols $\{0,1,;,.\}$. Non-terminals are indexed by binary strings of length at least 2. Rules are separated by full stops. Each rule is a sequence of binary strings separated by semicolons. The first binary string is the non-terminal on the left-hand side, and the rest (if any) constitute the right-hand side; if the first binary string is not a non-terminal (i.e., it is $\epsilon$,0,1), then the starting non-terminal is assumed. The starting non-terminal is always 00.

Under this encoding, every string in $\{0,1,;,.\}^*$ describes some grammar. A random grammar will with high probability contain many copies of $.00;00.$ and $.00;0.$, and in particular will be ambiguous.


Shortest path hitting a given vertex I believe this problem to be NP-Complete, but I'm unable to find any references on possible reductions. Given a weighted graph (either undirected or directed, I cannot find results for either but am interested in both), and vertices s, t, u, find the shortest path from s to t which includes u. To clarify, the path should NOT repeat edges. Hence simply combining the shortest s-u and u-t paths is not valid.

It is NP-complete for directed graphs. Even deciding if there exist a path from $s$ to $t$ using vertex $u$ is NP-complete.

The 2-node disjoint path problem is NP-hard for directed graphs$^1$.

  Given a directed graph $G$ and vertex pairs $(s_1,t_1)$ and
  $(s_2,t_2)$, does there exist two node disjoint paths that goes from
  $s_1$ to $t_1$ and $s_2$ to $t_2$?

We can reduce this problem to your problem:
Split each vertex of $G$, so each vertex $v$ in $G$ become $v^-$ and $v^+$, and edge $uv$ become $u^+v^-$, also there are edges $v^-v^+$. Add one new vertex $u$, and edges $t_1^+u$ and $us_2^-$. Let this graph be $G'$.

There exist a path from $s_1^-$ to $t_2^+$ in $G'$ that uses $u$ if and only if there exist a node disjoint path between $(s_1,t_1)$ and $(s_2,t_2)$ in $G$.

The directed subgraph homeomorphism problem, Steven Fortune, John Hopcroft, James Wyllie.


What is the complexity class for quantum subroutines taking in arbitrary quantum states as inputs? The complexity class BQP corresponds to polynomial time quantum subroutines taking in classical inputs and spitting out a probabilistic classical output. Quantum advice modifies that to include copies of some predetermined quantum advice states but with classical inputs as usual. What is the complexity class for polynomial time quantum subroutines taking in arbitrary quantum states as inputs, with one copy only due to no cloning, and spitting out quantum states as an output?

I think that what you want to know about is quantum analogs of classes of function problems.  (Thanks to Peter Shor for pointing out this concise description in a comment.)

An abstract process which takes a quantum state of fixed size as the input and produces a quantum state of fixed size as the output is called a quantum channel.  In your situation, we do not want to fix the input size or the output size, and therefore we naturally consider a family of quantum channels as the quantum analog of functions from classical strings to classical strings.

It is clearly possible to define the class of families of quantum channels which can be implemented/approximated by families of efficient quantum circuits (with suitable notions of efficiency, uniformity, and approximation).  I do not know if this class has any standard name (but see Peter Shor’s comment for a suggestion).

In my speculation, classes of quantum channels are not often studied because one of the reason to consider complexity classes is in order to compare the powers of different computational models, and classes of quantum channels cannot be used to compare classical and quantum computational models.  However, it is perfectly fine to define and talk about such classes if anything interesting can be proved about them.


Regarding Pfaffian Methods in Counting and Combinatorics Recently, I was going over an introduction to Holographic Algorithms. I came across some combinatorial objects called Pfaffians. I do not really know much about those at the moment and came across some surprising uses they can be put to.

For instance, I came to know that they can be used to efficiently count the number of perfect matchings in planar graphs. Also, they can be used to count the number of possible tilings of a chessboard using 2*1 tiles. The tiling connection seemed very curious to me and I tried searching for more relevant materials on the web but in most places I merely found just one statement or two about the connection and nothing else.

I just meant to ask if someone could suggest some reference to relevant literature as that would be really great and I am looking forward to study some related materials.

(This is an interesting question for me because I'm also reading about the Pfaffian.)

I suggest the following references:

Chapter 8 of the awesome book Matching Theory by Lovasz and Plummer.
The paper Division-Free Algorithms for the Determinant and the Pfaﬃan: Algebraic and Combinatorial Approaches by Rote. This paper relates the Pfaffian with the combinatorial object called alternating closed walk sequence (aka. alternating clow sequence), which gives us a dynamic (division-free) algorithm for computing the Pfaffian.
The paper Nonintersecting paths, pfaﬃans, and plane partitions by Stembridge, which shows how to use the Pfaffian to enumerate configurations in combinatorics. The paper also gives combinatorial proofs of basic identities, e.g.,

  If $A$ is a skew-symmetric matrix, then $\mathsf{pf}(A)^2 = \mathsf{det}(A)$.


An explanation of Whirlpool C implementation - or the general algorithm Note: Question originally asked on StackOverflow - was directed here

Anyone got a tutorial on the designers concept implementation of Whirlpool in C, or the Whirlpool algorithm in general? I find the source code hard to understand, mostly because I do not know anything about the algorithm. I am not a cryptographer, nor am I a good mathematician, so their documentation kind of went over my head...

The implementation and other documentation can be found here.

Initially I was just searching for a free (public domain) implementation to use in a project, but I figured I better know something about it as well... Currently I do not even know how to use it.

In the following, I try to minimize the background knowledge needed to understand the answer. If you need more details, I suggest taking a look at section 12.2 of Cryptography and Network Security Principles and Practices, Fourth Edition. (Though it requires a fair knowledge of crypto.)

First take a look at Merkle–Damgård construction. Virtually all hash functions follow such construction. Informally, it applies a compression function iteratively to reduce the input size to get some fixed-length output. For instance, you can hash a whole DVD (~ 4.3 GB) and get a 128-bit code.

Let $M$ be the input to an MD-based hash function. The MD construction appends a pad and the length of $M$ to it, so as to prevent several attacks.

Whirlpool uses a compression function named $W$. $W$ is similar to a block cipher named Rijndael, which is now standardized under the name AES (Advanced Encryption Standard). Rijndael has 3 variants: 128-bit, 192-bit, and 256-bit. The inventors of Whirlpool decided that no Rijndael variant is secure enough to be used as the compression function for a hash. Thus, $W$ is designed so as it accepts 512-bit inputs, and produces 512-bit outputs. The key size of $W$ is 512 bits as well.

Whirlpool works as follows. Let $M$ be the input. $M$ is divided into 512-bit segments: $M=(M_0,M_1,\ldots,M_t)$. Let $h_0$ be some initial value (fixed by Whirlpool standard).

For $i=1,2,\ldots,t$, apply $W$ iteratively as follows:

$h_i = W(h_{i-1},m_i) \oplus h_{i-1} \oplus m_i$

where the first input to $W$ is a block-to-be-encrypted, and its second input is the encryption key. $\oplus$ denotes the XOR operation.

$h_t$ is considered as the output of the Whirlpool hash function.

The whole complexity lies in designing $W$. As pointed out before, it is similar to Rijndael, so you can understand it if you get familiar with Rijndael, on which I have designed a set of slides. The slides are self-contained and do not assume any math background beyond high school.


Complexity of finding the most likely edge Consider a connected, unweighted, undirected graph $G$. Let $m$ be the number of edges and $n$ be the number of nodes.
Now consider the following random process. First sample a uniformly random spanning tree of $G$ and then pick an edge from this spanning tree uniformly at random. Our process returns the edge.
There is a probability distribution on edges implied by this process.  https://math.stackexchange.com/a/3781031/678546 points out that if $T$ is a uniform sampled spanning tree then
$$P(e \in T) = \mathscr{R}(e_- \leftrightarrow e_+)$$
where $e = \{e_-, e_+\}$ and $\mathscr{R}(a \leftrightarrow b)$ is the effective resistance between $a$ and $b$ when each edge is given resistance $1$.
Marcus M goes on to give a complexity of $O(mn^3)$ for computing the probabilities for every edge.  This is much too slow to run in practice for all but the smallest graphs.
If I only want to find an edge with the maximal probability, is there a faster algorithm? How about if I am happy with an approximation?

If you are happy with an approximation, then you can use approximate Laplacian solving, which takes time $\widetilde{O}(m)$. This is done explicitly in this paper by Spielman and Srivastava, Theorem 2.
My guess is that this is optimal, even if you just want to determine the edge with maximal effective resistance.


Are there non-constructive proofs of existence of "small" Turing machines / NFAs? After reading a related question, about non-constructive existence proofs of algorithms, I was wondering if there are methods of showing existence of "small" (say, state-wise) computation machines without actually building it.
Formally:
suppose we are given some language $L\subseteq \Sigma^*$ and fix some computation model (NFAs / turing machine/ etc.).
Are there any non-constructive existence results showing a $n$-state machine for $L$ exists, but without the ability of finding (in $poly(n,|\Sigma|)$ time) it?
For example, is there any regular language $L$ for which we can show $nsc(L)\leq n$ but we don't know how to build a $n$-state automaton for?
($nsc(L)$ is the non-deterministic state complexity of $L$, i.e. the number of states in the minimal NFA that accepts $L$).

EDIT: after some discussion with Marzio (thanks !) I think I can better formulate the question as follows:

Is there a language $L$ and a computation model for which the following holds:

We know how to build a machine that compute $L$ that has $m$ states.

We have a proof that $n$-states machine for $L$  exists (where $n << m$), but either we can't find it at all or it'd take exponential time to compute it.

Only an extended comment with a trivial example; you can pick the one-element language:

$$L_k = \{ M \mid  \sigma(M) = \Sigma(k) \}$$

i.e. $L_k$ contains the first (in lexicographical order) busy beaver Turing machine of size $k$ (the Turing machine of size $k$ that attains the largest number of 1s on its tape after halting).

For every $k$ the language $L_k$ is regular ... but we have no idea on how to  build the small DFA that recognizes it (though it has only $\leq 2*k(\log k+2)$ states) :-)


"Matrix complexity" - is it possible? While browsing old CStheory.se posts, I ran across a fascinating blog post on the matrix mortality problem.  Unless I've misinterpreted the problem, it states that given a finite collection of 3 x 3 matrices with integer entries for each matrix value, one must decide if there exists a finite product of those matrices that equals a matrix comprised of all zeros.

Amazingly, this problem is undecidable, due to a reduction from the Post correspondence problem.  My question is:  Given the undecidability of the problem, and its link to a problem that is linked to Turing machines, can you show that there exists a way to characterize (for example) all r.e. languages, the class P, and the class NP using matrices?

I've done a little work on this myself, but lack the training to be sure if my belief is correct.  This problem would, I think, require a little bit of work on the reader's part to solve.

I don't know how to use LaTeX to write matrices on SE, but here's my first attempt to characterize NP:

  Given a finite set $S$ of 3 x 3 matrices with integer entries and an integer $k$ as an NP "query," let an additional matrix $M$ be taken as a "structure."  The "query" accepts the "structure" if there exists a product of $|M|^k + k$ matrices from $S$ that equals a matrix that consists of only zeros.

This attempt is not complete and does include any proof, as you see, but I wanted to give my first thoughts on the problem to see if a more sophisticated attempt could be made to formalize a notion of matrix complexity.  This is interesting because, like Fagin's characterization of NP using descriptive complexity, it could be used to characterize NP in a machine-independent fashion.

This isn't a characterization of NP: it's just an NP-complete problem (well, I assume it's NP-complete, anyway). OK, if so, you could characterize NP as the class of problems reducible to your matrix problem but how are you going to define reductions? Using reductions from some existing model of computation (e.g., Turing machines) would be self-defeating. What advantages would such a characterization have over, say, considering NP to be the class of problems reducible to, say, independent set?

Also, the "structure" matrix $M$ plays no role in the problem except via its determinant so there's no reason for it to be a matrix, rather than just a natural number.


Formal Methods Applied to Role-Based Security (RBAC) I wonder if someone could direct me to a basic introduction to formal methods applied to role-based security.  I'm particularly interested in the question of formal verification and the kind of mathematical abstractions that would appropriately address confidentiality and / or conflicts of interest that arise from overlapping roles in a SSO (single sign-on) system.  Thanks much in advance.

PS I'm asking this question in parallel w/ conducting my own literature search.

My knowledge is a bit stale, as I haven't actively researched this field in the last couple of years. None of these is probably the state of the art, but a good place to start looking backwards (i.e., chase references) and forwards (i.e., see who cites it).

If you're looking into information flow (making sure classified information doesn't leak to untrusted roles), a reasonable place to start is Martin Abadi et al's Dependency Core Calculus. I think it's reasonable enough that anyone who does formal methods in the area would refer to it (directly, or once removed).

If you're looking into access control/authorisation (role A says role B controls the data, role B says you can access the data, etc.), Abadi recently published a tutorial book chapter on the subject, so might be a good place to start.

If you're looking into authentication (whether the agent saying he is A is indeed A), I defer to someone else. I'll try to have a look later.


Non-rooted MST of directed graph I've found a problem that boils down to this: I need to find the non-rooted MST of a directed weighted graph. In other words, I need to find the minimal set of edges such that from any one node in the graph you can get to all others.

This is similar to the rooted MST digraph problem, which the chu-liu algorithm solves quite nicely. My intuition is to calculate the rooted MST for all nodes using chu-liu and then merge each, removing redundancies along the way. However, I don't believe that that would be optimal.

Has anybody been working on this? Can you point me towards some papers that I should read?

Thanks.

If I understand your question correctly you aren't looking for a tree, or an arborescence, but rather a minimum weight set of arcs that suffice to keep the graph strongly connected.

Your problem is NP-complete by reduction from Hamiltonian cycle problem. Given an input undirected graph that you wish to find the Hamiltonian cycle of create a directed graph by replacing each edge with a pair of oppositely directed arcs. Give all arcs weight 1. This directed graph has a set of arcs that leave the graph strongly connected with weight at most the number of vertices if and only if it has a Hamiltonian cycle.

You can get a two-approximation by picking an arbitrary root, finding the minimum weight spanning tree with arcs pointing towards the root, finding the minimum weight spanning tree with arcs pointing away from the root, and then unioning the two sets of arcs.

I don't recognize this problem off the top of my head but have you tried looking in the various NP-complete problem directories for it?


Complexity of marriage matching problem? Suppose you have $n$ males and $n$ females. Each person has $m$ attributes. Each person indicates a set of attributes that a possible candidate should have. A matching is a set of pairs. Each pair binds one male to one female. The satisfaction of a matching is number of attributes satisfied for the least lucky person.

  Is finding a matching with maximum satisfaction efficiently solvable or is it $NP$-hard?

I may have misunderstood the question, because my answer conflicts with Serge's. To my understanding, you're asking about the Linear Bottleneck Assignment Problem. This is known to be solved in O(n^2.5).

The most complete source of information is [1], although I really don't like the book's style. There's also a website: http://www.assignmentproblems.com/linearBNAP.htm

EDIT: To clarify, the we want an assignment such that the edge with maximal cost is minimized. The cost will be the maximal number of unassigned attributes for either the man or the woman that are matched.

EDIT2: I can only offer references from the book I cited. Three of them are:

G. Carpaneto and P. Toth Algorithm for the solution of the bottleneck assignment problem. Computing, 27:179-187m 1981
U. Derigs. Alternate strategies for solving bottleneck assignment problems - analysis and computational results. Computing, 33:95-106, 1984
U. Derigs and U. Zimmermann. An augmenting path method for solving linear bottleneck assignment problems. Computing, 19:285-295, 1978

You should try to get hold of the book, since lists some of the available algorithms.

[1] Assignment Problems by Rainer Burkard, Mauro Dell'Amico, Silvano Martello


About a pre-processing step for primal–dual weighted set cover problem I was reading the paper titled "Primal-dual RNC approximation algorithms.." by Rajagopalan and Vazirani. I have a problem of understanding the Lemma 4.1.1.
They present a dual fitting based algorithm for weighted set cover. First let me set up the required concept to clarify where I am having trouble. Suppose we have $n$ elements($U$) and $m$ sets($S$). Each set has a positive weight. Let $E_v$ holds the sets in which the element $v$ is present. Let $\beta =$max$_{v \in U}$ min$_{s \in E_v}$ weight(s). Let also $IP^*$ is the weight of an optimal set cover. It is easy to see, $IP^*\geq \beta$. Now assume we have an approximation algorithm for weighted set cover. What the paper is saying in the lemma is that you can do a pre-processing before starting the approximation algorithm as follows. You can scan through the sets and add any sets that have weight $\leq \beta/n$. Since there are $n$ elements the additional cost is at most $\beta$. Then they claim that, "Since $\beta$ is a lower bound on $IP^*$, this cost is subsumed in the approximation. " And this is the statement I did not understand.

Call a set cheap if it has cost at most $\beta/n$.

Let $S_0$ be the collection of sets obtained by "scanning through the sets and adding any cheap sets". This wording is not quite right.  In this step one should only add cheap sets whose elements are not all covered by previously added cheap sets -- this ensures that the size of $S_0$ is at most $n$.  So, the total cost of sets in $S_0$ is at most $n\beta/n = \beta$, and these sets cover every element that is in any cheap set.

The intuition is that, if we're willing to give up a factor of two in the performance guarantee, we can go ahead and add the cheap sets, in $S_0$, up front, because these sets cost at most $\beta$, which is a lower bound on the optimal cost.  Once we've done this, all that remains is to cover the elements that are not covered by any cheap set.  If we can do this using sets that have cost $O(\log n)$ times the original optimal, the total cost (after adding in the cheap sets in $S_0$) will still be $O(\log n)$ times the original optimal.

In more detail: after committing to using the cheap sets in $S_0$, the remaining problem is to compute some collection $S'$ of sets that covers the remaining elements --- those that aren't in any cheap set.  And $S'$ should have cost $O(\log n)\cdot IP^*$.

This is the problem that the paper then shows how to solve.  To complete the details, suppose that we have some such set $S'$.  Obtain the complete solution by taking $S = S_0\cup S'$.

This $S$ then covers all the elements in $U$ (as $S_0$ covers the elements that are in any cheap set, while $S'$ covers the rest), and the cost of $S$ (the  cost of $S_0$ plus the cost of $S'$) is at most $\beta + O(\log n)\cdot IP^* = O(\log n)\cdot IP^*$.  So $S$ is an $O(\log n)$-approximate solution to the original problem.

A slightly subtle point is that, to compute $S'$, it is enough to compute take $S'$ to be any $O(\log n)$-approximate solution to the problem with universe restricted to the elements not covered by any cheap set.  This is because the optimal cost for the restricted problem is at most the optimal cost for the original problem.


Proof of an Ising model representation of graph isomorphism problem I am going to through Ising formulations of many NP problems by Andrew Lucas. In section $9$ on page 22, the author introduced an exact Ising formulation of the graph isomorphism problem. Given two gaphs, $G_1$ and $G_2$, the Ising Hamiltonian, $H$ is,

$$
H = A \sum_v \left(1 - \sum_i x_{v,i}\right)^2 + A \sum_i \left(1 - \sum_v x_{v,i}\right)^2 \\
+ B\sum_{ij\not\in E_1}\sum_{uv \in E_2} x_{u,i} x_{v,j} + B \sum_{ij \in E_1}\sum_{uv \not\in E_2} x_{u,i} x_{v,j}
$$

Here, $|G_1|=|G_2|$ and the binary variable $x_{v,i}$ is $1$ when if vertex $v$ in $G_2$ is mapped to vertex $i$ of $G_1$. For an isomorphic pair, $H = 0$.

My questions:

Is there any rigorous proof that this model is correct?
I understand that the classical computational complexity of the graph isomorphism problem is not known but it is conjectured to be NP-intermediate. On the other hand the classical computational complexity of the Ising model is well understood. So, if the graph isomorphism problem can be reduced to an Ising model in polynomial time, shouldn't be it's complexity same as the Ising model problem?
When I code it up using Mathematica (assuming $A = B = 1$) for the following two isomorphic graph pairs, I am getting false positives.

The graphs are:

 and .

For this pair of graphs, I get the following configurations which are correct isomorphisms and for them $H=0$. They are:

$x_{1,1}, x_{2,2}, x_{4,3}, x_{3,4}$
$x_{4,1}, x_{3,2}, x_{1,3}, x_{2,4}$
$x_{1,1}, x_{3,2}, x_{4,3}, x_{2,4}$
$x_{4,1}, x_{2,2}, x_{1,3}, x_{3,4}$

But when I evaluate the Ising formulation with all possible inputs using Mathematica, I get five more false positives along with these four. They are:

$x_{1,4}, x_{2,3}, x_{3,2}, x_{4,1}$
$x_{1,4}, x_{2,2}, x_{3,1}, x_{4,3}$
$x_{1,3}, x_{2,4}, x_{3,1}, x_{4,2}$
$x_{1,1}, x_{2,4}, x_{3,3}, x_{4,2}$
$x_{1,4}, x_{2,3}, x_{3,1}, x_{4,2}$

What am I missing?

The counterexamples you give are not correct. I suspect your bug is this: when doing the sums over edges in (or not in) $E_1$ and $E_2$, you need to consider both orderings of each pair.

Consider your first false positive. One of the mismatched edges corresponds to (the lack of) $(2,4)$ in $G_1$, which maps to $(3,1)$ in $G_2$ (which is present). This makes the third term in the sum non-zero: consider $(i,j)$=$(2,4)$ and $(u,v)$=$(3,1)$; $x_{3,2}x_{1,4}$ is non-zero. If you only consider the edge pairs $(u,v)$ where $u<v$, you miss counting these non-zero terms and get the incorrect zero result.


Can a flow be decomposed in a given number of paths? If we have a digraph $G=(V,A)$ with capacity $u_a\in \mathbb{N}$ for $a\in A$ and a source $s$ and sink $t$. I know the following theorem:

  Let $f$ be a flow in the network above. Then there is a collection of feasible flows $f_1,\dots,f_k$ and $s$-$t$ paths $p_1,\dots,p_k$ such that

  $k\le |A|$
  the flow value of $f$ is equal the sum of the flow values of the $f_i$'s
  the flow $f_i$ sends only positive flow on the edges of $p_i$

I am wondering if for a given flow $f$ and integer $n$ under additional assumption there is such a decomposition in exactly $n$ such paths?

Motivation: In our lecture notes there use two iteration of the Ford–Fulkerson algorithm and claim: the resulting flow can be decomposed in 3 paths and a circulation. Clearly, from the algorithm I get two path, but how can I decompose the flow in three path and a circulation? The only decomposition theorem we had, is the one I stated above. I guess it uses some other approach.
However the question of decomposing in exactly $n$ paths is also of particular interest for me. Thanks in advance.

math

This is the proof given here, to show that the flow obtained after two iterations of Ford-Fulkerson algorithm can be decomposed into at most $3$ paths and a circulation. It is assumed that at each iteration, the algorithm picks the path that allows maximum flow.

Let the path obtained in first iteration be $P_1$ with flow $f_1$. And the path in the residual graph w.r.t this flow, picked by the algorithm in second iteration be $P_2$ with flow $f_2$. Clearly $f_1 \geq f_2$. Now consider the path $P_1$ with flow $f_1-f_2$. Removing this flow from the total flow, the remaining flow can be described as follows (for each edge $e$).

If $e \notin P_1$ and $e \notin P_2$ then $f(e)=0$.
If $e \in P_1$ and $e \notin P_2$ then $f(e)=f_2$.
If $e \notin P_1$ and $e \in P_2$ then $f(e)=f_2$.
If $e \in P_1$, $e \in P_2$ and $e$ is a forward edge in $P_1$, then $f(e)=2f_2$.
If $e \in P_1$, $e \in P_2$ and $e$ is a backward edge in $P_1$, then $f(e)=0$.

So the remaining flow is now $f_2$-integral, with a total flow of $2f_2$ from $s$ to $t$. We can show in general that if a flow is $r$-integral with a total flow of $kr$ from $s$ to $t$, then this flow can be decomposed into at most $k$ $s$-$t$ paths and a circulation. We can just start from $s$ and move along any edge carrying some flow and reach $t$. This gives an $s$-$t$ path with flow $r$ (or some multiple of $r$). Remove this flow and repeat this process again (walk from $s$ to $t$ along flow carrying edges). Finally, when there is no net flow let from $s$ to $t$, the remaining flow is a circulation. That this process ends in $k$ steps can be shown formally using induction.


Explaining input-size of integral arguments to undergraduate CS students When I teach undergraduate algorithms, the students have no problem accepting that two n-bit numbers can be added in $O(n)$ time, or that modular exponentiation takes $O(n^3)$ time.

But when we get to knapsack and solve it via DP, they are confused.  For example, the conventional approach to knapsack for $N$ items and a $W$-capacity bag  is the straightforward $O(NW)$ DP method.  But I then point out that $W=2^n$ and therefore DP is exponential time.  This invariably causes objections, confusion, and lots of doubt.  I have yet to find a way of explaining this that makes it clear.  Can anyone help?

Oh, and they haven't seen Turing machines, so that's off-limits.

Ask them to them implement the algorithm and then run it on a few dozen 12-digit numbers.


How to choose good diagonals when partitioning an orthogonal polygon into rectangles? Following this answer on MathOverflow and section 3 of the linked paper by David Eppstein on how to split an orthogonal polygon into rectangles I came to a point where I just fail to understand how to proceed.

As you can see on my example image I have added all diagonals connecting two concave vertices each. The green ones do not have any intersections with other diagonals and thus can be applied immediately for sectioning. The other diagonals lead to the following intersection graph:

The graph already shows a maximal matching as found by the Hopcroft-Carp algorithm in blue. (If you are interested in an easy step-by-step tutorial for applying it manually, I can recommend this YouTube video.)

For the next step (choosing the good diagonals) Eppstein writes:

  [...] ﬁnding the maximum
  number of disjoint good diagonals translates, in graph-theoretic terms, into ﬁnding a
  maximum independent set in a bipartite graph. By König’s theorem [49], in any n-
  vertex bipartite graph the maximum independent set has size n − M, where M is the
  cardinality of a maximum matching; an independent set of this size may be found from
  a maximum matching by partitioning the vertices according to the lengths of the shortest alternating paths from an unmatched vertex to the given vertex, and including the
  vertices at even levels of this partition.

If I understood it correcty, I do not know how to determine this length for each node in my graph, as there are nodes unable to reach an unmatched node via an alternating path. Here is what I would assume is meant:

Node | Alternating Path Length to unmatched Node
-----+------------------------------------------
  1  | ?
  2  | ?
  3  | ?
  4  | ?
  5  | 2 (5-e-7)
  6  | 1 (6-g)
  7  | 0 (7)
  a  | ?
  b  | ?
  c  | ?
  d  | ?
  e  | 1 (e-7)
  f  | 2 (f-6-g)
  g  | 0 (g)

According to this I would definitely choose 5, 7, f and g as good diagonals, wouldn't I? But there will be remaining intersections not resolvable by this information.

I asked this question in very short form and without an example on the linked MathOverflow page in a comment, but the question there already left primary school (*) and I'm not sure if I will get any reaction there.

(*) In Germany primary school has four grades and usually one switches to a secondary school at the age of 10.

Starting with 5,7,$f$ and $g$ is correct. In order to complete the maximum independent you can proceed as follows. First, delete the vertices that are reachable from an unmatched vertex via an alternating path (in your example 5,6,7,$e$,$f$,$g$). This leaves a balanced bipartite graph (that is, it has the same number of vertices on each side), and you can simply add one of the two sides to your independent set. In your example, you get the maximum independent set $\{1,2,3,4,5,7,f,g\}$ or $\{a,b,c,d,5,7,f,g\}$.


Is algebraic dependency decidable? A set of numbers $S=\{x_1,...,x_n\}$ is said to be algebraically dependent if there exists a (multivariate) polynomial $p$ with coefficients in $\mathbb Q$ whose roots contain $x_1,...,x_n$ (or a subset thereof).

  Given numbers $S=\{x_1,...,x_n\}$, is it decidable whether they are algebraically dependent?

Now, there is obviously an encoding issue here, since the numbers need to be transcendental, so describing them is problematic. Any solution would do, but specifically, I am interested in the case where all the numbers are of the form $e^{a_i}$, where the $a_i$'s are linearly independent over $\mathbb Q$.

The motivation for this question is understanding whether a (positive) solution to Schanuel's conjecture would automatically lead to a constructive solution.

UPDATE (based on the comments): the encoding of the numbers is an issue. I'll accept any answer which suggests either a reasonable encoding for a subset of the reals for which the problem is non-trivial, or a solution that uses a computational model that allows real numbers.

A model of computation allowing real numbers is the Real-RAM model. In this model, it is impossible to even decide if a number is rational. Indeed, the time-T halting sets are semialgebraic. If any one of them has a non-empty interior, then the time-T yes-set and time-T no-sets are semialgebraic subsets with no-empty interior, which is a contradiction. If none of the time-T halting sets is semialgebraic, then their union cannot be $\mathbb{R}$.

Answer to the previous version of the question:

If $a_1,\dotsc,a_k$ are algebraic numbers that are linearly independent over $\mathbb{Q}$, then $e^{a_1},\dotsc,e^{a_k}$ are algebraically independent over $\mathbb{Q}$. This is the Lindemann–Weierstrass theorem. So, if $a$'s are algebraic (as in the current version of the question), then the answer to your question is "yes".


Are there any results on the following "generalized matching" problems? Given a graph $G = (V, E)$, one can view a matching $M$ on the graph as a partition of $V$ into vertex sets $S_{i, j}$ for $j \in \{1, 2\}$, where each $S_{i, j}$ induces a subgraph in $G$ isomorphic to $K_{j}$. That is, the edges in $M$ correspond to subgraphs isomorphic to $K_{2}$ and the leftover (unmatched) vertices correspond to subgraphs isomorphic to $K_{1}$. A matching algorithm can then be viewed as partitioning the vertex set into subsets which induce complete graphs, where we try to include as many $K_{2}$s as possible before resorting to $K_{1}$.

I'm interested in a generalization of this problem where $j$ is as large as possible (or perhaps some fixed j > 2, if there are nice results). In particular, I'd like an algorithm which first tries to find subsets of $V$ which induce subgraphs isomorphic to $K_{l}$, for $l$ as large as possible, and then $K_{l-1}$, etc.

Is there any work on problems like this?

In http://www.sciencedirect.com/science/article/pii/S0012365X13003543 , we use exactly this process of picking the largest possible clique, then the next largest available clique, and so on (without repeating any vertices). When applied to a cograph $G$, this algorithm forms a cluster graph subgraph of $G$ with the max number of edges possible. The paper contains some combinatorial results on sizes of cliques obtained during such a process.

This paper http://publicaciones.dc.uba.ar/Publications/2015/BDNV15/BDNV15.pdf generalizes our result to a class of graphs beyond cographs.

I'm not sure which way you want to generalize matchings ... towards triangle covers or clique covers, but either way, it seems you will be moving from P-territory into NP-complete land. Unless you restrict your initial graph to certain structural classes.


Different forms of genetic algorithim I wrote a code that implements a simple genetic algorithm to maximize:

f(x) = 15x - x^2

The function has its maximum at 7.5, so the code output should be 7 or 8 since the population are integers. When I run the code 10 times I get 7 or 8 around three times out of 10.I chose mating probability of 0.7 and mutation probability of 0.001. What modification should I make to further improve the algorithm and what are different types of genetic algorithms?

Here is the code:

from random import *
import numpy as np

#fitness function
def fit(x):
    return 15*x -x**2
#covert binary list to decimal number
def to_dec(x):
    return int("".join(str(e) for e in x), 2)

#picks pairs from the original population
def gen_pairs(populationl, prob):
    pairsl = []
    test = [0, 1, 2, 3, 4, 5]
    for i in range(3):
        pair = []
        for j in range(2):
            temp = np.random.choice(test, p=prob)
            pair.append(populationl[temp].copy())
        pairsl.append(pair)

    return pairsl

#mating function
def cross_over(prs, mp):
    new = []
    for pr in prs:
        if mp[prs.index(pr)] == 1:
            index = np.random.choice([1,2,3], p=[1/3, 1/3, 1/3])
            pr[0][:index], pr[1][:index] = pr[1][:index], pr[0][:index]

    for pr in prs:
        new.append(pr[0])
        new.append(pr[1])

    return new

#mutation
def mutation(x):
    for chromosome in x:
        for gene in chromosome:
            mutation_prob = np.random.choice([0, 1], p=[0.999, .001])
            if mutation_prob == 1:
                #m_index = np.random.choice([0,1,2,3])
                if gene == 0:
                    gene = 1
                else:
                    gene = 0
    #generate initial population
    randlist = lambda n:[randint(0,1) for b in range(1, n+1)]
for j in range(10):
    population = [randlist(4) for i in range(6)]
    for _ in range(20):
        fittness = [fit(to_dec(y)) for y in population]

        s = sum(fittness)
        prob = [e/s for e in fittness]
        pairsg = gen_pairs(population.copy(), prob)

        mating_prob = []
        for i in pairsg:
            mating_prob.append(np.random.choice([0,1], p=[0.4,0.6]))

        new_population = cross_over(pairsg, mating_prob)
        mutated = mutation(new_population)
        decimal_p = [to_dec(i)for i in population]
        decimal_new = [to_dec(i)for i in new_population]
        # print(decimal_p)
        # print(decimal_new)
        population = new_population
    print(decimal_new)

Without paying much attention to your code, your crossover rate is maybe a touch low, your mutation rate is orders of magnitude too low, your population is tiny, and you're only running 20 generations. You're just not doing enough search for anything to work. If your initial population had a 6 or 7, you find it. Otherwise, you get a handful of crossovers to hope to get lucky and then you're done.

You have 4 bits * 6 individuals = 24 bits per generation * 20 generations. At best, you have 480 bits of information here, and your mutation operator expects one flip per thousand bits.

You also select parents using fitness proportionate selection, which has pretty severe issues with selection pressure, made even worse with such a small population. Look at it this way, suppose you generate the following six individuals for your initial population (6, 0, 15, 13, 11, 2). f(6) is quite a bit better than every other choice -- the selection probabilities are roughly (0.36, 0, 0, 0.17, 0.29, 0.17). So you'd expect the parent pool to look something like (6, 13, 6, 11, 11, 2). Obviously the exact choices are random, but that fits the distribution. Now if you pair a 6 with a 6 or an 11 with an 11, you're guaranteed to produce another copy of those, as crossover of identical parents can't flip any bit. And you have no mutation at all (practically speaking). So your population just rapidly converges to the best thing you found in your initial random population.

Crossover does have some chance of producing better individuals, which is why you see the optimum 30% of the time instead of ~10% that you'd expect just by sampling for the initial population. But that's about it. You just don't have enough search happening to reliably do any better.

Again, there may also be bugs -- I didn't look carefully.


What is the advantage of a transformation matrix in perspective projection? I was messing around with perspective projection. And it got me wondering whether using a perspective transformation matrix is the most efficient way. Because I also came up with another method which seems to need about the same amount of calculations:

Given:

The position of the "camera" $\vec{O}$.
The normalized vector $\vec{n}$ in the direction in which the camera
is looking (normal of the plane on which the points will be
projected).
Vectors $\vec{X}$ and $\vec{Y}$ which determine the orientation of
the projection. Both should lie in the projection plane and together with $\vec{n}$        should span an orthonormal basis in the $\mathbb{R}^3$.
The shortest distance from the camera to projection plane $h$
The point $\vec{P}$ which needs to be projected.

$\vec{\Delta}=\vec{P}-\vec{O}$
with $\vec{\Delta}$ the relative coordinates of $\vec{P}$ with respect to $\vec{O}$.

$\vec{\alpha}=h\left(\frac{\vec{\Delta}}{\vec{\Delta}\cdot\vec{n}}-\vec{n}\right)$

$x=\vec{\alpha}\cdot\vec{X}$

$y=\vec{\alpha}\cdot\vec{Y}$

Or do methods, which use transformation matrices, use eigen-value/vectors to reduce the amount of calculations?

One advantage of transformation matrices over direct calculations is that you can compose transformations simply by multiplying matrices. E.g. you might have different transformations for basic motions such as rolling, panning, or dollying the camera and doing similar things to the objects in the scene. Keeping track of all this in a direct calculation becomes an unmaintainable mess.


Fastest known algorithm for finding simple paths through given set of vertices For an undirected graph $G$ and a given set $S$ of vertices, what is the asymptotically fastest known algorithm for finding a simple path containing
all elements of $S$. What if we require the path to be as short as possible ?


Adjective for: algorithm that outputs its input if it is one of its outputs? Is there a well established adjective or name for an algorithm such that, given as input any of its own output, always outputs it unchanged? In other words, an algorithm such that it implements a function $f$ with the property $f\circ f=f$. What would be a reference?

My application is a cryptographic security reduction. An example would be an algorithm which on input $X\in\{0,1\}^*$, outputs $1^{|X|}$.

Besides identity, an algorithm implementing $X\mapsto|X|$ in one of $\Bbb Z$, $\Bbb Q$, $\Bbb R$, $\Bbb C$ also comes to mind.

Stationary algorithm or circular algorithm would do, but neither googles. In my experience that means quickly it will google here, bringing circularity to a new level!

In mathematics we would say $f$ is an idempotent function. It's a widely known term and I suppose most TCS people should also recognize it.


Is it possible to create an algorithm-aware optimizer? I've recently implemented a physics system where each object has to interact with eachother. It consisted of, pretty much, the following algorithm:

for obj_a in world
    for obj_b in world
        obj_a.collide(obj_b)

This is O(N^2) and obviously scales very badly. I know, though, that distant objects don't collide, so I partitioned the space. The algorithm became:

for obj_a in world
    for obj_b in space_partition_of(obj_a)
        obj_a.collide(obj_b)

Considering the second loop iterates only over objects close to A, it brings the complexity down to almost O(N) and is ridiculously faster.

That made me think: it does not matter which language I implemented the first algorithm, it would always be sluggish. There is not a single compiler in the world that would fix my mistake, as much as obvious it seems for a human programmer. My question is: what is there stopping us to create a compiler that replaces the algorithms and data-structures used for the optimal ones? Is it impossible in a turing complete language? Would it be possible in a non-turing-complete language such as Idris?

Actually, optimizing compilers do that kind of things. I am for
example thinking of the work of Robert Paige at NYU. The problem is of
course to identify situations where a given type of transformation may be useful.
That require identifying computational structures, and knowing some of
the algebraic properties of the data being manipulated.

A classical example, very simple, is the strength-reduction in
loops, where you replace a product by a sum. It usually does not change
much the complexity (see more below), but can effectively speed up your algorithm, at
the cost of one extra variable. This is a special case of finite
differencing techniques.

I think you should find example in the litterature on high-level
optimization, which is quite different from peep-hole optimization in
the code generation process. See the two wikipedia article for various types of code optimization.

Regarding the identification of such situations, they can sometimes be
found by formal analysis of program. It can also help to make them
more apparent by using very high-level abstractions in the programming
process.

Many such transformations improve the program without changing the
complexity. But it much depends on what complexity you are considering
and what is a unit operation.

For example if you consider arithmetics of unbounded integers,
addition has linear cost, while multiplication has a higher cost
(quadratic in the naive case). Using reduction in strength in loops
will reduce complexity.

I unfortunately do not remember more spectacular cases.

There is also some significant litterature on program transformations, with a variety of techniques that started in the 1970ies. Some transformations may not bring much by themselves, but may enable other transformations. Pattern matching in equational algebras is one way of identifying possible tranformations that has been considered. This may be one reason why very high level abstractions can help the process.


"Natural" decidable problems known not to be in NP. Every time I teach NP-Completeness, students ask "are there any problems that are known to not belong to NP?"

How would you answer?  I usually give them an undecidable problem as an example, but this often doesn't turn out well: (a) if I give them the Halting Problem they think it's some dumb corner case, and (b) if I give them Diophantine Equations they don't see why it's not in NP (you can check solutions in poly-time... just plug them in!  I have a hard time disabusing them of this approach.)

I'd like to give them something like QBF as an example, but there is no proven separation.

Suggestions?

One possibility is a problem that is EXPSPACE-complete. NP is trivially in PSPACE, which is strictly contained in EXPSPACE. One problem that is EXPSPACE-complete is deciding whether a regular expression that allows exponentiation is all of $\Sigma^*$.


Powerful algorithms that are just too hard to implement-- how to be sure they are right? I am referring to the question here: powerful algorithms too complex to implement.

If an algorithm is powerful, but too complex to implement, how can you be sure that the algorithm is correct? Without implementation you won't be able to test the algorithm in a real world scenario, and such a complex algorithm can contain bugs, which may invalidate the algorithm.

This is what I do not understand; if you have the techniques to prove the correctness of an algorithm, then you would have the algorithm to implement it already, isn't it? Or else how can we be sure that the proving technique is correct?

I'm sorry if I sound elementary!

Update from Kaveh ( reproduced here because the argument is better!):

  If you can formally prove the
  correctness of an algorithm in a
  formal system like Coq then you can
  also extract the algorithm (because
  essentially you have implemented the
  algorithm), but the key fact is that
  for most algorithms we don't give
  formal proofs of correctness for the
  algorithm, we use informal proofs of
  correctness. The proofs can be false,
  which does happen from time to time,
  and even a formal proof of correctness
  will not make us absolutely sure that
  the algorithm is correct.

Several years ago, there has been a (rather harsh) debate on a topic similar to this. It all started when several complex proofs turned out to be incorrect, and some researchers started to raise doubts on the very nature of proofs (well, I should have said "provable cryptography," but for the sake of generality, I didn't). Both sides of the controversy accused the other to misunderstand the concepts. Here's a link for more info.

Proofs are our (mathematical) tools to prove theorems/algorithms are correct, but when they became too complex, we may slip and prove wrong things to be right. The recent 100-or-so-page proof on P≠NP is an excellent example. However, this does not rule out the very nature of proofs: Nothing's wrong with them.

One last point: I think studying the philosophy of science will give us more insight on this. (Under the given link, see the bullet "How do we know whether a mathematical proof is correct?")


Canonical forms for relational algebra expressions I'm looking for whatever work may exist, or thoughts people have, on the question of whether/to what extent there exist(s) one or more canonical form(s) to which relational algebra expressions may be reduced.

I'm investigating the feasability of building a relational query optimizer which allows hand-writing of query plans but proves (or assists the user in proving) that the plan satisfies the query.

If there isn't a (usefully non-enormous) canonical form, then I wouldn't know the first thing about how to attack the problem. I suppose read up on Coq or Isabelle, work on translating my equivalence question into theorem prover's language, and work on providing a less-grad-school-required interface that exposes (relevant parts of) the theorem prover's output.

If there is a canonical form that doesn't tend to blow up to enormous sizes, then of course its a much easier problem.

There are canonical forms, but there are not unique canonical forms. Roughly, the idea is to use observe that sets form a monad and use the equational theory of Moggi's monadic metalanguage as a well-behaved IR for  optimizing queries. See Torsten Grust's PhD thesis, Comprehending Queries.

More recently, the Ferry Project has been investigating integrating programming languages with query languages.


Asymmetry in converting Burrows-Wheeler transform to suffix array? Given a suffix array of a string $w$, it's possible to construct the Burrows-Wheeler transform of $w$ by subtracting one from the indices of the suffix array (wrapping around if necessary), then outputting the characters in $w$ that appear in that position.

However, to the best of my knowledge, there doesn't seem to be an algorithm to directly construct a suffix array for $w$ given the Burrows-Wheeler transform of the string $w$. It's still possible to do so in linear time by inverting the transform to get back $w$ and then constructing the suffix array directly, but that doesn't make any use of the transformed array.

Is there a fundamental reason why the reverse direction would be "harder" than the forward direction?

Thanks!

It's possible to build the suffix array of $s$ in linear time from $s$ and $BWT(s)$ in a somewhat easy way. You do need to build a rank-select data structure on $s$ in order to do this.

To see how to do this, look at Ferragina and Manzini's paper "The FM-Index". The LF mapping they describe also essentially computes the suffix array.


Generating graph for random walk given hitting time distribution given a discrete distribution of hitting time probabilities, is it possible to generate a random walk that generates this hitting time distribution? More specifically I am interested in generating a finite graph so that a simple random generates the given hitting time distribution.

I guess it is not possible to generate the exact distribution, but maybe approximate it?

Any hints on papers etc. are welcome!

Thanks,
Chris

There are lots of different kinds of random walks (discrete vs continuous, weighted vs constant, classical vs quantum) so the exact approach will differ some what in each case, but I will attempt to outline a fairly general approach here.

Usually the evolution of that system will be given by $A^t$ for some matrix $A$, where $t$ is time. The exact nature of $A$ will depend on the type of random walk you have in mind, but in any case, we expect the system to be in a state $A^t v$ after time $t$, where $v$ denotes the starting state. The question then becomes: given a set of hitting times $\{t_i\}$, corresponding states $\{u_i\}$, and hitting overlaps $\{p_i\}$, can we find some matrix $A$ which satisfies $u_i^\dagger A^{t_i} v = p_i$ for all $i$? Certainly this will not always be the case (since we could have conflicts where orthogonal states are required at the same time), so I assume you are really interested in how to find $A$ when there does exist an $A$ satisfying these relations.

EDIT: My previous answer was incorrect beyond this point, so I have replaced that portion.

I am not 100% sure of the most efficient way to find $A$. You have a system of equations in the enteries of $A$, and these can obviously be solved numerically using, for example, Buchberger's algorithm. However, this approach is not computationally efficient, and there may exist a more straight forward approach.

If you simply want find a transition matrix which approximates this, then you can use any number of optimization strategies, though these too may be inefficient.

Note, here I have assumed a very general model which should be true for all random walks, but it makes it hard to say anything concrete about how hard long it will take to numerically find a solution. If you have more information (i.e. is this a discrete time walk? Is it classical (I assume so)? Are weighted transitions probabilities allowed or do they have to be constant? Is this associates with some lattice (1d, 2d, or an arbitrary graph)?) Then you can possibly do much better. In the worst case, though, this problem seems to be NP-hard (since you get an integer programming problem if you restrict the transition probabilities to be multiples of some constant).


Source of Turing-machine illustration I am writing a computer science textbook and want to use an illustration showing a Turing machine.  Images are all over web, but almost always without authorship/illustratorship credited. I need to attribute authorship (and perhaps also clear rights).
Does anybody know where the image reproduced below first appeared?
Alternative: Can anybody point me to a similar illustration of a Turing machine where authorship is known?

The figure appears to come from the paper "Games, Logic, and Computers" by Hao Wang, which appeared in Scientific American, Volume 213, Number 5, November 1965, pages 98-106.  There is a copy online here:

http://www.cs.virginia.edu/cs200/readings/wang.pdf

In case you're wondering how I found it, I googled 'Turing machine "memory dial"'.  None of my Turing machines have a memory dial, so I was hoping to learn where to buy one.