What is a min-max theorem in graph theory? I'm currently studying a paper which uses extensively the term 'min-max theorems' in graph theory, and claims to present a tool allowing to generalize these theorems. (here is the link to the paper if needed)

Among those, we can find for example :

The max-flow-min cut theorem.
Edmond's disjoint arborescences theorem (link).

I have some intuition about what a min-max theorem would be, but I can't come with a concise and precise definition.

My question is : what would be a definition of such a family of theorems ?

And a second question along : is this min-max theorem concept always linked to the strong duality theorem, meaning that they mainly state that one problem is actually the dual of the other, like the max-flow-min-cut is ?

A min-max theorem is simply a theorem that says that the minimum value possible for one quantity is the maximum value possible for some other.
For example,

Max-flow min-cut says that the value of the biggest flow between two vertices in a weighted graph is equal to the value of the minimum cut that separates them.  Closely related, Menger's Theorem says that the maximum number of edge-disjoint paths between two vertex sets is equal to the size of the minimum cut that separates them.
Edmonds' Theorem says that the maximum number of edge-disjoint spanning arborescences is equal to the minimum value of something called $\varrho(X)$ over certain non-empty vertex sets.
The cops and robbers characterization of treewidth says that the minimum width over all tree decompositions is equal to the maximum number of cops that a robber can escape (er, plus or minus one, probably).


sub-optimal but fast partition generation I have a set of N integers that I want to partition into m subsets. I want these subsets to be well-balanced wrt some criterion say that minimize the max difference between the size of all subsets. But I am not really interested in THE optimal solution. I am interested in a FAST algorithm that generates some good partition wrt the criterion.

Let us say a set is [1,23,12,2456,234,16,188,22] and needs to be divided 3-ways. When partitioning we try to minimize the max difference between the size of all subsets.

One quick partition that can be generated is {[1,23,12],[2456,234,16],[188,22]}. This may not be optimal or maybe it is. It does not matter in this context.

We could have an algorithm: put 1st element in 1st set, 2nd element in 2nd set, all others in 3rd set. This would give us: {[1],[23],[2456,234,16,188,22]}. One can see this algo will be very fast but wrt to our criterion, it does not necessarily give a good-looking solution.

Can someone suggest existing work in this direction?

The following is directly taken from pages 358-360 of The Nature of Computation by Moore and Mertens and I think addresses your problem directly.

  Imagine that you run a computer center with $p$ identical machines, or a parallel computer with $p$ processors, for some constant $p$. You are given $n$ jobs with running times $t_1,t_2,...,t_n$. Your task is to find a schedule - a function $f:\{1,...,n\}\rightarrow\{1,...,p\}$ that assigns the $j$th job to the $f(j)$th machine.
  The load on the $j$th machine is the total time it takes to run the jobs assigned to it,
  $$
L_j = \sum_{i:f(i)=j} t_i\,.
$$
  Since the machines run in parallel, the time it takes us to finish all the jobs is the maximum load on any machine,
  $$
M=\max_{i\leq j\leq p} L_j\,.
$$
  We call this time the makespan, and your goal is to minimize it. This gives the following problem:

    Makespan
    Input: A set of $n$ running times $t_i\geq0,\,i=1,...,n$
    Output: A function $f: \{1,...,n\}\rightarrow\{1,...,p\}$ that minimizes the makespan
    $$M = \max_{1 \leq j \leq p} \sum_{i:f(i)=j}t_i$$

  Exercise 9.3 Reduce Integer Partitioning to the case of Makespan where $p=2$.

  There is, however, a simple algorithm that comes with a quality guarantee. The idea is to divide tasks into two groups, "large" and "small", and schedule the large tasks first. Let $T_{\text{tot}}=\sum_{j=1}^n t_j$ be the total running time of all the tasks. We choose some constant $\eta > 0$, say $\eta = 1/10$. We call the $j$th task large if its running time is at least a fraction $\eta$ of the total, $t_j \geq \eta\,T_{\text{tot}}$, and small if $t_j < \eta\,T_{\text{tot}}$.
  The algorithm then proceeds in two phases:

  Find a schedule that minimizes the makespan of the large tasks, using exhaustive search.
  Distribute the small tasks by giving each one to the machine with the smallest load so far, regardless of that tasks's running time.

  How long does this algorithm take? Since there are at most $1/\eta$ large tasks, there are $p^{1/\eta}$ ways to schedule them. Since $p$ and $\eta$ are constants, this gives a constant number of possible schedules to explore in phase 1, and we can check all of them in polynomial time using exhaustive search. Phase 2 clearly runs in polynomial time as well.
  Now let $M$ denote the makespan of the schedule produced by this algorithm. How does it compare to $M_{\text{opt}}$? Let $M_{\text{large}}$ denote the maximum load of a machine after phase 1, i.e., the minimum makespan of the large tasks. Since adding the small tasks can only increase the makespan, we have $M_{\text{large}} \leq M_{\text{opt}}$. If the algorithm manages to fit all the small tasks in phase 2 without increasing the makespan, putting them on machines with load less than $M_{\text{large}}$, then $M = M_{\text{large}}$. But since $M_{\text{opt}} \leq M$, in this case $M = M_{\text{opt}}$ and the algorithm performs perfectly.
  So, we will focus on the harder case where the makespan increases in phase 2, so that $M > M_{\text{large}}$ and our schedule for the small tasks might not be optimal. Let $L_j$ denote the load of machine $j$ after phase 2. Without loss of generality, we can assume that $L_1 \geq L_2 \geq ... \geq L_p$. Since $L_1 = M > M_{\text{large}}$, we know that at least one small task was added to machine 1.
  Let $t$ be the running time of the last such task. Since our strategy greedily assigns small tasks to the machines with the smallest load, the load of machine 1 must have been less than or equal to the others just before this task was added. This means that, for all $2 \leq j \leq p$,
  $$
M-t \leq L_j \leq M\,.
$$
  Since $t<\eta\,T_{\text{tot}}$, we also have
  $$
T_{\text{tot}} = M + \sum_{j=2}^p L_j \geq pM-(p-1)t\geq pM-\eta(p-1)T_{\text{tot}}\,.
$$
  Rearranging this gives an upper bound on M,
  $$
M \leq \frac{T_{\text{tot}}}{p}(1+\eta(p-1))\,.
$$
  On the other hand, the best schedule we could hope for would be perfectly balanced, keeping all the machines busy all the time. Thus the optimum makespan is bounded below by
  $$
M_{\text{opt}}\geq\frac{T_{\text{tot}}}{p}\,.
$$
  Combining this lower bound on $M_{\text{opt}}$ with the upper bound we have on $M$ gives an approximation ratio
  $$
\rho \leq \frac{M}{M_{\text{opt}}} \leq 1+\eta(p-1)\,.
$$
  By setting $\eta = \epsilon/(p-1)$, we can approximate $M_{\text{opt}}$ within a factor of $\rho = 1+\epsilon$ for arbitrarily small $\epsilon > 0$. In fact, we can define an algorithm that takes both the problem instance and $\epsilon$ as inputs, and returns a $(1+\epsilon)$-approximation. For each fixed $\epsilon$, this algorithm runs in polynomial time. Such an algorithm is called a polynomial-time approximation scheme or PTAS.
  On the face of it, a PTAS seems to be sufficient for all practical purposes. It allows us to find solutions within 1%, 0.1%, 0.01% ... of the optimum, each in polynomial time. However, improving the quality of the approximation comes at a cost, since the running time increases as $\epsilon$ decreases. Our PTAS for Makespan, for example, has to explore $p^{1/\eta} = p^{(p-1)/\epsilon}$ possible schedules in phase 1, so its running time grows exponentially as a function of $1/\epsilon$. Even for $p=2$ and $\epsilon = 0.01$, this number is $2^{100}$ - hardly a constant that we can ignore.
  We would prefer an algorithm whose running time is polynomial both in $n$ and in $1/\epsilon$. Such an algorithm is called a fully polynomial-time approximation scheme, or FPTAS for short. There is, in fact, an FPTAS for Makespan, which we will not describe here.

The end of chapter notes further recommend the "outstanding" book Approximation Algorithms by Vazirani, from which this algorithm is apparently taken.


What are $(S,\Sigma)$-CCCs? I was reading this and I was trying to understand the definition of $(S,\Sigma)$-CCC. The first requirement says:

  a mapping [[_]] : S → |C|, associating some object [[s]] ∈ |C| to
  any s ∈ S;

which I find very confusing and having a hard time understanding what it means. What is $S$ and what is $\Sigma$?

why do all the other requirements mean intuitively?

The meaning of $S$ and $\Sigma$ is defined on slide 6. $S$ is a set of base types (for example, natural numbers $\mathbb N$, Booleans $\mathbb N$, etc.): these are just formal symbols. $\Sigma$ is a set of operators, which included constants and functions (for example, $0 : \mathbb N$, $\text{true} : \mathbb B$, $\text{not} : \mathbb B \to \mathbb B$, etc.): these are pairs of an element of $S$ and a formal symbol. In the definition on slide 7, they seem to be limiting the operators to just constants.

The mapping $⟦-⟧ : S \to \mathrm{Ob}(\mathcal C)$ gives us an interpretation of a base type in the category $\mathcal C$: given any type $A \in S$, we have an object $⟦A⟧ \in \mathcal C$ interpreting that type.

They overload notation and also define a function $⟦-⟧: \Sigma \to \mathcal C^\to$. We interpret each constant $(c : A) \in \Sigma$ as a morphism $⟦c⟧: 1 \to ⟦A⟧$, where $1$ is the terminal object (called $\star$ in the lecture slides). This aligns with the usual interpretation of terms $\Gamma \vdash t : A$ as morphisms $⟦t⟧ : ⟦\Gamma⟧ \to ⟦A⟧$.

Together, both of these mappings $⟦-⟧$ allow us to interpret a signature for a simply-typed $\lambda$-calculus inside a cartesian-closed category, which is the first step in showing the equivalence between simply-typed $\lambda$-calculi and cartesian-closed categories.


Looking for an algorithm to iterate over essentially different solutions I'll explain my problem with an analogy to Sudoku-grids.

Consider a filled Sudoku-grid. If you exchange labels or rearrange rows/columns within a block, you have another valid Sudoku-grid. However the new grid is essentially equivalent, if that makes sense. One might say, under the operations "swap rows", "exchange labels" etc., both grids are in the same orbit. (https://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumerating_essentially_different_Sudoku_solutions)

I want to iterate over all grids, but in a way that the algorithm ignores other solutions in the same orbit. However, this question is not about Sudoku grids! My grids have a different structure, which is a bit simpler:

I want to fill a 4x6 table with the integers 1 to 8 (each three times) such that each row contains each integer at most once. There are a few other more complex conditions, but I think it's easier to check them later after a solution has been generated.

Just like in the Sudoku analogy, there are a few operations that generate other essentially equivalent solutions:

1) Rearranging rows: if one row is

1 3 5 6 2 8

the solution with that row replaced by

1 2 3 5 6 8

is of course also valid and consindered essentially equivalent.

2) Swapping rows.

3) Exchanging labels.

E.g. these solutions are essentially equivalent

1 3 5 6 2 8
4 1 5 7 8 2
4 7 6 1 2 3
3 4 5 6 8 7

First row rearranged:
1 2 3 5 6 8
4 1 5 7 8 2
4 7 6 1 2 3
3 4 5 6 8 7

First two rows swapped:
4 1 5 7 8 2
1 3 5 6 2 8
4 7 6 1 2 3
3 4 5 6 8 7

All 1's and 2's exchanged
2 3 5 6 1 8
4 2 5 7 8 1
4 7 6 2 1 3
3 4 5 6 8 7

My question is what an efficient (both runtime and memory) algorithm to generate these solutions might be.

The naive approach would be to store all previous solutions and check whether an equivalent solution has already been found. However, this is expensive in both runtime and memory!

