Push Down Automatons "guess" - what does that mean? I realize non-deterministic pushdown automata can be an improvement over deterministic ones as they can "choose" among several states and there are some context-free languages which cannot be accepted by a deterministic pushdown.

Still, I do not understand how exactly they "choose". For palindormes for example every source I found just says the automaton "guesses" the middle of the word. What does that mean?

I can think of several possible meanings:

It goes into one state randomly and therefore might not accept a
word, which actually is in the language
It somehow goes
"every possible way", so if the first one is wrong it tests if any
of the other might be right
There is some mechanism I am not
aware of, that chooses the middle of the word and is therefore not
random, but the automaton always finds the right middle.

This is just an example; what I want to know is how it works for any automaton that has several following states for one and the same state before it.

Quite simply, the mechanism is magic. The idea of non-determinism is that it simply knows which way it should take in order to accept the word, and it goes that way. If there are multiple ways, it goes one of them.

Non-determinism can't be implemented as such in real hardware. We simulate it using techniques such as backtracking. But it's primarily a theoretical device, which can be used to simplify the presentation of certain concepts.

For the palindrome, you can think about it in two ways. Either there's a magical power that lets your machine say "this is the middle of the word, time to switch from pushing to popping", or after reading each letter, it says "I'm going to fork a new process which that this letter is the middle of the word, and see if it finds it's a palindrome. Then in this other thread, I'll keep trying, assuming this isn't the middle of the word".

Another way to think of it is as infinite parallelism. So an equivalent model would be that, instead of choosing a new path, it simultaneously tries both paths, branching off new "processes," succeeding if any are in a final state after reading the whole word. Again, this can't be built using real hardware, but can be modelled with non-determinism.

The interesting thing about nondeterminism is that for finite-automata and Turing machines, it doesn't increase their computational power at all, just their efficiency.


Prove fingerprinting Let $a \neq b$ be two integers from the interval $[1, 2^n].$ Let $p$ be a random prime with $ 1 \le p \le n^c.$ Prove that
$$\text{Pr}_{p \in \mathsf{Primes}}\{a \equiv  b \pmod{p}\} \le c \ln(n)/(n^{c-1}).$$

Hint: As a consequence of the prime number theorem, exactly $n/ \ln(n) \pm o(n/\ln(n))$ many numbers from $\{ 1, \ldots, n \}$ are prime.

Conclusion: we can compress $n$ bits to $O(\log(n))$ bits and get a quite small false-positive rate.

My question is how can i proove that $$\text{Pr}_{p \in \mathsf{Primes}}\{a \equiv  b \pmod{p}\} \le c \ln(n)/(n^{c-1})$$?

The probability $P$ that a uniformly chosen random prime between $1$ and $n^c$ satisfies $a \equiv b \mod{p}$ is the number of primes in this range that satisfy $a \equiv b \mod{p}$ divided by the total number of primes in this range. Writing $[C] = 1$ if $C$ is true and $[C] = 0$ if $C$ is false, and $\pi(x)$ for the number of primes less than $x$:
$$P = \dfrac{\sum\limits_{p\le n^c} [p\text{ prime}] [p \mid (a-b)]}{\pi(n^c)}$$

Since $|a-b| \le 2^n$, there are at most $n$ distinct primes that divide $a-b$. The prime number theorem directly gives an upper bound for the denominator. Thus:
$$ P \le \dfrac{n}{n^c/\ln(n^c) + o(n^c/\ln(n^c))}
     = \dfrac{c \ln(n)}{n^{c-1}} (1+o(1))$$

You won't get an exact bound from an asymptotic version of the prime number theorem. An exact bound, if I am not mistaken, is $\pi(x) \gt \dfrac{x}{\ln(x)}$ for $x \ge 11$. Using this bound, we see that if $n^c \ge 11$ then
$$
P \le \dfrac{c \ln(n)}{n^{c-1}}
$$

Application: we can compress $a \le 2^n$ (which takes $n$ bits to represent exactly) approximately by storing $a \mod p$ for several random prime numbers $p_i$. If we use $k$ primes chosen independently of the value of $a$, then the representation requires $k \, \lceil c\,\log_2(n) \rceil = O(k \log(n))$ bits to store the values modulo every chosen prime. The probability of a collision on each prime is at most $c \ln(n) / n^{c-1} = O(\ln(n)/n^{c-1})$. To evaluate how the precision increases with $k$ would require further analysis.


What is this operator in "The Temporal Logic of Programs" Pnueli 1977? In The Temporal Logic of Programs there is an operator first appearing on page 3 (48) under "Partial Correctness" that looks like an elongated super set symbol. What is it?

It's implication as indicated in en.wikipedia.org/wiki/List_of_mathematical_symbols


Prove that the language L = {a^(m+n) b^m a^n | m, n ≥ 0} ∪ {a^m b^n a^(m+n) | m, n ≥ 0} is not regular In general, how can we go about proving that union of two languages as non regular. In this case, the individual languages can be proved as non regular using pumping lemma. How can we apply pumping lemma to union of two languages ?

Regular languages are closed under finite intersection, use that to your advantage. In this case, the reason the language isn't regular is because it has a $K = \{a^n b^n | n \geq 0 \}$ hidden inside it, pull it out using a regular language as a filter. More explicitly, notice that $K = L \cap a^*b^*$.


How to efficiently get frequency of subranges and update its values altogether? I'm trying to solve the following problem:

There are N notes in an array (2<=N<=105) labeled 0..N-1, all of them initially set to 1. Then there follows Q operations to perform in the array (1<=Q<=105).

The task for each operation is:

Find the most frequent value between the inclusive range [A,B].
Add that value to all elements in the same range. The new values must be in range [0..8], then we take it modulo 9.

At the end, output all array values.

This is the first problem of "Maratona de Programação da SBC – ACM ICPC – 2017" here in Brazil, and I'm trying to solve it in the URI Online Judge site. Time Limit: 1 second.

First I tried SQRT Decomposition because it looked good, but it's not. This week I came up with a few nice ideas to solve it using Segment Tree. I was so sure my code was perfect... but it wans't. Time limit exceeded again.

I don't have Advanced Data Structures classes, I learn those things by myself. So I'm probably lacking some fancy tree structure that would solve this problem really faster. Please, give me some resource to learn such a structure.

Here is an Ideone link to my code. Let me describe the few nice ideas using Segment tree that I mentioned above:

Storing the difference (delta) instead of values. With that I was able to update the ranges without going to the leaf nodes. And to find value of some node, ex: leaf node [0,0] for N=8, I can traverse from root to that node and sum up delta values [0,7].delta + [0,3].delta + [0,1].delta + [0,0].delta.
Store in each node the count of every value [0..8] in its descendants and itself. Because each node represents a subrange, then the frequencies can be precalculated.
Instead of recalculating the subrange array of frequencies, I can rotate it. Ex: If the most frequent note is 3, the previous quantity of values 2 is now the quantity of values 5, and so on... so rotating makes sense instead of calculating the quantities of descendant nodes again.
This is the most brilliant, I think. Instead of rotating, use the value (calculated using delta since root path) to find which index of the frequency subrange array should be treated as the first index 0.

I spent more than twenty hours over this week since the first version of the segment tree approach. It was not easy to think all the ideas I listed above. I know I'm not the best at it. But I think you can feel how frustrated I am, after getting Time Limit Exceeded in all of my attempts.

I also think I evolved since the Square Root Decomposition approach. The problem is that I am out of ideas to improve it further. If I didn't see that 156 people have already solved it. I would think it is impossible.

Please, share a bit of your knowledge with me. Thanks in advance.

Almost one year later... I tried to solve it today without looking my previous code and I got ACC'ed now. (ideone link)

Reading my question now, I've implemented what I called delta and rotate in a simpler way. I will try to illustrate.

This is how the segment tree for N = 5 looks like after build():

My node struct has:

int freq[9], i, lazy;

The i variable is the position circled in red in the picture, it will hold which position of the freq array contains the frequency for note 0 (which initially is zero). The lazy flag stores pending sums for children (both left and right), blue in the picture.

Now suppose first query for [1, 2]. The query() function will find nodes [1, 1] and [2, 2] and the resulting int fquery[9] array will have values [0,2,0,0,0,0,0,0,0]. The greatest() value then is 1. Ok, this is a simple search.

Now the function chord() will update those ranges by setting lazy += 1 and i -= 1:

Note that since those are leaf nodes, the lazy property does nothing. Also note that since i was decreased, there is no need to update freq[] array. This two things were done in the pre-order traversal of the recursive chord() function.

Now we update the freq[] array of the parents using the post-order traversal of the recursive chord() function by calling update(), this update function is just a merge of left and right child nodes:

These separation of pre-order and post-order traversal of the recursive call was the main point that I didn't understand last year. I was trying to update the parents out of the recursion track, and it caused me TLE.

Now suppose second query for [0, 4]. The query() function will find node [0, 4] and the resulting int fquery[9] array will have values [0,3,2,0,0,0,0,0,0]. The greatest() value then is 1.

Now the function chord() will set lazy += 1 and i -= 1:

Since we found the desired range in the root, this time we don't have post-order traversal.

Now suppose third query for [0, 2]. The query() function will find node [0, 2]. But, we can only reach a node if there is no pending sums. So, we need to resolve the lazy = 1 flag of node [0, 4]. This is what propagate() function does:

Note: the i value of node [0, 2] is 8.

And the resulting int fquery[9] array will have values [0,0,1,2,0,0,0,0,0]. The greatest() value then is 3.

Now the function chord() will set lazy += 3 and i -= 3:

As previously, we update the freq[] array of the parents using the post-order update():

To get the output after all queries, you just need to propagate() every node, doing so the leaf nodes will have the final values. You can check the show() function.

The output for this example will be: 5 6 6 2 2. (The first test case in the URI Online Judge).

Conclusion: The solution to the problem is a standard segment tree with lazy propagation with each node containing an int freq[9] array and an additional index starter holder.


How can I prove that if $\chi(G) > k \wedge \vert\{ad(H): H\ is\ an\ induced\ subgraph\ of\ G\}\vert$ then $G$ has a $k-regular$ induced subgraph? I have found an interesting exercise in my introduction to graphs workbook:

Let $ad(G) = \frac{2\vert E(G)\vert}{\vert V(G) \vert}$ and $mad(G) = max\{ad(H): H\ is\ an\ induced\ subgraph\ of\ G\}$.

Given a graph $G$ and a number $k \geq 3$, prove that if $\chi(G) > k \wedge mad(G) \leq k \Rightarrow \exists A \subseteq V(G)$ such that $[A]_{G}$ is $k - regular$.

I believe this can proved by contradiction:

Given a $G$ and $k$ for which the properties hold, we assume that $G$ has no induced subgraph $H$ that is $k - regular$. We then prove that if $\nexists H$ then at least one of the property is false and thus we contradict ourselves however I can't quite figure out the connection between $H$ and the mentioned properties.

How would you go about solving this?

Hint: It's better to prove that if $mad(G) \leq k$ and no induced subgraph of $G$ is $k$-regular then $\chi(G) \leq k$. Here is the idea of the proof:

Show that $G$ has a vertex $v$ of degree smaller than $k$.
Color $G - v$ using $k$ colors (by induction).
Complete this to a $k$-coloring of $G$.


