What is the significance of a Θ-bound on the running time of Mergesort? While studying algorithm analysis I found that there is something called tight bound and there is some mathematical formula to support it.
Given:

  Mergesort takes $\Theta(n \log n)$ compares to sort $n$ elements.

What insight can we get from the above statement?

Mergesort takes $Θ(n \log n)$ compares to sort n elements [in the worst case].

Just unfold definitions. Step one:

  Mergesort takes $O(n \log n)$ and $\Omega(n \log n)$ compares to sort $n$ elements [in the worst case].

Step two (and three, I guess, since I recombine the unfolded definitions of $O$ and $\Omega$):

  For some $n_0 \in \mathbb{N}$ and $a,b \in \mathbb{R}_{>0}$, the number of comparisons $C_n$ Mergesort uses to sort $n$ elements [in the worst case] is bounded by $a \cdot n \log n \leq C_n \leq b \cdot n \log n$ for all $n \leq n_0$.

That's it. Would I call that insight? Hardly.

Adding the justification for why we ignore constant factors in the first place and that comparisons are a dominant operation in Mergesort, I guess the intended statement is something like this:

  If you implemented this Mergesort algorithm on a machine [that fits the RAM model and can compare all input numbers in constant time], its running-time cost would be roughly proportional to $n \log n$ for large enough $n$.

Note that neither the proportionality constant nor the sense of "roughly" and "large enough" are specified by the formal definitions. It may very well be that the algorithm is utterly unusable for all instances relevant to you. Hence, statements about algorithm performance using Landau notation are, for practical purposes, mostly vacuous -- formally speaking.

Implicitly, "we know" that "usually" constants are small and lower-order terms behave "nicely" (see e.g. here for a more precise result on Mergesort) so comparing Landau bounds is a somewhat meaningful criterion for choosing algorithms in practice. It has serious limitations, though, and it is important to keep those in mind.


Function whose implementation is difficult (computationaly) to work out Let's say I've got a function $f$ that takes a single number and returns a number. And I have another function $\mathrm{verify}f$ which takes the input I gave to $f$ and the number returned by $f$ which returns true if the output is the same as $f$ would have returned given the input.

If you know the input and output to $f$ and the function to verify then it is possible to work out what the implementation of $f$ is.

What I'd like to know, is if there exist some function that even if you know the output and the input and the verification function it's impossible to work out what $f$ does.

It feels like these functions must not exist – but I don't know that for sure.

If the function $f$ is computable, then $\mathrm{verify}f$ is computable too: to work out if $y=f(x)$ for some given $x$ and $y$, just compute $f(x)$ and see if it's equal to $y$. That tells you nothing about the implementation of $f$.

The relationship between the difficulty of computing $f$ and $\mathrm{verify}f$ is the essence of the P-vs-NP problem.


Problems that become far easier when restricted to only integer values I know that there are some problems that are very hard to solve in general, but become much easier and asymptotically faster if restricted to only integer values.

One such example would be sorting which can be done in O(n+M) if only integer values are allowed.

Another example (I think) is the undirected single source shortest path problem which seems to be solvable in linear time if all weights are positive integers.

My question now is which problems are significantly easier to solve if restricted to integer values (and why?)

Note: I obviously don't expect a complete listing, I just want to understand the general principle behind the speed up by restricting the problem space to integers.

There's no single answer.

Some algorithms are faster when dealing with small integers, because you can use small integers as the index into an array.
Some algorithms are faster when dealing with positive integers, because the set of positive integers has the property that it does not contain any infinite decreasing chains: any set of positive integers has a minimum.
Some algorithms are faster when dealing with integers because they assume a computational model where you can add or multiply integers in $O(1)$ time.  It is dubious whether these algorithms are truly faster in practice, as that assumption isn't literally true, but they might be.
Some algorithms are faster (or simpler) when dealing with integers because integers can be not only compared, but also hashed, and the ability to hash items increases the range of options available to the algorithm designer.  See the nuts-and-bolts problem for an example vaguely of this form (there are probably better examples).

There are probably many other principles I'm not thinking of right now.

Most of the cases I know of involve only a $O(\lg n)$ speedup.   However, be warned that asymptotic $O(\lg n)$ speedups are not very robust, for several reasons.  Just because algorithm A is asymptotically faster than algorithm B by a factor of $\Theta(\lg n)$ doesn't mean it'll be faster in practice; it might be slower in practice, because of constant factors or because of considerations ignored in the theoretical analysis (e.g., caching  effects, the memory hierarchy, and so on).  Also, often the $O(\lg n)$ speedup results you see in this area will be dependent on a particular computational model and might not carry over to other computational models.

So, it's not clear how much weight you should put on this, if you are motivated by practical concerns.

See also:

Is there a meaningful difference between O(1) and O(\log n)?
Logarithmic vs double logarithmic time complexity
Why is quicksort better than other sorting algorithms in practice?
Explaining the relevance of asymptotic complexity of algorithms to practice of designing algorithms
How can a quadratic algorithm be faster than a linearithmic one?
Shouldn't complexity theory consider the time taken for different operations?
How can we assume that basic operations on numbers take constant time?


Finding dimensions of a point cloud - floating point issues I have $N$ data points of some dimension $D$.

I want to know the dimension of the shape that those data points represent - for instance they might be a 2 dimensional triangle, even though they are in 8 dimensional space.

A way of doing this mathematically is to pick one of the points and subtract it from all of the other points to get $N-1$ vectors.

If i make these vectors into a matrix, the rank of the matrix will tell me the dimension of the shape of the data points.

The problem though is that implementing this using floating point math, not all vectors will cancel out that should.

I was wondering, is there a better way to do this when using floating point math?  Or, is there a way to get a thickness in each dimension so that very thin dimensions can be ignored?

One common way to do this is to apply a Principal Component Analysis (PCA) to your data. The operation essentially consists of rotating the data around the mean to align with the principal components. Most of the variance is moved to the first components. If you know the dimension of your manifold, then you can simply select the first $k$ components and reconstruct the lower dimensionality data. If you don't, there are simple criteria such as threhsolding the ratio of the variances. Of course more elaborate Bayesian methods also do exist, such as this one. I'll quickly give an overview of the simple method. Let $\mathbf{\lambda}=\{\lambda_1..\lambda_N\}$ denote the sorted eigenvalues (giving you the variances).  We could create a monotonically increasing CDF-like curve:

$$
f(i) = \frac{\sum\limits_{j=1}^i \lambda_j}{\sum\limits_{j=1}^N \lambda_j}
$$
where each element represents the variance explained up to that eigenvalue (or component). We could then pick a threshold $\tau$ (e.g. \tau=0.98). Then we throw out the components which remain above that (meaning low contributions)

$$
f(i)>\tau
$$

Similarly, one could also threshold the difference $g(i)=max(f(i)−f(i−1))$, as this will be the value where adding a dimension really makes sense. If $g(i)$ is small, there would be no real contribution to explain the variance.

This problem sounds like 'dimensionality estimation' or 'dimension discovery'. There are also other methods available. PCA is just the most easy-to-implement and famous one. If your structure is linear (such as a triangle as you mentioned) PCA should be suitable.


Don't understand closure under string reversal I am trying to learn from http://www.cs.uiuc.edu/class/su08/cs273/lectures/lect_06.pdf #2 and I understand everything except for the 2nd line of delta prime prime function,

I having breaking down the syntax to english, my attempt it

for the function delta'' for a given state q and a symbol t the r inside the original set of states Q such that the state q exists in the modified function (in which all final states go to one final state via e-transition) ...

This is where I get confused, its sending r to the modified function delta' but I dont understand what the r stands for and how it comes to be. Furthermore I don't know what Sigma_epsilon means, I assume its the alphabet union with {e}

I also don't see how the induction proof is trivial or easy

Both $q$ and $r$ are states in this construction. If in original $\delta'$ we can step $r\stackrel{t}{\rightarrow} q$ then in the new $\delta''$  we can step $q\stackrel{t}{\rightarrow} r$. Like stated in the proof the arrows are reversed.

You are right, $\Sigma_\epsilon$ is $\Sigma$ plus the empty word $\epsilon$. The original automaton initially has no $\epsilon$-transitions. However it has multiple final states, and after reversing it would have multiple initial states. A possible solution is given here, using $\epsilon$-transitions, connecting a new final state from the original final ones. This is the first step, from $\delta$ to $\delta'$.

If you are still trying to decipher the construction then of course the induction is not trivial. Once you see the arrows are just reversed, then it is not hard to come up with a possible induction assumption: if I can go from $q$ via string $w$ to $r$ in $\delta'$, then I can go from $r$ via string $w^R$ to $q$ in $\delta''$. Then it is no longer difficult. It would not say "easy" as that depends on your experience with induction.


About the interpretation of the SOS hardness results of the planted Max-Clique problem One can look at these two papers http://arxiv.org/abs/1502.06590 and http://arxiv.org/abs/1507.05136 and see their main theorems. If I understand right then both these papers are talking of the planted-Max-Clique problem and the second one is improving the detection threshold from $n^{1/3}$ in the first paper to $n^{1/2}$.

Does any of these results imply or do they implicitly contain the hardness threshold for say just the Max-Clique problem w.r.t even just the degree-4 SOS?
Or are both these results totally specific to the planted problem and say nothing about the Max-Clique?

If I say look at the corollary 2.1 (bottom of page 10) in http://arxiv.org/pdf/1502.06590v1.pdf then this seems to be a hardness threshold for just the Max-Clique problem but I am not feeling very sure since the authors never put in these same words. Am I missing something?  The same can be said about Theorem 1.1 (page 2) in the second paper.
If one sees the section 2.4 in the second paper, where they construct the SDP witness it feels that their construction would make sense only in the "planted" setting and then contrary to my feeling from theorem 1.1 now I start feeling that the result applies only with planting.

The planted clique problem and the maximum clique problem are different problems, though the former was introduced as an average case version of the latter. A paper addressing the planted clique problem doesn't address the maximum clique problem, and vice versa.

In particular, the papers you mention concern the planted clique problem, not the maximum clique problem.


Permutation of words that have matched parentheses Let $L$ denote the (context-free) language of matched parentheses over the alphabet $\Sigma$.  Consider the following problem:

Input: words $x_1,\dots,x_n \in \Sigma^*$
Question: does there exist a permutation $\sigma$ of $\{1,\dots,n\}$ such that $x_{\sigma(1)} x_{\sigma(2)} \cdots x_{\sigma(n)} \in L$?

What is the complexity of this problem?  Can it be solved in polynomial time?  Is it NP-hard?

It "smells" like something that might be NP-hard.  But perhaps there is a way to reduce this to the route inspection problem (which has a polynomial-time algorithm),  perhaps by treating each $x_i$ as an edge in some graph, or something?

Motivation: This is inspired by a question about permutations of lines of code, but my main interest is just curiousity.

Related:

Time complexity of a problem inspired by palindromes claims to show that the problem is NP-hard when $L$ is the language of palindromes, a different context-free language (though I don't understand the proof).
Word tiling, where you must use each tile exactly once considers the problem where $L=\{y\}$ where $y \in \Sigma^*$ is a single word specified as part of the input, and the answers show this is NP-hard too.

When there are more than one type of parentheses (say [] and ()), the problem is NP-complete. The proof is the same as the proof for the palindrome problem except that in the reduction, 0s and 1s in $w$ are changed to [s and (s respectively, 0s in $v_i$ are changed to ]s and 1s in $r_k$ are changed to )s.

When there are only one type of parentheses (say ()), the problem can be solved in polynomial time.

For a character $c\in\{$($,$)$\}$, denote
$$
t(c)=\begin{cases}
1 & \text{if }c\text{ is '('},\\
-1 & \text{if }c\text{ is ')'}.
\end{cases}
$$
For a string $s=s_1s_2\ldots$ where $s_i\in\{$($,$)$\}$, denote $f(s)=\sum_{i=1}^{|s|}t(s_i)$ and $g(s)=\max_j\sum_{i=j}^{|s|}t(s_i)$. We have
$$
\begin{align}
f(s_1s_2)&=f(s_1)+f(s_2),\\
g(s_1s_2)&=\max\{g(s_1)+f(s_2), g(s_2)\}.
\end{align}
$$

We say a string $s$ is potentially accepted if for any prefix $p$ of $s$, $f(p)\ge 0$. Note $s$ is potentially accepted if and only if $f(s)\ge g(s)$. Also note $s\in L$ if and only if $f(s)=0$ and $s$ is potentially accepted.

Note if $\sigma$ is a valid permutation, and $f(x_{\sigma(i)})<0$ and $f(x_{\sigma(i+1)})\ge0$ for some $i$, we can swap the two elements to get another valid permutation. This suggests that we can arrange all $x_i$'s satisfying $f(x_i)\ge 0$ (say $x_{r_1},\ldots,x_{r_k}$) on the first $k$ positions, then arrange other $x_i$'s on the rest positions.

For the first $k$ positions, we process greedily. That is, say $\sigma(1),\ldots,\sigma(j)$ is determined, if there is some $i$ such that $x_{\sigma(1)}x_{\sigma(2)}\ldots x_{\sigma(j)}x_{r_i}$ is potentially accepted, we arrange $x_{r_i}$ on position $j+1$, i.e. $\sigma(j+1)=r_i$. Otherwise, we cannot arrange these $x_{r_i}$'s on positions $1,\ldots,j$ too, so we assert there is no valid permutation.

For the rest positions, we arrange them according to $g$ from big to small. That is, $g(x_{\sigma(k+1)})\ge g(x_{\sigma(k+2)})\ge\cdots\ge g(x_{\sigma(n)})$. If this arrangement is invalid, i.e. the final string does not belong to $L$, we assert there is no valid permutation. The correctness of this process comes from the following lemma:

  If for some valid $\sigma$ such that $f(x_{\sigma(k+1)}),\ldots,f(x_{\sigma(n)})<0$ and for some $i$, $g(x_{\sigma(k+i)})<g(x_{\sigma(k+i+1)})$, we can swap $x_{\sigma(k+i)}$ and $x_{\sigma(k+i+1)}$ to get another valid permutation.

Proof of the lemma. For convenience, denote $s_0=x_{\sigma(1)}\ldots x_{\sigma(k+i-1)}$ and $s=x_{\sigma(1)}\ldots x_{\sigma(n)}$. Note after swapping, $f(p)$ is not changed for prefix $p$ of $s$ such that $|p|\le |s_0|$ or $|p|\ge |s_0x_{\sigma(k+i)}x_{\sigma(k+i+1)}|$, we need only to show $s_0x_{\sigma(k+i+1)}x_{\sigma(k+i)}$ is potentially accepted. Note
$s_0x_{\sigma(k+i)}x_{\sigma(k+i+1)}$ is potentially accepted, we have
$$
\begin{align}
g(s_0x_{\sigma(k+i)}x_{\sigma(k+i+1)})\le f(s_0x_{\sigma(k+i)}x_{\sigma(k+i+1)})
\end{align}
$$
or
$$
\begin{align}
g(s_0)+f(x_{\sigma(k+i)})+f(x_{\sigma(k+i+1)})&\le f(s_0x_{\sigma(k+i)}x_{\sigma(k+i+1)}),\\
g(x_{\sigma(k+i)})+f(x_{\sigma(k+i+1)})&\le f(s_0x_{\sigma(k+i)}x_{\sigma(k+i+1)}),\\
g(x_{\sigma(k+i+1)})&\le f(s_0x_{\sigma(k+i)}x_{\sigma(k+i+1)}),
\end{align}
$$
or
$$
\begin{align}
g(s_0)+f(x_{\sigma(k+i+1)})+f(x_{\sigma(k+i)})&\le f(s_0x_{\sigma(k+i+1)}x_{\sigma(k+i)}),\\
g(x_{\sigma(k+i+1)})+f(x_{\sigma(k+i)})<g(x_{\sigma(k+i+1)}) &\le f(s_0x_{\sigma(k+i+1)}x_{\sigma(k+i)}),\\
g(x_{\sigma(k+i)})\le g(x_{\sigma(k+i+1)})&\le f(s_0x_{\sigma(k+i+1)}x_{\sigma(k+i)}),
\end{align}
$$
which means
$$
\begin{align}
g(s_0x_{\sigma(k+i+1)}x_{\sigma(k+i)})\le f(s_0x_{\sigma(k+i+1)}x_{\sigma(k+i)}).
\end{align}
$$
Hence $s_0x_{\sigma(k+i+1)}x_{\sigma(k+i)}$ is potentially accepted.


How do you translate these 2 regular languages in words correctly? Given are 2 different languages and I'd like to know if I understand them correctly.

L ⊆ ∑* is a regular language.

cycle(L) = {vu ∈ ∑* | uv ∈ L}
L/2 = {x ∈ ∑* | ∃y ∈ ∑* : xy ∈ L, |x| = |y|}

I need to know that because the actual task is to show that these languages are regular by either describing how you build a DFA or NFA for them.

But I just like to know if I understood them correctly.

So 1. means that every word has an existing reverse.

As example we have word aaa and bab, if we concatenate them, we have aaabab. Now the language says that there is also a word babaaa

Means that we have two words of same length and we concatenate them?

For 1. it is not quite the reverse; it happened to be a reverse in your example. So if $u = aab$ and $v = abb$ and $uv \in L$, then you know $vu = abbaab \in \text{cycle}(L)$, but you wouldn't be able to say that $bbabaa = v^Ru^R \in \text{cycle}(L)$.

For 2. it is not that you want the concatenation of two strings of equal length, but rather you only want the first half of even-length strings in $L$. That is, if, say, $aabbabbabb \in L$, then $aabba \in L/2$.


Question About Floating Point System I have begun reading Numerical Analysis by Walter Gautschi. On page $3$, the author introduces the floating point number system as follows: a floating point number is a number representible as
$$
\begin{equation}
\pm (.b_{-1}b_{-2}...b_{-t})_2 \cdot 2^{\pm(c_{s-1}c_{s-2}...c_0.)_2} \tag {1}
\end{equation}
$$
where $s, t$ are fixed. We denote this number system by $\mathbb{R}(t, s)$.

Then, Walter says that a number $x \in \mathbb{R}(t, s)$ is normalized if $b_{-1}=1$, and that we $"$assume all numbers in $\mathbb{R}(t, s)$ are normalized $"$.

My Question: Consider consider the number
$$x = +(.00100) \cdot 2^{-(111.)}$$
Is this number an element of $\mathbb{R}(5, 3)$? According to the definition, I want to say yes. But when the author says $"$we assume all numbers in $\mathbb{R}(t, s)$ are normalized,$"$ I don't know if he is implicitly redefining $\mathbb{R}(t, s)$ to be numbers of the form $(1)$ with the additional requirement that $b_{-1}=1$. If we try to impose this requirement on $x$, I believe $x$ would come out to
$$x=+(.10000) \cdot 2^{-1001}$$
which shouldn't be part of $\mathbb{R}(5, 3)$

Background
I am a math major taking my first numerical analysis. I do not have any prior experience with computer science or numerical mathematics.

After reading further, I found the answer. The answer is that the $x$ given in the question is not in $\mathbb{R}(5, 3)$. The way I figured this out is as follows:

On the next page, the author states that
$$\min_{x \in \mathbb{R}(t, s)} |x| = 2^{-2^s}$$
This is consistent with $(.100 \cdots 0) \cdot2^{-(11\cdots 1)}$ being the least positive number in $\mathbb{R}(t, s)$, and not $(.000 \cdots 01) \cdot2^{-(11\cdots 1)}.$


Best data structure for queries about subsets? I am interested in finding a data structure that supports the following operations:

Insert Set: Insert a set into the data structure.
Decide Subset: Determine whether a given set is a subset of any of the inserted sets.

The most obvious way to implement this would be as a hash set of hash sets, but I think some performance gains could be had by exploiting common subsets among the stored sets. For example, if {1} and {1,2} were both stored, only {1,2} would need to be kept. Any ideas?

There is a popular algorithm in bioinformatics for solving this exact problem. I believe it is known as the multi-set membership testing problem (MSMT).

BigSI

The idea in BigSI is that you represent each of the $N$ inserted sets as a bloom filter of length $m$ with $k$ hashes. Let $Q$ be our $m\times N$ table, where the columns represent each of the $N$ bloom filters for each of our $N$ sets $\{X_1, ... , X_N\}$.

Now we wish to query $Q$ for an input set $S$. Let $A=\{h_i(s) \;\;\forall i\in[k],s\in S\}$ be all of the hash values for the input set. We have the following condition
$$S\subseteq X_i \iff Q[r][i] = 1 \;\;\forall r\in A$$ It remains to find columns such that the right hand side holds true. To do this, we create a subset of the rows  $Q'=\{row_i(Q) \; | i \in A\}$ . Now our condition is that
$$S\subseteq X_i \iff Q'[r][i] = 1 \;\;\forall r\in [|A|]$$
i.e. any columns with all $1$s in $Q'$ is a superset of $S$. We can find such columns $C$ by performing
$$ R = \bigwedge_{r\in[|A|]}Q'[r]$$
$$ C = \{i \;\;| \;\; R[i] = 1\}$$
If $C\neq \emptyset$, then $S$ must have been a subset of one of the original $N$ sets. Of course this algorithm is also able to tell you which of the original sets $S$ is a subset of. Since your question doesn't need that information, there may be some minor optimizations.

Here is a figure from the BigSI publication, where the input sets are FASTQ files which are broken down into $k$-mers. Part (a) represents the 5 input sets, each of cardinality 2. Figure (b) shows the resulting $Q$ table and the $\texttt{AND}$ operation used to find the superset inputs. Figure (c) is a naive alternative, where each row represents a possible element from one of the input sets, however this table would have to grow vertically as well as horizontally for each input set, as we may see new elements.


Splitting permutations into transpositions Suppose we are given an array $\texttt{a[]}$ of $n$ non-negative integers. The algorithm should give back $\texttt{-1}$ if an integer appears more than once in $\texttt{a[]}$.

Otherwise we interpret $\texttt{a[]}$ as a permutation $\pi:\{0,\ldots, \texttt{max(a[])}\} \to \{0,\ldots, \texttt{max(a[])}\}$ sending $\texttt{i}$ to $\texttt{a[i]}$ for $\texttt{i} \in \{0,\ldots,n-1\}$, and $\pi(k) = k$ for $k\geq \texttt{length(a[])}$.

What could be an algorithm to write $\pi$ as represented by $\texttt{a[]}$ as a sequence of transpositions, and what is the complexity?

One way to do it consists of two steps:

Find the cycle representation of the input.
Convert the cycle representation into a product of transpositions.

The first step is very similar to DFS. The second step is an exercise in permutation group theory.


Segmenting a human body point cloud into limbs I have a human body point cloud taken through a Kinect (v1). Now, I want to segment the point cloud into different parts, namely hands, lower arms, upper arms, torso, upper legs, lower legs, feet and head.

Here's the method I'm currently using:

I get the approximate skeleton from the point cloud using OpenNI
I take those points from the point cloud that are at a distance d from the line that is the bone (obtained from OpenNI). This distance d is currently set differently for different parts, based on observations only.

The problem with the above method is that it's not very robust. The parameter d can be different for people with different body types and also this is prone to errors since at the joints, the points within the circle of radius d will lie in both the parts.

Is there a better way of segmenting the point cloud?

Edit: This is what I get from OpenNI

The blue portion is the lower arms segmented using the above algorithm.

Suggestion: for each point $P$ in the point cloud, find which bone it is nearest to, and associate it with that bone.  In other words, find which point $Q$ on the skeleton is closest to $P$, and associate $P$ with $Q$.  Now associate $Q$ with a particular part of the skeleton (e.g., arm, leg, etc.); that will let you associate $P$ with a particular part of body (e.g., arm, leg, etc.).  Do this for each point in the point cloud.

Try that -- it's a very simple approach, and it might just work.


Scoring metric for machine learning method For a machine learning method X (Deep Neural Nets variant), which performs classification tasks.

In the output layer, for every label method, X also emits the uncertainty U associated with the respective prediction.

So, in case the testing dataset is very different then the predictions made by X should have a high U. (Mean of U across all labels should be high)

In the case of testing, the dataset is indeed from the same source from which training dataset was generated. For true positives, the mean of uncertainty for the correct label would be low. In the case of false positives, the mean of U would be high (ideally).

What is the principled approach to measuring the effectiveness of method X in outputting the uncertainty? In other words, what would be a good metric to understand the performance of the method in computing the uncertainty for each label?

Metric similar to Root mean squared error or others.

There are at least two possible interpretations of uncertainty: (a) uncertainty/confidence in the label that the network predicts; (b) uncertainty in the probability/confidence score that the network outputs for the predicted label.  (There might be others as well.)  Let me explain both of those.

Confidence scores: uncertainty in the label

Standard deep learning methods already provide a confidence score for their prediction.  They output not a single label, but a probability distribution on labels (through a final softmax layer).  Then a cross-entropy loss function is used to measure how well the predicted distribution matches the known labels, on the training set.

Once you have this, you can easily measure uncertainty.  When applied to a test instance $x$, the output will be a probability distribution on labels.  If the label $\ell$ has the highest probability (in this distribution), say probability $p$, then $p$ is a measure of the network's uncertainty/confidence: the smaller $p$ is, the more uncertain (the less confident) the network is in its prediction.

For example, suppose we have a neural network whose input is an image of a stoplight, and classifies whether it is showing a red light, i.e., the two labels are "red" or "not red".  Such a neural network (if it ends with a softmax layer) actually outputs a vector $(p_\text{red},p_\text{not red})$ where we interpret $p_\text{red}$ as the network's estimate of the probability that the light is red.  Thus, the network classifies the image as "red" if $p_\text{red} \ge p_\text{not red}$ and "not red" otherwise, and the confidence score is the probability score associated with that label.

This provides a notion of uncertainty.  For instance, suppose the network outputs the vector $(0.8,0.2)$.  Then we'll classify the image as "red", and the confidence score indicates that the network thinks there is a 80% chance that the image is red, so that is a notion of how certain it is that the image is "red".  This confidence score is also known as a "posterior probability", in a Bayesian framework, and it can be treated as measuring one kind of confidence.

Uncertainty in the confidence score

Alternatively, perhaps what we want to measure is not uncertainty in the predicted label, but uncertainty in the confidence score associated with that label.  For instance, if the output vector is $(0.8,0.2)$, then we'll classify the image as "red", with 80% confidence; perhaps what we care about is, how certain/uncertain are we, in the number "80%"?

That can be measured by the variance of this score.  We can construct 1000 different neural networks for this task.  Each one will output an output vector, and in particular, a confidence score that the image is red.  If we want our best estimate of the posterior probability that the image is red, we take the average of those 1000 scores. If we want to know the uncertainty in that estimate, we take the variance (standard deviation) of those 1000 scores.  Thus, this might let us say "we classify the image as 80% likely to be 'red', with standard deviation of 5% around the 80%".  That variance (or standard deviation) can be taken as a measure of our uncertainty in the number 80%.

This is what Nicolas Mancuso's excellent answer is explaining, in mathematical terms.  I've tried to explain it in non-mathematical terms, to help understand the idea.

Why 1000 networks?  The number 1000 is arbitrary.  A smaller number will be faster.  A larger number will provide a more precise measure of the standard deviation.

How do you train 1000 random networks?  There are several possibilities.  One is to use bagging.  Another is to train on the same training set, but use different random values when creating the network (e.g., initialize each network randomly and independently; use dropout, and use different randomization for each network's dropout, and maybe enable dropout at test time too).


Incremental View Maintenance for projection I was reading https://www2.cs.duke.edu/courses/spring02/cps296.1/lectures/08-view.pdf

Or in the paper "Incremental Maintenance of Views with Duplicates," by Griffin and Libkin, SIGMOD, 1995. figure 2.

I don't understand why we need to min(R,ΔR) before -.
Is there any counterexample?

Just realize the reason after posting the question.
Counterexample:
R =

A  B

1  2

1  1

1  1

ΔR =

A  B

1  1

1  1

1  1

Assume we want ΠA(R - ΔR)

The true answer is first R - ΔR:

A  B

1  2

Then project A:

A

1

However, if ΠA(R - ΔR) = ΠA(R) - ΠA(ΔR).
ΠA(R):

A

1

1

1

ΠA(ΔR):

A

1

1

1

ΠA(R) - ΠA(ΔR) = ∅

ΠA(R - ΔR) = ΠA(R) - ΠA(R min ΔR).

R min ΔR:

A  B

1  1

1  1

ΠA(R min ΔR):

A

1

1

ΠA(R) - ΠA(R min ΔR):

A

1


What problems are solvable in Datalog? Datalog is not Turing complete. It does however have the wonderful property of not being order sensitive. What problems can be solved in Datalog? Where does it fit in the Chomsky hierarchy, i.e. what abstract machine does it model?

According to these slides, deciding whether a single atom is generated by a Datalog program is EXPTIME-complete. There are several corresponding machine models, for example an EXPTIME Turing machine or an EXPTIME RAM machine.


A push-down automaton with two stacks which is equivalent to a linear-bounded automaton It is known that a PDA with two stacks is equivalent to a TM.

On the other hand a PDA with one stack is capable to recognise only context-free languages.

Hence there is a kind of a gap between the class of PDA with one stack and the class of PDA with two stacks which should be capable to recognise only context-sensitive languages.

I feel like it should be already an examined question, but I couldn't find an answer: what restrictions should we apply to a PDA with two stacks in order to make it equivalent to a Linear-bounded automaton?

A 2-stack PDA with a linear bound on both stacks is equivalent to a LBA.

What happens if only one of the two stacks is linear bounded and the other is unlimited? I optimistically wrote a quick comment that the LBA equivalence holds also in this case ... but ...

It's easy to see/prove that a 2-stack PDA with a linear bound only on one stack can simulate a LBA with one stack; and it is an open problem if a LBA with one stack is more powerful than a standard LBA.

For further details see T.Klimpel's answer to the question Is a LBA with stack more powerful than a LBA without?

This is a sketch of the proof that a PDA + 1 linear bounded stack + 1 unbounded stack (PDA+1B+1U) can simulate a LBA + 1 unbounded stack (LBA+1U)

Given a LBA+1U build a PDA+1B+1U in which the bounded stack is used to store the leftmost tape portion (reversed) and the unbounded stack stores the rightmost portion plus the unbounded content of the LBA stack.

A particular configuration of the LBA+1U:

    # x a y # stack: [b w   ]
        ^head

(where $\#$ are the endmarkers of the linear space, the head is on symbol $a$, the content of the tape is $xay$, the stack contains $bw$, $b$ is the top)

is represented into the PDA in this way:

    stack 1: [ > a x^R #  ]  (bounded stack)
    stack 2: [ y # b w       ]  (unbounded stack)

(where $>$ is a marker for the head position, $x^R$ is the reverso of $x$.

Suppose the LBA pops the b, change $a$ into $c$, moves left and pushes $d$ into the unbounded stack reaching this configuration:

    # x c y # stack: [ d w   ]
      ^head

The PDA can simulate that behavior in this way: it checks and pops the content of the unbounded stack using stack 1 as temporary storage:

    stack 1: [# y^R >a x^R # ]  (bounded stack)
    stack 2: [b w    ]  (unbounded stack)

Then it goes back to the head marker (storing "b" in its internal state)

    stack 1: [>a x^R # ]  (bounded stack)
    stack 2: [y # w    ]  (unbounded stack)

Then it moves left (and push c in the second stack simulating the a->c write operation):

    stack 1: [>x^R # ]  (bounded stack)
    stack 2: [c y # w    ]  (unbounded stack)

"goes" to the stack marker and push d:

    stack 1: [# y^R c >x^R # ]  (bounded stack)
    stack 2: [d w    ]  (unbounded stack)

then "goes back" to the head position:

    stack 1: [>x^R # ]  (bounded stack)
    stack 2: [c y # d w    ]  (unbounded stack)

Addendum

The proof that a PDA+2bounded stacks (PDA+2B) can simulate a LBA is similar.

For the other direction (a LBA can simulate a PDA+2B) the idea is to use two symbols to mark the top of both stacks $b_1, b_2$, and use the linear space to store the two bounded stacks "overlapped" (just use an expanded $\Sigma \times \Gamma \times \Gamma \times \{ b, b_1, b_2 \}$ alphabet).

By further expanding the alphabet you can store in the same (linear) space the original input, the head position of the PDA+2B, and an enumeration of the nodeterministic choices (there are at most $c|x|$ of them, one for each symbol of the initial input. Where $c$ depends only on the size of the transition table).

Then you can scan all the nondeterministic choices and simulate the behaviour of the PDA+2B using the top stack markers.

Note that if you allow epsilon transitions you must run two enumerations in parallel in order to check if the PDA+2B enters the same configuration due to  $\epsilon$ transitions (i.e. detect if it loops forever)


Can heuristic methods and machine learning approaches be considered alternate methods to solve NP-Complete problems? I was watching the videos from Skiena's Computational Biology Lectures, which is also available at youtube. In those videos, the professor made a statement that, most of the problems posed to computer scientists by biologists were proved to be NP-Complete. My questions are the following ones:
( Please forgive me, if I make blunders here in asking questions. I am not from CS background.)

Do NP-Completeness imply no algorithm exist for that particular problem?
The professor was talking about heuristic approaches where normal approaches fails. Do there exist 'heuristic' approaches in computer science to solve problems? If so , Can some one give examples. (I have heard of heuristic approaches in analog circuit design in electronics. But I am not sure. Music composition is heuristic , right?)
Is Machine learning a solution to solve some computational problems, where traditional algorithmic solutions doesn't exist?

I haven't seen these lectures, but here's what I think about he questions you pose.

No. NP-completeness is unrelated to the existence of algorithms. For example, we have plenty of problems that we can prove only have an exponential solution. We typically talk about "is there a solution" as decidability. There are problems that have no solution and we call these undecidable. The Halting Problem is a popular example.
Absolutely. When we can't find an efficient solution for all inputs, we find something that works for "most cases". In some cases, we can can prove the solution generated is not worse than K times the true optimal solution. In other cases, we cannot.
Yes.  Machine learning works well for certain classes of problems, but is really hard to apply to others.  It's not a "silver bullet" or alternate solution to computational complexity.

Regards.


Decidability of Equality of Radical Expressions Consider terms built from elements of $\mathbb Q$ and the operations $+,\times,-,/$, and $\sqrt[n]{\,\cdot\,}$ for each natural number $n$. Given the promise that two terms are well-formed -- that is, there is no division by zero, and no even roots of negative numbers -- is there an algorithm which decides when the two terms are equal?

A related question was posted here, but it is more general (as it allows arbitrary exponentiation, rather than just by rational numbers).

Algebraic numbers are solutions of polynomials with rational coefficients.
$+,\times,-,/$ of algebraic numbers result in algebraic numbers because algebraic numbers form a field (1). This means nested radicals are algebraic numbers too (2).
Nested radicals can be denested by algorithm (3,4).
Each algebraic number of degree $n$ can be uniquely represented as a $n$ by $n$ matrix of integers under a suitable basis (for example, $[1,x, (x^2+1)/2]$). This representation allows symbolic evaluation of $+,\times,-,/$ by matrix addition, multiplication, and inverse (p.159 of 5,6,7).
Two terms are equal if their unique representations are identical.


What does least fix point and greatest fix point mean in Safety games In safety games there are these mathematical notation about greatest fix points and least fix points but I don't get it. How would we describe them plain English without mathematical symbols.

Probably the most common fixpoint expressions in model checking are things like $\mu X.A\cup(B\cap\circ X)$ and $\nu X.A\cap(B\cup\circ X)$, where $\circ$ is some flavour of "next state" operator. That is, the least $X$ such that $X = A\cup(B\cap\circ X)$, and the greatest $X$ such that $X = A\cap(B\cup\circ X)$, respectively. More generally, we are talking about fixpoints of monotonic set transformers, i.e. functions $P({\cal S})\to P({\cal S})$ operating on the subsets of a given set $\cal S$.

An intuitive way of thinking about least fixpoints is that they represent sets constructed bottom-up using constructors. Suppose you wanted to define the natural numbers as a subset of the reals: $n$ is a natural number iff it is $0$, or the successor of another natural number. This means that $\mathbb{N}$ is a fixpoint of the set transformer $F:S\mapsto\{0\}\cup succ(S)$. This is not enough, though: the set of all real numbers is also such a fixpoint. $\mathbb{N}$ is the least fixpoint, though, meaning that it only contains those elements which it has to in order to be a fixpoint. Computationally, this fixpoint is the limit you obtain by iterating the given set transformer $F$ on the empty set, gradually assembling the elements of $S$, i.e. the limit of $\emptyset,F(\emptyset),F(F(\emptyset)),\dots$.

In the case of $S:=\mu X.A\cup(B\cap\circ X)$ this means that $S$ contains exactly those elements which can reach $A$, satisfying $B$ until they get there; not requiring the least fixpoint would mean that you could additionally have arbitrary $B$-cycles, infinite $B$-paths never satisfying $A$, etc in your set.

For greatest fixpoints, you have the dual situation: the set contains all elements which are not explicitly eliminated by the given conditions. For $S=\nu X.A\cap(B\cup\circ X)$, this includes any element which satisfies $A$, and either also satisfies $B$ or has a successor in $S$. We pick the greatest fixpoint because we want to include everything which doesn't violate the requirements. Otherwise we might end up with an excessively restrictive set (such as the least fixpoint, which is just $A\cap B$ in this case). Computationally, this is the limit you get by iterating the transformer on the full set $\cal{S}$ of states, gradually eliminating all which fail the specification, i.e. the limit of ${\cal S},F({\cal S}),F(F({\cal S})),\dots$.


Variation of rank selection in genetic algorithm I'm looking for a specific variation of rank selection in genetic algorithms.

I came across a python program tailored for a specific problem that uses a variant of "rank" selection.  In normal rank selection, all individuals are sorted by fitness (in descending order) so that worst chromosome gets a weight of 1 and the best gets a weight of the population size.  Then, usual roulette wheel selection is used based on those "weights".

In the case of that program, a slightly different variation of rank selection is used.  Instead of relying on rouletted wheel selection after the chromosomes have beed sorted by rank, that program just pairs chromosome 1 with 2, 3 with 4, 5 with 6 and so on for crossover.  Does that rank selection method have a particular name and/or can anyone pinpoint me to a link describing that variation.  I googled it but haven't been able to find anything similar so far...

For Differential Evolution (DE) there is the Rank-Based Crossover Operator that is quite similar.

It has been proposed in "A line up evolutionary algorithm for solving nonlinear constrained optimization problems" by Haralambos Sarimveis, Athanassios Nikolakopoulos (2005):

  The idea is to line up the solutions in each generation in a descending order according to the corresponding values of the objective function. The crossover and mutation operations are then applied to the solutions as follows: during the crossover operation, for each adjacent pair the difference vector is computed, weighted by a random number between 0 and 1 and added on the first vector of the pair. The produced solution replaces the first vector, if it produces an objective function value that is lower than the fitness value of the second vector. At the end of the crossover operation, the solutions are lined up again.

Of course DE has a peculiar crossover operator but the general idea of lining up individuals (rank based order) to choose crossover pairs is the same.


What are the first computer science papers that used asymptotic time complexity? When was big O first used in computer science and when did it become standard? The Wikipedia page on this cites Knuth, Big Omicron and Big Omega And Big Theta, SIGACT April-June 1976, but the beginning of that paper reads

  Most of us have gotten accustomed to the idea of using the notation
  $O(f(n))$ to stand for any function whose magnitude is upper-bounded by a
  constant times $f(n)$, for all large $n$.

This quote indicates that the idea and notation were already in common use.

The Wikipedia page also cites math papers from the late 1800s and early 1900s, but that doesn't quite answer the question. In particular, I've heard researchers who were around back then (in the 60s and 70s, not the late 1800s) say that when asymptotic analysis was first used, some people pushed back, saying that wall clock time was a better metric. However, no one I've talked to can cite the specific papers that got pushback like this and I'd like to find evidence that can confirm or deny these stories.

with history questions there are typically subtle nuances and its not easy to determine a particular paper that introduced a particular concept because it tends to be spread over many contributors and is sometimes rediscovered independently when obscure early references dont necessarily disseminate (fundamental ideas are like that). but the history basically goes something like this: Landau notation is an old mathematical formalism (1894/ Bachman)[1] which was imported into CS as a "key concept" around the early 1970s. by the mid 1970s this was somewhat accepted as in your Knuth reference and Knuth himself was involved in spreading this concept.

interestingly its import into CS was probably closely related to the P vs NP vs Exptime distinctions uncovered in early 1970s which were highly influential/ heralded in the field. it was Cobham/ Edmonds who started to define the class P in early 1970s.[3] there were early proofs about Exptime and Expspace by Stockmeyer/ Meyer.[2] the Cook-Levin theorem[4] (1971) showed the core relevance of P vs NP time, immediately supported by Karp[5] (1972).

an early mathematician who worked in number theory but also on the edge of computer science was Pocklington. as in [3] it points out:

  However, H. C. Pocklington, in a 1910 paper,[11][12] analyzed two algorithms for solving quadratic congruences, and observed that one took time "proportional to a power of the logarithm of the modulus" and contrasted this with one that took time proportional "to the modulus itself or its square root", thus explicitly drawing a distinction between an algorithm that ran in polynomial time versus one that did not.

another early pioneer in analyzing complexity of machine-based algorithms for number theory, ie factoring, was Derrick Lehmer, professor of mathematics at University of California, Berkeley, and built/ analyzed factoring "algorithms" (sieve based implementations) as early as the 1920s and its possible he may have described something like computational complexity wrt factoring in an informal way.[6]

yet another case is a "lost" 1956 letter by Godel to von Neumann talking about complexity measurements of steps f(n) of a machine to find proofs of size n.[7]

[1] Big O notation history / wikipedia

[2] Word problems requiring exponential time. / Stockmeyer, Meyer (1973)

[3] P time class history / wikipedia

[4] Cook-Levin theorem / wikipedia

[5] Karps 21 NP complete problems / wikipedia

[6] Lehmer factoring machine/ sieve / wikipedia

[7] Godels lost letter / RJLipton


Deriving the Time Complexity of Ryser's Algorithm for Evaluating the Permanent of a Matrix Ryser has shown that the permanent of an $n \times n$ matrix $A=(a_{ij})$ can be expressed as

\begin{align}
Perm(A) = (-1)^n \sum_{s \subset [n]} (-1)^{|s|} \prod_{i=1}^n \sum_{j \in s} a_{ij},
\end{align}

where $[n]=\{1,2,\dots,n\}$. This algorithm runs in $\mathcal{O}(2^{n-1}n^2)$ time. I've been trying to derive this, but can't quite get the result. Here's my work so far.

The outer sum is over all non-empty subsets of $[n]$, of which there are $2^n-1$. We recall that the number of subsets of size $r$ is ${n \choose r}=\frac{n!}{r!(n-r)!}$.

For each set $s$ in the outer sum we compute $\sum_{j \in s} a_{ij}$, which uses $|s|-1$ additions. Next, this sum sees the product $\prod_{i=1}^n$, which takes $n-1$ multiplications. This happens for each non-empty subset of $[n]$, so there are the following number of total additions:

\begin{align}
\sum_{s \subset [n]} \left(|s|-1\right) &= \sum_{k=1}^n (k-1) {n \choose k} \\
&= \sum_{k=1}^n k {n \choose k} - \sum_{k=1}^n {n \choose k} \\
&= n \sum_{k=1}^n {n-1 \choose k-1} - \left(2^n - 1\right) \\
&= n \left( 2^{n-1}-1 \right) - \left(2^n - 1\right) \\
&=n2^{n-1} - 2^n -n +1.
\end{align}

The total number of multiplications is $(n-1)(2^n-1)$.

There is also the $(-1)^{|s|}$, which takes another $2^n-1$ operations in total.

This gives us a grand total of $n2^n + n 2^{n-1} - 2^n -2n+1$, which is not correct. It looks like I'm off by a factor of $n$ on the second term here. Where am I going wrong?

For a given $s$, you do $(|s|-1)n$ additions, not $|s|-1$ additions: you have to compute the inner sum for each $i\in [n]$. Thus, you are missing a factor of $n$.


Is the Post Correspondence Problem with more than two rows harder than the standard two-row variant? The standard Post Correspondence Problem concerns tiles with two rows of symbols, and whether a tile arrangement can be made so that the sequence of the top symbols of the tiles is equal to the bottom one.
Let $\text{n-PCP}, \text{n} > 0$ a generalization of the Post Correspondence Problem where the tiles contain $\text{n}$ rows, and the sequences of the symbols have to be equal for all of these rows.
Obviously $\text{1-PCP}$ is decidable (in fact it's trivial because the answer to the problem is always true). $\text{2-PCP}$ is the standard PCP.
But what if $\text{n} > 2$? Is it harder or can it be reduced to the standard PCP (like >3-SAT being reduced to 3-SAT)?

$\text{n-PCP}$ can be reduced to $\text{2-PCP}$ as follows.
Let $M$ be a nondeterministic Turing machine that accepts an $\text{n-PCP}$ instance as input, guesses a solution for that instance, and then checks that it is correct. Clearly, $M$ accepts if and only if there is a solution to the input instance.
Now, let $p$ be an instance of $\text{n-PCP}$. The reduction encodes $M(p)$ as a $\text{2-PCP}$ instance in the standard fashion.


Describe in words how a NTM can simulate a DTM I have this assignment

Describe in words how a DTM can simulate a NTM
Describe in wordshow a NTM can simulate a DTM

I'm working on this request and I'm crushing with the comparison.

1-I understand that every NTM can be represented by a DTM with a tree structure, that represents every step of the different possibilities of a NTM. Every step should simulate with n tapes the configuration states of the NTM with the DTM etc.

2-For this I'm a little lost, I think you can't have a DTM simulated by an NTM, the multiplicity of states allowed in NTM with guesses makes difficult to create a deterministic process o linear, ¿I'm going in the right path?.

A nondeterministic Turing machine has zero or more possible transitions in every configuration; a deterministic one has exactly one. One is "zero or more".


Can one consider living (biological) cell to be Turing Complete? Universal Turing Machine can be boiled down to two components.
Infinite tape of input and an action table, a finite state machine that moves read/write head along the tape and writes to it depending on input provided by the tape.

From this point of view cells have some properties very similar to UTMs, the DNA is in an essence a tape of instructions that can be read and written to.
Rest of the cell behaves similar to action table, defining rules that guide which part of DNA is read and when it happens, a moving "head" along DNA "tape".

Subquestion 1: DNA can be used for computation. Can entire cell be used for similar purposes?

Subquestion 2: If every living organism contains at least one UTM is it possible that all organism are in some sense Turing Complete?

Every living organism has -- to our knowledge -- only a finite amount of resources available. So no, they can not be Turing-complete.

That said, there is quite a number of bio-inspired models of computation that can be studied formally. Sticker systems [1], for instance -- an abstraction of recombining DNA fragments -- can be shown to reach Turing-power when we assume infinite resources. Splicing systems [2] are another example.

I am not aware of any abstractions of entire cells. To my knowledge, we do not have a full understanding of how cells work so that is out of reach -- today.

Note: Turing-completeness requires programmability resp. universality. Can you elicit any response from a cell by applying suitable stimuli? I wouldn't think so. In my opinion, any given cell is more likely to correspond to a specific program with a specific purpose.

Sticker Systems by G. Păun and G. Rozenberg (1998).
Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors by T. Head (1987).


Does spectral graph theory say anything about graph isomorphism Is there research or are there results that discuss graph isomorphism in the context of spectral graph theory?

Two known theorems of spectral graph theory are:

Two graphs are called isospectral or cospectral if the adjacency matrices of the graphs have equal multisets of eigenvalues.
Almost all trees are cospectral.
The eigenvalues of a graph's adjacency matrix are invariant under relabeling (but this is not a necessary and sufficient condition).

Furthermore, is graph isomorphism "easy" to solve?

Graph isomorphism has been mentioned along with primality testing as early as 1971 in Cook's famous paper on NP-completeness. Cook mentions that he was unable to prove the NP-completeness of both problems. Nowadays we known that primality testing is in P, but the status of graph isomorphism is still unknown. Most experts conjecture that it is "NP-intermediate", that is, not in P but not NP-complete. Some conjecture that it should be solvable in quasipolynomial time (algorithms running in time $2^{\log^{O(1)} n}$). The best currently known algorithm, due to Luks, has running time $2^{O(\sqrt{n\log n})}$. It uses the so-called group theory method.

The two most common approaches are individualization/refinement and the group theory method. The former approach tries to match vertices of one graph to vertices of the other. Given a vertex of degree $d$ belonging to the first graph, it can only be matches to a vertex of degree $d$ in the other graph, but this offers no saving if both graphs are $d$-regular. Individualization/refinement is a framework for generating more detailed "types" of vertices.

It is possible that a similar approach can enhance the spectral method (which as stated fails for cospectral graphs), but I am not aware of any work along these lines (though it might exist; I'm not an expert in this area).

The group theory method reduces graph isomorphism to the problem of finding generators for the automorphism groups of graphs. Given two graphs $G_1,G_2$, the idea is to compute generators for $\operatorname{Aut}(G_1 \cup G_2)$, and check whether any of them switches a vertex of $G_1$ with a vertex of $G_2$. For more details, see for example lecture notes of Arvind.

For a recent overview of the state of the art, consult a paper by Babai; Babai is one of the principle researchers in the area.

Practical graph isomorphism is a completely different issue. A recent overview can be found in a paper of McKay, author of the popular package nauty.


Using a proof-of-work system to discourage piracy or encourage donations Background

A proof-of-work system allows one peer to prove to another peer that a certain amount of computational effort was performed.
In a network setting this can be used to throttle peer requests without needing to keep a precise track on the identity of the peers or prior events.
The most well known use of proof-of-work is to throttle spam throughput in an email network*.

Some proof-of-work systems allow certain roles on the network (say, a mailing list) to calculate the proof of work much faster by using a secret "short-cut" - typically a pre-calculated trapdoor or a private key depending on the proof-of-work system.

Hypothesis

Any algorithm or a certain class of algorithms can be converted into a proof-of-work version of that algorithm. That is: A deliberately inefficient and incompressible algorithm.
Such converted proof-of-work algorithms can support proof-of-work shortcuts.
Such converted proof-of-work algorithms can not be converted back to the original algorithm without considerable computational power; if at all.

Extrapolation

If the hypothesis holds, then selected business logic of an application - specifically that which is unique or value-added by that application vs existing applications - could be converted to proof-of-work equivalents.

End-users could then be provided such an application; which will run slowly either generally or for certain premium features. The development team however, possesses a secret PoW shortcut and set up a subscription, donation or advertising(!)-based service - an SaaS - for solving the proof-of-work bottleneck for the end-user. The end-user can now choose to run the application slower without the SaaS or faster with the SaaS.

This SaaS needs to process considerably less client-side business logic than a general cloud solution (e.g. Diablo 3 style SaaS); as the goal is the speed of execution rather than no execution - and the SaaS proof-of-work speed ratio is tailored accordingly.

This is especially relevant for software projects supported by charity as the developers do want the software available to anyone but can encourage donations without needing a separate fairly easy to pirate Freemium edition. The Tragedy of the Commons (freeloading) could be discouraged to a fair extent without guilt-tripping or rat poisoning, by adjusting the proof-of-work cost relative the value of the application or service.

  Example 1: A commercial stock market estimation tool licensed per
  month. If the user forgoes paying for a subscription, the estimation
  occurs at 1% the normal rate.

  Example 2: A free Triple A co-op video game runs twice fast if the
  user donates some money once a year.

In either example the user must decide between accepting the default speed; spending money on a faster computer/cloud services; or contributing to the upkeep of the product.

Question

Does the hypothesis hold and has anyone attempted to explore or implement this hypothesis?

Any example of an open source library or application that attempts to implement the hypothesis qualifies as a sufficient answer (from my perspective); as I could dissect the code.

 * Which has a variety of issues for the Digital Divide, but that's another story

Hypothesis

Any algorithm or a certain class of algorithms can be converted into a proof-of-work version of that algorithm. That is: A deliberately inefficient and incompressible algorithm.
Such converted proof-of-work algorithms can support proof-of-work shortcuts.
Such converted proof-of-work algorithms can not be converted back to the original algorithm without considerable computational power; if at all.

Surprisingly, this is possible.
Essentially the idea is: you can convert any program into a proof. Add some probabilistic complicated mathematical voodoo, and you can get succinct proof that someone ran a program on his machine, the full program, no cheating. This means you can essentially turn any busy-work algorithm into a POW, or even use useful algorithms as POW, and not have to worry about a shortcut (for example, you can use protein folding as POW, and not have to worry that average-case might not be hard). The proof guarantees that the entire program ran until termination.
For deliberate shortcuts you can simply build in early termination into the program for your deliberate shortcuts. For example:
def P(user_input,hard_coded_n):
  if user_input is not None:
    p,q = user_input
    if p*q = hard_coded_n:
      return True
  protein_fold()
  return True

In this program, you generate and hard-code a semi-prime, $n$, into the program. If you want to provide the user with a shortcut, you give him the p,q that he can use as input for early termination. Then you check his proof that he ran the program, and the proof will guarantee that the output he provides was the output of his program; therefore his POW is to provide "True" as output, and the proof.
This type of system is insanely powerful IMO; you can think of all sorts of things you can do with this; your cheap "DRM" ideas are the least of it :P
Further terminology/keywords:

Succint Non-interactive Argument of Knowledge (SNARKs) are basically succinct proofs that someone ran some computation.
SCIP: Succinct Computational Integrity and Privacy, is a practical system being built upon many years of research/complicated mathematics.

There is a large body of research into this, attempting to make it practical. For an actual project (SCIP) (you asked this question at the right time in history) see this talk: Universal and affordable computational integrity - Bitcoin 2013 Conference by Eli Ben-Sasson (another talk if you found that one interesting); though he applies it to bitcoin (it is a talk given at a bitcoin conference), he generally explains the power of the system, it is a good watch, even if you don't care about bitcoin.
However, the application to bitcoin, distributed trust systems, and systems that rely on proof-of-work are very numerous and abstract. Suffice to say, though the practical applications are hard to come by at first, the intuitive power of such a system suggests that they will be numerous.
Wrt. bitcoin, this system magnifies the potential of a distributed currency by orders of magnitude; read through bitcoin forums/mailing lists/proposals on the wiki, and you can find countless applications of being able to guaranteeing secure computation on someone else's machine.

For example, instead of verifying the entire bitcoin blockchain on your machine, you can have someone else do it, and then simply verify that he ran the verifier!
Of course arbitrary POW is a big possible win for future bitcoin; perhaps one day we'll see a blockchain doing useful work (now doubly useful, not just guaranteeing the integrity of bitcoin, but also computing something useful), or even a secure distributed computing marketplace, where the lottery of minting the next block is won by one of the participants.

For further reading see SNARKs for C :
Verifying Program Executions Succinctly and in Zero Knowledge
(extended version) (PDF): yes, they are making a C compiler. They designed a virtual architecture, called TinyRam from which they generate the proof and the program to be run. They are also considering an LLVM backend. They have created a website for the SCIP project.


Efficient way to check if a graph node's children were visited during traversal I have a generic traversal algorithm for graphs:

Traversal (container) {
    while (container is not empty ){
        visit container.pop()
        push new nodes
    }
}

and I want to make a time-efficient "child head count" for nodes that sets a flag for nodes whenever all their children have been visited:

Traversal (container) {
    while (container is not empty ){
        visit container.pop()
        push new nodes
        set close flag on parent nodes if last child to be visited
    }
}

The best ways that i could think of was to have pointers to "visited" booleans of the node's children and just "and" them up as such:

node1 -> [node2(true), node5(false), node7(true)]

node1.all_children_visited() = false

Or iterate through the parents whenever I visit the node for the first time:

Traversal (container) {
    while (container is not empty ){
        visit container.pop()
        push new nodes
        if first visit {
            for each parent {
                increase count
                if count(parent) = number of children {close(parent)}
            }
            if count(this) = number of children {close(this)}
        }
    }
}

Is there a way to do this with lower than O(n) complexity?

If you can afford more memory, add a field to each node's data containing a count of already visited children. Assuming that you know the number of children, if you update this field each time you visit a child, you will know when all children have been visited.


Decidability of dependent typing on primitive recursive languages With a dependent type system in a normal functional language type checking may never halt. This is partially because dependent typing removes the isolation between types, and code. My question is this: would an implementation of dependent typing for a primitive recursive language(not Turing-complete) be guaranteed to halt? Thanks!

Not only is the answer to this question yes, but this is exactly the strategy that modern implementations like Coq and Agda take! To be precise, the type checker has to preform evaluation when deciding definitional equality so it would, if given the right language, be possible to write an infinite loop and ask whether a term was definitionally equal to another term. Because of the way we define definitional equality in most cases, this demands evaluation.
The calculus of constructions (CoC) is actually strongly normalizing. Type checking of CoC is decidable and requires no termination checking. But to make this theory more useful, we add the ability to define inductive types and recursions over them. This way, we get the calculus of inductive constructions (CIC), which Coq is based on.based on). You can view this as a means of adding terms to our language that add computational content that would otherwise not be present.
Note than many inductive types can already be represented in CoC without the aid of CIC, but CoC cannot represent everything CIC can. Coq and Agda both have termination checkers which accept all primitive recursive functions, and both also allow encoding the Ackermann function. You can see more about this in a question I once asked here on a characterization of the class of primitive recursive functions.
Good refrences on Agda's termination checker are

http://www2.tcs.ifi.lmu.de/~abel/foetus/
http://wiki.portal.chalmers.se/agda/pmwiki.php?n=ReferenceManual.TerminationChecker

There is also a lot of work on sized types to provide an alternative to termination checking as well as some work on abstract interpretation based solutions. Currently however, checking for a generalization (see Foetus) of primitive recursion is as far as the state of the art in mainstream implementations goes — at least as far as I am aware.


Compiler backend generated from declarative description of the architecture Is it possible, given a declarative description of an architecture's register layout and instruction semantics and machine code encodings, to autogenerate a compiler back-end?

If so, has anyone ever done this?

João Dias; Norman Ramsey: "Automatically Generating Back Ends Using Declarative Machine Descriptions", Proc. ACM Symp. Principles of Prog. Lang., (POPL-37):403-416, 2010.

I think this goes a bit farther than you asked for, because they're actually looking for good code sequences.  For something a little more basic you could go back to some of Norm Ramsey's earlier work, like: Norman Ramsey; Mary F. Fernández: "Specifying Representations of Machine Instructions", ACM T. Prog. Lang. and Sys., 19(3):492–524, May 1997.

There's a long line of research on trying to automatically generate back ends from simpler descriptions.  Look for papers by Christopher W Fraser, David R Hanson and Todd A Proebsting.


How to prove the following language is not in R Let $c\in \mathbb{N}$. Denote: $L _c= \{ \langle M \rangle \mid \exists _{U \subseteq \Sigma ^* }$ s.t. $|U| $ is infinite and for each $w\in U $ the TM $M$ accepts $w$ within no more than $c$ steps $\} $.

I would like to prove that for any given $c$ the language $L_c \notin R $.

I would like to find a language $L \notin R$ and find a reduction $L \leq L_c$, but Im having trouble as to which $L$ should I aim for.

I tried with $L_{acc}$, $L_{\Sigma^*}$ , but could not find what my reduction should be.

Im not necessarily looking for a complete solution, but even a hint from which language and how my reduction should look like (an idea behind the reduction) would be also great, sonce I feel Im at a loss here and dont know whre to start from.

Hint: This language is actually computable for every $c$. If $M$ terminates within $c$ steps, then it only gets to see at most $c$ symbols of its input, so in some sense its domain is finite.

There are some subtleties here. For example, it might be that there are also infinitely many inputs on which $M$ doesn't stop within $c$ steps. Perhaps it's better to first prove that the following language is computable for every $c$:
$$
L'_c = \{ \langle M \rangle \mid \text{$M$ stops within $c$ steps on all inputs}\}.
$$


Proof that {$a^m b^n$ | m!=n} is not regular I know that the language $\{a^m b^n | n\neq m\}$ satisfies the pumping lemma, but it's still not regular (I have to count the # of a's and b's).
How can I formally prove it?

Suppose $L = \{ a^m b^n : m \neq n \}$ were regular. Then $a^*b^* \setminus L = \{ a^n b^n \}$ would also be regular.

There is a variant of the pumping lemma in which you mark certain symbols of your choice (at least as many as the pumping constant $p$), and then the pumped part is certain to contain at least one of these symbols (and at most $p$). Now consider $a^p b^{p+p!}$ for large enough $p$, and mark the $a$ part. We arranged things so that whatever the length of the pumped part (which must consist solely of $a$s), you can pump it to exactly $a^{p+p!} b^{p+p!}$.

Another possibility is to use the Myhill--Nerode theorem. The words $a^n$ ($n \in \mathbb{N}$) are an infinite set of pairwise inequivalent words: if $n \neq m$ then $a^n b^n \notin L$ yet $a^m b^n \in L$.

Take your pick...


Big-O Time Complexity of nested for loops My gut tells me the time-complexity of the following code is simply O(n^2).  However, I'm not convinced, thinking it could possibly be O(n^3):

cin >> n;
sum = 0;
for (int i = 0; i < n; i++)
    for (int j = 0; j < n * n; j++)
        sum++;

Can anyone provide a distinction, and why?

Thanks in advance.

Hint: What is the value of sum at the end of the code, as a function of $n$? If it is $s$ then the fifth line must have been run exactly $s$ times.


How do I calculate the Nth result of a context-free grammar? Given a context-free grammar and a maximum depth, how do I directly compute the Nth sentence without calculating or caching intermediary sentences?

Take as an example the following grammar:

(from http://www.nltk.org/howto/generate.html)

S -> NP VP
NP -> Det N
PP -> P NP
VP -> 'slept'
VP -> 'saw' NP
VP -> 'walked' PP
Det -> 'the'
Det -> 'a'
N -> 'man'
N -> 'park'
N -> 'dog'
P -> 'in'
P -> 'with'

Given a maximum depth of 4, it will deterministically generate the following 6 sentences:

0 the man slept
1 the park slept
2 the dog slept
3 a man slept
4 a park slept
5 a dog slept

So the brute force way of finding the Nth sentence is to compute sentences 0..N, discard them, then return the Nth. But with a more complex grammar it's wasteful to recompute it every time and it's not possible to hold the current state in memory.

But my question is, is there a way to directly compute the Nth sentence?

Also, is it possible to do the reverse: given a the grammar, depth, and sentence, determent what's the sentences index of all possible sentences.
Something like:

>>> find_index_in_grammar("a man slept", grammar, depth=4)
3

Update

To clarify: traversal order, lexicographical order, or ordering by length is not important as long as it's deterministic. The example above is just one possible ordering that is deterministic and would work.

What I've tried so far is to consider the grammar as a different numeric "base", with its sentences as specific numbers in that base. With the key difference being the "base" varies with the number of possible replacements at each branch in the grammar.

def grammar_index(grammar, index):
    sentence = [grammar.start()]
    while set(sentence) & set(grammar._lhs_index):  # any non-terminals?
        for i, symbol in enumerate(sentence):  # loop for the non terminal
            possible_replacements = grammar._lhs_index.get(symbol)
            if possible_replacements:  # if there is a replacement
                base = len(possible_replacements)  # the len of replacements is the "base"
                rem = index % base
                index = index // base
                replacement = possible_replacements[rem]
                del sentence[i]
                sentence[i:i] = replacement.rhs()
            if index <= 0:
                break
        if index <= 0:
            break
    return ' '.join(str(s) for s in sentence)

So this returns partially generated sentences with some duplicates as well.

Pros: it is deterministic, fast

Cons: has non terminals in the results...

>>> for i in range(20):
...:     s = grammar_index(grammar, i)
...:     print(i, s)
...:
0 NP VP
1 NP saw NP
2 NP walked PP
3 Det park slept
4 NP saw Det park
5 NP walked P Det park
6 Det dog slept
7 NP saw Det dog
8 NP walked P Det dog
9 a man slept
10 Det park saw Det man

The problem is likely hard, by reduction from SAT.

Let $\varphi$ be a CNF. For each clause $C$, we can construct a production which generates all truth assignments falsifying $C$. By going over all clauses, we can construct a grammar for all nonsatisfying truth assignments. For example, if the CNF is $(x_1 \lor x_2) \land (\lnot x_1 \lor x_3)$, the grammar is
$$
\begin{align}
&S \to 00B \mid 1B0 \\ &B \to 0 \mid 1
\end{align}
$$
This grammar generates $2^n$ words iff $\varphi$ is unsatisfiable. Therefore, by querying the $2^n$'th word, we will be able to tell whether $\varphi$ is satisfiable or not, and so solve SAT.


Minimum number of strings to cover entire space within Hamming distance Given $(n, k)$:

What is the minimum number $x$ of (binary) strings such that all $n$-bit (binary) strings are within $k$ Hamming distance of some string?

Is there an asymptotic expansion or lower bound, at least?
A somewhat-trivial lower bound is as follows:

There's $\sum_{i=0}^{k} {n \choose i}$ strings within distance $k$ of a given string.
There's $2^{n}$ strings total.
Each string can be counted no less than once.
So we have a lower bound of: $$x \ge \frac{2^{n}}{\sum_{i=0}^{k} {n \choose i}}$$

Is there an explicit formula that maps an index $1..k$ (or $0..(k-1)$) to these strings? (I am aware that this is likely not unique.)

This is closely related to error-correcting codes, but ultimately distinct. (In an error correcting code you (usually) want to have every string within distance $k$  (or $k/2$, etc, etc) of no more than one codeword, whereas here you want to have every string within distance $k$ of at least one codeword.)

The object you are interested in is called a covering code. While less popular than error-correcting codes, covering codes share many of the same difficulties. In particular, there is little hope for an exact formula for the minimal size of a covering code.


Difference between logic, fuzzy logic, probabilistic logic, quantum logic? I am not sure if the names of these logics are right, but I saw that you can generalize logic with probability theory. Then I found 3 ways of reasoning with probabilistic/smooth logic, Fuzzy, Bayes/probabilistic and quantum. Can someone explain what are the major differences and expressiveness of such logics? Are they useful in normal logic?

Russell and Norvig catalogue a few formal languages in the following table[*]:

\begin{array} {lll}
\hline
\text{Language} &
\text{Ontological Commitment} &
\text{Epistemological Commitment}
\\
&
\text{(What exists in the world)} &
\text{(What an agent believes about facts)}
\\
\hline
\text{Propositional logic} &
\text{facts} &
\text{true/false/unknown}
\\
\text{First-order logic} &
\text{facts, objects, relations} &
\text{true/false/unknown}
\\
\text{Temporal logic} &
\text{facts, objects, relations, times} &
\text{true/false/unknown}
\\
\text{Probability theory} &
\text{facts} &
\text{degree of belief $\in [0, 1]$}
\\
\text{Fuzzy logic} &
\text{facts with degree of truth $\in [0, 1]$} &
\text{known interval value}
\\
\hline
\end{array}

(Note this is within the context of artificial intelligence.)

So the most important difference between fuzzy logic and probabilistic logic seems to be that in probabilistic logic you do not deal with degrees of truth, only degrees of belief.

I couldn't tell you very much about quantum logic other than that it appears to have originated in this paper by Birkhoff and von Neumann.

[*] Russell, S. and Norvig, P. (2009). Artificial Intelligence: A Modern Approach (third edition). Pearson. Chapter 8, First-Order Logic.


Quantum Computing - Relationship between Hamiltonian and Unitary model When developing algorithms in quantum computing, I've noticed that there are two primary models in which this is done. Some algorithms - such as for the Hamiltonian NAND tree problem (Farhi, Goldstone, Guttman) - work by designing a Hamiltonian and some initial state, and then letting the system evolve according to the Schrödinger equation for some time $t$ before performing a measurement.

Other algorithms - such as Shor's Algorithm for factoring - work by designing a sequence of Unitary transformations (analogous to gates) and applying these transformations one at a time to some initial state before performing a measurement.

My question is, as a novice in quantum computing, what is the relationship between the Hamiltonian model and the Unitary transformation model? Some algorithms, like for the NAND tree problem, have since been adapted to work with a sequence of Unitary transformations (Childs, Cleve, Jordan, Yonge-Mallo). Can every algorithm in one model be transformed into a corresponding algorithm in the other? For example, given a sequence of Unitary transformations to solve a particular problem, is it possible to design a Hamiltonian and solve the problem in that model instead? What about the other direction? If so, what is the relationship between the time in which the system must evolve and the number of unitary transformations (gates) required to solve the problem?

I have found several other problems for which this seems to be the case, but no clear cut argument or proof that would indicate that this is always possible or even true. Perhaps it's because I don't know what this problem is called, so I am unsure what to search for.

To show that Hamiltonian evolution can simulate the circuit model, one can use the paper Universal computation by multi-particle quantum walk, which shows that a very specific kind of Hamiltonian evolution (multi-particle quantum walks) is BQP complete, and thus can simulate the circuit model.

Here is a survey paper on simulating quantum evolution on a quantum computer. One can use the techniques in this paper to simulate the Hamiltonian evolution model of quantum computers. To do this, one needs to use "Trotterization", which substantially decreases the efficiency of the simulation (although it only introduces a polynomial blowup in computation time).


Name for data structure I have a data structure that implements the following operations all in $O(1)$:

$\text{insert(x)}$, inserts a value into the data structure and returns a unique key $k$ to the value
$\text{delete(k)}$, deletes the value at key $k$ and returns it
$\text{get(k)}$, returns a reference to the element at key $k$

Internally the storage is simply a contiguous array $A$ of $(x, v)$ tuples. $x$ is either a value or is used to store a freelist. $v$ is a version tag. When $v$ is odd $x$ is a valid item with version $v$. When $v$ is even $x$ is unoccupied and is re-used to store the index of the next unoccupied item after this.

The key $k$ is a tuple of $(i, v)$, an index into the contiguous array and a version. Only when $A[k_i]_v = k_v$ is this key valid and contained in the data structure. Finally, on every insert and delete $A[i]_v$ is incremented.

Now this is very similar to a memory allocator (which returns pointers instead of keys), but the difference is that physical memory locations can be safely re-used here without spurious errors where old pointers point to new items. So from the perspective from the user every key that $\text{insert}$ ever gives is unique.

The question is, what is a good name for this data structure? I've seen similar data structures called "slot maps" in game development, but it's not quite the same. They don't use versioning and support dense iteration through using two indirections (one key -> idx and idx -> item), whereas this data structure can have a sparse memory layout.

It's also very similar to a slab allocator, but again it has added safety of returning permanently unique keys, even when re-using storage.

I ended up settling for Sparse Slot Map. I was wrong to say that slot maps don't do versioning - that depends on the implementation.


Negative weight cycle vs maximum weight cycle I'm having trouble understanding why it's easy to detect negative-weight cycles (Bellman Ford) but hard to find the maximum weight cycle in an undirected graph.

If we negate the weight of each edge, we can easily find if there are any cycles with total weight > 0. However it must not be easy to find if there are any cycles with weight > 1 or else we could repeat with 2, 3, 4 etc until the answer is no.

Is this correct? Why is it so much harder to detect if there exists a cycle with weight > 1 then to find if there is a cycle with weight > 0?

I don't think it's very surprising that finding a single negative-weight cycle is easier than finding the highest-weight cycle. If you ask me to find a negative-weight cycle, I can find any one and, if I give you what I claim is an answer, it's very easy for you to check the sequence of vertices and see that the weight really is negative. But the maximum-weight cycle feels like a very special object. Even if I claimed to have found it how would I convince you that there isn't another cycle with even higher weight?

On the other hand, maybe this intuition isn't helpful, since it's also trivial to check that a given cycle has weight at least 1 or 2 or 17...


Operation on a regular language and context free language Given $L_1$ and $L_2$ over some alphabet:

$L_1@L_2 = \{uv \mid u \in L_1 \land v \in L_2 \land |u|=|v|\}$

The question is: if $L_1$ is regular and $L_2$ is context-free, is $L_1@L_2$ context free?

I've been trying to disprove this but to no avail. So I've been thinking to prove this by buiding a PDA but I can't seem to figure this out.

There is no guarantee that your resulting language will be context free.

Here is a hint for creating a more formal proof.  Try the languages $L_1 = c^*$ and $L_2 = a^nb^n$.  The resulting language, given your additional requirement of $|u| = |v|$ would be $c^{2n}a^nb^n$.

Using the pumping lemma for context free languages, are there two substrings that you can pump indefinitely that will match this language?


Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs I am studying "An Introduction to the Theory of Computation" by Sipser -- there is a problem *3.17 (p.161) which I can not solve.
Any hints (not answers) from which side to attack it?

  Let $B=\{M_1, M_2, ...\}$ be a Turing-recognizable language consisting of TM descriptions. Show that there is a decidable language C consisting of TM descriptions s.t. every machine in B has an equivalent machine in C and vice versa.

Let $M$ be the Turing machine recognizing $B$.
Hint
For a Turing machine, try to encode the running time required for $M$ to accept it into itself, so that one can simulate $M$ on it without going into infinite loop.
Complete Answer

 Let $f$ be a computable bijection from $\mathbb{N}_0^2$ to $\mathbb{N}_0$, where $\mathbb{N}_0$ is the set of non-negative integers.

  Define a state of a Turing machine to be isolated if no state can be transitioned to it and it cannot be transitioned to any state. Obviously adding or deleting isolated states does not affect the function of a Turing machine.

  Define $M_d$ to be a decidable Turing machine, which works as follows on input <$M_w$> where $M_w$ is a Turing machine.

  Compute the number $n$ of isolated states in $M_w$.
  Let $(n_1,n_2)=f^{-1}(n)$.
  Let $M_w'$ be the Turing machine that is almost the same as $M_w$ except it has $n_1$ isolated states.
  Simulate $M$ on <$M_w'$> with at most $n_2$ steps.
  If $M$ accepts, accept; otherwise, reject.

  Consider $M_i$ (recall $M$ accepts <$M_i$>). Suppose $M$ runs in total $n_2$ steps on <$M_i$> and $M_i$ has $n_1$ isolated states. Let $M_i'$ be the Turing machine that is almost the same as $M_i$ except it has $f(n_1, n_2)$ isolated states. Now $M_i'$ and $M_i$ are functionally equivalent, and easy to see <$M_i'$> is accepted by $M_d$.

  On the other hand, suppose <$M_w$> is accepted by $M_d$ and $M_w$ has $n=f(n_1,n_2)$ isolated states. Let $M_w'$ be the Turing machine that is almost the same as $M_w$ except it has $n_1$ isolated states. Now $M_w'$ and $M_w$ are functionally equivalent, and easy to see <$M_w'$> is accepted by $M$.

  So the language deciding by $M_d$ is what we want.


How to count in binary? (basic problem) I am trying to learn the binary number system but I keep coming up against a barrier to my comprehension. To people who are in the know this will no doubt seem an extremely elementary error so please be  kind :). The problem concerns the eighth count. I’m going to explain my reasoning up to that point alongside the counting record in the hope that my error can be pinpointed. Apologies for being long-winded. Here goes…

First count to 1 (from 0)
 We want to continue but have run out of digits. Therefore mark the                     first count with a digit on the left and begin counting from 0 again. Thus:    10 (This shows that the count is accumulative and not simply a repeat of
(1) and is  analogous to starting the tens column in decimal place                  value.)
 Simply count forward in the right column, "carrying" the 1 from the previous count to indicate place value. Thus: 11.
Repeat the procedure at (2), getting the original 1 to budge up and put a zero to the left to show place value. Thus: 100.
Count forward, thus: 101.
Repeat as per (2) and (4). We now have two left columns with 1s as their value and a fresh 0 in the right column, thus 110.
 Simply count forward in the right column as per (1), (3), (5), thus: 111.

Right, the next stage [(8)] is what baffles me. I know that the next number is 1001 but I don’t understand why. Surely if we are following the pattern I have outlined above (and, assuming this is correct) the next number should be 1101, i.e we start a new column as we did when faced with 1 on the right side at (2), (4) and (6). Instead it seems to be that when we max out on 1s (i.e. 111) we have to reset several columns at once. Why am I wrong? I know it will most likely have to do with 2 being the exponent for binary numbers but I can’t make the connection and all web explanations are overly complex. Any help gratefully received.

I don't really understand the algorithm you're trying to use to count. It seems rather complicated and, instead of trying to correct it, I'm just going to start from scratch.

Really, everything is just like decimal, only there are fewer choices for each digit.  Just like decimal, leading zeroes don't alter the value of the number (0123 is the same number as 123 and 0000123) so we can always add leading zeroes if that helps us.

To add 1 in decimal, we just increase the last digit by 1, if it's not already the biggest possible value. If it is the biggest possible value, we replace it with 0 and "carry 1" to the second-to-last digit. What does that mean? Well, it just means that we increase that digit if we can and, if we can't, we reset it to 0 and carry the 1 to the previous digit. Eventually, if we started with something like 999, we'll have to say that 999 is the same thing as 0999 when we need to the 1 past the left-most 9

So, to add 1 in binary, we increase the last digit by 1, if it's not already the biggest possible value, which is 1.  If the last digit is 1, we reset it to zero and "carry the 1", which we do just like we did before.

This means that it goes as follows:

0
1 (Increase the last digit)
10 (We can't increase the last digit, so we reset it to zero and carry the 1. We've run out of digits, so we put a new zero on the left. Then, to carry the 1, we add 1 to that new digit.)
11 (Increase the last digit)
100 (Reset the last digit to zero, carry the 1. Reset the second-to-last digit to zero, carry the 1. No digits remain, so put a new zero on the left and carry the 1 to it.)

Perhaps it was overly complicated to say that we put a zero on the left-end of the number and then increase it; I could have just said that we put a one on the left end and we're done. I used the slightly longer formulation because you can keep using that when you start adding numbers bigger than one.


Enumerators and recognizers I got confused by this a bit... the words of any recursively enumerable language $\mathcal{L}_{RE}$ can be enumerated by an enumerator $E$, i.e. there is an effective procedure (using lexicographic ordering of inputs) for all words $w \in L$ (with $L \in \mathcal{L}_{RE}$) to be printed by $E$.

Now suppose $E$ lists down all words $w \in L$ by taking as input the computation history of a word $w$. The computation history is derived using transitions of a Turing Machine $TM$ that recognizes $L$. $E$ operates by checking if all segments of the computation history are valid given transitions of $TM$. To print $w$, $E$ uses a homomorphism, i.e. by printing the first segment of the computation history. In this case, the set of all words that enumerated by $E$ is equal to $L$.

But if the enumerator $E$ is a Turing Machine itself, call it $TM^E$, is it accurate to say that $TM^E$ recognizes $L$? If true, there seems to be a contradiction since $E$ does not loop - since it can check whether or not a computation history input from a lexicographic ordering follows the transitions of $TM$ and results in $w$.

An enumerator has no input. It works as follows:

Generate the next computation history.
Check if the computation history is valid.
If the computation history is valid, print the corresponding string.
Go to Step 1.

I'm unclear how your $\mathrm{TM}^E$ works. I can image the following possibilities:

On input $w$, $\mathrm{TM}^E$ enumerates all computation histories and see if $w$ matches some computation history. In this sense, there is no contradiction. $\mathrm{TM}^E$ has to endlessly enumerate computation histories if $w$ matches no computation history (i.e. $w\notin L$), so it may loop.
On input $w$, $\mathrm{TM}^E$ firstly constructs the computation history corresponding to $w$... but wait, how do you construct such a computation history while it may not even exist (i.e. $w\notin L$)?
On input $w$, $\mathrm{TM}^E$ checks whether $w$ is a valid computation history, and accepts if it is valid. In this sense, $\mathrm{TM}^E$ does not accept $L$. Instead, it accepts the language of valid computation histories. This language is different from $L$.


Does strong typing contribute to better performance optimization by compiler? Do guarantees provided by the type systems enable better performance optimizations by the modern compilers? I found a 20+ year article suggesting that it would. Also, intuitively speaking, knowing more about the code in advance should also be useful. However, a friend claims that modern JIT compilers make such claim irrelevant. In his words:

This is a paper from 1998. Today, JIT compilers eliminate many of the cases mentioned in the paper for dynamically typed systems. For example, JavaScript uses integer arithmetic for integer types, without knowing the type declarations in advance. I doubt if predeclared types are as significant for performance today as they were two decades ago. Native instruction set and memory management mechanisms seem to have much more influence on performance to me.

What's the situation in modern compilers?

I think your friend somewhat presents a false dichotomy.
I will just give one example: when it first came out, the Self VM was one of the fastest dynamic language implementations. In fact, the Smalltalk VM written in Self that shipped as part of the Self system was one of the fastest Smalltalk VMs of its time, despite being written in a dynamic language (much more dynamic than Smalltalk, Python, or Ruby) and running on top of another VM.
Even more, at the time it was first released, Self was one of the fastest OO language implementations in general, even competing with some C++ compilers of that time.
However, it achieved this performance precisely because of its aggressively optimizing JIT compiler aided by dynamic type inference and type feedback!
It is precisely because JIT compilers have more and better type information than AOT compilers that JIT-compiled language implementations can be so fast.
A JIT compiler can potentially have all the same information available that an AOT compiler has. But, a JIT compiler also has runtime information that an AOT compiler cannot possibly have because of all our favorite impossibility results such as the Halting Problem, Rice's Theorem, etc.
For example, Escape Analysis is equivalent to solving the Halting Problem. So, an AOT compiler cannot know in every circumstance whether a reference will escape the local scope or not, and thus must conservatively allocate it under the assumption that it will escape. A JIT compiler, however, can simply assume that the reference will never escape and compile the code accordingly, and then when it observes the reference escaping at runtime, it recompiles the code. (This is sometimes called Escape Detection.)
Likewise, Class Hierarchy Analysis is equivalent to solving the Halting Problem (in languages with dynamic code loading at least). So, an AOT compiler is limited in its ability to de-virtualize and thus inline potentially overridden methods. A JIT compiler, however, can simply look at the class hierarchy at runtime and see whether the method is overridden or not, and thus potentially inline it. And if it observes a piece of code loaded later that overrides the method after the fact, it can re-compile the code so that the method is no longer inlined but dynamically dispatched again.
So, yes, type information is helpful, and JIT compilers do use type information in their optimizations, including type information empirically collected at runtime that is not available to AOT compilers.
Your friend even uses an example of using type information in their own example! Modern ECMAScript execution engines indeed use type information about numeric values collected at runtime to optimize them even though semantically ECMAScript only has IEEE Std 754-2019 binary64 as its one and only numeric type. (The recently added bigint is a distinct type with distinct numeric literals.) Typically, modern ECMAScript execution engines will segregate numeric values into at least doubles and 53 bit integers, possibly even more.
Similarly, they will detect the type of arrays and represent them as machine arrays (i.e. contiguous pieces of memory) even though semantically, an array is actually just a dictionary whose keys are the strings "0", "1", "2", etc.
The two key differences between an AOT compiler and a JIT compiler are:

The JIT compiler has more information available: it can theoretically gather all the same static information that an AOT compiler can, but it also has runtime information available that the AOT compiler cannot possibly have.
On the flip side, the AOT compiler has "infinite" resources available (it can take as long to compile and use as much RAM as it wants), whereas the JIT compiler is competing with the user program for the same resources while the user is waiting for their program to start.

However, the kinds of information and the kinds of optimizations are mostly the same for both. Both like long stretches of straight-line code, both like type information, etc.
Personally, I believe that the best possible performance will come from an approach that has not yet been heavily explored commercially: use an AOT compiler to crunch out as much static information as possible, and perform heavy and expensive optimizations, but keep all that information around and keep a rich representation of the program. Then, hand this off to a JIT compiler which can use all of the expensively calculated information and the rich representation to even further optimize at runtime.
Real world systems typically work differently. For example, C++ compilers are highly sophisticated, by they typically produce very low-level "anemic" output such as x86 machine code which has no types and loses almost all of the information and intent of the original program. On the other hand, we have typical Java implementations which have sophisticated JIT compilers but very stupid practically non-optimizing AOT compilers.


What does a proof that Co-NP =P entail for the NP versus Co-NP question What I wonder is what exactly would it entail. Would it,for instance imply that P=NP or would there be different consequences,I haven't found any assorted consequences so far in my research.
Thank You,
Akash

$\text{P}=\text{co-NP}$ implies that $\text{co-P}=\text{co-(co-NP)}=\text{NP}$.  But
$\text{co-P}=\text{P}$: you can just swap the accept and reject states of a deterministic Turing machine to complement the language that it decides.


Notation for field access in Algorithm While writing array index in an algorithm $a[i]\gets v$ is conventionally used. Is the notation $a_{i}\gets v$ also used ?

If the algorithm uses struct or equivalent, some notation is required for property access. In some occasions $p(s)$ is used where $p$ is the property. Using $s \rightarrow p$ messes up with the assignment arrow. Using $s_{p}$ looks like $p$ is an index and $p\in \mathbb{Z}^{+}$. Should $s["p"]$ be used ? What is the convention to denote property access in algorithm ?

Is there any reference where I can check different notations of these two scenarios ?

Not everyone follows the same conventions, but I'll describe the ones I see most commonly.  Your experience may vary.

If $a$ is an array, $a[i]$ is typically used, but not $a_i$.
If $(a_1,\dots,a_n)$ is a sequence, $a_i$ is typically used, but not $a[i]$.  Usually sequences are not updateable.
If $a$ is a string, you might see either $a[i]$ or $a_i$; both are common, in my experience.
I have most commonly seen $s.p$ used for property access.  Sometimes I have seen people use $p(s)$ used.

Different sources may follow different conventions.  There is no one right answer.  A good approach is to find a textbook that you like (e.g., CLRS), and then follow the same conventions they use.  Odds are that they have put some thought into choosing consistent and understandable conventions, so they probably have chosen something reasonable.