I managed to improve this by calculating a hash of each solution in such a way that equivalent solutions generate the same hash. Then we can store the solutions in a map, so that we need to check fewer solutions and thus reduce the runtime. However, the memory cost is still huge.

If the hash has the property that different solutions yield different hashes, then I would only need to store the hashes and reduce the required memory by a large factor.

Can you think of a more elegant algorithm that does not store hashes nor previous solutions?

EDIT:

I simplified my problem too much without realising that I reduced the number of orbits to 1. (Thanks @Klaus Draeger). In fact the numbers 4,6,8 and 3 were made up as an example. I thought I could adapt the algorithm to the more general case later.
Actually, my problem is a bit more complex: The number of rows is variable and rows need not have the same length, so rule 2) only applies to rows of equal length. Also the frequency of the numbers is not necessarily constant (e.g numbers 1,2,3,4 might appear four times and 5,6,7,8 three times or whatever), so rule 3) only applies to labels with the same frequency.

EDIT2:

And this is the more complex condition, that I thought doesn't matter for now. Maybe I'm wrong again...

If, in one row, y appears directly to the right of x (or y is in the first column and x in the last), then in a (unique) different row there must be an x to the right of y (above example does not satisfy this). This means that rule 1) only applies to rotations of rows and not any permutation.

I think this can be dealt with at a later point.

All solutions are equivalent modulo the equivalence you have given.

Suppose $(a_{i,j})_{1\le i\le 4,1\le j\le 6}$ is some solution. Each row misses two labels, and these pairs of labels form a partition of $\{1,\dots,8\}$ (otherwise some label would occur too often). But then we can choose an exchange of labels modulo which row $1$ misses $7,8$; row $2$ misses $5,6$; row $3$ misses $3,4$; and row $4$ misses $1,2$.

Each row can then be reordered to arrive at the solution

$A=\begin{pmatrix}1&2&3&4&5&6\\1&2&3&4&7&8\\1&2&5&6&7&8\\3&4&5&6&7&8\end{pmatrix}$

Since every solution is equivalent to $A$, by transitivity, they are all equivalent.


If a problem is Cook-NP hard, and this problem is in NP, does it prove that the problem is Karp-NP-complete? I got recently confused when I noticed that there exists 2 types of polytime reductions, which lead to 2 different concepts of NP-hardness.

This is well explained in the answer to this question:
Can one show NP-hardness by Turing reductions?

While a Karp reduction is required to show whether a problem is NP-Hard or co-NP-Hard, with Cook (aka Turing) reductions one only shows that a problem is "Cook-NP-hard", in a sense which does not distinguish NP-hardness from co-NP-hardness. More precisely,

In a Karp reduction, you map each instance $I$ of Problem $A$ to an instance $f(I)$ of Problem $B$, where $f(I)$ can be computed in polytime, and such that
$$I \text{ is a Yes-instance for $A$} \iff f(I) \text{ is a Yes-instance for $B$}.$$
If $A$ is (Karp-)NP-Hard, this shows that $B$ is (Karp)-NP-Hard, too.
And if $A$ is (Karp-)co-NP-hard, this shows that $B$ is (Karp)-co-NP-Hard, too.
In a Cook-reduction, you assume that there exists a polytime procedure $F$ to solve Problem $B$, and you show that Problem $A$ could be solved by calling this procedure a polynomial number of times.
If Problem $A$ is known to be NP-hard, this shows that $B$ is (cook)-NP hard, but this does not tell us anything about the membership of $B$ in (Karp)-NP-Hard or (Karp)-co-NP-Hard.

1) In my understanding, Karp reductions only apply to decision problems, while we can show that any kind of problem is Cook-NP-Hard, is that correct?

2) If I want to prove that a problem is NP-complete, is it enough to show that this problem is Cook-NP-hard, and then to show that this problem is in NP? Similarly is a problem is Cook-NP-hard and in co-NP, does it prove that this problem is co-NP-complete?

3) A perhaps equivalent formulation of this question is as follows: While there is a distinction between the notions of Cook- and Karp-NP-Hardness, is there a real distinction between the notions of Cook- and Karp-NP-Completeness?

NP-hardness is a property of decision problems. It doesn't matter whether you define it using Karp reductions or Cook reductions.

NP-hardness and NP-completeness are defined using Karp reductions. If you prove that a problem is Cook-NP-hard, then it doesn't imply that it is Karp-NP-hard. Indeed, coSAT (the collection of unsatisfiable CNFs) is Cook-NP-hard but probably not Karp-NP-hard. Under reasonable hardness assumptions, there are even problems in NP which are Cook-NP-hard but not Karp-NP-hard. See for example Mandal, Pavan, and Venugopalan, Separating Cook Completeness from Karp-Levin
Completeness under a Worst-Case Hardness
Hypothesis.


Number of sequnces with given value Consider a valid string with bitwise operations (AND, OR, XOR), and also placeholders $X$, where each $X$ stands for an arbitrary number from $\{0,1\}$. There are $n$ many $X$s, so there are $2^n$ possible sequences. How many out of the
  $2^n$ strings have value $0$? How many have value $1$?

My approach to this problem was, I assumed that the interpretation of strings is done by associating left-to-right (that is, $0 \oplus 1 \land 0$ means $(0 \oplus 1) \land 0$).
I will use $\lor,\land,\oplus$ for OR, AND, XOR.

Let $s$ be an arbitrary string with $n$ many $X$s that evaluates to 0, and let $t$ be an arbitrary string with $n$ many $X$s that evaluates to 1.

Then, the strings with $n+1$ many $X$s that evaluate to $1$ are:
$$ t \lor 0, s \lor 1, t \lor 1, t \land 1, s \oplus 1, t \oplus 0. $$
The ones that evaluate to 0 are:
$$ s\lor 0, s\land 1, s\land 0, t\land 0, s\oplus 0, t\oplus 1. $$

Fixing a sequence of operations, let $S(n)$ be the number of strings with $n$ many $X$s that evaluate to 0 with the given operations, and let $T(n)$ be the number that evaluate to 1.

Denote the $i$'th operation by $O_i$.
Then, just counting the combinations in the previous paragraph for each operator, I get the following recurrence relations:
$$
\begin{align}
&S(1)=T(1)=1 \\
&S(n+1),T(n+1) =
\begin{cases}
S(n), S(n)+2T(n) & \text{if } O_{n+1}=\lor \\
2S(n)+T(n), T(n) & \text{if } O_{n+1}=\land \\
S(n)+T(n), S(n)+T(n) & \text{if } O_{n+1}=\oplus
\end{cases}
\end{align}
$$

  What should I do if my assumption was wrong, that is, if the sequence could contain parentheses, e.g. $(X \lor (X \oplus X))$?

You should first build the binary expression tree of the given boolean expression. You can then do a Depth First Search on this tree, and start computing the answers from the leaves to the root (bottom to top), similar to the way you've done in your approach.

But instead of $S(i)$ denoting the number of assignments of the first $i$ $X$s which evaluate to 0, it will now be $S(u)$ denoting the number of assignments of the $X$s which lie in the subtree of $u$, which evaluate the expression until $u$ to be 0. Here $u$ refers to a node in the tree. Similarly $T(u)$ is defined for evaluation to 1.

The base case would be when $u$ is a leaf (which would happen when it corresponds to an operand), and both $S(u)$ and $T(u)$ would be equal to 1 in that case. Else, if $u$ is an internal node (which corresponds to an operator), you compute the $S$ and $T$ values by looking at the $S$ and $T$ values of its children, $c_1$ and $c_2$, and applying recursion similar to what you had in your answer:

If $u$ is an OR node,

$S(u) = S(c_1)  S(c_2)$

$T(u) = S(c_1)  T(c_2) + T(c_1)  S(c_2) + T(c_1)  T(c_2)$

If $u$ is an AND node,

$S(u) = S(c_1)  T(c_2) + T(c_1)  S(c_2) + S(c_1)  S(c_2)$

$T(u) = T(c_1)  T(c_2)$

If $u$ is an XOR node,

$S(u) = S(c_1)  S(c_2) + T(c_1)  T(c_2)$

$T(u) = S(c_1)  T(c_2)  + T(c_1)  S(c_2)$

And the final answer would be $S(\mathit{root})$ and $T(\mathit{root})$.


Upper bound on the covering radius of a code Let $C$ be a $[n,k]$ linear code over $\mathbb{F}_q$.

Suppose that $\rho$ is the covering radius .

I want to show that $\rho \leq n-k$.

Could you give me a hint how we could show this?

The covering radius is defined as follows:

$$\rho=\max_{x \in \mathbb{F}_q^n} d(x,C) \\ d(x,C)=\min_{c \in C} d(x,c)$$

You need to show that every vector is at distance at most $n-k$ from a codeword. The code is the collection of all vectors $x$ satisfying $Ax = 0$, where $A$ is an $(n-k) \times n$ matrix, which without loss of generality has the form $A = \begin{bmatrix} I_{n-k} & B \end{bmatrix}$ (use Gaussian elimination, possibly permuting coordinates to avoid zero columns). Let $v$ be a completely arbitrary vector, and suppose that $Av = s$. Extend $s$ to a vector of length $n$ by adding zeroes at the end. Then $A(s + v) = 0$, i.e., $v + s$ is a codeword, which is at distance at most $|s| \leq n-k$ from $v$.


Is it possible to partially decide when will halt given any arbitrary input? This is a problem that I think is a reduction from the halting problem. I have on two separate practice exams statements that,

  Given a Turing machine T and a string w, to determine whether T will halt when started on input w.

and

  Given a Turing machine T and a string w, to determine whether T will halt when started on a blank tape.

The answer key states that these problems are both partially decidable, which is astonishing to me given that they are reductions from the halting problem, which is undecidable.

If there was a Turing maching M, that would halt if it's input was another Turing machine T that also halted on an arbitrary string, would that not violate the halting problem? Why are the two above statements considered to be partially decidable?

The halting problem is not decidable, but it is still partially decidable (other terms for this are "recursively enumerable" and "Turing recognizable"). So, you are right that both of these problems are equivalent to the halting problem. That is why they are undecidable, but still partially decidable.

You may want to review the definition of "partially decidable" in your textbook or notes.


Why divide by $b-1$ when computing size of a tree In one of the lectures I went to, my professor stated that in order to determine the size of a search tree, we use the following formula:
$$\frac{b^{d+1}-1}{b-1},$$
whee $b$ is the branching factor and $d$ is the depth of the tree in question. I would like to understand why we divide by $b-1$. I would have thought that the correct solution is $b^{d+1}-1$.

There are $b^i$ nodes at depth $i$, and so the total number of nodes is
$$
1 + b + b^2 + \cdots + b^d = \frac{b^{d+1}-1}{b-1},
$$
using the formula for the sum of a geometric progression.


What is the "description" of a Turing machine? I am currently reading about the Halting Problem in my course on the theory of computation and the following was given in my lecture slides

Now my question is that if $d$ is the description of a Turing machine, what exactly is $d$ from a strictly mathematical point of view? The way that $d$ is written above seems to suggest that $d \in Q$ (i.e. that $d$ is a state of the Turing machine $T$), but I can't be entirely sure.

The description is a string that encodes the formal specification of the machine, comprising:

the set of states,
the start state,
the set of halting states (or, where appropriate, the sets of accepting and rejecting states),
the tape alphabet,
the input alphabet,
the transition function.

Some authors also explicitly include the identity of the blank symbol in the description of the machine; others leave it to convention (e.g., stating that the alphabet will always be $c_1, \dots, c_k$ for some $k$, and $c_1$ is the blank symbol).


Is this proof for showing that $EQ_{CFG}$ is co-Turing-recognizable incorrect? I have been searching for proofs that show that $EQ_{CFG}$ is co-Turing-recognizable. When searching for proofs I can only find proofs on the following form:

  Construct a TM $M$ which recognizes the complement of $EQ_{CFG}$, M =
  "On input ⟨G,H⟩":

  For each string $x \in \Sigma^*$ in lexicographic order:
  Test whether x ∈ L(G) and whether x ∈ L(H), using the algorithm for $A_{CFG}$ .
  If one of the tests accepts and the other rejects, accept; otherwise, continue.”

