In TensorFlow tutorials, why do they use only the first term of cross-entropy as the cost function? The cross-entropy cost function is usually defined as

$$C = -\frac{1}{n} \sum_x \left[y \ln \hat{y} + (1-y ) \ln (1-\hat{y}) \right]$$

where $y$ is the expected output and $\hat{y}$ is the predicted output, for training example $x$.

But, in TensorFlow MNIST tutorial, they use

cross_entropy = tf.reduce_mean(-tf.reduce_sum(y_ * tf.log(y_conv), reduction_indices=[1]))

which, I suppose, is equivalent to

$$C = -\frac{1}{n} \sum_x y\ln\hat{y}$$

That means only the first term of the cross-entropy expression, $y\ln\hat{y}$, is being used. Why? Why isn't the second term, $(1 - y)\ln(1 - \hat{y})$, being used too?

Great question!  Actually, there's no contradiction.  The short version of the explanation is that those two equations look different because they are intended for slightly different scenarios -- but under the covers, they're actually much more similar than you might think.  Let me walk you through it, and hopefully by the end of this explanation you'll see how everything is consistent and why both equations are correct, in the particular context where they're used.

Cross-entropy loss for multi-class neural networks

When using neural networks for MNIST, we have 10 classes (one per digit).  The neural net has 10 outputs (i.e., 10 neurons at the final layer).  Call the outputs $\hat{y}_0,\hat{y}_1,\dots,\hat{y}_{9}$.  If you feed in an image $x$, the intended interpretation is that $\hat{y}_d$ is supposed to represent the neural network's estimate of the "probability" that the image is an instance of the digit $d$.

For the training set, we know what the desired output is.  Let's define $y_0,y_1,\dots,y_9$ to be the desired "probability distribution".  In particular, $y_d$ should be $1$ for the correct digit $d$ and $0$ for all other values of $d$.

With these definitions, the cross-entropy loss for a single instance $x$ is defined to be

$$C_x = - \sum_{i=0}^9 y_i \log \hat{y}_i.$$

(Notice that if the correct digit is $d$, then this value simplifies to $-\log \hat{y}_d$, since we have $y_d=1$ and $y_i=0$ for all other $i$.)

The empirical cross-entropy loss for an entire training set is the average of these values, over all of the instances in the training set:

$$C = - {1 \over n} \sum_x \sum_{i=0}^9 y_i \log \hat{y}_i.$$

That's the cross-entropy loss.  I think this is exactly what the Tensor Flow tutorial is computing.  (Side note: this is different from the equation you presented.  You were missing the inner sum over all 10 classes.  I suspect you might have misinterpreted the Tensor Flow code.  No biggy.)

You can also see how this generalizes to any number of classes: the sum over $i=0,1,\dots,9$ gets changed to a sum over all classes, however many of them there may be.

Cross-entropy loss for two-class neural networks

As a special case, suppose we have two classes.  In particular, suppose there are two classes and two outputs from the neural network (two neurons at the output layer).  Then the cross-entropy loss for a single instance (the inner sum) becomes just

$$C_x = - y_0 \log \hat{y}_0 - y_1 \log \hat{y}_1.$$

Normally we normalize $y_0,y_1$ to be a probability distribution, so $y_0+y_1=1$, and similarly for $\hat{y}_0,\hat{y}_1$.  As a result, we have $y_0 = 1-y_1$ and $\hat{y}_0 = 1-\hat{y}_1$.  So, for a two-class neural network, we have

$$C_x = - y_1 \log \hat{y}_1 - (1-y_1) \log (1-\hat{y}_1),$$

and the empirical loss for an entire training set is

$$C = - {1 \over n} \sum_x [y_1 \log \hat{y}_1 - (1-y_1) \log (1-\hat{y}_1)].$$

So far, so good.

Cross-entropy loss for two-class neural networks with a single output

Now if we have a two-class classification problem, it's not actually necessary for the network to produce two outputs.  Alternatively, we could build a network with only a single output $\hat{y}$.  We could interpret this single output value as "probability" that the input instance should be labelled as class 1.  It follows that the "probability" that the instance should be labelled as class 0 is $1-\hat{y}$.  So, if $\hat{y}>0.5$, we'll label the input as class 1; otherwise, we'll label it as class 0.  This is the architecture used in the first web page you link to.

How should we measure the cross-entropy loss for this network?  Well, just replace $\hat{y}_0,\hat{y}_1$ with $1-\hat{y},\hat{y}$ and everything goes through unchanged.

A slightly tricky thing is that we need to replace $y_0,y_1$ with something.  What should we replace it with?  I suggest we replace it with $1-y,y$, where $y$ is a value that indicates the desired output: if the correct label is class 1, then $y=1$, else $y=0$.  Notice how this all works out nicely: if the correct label is class 1, then we get the distribution $0,1$; if the correct label is class 0, we get the distribution $1,0$.

Now plugging into the equations above, we see that the cross-entropy loss for a single instance $x$ is

$$C_x = - y \log \hat{y} - (1-y) \log (1-\hat{y})$$

(since we decided that instead of $\hat{y}_1$ we now have $\hat{y}$, and similarly for $y_1,y$).

As a result, the empirical loss for an entire training set is

$$C = - {1 \over n} \sum_x [y \log \hat{y} - (1-y) \log (1-\hat{y})].$$

This exactly matches the formula found in the first link you gave.

Bottom line

See how it all lines up and is consistent?  Basically, the cross-entropy is a well-defined notion in information theory; there is only a single definition of the cross-entropy.  In information theory, the cross-entropy is defined in terms of two probability distributions.

To use this idea to construct a loss function for a neural network, we construct two probability distributions (one based on the actual outputs from the neural network, the other based on the desired outputs), and then we apply the information-theoretic definition.  The exact way of defining those two probability distributions will depend on the architecture of the neural network, and in particular, on the number of outputs from the neural network.  When you have slightly different architectures, you'll get a slightly different equation for the cross-entropy loss function.  But the underlying idea is exactly the same: we apply the same information-theoretic cross-entropy slightly differently, to distributions defined in a slightly different way, so the equations look different on the surface -- but they're actually not as different as they might seem.

I hope this helps!


Showing filling a container with rectangles is hard by reducing from SUBSET-SUM Given a set of rectangles, $D = \{ (a_1, b_1), (a_2, b_2) \dots , (a_n, b_n) \}$, where in each pair $(a_i, b_i)$, $a_i$ represents the height of the rectangle and $b_i$ the width, and given another pair $(w, h)$ representing the width and height of a container $C$, does exist a way that taking some of the squares in $D$, the whole container C is perfectly filled? Here, $a_i, b_i, w, h \in \mathbb N$.

I am trying to reduce it from Subset Sum, but can't find the way... Hope you guys can give me a hint over it!

Hint: Follow frafl's advice and set $b_i = h = 1$.


Rice–Shapiro theorem in computation theory I am trying to learn the Rice–Shapiro theorem on my own. Here is the theorem:

  Let $Γ$ be a set of computable functions such that the set $R_Γ$ is recursively enumerable. We have $f ∈ Γ$ if and only if there exists a finite function $θ ∈ Γ$ such that $θ ⊆ f$.

I will appreciate if anybody helps me to make the theorem crystal clear.
I just want to know what it really means and how I can use it to say that a set is not r.e., for example the set Empty or TOT.

Rice-Shapiro greatly helps in proving that a set is not RE, for some sets of the form $R_\Gamma$.

E.g. take $A = \{ n \ |\ {\sf dom}(\phi_n) \mbox{ finite} \}$. We have $A=R_\Gamma$ with $\Gamma = \{ \phi_n | {\sf dom}(\phi_n) \mbox{ finite} \}$. If $A$ were RE, since e.g. the always undefined function belongs to $\Gamma$, then by Rice-Shapiro any recursive extension of that would be long to $\Gamma$ as well -- but this is false, since e.g. the identity function  $\notin\Gamma$. Hence $A$ is not RE.

The above one is a typical use, where you reach a contradiction by extending a function inside $\Gamma$ to one recursive function outside.

We can also use it in the other direction: we reach a contradiction if we can take any function inside $\Gamma$ whose finite restrictions are all outside $\Gamma$. For instance, take $B = \{n \ |\ \forall k\in\mathbb{N}.\ \phi_n(2k)=5 \}$. Clearly $B=R_\Gamma$ with $\Gamma = \{\phi_n \ |\ \forall k\in\mathbb{N}.\ \phi_n(2k)=5 \}$. The function $f(x)=5$ is inside $\Gamma$, but any finite restriction of $f$ can not evaluate to $5$ on all even numbers, hence it must be found outside $\Gamma$. If $B$ were RE, by Rice-Shapiro one such restriction should instead be found inside $\Gamma$. We conclude that $B$ can not be RE.

I find Rice-Shapiro easier to use if I think about it as two separate results:

One is a monotonicity result, telling us that if $f \in \Gamma$ and $f \subseteq g$ with $g$ partial recursive, then $g \in \Gamma$. I.e. recursive extensions of functions in $\Gamma$ must belong to $\Gamma$ -- otherwise, $R_\Gamma$ is not RE.

The other is a compactness result. For any function in $\Gamma$, there must be a finite restriction of it inside $\Gamma$ -- otherwise, $R_\Gamma$ is not RE.

Many, many common examples of non-RE sets violate one of these two conditions, making it simple to prove they are not RE. For instance, consider $C = \{n\ |\ \phi_n(3)\neq 4 \land \phi_n(5)=2 \}$, where the notation $\phi_n(3)\neq 4$ is meant to be true when $\phi_n(3)$ is undefined. This immediately violates monotonicity, since I can always extend a (recursive) function which is undefined on $3$ so that it evaluates to $4$ on that point (and still get a recursive function). So $C$ is not RE.


What is the main difference between binary decision tree and binary decision diagram(BDD)? What is the main difference between binary decision tree and binary decision diagram(BDD)? From what I can tell I only understand that a binary decision diagram is a more compact representation because it eliminates nodes that have both edges pointing to the same node, eliminates nodes that have  removes  and removes terminal $2^n$ terminal nodes to just $2$, and but perhaps there is fundamental difference other then this?

One is a tree; one is not.  A BDD is a directed acyclic graph (dag), but not necessarily a tree.  This allows a BDD to be more compact, in some cases.

That's the only essential difference.  Of course, they have different properties (that follow from this difference in their definition).


Reduction from minimum dominating set to the set cover To solve the min dominating set problem of a graph G, we can reduce it to a set cover problem.

For example to find the MDS of the graph G:

We can create an instance of the Set Cover problem by:

Introducing the universe U to be equal to all vertices of the graph: U={0, 1, 2, 3, 4}.
For every closed neighborhood of a vertex in G, we introduce a subset S:

s= {{0, 1}, {0, 1, 2}, {1, 2, 3, 4}, {2, 3, 4}, {2, 3, 4}}

A minimum set cover solution of the instance (s, U) is similar to a minimum dominating set solution in the graph G.

My first question is how we can prove that this reduction is correct, and will give the correct MDS solution for every graph. In our example, the reduction works well and give the correct result.

My second question is how this reduction is related to the reduction when we deal with NP-complete proof(for example we can prove that the MDS problem is NP-complete by reduction to the vertex cover problem).

Are those reductions related?
Thank you

