Prove that A** = A*, where A is a language over Σ* Let $\mathcal A$ be an arbitrary language over $\Sigma^*$

Proof.

To prove, $\mathcal A^{**} = \mathcal A^* $

$\mathcal A^{**} = \left( \mathcal A^0 \cup \mathcal A^1 \cup {...} \cup \mathcal A^n \right)^*$ by definition of Kleene Star

My idea is that Kleene star operation distributes over the union of languages but then, I dont know what to do next.

I need some directions.

Since $L \subseteq L^*$ for all $L$, we have $\mathcal{A}^* \subseteq \mathcal{A}^{**}$. In the other direction, suppose that $w \in \mathcal{A}^{**}$. Then there exists an integer $n \geq 0$ and words $x_1,\ldots,x_n \in \mathcal{A}^*$ such that $w = x_1 x_2 \ldots x_n$. Since $x_i \in \mathcal{A}^*$, there exists an integer $m_i$ such that $x_i \in \mathcal{A}^{m_i}$. Thus $w \in \mathcal{A}^{m_1 + \cdots + m_n} \subseteq \mathcal{A}^*$, and it follows that $\mathcal{A}^{**} \subseteq \mathcal{A}^*$.


Applying minimax tree to this array Please tell me how I should apply minimax algorithm to the array
$$ 15, 12, 14, 16, 11, 13$$
and make a tree?(I understand how minimax algorithm works but I can't apply it to an array)

Minimax is actually applied on a 2D matrix like:

3  5  6  13  8
7  9  2  4   6
4  12 15 16  10

Generally, you have a choice to do, let say it corresponds to one of the columns in the exemple (5 choices). And there is an unpredictable choice (random, opponent choice ...), the row in the example (3 choices). Minimax minimizes the risks by assuming this unpredictable choice will be the worst for you.

In the example, you first compute the minimum on all colums:

3 5 2 4 6

So you finally pick the 5th choice, which guarantees at least 6.

In your problem you have 1 dimension, then minimax has no sense on it. Or you can degenerate it saying there is no unpredictable variable and just pick the maximum.


Existence of particular/specialized halting oracles It is known that there does not exists an oracle $H$ which given any pair $(M,I)$ where $M$ is a machine and $I$ is an input (possibly still a machine) to have $H(M(I)) = YES$ if $M(I)$ halts and $H(M(I)) = NO$ if $M(I)$ does not halt. This was proven by Turing. However, this can be shortly written as
$$ \not\exists H \hspace{0.5cm} \forall M,I \hspace{0.5cm} H(M(I)) = \begin{cases} YES, \hspace{0.3cm}M(I)  \text{  halts }\\ NO, \hspace{0.4cm} M(I) \text{ doesn not halt}\end{cases}$$
But is it possible to have the following:
$$ \forall M,I \hspace{0.5cm} \exists H_{M,I} \hspace{0.5cm} H_{M,I}(M(I)) = \begin{cases} YES, \hspace{0.3cm}M(I)  \text{  halts }\\ NO, \hspace{0.4cm} M(I) \text{ doesn not halt}\end{cases}$$

Yes. Given a machine $M$ and input $I$, one of the two things happens:

$M(I)$ halts.
$M(I)$ does not halt.

We may not be able to predict or compute which of these happens, but one and only one happens simply by rules of classical logic.
Now to show that $H_{M,I}$ exists we consider two cases:

If $M(I)$ halts then $H_{M,I}$ exists because we can take it to be a machine that immediately halts and outputs "yes".
If $M(I)$ does not halt then $H_{M,I}$ exists because we can take it to be a machine that immediately halts and outputs "no".

Note: we proved existence of $H_{M,I}$, but we did not give a way of computing $H_{M,I}$ from $M$ and $I$, which is impossible as that would give us the halting oracle (exercise).
So, what Yuval said.


Is there any theoretically proven optimal compression algorithm? Is Huffman coding always optimal since it uses Shanon's ideas?
What about text, image, video, ... compression?

Is this subject still active in the field? What classical or modern references should I read?

Huffman coding is optimal for a symbol-to-symbol coding where the probabilities of every symbol are independent and known before-hand. However, when these conditions are not satisfied (as in image, video), other coding techniques such as LZW, JPEG, etc. are used. For more details, you can go through the book "Introduction to Data Compression" by Khalid Sayood.


Is $\Omega^\infty (g(n)$ a more general version of $\Omega(g(n))$? In CLRS, one question defines $\Omega^\infty(g(n))$ such that:
$$f(n) = \Omega^\infty (g(n)) \iff \exists c \in \mathbb{R}^+ : \text{for infinitely many integers } n, 0 \leq cg(n) \leq f(n) \ .$$

My question:
What does it mean by "infinitely many integers"? Does it mean $\{n : n \in \mathbb{Z}\}$ or does it just mean some infinite subset of $\mathbb{Z}$ (say, for instance, every odd positive integer)?

If the latter is true, then why is $\Omega^\infty$ even useful? I'm struggling to find out what knowing the behaviour of $f(n)$ for some arbitrary infinite scattering of integers could possibly achieve.

If the former is true, why do we care about what a function $f(n)$ does for small $n$ (i.e. for $n < n_0$)? Isn't the whole point of asymptotics that we're looking for the behaviour of functions as they approach infinity?

Can someone give a bit of context to the definition of $\Omega ^\infty$, because at the moment, it just seems a very contrived definition.

The phrase "for infinitely many integers" means "for an infinite set of integers". This strange definition is what you get when you negate little $o$. That is, for any two functions $f,g \geq 0$, either $f = o(g)$ or $f = \Omega^\infty(g)$. In some cases $f = \Omega^\infty(g)$ is enough to derive certain consequences, and so is a useful property.


What's wrong with my pumping lemma proof? The language $L = \{0^{2n} \space |\space n \ge 0 \}$ is obviously regular – for example, it matches the regular expression $(00)^*$. But the following pumping lemma argument seems to show it's not regular. What's gone wrong?

I've found a way of splitting an input $s$ as $xyz$ satisfying the requirements of the pumping lemma but it's not true that $xy^iz\in L$ for all $i$. Doesn't that mean the language isn't regular?

In more detail, the pumping lemma for regular languages says that, if a language $L$ is regular, there exists pumping length $p \ge 1$ such that any string $s\in L$ with $|s|> p$ can be written as $s = xyz$ such that:

$\lvert y \rvert \ge 1$
$\lvert xy \rvert \le p$
$xy^iz\in L$ for all $i \ge 0$.

So, let's take $s = 0^{2p}$ and write it as $s=\epsilon\, 0 \, 0^{2p-1}$ (i.e., $x = \epsilon$, $y = 0$, $z = 0^{2p-1}$). This satisfies 1. and 2. But, taking $i=0$, we get $xy^iz = \epsilon\, 0^0\,0^{2p-1} = 0^{2p-1}$, which isn't in $L$ because its length is odd. So it looks like the language isn't regular after all.

This is intended as a reference question illustrating a common mistake in the use of the pumping lemma for regular langauges. Thanks to Ariel for spotting the issue in the original version of the question.

The problem is in the quantifiers. The pumping lemma says that any string $s$ with $|s|\geq p$ can be written as $xyz$ such that the three properties hold. It doesn't say that every way of writing it as $xyz$ that makes the first two properties hold also makes the third one hold.

For the language $\{0^{2n}\mid n\geq 0\}$, we proceed as follows. First, note that we must have $p\geq 2$, since if $p=1$, we're forced to take $x=\epsilon$, $y=0$, $z=0^{2p-1}$ and you already showed in the question that this doesn't work.  So, with $p\geq 2$, we can write $s = 0^{2p}$ as $s=\epsilon\,00\,0^{2(p-1)}$ ($x=\epsilon$, $y=00$, $z=0^{2(p-1)}$). We have $|\epsilon00| \leq p$, $|00|>1$ and $(00)^i\,0^{2(p-1)}\in L$ for all $i\geq 0$. Thus, there exists some way of decomposing the string as $xyz$ that satisfies all the properties, even though the first decomposition you thought of didn't work.

To show that a language isn't regular, you need to show that every decomposition into $xyz$ that satisfies the first two properties fails to satisfy the third one. It's not enough to just show that one decomposition doesn't work.

To understand why the pumping lemma is the way it is, it helps to think about the proof. If a language is regular, it is accepted by some DFA. That DFA has some number of states: call it $p$. By the pigeonhole principle, whenever that DFA reads a string longer than $p$, it must visit some state twice: say state $q$. Now, $x$ is the part of the input read upto (and including) the first visit to $q$, $y$ is the part read after the first visit and upto and including the second (which must be at least one character) and $z$ is the rest. But now you can see that $xz$ must be accepted: $x$ takes you from the start state to $q$ and $z$ takes you from $q$ to an accepting state. Likewise, $xy^iz$ must be accepted for any positive $i$, since each repetition of $y$ takes you from $q$ back to $q$.  Note that the decomposition of the input into $x$, $y$ and $z$ is entirely determined by the automaton which is, in turn, determined (but not uniquely) by the language. So you don't get to choose the decomposition: if the langauge is regular, some decomposition exists; to show that a language is not regular, you must show that every decomposition fails.


Listing all prime numbers less than an integer N I am trying to solve this problem listing all prime numbers less than an integer but using the smallest amount of memory.

Is it possible to solve this problem using a smaller amount of memory?

int main ()
{
    int n = 10000;
    for (int i=2; i<n; i++)
        for (int j=2; j*j<=i; j++)
        {
            if (i % j == 0)
                break;
            else if (j+1 > sqrt(i)) {
                cout << i << " ";
            }
        }
    return 0;
}

Yes, but only after we have stated what is considered memory used by an algorithm or program.

For this particular problem, I would like to use one of the simplest choices. The memory used by the program is the extra or temporary space used excluding the input and output. Furthermore, each variable (that does not share its storage with others) uses a unit of space. One might argue the output should count towards memory usage. My point is to let us choose a usage model so that we can concentrate on the most relevant and interesting part, although in another situation, how to reduce the memory used by the output might be the more significant part.

Here is the snippet that use 3 units of memory, where I remove the call to sqrt(i). Each of $n$, $i$, $j$ uses 1 unit of memory. I comment out the output code to make it clear that its memory usage is not considered.

int n = N; // N should be given elsewhere
for (int i=2; i<n; i++)
    for (int j=2;; j++)
    {
        if ( j*j > i) {
            // cout << i << " ";
        }  else if (i % j == 0)
            break;
    }

But wait, how can we check j*j > i? Even if we assume the computing machine can compute j*j magically without using extra memory, it still needs to store the result of j*j so as to compare with i. So it is only reasonable that we add 1 or more unit of memory usage here. Then how about i % j? We would like add 1 or more unit of memory usage here.

If we dig deeper, we will ask whether those 2 and 0 in the program count towards memory or not. We may have to ask during the program execution, doesn't it need to use some space to remember where it is executing and how to jump around? If those memory are needed, can we reuse them during different execution time?

The more we study this way, the more uncertain the answer becomes. This is, in fact, the truth. It is almost impossible to get an accurate usage of memory theoretically unless we have an accurate model of storage and computation specified down to the bit. When we do have that accurate model, an accurate analysis to the bit may become so tedious and distracting we might lose the big picture.

The way out to get a healthy picture is the big $O$ or $\Theta$ notation. We will simply say that this program use $O(1)$ or $\Theta(1)$ memory. That is, for a reasonable model of storage and computation, there is a constant $C$, for any give $N$, the program will use less than $C$ units of memory. In practice, we usually mean a small or reasonable $C$.

By the way, the program in the question misses primes 2 and 3.


Algorithm to find a simple path with maximum weight less than a constant in DAG Given a weighted directed acyclic graph $G=(V,E,W)$, where the weights are non-negative and are on the vertices. I am searching for a simple path of maximum total weight, but this total weight should not exceed a given constant $K$.

Perhaps my question is elementary but I cannot find any solution. Indeed, it is well known that finding a simple path with maximum weight in $G$ is polynomial, but by adding the fact that this total weight should not exceed a given constant $K$, will the problem remain polynomial? because we need to keep at each node the set of path lengths that can be reached by the next vertices.

Since there is no negative weight, you only need to keep at each node the set of path lengths no more than $K$. Because $K$ is a constant, you only keep a constant number of path lengths at each node. Hence, the algorithm remains polynomial-time.


Matrix multiplication randomised verification - error probability Let s  say we have an algorithm that takes as input 3 matrix A,B and C

  $$ \text{Input} :A,B,C \in Mat(n\times n)$$
  $$\text{Question} :\text{is } A\cdot B=C$$

the algorith works as follow ;

$$ \text{if }(A\cdot B)_{ij}=C_{ij} \Rightarrow A\cdot B=C  $$
$$ \text{if }(A\cdot B)_{ij} \neq C_{ij} \Rightarrow A\cdot B \neq C  $$

with random chosen $i$ and $j$  .

I have to find in this case the error probrabilty. Can someone please give me some hints.

This problem looks a bit like  the freivalds algorithm, somehow i think i have to drive a trick with it so solve mine but i am not sure .

If that's the whole algorithm, only one iteration, then the only bound on the probability of error you can get is that it is smaller than $1-1/n^2$.

Hint 1) Notice that the algorithm only can fail when it enters in the first case you describe, why?

Hint 2) What is the worst possible case for A, B and C so you get the worse probability of error?