(From: http://cobweb.cs.uga.edu/~potter/theory/6_reducibility.pdf)

Isn't this proof incorrect?

Say that my language is $\Sigma=\{a,b\}$ and that I have $L(G_1) = \{b\}$ and $L(G_2) = {bb}$. $M$ should accept $\langle G_1, G_2\rangle$ since $L(G_1) \neq L(G_2)$. But if we run $M$ with $\langle G_1, G_2\rangle$ the TM will first generate $x=a$, which isn't in either languages so the machine will go back to step 1 and then generate $x=aa$, then $x=aaa$ and so on forever. The machine will never get to $x=b$. Hence, the machine will loop on input that it should accept. Therefore $M$ isn't a Turing recognizer.

Would the proof be correct if step 1 instead would state "For each string $x \in \Sigma^*$, ordered by increasing size and then lexicographic order:"? This should generate strings in the following order: $x=a$, $x=b$, $x=aa$, $x=ab$, $x=ba$, $x=bb$, $x=aaa$, and so on. So in the case above $M$ would reject when $x=b$.

In this context, lexicographic order means:

First order by length.
Within each length, order lexicographically.

You're saying that the proof is incorrect, but in fact it is only inaccurate in that the order is not quite the lexicographic order. I would say that the proof has a small mistake, but is otherwise correct.

One often encounters such small issues in intricate mathematical arguments. Instead of immediately declaring failure when you run upon such a difficulty, you should try to see if the argument can be fixed by making small adjustments. You're not in a trial, acting as a prosecutor. Rather, you should believe the author that she had some valid proof in mind, but perhaps was a bit sloppy when trying to express her thoughts on paper. It's a cooperative game, in which you are trying to make the proof work rather than try to break it.


How to get a heatmap of pixel influences from a Convolutional Neural Network If I have a CNN model (let's say I'm using Tensorflow and Keras) that I've trained for a particular task. For example, let's say I've trained it to detect the difference between an apple and banana. For a given input image, is there a way to generate a heatmap overlaid on the original image that indicates which parts of that image influenced the network's decision?
I'm guessing that you'd have to use the chain rule to get the partial derivative of the loss function with respect to each pixel, and the normalize those values and heatmap them. Is there a library or existing method that does this?
How would I do this if I had a CNN mapping to predictions for more than two classes?

Yes, there are various proposals out there.  Many of them work by computing a saliency map.  If you search for "saliency map", you should be able to find multiple schemes for that.
Personal opinion: these methods give heatmaps that seem superficially plausible; but my sense is that they have major limitations.  So don't set your expectations too high, or you may be disappointed.


Addition or Subtraction of Polynomials Can addition (or subtraction)  of polynomials of degree $< n$ be done in constant time ?

I am quite new to algorithms. I thought about using sorted arrays for storing the coefficients. But the addition of two sorted arrays appears to be $\in O(n)$. However, I am not convinced that this is the best solution. Could someone please help clarify?

Because the set $\{1,x,\ldots,x^{n-1}\}$ is a base for polynomials with degree $<n$, by definition of base, no element in this set can can be expressed as a combination of others, i.e. no element can be “ignored”.

Therefore, we know that our algorithm needs to at least read all the coefficients corresponding to $n$ elements of the base, thus making at least $n$ steps.

On the other hand, you found that adding/subtracting polynomials can be simulated by element-wise adding/subtracting lists of their coefficients, which is $O(n)$, meaning it requires less than $c \cdot n$ steps for some constant $c$.

Now we know that your algorithm needs to make some number of steps that is between $n$ and $c\cdot n$, and as @Yuval pointed, this is $\Theta(n)$ time complexity.

(this is all for general case and I don’t know if there exists some special space of polynomials that can be represented more compactly, thus making it possible to add/subtract them faster, but also I think that you are in fact interested in a general case)


Prove $\varphi(x)$ to be primitive recursive Let $\varphi(x)=2x$ if $x$ is a perfect square, $\varphi(x) = 2x+1$ otherwise. Show $\varphi$ is primitive recursive.

In proving $\varphi$ to be a p.r. function I think it could come in handy the following theorem:

Let $\mathcal C$ be a PRC class. Let the functions $g$, $h$ and the predicate $P$ belong to $\mathcal C$, let

\begin{equation}
 f(x_1,\ldots, x_n) =
 \begin{cases}
  g(x_1, \ldots, x_n) \;\;\;\;\;\text{ if } P(x_1, \ldots, x_n)\\
  h(x_1,\ldots,x_n) \;\;\;\;\;\text{ otherwise}
 \end{cases}
\end{equation}
Then $f$ belongs to $\mathcal C$ because $$f(x_1, \ldots, x_n) = g(x_1, \ldots, x_n) \cdot  P(x_1, \ldots, x_n) + g(x_1, \ldots, x_n) \cdot \alpha(P(x_1, \ldots, x_n))$$ where

\begin{equation}
 \alpha(x) =
 \begin{cases}
  1 \;\;\;\;\;\text{ if } x = 0\\
  0 \;\;\;\;\;\text{ if } x \neq 0
 \end{cases}
\end{equation}

and $\alpha(x)$ is p.r.

So similarly I would say that $\varphi(x)$ is p.r. as

\begin{equation}
 \varphi(x) =
 \begin{cases}
  2x \;\;\;\;\;\;\;\;\;\;\;\text{ if } x = t \cdot t \\
  2x+1 \;\;\;\;\;\text{ otherwise}
 \end{cases}
\end{equation}
hence $$\varphi(x) = 2x \cdot  P(x_1, \ldots, x_n) + (2x+1) \cdot \alpha(P(x_1, \ldots, x_n))$$ and $P$ is a primitive recursive predicate as $x \cdot y$ is p.r. and also $x = y$.

Does everything hold? Is there anything wrong? If so, since I am tackling this kind of exercise for the fist time, will you please tell me what's the proper way to solve this?

To see if $x$ is a perfect square is easy (for example, by adding 1 + 3 + 5 ... you get the succesive squares); once that is settled your problem is solved. Think of such problems primarily as programming asignments (in a rather cruel programming language).


How to convert a Complete Binary Tree to a Priority Search Tree in O(n) There doesn't seem to be any resources on this.
I would like to know if there is a linear-time algorithm to convert a Complete Binary Tree with data left-to-right increasing stored in external nodes, to a Priority Search Tree.

edit: Convert = create a priority search tree with all of the elements of some complete binary tree

edit 2: or modify the original Complete Binary Tree such that it has all of the properties of a Priority Search Tree

No.  If you could, you'd obtain a sorting algorithm that would run in $O(n)$ time (construct the priority search tree, then traverse the nodes in increasing order of key), but you can't sort in $O(n)$ time.


Memory Requirement for a Computable Problem I was thinking whether it is true that every computational problem intrinsically has a minimum ammount of memory required for any algorithm that computes it.
But then i was confused to what "memory requirement" really means and how we could quantify it .
Looking for how Computational Complexity treats the memory requirement of a computational problem made me even more confused, because it always consider memory requirement under Turing Machines ... so it really doesnt treat the memory requirement as universal as it could ( applied to any possible model of computation : be it FSM, Lambda Calc, or whatever ).

Let me elaborate on my confusion.

It was intuitively thinking of characterizing the memory requirement of algorithms in terms of levels of memory.     For automatas,  binary addition of numbers too small so we don't need carriers would be a problem that would require no memory at all .
But addition with carriers and  1-momment delaying would be problems at least 1 level of memory.  Binary multiplication of arbitrarily large numbers, however, would require arbitrarily large levels of memory .    It's so wierd that Combinational Logic circuits can solve all those problems ( arithmetic with carriers ) if it doesn't have any memory at all ( no flip-flop ). How can we understand that ? Is a combinational logic circuit doing computations ? Can we see it as a weak model of computation ?

I had a hope that Space Complexity in the Computational Complexity discipline cold formalize this idea of "levels of memory, but it seems that since the framework is always Turing Machines, everything requires memory, even a simple addition without carriers ( in fact, it needs memory to simulate combinational logic circuits that are models of computation that don't require memory )  .

But there are many problems with this notion of "levels of memory".

1 - What does a level of memory really mean ?  Do we universally have only two ways of encoding those levels of memory :  either on the states of a machine , or on auxiliary memory read by a machine.

2 - In case the first question is true, would the correspondence for encoding levels of memory on the states of a machine be :   n levels of memory require at least 2^n states ?  At least, for Finite State Machines, it seems to be that way .
But what about the correspondence for encoding levels of memory on auxiliary memory ( tape-memory ) read by a machine ?

Anyways,  i'm really stuck with this doubt for some time and any clarification ( suggestion of a topic for me to read, or any resource at all  ,   explanations and any insight about that ) on how we can understand treat this memory requiment concept universally would be really helpful.

Thanks a lot in advance.

Yes, there's plenty of theoretical work on space complexity.  No, it's not necessarily Turing machines; you can talk about space complexity in other models of computation, e.g., the RAM model.  You might find that more practically relevant.  I suggest you study RAM machines and existing work on space complexity.

It's not clear what you mean by "levels of memory", and I don't see anything there that's useful.  Instead, standard space complexity results talks about the space requirement: e.g., $\Theta(n)$ space, $\Theta(n^2)$ space, $\Theta(2^n)$ space.  See also LOGSPACE, PSPACE and similar complexity classes.


What does this mean $[X]_1^T$? I found this in information theory paper, P.3883*
the authors states the following

Most existing theoretic studies of network coding focus on DAGs due to its simpler structure and dure to the fact that one can always convert a cyclic network to its acyclic counterpart by taking into account the time index and the causality of information transmission. Nonetheless, when studying Pair Intersession Network Coding on a cyclic network, one cannot rely on this cyclic-to-acyclic conversion since after conversion, there are T symbols in the $(s_1, d_1)$ (resp. $(s_2,d_2)$) multicast session and network coding allows complete freedom of mixing the $2T$ symbols $[X]_1^T$ and $[Y]_1^T$.

It looks ambiguity because does it mean that we have input from 1 to T; or Is it field = T and size = 1 (since capacity = 1)? so I hope I find answer here.
Thank you ..
*for those who doesn't have access go to this site Paper

Responsing to D.W. (The following information is for reference about the paper.)
C-C. Wang and N. B. Shroff. Pairwise Intersession Network Coding on Directed Networks. IEEE Tran. on Info. Theo., Vol. 56, No. 8, August 2010.

This notation is quite common in EE works:
If $S=S_1S_2S_3\cdots$ is a string (of some length), then

$S_i^j$ is the substring between places $i$ and $j$, that is, $S_i^j=S_i\cdots S_j$.

I didn't looks at the paper, but I guess that $[X]$ is a string (of expectations? of $X$ directly? this should be defined in the paper), and they just look at a prefix of length $T$ of that string.


Time complexity of recursive power code While I was learning about time complexity of recursive functions, I came across this code to calculate $x^n$:

power (x, n) {
    if n == 0
        return 1
    if n is even
        return power(x, n/2) * power(x, n/2)
    if n is odd
        return power(x, n/2) * power(x, n/2) * x

According to the book, its complexity is $\Theta(n)$ which seems rather strange to me. In my eyes, this code should have complexity $\Theta( n^2)$.

What am I seeing wrong?

An Answer

I will take your code at face value under the Uniform Cost Model.

Let's now assume $n$ is of the form $n = 2^k$ where $k \in \mathbb{N} \wedge k \geq 0$ (e.g. $n$ is a power of $2$).

We then get a recurrence relation like so:

$$\begin{align}
T(x, n) & = 2 \cdot T\left(x,  \frac{n}{2} \right) + c \\[0.5em]
& = 4 \cdot  T\left(x,  \frac{n}{4} \right) + 2c + c \\
& = \vdots \\[0.5em]
& = \sum_{i = 1}^{\log_2 n} 2^{i - 1} \cdot c\\[0.5em]
& = c(n - 1)\\
& = \Theta(n)
  \end{align}$$

Some Fun

Now let's take a step back and check out the Logarithmic Cost Model. Let's define the cost of multiplication as $g(n)$ where $n = \log_2 x$ (the size of $x$ in binary) and $x$ maximum of the two arguments.

Along with our prior assumption about $n$, let's also assume $x$ is of the form $x = 2^k$ where $k \in \mathbb{N} \wedge k \geq 0$ (e.g. $x$ is a power of $2$).

We get a recurrence of the form:

$$\begin{align}
T(n) & = 2 \cdot T\left(\frac{n}{2} \right) + g\left(\frac{n}{2}\right) \\[0.5em]
& = 4 \cdot  T\left(\frac{n}{4} \right) + 2 \cdot g\left(\frac{n}{4}\right) + g\left(\frac{n}{2}\right) \\
& = \vdots \\[0.5em]
& = \sum_{i = 1}^{\log_2 n} 2^{i - 1} \cdot g\left(\frac{n}{2^i}\right)\\[0.5em]
\end{align}$$

Now we can analyze some interesting multiplication methods:

Multiplication is linear in size, e.g. $g(n) = n$.

$$
\begin{align}
T(n) & = \Theta(n \log n)
\end{align}$$

Multiplication is quadratic in size, e.g. $g(n) = n^2$.

$$\begin{align}
T(n) & = \Theta(n^2)
\end{align}$$

Karatsuba Multiplication, the divide and conquer method, e.g. $g(n) = \Theta(n^{\log_2 3})$

$$\begin{align}
T(n) & = \Theta(n^{\log_2 3})
\end{align}$$

Just for fun, and to plug Yuval's answer to my own question, multiplication is super-linear-polylogarithmic and sub-polynomial-polylogarithmic, e.g. $g(n) = \Theta(n\log n \cdot 2^{\sqrt{2\log n}})$. We also assume size $n$ for $g$ instead of $\frac{n}{2}$.

$$\begin{align}
T(n) & = 2 \cdot T\left(\frac{n}{2} \right) + \Theta\left(n\log n \cdot 2^{\sqrt{2\log n}}\right) \\[0.5em]
\end{align}$$

We use case 3 of the Master Theorem to get:

$$\begin{align}
T(n) & = \Theta\left(n\log n \cdot 2^{\sqrt{2\log n}}\right) \\[0.5em]
\end{align}$$

Essentially, but not exactly, as the time complexity becomes superlinear, the time it takes to multiply overtakes the recursive time. This can be seen as case 3 of the Master Theorem.

Even More Fun!

Now let's say this was implemented in a smart manner, not repeating the recursive calls or using DP.

We get a recurrence of the form:

$$\begin{align}
T(n) & = T\left(\frac{n}{2} \right) + g\left(\frac{n}{2}\right) \\[0.5em]
& = T\left(\frac{n}{4} \right) + g\left(\frac{n}{4}\right) + g\left(\frac{n}{2}\right) \\
& = \vdots \\[0.5em]
& = \sum_{i = 1}^{\log_2 n} g\left(\frac{n}{2^i}\right)\\[0.5em]
\end{align}$$

The major improvement now is when multiplication is linear in size, we now get linear exponentiation!

$$
\begin{align}
T(n) & = \Theta(n)
\end{align}$$


Lambda Calculus in Rewriting systems How to do or implement Lambda Calculus in a Rewriting systems?

Rewriting systems are Turing complete.

But I can't figure out how to do lambda calculus or functions with them.

See also this question: "How is Lambda Calculus a specific type of Term Writing system?".

Term rewriting, as introduced in (1), and described in e.g. (2), is a first-order system that cannot handle binding. Consider the $map$ function.

$$
  \begin{array}{lcl}
  map(f, []) &\rightarrow& [] \\
  map(f, cons(x, l)) &\rightarrow& cons( f\ x, map\ f\ l)
  \end{array}
  $$

The problem is that $f$ is used both as a variable and a function
  symbol, which is not permitted by first-order term-rewriting system.

This lead to higher-order rewriting, see e.g (3) for an overview. Another approach to unification of term-rewriting with the $\lambda$-calculus is
the rewriting calculus (4). Yet another approach  towards rewriting with binders -- arguably the most modern -- is nominal rewriting (5).

D. E. Knuth, P. Bendix, Simple Word Problems in Universal Algebras.
F. Baader, T. Nipkow, Term Rewriting and All That.
T. Nipkow, C. Prehofer, Higher-Order Rewriting and Equational Reasoning.
H. Cirstea, C. Kirchner, Introduction to the rewriting calculus.
M. Fernandez, M. J. Gabbay, Nominal Rewriting.


Why not relax only edges in Q in Dijkstra's algorithm? Can someone tell me why almost in every book/website/paper authors use the following:

foreach vertex v in Adjacent(u)
    relax(u,v)

when relaxing the edges, instead of:

foreach vertex v in Adjacent(u)
    if (v is in Q)
        relax(u,v)

This is extremely confusing for someone when learning the algorithm. Is there any reason why the people are omitting the IF ?

Anyway I wrote a semi-Javascript (I changed it here to a readable syntax) implementation of Dijkstra and I wanted to be sure if it is correct because of this IF case. Here is my code excluding the initialising:

while (queue.length != 0)
    min = queue.getMinAndRemoveItFromQ()
    foreach v in min.adjacentVertices
        // inspect edge from "min" to "v"
        if ( queue.contains(v) AND min.priority + weight(min,v) < v.priority )
            v.priority = min.priority + weight(min,v)
            v.pre = min

Is this implementation correct or am I missing something ?

The condition

  min.priority + weight(min,v) < v.priority

can only be true if $v$ is in the queue. If a vertex $v$ has been removed from $Q$ the invariant of Dijkstra's algorithm guarantees we've already found the shortest path to $v$.

Edit: Proof Sketch
Suppose v isn't in Q. Then we must have already found the shortest path to v. Now if we later examine a vertex u connected to v, the condition min.priority + weight(min,v) < v.priority must be false, otherwise we would have found a shorter path to v which is a contradiction.


A nim game variant with pass move This variant is almost similar to the normal nim game which states -

  Two players take turns to remove one or more items from a single, non-empty pile. The player who removes the last item from the last non-empty pile is declared as a winner.

The twist is an inclusion of a "pass" move for each non-empty pile. To make myself clear, a player can choose to pass his move on any non-empty pile on which there was no "pass" move made.

I looked up grundy numbers to solve this problem, but I do not how to add the rule of pass move.

For ex:

$G(0) = mex(empty-set) = 0$

$G(1) = mex(G(1),0) = ?$

Heremex(g) is a function which takes a set of non-negative integers and outputs smallest non-negative integer that is not present in the list.

For ex : mex(0,1,2) = 3 and mex(0,2,3) = 1

I just don't know how to proceed. I'd appreciate some help. Also, I'd like to add that the number of piles is small say 10-15 but the number contained in each pile is quite huge. Hence those recursive backtracking type of solutions won't work.

Update : The pass move is not mandatory.

You have to augment each pile with an extra bit which states if it has been passed or not. Then you can compute the Grundy function as usual. For example, here are some values:
$$
\DeclareMathOperator{\mex}{mex}
\newcommand{\yes}{\text{Yes}}
\newcommand{\no}{\text{No}}
G() = \mex(\emptyset) = 0 \\
G(1,\yes) = \mex(G()) = \mex(0) = 1 \\
G(1,\no) = \mex(G(),G(1,\yes)) = \mex(0,1) = 2 \\
G(2,\yes) = \mex(G(),G(1,\yes)) = \mex(0,1) = 2 \\
G(2,\no) = \mex(G(),G(1,\yes),G(2,\yes)) = \mex(0,1,2) = 3
$$
Here Yes means that the pile has been passed, and No that it hasn't been passed.

You mention that a recursive solution won't be efficient enough. In that case, I suggest trying to find a formula for the Grundy function. Here is a hint:

  A pile which has been passed behaves like a normal pile. A pile which has not been passed behaves like a pile which is one item larger.


Remove features with too little variation I have the following messy chart;

As you can see some features are very stable through the time series (post-2011) like Extraversion.
Is there an algorithm to remove features that do not have much variation compared to the other features?

Step 1. Identify a measure of variation for a feature.
Step 2. Remove all features for which this measure is below some threshold (or is below that of msot other features).
There are many measures of variability that you could use in step 1: standard deviation, interquartile range, range (max minus min), median absolute deviation, and more.  Any of these are probably reasonable.


Doubts on Definition of Indistinguishable Encryption in the Textbook In the classic crypto textbook "Introduction to Modern Cryptography" by Jonathan Katz and Yehuda Lindell, there is a definition for indistinguishable encryption in the presence of an eavesdropper as such that for every probabilistic polynomial time adversary A there is a negligible function negl(n) such that

$\Pr[PrivK_{A,\Pi}=1] \leq negl(n)$

where PrivK is the indistinguishability experiment and for the purpose of this question we only need to know that the experiment outcome is 1 iff the adversary makes the correct guess.

My doubts are as follows. Consider a sequence of probabilistic polynomial time adversaries $\{A_i\}_{i>=1}$ whose advantage in the indistinguishability experiment is bounded by the following sequence of negligible functions

$\Pr[PrivK_{A,\Pi}=1] \leq negl_i(n) = \frac{1}{(1+1/i)^n}$

Clearly it is necessary for the above conditions to hold for a indistinguishable encryption. But is it a correct model/condition for real-world applications? For example, in practice we typically choose a sufficiently large n and set up some encryption scheme. However, there is the always some adversary $A_i$ that wins the experiment with probability close to one. So what's wrong?

Depends on how different your algorithms are. If you can compute $A_i$ from $i$ in polynomial time, then $A'$ with $A'(n) = A_n(n)$ is a polynomial time adversary too and violates the assumption (as it has non-negligible success probability). This would make your series of $A_i$ uniform and is one usual class of adversaries to consider.

If you'd like your crypto system to be secure against any such series of polynomial bounded adversaries you have to consider non-uniform adversaries (at least non-uniform in polynomial time), by e.g. defining a single adversary as a series of (randomized) circuits with polynomial size.


Proving $\lceil \lg n \rceil -1 = \lfloor \lg n \rfloor$ I recently came across the question:
Show that there are at most $\lceil n / 2^{h + 1} \rceil$ nodes of height hh in any nn-element heap.
I looked for some solutions and found this one:
Binary heap: prove that number of nodes of height h is not bigger than $\lceil \frac{n}{2^{h+1}} \rceil$
But I got confused with the answer which used the expression:
$$\lceil{\log_2n}\rceil-1$$
as the height of the tree.
But, I am confused because I have earlier proved that the height of the tree is:
$$\lfloor \lg n \rfloor$$
Even if I consider both are the same it could only be true if $\lg n$ returns a decimal value instead of an integer.
For example, consider an example of taking $n=4$ the example would fail as:
$$\lfloor \lg n \rfloor \le \lg n \le  \lceil \lg n  \rceil$$
Please help.
Thank you.

The expression $\lceil \log_2 n \rceil - 1$ for the height of a $n$-element heap is wrong.
For $n=1$ the expression yields $-1$ instead of $0$, for $n=2$ it yields $0$ instead of $1$, etc...
In general, for $i \in \mathbb{N}^+$, an heap with $2^i$ nodes has height $i$ but $\lceil \log_2 2^i \rceil - 1 = i-1$.
The equality $\lceil \log_2n \rceil -1=\lfloor \log_2 n\rfloor$ is also wrong, as it can be seen by picking $n=2^i$ for any $i \in \mathbb{N}^+$.


Kripke Models - evaluating the meaning of $\Box\Box p$ In Kripke models the evaluation of $x \vdash \Box p$ would be that every world reachable from $x$ satisfies $p$.

But how would the truth of $\Box\Box p$ be evaluated in Kripke models?

This is an unfortunate use of the word “reachable”, in that Kripke structures are graphs but “reachable” in a Kripke structure is not the same thing as “reachable” in a graph.  Let us avoid this confusion by saying that a state $y$ is a successor of state $x$ if there is a (directed) edge $(x,y)$ in the structure.

Now, the semantics of modal logic says that $\Box\varphi$ is true at state $x$ if, and only if, $\varphi$ is true at every successor of $x$. Informally, $\Box\varphi$ means, “$\varphi$ is true everywhere I can get to from here in one step.” So, to understand the meaning of $\Box\Box p$, just substitute $\Box p$ for $\varphi$:

$\Box p$ is true at every successor
$p$ is true at every successor of every successor.

In other words, $p$ is true everywhere I can get in two steps.  Note that this is not, in general, the same thing as $\Box p$, which means that $p$ is true after one step. Indeed, one can show that $(\Box \varphi)\rightarrow (\Box\Box\varphi)$ is a tautology in a particular Kripke frame if, and only if, the successor relation is transitive.

Note that, without assuming transitivity, basic modal logic with only $\Box$ and $\Diamond$ has no way of expressing “$\varphi$ is true everywhere that can be reached from here, in any number of steps” (i.e., the usual graph-theoretic meaning of “reachable”).


About trap states when converting DFA to regular expression If we were to have a trap state in a DFA and we are converting it to a regular expression, how exactly would I incorporate that into the regex? Let's say our language only accepts a*, and my DFA has a start state/final state with a a loop, and once I get a b it goes into a trap. Would the regex simply be a* meaning we ignore the b?

Yes, since the automaton can never accept after reading a $b$.


Conditional lower bounds on the running time of the single source shortest path problem Just out of curiosity, I was wondering whether there is a conditional lower-bound on the running time of an algorithm for the Single Source Shortest Path Problem (on directed or undirected graphs). I found papers with lower-bounds on some special models of computing such as PRAM or distributed systems but I was wondering if there is a well-known lower-bound based on the 3-sum, SETH or these kinds of conjectures.

I found a lower-bound on the decremental SSSP based on the online matrix vector hypothesis. Decremental SSSP is a dynamic version of SSSP where updates are edge-deletions. On the other hand, it is appearing clear to me, that typical conditional lower-bounds do not make sense for SSSP, since relevant conjectures show that the exponent can not be improved and do not exclude improvement of log factors. On the other hand, improving the exponent in SSSP means a sublinear algorithm which is excluded since the size of the input is a lower-bound on the running time of any problem.


Estimating (c-1) from approximation of c If we have a FPRAS for approximating the quantity c, can we get another FPRAS for estimating (c-1) using the estimation of c?

No. An FPRAS for a function $f$ must return an answer between $(1-\epsilon)f(x)$ and $(1+\epsilon)f(x)$ say 75% of the time. Therefore, if $f(x)=0$, an FPRAS for $f$ must return exactly zero, at least 75% of the time: an FPRAS must be able to reliably distinguish zero from non-zero. It does not, however, have to reliably distinguish $y$ from not-$y$ for any $y\neq 0$.

In more detail, suppose we have an FPRAS for a function $f(x)$ and we want to produce an FPRAS for $f(x)-1$.  If $f(x)=1$ for some $x$, the FPRAS will give an answer in the range $1\pm\epsilon$, 75% of the time. Just subtracting $1$ from the result of the FPRAS gives an answer within the range $\pm\epsilon$, 75% of the time but an FPRAS for $f(x)-1$ would have to give exactly zero, 75% of the time.


Problem with understanding two sided Matching Algorithm: maximium cardinality I am trying to understand the maximum cardinality problem in the context of stable matching algorithm. I am reading the following article at the link:

A Two-Sided Matching Decision Model Based on Uncertain Preference Sequences

The article says that:

  In general, we can categorize two-sided matching problem into three
  typical kinds of models in terms of different decision objectives:
  stable matching, maximum cardinality matching, and maximum weight
  matching. In the first model, the objective is to seek a stable matching
  solution, and we count a solution as stable matching only when there
  does not exist any alternative pairing (, ) in which  and  are
  individually better off than they would be with the element currently
  matched. Gale and Shapley put forward an approach, also named
  Gale-Shapley algorithm, to get a stable matching solution in the
  perspective of mathematics and game theory, which symbolizes the
  beginning of two-sided matching research and enlightens the subsequent
  scholars to pay more attention to this topic. In the second model, the
  objective is to seek a solution in which the number of matching pairs
  is maximized.

I am able to understand stable matching. I can’t understand how the number of matching pair is maximized. This may occur because we have 2 sets. One of boys and other of girls. One element in one set has more than
one matching in the other set. This might occur due to preference sequence.
Am I right about maximum cardinality?

What I understand preference sequence as the order of preferences of elements of one set for the other. Due to maximum cardinality, it is possible  that element
Of one set has same preferences for  multiple elements of the other set.

Am I right about preference sequences?

Somebody please guide me.

Zulfi.

The standard definition of the stable marriage problem is, given $n$ men and $n$ women, find a stable matching that marries all of the men and women.  Consequently, by definition, everyone will be matched and the number of matches will be exactly $n$ in any solution.  So, no, what you mention cannot happen, if you use that as the definition of the stable marriage problem.

I'm not 100% sure what your text is referring to when it talks about maximum cardinality matching, but I suspect it's referring to find a maximum matching in a bipartite graph, which is completely separate problem.  In this problem, the matching is not required to be a stable matching and it has nothing to do with the stable marriage problem.


Turing Machines: Arbitrary alphabet equivalence with binary alphabet Think of an $n$-ary alphabet as $\{0, 1, ..., n-1, n\}$. For example, a binary alphabet is $\{0, 1\}$.

  Do Turing Machines with binary alphabets decide the same set of languages as Turing Machines with $3$+ symbol alphabets?

I am unsure of how to show equivalence. Clearly, any $3$+ symbol TM can simulate a TM with $2$ symbols, but I don't know how to show the other direction (if one exists).

I am answering the question "Can Turing Machines with binary alphabet decide the same languages as Turing Machines with 3 or more alphabet symbols?"

Now, on the one hand, it's not well-defined what happens if you take a string with three different alphabet symbols and give it to a TM that only is designed to see a binary alphabet on the tape. So in that sense, a three-symbol Turing Machine can decide languages with these strings, while the two-symbol machine isn't allowed to read them. (For instance, if the language has "a", "b", and "c" in it, then there is no TM with a binary alphabet that reads these strings.)

But you might ask this question instead. Let's consider only languages whose strings have two symbols, in order to give a fair comparison between the two-symbol TM and the three-symbol TM. Now, can the three-symbol TM decide more of these languages, simply because it can write more types of symbols on the tape while it is computing?

The answer here is "no". The idea is that we have to take any three-symbol Turing Machine and show that there is a two-symbol TM that essentially takes the same "steps" and accepts whenever the original one accepts, etc. Just as a hint, the idea here is to make a TM with a modified transition table so that it can "act like" it's writing the third symbol down, even though it's only using two symbols.


How post correspondence problem is undecidable? An undecidable problem is a problem that cannot have any algorithm to solve it.

Post correspondence problem can be solved using a brute force approach. Then how can it be an undecidable problem?

Post correspondence problem can be solved using a brute force approach.

No. Brute force can be applied only if the number of dominoes we are going to use, is finite. For example, if we restrict each domino to be used at most once, then the number of possibilities will be finite and we can use a brute force algorithm.
 But the PCP allows us to use each domino as many time as we want, which makes the number of possible configurations infinite.

Proof of undecidability:
We will prove this by reducing "Acceptance problem of Turing Machine" to an instance of PCP. We already know that, acceptance problem of Turing Machine: $$ L^A = \{ <M,w> | M \:is \:a \:TM \:and \:M \:accepts \:w \} $$
is undecidable. Hence, if our instance of PCP is decidable, acceptance problem of Turing Machine will also be decidable, A contradiction.
The reduction involves making dominoes for all possible configurations of a TM when run on the input string. A full reduction can be found here. Let me know in the comments, if you need any clarifications on the reduction.


When does the nearest neighbor heuristic fail for the Traveling Salesperson? Can you provide an example of NN algorithm failure on the Euclidean traveling salesman problem?

I was trying to construct a specific example of this for my friends and was failing.

Consider a ladder

a----b----c
|    |    |
d----e----f

Say length of a-b is $2$ and length of a-d is $1$. The optimal route is a-b-c-f-e-d-a, $10$ units long. Starting at a, NN would produce a-d-e-b-c-f-a which is $7 + \sqrt{17} > 11$ units long.

There is actually a four node example, a rhombus

  A
 /|\
B-+-C
 \|/
  D

Say length of B-C is $10$, length of A-D is $24$ and thus length of A-B is $13$. The optimal route is A-B-D-C-A, $52$ units long. NN would produce the path A-B-C-D-A, $60$ units long.


Calculating positions of nodes relative to a known point If I know all the distances between a set of nodes and I also know that one of the nodes is at location (0,0), using the distances between the nodes, can I calculate the absolute positions between all of the nodes? I feel that this will involve some form of trilateration but only a single node position is known. Will I need an iterative algorithm to eventually find a unique solution?

I wrote an algorithm that determines a configuration if one exists, given a distance matrix. It repeatedly uses circle-circle intersection  to triangulate new nodes based on their distance to the first, second and third. As others have mentioned in comments, the first three points have some degree of freedom, which I've made assumptions for, in line with yours.

The code assumes all points are unique and invariant to changes smaller than a certain $\epsilon$.

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <cmath>

using namespace std;

const double epsilon = 0.00001;

struct Point {
    double x, y;
};

double dist(Point p, Point q) {
    return sqrt((p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y));
}

vector<Point> intersections(Point p, Point q, double pr, double qr) {
    double d = dist(p, q);
    if(pr + qr < d) return vector<Point>();
    if(min(pr, qr) + d + epsilon < max(pr, qr)) return vector<Point>();
    double a = (pr * pr - qr * qr + d * d) / (2.0 * d),
        h = sqrt(pr * pr - a * a);

    Point m = { p.x + (a * (q.x - p.x)) / d,
        p.y + (a * (q.y - p.y)) / d },
        r = { m.x + (h * (q.y - p.y) / d),
            m.y - (h * (q.x - p.x)) / d },
        s = { m.x - (h * (q.y - p.y) / d),
            m.y + (h * (q.x - p.x)) / d };

    return {r, s};
}

int main() {
    int N;
    cin >> N;

    vector<vector<double> > adj(N, vector<double>(N));

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> adj[i][j];
        }
    }

    vector<Point> ps(N);

    for(int i = 0; i < N; i++) {
        if(i == 0) ps[i] = {0.0, 0.0};
        else if(i == 1) ps[i] = { adj[0][1], 0.0 };
        else if(i == 2) {
            vector<Point> is = intersections(ps[0], ps[1], adj[0][2], adj[1][2]);
            if(is.empty()) {
                cout << "Invalid" << endl;
                return 0;
            }
            ps[i] = is[0];
        } else {
            vector<Point> first = intersections(ps[0], ps[1], adj[0][i], adj[1][i]),
                second = intersections(ps[1], ps[2], adj[1][i], adj[2][i]);
            if(first.empty() || second.empty()) {
                cout << "Invalid" << endl;
                return 0;
            }
            if(min(dist(first[0], second[0]), dist(first[0], second[1])) < epsilon) ps[i] = first[0];
            else if(min(dist(first[1], second[0]), dist(first[1], second[1])) < epsilon) ps[i] = first[1];
            else {
                cout << "Invalid" << endl;
                return 0;
            }
        }
    }

    for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) {
        if(abs(dist(ps[i], ps[j]) - adj[i][j]) > epsilon) {
            cout << "Invalid" << endl;
            return 0;
        }
    }

    cout << "Valid" << endl;
    for(const Point &p : ps) {
        cout << p.x << " " << p.y << endl;
    }

    return 0;
}

