Why does Bellman-Ford algorithm use < rather than ≤? The Bellman-Ford Algorithm uses a less-than symbol rather than a less-than-or-equal-to symbol. How does this identify that there is a negative cycle?

For instance, say I have the below example going from initialization state through the first iteration and on to the second.

Initial state

    (0)S----(1)----B(inf)
        \         /
        (1)    (-1)
          \     /
           \   /
             C(inf)

First phase

...Check edges...
S->B
D[S] + 1 < D[B] = 0 + 1 < inf => True => Update D[B]

B->C
D[B] + (-1) < D[C] = 1 + (-1) < inf => True => Update D[C]

    (0)S----(1)----B(1)
        \         /
        (1)    (-1)
          \     /
           \   /
             C(0)

Second phase when checking for negative cycles

...Check edges...
...Skipping to check B->C...
B->C
D[B] + (-1) < D[C] = 1 + (-1) < 0 => False

    (0)S----(1)----B(1)
        \         /
        (1)    (-1)
          \     /
           \   /
             C(0)

Shouldn't the last check between B->C be true to detect the negative cycle? i.e. Shouldn't we use less-than-or-equal-to (≤) rather than (<)?

First of all, let me clarify a few points about your example:

Bellman-Ford-Moore consists of two phases, stages or steps, each one consisting of a number of iterations as they are implemented with loops. The first phase computes the cost of the shortest-path to reach each vertex from the start vertex and it consists of two nested loops; the second one consists of a single loop which checks whether there are negative cycles or not. I mention this because it seems to me that you refer to the phases as iterations.
Let me also note that in the first phase you skip the evaluation of reaching $S$ from $C$. I assume you just simply avoid making the computation because it is pointless for exemplifying your case, but let me just highlight that Bellman-Ford-Moore would also perform that evaluation. By the way, it is unclear whether you are considering a directed or undirected graph. I just assumed it is directed: $S\rightarrow B\rightarrow C\rightarrow S$.
As noted in the comments by xskxzr, there is no negative cycle in your exmaple. A negative cycle is defined as a path which starts and ends in the same vertex whose overall cost (defined as the sum of all edge costs) is strictly negative. In your case, there is only one cycle from $S$ to it, but it has a cost which is is strictly positive: $c(S, B) + c(B, C) + c(C,S)=1-1+1=1>0$.

I mention these points only to make the answer clearer (if possible) and more useful to other readers.

I will try now to address your question. Once the first phase is over, the distance of the shortest-path from the start vertex $S$ to all other vertices in your graph has been already computed. Let $d_i$ denote the cost of the shortest path from $S$ to the $i$-th vertex.

Consider now any vertex of your graph, $v_i$, and all incident edges to it. Clearly, at least one should be in the shortest-path from $S$, whereas all the others should not. Take any vertex $u$ which has an edge from it to $v_i$:

If the edge $\langle u, v_i\rangle$ is part of the optimal path from $S$ to $v_i$ then clearly $d_u + c(u, v_i)=d_{v_i}$
Otherwise, $d_u + c(u, v_i)>d_{v_i}$ as this is not part of the optimal path.

Thus, when starting the second phase (for detecting negative cycles), there is at least one edge for each vertex for which equality holds without the presence of negative cycles! This is just a consequence of the definition of shortest-path as shown above. This observation precludes the usage of $\leq$ for detecting cycles, as equality holds without negative cycles.

Let us now consider the case of negative cycles. Their essential property is that they  decrease the value of reaching its final vertex indefinitely (as crossing it again would reduce the cost to reach its end vertex), i.e., negative cycles strictly decrease the cost of reaching its end vertex and hence, the only way $d_u + c(u, v_i) < d_{v_i}$ is because there is at least one negative cycle.

In your specific example, make $c(C,S)=-1$. Now you have a negative cycle from $S$ to itself. Clearly, once the first phase is over, the cost of the shortest distances computed by Bellman-Ford-Moore would be: $d_S = -2, d_B = 0, d_C = -1$. I assume the following order of edges: $\langle S, B\rangle$, $\langle B, C\rangle$ and $\langle C, S\rangle$ and recall that the first phase is ran as many times as edges minus 1, i.e., twice in your example. So far, after the first iteration (which considers updating the target vertex of all edges in the order given above) of the first phase $d_S = -1, d_B = 1, d_C = 0$. Because Bellman-Ford-Moore dictates to run the first phase as many times as vertices minus one (the reason beig that the costs computed in the previous iteration should be propagated to the longest path whose number of edges is upper bounded by the number of vertices minus 1), a second iteration of the first phase is conducted and the cost of the shortest-path to all vertices gets decremented again, $d_S = -2, d_B = 0, d_C = -1$.

Next, when running the second phase it turns out that $d_S + c(S,B) = -2 + 1 = -1 < d_B = 0$ which reveals the presence of the negative cycle using $<$.

Hope this helps,


Modeling timing characterists of an architecture I am building a system and I have a couple of architectures in mind. I want to have an idea of which architecture is likely to be most performant (quickest).

I can make different decisions like
1) Do everything in one thread
2) Separate this part into one thread, that part into another thread since it can run in parallel and so on

Instead of actually building the system in two different ways and seeing how it performs, is there a way to quickly model/prototype the system where I can express the above concepts and the times it takes for inter thread I/O etc (of which I have a very good estimate) and use the model/prototype to estimate which architecture is better?

The simple answer is to just build the simplest architecture that gives the results you want. You will have lots of problems anyway, making the system more complex than strictly required is just making more work. And a simple architecture is probably more performant than a more complex one, and easier to work with for further analysis.

Once it is running, check if the performance is enough. If it isn't, measure where it doesn't is up to the task (programmers are notoriously unreliable at estimating that, another reason not to "optimize" before seeing results), then go searching for ways of increasing performance. The most gain can be gotten by architecture changes, then selection of algorithms and data structures, and at the very end local changes (but most of those your compiler will make anyway). Independent of the above, a faster machine might be cheaper than the programmer time required to redo the code.


Left recursion and left factoring -- which one goes first? if I have a grammar having a production that contains both left recursion and left factoring like

$\qquad \displaystyle F \to FBa \mid cDS \mid c$

which one has priority, left recursion or left factoring?

Transformations such as left factoring or removing left recursion do not have precedence rules. Obviously, the resulting grammars may be different but they will recognize the same language.

The question's example grammar is more difficult than the typical undergrad homework problem. So showing our work will be useful.

Left Recursion

Let's define a transformation that removes left recursion.

Given

$\qquad \displaystyle A \to A\alpha_0 \mid A \alpha_1 \mid \dots \mid A \alpha_n \mid B \beta_0 \mid B \beta_1 \mid \dots \mid B\beta_n$,

we remove left recursion like this:

$\qquad \displaystyle \begin{align}
    A_h &\to B \beta_0 \mid B \beta_1 \mid \dots \mid B \beta_n \\
    A_t &\to \alpha_0 \mid \alpha_1 \mid \dots \mid \alpha_n \\
    A_{t^+} &\to A_t A_{t^+} \mid A_t \\
    A &\to A_h A_{t^+} \mid A_h
\end{align}$

The generality of above is typically not given in compiler texts, but parsing texts like Grune & Jacobs do cover this. Left factoring can be applied to the above transformed grammar but will be just introduce extra rules that will not change the answer. So we will simplify the presentation without extra left factoring being performed.

In this answer we will not cover indirect left recursion issues because we are only concerned with a single non-terminal's rules. Note that indirect left recursion can be dealt with, though. (Open a separate question if that is important.)

Left Factoring

Removing left factoring is in most introductory compiler texts done like this. Given

$\qquad \displaystyle A \to x y \mid x z$

left factoring yields:

$\qquad \displaystyle \begin{align}
 A_s &\to y \mid z \\
 A &\to x A_s
\end{align}$

Now that's perform the transformations in both ordering.

Left factoring first

Let's left factor the question's grammar

$\qquad \displaystyle \begin{align}
    F_s &\to D S \mid \varepsilon \\
    F &\to F B a \mid c F_s
\end{align}$

and then remove the left recursion:

$\qquad \displaystyle \begin{align}
    F_h &\to c F_s \\
    F_t &\to B a \\
    F_{t^+} &\to F_t F_{t^+} | F_t \\
    F_s &\to D S \mid \varepsilon \\
    F &\to F_h F_{t^+} \mid F_h
\end{align}$

Removing left-recursion first

And for the other ordering, let's remove left recursion from the question's grammar

$\qquad \displaystyle \begin{align}
    F_h &\to c D S \mid c \\
    F_t &\to B a \\
    F_{t^+} &\to F_t F_{t^+} \mid F_t \\
    F &\to F_h F_{t^+} \mid F_h
\end{align}$

and then left factor the terminal $c$:

$\qquad \displaystyle \begin{align}
    F_{hs} &\to D S \mid \varepsilon \\
    F_h &\to c F_{hs} \\
    F_t &\to B a \\
    F_{t^+} &\to F_t F_{t^+} \mid F_t \\
    F &\to F_h F_{t^+} \mid F_h
\end{align}$

Aha, the resulting grammars are the same!

In general, proving that two grammars are equivalent is undecidable. So if a series grammar transformations could influence the language that is recognized then, it would be disastrous.


Fast software pipelining for stream processing I have a pipelined stream processing situation, where a number of streams is linked in the computational process S0 -> S1 -> S2 -> .... You can understand "stream" as a list of numbers.
In this process, S0 is initially given in totality. S1 is a mapped result from S0 according to function f; S2 is the result from S1 by the same f, so on and so on. f(S) works by traversing stream S linearly and produces the resulting stream as it goes. Hence, f can work on a stream "partially": that is, for example, we don't need the totality of stream S1 in order to begin producing S2. The processing S0->S1 can occur concurrently with S1->S2 in a pipelined fashion.
I attempted implementing this pipeline using C. In my code, I use an atomic variable to synchronize progress between each pipeline stage $S_i\quad\overrightarrow{\small f_i}\quad S_{i+1}$: basically, thread $f_i$ constantly polls progress from the previous pipeline $f_{i-1}$ to see if new tokens are written into $S_i$. If so, it continues its own work. Otherwise, it spins and waits. Of course, this assumes each $f_i$ is responsible for reporting its progress to $f_{i+1}$. It turns out that this synchronization is too costly. I wasn't able to gain any speedup using multiple threads. In fact, it makes the code much slower than a single-threaded implementation.
My question is, what is a better approach to implement this construction in order to actually take advantage of multi-threading? This seems to be very hard because the $f$ in my scenario is computational-bound. It seems to me highly unlikely to extract parallel performance unless there is a very low-cost synchronization scheme. Thanks in advance for any comments and advice.

Do the work in batches.  Have a separate buffer for each stream that stores the unprocessed items.  When you invoke $f$ for stream $S_i$, invoke 100 times on the 100 oldest items in the buffer for $S_{i-1}$, then remove those items from the buffer.  This basically increases the granularity of operations, and should reduce the overhead from synchronization by about 100x.  You can of course tune the number 100 to adjust throughput vs latency.


Prove G have a single MSP We have undirected connective, weighted graph $G = (V,E)$.
we also know that for every $e,e'$ in $E$, $w(e)≠w(e')$.
Prove that $G$ has a single MSP.
Ideas?

