Decidability of Turing machines that never move their heads past any input string $L_1 = \{ \langle M, w\rangle : M \text{ is a TM that never moves its head past the input string } w \}$
  $L_2 = \{ \langle M\rangle : M\text{ is a TM that never moves its head past any input string} \}$

Consider the two languages above. I want to know which ones are decidable.

I know that $L_1$ is decidable, because $M$ has only a finite amount of possible configurations with the input string $w$, so we can create a Turing Machine (TM) for to check 1 step past the number of combinations and decide.

However, for $L_2$, can we do that? I feel like $L_2$ is undecidable, because we can there seems to be no limit to the possible configurations.

The halting problem, $\mathsf{HALT}$ reduces to $\overline{L_2}$.

Given a TM $T$ and input $w$, create a new TM $N$ that on any input of length $n$, simulates $T$ on input $w$ for $n$ steps and then stops except that if $T$ ever halts before $n$ steps, $N$ will move its head to the right forever.

There is a gap in the above reduction. When $N$ simulates $T$ on $w$ for $n$ steps, it may move out of the input when it moves left (we assume that input is put to the right of the origin, the initial position of $N$'s head, inclusively). This gap can be resolved by the classic trick of "translating the tape". When the simulation is about the move to the left of origin, let $N$ translate the current of the tape one cell to the right. Then $N$ goes to the origin, as if it were the cell to the left of the origin. In this way, we will make sure $N$ will never move out of the input string as long as the simulated $T$ on $w$ does not halt. (To enable $N$ to recognize the origin, it should always mark the origin with a "compound" symbol that also tells its original symbol. For example, if the original symbol at the origin is $A$, $N$ should change it to $A_o$, a symbol that is not $A$ but points to $A$. "Compound" symbols are also used when $N$ translates the content of the tape.)

Since $\mathsf{HALT}$ is not decidable, $\overline{L_2}$ is not decidable. So, $L_2$ is not decidable.


Construct Turing Machine which accepts the language $ww$ I try to construct a TM that accepts the language $\{ ww \mid w \in \{a,b\}^* \}$.

Between the words $w$ is no delimeter, so I don't know, how my TM can know where the first $w$ ends and the second $w$ begins.

Is there a trick for this?

Here is a sketch for how a deterministic machine might work:

place a marker in front of the input.
go through the input, checking if the length is even. If not, reject.
place a marker behind the input.
going back and forth, move the markers towards each other until they meet in the middle.
as long as the halves are nonempty, compare and erase their first letters and reject if not equal.
accept.


What does Arora mean by 'computational history'? In Arora's paper, he wrote,

  Papadimitriou and Yannakakis also noted that the classical style of reduction (Cook-Levin-Karp [41, 99, 85]) relies on representing a computational history by a combinatorial problem. A computational history is a very non-robust object, since even changing a bit in it can affect its correctness. This nonrobustness lay at the root of the difficulty in proving inapproximability results.

What does he mean by this statement? In particular: what does it mean by 'computational history', and 'representing a computational history by a combinatorial problem'?

I conjecture that: [it is] a very non-robust object, he means that computation could make many many errors. So, in the last statement in the paragraph, maybe he means nonrobustness [the ability to make many errors] lay at the root of the difficulty in proving inapproximability.

Could someone tell me how nonrobustness exists in Karp/Levin reduction?

The computational history consists of the contents of the tape of the Turing machine after each step. These are the variables in the SAT instance produced by the Cook-Levin theorem, which is the combinatorial problem which represents the computational history.

This representation is fragile in the sense that even when the SAT instance is unsatisfiable, we may be able to satisfy almost all of its clauses - say, all but a constant number. This is because the reduction in the Cook-Levin theorem is very local: if we flip a single bit in the computational history, then this falsifies only a small number of clauses.
In contrast, the PCP theorem guarantees that the SAT instance is either satisfiable or at most 99% of its clauses can be satisfied, and this implies a hardness of approximation result for MAX-SAT.


Can this language be defined by a Context Free Grammer? I was solving one of my practice questions, defining a language with Context Free Grammar Productions , but I am stuck on one question , Here are my attempt:

Question: $L = \{a^n b^m c^p \mid n = m + p + 2\}$

My Attempt:

S -> aaBC

B -> aBb | ^

C -> ?  (Now how can i increase length of `a` Terminal by C as i increased from B)

Is this language not context free / impossible ?

You'll need to "wrap" the Bs in the Cs:

S -> aaC
C -> aCc | B
B -> aBb | ɛ

With that, we have

$L(B) = a^m b^m$,

$L(C) = a^p \cdot L(B) \cdot c^p = a^p a^m b^m c^p$ and

$L(S) = a^2 \cdot L(C) = a^2 a^p a^m b^m c^p = a^{m+p+2} b^m c^p$.


Proof that this problem is in NP I have to prove the following problem is in NP (and define verifier as well as the certificate/witness):

The input is a set of $n$ boxes with weights $w_{1},\ldots,w_{n}$ and two numbers $s$ and $t$ (all natural numbers).
Can the boxes be loaded onto $s$ trucks if each truck can only carry a total weight of $t$?

Apparently this is supposed to be easy, but I'm stuck.

Once you get the hang of these, they are quite easy, so the first thing is not to over think things.

To prove containment in NP (in this manner) you need (as you mention):

A witness. This is just a "string" that proves an instance is a Yes-instance. So it can just be the solution. When we say "string", typically we don't define how the string is encoded, or even really that the witness is a string. What we give is a format for a solution.
A verifier. This is a Turing Machine that takes a witness (hence why the witness is a string, formally) and the original input, and checks that the witness is correct. So really the verifier is a set of steps to perform this check, given a witness in the correct format. For NP, we have the additional restriction that the verifier has to run in deterministic polynomial time.

So for this problem we can represent a solution as a collection of sets of boxes. We can assume that the boxes have a unique ID. This is the witness. You should, to cement this, try to write done a more precise format for this.

The verifier then should take such a string and check the following:

There are at most $s$ sets (or exactly, depending on the exact problem specification).
That each box appears exactly once, somewhere.
That the total weight of each set is at most $t$.

It should, hopefully, be clear that this verifiers that the solution is correct. The only thing that remains to do, is show that the verifier runs in deterministic polynomial time. Again this should hopefully be fairly clear. Even if we do each step separately, it's three passes over the list  (we can, for convenience, assume that the verifier is a multitape machine, so we can more easily represent data structures), and this is certainly polynomial.


Randomly assign n elements to n agents such that each agent only knows its own element Problem
I'm working on an app that involves shuffling and distributing playing cards to players. As a challenge, I tried to solve this problem in a way that doesn't require a trusted intermediary.
In other terms, the task is to find a distributed algorithm that

uniquely assigns $n$ agents numbers $1..n$
allows each agent to know nothing about the assignment but its own
when revealing the assignment, allows other players to verify the assignment

We also assume that knowing other's assignment is an advantage for each agent, and revealing its own prematurely a disadvantage. Agents are also assumed to be able to talk with each other in a way hidden from all other agents.
Partial solution
The solution I came up with works only under the assumption that adversaries do not collaborate.
The idea is to create a set of $n$ nonces, and assign each agent exactly one nonce. The set is then passed from agent to agent in an agreed upon order, hidden from all others, until each agent received the set exactly once. Each time an agent receives the set, it swaps its nonce with a new one, memorizes the new nonce, and confirms receival of the set to the others. This entire procedure is done twice, at which point, all agents have received the set at least once after all other agents swapped their nonces, making it impossible to recognize and hence map the nonces to the other agents.
When the last agent receives the set the second time, it shares it with everyone, and all agents confirm to the others that their nonce is contained in the set. The agents then assign a number to each nonce in the set based on an agreed upon random seed, giving us the required unique assignment.
To allow ownership verification, instead of the nonces, agents put the hash value of their nonce on the set, revealing the actual nonce only when verification is required.

The problem with this solution is that if adversaries are allowed to collaborate, each time an adversary receives the set, they can compare their versions, identify changes and potentially derive which nonce belongs to other agents, allowing them to know what number got assigned to them.
All ideas are appreciated!

This problem is part of a set of problems known as Mental Poker.
There is an excellent and small article by Shamir, Rivest and Adleman that describe a practical way about how to implement such algorithm.
The abstract is gold:

Can two potentially dishonest players play a fair game of poker without using any cards (e.g. over a phone)?
This paper provides the following answers:

No. (Rigorous mathematical proof supplied.)
Yes.(Correct & complete protocol given.)

Basically, from an information-theoretic point of view, playing such a game is impossible without a trusted third party, but it is feasible to design a protocol using well-known hard to reverse cryptographic functions.

The algorithm will work as following:
Suppose you have $n$ nonces (numbers from $1$ to $n$). Each participant in the protocol has access to secret functions $e_i$ and $d_i$ which are used to encrypt and decrypt data. This functions should satisfy few properties, which we will analyze later.
The first participant is given the full set of nonces. It encrypts each nonce with its secret function $e_1$, shuffles them randomly, and passes the resulting data to second participant.
Second participant will do the same, but in this case it doesn't have nonces, but a random permutation of the encrypted nonces. It will also encrypt each element with its own secret function $e_2$ and shuffle the data again.
Then third participant, and so on, until all participants have shuffled and encrypted the data with its secret function.
Overall the setup process is:
data = [1..n]
for i in [1..n]:
    data = [e_i(nonce) for nonce in data]
    shuffle(data)

After this setup, each element of data are the nonces encrypted with all secret functions $e_i$ in a random order unknown to any participant.
Notice that at this point is impossible for each participant to deduce each nonce without the help of other participants. And it is enough that one of the participants to shuffle the data completely random to remove any possible bias in the resulting order, independently if some malicious participant tries to bias the order.
Participant $i$-th is assigned the nonce at position $i$. To recover such nonce, participant $i$ asks each other participant $j \neq i$ to decrypt the value with its secret function $d_j$ in turns. At the end participant $i$ will have its nonce only encrypted with its own secret function $e_i$ so it can recover it using $d_i$.
Recovering nonce $i$:
nonce_i_encrypted = data[i]
for j in [1..n]:
    if j == i:
        continue
    nonce_i_encrypted = d_j(nonce_i_encrypted)

nonce_i = d_i(nonce_i_encrypted)

At the end of this procedure each participant knows its own nonce, but no other participant know anything about it.
After using this values for your current problem a player can claim they are really in control of such nonce, by either publishing the secrets functions $e_i$ and $d_i$, so everyone can compute locally all the values, or decrypting the value data[i] after the first step but before the second step, publishing and then using this value as the input in the second step to fully decrypt it.
The functions $e_i$ and $d_i$ should have the following properties:

$e_i(x)$ is the encrypted version of a message $x$ under key $i$,
$d_i(e_i(x)) = x$ for all messages $x$ and keys $i$,
$e_i(e_j(x)) = e_j(e_i(x))$ for all messages $x$ and keys $i$ and $j$,
Given $x$ and $e_i(x)$ it is computationally impossible for a cryptanalyst to derive $i$, for all $x$ and $i$,
Given any messages $x$ and $y$, it is computationally impossible to find keys $i$ and $j$ such that $e_i(x) = e_j(y)$.

As stated in the paper, most of this assumptions are somehow common except for property 3), which tells the encryption functions must commute.
They propose a simple encryption scheme that satisfies these properties. Let's say all participants agree on some large prime number $P$ (it is ok if it fixed in the protocol). And each participant secretly choose a random number $k_i$ such that $gcd(k_i, P - 1) = 1$. Let's say $q_i$ is such value that $k_i \cdot q_i \equiv 1 \mod(P -1)$. Then participant $i$ can use secret functions:
$$e_i(x) = x^{k_i} \mod(P)$$
$$d_i(y) = y^{q_i} \mod(P)$$
Some caveats about this algorithm: Participants can't cheat in such a way that colluding benefits them in learning the nonce about the other peer (unless of course $n-1$ participants collude, and only one nonce is remaining). However, malicious participants can attack the protocol by no participating, effectively stalling the dealing process, since a lot of actions are required from each participants while they are dealing the nonces. They can also produce gibberish, but this can be mitigated extending the protocol to detect which participant was the culprit and penalizing such participant at a higher level.