Is it known whether the MD5 algorithm is surjective? Does MD5 map to all possible 128 bit numbers? To put it another way:
For every 128 bit number y, does there exist at least one x for which md5(x) = y?

The answer probably is yes, for arbitrary x, and probably no proof exists. However, feel free to prove me wrong :)

But what if I impose some kind of limit on x, e.g. x <= x_max? Of course, for very small x_max the answer is no. But what is the minimum value of x_max for which the answer likely becomes yes? Or the maximum value for which the answer can be shown to be no?

I'm not really interested in the exact value for x_max, rather in the approximate order of magnitude.

Q: Does MD5 map to all possible 128 bit numbers?

Taking into account the facts that MD5 accepts input of the arbitrary length, the output is "only" 128 bits, and the algorithm itself which behaves similarly to random functions, I would expect that the all outputs are possible. However, without any strong mathematical evidence, this is merely a speculation, or in the best case, the hunch.

  Q: The answer probably is yes, for arbitrary x, and probably no proof exists.

Exactly, there is no proof (currently). Proving that MD5 is surjective would require either one of these:

Brute force check - taking into account coupon's collector problem, it takes something like 10^40 inputs to hit all 128-bit outputs. Assuming again that MD5 behaves similarly to random function, that should be enough to verify in the case that MD5 is surjective.
Concrete mathematical proof - eventual proof of surjectivity should be able for arbitrary 128-bit number y prove that there exists some input x such that MD5(x) = y. That should require deep mathematical analysis of MD5 function and it would probably shed some light on reversing this hash function. Even though MD5 is far from desirable hash function, it is still not known how to predict the input based on the given output.


Simple Hamiltonian cycle reduction HAMPATH

  Input: An undirected graph $G$ and 2 nodes $s, t$
  Question: Does G contain a Hamiltonian path from $s$ to $t$?

  HAMCYCLE

  Input: A undirected graph $G$ and a nodes $s$
  Question: Does $G$ contain a Hamiltonian cycle starting at $s$?

I wish to show HAMCYCLE is NP-hard. I'll show this by doing $HAMPATH \leq_p HAMCYCLE$ since HAMPATH is known to be NP-complete.

add edge from t to s

if theres a hampath then the reduction shows there a hamcycle

if theres a hamcycle then clearly theres a hampath

Above is my entire attempt. I was wondering if I could call on $t$ in my reduction since its not used as a input in HAMCYCLE?

Instead of cutting corners and jumping right in to a reduction, I believe you would profit from actually stepping back and clarifying the logical basis of your argument.

Given an instance $(G, s, t)$ of HAMPATH, your reduction produces an instance $(G', s')$ of HAMCYCLE, as you have described. To prove your reduction works, you need to show:
$$(G, s, t) \in \textsf{HAMPATH} \iff (G', s') \in \textsf{HAMCYCLE}$$
for every instance $(G, s, t)$ of HAMPATH, where $(G', s')$ is uniquely determined as a function of $(G, s, t)$ (the function in case being your reduction).

To prove this equivalence, you first fix an arbitrary instance $(G, s, t)$ of HAMPATH (which may be a "yes" or a "no" instance). $(G', s')$ is then uniquely determined by $(G, s, t)$. Then, you either prove the two sides of the equivalence (as you have done) or show that, if $(G, s, t)$ is a "yes" instance, then $(G', s')$ is a "yes" instance and, if $(G, s, t)$ is a "no" instance, then $(G', s')$ is a "no" instance. Although usually the latter is preferred, either is fine; you can reference all of $G$, $s$, $t$, $G'$, and $s'$ in both cases since they are all fixed.

The problem with your argument is that you obtain a cycle $(s, \dots, s)$ and then (correctly) reason there is a node $t'$ right before $s$ which makes it a Hamiltonian cycle (and gives you a Hamiltonian path from $s$ to $t'$). However, because $t$ is fixed, there is no guarantee that $t' = t$. You still need to consider the case $t' \neq t$ and show this gives you a Hamiltonian path from $s$ to $t$ even if you delete the edge $(t, s)$ (since this yields $G$ from $G'$).

Unfortunately, you will not be able to. Consider, for instance, the case where $G$ is a cycle $(s, t, v, s)$. Then both $G$ and $G'$ obviously have a Hamiltonian cycle which starts and ends at $s$, but there is no Hamiltonian path from $s$ to $t$ in $G$; the only way to reach $t$ from $s$ (by a path) is the single edge $(s, t)$, which fails to visit the vertex $v$.

You will have to modify your reduction. Hint: Try to find a way of forcing $G$ to not have a Hamiltonian cycle in the first place (and note this implies $t' = t$ above).


Difference between specifying argument and not in NumPy Running these lines in Colab:
import numpy as np
size  = 2**13
%timeit np.random.normal(size=(size, size))
print("-----------")
%timeit np.random.normal((size, size))

yields:
1 loop, best of 5: 2.67 s per loop
-----------
The slowest run took 7.05 times longer than the fastest. This could mean that an intermediate result is being cached.
10000 loops, best of 5: 16.3 µs per loop

Why is the difference in computational time between these two lines of code so large? In my mind they should be the same.

This due to the order of optional arguments. Perhaps this example can explain thing for you:
def foo(x = 1, y = 2, z = 3):
    print((x, y, z))

In [1]: foo()
(1, 2, 3)

In [2]: foo(4)
(4, 2, 3)

In [3]: foo(z = 4)
(1, 2, 4)

Now looking at help about np.random.normal, we get:
In [4]: help(np.random.normal)
Help on built-in function normal:

normal(...) method of mtrand.RandomState instance
    normal(loc=0.0, scale=1.0, size=None)

That means that since loc is the first optional argument, np.random.normal((size, size)) is interpreted as np.random.normal(loc = (size, size)) and not as np.random.normal(size = (size, size))


What is the correct complexity of All paths from Source to Target DFS solution? The question: "Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order."

The DFS solution is described here. https://leetcode.com/articles/all-paths-from-source-to-target/

I feel like the author likely got the time complexity analysis wrong. I would have asked the author themselves, but from the discussion below, they don't really respond to questions. So, what is the correct time complexity analysis for this problem, and how to derive it?

First recall the definition of topological sort: given a DAG (Directed Acyclic Graph) with vertices $1, \dots n$ define the vector $\operatorname{TS}[1, \dots n]$ such that $\operatorname{TS}[1, \dots n]$ is a permutation of $1\, \dots n$ and $i < j$ implies that a path from node $\operatorname{TS}[j]$ to $\operatorname{TS}[i]$ does not exist. This vector can be computed in $\mathcal{O}(n)$ time.

Consider the algorithm exposed in your link, and denote with $T(n)$ the time complexity of that problem for a DAG of size $n$, then it holds:

$$ T(n) = \sum_{i=1}^{n}T(i).$$

Proof: If you call your function on $\operatorname{TS}[i]$ its execution consists of recursively calling that function on the sub-graphs composed of vertices reachable (following a directed path) from $\operatorname{TS}[j]$ such that $(i, j) \in E$. Exploiting the topological sort property it turns out that

$$\{\text{Vertices Reachable from} \operatorname{TS}[j]\} \subseteq \{\operatorname{TS}[k] \;|\; k = j + 1, \dots n\}.$$

Moreover $(i, j) \in E \implies i < j$, then you are calling the same function on smaller instances of the same problem, satisfying the equation above.

Finally, considering that $T(0) = T(1) = 1$ the complexity is $T(n) = \mathcal{O}(2^n)$ that solves that recursion.


Efficient compression of simple binary data I have a file containing ordered binary numbers from $0$ to $2^n - 1$:

0000000000
0000000001
0000000010
0000000011
0000000100
...
1111111111

7z did not compress this file very efficiently (for n = 20, 22 MB were compressed to 300 kB).

Are there algorithms that can recognize very simple structure of data and compress file to several bytes? Also I want to know what area of CS or information theory studies such smart algorithms. "AI" would be too broad, please suggest more concrete keywords.
Notion of symmetry should play fundamental role in data compression, but search queries "symmetry in data compression" and "group theory in data compression" surprisingly return almost nothing relevant.

Sure, of course there are algorithms.  Here is my algorithm:

First, check if the file contains ordered binary numbers from $0$ to $2^n-1$, for some $n$.  If so, write out a 0 bit followed by $n$ one bits followed by a 0 bit.
If not, write out a 1 bit, then write out the 7z-compression of the file.

This is extremely efficient for files of that particular structure.

The point is: there is no free lunch in data compression.  You might be able to build a compression algorithm that compresses one type of file well, at the cost of compressing others worse.  But, if you know a priori something about the nature of the files you will be compressing, you can optimize your algorithm for that particular type of file.

The area is "data compression".  See our data-compression tag, and read textbooks on data compression.


Complexity Reduction Analysis I am struggling to grasp fully grasp complexity reductions, I have this example that I am working through and can not fully comprehend how to determine the complexity of one algorithm given the complexity of another, either $ O$ or $\Omega$
The example algorithm is:

  Input: left: array of n integers
  Input: right: array of m integers
  Input: n,m:  size of left and right
  Output: TwoSumSplit(left, right,t)
1 mix = Array()
2 for i = 1 to n do:
3  Add 3(left[I]) + 1 to mix
4 end
5 for i = 1 to m do:
6  Add 3(right[I]) + 1 to mix
7 end
8 return TwoSum(mix,3t)

the complexity of TwoSumSplit(TSS) is $\Theta(n + m + TS(n + m))$

My question is how can I determine the complexity of an algorithm given the complexity of another, for example:
$if\space TS(n) = O(n)$
$if\space TS(n^2) = O(n^2)$

then what can be determined of the complexity of TSS?

Using the notation of $A \le_p B$,I know that "TSS surrounds TS", along with rules such as reducing from unknown to known for $O$ and reducing from known to known for $\Omega$. I've determined that from statements like $if\space TS(n) = \Omega(n)$ nothing can be determined using these stated rules/observations.

Source: Dr. Hendrix; Analysis of Algorithms. Spring 2017 USF

If $TS(n) = O(n)$ then $TSS(n,m) = \Theta(n+m)$.

If $TS(n) = O(n^2)$, then all we can say is that $TSS(n,m) = \Omega(n+m)$ and $TSS(n,m) = O(n^2+m^2)$.

How did I reach these conclusions? First of all, clearly $TSS(n,m) = \Omega(n+m)$. If $TS(n) = O(n)$ then $TS(n+m) = O(n+m)$ and so $TSS(n,m) = O(n+m + O(n+m)) = O(n+m)$. Altogether, $TSS(n,m) = \Theta(n+m)$.

If $TS(n) = O(n^2)$ then $TS(n+m) = O((n+m)^2) = O(n^2+m^2)$, since $(n+m)^2 = \Theta(\max(n,m)^2) = \Theta(n^2+m^2)$ (you might prefer the middle form to the one on the right). Therefore $TSS(n+m) = O(n+m+O(n^2+m^2)) = O(n^2+m^2)$.


Is the NP-hardness Proof with One Way Implication Correct and Why? A problem $\Pi$ is NP-hard if I can prove this:

a known NP-hard problem $\Pi'$ reduces to $\Pi$ in polynomial time; and
$f(x) \in \Pi\iff$  $x \in \Pi'$.

If I can show only one way implication, that is  $f(x) \in \Pi\Rightarrow$  $x \in \Pi'$. Is this reduction known, correct and why?

For me it is correct because, if I had an algorithm for $\Pi$ then I would use it to solve $\Pi'$. Therefore, $\Pi$ is at least as hard as $\Pi'$ then $\Pi$ is NP-hard.

Consider the following two wrong "reductions" from $SAT$ to $L = \{1\}$.  Let $\phi$ be a $SAT$ instance.

We "reduce" every $\phi$ to 1, i.e. $f(\phi) = 1$. Now we have $\phi \in SAT \Rightarrow 1 \in L$. But $L$ is clearly not NP-hard.

Next we "reduce" every $\phi$ to 0, i.e. $f(\phi) = 0$. Now we have $ 0\in L  \Rightarrow \phi \in SAT$. But again $L$ is clearly not NP-hard.

Thus we can see that for a correct reduction we need a proper if and only if condition: $x \in \Pi' \Leftrightarrow f(x) \in \Pi$.

If we have a reduction as above, and if we know that SAT is NP-complete (in other words a hard problem), we have two corollaries from this.

1) Any language can be reduced to SAT. So every language can be reduced to SAT and then to $L$, so $L$ is also NP-complete (now we know that $L$ must also be a hard problem).

2) Any algorithm for membership of $L$ can be used to solve membership to SAT. So if we have an "algorithm" for $L$ then so do we have an "algorithm" for SAT. The algorithm will work this way. From $\phi$ we will construct $f(\phi)$ and then apply our "algorithm" to $f(\phi)$. If answer is YES then $\phi$ is also satisfiable, and if answer is NO then $\phi$ is not satisfiable.