I haven't had time to comment the code. If you want me to, leave a comment. I took your drawing as a sample (which is invalid) and wrote another sample myself:

4
0 10 11 10
10 0 8 11
11 8 0 8
10 11 8 0

Invalid

4
0 4 5 3
4 0 3 5
5 3 0 4
3 5 4 0

Valid
0 0
4 0
4 -3
0 -3

As you can see, a valid configuration is printed if one exists. The complexity of the construction algorithm is $O(N)$, but we need to check if all matrix entries are valid after construction, which is $O(N^2)$.


How to generate all combinations given an array of elements using backtracking? Given an array, generate all combinations

For example:

Input: {1,2,3}

Output: {1}, {2}, {3}, {1,2}, {2,1}, {1,3}, {3,1}, {2,3}, {3,2}, {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1}

I am practicing Backtracking algorithms and I think I understand the general idea of backtracking. You are essentially running a DFS to find the path that satisfies a condition. If you hit a node that fails the condition, exit the current node and start at the previous node.

However, I am having trouble understanding how to implement the traverse part of the implicit tree.

My initial idea is to traverse down the left most path which will give me {1}, {1,2}, {1,2,3}. However, once I backtrack to 1, how do I continue adding the 3 to get {1,3} and {1,3,2} afterwards? Even if I have 2 pointers, I would need it to point to the 2 to eventually get {1,3,2}.