I implemented this algorithm for a poker game in NEAR blockchain. You can see the code in rust here. Notice there isn't any trusted third party in a blockchain, but there is a trusted computing environment which all participants can use as a mechanism to run this protocol.


Stack without duplicates I was thinking about the implementation of a DFS on graphs, and particularly about space complexity. The DFS algorithm can be implemented with a stack data structure. When a vertex $v$ is met during the exploration of the adjacency list of a vertex $w$, if $v$ has not already been processed, then $v$ is added to the stack. A vertex is marked a processed when it exits the stack (contrary to BFS, where a vertex is marked as seen when it enters the queue).
That way, the stack may contains duplicates during the execution of the DFS. Since each vertex is processed at most once, the size of the stack for a graph $(V, E)$ is $O(|V| + |E|)$.
Since I wondered if it was possible to get $O(|V|)$ space memory for the DFS, I tried to find a data structure of stack without duplicates. I found a solution for the DFS (given as an answer to this question), but the structure I found has restrictions: it works in space $\Theta(n)$ in the case I know in advance that the values entering the stack will be in $[\![0, n-1]\!]$.
My question is: is there a more efficient way to implement a stack without duplicates (in a stack without duplicate, if I push an element already in the stack, then this element is put at the top of the stack, and the duplicate is deleted), in the general case where I don't know in advance the values entering the stack? The time complexity for operation of pushing/popping should be in $O(1)$ worst case, amortized or average case (in this order of preference). Also, is there a way to use $\Theta(n)$ space memory, $n$ being the current size of the stack (and not the maximal size).

Here is the solution I found. I suppose here that the values entering the stack will be in $[\![0, n-1]\!]$. For that, I create an array $a$ of size $n$ that will implement a kind of doubly linked list: it is such that for $i \in [\![0, n-1]\!]$, $a[i] = (p_i, n_i)$ where:

if $i$ is not in the stack, $(p_i, n_i) = (-2, -2)$;
if $i$ is in the stack, $p_i$ (previous) is the value that is above $i$ in the stack ($-1$ if $i$ is the top of the stack) and $n_i$ (next) is the value that is below $i$ in the stack ($-1$ if $i$ is the bottom of the stack).

The stack is then a couple $(i_0, a)$, where $i_0$ is the top element of the stack ($-1$ if the stack is empty).
That way, the usual operations on stack can be done in $O(1)$ worst case:

testing emptyness: just check if $i_0 = 1$ or not;
pushing element $i$:

if $a[i] = (-2, -2)$, $a[i] \leftarrow (-1, i_0)$ then $i_0 \leftarrow i$
if $a[i] = (p_i, n_i)$ (duplicate case), then $a[p_i] \leftarrow (p_{p_i}, n_i)$, $a[n_i] \leftarrow (p_i, n_{n_i})$ (only if $p_i/n_i\neq -1$), $a[i] \leftarrow (-1, i_0)$ then $i_0 \leftarrow i$

popping element: $i\leftarrow i_0$, $i_0 \leftarrow n_{i_0}$ $a[i] \leftarrow (-2, -2)$, return $i$.

In the case of the DFS, one can also add the case $a[i] = (-3, -3)$ to differentiate vertices that already exited the stack from the $a[j] = (-2, -2)$, vertices that have not already entered the stack. The array a can then replace the boolean array usually used.


Time complexity for modular arithmatic I read about the time complexity for modular arithmetic in many books. There is one thing that I don't understand. I read in some books the following:

For any $a \mod N$, $a$ has a multiplicative inverse modulo $N$ if and only if it is relatively prime to $N$. When this inverse exists, it can be found in time $O(n^3)$ (where  $n$ denotes the number of bits in the binary representation of $N$) by running the extended Euclid algorithm. My question revolves around extended Euclid algorithm having $O(n^3)$ complexity.

When I write in Java or C#, a line like this:

A = B.modInverse(N) // Java syntax

Can I usually say that this line has time complexity $O(n^3)$?
Or is it necessary to write the code for the extended Euclid algorithm?

Secondly, does extended Euclid algorithm depend on the compiler or the computer architecture?

The running time of a library function depends on the way the library function is implemented. Moreover, oftentimes it is worthwhile to code non-optimal algorithms, since for practical $n$ they might be more efficient. One good example is matrix multiplication, where the fancy algorithms are slower in practice than optimized versions of the trivial one.

In your specific case, my guess would be that they implemented the textbook solution. You can always try looking at the source code. Another possibility is timing the function for various $n$, and see if the running time scales like $n^3$.


Are synchronous message sends a subset of async. ones? Imagine any object oriented PL based around the idea of message sends: some method basically performs something like this:

send(target=someTarget, sender=self, message=someMessage)

Also, most of the PL allow for async message communications, where you can issue multiple messages to multiple targets and then "yield" to scheduler.
My question is: are synchronous communcations a subset of asynchronous ones?
In my head you can break down any synchronous message send into something like this:

asyncSend(target=someTarget, sender=self, message=someMessage)
target.setNotify(self)
self.setBlocked()
yield

Which will be totally aquivalent to a synchronous message send, BUT:

The problem I currently see if you try to mix these two together. When some method issues an async message send and then, before yielding, performs a synchronous message send, which gets kinda messed up. Hence the question :)

Also, sorry if this is wrong stackexchange. I don't think this question applies to the usual SO.

EDIT1: rephrasing the question: which of both concepts is more general? can you even say that?

There are several possible semantics for asynchronous message passing, so there isn't a single answer to this question. It depends how the scheduler works.

From a theoretical perspective, the simplest model (for some version of simple) is to not have a scheduler. Once a message has been emitted, it may be received at any time when the receiver is ready. All the parts of the system work in parallel. This is the principle of process calculi, of which there is a rich theory.

The notion of synchronicity then depends on what the continuation of a send operation is. In the pi calculus, which is arguably the most important model of concurrency, sending is a synchronous operation, with a continuation. $\bar a\langle x\rangle.P$ (“send $x$ on $a$ then do $P$”) blocks until some other part of the system is ready to receive a message on $a$. An asynchronous send operation is represented by doing the send in parallel with something else:

asyncSend(target=a, message=x);
stuff();

is represented by $(\bar a\langle x\rangle. 0) \mid \mathtt{stuff}$ (send $x$ on $a$, then do nothing; all of this in parallel with stuff).

The join calculus is another process calculus inspired from the pi-calculus. It defines both asynchronous and synchronous messages. Synchronous messages act like function calls — they're remote procedure calls. Asynchronous messages have no continuation: once the order to send the message has been given, the message will sit around until it gets received; the only way to know that the message has been received is to take action on the receiver. The snippet above is represented by $a\langle x\rangle \mid \mathtt{stuff}$. The notation $a\langle x\rangle$ means “send $x$ asynchronously on $a$”; there's no continuation for the send operation: $\color{red}{a\langle x\rangle; Z}$ is not even syntactically valid. A synchronous call can be encoded with asynchronous calls by having the receiver reply. If the receiver sends an acknowledgement:
$$ a\langle x\rangle \mapsto  \mathtt{ack}\langle\rangle \mid \ldots$$
then the sender can wait for this acknowledgement:
$$ a\langle x\rangle \mid (\mathtt{ack}\langle\rangle \mapsto \ldots) $$
models

syncSend(target=a, message=x);
...

In the join calculus, synchronous and asynchronous operations are distinguished in the syntax. Therefore there's no possibility of “getting messed up”.

The mess comes from trying to force concurrent behavior into a sequential framework. Since you mention object oriented languages (which have absolutely nothing to do whatsoever about asynchronous message passing), you're probably thinking of implementations of these concepts in languages like Java and C#. I'm not familiar with those libraries, but as far as I know, they introduce additional complications by forcing the programmer to be explicit about threads. Threads are not a natural concept in process calculi: if things happen in a certain order, it's because of how the information is propagated, not because the language describes how a scheduler will do its job. A call like asyncSend may have additional constraints on when it takes place relative to other things that are going on in the same thread. If there is some constraint between an asynchronous send and a subsequent synchronous send, that's a limitation of the library which defines when the asynchronous send may take place. A true asynchronous send would not have such a constraint.


Confirmation of alternative correctness proof for Floyd-Warshall's all-pair shortest-path algorithm The most common proof for Floyd-Warshall's algorithm is an induction proof on the outer-most loop, which says

$\delta^k(i,j)=\begin{cases}
\min\{\delta^{k-1}(i,j),\delta^{k-1}(i,k)+\delta^{k-1}(k,j)\} & \text{for}\,k\geq 1\\
w(i,j) & \text{for}\,k=0\,\text{(i.e., base case)},
\end{cases}$

where $d^k(i,j)$ is the shortest path from $i$ to $j$ using $k$. Here I present another proof using induction on the length of any shortest path. I have a feeling that the main idea of my proof is the same as above, but I'm not sure if it is correct (missing something important). Here is the proof below:

Proof. (induction on $l$, the lengths of all shortest paths between all pairs of vertices $x_i$ and $x_j$ in the graph)

Base case $l=1$: the shortest path between some pair of vertices $x_i$ and $x_j$ is exactly the edge $(x_i x_j)$. In this case, $d_{ik}+d_{kj}\geq d_{ij}=k((x_i x_j))$ for all $k$ by the fact that $(x_i x_j)$ is the shortest path. The algorithm will not change $d_{ij}$ in this case, so it is correct.