I missed the part where $\omega(e) \neq \omega(e')$ for $e\neq e'$ so please only consider my answer for the general case, i.e. Given a graph $G =(V,E)$ how to check if $G$ admits a unique MST.

The answer is based on the following claim.

Claim. An MST $T$ is unique, if and only if each edge $\{u, v\}$ not in $T$ has greater weight than all edges on the path in $T$ between $u$ and $v$.

Assuming for now that the claim is true, the task turns into checking for each edge $\{u, v\} \in E \setminus E(T)$, if the path in $T$ between $u$ and $v$ contains an edge with weight at least $w$. If this is the case the answer is No. If this is not the case for all edges not in the tree, output Yes.

Now we need an algorithmic approach to solve the previous problem. Naively, We start by building an arbitrary MST, then we can traverse the path for each such pair $u, v$, where $\{u, v\}$ is not in the tree. However, in a dense graph (say the complete graph $K_n$), this algorithm has running time of $\theta((n+e)\log n + n^3) = O(n^3)$ since we have $\Theta(n^2)$ edges not in the tree and the length of the path is linear. In the following we show how to do each check in $O(\log n)$ time instead achieving a better total running time.

The trick is to use LCA (lowest common ancestor), a data structure defined on rooted trees, that answers the following queries efficiently. Given a pair of vertices $u, v$ in the tree, find a vertex $w$ with the lowest height, such that $w$ is an ancestor of $u$ and an ancestor of $v$. Note that $x$ is an ancestor of $y$ if it lays on the path from the root of the tree to $y$. LCA can be built in running time $O(n \log n)$ answering queries can be done in $O(\log n)$. there are also better "theoretical" results using sparse-tables. However, this ones suffices our needs. We also need to tweak the data structure to answer queries of the form (what is the maximum weight of a vertex on the unique path from $u$ to $v$), note that this is doable by keeping more data about the tree while building the data structure. Also note the choice of the root in this case does not matter and you can choose any vertex to be root.

Now assuming a black-box is given (the LCA data structure) that in $O(\log n)$ time for two given vertices $u$ and $v$ finds the maximum weight of an edge on the path from $u$ to $v$ in the tree. We can do the following, for each edge $\{u, v\}$ not in the tree, call the black-box on $u, v$. If the answer is at least the weight of the edge, output No. If the answer is less than the weight for all edges not present in the tree, output Yes. The running time can be found as follows. We need $O((n+m)\log n)$ to build an MST. We need $O(n \log n)$ to build the LCA data structure (including rooting the tree and computing the depth and the parent of each vertex). We need $O(\log n)$ pro query totaling in $O(m \log n)$ for all queries. Hence a total running time of $O((n+m)\log n)$.

Now we still have to prove the claim presented in the beginning, namely that the tree is unique if and only if for each edge $\{u, v\}$ not in the tree, all the edges on the path between $u$ and $v$ in the tree have strictly smaller weight than the edge $\{u, v\}$.

Proof. Let $\omega: E \rightarrow R$  be the weight function. Assuming there is an edge $\{u, v\}$, such that the path in $T$ between $u$ and $v$ contains and edge $\{x, y\}$ where $w(\{u, v\} \leq w(\{x, y\})$. Then by removing $\{x, y\}$ from the tree adn adding $\{u, v\}$ we get a spanning tree of total weight at least as good as $T$ and hence an MST is not unique. Try to see why the resulting structure is a tree.

For the other direction, we prove the following claim. If there is a simple cycle $C$ where an edge $\{u, v\} \in C$ is heavier than all other edges in the cycle, then there is no $MST$ containing $\{u, v\}$ as an edge. Assuming there is such a tree, by removing $\{u, v\}$ from the tree, we get two connected components. One of the edges in the cycle (say $e'$) must also connect these two components (since cycles are 2-connected) and hence we can  add $e'$ to build a strictly lighter MST, contradicting the claim that the given tree was an MST. Hence $\{u,  v\}$ is not in any MST as claimed. Now complete the original proof, note that the path in the tree from $u$ to $v$ with the edge $\{u, v\}$ build a cycle. Hence, we output Yes if all edges not in the tree are heavy for some cycle and hence cannot appear in any minimum spanning tree.


Determine the optimal strategy and maximize the reward Given an array of length n filled with objects which contain 2 ints (size and reward).

Now 2 players are taking turns, each player has an int value we call strength. Let's call them player A and player B, player A goes first.

Player A can pick whichever object from the array he wants and decrease the size of the object by his strength (pickedObj.size -= playerA.strength), he can also skip his turn by simply not picking an object.

Player B is simple minded and for all his turns uses the same greedy strategy: he picks the object with the smallest size and decreases it's size by his strength (pickedObj.size -= playerB.strength), player B can't skip turns.

Once a player decreases the size of an object to 0 (or bellow) he receives the reward (playerX.reward += finishedObj.reward) associated with that object. Each player starts with 0 reward points (playerX.reward = 0).

Given an array with n objects, player A with strength = m and player B with strength = k, compute the maximal amount of reward points that player A can win.

Examples:

Example 1:

obj[] array = `{ (9,5), (6,2), (7,3) }`;
playerA.strength = 4;
PlayerB.strength = 5;

int solution = determineMaxReward(array, 4, 5);

// The solution (max amount of money player A can win) is 10.

Explanation:

Round 1: Player A skips this round, player B picks arr[1] and therefore decreases it's size by his strength (now arr[1] = (1,2)).
Round 2: Player A picks and finishes arr[1] (playerA.reward += 2), player B picks arr[2] (arr[2] = (2,3))
Round 3: Player A picks and finishes arr[2] (playerA.reward += 3), player B picks arr[0] (arr[0] = (4,5))
Round 4: Player A picks and finishes arr[0] (playerA.reward += 5)

That's an optimal game for player A, the at the end he is left with 10 reward points which is the maximal amount of reward points he can possibly achieve.

Example 2:

obj[] array = `{ (2,1), (2,5) }`;
playerA.strength = 1;
PlayerB.strength = 2;

int solution = determineMaxReward(array, 1, 2);

// The solution (max amount of money player A can win) is 5.

Example 3:

obj[] array = `{ (9,3), (10,3), (4,1), (8,1), (9,2) }`;
playerA.strength = 5;
PlayerB.strength = 3;

int solution = determineMaxReward(array, 5, 3);

// The solution (max amount of money player A can win) is 10.

My current unproven (in the sense of optimality) approach:

For each object, I compute the minimal number of picks player A needs to make in order to finish that object. Then I reduce to the knapsack problem, size of the knapsack being the number of picks player A can do during the game, then the best way to fit the objects with their size and reward into the knapsack (such that the reward is maximized) is found.

Now I'm not sure if this is optimal, I can't find a counterexample where my approach doesn't work but I also can't prove that it's optimal. Any help/comments are appreciated.

This is a problem I have been struggling with for a while now, I encountered it during a programming contest in the context of dynamic programming.

The key observation is that, for player A, picking an object which is not being picked by player B is equivalent to skipping the turn and saving this pick for later (for example use a variable savedPicks). Now instead of having to decide upon which object to pick the problem becomes deciding if player A should pick the current object picked by player B or save the pick for later. So we iterate through the objects depending on how player B picks them and either also pick the object as he does or save a pick for later.

Now the problem is solvable with DP, observe that your state consists of the current object which is targeted by player B, the remaining size of the object and the number of picks player A has saved.

There are three transitions:

Object is finished, move to the next one,
Player A skips the round and saves a pick for later (savedPicks++),
Player A uses a saved pick to pick the current object (potentially getting the reward if his pick finished the current object).

Solve each of the three transitions, apply memoization (save already computed states, use a 3 dimensional array for example), don't forget the base case (all objects have been finished).

Happy coding!


Weak hashing function for memorable IPv6 addresses IPv6 addresses in the form of 862A:7373:3386:BF1F:8D77:D3D2:220F:D7E0 are much harder to memorize or even transcribe than the 4 octets of IPv4.

There have been attempts to mitigate this, making IPv6 addresses somehow more memorable.

Is there an intentionally-weak hashing function which could be reversed to find that the phrase, say, "This is relatively benign and easy to spot if the phrase is bent so as to be not worth paying" would hash to a target IPv6 address?  The hash would, of course, have many colliding inputs to choose from, and a potentially more memorable sentence, such as this example phrase, could be automatically offered.

I guess there are two parts: First a weak hash with good distribution in both directions.  Second is an algorithm for selecting memorable phrases from among the many collisions (short, consisting of words from a specified language, perhaps even following a simplified grammar).

Although the hash function would need to be weak, I don't doubt that the effort is still significant - however, once the phrase is known, the computation of the hash to the target address is very quick.

EDIT

I found this related idea, Piphilology, for memorizing some digits of π:

  How I wish a drink, alcoholic of course, after the heavy lectures involving quantum mechanics!

Take the IP address and a wordlist. Then turn the IP address into a list of words from the wordlist based on the digits of the address, base {length of wordlist}.

So, for instance, taking the diceware wordlist and your example, I get: 862A:7373:3386:BF1F:8D77:D3D2:220F:D7E0 -> mew hades cup viii 72 grit photo pick raid dey (or potentially the other way around, and/or padded on the other end).

Note this isn't lossy. Although you can relatively easily apply any lossy techniques to this. You may just wish to truncate the IP address, or only select every second bit or something before running it through this mapping.


Comparing different asymptotic notations Suppose we have 3 algorithms complexity times at the worst case:

A = $O(nlogn)$
B = $O(n\sqrt{n})$
C = $\Theta(n)$

In my opinion, it is not possible to define the best solution, since we don't know how Cgrows. I'd like to confirm if that's correct.

Well, we know how the algorithm C running time grows - it's linear, and it's two-side (lower and upper) bound.

However there is still not enough information to choose the best (meaning: fastest in practice) algorithm here, because:

We know only upper bounds for algorithms A and B - they might be more efficient than C actually, we just don't know that yet.
We don't know constants, hidden in the $\Theta$ bounds - they might make the algorithm C less practical than A or B for limited problem size.

Using the given information we can say only that for some sufficiently large problem size the algorithm C might win over algorithms A and B.


determine if a turing machine halts in less than n step, in less than n step I would like to know if there is a turing machine which can do the following:

take as input a turing machine T and integer n:
return true if the turing machine halts before time n and false otherwise

Clearly such a TM (turning machine) exists. Take the TM that simply runs T for n steps, then if it has halted return true and return false otherwise, however what I would like to know is if there exists a TM that can do better than this. I'm not sure how to formalize this question exactly. so hopefully it is clear what I am asking. Thanks

Maybe the Turing Machine Linear Speed Up Theorem will answer your doubt (https://en.wikipedia.org/wiki/Linear_speedup_theorem)

Counter-intuitively or maybe intuitively, this states that given a Turing Machine which does something in say $n$ steps there are Turing Machines which can solve the same problem in $n/k$ steps for any constant $k$ independent of $n$. These Turing Machines would basically run $k$ steps of the original TM as $1$ step, hence having more state space, but linearly faster.

Was this your question?


what is the time complexity for an algorithm that operations to complete grows by 4 when doubling the input length? I'm working on an algorithm and I'm trying to figure out its time complexity given the operations it takes to complete a input set of specific length, I have been testing the algorithm with varying input lengths.

The results shows that every time I double the input length, it takes 4 times more operations than before to complete:

20 items = 1M (M=million)
40 items = 4M
80 items = 16M
160 items = 64M
320 items = 256M
640 items = 1024M

What is the time complexity/running time that fits better with the above results?

Recurrent equation:
$$T(n) = 4 \cdot T(\frac{n}{2})$$
$$T(1) = O(1)$$
Its solution:
$$T(n) = \Theta(n^2)$$


Proving ALLTM complement not recognizable A few definitions..

$$
\begin{align*}
\mathrm{ALL}_{\mathrm{TM}} &= \Bigl\{\langle M \rangle  \,\Big|\, \text{$M$ a Turing Machine over $\{0,1\}^{*}$},\;\; L(M) = \{0,1\}^{*} \Bigr\}
\\[2ex]
\overline{\mathrm{ALL}}_{\mathrm{TM}} &= \Bigl\{\langle M \rangle  \,\Big|\, \text{$M$ a Turing Machine over $\{0,1\}^{*}$},\;\; L(M) \ne \{0,1\}^{*} \Bigr\}
\\[2ex]
B_{\mathrm{TM}} &= \Bigl\{\langle M \rangle \,\Big|\, \text{$M$ is a Turing Machine over $\{0,1\}^{*}$},\;\; \varepsilon \in L(M) \Bigr\}
\end{align*}
$$

We are showing a reduction from $B_{\mathrm{TM}}$ to $\overline{\mathrm{ALL}}_{\mathrm{TM}}$. In my notes I have the following solution to this problem which I'm trying to understand.

Let $\alpha \in \{0,1\}^*$. Check that $\alpha$ is of form $\langle M \rangle$, where $M$ is a TM over $\{0,1\}$. Else, let $f(\alpha)$ be anything not in $\overline{\mathrm{ALL}}_{\mathrm{TM}}$.
Let $f(\alpha)$ be $\langle M' \rangle$, where $M'$ on $x$ runs $M$ on $\varepsilon$ (blank string) for up to $|x|$ steps. If $M$ accepts (in that time), then $M'$ rejects. Otherwise, $M'$ accepts.

What I'm trying to understand is why must we run the TM $M'$ for $|x|$ steps for this to work? If we change the part #2 of the transformation to the following, why wouldn't this work?

Let $f(\alpha)$ be $\langle M' \rangle$, where $M'$ on $x$ runs $M$ on $\varepsilon$ (blank string). If $M$ accepts, reject. Otherwise accept.

Which then it follows that $\varepsilon \in L(M) \!\iff\! L(M) = \varnothing$,  that is $L(M) \neq \{0,1\}^*$.

First, there is a small typo in (1) - if $\alpha$ is not a legal encoding, then you should return something that is in $ALL_{TM}$ (since you are reducing to the complement).

For your question: the key point here is that a TM does not always halt on its input. Thus, the phrase "otherwise accept" in your suggestion for (2) is not computable. If you run $M$ on $\epsilon$, and $M$ does not halt, then the lanugage of $M'$ will be $\emptyset$, which makes the reduction fail.

In general, when you perform reductions that output a machine that simulates another machine, you must always consider the possibility that the latter will not halt. If this poses a problem (as it does here), a good trick to circumvent it is to limit the step number, and since often you want this limit to exist, but to be ``unbounded'', then using the input for the machine as a limit is a good idea.


Marginal Probability of Generating a Tree Fix some finite graph $G = (V, E)$, and some vertex $x$.

Suppose I generate a random sub-tree of $G$ of size $N$, containing $x$, as follows:

Let $T_0 = \{ x \}$.
For $0 < n \leqslant N$

i. Let $B_n$ be the set of neighbors of $T_{n-1}$ outside of $T_{n-1}$.

ii. Form $T_n$ by

Sample a pair $(x_n, y_n) \in E(G) \cap \left( V (T_{n-1}) \times B_n \right)$, with probability $q_n (x_n, y_n | T_{n-1} )$,
Add $y_n$ to $V(T_{n-1})$, and add $(x_n, y_n)$ to $E (T_{n-1})$.

Return $T_N$.

Suppose also that $q_n ( x_n, y_n | T_{n-1} )$ can be computed easily for all $(T_{n-1}, x_n, y_n)$. I am interested in efficiently and exactly calculating the marginal probability of generating the tree $T_N$, given that I began growing it at $T_0 = \{ x \}$, i.e.

$$P(T_N | T_0 = \{ x \}) = \sum_{x_{1:N}, y_{1:N}} \prod_{n = 1}^N q_n (x_n, y_n | T_{n-1} ).$$

My question is essentially whether I should expect to be able to find an efficient (i.e. polynomial-time) algorithm for this, and if so, what it might be.

Some thoughts:

Naively, the sum has exponentially-many terms, which precludes trying to evaluate the sum directly.
On the other hand, this problem is also highly-structured (trees, recursion, etc.), which might suggest that some sort of dynamic programming approach would be feasible. I'm not sure of exactly how to approach this.
Relatedly, I know how to calculate unbiased, non-negative estimators of $P(T_N | T_0 = \{ x \})$, which have reasonable variance properties, by using techniques from Sequential Monte Carlo / particle filtering. This suggests that the problem is at least possible to approximate well in a reasonable amount of time.

No.  If $q(x_n,y_n|T_{n-1})$ is arbitrary -- there can be an arbitrary dependence on $T_{n-1}$ -- then this requires exponential time.

Consider a tree $T_N$ that has a single root node, $N-1$ leaves, and an edge from the root to each leaf.  There are $2^N$ subtrees of $T_N$, and in particular, there are $2^N$ possible values of $T_n$ that can occur in the expression

$$\sum_{x, y} \prod_{n = 1}^N q_n (x_n, y_n | T_{n-1} ).$$

One can use a simple adversary argument to prove that evaluating this expression requires exponential time.  Suppose that we evaluate $q_n(x_n,x_n|T_{n-1})$ by querying an oracle with $x_n,y_n,T_{n-1}$.  Suppose there is a single tree $T$ that is never queried to the oracle as any $T_{n-1}$.  Choose all of the $q_n(\cdots)$ values to be strictly positive.  Then since $q_n(x_n,y_n|T)$ wasn't queried during execution, we can choose it after observing the output of the algorithm; but by varying it, we can choose a value that makes the algorithm's output wrong (in particular, the value of the expression depends on $q_n(x_n,y_n|T)$ but the algorithm's output doesn't depend on $q_n(x_n,y_n|T)$, so the algorithm's output cannot correct).  We have proven that, to produce the correct output, any correct algorithm must query the oracle for all $2^N$ possible subtrees of $T_N$.  It takes at least $O(1)$ time to query an oracle.

In conclusion, this argument proves that any correct algorithm for computing this expression must take $\Omega(2^N)$ time.

I don't know whether it can always be done in $O(2^N)$ time, or whether perhaps $O(N!)$ time might be required.


$L_{\Sigma^*}=\{\langle M\rangle|L(M)=\Sigma^*\}\notin coRE$ I'm trying to understand why:
$$L_{\Sigma^*}=\{\langle M\rangle|L(M)=\Sigma^*\}\notin coRE$$
As I see it TM, $\langle M\rangle$, should accept all the inputs, and if one of the inputs rejected it's not $L(M)=\Sigma^*$ any more, so why it's not? $$L_{\Sigma^*}\in coRE$$
$*$ I familiar with the reductions $HP\le L_{\Sigma^*}$ and $HP\le \overline{L_{\Sigma^*}}$ to proof $L_{\Sigma^*}, \overline{L_{\Sigma^*}}\notin RE$

You say

$\langle M \rangle$ should accept all the inputs, and if one of the inputs rejected it's not $L(M)=\Sigma^∗$.

The above two statements are true, but you are not handling all behaviors of $M$.
In particular you are not considering that $M$ could never halt on some input $x$. In that case $L(M) \neq \Sigma^*$.
In short, your observation do not imply the existence of a Turing machine that accepts on input $M$ whenever $L(M) \neq \Sigma^*$, which would show $\overline{L_{\Sigma^*}} \in \mathsf{RE}$.
In fact, you can formally prove that $\overline{L_{\Sigma^*}} \not\in \mathsf{RE}$ by reducing from the halting problem:
for any Turing machine $T$ you can construct another machine $M_T$ that simulates $T$ and then accepts.
If $\overline{L_{\Sigma^*}}$ were in RE, then there would be a Turing machine $T^*$ that accepts iff $M_T \in \overline{L_{\Sigma^*}}$, i.e., iff $T$ does not halt.
Interleaving the execution of $T^*$ with that of $T$ itself allows  you to solve the halting problem.


Should names of built-in funtions be part of BNF grammar? We're creating our own programming language for a subject. And we're confused whether to add the names of the functions we want to have in our language (like our own version of print) in the BNF grammar.

Reserved words should be recognized by the lexer, right? How about function names?

If your language has a small set of functions and there is no mechanism for adding other ones, then you could include the function names as keywords. But that's not a very likely scenario, unless your "language" is just a desk calculator (and even then, these days many calculators allow you to define functions).

So in general, it's not going to be feasible to include all the function names in the lexer, and unless function names are somehow lexically distinguished from other identifiers, all the lexer can do is report that it has found an identifier.

Assuming the grammar is unambiguous, a common idiom is to use a unit rule in the BNF in order to encapsulate whatever needs to be done to turn an identifier into a function reference (and similarly for identifiers representing other kinds of things) [Note 1][Note 2]:

function_name: IDENTIFIER
type_name:     IDENTIFIER
...

term:          function_name '(' optional_expresion_list ')'

But that won't work if certain expressions in the language would be ambiguous without knowing whether an identifier in the expression names a function or some other kind of thing. That's not very common for function names, but C and derived languages famously feature an analogous ambiguity with type names in C.

It's not totally unknown, though. For example, in awk, string concatenation is expressed with simple operand juxtaposition, so that

first "-" second

is the concatenation of two variables and a string containing a dash. The result is that

first (second)

is ambiguous: if first names a function, it could only be a function call; otherwise, it could only be string concatenation. If the language insists of declaration before use (awk doesn't), it would be possible to disambiguate by distinguishing according to the type of first.

The implementation involves sharing a symbol table between the parser and the scanner. The scanner looks each identifier up in the symbol table, and returns a token based on the broad type (or "kind") of symbol. If the scanner does not find the symbol, it will return a token of type UNDEFINED_SYMBOL or some such, which will be required (or at least allowed) in grammar rules where a new symbol is defined.

This technique is commonly called "semantic feedback". Much care must be taken to ensure that the symbol table seen by the lexer while it is examining a token corresponds to the actual semantic state at the moment in which the parser is examining the token. Since lexers typically consume tokens in advance of the parse (or at least one token), this guarantee is not as easy as it might look at first glance.

Semantic feedback is often discouraged, both because of this fragility and because it contaminates the lexer with data which should be private to the parser. But sometimes it is the simplest solution.

As it happens, awk does not use this approach, in part because it does not require functions to be declared prior to use. Instead, it has a whitespace-aware lexical rule: a parenthesis which immediately follows an identifier without intervening whitespace is used in a function call expression; if there is intervening whitespace, the parenthesis must be a grouping parenthesis and the expression is treated as a concatenation. This rule is the source of occasional confusion about apparently mysterious errors (see below).

That rule could be expressed in two ways (at least):

The lexer could return a FUNCTION_NAME token when it sees that the character immediately following an identifier is a (. In that case, the grammar might include

term: FUNCTION_NAME '(' optional_parameter_list ')'
    | '(' expression ')'

The lexer could distinguish between two kinds of open parenthesis: a parenthesis which immediately follows an identifier, and all the other ones. So then the grammar might include:

term: function_name OPEN_APPLY optional_parameter_list ')'
    | '(' expression ')'

(A third possibility exists, in which the function name and the following parenthesis are recognized as a single token, leading to the rather odd-looking grammar rule FUNCTION_NAME optional_parameter_list ')'. Some real-world implementations actually use this for efficiency, but it's confusing for the reader.)

Editorial comment (i.e. my opinion)

On the whole, you should attempt to avoid playing tricks in your lexer. Ambiguities like the ones mentioned above should be treated as flaws in the language design rather than challenges to be overcome by clever hacks in the parser, particularly if you are designing a language. History demonstrates that ambiguities like the above not only complicate parsers, but also confuse people using the language in question.

A casual search for "most vexing parse" will show the extent of confusion created by an ambiguity in the C++ language. And the use of juxtaposition for concatenation in awk creates so many confusing parse errors that the Gnu awk manual has a chapter about how to write concatenation, citing the alleged explanation for the syntax given by one of the awk authors: "It seemed like a good idea at the time."

Notes

In this post, I use yacc syntax for the BNF, with the convention that terminals (tokens) are represented either by UPPER_CASE or by quoted characters, and non-terminals are spelled in lower_case.
While some languages might be content to not allow higher-order types, almost all languages -- even C -- allow the target of a function application expression to be a computed value. So if you find yourself writing the above rule, you might want to think about its implications for the semantics of your language.


Why can't we reduce register automata to symbolic automata? When considering automata, they are normally considered over finite alphabets. The following are two types of automata that can handle words over infinite alphabets (definitions included for clarity).

The symbols $\triangleright$ and $\triangleleft$, appended to the beginning and end of the word respectively, are delimiters and are not in $\Sigma$. That is, the automata process words of the form w = $\triangleright$v$\triangleleft$ where v $\in$ $\Sigma^*$.

A k-register automaton $\mathcal A$ over $\Sigma$ is a 5-tuple (Q, $q_0$, F, $\tau_0$, P) where:

Q is a finite set of states;
$q_0$ $\in$ Q is the initial (or starting) state;
F $\subseteq$ Q is the set of final (or accepting) states;
$\tau_0$ : $\{0,1,...,k\}$ $\to$ $\Sigma$ $\cup$ $\{\triangleright,\triangleleft\}$ is the initial register assignment; and,
P is a finite set of transitions of the form ($i$, $q$) $\to$ ($q'$, $d$) or $q$ $\to$ ($q'$, $i$, $d$) for $i$ $\in$ $\{0,1,...,k\}$, $q$, $q'$ $\in$ Q and $d$ $\in$  $\{Stay, Left, Right\}$.

A symbolic finite automaton (SFA) $\mathcal M$ is a 5-tuple ($\mathcal A$, Q, $q_0$, F, $\Delta$) where:

$\mathcal A$ is an effective Boolean Algebra (the alphabet);
Q is a finite set of states;
$q_0$ $\in$ Q is the initial (or starting) state;
F $\subseteq$ Q is the set of final (or accepting) states; and,
$\Delta$ $\subseteq$ Q $\times$ $\Psi_{\mathcal A}$ $\times$ Q is a finite set of transitions.

Research has shown that for register automata, equivalence is not decidable but in symbolic automata, it is. My question is why? These two automata types work with similar results, so why is it that we can't reduce one to the other?

Something tells me this is a very simple problem but I can't seem to find an answer anywhere, so thank you for any help! :)

My current thoughts are to do with the fact that SFA require their alphabet to be an effective boolean algebra, whereas RA work on anything and so their alphabets dont have to follow the rules of a Boolean algebra. I dont know how to correctly formulate this idea into anything useful though.

The basic difference is that register automata have a memory while symbolic finite automata do not. Over an infinite alphabet this gives RA a power that can't be replicated in SFAs. Symbolic automata can only recognize unary predicates, and other relations are much harder.

For a simple example, consider the language $L=\{xx\mid x\in\Sigma\}$. That is, the set of all strings of length 2 that repeat a character. There is an easy RA to achieve this: state 0 reads x and stores it in register 1, going to state 1 (i.e. $q_0\to (q_1,0,\mathsf{right})$), and state 1 goes to the accept state 2 if the current value matches (that is $(q_1,0)\to (q_2,\mathsf{stay})$, and $F=\{q_2\}$) and rejects otherwise.

Suppose that a SFA accepts this language, where $\Sigma$ is infinite. Because for all $x\in\Sigma$, $xx\in L$, every character must initially be permitted. That is, for all $x\in\Sigma$ there is a state $q_x$ such that $(q_0,\phi,q_x)\in\Delta$ and $\phi(x)$ is true. Since $\Delta$ (and $Q$) are finite, there are clearly a finite number of such states $q_x$. But they are being tasked with distinguishing an infinite number of possible outcomes, depending on which $x$ was read. More precisely, by the pigeonhole principle there must exist $x\ne y$ such that $q_x=q_y$. Then the SFA must accept the string $x$ starting from $q_x$, since $xx\in L$, but that means it also accepts the string $x$ starting from $q_y$, so $yx\in L$ as well and hence the SFA doesn't correctly recognize $L$.


Use of Big-Oh in Worst case If it is given that a program has a worst case running time of $O(n)$, then is it still okay to define the running time as being $O(n^2)$. By definition, this seems corrects since Big-Oh is essentially an upper bound.

But, since we already established a worst case running time, can this still be correct.

Yes, if a program runs in time $O(n)$, then it also runs in time $O(n^2)$. However, usually we try to give the best possible bound, to prevent readers from being misled. You can signify that the bound is tight using big theta: the worst-case running time of the program is $\Theta(n)$.


How to use Sigma Scaling in a genetic algorithm I have a genetic algorithm in Java and I'm testing new types of selections.

For my tests I'm using the De Jong Half Sphere, my fitness function is $x^2 + y^2$.

The selection method used is Sigma scaling :

fscaled = S + (fraw −fmean)/2σ

Example using S=1

 - a) Fitness = 5.927822124 |  After Scaling = 0.900756351532265  | 17.74410992 %
 - b) Fitness = 3.431749363 |  After Scaling = 0.5720553077878213 | 10.27246375 %
 - c) Fitness = 8.428103101 |  After Scaling = 1.2300115637030606 | 25.22835279 %
 - d) Fitness = 2.548825744 |  After Scaling = 0.455785494144756  | 7.629554871 %
 - e) Fitness = 13.07076638 |  After Scaling = 1.841391282832097  | 39.12551868 %

I know that sigma scaling should be used with a proportional selection.

Is this the right way to implement this type of selection?
If I wanted to minimize the function instead of maximize it how can I accomplish it, should I subtract the mean to each fitness and get the percentage this way or is there a better way?

Well I just tried this :

(1.0/f(x,y))+1.0

a) 21.37858466 | After the reciprocate | 1.046775781
b) 1.425432689 | After the reciprocate | 1.701541369
c) 15.48548031 | After the reciprocate | 1.064576621
d) 14.56668667 | After the reciprocate | 1.068649791
e) 41.0387647  | After the reciprocate | 1.024367205