So from 2) we can see that an algorithm for $L$ is applicable for $SAT$. But vice versa is not true. Any algorithm for $SAT$ (polynomial or exponential) can not be used for $L$ using this reduction (there might be other ways but not using just the above reduction). Notice the uncovered region in $L$. So this is what is meant by cryptic comment: solution of $L$ $\Rightarrow$ solution of SAT.


Büchi automata: accepting run vs. runs with arbitrarily many final states I am currently learning about Büchi automata and have a combinatorial question about the acceptance condition.

Let $A=(Q,\Sigma,\delta,q_0,F)$ be a (nondeterministic finite) Büchi automaton and $w=w_1w_2w_3\ldots$ an infinite word over $\Sigma$. Suppose that for each natural number $n$ there exists a run

$q_0 \xrightarrow{w_1} q_1 \xrightarrow{w_2} q_2 \xrightarrow{w_3} \cdots$

that contains at least $n$ occurrences of a final state.

Does that imply the existence of an accepting run for $w$, i.e. one with infinitely many final states? I expect that the answer is no, but cannot find a counterexample. Hints would be appreciated.

Consider $\Sigma = \{0,1\}$ and $w = 1101001000100001\ldots$, i.e., there is an increasing number of zeros between two ones. Now consider the automaton with states $q_0, q_1$, and $q_A$ where $q_A$ is the only accepting state. On input $0$, always stay in the current state. On input $1$ allow the following transitions: In state $q_0$, either stay in $q_0$ or go to state $q_A$; in state $q_A$, go to $q_1$; in state $q_1$, stay in $q_1$.

If the transition $q_0 \to q_A$ happens at a position in $w$ that is followed by $n$ zeros, $q_A$ will occur exactly $n+1$ times in that run. Since $w$ contains $n$ consecutive zeros for all $n$ but no infinite sequence of zeros, this is a counterexample to your statement.


Why are non-deterministic Buchi automata factorially succinct when compared to deterministic Rabin Automata? I am trying to demonstrate the following idea without success.

  There are infinitely many $n \in \mathbb{N}$ such that: There is a
  non-deterministic Buchi automata of size $n$ such that a deterministic Rabin Automata
  accepting the same language has at least $n!$ states.

Any help would be appreciated

This is Theorem 1.30 in the chapter "Omega-Automata" in the book "Automata, Logics, and Infinite Games: A Guide to Current Research" edited by Erich Grädel, Wolfgang Thomas and Thomas Wilke. They have a proof as well (and a literature referene to the original publication).

Note that instead of the nondeterminstic Buchi automaton having $n$ states, it needs to have $O(n)$ states to make the proof work. The problem is then defined slightly differently to make this precise.

Note that it is a bit confusing if you write "Buchi automata" and "deterministic Rabin automata" in the same question if the former are meant to be "nondeterministic Buchi automata". There is ample work both on deterministic and non-deterministic Buchi automata, so spelling out which variant is meant is important.


Is finding dead-end nodes in NL? Given a directed graph $G$ and two nodes $s,t$, decide whether there is some node $s'$ such that $s'$ is reachable from $s$ while $t$ is not reachable from $s'$.

I am wondering whether this problem is in NL.

It is in NL.  Here is the outline of a possible proof:

If you already fix s′, you can check whether s′ satisfies your condition or not in NL.  Reachability is easy, non-reachability is by the Immerman–Szelepcsényi theorem, and taking the AND of two conditions is easy.
Because there are only polynomially many possibilities for s′, you can test these possibilities one by one until you find the right s′ or find out that no such s′ exists.  Alternatively, you can guess s′ by using nondeterminism.


Converse of halting problem It is well known that if some computing apparatus is Turing-complete, then the halting problem is undecidable for that computing apparatus. However, is it true that if the halting problem is undecidable for some computing apparatus, then it is Turing-complete?

Here's an artificial counterexample:

Define an apparatus "aTM" like a TM, except that any input word which does not start with the symbol $a$ is immediately rejected. For words which do start with $a$, the TM is run as usual (and can accept/reject as usual).

This is clearly not Turing complete since it can't recognize the language $\{b\}$, which is decidable by a TM. Still, the halting problem on aTMs is as hard as the halting problem  for TMs.


P = NP clarification Let's use Traveling Salesman as the example, unless you think there's a simpler, more understable example.

My understanding of P=NP question is that, given the optimal solution of a difficult problem, it's easy to check the answer, but very difficult to find the solution.

With the Traveling Salesman, given the shortest route, it's just as hard to determine it's the shortest route, because you have to calculate every route to ensure that solution is optimal.

That doesn't make sense. So what am I missing? I imagine lots of other people encounter a similar error in their understanding as they learn about this.

Your version of the TSP is actually NP-hard, exactly for the reasons you state. It is hard to check that it is the correct solution. The version of the TSP that is NP-complete is the decision version of the problem (quoting Wikipedia):

  The decision version of the TSP (where given a length L, the task is to decide whether the graph has a tour of at most L) belongs to the class of NP-complete problems.

In other words, instead of asking "What is the shortest possible route through the TSP graph?", we're asking "Is there a route through the TSP graph that fits within my budget?".


How to build tree from graph with specific property We are given connected undirected graph of $n$ nodes and $m$ edges. On each node one integer(value) from $0$ to $n-1$ is written.

We need to build tree such that for each node $i$, all nodes in the subtree of $i$ should be reachable from $i$ by going only through edges with values greater than $i$.

Such tree is always rooted at $0$ since all vertices can be reached from $0$.

For example, for the given graph:

(5, 1), (1, 2), (1, 3), (3, 4), (3, 0), (5, 2)
The tree we are looking for is rooted at 0 and its edges are:
(0, 1), (1, 2), (1, 3), (2, 5), (3, 4)

I have heard that this is solvable with using disjoint data set structure however I couldn't find a way how to properly find a way to connect the components.

In a connected component, the minimum node can reach any other node without passing by a lower index node. As your initial graph is connected, the node 0 can indeed reach any other and is the perfect root for your tree.

For any connected component, you keep the index of the node it is attached to. Initially, there is none as 0 will be te root.

Once you considered the minimum node of a connected component, you can remove it as no other node in the CC may use it. Let's call this node $k$, you add $k$ to its place in the tree you are building, as child of the node index of the connected component.

Then either the connected component is still connected and its new index is $k$, either it is cut in several connected components, all having $k$ as index.