Now, suppose that the algorithm will correctly find the length of all shortest paths of length up to some $c$, and that the shortest path between some pair of vertices $x_i$ and $x_j$ is $(x_i x_{p_1} x_{p_2}\cdots x_{p_c} x_j)$, which has length $c+1$. Now, let $x_{p_m}$ be the vertex in the path that has the biggest index in the distance matrix, and consider the path divided into $(x_i\cdots x_{p_m}\cdots x_j)$; let $P_1=(x_i\cdots x_{p_m})$ and $P_2=(x_{p_m}\cdots x_j)$. For $P_1$, the algorithm will correctly find its length by the inductive hypothesis, since it is of length at most $c-1$ and it is the shortest path between $x_i$ and $x_{p_m}$; similarly the algorithm will correctly find the length of $P_2$, since it is of length at most $c-1$ and it is the shortest path between $x_{p_m}$ and $x_j$. The algorithm will correctly do the comparison $d_{i p_m}+d_{p_m j}<d_{ij}$ when $d_{i p_m}$ and $d_{p_m j}$ are the length of $P_1$ and $P_2$, respectively, and update $d_{ij}$ correctly. This is because $p_m$ has the biggest index in the matrix, meaning that the algorithm would have already correctly found the length of $P_1$ and $P_2$ and stored them in $d_{i p_m}$ and $d_{p_m j}$, since they share intermediate vertices of smaller index and therefore would have been found in previous iterations of the outer-most loop.

P.S. To clarify, this is for a homework problem (as these problems typically are), and I am asking this after the due date. Most large universities in the U.S. nowadays employs graders (I am one myself), which means that my alternate proof may or may not receive a careful look. My point is that I want to know whether I missed something in the proof.

Your effort towards a new kind of proof for Floyd-Warshall algorithm is appreciated.

On one hand, your proof is very well written. It cannot be said to be all wrong as apparently you have tried to avoid saying anything wrong.

On the other hand, I would not call you proof a proof that is different from the usual induction proof on the loop variable of the outer-most loop.

  ... $p_m$ has the biggest index in the matrix, meaning that the algorithm would have already correctly found the length of $P_1$ and $P_2$ and stored them in $d_{i_{p_m}}$ and $d_{p_{m_j}}$, since they share intermediate vertices of smaller index and therefore would have been found in previous iterations of the outer-most loop.

Take a moment to reflect. What you said above is basically the induction hypothesis in the usual induction proof on the loop variable of outer-most loop. That induction hypothesis can be viewed as a proposition that is even stronger than the final result of the Floyd-Warshall algorithm. Armed with that kind of knowledge, it is expected the correctness can be proved easily. In other words, it is not far fetched to say you just proved its correctness by admitting its correctness. Or, you just repeated the usual proof with some extra unnecessary logic.

There is another hidden flaw in your proof that is actually critical. Suppose there is a negative cycle in a connected graph. Floyd-Warshall algorithm handles that situation graciously. However, there is no shortest paths between any pairs of vertices in the graph, since given any path, you can always find another path that is shorter. So, your induction hypothesis becomes void in that case.


Proving that every derivation-tree has at most one leftmost-derivation in a context free grammar I am trying to prove the following theorem:

For every derivation-tree in a context-free grammar $G=(V,T,P,S)$ there exists at most one leftmost derivation.

My partial proof by contradiction (I stucked at Cases (2) and (3)):

Let $G = (V,T,P,S)$ be a context-free grammar.

Suppose that for some derivation-tree there are two distinct rightmost derivations:

$S = _0 ⟹_{lm} _1 ⟹_{lm} _2 ⟹_{lm} … ⟹_{lm} _n = x$
$S = _0 ⟹_{lm} _1 ⟹_{lm} _2 ⟹_{lm} … ⟹_{lm} _m = x $
(x is the frontier of the tree)

It is clear that $_1 = _1$ since the first derivation uses a production rule of the form
$S ⟶ Y_1 … Y_k$ where $Y_1 … Y_k$  are the children of the root node $S$.

Now since the derivations are distinct we get that there are three cases:

(1) $∃ i_0 ∈ \{2, … , min(m, n)\}, (∀ k ∈ \{ 0, … , i0 -1 \}, _k  = _k ) ⋀  _{i_0}  ≠ _{i_0}$
(In other words: it says that the two derivations are identical till we reach some point in both derivations where they become distinct)

(2) $n < m ⋀ ∀ k ∈ \{ 0, … , n \}, _k  = _k$
(In other words: it says that the first derivation is a “sub” derivation of the second one)

(3) $n > m ⋀ ∀ k ∈ \{ 0, … , m \}, _k  = _k$
(In other words: it says that the second derivation is a “sub” derivation of the first one)

Case (1): If $∃ i0 ∈ \{2, … , min(m, n)\}, (∀ k ∈ \{ 0, … , i0 -1 \}, _k  = _k ) ⋀  _{i_0}  ≠ _{i_0}$ , We get that $∃w∈T^*, ∈(V∪T)^* , A∈V, _{i_0-1}  = _{i_0-1} = wA$ , Since both derivations are in the same derivation-tree, The only possibility is that different production rules where used on different variables, but since the derivations are leftmost-derivations, we must use at the $i_0$’th derivation the corresponding production-rule (in the derivation-tree) on $A$,  since $A$ is the leftmost variable. Again, since the derivations are in the same derivation-tree, The production rule used on A  must be the same rule $A ⟶ Z_1 … Z_k$ where $Z_1 … Z_k$  are the children nodes of the node $A$. Therefore we reached the contradiction $_{i_0}  = _{i_0}$.

Case (2): If $n < m ⋀ ∀ k ∈ \{ 0, … , n \}, _k  = _k$ then we get that $_n  = _n$ , Now  since $_n = x$ we get $_n  = _n = x$, Since m > n and since $x = _n ⟹_{lm} … ⟹_{lm} _m = x$, we get that $x  ⟹_{lm}^+  x$.

Now I do not know how to proceed.

Case (3): If $n > m ⋀ ∀ k ∈ \{ 0, … , m \}, _k  = _k$ then we get that $_m  = _m$ , Now since $_m = x$ we get $_m  = _m = x$, Since n > m and since $x = _m ⟹_{lm} … ⟹_{lm} _n = x$, we get that $x  ⟹_{lm}^+  x$.

Now I do not know how to proceed.

Maybe it got something to do with the fact that $x$ is the frontier of the derivation tree.

Thanks for any help.

Here is a paraphrase of your proof. Suppose
$$
S \Rightarrow \alpha_1 \Rightarrow \cdots \Rightarrow \alpha_n \Rightarrow w \\
T \Rightarrow \beta_1 \Rightarrow \cdots \Rightarrow \beta_m \Rightarrow w
$$
are two leftmost derivations corresponding to the same derivation tree. Then the first step must be the same. This is the point where you're stuck.

What you want to do now is to say that $\alpha_1 \Rightarrow \cdots \Rightarrow w$ and $\beta_1 \Rightarrow \cdots \Rightarrow w$ are also leftmost derivations corresponding to the same derivation tree (obtained from the original one by taking into account the first step), and so by induction these derivations are the same.

There is a small problem – $\alpha_1$ is now not a single symbol! You therefore have to strengthen your induction hypothesis and prove something more general which involves derivation trees starting from sentential forms (words which can involve both terminals and non-terminals).

Alternatively, if you prefer using frontiers of derivation trees, you should strengthen your induction hypothesis in a different (but equivalent) way. Now you are still given the original derivation tree, but some of the productions are marked as already having been performed. Your induction hypothesis now states that all leftmost derivations from this state are the same.

It's also possible to avoid strengthening the induction hypothesis, at the cost of a more complicated argument during the inductive step. Suppose that the first step is $S \to x_1 A_1 x_2 A_2 \dots x_n A_n x_{n+1}$, where $A_1,\ldots,A_n$ are non-terminals and $x_1,\ldots,x_{n+1}$ are words. Any leftmost derivation must first completely derive $A_1$, then completely derive $A_2$, and so on, until $A_n$ is completely derived. Induction shows that there is only one way to achieve any of these $n$ steps.

More generally, I suppose you focus first on why the result is true; only then focus on how to write the argument formally.


Given two total Turing machines, is it undecidable problem to detect whether they give the same output on all inputs? See title. And by all inputs I mean providing the functions with the same input and checking whether they give the same output for each case.

EDIT

If it can be reduced to Halting problem, then how?

EDIT 2

@Ariel's answer doesn't satisfy me since given the concrete machine $T$ and input $x$ he states that there exists a computable function that is equal to $1$ everywhere except $x$ and indicates whether $T$ terminates on $x$, on $x$. Note: there is no algorithm for building such a function since it would answer the Halting problem immediately. He proceeds with noting that if that function coincides (by required in the question decision algorithm) with the constant $1$ (as a function) then $T$ terminates on $x$. Otherwise - it does not. So, Halting problem solved, a contradiction. Except there is no. We didn't build an algorithm for building that function ($f_{M_x}$, if I understood correctly), so we didn't build an algorithm for deciding whether arbitrary $T$ terminates on given $x$. @Ariel, correct me, if I'm wrong...

EDIT 3
@Ariel was correct!!! Since I did not mentioned that required decider algorithm must only accept not descriptions of computable functions but Turing machines implementing them, his answer was fully correct.
Now the thing - I just require for seeked algorithm to process only pairs of always halting Turing machines and testing them for equality on every input. @Ariel, I'm really sorry :-(

EDIT 4
And if somebody still wishes to answer this question, Rice's theorem for partial functions does not help, since I don't require the decider beeing searched for to be such over all partial function, only over total function, i.e. it may not halt on arbitrary not-always-halting Turing machine.

The problem

  Do two halting Turing machines accept the same language (or compute the same "function")?

is undecidable.

Let $M$ be an arbitrary Turing machine. Let $M'$ be a Turing machine that on input $x$, simulates $M$ (on some predefined input) for $|x|$ steps and accepts if (and only if) $M$ halts within $|x|$ steps (or, if you want to go with a TM computing a function, returns $1$ if $M$ halts within $|x|$ steps and $0$ otherwise).

If $M$ doesn't halt then $M'$ accepts the empty language (or, computes the function $f(x)=0$). If $M$ does halt then the language $M'$ accepts is non-empty (or, the function is non-constant).

This gives a reduction from the Halting problem to the problem of detecting equality, since we just need to ask whether $M'$ is equal to the machine accepting the empty language (or, the machine computing the function $f(x)=0$).

This avoids all the issues of the function not being total or being unable to construct the function explicitly.


Show that this language is in NP $\cap$ coNP Say $\ell: \{0,1\}^\ast \to \{0,1\}^\ast$ is a one-to-one polynomial-time computable function that preserves length. Consider the language $$L = \Bigl\{v \;\Big|\; \exists u: \bigl(u_1 = 1 ~~\text{and}~~ \ell(u) = v\bigr) \Bigr\}.$$ How do I prove that $L$ is in $\mathsf{NP} \cap \mathsf{coNP}$? Basically, what would appropriate witnesses for $L$ in $\mathsf{NP}$ and $\mathsf{coNP}$ be?

Hint: Use the fact that $\ell$ is one-to-one, and so to every $v$ there corresponds a unique $u$ such that $\ell(u) = v$.


How to count in linear time worst-case? This question and this question got me thinking a little bit. For sorting an array of length $n$ with $k$ unique elements in $O(n + k \log k)$, we need to be able to store counts of values in the array. There are some suggestions, but I'm looking for a way to do this in worst case linear time. More specifically:

  Given a list $A$ of $n$ elements with $k$ elements distinct, determine a list of tuples $U = \{(x_i, c_i)\}^k$ of all unique elements $x_i \in A$ such that $c_i$ is the count of element $x_i$ in $A$.