With these new fitness I used S=1

  fscaled = S + (fraw −fmean)/2σ

Mean = 1.181182154
Dev Std = 0.260649227

And this was my final result :

a) 0.742170015 | 14.8434003 %
b) 1.998198272 | 39.96396544 %
c) 0.776317134 | 15.52634267 %
d) 0.784130642 | 15.68261284 %
e) 0.699183937 | 13.98367874 %

These can be used with proportional selections.
I think this is the right way to use sigma scaling.
And I used the reciprocate plus one to make this a minimization problem.


Probabilistic test of matrix multiplication with one-sided error Given three matrices $A, B,C \in \mathbb{Z}^{n \times n}$ we want to test whether $AB  \neq C$. Assume that the arithmetic operations $+$ and $-$ take constant time when applied to numbers from $\mathbb{Z}$.

How can I state an algorithm with one-sided error that runs in $O(n^2)$ time and prove its correctness?

I tried it now for several hours but I can't get it right. I think I have to use the fact that for any $x \in \mathbb{Z}^n$ at most half of the vectors $s \in S = \left\{1, 0\right\}^n$  satisfy $x \cdot s = 0$, where $x \cdot s$ denotes the scalar product$\sum_{i=1}^{n} x_is_i$.

If $AB=C$, then $A(Bx)=Cx$ for all vectors $x$. Generate vectors randomly and check. This known as Freivalds' algorithm. Wikipedia has details.