DFA's with more than one initial state ( This may be related to NFAs with more than one initial state )

Consider a dfa $M$ with alphabet $\Sigma$ and states $Q$, typically also characterized by a specific initial state $q_0\in Q$. As the above-cited question points out, nfa's that nondeterministically select among several possible initial states can be converted to equivalent (wrt to their accepted language) nfa's with a unique initial state. And I'm asking if the same is true of dfa's, as follows.

Instead of $M$'s input being only a tape/string $s\in\Sigma^\ast$, let its input be $(q_0,s)\in Q\times\Sigma^\ast$, i.e., you give it the initial state $q_0\in Q$ that you want it to start in, as well as a string.

I'd think each possible $q_0\in Q$ defines a different language, call it $L_{q_0}\subseteq\Sigma^\ast$, accepted by $M$. But $Q$ can possibly be partitioned into equivalence classes, where all the states in a class accept the same $L$. But if there's more than one such class, then no single dfa with a unique $q_0$ starting state could represent this $M$.

So, assuming that's more-or-less correct, my additional question is how to characterize the equivalence classes. That is, given $M$'s transition function, $\delta:\Sigma\times Q\to Q$, how would you determine whether $q\equiv q^\prime$ belong to the same class (besides, that is, individually working out the language each accepts)? Is there a more elegant way to do that?

As Lukas points out, having multiple initial states is something of a red herring. You've defined your automaton to accept a subset of the strings that match the regular expression $Q\Sigma^*$ and that regular expression matches the language accepted by some ordinary DFA using the usual techniques. (Lukas gives an explicit construction in terms of the original automaton.)

For equivalence, there is a standard polynomial-time technique used for state minimization for DFAs. Luca Trevisan has a good set of notes (PDF) on this, which I'll briefly summarize.  Let the automaton have state set $Q$, alphabet $\Sigma$ and transition function $\delta$.

For a state $q$ and string $w$, write $\delta^*(q,w)$ for the state that you reach by starting at $q$ and reading $w$.  For states $p$ and $q$, write $p\equiv q$ to mean that $\delta^*(p,w)$ and $\delta^*(q,w)$ are either both accepting or both rejecting. This gives the same relation $\equiv$ that you give in the question.  We'll show how to compute $\equiv$.

To do this, for any $n\geq 0$, define $p\equiv_n q$ in the same way as $p\equiv q$, except restricting $w$ to be of length at most $n$.  We'll compute the relations $\equiv_n$ inductively, and show that knowing a finite number of them is the same as knowing $\equiv$.

First, note that $p\equiv_0 q$ if, and only if, $p$ and $q$ are both accepting or both rejecting so we can compute $\equiv_0$ easily.  Now, suppose we've already computed $\equiv_n$.  We claim that $p\equiv_{n+1}q$ if, and only if, $p\equiv_n q$ and $\delta(p,u)\equiv_n\delta(q,u)$ for all $u\in\Sigma$. Obviously, if $p$ and $q$ "agree" on all strings of length at most $n+1$, they must also agree on all strings of length at most $n$. For the second part, consider a string $uw$ where $|u|=1$ and $|w|=n$. We're saying that, for $p$ and $q$ to agree on $uw$, it must be that, after reading $u$, they move to states that agree on $w$.

This allows us to construct the relations $\equiv_n$ for all $n$.  Finally, we claim that $\equiv_{|Q|}$ is actually the same relation as $\equiv$.  To see this, observe that every $\equiv_n$ is an equivalence relation and, furthermore, the procedure from moving from $\equiv_n$ to $\equiv_{n+1}$ can only split equivalence classes into smaller ones: it can never merge them. Also, if $\equiv_n$ and $\equiv_{n+1}$ are the same relation, then $\equiv_{n+i}$ is the same relation for all $i\geq 0$.  $\equiv_0$ has at most two equivalence classes.  Every step of the process either splits at least one equivalence class or is the end of the game: it doesn't split any class and nor does any future step. We can't split classes more than $|Q|$ times because, if we did, we'd have more equivalence classes than states, which is impossible. So it must be that $\equiv_{|Q|}$ is the same thing as $\equiv$ and we're done.


How do we know for sure that EXPTIME ≠ P? I'm a beginner in learning about computational complexity and this has stumped me. I've read that by the time hierarchy theorem, it's known that EXP-complete problems are not in P. (Wikipedia) It makes absolute sense intuitively that this is the case, as does P≠NP. From what I understand, the time hierarchy theorem states that given more time, a turing machine can solve harder problems.

I have 2 questions:

How is the time hierarchy theorem (or anything else) used to prove that P≠EXPTIME?
If we assume P=NP and NP=EXP, P=EXP and that contradicts P≠EXP. So one of those statements MUST be false. But we can only conjecture that both these are false, and can't prove it? Is that the case?

