Can there be two different left most derevations for a grammar? Suppose there is a CFG with the rules

S--> Aa
A--> Bb
B--> A
B--> Epsilon

To my best understanding the left most derivation would go like this..

 S==> Aa ==>  Bba ==> Aba ==> Bbba ==> bba

or

 S==> Aa ==>  Bba ==> Aba ==> Bbba ==> Abba ==> Bbbba ==> bbba

or

 S==> Aa ==> Bba ==> ba

Of these which is the true left most derivation of the language? If it is true that all of them are valid left most derivations,why is it that many text book talk about left most derivations of a language rather than a final string??

A leftmost derivation of a string in the language defined by a
grammar $G$ characterizes a parse-tree for that string. It is a way of
describing the parse tree, which is unique for each parse tree.

But to answer the specifics of your question, there is no lefmost
derivation of a language, only of the strings of a
language. Furthermore, since a leftmost derivation is a sequence of
grammar rules applications to produce the string, a leftmost
derivation is necessarily defined with respect to a specific
grammar. Indeed, the language does not really matter, only the grammar
and a string derived with that grammar.

If a string has only a single derivation for a grammar $G$, it is said
unambiguous for that grammar. When it has several, it is said
ambiguous for that grammar. When it has none, it does not belong to
the language generated by the grammar.

A grammar is ambiguous if it generate at least one ambiguous
string. It is unambiguous if every string in its language is
unambiguous.

The grammar in your question is unambiguous. Each of the derivations
you give is a leftmost derivation, but each for a different string in
the language of the grammar.

Actually, this grammar is so simple that it has only leftmost
derivations, because there is at most one non-terminal in each rule
right-hand side. But a grammar can have only leftmost derivations and be ambiguous.


Proving that a language of Turing machine descriptions is/is not Turing recognizable How to approach to solve this question and the likes of it?

  Let $L$ be the set of strings $\langle M\rangle$ such that $M$ accepts all strings of even length and does not accept any strings of odd length.

  a) Is $L$ Turing-recognizable? Prove your answer.
  b) Is the complement of $L$ Turing-recognizable? Again prove your answer.

Please have a look at my approach, is it correct? :

  Since the string representation of set of all the Turing Machines (say S) is Infinite countable and Recursively Enumerable, there fore there exists a Turing Machine that accepts S. Now, if we choose the Turing Machines M1, M2, ... from S, in the given order, such that all the chosen machines accept even length string and reject odd length strings, then the set we get (Say T) will also be Infinite Countable and recursively Enumerable and will have a Turing Machine which accepts it. That is why it is language T is Turing Recognizable. Similarly complement of T is Turing Recognizable.

@Rick if I use the following code :

RL(<M>) =
  for n = 0, 1, ...
     for s = s0, ..., sn  \\in the standard order on all strings
       run M on s for one move
         if M(s) = accept AND |s| is odd
           reject // accept as string in L complement
     if not rejected for any string then accept as a string in L

This code will select all the $M$ which accept all strings of even length and do not accept any string of odd length. Then now since we have a membership algorithm for $L$ (as well as for $\overline L$), then can we say that the $L$ and $\overline L$ are recursive?

The problem with your proposed algorithm is where you say

  ... choose the Turing Machines M1, M2, ... from S, in the given order, such that all the chosen machines accept even length string and reject odd length strings.

How are you going to do this? If you could, then you would have answered your original question, i.e., you've fallen into the trap of assuming what you want to prove.

In fact, your language $L$ isn't recursively enumerable.

There are at least two ways to show that $L$ isn't r.e.. I'll give one, but it requires that you be able to show that $L$ isn't recursive. Rice's theorem is an immediate way, but you don't know it yet, so you'll have to reduce it from a known non-recursive language like the Halting language. That's not hard, but I won't give it now. Just accept for the moment that $L$ is not recursive.

Suppose that we wrongly guessed that $L$ was recursive and we wanted to build a recognizer for it. One way is to simply dovetail all strings and test whether $M$ accepted any odd-length strings (so we'd know then if $M$ wasn't in $L$). This gives us a proposed recognizer for $L$:

RL(<M>) =
  for n = 0, 1, ...
     for s = s0, ..., sn  \\in the standard order on all strings
       run M on s for one move
         if M(s) = accept AND |s| is odd
           reject

If $M$ accepts any odd-length string, sooner or later this program will find it and so will be able to recognize that $M$ is not in $L$. Of course this isn't what we wanted: we need to make a program that recognized if a given $M$ is in $L$. However, all is not lost---simply by changing the "reject" to "accept" we would have made a recognizer for the complement, $\overline{L}$, so we've stumbled across the interesting fact that  $\overline{L}$ is recognizable.

So what, you might ask? Remember, if a language $A$ and its complement, $\overline{A}$ are both r.e., then $A$ must be recursive. We just showed that $\overline{L}$ is r.e., so if $L$ was also r.e., then we could conclude that $L$ was recursive. However, you've accepted that $L$ is not recursive, so we must conclude that $L$ must not be r.e..


Help reducing 3-SAT to 3-COLORING I am working on showing that 3-colorability is NP-complete. I read a few articles and walkthroughs on this but none are really clicking. I get to this part

  "Then for every variable xi that appears in the instance of Satisfiability, we connect a
       vertex xi to a vertex xi, and we connect both xi and xi to red. This is illustrated
       below for a case where there are (only) 3 variables."

I think what they mean is something like this:

x1----x1*     x2----x2*      x3----x3*
 \   /         \   /          \   /
  \ /           \ /            \ /
   R             R              R

But my question is, what exactly is this step doing?

With a little bit more thought, is this step just showing that given xi to be one color, then xi* has to be another, but also cannot be R, as they are both connected to it?

I believe the goal of this construction is to try to assign true or false to each variable. The color assigned to x will determine whether it's true or false, and there's an edge from x to ¬x to ensure that each variable and its negation get different values. The edge from each variable to R ensures that there are only two possible colors that can be assigned to x, one of which means true and one of which meand false.

Hope this helps!


Number of vertices of a graph in vertex cover of size $m$ Let $G$ have a vertex cover of size at most $m$ and let the degree of $G$ be bounded by $k$. Then $G$ has at most $m(k+1)$ vertices.
Note: Remove all vertices of degree $0$.

Answer:
The idea is to have $m$ graphs like the below one.

But how can I prove this proposition formally?
Thank you in advance for your answers.

Consider the graph $G=(V, E)$, where each vertex in $G$ has at most $k$ neighbours. Let $C\subseteq V$ be a vertex cover of size at most $m$. For a vertex $v\in C$, let $c(v) = \{v\} \cup \{ u\in V: \{u, v \}\in E\}$, that is, $c(v)$ is the set of vertices that are covered by the vertex $v$ (including $v$ itself).
A side note: the subgraph induced by the vertices in $c(v)$, for any $v$, is a "star" graph (similar to the one you attached, yet the number of vertices that are neighbours of $v$ in this subgraph can be strictly less than $k$). The idea is to consider star graphs corresponding to the vertices in $C$, and then use the union bound for sets.
Now $C$ being a vertex cover implies that $\bigcup\limits_{v\in C} c(v) = V$. This is easy, yet we prove it for completentss:  the $\subseteq$-containment is trivial. The other direction follows as for every vertex $v\in V$, one of the following holds:

$v\in C$: in this case, as $v\in c(v)$, we have that $v\in \bigcup\limits_{v\in C} c(v)$.
there is $u\in C$ such that $\{u, v\}\in E$: in this case, as $v\in c(u)$, we have that $v\in \bigcup\limits_{v\in C} c(v)$.

Finally, the following holds $$ |V| = |\bigcup\limits_{v\in C} c(v)| \leq \sum\limits_{v\in C} |c(v)| \leq |C|\cdot max_{v\in C} (|c(v)|) \\\leq |C|\cdot max_{v\in C}(degree(v) + 1) \leq |C|\cdot (k + 1) \leq m\cdot(k+1)$$


Is this language defined using twin primes regular? Let

$\qquad L = \{a^n \mid \exists_{p \geq n}\ p\,,\ p+2 \text{ are prime}\}.$

Is $L$ regular?

This question looked suspicious at the first glance and I've realized that it is connected with the twin prime conjecture. My problem is that the conjecture has not been resolved yet, so I am not sure how can I proceed with deciding that the language is regular.

If the twin prime conjecture is true, then $L = a^{*}$, which is regular. If the twin prime conjecture is not true, then there are finitely many twin primes; indeed, there is a largest pair of twin primes $\{p, p + 2\}$. In this case, $L = \{a^{n} | n < p + 1\}$, a finite language. In either case, you get a regular language, so I think it's safe to conclude that $L$ is a regular language... we just won't know which one it is until the twin prime conjecture is resolved.