how to find all negative weight cycles(elementary circuit) in a strongly connected directed graph? I can use Bellman-Ford to get some of the elementary negative weight cycles in a graph. It's not guaranteed to always get all of them.
(Elementary Cycle: A cycle is elementary if no vertex but the first and last appears twice.)
But I want to find ALL elementary negative weight cycles. Even taking each vertex as the source will not always get ALL negative weight cycles.
Take this graph for example:

With Bellman-Ford, starting from any vertex, I can only get one cycle "U→H→U".
The cycle "U→S→U" is always missing.
Is there any algorithm with which I can find all negative weight cycles reliably?

My current strategy is:

first enumerate all elementary cycles. I use the hawick algorithm which is already implemented in the c++ boost library.
sum all the weights of edges in each cycle and then check if the sum is negative.


Meaning of the "why not" modality from linear type theory? In linear type theory there is a modality written ! where !T can be read as "infinite copies of T".

According to ncatlab, there is a dual to this modality which is sometimes written ?T and referred to as the "why not" modality. What is the meaning of this modality? How does ?T behave as a type?

First off, one thing I'd recommend is reading Filinski's Linear Continuations for ideas on how to interpret linear connectives (note, the ? modality got typeset as Γ in that for some reason).

In that paper, he uses the modality as part of the interpretation of call-by-name into linear logic. The idea is that you can kind of think of the non-modal types $T$ as being total, while $?T$ adds the possibility of divergence. If you want an analogue of "infinitely many copies of $T$", then it's, "zero or one $T$".

But of course, it's not like $1 + T$. It's more like a partiality monad living in an otherwise total language.


Necessary conditions for proving If f(n) = O(g(n)), then is log(f(n)) = O(log(g(n))) I am learning about algorithmic complexities and I read that  if f(n) and g(n) are asymptotically positive functions and if  $f(n) =O(g(n))$ then the relationship $log(f(n)) = O(log(g(n)))$ holds.

I would like to know what are the necessary and sufficient conditions for this relation to hold?

It's obviously wrong. As an example take f(n) = 2, g(n) = $1 + e^{-n}$.

log f(n) = 1, log g(n) ≈ $e^{-n} / \log e$.


Modeling the problem of finding all stable sets of an argumentation framework as SAT As a continuation of my previous question i will try to explain my problem and how i am trying to convert my algorithm to a problem that can be expressed in a CNF form.

Problem: Find all stable sets of an argumentation framework according to Dung's proposed framework.

Brief theory: Having an argumentation framework AF, with A the set of all arguments and R the set of the relations, a stable set is a set which attacks all arguments not in their set and there is no attack relation between arguments in the stable set.
Example:

Let's say we have an argumentation framework AF ,A={1,2,3,4}(arguments of AF) and attack relations R{1,3} and R{2,4}.
It's obvious that the set {1,2} is a stable extension of the framework because:

a)it attacks all arguments not in their set (3 and 4)

b)it's conflict free(no attacks between arguments in the set) because argument 1 does not attack argument 2 and the opposite

My exhaustive abstract algorithm:

argnum=number of arguments;

Ai[argnum-1]=relation "attacks" ,where 1<=i<=argnum

P[2^argnum-1]=all possible relations that can be generated from all the arguments

S[2^argnum-1]=empty; where S are all the stable sets

j=0; //counter for while
k=1; //counter for counting stable sets
while j<2^argnum-1
    if P[j] attacks all arguments not in P[j](check using Ai[])
        if all arguments in P[j] are conlfict-free
            S[k++]=P[j];
        end if
    end if
    j++;
end while

I want to solve the above problem either by transforming the above algorithm to CNF or by using a different algorithm and finally use a SAT Solver(or anything similar if exists) give CNF as input and get stable sets as output.

I wonder if someone can give me any feedback of how i can transform any algorithm like the above to CNF in order to be used into a SAT Solver.

I decided to use precosat.

Finding a stable argument set is equivalent to finding an independent set in the directed graph of argument attacks, with the added restriction that some member of the set must be adjacent to each vertex in the graph not in the independent set.  The problem is at least as hard as the indepependent set decision problem and is thus NP-hard.  The decision version of the stable argument set problem is reducible to Boolean SAT as follows:

Input: Given a set of $n$ arguments $ARG_{1}$ to $ARG_{n}$, let the SAT propositional variable $ATTACK_{i,j}$ be true if $ARG_{i}$ attacks $ARG_{j}$.

Output: Let $INDSET_{1} ... INDSET_{n}$ be a new set of propositional variables. $INDSET_{i}$ will be true in the SAT solution iff $ARG_{i}$ is part of the stable set found.

Generating the clauses:

For every pair of variables $INDSET_{i}$, $INDSET_{j}$, add clauses that require

$\overline{(INDSET_{i} \land INDSET_{j})} \lor (\overline{ATTACK_{i,j}} \land \overline{ATTACK_{j,i}})$.

These clauses prohibit any stable set argument from attacking another.
Let $NEEDATTACK_{1} ... NEEDATTACK_{n}$ be a new set of propositional variables.  For each $INDSET_{i}$ variable, add clauses that require

$INDSET_{i} \oplus NEEDATTACK_{i}$

These clauses record which arguments must be attacked by the stable set arguments.
Let $GOTATTACK_{1} ... GOTATTACK_{n}$ be a new set of propositional variables.
For each $GOTATTACK_{j}$ variable, add clauses that require

$GOTATTACK_{j} = (INDSET_{1} \land ATTACK_{1,j})$ $\lor$ ... $\lor$ $(INDSET_{n} \land ATTACK_{n,j})$

These clauses record which arguments have been attacked by the stable set arguments.
For each $GOTATTACK_{i}$ variable, add clauses that require

$NEEDATTACK_{i} \oplus \overline{GOTATTACK_{i}}$

These clauses require that every argument that needed to be attacked by some stable set argument was in fact attacked.

The Boolean expressions can be converted to circuits and from there to CNF using Tseitin transformations.

To obtain all the stable sets, when the SAT solver returns a set of $INDSET$ variables, you must construct a CNF clauses that forbids that solution and append it to the CNF formula.  Rerun the solver and it will either find a new solution or report that the formula is now unsatisfiable.  If "unsatisfiable" is reported, then you know you've found all the stable sets.  If a new solution is found, construct another CNF clause to forbid that solution, append it to the formula and run the solver again.


Is every file an integer amount of bytes? I'm not sure whether I'm asking on the right site, since all the other questions seem to be a lot more abstract and theoretical. If I should remove the question, please tell me.

Are all files on my computer an integer amount of bytes? That is, does every file on my computer consist of an amount of bits divisible by 8? Or are there files that are, for example, 300 bits (37 and a half byte), or 301 bits (37.625 bytes)?

Follow-up question: does this mean that every file can be 'read' using a program that reads ASCII encoded files? (Of course the output would be nonsense, but the program shouldn't notice any difficulties, right?)

Yes, every file has an integer amount of bytes. In fact, most file systems deal with blocks or clusters of bytes. If cluster size is 64KB a file may claim to take up 250KB, but it will actually take 4 clusters or 256KB. This reduces the problem of fragmentaton (now fragments can only get so small, and there can only be so many of them) and the problem of addressing (how big do addresses need to be to access any byte in your 500GB drive? Now the addresses can be shorter by 16 bits).


Construction of the complement of universal Turing machine - where is the catch? This is pretty fundamental but I'm getting confused. Let $U$ be the Universal Turing Machine and $L_{u}$ the language it accepts which is recursively enumerable. Obviously we are not able to construct the machine for its complement i.e. for $\bar{L_{u}}$, otherwise the whole theory crashes but still let's try. Let $V$ be a Turing Machine constructed the same way as $U$ but with the final states switched i.e.: on input code $\langle M, w \rangle$ it simulates $M$ on $w$ but if $M$ accepts $w$ then $V$ rejects $\langle M, w \rangle$ and if $M$ rejects $w$ then $V$ accepts $\langle M, w \rangle$ (implicitly if $M$ loops then $V$ loops). So the language that $V$ accepts is $\bar{L_{u}}$, isn't it? There must be a flaw in this construction but where?

Let V be a Turing Machine constructed the same way as U but with the final states switched

This construction won't work. This is a pattern in automata theory, by the way: for deterministic deciders, flipping final states provides a new proof for closure against complement. For all others, it usually fails.

Here, observe that your semi-decider $U$ of L is, by definition, of the form:

  Accept after finite time if $w \in L$; loop otherwise.

With your construction for $V$, you get:

  Reject after finite time if $w \in L$; loop otherwise.

This is not a semi-decider for $\overline{L}$!

Intuitively, you can not flip a non-termination; you don't get the result you would flip!


Looking for books on creating and understanding theorems targeted at Computer Science In studying logic to understand verifying programs I have found that there are books on logic targeted at Computer Science e.g.

Logic in Computer Science: Modelling and Reasoning about Systems
Mathematical Logic for Computer Science
Computability and Logic
Handbook of Practical Logic and Automated Reasoning

With regards to books on understating theorems targeted at Computer Science I find only one that may fit. As I don't have the book I can't say for sure.

Handbook of Logic and Proof Techniques for Computer Science

Are there any books for understating theorems targeted at Computer Science? In other words are there books for understating syntax, semantics and construction of theorems that don't rely on a heavy math background and that give examples more from the world of computer science and explain in a style more natural to a person in computer science.

EDIT

After seeking more on this topic I have come upon the phrases "informal mathematics" and "mathematical discourse" which are starting to turn up useful info from Google. In particular the following: Understanding Informal Mathematical Discourse found at Understanding Informal Mathematical Proofs

Algorithm Design, by John Kleinberg and Eva Tardos looks like it may be what you want. Here's the description on Amazon:

  Algorithm Design introduces algorithms by looking at the real-world problems that motivate them. The book teaches students a range of design and analysis techniques for problems that arise in computing applications. The text encourages an understanding of the algorithm design process and an appreciation of the role of algorithms in the broader field of computer science.

However, since the fields of computer science and mathematics are so closely related, you really should take the time to understand the math side of things. This looks like it could be a good starting point though


Correctness proof of the algoritm to generate permutations in lexicographic order The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
Find the largest index l greater than k such that a[k] < a[l].
Swap the value of a[k] with that of a[l].
Reverse the sequence from a[k + 1] up to and including the final element a[n].

(from https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order)

I would like to know a (possible formal) proof.

One can try to come up with the algorithm by oneself (thereby proving its correctness) after incremental understanding of: (a) how to define a permutation as "larger" (lexciographically) than another one, (b) what really the very next permutation of $P$ "looks like" compared to $P$ (how/where it differs from $P$). Once we find-out some properties, we may be able to write this algorithm ourselves.
Some outline:

define the "lexicographic order" of permutations $P_1$ and $P_2$. Say, $k$ is the very first index at which they differ. Then the "order" of their elements at index $k$ decides the "lexicographic order" of $P_1$ and $P_2$.

So what should be the smallest and largest permutation of array $a$ ?

Suppose array $a$ currently holds permutation $P$. Say $P'$ is the very next permutation of $P$ in the lexicographic-order, and they first differ at index $k$. Now, use the definition in (1) and the observation in (2) to find out what is the structure of elements in $P/P'$ at index $k$ and after it. You can argue that:

elements in $P$ after $k$ must form a decreasing-sequence (call it $S$).
element in $P$ at $k$ must be smaller than the largest element of $S$, which is $a[k+1]$.
due to above, we must have an element $a[l]$ in $S$ which is the smallest element in $S$ larger than $a[k]$. In $P'$, this element must appear at index $k$.
so the remaining (after $k$) elements of $P'$ are simply $S$ with $a[l]$ removed and $a[k]$ added.
these remaining (after $k$) elements of $P'$, must be in increasing order (for $P'$ to be the smallest possible, but larger than $P$). The 4th step in the posted algorithm is simply obtaining this increasing order by reversing the existing decreasing-sequence $S$ (now modified via swap, but continues to remain decreasing).