Curious about an old algorithm which calculates modular inverse I am not sure if I should ask this question here or somewhere else. In fact, I initially asked my question here at mathoverflow.net but it was marked as off-topic

Background: I was searching through random mathematics paper that are related to cryptography and I came across this paper (page 3). I just read the abstract and algorithm itself, I don't understand Chinese. It offers new method to find a Modular inverses. It has some interesting properties that I observed:

during each step iteration of the loop: $x_{11} * x_{22} + x_{12} * x_{21} = m$ which is good to validate the result during each iteration
algorithm terminates in even number of steps for some unknown reason

In abstract section, author says this method was invented by this mathematicians.

My question is, why does this algorithm always terminate in aeven number of steps (or number of iterations of the loop is always even)?

Algorithm to calculate: $a^{-1} (\bmod m)$:

  $\text{xgcd}(a, m):$

  $\quad x_{11} \leftarrow 1, x_{21} \leftarrow 0, x_{12} \leftarrow a, x_{22} \leftarrow m$

  $\quad \text{While }(x_{12} > 1) \text{ do}$

  $\quad \quad \text{If }(x_{22} > x_{12}) \text{ then}$

  $\quad\quad\quad\quad q \leftarrow \Big\lfloor\frac{x_{22} - 1}{x_{12}}\Big\rfloor$

  $\quad\quad\quad\quad r \leftarrow x_{22} - q ~x_{12}$

  $\quad\quad\quad\quad \begin{pmatrix}x_{11} & x_{12}\\x_{21} & x_{22}\end{pmatrix} \leftarrow \begin{pmatrix}x_{11} & x_{12}\\q~x_{11} + x_{21} & r\end{pmatrix} $

  $\quad\quad \text{If }(x_{12} > x_{22}) \text{ then}$

  $\quad\quad\quad\quad q \leftarrow \Big\lfloor\frac{x_{12} - 1}{x_{22}}\Big\rfloor$

  $\quad\quad\quad\quad r \leftarrow x_{12} - q~x_{22}$

  $\quad\quad\quad\quad \begin{pmatrix}x_{11} & x_{12}\\x_{21} & x_{22}\end{pmatrix} \leftarrow \begin{pmatrix}q~x_{21} + x_{11} & r\\x_{21} & x_{22}\end{pmatrix}$

  $\quad \text{Return } x_{11}$

Screenshot of the algorithm
Python and SageMath implementations

You can replace:

$$ ~~q \leftarrow \Big\lfloor\frac{a - 1}{b}\Big\rfloor $$
$$ r \leftarrow a - q ~b  $$

By $q, r \leftarrow \text{divmod}(a, ~ b)$

  Algorithm terminates in even number of steps for some unknown reason

Those matrices assignments seem to be a fancy way of writing:

$$ \gcd(m_0, \color{blue}{a_0}) = \gcd(a_0, \color{red}{m_0 \pmod{a_0}}) = \gcd(\color{red}{m_1}, \color{blue}{\underbrace{a_0 \pmod{m_1}}_{a_1}}) = \dots = \gcd(m_n, 1)$$

So $a_i$ decreases every $2$ iterations, and $\gcd$ stops when $a_n = 1$.

Of course, you're not interested in computing the $\gcd$ per see, since you already know it's $1$, but finding the integers such that $Xm + Ya = gcd(m, a) = 1$.


Does a language have a regular expression if and only if it is regular? I know that if a language has a regular expression it is regular, is the other way also true?

Yes, a language can be described as a (pure vanilla) regular expression if and only if it is regular. You can see the proof in any decent textbook on formal languages.


Integer set disjointness query on sketches with something like homomorphic hashing Suppose I have two sets of integers $A$ and $B$ and I have a sketch data structure described by a function $\mathsf{sketch}_n : \mathcal{P}(\mathbb{Z}) \to 2^n$ that returns a bitstring of size $n$. These sketches can be checked for disjointness with a function $\mathsf{disjoint}_n : 2^n \times 2^n \to 2$, where if $\mathsf{disjoint}_n(\mathsf{sketch}_n(A), \mathsf{sketch}_n(B)) = 1$, then $A \cap B = \emptyset$ (but $A \cap B = \emptyset$ may also be true when $\mathsf{disjoint}$ returns 0, i.e.: no false positives).
This can easily be accomplished with a bloom filter, where $\mathsf{sketch}_n$ is the result of inserting each element of the set into a bloom filter and $\mathsf{disjoint}_n(x, y) = (x \,\&\, y) \equiv \mathbf{0}$ ($\&$ being bitwise AND).
Now, suppose that I want there to exist a function $\mathsf{shift}_n : 2^n \times \mathbb{Z} \to 2^n$ such that $\mathsf{shift}_n(\mathsf{sketch}_n(X), \delta) = \mathsf{sketch}_n(\{x + \delta \mid x \in X\})$. Is there a data structure that supports this operation, perhaps using some variety of homomorphic hashing?
Alternatively, $\mathsf{shift}_n$ need not exactly return the same sketch as $\{x + \delta \mid x \in X\}$, but rather a different sketch that still has the no-false-positives property when checked for disjointness with another set.
I'm also willing to consider answers where we can't ensure no false positives, but there is a good bound on the probability of a false positive.
Also, wherever I've said $\mathbb{Z}$ here, feel free to interpret that as some finite set of integers (e.g.: 32-bit integers).
Bonus points if there is a way to compute the union of two sketches, and if there is a way to extend this to sets of tuples in $\mathbb{Z} \times 2^p$ where $\mathsf{shift}$ only affects the first element of each tuple.

Here is one simple idea -- not sure if it's practical.
Define $\mathsf{sketch}_n(X)$ to be a length-$n$ bitstring in which bit $i$ is set iff there exists $x \in X$ such that $x = i \mod n$. In practice, this means that inserting an element $x$ into a set involves turning on bit $x \mod n$. $\mathsf{disjoint}_n(\cdot)$ is defined as before. Then $\mathsf{shift}_n(\cdot, \delta)$ can be found by rotating the sketch right by $\delta$ bits (which can be done implicitly by storing a "rotation amount" in the data structure).
To reduce the false positive rate for membership tests (but increase the false negative rate for disjointness tests), you can store multiple bitstrings using different moduli -- e.g., if the moduli 100, 101 and 105 are used, there would be 306 bits in total. Intuition suggests relatively prime moduli would work best, but I have not tried looking into this in detail.


Set Difference of Two RE Languages - An Intuitive Idea of Why It's Not Closed I'm new to studying formal languages, so apologies if I get a lot of basic stuff wrong, but I'm trying to get an intuitive understanding of why the difference between two Recursively Enumerable languages (A and B, say) is not itself RE? I.e. why for A-B = Z, Z is not RE?

The basic set notation and maths I understand, but I've added a more textual description as I'm looking for an intuitive answer: let C = complement of B.

Some of the words C contains in its set would cause a TM for B to reject, others would cause it to never halt. So C is not RE.

Now, A-B = A n C, by basic set operations. The theory I've read now says that the intersection of an RE (A) and a non-RE (C) cannot be RE, which is why the original A-B = a non-RE. I accept this logic, but am struggling to understand intuitively how this is true, in terms of picturing a Turing Machine that halts or loops, given the input of words from A n C.

My First Attempt at an Intuitive Explanation:

My guess is that I've missunderstood something fundamental about TMs, and what their acceptance/rejection/looping on words of a language really means, but here we go:

Imagine a TM for the RE lang A. Every word in A will cause TM to accept. Now, isn't A-B just a subset of the words from the language A? Therefore, wouldn't all the words in A-B cause our TM to also accept? By this logic then, wouldn't the difference between two RE's, A-B, be an RE language, too?

My Final Thought:

I tried to picture this in different ways, with say having the condition be that you test your newly outputted language (A-B in this case), on a TM that accepts on each of the initial languages (A, B), and if the new language accepts on all those TMs, it must be RE? But that didn't hold for things like A u B.

So, I'm stuck as for an intuitive understanding as to why A - B is not RE, when A - B is just a subset of words of A, and A will accept on its TM?
Further, what's the rule for how your new language (be it A-B, A u B, A* n B, etc) should accept in relation to TMs that accept on the initial languages?

Thanks very much for your help.

Given a language $L$, $L$ is RE if there is a TM $M$ such that $L(M) = L$. $L(M)$ is the set of words which $M$ accepts and it must be equal to $L$; words not in $L$ must cause $M$ either to reject or to never halt. It is not sufficient for $L$ to be a subset of $L(M)$, which is why your reasoning is incorrect.

Given RE languages $A$ and $B$, what makes $A \setminus B$ not RE (in general) is not the problem of knowing whether the input is in $A$; since $A$ is RE, there is a TM $M_A$ which you can simulate to find out (and if $M_A$ does not halt, the input is not in $A$ and, hence, not in $A \setminus B$ too; so there is no need to halt at all). The problem is that, to accept an input $w$ which is not in $B$, you need to simulate the respective TM $M_B$ on $w$ and accept if $M_B$ does not halt; hence, you need to solve an instance of the complement of the halting problem, which is (famously) not in RE.


NPC-problem reduction to triangle-free 3-colorability lately, I have encountered a problem that I struggle to find a satisfactory solution for. I need to prove that triangle-free 3-colorability is NP-complete. Therefore I assume the right way is to find an NP-complete problem and reduce it to my problem.
I tried it with general 3-colorability, but I was unable to create function F() that would reduce a general graph to a triangle-free graph without changing its colorability.
Is it a good direction? Does it make sense to reduce the 3-colorability problem?
If yes, I would appreciate any advice on how to finish the proof. If I am doing it wrong, I would appreciate any advice on the reduction.

We reduce from 3-coloring, following Kráľ, Kratochvíl, Tuza and Woeginger, Complexity of Coloring Graphs without Forbidden Induced Subgraphs. We will need to use a gadget $H$, with the following properties:

$H$ is a 3-colorable triangle-free graph.
There are two vertices $a,b \notin H$, not connected by an edge, such that any 3-coloring of $H$ gives $a,b$ different colors.

Given such a gadget $H$, here is how to reduce 3-coloring to triangle-free 3-coloring. We start with a graph $G$. We construct a new graph $G'$ as follows. The graph $G'$ will have all vertices of $G$, together with some new vertices. For each edge $e = (x,y) \in G$, there is a copy $H_e$ of $H$. We identify $a_e$ (the copy of $a$ in $H_e$) with $x$, and $b_e$ with $y$. This completes the construction.
The new graph is triangle-free. Indeed, suppose that it contained some triangle $u,v,w$. Since the vertices $u,v$ are connected, they must reside in some copy $H_e$ of $H$. Since $(a,b) \notin H$, at least one of these vertices doesn't belong to $V$, say $u \notin V$. Since all neighbors of $u$ are in $H_e$, it follows that $u,v,w$ all reside in $H_e$, contradicting the triangle-freeness of $H$.
If $G$ is 3-colorable, then we can easily complete a 3-coloring of $G$ to a 3-coloring of $G'$ by using a 3-coloring of $H$ (by symmetry, it doesn't matter what colors $a,b$ get, as long as the colors are different). Conversely, the restriction of any 3-coloring of $G'$ to $V$ is a 3-coloring of $G$.
To complete the proof, we need to describe the gadget $H$. Our starting point is any critically 4-colorable triangle-free graph $H'$, such as the Grötzsch graph; here critically 4-colorable means that the graph is not 3-colorable, but becomes 3-colorable if we remove any edge.
We take any edge $(a,c) \in H'$ and replace it by an edge $(b,c)$, where $b$ is a new vertex (in particular, $(a,b)$ is not an edge). The resulting graph $H$ is still triangle-free. Since $H'$ was critically 4-colorable, the graph $H$ is 3-colorable: take a 3-coloring of $H' \setminus \{(a,c)\}$, and color $b$ appropriately. Any 3-coloring of $H$ must give $a,b$ different colors, since otherwise its restriction to all vertices but $b$ would be a 3-coloring of $H'$.


What we lack to do automatic programming? From time to time I am trying to implement automatic programming system. We already have the formalization of norms (laws/legislation, business policies and rules) as some kind of deontic logic (there have been endeavours to convert deontic logic formulae into executable rules). We have ontology of GUI elements. So - we have specification. But how to convert this specification into executable code? What we lack to do automatic programming at least in the domain of business software (that is specified by legislation and enterprise rules)?

We already have the formalization of norms

I don't think we do. Norms are written in natural languages (e.g. English). And truly understanding text written in a natural language (even a subset of it, such as the one used to write norms) is still not something that can be done.

Even if you solved that, business policies and rules usually aren't detailed enough to directly create useful programs out of them. That's another hurdle that's not going to be easy to cross.


Which is the most efficient out of Bubble Sort, Selection Sort, Insertion Sort for a identical set of elements? Which of the sorting algorithm is (classical implementation with no enhancements) the fastest for a data set with all identical elements? And why?

How would one justify the answer to the above question logically?
Logically as in without implementing the algorithms and finding the average time consumed for few sample data sets.

All elements being the same is equivalent to data being sorted. The class of algorithms you are looking for is adaptive sort, which benefits from presortedness of the input data - this is the justification - since data is already sorted we have to find algorithm that uses this fact. The classic example is the insertion sort, but also Timsort (a variant of natural merge sort) and other exist. All adaptive algorithms should show the best case performance as $\mathcal{O}(N)$, which in case of insertion sort is exactly $N - 1$ comparisons, where $N$ is the length of input data.
There is no need to implement or run those algorithms, it is suficcient to show that part responsible for swapping elements is never executed, show that appropriate conditions are always true (or false depending on code) so analysis is easier.

From the possible algorithms you have provided the best cases are: Bubble sort - $\mathcal{O}(N)$, Selection Sort - $\mathcal{O}(N^2)$ and Insertion Sort - $\mathcal{O}(N)$.


Useful functions between polylogarithmic and polynomial? I'm wondering if there are any useful functions asymptotically greater than a polylogarithmic function and less than a polynomial function.

That is, a function $f(n)$ such that