Let $G$ be an instance of dominating set and construct an instance of $(U,\mathcal{S})$ of set cover as you describe. The claim is that $G$ has a dominating set of size $k$ if and only if there is a subfamily $\mathcal{S}' \subseteq \mathcal{S}$ with $k$ members that covers $U$.

In the first direction, which you indicate is clearer, let $D$ be a dominating set of size $k$. Construct $\mathcal{S'}$ by adding into it the set corresponding to the closed neighborhood of every $v \in D$. Clearly, $\mathcal{S}'$ has size $k$ as $D$ has size $k$. Further, by the definition of a dominating set, $\mathcal{S}'$ also covers $U$.

In the second direction, let $\mathcal{S}'$ be a set cover for $U$. Build $D$ such that if the set $S_v$, the set corresponding to the closed neighborhood of $v$, is in $\mathcal{S}'$, add the vertex $v$ to $D$. Because $\mathcal{S}'$ covers $U$ which by construction corresponds to the vertex set of $G$, we have that $D$ is a dominating set. Moreover, we clearly have that $D$ has size $k$ as $\mathcal{S}'$ has size $k$.

Your second question however is unclear. A reduction "being related to another reduction" is not a formal statement. In an informal sense, you can use similar ideas to establish other reductions between dominating set, set cover and/or vertex cover but you have to work through the details yourself.


What is the difference between the semantic and syntactic views of function types? Edit: My original question referred to nonconstructive and constructive definitions of function types.  I changed the terminology in the question and the title to semantic and syntactic, which the answer indicates is the correct terminology for this distinction.

I can recall two ways of defining functions in set theory and programming languages with set-theoretic foundations.  The function type $\tau \to \sigma$ can be defined semantically as the set of all maps from $\tau$ to $\sigma \cup \{\bot\}$, i.e., all objects $f$ such that if $x \in \tau$ then $f(x) \in \sigma \cup \{\bot\}$.  Alternatively, the function type $\tau \to \sigma$ can be defined syntactically as the set of all terms in a given language whose type is $\tau \to \sigma$ (possibly modulo some equivalence relationship).  As a programmer, I work with the latter definition, but I often pretend that I'm working with the former definition.

What are the differences between the inhabitants of $\tau \to \sigma$ according to the two definitions above?  For instance, are uncomputable functions included in the first but not the second definition?

To be precise, I'm interested in the situation where terms are strongly typed, functions are side effect free and may be nonterminating, and functions are equal iff, for all inputs, they both diverge or both return the same value.

These are not called constructive and nonconstructive! The one you call "nonconstructive" works just as well in constructive mathematics (you have to be a bit careful about how you define the $\bot$ value, but that is a technical detail).

Rather, you are asking about semantic and syntactic distinctions. We imagine that the expressions we write in a program correspond to abstract mathematical objects. For example, the syntactic expression (fun n => 2 + n) 2 denotes the number $4$. (Under this view "evaluating a program" is about finding out which abstract mathematical object it denotes.)

We can then ask what mathematical objects corresponding to expressions of type a -> b. Presumably they are actual mathematical functions (although that is not so clear in the presence of computational effects). But they are not all functions, because those functions that can be expressed in a programming language have special properties, such as:

they are Turing computable (because programming langauges can be interprted by Turing machiens).
they are continuous (because in finite time we can only get finite information about input, and continuity essentially says that only finite amount of input is required to produce a finite amount of output).

So, it may make sense to restrict to special kinds of mathematical functions (only computable ones, only continuous ones). This way our mathematical objects will correspond more closely to our programs, and so presumably we will have a better setup. (In fact, as soon as we have a language with recursion, we cannot think of expressions of type a -> b as just ordinary functions, but rather somehting like the continuous ones--but let me not go there just now.)

As you say, most programers take a syntactic view, in which functions are syntactic expressions. This is certainly a possibility that can go a long way. But the semantic view in which we think of programs as denoting mathematical objects has its benefits too. Mathematicians know an awful lot about computability and continuity, and you can bring the knowledge in when you take the semantic view.

A trivial application of the semantic method is this: suppose we want to implement comparison of functions eq : (nat -> nat) -> (nat -> nat) -> bool which tells us whether two functions f, g : nat -> nat are equal. How do we do it? The answer is that we cannot implement it because that would give us a discontinuous function. But proving this fact using only syntactic methods is much harder. In fact, I do not know how to do it without using some computability theory, which again is a semantic method. You may think it is obvious that eq cannot be implemented, in which case you should wonder why eq : (nat -> bool) -> (nat -> bool) -> bool can be implemented (and the implementation was first found using semantic methods).

Another area where the semantic view is needed is numerical computation. It is absurd to claim that a program (syntactic entity) for solving a differential equation has nothing to do with differential equations (semantic entity).

Let me also say what the constructive-nonconstructive distinction is. This is about the logic you use to do math. If we use nonconstructive logic, which is the traditional way to do it, then we will be able to prove that there exist non-computable functions. Consequently, there will be functions we cannot implement. But if we use constructive logic, then it is impossible to prove existence of a non-computable function. (In fact, we may add an axiom to constructive logic which says "all maps are computable", although I would advise against this: how do you know that all external input that is coming into your computer from the universe is computable?) This is not the traditional way, but it is one that programers can sympathize with.

Lastly, I want to nitpick about something your write in your title. Definitions are not constructive or non-constructive. They just are. Constructivity is important when we prove and construct things. Function types in a programming language are defined a la type theory in terms of:

a type constructor, such as ->
rules for forming terms, such as $\lambda$-abstraction
rules for using terms, such as application
equations which are supposed to hold, such as $\beta$-reduction.

This works equally well in constructive and non-constructive logic, because it is just syntax. There are meta-theorems which say that for finite discrete objects (syntax, natural numbers, finite graphs, lists, ...) there is no difference between constructive and non-constructive logic (I am skipping over a lot of details). But when you ask for the semantics of your type, i.e., what mathematical object it corresponds to, then it makes a difference.


Drawbacks of repeating a single pattern matching procedure for many patterns One naive approach in solving multiple pattern matching problem is to call single pattern matching procedure on each of the pattern.

There must be some drawbacks in this approach, given the variety of multiple pattern matching algorithms such as Aho Cornsick algorithm, which prove to be more efficient.

So what are the drawbacks on this straightforward yet naive approach? In what scenario is this algorithm doing unnecessary works?

One common way of solving pattern matching problems is compiling a DFA that matches the pattern. If you have several patterns in mind, you can combine all of them into a single DFA, which will match all of them with a single pass, rather than one pass per pattern. On the flip side, the DFA could have many states and so might not fit into cache, which would cause a performance hit.


Does a shift operation distribute over XOR In this question, we abuse the mathematical notation to express bitwise operations in the following way:

$\ll$ is a binary left shift
$\oplus$ is a bitwise XOR
$0b1, 0b110, 0b10 \ldots$ are used to denote raw bits
$repr$ is a function associating to a number a given bit representation
$\mathbb{B}$ is the set of natural numbers to which $repr$ associates a two's complement bit representation
$\mathbb{G}$ is the set of natural numbers to which $repr$ associates a Gray code bit representation

I was trying to prove that the binary representation of a power of $2$ in binary reflected Gray code was always two ones followed by zero or more zeroes, except for $2^0$. The demonstration is roughly as follows:

  We know that the two's representation of powers of $2$ can be expressed as follows:

  $$ \forall n \in \mathbb{N} : repr(2_\mathbb{B}^n) = 0b1 \ll n $$

  And the function $to\_gray$ can be expressed as follows:

  $$ \forall n \in \mathbb{B} : to\_gray(n) = n \oplus (n \gg 1) $$

  Therefore, we have the following equivalence (ignoring the special case when $n = 0$):

  $$\begin{align*}
\forall n \in \mathbb{N} : repr(to\_gray(2_\mathbb{B}^n)) &= (0b1 \ll n) \oplus ((0b1 \ll n) \gg 1)\\
&= (0b1 \ll n) \oplus (0b1 \ll (n - 1))\\
&= (0b10 \ll (n - 1)) \oplus (0b1 \ll (n - 1))\\
&= 0b11 \ll (n - 1)
\end{align*}$$

However, the last line of the demonstration assumes that $\ll$ distributes over $\oplus$. Is this assumption true or does it only work for my specific use case?

Shift is right-distributive over XOR, and over many other operations as well (AND, OR, addition, min, max)

As for why, informally for the bitwise operations I'd explain it as: bitwise operations are like pointwise operations (if you view a number as a function from bit index to the bit at that index), translating (or permuting, etc) the positions distributes over doing the operation. Eg if we have two numbers $f$ and $g$ as such functions, then $(f ⊕ g)(k) = f(k) ⊕ g(k)$ so $(f ⊕ g)(k + j) = f(k + j) ⊕ g(k + j)$, here $f(k + j)$ is just $f$ shifted by $j$ so this showed that it didn't matter whether the shift is done after the XOR or on both of its operands. In general this applies to any remapping of the coordinates, ie $(f ⊕ g)(r(k)) = f(r(k)) ⊕ g(r(k))$ where $r$ is any function from $\mathbb{N}$ to $\mathbb{N}$.

As pointed out in the comments, this also relies on the operator to map two zeroes to an other zero, ie $0 ⊕ 0 = 0$.

Or simpler but less general, using string notation, let's say we have two number $a$ and $b$ and let their XOR be $c$, then $a0^k ⊕ b0^k = c0^k$ and $(a⊕b)0^k = c0^k$ (by substitution).


Evolutionary optimisation algorithm and graph based search Simulated annealing and genetic algorithm are examples of evolutionary optimisation algorithms. Both of these methods entail doing a search on a graph of candidate solutions.
Do all other evolutionary algorithms too entail - performing search on a graph?

Simulated annealing and genetic algorithm are examples of evolutionary optimisation algorithms

These are examples of meta-heuristics. Genetic algorithms are a class of Evolutionary algorithms which itself is one of many meta-heuristics.

  Both of these methods entail doing a search on a graph of candidate solutions.

Usually the "graph" is more conceptual than  physical. Meaning that it's not actually represented by a graph data structure living in memory due to the huge search space. These techniques go (or not) from one solution (or a set of solutions) to its "neighbor" using heuristics. For example a solution that has a better fitness value.

  Do all other evolutionary algorithms too entail - performing search on a graph?

Yes. Evolutionary algorithms are search based, meaning that we go from a set of solutions to another based on fitness functions. We also include a mutation step (and may include crossover).

This search happens on the "conceptual" graph of possible solutions.

It is worth to mention that this class is global search based in contrast with local search like the Simulated Annealing algorithm.

For more info check out this Wikipedia article on Meta-heuristics.


reduction from 3-SAT to Subset Sum problem How to reduce 3-SAT to subset sum problem?

The trick to the reduction is to use numbers to encode statements about the 3CNF formula, crafting those numbers in such a way that you can later make an arithmetic proposition about the numbers that is only true if the original 3CNF formula is satisfiable.  The reduction below is lifted directly from the lecture notes found at https://people.clarkson.edu/~alexis/PCMI/Notes/lectureB07.pdf .

  We reduce 3SAT to SUBSET-SUM. Consider a 3CNF formula with variables $x_1, . . . , x_n$ and clauses $c_1, . . . , c_r$.  For each variable $x_i$, we will have two numbers $y_i$ and $z_i$ in the list.  For each clause $c_j$, we will also have two numbers $s_j$ and $t_j$.  We define all of these numbers by specifying their base 10 representations.  The construction is best explained by an example and a picture.

  If the formula is $(x_1∨x_2∨\overline{x_3})∧(\overline{x_1}∨x_2∨\overline{x_3})$, then the base 10 representations of the numbers will look like this:

  \begin{array}{c|ccc|cc}
 & x_1 & x_2 & x_3 & c_1 & c_2 \\
\hline
y_1 & 1 & 0 & 0 & 1 & 0  \\
z_1 & 1 & 0 & 0 & 0 & 1  \\
y_2 & 0 & 1 & 0 & 1 & 1  \\
z_2 & 0 & 1 & 0 & 0 & 0  \\
y_3 & 0 & 0 & 1 & 0 & 0  \\
z_3 & 0 & 0 & 1 & 1 & 1  \\
\hline
s_1 & 0 & 0 & 0 & 1 & 0  \\
t_1 & 0 & 0 & 0 & 1 & 0  \\
s_2 & 0 & 0 & 0 & 0 & 1  \\
t_2 & 0 & 0 & 0 & 0 & 1  \\
\hline
k & 1 & 1 & 1 & 3 & 3 \\
\end{array}

  The number $y_i$ corresponds to the positive occurrences of $x_i$ in the formula while the number $z_i$ corresponds to its negative occurrences.  It should be clear how to generalize this construction to an arbitrary 3CNF formula.  And the list of numbers can clearly be constructed in polynomial time.  We claim  that  a  subset  of  these  numbers  adds  to  exactly $k$ if  and  only  if  the  formula is satisfiable.  A key point is that the sum of the numbers can be done column by column,  independently,  because  carries  will  never  occur.

The $s$ value is crafted the same way for each clause; put a one in the digit position corresponding to that clause, and zeroes everywhere else.  The $t$ value will be the same as the $s$ value for each clause.

The $k$ value is always 1111... followed by 33333.... where the number of ones is the same as the number of distinct variables in the formula and the number of threes is the number of clauses in the formula.  Note that the required sum $k$ has a one in each digit position corresponding to the variables.  This means that any solution to the subset sum problem can include only encoded statements about either a positive instance of the variable or a negative instance in each clause, not both.  Note also that sum $k$ has a three in the digit position corresponding to each clause.  The $s$ and $t$ values for each clause will sum to two, but to complete the sum a third one will have to come from one of the $y$ or $z$ values.  All three ones could come from the $y$ and $z$ values, but the fact that $s$ and $t$ will only sum to two for any clause guarantees that any empty clause in the 3CNF formula forces the subset sum problem to become unsatisfiable.


Subset with modified condition, is it still NP-complete? So I know the conditions required for a problem to be NP-Complete is that it has to lie within NP and has to be NP-hard.

The given problem I have is subset sum.

However, the conditions have been change to sum ≤ M and sum ≥ M from sum = M. To be more specific:

"If we ask if there is a subset with sum ≤ M, is the problem still NP- Complete?"
"If we ask if there is a subset with sum ≥ M, is the problem still NP- Complete?"

My initial reaction is that the two problems are no longer NP-complete since they can both be solved within polynomial time.

Check each element and see if there exists at least one smaller than M.
Add all positive integers and see if the sum of all elements is larger than M.

Since it isn't NP Hard, it cannot therefore be NP-complete.

Am I thinking/approaching this correctly?

What precisely are the problems? I may be missing something (and cannot do comments yet). Are they

(1) Given a set $A \subseteq \mathbb{Z}$ of $n$ elements, does there exist some subset $S \subseteq A$ with $\sum_{x \in S} x \le M$.

(2) Given a set $ \subseteq \mathbb{Z}$ of $n$ elements, does there exist some subset $S \subseteq A$ with $\sum_{x \in S} x \ge M$.

If so these problems seem clearly in $\mathbf{P}$, basically by the reasoning you described -- we just want the minimum/maximum possible subset sum, and then we compare that with $M$. Assuming empty $S$ is allowed:

for (1), add up all the negative numbers in $A$ and see if it's $\le M$. If Yes, then return yes. If not, return No.
for (2), add up all the positive numbers in $A$ and see if it's $\ge M$.

Again I may be missing something, but it seems like the other answer's reduction might not be addressing the possibility that $SS_\le$ and $SS_\ge$ would return yes based on different sets? Like consider input $A = \{1, 3\}$ and $M=2$.


Simplying this regular expression I am trying to prove (without converting it into Automata, through just simplification) that the following two regular expressions are equal:

$ (\epsilon + 0^*1^+0)^* = \epsilon + (0+1)^*10 $

here is what I have got so far:

$$ (\epsilon + 0^*1^+0)^* = \\
  (0^*1^+0)^* = \\
  (0^*1^*10)^* = \\
\epsilon + (0^*1^*10)^+ = \\
\epsilon + (0^*1^*10)(0^*1^*10)^* = \\
\epsilon + 0^*1^*10(0^*1^*10)^*$$

I seem to be stuck, I am not sure if I am doing it the correct way, or if there is a better way to prove this.

I know that $(a+b)^* = (a^*b^*)^* $ is true and I think this will certainly come in handy for the problem above but I am not sure how to prove $(a+b)^* = (a^*b^*)^* $ either.

The regular expression on the right consists of the empty word along with all words ending in $10$. All words accepted by the regular expression on the left are of this form. It remains to show that all words accepted by the regular expression on the right are also accepted by the one on the left. This is clear for the empty word, so it remains to show the following:

  Every word ending in $10$ is accepted by $(0^*1^+0)^*$.

Indeed, every word ending in $10$ has the form
$$
0^{a_1} 1^{b_1} 0^{a_2} 1^{b_2} \cdots 0^{a_n} 1^{b_n} 0,
$$
where $b_1,a_2,b_2,\ldots,a_n,b_n \geq 1$. We can decompose this word as
$$
(0^{a_1} 1^{b_1} 0) (0^{a_2-1} 1^{b_2} 0) (0^{a_3-1} 1^{b_3} 0) \cdots (0^{a_{n-1}-1} 1^{b_n} 0) \in (0^*1^+0)^*.
$$


Cyclic Redundancy Check Codewords Finding the Original Message So I have the received transmitted message in polynomial form as
$$T'(X) = X^{15}+X^{13}+X^8+X^7+X^4+X^3$$
and the error polynomial as
$$E(X) = X^{16}+X^{13}+X^3$$
 and the generator polynomial as
$$G(X) = X^4+X^3+X+1.$$

I am trying to find $T$ before it is transmitted. It is my understanding that the received transmitted message is the original codeword transmitted ($T$) plus the error polynomial ($E$), but in this case $T'$ is less than $E$, so when I subtract to find $T$, I get a negative polynomial. What am I doing wrong?

You should do arithmetic modulo 2. Modulo 2, $-1$ is the same as $+1$.


How to prove that $n\log n$ is space constructible? I'm trying to prove that $n\log n$ is space constructible. I've already managed to prove that $\log n$ is space constructible, but I cannot figure out how to prove the same about $n$. I assume, that if both $n$ and $\log n$ are space constructible, $n\log n$ will be space constructible as well.

I'm using Sipser's definition of space constructibility:

  A function $f\colon N\to N$, where $f(n)$ is at least $O(\log n)$, is called
  space constructible if the function that maps the string $1^n$ to the
  binary representation of $f(n)$ is computable in space $O(f(n))$.

You are right that if we can construct both $n$ and $\log n$ in $O(n\log n)$ space, we can construct $n\log n$ by multiplying these two values. I think constructing $\log n$ is actually the harder part here, which you seem to have already figured out. But let's go through it.

First, recall that a $k$-tape Turing Machine can be simulated on a single-tape Turing Machine by concatenating all the tapes onto a single tape. I am glossing over the details a bit here (but see Sipser for the details), but the key observation is that the space complexity can equivalently be viewed as the total space used across all tapes of a $k$-tape Turing Machine. So if we can construct a procedure for a $k$-tape Turing Machine that uses $O(n\log n)$ space across all tapes, then we have shown that $n\log n$ is space constructible.

We can construct $\log n$ through repeated halving of $n$. Specifically, we can copy $1^n$ from our initial tape containing the input to a second tape. Then, we can blank half of the ones on this second tape. Once we have blanked half of the ones, this tape will store $1^{n/2}$. We can repeat this halving process until there is only a single $1$ left. We count the number of halvings performed, in binary. We simply maintain a binary counter on a third tape, and perform a binary increment each time we perform a halving on $n$. At the end, the third tape will store the binary representation of $\log n$.

I am assuming that you already had figured the above out since you said you managed to prove $\log n$ is space constructible. And indeed you are correct that if we can independently construct $n$, we can multiply $n$ by $\log n$ in binary, using at most $n\log n$ space (in fact we will need less). All we really need then is to write out the binary representation of $n$ to another tape. Recall how we convert numbers to binary representation: the least significant bit of the binary representation of $n$ is $n\bmod 2$. Then, we can convert $\lfloor n/2\rfloor$ to binary (in a recursive manner) to compute the remaining bits. So, our Turing Machine will continue as follows: Copy $1^n$ to an available tape. Then, compute $n\bmod 2$. Note that we can do this fairly easily (If you are following Sipser, you should hopefully be comfortable with the fact that the set of all even-length strings is even a regular language). We write out the value of $n\bmod 2$ to another tape (call this the "$n$ tape"). Then, we perform the halving procedure on the $1^n$ again. Here, we should be careful about how we handle the case where $n$ is odd: we round down (For example, if $n=5$, after the halving procedure, the tape should contain $11$, the unary representation of $2$). This is to ensure the halving semantics are consistent with $\lfloor n/2 \rfloor$. Then, we move the head on the "$n$ tape" to the left one space, compute the mod once again, and write the result to the "$n$ tape" again. If we continue this modding and halving, writing the results of the modding to the left of the previously written bits on the "$n$" tape, we will eventually write out the binary representation of $n$ (once the working tape has only a single $1$ on it, the "$n$ tape" will contain the binary representation of $n$).

After these two procedures, we should have $\log n$ on one tape and $n$ on another tape, both in binary. Then, as you have already recognized, we can compute the product in $O(n\log n)$ space.


How does universal calculator work? As I understand, the concept 'computation' started dependent on hardware (like looms for instance).

The Hardware defines (physical cascades) what happens between input and output.
I think I saw in a CS class, a mention about universal calculation where software is not limited by hardware?

It's hard to find a succint answer.
What makes a universal calculator, universal?

(I'm not a CS major, so forgive my unprofessional terms and wordings)
Thank you.

I think you're asking about universal Turing machines? The machine is universal, in the sense that it can compute anything that any other Turing machine can compute.  This is interesting is that Turing machines seem to be a very good model of what can be computed by physical devices, such as actual computers. In particular, we're not aware of any physical computation process (i.e., any mechanism we could use to build a computer) that can compute something that a Turing machine can't. So, in practice, the Turing machine is taken as the definition of what can be computed. (See also the Church–Turing thesis.)


number of connected induced subgraph in a tree Let G be a tree-structured graph. A connected induced subgraph is an induced subgraph from G that is connected. (Since the original graph is a tree, any connected induced subgraph is also a tree)

My question: Given a tree G of n vertices, how many connected induced subgraph can be obtained from G?

An example: n = 4, G looks like 1---2---3---4 (I name those four vertices by 1, 2, 3, 4). Then we have 10 connected induced subgraph. Namely, they are {1}, {2}, {3}, {4}, {1,2}, {2,3}, {3,4}, {1,2,3}, {2,3,4}, {1,2,3,4} where I represent a connected induced subgraph by a set of their vertices.

Another example: n = 4, G looks like 1---2---3, 1---2---4 (node 2 directly connects 3 and 4. forgive my poor way of drawing it in text)
In this case, we have 11 connected induced subgraph. Namely, they are {1}, {2}, {3}, {4}, {1,2}, {2,3}, {2,4}, {1,2,3}, {1,2,4}, {2,3,4}, {1,2,3,4}.

From those two little examples we can see that the actual number depends on the exact structure of the tree, so, I am hoping you can help me further determine what is the factor that influences the result (I guess the maximal degree?).

Thank you!

Let $T$ be a tree rooted at $r$. Let the children of $r$ be $r_1,\ldots,r_\ell$, and let the corresponding subtrees be $T_1,\ldots,T_\ell$.

Consider a connected induced subgraph of $T$. There are two cases:

The subgraph doesn't contain $r$. In this case, the subgraph is a connected induced subgraph of some $T_i$.
The subgraph contains $r$. In this case, for each $i$, either the subgraph contains no vertices of $T_i$, or its intersection with $T_i$ is a connected induced subgraph of $T_i$ containing $r_i$.

Let us denote the number of subgraphs of the first type by $A(T)$, and those of the second type by $B(T)$. You are interested in $A(T) + B(T)$. The description above translates to the following recurrences:
$$
\begin{align}
A(T) &= \sum_{i=1}^\ell (A(T_i) + B(T_i)) \\
B(T) &= \prod_{i=1}^\ell (1 + B(T_i))
\end{align}
$$
Using this, you can calculate the number of connected induced subgraphs of a tree in linear time (ignoring the cost of arithmetic).


Kleene star operations Let $$ be any alphabet and let $_ \subseteq ^{∗}$ and  $_2 \subseteq ^{∗}$ be two non-empty languages.

a. If  $_ ^{∗} \neq ^{∗}$ than what can we say about $L_1$.

b.Let $\Lambda \in L_1$ and $\Lambda \in L_2$. Show using axioms and theorems of languages that $_ ^{∗}_2 =  ^{∗}$

For (a), $\Lambda$ should not belong to $L_1$ but I do not know how to prove that.

For (b),we have to prove that $_ ^{∗}_2 \subseteq  ^{∗}$ and $  ^{∗} \subseteq_ ^{∗}_2$ for equality to exist. We can also distinguish two cases, when $L = \Lambda $,  then $\Lambda ^{∗} \Lambda = ^{∗}$, but how can we prove that when $L \neq \Lambda $

Any idea

Hint:

You are right on (a). The proof involves key results for Kleene star as follows.
$$
\Sigma^{*}=\bigcup_{n\geqslant1}\Sigma^{n}\quad\text{and}\quad L\Sigma^{*}=\bigcup_{n\geqslant1}L\Sigma^{n}\quad\text{and}\quad \Sigma^{*}L=\bigcup_{n\geqslant1}\Sigma^{n}L
$$
Where $\Sigma^{n}$ can be considered as the set of the concatenation of i strings in $\Sigma$, and $L\subset \Sigma^{*}$.

For (a), $L_1\Sigma^{*}\subset\Sigma^{*}$ since for all $n,L_1\Sigma^{n}\subset\Sigma^{n}$. If $\Lambda\in L_1$, then $n,L_1\Sigma^{n}=\Sigma^{n}$ for all $n$. Thus $L_1\Sigma^{*}=\Sigma^{*}$.

For (b), notice that if $\Lambda\in L_1$ and $L_2$, then $L_1\Sigma^{*}=\Sigma^{*}$ and $\Sigma^{*}L_2=\Sigma^{*}$. Thus
$L_1\Sigma^{*}L_2=\Sigma^{*}L_2=\Sigma^{*}$.


What does "fast-forwarding" mean in the context of CPU simulation? I'm using a simulator for my thesis and I've come across the term "Fast-forwarding" but I have found no definition anywhere in the documentation or online. From a pdf I've been reading about the simulator I am using (gem5), I've come across this section:

  The gem5 simulator supports four different CPU models: AtomicSimple,
  TimingSimple, InOrder, and O3. AtomicSimple and TimingSimple are
  non-pipelined CPU models that attempt to fetch, decode, execute and
  commit a single instruction on every cycle. The AtomicSimple CPU is a
  minimal, single IPC CPU which completes all memory accesses
  immediately. This low overhead makes AtomicSimple a good choice for
  simulation tasks such as fast-forwarding. Correspondingly, the
  TimingSimple CPU also only allows one outstanding memory request at a
  time, but the CPU does model the timing of memory accesses.

Does anyone know what this term actually means?

Fast forwarding is used to warm-up microarchitectural state (caches, branch predictors, etc.) in preparation for more accurate simulation of a particular section of interest within an application. Since microarchitectural state can depend on operation ordering (e.g., cache replacement for data accesses and interactions between threads), speculation (e.g., instruction caching behavior), and even timing (e.g., thermal behavior), this is not a perfectly accurate warm-up, but "all models are wrong".


Is the empty string of even length? There is this example of regular expressions:

$$(\Sigma\Sigma)^*= \{w\mid |w|\text{ is even}\}\,.$$

From that I understand the empty string is valid as a string of even length. Is this true?

A number is even if it leaves no remainder when divided by two. Zero leaves no remainder when divided by two.


Why each function may be computed with circuit with 2^n gates? Why each function may be computed with circuit with 2^n gates ?

I am trying to understand this thing, but I can't. In particular why function constant $1$ requires $2^n$ gates. For me, it should be simple to return $1$ regardless of input.

The meaning of the statement is that each function can be computed with at most $2^n$ gates; it doesn't anything about the minimal number of gates needed to compute any function.

That said, you can always add dummy gates to increase the number of gates in your circuit without changing the function it computes. For example, you can replace one of the inputs $x_i$ to $x_i \lor x_i$ to increase the number of gates by 1.


Constraints on subset sum problem Subset sum is given by this question:
"The problem is this: given a set (or multiset) of integers, is there a non-empty subset whose sum is zero?"

My question is: If the numbers in the set are functions of other numbers, is that still subset sum? For example
The set {1,2,3} where the first number is X, the second is X+1, third is X+2 and so on. So it is a general set.

Is this allowed?

A set such as $\{1,2,3\}$ is valid input to the problem you defined, so yes, it is "allowed". When setting such constraints, you typically want to know "does the problem still remain NP-complete?". In this sense, notice there is a difference between "can my input take form such as this" and "if my input always takes this form, is the problem still NP-complete?"

I believe you are after the latter; if you impose some constraints on the input, does the problem remain NP-complete? For example, if your input is the set $\{1,\ldots,n\}$ for some positive integer $n$, the answer is no, the problem can easily be decided in polynomial time (can you see why?)


What is the big-$O$ notation of a summation of a log? For:
$$\sum^{n+m}_{i=n} \log(i)$$
I'm wondering what the big O notation is and how to prove it...
I believe that we can also write this as
$$\log(n) + \log(n+1) + \log(n + 2) + \ldots + \log(n+m)$$

also $$\log(n+m)!/\log(n-1)!$$

Thanks

Recall that the sum of $\log$'s is equivalent to the $\log$ of products.

That is:

$$\log(xy) = \log x + \log y$$

Thus we can change your function:

$$
\begin{align}
\sum_{i=n}^{n+m} \log i &= \log \prod_{i = n}^{n + m} i\\
&= \log (n \cdot (n+1) \cdot (n+2) \cdot \ldots \cdot (m-1) \cdot m )\\
&= \log (m!\ /\ (n-1)! )\\
\end{align}
$$

Then we can similarly use the division rule to get these back out:

$$
\log (m!\ /\ (n-1)! ) = \log (m!) - \log((n-1)!)
$$

Then using Stirling's Approximation we can immediately see:

$$
\log (m!) - \log((n-1)!) = O(m \log m)
$$

You might be able to do better though by taking more precise bounds to get:

$$
\begin{align}
\log (m!) - \log((n-1)!) &\leq em^{m + \frac{1}{2}}e^{-m} - \sqrt{2\pi}(n-1)^{n- \frac{1}{2}}e^{1-n}\\
&= \vdots
\end{align}
$$


How to build a TM which decides $L_k := \{(\langle M \rangle ,x)\in HP : |(\langle M \rangle ,x)| \le k \}$ For a specific natural $k$ we define the language of couples $(\langle M \rangle, x)$ such that $M$ stops on $x$ and the couple's encoding is bounded by $k$ i.e $L_k := \{(\langle M \rangle ,x)\in HP : |(\langle M \rangle ,x)| \le k \}$
This language is finite thus in $R$. I wish to understand how to build (Not formally) a TM, $\tilde{M}$ which decide this language. Since the only given information is that the encoding is bounded, I tried to think about "Pigeonhole" claim, i.e define $\tilde{M}$ which simulate $M$ computation on $x$ and remembering the configurations made by $M$ or by counting steps made by $M$ during the simulation in order to determine that $M$ is stuck in a loop. Since $M$ is deterministic, if $\tilde{M}$ "see" the same configuration twice, it guarantees that $M$ entered a loop, but I can't explain why the finite encoding of $(\langle M \rangle,x)$ promises that a configuration will repeat itself.

You cannot construct an explicit algorithm/TM which will decide the language $L_k$. Regarding your attempt at the proof: you are right that there is no guarantee that the configuration will repeat because these machines are not given to be space bounded.

The TM $M_k$ to decide $L_k$ will have all the tuples (which are finite in number) which are accepted hard coded in it. The TM will basically perform a search in a look up table: if that tuple is found then accept it, else reject.
We don't care how these tuples are actually obtained.

We can perhaps even prove that a general method to construct such TM $M_k$ for each $L_k$ cannot exists: Suppse there exists, then for a given input $<M,x>$, find the length of input, let it be $k$ and construct the TM $M_k$. Simulate $M_k$ over $<M,x>$. This will act as a decider for Halting Problem: which we know is undecidable. Hence, the assumption that we can have such a method is false.


Total functional computable real numbers Is there any computable real number which can not be computed by a higher order primitive recursive algorithm?

For computable real number I mean those that can be computed by a Turing machine to any desired precision in finite time. For higher order primitive recursive algorithm I mean common primitive recursive functions theory extended with first-class functions (as in Ackermann function).

Turing machines are more powerful than higher order primitive recursive functions so there exists the possibility that some computable reals numbers are not expressible by them.

The set of higher-order primitive recursive reals is essentially the class of functions $\mathbb{N}\rightarrow\mathbb{N}$ which can be represented by a term $\mathrm{Nat}\rightarrow\mathrm{Nat}$ in Gödel's system T.

Since every such function is total, and every well-typed term in the system can be enumerated effectively, there is a relatively easy proof by diagonalization that there is some computable real which cannot be represented.


premiss of reduction rule (abst) of pure type systems $$(abst) \:\frac{\Gamma, x: t_1 \vdash t_2: t_3 \quad \Gamma \vdash (x: t_1) \to t_3: s}{\Gamma \vdash (x: t_1. t_2): (x: t_1) \to t_3}$$

In this rule, why is $(x: t_1) \to t_3$ required to be an inhabitant of some sort? Isn't assuming $t_1: s$ enough?

There are two issues here.

The first most obvious one, is that if there is no rule $(s_1,s_2,s)$ in the pure type system, then there is no way to get from the hypotheses
$$ \Gamma \vdash t_1:s_1$$
and
$$ \Gamma, x:t_1\vdash t_3:s_2$$
to the conclusion
$$ \Gamma\vdash (x:t_1)\rightarrow t_3 : s$$
You can see that if there is no such rule, then your hypothesis is insufficient for forming the product type, and therefore you shouldn't be able to form terms of that type. Note that in the Calculus of Constructions, any $s_1, s_2$ has a corresponding $s$ ($=s_2$), so the premisses are sufficient for the conclusion in all cases.

Another, more subtle issue is that even the fact
$\Gamma, x:t_1\vdash t_3:s_2$ for some $s_2$ is not obvious from the fact
$$\Gamma, x:t_1\vdash t_2:t_3 $$
While actually true, this fact can be subtle to prove depending on how you set up your rules.

The rule you give minimizes the hassle, as it gives you directly the hypothesis that the product is well-formed without having to prove it after the fact.


Which languages do Perl-compatible regular expressions recognize? As the title says, I spent a couple of hours last weekend trying to wrap up my mind about the class of languages matched by Perl-compatible regular expressions, excluding any matching operator that allows to execute arbitrary code inside the pattern.

If you don't know what PCREs are, please read this and this.

The problem is, the resources available on internet pretty much stop at context-free languages, and PCREs can match more than those (see below); but I really don't know where to find more theorems or papers about this kind of stuff.

In particular: PCREs are obviously a superset of regular languages (as the PCRE syntax has all the regular language operators).

Any CFG can be put in Greibach normal form, which removes left recursion. I think this can be used by means of (?(DEFINE)...) groups to "translate" the grammar into matching subroutines, avoiding to choke on left recursion, by translating:

the non-terminal at the head of each production becomes a subroutine (?<HEAD>...)
the body of each production is put in the subroutine; terminals are left as-is, non-terminals become procedure invocations (i.e. (?&NONTERMINAL));
all the productions with the same nonterminal as head are ORed together by means of the | operator (plus additional grouping with (?:...), if necessary)
the pattern then becomes a (?(DEFINE)...) group containing all the "translated" productions, and an invocation for the procedure of the starting symbol, to match the entire string, i.e. ^(?(DEFINE)...)(?&START)$

This should deal with any CFG. Therefore, PCREs should be able to match any CFL.

There's more: let's take the simple language
$$L = \{ ww | w \in \Lambda^* \} $$
i.e. the language of the strings repeated twice. This language is not a CFL -- the pumping lemma for CFLs fails. (Pay particular attention that
$$ |vxw| \leq p$$
must hold, thus you can't just pump the beginnings or the ends of the two repeated strings.)

However, this language is easily matched by a PCRE: ^(.*)\1$. Therefore, we're strictly above CFLs.

How much above? Well, as I said, I have no idea. I couldn't find any resources about CSLs or all the other classes in between to make up my mind. Any expert willing to discuss this?

Addendum: I was asked to specify exactly which subset of the PCRE syntax must be allowed. As I wrote at the beginning of the post, I wanted to exclude any operator that allows to execute arbitrary code inside of the pattern, such as ??{}.

For the argument's sake, I think we can stick with the syntax defined by the pcresyntax(3) man page, which is a reasonable subset of what Perl 5.10-5.12 offers, minus the callouts (as they're not inside the pattern). I'm not sure that adding or removing backtracking control verbs change the language we can recognize; if so, it would be nice to figure out which classes we get with and without those.

I've also found this blog post extremely interesting http://nikic.github.io/2012/06/15/The-true-power-of-regular-expressions.html. It provides the very same proof I gave before about the fact that regexps recognizes the CFLs (by rewriting the grammar through DEFINE blocks), and even some CSLs (like the language of repeated strings); it builds on that and goes on, giving a proof that regexps with backreferences are NP-hard (by reducing 3-SAT to a regexp).


How do computers synchronize their clocks with the standard time I'd like to know how clock synchronization is done on computers, I've read this wikipedia article however it didn't give me exactly what I was looking for, I'll outline the problem I'd like answered:

My computer has the current time stored inside it which is maintained by a clock however this clock is subject to clock drift so it is nessisary to synchronize my computers time occasionally. Say my computer would like to do such a synchronization, then it would need to make a request to some time keeping server. This server would then respond to my computer with the correct time however there would be an inaccuracy due to the fact that the servers response would not be received immediately. My computer could attempt to estimate the travel time for the response however this is bound to be inaccurate. For this reason I suspect that GPS is used to synchronize time on computers. I'd imagine this is done by having the computer receive the time directly from the satellite and synchronize based on that.

I'd like to know if this is correct, if not, how is time synchronization done? Thanks

The Network Time Protocol (NTP) uses a rather simple basis, it assumes that the roundtrip time is divided equally between up and down delays after server processing is subtracted.

NTP keeps 4 timestamps per poll: client send $t_0$, server receive $t_1$, server send $t_2$ and client receive $t_3$. Server timestamps being in the server's clock and client timestamps being in the client's clock (that possibly needs adjusting).

Then the offset from one clock to the other is

$$\theta = \frac{(t_1-t_0)+(t_2-t_3)}{2}$$

The client will do statistical analysis to average out the delta and filter out outliers (filtering out excessive roundtrips for example) before adjusting the clock.

It is possible to use GPS to synchronize


Instruction level parallelism Can we distinguish instruction level parallelism and SIMD instructions (SSE, 3D now...) ?

Or is SIMD instructions one of the multiple ILP techniques ?

Thank you.

Instruction-level parallelism, data-level parallelism, loop-level parallelism, and task-level parallelism are not well defined terms.  The definable concept is parallelism.  Two operations can run simultaneously (or "in parallel") when the portions of the state they write are non-overlapping, and when the portion of the state written by each operation does not overlap with any of the state read by the other operation.

So two different instructions can run in parallel when the registers and memory they read and write don't overlap.  The sub-operations of a SIMD instruction can run in parallel because they are defined to only perform sub-operations that each read or write different portions of a vector register or cache line.

I like to say

  parallelism is as parallelism does

and what parallelism does is run multiple operations simultaneously.

The benefit of SIMD instructions, over just using 4 or 8 or N individual instructions that perform the same sub-operations, is that the fetch, decode, renaming, and scheduling units of the processor don't need to do as much work to exploit the parallelism between the sub-operations.


Deciding whether the language of a CFG equals some specific regular language I was wandering if $L = \{\langle G \rangle \mid \ G \text{ is a context free grammar and } \mathcal L(G) = A \}$ is decidable where A is a some regular language. Is
$L' = \{ \langle G \rangle \mid \ G \text{ is a context free grammar and } \mathcal L(G) = \overline A \}$ decidable ?  I feel like $L'$ should be decidable, but can't see how. Or does it depends on $A$?

It depends on your choice of $A$. For example, the problem $\{\langle G \rangle \mid L(G) = \Sigma^* \}$ is undecidable, while $\{\langle G \rangle \mid L(G) = \phi \}$ is decidable.

Also, the two languages that you have given (the one with $A$ and the other with $\overline{A}$) are equivalent since regular languages are closed under complementation.


Property of cyclic codes Let $C$ be a $[n,k]$ cyclic code over $\mathbb{F}_q$ with $(n,q)=1$.

I want to show that $(1, \dots, 1)$ is a codeword iff $X-1 \nmid g(X)$.

$g(x)$ is the generator polynomial.

We suppose that $(1, \dots, 1)$ is a codeword.

We consider the following correspondence

$$\pi: \mathbb{F}_q^n \to \mathbb{F}_q[x] / x^n-1, (a_0, a_1, \dots, a_{n-1}) \mapsto a_0+ a_1 x+ \dots+ a_{n-1} x^{n-1}$$

Then $(1, \dots, 1) \mapsto 1+ x+ \dots+ x^{n-1}$.

We want to show that $X-1 \nmid g(X)$.

Then $g(X)=b(X)(X-1)$ for some polynomial $b(X)$. How can we get a contradiction?

How can we show that if $X-1 \nmid g(X)$ then $(1, \dots, 1)$ is a codeword?

The word $(1,\ldots,1)$ is in your code iff there exists a polynomial $p(x)$ such that $$ \frac{x^n-1}{x-1} = p(x) g(x). $$
Since the code is cyclic, $g(x)$ divides $x^n-1$, and so $(1,\ldots,1)$ is in your code iff there exists a polynomial $p(x)$ such that
$$ \frac{x^n-1}{g(x)} = p(x)(x-1). $$
In other words, $(1,\ldots,1)$ is in your code iff
$$
x-1 \mid \frac{x^n-1}{g(x)}.
$$
I'll let you complete the proof, using the fact that $x-1$ divides $x^n-1$ but not $\frac{x^n-1}{x-1}$.


Initial Algebra example If the definition of Initial Algebra is:

"An object is initial if there exists a unique morphism from the object to every
object in the category"

Why do we need such object, and could any one give an example ?

An initial algebra is an initial object in the category of $F$-algebras for a given endofunctor $F : \mathcal{C} \rightarrow \mathcal{C}$.

This construction is widely used to gives semantics to data-structures in (functional) programming languages. Intuitively, the functor $F$ captures the "shape" of the data-structure (e.g., $F(X) = 1 + A \times X$, with $A$ a fixed set for instance).

The underlying set $\mu F$ of the initial algebra
$\langle \mu F, \alpha \rangle$ intuitively captures the set of syntactic expressions you can build by induction on the shape functor (e.g., for the previous functor with $A = \{a,b \}$, $\mu F = \{(1), (a,1), (b,1), (a,a,1), (a,b,1) \ldots \}$ is the set of finite lists of $A$-elements).

The initiality is the key property to construct inductive function (see catamorphism). Some excellent references on this topic:

Lectures on Semantics: The initial algebra and final coalgebra perspectives
A Tutorial on (Co)Algebras and (Co)Induction


What is the complexity of the following problem? Input: $M$ is non deterministic Turing machine that always halts in $cn^k$ moves/steps, where $c$ and $k$ are constants and $n$ is the length of the input string of $M$, $w$ is any string in $\Sigma^*$ and $a$ is another string in $\Sigma^*$ where $\Sigma=\{0,1\}$.

Output: Does $a$ represent a valid computation of $M$ on $w$?

$a$ indeed encodes truth assignment, when the symbol $0$ encodes false value and the symbol $1$ encodes true value.

If $a$ satisfies $\Phi_{M,w}$, where $\Phi_{M,w}$ is the boolean formula that deterministic Turing machine can compute in polynomial time by the Cook Levin reduction that is satisfiable if and only if $M$ accepts $w$, then $a$ is indeed represents a valid computation of $M$ on $w$ since the Cook Levin reduction is parsimonious.

But if $a$ falsifies $\Phi_{M,w}$ then this is not necessarily true
that $a$ represents a valid computation of $M$ on $w$, because it is possible that the given non deterministic Turing machine $M$ accepts the given string $w$ on all computations, paths and routes and the given truth assignment $a$ still falsifies $\Phi_{M,w}$.

So in case that $a$ falsifies $\Phi$, how do I decide whether or not $a$ represents a valid computation of $M$ on $w$?

What is the complexity of this problem?

Does exist polynomial time deterministic algorithm that decides/solves this problem or nobody doesn't know if such algorithm exist yet?

As Ariel explained in the comments:

"then $a$ indeed represents a valid computation of $M$ on $w$ since the Cook Levin reduction is parsimonious" - This has nothing to do with the reduction being parsimonious, this is a result of the specific construction of the reduction. Also, you don't have to appeal to Cook-Levin to encode computations of a Turing machine, there is no real reason to talk about assignments for boolean formulas in this context. You can simply say that $a$ is a description of $M$'s tape, state, and head location during some prefix of its computation.

Additionally, the input should consist of $M,w$ alone, you don't have any information about $M$'s running time from its encoding (how would you know if the machine actually runs in exponential time?). Now, the problem is trivially solvable in polynomial time by reading $a$ and checking that any configuration is reachable from its predecessor by one of $M$'s transition functions.


Is everything that is turing computable an element of NPSPACE? So, if there is something that is turing computable, I know it is in NP (is that right?).

If M is computable, does it mean M is in NP?

M computable IFF in NP (is that true)?

And does all computable machines exist under NPSPACE?

So, if there is something that is turing computable, I know it is in NP (is that right?).

No!!! The time hierarchy theorem says that, for example, there are problems in $\mathrm{NEXP} = \mathrm{NTime}[2^{\mathrm{poly}(n)}]$ that aren't in $\mathrm{NP}$. And that there are problems in $\mathrm{2NEXP} = \mathrm{NTime}[2^{2^{\mathrm{poly}(n)}}]$ that aren't in $\mathrm{NEXP}$. And so on, ad infinitum.  In particular, this means that any $\mathrm{NEXP}$-complete problem is decidable but not in $\mathrm{NP}$.

To put it another way, there's no function $f$ such that every decidable problem can be solved in time (or space) $f(n)$, deterministically or nondeterministically.

In particular, there are perfectly reasonable decidable problems that aren't in $\mathrm{NP}$. For example, suppose you want to work with a graph on $n$ vertices. The graph is really large, so you can't store it. But, if I give you two vertices, it's easy for you to compute whether or not there's an edge between them (e.g., you can do that in deterministic polynomial time). Any problem that's $\mathrm{NP}$-complete when you're just given the full adjacency matrix as the input becomes $\mathrm{NEXP}$-complete when the graph is encoded in this way.


Can you get O(n) with a word frequency algorithm? By a word frequency algorithm:
An algorithm gets a document as an input, and returns each unique word along with the number of times it has appeared in the document.

For example:

in:"Hello my name is Hello"
out: {'Hello':2, 'is':1, 'my':1, 'name':1}

In my implementation, I used a hash table to store the words.

But I've seen uses of a trie, but I don't understand why this improves runtime.

I've read that you can get O(n). I assume with a trie correct?

If the size of the alphabet is constant and $n$ denotes the length of the document (i.e. the total number of characters), you can indeed use Tries to get $O(n)$ running time - regardless of the length of the words.

In a Trie, you can search for (or insert) a word in time linear in the length of the word. You can use a Trie to keep track of the words as you encounter them in the text, and in each Trie node corresponding to a word you can store that word's frequency (which is updated each time you encounter it).

The running time of this algorithm is indeed $O(n)$: the sum of all the lengths of the words in the documents is precisely the length of the document. Note that you can also traverse the Trie (and list the words it contains to generate the desired output) in $O(n)$ (since the number of nodes in the Trie is at most $n$).


Intersection of two particular languages Here's the question:

  Compute the intersection of the following two languages:
  \begin{align}
&L_1 = \{ a^{n+1} b^{2n} a^{n+1} \mid n \ge 0 \} \\
&L_2 = \{ w \in \{a,b\}^* \mid \#_a(w) + \#_b(w) \equiv 1 \pmod 2 \}
\end{align}

I'm pretty sure that $L_2$ is just "$|w|$ is odd", which would mean the intersection of the two languages would be $L_1$ when its length is odd, right?

What I'm confused about is that $|w|$ for every $w ∈ L1$ will always be even no matter what $n$ is.

Can someone help me find the solution? I have absolutely no clue how to do it.

Edit:  #a(w) + #b(w) %2 = 1 not 0 (my bad)

$$L_1 = \{a^{n+1}b^{2n}a^{n+1} \mid n \ge 0\}$$

$$L_2 = \{w \mid (\#_a(w) + \#_b(w)) \bmod 2 = 1\}$$

I assume that $\#_a(w)$ means the number of $a$s in $w$.

First, I would write out some $w$ in $L_1$ and $L_2$:

$$L_1 = \{aa, aabbaa, aaabbbbaaa, \ldots\}$$

$$L_2 = \{a, b, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaaa, \ldots\}$$

From this, we see that words in $L_1$ are always even length ($(n+1) + (2n) + (n+1) = 4n + 2 = 2(2n+1)$ and odd + even + odd = even) and words in $L_2$ are always odd length ($(a+b)\bmod2 = 1$).

This means $L_1 \cap L_2 = \emptyset$.

Before OP's edit to post ($L_2 = \{w \mid (\#_a(w) + \#_b(w)) \bmod 2 = 0\}$):

First, I would write out some $w$ in $L_1$ and $L_2$:

$$L_1 = \{aa, aabbaa, aaabbbbaaa, \ldots\}$$

$$L_2 = \{aa, ab, ba, bb, aaaa, aaab, aaba, \ldots\}$$

From this, we see that words in $L_1$ are always even length ($(n+1) + (2n) + (n+1) = 4n + 2 = 2(2n+1)$ and odd + even + odd = even) and words in $L_2$ are always even length ($(a+b)\bmod2 = 0$).

This means $L_1 \cap L_2 = L_1$ (because $L_1 \subset L_2$).


Could we design a Turing machine that output every bit of $\pi$ one after another correctly with limited tape length? Could we design a Turing machine that output every bit of $\pi$ one after another correctly?

I think we have computer programs that calculate the value of $\pi$ day after day, and thus it's viable.

Could we do that if the Turing machine has a limited tape length?

If by "limited tape length", you mean having a finite amount of memory, then the answer is "no".  With a finite amount of memory, the Turing machine as a whole can be modeled as a finite state machine.  A finite state machine that doesn't terminate must eventually repeat a state and thus fall into a loop. Therefore, the output of any such machine must correspond to the binary expansion of a rational number. The binary expansion of any irrational number whatsoever will require an unbounded amount of state.


Confused about pumping lemma, What i'm missing? When I apply pumping lemma on this language:
${L=\{010^n:n\ge0\}}$ over the alphabet ${\Sigma =\{0,1\}}$ I get that it is non-regular despite the fact that it is regular.

let ${n=4}$, then $w=010000$
$w=xyz$ ,  $ { \mid xy\mid \leq n} $ and $ {\mid y\mid \geq 1}$
$x=0$ , $y=10$ , $z=000$
let $i =2$
$xy^2z = 01010000$ $\not\in L$ so L is non-regular.

so, what I'm missing?

you can't claim to know how $w$ distributes.

you know that some $w \geq n_0$ exists, in such a way it can be denoted as

$w=xyz$

$y \neq \epsilon $

$ |xy|\leq n_0 $

and for every $i>0: xy^iz \in L$

your error is that you claimed you know the distribution of $w$ to $x,y,z$. Namely, you fixed $y$ to be $10$

The language of course can be pumped, since it's regular. But for any $w = xyz, y$ must be a word of only $0$, since $1's$ cannot be pumped.


Is it possible to solve the halting problem if you have a constrained or a predictable input? The halting problem cannot be solved in the general case. It is possible to come up with defined rules that restrict allowed inputs and can the halting problem be solved for that special case?

For example, it seems likely that a language that does not allow loops for instance, would be very easy to tell if the program would halt or not.

The problem I'm trying to solve right now is that I'm trying to make a script checker that checks for the validity of the program. Can halting problem be solved if I know exactly what to expect from script writers, meaning very predictable inputs. If this cannot be solved exactly, what are some good approximation techniques to solve this?

The intuitive answer is that if you don't have unbounded loops and you don't have recursion and you don't have goto, your programs terminate. This isn't quite true, there are other ways to sneak non-termination in, but it's good enough for most practical cases. Of course the converse is wrong, there are languages with these constructs that do not allow non-terminating programs, but they use other kinds of restrictions such as sophisticated type systems.

Recursion

A common restriction in scripting languages is to dynamically prevent recursion: if A calls B calls C calls … calls A, then the interpreter (or checker, in your case) gives up or signals an error, even if the recursion might actually terminate. Two concrete examples:

The C preprocessor leaves a macro intact while it is expanding that macro. The most common use is to define a wrapper around a function:

#define f(x) (printf("calling f(%d)\n", (x)), f(x))
f(3);

This expands to

(printf("calling f(%d)\n", (3)), f(3))

Mutual recursion is handled as well. A consequence is that the C preprocessor always terminates, although it's possible to build macros with high run-time complexity.

#define f0(x) x(x)x(x)
#define f1(x) f0(f0(x))
#define f2(x) f1(f1(x))
#define f3(x) f2(f2(x))
f3(x)

Unix shells expand aliases recursively, but only until they encounter an alias that's already being expanded. Again, the primary purpose is to define an alias for a similarly-named command.

alias ls='ls --color'
alias ll='ls -l'

An obvious generalization is to allow a recursion depth of up to $n$, with $n$ perhaps being configurable.

There are more general techniques to prove that recursive calls terminate, such as finding some positive integer that always decreases from one recursive call to the next, but these are considerably harder to detect. They are often hard to verify, let alone infer.

Loops

Loops do terminate if you can bound the number of iterations. The most common criterion is that if you have a for loop (without tricks, i.e. one that really counts from $m$ to $n$), it performs a finite number of iterations. So if the body of the loop terminates, the loop itself terminates.

In particular, with for loops (plus reasonable language constructs such as conditionals), you can write all primitive recursive functions, and vice versa. You can recognize primitive recursive functions syntactically (if they are written in an unobfuscated way), because they use no while loop or goto or recursion or other trick. Primitive recursive functions are guaranteed to terminate, and most practical tasks don't go beyond primitive recursion.


How to define quantum Turing machines? In quantum computation, what is the equivalent model of a Turing machine?
It is quite clear to me how quantum circuits can be constructed out of quantum gates, but how can we define a quantum Turing machine (QTM) that can actually benefit from quantum effects, namely, perform on high-dimensional systems?

(note: the full desciption is a bit complex, and has several subtleties which I prefered to ignore. The following is merely the high-level ideas for the QTM model)

When defining a Quantum Turing machine (QTM), one would like to have a simple model, similar to the classical TM (that is, a finite state machine plus an infinite tape), but allow the new model the advantage of quantum mechanics.

Similarly to the classical model, QTM has:

$Q=\{q_0,q_1,..\}$ - a finite set of states. Let $q_0$ be an initial state.
$\Sigma=\{\sigma_0,\sigma_1,...\}$, $\Gamma=\{\gamma_0,..\}$ - set of input/working alphabet
an infinite tape and a single "head".

However, when defining the transition function, one should recall that any quantum computation must be reversible.
Recall that a configuration of TM is the tuple $C=(q,T,i)$ denoting that the TM is at state $q\in Q$, the tape contains $T\in \Gamma^*$ and the head points to the $i$th cell of the tape.

Since, at any given time, the tape consist only a finite amount of non-blank cells, we define the (quantum) state of the QTM as
a unit vector in the Hilbert space $\mathcal{H}$ generated by the configuration space $Q\times\Sigma^*\times \mathrm{Z}$. The specific configuration $C=(q,T,i)$ is represented as the state $$|C\rangle = |q\rangle |T\rangle |i\rangle.$$
(remark: Therefore, every cell in the tape isa $\Gamma$-dimensional Hilbert space.)

The QTM is initialized to the state $|\psi(0)\rangle = |q_0\rangle |T_0\rangle |1\rangle$, where $T_0\in \Gamma^*$ is concatenation of the input $x\in\Sigma^*$ with many "blanks" as needed (there is a subtlety here to determine the maximal length, but I ignore it).

At each time step, the state of the QTM evolves according to some unitary $U$
$$|\psi(i+1)\rangle = U|\psi(i)\rangle$$

Note that the state at any time $n$ is given by $|\psi(n)\rangle = U^n|\psi(0)\rangle$. $U$ can be any unitary that "changes" the tape only where the head is located and moves the head one step to the right or left. That is, $\langle q',T',i'|U|q,T,i\rangle$ is zero unless $i'= i \pm 1$ and $T'$ differs from $T$ only at position $i$.

At the end of the computation (when the QTM reaches a state $q_f$) the tape is being measured (using, say, the computational basis).

The interesting thing to notice, is that each "step" the QTM's state is a superposition of possible configurations, which gives the QTM the "quantum" advantage.

The answer is based on Masanao Ozawa, On the Halting Problem for Quantum Turing Machines.
See also David Deutsch, Quantum theory, the Church-Turing principle and the universal quantum computer.


Help with context free grammar excercise So, I have an exercise in which I have to write a context free grammar for this language:
$$L = \{x \in L(a^∗b^∗c^∗) : |x|_a > |x|_c; |x|_b > 0; |x|_c ≥ 0\}$$
meaning every string with any number of $a$'s, $b$'s and $c$'s in that order, with the amount of $a$'s greater than the amount of $c$'s and the amount of $b$'s greater than zero.
I am having trouble figuring out the rule that makes sure there are more $a$s than $c$s.
I have:
$$\begin{align}S&\to aABC | ab\\
A&\to aA | a\\
B&\to bB | b\\
C&\to cC | c\\
\end{align}$$
I know this is wrong because I should be adding an $a$ every time I add a $c$, but I don't know how to write that.

I think you can do it in this way
$$\begin{align}
X&\to A\ |\ aXc\ |\ aAc\\
A&\to aA_t\\
A_t&\to aA_t\ |\ B\\
B&\to bB_t\\
B_t&\to bB_t\ |\ \epsilon\\
\end{align}$$
Here $X$ can choose to do the first transformation, if there are not going to be any $c$s. $X$ can do the second transformation many times to add an initial chunk of the same amount of $a$s and $c$s, or do the third transformation to put a last pair of an $a$ and a $c$.
In that third case, it goes to $A$ which puts one extra $a$ and goes to $A_t$, which can put even more $a$s or go to put $b$s.
Then $B$ puts one $b$ and goes to $B_t$, which puts as many more $b$s as wanted or terminates.
But check it. This is the first ever context free grammar rules that I write in my life.

Shorter rules by nir shahar
$$
\begin{align}
S&\to AB\ |\ aSc\\
A&\to aA\ |\ a\\
B&\to bB\ |\ b
\end{align}
$$


Decide whether a context-free languages can be accepted by a deterministic pushdown automaton Given a context-free grammar G, there exists a Nondeterministic Pushdown Automaton N that accepts exactly the language G accepts. (and visa versa)

There may also exist a Deterministic Pushdown Automaton D that accepts exactly the language G accepts too.  It depends on the grammar.

By what algorithm on the productions of G can we determine if D exists?

There is no algorithm that given a context-free grammar, decide if a DPDA recognizes the same language and computes it if it exists.

Because if such an algorithm existed, we would be able to decide the undecidable problem of the universality of a context-free grammar i.e. whether a given context-free grammar $G$ on $Σ$ recognizes the whole language $Σ^*$.

Suppose there is such an algorithm $A_{DPDA}$. Let $G$ be some context-free grammar. Let $L$ be $\mathcal L(G)$. Then the algorithm $A_{DPDA}$ will decide if there is a DPDA $A$ recognizing $L$.

If there is no such DPDA, then $L$ is not recognizable by a DPDA, in particular it is not regular, so it can't be $Σ^*$.
If a DPDA $A$ exists then we can decide if $L$ is equal to $Σ^*$ because universality is decidable for DPDAs.
Why? Because:

DPDA languages are closed under complementation (because DPDAs are deterministic)
emptiness is decidable for DPDAs (because it is for PDAs)

Using $A_{DPDA}$ we have built an algorithm deciding whether $L(G)=Σ^*$ for any context-free grammar $G$, which has been proven impossible. Therefore $A_{DPDA}$ does not exist.


Can a functional language be homoiconic? According to the wikipedia page on homoiconicity:

  In a homoiconic language the primary representation of programs is also a data structure in a primitive type of the language itself.

I was wondering if the lambda calculus was homoiconic (I assume not, because applications are not data (which, for the calculus, would mean variable or abstraction?)), and if not, what it would take to make it homoiconic (wrap all applications in an abstraction with a useless variable, a la \a.b c?).

But the more important question is this: If the only primitive data type in the language is the function, is it possible to achieve homoiconicity? (Does homoiconicity even make sense if all you have are functions?) If not, then is there some formal definition of what data-properties must be present in order to achieve homoiconicity?

The definition implies not only that programs are represented by a "primitive" datatype, but presumably also that it is possible to inspect the elements of this type, i.e., one can actually get at the code (otherwise I can just declare a primitive abstract type code and never let you look at it).

In general, the construct you are looking for is known as quote. It takes a piece of code (in $\lambda$-calculus or anywhere else) and returns its representation, either as an abstract syntax tree, a string, or just an integer (because integers can encode syntax trees). Of course, in the case of $\lambda$-calculus such trees, strings or numbers would be encoded in the usual way that we encode datastructures in $\lambda$-calculus.

It is known that having quote in general increases the expressive power of the language. For example, in $\lambda$-calculus we cannot implement the statement "all functions are continuous" but we can if we also have quote at our disposal (this is the essence of Kreisel-Lacombe-Shoenfield-Tseitin theorem).

The opposite of quote is eval, which many languages have. However, eval does not add to the expressive power of a language because it can be implemented within the language, assuming the language is general enough (eval is essentially an interpreter for the language).

It is worth mentioning that quote is an abstract way of making a programming language be a lot more like the Turing machine model (TM) of computation. In the TM model a piece of code is a Turing machine, and it is represented on the tape as a sequence of symbols, which is the only datatype that Turing machines know about.

Note: it is common knowledge that "all models of computation are equivalent". What this means is that they compute the same class of functions from numbers to numbers $\mathtt{nat} \to \mathtt{nat}$, but they are not equivalent when it comes to higher-order functions such as $(\mathtt{nat} \to \mathtt{nat}) \to \mathtt{nat}$.


Hamiltonian cycle, verifying and finding If we have an algorithm that in polynomial time says if a graph G has an hamiltonian cycle, can we have an algorithm that in polynomial time find an hamiltonian cycle?

My attempt is to delete an edge of graph G and have G', after run the algorithm on G' to know if it has an hamiltonian cycle if not it means that the edge is in some hamiltonian cycle. Now I don't know how to go on.

Let $P$ be an arbitrary simple path in the graph. If $P$ appears in a Hamiltonian cycle of the graph, you can remove all the vertices of $p$ except the first and the last vertex, connect these two vertices with an edge and the resulting graph must be Hamiltonian.

Keeping this in mind, we can build the Hamiltonian cycle step by step starting with path of length one, since you already described how to build such a path. Then we can extend a path of length $i$ to a path of length $i+1$ using the trick above, where we try all neighbors of the last vertex in the path as a next vertex and we apply the trick above to check if a Hamiltonian cycle exists where the new path is a part of the cycle. Note that we call the black-box at most $m := |E|$ times. Once we reach a path of length $n-3$ it is easy to complete the path into a Hamiltonian cycle in linear time.


Is there a formalization for the trade-off between the expressiveness and the speed of a programming language? I do not have a strong background in theoretical computer science, so the terminology I use may not be the most ideal.
Basically the "trend" across programming languages I have noticed is that there appears to be an trade-off in the speed of a programming language (how long it takes to execute a program) and its expressiveness (saying you want something done vs saying you how you want something done, more expressive languages focus less on the "how", from this definition).
For example, in "higher-level" languages like Python or Java - it is very easy to do something like finding the index of an item in a list with a single line like list.indexOf(item). In comparison, doing the same action in a "lower-level" language like C can result in code that is much faster, but at the cost of having write the code yourself which may be several times as long.
Again, this is really just a trend I have noticed and not a hard and fast rule. Languages like C++ that are both very fast yet can also be pretty expressive at times blur the lines.
So I am curious, is there any sort of formalization in programming language theory - or even just rough rules of thumb backed by empirical studies - explicitly listing out the trade off between the expressiveness and execution speed of a programming language?
Or perhaps I am just overthinking it, and having slower code is just a unavoidable byproduct of having a more expressive language as more things are taken care of "behind the scenes" / abstracted away from during compilation, interpretation, etc.?

This is a really interesting problem and I don't think there are definitive answers. There are two important, and distinct dimensions to this problem.

What does expressivity actually mean? In the light of the
Church-Turing thesis, which states that all programming languages
are the same (can be compiled into each other). Nevertheless it
seems pretty clear that e.g. assembler programming is quite
different from programming in Python. There is a research field that
studies this. It was pioneered by (1), but much ink has been spilled
since.

In computational complexity theory speedup theorems show that for
any algorithm solving a problem, there is a faster algorithm  solving the same problem. Examples are
Blum's speedup theorem  and the linear speedup theorem. Basically, what those speedup theorems tell you is that you can
always speed up computers (Turing machines) a bit by adding more
powerful commands. In processors we went from 4 bit CPUs to 8 bit,
then 16 bit, the 32 bit and nowadays 64 bit.

Neither quite answers your question, I'm afraid!

(1)  M. Felleisen, On the Expressive Power of Programming Languages.


Why "Choice Points" introduce non-determinism in a program? I'm studying the didactic programming language Oz, following the book "Concepts, Techniques, and Models of Computer Programming".

In the book, the nondeterminism is introduced through the concept of choice, as it's explained here.
However, in the Oz language if the programmer calls a choice between alternatives A, B, C it happens that the alternative A is always travelled first, and consequently (in case of backtracking) first B and then C. So the choice happens to be deterministically, since I know a priori how the choices' tree will be constructed.
So what's the link between choice and nondeterminism?

I also have another question. In the book, the authors state that if I want to introduce the choice concept in my computation model I am obliged to use a stateful (non-declarative) computation model. Why?

Nondeterminism is an inherently unphysical concept. If you think about the various definitions of nondeterministic computation, they always say something like one of the following:

the computation is structured as a tree and, if any of the paths through the tree succeeds, the computation succeeds, regardless of how many failures there are on other paths;
the computer "magically" considers all the options in parallel, even though there might be exponentially many of them;
the computer only considers one option but it "magically" knows which one will lead to success, if any of them will, and chooses that one.

In principle, the "choice" operator achieves nondeterminism – at least, it would, if we could implement it using one of the above schemes. Unfortunately, in the real world, we don't know how to do that, so we have to pick an option, see if it works out, and backtrack if it doesn't. Maybe we could do something a bit smarter than just trying the options in order but, at the end of the day, we don't know any efficient way of implementing nondeterminism on a real, deterministic, computer (which is why we don't know that $\mathrm{P}=\mathrm{NP}$).


Help understand the notation I'm reading a computer science paper, this one: https://arxiv.org/abs/1608.03960. It uses certain notation in one of the illustrations (Figure 9, page 8 in the PDF version) that I don't understand how to interpret.
Attaching here as well for better visibility:

$$ \text{EXEC} ~ \frac{\text{cmd}_1 : \text{CMD} \quad A_p, \text{cmd}_1 \implies A^\prime_p}{A_p, \langle \text{cmd}_1 ~ ; ~ \text{cmd}_2 ~ ; \ldots \rangle \implies A^\prime_p, \langle \text{cmd}_2 ~ ; \ldots \rangle} $$

I've tried to search for this online, but haven't come up with anything. I'd appreciate if someone explain it to me, particularly these questions:

Does this notation has an official or widely recognized name?
What's the relationships between expression above and below the horizontal line?
What's the meaning of $\Rightarrow$, long arrow?
What's the meaning of two expressions being separated by a comma, as in $A_p, cmd_1$? How is it different from two expressions separated by a blank space, as in $$\mathrm{cmd}_1, \mathrm{CMD}\ \ \ \ \ \ \ \ A_p, \mathrm{cmd}_1\,?$$

Here's another example from the paper:

$$ \text{VAR} ~\frac{x \in \text{dom}(A_p)}{A_p, x \implies A_p(x)}$$

What's the meaning of $dom(A_p)$ here?

Answering your questions one by one:

The rules are part of an operational semantics, which defines how to evaluate expressions.
The notation with the horizontal line is an inference rule: if all the logical statements above the line are true, then you can conclude that the statement below the line is also true.
The arrow is a predicate that indicates that the left hand side can be evaluated (or reduced) to the right hand side.
The expressions separated by a comma form a tuple; for example, $A_p, cmd_1$ is a pair consisting of $A_p$ and $cmd_1$.
$\mathrm{dom}(f)$ returns the domain of the function $f$, that is, the set of values $x$ for which $f(x)$ is defined.

In these rules, $A_p$ is a state object: a function that maps variable names to values. (Think of it a bit like the heap on which you can allocate objects, and where the variable names are pointers.) The VAR rule performs variable lookup in that state:

If the statement above the line is true: $x \in \mathrm{dom}(A_p)$, that is, the function $A_p$ is defined for the argument $A_p(x)$,
Then the statement below the line is true: $A_p, x \Longrightarrow A_p(x)$, that is, the expression $x$ in the state $A_p$ can be evaluated to $A_p(x)$, which is just the value of the function $A_p$ when you pass in the variable name $x$ as argument.

Hope that helps. For more details, lecture notes on operational semantics (e.g. these from Cambridge) will further explain the notation.


Can BNF consist of zero rules? I am trying to use BNF to describe its own grammar to get used to it. What I can not find any information about is whether BNF must consist of zero or more rules or one or more rules. The difference would be:

<grammar> ::= <grammar> <rule> | <rule>

vs.

<grammar> ::= <grammar> <rule> | ""

The only difference I can see is that an empty language can be described by an emtpy BNF in the second case, but must use <grammar> ::= "" in the first case.

Concretely speaking, the Backus-Naur form is a notation for context-free grammars, applied to the (formal) description of languages at the syntactical level.

While there are extended versions of BNF that have been standardized, the BNF itself hasn't, so there is no way of determining if the empty grammar is "legal" BNF.

As a mathematical object, the possibility of an empty grammar will depend on the definition (of grammar) used. A grammar that has no productions is usually said to define the empty language, but any grammar whose set of possible terminal derivations is empty is also a candidate definition of the empty language.


Prove that $BPP^{BPP} = BPP$ Prove that $BPP^{BPP} = BPP$.

Obviously $BPP\subseteq BPP^{BPP}$. So we're left with proving $BPP^{BPP} \subseteq BPP$. Let's consider $L\in BPP^{BPP}$. Then, there's a PTM $M$ to decide $L$ for some $BPP(\alpha, \beta)$ which uses an oracle for some language $O\in BPP$. $O$ also has a $PTM\in BPP$, let's denote it $M_o$. So we could create $M'$, a PTM which behaves exactly as $M$, but everytime $M$ uses the oracle, it simulate $M_o$ on the given input for the oracle.

Now, I want to show that $M\in BPP$. By definition, $BPP=BPP(1/3, 1/3)$, so every time $M$ calls $M_o$ it takes a probabilistic risk basing a deciion upon $M_o$ answer.

We've learned in class that $BPP = BPP(1/3, 1,3) = BPP\left(\frac{1}{3^n}, \frac{1}{3^n} \right)$ and I think I shall explain that even though $M_o$ may return false answers, $M_o$ is still in $BPP$.

Can you help me with doing that?

Thanks

EDIT:
Basically, I want to give a lower bound for the probability of $M$, answering correctly. Let's assume that $M$ queries the oracle $n^c$ times for some $n\in\mathbb{N}$. I think the lower bound is $\frac{1}{3^{n^c}}$.

My explanation is that we're assuming the worst case. That is, if the oracle is returning a false answer then we are returning a false answer.

Is that right?

EDIT2
I'm not sure it's $100\%$ correct, since I didn't take into account the probabilistic behavior of $M$ itself.

Here's a sketch: you seem to be on the right track. Let $L\in BPP^{BPP}$ be decided by a BPP machine $M$ that makes queries to an oracle $A\in BPP$ decided by a $BPP$ machine $M'$. Let $E$ be the error for $M$, $E'$ the error for $M'$ (that is, the probability that the BPP machines fail is at most $E, E'$). We will choose $E, E'$ appropriately via error reduction.

Now, fix a string $z$ to use as randomness for all queries to $M'$. There are at most polynomially many queries to $M'$, say at most $|x|^k$, since $M$ is a ppt TM. Thus, $$\operatorname{Pr}[\text{an error occurs in some query to } M']\le |x|^k\cdot E'$$ So the overall probability of error by $M$ in deciding $L$ is at most $|x|^k\cdot E' + E$, so if we choose $E=\frac{1}{6}$ and $E'=\frac{1}{6|x|^k}$ (which we may do by the standard BPP error reduction), we get an overall probability of error $\le\frac{1}{3}$, so the procedure described is a $BPP^P\subseteq BPP$ procedure.

By the same proof we have the more general statement that $BPP^{BPP^A}\subseteq BPP^A$.


fixing a slightly broken BST tree I'm stuck on this question, a BST is slightly broken only if there is a node with value x in which :

there is at least one value less than x on its right branch or atleast one value greater than x on its left branch.

for example :

                3
               / \
             10   5
             /\   /\
            8 15 4  7

suggest an algorithm which will fix the tree also it should keep its original shape and same values, at worst case $O(n)$, where $n$ is the number of values.

I know it is possible to fix it and keep same shape but I can't seem to find the an algorithm that is at worst case $O(n)$.

The problem must have said that there is at most one node such that, if its value is $x$, "there is at least one value less than $x$ on its right branch or at least one value greater than $x$ on its left branch". Otherwise, any binary tree could be "a slightly broken BST tree". It is not possible to construct a BST in $O(n)$ from random $n$ values in general.

Here is the explanation for an $O(n)$ algorithm.

First, as you should have observed, we can concentrate on the subtree with the broken node as the root. Let us assume that the root of the tree is the broken node.

Perform in-order traversal on the left subtree to list all values in the left subtree. Perform in-order traversal on the right subtree to list all values in the right subtree. Merge these two ordered list. Insert the value of broken node. Now we get all values in an ordered list.

Now traverse the whole tree in-order. In other usual situations we will print its value when we visit a node. Instead, we will  replace the values of nodes using the successive values in that ordered list when we visit the nodes.

It is clear that each step above takes $O(n)$ time.


Binary Search Tree Stability Data Structure After constructing a binary search tree, you can read off the key values in ascending order by performing an in-order traversal.
Will the resulting sorted order be stable?
If so, how would the tree have to be coded to ensure this?
If it is not possible, why not?"

Just a review question I came across. From what I understand,
Stability ensures that if A and B share the same Key, if A comes before B originally, A comes before B after sorting as well.
Ascending order = Bottom up
Inorder = Left - Root - Right
if we have a BST that looks as such;
----5,a
--3,c  4,b
-1,d
and we insert a 1,e into the tree. We can get that 1,e on the left or right child of 1,d.
We want to return 1,d first then 1,e so that stability is retained.
How do we change the code for the BST to do this? My suggestion was to make a linked list that returns the head of duplicate values whenever duplicates are encountered. However I'm not sure this is entirely the best method here.

You can ensure that the inorder is stable by modifying the insertion routine (if necessary) so that when it compares an element $x_1$ already in the tree to the new element $x_2$, if $x_1 = x_2$ then it answers that $x_1 < x_2$.

Caveat: I'm not sure that this works for self-balancing trees.


Prove that  is not a element of NOT-SELF I know this has been a question but based on a past experience, i thought i would rewrite it so i can get input and ask questions faster.

Suppose we have
$$\text{NOT-SELF}=\{\langle M\rangle \mid  M \text{ is a Turing machine that does not accept }\langle M\rangle\}$$
the set of all machines that don't accept their own coding.

Let $Z$ be a TM such that $L(Z)$ is a subset of $\text{NOT-SELF}$. Prove that $\langle Z\rangle$ is an element of $\text{NOT-SELF}$.

My answer so far is very broad and I'm trying to improve it.

If $\langle Z\rangle$ is not an element of $\text{NOT-SELF}$, than $\langle Z\rangle$ can’t be an element in $L(Z)$. Since there’s a condition that $L(Z)$ is a subset of $\text{NOT-SELF}$,  this contradicts so $\langle Z\rangle$ must be an element of $\text{NOT-SELF}$.

Assume (i) $L(Z) \subseteq \text{NOT-SELF}$ and assume towards contradiction that (ii)
$\langle Z \rangle \notin \text{NOT-SELF}$.

Because of (ii) and (i) we get that $\langle Z \rangle \notin L(Z)$.

(if it was in $L(Z)$ and $L(Z)$ is a subset of $ \text{NOT-SELF}$, it must also be in $\text{NOT-SELF})$.

Thus, $Z$ does not accepts its own encoding.
Thus, by the definition of $ \text{NOT-SELF}$ it should be that $\langle Z \rangle \in \text{NOT-SELF}$, which is a contradiction.

Also see the related question:
Can I construct a Turing machine that accepts only its own encoding?