(For further details, refer to section "Lexicographical Order" in this).


Efficient algorithm to find minimum steps to cover all the given points in infinite 2D grid? Problem statement: You are in an infinite 2D grid where you can move in any of the 8 directions :

(x, y) to
(x+1, y),
(x-1, y),
(x,   y+1),
(x,   y-1),
(x-1, y-1),
(x+1, y+1),
(x-1, y+1),
(x+1, y-1)

You are given a sequence of points. Give the minimum number of steps in which you can cover all of them. You start from the first point.
Example:

Input : [(0, 0), (1, 1), (1, 2)]
Output : 2

My approach:

For each pair $0\le i\le N-1$ in the list find its subtraction with  $\forall{j}$ except $i\neq{j}$.
Sort the list of resultant subtractions.
Selection of each pair in the list corresponds to the subtraction in increasing order & keep counting $\max(x_{2}-x_{1},y_{2}-y_{1})$ till the end.

Now,

If it is correct it's complexity is $\Theta(n^{2}\log n)$ because of subtraction between $\frac{n(n-1)}{2}$ pairs + sorting in $n^{2}\log n$. Is there any better efficient algorithm? (Updated from Prateek's answer)

Actually I did not get exactly what you are trying to do in Step 1 but complexity of this algorithm should be $O(n^{2} log(n))$ because you will get $(n*(n-1)/2)-c$ elements i.e $O(n^{2})$ elements and then to sort them you will get $O(n' log(n'))$ complexity where $n'=O(n^{2})$.

Their is a full proof solution for this problem and it also has complexity of $O(n^2 log(n))$.

Step 1. Lets assume all co-ordinates are nodes from 1,2.....N.First find
 distance b/w all the vertices in O(n^2).
Step 3. Find minimum spanning tree which can be formed using Prim's
 algorithm or Kruskal's algorithm whose complexity is O(E log(E))
 where 'E' is the number of edges and in our case E=n^2.

Hope that helps.


Need help constructing a Deterministic Finite Automata with AT MOST I am stuck with constructing an DFA that has at most in it.

The question I am stuck with is:

  Design an DFA that accepts all strings over {0, 1} that contain at most two 00’s and at most three 11’s as a substring.

An answer in a form of a graph would be perfect but if someone can explain in plain words, I will appreciate that as well.

You can use states of the form $(i,j)$ where $i$ counts the number of 00s and $j$ counts the numbers of 11s read so far.


What is a space constructible function? I've searched this and was not able to understand the answer.

What's the idea/intuition behind this? What's the purpose and why is it important?

And considering the wikipedia explaination, specifically this part:

  outputs the binary (or unary) representation of f(n), while using only O(f(n)) space

Why does it matter that the binary representation doesn't exceed O(f(n)) space?

And what does it mean to not exceed that space? Why is the function f(n) = c not space constructible?

Sorry if this has been asked before but I didn't find it.

The space used by a Turing machine is the total number of cells that the head (or heads, if a multitape machine) of the Turing machine has ever visited. A function $f(n)$ is space-constructible if there is a Turing machine that on input $1^n$ outputs the binary representation of $f(n)$, and while doing so only visits $O(f(n))$ cells. Note that $O(f(n))$ is an upper bound on the visited cells, not on the length of the representation.

Whether constant functions are space-constructible or not according to this definition depends on the Turing machine model. If the input and output are on the same tape, then a Turing machine space-constructing $c$ should first erase the input $1^n$ and then write the binary representation of $c$. Unfortunately, this takes $n$ space rather than $O(c) = O(1)$ space. If, in contrast, the input is on a special read-only tape and the output is on a special write-only tape (as is the case for log-space machines), then there is absolutely no problem to (fully) space-construct $c$.


What does it mean for a grammar to be LR(0)? I am unsure what it means for a grammar to be $X$. More specifically, what it means for a grammar to be LR(0).
For part of an assignment I had to form the DFA for a grammar, which I had no issues with. And then I have been asked whether the grammar is LR(0).
My guess is yes, but not because I understand exactly what it means. I would assume it isn't if, when creating the DFA I came across some strange behaviors that prevented the DFA making any sense (if you know what I mean/if I'm making any sense).

A bottom-up parsing technique, used for parsing most context-free grammars is LR(k): L indicates that the input is parsed from left to right, R indicates that in the parsing process a rightmost derivation is produced; the number k indicates how many lookahead symbols are used.
An LR parsing scheme consists of: input, output, stack, a parsing program and a parsing table divided into two parts (actions (shift, reduce) and goto).
The idea is that the parsing program reads characters from an input buffer one at a time and uses the stack to store strings of the form s0X1s1X2s2...smXm where s0 is the initial state, the only one present at the beginning of the computation on the stack, while sm is the state at the top of the stack. Each Xi is a grammatical symbol while each si is a symbol that identifies a state. Each state describes the information contained in the stack before it; the combination of the state at the top of the stack and the current input symbol is used to index the parsing table and to determine the parser's shift-reduce decisions.
Given a grammar, to prove that this is LR(0) builds the DFA of viable prefixes.
The first prefix is always S' -> .S because we consider the grammar increased. Then follow the rules to build the LR(0) parsing table.
A grammar is LR(0) if each position in the parsing table LR(0) contains at most one element.
Furthermore, the LR(0) languages all enjoy the prefix property. So if a language does not have this property, we can immediately say that it is not LR(0).
If the grammar is ambiguous then it cannot be LR(k) for any k.


Language in $R \setminus \mathit{NP}$ I am wondering whether the language $$L_{\textrm{hanoi}} = \{\langle k,s \rangle \mid \text{$s$ is a solution of Tower of Hanoi problem on $k$ rings}\}$$ is in $R\setminus \mathit{NP}$.
I want to claim that there is a Turing machine that solves the problem, therefore, $L_{\mathrm{hanoi}} \in R$, but given a solution to the problem, verifying that it is a valid solution takes $\Omega (2^k)$. However, $2^k$ could be be linear to the length of the input (number and sequence).
Is my solution valid? If not, how can I construct a language in $R \setminus \mathit{NP}$?

We always measure the running time of a machine with respect to input size. For this reason, your language is in P. Given a sequence of moves, you can easily check in polynomial time that the sequence is valid.
You can construct a language in $R \setminus \mathit{NP}$ using diagonalization. This is the content of the nondeterministic time hierarchy theorem.


Asymptotic analysis for machine learning algorithms I wanted to know if it would practical and useful to analyse machine learning algorithms in terms of asymptotic computational complexity.

I have noticed this is very uncommon. However, I believe it would help us compare these algorithms and decide which one to use for a given scenario.

I am also aware that the running time of most machine learning algorithms is highly dependent on the data. For example, gradient descent algorithm can iterate significantly more times on certain data sets than others.

Considering this, what would be a nice complexity measure for comparing machine learning algorithms?

Well, first let's clarify the following. Asymptotic Complexity and real life situations are different. Please take a look at this Question.

Now, machine learning is a very hard topic to explore precisely the asymptotic complexity of your algorithms. If we think machine learning as linear algebra, then the asymptotic complexity is the complexity of multiplying matrices. In the area of machine learning, the most important thing is not so much the complexity, but the efficient use of GPUs and TPUs. Let's say you need to train a model for Natural Language Understanding and you use LSTM, GRU and CNN (CNN ?!). Each algorithm has its own complexity because each one does easier or harder calculations. Unfortunately there is no metric such as Model's Accuracy / # of computations. But we all can agree that two LSTM can vastly vary on their speed depending on how good use of GPUs and TPUs they make.


How powerful are CFGs that allow an infinite number of rules? I was wondering recently what would happen if we'd allow context-free grammars to have an infinite number of rules. Clearly, if we'd allow arbitrary such infinite sets of rules, every language $L$ over some alphabet $\Sigma$ could be described by a CFG $G = (\{S\},\Sigma,R,S)$ with $R = \{S \rightarrow w  \mid w \in L \}$. But what if we restrict $R$ to such sets of rules that can be created by context free grammars?

For that purpose, given a set of nonterminals $N$ and terminals $\Sigma$, let us view rules not as elements of $N \times (N\cup \Sigma )^*$, but as strings over the alphabet $R_{(N,\Sigma)} = N \cup \Sigma \cup \{\rightarrow\}$. Now my question is, if we define an infinite rule CFG to be a tuple $G = (N, \Sigma, R, S)$ where

$N$ is a finite set of nonterminals
$\Sigma$ is a finite alphabet
$R$ is a set of rules of the form $A \rightarrow w$ with $A \in N$, $w \in (N \cup \Sigma)^*$ such that there is some CFG $G'$ over $R_{(N,\Sigma)}$ with $R = L(G')$
$S \in N$ is the initial nonterminal

and we define $L(G)$ for such infinite rule CFGs just like it is done for CFGs, what is the relation between the class of languages generated by infinite rule CFGs (let's call that class $irCF$), the class of context-free languages $CF$ and the class $RE$?

Obviously, we have $CF \subseteq irCF \subseteq RE$, but is $irCF$ equivalent to one of these classes (or some other class)?

Suppose we take the metagrammar $G'$ and factor it by two-symbol prefixes. In other words, for each $A \in N$ construct  $G'_A$, the left-derivative of $G'$ over the string $A \to$. That will produce a (finite) set of (finite) metagrammars, each one producing all the (possibly infinite) productions for some $A \in N$.

Now, construct the grammar $G''$, whose rules are the union of all the rules in the $G'_A$ grammars (with non-terminals renamed to avoid collisions), along with $A \to S_{G'_A}$ for each $G'_A$, where $S_{G'_A}$ is the start non-terminal for $G'_A$. The non-terminals for $G''$ include $N$ and all the non-terminals for each $G'_A$; the start non-terminal is the start non-terminal of $G$, and the terminals for $G''$ are precisely the terminals for $G$. I assert (without proof) that $G''$ is a finite grammar for the same language, since the derivation process isn't affected by the origin of the rules; it is just a string substitution over an alphabet.

If the above proof outline is valid, $CF$ and $irCF$ are the same.