$f(n) = \omega(\log(n)^k)$  for some constant $k > 0$

and

$f(n) = o(n^k)$ for some constant $k > 0$

What I mean by useful, is that it was used in a proof, algorithm, etc. rather than simply producing a function to fit these restrictions.

According to Wikipedia (which attributes the following result to Knuth), the running time of the mixed-level Toom–Cook algorithm for integer multiplication is
$$ \Theta(n\log n \cdot 2^{\sqrt{2\log n}}). $$
The function $2^{\sqrt{2\log n}}$ is super-polylogarithmic but sub-polynomial.


Every regular language has a finite index For a language $L$ over an alphabet $\Sigma$, we say that two words $v,w \in \Sigma^*$ are equivalent, denoted $v\sim w$, if for every word $z \in \Sigma^*$, $vz \in L$ iff $wz \in L$. We define $[w]_L$ to be the equivalence class of $w$ under this relation. The index of $L$ is the number of equivalence classes of strings in $L$.

How can I prove that every regular language has a finite index?
can I use the Myhill-Nerode theorem?

I tried to use the fact that if $\delta^*(v) = \delta^*(w)$ then $v \sim w$.

The Myhill-Nerode theorem suggests that a language $L\subseteq \Sigma^*$ is regular iff $L$ has a finte index, and this clearly implies that a regular language has a finite index. So, let's prove this direction of the Myhill-Nerode theorem directly. Assume that a language $L$ is regular, and let $\mathcal{A} = \langle Q, \Sigma, q_0, \delta, F\rangle$ be a DFA for it.

The idea is to define an equivalence relation, denoted $\sim_{\mathcal{A}}$, over $\Sigma^*$, and then prove that:

The number of equivalence classes of $\sim_{\mathcal{A}}$ equals $|Q|$.
The Myhill-Nerode equivalence relation w.r.t $L$,  which i denote by $\sim_L$,  is coarser than the relation $\sim_{\mathcal{A}}$:
for every two words $x, y\in \Sigma^*$, if $x\sim_{\mathcal{A}} y$ then $x\sim_L y$.

Note that $2$ implies that the index of $L$ is at most the number of the equivalence classes of $\sim_{\mathcal{A}}$, and thus by $1$ and the fact that $|Q|$ is finite, we get that $L = L(\mathcal{A})$ has a finite index.

To begin with, the transition function $\delta$ which is a funtion from $Q\times\Sigma$ to $Q$ can be generalized to $\delta^*$ inductively to read words as follows. The generalized transition function $\delta^*: Q\times \Sigma^*$ is defined by:

$\delta(q, \epsilon) = q$, for every state $q$.
and, $\delta(q, u\sigma) = \delta(\delta^*(q, u), \sigma)$ for every word $u$ and letter $\sigma$.

Intuitively, $\delta(q, w)$ is the state that is reached from $q$ upon reading the word $u$.

Now we define the relation $\sim_{\mathcal{A}}$ over $\Sigma^*$. For every two words $x, y \in \Sigma^*$ we say that $x \sim_{\mathcal{A}} y$ iff $\delta^*(q_0, x) = \delta^*(q_0, y)$. In words, $x$ and $y$ are equivalent iff the automaton $\mathcal{A}$ reaches the same states upon reading $x$ and upon reading $y$.

The following lemma can be proved by induction and i leave it to you.

Lemma: $\delta^*(q, u\cdot v) = \delta^*(\delta^*(q, u), v)$, for every state $q$ and words $u$ and $v$.

Let's prove 1 and 2:

Follows immediately by the definition of $\sim_{\mathcal{A}}$. Indeed, every state $q$ of $\mathcal{A}$ defines an equivalence class.
Assume that $x$ and $y$ are such that $x \sim_{\mathcal{A}} y$. By definition we have that $\delta^*(q_0, x) = \delta^*(q_0, y)$. Let $z\in\Sigma^*$ be a word. We need to show that $xz\in L$ iff $yz\in L$: using the above lemma and what we have so far, we get the following:

$$xz \in L$$ $$iff$$

$$\delta^*(q_0, xz) \in F$$ $$iff \ \          (\text{By the lemma})$$

$$\delta^*(\delta^*(q_0, x), z) \in F$$ $$iff \ \         (\text{By the fact that $\delta^*(q_0, x) = \delta^*(q_0, y)$})$$

$$\delta^*(\delta^*(q_0, y), z) \in F$$ $$iff  \ \       (\text{By the lemma})$$

$$\delta^*(q_0, yz) \in F$$ $$iff$$

$$yz\in L$$.

thus, $x \sim_L y$ and so we are done.


What are the $EXP^{NP}$, $EXP^{PSPACE}$, and $EXP^{EXP}$ equal to What are the  $EXP^{NP}$, $EXP^{PSPACE}$, and $EXP^{EXP}$ equal to?

I suspect that their, NEXP, ESPACE and 2EXPtime respecitvely.
And what bout $NP^{EXP}$

The trivial implications are:

$\mathsf{NP^{EXP}=EXP\subseteq NEXP \subseteq EXP^{NP}\subseteq EXP^{PSPACE}\subseteq EXP^{EXP} = 2EXP}$

I suggest that you try proving these relationships yourself. $\mathsf{NEXP\subseteq EXP^{NP}}$ requires a simple padding argument, and for $\mathsf{2EXP\subseteq EXP^{EXP}}$ observe that the language $L=\{\left(M,x,t\right) | \text{M accepts $x$ within $t$ steps}\}$ is EXP-complete (when $t$ is encoded in binary). Anything more than that is probably hard, e.g. $\mathsf{NEXP\subsetneq EXP^{NP}}$ implies $\mathsf{NP\subsetneq P^{NP}}$ via a padding argument.


My professor claims that inserting the same key into a hash table again will lead to a collision … – Is he really right? My whole life I thought

  a collision is a situation that occurs when two distinct pieces of data have the same hash value.

Everything looks a little bit different now: A few days ago we had to analyse common collision resolution strategies to handle the event that at least two keys being hashed to the same slot of an ordinary hash table. As mentioned above, to my knowledge (as well as my intuition) when inserting the very same key $k$ – that is already assigned to a slot of a hash table $T$ – again,  nothing (special) happens and $T$ remains unchanged.

I wonder now, if i misunderstood this basic concept, since my professor claims, that inserting the key $k$ into a hash table $T$ again will lead to a collision anyway and we have to analyse some collision resolution strategies in this case too …

Many thanks in advance for your help and clarification!

I suppose one could define the word however you like, but I've always understood it to mean the same thing you are talking about. Here I'm assuming if you try to insert a key the second time, no change is made, as it is already present.  If inserting the key caused a second copy to be inserted somewhere, then I think it's more ambiguous and in any formal analysis it would be best to define precisely what you mean by a collision and state whether you consider that a collision, to avoid confusion.


How to think when devising a TM that decides if a DFA rejects some string? The title should explain my question thoroughly enough. I can't seem to get started anywhere. Intuitively it seems like some kind of brute-forcing would work i.e if the DFA has the symbols $\Sigma$ you would simply be passing strings from $\Sigma^*$ until the DFA rejects. What would even be the time complexity of this though? Or am I completely out and about?

The problem with your approach is that there are infinitely many strings in $\Sigma^*$. If the automaton keeps accepting and accepting, how would you know hen to stop?

Instead, consider how an automaton can reject: it rejects by getting to a rejecting state.


What does it mean for a problem to be solved in polynomial time "relative to" an oracle? I came across the following theorem in page 12 of the following pdf :

  There exists an oracle relative to which there is a problem solvable
  in polynomial time (with bounded error probability) on a quantum
  computer, but any probabilistic Turing Machine with bounded error
  probability solving this problem (using the oracle) will require
  exponential time (at least $2^\frac{n}{2}$ steps on infinitely many
  inputs (of length n).

My question is what does it mean to say "There exists an oracle relative to which there is a problem". My take on it is that if we try to solve the problem using a non deterministic T.M. or non deterministic Quantum computer (I don't know if such a thing even makes sense as I just started studying Quantum Computing) the oracle is a black box which tells the machine which path to take in the non deterministic step. Is this the correct interpretation?

Oracles have nothing to do with non-determinism. They are just a communication mechanism between the algorithm (or Turing machine) and an outside entity, the oracle $O$, which is just a language. In the classical case, the algorithm can query the oracle on a specific input $x$, and it immediately gets the (Boolean) value of the oracle at that input: 1 if $x \in O$, and 0 if $x \notin O$. I'm not quite sure how this works in the quantum case, but perhaps the PDF explains that.

The theorem states that there is some oracle that allows quantum algorithms to solve some problems much faster than classical ones. That is, if a quantum algorithm is given access to this oracle, then it can solve some problem in time Q, but a classical algorithm which is given such access can only solve the problem in time C$\gg$Q.


Confusion about definition of languages accepted by Turing Machine, very basic question I'm studying for an upcoming exam and my book gives the following definition:
Let $M$ be a Turing machine, then the accepted language $T(M)$ of $M$ is defined as $T(M) = \{x \in \Sigma^* \mid z_0 x \vdash^* \alpha z \beta; \alpha, \beta \in \Gamma^*; z \in E\}$.
As a side note, $\vdash$ denotes the transition from one configuration of the TM to the next, and the $^*$ denotes an arbitrary number of applications of this relation.
What I'm confused about is that under this definition of acceptance, I only have to enter the end state once and even if I leave it, the word would be accepted, or I could loop in this end state. In push down automata or regular automata, we do not have this problem as we move through the word sequentially from beginning to very end, especially in push down automata where the stack is separated from the input word.
Now I read in most other definitions, additionally to ending up in an end state, the Turing machine must also halt, meaning that it must end in a state that has no transitions. Although I'm not sure what this would mean for deterministic Turing machines as they have to have transitions for all configurations of the machine.
To wrap it up:
Question 1: Is halting required? Is it a useful property for accepting languages or is there a reason the definition was given as is?
Question 2: How would you define "halting" for deterministic Turing machines?

Even in a deterministic Turing machine, the transition function $\delta$ may be a partial function i.e. there can be pairs of states and tape symbols for which the transition function is not defined. If the Turing machine is in state $z$ and reads symbol $\alpha$ and $\delta(z,\alpha)$ is not defined then it halts. Usually the accepting states $E$ are implemented by creating states for which the transition function is undefined for all inputs i.e. the Turing machine will always halt once it enters a state $z \in E$, regardless of the symbol it reads from the tape. You may also have other halting states, but if the machine halts in a state $z \notin E$ then it has rejected the input string.


Function whose domain is strictly included in its range Hi I'm doing some exercices on reductions and one of them is like this:

My problem rather than doing the reduction is understanding it. For the positive case I want that if Mx(x) never stops then p's domain has to be strictly included in q's domain which has to be stricly included in p's range. Am I wrong? Therefore Dom(p) has to be stricly included in Range(p), right?

Let's forget about reductions for a moment, my problem here is: is there any function $f(x)$ whose domain is strictly included in its range?

We would want to have $Dom(f(x)) = \{1\}$ and $Range(f(x)) = \{1, 2\}$ That would mean that 1's image has to be 1 AND 2 :/

What am I doing wrong?

Thanks for your time and have a nice day! :D

Without getting to the technicality of codomain/range/image and surjective functions, the property you ask for can surely happen. For instance,

$$f(x) = 2x$$

defined over the domain interval $[0,1]$, has the image $[0,2]$. This should not happen over finite domains.


How to prove formally that grammar isn't LR(1) I want to prove that grammar
$$
\begin{cases}
S'\rightarrow S\\
S\rightarrow aSb ~|~ A\\
A\rightarrow bA~|~b
\end{cases}
$$
isn't $LR(1)$. I've constructed parser table and got Shift-Reduce conflict.

I want to prove that without parser table, using another $LR(1)$ definition.

Here's definition:
Grammar is $LR(1)$, if from

$S' \Rightarrow^*_r uAw \Rightarrow_r uvw$
$S' \Rightarrow^*_r zBx \Rightarrow_r uvy$
$FIRST(w) = FIRST(y)$

$\Rightarrow uAy=zBx.$

So how can prove that?

$$S'\Rightarrow^*\underbrace{ab}_uA\underbrace{b}_w\Rightarrow \underbrace{ab}_u\underbrace{b}_v\underbrace{b}_w$$

$$S'\Rightarrow^*\underbrace{abbbb}_zA\underbrace{b}_x\Rightarrow \underbrace{ab}_u\underbrace{b}_v\underbrace{bbbb}_y$$

$$FIRST(w)=FIRST(y)=b$$
But:
$$abAbbbb=uAy\neq zBx=abbbbAb$$


Can Eve impersonate Alice or Bob by using a replay attack? For my computer science study, I have to design a replay attack (if possible) for the following authentication protocols.

I use the standard security protocol notation.
In these protocols, $A$ is Alice, $B$ is Bob and $E(A)$ is for example Eve impersonating Alice. $K_{AB}$ is a shared secret key only Alice and Bob know, $K_{AB}\{x\}$ is the data $x$ encrypted with this key, and $N_A$ and $N_B$ are fresh random nonces generated by $A$ and $B$. We assume that Eve cannot simply break the encryption.

a)
$1. A \rightarrow B : A, K_{AB}${$N_A$}
$2. B \rightarrow A : B, N_A, K_{AB}${$N_B$}
$3. A \rightarrow B : A, B, N_A, N_B, K_{AB}${$N_A, N_B$}

For this, I designed the following replay attack:

$1. A \rightarrow E(B) : A, K_{AB}${$N_A$}
$2. E(A) \rightarrow B : A, K_{AB}${$N_A$}
$3. B \rightarrow E(A) : B, N_A, K_{AB}${$N_B$}
$4. E(B) \rightarrow A : B, N_A, K_{AB}${$N_B$}

Is this gonna work?

The next example is this:

b)
$1. A \rightarrow B : A, N_A, K_{AB}${$A, N_A$}
$2. B \rightarrow A : B, N_B, K_{AB}${$B, N_A, N_B$}
$3. A \rightarrow B : K_{AB}${$A, B, N_A$}