Here are some (failed) ideas I've had and have been suggested:

Balanced Binary Search Tree - With this it will take $O(\log k)$ to insert into the tree and increase values. After inserts we could do a tree traversal in $O(k)$. Thus, total time comes out to $O(n \log k)$ which is too slow.
Hash Map - With this we can get $O(1)$ expected inserts and thus $O(n)$ expected time. However, this is still not $O(n)$ worst case.
Empty Space Mapping - Find the minimum and maximum element in $A$. Allocate (but do not initialize) enough memory to cover this range. Use this memory basically as a hash map and include a random hash so that we don't try to access corrupted memory. This strategy presents issues. (1) It's probabilistic with very very very low probability of failing, but still not guaranteed. Using memory like this limits us to floating-point or integer constraints.
Associative Arrays - There are many other associative arrays that can be used, similar to hash maps and BSTs, but I am not finding any that match these constraints.

Maybe there is some obvious method I am missing, but I also think it could be potentially not be possible. What are your thoughts?

This is a nice question.

In the comparison model or, what is more general, the algebraic decision-tree model, the problem of element distinctness has a lower bound of $\Theta(n\log n)$ time-complexity in the worst case as said in this Wikipedia article. So there is no algorithm to count distinct elements in linear time in the worst case, even without counting the duplicities.

However, it is not clear whether it can be done in another computational model.  It seems unlikely in any reasonable deterministic computational model.


Why Right-Division of regular language with RE\E language is regualr? I think I can't understand the meaning of language being decidable.
The next case makes no sense to me:

Considering I have language L1 which is regular, and language L2 which is in RE\R (in particular, it cannot be decided).

The right-division of any regular language with some language is regular, and in particular in R.

so:

L1/L2={x ∈ Σ* | ∃ y ∈ L2 : xy ∈ L1}

is decidable.

But I can't see why. I can't describe an algorithm that decides L1\L2, so how come this language is decidable?
I know how to define the transition function, but does it means that the language is decidable?
After all, I can also define a transition function to the accepting problem, it still does not make it decidable.

After all, to check if x belongs to L1 \ L2 I need to go over words and check if there is a word in L2 that completes x to a word in L1, but if there is none, I will run forever.

I think I'm missing something, so I'm very confused. Would appreciate help!

In fact, if $L_1$ is regular then $L_1/L_2$ is regular for any $L_2$.

Indeed, consider a DFA for $L_1$ with transition function $\delta$ and accepting states $F$. We modify the set of accepting states to
$$
F' = \{ q : \delta(q,w) \in F \text{ for some } w \in L_2 \}.
$$

You might object that "$F'$ cannot be computed". So what? We never said that you can compute a DFA for $L_1/L_2$ given one for $L_1$ and some reasonable representation of $L_2$. All we claim is that $L_1/L_2$ is regular.

Check out this question for a similar but simpler situation.


How to achieve Dijkstra's O(X+Y) in time complexity if edge weights always is 1 or 2? If we were to have a connected directed graph that has X edges and Y vertices and all the edge weights are either 1 or 2. Would it be possible to somehow achieve a time complexity of O(X+Y) using Dijkstra's algorithm, when finding the shortest path between the two given vertices A and B from the graph.

If all edge weights are $1$ or $2$ you can have a linear time algorithm to find shortest path.
First perform a BFS and for every edge $(u,v)$ of weight $2$ add an vertice at the middle $w$ so that you now have two edges of weight one $(u,w)$ and $(w,v)$.

After this BFS your new graph have all it edges of weight $1$ and have at most $2X$ edges.

Now perform an other BFS on this graph to find the shortest path. It gives you a complexity of $O(2X+Y)$.
Thus the total complexity is $O(X+Y)$


How to partition a set into a given number of disjoint subsets subject to some conditions? I am given a set $A\triangleq\{1,\ldots,k\}$, an integer $s\leqslant k$, and non-negative integers $a_{ij}$. My problem is to find $s$ disjoint subsets $S_j$ of $\{1,\ldots,k\}$ such that:

$\bigcup_{j=1}^s S_j=A$; and
$|S_j|\leqslant a_{ij}$ for all $i\in S_j$ and $j=1,\ldots,s$.

How to solve this problem? Is it hard to find a feasible solution?

I think it is not easy to solve the problem because I tried some procedure that starts by some $j\in\{1,\ldots,n\}$ and assigns $i\in\{1,\ldots,k\}$ until the number of $i$ assigned to $j$ are greater than $a_{ij}$ for some $i$ assigned. But this is not correct because I could be left of some $i$ that could not be assigned to any $j$ (because of their $a_{ij}$ which could be not satisfied).

The brute force method, when I have to generate all subsets of $A$ and test each one, works for me ($k=8,n=3$) but very inefficient.

This problem is NP-hard by reduction from Vertex Cover.

In the Vertex Cover problem, we are given a graph $G = (V, E)$ and a number $r$, and our task is to determine whether there is some subset $U$ of at most $r$ vertices from $V$ such that every edge in $E$ is incident on at least one vertex in $U$.  (Equivalently: Is it possible to kill every edge in $G$ by deleting at most $r$ vertices?)

First, partitioning $A$ into $s$ disjoint subsets is equivalent to assigning each element in $A$ exactly one of $s$ possible labels.  The basic idea of the reduction is to create a label $S_j$ for each vertex $v_j$ in $V$, and to "allow" each edge to be assigned only one of the two labels corresponding to its endpoints, in the following sense: assigning an edge a corresponding label introduces no (genuine) constraint on what other edges can be assigned the same label, while assigning an edge to a non-corresponding label prevents any other edge being assigned the same label -- which of course has the effect of pushing up the number of distinct labels required.

To construct an instance $(A, a, s)$ of your problem from an instance $(G, r)$ of Vertex Cover:

Set $k$ to $|E|$, and create an element $(i, j)$ in $A$ for each edge $v_iv_j$ in $E$.  (These pairs can be thought of as the integers $1, \dots, k$; any bijection between them will do.)
Set $a_{(b, c), d}$ to $|E|$ if $d=b$ or $d=c$; otherwise, set $a_{(b, c), d}$ to 1.
Set $s=r$.

If $(G, r)$ is a YES-instance of Vertex Cover, then it's easy to see that the just-constructed instance of your problem is also a YES-instance: just pick the labels $S_j$ corresponding to the vertices $v_j$ in any solution $U$, and for each edge $v_bv_c \in E$ assign the corresponding element $(b, c) \in A$ whichever one of the labels $S_b$ or $S_c$ was picked (choose arbitrarily if both labels were picked).  This solution uses $s$ subsets, and is valid because the only $a_{ij}$ in force are those for corresponding labels, which have the (non-) effect of preventing more than $|E|$ edges being assigned the same label.

It remains to show that a YES-instance $X=(A, a, s)$ of your problem implies that the original $(G, r)$ is a YES-instance of Vertex Cover.  This is slightly more complicated, since a valid solution $Y$ to $X$ may in general assign an edge $(i, j)$ a non-corresponding label $S_m$, i.e., $m \notin \{i, j\}$, meaning that we can't necessarily "read off" a valid vertex cover $U$ from a valid solution $Y$.

However, assigning a non-corresponding label has a high cost that severely limits the structure of the solution: whenever an edge $(i, j)$ is assigned such a label $S_m$, with $m \notin \{i, j\}$, the fact that $a_{(i, j), m} = 1$ ensures that it must be the only edge assigned this label.  So, in any solution $Y$ containing such a non-correspondingly-labelled edge $(i, j)  \mapsto S_m$, we could construct an alternative solution $Y'$ as follows:

Arbitrarily choose the new label $S_z$ for $(i, j)$ to be either $S_i$ or $S_j$.
Assign $(i, j)$ this new label.  If this results in an invalid solution, it must be because exactly one other edge $(i', j')$, $z \notin \{i', j'\}$ had already been assigned the label $S_z$.  In that case, set $(i, j) = (i', j')$ and go to step 1.

The above algorithm must terminate in one of two ways: either a new label $S_z$ is found that introduces no contradiction, or a complete cycle of vertices is found.  In the former case, a valid new solution with $s-1$ sets is found, while in the latter case a valid new solution with $s$ sets is found; either way, we have constructed a valid new solution with at least one more edge assigned to a corresponding label.  After repeating this entire process at most $|E|$ times, we will have produced a valid solution $Y''$ from which a solution to the original Vertex Cover problem can be read off.

This construction is clearly polynomial time, so it follows that your problem is NP-hard.


Finding a cycle in a graph with the biggest value (the sum of all edges) I am trying to solve this problem: we have an oriented, weighted graph and we have to find a cycle with the biggest weight. Weight of a cycle is the sum of all edges forming the weight. The preferred solution is via backtracking.

My idea was to :

backtrack all combinations of vertexes (0s and 1s representing whether vertex is in a subgraph)
then verify if the subgraph is connected
then verify if a source vertex of any edge is in the subgraph is used only once
and then connecting the first vertex with the last one, thus forming a cycle.
If the sum of all weights is > then max, max = sum.

However, this solution doesn't work correctly on any almost any vertex. It finds a cycle, but it never finds the biggest one. Could you help me fix my algorithm? Thanks!

You should note that this problem is NP-hard (i.e., when all edges have uniform weight, a cycle of maximum weight is a Hamiltonian cycle). So unless your inputs are small or somehow usefully structured, it's probably a better idea to go for heuristics since there is likely no polynomial-time algorithm.

To fix your exact algorithm, possibly with a few tricks to speed things up as well, you can have a look at the description of an algorithm given by Rubin [1].

[1] Rubin, Frank. "A search procedure for Hamilton paths and circuits." Journal of the ACM (JACM) 21.4 (1974): 576-580.


How to handle the time complexity for an optimization that depends on numerical values I'm working on an algorithm and there is an optimization I applied that is unpredictable because it depends on calculations done on top of the input trough several iterations, so as the input values change, the optimization gain oscillates (between a 20% to 90% step count reduction) as is adaptive to the input.

Is there any formal approach to handle these situations in respect to time analysis?

One approach not mentioned above is parametrized complexity. The idea is to express the complexity of the algorithm with respect to a parameter of the input. A classical example is when the input is a graph and the parameter is the tree-width. But more generally, the parameter will be something that is typically not easily computable from the input. On a related note, the condition number can be seen as a particular case of parametrized complexity when dealing with numerical problems.


How to compute function rolling averages maximum for each possible interval length? I'm searching for a fast way to calculate

$$ g(k):=\max_{0<i<T-k} {\frac{1}{k} \sum_{j=i}^{i+k} f(j)}$$

for $ 0<k \le T $ given some discrete function $f$ defined on $ [0; T]$.

Is there algorithm to do it faster then naive $O(n^2)$? If so, how?

The usual approach to compute rolling function is to keep/recompute old data and on each step "add" new data and subtract the data going out of the window. So, you need to transform your sum function into updateSum one:

sum(i+1) = updateSum(sum(i), f(i), f(i+k+1))


Show that a function is not a PRFs I am studying cryptography and having some trouble with the PRFs
How do I show that  $f_{k}(x) =x+k^2$ mod $2^n$ is not a Psuedo Random function?  I know that I need to show that the distignuisher can tell this is not random with a better then $\frac{1}{2}$ probability but how would it do that? (I don't just want an algorithm but a means to find such an algorithm for a query attack)
Thanks

Any known plaintext attack instantly reveals the key:
$$f_k(x) - x + 2^n \equiv k^2\mod 2^n$$

On top of that, even without knowing the key or the plaintext, here's a property that no random function should have:

$$f_k(x + 1) \equiv f_k(x) + 1 \mod 2^n$$


What is the reason of using Gaussian model for Background Modeling? I am a new learner to Background Subtraction (Background Modeling) and I am reading a few previous works on how it is performed. Starting with Wikipedia (by searching "Background Subtraction"), I could understand the first few simple methods, until the part "Running Gaussian average". I simply have no idea why a Gaussian probabilistic density function was proposed to fit on the most recent n frames. Reading from the original paper by Wren et al., the reason for using the Gaussian PDF is "computational convenience", which baffled me since the Gaussian PDF does not look simple to me.

In addition, many later methods were based on the Gaussian Mixture Model by Stauffer and Grimson, which was even more complicated. But there seems no explanation about why a Gaussian PDF was used, and why the use was justified.

Can anyone throw some light to me on these questions? Thanks!

The Gaussian function is ubiquitous in statistics and many other fields. One reason is the Central Limit Theorem, which says that the means of independent identically distributed random variables themselves have a normal (Gaussian) distribution. This is why you see the bell curve in nature so often.

The Gaussian PDF may not look simple at a first glance, but it is actually very simple to differentiate and integrate. Remember that exp(x) is its own derivative and its own indefinite integral. It is also one of very few functions whose Fourier Transform can be computed analytically.

Finally, the reason Stauffer and Grimson and others used the Gaussian Mixture Model, is that it is an easy way of approximating a complicated multi-modal distribution.


Is it possible to find the nodes larger than k in a min-max heap in O(m) time? Is it possible to find the nodes larger than $ k $ in a min-max heap in $ O(m) $ time, where $ m $ is the number of nodes larger than $ k $?

If it is possible, then how do I implement the rest of the standard heap procedures in standard time (insert and delete, extract min and extract max is easy obviously)?

If needed the whole problem statement goes like this:

We want to add operation to our (max) priority queue. We are interested in adding the following operation. Below, x and y are objects and x.key and y.key are their keys in the priority queue (the objects can also have other satellite data). If an implementation of the priority queue is done as in CLRS, chapter 6, then the table can be a table of objects – not numbers; in that case x and y can have an attribute i, so that x.i and y.i denote their places (indices) in the table.

REMOVELARGEST(m): remove the m largest elements in the heap
DELETE(x): remove the element x from the heap.
FUSION(x,y): remove x and y from the heap and add the element z with key x.key+y.key
EXTRACTMIN: remove and return the element with the smallest key

Expand the priority queue to support REMOVELARGEST(m) in $ O(m*log(n)) $ time.
Expand the priority queue to support DELETE and FUSION in $ O(log(n))  $ time
Expand the priority queue to support FINDLARGEST(k) in $ O(m) $ time, where $ m $ is the number of elements $ >=k $.
Expand the priority queue to support EXTRACTMIN in $ O(log(n)) $ time.

You can use a max-heap and a min-heap containing the same elements, with pointers joining pairs of identical elements in both heaps. This allows supporting all the usual operations in logarithmic time, and the new operation (finding all nodes larger or smaller than a given value) in time linear in the output size.


Time complexity of $T(n) = nT(n-1) + n^2$ This time complexity comes from $N$-queen problem. There are many threads talking about the time complexity to be $O(n!)$ but I cannot figure out how we get it. Here is the progress I have so far:

$$
\begin{align}
T(n) & = n T(n-1) + n^2\\
& = n(n-1)T(n-2) + n(n-1)^2 + n^2\\
& \vdots\\
& = n! + n! + n(n-1) \dots 2^2 + n(n-1) \dots 4*3^2 + \dots + n(n-1)^2 + n^2
\end{align}
$$

RHS and LHS divided by $n!$

$$
    \frac{T(n)}{n!} = 2 + \frac{2}{1!} + \frac{3}{2!} + \dots + \frac{n-2}{(n-3)!} + \frac{n-1}{(n-2)!} + \frac{n}{(n-1)!}
$$

From comments in GeeksForGeeks the RHS converges to a constant. Can anyone please explain why the RHS converges to a constant?

We can compute the limit explicitly:
$$
1 + \sum_{n=0}^\infty \frac{n+1}{n!} = 1 + \sum_{n=0}^\infty \frac{1}{n!} + \sum_{n=1}^\infty \frac{1}{(n-1)!} = 2e + 1.
$$


Is it undecidable if the language of a given Turing Machine is the set of composite numbers? I am aware that the following problems are undecidable and tried to reduce the given problem to one of the following but with no success:

Halting problem
Blank Tape Halting problem
State-Entry problem
If a TM accepts nothing
If a TM accepts everything

I am looking for hints :)

Do I have to make multiple reductions?

Do I have to make a contradictory argument like we do for the Halting Problem?

Hint 1: Do you know Rice's theorem? It's the go-to result for any version of "Prove it's undecidable whether $L(M) =\,$ something."

Hint 2: You can reduce from "Does this TM accept everything?" You're given a Turing machine $M$ and you want to produce a new machine $T$ such that $T$ accepts the set of composites iff $L(M)=\Sigma^*$. Have $T$ reject its input if it's prime.  If the input is composite, use its factors to decide what input you'll feed to $M$. You need to do this in a way that every possible input to $M$ corresponds to some combination of factors of $T$'s input.

Hint 2.5: Alternatively, go from "Does this TM accept nothing?" Similar idea but now $T$ will accept if its input is composite and you'll use prime inputs to $T$ to code inputs to $M$. Actually, this one might be slightly easier to see.


Definition of Turing machines and rejection states In some definitions of Turing machine, there is only a set of accepting states and no mention of a set of rejecting states.

But it seems to me that the definition that includes only a set of accepting states and that includes also a set of rejecting states will differ.

How can they actually be shown to be equivalent? Or is it not the case?

A deterministic Turing machine accepts if, and only if, it terminates in an accepting state. Any state that is not accepting is rejecting by default.  There are various equivalent ways of defining Turing machines: for example, instead of having a HALT instruction and accepting and rejecting states, you could have explicit ACCEPT and REJECT instructions.


Paging only for user code. What about kernel code? Why is paging done only for user code (user space)? I know that the basic intuition behind paging is for managing larger logical address space in smaller physical main memory space. Won't the kernel size also be large? If the kernel code is large enough and the RAM size is small, then how is it managed? Please clarify.

Other than the fact that kernels tend to be small, as Yuval points out, you should also consider that they are often not relocatable code (in fact, address binding for kernels is done at compile-time) and so the memory they are allocated could not be moved or swapped-out in any case, not only for paging.  Obviously there are also performance-related concerns, and one should consider handling exceptional cases too, like the code responsible for paging being swapped out.
Usually, memory limitations in operating systems are handled in different ways other than paging. For monolithic kernels, this means offering a loadable module system, while for microkernels the problem might not even apply, since their footprint on main memory is usually much lower than monolithic kernels (system services in microkernels are implemented as user-level processes).

Last but not least, enabling paging on kernel memory would defy one of its main definitions, being "[that] part of the operating system that is always resident in memory"1 ;-).


Floyd's Cycle Detection Algorithm Proof In Laymen I came across the algorithm question of detecting a cycle in a linked list, but the solution has to be constant space O(1).
I have looked through various proofs proving that:

If there is a cycle, at some point the tortoise and the hare will meet. I understand that at some point, both will be within the cycle, but how do we know that they will eventually meet?
The time complexity will equal O(N), where N = # of nodes.

I do not care about the case where we want to find the START of the cycle, only about proving that if there is a cycle, then the two pointers will meet at a point within the cycle, and that the time complexity is O(N).
None of these proofs make intuitive, logical sense to me.
Can someone PLEASE explain the two bullet points above in an intuitive manner?
If there is math in the proof, it would be great if you could explain all parts of the proof that would not make logical sense to someone without a CS degree.  Thanks!

The easiest way to understand this is really to draw it out and move your fingers on a graph, so I recommend literally pulling out a piece of paper to follow along.
Picture the part before the cycle as a line, and the cycle is a circle. So we have a straight line of arrows pointing into a circle of arrows. The length of the line is X steps, and the length of the circle is Y steps.
After X steps, the tortoise has gotten into the cycle, and the hare is further ahead, so it definitely is in the cycle too.
To understand why the tortoise and hare meet after they get into the cycle, think about the distance between the two in the circle. Assume the hare is BEHIND the tortoise--it's a circle, so while the hare is ahead, it's also fine to think of it as behind. It's at most Y steps behind in the circle, because the circle is only size Y.
At each step, the hare moves two steps, and the tortoise only moves one step, so the hare "catches up" one step. Eventually it will catch up to the tortoise. It catches up in the number of steps the hare started behind the tortoise, again at most Y steps.
So it does catch up, and it catches up in at most X + Y steps.


How does this recursive algorithm work? One question from the Grokking Algorithms book:

Implement a max([]int) function, returning the biggest element in the array.

Here's my solution in Golang (adapted from the Python solution in the book):

func maxNumber(arr []int) (r int) {
    // base case
    if len(arr) == 2 {
        if arr[0] > arr[1] {
            return arr[0]
        } else {
            return arr[1]
        }
    }

    // recursive case
    subMax := maxNumber(arr[1:])

    if arr[0] > subMax {
        fmt.Println("arr[0] > subMax")
        return arr[0]
    } else {
        fmt.Println("arr[0] < subMax")
        return subMax
    }
}

It works, but I can wrap my head around it. How is the third block called if every time maxNumber(arr[1:]) is called it executes the function again, passing the array with one last element? If so, at some point in time it will hit the first block (base case) and return or the first element or the second.

I know the function works, but I'm missing the how.

Could someone help me around, explain like I'm 5 styles haha

Thanks!

The base case works because, if the array contains only 2 elements, it compares them and return the biggest.
Starting from this assumption, the recursive call to the function maxNumber compare the maxnumber of the precedent call to the next element in the array.
when the list has been read all the way to the end, the algorithm will return the max number of the whole list.


Can every state in a DFA be an accepting state? I know that we can have 0 accepting states in a DFA, it would just recognize the empty language. What about the case of all states being accepting? Would that mean it would recognize all of the strings in the DFA's particular alphabet?

Thanks

Yes, every state can be accepting.  Assuming the transition function is total (complete), so every state has a transition out on every possible letter in the alphabet, then yes, this would recognize all strings in the DFA's alphabet: the DFA would recognize $\Sigma^*$.