As I alluded in a comment, there are more interesting examples of two-level grammars, including Van Wijngaarden grammars and the various attempts which have been made to create more manageable formalisms without losing all of the additional power.


What is rightmost sentential forms? I'm solving some past job interview problems.
I met an embarrassing question about compilers.

The question is :

  Consider the following grammar, with start symbol $E$:

  \begin{align*} E &\rightarrow E \ast E\\  &\quad \mid E ~/~ E\\
 &\quad \mid E + E\\  &\quad \mid E - E\\  &\quad \mid (E)\\  &\quad
 \mid a \mid b \mid c \mid \ldots \mid x \mid y \mid z \end{align*}

  The following strings are legal derivations from this grammar:

  $a \ast b + c$
  $( a - b ) \ast c$
  $a ~/~ ( b – c)$

  Which of the above are rightmost sentential forms?

When I was an undergraduate student, I learned that rightmost(leftmost) sentential form is result of rightmost(leftmost) derivation.
so, I think if $1,2,3$ are legal derivations form above grammar then absolutely all of $1,2,3$ are rightmost sentential form.
If I'm correct, above question is very worthless.

Is there any counter example that is not rightmost sentential form of the grammar $G$ although it is a legal derivation from $G$?

OR

Is there another definition about rightmost sentential form corresponding to above question? I have googled "rightmost sentential form" but there are few results and most of them is the definition that I already know.

I found other answers here confusing, so let me explain it clearly here-
Definitions:

A sentential form is any string derivable from the start symbol. Note that this includes the forms with non-terminals at intermediate steps as well.
A right-sentential form is a sentential form that occurs in a step of rightmost derivation (RMD).
A sentence is a sentential form consisting only of terminals

The examples in your question are all sentences. And since any way of derivation (including RMD) ultimately leads to a sentence, technically all sentences are right-sentential as well as left-sentential forms. So there isn't any counter example which you asked for.
Clarifying Examples : Page 2 of this link


Subspace clustering with random transformation One approach for clustering a high dimensional dataset is to use linear transformation, and the most common approaches are PCA and random projection (where random projection arises from the Johnson-Lindenstrauss Lemma). I was wondering why we can't use other random transformation  s like when our transformation matrix $R$ was drawn from a uniform distribution?

It is possible that choosing $R$ according to a uniform distribution with zero mean constitutes a Johnson–Lindenstrauss random projection (i.e., it approximately preserves distances). See for example a paper by Achlioptas which suggests three distributions that definitely work: a zero-mean Gaussian, a random $\pm 1$, and a specific distribution on $\{0,\pm 1\}$. It is probable that using the methods in the paper, the case of the uniform distribution can also be analyzed.


Why does SAT-UNSAT $\in NP \implies NP = coNP$ I was reading this post about the DP completeness of the problem SAT-UNSAT (both are well defined in this post). The answer added a note at the end that states the class complexity DP differs from NP, unless NP = coNP.
I fail to see why.
I searched and I came across multiples posts such at this one and that one that prove that if SAT-UNSAT is in coNP, then NP = coNP. But unless the fact that SAT-UNSAT $\in NP \implies$ SAT-UNSAT $\in coNP$ (which I do not see), then those proofs are not exactly what would help me. The same goes for this question, I would need SAT-UNSAT $\in coNP$.
Question : Considering the first question (and the answer associated), if the problem SAT-UNSAT $\in NP$, why does NP = coNP.
My take :
Well, I can see that the problem SAT-UNSAT is NP-hard and coNP-hard. If SAT-UNSAT $\in NP$, then SAT-UNSAT is NP-complete. This implies things such that the problem UNSAT (which is coNP-complete) is NP-hard since we can reduce UNSAT to SAT-UNSAT which is NP-complete. That's all I got and that doesn't really help.
I'd appreciate any clarification on the subject. Thanks to you all

Suppose that $X$ is a coNP problem which is NP-hard.
Let $A$ be any problem in NP. Since $X$ is NP-hard, there is a polytime reduction from $A$ to $X$. Since $X$ is in coNP, this shows that $A$ is in coNP.
We have shown that $\mathsf{NP} \subseteq \mathsf{coNP}$. Now suppose $B$ is in coNP. Then $\overline{B}$ is in NP, and so in coNP. Hence $B$ is in NP. This shows that also $\mathsf{coNP} \subseteq \mathsf{NP}$, and so $\mathsf{NP} = \mathsf{coNP}$.


Coercing a list of nodes into the most probable tree Suppose that we have an RTF document which contains sections and sub-sections. The sections and subsections all have headings that are visually marked up (e.g., bold and italic), but the document structure is not made explicit (i.e., we have a linear flow of text). From the section headings, we wish to automatically determine the most likely document structure.

For titles on the same sectioning level, we know that they probably have the same kind of markup, and they probably increment in numbering, but we don't know exactly what they should look like (e.g., bold/italic; arabic/roman; how deep subsectioning goes), and their relatedness may be fuzzy (the author might forget a number in a sequence, for instance 1. First section, Second section, 3. Third section).

To make things more explicit, we can assume assume that we have a features vector fs with a fixed number of features, that combines linearly into a fitness function f(fs) = w₁ f₁ + w₂ f₂ … wₙ fₙ, given a weight vector ws. The fitness function is arbitrary, this is just to make the problem explicit.

So from list G:

We wish to create a tree G' such that:

G' maintains the preorder relations of G
G' maximizes some fitness function f(G'), where f calculates how alike nodes are that are children of the same parent (same markup; incrementing numbering).

(root not displayed)

My question: does this problem reduce to another well-known problem?

This problem reminds me of a lot of stuff I've seen before, from finding the best path through a DAG to hierarchical clustering, except nothing seems to hit the sweet spot in terms of describing or solving the problem.
I guess it's closest to the problem of finding the minimum spanning tree, except calculating the spanning tree score is not as straighforward.

I have thought of my own solution, but I was surpirised that I could find no resources that deal with this problem exactly.

My solution would be a dynamic programming algorithm that attaches a score to each possible tree as a linear function. (Meaning we can cache subtrees without re-calculating everything.) We can learn the constants of our function using some expectation maximization algorithm based on existing document structures.

In the end, I ended up solving my particular problem using Stochastic Context Free Grammars.

There may be some additional cost incurred for production, or otherwise probability operations that you can't express in the CFG. The probabilistic Earley algorithm (Stolcke, 1995) allows us to intervene in the parsing process somewhat by producing callbacks on scannning a token (or predicting / completing).

I have arbitrarily chosen my rule probabilities, but you can train them using the inside-outside algorithm, although that will probably mess up the the soundness of any probability-tinkering callbacks.

Practically, this question lead me to create a Probabilistic Earley Parser for Javascript and for Java. These libraries only allow the user to multiply scan probability given a token at a position the sentence, but it is easy to add other callbacks with more information. Please create an issue in Github if you need this. Also, these libraries do not support training a grammar on a test set (inside-outside), because I did not have time to implement this.

For an exposition of my use case, consider the chapter in my master thesis Automatic Assignment of Section Structure to Texts of Dutch Court Judgments, Inferring a Section Hierarchy


Is there any NP-hard problem which was proven to be solved in polynomial time or at least close to polynomial time? I know this could be a strange question. But was there any algorithm ever found to compute an NP-problem, whether it be hard or complete, in polynomial time. I know this dabbles into the "does P=NP" problem, but I was wondering whether there were any particular instances when people were close to it. I've also heard about the factoring number problem being solved by a quantum computer by Shor's algorithm. Would this count as an algorithm which solved an NP-problem in polynomial time please ? Please do ask if you want me to clarify any parts in my questions. Thanks in advance.

By definition, if you were to find a polynomial time algorithm for an NP-hard (or NP-complete) problem, then $P=NP$. So, short answer is - no.
However, its possible to think instead of solving the problems fully, to approximate a solution, or to solve them randomly. There are attempts at attacking from those points of view, but they are not perfect at all. Randomization isn't known to help "as-is", and many NP-hard problems are known that are also hard to approximate (finding an approximation will yield $P=NP$)
There are also attemps taking a look at notions much stronger than the usual turing machine. For instance, the quantum computer can be considered one. Another obvious example is the non-deterministic turing machines, in which - by definition - $NP$ would be in polynomial time.


Bin packing variant for maximizing value in a bin I'm creating a tool where, given a list of N items that have a volume (v) and a price (p), it should produce a list L that optimally fits as much value as possible into a single bin with a fixed size V. L does not need to contain all N.
My current solution is a heuristic that simply sorts all the items by price-per-volume and iterates over all items, inserting it into the bin if it can. This produces mixed results, so I'm looking to a bin-packing variant to solve this. All of the examples of bin-packing I've seen only seem to optimize for reducing the number of bins.
Is there a specific name for the variant I've described here?

This is the knapsack problem.  It is NP-complete, so there are no algorithms that are both efficient on all problem instances and always optimal, but there are many different techniques that yield different points in the tradeoff between computation time and quality of the solution.


Wrapping the complexities of alternative algorithms: What is the proper "term" for it? Suppose that we have two algorithms for the same task (e.g. search):

AlgC: has bounded worst-case complexity, e.g. O(n.logn)
AlgH: is a heuristic algorithm that is experimentally faster than AlgC, but there is no tight complexity bound for AlgH.

If we want to have an algorithm that is FAST but also has a guaranteed computational complexity, we can use some simple tricks. For example:

We can run AlgC and AlgH simultaneously in an interleaved fashion (or in parallel), and once any of them finishes the task, we stop the other one. This ensures that AlgC binds the complexity, while the execution is as fast as AlgH.
We can also run AlgH for a limited time (e.g. a factor of $n.\log n$) and if it hasn't finished, we run AlgC.

What are such techniques called in Algorithm's community? There should be a proper term for that, right?

Hybrid algorithms.

In sorting algorithms it's rather common, Start with quicksort and if the size of the array is small enough switch to insertion sort (much faster for small $n$). Additionally when the recursion depth becomes too large (threatens to become $O(n^2)$) fall back to heapsort (guaranteed $O(n\log n)$).


Reinforcement Learning: An Introduction, A Gambler's Problem, Exercise 4.7 Solution Currently reading a recent draft of Reinforcement Learning: An Introduction by Sutton and Barto. Really good book!

I was a bit confused by exercise 4.7 in chapter 4, section 4, page 93, (see attached photo) where it asks you to intuit about the form of the graph and the policy that converged. I do not understand why this policy is as it is, and was wondering if anyone has any insight into the problem or answers for this exercise in the book.

I have so far look extensively around Google for answer booklets or any work on the problem to no avail. I could not resolve why s=50 would be a bound with a high a=50 when surely any similar policy could be applied to s=51 with a=49? Any help is much appreciated, many thanks!

The question, as written, certainly suggests that it's a "good policy" to bet a=50 for s=50 , while not "betting it all" with a=49 for s=51.  However, in an e-mail discussion surrounding this (here), Daniel Loeb asks a similar question and notes, "in particular, the simple policy of always making the largest allowed bet is optimal", which would suggest that betting 49 at s=51 would be fine. Andy Barto replies and seems to endorse this conclusion.