I have no idea how to solve this one. Could you please help me with that?

well, you don't really explain what happens in each step, and how the authentication procedure works, but your first suggestion is at the right direction. However, the impersonator wishes to authenticate himself, so the attack should actually be

$1. A \rightarrow E(B) : A, K_{AB}${$N_A$}
$2. E(A) \rightarrow B : E(A), K_{AB}${$N_A$}
$3. B \rightarrow E(A) : B, N_A, K_{AB}${$N_B$}
$4. E(B) \rightarrow A : E(B), N_A, K_{AB}${$N_B$}

and you are missing the last reply, but it is easy to see that Eve can generate both $N_A$ and $N_B$ and thus succeed with authenticating itself.
Try to write it more carefully: what exactly is begin sent at each step (i.e., what is the meaning of sending "A"?), and what verification each side performs at each step.

For the second example, such an attack cannot work. The identity $A$ is included inside the encryption, and Eve has no way to replace it.


Does $f(n)=\theta(g(\log{n}))$ imply $f(n)=\theta(\log{g(n)})$? I am learning about algorithmic complexities and I have this claim which I need to prove or disprove: $f(n)$ and $g(n)$ are asymptotically positive functions, if $f(n)=\Theta(g(\log(n))$ then $f(n)=\Theta(\log(g(n)))$.
Is it true?

An obvious counter example is $g(n) = \sqrt{n}$. If $f(n) = \Theta(\sqrt{\log n})$, you can't conclude that $f(n) = \Theta(\log{\sqrt{n}}) = \Theta(\log{n})$.


Is there a non-recursive and uncountable language L? Does there exist a non-recursive language, L, such that the cardinality of L is uncountable?

I would really like an explanation as to why this question is true or false because at the moment, I have no idea.
My understanding is that all recursive languages have to be countable since the set of all finite strings is countable.
But I'm not sure if there is a non-recursive language which is uncountable.
Any help would be greatly appreciated,

Definition: a word over an alphabet $A$ is a finite sequence of elements of $A$.
Definition: a language over an alphabet $A$ is a set of words over $A$.

With these definitions, if $A$ is a finite set, then any language is countable (either finite, or countably infinite). This is because any language is a subset of the complete language $A^*$ (set of words over $A$).

Direct proof sketch: you can enumerate all the words in the language, in order of increasing length (and in lexicographic order for each given length, having defined an order of $A$). This process is well-defined because set of words of a given length is finite. This process assigns an index to all the words in the language because all words have a finite length.

Follow-up exercise: if $A$ is countably infinite then a language over $A$ is countable. Adapt the proof above (change the enumeration order to cover the whole language in finite batches).


simple but (seemingly?) tricky recurrence I'm cross-posting from math stack exchange after receiving no answers there.

I came across the following very simple recurrence-style expression but am having trouble solving it:
$$T(2n) \in \theta(T(n) \log(T(n)))$$
for sufficiently large $n \in \mathbb{N}$.

My first thought was to take the logarithm of both sides and apply the Master Theorem but the "$f(n)$" term unfortunately is not in the right form. Repeated expanding quickly yields a mess. Wolfram Alpha was no use.

Plugging in $T(n) = n^a$ makes the left side grow too slowly so $T$ must grow faster than any polynomial. But plugging in $T(n) = \exp(\log(n)^b)$, $b>1$, causes the left side to grow too fast so $T$ must grow more slowly. So it seems $T$ is super-polynomial but barely.

What approaches are viable for such an equation?

Let us attempt to solve the easier recurrence $T(2n) = T(n) \log T(n)$. Define $S(m) = \log T(2^m)$. Then $S(m+1) = S(m) + \log S(m)$. Let us heuristically convert this into a differential equation: $S' = \log S$. The solution to this equation is $S = \mathrm{li}^{-1} + C$, where $\mathrm{li}$ is the logarithmic integral. Roughly speaking, $\mathrm{li}(x) \approx x/\log x$, and so $\mathrm{li}^{-1}(x) \approx x\log x$. This heuristic implies that $S(m) \approx m \log m$, and so $T(n) \approx \exp \Theta(\log n \log \log n)$. Of course, at this point this is just an educated guess.

As a sanity check, suppose that $T(n) = \exp (\log n \log \log n)$, where all logarithms are base 2. Then
$$
\begin{align*}
T(n) \log T(n) &= \exp (\log n \log \log n) \log n \log \log n \\ &=
\exp (\log n \log \log n + \log \log n + \log \log \log n) \\ &=
\exp (\log (2n) \log \log n + \log \log \log n).
\end{align*}
$$
This is quite similar to $T(2n) = \exp (\log (2n) \log \log (2n))$ (though not the same).


Linear programming: reduce a contstraint that includes minimun I have an almost linear programme. However one of the constraints has a form $z = min(x,y)$ (all the other things are linear in the model). Is there a way to substitute this with something (or introduce additional variables) to turn this into a linear programme?

In other words, I have the problem that looks like the following:
$$
\mathbf c' \mathbf x \to \min,
$$
s.t.
$$
A \mathbf x = \mathbf b,\quad x_1 = \min(x_2, x_3).
$$

Update: I thought about substituting the constraint with $\min$ to the following pair: $x_1 \le x_2$ and $x_1 \le x_3$. However, this doesn't work if $x_1$ has a positive coefficient in $\mathbf c$, which is exactly the case for me. In fact, all the entries are positive in $\mathbf c$.

Solve two linear programs.  The first has the constraints
$$
A \mathbf x = \mathbf b,\quad x_1 = x_2 \le x_3.
$$
The second has the constraints
$$
A \mathbf x = \mathbf b,\quad x_1 = x_3 \le x_2.
$$
Choose whichever solution gives you a smaller value for $\mathbf c' \mathbf x$.

This works for your particular situation.  It doesn't scale to a case where you have a large number of $\min$ constraints.


Bin packing with item weight constraint In the bin packing problem, we are given a set of items I={a1,...,an}, each item with weight w_a1,...,w_an, and a set of n bins with B={b1,..., bn} all bins with capacity C. I want to restrict the weights of the items to be polynomial in n. Is the problem still being NP-hard (restricting the weight of the items)?

Any information and sources about this would be appreciated.

Thanks.

Assuming that you mean the usual bin packing problem, your question is answered on Wikipedia, on the page on strong NP-completeness.

A problem is strongly NP-complete exactly when it remains NP-complete even when the weights are assumed to be of polynomial size (this is not an informal definition, so this should be regarded as an informal notion). Another way to put this is that the problem remains NP-complete even when weights are encoded in unary (the two formulations might not be formally equivalent, but they are morally equivalent). Bin packing is one of the standard examples of a strongly NP-complete problem.


Efficient representation of a given surjective function $\{1 \ldots N\} \rightarrow \{1 \ldots M\}$ when $N \gg M$ More precisely: The input is set of $M$ sets (most likely stored sequentially on disk) that contain partitions of the set $\{1..N\}$. I want to efficiently (as far as memory and time complexity goes) represent this structure. Let's call this hypothetical structure $S$. I need the structure to support just a single function $p : S \times \{1 \ldots N\} \rightarrow \{1 \ldots M\}$.

It's also safe to assume that I will call this function in order, meaning I will be interested first in $p(S, 1)$, then in $p(S,2)$, etc.

I can represent this structure as an array of $N \times \lceil log_2(M)\rceil$ bits, but that seems too memory inefficient when $M$ is small and $N$ is in billions. I have a hunch that perfect-hashing might be of use here.

You can reduce your $N \lceil \log_2 M \rceil$ bits to $\lceil N \log_2 M\rceil$ by using Dodis et al's "Changing Base without Losing Space".

I don't think you're going to get much smaller than $N \log_2 M$ bits. For $N \gg M$, many functions will be surjective. In particular, there are $\{{N \atop M}\}$ surjective functions, which is at least $M^{N-M}$.
Thus, at least $\log_2 \left(M^{N-M}\right) = N \log_2 M - M \log_2 M \in \Omega(N \log_2 M)$ bits must be used to represent one, on average.


Algorithm to Minimize a Regular Expression I am referring to regular expressions with alphabet {$0$, $1$}. We want to minimize them so that they have the least possible number of symbols and operators. Is there an algorithm to do this?

For instance, what is done on this page in the accepted answer:

https://stackoverflow.com/questions/35112630/minimize-specific-regular-expression

Is there a formal algorithm to explain the process that the answer went through?

There is a trivial algorithm to find the minimum regular expression equivalent to a given one:

  Go over all regular expressions in nondecreasing order of length. For each one, check whether it is equivalent to the original regular expression. Return the first one which is.

To check equivalence, convert the regular expressions to NFAs, then to DFAs, then computed the product automaton for the symmetric difference, and check whether any accepting state is reachable from the initial state.

This algorithm isn't very efficient. Indeed, minimizing regular expressions is PSPACE-complete. See for example Gramlich and Schnitger, Minimizing nfa's and regular expressions.


Solving a dynamic programming problem? Alex writes down the decimal representations of all natural numbers between and including m and n, (m ≤ n). How many zeroes will he write down?

My one friend said to me that this problem can be solved by dynamic programming.But I can't understand how to solve it by dynamic programming .Can someone explain it with great details.Here is some input and output.

1.input:m=10, n=11 and output:1

2.input:m=100,n=200 and output:22

Let $T(n)$ denote the number of noughts that are necessary to write down all numbers from $0$ to $n$ (included) in base $10$. On input $(n,m)$ ($m>0$), the number you are looking for is then $T(n)-T(m-1)$ (i.e. count the numbers of noughts that you write to go up to $n$, then subtract the ones that you used to go up to $m-1$. The remaining number is the number of noughts that you wrote from $m$ to $n$.), and on input $(n,0)$ the output is simply $T(n)$. It remains to compute the table $T(n)$ quickly enough.

We write $T(0)=1$, and then use the relation $T(n) = T(n-1) + \mathrm{Noughts}(n)$ for $n>0$, where $\mathrm{Noughts}(n)$ denotes the number of noughts needed to write $n$ in base $10$. Given $n$, one can compute all the values of $T$ up to $n$ in time $O(n\log n)$ (the function $\mathrm{Noughts}(n)$, that could be built by examining all the digits of $n$, takes time proportional to $\log n$). Then, for any $0\leq m\leq n$, one can give the output to the problem on $(n,m)$ in constant time!


Prove or disprove L is regular There is question in one of my exercise but I couldn't prove or disprove anything about it.
This is language $L$ which is introduced with grammar:
$$S \to 0S1 | 1S0 | AA$$
$$A \to 0A | \lambda|A1$$

My explanation and work:
I know that we can prove with pumping lemma that a language is not regular.
I know that if $L_1 \subset L_2$ and $L_2$ is regular, then $L_1$ maybe regular or not so in this example, $0^n1^n \subset L$ but we can't say that this language is not regular.
next, I think that $L$ is regular because grammar $A$ can produce anything but after a little try, I found that $A = 0^*1^*$ and $110101$ is not a part of language, so it can not be $(1 | 0)^*$ which is regular.
at this point, I don't know is it regular, or not. $S$ grammar can produce strings which has equal 0 and 1 at the start and end, but maybe $A$ grammar can produce something that make language regular.
Is it possible to help me? can you give me any idea?

Idea (from comment):

if we say that $L$ is regular, then we get intersection of it and $0^*1010101^*$.
for accept a string in this language, there is two state.

1) not equal number of $0$ and $1$ at the start and end of string:
suppose number is form of $0^n1010101^{n+k}$ for $k \gt 0$ (we can prove same for $0$). use $S \to 0S1$ to create $0$ at the start and $1$ end, after some level we get to $0^nS1^n$ but we can't use any $S \to 0S1$ or $S \to 1S0$ anymore so we must use $S \to AA$ and $A = 0^*1^*$ and we can't match string. we couldn't construct it if we start with $S \to AA$.
so $L$ can't produce this kind of strings.