Sums of $2^{-l}$ that add to 1 Consider the following problem:

  You are given a finite set of numbers $(l_k)_{k\in \{ 1, ..., n \}}$ such that $\sum_{k=1}^n2^{-l_k}<1$. Describe an algorithm to find a set $(l'_k)_{k\in \{ 1, ..., n \}}$ such that $\forall k \in \{ 1, ..., n \}:l'_k\le l_k$ and $\sum_{k=1}^n2^{-l'_k}=1$.

(For what it's worth, this is a problem arising from Information Theory, where the Kraft-McMillan Theorem gives that the result above yields a more efficient binary code than the one with codeword lengths $(l_k)$.)

Here are my initial thoughts. We can consider $\sum_{k=1}^n2^{-l_k}$ as a binary number e.g. $0.11010011$ and then we need to reduce the value of some $l_k$ values whose digit position is preceded by a $0$. So for instance, with the initial $0$ in the $\frac{1}{8}$ position of the example number I gave, we want to decrease the value of some $l_i=4$ to $l'_i=3$ to add $\frac{1}{8}$ and subtract $\frac{1}{16}$ to the sum. We then have $0.11100011$, so we've moved the problematic $0$ along a digit. When we get to the end we presumably have something like $0.11111110$, and then need to reduce the value of the longest codeword by 1 to get the overflow to $1.00000000$.

However, I encounter two problems: there may not be such an $l_i=4$, for instance, if the $1$ in the $\frac{1}{16}$ digit place arises as the sum of three $l_i=5$ numbers. Additionally, if we multiple have $0$ digits in a row then we presumably need to scan until the next $1$ and then decrement a corresponding $l_i$ multiple times, but it's conceivable that I would "run out" of large enough $l_i$ codewords that I can manipulate in this way.

Can anyone describe an algorithm with a simple proof of correctness?

A follow-up problem: how do we generalise this algorithm to bases other than $2$?

Here is a very simple algorithm. We will require the following lemma.

Lemma. Suppose that $1 \leq \ell_1 \leq \cdots \leq \ell_k$ and $\sum_{i=1}^k 2^{-\ell_i} \geq 1/2$. Then there exists $r \in \{1,\ldots,k\}$ such that $\sum_{i=1}^r 2^{-\ell_i} = 1/2$.

Proof. Let $r$ be the first index such that $\sum_{i=1}^r 2^{-\ell_i} \geq 1/2$. Since the $\ell_i$ are non-decreasing, there are integers $A,B$ such that
$$
\begin{align}
\sum_{i=1}^{r-1} 2^{-\ell_i} &= \frac{A}{2^{\ell_r}}, &
\sum_{i=1}^r 2^{-\ell_i} &= \frac{B}{2^{\ell_r}}.
\end{align}
$$
Moreover, $A < 2^{\ell_r-1}$ and $B \geq 2^{\ell_r-1}$. Since $B-A=1$, we conclude that $B = 2^{\ell_r-1}$, and so $\sum_{i=1}^r 2^{-\ell_i} = 1/2$. $\quad\square$

This suggests the following algorithm. We can assume that your sequence is sorted, that is, we are given a sequence $\ell_1 \leq \cdots \leq \ell_k$ such that $\sum_{i=1}^k 2^{-\ell_i} \leq 1$. We now consider three cases:

$\sum_{i=1}^k 2^{-\ell_i} = 1$. In this case, there is nothing to do.
$\sum_{i=1}^k 2^{-\ell_i} \leq 1/2$. In this case, we can decrease each $\ell_i$ by $1$.
$1/2 \leq \sum_{i=1}^k 2^{-\ell_i} \leq 1$. Applying the lemma, we find $r$ such that $\sum_{i=1}^r 2^{-\ell_i} = 1/2$, and so $\sum_{i=r+1}^k 2^{-\ell_i} \leq 1/2$. We thus have to solve the same kind of problem for the second half $\ell_{r+1},\ldots,\ell_k$, aiming at $1/2$ rather than $1$.

To implement this recursion more cleanly, we add a parameter $s$, and our goal is to correct a sequence satisfying $\sum_i 2^{-\ell_i} \leq 2^{-s}$ to one satisfying $\sum_i 2^{-\ell_i} = 2^{-s}$ by only decreasing elements.

Here is how the algorithm works in the case of the sequence $1,2,4,7,8$, which matches your example. The sum in your case is more than $1/2$, so we separate the sequence into two parts: $1$ and $2,4,7,8$. We only handle the second, aiming at a sum of $1/2$.

The sum in the case of $2,4,7,8$ is more than $1/4$, so we separate the sequence into two parts, $2$ and $4,7,8$, and only handle the second, aiming at a sum of $1/4$.

The sum in the case of $4,7,8$ is less than $1/8$, so we decrement each element, obtaining the sequence $3,6,7$, whose sum is more than $1/8$. We separate it into $3$ and $6,7$, and only handle the second, aiming at a sum of $1/8$.

We decrement $6,7$ twice, obtaining the sequence $4,5$ whose sum exceeds $1/16$. We separate it into $4$ and $5$, and decrement the latter once.

Putting everything together, we obtain the sequence $1,2,3,4,4$.

In the $q$-ary case, we have to change the problem somehow, since the result is not true in general. For example, take $q = 3$ and consider the sequence $1, 1$.

Here is another simple algorithm, based on the following lemma.

Lemma. Suppose that $0 \leq \ell_1 \leq \cdots \leq \ell_k$ and $\sum_{i=1}^k 2^{-\ell_i} < 1$. Then $\sum_{i=1}^{k-1} 2^{-\ell_i} + 2^{-(\ell_k-1)} \leq 1$.

Proof. Since the $\ell_i$ are nondecreasing, we can write $\sum_{i=1}^k 2^{-\ell_i} = A/2^{\ell_k}$, where $A < 2^{\ell_k}$. Replacing $\ell_k$ with $\ell_k-1$ increases the sum by $1/2^{\ell_k}$. Since $A+1 \leq 2^{\ell_k}$, the sum remains at most $1$. $\quad\square$

This suggests the following simple algorithm: repeatedly decrement the largest $\ell_i$. The algorithm necessarily terminates since at most $\sum_i \ell_i$ iterations can take place.

Let us apply this on our example above:
$$
\begin{align}
&1,2,4,7,8 \to 1,2,4,7,7 \to 1,2,4,6,7 \to 1,2,4,6,6 \to 1,2,4,5,6 \to \\
&1,2,4,5,5 \to 1,2,4,4,5 \to 1,2,4,4,4 \to 1,2,3,4,4
\end{align}
$$
This algorithm can be implemented easily using a heap. However, it is slower (in general) than the preceding algorithm, if the latter is implemented correctly. For example, the sequence $\ell$ takes $\ell$ steps in this algorithm, but could be handled by a single iteration of the preceding algorithm.


Edit distance proof when last chars of 2 strings are the same from Wagner–Fischer_algorithm:
I understand substitution cost needs to be adjusted, either 0 or 1:
 for j from 1 to n:
      for i from 1 to m:
          if s[i] = t[j]:
            substitutionCost := 0
          else:
            substitutionCost := 1

          d[i, j] := minimum(d[i-1, j] + 1,                   // deletion
                             d[i, j-1] + 1,                   // insertion
                             d[i-1, j-1] + substitutionCost)  // substitution

But in later proof part, it claims when s[i] == t[j], d[i, j] = d[i-1, j-1]:

If s[i] = t[j], and we can transform s[1..i-1] to t[1..j-1] in k operations, then we can do the same to s[1..i] and just leave the last character alone, giving k operations.

I don't understand, shouldn't it be d[i, j] = min(d[i-1, j-1], d[i-1, j] + 1, d[i, j-1]+1)?
It's also mentioned in edit distance wiki

How do you prove if the last chars are matched, d[i, j] is d[i-1, j-1]?

following the lemma here,
I can think one way to prove this is to assert minimal is not from d[i-1, j-1] when s[i] = t[j]. Then draw contradiction.
if minimal is not from d[i-1, j-1], the minimum must come from

deleting last char from s, s[i].
or inserting last char from t, t[j].

If we go with 1, we need to match s[0..i-1] with t[0..j].
A: if s[i-1] != t[j],

insert t[j] to end of s, we are rewinding to the original state.
modify s[i-1] to t[j], it's equvilent to deleting s[i-1] (+1) when matching s[i-1] with t[j-1], whose minimum is d[i-1, j-1].
delete s[i-1] -> only viable way

B: if s[i-1] = t[j],

no insert t[j], otherwise the previous deletion is redundant.
no modification: equivalent to 2nd point in discussion A.
deletion -> viable

Combine A and B, only deletion is acceptable and it's impossible to match if only deletion is performed on s.
Do you guys think this proof is correct?

Let's show that if $s$ and $t$ end with the same symbol, then there is always an optimal solution in which the final letters are left alone. Note that there could be other optimal solution in which this is not the case. For example, if $s = a$ and $t = aa$, then an optimal solution would be to delete the final $a$ from $t$. All we are claiming is that some optimal solution leaves these letters alone.
Instead of deleting letters from $s$, let's add them to $t$. The situation thus looks as follows: starting with $s,t$, we add some letters to both, and change some letters in $s$, so that the resulting strings $s',t'$ coincide.
If the final letters in $s',t'$ were both added, then we can improve the solution by not adding them, so we can assume that this is not the case.
If the final letter in $s'$ resulted from changing the last letter in $s$, then necessarily the last letter in $t'$ was added; we can instead not change the last letter in $s$, and add a different letter in $t'$, improving the solution, so we can assume that this is not the case.
Thus either the last letter in $s'$ is that of $s$, or the last letter of $t'$ is that of $t$, or both; in the latter case, there is nothing to prove. The two remaining cases are symmetric, so let's suppose that the last letter in $s'$ is that of $s$, say $\sigma$, while there is a suffix of $t'$, say $r\sigma$ (it must end with $\sigma$!), which was added after the last letter in $t$, which is also $\sigma$.
Instead of adding $r\sigma$ at the very end of $t'$, we add $\sigma r$ just before the final letter of $t$. In both cases this results in an identical suffix $\sigma r \sigma$, so we have converted the given solution to a solution with identical cost in which the final letters of $s,t$ are left untouched.

Finally, let me comment that the original paper doesn't seem to make this optimization.


What are these special strings called? Is there any specific name for strings of data that have well defined format ? For example URLS, domain names, IP Addresses, Email addresses, File Paths etc. are all having well defined delimiters and data formats. What are these special strings in general called ?

Any set of strings is a (formal) language. That's probably not what you mean since you have quite specific restrictions in mind.

Many standardised string formates are defined by regular expressions what makes the respective sets of strings they admit regular languages. Note that some examples are actually finite languages (IPs).

In then end, it depends on what you mean by "well defined". Any set of strings is well-defined. Anything more will depend on the kind of specification you give, and then the language will (sort of) inherit the specification's "name".


What is the difference between formal language, regular language and regular expression? I want to know the difference between these three languages and it would be great if you would give some examples as well.

An alphabet $\Sigma$ is a finite collection of symbols. For example, $\Sigma = \{0,1\}$.

A word over an alphabet $\Sigma$ is a finite sequence of letters from $\Sigma$. For example, $0$, $01$ and $1110$ are all words over $\{0,1\}$. The empty word (that is, the empty sequence) is also allowed, and denoted $\epsilon$ (or sometimes $\lambda$).

The collection of all words over $\Sigma$ is denoted $\Sigma^*$.

A formal language over an alphabet $\Sigma$ is a set of words over $\Sigma$. Equivalently, a formal language over $\Sigma$ is a subset of $\Sigma^*$.

A regular language over $\Sigma$ is a formal language over $\Sigma$ which is accepted by some DFA.

A regular expression over $\Sigma$ has the following syntax:

$\epsilon$ is a regular expression.
$\sigma$ is a regular expression for all $\sigma \in \Sigma$.
If $r_1,r_2$ are regular expressions then so are $(r_1)^*$, $(r_1+r_2)$ and $(r_1r_2)$.

In practice we don't write all the parentheses. Each regular expression denotes some formal language (you will learn this translation in class). It turns out that a formal language is regular if and only if there is some regular expression denoting it.

If you have any more questions, I recommend reading a textbook which covers regular languages, for example Hopcroft and Ullman.


Is there a designation for this not-quite-exponential time? I've been working and experimenting with an algorithm that may take time $O^*(2^\sqrt{n})$.  Here $O^*(f(n))$ simply neglects all polynomial terms.  I've seen a comment on Scott Aaronson's blog that mentions graph isomorphism algorithms run in this time, too.  Actually, $O(2^\sqrt{n})$.  Is there a designation for this time?

I thought perhaps quasi-exponential may describe it, but I'm wondering if there is already a name/designation for it.

Two useful classes are sub-exponential, $c^{n^\epsilon}$ for $\epsilon \in (0,1)$, and quasi-polynomial, $c^{\log^k n}$ for $k > 1$. (In both cases, $c > 1$.)

The terms themselves sometimes have different meanings. For example, in some contexts "sub-exponential" means $2^{(1-\epsilon)n}$ for some $\epsilon > 0$, and in others it means $2^{o(n)}$.

Since the term "sub-exponential" is loaded, it is better to mention what you mean by it whenever you use it.


Which is the best approach to solve Turing machines exercises? I've this exercise of which I'm not very sure about my solution.

Exercise:

  Define the transition table about a Turing Machine that accepts words
  on the {a, b} alphabet where each a is followed by only two b.

My proposed solution is:

(f stands for transition function)

f(q0, a) = (a, q1, R)
f(q0, b) = HALT
f(q1, a) = HALT
f(q1, b) = (b, q2, R)
f(q2, a) = HALT
f(q2, b) = ACCEPT

I came up with this after thinking in the same way as finite state machines, even if I know are different with respect to Turing Machines (no tape, no reading/writing symbols and no right/left moves).

So, my question is, which is the best way of reasoning when I have to solve these kinds of problems?

Thank for your attention!

There isn't really a "best way of reasoning". Mathematical proof is essentially a creative act and there isn't a straightforward recipe you can follow. I usually find it helps to treat Turing machine construction as a programming problem, which is basically what it is.


Variant of (WEAK) PARTITION with 2 distinct solutions I am interested in the complexity of the following problem:

Input: A list $a_1\leq ⋯ \leq a_n$ of positive integers.

Question: Are there two vectors $x, x'\in\{−1,0,1\}^n$, with at least one $x_i$ and one $x'_i$ non-zero (the subsets must be non-empty), such that
$$\sum_{i=1}^nx_ia_i=0, \sum_{i=1}^nx'_ia_i=0 \text{ and } x_ix'_i=0 \text{ }\forall i.$$
WEAK PARTITION is a variant of PARTITION where we are looking for a partition of a subset of the input, and not a partition of all the integers. This is the reason why we have $\{−1,0,1\}^n$ and not $\{−1,1\}^n$. Note that the subset must be non-empty, it means at least one $x_i$ must be non-zero.

But I am interested in the problem described above where we are looking for two distinct weak partitions.
For example, with $A=(1,2,3,4,5,7,11,11)$, we have $x=(1,0,1,0,0,1,-1,0)$, $x'=(0,1,0,1,1,0,0,-1)$ and for each component $i$ we have $x_ix'_i=0$. It means we have two disjoint subsets of $A$ where there is a weak partition.

There is clearly a reduction from WEAK PARTITION but I suspect this problem to be NP-hard in the strong sense. Do you see any reduction from a problem which is NP-hard in the strong sense ?

Thank you very much.

No such reduction is likely to exist (unless P=NP).  In particular, there's a pseudo-polynomial time algorithm for your problem, so your problem isn't strongly NP-hard (unless P=NP).

The algorithm uses dynamic programming and is a straightforward modification of the dynamic programming algorithm for PARTITION.  Define $f(j,y,z)$ to be 1 if there exists two non-zero disjoint vectors $x,x'$ of the required form such that

$$\sum_{i=1}^j x_i a_i = y, \sum_{i=1}^j x'_i a_i = z.$$

Otherwise, $f(j,y,z)=0$.  Also define $g(j,y)$ to be 1 if there exists a non-zero vector $x$ such that $\sum_{i=1}^j x_i a_i = y$, or 0 otherwise.

Note that $f,g$ satisfy the following recurrence relations:

$$\begin{align*}
f(j,y,z) = &f(j-1,y,z) \lor f(j-1,y-a_j,z) \lor f(j-1,y+a_j,z) \lor f(j-1,y,z-a_j)\\
&\lor f(j-1,y,z+a_j) \lor (g(j-1,y) \land z=\pm a_j) \lor (g(j-1,z) \land y=\pm a_j).\\
g(j,y) = &g(j-1,y-a_j) \lor g(j-1,y+a_j) \lor g(j-1,y) \lor (y=\pm a_j).\end{align*}$$

The base cases are $f(0,y,z)=0$ and $g(0,y)=0$ for all $y,z$.

With this recurrence, evaluate $f(j,y,z)$ and $g(j,y)$ for all $0 \le j \le n$ and all $y,z$ satisfying $|y|,|z| \le a_1 + \dots + a_n$.  Each such value can be computed in $O(1)$ time using memoization / dynamic programming.

Finally, look at the value of $f(n,0,0)$ that you computed.  If $f(n,0,0)=1$, then there is a solution to your problem (i.e., there exists two disjoint vectors $x,x'$ that each represent two disjoint weak partitions).

What's the running time of the algorithm? If the inputs are represented in unary, the number of $f$-values we compute is polynomial in the size of the input, and each $f$-value can be computed in $O(1)$ time using the recurrence relation above.  It follows that this dynamic programming algorithm runs in polynomial time, if the inputs are provided  in unary.


Computer Science and Programming for a complete novice everyone!
I am going to learn mathematics in a university, but it will be rather ''pure'' math, so, I want to get some exposure to computer science on my own. The problem is, I've never tried any programming or computer science activities. I'm not sure where should I start. Now, I realise that internet is full of online or video courses about cs or codes, but they are specific, for example, ''how to learn C++/Python'' or ''algorithms''.
As far as I'm concerned, what I need is some kind of introductory book for computer science( basics, how this and that works and why, what is this and what is that ). Though, some people say that it's better to learn some programming language first even before getting exposed to theoretical material.
Thanks in advance, I will appreciate any answers.

I started progamming as a kid and (at adulthood) graduated in Computer Science. I really don't know what's the best to learn first.

Computer Science is a breed of mathematics and programming is a craftworking. To implement the ideas of the first you must use the second.

IMHO programming is something you learn by demand while CS is a knowledge you study by passion.

The modern languages today (C#, Java, Javascript) are complex tools of trade and one learning it must dive in to learn it idiosyncracies (and not to mention the libraries and frameworks like jQuery, Hibernate, etc).

So while you are not willing to become a pro programmer I can advice you to use more "crude" languages like C||C++.

To get start in CS go to the basics: Algorithms.

There are a lot of classical and well studied problems like sorting, path finding/evalutaion, finding substring, etc.

While studing these problems you can learn how to implement some know solutions again IMHO that's can the best approach to get starting.


CFG for a given languague Give a CFG for the languague L = $ \{ 1^n +1^m = 1^{n+m}| n,m \in N_{0}\} $ , with the alphabet $\Sigma =\{1,+,=\}$.

I am currently trying to solve the given task, I thought a good way is to split the Languague into two more simple languagues, but I am keep failing. May some can help

The idea is to start generating the ones of the first addend from the axiom $S$, while simultaneously adding the corresponding number of ones at the end of the sentential form. Then you have a production from $S$ to non-terminal $A$ which takes care of generating the second added, while still appending ones at the end of the sentential form.

When you are done generating the second addend you can replace $A$ with $=$ in order to split all the ones from the two addends (on the left side) from the corresponding number of ones on the right size.

$$
\begin{align*}
S &\to 1S1 \mid +A \\
A &\to 1A1 \mid \,=
\end{align*}
$$


Why is $\mu$ finite looping? It is said that the intuitive meaning of $\mu$ is finite looping where as the intuitive meaning of $\nu$ is infinite looping in $\mu$ calculus. I understand this for finite systems, but why is this true in general?

Is there any theorem which proves this ?

It is said that the intuitive meaning of μ is finite looping where as the intuitive meaning of ν is infinite looping in μ calculus

Here's a better phrasing: µ is about looping with a known bound on the number of iteration. For ν we do not necessarily know the bound, and there may in fact not even be one.

  Is there any theorem which proves this ?

Theorems can not prove how apt an intuition is. The property you have in mind follows from the definitions and can be illustrated by some examples.


How to detect Farkas or MPEG4 FDP points on image with a face? Brief problem description

I'm using a Basel Morphable Face Model, which was labeled with MPEG4 and Farkas landmarks. I can generate different faces, use different lighting conditions, rotations, perspective etc.

I want to use it to train an algorithm in order to find these landmarks on real pictures further.

More strictly

Given a labeled set of images (with fixed size, if it's critical), I want to get a function $q\left( x \right)$ (where $x$ is an image), which will minimize loss expectation (Bayes' task)

$$E = \sum\limits_{x \in X, k \in K} P\left( k \mid x \right) \cdot W\left( k, q\left( x \right) \right)$$

$k$ is a tuple of feature points' coordinates like $<(x_1, y_1), (x_2, y_2), \dots>$.

Loss function is either

$$W\left(k, k'\right) = \sum\limits_{i=1}^n ||k_i - k_i'||^2$$

or

$$W\left(k, k'\right) = \sum\limits_{i=1}^n(1\; if\; ||k_i - k_i'|| > \Delta\; otherwise\; 0)$$

Maybe there is a better problem description, and loss expectation minimization is not suitable for this task?

Details

I guess, there are more specific algorithms for this issue than Brute Force (estimate probabilities by training set and use them to find landmarks on input images) or Artificial Neural Networks.

Why not ANN: the problem "as is" is incredibly hard. I have $44$ points, most of which have symmetric ones (so, it's something between $60$ and $80$). Given image $100×100$, I have at least $10'000^{60}$ different solutions and should find the best one (or weighted average in case of $l^2$ loss function). $10^{240}$ is a huge number. Add probabilities estimate to this Math carnival, and you'll get a problem of estimating probability function for $10'000$ dependent random variables via each image of the training set. So, if some general approach will work fast, I'm not sure that it will be accurate enough. The new problem will occur — what exactly will we lose when ANN will be applied?

Maybe two-dimensional context-free grammars can solve this, and I just need a proper representation to take scale and rotations into account.

Maybe the problem can be stated in terms of constraint satisfaction problem and solved efficiently.

Question

Which algorithms you can recommend for my purpose?

In the simplified special case where each image $x$ has a single correct labelling $k=\kappa(x)$, this becomes just a regression problem: you want to find a function $q$ that minimizes the risk

$$\mathbb{E}[||q(X)-\kappa(X)||^2],$$

where $X$ is a random variable distributed according to some distribution on faces.  One way to solve this is to build up a training set of pairs $(x_i,k_i)$ where $x_i$ is a face and $k_i$ is its label, and then minimize the empirical risk

$$\sum_i ||q(x_i)-k_i||^2.$$

This then becomes an optimization problem: find parameters for $q$ that minimize the empirical risk.  You could use any of a number of different methods for regression, based on what structure you think $q$ might have.  For instance, you could use a convolutional neural network.

Your problem is a more general version of this, where we want to minimize the risk

$$\mathbb{E}[\ell(X,q(X))],$$

where

$$\ell(x,y) = \int p(k|x) ||y-k||^2 dk.$$

I will assume you have an efficient way to compute $\ell(x,y)$ for any particular $x,y$ (whether by integrating analytically using some expression for $p(k|x)$, or by sampling many $k$ from the distribution $p(k|x)$ and taking the average value of $||y-k||^2$).  If this is the case, one approach is again to build a training set of faces $x_i$, each with a known distribution $p(k|x_i)$, and then minimize the empirical risk

$$\sum_i \ell(x_i,q(x_i)).$$

This is just an optimization problem, where you try to find parameters for $q$ that minimize the empirical risk.  Assuming you have an efficient way to compute $\ell(\cdot,\cdot)$, you can proceed as before and use any standard method for regression (e.g., a convolutional neural network).


Characterizing cycles in a directed graph with optional edges Consider a directed graph in which some edges are marked as "optional". A graph with $N$ optional edges induces a family of $2^N$ graphs depending on which edges are removed. In some cases, some of these graphs may be acyclic while others contain cycles.

For example, consider the graph with vertices $\{1, 2, 3, 4\}$ and edges $\{1 \rightarrow 2,\ 2 \xrightarrow{?} 3,\ 3 \rightarrow 1,\ 2 \xrightarrow{?} 4,\ 4 \xrightarrow{?} 1\}$ where the optional edges are the ones marked with a question mark.

This defines a family of eight different graphs with the same vertices but different sets of edges. If we denote the presence or absence of an edge between vertices $u$ and $v$ as $E(u \rightarrow v)$, then the following Boolean expression describes whether a particular graph in this family in cyclic: $E(2 \rightarrow 3) \vee [E(2 \rightarrow 4) \wedge E(4 \rightarrow 1)]$

Given a particular graph containing some optional edges, I'd like to be able to describe compactly the combinations of optional edges that must be present for the graph to be cyclic without having to specify the entire original graph. In particular, I'd like to know if there is a description whose length is polynomial in the number of optional edges rather than the total number of edges.

More formally: Is there a pair of (ideally efficient) algorithms $P$ and $Q$ such that $P$ takes in a description of a directed graph with $N$ optional edges and produces an "encoded" string whose length is polynomial in $N$, and Q can read in that encoded string and a subset of the $N$ optional edges and determine whether, with those edges present (and the other optional edges removed), the original graph would be cyclic?

Yes, this is doable.  An encoded string of length $O(N^2)$ suffices.

Let me describe how to do it.  Let $V'$ denote the set of vertices that are the endpoints of the optional edges.  Obviously, $|V'| \le N$.  I'll describe the two procedures P,Q below.

Procedure P: Compute reachability information for each pair of vertices in $V'$.  In other words, for each $s,t \in V'$, compute whether $t$ is reachable from $s$ in the original graph (without using any optional edge); the answer is either "yes" or "no".  Note that there are $O(N^2)$ pairs $s,t$, so we can encode the answer to all those questions using $O(N^2)$ bits (one bit per pair $s,t \in V'$).  Let this be the encoded string.  Of course, the length of this encoded string is polynomial in $N$.

In particular, we can think of this encoded string as the representation of a graph $G'=(V',E')$.  $G'$ has vertices $V'$ and has an edge $s\to t$ if and only if $t$ is reachable from $s$ in the original graph (without optional edges).  The length of the encoding of $G'$ is $O(N^2)$, so polynomial in $N$.

Procedure Q: Given a set $S$ of optional edges and the encoded string, here's how we can tell whether adding those edges would create a cycle.  Basically, add every edge in $S$ to the graph $G'$.  (The encoded string tells us $G'$, so we can treat $G'$ as known, i.e., it is one of the inputs to Q.)  Now you can do depth-first search in the resulting graph, $G''=(V',E' \cup S)$, to test whether $G''$ contains any cycle.  $G''$ will have a cycle if and only if adding $S$ to the original graph (without any other optional edges) has a cycle.


Method provided by component may need to be implemented, What does this mean? I can't wrap my head around this statement:

  One common drawback of using composition instead of inheritance is that methods being provided by individual components may have to be implemented in the derived type, even if they are only forwarding methods

It's from here.

I am also not entirely sure what it's saying, but to me, it sounds like this is saying that in inheritance, if e.g. the Dog class already has function bark() { print('woof!')}, then the person writing a GoldenRetriever class which inherits from Dog doesn't need to write a bark method since it's inherited from Dog.

On the other hand, if someone is writing a GoldenRetriever class that contains an instance of Dog inside each instance of GoldenRetriever, you will have to define function bark() { this.dog.bark() }.


Find out duplicate number between 1 to N numbers I first saw this question on this website where I was trying on Java puzzles.

Here is the Question:-

You are given in an ArrayList, 1 to N Numbers. For Example, 1,2,3,4,5. However, one of
the numbers is repeated twice. That is, in the form 1,2,3,4,2,5. Find the duplicate number
without using loops.

I thought that this could be done with 2 For loops, and tried running the program which Worked fine. However, the question specified otherwise. Therefore, I checked the answer, which read as follows :-

int highestNumber = numbers.size() - 1;
int total = getSum(numbers);
int duplicate = total - (highestNumber*(highestNumber+1)/2);
return duplicate;

Here numbers is the List(Java) which contains the elements. The getSum(List n)method returns the sum of all the elements in the List.

Then comes this line which I fail to understand. How does total - (highestNumber*(highestNumber+1)/2); result in the correct Answer?

Edit1: As answered below the formula -  n(n+1)/2 is derived from Arithmetic Progression. More details are here

Here is the question:

You are given a list of length $n+1$ which contains the numbers $1,\ldots,n$, one of them appearing twice (and the rest appearing once).
Find the number which appears twice.

The sum of numbers from $1$ to $n$ is $\frac{n(n+1)}{2}$, so if you subtract that from the sum of the list you get the number appearing twice.


EVEN-CFL Decidable / Undecidable - Rice-Theorem Let EVEN-CFL $=\left\{w | M_{w} \text { is a } \mathrm{TM}, \text { such that } L\left(M_{w} \right) \\ \text{ has only words with even length and is context free.}\right .\}$

Question : Is EVEN-CFL decidable?

Am trying to learn this type of proofs

Now the Rice-Theorem states, that semantic properties that are non-trivial are undecidable.

For this, EVEN-CFL is not a syntactic property of a TM, it's a property of the language and it's non-trivial because there exists languages that are context free and others that are not, like recursive languages or they have the length or not.

Is this right so far? How do I proceed now is this it? The use of the RICE-THEOREM

Thanks

The property of being EVEN-CFL of c.e. languages is not trivial, by Rice's theorem this is not decidable.


Computational complexity vs. Chomsky hierarchy I'm wondering about the relationship between computational complexity and the Chomsky hierarchy, in general.

In particular, if I know that some problem is NP-complete, does it follow that the language of that problem is not context-free?

For example, the clique problem is NP-complete. Does it follow that the language corresponding to models with cliques is of some minimal complexity in the Chomsky hierarchy (for all/some ways of encoding models as strings?)

There are four classes of language in the Chomsky hierarchy:

Regular languages — this class is the same as $\mathrm{TIME}(n)$ or $\mathrm{TIME}(o(n\log n))$ (defined using single-tape machines, see Emil's comment), or $\mathrm{SPACE}(0)$ or $\mathrm{SPACE}(o(\log\log n))$ (per Emil's comment).
Context-free languages — this class doesn't have nice closure properties, so instead one usually considers $\mathrm{LOGCFL}$, the class of languages logspace-reducible to context-free languages. It is known that $\mathrm{LOGCFL}$ lies in $\mathrm{AC}^1$ (and so, in particular, in $\mathrm{P}$), and it has nice complete problems detailed in the linked article.
Context-sensitive languages — this class corresponds to $\mathrm{NSPACE}(n)$.
Unrestricted grammars — this class consists of all recursively enumerable languages.

If a language in NP-complete then assuming P$\neq$NP, it is not context-free. However, it could be context-sensitive (clique and SAT both are). Any language in NP is described by some unrestricted grammar.


Term for most degenerate tree with two children on every inner node I'm looking for the name of a binary tree which is almost degenerate: at least one child of every interior node in the tree is a leaf.

(Image from Penn State course STAT 557, Data Mining, lesson 10.)

This is a binary tree, when by a binary tree we mean a tree where each vertex has at most 2 children. In other words, you have a tree of maximum degree 3. Also, generally a tree that has a dominating path is a caterpillar.


Near Triangulation Planar Graph This is the problem I am dealing with:

Given a set P of n points in general position, let a graph G be defined as follows:

The vertex set is P. Two vertices, a and b, are joined by an edge provided there exists an axis parallel square S with a and b on the boundary and no other point of P in the interior of S.

I need to prove or disprove that G is a near-triangulation where every face except the outerface is a triangle and the outerface is a cycle.

Thanks in advance

An easy contradicting example is three points forming an obtuse triangle. Note that any Axis-parallel square containing $A$ and $B$ on its boundaries, contains $C$ in its interior and hence, the outer face is not bounded by a cycle since $AB$ is not an edge in the graph.


DFA with less states than NFA Is it possible for a DFA to have less states than its equivalent NFA? Number of transitions does not matter. If possible also give an example.

Theoretically yes, that NFA could have 9001 unreachable stats that are completely useless.

If you expect that NFA to be connected (common sense) then if you allow epsilon-moves you can have a huge useless cykle.

If you rephrase your question to:

Lets consider any Language and its 'smallest' (min number of states) NFA with $\epsilon$-moves and its 'samllest' DFA then the answer is no and the reason is simple.

any DFA is also NFA (names does not suggest that though).
therefore if we take a 'smallest' NFA and then manage find equivalent DFA that is 'smaller' that would contradict previous NFA being smallest.


Why does the neural network logistic regression cost function sum for all layers only for lambda? I'm taking Andrew Ng's machine learning course and week 5 covers the training of neural networks. The modified cost function for neural network training is derived from the logistic regression cost function, and is described as follows:

$$\begin{gather*} J(\Theta) = - \frac{1}{m} \sum_{i=1}^m \sum_{k=1}^K \left[y^{(i)}_k \log ((h_\Theta (x^{(i)}))_k) + (1 - y^{(i)}_k)\log (1 - (h_\Theta(x^{(i)}))_k)\right] + \frac{\lambda}{2m}\sum_{l=1}^{L-1} \sum_{i=1}^{s_l} \sum_{j=1}^{s_{l+1}} ( \Theta_{j,i}^{(l)})^2\end{gather*}$$

Here, K is the number of output units, L is the total number of layers in the network, and ${s_l}$ is the number of units in layer l.

I don't understand why the second half of the cost function, intended to prevent over-fitting by minimizing the values of the theta parameters, is summed across the entire network while the first half of the equation which actually determines theta is only for a specific layer. If each layer's cost function already includes a minimization parameter for that layer's theta values, why is it necessary to perform this minimization globally for every layer in the cost function J?

As I understand it, in training a neural network you mainly treat each layer as completely separate from the next (and in fact, that is one of the major selling points of the NN approach, wherein solving L layers independently of one-another lets you use a simple approach to obtain powerful results) - so why are we summing the second half of the equation over all layers?

The first term depends on the output of the entire network, i.e., on all the parameters for all layers, not just a single layer's parameters.

This is an application of the empirical risk minimization framework for training a classifier, with regularization.  The cost function $J(\Theta)$ has the form

$$J(\Theta) = \text{empirical risk} + \text{regularization penalty}.$$

Denote the empirical risk by $R(\Theta)$; it depends on the parameters $\Theta$ (for all layers).  Denote the regularization penalty by $P(\Theta)$; it depends on the parameters $\Theta$ (for all layers).

The empirical risk $R(\Theta)$ is the sum of the loss for each instance in the training set, i.e., it has the form

$$R(\Theta) = {1 \over m} \sum_{i=1}^m \ell(h_\Theta(x^{(i)}), y^{(i)}),$$

where $\ell$ is a loss function, $x^{(i)},y^{(i)}$ is the $i$th instance in the training set, and $h_\Theta(x)$ denotes the output of the classifier on input $x$ when the parameters are $\Theta$.  Note that the output of the classifier depends on all the parameters for all the layers, so $R(\Theta)$ depends on all the parameters for all layers (not just a single layer).

A comment on notation: We use $\Theta$ to denote all of the parameters, i.e., a single vector that concatenates the parameters for each layer.  Here it appears $\Theta^{(l)}$ has been used to denote the parameters for the $l$th layer, so $\Theta = (\Theta^{(1)}, \dots, \Theta^{(L)})$.

In your specific example, we use the cross-entropy loss for $\ell$ (this is also known as the logistic loss function, where there are only two classes).  That's how we get the first term.

Also the regularization penalty $P(\Theta)$ depends on all of the parameters, for all layers; it is a sum of penalties for each layer.

If you work through the math, you'll see how we get something of the form you've shown in the question.  As this answer hopefully makes clear, each term depends on the parameters for all the layers, not just a single layer.


CFG for the language {ω ∈ {a, b}*| in every prefix of ω, the number of a’s is greater than or equal to number of b’s} I know the answer which is:

\begin{align}
S &\rightarrow aS \mid T\\
T &\rightarrow aTbT\ \mid \varepsilon
\end{align}

Now, $bbaaa$ is in the language. But the given CFG cannot generate it. Is it a possible misunderstanding on my end about the prefix's? Can you explain? And if the CFG given is wrong, what is the correct CFG for the language?

Maybe this is the right grammar?

\begin{align}
S &\rightarrow aS \mid T\\
T &\rightarrow aTbS \mid bTaS\ \mid \varepsilon
\end{align}

The string $bbaaa$ is not in the language, as Draconis pointed out (its prefix $b$ contains more $b$'s than $a$'s). As such, the second grammer is wrong.

However, the first suggestion is also wrong. It does not accept the string $abaaaa$, which belongs to the language.

The correct grammar is:

$$S \to \epsilon \mid aS \mid aSbS$$

To see that every word accepted by this grammar indeed belongs to the language, a straight-forward induction proof will do. So let's check that every word where each prefix has at least as many $a$'s as $b$'s is accepted by our grammar.

If the word is empty, we are done. Else it has to start with an $a$. There are two cases.

There is one prefix of the word that has an equal number of $a$'s and $b$'s. Write the word as $awbv$ where $awb$ is the shortest such prefix. Both $w$ and $v$ must belong to the language, so we can use the rule $S\to aSbS$.
Every prefix of the word has more $a$'s and $b$'s. Write the word as $aw$. Then $w$ must belong to the language, so we can use the rule $S \to aS$.


Is a computer equivalent to a Turing machine or linear bounded automata? Till date I have read that a Turing machine can do whatever a computer can.

Wikipedia Turing machine

mentions that since a real machine can have only a finite number of configurations it is equivalent to linear bounded automata.

Is this true?

A machine bounded by $\Theta(1)$ memory is a finite state automaton (As a matter of fact, proving that $\textsf{DSPACE}(\Theta(1)) = \textsf{REG}$ is a classical exercise).

We say that "Turing machines can do whatever computers can" because, as long as we keep in mind that real computers are subject to limitations in computational power, it's more useful to think of computers as imperfect implementations of a universal Turing Machine rather than perfect implementations of a finite state automaton.


Letter Combinations of a Phone Number I came across this problem in the “Elements of Programming Interviews” interview preparation book, and also on the site, leetcode.com (link to problem).

Problem statement – Letter Combinations of a Phone Number

"Given a digit string, e.g., “23”, return all possible letter combinations that the number could represent.  The mapping of digits to numbers is the same as on a telephone number pad.
So for “23”, the combinations are, ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]."

There are plenty of solutions online and in books. However, I’m curious to know about the fundamentals of this problem.

Is this problem essential asking for the Cartesian product of multiple sets? If so, what are some efficient algorithms to compute this? Some solutions reference DFS and BFS. How are DFS and BFS related to this problem (are they possibly referring to the type of recursion being used to solve the problem) ?

Thanks

There are plenty of solutions online and in books. However, I’m
  curious to know about the fundamentals of this problem.

Basically, this problem is trying to reveal your ability to solve problems using recursive algorithms/divide&conquer for generating all possible permutations (brute-force). There are some filtering techniques that can be used in practice, but the worst-case running time is exponential.

  Is this problem essential asking for the Cartesian product of multiple
  sets? If so, what are some efficient algorithms to compute this?

Yes, one way to look at the problem is 'Cartesian product of multiple sets'. Given a string S, you can consider two sets a[i] and b[i], where a[i] is the set of character strings that can be made by substring S[1:i], and b[i] is the set of character strings that can be made by substring S[i+1,end]; then output the Cartesian product of a[i] and b[i] for every possible i.
However, this algorithm is not the best one.

  Some solutions reference DFS and BFS. How are DFS and BFS related to
  this problem (are they possibly referring to the type of recursion being
  used to solve the problem) ?

These algorithms use DFS for its recursive nature. Probably, it uses BFS to avoid stackoverflow.


What is the distribution of Garden of Eden patterns in cellular automata with increasing pattern size? In a given cellular automaton, such as Conway's Game of Life, is there anything known about how many Garden of Eden patterns there are by pattern size? Say, pattern size is n x n, what's the likelihood that a random pattern is a GoE as n increases?
Also, by the Garden of Eden-theorem, only cellular automata which are non-injective, that is, for which a given pattern may have more than one predecessor, contain Gardens of Eden.

Is it then in general impossible to see whether a given cellular automaton pattern at some time-step is derived from a GoE (since there could also have been a non-GoE ancestor leading to the same state)? That is, does the evolution of the CA 'wash out' the information that it is derived from a GoE? (I hope it's sufficiently clear what I mean.)

Furthermore, is there a relation between GoE-patterns and uncomputability/undecidability? It seems to me that if you consider the CA to be implementing some computation, then the GoEs are 'outputs that could never be produced', at least heuristically, but a brief Google search led nowhere. Perhaps asked another way, is there a relation between the existence of GoEs and the universality of a CA? I know Life is both universal and has GoEs, but I don't know about the general case. Any pointers would be much appreciated.

Having done some additional reading, I think I can strike out the third question: since reversible cellular automata that are computationally universal exist (according to wiki), there doesn't seem to be any connection between computational universality and GoEs. Now, what about universal constructors? Are there reversible universal constructors? Von Neumann's original rule happens not to be reversible, and in fact, has GoEs, but again, this need not say much.
The wikipedia page above mentions a way to emulate d dimensional irreversible CAs within d + 1 dimensional reversible ones, which readily establishes the computational universality of the latter, but I'm not sure if this holds as well for universal construction: the emulated constructor would only construct patterns on a d-dimensional sub-grid of the automaton (?).

as said by vzn, any pattern containing a Garden of Eden pattern is itself a Garden of Eden Pattern, the probability that a random nxn pattern is actually GoE goes to 1 as n goes to infinity (in the case of a non-surjective CA of course, otherwise it's 0). More precisely, it is lower bounded by $1 - \alpha^{n²}$ for some $0<\alpha<1$.
Indeed, consider a fixed GoE pattern P of size $k\times k$, then the probability for a random pattern of size $n\times n$ to be a GoE is at least $1 - (\frac{1}{q^{k^2}})^{(\frac{n}{k})^2}$, where $q$ is the number of states of the CA.
you can generate all the possible pre-image of a given pattern in finite time and you can also test whether a pattern is a GoE so your problem is clearly decidable. It's polynomial-time decidable in 1D and NP-hard in 2D.

in the 1D case, a CA can be seen as a finite state transducer. So the language $L_{GoE}$ of all GoE patterns is a regular language because it is the complement of $T(Q^\ast)$ (where $T$ is the transducer and $Q$ the set of states of the CA) which is itself a regular language as the image of a regular language by a transducer. Then $T(L_{GoE})$ is also regular and its the set you asked.
in the 2D case, I think we can show that it is NP-hard using the classical simulation of Turing machines by Wang tiles. The rough idea is the following. Consider any NP-complete problem $L$ and take a Turing machine $T$ which is a polynomial time verifier for the problem. Then construct a CA that basically checks that the input, if written in some special alphabet $A$, encodes a successful computation $T(x,y)$ of $T$ working on input $x$ and witness $y$. If so erases everything with a special state $a\not\in A$, but keep the input x. If some error is detected produce some special state $b\not\in A$. Finally, the CA does nothing on states which are not in $A$. Now consider a pattern formed by an input $x$ surrounded by many $a$. The pattern as always itself as a preimage, but it as a GoE preimage if and only if there is some $y$ such that $T(x,y)$ says "yes", i.e. iff $x\in L$. CQFD
At the time of writing I don't see how to prove that the problem is NP

as pointed-out Turing-universality is still possible without GoE patterns (in reversible CA for instance). But intrinsic universality requires GoE patterns. This comes from the fact that, first, a surjective CA only admits surjective CA as subautomata, and, second, grouping and iterating a CA doesn't change its surjectivity.


Alpha-Beta Pruning with simultaneous moves? I have a game I'm building some ai for that has 2 players making simultaneous moves.  In this game there is exactly one move where, if they both make it at the same time, the outcome is different than if they'd made it separately (all other moves are pretty independent).

Anyway, I'm trying to find a good algorithm to throw at it.  Minimax with alpha-beta pruning seems like it would be a good candidate if the players were making alternating moves, but not for simultaneous ones.  I found a paper(pdf) on the topic, but it's a little over my head- I'm having trouble reading the pseduocode.

So, can someone either help clarify that approach, suggest another way to accomplish alpha-beta pruning on such a game, or suggest a better algorithm entirely?

The thing is that with simultaneous moves, the optimal strategy is harder to guess, because you need to compute something that is not always obviously winning.

Have a look at Nash equilibrium and the prisoner's dilemma if you don't know them yet. This is the kind of reasoning that you will need each time you are considering two simultaneous moves, instead of simply choosing a move that goes into a winning configuration in games with non-simultaneous moves. The concept of dominance replaces the concept of winning.

The algorithm in your reference does that when referring to figures 4 and 5 but first try to figure out what those figures are supposed to do before understanding how they do it.


If we can simulate $NP$-machines why isn't it trivial that $NP=coNP$? I'm looking at some proof that shows $NP^{NP\cap coNP} = NP$.

Let's consider the non-trivial direction. Consider $L\in NP^{NP\cap coNP}$. Then, there's an $A\in NP\cap coNP$ such that $L\in NP^A$.

Since $A\in NP\cap coNP$, there're two machines $M_A$ and $M_{\overline A}$ to decide $A$ and $\overline A$, respectively.

Also, there's a machine $M_L$ to decide $L$ which uses an oracle of $A$.

Let $M$ which acts in the following manner:

Act as $M_L$.
instead of querying the oracle:
simulate the query on $M_A$
simulate the query on $M_\overline A$
write on the result tape the proper result and proceed

I don't understand few things:

How do we simulate $M_A$ and $M_\overline A$ exactly?
If we can do the above then why both $M_A$ and $M_\overline A$ are needed? (just simulate one of them to infer if $x\in A$ or not)
Finally, as a consequence of #2, we could infer that $NP=coNP$

I'd be glad for clarifications since this questions bothers me a lot and clearly, I'm missing something crucial of how those machines are simulated.

When we say "Simulate $M_A$ on the query string $s$", we simply mean execute $M_A(s)$. Note that you construct a non-deterministic machine for $L$, thus you are able to simulate other non-deterministic machines. If both $M_A(s)$ and $M_{\overline{A}}(s)$ output $0$, then stop and reject $x$ (the initial input). Only when one of the machines outputs $1$, you can be sure about whether or not $s\in A$, and can continue simulating the oracle machine for $L$.

Note that this newly constructed non-deterministic polynomial time machine, $M(x)$, may accept its input $x$ only in computations where for each query $s$ raised during the computation, either $M_A(s)$ or $M_{\overline{A}}(s)$ output 1. Using this observation, you can simply show that $M$ indeed decides $L$.


How does the Weibull distribution work as fault model in wireless sensor networks? I am a little bit confused with the concept of using the Weibull distribution or other distribution for fault model. As I understand, in simulation this distribution is often used for modelling a fault in components.

On the other hand when designing systems we often assume some components might become faulty and we use fault detection method to know where the distinct component is faulty or not.

I want to categorize faulty sensor in 5 groups: transmitter circuit/battery condition/micro controller/receiver circuit and sensor circuit fault and correlated these kinds we can have different attribute in network.

The question is, how can i write the Weibull distribution function to produce these kinds of fault in a wireless sensor networks?

Step 1: Fit a Weibull distribution to all transmitter circuit faults (with one set of parameters).  Fit a Weibull to battery condition faults (with another set of parameters).  You get five different Weibull distributions.

Step 2: During simulation, randomly draw one number from each of the Weibull distributions.  This gives you the time until the first transmitter circuit fault, the time until the first battery condition fault, and so on.  Pick the smallest number; that's the fault that occurs first.  Simulate a fault of that type, at that time.  (You can continue the simulation to simulate multiple faults if you want.)


Prove or disprove, If A ≤p B and B is NP-hard, then A is in NP-hard Intuitively if A can reduce to B, and B is NP-Hard, A might be NP Hard but maybe not. If there is a way to solve A that does not involve reducing to B, it might be faster.

How do I formally disprove this statement using a counter example or some well known algorithms, or using some other technique?

Let A be the empty language. It is trivially reducible to, say 3SAT: transform any input into the formula $a \land \lnot a$. But only the empty language is reducible to the empty language, thus A is not NP-hard.

If P = NP, then any nontrivial language is NP-hard, thus it will be really hard to find counterexamples where both A and its complement are nonempty.


Are universal types a sub-type, or special case, of existential types? I would like to know whether a universally-quantified type $T_a$: $$T_a = \forall X: \left\{ a\in X,f:X→\{T, F\} \right\}$$ is a sub-type, or special case, of an existentially-quantified type $T_e$ with the same signature: $$T_e = \exists X: \left\{ a\in X,f:X→\{T, F\} \right\}$$

I'd say "yes": If something is true "for all X" ($\forall X$), then it must also be true "for some X" ($\exists X$). That is, a statement with '$\forall$' is simply a more restricted version of the same statement with '$\exists$': $$∀X, P(X) \overset?\implies ∃X, P(X).$$

Am I wrong somewhere?

  Background: Why am I asking this?

  I am studying existential types in order to understand why and how "Abstract [Data] Types Have Existential Type". I cannot get a good grasp of this concept from theory alone; I need concrete examples, too.

  Unfortunately, good code examples are hard to find because most programming languages have only limited support for existential types. (For instance, Haskell's forall, or Java's ? wildcards.) On the other hand, universally-quantified types are supported by many recent languages via "generics".

  What's worse, generics seems to easily get mixed up with existential types, too, making it even harder to tell apart existential from universal types. I'm curious why this mix-up occurs so easily. An answer to this question might explain it: If universal types are indeed only a special case of existential types, then it's no wonder that generic types, e.g. Java's List<T>, can be interpreted either way.

First, from a mathematical point of view, $\forall x:T, P(x)$ does not imply $\exists x:T,P(x)$. The implication holds if and only if $T$ is not empty. However, in programming languages, it is uncommon to deal with empty types (though it happens).

Still from a mathematical point of view, even when $(\forall x:T, P(x)) ⇒ (\exists x:T, P(x))$, the two are not the same. If you give types a set semantics, then $T_a$ is a superset of $T_e$, not the same type. (Actually it's not a superset; it's close to isomorphic to a superset.)

Let's get closer to programming language theory and see what these types actually mean. $T_a = ∀X.\{a: X, f: X\rightarrow\mathsf{bool}\}$ is a universal type: if you have a value $A$ of that type, you can construct $A(M)$ for any $M:X$. In particular, if you have $M_1$ and $M_2$ both of type $X$, you can construct $A(M_1)$ and $A(M_2)$. In essence (and possibly in effect, depending on the language) $T_a$ is a function from types to terms. As such, the universal type provides type parametrization: one value working for all types. Universal types are at the heart of polymorphism.

The existential type $T_e = \exists X.\{a: X, f: X\rightarrow\mathsf{bool}\}$ is quite a different beast. Given a value $B$ of type $T_e$, there is only one term $N: X$ such that $\pi_1(B) = N$, and for this term $\pi_2(B) = \{a:N, f:N\rightarrow\mathsf{bool}\}$. The existential type provides a way to hide the nature of $N$; it's saying, “There exists a type! But I won't tell you which!”. As such, the existential type provides type abstraction: one specific hidden value. Existential types are at the heart of module systems.

Don't get mislead by Haskell's forall: despite its name, it's a form of existential quantifier.

For background, I strongly recommend Types and Programming Languages (chapters 23 and 24 discuss universal types and existential types respectively). It's will provide useful background to understand research articles.


How does pre-training help with semantic segmentation with U-net I am working with a u-net, a variation of the more commonly known fully convolutional network for semantic segmentation. For training a u-net, I was given the suggestion that I should use a pre-trained network. But, I'm not quite sure how this makes sense.

My understanding is, in pre-training, we freeze the network up to the final classifying layers from a pre-trained network and then, we initialize random weights for the classifying layers. Then, we take our new dataset and retrain the weights through the whole network. Basically, we don't have random initialized weights for the convolutional blocks.

Now, if I'm using something like the u-net which has a very unique structure, how exactly would I do this pre-training with something like vgg16? The only thing I can think of is to share the feature maps during the upsampling layers but that's about it and that's not really pre-trained weights.

The procedure you described is how to do fine-tuning of a network for object classification.  There are two standard techniques: (1) freeze all but the last few layers, replace the last layers with new layers of the appropriate size and random weights, and train them; or (2) train all of the layers, starting from the weights of the pre-trained model as your initial weights, but use a very low learning rate.  You can also do (1) then (2).  See https://datascience.stackexchange.com/q/28383/8560 for a nice overview.

I'm not an expert on u-nets, but it appears they are used for image segmentation rather than object classification.  Therefore, the same approach of freezing the last few layers probably isn't suitable here.  You can still use method (2), i.e., fine-tuning using stochastic gradient descent with a very low learning rate.  If your task is similar enough to the task the pre-trained network was trained for, that might be effective.

I can't see any way to use a pre-trained model for object classification (like VGG16), as they use a different architecture.  Rather, you'd probably have to start with a pre-trained model for segmentation (i.e., a pre-trained U-net model).  The U-net paper says that they make pre-trained models available on their website, which perhaps you could use as a starting point.


Recurrence relation (not solvable by the master theorem) Consider the following recursion:
$\begin{cases}
T(n) = 2T(\frac{n}{2}) + \frac{n}{\log n} &n > 1 \\
         O(1) &n = 1
\end{cases}$.

The master theorem doesn't work, as the exponent of $\log n$ is negative. So I tried unfolding the relation and finally got the equation:
$T(n) = n[1 + \frac{1}{\log(\frac{n}{2})} + \frac{1}{\log(\frac{n}{4})} + ... + \frac{1}{\log(2)}]$.

I do not know how to simplify (inequalities to use???) from here. A trivial method would be to assume that all reciprocal of the log terms are $< \frac{1}{\log(2)}$, and since there are $\log n$ terms, the summation of all the reciprocal-log terms is $< \frac{\log n }{\log(2)} = \log_2 n$, which gives $T(n) = O(n \log n)$. However this is a very poor approximation, as by the master theorem we can check that the time complexity for the recursive relation $T(n) = 2T(\frac{n}{2}) + n$ is $O(n \log n)$. Can someone find a tighter correct upper bound?

Wikipedia has a slight extension of the master theorem which covers your case: case 2b here.
For the recurrence $T(n)=aT(n/b)+f(n)$ where $f(n)=\Theta(n^{\log_b a}/\log n)$, it gives $T(n)=n^{\log_b a}\log\log n$.


Find all intervals that overlap with a given interval Note: I moved this question from stackoverflow.com

I have an algorithmic problem where I would like to see if it can be solved in better than $O(n)$:

I have given a table $T$ of $n$ elements where each element is a tuple $(s_i, e_i)$ with $s_i, e_i \in \mathbb{N}$ and $s_i < e_i$, i.e. each tuple is some kind of an interval. I have to find all intervals that overlap with a given interval $[t_0, t_1]$ with $t_0, t_1 \in \mathbb{N}$ and $t_0 < t_1$. Further, I have available two sorted lists $S$ and $E$, containing the $s$ values, or $e$ values respectively, together with the index $i$ pointing to the respective entry in $T$. The lists are sorted by $s$ values, or $e$ values respectively. (Let's assume both, $s$ and $e$ values, are unique.)

Problem:

We have to find each interval/tuple $(s_i, e_i) \in T$ where $s_i \leqslant t_1$ and $e_i \geqslant t_0$.

My thoughts so far:

We can exclude some elements by either applying one of the interval boundaries, i.e. searching $t_1$ in $S$ or $t_0$ in $E$. This gives us a list $L$ of remaining elements:
$$
    L \leftarrow \{e \in E \mid e \geqslant t_0\} \text{ or } L \leftarrow \{s \in S \mid s \leqslant t_1\}
$$
However, there is no lower bound on the number of elements in $L$, no matter which search we perform. Further, we have to check every element in $L$ if $s \leqslant t_1$, or $e \geqslant t_0$ respectively depending on which search we performed before.

The complexity for this solution is $O(n)$.

However, let's say that $k$ is the maximum number of elements overlapping with interval $[t_0, t_1]$. If we assume $k \ll n$, then the complexity is $O(n/2)$ since we can exclude at least $n/2$ elements by choosing the appropriate search for $L$. Still $O(n/2)$ is in $O(n)$.

Can you think of a better approach to solve this problem?

For record:

The complexity for finding all intervals overlapping with a certain given interval using an interval tree is $O(\log n + k)$ where $k$ is the number of overlapping intervals. However, in my practical case I am using a MySQL database which provides index trees for each value, i.e. $s$ and $e$, separately. This way I can not find overlapping intervals in less than $O(n)$. I would need to create an interval tree which is a search tree that stores both interval boundaries, i.e. $s$ and $e$, in a single data structure. The complexity for constructing the interval tree is $O(n \log n)$. [http://www.dgp.utoronto.ca/people/JamesStewart/378notes/22intervals/]

I believe that interval trees offer a solution to your problem.  Basically, you store your intervals in the interval tree data structure; then, to find all intervals that overlap with $[t_0,t_1]$, you do a query into the interval tree.  This should solve your problem and run faster than $O(n)$ time.


What is the branch of Computer Science that studies how Anti Virus programs work? It is a trivial exercise in finite automata to show that there is no algorithm that can detect all the viruses, yet there are many software companies selling Anti Virus Software.

Is there any part of CS that deals with Viruses and Anti Viruses ?

PS : I am not asking about non CS related justification of to have AV or not, but only what category/subject within CS they come under, if any. If AV is not a subject within CS then that is also an acceptable answer, are there any refrences within CS context to Viruses and AV's?

There is a subarea of computer security called Computer Virology. The Journal of Computer Virology is devoted to the topic. Studying how anti-virus software works only scratches the surface of what the area is about.

For instance,  there is even some work applying logic to malware: A General Definition of Malware by S. Kramer and J.C. Bradfield. Journal of Computer Virology (6) 2010.


Reduction and decidability Consider the following language: $$ L = \{ \langle M \rangle \ |\ M \text { accepts } w \text { whenever it accepts } w^R \}$$

I am trying to understand the following proof that this language $L$ is undecidable.

The proof proceeds by contradiction, by reducing to $L$ the language  $A_{TM}=\{\langle M,w \rangle\mid M\text{ accepts }w\}$ known to be undecidable. It goes as follows:

Suppose that $L$ is decidable, then there's a TM $M_L$, that decides $L$

Thus we can build $M_{ATM}$ to decide $A_{TM}$ as follows:

Let $\langle M, w \rangle$ be an input for $M_{ATM}$.
Construct a machine, $M_1$ which on input $x$: Simulate $M$ on $w$; if $M$ rejects $w$, $reject$.  If $M$ accepts $w$, $accept$ if $x=01$, $reject$ otherwise.
Simulate $M_L$ on input $\langle M_1 \rangle$.
$accept$ if $M_L$ rejects. $reject$ otherwise.

Since $A_{TM}$ is not decidable, we have a contradiction, which implies that $L$ cannot be decidable.

However there is a point of the proof I do not understand.

My question is: What happens if $M$ gets into a loop on some $w$?

In this reduction of $A_{TM}=\{\langle M,w \rangle\mid M\text{ accepts }w\}$ to $L$, what matters in the construction of the Turing machine $M_1$ is  that the language accepted by
$M_1$ is $\{01\}$ iff $M$ accepts $w$, and is $\emptyset$
otherwise.

Whether $M$ does not halt on input $w$, or halts rejecting it, does not make any difference. In both cases, the language accepted by $M_1$ is  $\emptyset$, thus satisfyiing the definition for $L$. Hence $M_L$ will accept $\langle
M_1 \rangle$, so that $M_{ATM}$ will reject.


Would it be possible for a new technology to make RAM obsolete? If a new technology is invented for storage devices, which is the same as or speeder than RAM (bandwidth&lanecy), is it possible to make RAM obsolete and consider the storage device as the main memory?

if that happened data and program would run directly from the storage device, or the RAM or its concept (especially as temporary space) must be part of the storage device such as at the beginning addresses.

There is nothing special about RAM. Before electronic computers were invented, mechanical data sorters and tabulators used punched cards as their main (and only) memory. Early electronic computers used many different technologies for their main memory, including vacuum tubes, acoustic delay lines filled with mercury, the screen of a cathode ray tube and tiny rings of magnetic material looped around wires. If a memory technology was developed that was just as reliable as solid-state RAM and at the same time significantly faster and/or cheaper then it could certainly replace RAM and make it obsolete.


"Combinational" Decision Graph - Cheapest search algorithm I have a special kind of decision graph, where Multiple decisions must be made in combination, to accomplish the path. Not sure if Multiobjective or Combinational is the right term here, let me know if there is a better one.
Picture better then words:

We have:

Joining Nodes (e.g. "Start") which joins decisions or costs nodes together - meaning solution path MUST cover all edges of joining nodes.
Decision Nodes (e.g. D1,D2,...) and Decision Edges (aka "local solution" - e.g. D1-1, D1-2,...) each solution path may cover only one of the edge of a decision.
Costs Nodes - (e.g. 3,7,5...) that have cost/reward applied to the Paths that cover it. Technically any node even decision or joining can have costs associated. COSTS MAY BE NEGATIVE.
Solution Path - goes from a starting node and must cover all edges of connected joining nodes and only one edge of each decision node it meets

Green is the cheapest Path for this example (D1-2,D2-1,D3-1) that you can calculate yourself empirically or combining all possible combinations and sorting by total costs. Total costs of Green path is $5.

Constraints:

Costs may be negative - in this case it's a reward.
Cycles are possible - they must be resolved as invalid path.
Decisions are NOT binary

Goal:

Find the best (BigO runTime) algorithm to find cheapest path covering this kind of graphs (without iterating all possible combinations and calculating its costs)? Pseudo code would help. Also what is the name of such type of decision graph?

Your problem is $\mathcal{NP}$-hard, by reduction from $\mathcal{3SAT}$. Let $\Phi = \phi_1 \wedge \dots \wedge \phi_m$ be a CNF formula with variables $V = \{x_1, \dots x_n\}$. Let $\mathcal{L}(V)$ be the set of literals of $V$. Let joining nodes, decision nodes, cost nodes be defined as in your question.

For each $x_i$, we create four cost nodes $t_i$, $f_i$, both with cost $1$, representing an assignment of, respectively, true and false to $x_i$. Let $S$ be the set of all such nodes.

Let $\phi_i = \psi_{1i} \vee \psi_{2i} \vee \psi_{3i}$ be a clause with $\psi_{1i}, \psi_{2i}, \psi_{3i} \in \mathcal{L}(V)$. Without loss of generality, we may assume that $\psi_{1i}, \psi_{2i}, \psi_{3i}$ are literals obtained from different variables. Of the eight possible assignments of truth values to those variables, seven satisfy $\phi_i$. For each of those assignments, we create a joining node $c_{ki}$, which has as a successor every node $s \in S$ corresponding to the values relative to such assignment. For example, if the $k$-th assignment were "$x_\alpha$ true, $x_\beta$ false, $x_\gamma$ true", $c_{ki}$ would have $t_\alpha, f_\beta, t_\gamma$ as successors. Finally, we create a decision node $d_i$ with successors $c_{1i}, \dots, c_{7i}$ and let the starting node have as successors each of the $d_i$.

Now, observe that any solution path in the decision graph that we have built has weight at least $n$. In fact, whenever we encounter a fresh variable $x_i$, we are forced to take either $t_i$ or $f_i$, both of which have cost $1$. Furthermore, any path with cost not exactly $n$ has taken, by the pigeonhole principle, both $t_k$ and $f_k$ for some $k$, which means that it does not correspond to a consistent assignment of truth values to the variables of $V$.

On the other hand, an assignment of truth values to variables that satisfies $\Phi$ corresponds to a path of weight exactly $n$ (choose $t_i$ for every variable $x_i$ set to true, $f_i$ for every variable $x_i$ set to false, follow every arrow in the opposite direction).

We conclude that determining the optimal path is at least as hard as $\mathcal{3SAT}$, and consequently, as every problem in $\mathcal{NP}$.

As always with $\mathcal{NP}$-hard problems, your choice is to go with either heuristics or approximation schemes. If I may make a suggestion, problems like this are a good fit for logical programming tools, such as CSP/ASP.


In general, does $f(g)$ and $f(h)$ have the same time complexity? I thought about this question while looking at a textbook where it wanted me to compare the time complexity of $\lg^*(n)$ and $\lg^*(\lg(n))$

Now it is well known that $\lg^*$ is a tremendously slow growing function, so what is inside of $\lg^*$ shouldn't contribute to its complexity.

But is it true in general that any $f(g)$ is $O$-equivalent to $f(h)$ where f is a non constant function?

No, $f \circ g$ and $f \circ h$ (to use the standard mathematical notation) do not in general have the same complexity. For example, take $g(x) = 1$ (constant function) and $h(x) = x$ (identity function). Then $(f \circ g)(x) = f(1)$ and $(f \circ h)(x) = f(x)$; these functions only have the same complexity if $f = \Theta(1)$ (i.e. $f$ is asymptotically constant). This shows that the only functions $f$ for which all functions of the form $f \circ g$ have the same complexity are the ones that are asymptotically constant.

With the example $f = \lg^*$, growth is very slow, so a lot of functions “collapse” when you plug them into $\lg^*$. Nonetheless it is easy to cancel this collapse: define the function $e(y) = \min\{x \mid \lg^*(x) \ge y\}$. This is essentially an inverse function for $\lg^*$ (growing by $1$ at increasingly long intervals). With this you can easily construct functions that grow at any rate you like: $f(e(x)) \approx x$, $f(e(x^2)) \approx x^2$, etc.

(N.B. In my mathematical statements, I assume functions from $\mathbb{N}$ to $(0,\infty)$.)


NP-Hardness reduction I have a problem $\Pi_1$ that I want to show that is NP-hard. I know that I must find an NP-hard problem $\Pi_2$ and a polynomial time reduction $f()$ from instances of $\Pi_2$ to $\Pi_1$ such that $I_2$ is an Yes-instance of $\Pi_2$ iff $I_1=f(I_2)$ is an Yes-instance of $\Pi_1$.

What if I find a (constant sized) family of reductions $f_i()$ such that $I_2$ is an Yes-instance of $\Pi_2$ iff at least one $f_i(I_2)$ is an Yes-instance of $\Pi_1$? Is this enough? Is there a way of translating this one in the "classical" definition? How to formalize this?

I know that in the second situation I can say that I can't solve $\Pi_1$ in polynomial time unless P=NP, but I'm no sure that is equivalent of saying that $\Pi_1$ is NP-hard.

NP-hardness is usually defined using many-to-one reductions, for various reasons, for example to separate NP from coNP (there was some question about it either here or in cstheory). What you're describing is a specific case of more general Turing reductions, which is more common in classical recursion theory, and it is natural since it has the consequences you mention. Unfortunately, the definition of NP-hardness requires a many-to-one reduction.


$TSAT$ is $NP$-complete In "Computational Complexity" by Arora and Barak they state that the following is $NP$-complete:

$\{ \langle \alpha, x, 1^n , 1^t \rangle : \exists u \in \{0,1\}^n \text{ s.t. } M_{\alpha} \text{ outputs } 1 \text{ on input } \langle x,u \rangle, \text{ within } t \text{ steps} \}$.

They call this language $TSAT$.

I am trying to check the "complete" part of the claim.

Suppose $L \in NP.$ By definition, there is a polynomial $p$ and poly-time TM $M$ such that $\forall x \in \{0,1\}^*,$ we have $$x \in L \iff \exists u \in \{0,1\}^{p(|x|)} \text{ such that } M(x,u)=1.$$
Let $t()$ be the polynomial in which $M$ runs, and let $\alpha$ be the TM $M$ represented as a binary string. Then I think this mapping reduction $f$ works: $$f(x) = \langle \alpha, x, 1^{p(|x|)}, 1^{t(|x|)} \rangle.$$

My two questions are:

1) Is this correct?

2) If it's correct, how do we know that $f$ is computable? Just because some verifier $M$ exists, how do we guarantee that $f$ can "compute" it? Or is $M$ "hardcoded" in the Turing machine that is used to compute $f(x)$ from $x$?

It's not correct. As you said, you cannot prove $f$ is polynomial-time computable.

However, you can reduce from a particular NP-complete language, for example, 3SAT. Now $f$ is polynomial-time computable as you can easily write a verifier for 3SAT.


Where does 1.3606 approximation ratio come from for vertex cover approximation? I was watching a coursera video on Approximation algorithms and I understood the 2-approximation algorithm.

Later, the professor asks if we can do any better. The lecturer went on to say that computing 1.3606 approximation is NP-hard in the following words at 8:14.
Here's the transcript for that part.

Actually, what is also interesting to note is that okay, maybe we still have some hope that we can get a little bit below two for the approximation ratio, but as the second staple that you see here shows is that it's not possible to get really close to one, but it's impossible to get something better than roughly 1.3, because already computing a 1.36 approximation as you see here, already that problem is NP-hard.

How does he skip from nobody found a 1.99-approximation algorithm
to getting 1.3606 is NP-Hard?
Where does 1.3606 come from?

The fact that nobody found a $1.99$ approximation doesn't necessarily mean that the problem of finding one is $\mathsf{NP}$-hard (e.g., it might be the case that that $\mathsf{P} \neq \mathsf{NP}$ and a polynomial-time $1.99$-approximation algorithm exists, we are just unaware of it).
Additionally, we can prove that finding a $1.3606$-approximation is a $\mathsf{NP}$-hard problem, i.e., if $\mathsf{P} \neq \mathsf{NP}$ no $1.3606$-approximation algorithm exists. This is not a direct consequence of the previous fact, but a separate result by Irit Dinur and Samuel Safra. The details can be found here.


Minimum number of comparisons in comparison-based sorting algorithms I've seen that every comparison-based sorting algorithm must perform at least $\log_{2}(n!)=\Omega(nlog(n))$ comparisons on some input (n being the size of the input).

Why is the minimum number of comparisons $\log_{2}(n!)$, and how is the omega-notation bound calculated?

Suppose the input array has $n$ elements. The goal of the sorting algorithm is to compute a permutation of $\{1,2,\ldots,n\}$ - the permutation needed to sort the input.  Let $A$ be the set of these $n!$ permutations.

Similar to the "guess my number" game (or the game of 20 questions), each comparison can reduce the search space by a factor of at most $2$.  For example, after the first comparison is made, one obtains a partition $A= A_1 \cup A_2$, where $A_1$ is the set of permutations in $A$ that are consistent with the comparison and $A_2$ are the remaining permutations.  The search space for the output is now restricted to $A_1$.  In the worst case, the size of $A_1$ would be larger than that of $A_2$, and so each comparison reduces the size of the search space by a factor of at most $2$. After each comparison is made, the search space is restricted further to those permutations which are consistent with all the comparisons made so far.

Hence, the number of comparisons required to reduce the size of the search space from $n!$ to $1$ is at least $\log_2(n!)$.  The product $1 \times 2 \times \cdots n$ is at least the product of the last $(n/2)$ numbers, which is $(n/2)^{n/2}$, and is at most $n^n$.  Thus, $\log(n!)$ is sandwiched between $(n/2) \log (n/2)$ and $n \log n$, both of which have the same asymptotic growth rate $\Theta(n \log n)$.


Find value of $a$ or $b$ of two XOR equations Is it possible to find $a$ or $b$ given that $a \oplus b = c$ and $c \oplus b = a$ when I only have the value of $b$?

No. $a\oplus b = c$ and $c\oplus b = a$ are just rearrangements of the same equation, since

$$a\oplus b = c \iff (a\oplus b)\oplus b = c\oplus b\iff a=c\oplus b\,.$$


What does it mean for something to be $\prod_x^y$-complete or $\sum_x^y$-complete? I'm having trouble understanding the definitions for complexity classes in the arithmetic heirarchy, and because of the naming schemes, "Googling" things is somewhat difficult.  Can anyone provide me concrete examples of what it means for something to be $\prod_x^y$-complete or $\sum_x^y$-complete, and when we can say that a problem is undecidable for some $(x,y)$?

The search term you're looking for is "arithmetical hierarchy".
The arithmetical hierarchy
All of the following relates to the logical language of Peano arithmetic. The operations available to us are the unary successor function $S$, the constant $0$ and the binary relation $=$, all with the usual, obvious meanings.  Variables range over the natural numbers.
In the notation $\Sigma_n^m$ or $\Pi_n^m$,

$\Sigma$ denotes a formula equivalent to one in prenex normal form with an existential quantifier outermost;
$\Pi$ denotes a formula equivalent to one in prenex normal form with a universal quantifier outermost;
$n$ denotes the number of quantifier blocks;
$m$ denotes the kinds of objects being quantified.

A formula is in $\Sigma_0^0=\Pi_0^0$ if it contains no quantifiers.  A formula is in $\Sigma^0_{n+1}$ if it is equivalent to one of the form $\exists x_1, \dots, \exists x_k\,\varphi$, where $\varphi\in\Pi_n^0$. A formula is in $\Pi^0_{n+1}$ if it is equivalent to one of the form $\forall x_1, \dots, \forall x_k\,\varphi$, where $\varphi\in\Sigma_n^0$.
All of the quantifier aboves are first-order: they range over the natural numbers.  Call the natural numbers "level $0$" objects and define level-$(m+1)$ objects to be sets of level-$m$ objects (or, equivalently, functions from level-$m$ objects to $\mathbb{N}$).  $\Sigma_n^m$ and $\Pi_n^m$ extend the definition of $\Sigma_n^0$ and $\Pi_n^m$, respectively, by allowing quantification over objects at any level between $0$ and $m$, inclusive.
Completeness
So far, we've only talked about formulae but a set $X\subseteq \mathbb{N}$ is said to be in $\Sigma_n^m$ if there is a formula $\phi(x)\in \Sigma_n^m$ with one free-variable such that $X = \{x\mid \phi(x)\text{ is true}\}$; similarly for $\Pi_n^m$.
Completeness just means what it always means. A set is complete for $\Sigma_n^m$ if it's in $\Sigma_n^m$ and every other set in $\Sigma_n^m$ can be reduced to it (similarly for $\Pi_n^m$-completeness). The notion of reducibility is usually either many-one reductions or Turing reductions.  So, for example, a set $Y$ is complete for $\Sigma_n^m$ under Turing reductions if, for every set $X\in\Sigma_n^m$, there is a Turing machine with an oracle for $Y$ that decides membership of $X$.  For many-one reductions, we insist that the oracle is called only once and the result of the oracle must be the result of the Turing machine's computation.  (Many-one reductions are the ones usually used to prove NP-completeness but, here, we're not restricting to polynomial-time reductions.)


How do I find a regular expression for a particular language? I have a language, and I want to find a regular expression for the language.  How do I do that?  Is there a step-by-step, systematic procedure for that?  Pretend I am just learning this topic; what approach can I use?

If it helps, you can assume the language is given in English (e.g., something like "$L$ is the set of words that contain at least one $a$, an even number of $b$'s, and does not contain the substring $ab$") or algebraically (e.g., $L=\{a^i b^j (abb)^k : i+2j+k=3\ell, i,j,k,\ell \in \mathbb{N}\}$).

This is intended as a reference we can point others to. Please explain your method in a form that someone new  can understand it.

Occasionally you can just stare at the language, get insight, and write down a regular expression just like that.  However, more typically, we need a systematic procedure.  Fortunately, the field of formal languages provides a more systematic approach that will help you structure your approach to this problem.  Often, one effective approach is as follows:

Step 1. Find a non-deterministic finite-state automaton (NFA) for the language.

Step 2. Convert the NFA to a regular expression.

Step 3. Double-check whether your regular expression is correct.

In more detail, here is how you do each of those two steps:

Step 1. To find a NFA for your language, you can think of this as a programming problem, where you have to write a program that works in a very limited programming language where you are only allowed to have a fixed, finite amount of state.  Try to write a program that reads in a string one letter at a time and decides whether the input string belongs to the language or not, using only a fixed amount of memory (say, $c$ memory cells, where $c$ is some constant that does not depend on the input string, not even on the length of the input string).  This program then corresponds naturally to a NFA, where the NFA has one state per possible value of the program's memory.

Sometimes, it can also be helpful to use the closure properties of NFA.  For instance, if the language $L$ is specifies as $L = L_1 \cup L_2$, then it suffices to build a NFA for $L_1$ and a NFA for $L_2$; then the closure properties for regular languages allow you to derive a NFA for $L$.  For more techniques to build a NFA, take a look at our reference question How to prove a language is regular? for more approaches.

Step 2. To convert the NFA to a regular expression, apply the algorithm described in How to convert finite automata to regular expressions?.

Step 3. To check whether your regular expression seems to be correct, you can try testing it on a few example strings to see if it seems to give the correct answer.  Try both several examples that are in the language and several that are not.

This is just one approach.  There are other approaches, including writing down a regular grammar and converting it to a regular expression, or writing a system of linear expressions in regular languages and converting to a regular expression using Arden's Lemma, or others.  For an overview of those methods, take a look at How to prove a language is regular?, How to convert finite automata to regular expressions?, and Known algorithms to go from a DFA to a regular expression.

You can also look at other examples of this kind of problem on this site, e.g., by looking at questions tagged regular-expressions.


Type inference of pair (product) types I am looking into Hindler-Milney type system and I am trying to add support for
the pair type. In Pierces book, he introduces special language constructs for creation of pairs and getting their elements.

What I am interested in is the following. What if I don't introduce new constructs, yet use special functions with this signatures:

$$pair: \alpha \rightarrow \beta \rightarrow \alpha \times \beta $$

$$proj1: \alpha \times \beta \rightarrow \alpha$$

$$proj2: \alpha \times \beta \rightarrow \beta $$

If I use Wand's algorithm for type inference, after collecting all equations between type expressions and solving it a bit, I get the following equation
for $((pair\; 2\;) 4): \tau$:

$$\alpha \rightarrow \beta \rightarrow \alpha \times \beta = Int \rightarrow Int \rightarrow \tau$$

It seems to me that the unification algorithm should infer at the end that $\tau = Int \times Int$. Is this true?

Do I really need a special construct for pairs? Is there something conceptually wrong with this? Probably their is, so it would be great if someone could point me out.

Note that I would also prefer using special constructs as that way looks cleaner and easier to program with; this question is just for my complete understanding of the subject.

You can use things like pair, proj ... as constants only. That works
very well conceptually. Nevertheless, there are reasons why
programming languages tend to use special syntactic forms for the like of
products:

Readability, e.g. ( M, N ) reads more natural than pair M N to
some.
For efficient reductions. It is possible to code the reductions for
pairs up in pure$\lambda$-calculus, but that's usually not as efficient.
Finally, you'd need a polymorphic typing system for this to work.

As an aside, the formalisation of logics in interactive proof assistants
like Isabelle is based on a similar idea, called logical frameworks.