Perhaps, if we forget that by construction you can't bet a=51 when s=51, then you could interpret "betting it all" to be betting a=51 when s=51, which is clearly sub-optimal, because your goal is only to reach 100, not to exceed it, and there's no reason to risk complete ruin (loss of the entire stake). So in that sense, it makes sense to "bet it all" when s=50 but obviously not when s>50.  But this is just speculation.


Was it known that $\mathsf{LTIME \subsetneq NLTIME}$? $\mathsf{LTIME = DTIME(\log n), NLTIME = NTIME(\log n)}$.

For example, it seems that NTM can find an element in unsorted array in log-time by use of non-deterministic binary search (check if first half leads to solution and if second half leads to solution).

Obviously, it can't be done by log-time deterministically. I couldn't find anything about this despite the fact this is so simple.

So, was it known and does it imply any consequences? (DFA vs NFA, for example).

I also believe it doesn't imply $\mathsf{P \subsetneq NP}$ because $\mathsf{LTIME}$ is smaller class than $\mathsf{P}$ and inequality between bigger classes is stronger statement (maybe it's some kind of any hierarchy rule). Or does it?

The other answer is quite misleading. The classes $\mathrm{DTIME}(\log n)$ and $\mathrm{NTIME}(\log n)$, usually denoted DLOGTIME and NLOGTIME, do indeed have a sensible and well-accepted meaning in the literature.

When discussing sublinear time classes (deterministic, nondeterministic, alternating, etc.), it is standard to use a Turing machine model that does not have an input tape, but a query tape on which one can write (in binary) the index of an input position, and obtain the input symbol at that position by entering a special state. (The query tape is not cleared or otherwise modified after a query.) This is essentially the same mechanism as used by oracle Turing machines, and the model is sometimes called the random-access Turing machine.

And yes, it is known that $\mathrm{DLOGTIME\subsetneq NLOGTIME}$: a simple NLOGTIME language not recognizable in DLOGTIME is
$$L=\{w\in\{0,1\}^*: \text{$w$ has at least one $1$ at some position}\}.$$
There are unconditional separations like this even for some bigger classes, for example $\mathrm{AC^0}$, whose uniform version coincides with languages recognizable by an alternating TM in time $O(\log n)$ with $O(1)$ alternations.


Minimum number of vertices to remove to bound the largest connected component of a graph I have this problem, maybe anybody could help.

Given a graph $G = (V, E)$ and an integer $k \geq 1$, find the minimum number $l$ of vertices to remove to make the largest connected component of $G \setminus \{v_1, \dots,v_l\}$ have at most $k$ vertices.

I wonder it this problem can be solved quickly (in polynomial time)?

(Related: finding the vertices when $k$ is small)

The optimization version of this problem is known as Graph Integrity, which is unfortunately NP-Hard problem:

  The integrity of a graph G, denoted $I(G)$, is defined by:
   $I(G) = min\{
 |S| + m(G − S) : S \subset V (G) \}$ where $m(G − S)$ denotes the maximum
  order of a component of $G − S$;


Algorithm to choose the best team of 6 Pokémon given a constraint Apologies if this is a duplicate. I searched for some time and the closest I could find was the Knapsack Problem, which does not fit because I have a fixed team size & a different value function.

I have $N \approx 50$ Pokémon, from which I need to choose a team of six to attack an enemy. Each pokemon can survive for a certain time "$t$" against the enemy, and each pokemon does a certain amount of damage per second "$DPS$" to the enemy. I may or may not defeat the enemy, but I would like to optimize the damage I can do to it within the time limit of 300 seconds without my entire team dying.

These data are sufficient to determine the optimal team. The damage done by a team, which fights in order of highest > lowest $DPS$, is the sum
$$Damage(DPS_i, t_i) = \sum_{i=1} DPS_i * \hat{t_i} $$
where $0<\hat{t_i}<t_i$ is the amount of time each pokemon battled for. Typically the first few pokemon will battle until they die ($\hat{t_i}=t_i$), one pokemon will win with a fraction of its health remaining ($0<\hat{t_i}<t_i$), and the rest may never get to battle ($\hat{t_i}=0$).

The optimization problem can be phrased as follows:

Maximize the function $Damage(DPS_1, ST_1, ..., DPS_6, ST_6)$
Given the constraint that $\sum_i t_i >300$

It is clear that this can be brute-forced by checking the damage and survival time of all team combinations. This is not an option because it takes too long.

Another possibility was to start with the highest-DPS team and then make "trades" in order of highest gain in $t$ per sacrifice of $DPS$. However I'm not convinced this will converge to the optimal solution.

I would be very thankful for any suggestions or references to analogous problems.

You could use A* to solve this problem.  A* is designed to optimally search through a state space to solve a problem based on trying to minimize a "cost."

The first thing I'd do is reframe the problem.  Instead of thinking in terms of time and DPS, use time and "damage" by multiplying them together.  I recommend this because that's the term you're trying to maximize.  It'll make it clearer.

Let's define a "state" in this A* algorithm as a team of 0-6 Pokemon, and their total damage.  State transitions consist of adding Pokemon to the team, updating the total damage.  Don't forget that this is a combination problem, not a permutation problem.  Team ABCDEF is the same as team FEDCBA.  The easy way to handle this is to sort by name when adding to the team. (And as a small optimization, if you care, 50 pokemon is small enough to fit into a 64-bit integer, so your teams could be defined by a datastructure as small as an int)

To fit this problem to A*, we have to define a goal function.  The goal function defines an "acceptable" solution, but saying nothing about whether its the best solution.  The goal function is a team of 6 Pokemon that has a total time greater than 300.  This will satisfy your constraint.

We can handle your goal of maximizing damage by using it as our "cost" metric.  A simple way to do this is to say the "cost" is equal to $-damage$, that is to say that it's always a negative number.  A* doesn't mind the final cost being negative.

The last thing you need for A* is the "heuristic underestimate."  You need an estimated cost for finishing out the team that is always an underestimate (a lower "cost" than the real answer, which means a higher damage than the real best answer).  This can easily be constructed by finding a "best damage team" using the remaining Pokemon, ignoring the time constraint.

Put those together, and A* will do the rest.  A* is "optimal," meaning that it is the most efficient algorithm you can come up with given the information provided.  Any more ideal algorithm will need to use more information than what we gave A* (i.e. more than just a cost function and a heuristic underestimate).


How on-chip multithreading prevents cache misses from stalling a processor pipeline? On-chip multithreading is considered a powerful performance enhancer technique that enables a processor to handle multiple threads at the same time. If I got the idea right, multithreading avoids pipeline stalls by processing instructions coming from different threads - since no data dependencies exist between different threads (in the textbooks, synchronization points are dropped for convenience), pipelines will never stall.
However, authors like Tannenbaum state things like that (Structured Computer Organization, 6th Edition, page 562):

  "... when a memory reference misses the level 1 and level 2 caches,
  there is a long wait until the requested word (and its associated
  cache line) are loaded into the cache, so the pipeline stalls. One
  approach to dealing with this situation, called on-chip
  multithreading, allows the CPU to manage multiple threads of control
  at the same time in an attempt to mask these stalls. In short, if
  thread 1 is blocked, the CPU still has a chance of running thread 2 in
  order to keep the hardware fully occupied."

I do understand that a pipeline will never stall if the data dependencies of subsequent instructions are eliminated (that is what out-of-order execution does), but if a memory reference is made by an instruction, the pipeline has to stall until the necessary information is retrieved for the main memory. I mean, no further instructions can be processed until the memory is read and the associated word is loaded. However, Tannenbaum and other authors suggest the opposite: while the word in question is being retrieved, additional instructions from other threads can be issued and that makes no sense to me. Can you folks clarify that? Shouldn't memory accesses prevent the pipeline from accepting new instructions, regardless the thread they come from? Thank you!

It's called "out of order execution".

When one instruction stalls, that doesn't mean the whole pipeline stalls. All instructions that don't depend on this one instruction can continue. Sometimes there is enough work to do even with a single thread to keep all the execution units busy even if one instruction stalls for 40 cycles. But with hyperthreading, you have a whole thread whose instructions are all independent of the stalling instruction, and which can all continue executing.


Time complexity of printing prime numbers within a range? I've written an answer to this question, which asks about the following:
What is the time complexity for the given code that prints prime numbers from start to end? Is it $O(end*\sqrt{n})$?
/**
 * Print prime numbers between start and end inputs
 * Time-Complexity: O(end * sqrt(n))
 * Space-Complexity: O(1) only one value as input
 * @param start, end
 * @return
 */
public void printPrimeSeries(int start, int end) {
    for (int i = start; i < end; i++) {
        if (findPrimeOrNot(i)) {
            System.out.println("The value " + i + " is a prime number");
        }
    }
}