Am I approaching this problem correctly by drawing this implicit tree and trying to code it? Or is there another approach I should take?

I am not looking for code to solve this, rather I am looking for some insight on solving these kinds of questions.

I wrote the description below thinking that you were asking for all combinations of elements. However, at second glance it is unclear. I'll describe both cases.
Combinations
So let's talk about the number of combinations. If you're trying to pick $k$ numbers from $1,2,...,n$, there's $2^n$ ways.
$$\sum_{k=0}^n{n\choose k} = 2^n$$
This is a subtle hint that you can think of a combination as a set of binary choices. Let us have $n$ levels in our search tree, not including the root level. At level $i$, we give ourselves the choice to add or not to add element $i$ to our current combination. In this way, we construct a tree of uniform depth such that any path from root to leaf constructs a unique combination and we also claim that all possible combinations are represented by the tree. Now we can just compute a DFS, and every time our search reaches a leaf node, we add the current path to the list of combinations (If you're wondering how to keep track of the current path, there are already many posts/resources about that). If you prefer to do it recursively, this is also trivial.
The difficult part of these problems is indeed coming up with the representation. Let's go back and take a look at your original proposal.
Permutations
Again lets think of our choices at every step. We construct a tree to represent these choices. At a node $p$ at level $i$, we can select any of the remaining numbers not present in the path $root\rightarrow ...\rightarrow p$. Therefore, every root to leaf path in our tree now represents a permutation of all $n$ elements. In order to also get the permutations of subsets of $1,2,...,n$, we consider all paths in the tree beginning at the root as possible permutations.
This seems to be what your tree depicts, and it is a common way to view the problem. Simply performing a DFS while keeping track of the current path should be sufficient to obtain an answer.


Proving parametricity for Gallina functions I have the following definitions

Definition nat'' {X : Type} := (X -> X) -> X -> X.
Definition nat' := forall (X : Type), @nat'' X.

And when I wanted to prove a certain property I ended up in the following situation:

  m : nat'
  H : 0 = m nat S 0
  X : Type
  s : X -> X
  z : X
  ============================
  m X s z = z

which should be some kind of free theorem! Specifically, m: (forall X : Type), (X -> X) -> X -> X is a function that should behave parametrically for any instantiation of X, so by knowing that 0 = m nat S 0 I should be able to deduce that x = m X f x for any x : X and f : X -> X.

But I haven't seen such free theorems stated in Coq for Gallina terms. Is there an easy way to go about proving such a result without some deep embedding of a language and proving parametricity for this language?

My belief has always been that you cannot prove such free theorems from within Gallina about Gallina terms, but I don't have a definite reason why. I certainly can't imagine how this proof would work, given that there's no way to analyze functions like instances of nat' other than applying them.

As you mentioned, you can (in principle) do a parametricity proof for a deeply-embedded language.


Complexity of not P or EXPTIME Question 1: Is it possible to create an algorithm for deterministic Turing machine that will run not in P neither EXPTIME?

Question 2:
For me it seems that the answer for my question is it is impossible. If my reasoning is correct, it means that any function that describes complexity will have polynomial(x) or 2^polynomial(x) form.

Does my reasoning is correct?

A function $f(n)$ is time-constructible if there is a Turing machine that runs in time exactly $f(n)$, where $n$ is the input size (in bits). Kobayashi, in his paper On proving time constructibility of functions, showed that if $f(n)$ can be computed in time $O(f(n))$ then $f(n)$ is time-constructible. In particular, functions like $n^{\lfloor \log_2 n \rfloor}$ are time-constructible, even though they lie strictly between polynomial time and exponential time.

In fact, the time hierarchy theorem even shows that there are some decision problems which can be computed in time $O(n^{\log n})$ but not in polynomial time. This shows that there are problem not in $\mathsf{P}$ which can be computed in faster than exponential time.


What is the Pumping Lemma a lemma to? This is something I couldn't find - but I always found it interesting that the pumping lemma is just a lemma (especially since it has the same name for regular languages, context free languages, etc...)

What is it a lemma to?

In the foundational paper of Rabin and Scott, Finite automata and their decision problems, the pumping lemma appears as a lemma (Lemma 8) to the following result (Theorem 9):

  The language accepted by an $n$-state DFA is infinite if and only if it accepts some word whose length lies between $n$ and $2n$.

The pumping lemma implies the $\Longrightarrow$ direction.

It also "gives another proof" that the language $\{0^n 1 0^n : n \geq 0\}$ isn't regular (the original proof in the paper uses Myhill-Nerode theory).


Estimate complexity of integer sequence enumeration I would like to seek help on the complexity of the following problem.  Given positive integers $m$, $n$, $D_1$ and $D_2$, find all sequences $a_1\lt a_2 \lt  \dots \lt a_n$ are there such that:

each $a_i\in\{1, \dots, m\}$
$\sum_{i=1}^n a_i = D_1$
$\sum_{i=1}^n a_i^2 = D_2$.

I want to know the complexity with respect to $m$, $n$, $D_1$ and $D_2$.

For example, when $m=12$, $n=4$, $D_1=26$ and $D_2=214$ the solutions are

$$    3,5, 6, 12\qquad
    2, 5, 8, 11\qquad
    1, 7, 8, 10$$

Here is a simple recursive solution that runs in exponential time.

Geometrically you want to enumerate the lattice points which lies inside
the first quadrant of the $n$-hypercube of height $m$ and on the intersection of the $D_1$-radius $L_1$ sphere and the $D_2$-radius $L_2$ sphere (let call them respectively $S_1$ and $S_2$), up to reordering of the coefficients.

Denoting by $V_n$ the volume of the $n$  unit dimensional ball, we have :

$m^n/n!$ points in the intersection of the hypercube and the quadrant (let's call it $D$) with the ordering ,
$\alpha = O\left(m^n e^{\frac{-(D_1-nm/6)^2}{3nm}}\right)$ in $S_1\cap D$ (see theorem 1.3 of http://www.doiserbia.nb.rs/img/doi/1452-8630/2008/1452-86300802222R.pdf), considering the ordering condition.
$\beta = \frac{1}{n!2^{n}}V_n D_2^{n/2} + O\left(D_2^{n/2-1+\epsilon}\right)$ in $S_2$ (Generalized Gauss circle problem+quadrant condition+order condition). I'm not considering intersection with the hypercube here, so the global complexity will be an overestimation.

Depending on your parameters choose the minimum of $\alpha$ or $\beta$.
If its $\alpha$ perform a recursive enumeration of the integers partitions of length $n$ with the restriction on $m$ and use early abort to
discard solutions which are getting out $S_2$.
In the other case, enumerate the lattice point on $S_2$ ( with recursive orthogonal projections for instance) and check for the appartenance in $S_1$ for each returned vector.

Hence the global complexity will be dominated by $min(\alpha, \beta)$.


How do I form a parse tree for equations? I have the following equation

if (x > y) {
   if (y < a) {
     x:= a
     y:= b
   } else {
    x:= b;
   }
 }

I was thinking of something like this however I've never done it with actual functions so I'm not quite sure how to proceed.

What are the steps to take in creating a parse tree for something like this?

To produce a parse tree you need a string to parse, which you have, but
you also need a grammar to tell you how well-formed (legitimate)
strings are to be structured.

In your case you did not give a grammar. so that your question makes
no sense. Usually this is done with context-free grammars

Furthermore I suspect that what you really want is an abstract syntax
tree (AST), which is often very close to parse trees, but is supposed
to be defined more abstractedly (for example with a sorted algebra),
indpendently of any parsing process, and from which semantics is more
easily defined. Note that, while the AST may be defined independently of any arsing process, it is usually associated to textual representation via a parsing process, though other means do exist.

Below is what an AST could look like for your example. But, as for parse trees, an AST can be properly given only if you have defined formally what the abstract syntax is for your language.

To be very complete, you need at least one formal definition that relates tree structures you may be interested in (parse trees or AST) for your text with corresponding textual strutures.

              if
     ________/|\________
    /         |         \
   >          if        :=
  / \    ____/|\____   /  \
 x   y  /     |     \ x    b
       <     :=     :=
      / \   /  \   /  \
     y   a x    a y    b

Warning: the referenced wikipedia articles could be much improved, at least on the pedagogical side.


Short quiz about Myhill-Nerode theorem Given is DFA M:

1.) abb and bbb

2.) baa and ab

3.) a and ε (where ε is the empty word)