If the transition function is not complete -- in other words, if there is some state $q$ and some letter $a$ where there is no transition out of $q$ on letter $a$ -- then the DFA doesn't necessarily recognize all of $\Sigma^*$.

See In a DFA, does every state have a transition on every symbol of the alphabet? for more on that distinction.  To avoid confusion, I generally recommend sticking to DFAs whose transition function is complete (total), at least until you understand the concepts well.


Can anyone give an example for worst case of quick sort if we employ median of three pivot selection? If we employ quicksort by selecting the pivot as the median of three elements viz., the first element, the middle element and the last element, then when will the algorithm hit worst case? and also can anyone give an example including integers?

Thanks.

Note: I have searched online for quicksort's worst case, but all of them are referring to quicksort wherein the pivot is either the first element or the last element, but what I want is completely different.

If we employ quicksort by selecting the pivot as the median of three elements viz., the first element, the middle element and the last element, then when will the algorithm hit worst case? and also can anyone give an example including integers?

The worst case is when the selected pivot reduces the problem size by the smallest possible amount, i.e. provides as lopsided a partition as is possible.  For the median of three elements, that cannot be either the largest or smallest valued element (assuming distinct values), as the definition of median ensures that in median of 3, there is one larger and one smaller element than the median.

For the rather poor but all too common case of using the median of the first, middle, and last elements (with distinct valued input), that worst case occurs when the median of the three is the second-smallest or second-largest valued element (because the largest or smallest is one of the other two of those three).  That can occur when an in-order sequence of elements is rotated by just one position.  Here are two examples:

1 2 3 4 5 6 7 8 0 (median of 1,5,0 is 1)

8 0 1 2 3 4 5 6 7 (median of 8,3,7 is 7)

When median of first, middle, last pivot selection is combined with most commonly used partitioning methods, the result is disastrous; each partition peels off two elements (the pivot and one extreme value) and leaves another rotated sequence remaining.  The combination of first, middle, last pivot selection and a partitioning method which swaps the pivot to the first (or last) array position (rather common) is worse; it also generates rotated sequences when the input is reverse-sorted (e.g. 8 7 6 5 4 3 2 1 0).

See https://github.com/brucelilly/quickselect/blob/master/lib/libmedian/doc/pub/generic/paper.pdf and/or the video at https://www.youtube.com/watch?v=iWmAf4RMMiM for details and examples of some widely-used implementations that exhibit this behavior.

When input values are not distinct, another bad case for median of first, middle, and last elements is "organ-pipe" (bitonic) input, such as

0 1 2 3 4 3 2 1 0 (median of 0,4,0 is 0)

In the case of organ-pipe input, use of first, middle, and last elements is the worst possible choice of three elements for pivot selection!


$m/p$-equivalence holds after union with an arbitrary finite language Problem 1: Let $A,B$ be languages over some alphabet $\Sigma$, if $A \equiv_m B$, then for every finite language $C$, $A \cup C \equiv_m B \cup C$.

Problem 2: Problem 1 but using polynomial time reductions.

Note: $A \equiv_m B$ means $A \leq_m B$ and $B \leq_m A$, same for $\equiv_p$. Every finite language can be decided in polynomial time.

By hypothesis, we have reductions $f$ from $A$ to $B$ and $g$ from $B$ to $A$, the obvious choice for a reduction from $A \cup C$ to $B \cup C$ would be: $$h(w) := \begin{cases} w &\text{ if } w \in C\\ f(w) &\text{ if } w \notin C \end{cases},$$ with this definition it follows that if $w \in A \cup B \Rightarrow h(w) \in B \cup C$, however, if $w \notin A \cup C$ I can't say that $h(w) = f(w)\notin B \cup C$, at most, $f(w) \notin B$.

My idea was to redefine $h$ like this:$$h(w) := \begin{cases} w &\text{if } w \in C\\ f(w) &\text{if } w \notin C \land f(w) \notin C\\ X(w) &\text{if } w \notin C \land f(w) \in C \end{cases},$$ where $X(w)$ must lie in $B \cup C$ when $w \in A \backslash C$, and outside $B \cup C$ when $w \notin A \cup C$. The problem now is how to define the mapping $X$, I can't ask whether $w \in A$ or not because $A$ may not be decidable (or decidable in polynomial time for problem 2) and here I'm stuck.