public boolean findPrimeOrNot(int n) {
    for (int i = 2; i <= Math.sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    System.out.println("Enter start number for prime:");
    int startInput = scanner.nextInt();

    System.out.println("Enter end number for prime:");
    int endInput = scanner.nextInt();

    PrimeNoSeries primeNoSeries = new PrimeNoSeries();
    primeNoSeries.printPrimeSeries(startInput, endInput);
}

Notice: That's not my code. It's by mahesh87.
My answer to that is:

In your case $n$ is end - start. In $O$ notation $n$ represents the problem size, which is the range between start and end in your case. In $O$ notation you are interested in the worst case, therefore we can assume that start is always 0. Now $n$ is just an alias for end.
As we have defined $n$, it's obvious that printPrimeSeries is just $O(n)$ (from 0 to end). The method uses findPrimeOrNot that iterates from 2 to Math.sqrt(n), which is $O(\sqrt{n})$. Combining both is $O(n)O(\sqrt{n})$, which is just $O(n\sqrt{n})$.
Notice that the $O$ notation tells you something about the asymptotic behaviour of the algorithm. It doesn't matter too much if there are 2 parameters, at least in this case.
So yes, your assumption is fully correct (ignoring that you've written end instead of $n$).

Other users have proposed that the correct answer is $O((end - start)\sqrt{end})$. I think this is a valid point of view but it doesn't provide any beneficial information in terms of $O$ notation for the given case.
Now my question: What is the formally correct way to describe the time complexity of the given algorithm? Is my reasoning valid or is it just plain wrong?

Both "the time complexity is $O( end \cdot \sqrt{end} )$" and  "the time complexity is $O( (start-end) \cdot \sqrt{end} )$" are correct statements (assuming that arithmetic operations on the involved integers can be performed in constant time).
The second upper bound is tighter in some cases. For example, setting $start=end-10$ the first upper remains unchanged while the second one simplifies to $O(\sqrt{end})$.
Also notice that "In  notation  represents the problem size, which is the range between start and end in your case." is false.
The size of (any reasonable encoding of) the instance is $O(\log end)$.


Is there a name for "density" of information? If we compare multimedia and text, if we have n bytes of text and compare it with n bytes of video, then we would be likely to think that n bytes of text is "more" information than n bytes of video data. Is there a name or measure of this difference in data? Loosely speaking it is a "density" or a "quality" of information per unit.

The classical measure of information is the entropy. Entropy measures the information content of a random source. Consider the case of text files: someone has generated some text, and she wants to communicate this text to you. Since you know that the text is in English, there is no need for her to spell out all the words in full; instead, she can replace each word by its index in some dictionary. Most of the time this scheme will be very efficient, but sometimes she might use uncommon words, and then the scheme could fare less well.

More generally, the entropy of a random source is the average number of bits that need to be communicated in order to guarantee that the receiver decodes the message successfully with high probability. You can check out the formal definition in textbooks on information theory, in Wikipedia, or in Shannon's classical paper from 1948 (still the best source on the subject).

Suppose now that you have a given text file. What is its entropy? Under the definition above, its entropy is zero: if both parties know that the text being communicated is this one particular text, then there is no need to pass any information; there is no uncertainty. Randomness and uncertainty underline the concept of knowledge which entropy tries to capture.

There are at least two ways out of this paradox. The first way is to use a universal compression mechanism, like Lempel-Ziv compression. This is a compression scheme that achieves the entropy (with small error) for all long random sources which are well behaved. If you apply such a universal compression mechanism on a random text file, on average you get roughly the entropy of the random source generating the text file. Therefore one way to estimate the entropy of the mechanism generating your text files is by compressing a given text file.

Another way out of the paradox is Kolmogorov complexity. The Kolmogorov complexity of a given string is the length of the shortest program (in some fixed programming language) that generates the string. This is a notion of complexity which does make sense for a fixed string, with no randomness assumed. However, Kolmogorov complexity is uncomputable, and it cannot even be approximated. While Kolmogorov complexity has some applications in theoretical computer science, in your case the notion of entropy seems more appropriate.


Does Church-Turing thesis also apply to artificial intelligence? By Church-Turing's thesis, it is impossible to design an algorithm to decide the halting problem.

Does the word algorithm in this context include artificial
intelligence or not, that is, does Church-Turing thesis also apply to artificial intelligence?

Is it possible to design an intelligence system in the future to decide this problem, or, by Church-Turing thesis, no AI will also be able to decide the halting problem?

The Church-Turing thesis says that the informal notion of an algorithm as a sequence of instructions coincides with Turing machines. Equivalently, it says that any reasonable model of computation has the same power as Turing machines.

An artificial intelligence is a computer program, i.e., an algorithm. If the Church-Turing thesis holds, then you could implement that algorithm on a Turing machine. Since Turing machines cannot decide their own halting problem, it follows that, under the Church-Turing thesis, artificial intelligences cannot decide the halting problem for Turing machines.


How to use frame based speech features for learning using a neural network classifier? I am doing supervised learning on speech audio files using neural networks. For this purpose, I'll have to extract features from the audio file. But since an audio file is a time varying signal, it is generally divided into multiple frames and then features like MFCC etc are extracted from each frame. So how should I encode my feature vector for each training example(audio file) considering that it will be divided into different no of frames(depending on duration of file)?

Simple neural network as a structure doesn't have invariance across time scale deformation that's why it is impractical to apply it to recognize time series. To recognize time series usually a generic communication model is used (HMM). NN could be used together with HMM to classify individual frames of speech. In such HMM-ANN configuration audio is split on frames, frame slices are passed into ANN in order to calculate phoneme probabilities and then the whole probability sequence is analyzed for a best match using dynamic search with HMM.

To train HMM-ANN you need a segmentation of speech on states. HMM-ANN system usually requires initialization from more robust HMM-GMM system thus there are no standalone HMM-ANN implementation, usually they are part of a whole speech recognition toolkit. Among popular toolkits Kaldi has implementation for HMM-ANN and even for HMM-DNN (deep neural networks).

There are several more complex types of neural networks that are intended to model sequence data. They fall into class of recursive neural networks where connections have cycles. Recursive neural network can process sequences of features of arbitrary length. RNN systems are state of the art systems these days and you can train very accurate recognition system using them, however, training is not simple. You can check RNN toolkits like CURRENNT.

A case of recursive neural networks are long-short term memory networks. They are state of the art system for speech recognition these days. You can learn more about them from the following publication:

http://arxiv.org/pdf/1303.5778.pdf


NX Bit in x86 vs x86_64 I've been reading about how the kernel manages memory in x86 from this popular blog post(https://manybutfinite.com/post/how-the-kernel-manages-your-memory/) and had a few questions.

There is a part where the author describes page table entries and their associated fields. To quote "This lack of a PTE no-execute flag illustrates a broader fact: permission flags in a VMA may or may not translate cleanly into hardware protection. The kernel does what it can, but ultimately the architecture limits what is possible.".

I looked into the kernel source and found that the NX bit in modern systems is actually the most significant bit. Is this because modern hardware now supports NX?

If I tried to execute code on the stack with NX enabled, I crash, but what actually happens? Does the kernel check the page permissions on every execute? That seems really slow. Is it the hardware that knows if I can/cannot execute? If so, how does the hardware know. Does this have anything to do with the CS segment selector?

No, the kernel does not check the page permissions on every execute. If the CPU supports the NX bit, it checks that bit.

Exactly what the CPU does with it and when probably varies between CPU manufacturers and vendors.

Modern CPUs implement a split TLB, one for instructions and one for data. The Core i7, for example, has (ignoring 2MB and 1GB pages for the moment):

L1 data TLB: 4-way set associative, 64 entries
L1 instruction TLB: 8-way set associative, 64 entries
L2 unified TLB: 6-way associative, 1536 entries

I'm not a CPU designer, so this could be wrong, but if it were me, I would check the NX bit when inserting the page table entry into the L1 instruction TLB.

There are a few things you need to consider; for example, the TLB load might be caused by speculative execution, so an exception shouldn't be raised unless instructions on that page are actually executed. But this is nothing special; it's exactly the same behaviour as you would expect if the instruction execution would cause a page fault.

There are architectures which manage TLBs in software or which allow for that possibility, most notably MIPS, Itanium, and some variants of SPARC V9. On such a platform, it is perfectly feasible for the kernel to perform the equivalent of the NX check on every instruction TLB miss.


Is an infinite language of halting TM is in $RE$? in $RE \setminus R$? Let an infinite language, $L$, which contains only TM which halt for every input (meaning, decides some language). Is $L$ in $R$ ? in $RE \setminus R$ ?

I've understood that the answer is: it depends on what exactly $L$ is.

So basically I'm trying to think of two scenarios for $L$ - one which $L\in R$ and one which $L\in RE \setminus R$, but haven't come up with something useful so far.

I'd be glad for help.

The empty set $\emptyset$ satisfies trivially the constraint as all the TM it
contains (actually none) halt for all input. But the emptys set is
also in $R$ since it is very easy to decide whether a TM is in it: the
answer is always NO. But unfortunately, this example cannot be used, because we hav a requirement that the set $L$ of TM be infinite (Thanks to @FrançoisG for reminding me).

So we choose another simple counter example, the set $L_{\emptyset,0}$ of TM recognizing the empty language that halt and reject after 0 steps, but may have a lot of useless states and transitions. There is also an infinite number of such machines, and it is easy to see by inspection of its transitions whether a TM is in $L_{\emptyset,0}$. Thus $L_{\emptyset,0}$ is infinite and recursive.

Since the set $L_{\emptyset,0}$ is recursive, there is a computable bijection   $\phi: \mathbb N\to L_{\emptyset,0}$

Then given any subset $S$ of $\mathbb N$, we can get get with the bijection $\phi$ a subset $\phi(S)\subset L_{\emptyset,0}$ which has the same level of computability.

Thus if we take any non-recursive RE subset $S_{RE\setminus R}\in\mathbb N$, we have $\phi(S_{RE\setminus R})\subset L_{\emptyset,0}$ which is RE but not recursive. And it contains only (Gödel indexes of) TM machines that always halt.

Of course, other levels of computability can be obtained in the same way.


Implications of truncation of numbers when converted into binary I have been posed with a question whereby a computer truncates numbers to x number of digits. Due to this, if this computer is trying to store a decimal number which has a binary equivalent greater than x, it truncates the remaining digits producing a different binary number. However, this binary number is still an 'approximation' of what it should be, but of course is the equivalent of a different decimal number (close to what we were trying to store initially).

What problems can occur due to this incorrect storage of data?

This is specifically about real numbers — integers can be represented exactly. Actually, real numbers can be represented exactly too, at least the one that matter, but this is very inefficient, so for most applications real numbers are represented by a floating point approximation.

By the way, this isn't specific to decimal numbers (numbers that can be represented in base 10 with a finite number of digits after the decimal point). No matter what base you choose, you can only represent a tiny subset of the real numbers (you can't even represent all rationals).

When computing with approximations, it's important to keep in mind that each step of computation may make the approximation worse, so that after many steps it's not always obvious how precise the result is — in some cases, the result is meaningless because the magnitude of the uncertainty is larger than the result. Numerical algorithms need to be constructed carefully to minimize errors due to approximations.

There is a whole subfield of computer science devoted to floating point calculations. To start with, read the classic paper What Every Computer Scientist Should Know About Floating-Point Arithmetic by David Goldberg.


Is automaton not practical in real coding? This question relates with this question and answer.
May I know why "Writing a structured program for any tangle of an automaton is possible in principle, but probably not worth the hassle (translating arbitrary transfers of control into a nice structure -- for some non-trivial value of "nice" -- is a lot of work, and making sure both check out even more so)" and why "it's rarely done in practice"?
Does that mean automaton is not useful in practice (real coding)? In terms of translating the automaton into a code. If not useful, then what is used in practice? Is automaton still useful in problem solving though?

While solving common programming tasks it's usually not helpful to think of an automaton. But there are still many cases where they are applied:

writing small parsers (e.g. parse an integer/float); in order to not forget edge cases drawing an automaton is really helpful; for more complicated parsers grammars are usually a better tool
state machines  are often encountered in game programming (e.g. to manage which animation is currently executing; e.g. press the UP key switches the animation state machine in walking up mode; or to manage game states like if are you currently in-game or in the main menu)
important (string) algos such as the KMP string matching algorithm use an automaton in the background but it's usually represented as a table and quite hard to wrap your mind around

Automatons are models that are theoretically useful to prove properties of language classes. To make proves as simple as possible their definition is also kept simple.
In day to day code you usually stitch together powerful high level data structures to solve your problems and don't think on the low level of e.g. a Turing Machine that would manipulate input on the bit level but rather in terms of higher data types such as ints and lists.
P.S. Automatons are very useful for designing circuits, since circuits work on the bit level and you usually try to minimize the components used it's useful to note down which states your circuit needs and how it should transition between them given some small binary input.