4.) abb and baa

If I understood correctly, x and y are equivalent to each other (in terms of Nerode), if you add the same suffix for both such that they can be read by the DFA, e.g. they are in L(M)

Thus 1.) is false because abb throws us into the "endless" state 5, there is no escape and thus no suffix.

2.) Is true, simply add suffix aa and both words will still be accepted.

3.) True, take a as suffix.

4.) False, same reason as 1.) you get into the endless state and there is no escape, thus no suffix.

Can you confirm if this is correct? Or did I understand the entire concept wrong? :o

You are mistaken. Strings $x$ and $y$ are equivalent modulo the language $L$ iff for  all suffixes added to the words the results are both in or both outside of the language:

$x\sim_L y$ iff $xw\in L \iff yw\in L$ for every $w$.

In particular, when the strings $x$ and $y$ end in the same state for the (deterministic) automaton $M$, then $x\sim_{L(M)} y$, as they can be extended by exactly the same strings. This also holds for the dead-end state where no strings can extend the original string to acceptance.


Where is the problem in this proof that deciders are no stronger than LBAs? So I've been working on a problem for fun and I'm worried I've run into some sort of contradiction, so I'm trying to figure out where I went wrong. I've simplified the issue down to this:
Decider acceptance can be reduced to LBA acceptance
Part 1: A decider can be reduced to a decider with an empty input alphabet.

Let $D$ be a decider with input alphabet $\Sigma$ and $\omega$ be an input string in $\Sigma^*$

Construct a decider $D_0$ with an empty input alphabet and the same tape alphabet as $D$, which starts by writing the characters of $\omega$ to the tape, returns to the left side, and then executes identically to $D$

$D_0$ accepts the empty string $\epsilon$ iff $D$ accepts $\omega$

Part 2: A decider with an empty input alphabet can be reduced to an LBA

Let $D_0$ be a decider with an empty input alphabet

$D_0$ halts in finite time, and therefore uses finite portion of the tape of size $m$