2) equal number of $0$ and $1$ at the start and end of string:
now our string is form of $0^n1010101^n$ and we can construct it with only $S \to 0S1|1S0$.

so intersection of $L$ and $0^*1010101^*$ is $0^n1010101^n$ which is easy to prove that is not regular. so our hypothesis is not correct and $L$ is not regular.

Thanks for idea. Is it true?

Your grammar generates the following language:
$$
L = \{ w0^*1^*0^*1^*\bar{w}^R : w \in \{0,1\}^* \},
$$
where $\bar{w}$ is obtained from $w$ by switching 0s and 1s. Consider now $L' = L \cap 0^*1010101^*$. It is not hard to check that $L$ contains all words of the form $0^n1010101^n$ (take $w = 0^n1$ and $0101 \in 0^*1^*0^*1^*$). Conversely, if $0^n1010101^m \in L'$ and $n \neq m$, say $n > m$, then the decomposition $0^n1010101^m = wx\bar{w}^R$, where $x \in 0^*1^*0^*1^*$, must satisfy that $\bar{w}^R = 1^k$ for some $k \leq m$; but then $x = 0^{n-k}1010101^{m-k} \notin 0^*1^*0^*1^*$. We conclude that
$$
L' := L \cap 0^*1010101^* = \{ 0^n1010101^n : n \geq 0 \}.
$$
It is not hard to check that $L'$ is not regular (for example, the words $0^n$ are pairwise inequivalent), and so $L$ also isn't regular.


How many languages exist over the following alphabets? (a) We have alphabet $\Sigma=\lbrace 1 \rbrace$, $\Sigma=\lbrace a,b \rbrace$ and (b) also an alphabet with size $k$ and words with length $n$.

For the first two alphabets in (a), we know that there are countably infinite words:
$$|\Sigma| = |\mathbb{N}|$$

For the alphabet in (b) we know we have $k^n$ number of words.

Now I need to find the number of languages that exist for the symbol set $(a)$ and $(b)$.

I think the number of alphabets is also countably infinite, so it has the same size as the power set of $\Sigma$ which has a cardinality $|\Sigma| = |\mathbb{N}|$, therefore there are $2^{|\mathbb{ℕ}|}$ languages.

Now my question is, does this $k^n$ have a role in this $2^{|\mathbb{ℕ}|}$; does it change anything?

A language over an alphabet $\Sigma$ is any subset of the set of all finite strings with elements in $\Sigma$. If $\Sigma$ is finite or countably infinite, and not empty, then the set of all finite strings with elements in $\Sigma$ is countably infinite ($\aleph_0$) and the set of all languages over the alphabet $\Sigma$ has the same cardinality as the real numbers ($\aleph_1$). (Not calling it just "uncountable", because the set of languages is indeed uncountable, but there are uncountable sets with higher cardinality).


Showing transitivity of PSPACE? For the following question:

If B is an element of PSPACE and A is an element of PSPACE-Complete, and A polynomial reduces to B, then B is an element of PSPACE-Complete.

I am trying to prove this, but I don't understand how to get started. Can anyone help please?

If $A$ is PSPACE-Complete, then any $A' \in$ PSPACE can be reduced to $A$ in polynomial time. What can you say about a polynomial time reduction from $A'$ to $B$?


Prior probability in HMM This is the HMM model considered in the question

And this is the emission probabilities for the respective states. There are two emission values, bringing an umbrella and not bringing an umbrella.

Description of the question:

The question considered the initial state as sunny.
On day 2, the person brought an umbrella.
On day 3, the person didn't carry an umbrella.

We have to find the probability that it's foggy on 3rd day.

Given: Prior probability of the caretaker carrying an umbrella is 0.5.

According to me, the answer to this question was addition of the terms in the red circles.

Where α1 = 0.8 * 0.1, α2 = 0.05 * 0.8, α3 = 0.15 * 0.3

Problem I faced:
But the answer included dividing the answer I got by (0.5)2. That is, I guess they are dividing by the prior probability two times for the two transitions, but I'm not clear as to why they are dividing.

Let $s_2,s_3$ be the states on the second and third days, and let $x_2,x_3$ be the indicators of carrying an umbrella on these days. Then
$$
\newcommand{\Sunny}{\mathit{Sunny}}
\newcommand{\Rainy}{\mathit{Rainy}}
\newcommand{\Foggy}{\mathit{Foggy}}
\newcommand{\Yes}{\mathit{Yes}}
\newcommand{\No}{\mathit{No}}
\Pr[s_3 = \Foggy \mid s_1 = \Sunny, x_2 = \Yes, x_3 = \No] =
\frac{\Pr[s_3 = \Foggy, x_2 = \Yes, x_3 = \No \mid s_1 = \Sunny]}{\Pr[x_2 = \Yes, x_3 = \No \mid s_1 = \Sunny]}
$$
It seems you might have forgotten the denominator.


What is Finite Automata Bowl? I was trying to find info about this Finite Automata type FAB (Finite Automata Bowl) and wasn't able to find a lot. It is basically the rules that apply to PDA apply to FAB except you drop the temporal order of the stack. So instead of being restricted to only removing the top symbol of the stack, you can remove any symbol of the bowl.

The question is, does there exist a context-free language that is not accepted by an FAB?

If I understand the rules correctly ...

First I call them here Bowl Automata, since they cannot be considered
finite because of the Bowl.

All you can do with the bowl symbols is to count, with a different
count for each symbol.

So the bowl automaton is only a multicounter automaton, which has been
analyzed a long time ago as counter machine, with many variants.

There seems to be significant literature about it.

Counter machines with 2 counters (i.e. 2 bowl symbols) are actually as
powerful as Turing machines (TM), up to proper initial encoding of the
problem ... which is a significant constraint. Read the proof in
Wikipedia. But this constraint is apparently only when the input of the
TM is to be encoded in the counters. This result appears in a 1967
book by Minsky, Computation. For off-line TM, taking their input on
a separate tape, there is no such problem.

So all recursively enumerable languages can be recognized by a two symbol Bowl Automaton, including of course the CF languages. The simpler case of the PDA is worth examining, as it is an important step of the general proof.

The PushDown Automaton is an off-line machine since the
input is from a normal read-only tape. The encoding suggested in the proof (step 2 of
the proof) TM allows it to simulate a PDA with only two bowl
symbols. The gist of the construction is to consider the PDA stack as
representing a number in base $n$, where $n$ is the cardinality of the
stack alphabet. Instead, you use one bowl symbol to represent the
stack number in unary notation (just use a very big bowl). Actually,
you simplify by first using a stack with only two symbols, to use
binary notation before making it unary in the bowl.  The remaining
bowl symbol is used for book-keeping while simulating the binary stack with unary notation.  Read it from wikipedia, it is
quite simple.

So each CF language is accepted by some Bowl Automaton, actually even restricted to two bowl symbols (but a very large number of each :-)

The construction is simpler for the simulation of a PDA stack. But since a TM can be simulated with two stacks and a finite control, a TM can be simulated by a Bowl Automaton. An the four counters (2 for each stack) can actually be reduced to two.


Push down automata what to do when there is no suitable transition This is a question that has emerged from a recent quiz I have taken. In short

  Consider the following transitions on a push down automaton. Assume the starting state is q. Which one of the following inputs will lead the automaton to state p with the stack containing the string XXZ?

I am gonna write only the transitions from state q regardless of the input symbol:

 (q, 0, Z) -> (q, XZ)
 (q, 0, X) -> (q, XX)
 (q, 1, X) -> (q, X)
 (q, ε, Χ) -> (p, ε)

Now the thing we note here is that there is no transition from state q when there is an empty stack regardless of the input symbol. How does one answer that question assuming we start from an empty stack? I have omitted the inputs cause I don't really care about the answer to the quiz, all I want to know is how would someone start working on that?

Starting with empty stack is not allowed.

A PDA is usually defined as (Q, Σ, Γ, δ, q0, Z0, F), where the symbols have their usual meanings. One of these is Z0, the stack start symbol. It is on the stack when the PDA starts.

So by definition you have Z0 on the stack at start.
You need to find Z0 in your case and start with that.