Can't see how to define $X$ without making questions about being in $A$ or $B$, those questions should be avoided because a $TM$ computing $h$ might loop forever. I'm starting to think that the problem needs some hypothesis like $A,B$ being decidable/decidable in polynomial time languages (the problem seems sound to me though, I can't find counterexamples to it).

Hint: You could prove that $A\cup C\equiv_p A$. For both directions, try functions in the form
$$h(w)=\left\{\begin{array}{ll}w & w\notin C\\ \textrm{something hardwired} & w\in C.\end{array}\right.$$


How this language belong to R? Consider the following language $$L= \{ \langle M\rangle | \text{ $M$ is a TM, and $L(M)\in coRE$}  \}$$
I don't understand why the language $L$ is in $R$, intuitively, I think this is not true. Indeed, suppose we have a TM $M$, now for input $x$ such that $x\notin L(M)$, it seems that we cannot decide whether $x\notin L(M)$ as $M$ may not halt on $x$.

The language $L$ is not decidable, this is an immediate consequence of Rice's theorem (you can instead try and prove that $L$ is not decidable directly using reductions). To begin with, there are two machines $M_1$ and $M_2$ such that $L(M_1)\in coRE$ and $L(M_2)\notin coRE$. For example, $M_1$ can be a machine that accepts all inputs, and $M_2$ can be a machine that recognizes the language $Halt_{TM} = \{\langle M, w\rangle: \text{ $M$ halts on $w$ }  \}$ which is known to be in $RE\setminus coRE$. So the property $P = \{ M: \text{$M$ is a TM, and $L(M)\in coRE$}\}$ is a non-trivial property. Also, for every two machines $M_1$ and $M_2$ with $L(M_1) = L(M_2)$, it holds that $L(M_1)\in coRE$ iff $L(M_2)\in coRE$. Thus, either both $M_1$ and $M_2$ are in $P$, or both are not in $P$. Hence, the property $P$ is also semantic, and so by Rice's theorem $L$ is not decidable.
Maybe you saw the claim suggesting that $L' = \{ \langle M\rangle:  \text{ $M$ is a TM, and $L(M) \in RE$}  \}$ is decidable, and this follows simply from the fact that $L'$ is the language of all legal encodings of TMs.


Problem similar to set packing Call a family of sets $\mathcal{F} = \{S_1, \dotsc, S_k\}$ "diverse" if each set $S_i \in \mathcal{F}$ has at least one unique element.  What are possible approaches for finding the largest diverse set $S$ in a family of sets $\mathcal{F}$?

One approach is to solve a modified set packing problem.  Suppose $\mathcal{F}=\{S_1,\dotsc,S_k\}$. Let $K$ be a subset of elements, $K \subset \bigcup S_i$, and let $\mathcal{F}_{-K}=\{S_1 \setminus K,\dotsc, S_k \setminus K\}$.  Then the maximal diverse set $S$ corresponds to the largest maximal set packing obtained from $\mathcal{F}_{-L}$ where $L$ is the set of all non-unique elements in $\mathcal{F}$.

But, what's a good heuristic for choosing $K$?  Or are there better approaches altogether?

The problem is NP-complete. This rules out an exact algorithm that works in all circumstances, but does not rule out heuristic algorithms that work well in practice, or approximations algorithm with provable approximation guarantees.

The reduction is from 3SAT. Given a 3SAT instance $\phi$ with variables $x_1,\ldots,x_n$ and clauses $\phi_1,\ldots,\phi_m$, construct the following set system. For each variable $x_i$ there are two sets $A_{i,0}$ and $A_{i,1}$ and $N=n+1$ sets $B_{i,t} = \{\beta_{i,t,0},\beta_{i,t,1}\}$, and for each clause $\phi_j$ there is a set $C_j = \{\gamma_{j,1},\gamma_{j,2},\gamma_{j,3}\}$. The set $A_{i,b}$ consists of the following elements:

The $N+1$ elements $\alpha_i,\beta_{i,1,b},\ldots,\beta_{i,N,b}$.
For each clause $\phi_j$ that contains $x_i$ as the $k$th literal and is not satisfied by $x_i = b$, the element $\gamma_{j,k}$.

One can find $n(N+1)+m$ diverse sets if and only if $\phi$ is satisfiable. Indeed, given a satisfying assignment $\vec{x}$, the family $\{ A_i^{x_i} : i \in [n] \} \cup \{ B_{i,t} : i \in [n], t \in [N] \} \cup \{ C_j : j \in [m] \}$ is diverse: $\alpha_i$ belongs only to $A_i^{x_i}$, $\beta_{i,t,1-x_i}$ belongs only to $B_{i,t}$, and if the $k$th literal of $\phi_j$ is satisfied then $\gamma_{j,k}$ belongs only to $C_j$.

For the converse, suppose $\mathcal{S} = \mathcal{A} \cup \mathcal{B} \cup \mathcal{C}$ is a diverse family of size at least $n(N+1)+m$, partitioned according to the type of the set. If $\mathcal{A}$ contains both $A_{i,0}$ and $A_{i,1}$ for some $i$, then $B_{i,1},\ldots,B_{i,N} \notin \mathcal{B}$. Hence $|\mathcal{S}| \leq 2n + (n-1)N + m < n(N+1) + m$, which is impossible. Therefore $\mathcal{B}$ and $\mathcal{C}$ must contain all sets of the corresponding type, and $\mathcal{A}$ must contain $n$ sets, which together encode an assignment $\vec{x}$. Since $C_j \in \mathcal{S}$ is diverse, by construction the assignment $\vec{x}$ satisfies clause $\phi_j$, hence $\phi$ is satisfiable.


Algorithm for solving incremental max flow problem I am working on a project where I need to be able to compute the maximum flow between two nodes in a graph after one of the edge weights has been incremented or decremented by 1. The graph is directed and edge weights are all integers. I can find the maximum flow the first time, by Ford-Fulkerson's algorithm or some variant, but at each step thereafter it would be great if I could use a different (faster) algorithm to find the max flow. At each step, only one of the edge weights is changed, and it is only changed by a value of +1 or -1. What sort of algorithm could do this incremental update for me? It needs to be faster than recomputing the max flow from scratch. It could also be two separate algorithms (but similar I would hope): one for the incrementing case and one for the decrementing case. Thanks in advance for the help!

You can do it in $\small \mathcal{O}(m + n)$ time where $\small m$ and $\small n$ are the # of edges and vertices respectively. Let the edge to be updated be $\small e = (u, v)$.

If you increment the capacity of $\small e$ by $\small 1$, the maximum flow increments by at most $\small 1$. Hence, starting with the current max flow $\small f$, you only need to find an augmenting path in the residual graph one more time, which costs $\small \mathcal{O}(m + n)$ time. Recall that each augmentation increments the flow value by at least $\small 1$. Therefore, it is guaranteed after the augmentation (if any), the flow attained is maximum.
If you decrement the capacity of $\small e$ by $\small 1$, the maximum flow decrements by at most $\small 1$. If the new capacity (after decreased by $\small 1$) $\small c(e) \geq f(e)$, where $\small f(e)$ is the current flow value of $\small e$, then nothing need to be conducted. Otherwise, we have to decrease the flow value of $\small e$. Let $\small s \rightarrow u$ be a simple path from $\small s$ to $\small u$, in which all edges have positive flow values and similarly define $\small v \rightarrow t$. We then decrease the flow values by $\small 1$ for all edges in the path $\small s \rightarrow u \rightarrow v \rightarrow t$. Finally, we again search for an augmenting path in the resultant residual graph.


Computability of a function and decidability Let $A$ and $B$ be finite alphabets and let $\#$ be a symbol outside both $A$ and $B$. Let $f$ be a total function from $A^∗$ to $B^∗$. We say $f$ is computable if there exists a Turing machine $M$ which given an input $x ∈ A^∗$, always halts with $f(x)$ on its tape.

Let $L_f$ denote the language $\{x\#f(x)∣x∈A^*\}$.

This is a part of the question and the answer says that if $L_f$ is recursive then $f$ is computable. If $L_f$ is recursive then we can accept all the string in the language but we have to reject the strings not in the language. A function is said to be computable when it has a halting Turing machine which computes the value for $f(x)$ for every $x$ in the domain and HALTS.
Then what about the values outside the domain?

Since $L_f = \{x\#f(x);x ∈ A^*\}$, $f$ must be total, otherwise $L_f$ isn't defined at all. So, we suppose that $f$ is total.

Let's prove : $L_f$ is recursively enumerable $=> f$ is computable. We will use a technic called dovetailing. For the need of the proof, suppose that $c_i$ denotes the $i^{th}$ element of $A^*$ (it's a function, we write $c_i$ instead of $c(i)$ for clarity). We use the lexicographic order to define the $i^{th}$ element of $A^*$.

$L_f$ is recursively enumerable, there exists so a Turing machine $M_{L_f}$ that, for each input $x ∈ (A \cup\{\#\}\cup B)^*$, halts if and only if $x ∈ L_f$.
Let's try to define a Turing machine $M$ that computes $f(x)$ foreach $x∈A^*$.
We will just describe this machine, we won't give a formal definition. Let $x$ be the input of $M$, the machine will proceed by this way :

Execute one step of $M_{L_f}$ with input : $x\#c_0$. If $M_{L_f}$ halts, then $f(x) = c_0$. Else, continue.
Execute two steps of $M_{L_f}$ on both inputs : $x\#c_0$ and $x\#c_1$ sequentially. If $M_{L_f}$ halts on one of them, let's call it $x\#c_i$, then $f(x) = c_i$. Else, continue.
Go by this way, at step $i$, $M$ executes $i$ steps of $M_{L_f}$ with inputs : $x\#c_0, x\#c_1 ... x\#c_i$. If $M_{L_f}$ halts on one of them, suppose it's $x\#c_k$, then $f(x) = c_k$.

Since $f$ is total, $x\#f(x)$ exists for each $x$. In addition, $L_f$ is recursively enumerable, so, when $M$ arrives to $x\#f(x)$, $M_{L_f}$ will halt after $k$ steps because $x\#f(x) ∈ L_f$. $M$ then computes $f(x)$ for every $x∈A^*$.

I hope i have explain it well.

To complete the proof, $c_i$ must be proved to be computable, it's somewhat easy to do.


Is there anything that MUST be done on a multi-core CPU? When considering how multi-thread-friendly our program must be, my team puzzled about whether there's anything that absolutely cannot be done on a single-core CPU. I posited that graphics processing requires massively parallel processing, but they argue that things like DOOM were done on single-core CPUs without GPUs.

Is there anything that must be done on a multi-core processor?

Assume there is infinite time for both development and running.

The question is: under what constraints?

There are certainly problems where, if we ask the question "can we solve this problem on hardware X in the given amount of time", the answer will be no.

But this is not a "future-proof" answer: things which in the past could not be done fast enough in a single core probably can be now, and we can't predict what future hardware will be capable of.

In terms of computability, we know that a single-tape Turing Machine is capable of computing all the same functions as a single or multi-core computer, so, runtime aside, there are no problems that a multi-core computer can solve that a single-core can't.

In terms of something like graphics, literally everything that is on the GPU could be done on the CPU... if you are willing to wait long enough.


Extreme instancing for computer graphics Instancing in GPU's, from my little knowledge, simply draw the same object at multiple locations. Each "instance" is just a copy of the same model at a different location. Any local effects, such as animation, would effect all instances. The performance improvement comes from gpu being able to deal with virtually all the instance aspects.

One could create several variations of the same object and instance each one. This would be very useful to create variations(say for leaves on a tree) but, while allowing for rather large number of instances(basically limited by the gpu) and variation increases the the cpu's involvement by the number of variations(from the previous case).

If we could send the changes to the gpu then we could get back to the first case(or very close) and achieve very high levels of variations with limited cpu involvement.

For example,

Suppose we wanted to populate a jungle with a lot of animals. Each animal object will have many instances(many tigers and birds but all using the same template). If we had one long animation containing all the possible animations of each animal and send it to the gpu we then would simply have to tell the gpu which part of the animation each instance was in(and we could have a default animation to limit cpu-gpu communications).

This would effectively let us control all the instances with just a animation position indicator(and possible a few other parameters such as scale) and coordinate position. The gpu would take care of all the rest.

The problem, of course, is that that each instance would not have any logic associated with it. This is not a big deal though for most computer objects. The cpu generally has to take care of the logic anyways but in this case, instead to tell send all that information to the gpu we can just send it a few bytes for each instance.

For example, suppose in our jungle we have a few cheetahs and on our cpu we are keeping track of which ones are doing what and simply sending which animation we want them to use to the cpu(instead of sending all the vertex data and/or telling it how to transform them).

This seems like it would be much faster and essentially just boils down to moving some of the code from the cpu to the gpu(which as been what is happening all along).

Using such a method is not ideal because of the lack of physical modeling per instance but for far enough away objects were intersecting objects won't be seen it won't matter.

We could have thousands of birds, for example, all seemingly moving individually but generated from one model with a few animations.... the cpu doing very little but sending which animations to use to the gpu. (and of course deciding what each bird should do)

Anyways, this is a thought but it seems to me the goal of future gpu's is to deal with all the visual aspects while the cpu deals with the logic(and the communication between the too is to be minimized).

Is my interpretation of instancing with animation's flawed or could it be implemented and be useful to 3d games?

Yes, you are correct. What you suggest is a viable approach in 3D games. Popular game engines already do this, and have been doing this for some time. If you choose to do this through the vertex shader, you can improve performance in many situations.

For more information about animation:
How animation works in realtime graphics


Restricted version of the Clique problem? Consider the following version of the Clique problem where the input is of size $n$ and we're asked to find a clique of size $k$. The restriction is that the decision procedure cannot change the input graph into any other representation and cannot use any other representation to compute its answer, other than $\log(n^k)$ extra bits beyond the input graph. The extra bits can be used for example in the brute-force algorithm to keep track of the status of the exhaustive search for a clique, but the decision procedure is welcome to use them in any other way that still decides the problem.

Is anything known at this point about the complexity of this? Has any work been done on other restrictions of Clique, and if so, could you direct me to such work?

This sounds like you are asking whether or not the NP-complete clique problem can be solved in logarithmic space. Using Turing machines, one tape is read only and stores the input graph. The other tape is bounded so that there's $c \lg n$ space available for some constant $c$. The class of problems solvable in this model is known as $L$, deterministic logarithmic space. (See wikipedia or in the complexity zoo)

It is unknown whether $\mathrm{CLIQUE} \in L$, but a positive answer would imply that $P = NP$, so you (almost surely?) won't find an answer. $L \subseteq P \subseteq NP$ and $\mathrm{CLIQUE} \in L$ implies $\mathrm{CLIQUE} \in P$, which implies $P = NP$.

Edit in case I misinterpreted the problem:

If you intend that the $k$ in $ \lg n^k = k \lg n $ is the same as the clique size $k$ (i.e. the amount of memory scales with input $k$), then there's a simple brute force algorithm: you can loop through all possible sets of $k$ nodes and check if they form a $k$-clique. A starting point for searching for better solutions might be the references of [1].

[1] Virginia Vassilevska, "Efficient algorithms for clique problems" pdf link


Early termination of A* with weak heuristic if solution is known I have a large graph G and a pair of nodes s,t.  I want to use the A* algorithm to find the shortest path from s to t, and I have a heuristic that is consistent.

Suppose I already know of a path whose length is guaranteed to be at most 1.1 times as long as the shortest path.  Does this help A* find the shortest path faster?  If so, how and why?  Can knowledge of this path be used to improve the running time of A*, reduce the number of nodes, or make the heuristic more accurate?

One improvement I can see is to remove the all the nodes in the open list which exceed the current solution. But if the heuristic is weak, this wouldn't help in reducing the number of nodes to be explored in the open list. So, in what other ways one can use the knowledge of known path in hand to help A* terminate itself earlier than without the knowledge of known complete path.

In order to prove that the solution is optimal, with a consistent heuristic A* needs to expand all states with f < f* (the perfect solution cost) and it also may expand some states with f = f* so it seems hard that knowing an upper bound on the number of expansions can help to reduce the number of node expansions without modifying the heuristic.

A potential way of helping A* in this context may be that of heuristic selection. That is, in cases where more than one heuristic is available, meta-reason about what subset of heuristics should be used [1,2].

In this scenario it could be possible to use the sub-optimal path to select which ones to use (e.g., it may be worth it to compute more expensive heuristics because they have greater chances of pruning the node). However, this is an open problem and I'm not aware of any work on that direction.

[1] David Tolpin, Tal Beja, Solomon Eyal Shimony, Ariel Felner, Erez Karpas:
Toward Rational Deployment of Multiple Heuristics in A. IJCAI 2013: 674-680

[2] Levi H. S. Lelis, Santiago Franco, Marvin Abisrror, Mike Barley, Sandra Zilles, Robert C. Holte:
Heuristic Subset Selection in Classical Planning. IJCAI 2016: 3185-3191


What is the difference between these terms? Between my textbook and various online sources (namely wikipedia), I'm very confused... can somebody clear up which words are synonymous and which mean different things?

Many-to-one reduction
Mapping reduction
Turing reduction
Cook reduction
Karp reduction
Polynomial-time many-to-one reduction
Polynomial time turing reduction

I've also seen others, but I can't recall them currently.

Let $A,B\subseteq \Sigma^*$ be languages.

Many-to-one: A (computable) function $f:\Sigma^*\to \Sigma^*$  such that $\forall x\in \Sigma^*$, $x\in A\iff f(x)\in B$.
The names "Mapping reduction" and "Karp reductions", to my knowledge, refer to "Many to one".
The "Many to one" means that $f$ may not be injective.

Turing reduction: we say that $A\le_T B$ if, given an oracle to the language $B$, we can use it to solve $A$. The word "solve" here should be in the context of a specific complexity/computability class.

Turing reductions are weaker than many-to-one reductions. The latter can be viewed as Turing reductions where we are only allowed to call the oracle once - at the very end of the run.

polynomial time many-to-one reductions - simply adding a constraint that the reduction $f$ is computable in polynomial time.

polynomial time Turing reduction (= Cook reduction) - add the constraint that the oracle machine runs in polynomial time, counting each oracle call as $O(1)$.


Resources for implementing dependent type theory I want to implement Martin Löf's intuitionistic type theory in a functional language such as Haskell, preferably also implementing a lexer/parser for the language. How should I start approaching it? Are there any good papers/blog posts/github repo examples that might be useful? Thanks!

This paper is my go-to for implementing dependent types. It starts from the basics, uses bidirectional types, and has accompanying code in Haskell.
If you're at all interested in type inference, this paper is great, and also has accompanying Haskell code.
David Christiansen has a tutorial on dependent type checking with bidirectional types, with a Haskell and Racket. More generally, I've heard great things about his book The Little Typer, though I haven't had a chance to read it myself.
I've heard great things about  smaltt  by András Kovács, particularly for it being an efficient implementation.


Why do TPTP Performance plots look like this? CASC is the premier Automated Theorem Prover competition performed annually at the Conference on Automated Deduction (CADE). The 2017 event has finished on the 9th of August this year.

During this conference provers are faced with a set of problems and a time limit of 5 minutes (300 seconds) per problem.
When the competition is over, the timings for each problem are taken to produce performance plots.

Here we see the results from the general first order formulas (FOF) division. 11 ATP systems participated, Vampire 4.2 was the winner in this division having solved over 450 problems from the set.

It  is clear from this plot that the timings for each prover were independently sorted in increasing order and plotted over the same axes.

What is puzzling is the shape of the graph: for most provers most of the problems were really easy (solved within 50 seconds) and only a small proportion of problems were difficult yet solvable within the time limit (i.e. about 5% for Vampire 4.2 and less than 10% for Vampire 4.0, the 2016 winner). On the remaining problems (there were 500 problems altogether) the prover failed. Is there an intuitively simple explanation of why the difficulty distribution is so skewed towards "easy" problems not for one but for all provers?

I can speculate/hypothesize.  Each solver has many heuristics and proof tactics.  Imagine that corresponding to each heuristic is a class of instances that are easy to solve if you use that heuristic, but hard if you don't (e.g., if you don't have a heuristic for it and you fall back to the generic methods, maybe you're effectively exploring the entire exponentially large space of possible solutions to try to find one that works).  An example would be 2SAT; if you use the right algorithm, it can be solved in linear time, but if you blindly search, that will take exponential time.

So, in this model, if an instance is handled by one of the prover's heuristics, it is solved very rapidly; otherwise you fall back to some generic method that may take exponential time.  This would lead to a kind of "very fast or very slow" dichotomy.  And the set of instances that a prover is fast on may be different for each prover, because prover uses a different set of heuristics.  In other words, this hypothesis would explain the observed behavior.

I have no data and no hard evidence, so this is merely speculation.  It could be entirely wrong.


Why are HMMs appropriate for speech recognition when the problem doesn't seem to satisfy the Markov property I'm learning about HMMs and their applications and trying to understand their usages. My knowledge is a bit spotty, so please correct any incorrect assumptions I'm making. The specific example I'm wondering about is for using HMMs for speech detection, which is a common example in literature.

The basic method seems to be to treat the incoming sounds (after processing) as observations, where the actual words being spoken are the hidden states of the process. It seems obvious the hidden variables here are not independent, but I do not understand how they satisfy the Markov property. I would imagine that the probability of the Nth word is not just dependent on the N-1 word, but on many preceding words before that.

Is this simply ignored  as a simplifying assumptions because HMMs are very good at correctly modeling speech detection problems, or am I not clearly understanding what the states and hidden variables in the process are? The same problem would appear to apply to a great deal of applications in which HMMs are quite popular, POS tagging, and so forth.

On that subject I recommend you to read a very good paper by James Baker and others who were actually responsible for introduction of HMM in speech:

A Historical Perspective of Speech Recognition
http://cacm.acm.org/magazines/2014/1/170863-a-historical-perspective-of-speech-recognition/abstract

  Using Markov models to represent language knowledge was controversial.
  Linguists knew no natural language could be represented even by
  context-free grammar, much less by a finite state grammar. Similarly,
  artificial intelligence experts were more doubtful that a model as
  simple as a Markov process would be useful for representing the
  higher-level knowledge sources recommended in the Newell report.
  However, there is a fundamental difference between assuming that lan-
  guage itself is a Markov process and modeling language as a
  probabilistic function of a hidden Markov process. The latter model is
  an approximation method that does not make an assumption about
  language, but rather provides a prescription to the designer in
  choosing what to represent in the hidden process. The definitive
  property of a Markov process is that, given the current state,
  probabilities of future events will be independent of any additional
  information about the past history of the process. This property
  means if there is any information about the past history of the ob-
  served process (such as the observed words and sub-word units), then
  the designer should encode that information with distinct states in
  the hidden process. It turned out that each of the levels of the
  Newell hierarchy could be represented as a probabilistic function of
  a hidden Markov process to a reasonable level of approximation. For
  today’s state-of-the-art language modeling, most systems still use
  the statistical N-gram language models and the variants, trained with
  the basic counting or EM-style techniques. These models have proved
  remarkably powerful and resilient. However, the N-gram is a highly
  simplistic model for realistic human language. In a similar manner
  with deep learning for significantly improving acoustic modeling
  quality, recurrent neural networks have also significantly
  improved the N-gram language model. It is worth noting that
  nothing beats a massive text corpora matching the application domain
  for most real speech applications.

Overall, the Markov model is pretty generic model for decoding black-box channel with very relaxed assumption on the transmission thus it is a perfect fit for the speech recognition, however, the question remains what to encode as a state indeed. It is clear that states should be more complex objects than what we assume now (just few preceding words). It is ongoing research to reveal true nature of such structure.


How to quickly find a few bisimulations on a given labelled digraph? We are given a labelled directed graph, where both vertices (or states) and edges (or transitions) have labels. Informally, two states are bisimilar when they have the same label and they can simulate each other's transitions. On the states the two states evolve to, the same again is true.

More formally, a binary relation $R \subseteq S \times S$ is a simulation iff $\forall (p,q) \in R$

$p$ and $q$ have the same label, and
if $p \overset{a}{\longrightarrow} p'$ then $\exists q', q \overset{a}{\longrightarrow} q'$ and $(p',q') \in R$.

A relation $R$ is a bisimulation iff $R$ and $R^{-1}$ are simulations. The largest bisimulation on the given system is called the bisimilarity relation.

There are algorithms for finding the bisimilarity relation, that run in $O(m \log n)$ time and $O(m+n)$ space, where $n$ is the number of states and $m$ the number of transitions. An example is the Paige-Tarjan RCP algorithm from 1987.

However, consider a simpler problem. Instead of finding all the bisimulations, I just want to find a few of them. Can it be done faster than in loglinear time? If so, how? For example, let's say one is given two states $p,q \in S$ such that they have the same label and they can make the same transitions. What I find problematic is to check that the states they lead to are once again bisimulations. In other words, one could also ask if there is a quick way to decide if two given states are a bisimulation.

You can always return the bisimulation $∅$ in constant time.

You are right about the fact that in order to return $R$, you will have at least some sanity checks.

For example you could think that returning all bisimulations of the form $\{(p,q)\}$ when $p$ and $q$ have the same label and such that $p\not→$ and $q\not→$ is easy, but not that much: you need to proceed through $O(m+n)$ time and $O(n)$ space! (Or $O(mn^2)$ time and $O(1)$ space (not counting the output)). Checking that a small relation is a bisimulation is not a lot easier than finding the relation $\sim$.

The computation of $\sim$ uses clever properties specific to $\sim$ and fusing states tricks. These techniques would not be useful for several relations and doing better than $O(m\log n)$ (not loglinear) is hard. Also, computing "a few" bisimulation is of arguable interest.

Another thing: deciding if $p\sim q$ implies computing the relation $\sim$ on the union of the directed graphs $G_p=\{x ∣ p \stackrel{a_1\dots a_n}{\longrightarrow}x\}$ and $G_q=\{x ∣ q \stackrel{b_1\dots b_m}{\longrightarrow}x\}$ which can be a significant part of the graph. If however you know have information like the size of $G_p$ and $G_q$ then you can compute $\sim$ on smaller graphs. Keep in mind that algorithms with Tarjan in their name tend to have very tight bounds. This is not an exception.


Is there any field that studies the equivalent of cellular automata, but for arbitrary graphs rather than 1D cells? A cellular automaton consists of a sequence of cells, each with a state, and a globally symmetric transition rule based on the neighbors of a cell. They can be interpreted as graphs where each cell is a node, and each node has an edge to a neighbor.

Is there any field studying that system, but generalized to arbitrary graphs - i.e., allowing cells to have, for example, 3 or more neighbors?

Graph dynamical systems is a general term for systems where each vertex of a graph carries a state, and the system evolves in time so that the next state of a vertex only depends on the states in its neighborhood (possibly in a nondeterministic way). Boolean networks are a special case where the graph is finite and each state is either $0$ or $1$. Boolean networks are used e.g. as models of gene expression in cells, and a lot of practical and theoretical research exists on them.


Difference between row-polymorpism and bounded polymorpishm? I recently came across this blog post by Brian McKenna explaining row polymorphism. This seemed like a wonderful idea to me, but then I realized it smells an awful lot like bounded parametric polymorphism:

With row-polymorphism:

sum: {x: int, y: int | rho} -> int
function sum r = r.x + r.y

With bounded parametric polymorphism:

sum: forall a <: {x: int, y: int}. a -> int
function sum r = r.x + r.y

Can someone clarify the differences to polymorphism between these two approaches?

So, there are a few differences:

In row polymorphism, you've bound $\rho$ to a name, so you can use it elsewhere. For example, forall rho . rho -> {x : int | rho} is expressible with row polymorphism, but not purely using bounded polymorphism. Likewise, you can even express field deletion this way: forall rho .{x : int | rho} -> rho is a perfectly valid row-polymorphic type, but subtyping doesn't really have a way of expressing this.

Because row polymorphism lets you add and delete fields this way, usually it works with a "stack" semantics, so that old fields are shadowed when new fields of the same name are added.
Bounded subtyping uses, well, subtyping. So with row polymorphism, you can't give x : {x : int, y : int} as argument to a function of type {x : int} ->int. But most systems with bounded subtyping would have non-polymorphic subtyping too, that would allow this, since most systems have {x : int} <: {x : int, y : int}.

Bounded subtyping tends to be  bit more precise and flexible, and the "stack" semantics of row polymorphism don't arise that much. But inference is much easier for row polymorphism, and can work in the absence of any type annotations (for example, in Elm), which usually isn't the case in the presence of subtyping.