Construct an LBA $A$ with the same states, symbols, and transitions as $D_0$ where the length of the tape is given by linear function $f(x)=x+m$

The only possible input is $\epsilon$, so the size of the tape will be $m$, so $A$ will execute identically to $D_0$ and not go out of bounds

$A$ accepts $\epsilon$ iff $D_0$ accepts $\epsilon$

This seems to prove that a decider can be reduced to an LBA, which is well known to be incorrect. I have a couple of guesses for where the error might be:

It could be in part 1, if you can't call a machine without input as
powerful as a machine with input. After all, the only languages $D_0$
could accept are $\emptyset$ and $\{\epsilon\}$, which are both
regular, not recursive. So you can't say that an input-less decider
accepts the same set of languages as a decider, but maybe it's as
"powerful" in a more abstract sense?

It could be in part 2, with the main problem being that computing $m$
would require running the decider, so the reduction to the LBA would
be just as difficult as the acceptance problem. In other words, does
the information you have prior to running automata change how
powerful you can consider the automata to be?

Basically, I'm wondering if either of these concerns is the actual issue or if it's something else. And if either of these concerns isn't actually an issue, could you explain why? Thanks!
Edit: As pointed out, I should've represented these as decision problems, so part 1 would be a reduction from $\{(D,\omega) | D\textrm{ is a decider that accepts } \omega\}$ to $\{D_0 | D_0 \textrm{ is an inputless decider that accepts}\}$ and part 2 a reduction to $\{A | A\textrm{ is an inputless LBA that accepts}\}$. I believe the first two of these problems are recursive and the third is context-sensitive, so the first reduction is possible but the second isn't, due to $m$ not being computed.

You seem to be mixing some concepts. Over an empty input alphabet, there are no decision problems, so as a model, Turing machines with empty input alphabets are not interesting.
It is true that the problem of deciding whether a given TM accepts the empty word is interesting (and undecidable), but it's not the same thing as having an empty input alphabet.
So the "reductions" you describe are not exactly reductions in the formal sense, just some translations between models.
As for a concrete problem with your argument: first, an LBA runs on a fixed portion of the tape which is prescribed by the input length. If you have an empty input, the LBA is not allowed to touch the tape, so it can't really do anything. An LBA doesn't just mean that the space is linear in the input. So you can't manually add the "m" input cells. This breaks your argument.
But also note that the definition of the function $f(x)=x+m$ is a bit strange, since on an empty input alphabet, you always have $x=0$.


How to show a language is regular through creating DFA I'm trying to prove that a given language is regular through proving that a DFA can be created from it, but have problems with how to the DFA should look.

The alphabet is $\Sigma=\{0, 1\}$ and the language is:
$$L = \{x \in \Sigma^*\mid \#_0(x)>\#_1(x)\text{ and }\#_1(x)\leq3\}\,,$$ where $\#_i0(x)$ means the number of $i$s in $x$.

When I should send it to a dead/trap state and what should the DFA look like?

As with any automaton, the states need to encode all the information you need to decide whether or not to accept the string you've read so far. In this case, that means that number of $0$s and $1$s that you've seen. Except you can't quite do that, because that would require infinitely many states. However, if you look more closely at the definition of the language, you'll see that you don't need to know the exact number of $0$s and $1$s: for example, if you've seen six $1$s, that's the same as seeing seven, or a million.

Once you've worked out what the states are, work out what the transitions between them are. You'll find that you have a trap state, without needing to figure out what it should have been. Trap states occur "naturally", whenever you've seen enough of the input to be able to say, "I don't care what else I see: I'm rejecting this string!"


How to prove these two distributions are statistically/computationally indistinguishable First we generate a key,
$$k \leftarrow \{\, 0,1 \,\}^{n}$$
And we construct two PPT algorithms $A$ and $B$ as follow:

$$A_{k}\left( \cdot \right) \colon y_{A} \leftarrow k, \text{ return } y_{A}$$
and
$$B_{k}\left( \cdot \right): y_{B} \leftarrow \{\, 0,1 \,\}^{n}, \text{ return } y_{B}$$

For fixed $k$, let $D_{A}$ be the distribution of $A$, and $D_{B}$ be the distribution of $B$. I want to know whether $D_{A}$ and $D_{B}$ are statistically indistinguishable or computationally indistinguishable.

In my opinion, $D_{A}$ is a one-point distribution and $D_{B}$ is a uniform distribution. Thus they are not statistically indistinguishable.

Let
$$A^{\prime}\left( \cdot \right) \colon k \leftarrow \{\, 0,1 \,\}^{n}, y_{A^{\prime}} \leftarrow A_{k}\left( \cdot \right), \text{ return }  y_{A^{\prime}}$$
and
$$B^{\prime}\left( \cdot \right) \colon  k \leftarrow \{\, 0,1 \,\}^{n}, y_{B^{\prime}}, \leftarrow B_{k}\left( \cdot \right), \text{ return } y_{B^{\prime}}$$
then $D_{A^{\prime}}$ and $D_{B^{\prime}}$ are statistically indistinguishable, thus they are also computationally indistinguishable.

Is my method correct? It looks strange and it seems that $k$ is not fixed when I show that they are computationally indistinguishable. Is there a better method from a clear view about the computationally indistinguishable and statistically indistinguishable?

Thanks for @D.W.♦'s answer, if $k$ is fixed, then $k$ is not a random variable anymore. Thus, there are 4 kinds of distributions.

Type (1)

  For $k \leftarrow \{\, 0,1 \,\}^{n}$, $A_{k}$ and $B_{k}$ (given the knowledge of $k$) are computationally indistinguishable if for all PPT adversary $\mathcal{A}$ such that
  $$\left\vert \Pr \left[  k \leftarrow \{\, 0,1 \,\}^{n}; \mathcal{A} \left(k, A_{k} \left( \cdot \right) \right) = 1 \right] - \Pr \left[ k \leftarrow \{\, 0,1 \,\}^{n}; \mathcal{A} \left(k, B_{k} \left( \cdot \right) \right) = 1 \right] \right\vert < \varepsilon(n) $$

Type (2)

  For $k \leftarrow \{\, 0,1 \,\}^{n}$, $A_{k}$ and $B_{k}$ are computationally indistinguishable if for all PPT adversary $\mathcal{A}$ such that
  $$\left\vert \Pr \left[  k \leftarrow \{\, 0,1 \,\}^{n}; \mathcal{A} \left( A_{k} \left( \cdot \right) \right) = 1 \right] - \Pr \left[ k \leftarrow \{\, 0,1 \,\}^{n}; \mathcal{A} \left( B_{k} \left( \cdot \right) \right) = 1 \right] \right\vert < \varepsilon (n) $$

Type (3)

  For $k \in \{\, 0,1 \,\}^{n}$, $A_{k}$ and $B_{k}$ (given the knowledge of $k$) are computationally indistinguishable if for all PPT adversary $\mathcal{A}$ such that
  $$\left\vert \Pr \left[ \mathcal{A} \left(k, A_{k} \left( \cdot \right) \right) = 1 \right] - \Pr \left[ \mathcal{A} \left(k, B_{k} \left( \cdot \right) \right) = 1 \right] \right\vert < \varepsilon(n) $$

Type (4)

  For $k \in \{\, 0,1 \,\}^{n}$, $A_{k}$ and $B_{k}$ are computationally indistinguishable if for all PPT adversary $\mathcal{A}$ such that
  $$\left\vert \Pr \left[ \mathcal{A} \left( A_{k} \left( \cdot \right) \right) = 1 \right] - \Pr \left[ \mathcal{A} \left( B_{k} \left( \cdot \right) \right) = 1 \right] \right\vert < \varepsilon (n) $$

To make it clear, I just want to know (4) holds true or not. And my original method confuses the definition between (2) and (4).

I think it may be helpful after we analyse the relation among these 4 types.

Obviously, "(1) holds true" $\Leftrightarrow$ "(3) holds true", since for all the PPT $\mathcal{A}$,
$$\Pr \left[ \mathcal{A} \left(k, A_{k} \left( \cdot \right) \right) = 1 \right] = \Pr \left[  k \leftarrow \{\, 0,1 \,\}^{n}; \mathcal{A} \left(k, A_{k} \left( \cdot \right) \right) = 1 \right]$$

And "(1) holds true" $\Rightarrow$ "(2) holds true" is also easy to prove.

However I still cannot find a clear proof about the relation between (3) and (4).

I think your problem is in trying to insist that $k$ is fixed.  That's getting you tied up in knots.

The statement "for fixed $k$, define $D_A$ to be the distribution..." makes no sense to me, because as you have previously defined $k$, $k$ isn't fixed -- $k$ is defined to be a random variable (that is uniformly distributed on $\{0,1\}^n$).  So, it looks to me like you are contradicting yourself.

Instead, let me suggest a better way to think about indistinguishability. Think about indistinguishability as a random experiment.  There is a formal definition of indistinguishability.  In that definition, we define an experiment.  The experiment works by running some algorithms that we have fully specified, and then observing the result.  As part of this you will need to fully specify the probability space and the event you care about.  For instance, if $F,G$ are two algorithms that depend only on a key $k$, then we might define them to be computationally indistinguishable if there does not exist a polynomial-time algorithm $A$ such that

$$|\Pr[k \leftarrow \{0,1\}^n ; A(F(k)) = 1] - \Pr[k \leftarrow \{0,1\}^n ; A(G(k)) = 1]|$$

is non-negligible.  That's a standard definition of computational indistinguishability.  Notice that the event $k \leftarrow \{0,1\}^n ; A(F(k)) = 1$ (and corresponding probability space) is fully defined, by defining some algorithms and then asking about the probability that it outputs 1.  Everything can be expressed as a statement about some random variable, where the random variable is defined by executing a well-specified algorithm (i.e., in pseudocode).  There is no step halfway along that says "fix $k$" (it's not even clear to me what that would mean).

The idea here is that we want to make a statement about the probability of some event.  That event is defined in terms of running a randomized algorithm and checking its output.  This is a well-defined and precise way to define an event in some probability space.  Once you start trying to add "fix $k$" in the middle of that, we lose that property and it's not clear what you mean.

So, stick with the standard definitions, and try to apply them as is.  Don't try to create your own definition.  Or, if you insist on it, first translate your idea to a statement about a probability of some event where the event is defined in terms of a well-specified randomized algorithm.  You should be able to write pseudocode for each step of your algorithm, without needing English (like "fix $k$").  If you try to do that for your idea, probably you'll find that at one step along the way your pseudocode assigns to $k$ (say, by picking a random value from $\{0,1\}^n$), and then $k$ is whatever it is (if it is picked randomly, then it's not fixed; it's a random variable).

For example, here is one fact that is true.  If we define $X$ by $k \leftarrow \{0,1\}^n; X \leftarrow k$ and $Y$ by $k \leftarrow \{0,1\}^n; Y \leftarrow \{0,1\}^n$, then $X,Y$ are computationally indistinguishable and statistically indistinguishable (just apply the definition and see what you get).  Same if you define algorithms $A,B$ as in your question and define $X$ by $k \leftarrow \{0,1\}^n; X \leftarrow A_k()$ and $Y$ by  $k \leftarrow \{0,1\}^n; X \leftarrow B_k()$.

However, if you give the adversary knowledge of $k$, they are no longer distinguishable.  Thus, for instance,

$$|\Pr[k \leftarrow \{0,1\}^n ; \mathcal{A}(A_k()) = 1] - \Pr[k \leftarrow \{0,1\}^n ; \mathcal{A}(B_k()) = 1]|$$

is negligible for all adversaries $\mathcal{A}$, but

$$|\Pr[k \leftarrow \{0,1\}^n ; \mathcal{A}(k,A_k()) = 1] - \Pr[k \leftarrow \{0,1\}^n ; \mathcal{A}(k,B_k()) = 1]|$$

is not.

As an aside, often we use $A$ to represent the adversary/attacker, so using $A$ to represent some other algorithm can potentialy get a little confusing.