The time hierarchy theorem says that, for any reasonable function $f$, there are problems that can be decided in time $O(f(n))$ that cannot be decided in time, say, $O(f(n)/n)$. (There are various versions of the time hierarchy theorem. The one I've just quoted isn't standard but it's strong enough to prove what we need, here.) In particular, then, there are problems that can be solved in time $O(2^n)$ that cannot be solved in time $O(2^n/n)$ so, in particular, cannot be solved in time $O(n^k)$ for any $k$.  These problems are in EXP but not in P.
Correct: we conjecture that P$\,\neq\,$NP and NP$\,\neq\,$EXP but we don't have a proof of either of those things.


Prove that if $p_1 \times p_2$ is positive, then $p_1$ is clockwise from $p_2$? In Introduction to Algorithms (CLRS), Exercise 33-1-1, we are asked to prove that if $p_1 \times p_2$ is positive then $p_1$ is clockwise from $p_2$ and if it's negative, then $p_1$ is counter-clockwise from $p_2$.
This is a picture from CLRS

I found the following proof:
https://sites.math.rutgers.edu/~ajl213/CLRS/Ch33.pdf
The proof above says to consider the angles both vectors make with the x-axis. We know the angle is $\arctan y/x$. We also know the cross product $p_1 \times p_2 = x_1y_2 - y_1x_2$. If this product is greater than zero, then this means that $y_2/x_2 > y_1/x_1$. Since $\arctan$ is monotone then the angle $p_2$ makes with the x-axis is larger. which means you need to move clockwise direction to get from $p_2$ to $p_1$
BUT the question is asking to prove that $p_1$ is clockwise relative $p_2$. What am I missing? is the above proof wrong?
I drew the following based on the proof above:

In two-dimensional space, $p_1 \times p_2$ is equal to $|p_1||p_2|\sin\theta$, where $\theta$ is the angle from $p_1$ to $p_2$. Depending which textbook you're using, this is probably the definition of the two-dimensional cross product—I'm not sure what definition Introduction to Algorithms uses.

$|p_1|$ and $|p_2|$ both have to be non-negative (by the definition of vector magnitude), so if neither of them is zero, the sign of the whole expression will be the sign of $\sin\theta$.

Now, how do we define "clockwise"? The easiest definition I know is is, $p_1$ is clockwise from $p_2$ if the angle(*) from $p_1$ to $p_2$ is less than 180 degrees. Try a few examples and you'll see how this definition works—remember that angles are traditionally measured with counter-clockwise being positive.

Now, we know that if $p_1 \times p_2$ is positive, then $\sin\theta$ must be positive. And if $\sin\theta$ is positive, then $\theta$ must be less than 180 degrees(*). So by the definition of clockwise, $p_1$ is clockwise from $p_2$.

(*) I'm assuming without loss of generality that all angles are positive and less than 360 degrees.


Proving the correctness of an algorithm, which computes the connectivity of a directed graph Let $G=(V,E)$ be a directed graph. The connectivity of a graph is the defined as the cardinality of a smallest separator of $G$. A separator of $G$ is a subset $U$ of $V$, such that $G-U$ is not strongly connected.

Why does the following algorithm compute the connectivity of a graph correctly?

\begin{equation}
\begin{split}
&\text{Connectivity}(\text{graph }G=(V,E)) \\
&\;\;\;\;01\text{:}\;\;k=\infty \\
&\;\;\;\;02\text{:}\;\;\text{for }i=1,\ldots,|V| \\
&\;\;\;\;03\text{:}\;\;\{\\
&\;\;\;\;04\text{:}\;\;\;\;\;\;\text{for each }v\in V\\
&\;\;\;\;05\text{:}\;\;\;\;\;\;\{\\
&\;\;\;\;06\text{:}\;\;\;\;\;\;\;\;\;\;\text{compute a minimum }v_i,v\text{-seperator }U_{v_i,v}\\
&\;\;\;\;07\text{:}\;\;\;\;\;\;\;\;\;\;k=\min\left\{k,\left|U_{v_i,v}\right|\right\}\\
&\;\;\;\;08\text{:}\;\;\;\;\;\;\;\;\;\;\text{if }(i>k+1) \text{ return }k\\
&\;\;\;\;09\text{:}\;\;\\
&\;\;\;\;10\text{:}\;\;\;\;\;\;\;\;\;\;\text{compute a minimum }v,v_i\text{-seperator }U_{v,v_i}\\
&\;\;\;\;11\text{:}\;\;\;\;\;\;\;\;\;\;k=\min\left\{k,\left|U_{v,v_i}\right|\right\}\\
&\;\;\;\;12\text{:}\;\;\;\;\;\;\;\;\;\;\text{if }(i>k+1) \text{ return }k\\
&\;\;\;\;13\text{:}\;\;\;\;\;\;\}\\
&\;\;\;\;14\text{:}\;\;\}
\end{split}
\end{equation}

More precisely, why can we return $k$ in line 08 (resp. 12) without concerning the other $u,v$-seperators?

Suppose that the algorithm is incorrect. We can slightly modify the algorithm by moving lines 8,12 just after the inner loop. If the algorithm returns $k$ incorrectly at the end of step $i$, then there must exist vertices $v_s,v_t$, for $s,t>i$, and a set $S$ of size $k-1$ not containing $v_s,v_t$, such that after removing $S$ there is no path from $v_s$ to $v_t$. I claim that $v_1,\ldots,v_i \in S$: if $v_j \notin S$ for some $j \leq i$, then since $S$ does not disconnect $v_j$ from any other vertex, we would have a path $v_s \to v_j \to v_t$. Since $v_1,\ldots,v_i \in S$, in particular $|S| \geq i$. Stated differently, $k-1 \geq i$. So if $i > k-1$, this is impossible.

My proof, if correct, shows that you can actually use the weaker condition $i > k-1$ in lines 8,12.


How can I show that a language is Turing-recognizable and decidable? I was wondering how I can show that the language $\{a^n b^n c^n \mid n \geq 0 \}$ is Turing-recognizable. Also, if it is Turing-decidable?

A language is Turing decidable if you can write a C program (replace C with your favorite programming language) that outputs YES if the input belongs to the language and outputs NO otherwise. It is Turing recognizable if in the latter case the C program simply never halts.


Help in understanding 'reasonable' encoding of inputs I read that a reasonable encoding of inputs is one where the length of the encoding is no more than a polynomial of the 'natural representation' of the input. For instance, binary encodings are reasonable, but unary encodings are not.

But say that the input is a graph, and its natural representation is a vertex and edge list. Suppose that the graph has $k$ vertices. If I use unary to encode, the overall length of the input referring to the vertex list would be $O(k^2)$, i.e. $=|1^1|+|1^2|+|1^3|+...+|1^k|$. Isn't this unary encoding still a polynomial with respect to the number of vertices of the graph (which is $k$)?

What am I missing here?

Unary encoding for values 0 <= k <= N takes O(N) space. Unary encoding of an n-bit number takes $\Theta(2^n)$ space. See the difference?


regular expression in license plates I'm trying to write a regular expression for some particular license plates. They consist of one up to three capital letters, a hyphen, one up to two capitol letters and one up to four numbers. The license plate should not exceed the 8 symbols.

Example: AA-AA123

What I have until now is the following:

because there has to be at least one letter before the hyphen, I have this expression for the first letter:
$$
P = (A\cup B \cup...\cup Z)
$$

For the second letter:
$$
D = (A\cup B \cup...\cup Z\cup empty)
$$
empty indicates the possibility that there could not be a letter.

For the numbers is basically almost the same procedure:
$$
E = (1\cup 2 \cup...\cup 9)
$$
$$
F = (1\cup 2 \cup...\cup 9 \cup empty)
$$

now for my explicit expression I think the answer would be:
$$
K= PDD^* - PDEF^*F^*
$$

but I'm not quite sure. I think this means I have 8 symbols, at least one letter before the hyphen but I could have up to three, the hyphen (that is a must), at least one letter after the hyphen but up to two and at least one number but I could have up to 4.

Something tells me I have something wrong here, I'm still new in the regular expressions world and I appreciate any help I could get in advance.

As David Richerby pointed out $D^*$ will accept an arbitrary number of letters (including none). If I'm not mistaken you need to take all possible options to achieve not having more than 8 characters.
$$
K = ( PDD-PDEF ) \cup (PDD-PEFF) \cup (PD-PDEFF) \cup (PD-PEFFF) \cup (P-PDEFFF)
$$
This assumes the hyphen is one of the 8 letters and thus does not allow more than 8 letters. Less letters are allowed because of your definitions of $F$ and $D$ including the empty word $\varepsilon$.

EDIT: added missing cases from commenter.


What is a sufficiently complex system? I have been reading about the AI approaches, and I came across the AI emergent approach that has the following definition:

That is, the appearance of an entity with a sense of its own identity and agency within a sufficiently complex system.

And I have got trouble understanding the meaning I have read the the paper What is a complex system? and the definition in this site, But I have still got trouble understanding the whole expression what does sufficiently mean exactly in this expression?

It just means "a system whose complexity is high enough to allow it to do [whatever thing we're talking about]."


Would a polynomial-time algorithm for an NP-hard problem implies that P=NP? An NP-hard problem is not in NP. (If it was in NP, it would be an NP-complete problem not NP-hard.)

So my question is: if someone can find a polynomial-time algorithm for an NP-hard problem, would that means that P=NP?

I think yes (I am almost sure) but I can't find the reason why?

Your conclusion is correct: Since an NP-complete problem exists that can be reduced to your NP-hard problem, if you should be able to solve your NP-hard problem in polynomial time the NP-complete problem would be in P, hence P=NP.


Repeated fingerprinting after array updates I've got a microprocessor and want to quickly identify the settings of my application (stored in some eeprom regions) via a fingerprint instead of having to dump the entire memory every time.

So I was going to compute a 32-bit hash from the few kbytes, but I am not sure which algorithm to use. It doesn't need to be cryptographically secure, but it should be fast and not need some large lookup tables. And most importantly, whenever one of the settings (bytes) changes I need to recompute the hash, which I want to do efficiently.

I guessed I could use any regular hashing algorithm and modify it so that it stores intermediate results in a tree-like structure which trades some memory for a logarithmic benefit in recomputation complexity. (As I found in my research, this concept seems to be called merkle tree). But surely there's an even better way to do it.

I then found about rolling hashes which employ some recursive algorithms, generalised to

$H(arr) = f_r(\ldots f_r(f_r(f_r(f_0 \oplus arr_0) \oplus arr_1) \oplus arr_2) \ldots \oplus arr_n)$

that can be expanded to

$H(arr) = f_0 \oplus f^0(arr_0) \oplus f^1(arr_1) \oplus f^2(arr_2) \oplus \ldots \oplus f^n(arr_n)$

This appears perfect for my use case if $\oplus$ is associative, commutative and reversible, which allows to do the recomputation for updating the array at index $i$ by

$H(arr_{new}) = H(arr_{old}) \ominus f^i(arr_{old,i}) \oplus f^i(arr_{new,i})$

The natural choices for $\oplus$ are bitwise XOR and modular addition, but which hash algorithms employ them, use a both simple and fast $f^i$ implementation, and still have good hashing characteristics?

I found some but am not totally satisfied.

CRC32 is known to be fast, and although all descriptions of the algorithm are iterative, I'm confident to be able to derive a non-recursive $f$ function (knowing that crcs have the property $\operatorname{crc}(x \oplus y \oplus z) = \operatorname{crc}(x) \oplus \operatorname{crc}(y) \oplus \operatorname{crc}(z)$). Still, CRC is used and designed for error detection, not fingerprinting, so maybe it's not suitable at all. Am I missing something there?
Rabin fingerprint appears to be suited better, but I only found iterative implementations with explicit polynom division. Not sure how to derive $f^i$ for this (is it even possible?). Also I'm not certain how it does differ from CRC computation.
Rabin-Karp rolling hash appears to be a good choice, but I have concerns. Does "modulo $n$" imply I won't get all 32 bit values? Isn't the exponentiation $f^i(x) = x \cdot a^i$ relatively slow? And what constants $a$/$n$ should I use?
Cyclic polynomial / Buzhash looks easy and efficiently to implement at first. But what about the $h$ in $f^i(x) = rotate(h(x), i)$, wouldn't this need to be a function that generates a 32-bit value from my 8-bit bytes? (I read a lookup table with random data works fine, but 256*4 bytes is too large for me). And isn't this rotation susceptible for swapping two settings that happen to be 32 bytes apart? Could the upper bytes of $i$, which is effectively used modulo 32, be utilised for something?

Can you dispel my doubts about any of these? Or is there some other algorithm that I missed entirely?

Any of the first three options you list are likely to be fine for what you want.

The CRC provides a good fingerprint (indeed, there's some theory to back that up, based on the theory of Carter-Wegman hashing, 2-universal hashes, etc.).

The Rabin fingerprint is also fine, and is essentially equivalent to the CRC (modulo small technical details that are unimportant).  $f^i(m_i) = m_i x^i \bmod p(x)$, which can be readily computed even for very large values of $i$ using fast modular exponentiation.

The Rabin-Karp hash is also fine, as long as you choose a good modulus $m$.  Don't pick a power of two; use a prime number.  Exponentiation is again fast if you use standard algorithms for fast modular exponentiation.  If possible, use a constant $a$ that is larger than the largest possible value of any single array element (single byte), i.e., larger than 256.  (Alternatively, it might be possible to pick $m$ to be a power of two if you also choose the constant $a$ to be a large random number modulo $m$; I haven't thought about that too carefully, so if that sounds attractive, please post a  separate question asking about that specific scenario.)

Buzhash is a little weaker than the other hash functions, though I suppose it's possible it might be good enough in practice.  Yes, Buzhash is susceptible to swapping of two values that are a multiple of 32 positions apart.  There might be ways to fix this, but given the large lookup tables required, that seems moot.  As you say, Buzhash requires a lookup table that maps from 8-bit values to 32-bit values (i.e., 256 entries, where each entry is a 32-bit word), so it sounds like Buzhash is not going to be feasible in your situation.


Is it possible that the universe of types could be closed? I asked a pretty vague question. I wasn't able to make it precise, but I can now. It seems to be out of the scope of the previous question, so I open another one.

In dependently-typed languages such as Agda or Idris, it's possible to define a universe inductive-recursively. However, W-types are known to have bad computational characteristics in traditional intensional type theories. Therefore, you need to be able to add new definitions of inductive data types anytime.

My question is, will HoTT improve this situation? That is, to have a closed universe. I know the general formulation of HIT is yet to be discovered, and that people seem not to be able to figure out induction-recursion, so I kind of suspect an definitive answer in the status quo. Still going to give it a chance though.

I'm uncertain what you're referring to exactly, but I can remark on a few things.

The first is that the usual problem with W-types is that encoding inductive types with them does not necessarily give you the right induction principles. For instance, we can try to define the natural numbers like so:

F : 2 → Type
F 0 = ⊥
F 1 = ⊤

ℕ : Type
ℕ = W 2 F

zero : ℕ
zero = sup 0 absurd

suc : ℕ → ℕ
suc n = sup 1 (const n)

induction : (P : ℕ → Type) → P zero → (∀ n. P n → P (suc n)) → ∀ n. P n
induction pz ps n = ???

The problem we'll run into is that induction on $W$ and $2$ allows us to observe the case $n = {\tt sup}\ 0\ f$, but we only have a proof of $P\ ({\tt sup}\ 0\ {\tt absurd})$. So we'll need a way to prove that $f = {\tt absurd}$, but there is no such principle in normal intensional type theory.

The answer to your question in this regard is that homotopy type theory does help in this regard, because e.g. univalence implies extensional equality of functions (and cubical type theory also includes this, for instance). So we should not have as many problems recovering the 'right' induction principles for $W$ based encodings.

However, another answer is that we didn't actually need this to begin with. This problem is somewhat particular to the specifics of $W$. Instead, we could use a more complex type of 'descriptions' of inductive definitions together with a decoding to a more 'first-order' representation of the container functor used in the $W$ definition. This approach is used in The Gentle Art of Levitation, which says it does not require extensional equality of functions (I believe).

This technique is also detailed in Ambrus Kaposi's thesis, which shows what sort of codes you need for inductive-recursive and inductive-inductive definitions.

The (I think) counter-intuitive bit about these systems is that they seem to actually be capable of describing themselves, and that this is not (it seems) contradictory.

So, it seems like we are relatively close to knowing how to to include most (commonly desired) definitions in type theory as a universe of descriptions with a 'decoding' function, instead of taking some universes to be open with respect to special definition forms. And this fact is somewhat independent of any features that homotopy type theory would have. I don't know of any system like Agda or Idris has this methodology on their roadmap, though.

I should say, there are potential traps, still. For instance, each universe Set i in Agda is called "Mahlo," because it admits inductive-recursive definitions. There are stronger universes known than Mahlo universes, too, which will in turn have (many) Mahlo universes within them. But the sort of 'universe' you define with induction-recursion cannot be Mahlo, because it is inconsistent for a Mahlo universe to have an induction principle. So any theory incorporating strong-than-Mahlo universes would at least need a different sort of 'description' system for those.


Selecting items from two arrays without duplicate indices to get maximum sum Given two arrays both of length n, you have to choose exactly k values from the array 1 and n-k values from the other array, such that the sum of these values is maximum, with constraint that if you choose a value from some index of any of the array you cannot choose from same index of second array.

I have encountered this type of question in many places but never able to solve it, and I always have an Intuition that this is a dynamic programming problem but never able to prove it. I do not quite understand If there exist a dynamic solution or not?

There are two ways to interpret the problem.

$k$ is part of the input

Let $a=(a_1, a_2, \cdots, a_n)$ and $b=(b_1, b_2, \cdots, b_n)$ be the two given array. Suppose we have chosen $k$ values from array $a$, $a_i$ where $i$ ranges over some index set $I$ that has $k$ elements. Then we have to choose the $n-k$ values from array $b$, $b_j$ where $j$ ranges over all indices that are not in $I$. The sum of all numbers are

$$\sum_{i\in I}a_i+\sum_{i\not\in I}b_i=(\sum_{i\in I}a_i-\sum_{i\in I}b_i) + (\sum_{i\in I}b_i+\sum_{i\not\in I}b_i)=\sum_{i\in I}(a_i-b_i)+\sum_ib_i$$

Since $\sum_ib_i$ is a constant, the sum reaches the maximum if $\sum_{i\in I}(a_i-b_i)$ reaches the maximum. So we can select the $k$ largest elements in the array $a-b=(a_1-b_1, a_2-b_2, \cdots, a_n-b_n)$. The indices of the those elements are the indices of the elements in $a$ that we should choose.

The $k$ largest element can be selected in $O(n)$ time using quickselect, this algorithm can be implemented in $O(n)$ time. It can also be implemented in $O(n\log n)$ easily by sorting the array $a-b.$

$k$ is not part of the input

Solve the previous problem  for $k=0$. Let the maximum sum obtained by $m_0$.
Solve the previous problem again but for $k=1$. Let the maximum sum obtained by $m_1$.
And so on.

Find the maximum number among $m_0, m_1, \cdots, m_n$. That is the maximum sum we want in this interpretation the problem. A bit of extra bookkeeping will let us know the numbers we should select to reach that maximum sum.

Exercises

Exercise 1. How about the case of smallest sum?

Exercise 2. How about exactly $k-1$ values from the first array and $n-k$ values from the other array?


Understanding growth function of closed intervals in $\mathbb{R}$ I as studying VCdimensions and growth functions and found the following example on Wikipedia:
The domain is the real like $\mathbb{R}$. The set H contains all the real intervals, i.e., all sets of form $\{c \in [x_1, x_2] | x \in \mathbb{R}\}$ for some $x_{0, 1} \in \mathbb{R}$.
For any set C of m real numbers, the intersection $H \cap C$ contains all runs of between 0 and m consecutive elements of C. The number of such runs of ${m+1 \choose 2} + 1$, so Growth(H, m) = ${m+1 \choose 2} + 1$.
Can anyone please explain to me what does the term "all runs of between 0 and m" refer to here and why the growth function is ${m+1 \choose 2} + 1$ and not ${m+1 \choose 2}$?
Thank you very much!

Let the real numbers be $r_1 < \cdots < r_m$. The intersection $H \cap C$ could be of the form $\{r_i,\ldots,r_j\}$ for $1 \leq i \leq j \leq m$, or empty. There are $\binom{m+1}{2}$ of the first type, and $1$ of the second type.
For example, if $m = 1$ then the possible intersections are
$$ \emptyset, \{r_1\}, $$
if $m = 2$ then the possible intersections are
$$ \emptyset, \{r_1\}, \{r_2\}, \{r_1,r_2\}, $$
and if $m = 3$ then the possible intersections are
$$ \emptyset, \{r_1\}, \{r_2\}, \{r_3\}, \{r_1,r_2\}, \{r_2,r_3\}, \{r_1,r_2,r_3\}. $$


HashTable open-addressing is used for main array or buckets I am trying to understand the HashTable open-addressing technique. I see there are three approaches: linear, quadratic and double hashing. I'm wondering are these techniques used:

to find an index of the main array and no bucketing is involved
or used when our buckets are arrays too and we are trying to add it to the bucket and we are not sure where to add.

Thanks in advance.

Open addressing is a method for handling collisions. Another method is chaining, in which we have lists at our table indices, like you say.

In other words, open addressing means that all elements are stored inside a single table. In particular, to resolve a collision, the probing sequence finds a free slot in our table.


Can a programming language be designed to use a fixed amount of memory? I have been toying around with the idea of creating a programming language as a side-project, specifically trying to get extreme performance out of a machine.

I have been thinking about the efficiency-memory tradeoff, and was wondering if it would be at all possible to design a language which always uses a fixed amount of memory.
That is, it allocates a large chunk of memory (16K, 64K, 1M, depending on the task), and instead of allocating from a heap, just gives some more memory out of the block we've already allocated.

The idea here is not to be practical, but rather to pose a challenge: design a fast algorithm that works on a fixed amount of memory.

If this sounds like a fun project, please let me know and I'll get on it.

If, however, this is a very naive thing to say (I don't know much about the inner workings of programming languages), I would very much appreciate some resources as to where I can learn more.

Yes. At least one variant of C supports this. Its call stacks are bounded in size: you can't call functions within functions indefinitely. It is used for embedded devices.


Algorithm to find shortest lightest path in a graph from source Given a directed graph $ G = (V,E)$  with non-negative(zero and positive) weights on the edges, and a vertex $ s \in V $

Problem: Find the lightest path from $s $ to each and every vertex $v \in V$ and that's from the shortest paths from $ s$ to all $v \in V$

Length of a path is the number of edges in the path.

Weight of a path is the sum of all weights of the path's edges

-------- Edit: Elaborating the question: --------

Suppose there are $x$ different paths between $s$ and some $v \in V$.
Each path has its own weight.
Among those $x$ paths, there are $y$ shortest paths(pay attention $ y \subseteq x$ and all the paths in $y$ have the same length).

What I'm trying to find: The lightest path among the above $y$ paths. Also, i want to calculate that weight for every vertex in $V$.

Initially, i thought about this algorithm:

run BFS on $G$ from source $s$
run Dijkestra on the BFS tree from step 1

However, i ran into this problem:

With source vertex $A$, the red path and the black path, both lead to the same vertex $D$.

Pay attention how $ A\rightarrow B\rightarrow D$ and  $A \rightarrow C \rightarrow D$ are both of length 2
Although they are both the shortest paths from $A$ to $D$, the red path is lighter than the black one.

I thought about 'tweaking' BFS:

Each time i arrive at a vertex $v$ which i already discovered, i check whether the "new" path i already walked to $v$ is lighter than the one already set to $v$.

However, i don't want to change in the algorithm, because i need to prove that it actually work from the start.

How can i modify my algorithm so that the problem i pointed won't pop-out?

The whole point about Dijkestra is that it finds the best path on it's own. You don't need BFS. In fact, Dijkestra is sort of a BFS.

Use tuples as weigths. Then your question becomes simply "find the lightest path".

How it works on your graph:

Start with a lists of undiscovered vertices and discovered ones. I labeled the unlabeled vertices E and F. I use tuples length, edgeweigth as weigth in terms of Dijkestra.

undiscovered
[B, C, D, E, F]

discovered (length, edgeweigth)
A (0, 0)

Enumerate all paths from discovered vertices to undiscovered ones along with the resulting weigth

A -(1)-> B (1, 1)
A -(1)-> C (1, 1)
A -(0)-> E (1, 0)  <

Find the best one according to your objective function. In your case: smaller length, on equal length smaller edgeweight. Add it to the discovered vertices.

Iteration 1

undiscovered
[B, C, D, F]

discovered (length, edgeweigth)
A (0, 0)
E (1, 0)

Paths
A -(1)-> B (1, 1)  <
A -(1)-> C (1, 1)

Iteration 2

undiscovered
[C, D, F]

discovered (length, edgeweigth)
A (0, 0)
B (1, 1)
E (1, 0)

Paths
A -(1)-> C (1, 1)  <
B -(10)-> D (2, 11)

Iteration 3

undiscovered
[D, F]

discovered (length, edgeweigth)
A (0, 0)
B (1, 1)
C (1, 1)
E (1, 0)

Paths
C -(1)-> D (2, 2)
C -(0)-> F (2, 1)  <
B -(10)-> D (2, 11)

Iteration 4

undiscovered
[D]

discovered (length, edgeweigth)
A (0, 0)
B (1, 1)
C (1, 1)
E (1, 0)
F (2, 1)

Paths
C -(1)-> D (2, 2)  <
B -(10)-> D (2, 11)

Iteration 5

undiscovered
[]

discovered (length, edgeweigth)
A (0, 0)
B (1, 1)
C (1, 1)
D (2, 2)
E (1, 0)
F (2, 1)

No more undiscovered vertices -> we're done.


Showing that a language is NP Complete (advice) I am currently getting ready for my final exam in computational models. I know that there aren't any rules or rule of thumb to show that a language is NP-complete and each problem has its own tricks, but I am really struggling with questions where they give me a language and showing that the language is NP-complete by showing that an NPC problem is polynomial reducible to the given language.

So I wanted to ask for advice. How can I approach such problems? Are there any steps that I can take before to help me somehow? Or is it just literally figuring out which NPC problem is "closest" to the the given language and try to construct a polynomial reduction?

I'd appreciate any advice. Thank you.

Typically, yes, it's a matter of finding a known NP-complete problem that's somehow similar to the one you're trying to work with. So if you're dealing with a problem about formulas, you probably want to reduce some version of SAT or 3SAT to it.

For graph problems, you probably want to reduce some other graph problem. Problems about long paths and cycles probably come from Hamiltonian path/cycle. Problems about classifying vertices into types sound like colouring problems. Problems about graphs containing or not containing some structure might come from clique or independent set. Problems about dividing graphs in two might be Max Cut, or Subset Sum.

Reductions from one type of problem to another are typically more difficult. If you ahve to do that, think about how you can use your target problem to encode things that are needed in the known NP-complete problem. For example, when you reduce 3SAT to independent set, being in or out of the independent set corresponds to being true or false; when you reduce 3SAT to 3-colourability, the three colours you use are "true", "false" and "er, the other colour".  But, in these cases, the reduction gadgets tend to be quite fiddly.

Another thing to bear in mind is that, if problem $A$ looks like problem $B$, which you already know to be NP-complete, it might be possible to modify that proof to make it work for $A$. For example, consider 4-colourability. The easy reduction is from 3-colourability: given a graph $G$, add a new vertex, connect that to everything and the new graph is 4-colourable if, and only if, the original graph was 3-colourable. But, if you didn't see that and you knew the reduction from 3SAT to 3-colourability well, it probably wouldn't be very hard to modify that reduction so the four colours were "true", "false", "er, the other colour" and "gee, there are a lot of colours today".


Why is SAT so important in theoretical computer science? In my Computability and Complexity class, we are focusing on P, NP,
NP-complete, and NP-hard problems and the one thing that keeps coming up
is the SAT problem, in the context of reduction from one complexity to
another or to explain certain concepts.
Why is SAT so ubiquitous in theoretical computer science?

SAT was the first problem shown to be NP-complete, in Stephen Cook's seminal paper. Even nowadays, when introducing the theory of NP-completeness, the starting point is usually the NP-completeness of SAT.
SAT is also amenable to surprisingly successful heuristic algorithms, implemented by software known as SAT solvers. As a result, there is a lot of practical interest into formulating problems efficiently as instances of SAT.
SAT also shows up in fine-grained complexity, one of whose main assumptions is the strong exponential time hypothesis, which is a conjecture on the computational complexity of SAT.


Parikh's Theorem: CFL's "contain" regular languages? The first sentence of the Wikipedia article for Parikh's Theorem states:

  "Parikh's theorem in theoretical computer science says that if one looks only at the relative number of occurrences of terminal symbols in a context-free language, without regard to their order, then the language is indistinguishable from a regular language."

I'm having some trouble understanding this sentence.  I understand that unary CFL's can be described as the union of finitely many arithmetic sequences.  Does this mean that if we apply a morphism $h$ to some CFL $L$ which, say, maps $a \longrightarrow a$ and $c \longrightarrow \epsilon$ for some $a \in \Sigma$ and for all $c \in \Sigma$ with $c \neq a$, then $h(L)$ is a unary regular language?  Could someone elaborate on this?

The Parikh image $\Psi$ of a word is a vector counting the number of each of the letters in the alphabet: for example $\Psi( abbabaaca ) = (5,3,1)$ assuming the alphabet is $\{a,b,c\}$.

The Parikh image of a language is the set of Parikh images of the strings in the language: $\Psi( \{a^nb^nc^n\mid n\ge 0 \}) = \{(n,n,n)\mid n\ge 0 \}$.

The theorem states that the Parikh images of context-free languages are in fact Parikh images of regular languages, as example   $\Psi( \{( ab)^n c^n\mid n\ge 0 \}) = \Psi( (abc)^*) $.

(In a previous edit I had the example  $\Psi( \{a^nb^nc^n\mid n\ge 0 \}) = \Psi( (abc)^*) $. Technically correct, but the reader will note that language is not context-free.)


Algorithm to shrink a DFA by introducing nondeterminism? This is somewhat related to another question I asked, but I feel it's different enough to warrant its own question.

I'm doing research where I'm trying to find the structure of complements of a certain class of finite languages. It's easy for me to get the minimal DFAs accepting these languages, but I'd like to examine what kind of structure NFAs accepting these langauges have, particularly how nondeterminism helps with state-size of the automata (the DFAs are exponentially large).

The problem is, the main NFA reduction technique uses equivalences, which won't produce any reduction if I start with a minimal DFA (since it's basically using the same technique). If I start with a non-minimal DFA, it just spits out the minimal DFA.

What I'm wondering is, are there algorithms which can start with a DFA, and shrink it into a smaller NFA by introducing nondeterminism? Are there "standard techniques" to do this?

I have found preorder reductions, which look promising but hard to implement. I'm open to many suggestions.

For efficient heuristics I'd suggest looking into the CAD literature on the state encoding problem (assigning binary identifiers to states of a DFA to minimize the amount of logic for the state transition function.)  Devadas and Newton, "Decomposition and factorization of sequential finite state machines," IEEE TCAD, 8(11):1206-1217, 1989 points out that there is a close relationship between state encoding and state machine decomposition.

If for a DFA with $N$ states you assign a unique $M$ bit state identifier to each state ($\lg_2N < M\leq N$), then you have essentially decomposed the DFA into a network of $M$ interacting two-state machines.  Equivalently: you have defined a set $S$ with $M$ elements, and assigned a unique subset of $S$ to each state in your original DFA.  This is also what the Rabin-Scott powerset construction algorithm does.  So by doing a state encoding on the DFA we are trying to reverse engineer the set that the powerset construction algorithm started from.

In the traditional state encoding problem all encodings are legal, and there is some objective function (related to the amount of logic in the state transition function) that you are trying to minimize.  To generate an NFA you need to solve a constrained version of the enconding problem where:

  an encoding of $M$ bit identifiers to the DFA states represents an NFA iff for each symbol in the alphabet the transition function for each bit is a simple disjunction of bits.  (No conjunction or negation is allowed.)

So you could enumerate all the $M$ bit encodings for all $\lg_2N < M\leq N$, and check whether each one satisfies the constraint.  (Note that for $M=N$ the trivial "one-hot" encoding always satisfies the constraints, and gives you the DFA.)  The enumeration is ridiculously large though, (Di Micheli's textbook gives it as something like $\frac{2^M !}{(2^M - N)!M!}$.)  The reason I'm suggesting the CAD literature is that there are techniques for doing this search implicitly rather than enumerating (for example, by using BDDs, see Lin, Touati and Newton, "Don't care minimization of multi-level sequential logic networks," Int'l Conf Comp-Aided Dsgn ICCAD-90:414-417, 1990.

Example

Take the following DFA, (with a state encoding that I derived by cheating (I generated the DFA from an NFA using Rabin-Scott, and the encoding represents the subsets chosen by Rabin-Scott.))

If we call the bits in the state assignment ABCD, then when the input symbol is 1, the transition function is A=A, B=A, C=B, D=C.  When the input symbol is 0, the transition function is A=A, C=B, D=C.  This is a purely disjunctive transition function with no conjunction or negation, so this state encoding gives us an NFA.  The states in the NFA correspond one-to-one with the bits in the encoding, and the transition function is as given:

Formulation as boolean satisfiability problem

The informal description above leads directly to an encoding as a boolean satisfiability problem.  There is a set of variables that describes the transitions in the NFA, and a set of variables for the DFA state encoding that would be derived from Rabin-Scott for the chosen NFA.  The transitions of the specific DFA you are trying to decompose are used to place constraints on the NFA transitions.

Suppose we are given a DFA with $N$ states for a language with $S$ symbols, and we would like to derive an $M$ state NFA, with $\lg_2N<M\leq N$.  We will use the variables $y_{sft}$ to represent the possible transitions in the NFA.  $y_{sft}$ will be true iff there is a transition in the NFA from NFA state $f$ to NFA state $t$ on symbol $s$.  In the above example NFA, the alphabet is of size 2 and there are 4 NFA states, so there are $SM^2=32$ $y$ variables and $y_{0AA}, y_{1AA}$, and $y_{1AB}$ are all true while $y_{1DA}$ is false.

We will use the variables $x_{dn}$ to indicate whether or not the Rabin-Scott algorithm should include NFA state $n$ in the set of states labeling DFA state $d$.  In the example above we have $N=8$ DFA states and $M=4$ NFA states so there are 32 $x$ variables.  In the example above suppose the bottom-most state (the one labeled "1011") is state $k$, then $x_{kA}$, $x_{kC}$, and $x_{kD}$ are true while $x_{kB}$ is false.

Now the constraints.  First of all, Rabin-Scott must find a different encoding for each DFA state, so for the DFA states $i < j$ and all NFA states $\{A,B,\cdots, D\}$:
$$
(x_{iA} \neq x_{jA}) + (x_{iB} \neq x_{jB}) + \cdots + (x_{iD} \neq x_{jD}).
$$

Next it must be the case that if Rabin-Scott found a transition from DFA state $i$ to DFA state $j$ on symbol $s$ then for each NFA state $k$ included in the encoding of $j$ there must be an NFA state $l$ from the encoding of DFA state $j$ such that the original NFA had a transition from $l$ to $k$.  In the example above, on symbol "1" there is a DFA transition from DFA state "1000" to DFA state "1100" so there must be an NFA transition from NFA state A to NFA states A and B and no NFA transition from NFA state A to either NFA state C or D.  So for each of the $o(SN^2)$ edges in the DFA we have the constraints:
$$
\begin{eqnarray*}
x_{jA} & = & y_{sAA} x_{iA} + y_{sBA} x_{iB} + \cdots + y_{sDA} x_{iD} \\
x_{jB} & = & y_{sAB} x_{iA} + y_{sBB} x_{iB} + \cdots + y_{sDB} x_{iD} \\
       &   & \cdots                                                    \\
x_{jD} & = & y_{sAD} x_{iA} + y_{sBD} x_{iB} + \cdots + y_{sDD} x_{iD}.
\end{eqnarray*}
$$

Finally we need to deal with the start and accept states.  The DFA start state is encoded with the union of the NFA start states, so the DFA start state better not be encoded with the empty set, so $x_0A + x_0B + \cdots + x_0D$.  And finally we need a set of variables $f_n$ to indicate whether each NFA state is an NFA accept state.  It must be the case that the encoding for every DFA accept state contains at least one NFA accept state and that the encoding for every DFA non-accept state contains no NFA accept states so: $x_{iA}f_A + x_{iB}f_B + \cdots + x_{iD}f_D$ for DFA accept states $i$ and $\neg (x_{jA}f_A + x_{jB}f_B + \cdots + x_{jD}f_D)$ for DFA non-accept states $j$.


How to modify Floyd-Warshall algorithm with space $O(V^2)$ with tracking actual path? The Naive way to reduce space complexity of Floyd-Warshall algorithm is consider only $d_{ij}^{(k)}$ and $d_{ij}^{(k-1)}$ in each time.

But in this case, we can't track actual shortest path with knowledge only two $d$ tables. It requires whole table.

There is a nice solution: Johnson's algorithm reduce both time and space complexity. (Especailly space complexity is $O(V^2)$) .

But I want to know can we apply simliar trick to Floyd-Warshall algorithm  as Divide and Conquer trick in Sequence Alignment problem.

The crux part of Divide and Conquer trick in Sequence Alignment is 'we can reverse recursive relation into center'.

But in recursive relation in Floyd-Warshall algorithm, its recursive relation seems to be it has no such property.

Is there any other technique to apply such reducing space complexity that can track actual shortest path?

Edit: Also I want to retain time complexity $O(V^{(3+\epsilon)})$.

For each $i,j$ keep track of the last $k$ for which the value $d_{ij}^{(k)}$ was changed. That must be the highest value on the shortest path from $i$ to $j$. The actual path can be retrieved recursively.

Added. A simpler solution. Keep track of array $n_{ij}$ of vertices, giving the next vertex on the shortest path from $i$ to $j$. Whenever $d_{ij}^{(k)}$ changes, $n_{ij}$ is set to $n_{ik}$.


Quickly pruning edges below average weight for a membership-based weighting I have points represented as sparse high-dimensional binary vectors, or put another way, I have a list of groups that each point belongs to. For two points, the edge weight between them is $\sum_i 1/|B_i|$ where $|B_i|$ is the number of points that belong to group $i$, and the summation is over all shared groups that both points belong to.

My distribution on group size is very skewed  where there are a few large groups that contain about 5 million points and many small groups that contain 2-10 points. Each point belongs to about 5 groups on average and there are roughly a million groups. Also there are roughly 10 million points total. The goal is to identify all edges that have weight above some pretty high threshold, e.g. the mean edge weight.

Currently the best algorithm I have in hand is to check all pairs of points within each group and compute the edge weight between them. However there are groups that give rise to on the order of $10^{13}$ pairs, which is too high. I was thinking of maybe going through groups from smallest to largest and somehow eliminating a lot of pairs to check once the larger groups are reached, since after all the overall edge weight has to be above a pretty high threshold. But I'm not 100% sure how to formalize that, or whether it would really help. Any help would be greatly appreciated, either advice on how to make my pruning idea effective, or even completely fresh ways to approach the problem.

Yes, we can make your idea work.  I'll show how below, and prove that it is correct (it does not miss any edges).

The first step will be to sort the groups by decreasing size.  Say their sizes are $s_1 \ge s_2 \ge s_3 \ge \dots$.  Say $t$ is your threshold.  Find the smallest $k$ such that

$$1/s_1 + 1/s_2 + \dots + 1/s_k \ge t.$$

Lemma. No edge can have weight above the threshold $t$ based only upon membership in groups $1,2,\dots,k-1$.  In other words, every edge with above-threshold weight must be in at least one of the groups $k,k+1,k+2,\dots$.

This observation lets you apply your idea, to optimize the performance of the algorithm.

Algorithm. Sort the groups by decreasing size and find $k$, as above.  For each of groups $k,k+1,k+2,\dots$, look at all pairs of points within the same group, and compute the edge weight of each such edge.  Output the ones whose edge weight is above the threshold $t$.

This algorithm can be proven to output all above-threshold edges, thanks to the lemma above.


One counter automaton as a function We can associate a one counter finite automaton with a function $f:\Sigma^* \to \mathbb{N} \times \{0,1\}$, where $f(x)=(n,b)$ describes the state where the automaton terminates when fed an input word $x \in \Sigma^*$: $n$ holds the number inside the counter, and $b=1$ iff the state is an accepting state.

Is it decidable to determine whether two of these automata are associated with the same function?

I looked at posts like this one and this one too but I can't find the answer.

Furthermore, since these machines are always aimed to accept/reject a string, is there any natural way to expand them to represent a function?
As an example, think of a machine that simply counts the number of times it visited a specific node in the DFA, or even simpler: counts the length of its input word.

You can use the counter value as the result of the function.

Furthermore, if I understood well your question, a simple way to map $(bool,nat)$ is the following: modify the state transitions of the original automata $A$ to make the counter value equal to $2x$ if the counter of the original A is $x$ and the state is rejecting, $2x+1$ if the counter of the original $A$ is $x$ and the state is accepting.

If the one-counter machine that returns $(bool, nat)$ (with no distinction between accept/reject states, because the accept/reject condition is embedded in the returned value as explained above) is deterministic, then you can decide equivalence using this trick:

Given automata $M_1$, $M_2$ computing $f_1,f_2:\Sigma^* \to N \times \{0,1\}$;  you can transform them back to two standard accept/reject automata $M_1', M_2'$ computing $f_1',f_2':\Sigma^* \to \{0,1\}$.

Expand the alphabet adding an extra symbol $*$; and make $M_1'(x*^k ) = Accept$ if and only if $M_1(x) = k$.

When $M_1', M_2'$ find a $*$ they decrement the counter if it is $>0$, otherwise they enter a permanent reject state. If the counter reaches $0$ after the decrement, then they enter an accept state. If they find another symbol after a $*$ they enter a permanent reject state.

Now you can check language equivalence of the "standard" one-counter automata $M_1', M_2'$ (decidable in the deterministic case, see L.G.Valiant, M.S.Paterson, Deterministic One-Counter Automata, 1975) and by construction $L(M_1') = L(M_2')$ if and only if $f_1 = f_2$.


Is there a philosophical counterpart question to P != NP? Gödels motivation to prove his incompleteness theorems was the philosophical statement "This sentence is wrong.". Is there a philosophical counterpart to the statement P != NP? For example such statement might be "This Theorem is practically unprovable". The consequences of an existence of such theorem would be: If the sentence is true, than there is no practical way to prove it. If it is not true, then there is a practical way to prove it, hence it must be true, which is a contradiction. Since P!=NP is such a deep question, I wonder if philosophist have a counterpart question in the sense given above.

Shortly: No.

Gödel motivation was to give closure, in a sense the very same as Hilberts to make one connected field. This is meta-science (meta-mathematics) but not based on philosophy but mathematics.
The concept of truth was connected with logic (in logic it is just well defined symbol), and the idea was to give axiomatic (absolute truth), in order to achieve that the one obvious idea is to give a function (even oracle) that evaluates given object (explicitly loose statement, as it was (and is) underdefined). It was meant to rescue the concept (the truth depends on context, field given, e.g. in Psychology the absolute truth would not be of that much use), which is required to prove anything.

Gödel started as mathematician, the pursuit of closure pushed him to mathematical philosophy (self-studied, not at the professional level), which was used as meta-science, meta-logic, but every time any advancement was made it was back in the field of mathematics. The urge to prove was bigger than to disprove so he picked contraposition to get back to mathematics (CS). After that he succumbed into idealism.

Any proof in given field must be proved in given field, using provided tools, meta-tools and must be verified (and understood) by people from that field otherwise this is just loose statement. In example $P vs NP$ cannot be proved using philosophy, where it is undefined problem. Unfortunatelly it would require to take understanding of the whole field, define the problem using strict notation and use M or CS tools.

The philosophical counterpart does not exist, moreover in that field the $P vs NP$ problem might be defined with assumption of one being true, both or neither. Nothing prevents from defining problem as exclusive alternative or nonexclusive alternative. The concept will be well defined in any cases giving the frame of reference, outcomes and closed entity (world) where we can go further with provided axioms (and this is what we do in CS, there are conditional proofs "if P = NP then ..."). But the task to actually prove it is in the field of Mathematics or Computer Science.

There is no counterpart theory or framework of inference. The sentence you have provided is not proper. Any kind of paradox, tautology or too loose statement to deal with in some other field gives nothing and proves nothing. For the sake of argument if there were counterpart theory it still would be too weak to infer anything.
The paradox is something that goes beyond formalism or simply includes mistakes at language level - which are totally irrelevant when analysing in philosophy since it can be resolved at any level giving explicit assumptions.


DPDA for $L_1 = \{0^i1^j2^k3^m | i,j,k\ge 0,m = i+j+k\}$ according to empty stack criterion I'm having some trouble with the following language:

$L_1 = \{0^i1^j2^k3^m | i,j,k\ge 0,m = i+j+k\}$

with alphabet $A=\{0,1,2,3\}$

I'd like to find a deterministic pushdown automata to recognise it according to the empty stack criterion.

I built the deterministic pushdown automata according to the final states criterion and as the language has the prefix property there should be an automata according to the empty stack criterion.

Is there an algorithm to do this? The one I use to translate from one criterion to the other doesn't not seem to work for deterministic automata.

DPDA for $\mathcal L=\{0^i1^j2^k3^m | i,j,k\ge 0,m = i+j+k\}$

let's try to understand wich words the automata should accept:

$\{\varepsilon,03,13,23,0033,1133,2233,0133,0233,1233,000333,111333,\dots \}\in \mathcal L$

So we can see the "two parts" of the automata, the first part will contain the $0,1,2$ digits and the second part of the automata will contain the $3$ digits, so for the first part we will do a "push" for some $X$ and for the second part we will do a "pop" for $X$, we will accept the word if the stack is empty so in the end we will do a "pop" for some $Z$ that have been in the stack alaready

Try this one, if it is not $100\%$ at least it will lead you to bulid it by yourself

SPOILER:


Union of a Deterministic Context-free language and a Regular Language is a Deterministic Context-free Language In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are the context-free languages that can be accepted by a deterministic pushdown automaton.

Now Assume that $R$ is a regular language and $D$ is a deterministic context-free language.
How can we prove that $R\cup D$ is a DCFL?

Note : I saw a similiar theorem for the intersection.  But i'm new to PDA's and i almost have no idea how to prove this one.

Thanks in advance.

Yes, deterministic context-free languages are closed under union with regular languages.

It is easy to show they are closed under intersection with regular languages. We can apply a product construction. When reading a symbol we also do a step of a FSA that is running in parallel. Accepting a computation means accepting both the DPDA part and the FSA part.

This doesn't work for union. Why? Because a DPDA may end up in an infinite loop of $\varepsilon$-transitions, so it will never read all of its input. In that way we cannot test acceptance by the FSA.

In order to make this work we also need a normal form for DPDA, that they will never do such infinite loops, and always read all input. That normal form is usually proved when showing DCFL are closed under complement (and is non-trivial).

By he way, once we know that DCFL is closed under complement and closed under intersection with regular languages, closure under union with regular languages follows by De Morgan: $L\cup R = (L^c \cap R^c)^c$.


How can a Turing Machine recognize a regular language? This is a practice problem for a midterm in a class I'm taking:

  Given a regular language $L$, describe formally a Turing machine that recognize $L$.

I'm not sure how I should do that.

Hint: A DFA consists of 5 parts: state-set, alphabet, initial-state, final-state-set and transition-function. What does a Turing Machine consist of, and which would correspond to each part of a DFA?


How to measure the degree of randomness in Disk I/Os? Most disk-based system's performance heavily depends on its disk access patterns. So maximizing the sequential I/Os while avoiding the random I/Os is a typical goal in performance perspective.
I am working on the same problem.

I have some difficulties in measuring the degree of randomness of Disk I/Os. I can measure the disk throughputs in MB/sec using the performance monitoring tools. However, MB/sec is a result of such and such possible causes including the disk access patterns. I want to directly measure how much random disk I/Os are occurring at a certain moment.

Is there any metric that is commonly used to represent the degree of randomness in Disk I/Os?

If there is, how can I measure those?

I am not aware of any formal discrete metrics of spatial and/or temporal locality of reference. Maybe someone else can enlighten us on that.

Often I see metrics used that are relevant to the particular platform you're studying. So the metric is either 'L1 cache misses', 'branch mispredicts', 'hard drive head movement', etc. You can google how to measure those.

You can make ad-hoc models by saving the location of your read/writes and applying penalties if those locations (or 4K blocks around those locations) haven't seen I/O recently.


Question on SAT reduction Let Two-Solutions-SAT be the language of Boolean formulas that have exactly two distinct satisfying assignments. Show Two-Solutions-SAT is co-NP-hard.

I know how to show that the complement of Two-Solutions-SAT is in NP, it's relatively easy to create a nondeterministic polynomial time TM that decides it.

My problem comes with reducing from SAT to the complement of Two-Solutions-SAT. I understand how to reduce from SAT to 3SAT, but in the case of 3SAT you will always have CNF's with 3 variables. With the complement of Two-Solutions-SAT, you have to somehow reduce to the case where you have 0 or 1 or >= 3 distinct satisfying assignments, and I'm not sure how to go about reducing to that.

Thanks

Hint: For a formula $\varphi$, let $\#(\varphi)$ be the number of satisfying assignments of $\varphi$. Come up with a polytime transformation $T$ so that $\#(T(\varphi)) = \#(\varphi) + 2$.


What does the term maximum-bottleneck (s,t)-path in the context of maximum flow optimization? I was reading the following notes on maximum flow and it said the term "maximum-bottleneck (s-t)-path" but I couldn't find were it precisely defined it, so I am left guessing what it means. I am assuming it means a path from s to t with maximum total capacities once you sum the capacities across the path. However, I am not sure what the term bottleneck adds to the definition nor was I sure if that was correct. Is that the correct definition?

While I suspect that the notion of "bottleneck" has been introduced in an earlier lesson, it's all in the document you link.

Page 8:

  Edmonds and Karp’s first rule is essentially a greedy algorithm:

    Choose the augmenting path with largest bottleneck value.

Page 11:

  For any flow network $G$ and any vertices $u$ and $v$, let bottleneck
  $G(u,v)$ denote the maximum, over all paths $\pi$ in $G$ from $u$ to $v$,
  of the minimum-capacity edge along $\pi$.

This sentence is a bit hard to parse. Unfolded:

Let $P_G(u,v)$ be the set of all $u$-$v$-paths in $G$, and $E(\pi)$ the set of edges that comprise a path $\pi$ in $G$. Then,

$\qquad\displaystyle G(u,v) = \max_{\pi \in P_G(u,v)} \quad \min_{e \in E(\pi)} c(e)$.

Note that $\min_{e \in E(\pi)} c(e)$ is the bottleneck (capacity) of $\pi$.

So Edmongs-Karp picks the $s$-$t$-path with the largest bottleneck (in the residual network), which means it picks the path it can send the most flow over (while maintaining conservation of flows).


Find a truth assignment of 2SAT that has the most number of true variables? Given a 2SAT instance in CNF where each clause has at most two literals. Let $m$ be the number of clauses and $n$ be the number of variables et let $k$ be a positive number.

Question: Is there a truth assignment such that the number of variables that are true is $k$ or more?

I cannot find the name of this problem, if it was already studied? If so, is it NP-hard?

Your problem is known as Weighted-2-satisfiability, and is known to be NP-complete. The easiest way to see that is by reduction from Vertex Cover (exercise).

Note that the link above is about whether there is a satisfying assignment having at most $k$ true variables. This is equivalent to your problem (exercise).


Show that A** subset of A*, where A is a regular language I do not understand the proof for this. I know that every word in $(A^*)^*$ is made up of words from $A^*$, and that this is made up from words in $A$. But how does this help with showing that $(A^*)^*$ is a subset of $A^*$.

Knowing that $A$ is regular is not relevant.

Hint. Just replace "made up of words of $A^*$" by "is a concatenation of words of $A^*$" in your sentence and you will have the answer.


Proving a certain superset the halting language is not recursive Let $\Sigma =\{ 0, 1\}$. Let $val:\Sigma^* \rightarrow \mathbb{N}$ be a function that given a string returns its decimal value, and $L_{halt} = \{\langle M\rangle \langle w\rangle \mid M $ halts on $w \}$.

I define the following language:

$L=\{ x \mid x\neq x^R \wedge (x\in L_1 \vee x\in L_2 \vee x\in L_3)\}$

where:

$L_1=\{ x \mid x\in L_{halt} \wedge x^R \in L_{halt} \wedge val(x)<val(x^R) \}$
$L_2=\{ x \mid x\notin L_{halt} \wedge x^R \notin L_{halt} \wedge val(x)<val(x^R) \}$
$L_3=\{ x \mid x\in L_{halt} \wedge x^R \notin L_{halt} \}$ (in this language there is no requirement on $val$ function)

That is, a string in $L$ has 3 options how to look like.

Intuitively I can feel that $L\notin R$, but I do not know how to approach a formal proof for this.

I tried using a reduction $L_{halt} \leq L$, and then since $L_{halt}\notin R$ I can deduce that $L\notin R$, but I could not find a reduction that will work.

The closest thing I could come up with is using an intermediate reduction, first defining $L_{halt}^{'} =\{ 1  x 0 \mid x \in L_{halt} \}$ and then easily $L_{halt} \leq L_{halt}^{'}$ and all I have to do is $L_{halt}^{'} \leq L$, so my idea for reduction was given $x=1y0$ then $f(x)=y$ (the reduction returns $y$), but then this reduction has a problem if $y\notin L_{halt}$ and $y^R\notin L_{halt}$ then it might be possible that $val(y) < val(y^R)$ and then $f(x)=y\in L$ but $y\notin L_{halt}^{'}$...

I'm kind of stuck at how my reduction should work?

I'm also assuming that any string from $\Sigma^*$ is a possible encoding of a $<M><w>$, that is I cannot assume something about the encoding itself and also every word is a possible encoding of $\langle M\rangle \langle w\rangle$...

Main idea of the proof is since $L$ is kind of superset of $L_{halt}$ we select reduction in such a way that we always deal with only that subset of $L$ which resembles $L_{halt}$.

First let us choose any encoding such that if $\langle M,w \rangle \in L_{halt}$ then $\langle M,w \rangle^R \not\in L_{halt}$. $L_{halt}$ is undecidable in every reasonable encoding so this is okay. Also this will be true for most of the encodings if we include $\langle \rangle$ also in the encoding. (Reverse will be $\rangle w^R, M^R \langle$). Also we should have $val(\langle) > val(\rangle)$. I assume that $val$ is calculated as a number with base $|\Gamma|$ where $\Gamma$ is the tape alphabet. In the question decimal base is mentioned, which means the same. We need to add extra 4 bits (= 1 decimal digit) in each cell if we do not have enough space for new symbols.

For this encoding we can have an identity reduction for valid input of the form $\langle M,w \rangle$. For invalid input not of the form $\langle M,w \rangle$ we shall reduce the input to $\langle\epsilon,\epsilon\rangle$ which does not belong to $L$. Let us call this reduction $f$. We assume that in our encoding $\langle\epsilon,\epsilon\rangle \not\in L_{halt}$.

We can now easily prove $x \in L_{halt}$ if and only if $f(x) \in L$.

($\Rightarrow$)
Let $x = \langle M,w \rangle \in L_{halt}$.
Then clearly $val(x) > val(x ^R)$.
And $\langle M,w \rangle^R \not\in L_{halt}$.
Therefore $\langle M,w \rangle \in L_3$ and hence $\langle M,w \rangle \in L$ as naturally $x \neq x^R$, Symbols $\langle,\rangle$ ensures that $x \neq x^R$.

($\Leftarrow$)

Note it $f(x) = \langle \epsilon, \epsilon \rangle$ then it does not belong to $L$. So take the other valid cases.

Let $f(x)= y =\langle M,w \rangle \in L$.
Then $\langle M,w \rangle \in L_3$, as $val(y) > val(y^R)$.
This gives us $\langle M,w \rangle \in L_{halt}$ straight away.

The idea of this proof holds even if we are given a specific encoding for $L$ as well.

1) If the encoding for $L$ is such that we do not have begin symbol $\langle$ and end symbol $\rangle$. Also assume $x_{reject}$ is a string such that $x_{reject} \not\in L$. We can easily find such a string as $L \neq \Sigma^*$. In this case the strings got by reduction will not be necessarily in $L_3$. We also assume our encoding of turing machines is such that we can find a string $\alpha$ such that $0^*\alpha$ is never a proper prefix.

To always get strings in $L_3$ we define the reduction as follows. All invalid input strings which are not of the form $\langle M,w \rangle$ are reduced to $x_{reject}$, and all valid input strings which are of the form $\langle M,w \rangle$ are reduced to $\langle M',w\alpha^R0^{|M'|+1}\rangle$. $M'$ will remove suffix $\alpha^R0^*$ and then behave as $M$.

With this reduction the proof given above can be modified slightly to prove that $L$ is undecidable.

If the encoding for $L$ is such that $\langle$ and $\rangle$ are always included and $val(\langle) < val(\rangle)$ then in the reductions given above we will always get strings from set $L_1$ and $L_2$. In this case by using $\alpha^R0^*$ suffix it is easier to get reduced strings from set $L_2$. Then it is better to reduce language $\overline{L_{halt}}$ which is also undecidable to $L$ to prove undecidability of $L$.


What is the index of the leftest child of node in a k-nery heap? Suppose the root node‘s index is 1, what is the index of the leftest child of a node e in a k-nery heap? What is the parent‘s index of a node in k-nery heap?

All questions regarding my problem I found talk about binary heaps, I just can’t think of a simple solution.

Let's assume you store the nodes by level and then from left to right. Here are the first few levels:

Root: $1$
Children of root: $2,\ldots,k+1$
Grandchildren of root: Children of $2$: $k+2,\ldots,2k+1$; Children of $3$: $2k+2,\ldots,3k+1$, ...

Let us guess that just like in the binary case, the formula for the leftmost child of $v$ is of the form $\alpha v + \beta$.

If we consider two adjacent nodes at the same level, their leftmost children will differ by $k$ (for example, leftmost child of $2$ is $k+2$, whereas leftmost child of $3$ is $2k+2$), hence $\alpha = k$.

We can find $\beta$ by considering the root: $k \cdot 1 + \beta = 2$ implies that $\beta = -(k-2)$. Overall, we get
$$
kv-(k-2) = k(v-1) + 2.
$$
This works for the root by construction. When $v = 2$, we get $k (2-1) + 2 = k+2$, which also works out. My guess it that this formula works out, and you should be able to prove it by induction. That's where you come in...


LALR(1) parsers and the epsilon transition I am having trouble getting my head wrapped around epsilon transitions while creating an LALR(1) parse table.

Here's a grammar that recognizes any number of 'a' followed by a 'b'. 'S' is an artificial start state. '$' is an artificial 'EOS' token.

0.    S -> A $
1.    A -> B b
2.    B -> B a
3.    B -> epsilon

Itemsets:

i0: S -> . A $
    A -> .B b
    B -> .B a
    A -> B . b  ! because B could -> epsilon
    B -> B . a  !    "

i1: S -> A . $

i2: S -> A $ .

i3: A -> B . b  ! from i0
    B -> B . a

i4: A -> B b .  ! from i0 or i3; the LALR algorithm compresses identical states.

i5: B -> B a .  ! from i0 or i3: the LALR algorithm compresses identical states.

I previously had a description on how this would work to parse a simple string. I removed it because I know less now than I did before. I can't even figure out a parse tree for 'ab'.

If someone could show me how I have mis-constructed my itemsets and how I'd reduce the epsilon transition I'd be grateful.

Your states and itemsets are not quite correct. The epsilon production must appear in relevant itemsets, and you have combined two states into one, which would produce a shift-reduce conflict if the epsilon production were added to the itemset (which should be done).

The following was generated with bison (using the --report=all command-line option); it differs from the theoretic model because the grammar has been "augmented" with an extra start symbol and an explicit end-of-input marker ($end). Also, it has done some table compression, so in the action tables, you can think of $default as meaning "either a or b".

It is worth explaining how State 0 comes about, since it shows how epsilon productions are handled (no differently from other productions).

We start with $accept: . S $end, by definition. ($accept is the starting state). Then the closure rule is applied as long as possible. Remember that the closure rule is: If any item in the itemset, the . is immediately before a non-terminal, add all the productions for that non-terminal with an initial .. Hence we add:

S: . A

continuing with A:

A: . B 'b'

continuing with B:

B: . B 'a'
B: .

We can't apply closure any longer, so we're done. Since the state now has an item with the dot at the end (the epsilon production for B), a reduction is possible.

State 0
    0 $accept: . S $end
    1 S: . A
    2 A: . B 'b'
    3 B: . B 'a'
    4  | .

    $default  reduce using rule 4 (B)
    S  go to state 1
    A  go to state 2
    B  go to state 3

State 1
    0 $accept: S . $end

    $end  shift, and go to state 4

State 2
    1 S: A .

    $default  reduce using rule 1 (S)

State 3
    2 A: B . 'b'
    3 B: B . 'a'

    'b'  shift, and go to state 5
    'a'  shift, and go to state 6

State 4
    0 $accept: S $end .

    $default  accept

State 5
    2 A: B 'b' .

    $default  reduce using rule 2 (A)

State 6
    3 B: B 'a' .

    $default  reduce using rule 3 (B)

In State 0, the closure rule has added the epsilon production (line 4). Furthermore, no item in the state 0 itemset has the point before a terminal. So with any lookahead, the parser is forced to reduce the epsilon production, after which it will use the goto function for state 0 to decide to move to state 3. (In your state machine, states 0 and 3 are conflated, but I do not believe this is correct.) State 3 will definitely shift a terminal; with the input ab$end, it will shift the a and move to state 6, which will then reduce a B. And so on.


Computing minimum partition of poset of $N$ intervals into chains in $o(N^{2.5})$ time? Consider a set $P$ of $N$ intervals $\{I_i = (l_i, r_i)\}$ partially ordered according the standard interval order: $I_i < I_j$ iff $r_i \le l_j$.

I want to find a minimum cardinality partition of $P$ into chains. By Dilworth's theorem, the cardinality will equal the maximum cardinality of any antichain. We can find such a maximum antichain in $O(N\log N)$ time: note that $I_i$ and $I_j$ are incomparable iff $I_i\cap I_j \ne \emptyset$, and applying Helly's theorem in one dimension, deduce that any antichain has nonempty overall intersection, and hence any maximal antichain $A$ is exactly the set of intervals containing $x$ (let us call this $A(x)$) for some point $x$. So it is sufficient to find a point $x$ that maximizes $|A(x)|$. After sorting the endpoints this can be done in $O(N)$ time.

I'm having trouble getting the dual partition though. We can find an optimal partition in $O(N^{2.5})$ time using Hopcroft-Karp to compute a maximum bipartite matching, but it seems like it should be possible to get close to linear time in this case using the duality between antichains and chain partitions. Unfortunately staring at the Wikipedia pages for Dilworth's and Kőnig's theorems doesn't seem to be getting me anywhere.

Your problem is the same as interval graph coloring.

There is a well-known greedy algorithm solving the problem optimally, running in linear time if the intervals are already sorted.


Number of Retransmission in case of Go Back N While Going through Exercise problem of " Computer Networking  A Top-Down Approach" by Kurose and Ross, i encountered this problem.I am giving my approach and the point where i am stuck at.
Question

Suppose Host A sends 5 data segments to Host B, and the 2nd segment
(sent from A) is lost. In the end, all 5 data segments have been correctly
received by Host B.How many segments has Host A sent in total and how many ACKs has Host B sent in total for Go Back N

Given Answer

GoBackN:
$A$ sends $9$ segments in total. They are initially sent segments $1, 2, 3, 4, 5 $and later resent segments $2, 3, 4, $and $5$. $B$ sends $8$ ACKs. They are $4$ ACKS with sequence number $1,$ and $4$ ACKS with sequence numbers $2, 3, 4,$ and $5.$

My Approach /Doubt
I agree with the number of transmission of data segment by Host $A$.But i have doubt regarding the Acknowledgement by Host $B$.
Why?

We know that GBN has sender side window size=$N$ while reciever side as only$1$ which is the reason that it cannot  recieve Out of order packet.

Now When Host $A$ sends entire packet $1,2,3,4,5$  where $2^{nd}$ gets lost then Host $B$ which is expecting Sequence number $1$.On recieving sequence number $1$, it will send ack as $2$i.e expecting sequence number $2$.As Sequence number gets lost , host $B$ will recieve sequence $3,4,5$ for which it will discard the packet as it is not the packet it is expecting.
On recieving again sequence number $2,3,4,5$(retransmitted packet), Host $B$ will send the Acknowledgement.
Total Acknowledgement i am getting is $5$ i.e ACk no for sequence number $1,2,3,4,5$ not $8$.
Please help me out where i am wrong ??
Thanks

GBN is resending ACK's for the discarded packets .

Excerpt from what I can find:

The receiver's actions in GBN are also simple. If a packet with sequence number n is received correctly and is in-order (i.e., the data last delivered to the upper layer came from a packet with sequence number n-1), the receiver sends an ACK for packet n and delivers the data portion of the packet to the upper layer. In all other cases, the receiver discards the packet and resends an ACK for the most recently received in-order packet. Note that since packets are delivered one-at-a-time to the upper layer, if packet k has been received and delivered, then all packets with a sequence number lower than k have also been delivered. Thus, the use of cumulative acknowledgements is a natural choice for GBN.


Assuming P = NP, how would one solve the graph coloring problem in polynomial time? Assuming we have $\sf P = NP$, how would I show how to solve the graph coloring problem in polynomial time?

Given a graph $G = (V,E)$, find a valid coloring $\chi(G) : V \to \{1,2,\cdots,k\}$ for some $k$ satisfying the property that $(u,v) \in E$ implies $\chi(u)\ne\chi(v)$ so as to minimize the fewest number $k$ of “colors”.

There are two cases:

$P = NP$ non-constructively: this means we have derived a contradiction from the assumption that $P \neq NP$, and thus can conclude that $P = NP$ by the law of the excluded middle. In this case, we have no idea what an algorithm to solve graph coloring in polynomial time looks like, or any other problem. We know one exists, because we know that if it doesn't exist, we can derive a contradiction. So a proof of this form is pretty useless for solving problems quickly.
$P = NP$ constructively. In this case, we have a polynomial time algorithm for some $NP$-hard problem, let's say $L$. If $L$ is NP-hard, then it must solve some other NP-hard problem in polynomial time (i.e. it reduces from that problem). That problem, in turn, either reduces from another problem, or has a direct reduction from every problem in $NP$. We keep following the trail of reductions until we get to one with a direct proof (probably 3SAT).

By composing these reductions, we get an algorithm that solves 3SAT in polynomial time (because each reduction only makes a polynomial number of calls to the previous algorithm, and our starting algorithm for $L$ runs in polynomial time.

We then plug that algorithm into the reduction from Cook-Levin theorem, which gives us a way to simulate any algorithm running in Polynomial time with a polynomial number of calls to a 3SAT solver. Again, a polynomial number of calls to a polynomial-time algorithm runs in polynomial time.

Finally, there is a simple non-deterministic algorithm that solves Graph-coloring in polynomial time: just guess a coloring and check if it's valid. So we use Cook-Levin to simulate this algorithm in polynomial time.

As you can imagine, each time we have to compose a reduction, the degree of our polynomial is going to get higher and higher. So it's entirely possible that $P = NP$ but graph colouring can only be solved in, say, $O(n^{100000000000000})$ time. This is still polynomial time, but it really doesn't buy us much in terms of practically solving problems.


Is there a way to create a "captcha"-like problem that computers can verify, but only humans can solve? In a normal CAPTCHA scenario, a computer creates a challenge and a correct response to it.  (The challenge is an image of distorted text, for instance, and the response is the characters depicted.)  These are constructed so that hopefully a human can easily determine the response from the challenge, but a computer cannot.  Ordinarily only the originating computer, which already knows the correct response, can determine whether a given response was correct.

My question: is it possible to create a CAPTCHA that computers can verify, but not solve?  In other words, is it possible to create a scenario that looks like this:

Computer A generates a challenge, sends it to Human B and Computer C

Computer C cannot feasibly determine the correct response, other than by brute-force search (which can hopefully be made impractical by the size of the response.)

Human B can feasibly determine the correct response.  ("Feasibly" is not easy to define.  We need the response to be much bigger than normal CAPTCHAs in order to deter simple brute-force searching by computers, so "as easy as a normal CAPTCHA" is going to be impossible.  But it's not out of the realm of possibility to make a human type in a large response.  It'd just be really annoying. A few hundred printable characters can get to 2048 bits, for instance.  So as a rough definition: it's allowed it to be annoying as hell, but it has to at least be feasible for a person.  Assume the person's physical and mental abilities are roughly average for a literate computer user.)

If Human B sends Computer C the correct response, Computer C can feasibly verify that the response is correct, without contacting computer A or having any prior knowledge other than the challenge.

Would it be possible, under today's technology and knowledge, to create such a protocol?

Furthermore, would it be possible to design the protocol such that even Computer A can't determine the correct response to the challenge it just generated without human input--and Computer C can verify that Computer A could not have known the response without a human providing the solution?  If this all this can be achieved, then the result is analogous to the "proof of work" seen in bitcoin and other protocols.  Instead of a proof of computational work, we'd have a proof of human work--the combination of the challenge and correct response would constitute proof that a human spent some marginal amount of effort.  This proof would then be verifiable by any computer.  Is such a thing even remotely plausible?

Of course, at some point in the future computers will probably overtake humans altogether.  Once that happens, there will not be any problems that are feasible for a human but not a computer, and therefore no CAPTCHAs or CAPTCHA-like protocols will be possible.

But what about under currently known human and computer abilities?

Yes.  Computer A can generate a CAPTCHA encoding a 24-digit code, and also compute a cryptographic hash of the correct response.  Computer A can give the CAPTCHA and the hash to B and C.  Now if B claims to have solved the CAPTCHA, computer C can verify the claimed answer using the cryptographic hash.  The cryptographic hash doesn't help computer C solve the challenge, because the hash is one-way and cannot be inverted (except by trying all possible codes, but that would take far too long).

In practice, this is not very effective, because no one knows how to build a CAPTCHA that humans can solve but that is expensive for computers to solve.  For one thing, there are black-market services that will solve CAPTCHAs for you at the price of about $1-2 per thousand CAPTCHAs solved, i.e., about 0.1-0.2 cents per CAPTCHA.  For another, there are algorithms that break most CAPTCHAs with probability higher than we'd like.  So ultimately, CAPTCHAs kinda suck.  But the reasons they suck have nothing to do with verifiability.  If we could make a CAPTCHA that didn't suck, we could probably build one that was verifiable in the sense you mention.

Also, if you were implementing this in real life, you'd make sure to use a slow hash (like PBKDF2, scrypt, or bcrypt) when hashing the code.  But again, because CAPTCHAs have so many limitations, I'm not sure you'd want to implement this scheme in real life anyway.


Is it possible to compute how many iterations this algorithm will take? I want to know exactly how many iterations it would take this algorithm to terminate. In other words, is there a closed-form solution for the number of iterations? (For my input values, it is always guaranteed to terminate.)

Let $x$, $y$, and $z$ be some positive integers.
The values of $x$, $y$, and $z$ are chosen such that neither $y$ nor $z$ will become $\le 0$ before the loop terminates.

$\text{do}$

$\qquad \text{if } (x+y) \text{ mod } z = 0 \text{ then done}$

$\qquad x \leftarrow x + y$

$\qquad y \leftarrow y - 4$

$\qquad z \leftarrow z - 2$

$\text{loop}$

For example, if we let $x =184$, $y = 376$, and $z = 187$, this algorithm terminates in $19$ loops.

Here is a plot of $(x+y) \text{ mod  } z$ for some real inputs. Here is another plot for larger inputs.

There might be no clean formula for that.

The values of $x,y,z$ after the $n$th iteration of the loop are $x_0 + (n+1) y_0 - 2n(n+1)$, $y_0 - 4n$, and $z_0 - 2n$, respectively, as can be verified by induction, where $x_0,y_0,z_0$ are their initial values (before the first iteration of the loop).   The loop terminates for the smallest positive integer $n$ such that

$$x_0 + (n+1) y_0 - 2n(n+1) + y_0 - 4n \equiv 0 \pmod{z_0 - 2n}.$$

There might not be any nice expression for the smallest $n$ that satisfies that equation, in terms of $x_0,y_0,z_0$.  It's also not obvious to me whether such an $n$ always exists, i.e., whether your loop will always terminate.

I'm glossing over a serious issue that you haven't addressed in the question: what is the meaning of $(x+y) \bmod z$ when $z=0$ or when $z<0$?  It's not clear, and that will affect the answer.