Address Word Structure In Vol. 1 Issue 1, Jan. 1958 of the magazine Communications of the ACM, Dr. Saul Gorn discusses the advantages of the computer architecture of Edvac to that of Eniac.

He states that the Edvac had a three-plus-one address word structure, and that the tendencies of his time period were to use one-address hardware and three-plus-zero address pseudo-codes. He then goes on to say that for the future he imagines using variable instruction-word-length machines.

My questions: What is a three-plus-one address word structure? What is a one-address hardware and three-plus-zero address pseudo code? What do these terms mean exactly? I understand what a word is, but not to an extent that would allow me to understand these terms contextually.

Link to this issue of CACM: here. I believe an ACM membership is required to access the magazine. This question refers to Dr. Saul Gorn's Letter to the Editor.

The EDVAC employed a 44 bit word with a 4 bit op code and 4 10 bit address fields.

While the use of the fields varied a lot, the ADD instruction was typical. The memory location in field 1 was added to the memory location in field 2 and the result placed into the memory location in field 3. Execution of code then continued at the location addressed by field 4.

Thus we can summarize C = A + B; GOTO D

As for simulation with pseudo codes, we can deduce that for the Accumulator + One address machines popular at the time, the C = A + B would be simulated with three instructions and the GOTO part would be omitted. Thus three-plus-zero. It might look something like (stylized not actual code):

; ADD A,B,C
LD Acc, A
ADD Acc, B
ST Acc, C

For more on EDVAC please see:

https://babel.hathitrust.org/cgi/pt?id=mdp.39015002095639;view=1up;seq=87


Does the BIOS run on the CPU? I was just thinking about this: Does the BIOS execute on the CPU? If so, how does it handle multiple CPU architectures/instruction sets? If not, what does it execute on?

Yes, the processor itself runs the BIOS boot program. Each motherboard has to be equipped with appropriate BIOS that a processor of compatible chip set can use.


How do you find the height of the recurrence tree $T(n,k)=T(\frac{n}{2},k)+T(n,\frac{k}{4})+nk$ I try to find tree height such that first i define:
$H(n,k)=H(\frac{n}{2},k)+H(n,\frac{k}{4})+1$
then find height of left branch of tree=logn & right branch of tree=logk,but now why height of tree is equal to logk+logn?i guess height of tree is Max(logn,logk)why my geuss is not true?

Here is a recursive definition of a height of a tree $T$:

If $T$ is a leaf, then its height is 0 (some people prefer to use 1).
Otherwise, the height of $T$ is the maximum height of any of its children, plus 1.

Equivalently, the height of a tree is the maximum length of a root-to-leaf path (in edges; if you measure it in vertices, leaves should have height 1).
This makes it clear that the correct recurrence for the height is
$$
H(n,k) = \max(H(\tfrac{n}{2},k), H(n,\tfrac{k}{4})) + 1,
$$
with an appropriate base case. The solution is roughly $\max(\log_2 n, \log_4 k)$, depending on the base case.


Can the concatenation of two non-regular languages be regular? Can anyone give an example of two non-regular languages $A, B \subseteq \{0, 1\}^∗$ for which the language $AB$ is regular?

Hint: Let $C$ be the language of words that have the same number of 1's as 0's.  Is $C$ regular?  Let $A = \{0,1\}^* \setminus C$.  Is $A$ regular?  Now, can you find a non-regular language $B$ that will make $AB$ regular?


Compute highest-scoring segmentation I have the following problem:

There is a "clean" sequence of sequences, say:

clean = [
    [1, 2],
    [3],
    [4, 5]
]

And a "noisy" sequence which is not segmented:

segmented = [1, 100, 2, 3, 3, 101, 4, 5]

I would like to partition segmented into exactly len(clean) parts such that the sum of the edit distances of each part and its clean counterpart is minimized.

For this example, one optimal solution would be:

optimal = [
    [1, 100, 2], # edit distance 1
    [3, 3],      # edit distance 1
    [101, 4, 5]  # edit distance 1
]                # total 3

It seems like a typical dynamic programming problem. My first thought was to use a similar algorithm to what TeX uses for line breaking, which brought me to SMAWK.

This is where I am stuck, because I cannot figure out the cost function. For regular line breaking, the function cost(i,j) is the cost of having a line go from index i to index j, like here. But for this problem, we would need a third parameter, namely which line in the clean reference to compare to.

Is this problem not conditioned correctly for SMAWK? Or is there a different cost function definition that I'm missing?
Is there another, similar problem which has a more applicable solution?

I would suggest letting cost(i,j,k) be the cost of transforming [the first i-1 segments of clean, followed by the first j elements of the ith segment of clean] into [the first k elements of segmented].

You can then write a recurrence relation that expresses cost(i,j,k) in terms of values of cost(i,j-1,k), cost(i,j,k-1), and cost(i,j-1,k-1) (with a convention that cost(i,0,k) = cost(i-1,len(clean[i-1]),k)).  Then, you can use dynamic programming to fill in these values.


Find a node with maximum distance from query node in a tree I solved this problem from codechef:
problem link

and now I want to change it a bit. Instead of find out the distance between node $u$ and $v$ I want to answer $k$ queries of the form: find node $u$ to which distance from node $v$ is maximum but I'm not able to see fast enough algorithm for it.
I think that heavy light decomposition is still my best option. Do you have any ideas?

Finding node to which distance is maximum in this way is $O(n)$ but the challenge here is that I have to answer to $k$ queries so the total complexity is $O(nk)$. I believe that this can be done in $O((n+k)\log n)$.

Start from any node and find (say, with a BFS) a farthest node from it; call it $u$. Then start from $u$ and find a farthest node from it; call it $v$. Nodes $u$ and $v$ achieve the absolute maximum distance in the tree.

Now with 2 more BFS, find the distances of all nodes from $u$, and the distances of all nodes from $v$. At this point you are ready to answer the queries: for each queried node $z$, the most distant node is either $u$ or $v$, depending on which has the larger distance. This solves your problem in $O(n + k)$ time.


Computational complexity of function $U^V$ Given $(U,V)$ two integers of finite size, I have a question about the complexity of calculating the $V^U$, i.e. $V$ raised to the power $U$. Is their a polynomial time algorithm to do this? If not is this an NP-hard problem?

One way to do this is by repeated squaring. First, express $V$ in binary,
$$
V = b_0+2^1b_1+2^2b_2+2^3b_3+\dotsm+2^nb_n
$$
where each  $b_i$ is either zero or one. Having done this, repeatedly square $U$ to get $U, U^2, (U^2)^2 = U^4, (U^4)^2=U^8, \dotsc, U^{2^n}$. Then
$$\begin{align}
U^V&=U^{b_0+2^1b_1+2^2b_2+2^3b_3+\dotsm+2^nb_n}\\
   &=(U^{b_0})((U^2)^{b_1})((U^4)^{b_2})\dotsm((U^{2^n}))^{b_n})
\end{align}$$
For example, to compute $3^{21}$ we would get the binary expansion of $21=16+4+1$ and then repeatedly square the $3$s:

$$\begin{align}
3^1 &=3\\
3^2 &=9\\
3^4 &=81\\
3^8 &=81^2=6561\\
3^{16} &= 6561^2=43046721
\end{align}$$
So we'll have
$$
3^{21}=3^{16+4=1}=(3^{16})(3^4)(3^1)=(43046721)(81)(3)=10460353203
$$
Consider the worst case, with $V=2^n-1$, and let $d$ be the number of bits in the representation of $U$. This will require $n-1$ squarings. Let's use the grade-school multiplication algorithm, for which the product of two $k$-bit numbers will take $O(k^2)$ primitive operations. We'll then have
$$\begin{array}{ccc}
\text{product}& \text{factor size} & \text{ops needed}\\
U^2 & d & d^2\\
U^4 & 2d & 4d^2\\
    & \dotsc & \\
U^{2^{n-1}} & 2^{n-2}d & 4^{n-2}d^2
\end{array}$$
So the total number of operations needed to precompute the squares will be
$$
(1+4+4^2+\dotsm+4^{n-2})d^2 = O((2^n)^2d^2) = O(V^2\log^2U)
$$

Now since we chose $V$ so that it involved all of the squares we computed, we'll have the final product $(U)(U^2)(U^4)\dotsm(U^{2^{n-1}})$. Mirroring the construction above, we find that the final product will also take $O(V^2\log^2U)$ operations, so to compute $U^V$ by repeated squaring will take time $(2^nd^2)$ where $n, d$ are the number of bits in $V$ and $U$, respectively. Unfortunately, this means that this construction is not polynomial in the size of $V$.

Notes.

In your original question, strictly speaking, the classes P, NP, Np-complete and NP-hard are generally applied to decision problems, which this isn't.
There are faster ways to compute the product of two integers, so you can actually do better than $O(V^2\log U)$.
While this (as it turns out) is actually less efficient than the naive algorithm of computing $U^V$ by successive multiplications, $U, U^2, U^3,\dotsc$, it works very well when computing modular powers, $U^V\pmod W$, since none of the intermediate products will ever be larger than $W$.


Data hazard after in load word after addi 5 stage pipline

addi $t1,$zero,0x30
lw $t2,0($t1)
sw $t2,0xff18($zero)
addi $t2,$zero,100

Question is to find hazards existing in the code and the answer is:

Hazard 1: Between lines 1 and 2. Register t1. Solved using
forwarding.
Hazard 2: Between lines 2 and 3. Register t2. Solved using
forwarding.

But I found the answer is rather strange,

So there is a hazard between line 1 and 2, in the first line t1 writes back in the fifth stage, and in the second line t1 uses in the decode stage, in my opinion there should be a stalling first and then forward to have access to t1 in the second line.
I don't see a hazard between line 2 and 3? line 2 t2 write back in the fifth stage, and line 3 fetches t2 in the first stage

Am I thinking something strange, why the correct answer seems not correct to me?

THe answers are correct.
There is a data hazard when the information stored in the "regular" location (generally a data reg) is incorrect with respect to the program flow.

Here information copied in the ID stage at line 2 will be the previous value of $t1, as the new one will be copied at the end of WB stage of instruction 1 (and hence at the end of MEM stage of instr 2).

Forwarding means discarding the regular information and replacing it by the new (and correct value).
It can be done

1/ as soon as the new value is available in the processor. Lets call t_a this time

2/ up to the last time that this information is required (because it will be transformed by the ALU, written to the mem, etc). Lets call t_u this instant

If t_a <= t_u, simple forwarding can be done. Otherwise one or more stalls are required.

Lets look at the code

1 addi $t1,$zero,0x30
2 lw $t2,0($t1)

Say Stage IF of instr 1 is t1, ID t2, etc

1 the new value of $t1 will be available at the end of stage WB (t5)

2 the value of $t1 is read at the start of ID stage (t3)

There is a data hazard.

When is the information associated with $t1 available ? After EX stage of 1. So t_a=t3

When is the last time that this information is required by instruction 2 ? Just before the adresse (0+$t1) is computed by the ALU. I.e. t_u=t4

There is no need of any stall. The value read in $t1 register is just discarded and replaced by the one in the ppline register.

Consider now instructions 2 and 3.

2 lw $t2,0($t1)
3 sw $t2,0xff18($zero)

There is a hasard as  $t2 is written at the end of WB stage of inst 2 (t6) and read at the beginning of ID stage of inst 3 (t4).

When if the information associated with $t2 available in the processor. At the end of MEM of instr 2 it is written in some ppline reg of the proc (t5=t_a).

When is this information required ? Just before writing to the memory by inst 3. After it is too late. That is at the start of MEM stage of inst 3 t6=t_u.

Again a simple forward can solve the problem.

(note that if instr 3 had been
sw $t5,0xff18($t2)
the situation would have been different. $t2 would have been required for the address computation (start of EX stage of inst 3 at t5), that is before its production (end of MEM of instr 2 t5), and a stall would have been required over the forwarding.)