Are there polynomial time reductions where the corresponding witnesses can't be translated in polynomial time? At the heart of NP-completeness is the idea that one can reduce instances of any problem in NP to, for example, 3-SAT. But this definition doesn't require that it must be possible to convert witnesses for yes-instances in polynomial time also. Does this fact follow regardless?
I'm looking at this in particular from the point of view of zero-knowledge proofs. Here the existence of computationally zero-knowledge proofs for all problems in NP is demonstrated by showing that 3-colorability has such proofs. But the guarantee that I can translate problems - or "conjectures" - in polynomial time is useless. I need to be able to translate witnesses - or "proofs". How is the possibility of this assured?

The proof of the Cook-Levin theorem shows that any problem in NP can be reduced to SAT in such a way that witnesses to the original problem can be converted efficiently to satisfying assignments of the resulting SAT instance. The proof of the NP-completeness of 3-colorability goes via a series of reductions, each of which also has this property.


Dynamic programming - maximize sum of functions subject to constraints Let $\{f_i\}_{i=1}^{k}:[0,k]\to\mathbb{Z}$.

The problem: Maximize the sum $\sum_{i=1}^{k}f_i(x_i)$ subject to the the constraint $\sum_{i=1}^{k}x_i\le k$

I think we suppose to come up with a polynomial time solution, but i got stuck on identifying the sub-problems and using them.

One direction that i had was creating a list for each function, where both the arguments and the function values are in decreasing order: in each iteration, find the argmax of the function, delete bigger arguments that yield smaller function values, and proceed with the smaller arguments that remain (($O(k^3)$ for all functions).

Then  use those lists to iterativly construct the optimal solution under the constraint for 1, 2, .. and finally for all $k$ functions, Got stuck about here. Not sure if it's a good direction at all...

Would appreciate any assistance.

Let us read the objective again, "maximize the sum $\sum_{i=1}^{k}f_i(x_i)$ where $\sum_{i=1}^{k}x_i\le k$."

The subproblems or the table entries are $DP[a][b]$ for all $0\le a\le k$ and $0\le b\le k$, where $DP[a][b]$ is the maximum value of $\sum_{i=1}^{a}f_i(x_i)$ where $\sum_{i=1}^{a}x_i=b$. The wanted maximum sum is the maximum of $DP[k][0],DP[k][1], \cdots, DP[k][k]$.

The base cases is $DP[1][b]=f_1(b)$ for all $b$.

How to reduce the computation of $DP[a][b]$ to smaller subproblems? The following equality is the critical observation, which is the reason why we have the first dimension "[a]" in the formulation of the subproblems. The other dimension "[b]" comes from the constraint $\sum_{i=1}^{a}x_i=b$.

$$\sum_{i=1}^{a}f_i(x_i) = \sum_{i=1}^{a-1}f_i(x_i) + f_a(x_{a}),$$
i.e., $DP[a][b]$ is the maximum of the following numbers,
$$\begin{aligned}
&DP[a-1][b] + f_a(0),\\
&DP[a-1][b-1] + f_a(1),\\
&\cdots,\\
&DP[a-1][0] + f_a(b).\\
\end{aligned}$$

Exercise 1. Using dynamic programming to maximize the sum $\sum_{i=1}^{k}f_i(x_i)$ subject to the the constraint $\sum_{i=1}^{k}x_i\le n$, where $n$ is a given integer.

Exercise 2. Using dynamic programming to maximize the sum $\sum_{i=1}^{k}f_i(x_i)$ subject to the the constraint $\sum_{i=1}^{k}x_i= n$, where $n$ is a given integer.

Exercise 3. Using dynamic programming to maximize the sum $\sum_{i=1}^{k}f_i(x_i)$ subject to the the constraint that for all $j$, $|x_{j+1}-x_{j}|\le n$, where $n$ is a given integer.


What is the runtime of Mergesort if we switch to Insertion Sort at logarithmic depth? Consider the Mergesort algorithm on inputs of size $n = 2^k$. Normally, this algorithm would have a recursion depth of $k$. Suppose that we modify the algorithm so that after $k/2$ levels of recursion, it switches over to insertion sort. What is the running time of this modified algorithm?

I know that MergeSort has worst-case runtime of $O(n \log n)$ and Insertion Sort has worst-case runtime of $O(n^2)$, but I'm not sure how these bounds will be affected within the problem above.

You know that MergeSort has a complexity of $O(n\log n)$. Why? We can write a recurrence for the running time of MergeSort:
$$ T(n) = 2T(n/2) + Cn, \quad T(1) = D. $$
(Assume for simplicity that $n$ is a power of 2.) The solution is $T(n) = O(n\log n)$. Why? Since we can write
$$ T(n) = 2T(n/2) + Cn = 4T(n/4) + Cn + Cn = 8T(n/8) + Cn + Cn + Cn = \cdots = (\log n)Cn + Dn. $$
That is, at each internal level the total complexity is $Cn$, there are $\log n$ levels, and at the bottom the complexity is $Dn$. It is instructive to rewrite it in terms of $n = 2^k$:
$$ T(2^k) = 2^1T(2^{k-1}) + C2^k = 2^2T(2^{k-2}) + C2^k + C2^k = \cdots. $$
In your case, you want to stop the recursion at depth $k/2$, and instead of expanding $2^{k/2}T(2^{k/2})$ using the recursion, apply the $En^2$ insertion sort algorithm. What would you get? (that's a question for you)


Intuition behind the Hadamard gate I'm trying to teach myself about quantum computing, and I have a decent-ish understanding of linear algebra.

I got through the NOT gate, which wasn't too bad, but then I got to the Hadamard gate. And I got stuck. Mainly because while I "understand" the manipulations, I don't understand what they really do or why you'd want to do them, if that makes sense.

For example, when the Hadamard gate takes in $|0\rangle$ it gives $\frac{|0\rangle + |1\rangle}{\sqrt{2}}$. What does this mean? For the NOT gate, it takes in $|0\rangle$ and gives $|1\rangle$. Nothing unclear about that; it gives the "opposite" of the bit (for the superposition, it takes in $\alpha|0\rangle+\beta|1\rangle$ and gives $\beta|0\rangle + \alpha|1\rangle$) and I understand why that is useful; for the same reasons (basically) that it is useful in a classical computer. But what (for example) is the Hadamard gate doing geometrically to a vector $\begin{bmatrix}\alpha \\ \beta \end{bmatrix}$? And why is this useful?

The Hadamard gate might be your first encounter with superposition creation. When you say you can relate the usefulness of the Pauli $X$ gate (a.k.a. NOT) to its classical counterpart – well, Hadamard is exactly where you leave the realm of classical analogue, then. It is useful for exactly the same reason, however, namely that it is often used to form a universal set of gates (like clasical AND with NOT and fan-out, or NOR with fan-out alone).

While a single $H$ gate is somewhat directly useful in random number generation (as Yuval Filmus said), its true power shows when appearing in more instances or in combination with other gates. When you have $n$ qubits initialized in $|0\rangle$, for example, and apply one $H$ to each of them in any order, what you get is
$$(|0\rangle + |1\rangle) \otimes (|0\rangle + |1\rangle) \otimes \ldots \otimes (|0\rangle + |1\rangle) / 2^{n/2}$$
which can be expanded to
$$1/2^{n/2} \cdot (|00\ldots00\rangle + |00\ldots01\rangle + |00\ldots11\rangle + \ldots + |11\ldots11\rangle)$$
Voilà, we can now evaluate functions on $2^n$ different inputs in parallel! This is, for example, the first step in Grover's algorithm.

Another popular use is a Hadamard on one qubit followed by a CNOT controlled with the qubit you just put into a superposition. See:
$$CNOT \big(2^{-1/2}(|0\rangle+|1\rangle)\otimes|0\rangle \big) = 2^{-1/2} CNOT(|00\rangle + |10\rangle) = 2^{-1/2} (|00\rangle + |11\rangle)$$
That's a Bell state which is a cornerstone of various quantum key distribution protocols, measurement-based computation, quantum teleportation and many more applications. You can also use a CNOT repeatedly on more zero-initialized target qubits (with the same control) to create
$$2^{-1/2} (|00\ldots00\rangle + |11\ldots11\rangle)$$
which is known as the GHZ state, also immensely useful.

Last but not least, it's a quite useful basis transform that is self-reversible. So another Hadamard gate undoes, in a sense, what a previous application did ($H^2 = I$). You can experiment around what happens if you use it to "sandwich" other operations, for example put one on the target qubit of a CNOT gate and another after it. Or on both of the qubits (for a total of 4 Hadamards). Try it yourself and you'll certainly learn a lot about Quantum computation!

Re "what is the Hadamard gate doing geometrically to a vector": read up on the Bloch sphere, you'll going to hear about it everywhere. In this representation, a Hadamard gate does a 180° rotation about a certain slanted axis. The Pauli gates (NOT being one out of three) also do 180° rotations but only about $x$ or $y$ or $z$. Because such geometrical operations are quite restricted, these gates alone can't really do much. (Indeed, if you restrict yourself to those and a CNOT in your quantum computer, you just build a very expensive and uneffective classical device.) Rotating about something tilted is important, and one more ingredient you usually need is also rotating by a smaller fraction of the angle, like 45° (like in the Phase shift gate).


Reducing 3SAT to Triangle Cover Graph The Triangle Cover Graph problem is this:

  Given a graph $G = (V,E)$ and an integer $k$, does there exist a set of at most $k$ vertices of $G$ such that every triangle contained in $G$ also contains a vertex of the set?

This problem is obviously in $NP$ as its verifier is just the set which you can easily check.  However, what's the reduction to be able to show that this is NP Complete?

I recognize the fact that a good reduction for this problem would be for 3-SAT as you could easily take a 3-sat instance and make a 3-vertex triangle in the graph corresponding to the variables which are in each clause.  However, I wasn't able to come up with a way to connect the different triangles together to ensure that the assignment of vertices would be a satisfiable truth assignment.

Hint: The obvious thing to do would be to have two vertices $v^+,v_-$ per variable and one triangle per constraint. You might have to tweak this construction a little to avoid the possibility that both truth values are selected for some variable. You can do this using a "gadget", one per variable, that forces the selection of at least one truth value per variable.


Can we prove using pumping lemma that language F = {$a^ i b ^j c ^k$ | i, j, k ≥ 0 and if i = 1 then j = k} is not regular? I am currently solving a problem in which we have to show that we can not prove using pumping lemma that the language mentioned in the question is not regular.Here is the full question

Consider the language F = {$a^i b^j c^k$ | i, j, k ≥ 0 and if i = 1 then
j = k}.
a. Show that F is not regular.
b. Show that F acts like a regular language in the pumping lemma. In other        words, give a pumping length p and demonstrate that F satisfies the three conditions of the pumping lemma for this value of p.
c. Explain why parts (a) and (b) do not contradict the pumping lemma.

But, I am able to prove it using pumping lemma that language is not regular. For that I take:

pumping length as 3
x:a ; y:b ; z:c
$xy^lz$ ∈ F for l = 1
$xy^lz$ ∉ F for l > 1

Is there some problem with the above shown proof or the question is wrong.

For that I take:

  x:a ; y:b ; z:c

You can't do that. You have to first give a pumping length $p$ and then you have to show that there is no decomposition of the word $abc$ into $xyz$ with $|y|\ge 1$ and $|xy| \le p$ for which $xy^n z \in F$. If we take your word $abc$ and decompose as $x=\varepsilon$, $y = a$, $z=bc$ then the pumped words are $a^nbc$ and are all in $F$.


Determining Asymptotic Tight Bound Let's say I have an algorithm, MyAlgo(n) as follows:
for i: = 1 to n do
   (something)
Where in the i-th iteration, (something) executes i^2 steps.
How can I determine an asymptotic tight bound (Big-Theta) on the running time of this algorithm? I know I have to determine Big O and Big Omega, but since the actual algorithm isn't shown, I don't know where to start.

If the number of steps executed in the $i$th iteration is $i^2$, then the number of steps overall will be asymptotic to
$$
\sum_{i=1}^n (C+i^2) = \Theta(n^3),
$$
for some constant $C$ that comes from the loop control (i.e., incrementing $i$ and checking whether it equals $n$).

To see that $\sum_{i=1}^n (C+i^2) = \Theta(n^3)$, use
$$
\sum_{i=1}^n (C+i^2) \leq n(C+n^2) = Cn+n^3 = O(n^3), \\
\sum_{i=1}^n (C+i^2) \geq \sum_{i=n/2}^n i^2 \geq (n/2) (n/2)^2 = n^3/8 = \Omega(n^3).
$$
(In fact, $\sum_{i=1}^n i^2 \approx n^3/3$, as can be seen by approximating it by the integral $\int_1^n i^2 \, di$, or by using the exact formula $\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$.)


Algorithm for nearest edge detection with respect to a point (in all directions) I'm looking for an algorithm, a set of algorithms, or any pointers/remarks how to solve the following problem:

Given a polygon, a central point, and a set of points scaterred around the central point inside the polygon, I want to find the nearest "edges" being created by those points with respect to the central point. One of the algorithm's parameters should be "distance sensitivity" (meaning how far two points have to be far from eachother to be considered in a different cluster and break the line).

An illustration will maybe explain it better... this could be the input, where the + denotes the central point:

The output would be the following:

I am not very well-versed in computational geometry, so any pointers would be welcome.

I'd naively like to imagine the algorithm as a growing circle spreading outwards from the central point, parts of it getting stuck on the points (larger parts get stuck if the cluster is dense enough), and tearing off at the ends of the cluster because there are no points to support it there.

I have done some research into line-sweep algorithms, which partly fit my criteria. However, what I think I need is some kind of a circle-sweep algorithm.

I would suggest you use a sweep line algorithm, sweeping a line that emanates from the origin and rotating around it.  Think of a lighthouse placed at the origin, with a beam of light that rotates around in a circle, and find the closest point illuminated by that beam of light.

In more detail: Convert the points to polar coordinates $(r,\theta)$ and sort them by increasing angle $\theta$.  Let $S$ denote the set of resulting points. Then for each angle $\theta$ find the point closest to the origin out of all points whose angle is in the range $[\theta-\epsilon,\theta+\epsilon]$, and use this as the location of the perimeter at that angle.  In particular, let $f(\theta) = \min \{r : (r,\theta') \in S, |\theta-\theta'| \le \epsilon\}$; then $f$ defines a curved line/path. You can apply some smoothing to it, and then use that as your red line.  If there is no point with angle in the range $[\theta-\epsilon,\theta+\epsilon]$, then there is no red line there; you have a break in the line.

You could of course apply a standard clustering algorithm first, and then do this separately on each cluster, removing clusters that are "hidden" (further away than another cluster).  From your image it looks like the clustering problem should be easy and you shouldn't have a difficult time finding a clustering algorithm that does a good job of separating the points into clusters.  However, I'm not sure that's even necessary.


Proof of undecideability that one state is reached before another I'm trying to show that, for a deterministic Turing machine $M=(Q,\Gamma,\Sigma,\delta,q_0)$, the language $K$, which includes all of the words $w \in \Sigma^\ast$ where the calculation of $M$ on $w$ pass on the state $q$ before reaching $q'$, but if $q'$ is never reached then $w$ is not in $K$, is both recursively enumerable and undecidable.

I am thinking that this could be solved by a reduction of the Halting problem, but I do not know how to proceed.

Reducing the Halting problem to this problem would mean that a machine $M$ with data $w$ will halt on $w$ iff a machine $M'$ with data $w$ that first passes state $q$ then $q'$.
I see that if we were to associate $q$ in $M'$ with $q_0$ in $M$ and $q'$ in $M'$ with $q_f$ in $M$ we could associate part of the problem with the halting problem, but how can the condition "$q_f$ must not be reached first" be included?

Let us follow the hint given by Yuval.

What is the halting problem?

It is the problem of accepting the following language.

$$\text{HALT}= \{⟨M, w⟩ : M \text{ is a TM and }M\text{ will halt on input } w\}$$

What is the current problem?

It is the problem of accepting the following language.

$$\begin{align}
\text{One}&\text{StateBeforeAnother}
= \{⟨M, q, q',w⟩: M\text{ is a TM} \\&\wedge q\text{ and } q'\text{ are two states of }M \\
&\wedge \left(M \text{ will reach } q' \text{ on input } w\right.\\
&\vee M \left.\text{ will reach } q \text{ before reaching } q' \text{ on input } w \right)\}
\end{align}$$

How to define $\text{HALT}$ in a way similar to how $\text{OneStateBeforeAnother}$ is defined?

The idea is that if we can formulate $\text{HALT}$ in a way similar to the way $\text{OneStateBeforeAnother}$ is defined, then we might reduce the former to the latter.

$M$ halts on input $w$ means $M$ reaches a halt state on input $w$. $\text{OneStateBeforeAnother}$ is about $M$ reaches $q$ and then $q'$.

Let us try brute pattern matching.

Let $q$ be a halt state. $M$ reaches $q$, the halt state and then reaches $q'$. That cannot happen since the halt state is the last state. Sigh!
Let $q'$ be a halt state. $M$ reaches $q$ and then reaches $q'$, the halt state. That makes sense. What is $q$ then? How about letting $q$ be the initial state of $M$?

Great, we have just found the following reduction, where $q_0$ is the initial state of $M$ and $q'$ is the halt state of $M$ on input $w$.

$$⟨M, w⟩\in\text{HALT} \to
⟨M, q_0, q',w⟩\in\text{OneStateBeforeAnother}$$

Wait, this is not a well-defined reduction as $q'$ cannot be known at the time of reduction since it depends on how $M$ runs on input $w$, the undecidable halting problem!

I will leave you to conquer the problem above, how to require $q'$ to be a halt state without dependence to $M$ and $w$.


Are there any more complex problems than the Totality Problem that appear in the practical world? We know the Halting Problem is in the 1st level of arithmetical hierarchy. We know that the Totality Problem is in the 2nd level of arithmetical hierarchy. What are some examples of problems in the 3rd (or higher) level of arithmetical hierarchy. +1 for problems which instances are solved in the practical world (programmers, mathematicians, etc.).

Let $\{W_e\}_{e\in\mathbb N}$ be a canonical list of the recursively enumerable, i.e., computably enumerable, i.e., Turing recognizable, languages (or sets).

The property that $W_e$ is actually recursive, i.e., computable, is $\Sigma^0_3$:
$$\exists d\forall n(n\in W_e\leftrightarrow n\not\in W_d).$$

It is at the 3rd level of the hierarchy: it is not of lower complexity than $\Sigma^0_3$. See e.g. Soare: Recursively enumerable sets and degrees, Theorem 3.4, for the proof.


Labeled points in $\{0,1\}^n$ such that every linear separator requires exponential weights I want to find labeled samples in $\{0,1\}^n$ such that the Perceptron algorithm takes $2^{\Omega(n)}$ steps to converge. One way to do this would be to find a sequence of labeled examples that are linearly separable, but require every linear separator to have at least one exponentially large weight. To show that the samples are linearly separable, it is enough to show that they are consistent with a decision list, which should be apparent from the list of samples. So, my question is

  Does there exist a set of labeled samples $S$ in $\{0,1\}^n$ that are consistent with a decision list and such that any linear threshold function that correctly labels $S$ has at least one exponentially large weight $w_i = 2^{\Omega(n)}$?

Here are the definitions that I'm working with: A linear threshold function $f \colon \{0,1\}^n \to \{0,1\}$ with associated weights $w_0, \dots, w_n \in \mathbb{R}$ gives $f(x) = 1$ if and only if $w_1x_1 + w_2x_2 + \dots + w_nx_n \geq w_0$. Given a set $S$ of points in $\{0,1\}^n$ labeled $0$ or $1$, we say that a linear threshold function $f$ correctly labels $S$ if $f(x) = 1$ whenever $x$ is labeled $1$ and $f(x) = 0$ whenever $x$ is labeled $0$ for all $x \in S$.

Note: I had asked the same question on math.stackexchange since it seemed relevant to both fields. Here is the link for that.

Håstad gave an even better example in his paper On the Size of Weights for Threshold Gates, which requires super exponential weights.

A simple example which requires exponential weights is the function $\sum_i 2^i (x_i - y_i) \geq 0$ or variants.


The maximum decimal integer that can be stored in memory of 8-bit word processor computer? Actually i am preparing for an exam and in the last year exam this que. was been asked. i.e

The maximum decimal integer number that can be stored in memory of 8-bit word processor computer ?

a) (128)10
b) (127)10
c) (129)10
d) (255)10

Answer of this que. as given in the answer key is b) 127. And I have no idea how they arrived at this result.

Acc. to my understanding, we have 8-bits, which is 28 = 256  so 255 should be the maximum integer which we can store.

EDIT - An another very similar que. asked in same exam was

The maximum permissible integer in a computer with n-bit word processor and one  word per integer is equal to

a) 2 n - 1 - 1
b) 2 n - 1
c) 2 n - 1 + 1
d) 2 n + 1

Its ans. is  a) 2 n - 1 - 1 (acc. to official ans. key).

By putting n = 8 from above que. we got the answer 127. But again i am clueless how did they derived this answer too.

I got the same question in my technical informatics exam. The right answer was also 127, my professor explained signed integer is the default format, therefore the range would go from -128 to 127. You can display 256 distinct value, but the maximum would still be 127.


(Finite Automata) Why the following is a NFA? The first one seems like a DFA. Could someone explain why this is a NFA?

Here is a similar question:

Which of the following are rational numbers: $$ 1, \frac{2}{3}, \sqrt{2}. $$

The correct answer is that both $1$ and $\frac{2}{3}$ are rationals, despite the fact that $1$ is also an integer.
One thing which is confusing here is that none of the given examples are DFAs or NFAs. Rather, they are pictorial representations of automata. Most of these pictorial representations can be interpreted as NFAs, and some can also be interpreted as DFAs. There would be no ambiguity if the automata were given as tuples, since the transition function of a DFA has signature $Q \times \Sigma \to Q$, whereas the transition function of an NFA has signature $Q \times \Sigma \to 2^Q$.


Does our PC work as Turing Machine? Does our PC work as Turing Machine?  The model of a Turing Machine consists of infinite memory tape, which means infinite states. But suppose if our PC has 128 MB memory and 30GB disk it would have 256^30128000000 states and thus, it has finite states.

I know that we can write a type of program that, if during execution we run out of memory, will request to swap memory disk with empty memory disk and resume execution.

But what if we don’t swap memory disk, in this case is it right to consider PC as FA?

You're right that physical computers have finite memory and so are not Turing-complete. There are other ways in which computability theory is not a good model for computing - it doesn't take into account time and memory constraints. Complexity theory was invented (perhaps) as a more realistic depiction of computing, but IMHO suffers from similar (but subtler) problems.

On the other hand, in order to mathematically study the capabilities and limits of computing, we need to use some abstraction which is unconstrained. That makes the analysis possible. Similarly, in statistical mechanics we assume that the number of elements (atoms or molecules) is so large, that the behaviour is close to the limit (that is, we let the number of elements tend to infinity). Studying computing from an asymptotic perspective has similar advantages, but sometimes is misleading. Here are some examples of the latter:

In cryptography, exponential algorithms are sometimes feasible. If we choose the wrong security parameters, our encryption might be insecure even though it's "provably secure".
Polynomial-time algorithms are supposed to represent efficient and feasible computing, but many of them aren't feasible. As an example, most sophisticated matrix multiplication algorithms aren't used in practice.
Modern complexity theory is obsessed with worst-case performance, and cannot analyze heuristic algorithms which are used in practice. NP-hard problems are considered infeasible, yet they are being solved in practice all the time.

A separate issue is that real computers don't work like Turing machines at all. They work like RAM machines, which are a better abstraction for actual computing.


Time Complexity: Why does $n^n$ grow faster than $n!$? Seeing the title, you will probably like to give your explanation as

$n!=n\times (n-1)\times (n-2)\times (n-3)\times\cdots\times 1$

where as

$n^n$ = $n\times n \times n\times n \times\cdots\times n$ $\text{($n$-times)}$

but consider one thing: if we do $\log(n!)$ then it comes out to be $O(n\log n)$.

On the other hand, if we do $\log(n^n)$ it also comes out to be $O(n\log n)$. So, aren't they equal asymptotically?

The core source of your confusion is that you have assumed that the asymptotic behavior of functions is closed under taking $\log$, which is false. There are countless examples, take:
$$f(n)=n^{100}, \quad g(n)=n$$
If you take their logarithm they become:
$$\log f(n) = 100 \log n,\quad \log g(n) = \log n $$
So their logarithms are both linear in $\log n$, while it's obvious they do not have a similar growth rate.  Another example can be:
$$f(n)=\exp(2 n), \quad g(n)=\exp(n)$$
and their logarithms are:
$$\log f(n) = 2n, \log g(n) = n$$
You can see that $f(n) = g(n)^2$ and it has faster growth rate, but both their logarithms are linear in $n$.
The intuitive reason is that, when you compare $\log f(n)$ and $\log g(n)$, you are basically comparing their exponents. Showing that the exponents of two functions have a similar growth rate is not the same as showing that the functions have the same growth rate.

In case you are wondering, the reversed direction would actually hold most of the time: If $\log f(n)$ grows faster than $\log g(n)$, and $g(n)=\Omega(1)$, then $f(n)$ grows faster than $g(n)$, and the condition $g(n)=\Omega(1)$ prevents cases like $f(n) = \exp(1/n), g(n) = \exp(1/n^2)$.


Turing machine - Transition between two states by more than one condition allowed? Is it allowed to transit between two states $q$, $q'$ by more than one condition? Thank you in advance.

e.g. coming from state $q$, the conditions $(0,0,L)$ and $(1,0,L)$ would lead to the same state $q'$. Is this formally allowed?

Yes, it's allowed.

I guess the underlying problem here is that you're not familiar with reading mathematical definitions. Properly written definitions state exactly the criteria that apply. So, for example, if you read the definition "An integer is even if it is divisible by two" you should assume that divisibility by two is the only criterion that applies. The definition says nothing about divisibility by three, for example, so divisibility by three doesn't matter.

In our case, the transition function of a Turing machine is defined as a function whose arguments are a state and a tape character, and whose outputs are a state, a tape character and a direction to move the head. No further restrictions (such as "you can't get the same output from two different inputs") are mentioned in the definition, so no further restrictions apply.


Why we don't consider cycles in path problems? I'm working on my research and I found that for directed graphs, there are many algorithms trying to solve shortest path problem(like Dijkstra, Bellman‐Ford algorithm), but few is to get all paths(including circles) in the result. Is it because the complexity is way too expensive? Thanks in advance for your help!

When solving most optimization problems on paths (e. g. shortest, longest path) a cycle is either useless or makes the optimum not exist (allowing infinitely long or short paths). Thus there's generally no point in allowing cycles.


Counting number of paths between two vertices in a DAG I need an algorithm that computes the number of paths between two nodes in a DAG (Directed acyclic graph) I need a dynamic porgramming solution if possible.

Here is a dynamic programming algorithm. Given a graph $G = (V, E)$ and two vertices $u, v \in V$. We define the recursive function $C:V\rightarrow \mathbb{N}$, such that $C(w)$ is the number of paths from $w$ to $v$. Note that we are looking for the value of $C(u)$. We set $C(v) = 1$ and $C(w)=0$ for each vertex $w \neq v$ with out-degree equal to zeroo. For each other vertex $w\in V\setminus \{v\}; \delta^+(w)>0$ we can compute the value of $C(w)$ using the following formula
$$C(w) =\sum\limits_{x\in N^+(w)}C(x),$$
where $N(w)$ is the set of neighbors of $w$.

Note that $C(w)$ depends merely on the value of $C$ at the neighbors of $w$ and since a DAGs define a natural ordering over the vertices of the graph (namely the topological ordering), such that all neighbors of a vertex are smaller that it upon this ordering, we can compute $C(w)$ for all vertices $w$ according to their topological ordering using dynamic programming.

The correctness of the solution can be proved with induction over the diameter of the graph or over the length of the longest path from $u$ to $v$ for example.

The running time can be bounded by. $O(n+m)$ and the space complexity by $O(n)$.


Is UTF-8 the final character encoding for all future time? It seems to me that Unicode is the "final" character encoding. I cannot imagine anything else replacing it at this point. I'm frankly confused about why UTF-16 and UTF-32 etc. exist at all, not to mention all the non-Unicode character encodings (unless for legacy purposes).

In my system, I've hardcoded UTF-8 as the one and only supported character encoding for my database, my source code files, and any data I create or import to my system. My system internally works solely in UTF-8. I cannot imagine ever needing to change this, for any reason.

Is there a reason I should expect this to change at some point? Will UTF-8 ever become "obsolete" and replaced by "UniversalCode-128" or something, which also includes the alphabets of later discovered nearby galaxies' civilizations?

UTF-8 might not last forever, but you probably don't have to worry too much.

Two universal truths:

We can't predict the future.
Nothing lasts forever, especially in software.

But that doesn't mean the benefit of (trying to) future-proof your code always outweighs the cost.

Is UTF-8 likely to become obsolete any time soon?

I would say no. UTF-8 is quite common, which makes it harder to replace. Unicode also still has quite a bit of empty space, meaning there isn't likely to be a pressing need to replace it soon. Between 2010 and 2020, less than 40k characters have been added. It will take about 240 years to use up the remaining ~1 million unallocated characters if we assume we keep going at the same rate. This is a lot faster than I imagined, but still quite a while away and assuming it will keep going at the same rate is quite an assumption.

It also doesn't seem like there'd be a need to replace it due to a fundamental flaw in the encoding. With other types of standards or technologies there may be some security issue that could be exploited, but this doesn't seem likely with character encodings that only tells you how characters are stored.

I speculate if a need to replace it arises, it would be due to inefficiencies or  constraints in new technology. Someone could develop some new piece of technology that rethinks how data is stored or loaded, which might make UTF-8 less than ideal or unusable. But there would still be plenty of systems without that technology for quite a few years.

Note that I didn't ask "are we likely to see a new character encoding any time soon". Anyone can create a new standard, but that doesn't mean it will be widely adopted nor replace other standards.

How bad would it be for you if there's a new standard?

Probably not that bad.

Even if there is a new standard that's widely adopted, your system will likely keep functioning for the foreseeable future with little to no changes. There are a lot of legacy systems out there.

If your system doesn't support the new encoding, you may have some issues with the user or other systems trying to send you data you don't support. But your system could still use UTF-8 internally, even if this means you don't support some characters (which might not be good, but it won't necessarily break your system).

Also, if it were to be replaced due to a reason other than running out of space (which, as noted above, doesn't seem likely any time soon), UTF-8 could likely be extended to include any characters in the new encoding. Meaning you can just convert from one encoding to the other where required and UTF-8 would still be usable.

Unicode versus Unicode?

The difference between UTF-8, UTF-16 and UTF-32 seems minor when compared to other (non-Unicode) encodings. They all support the same characters, so it shouldn't be a huge issue if one replaces the other.

If another one of those were to become the widely adopted one, it would probably be trivial to convert between them where required and continue to use UTF-8 everywhere else.


I have trouble to understand pattern calculus, could someone explain it in simple terms? I am trying to understand the basic ideas of pattern calculus and do not have a lot of time to read through a rather long book. Can someone explain this in simple terms and give an example of how pattern calculus works?

http://bondi.it.uts.edu.au/

http://www.amazon.com/dp/3540891846/?tag=stackoverfl08-20

I don't understand "The ability to pass patterns as parameters (pattern polymorphism) is illustrated by defining a generic eliminator." as explained here in the Wikipedia article. If someone could work through an example showing how the patterns were transformed and why they were transformed in that way, that would be useful to me, thanks.

I can't really say that I know bondi (this is the first time I heard about it), but my experience with functional languages will allow me to give you hints.

Let's first discuss what the example given in the wikipedia page do. There are two functions called elimLeafs and elimCount. Both are accessed such as elimLeaf (Leaf 3) returns 3 and elimCount(Count 3) returns 3. "Do not focus on what these functions do !" .. There is a similarity between the two functions in that:

elimLeaf (Laef x) or elimCount (Count x) can be return as elimPattern (Pattern x) where Pattern is either Count, Leaf or any other thing you want to name.

Knowing this, you can write both functions such as "Pattern" in elimPattern (Pattern x) is a variable .. and whence you can write both elimPattern and elimLeaf such as:

 elim = | x -> | {y} x y -> y

which can be called as:

  elim Leaf (Leaf 3) returns 3 .... for example.

The function elim above is actually two functions (or I dont know what is called in Bondi). First, you got the name of the function, which is elim. The name shall be followed by =| . Then you have the definition of the function"s" which is followed by ->. So,

"elim Leaf" is matched with "elim =| x" and therefore evaluated to | {y} x y
Now, x is Leaf in "elim Leaf". Thus, "| {y} x y"  is equivalent to "| {y} Leaf y".
The function elim above can be further evaluated such that "| {y} Leaf y -> y"  (that is "| {y} Leaf y" is evaluated to y.) y in this case would be 3, given the input above.
Note here that right now you did exactly what elimLeaf did ! You can do the same for elimCount by simply replacing Leaf by Count in the input.

To clarify more:
Assume you want to do this with C++. The definition of the functions elimCount and elimLeaf are as follows:

int elimCount(int x) { return x;}
int elimLeaf(int x) { return x;}     // we are just assuming int in this example,

To write both these functions with only one, perhaps you would do something like:

int elim (const char* pattern, int x) {
    if (strcmp(pattern, "Leaf") == 0) return x
    if (strcmp(pattern, "Count") == 0), return x
 }


What motivates the RAM model? It looks like most of today's algorithm analysis is done in models with constant-time random access, such as the word RAM model. I don't know much about physics but from popular sources I've heard that there's supposed to be a limit on information storage per volume and on information travel speed, so RAMs don't seem to be physically realizable. Modern computers have all these cache levels which I'd say makes them not very RAM-like. So why should theoretical algorithms be set in RAM?

Let me give a different take on it than vonbrand. Everything you said is true: the RAM model is not realistic for a number of reasons, and whereas it is possible to defend different aspects of it, such a defense doesn't really get to the heart of the matter.
The heart of the matter -- and the answer to your question -- is that the RAM model is the best thing we have. Compared to other models that are accepted, it more accurately models real-life computation. In particular, the reason we adopted the RAM model was primarily a response to Turing machines, as we found that the use of Turing machines leads to problems being artificially difficult to solve in terms of time complexity. The RAM model clearly solves this glaring issue, and thus it has been accepted, even though it remains far from perfect.
A classical example that illustrates the glaring issue with Turing machines is the problem of string equality: given input
$$ w_1 \# w_2$$
where $w_1, w_2$ are binary sequences and $\#$ is a separator, determining whether $w_1 = w_2$. It can be shown that any Turing machine for the equality problem takes $O(n^2)$ time. This is uncomfortable, because Turing machines are what everyone thinks of as the universal model of computation -- yet no software engineer or algorithms researcher believes that string equality really takes $O(n^2)$ time. So what gives? String equality should be linear, so we invent a new model where it is, and the best solution available right now is word RAM machines.
Perhaps some day in the future we will come up with a better model -- one that is simple, conceptually clear, and improves on RAM in its ability to model real-life computational complexity. For now, we can only make do with the best that we have.


Complexity of space density and sequentiality I'm looking for some standard terminology, metrics and/or applications of the consideration of density and sequentiality of algorithms.

When we measure algorithms we tend to give the big-Oh notation such as $O(n)$ and usually we are measuring time complexity. Somewhat less frequently, though still often, we'll also measure the space complexity of an algorithm.

Given current computing systems however the density of memory and the sequence in which it is accessed plays a major role in the practical performance of the algorithm. Indeed there are scenarios where a time complexity algortihm of $O(\log n)$ with disperse random memory access can be slower than a $O(n)$ algorithm with dense sequential memory access. I've not seen these aspects covered in formal theory before; surely it must exist and I'm just ignorant here.

What are the standard metrics, terms, and approaches to this space density and access sequentiality?

There are a few models that take into account the number of memory transfers an algorithm makes. One of the most successful ones is the cache-ideal model introduced by Frigo et al, Cache-oblivious algorithms, 1999. It is based on the external memory model introduced by Aggarwal and Vitter, The Input/Output Complexity of Sorting and Related Problems, 1988. The notes by Demaine give a nice, readable overview of the model and of some of the algorithms and data structures out there. Alternatively, check out the chapter on cache-oblivious data structures in the Handbook of Data Structures and Applications. If you prefer videos, Demaine covers all the basics and perhaps even more on the MIT Introduction to Algorithms lectures.

The model assumes no knowledge of the number of levels in the memory hierarchy. In addition, there are no parameters such as cache-line length or cache size to configure. One property is that if an algorithm performs optimally in the cache-ideal model, it performs optimally on any $k$-level memory hierarchy. Furthermore, algorithms that do perform optimally in the model are called cache-oblivious. They offer the advantages of simplicity, robustness and portability over the cache-aware algorithms, whose resource usage must be managed explicitly.

The ideal-cache model has two complexity measures. The first one is work complexity, that is the conventional running time of an algorithm in the RAM model. The second one comes from the external memory model, that is the number of memory transfers. The ideal-cache model however modifies the external memory model in a few ways. It has a optimal block replacement strategy, automatic replacement and full associativity. All of these assumptions are justified by a collection of reduction by Frigo et al.

Algorithms and data structures are then analyzed in the model. For example, consider the classic binary search. The runtime leads to a recurrence

$$T(N) = T(N/2) + O(1).$$

Looking at the recursion tree, each level attributes an $\log N$ factor yielding the solution of $\Theta(\log N)$. When analyzing algorithms in the RAM model, we often assume the base case of $T(1)=O(1)$ for our recurrences. However, in the cache-ideal model we often let the algorithm divide the problem all the way, but consider the point at which the problem either fits the cache or fits in $O(B)$ number of memory blocks. In fact here, we can we can improve on our analysis by using a stronger base case of $T(O(B))=O(1)$. With this, the classic binary search incurs $\Theta(\log N - \log B)$ memory transfers. What is more, the classic binary search is not optimal the in cache-ideal model. There are more clever ways needed to achieve the optimal $\Theta(\log_B N)$ bound.

I guess the success of the model comes from the fact that it is easy and fun to work with, and it also works in practice, meaning it has been fairly effective at predicting the costs of an algorithm on real systems. There are a lot of cache-oblivious algorithms and data structures. For example, we have cache-oblivious algorithms for many problems in computational geometry, scanning of dynamic sets, bioinformatics, stencil computations, linear algebra, suffix array construction and for some fundamental graph problems using cache-oblivious priority queues. The main techniques that are effective are linear scanning of memory and divide-and-conquer.

In practice, the overall conclusion has been such that cache-oblivious algorithms often outperform RAM algorithms. However, the cache-aware algorithms are usually even faster, since they are tuned for a specific problem size and memory hierarchy. For a nice example see Ladner et al., A Comparison of Cache Aware and Cache Oblivious Static Search Trees Using Program Instrumentation, 2002.


Name for multiset with fractional amounts? What do you call a set which accepts multiples of the same element, even in fractional amount? Is there even an established for this?

Example from a video game about production chains:

For a carpenter to run at full capacity, you need:
1 carpenter
1 sawyer
0.5 woodcutter
0.25 forestry

And knowing the fractional amount is important to know for example that you can build only 1 forestry to feed 4 carpenters.

There is the "multiset", but definitions I've read all say elements must have an integer count. I've search for keywords like "multiset fractional amounts", "multiset fractional multiplicity", but didn't find anything .

There is the "knapsack" that turned out on occasion, but the problem's definitions also say the elements must have an integer count?

Am I just approaching this the wrong way??

(I'm a 1st year undergrad student in a computer science/programming degree)

I don't know a standard name for this, but what you've described is representable as a function into $\mathbb{R}$.

For your example, if $X$ is the set of your things then you can represent your 'fractional multiset' as a a function $f : X \to \mathbb{R}$ such that

$$
f(x) =
\begin{cases}
1 & x = \text{carpenter}, \text{sawyer} \\
0.5 & x = \text{woodcutter} \\
0.25 & x = \text{forester} \\
0 & \text{otherwise}
\end{cases}.
$$

If you're looking for a way to implement this in a programming language, if you need to store only finitely many things then you could use a map/dictionary data structure. For example in java you could use some implementation of Map<X, Float>

As for what to call this, "fractional multiset" sounds fine as long as you explain it in whatever context you're using. Alternately you could just refer to it as a "size/measurement function".


Why is $\sum_{i=1}^n O(i)$ not the same as $O(1)+O(2)+\dots+O(n)$? The well-known textbook Introduction to Algorithms ("CLRS", 3rd edition, chapter 3.1) claims the following:

$$ \sum_{i=1}^n O(i) $$

is not the same as (I'm not using DNE because the book explicitly says "is not the same as")

$$ O(1) + O(2) + \dots + O(n) $$

Why is this? How are we to explicitly represent the first summation if not with the second? As an extension of the previous question, how do we do asymptotic analysis on such a summation?

The difference is IMHO well explained in that book, the part you are referring to says

  The number of anonymous functions in an expression is understood to be equal to the number of times the asymptotic notation appears.

So this $$ \sum_{i=1}^n O(i) $$

means a placeholder for $$ \sum_{i=1}^n f(i), $$

where $f(i)$ is an anonymous function from the set $O(i)$ — but it is always the same function in all terms of the sum. However, in $O(1) + O(2) + \dots + O(n)$, each term represents a placeholder for a (potentially) different anonymous function $f_i$ from the set $O(i)$. Note the book also says, the latter has "no clear interpretation", so it is quite meaningless.


Is an infinite tape alphabet for TM valid? Can I use an infinite alphabet for the tape in a turing machine?

e.g. with input string as (1, 0)*
can I define the symbol 1j as the symbol 1 with j marks on top of it where j in a natural number, to be used on the tape?

Turing machines have a finite tape alphabet.

You can think of a generalization of Turing machines with infinite tape alphabet, but there are two problems:

The description of the machine is no longer finite.
Such a machine can decide any language over $\{0,1\}$ (exercise).

There are ways around it - for example, we might require the rules to be finitely specifiable in some specific form. The resulting model will then be equivalent to Turing machines (in terms of computability).


How does the use of oracle Turing machines not lead to contradictions? How can we ensure that we are continuing to make sound and valid statements about complexity classes when using oracle Turing Machines?  According to my understanding (based on the definitions given in introductory textbooks on the subject)  oracle Turing machines can determine the membership status of a string with respect to an oracle language in one computation step.  However the oracle languages often used are provably impossible to solve in constant time (take an EXPTIME-complete oracle, for example).  To me this seems like "opening the door" to contradictions and after all, anything follows from a contradiction.

There's a number of ways to look at this.

One is that in proofs, implication is kind of like a function, that takes as input a proof of something, and outputs a proof of something else.

We can write functions that operate on values that we don't have.

For example, let's consider the halting number $h$, which is not computable. I can write the function

$haltingPlusOne : \{h \} \rightarrow \mathbb{N}$

$haltingPlusOne(x) = x + 1$.

This function takes as input the Halting number, and returns the Halting number plus one. Clearly this is a well defined function: if we give it the right input, it gives the right output. The fact that we can't find the right input doesn't make it any less valid of a transformation.

I see proofs with oracles as similar. They're basically functions which say, give me a Turing machine that solves problem $X$, and I'll give as output a proof of some theorem.

It's also important to realize that when we say something like "There is no Turing Machine that can decide the halting problem,"  that is saying that, there's no TM matching the standard definition of a TM that decides the halting problem.

An oracle is basically saying "Assume we have a TM that matches the normal definition except also assuming we can solve some problem". So there's no contradiction, since we're not assuming there's a normal TM accepting the problem, we're assuming there's a special TM accepting the problem.

In a very informal analogy, think of it like this. If I can prove to you that no humans without superpowers can fly, there's no contradiction saying that there's a superhero that can fly.

These oracles are purely logical objects. We don't know how to build physical machines that emulate them, the way we can with Turing machines, but as far as we know, there's no inherent contradiction between their definitions and our basic axioms.
As logical objects, these oracles do exist. We know they're not standard Turing Machines or Lambda-Calculus terms or Partial-recursive functions. The Church-Turing thesis says that there's no more powerful model, but it's not a theorem, it's just a conjecture, and is too informal to ever really be proved.


Context-sensitive grammars without permutation rules Permutation rules are called those which are of the form $AB\Rightarrow^*BA$1. It is also proven that permutation rules expand context-free grammars and allow them produce non-context-free languages.

My question is: are any examples of context-sensitive grammars, which doesn't contain any permutation rules but still able to produce non-context-free languages?

1) Book, R.V. International Journal of Computer and Information Sciences (1973) 2: 129. doi:10.1007/BF00976059. More generally permutation rules have form of $Y_1 \dots Y_m\rightarrow Y_{\pi_1}\dots Y_{\pi_m}$, where $\pi$ is some permutation of $\{1\dots m\}$.

You have the Koruda normal form in mind. It is indeed often useful, in particular in simulation LBAs.

However, many definitions of CSGs (including Chomsky's) are different; they require rules to have the form

$\qquad \alpha A \beta \to \alpha \gamma \beta$.

You can see how this precludes "permutation rules".

Obtain a concrete grammar by applying the simulation you find in a proof that KNF is equivalent to the classical definition.


On lambda calculus notation: FGa If we've got this expression:

FGa

where F and G are functions (as well as a, of course; but let's treat a as a constant).
It must be understood that:
first apply F taking G as input; then apply the previous result with a as input. This is

FGa = (FG)a

conventionally expressed:

( F(G) )( a )

Or is it this instead:

FGa == F(Ga) == F(G(a))

Thanks.

It's the first one. Function application is left-associative.
$$FGa = (F G) a$$


Gas Station Problem - Dijkstra's Algorithm variation I am trying to find an algorithm which finds the least expensive route from one town to another.

This is the general setup.

There are a series of one-way roads from some towns to other towns. Not all towns have roads between them. Let R be the set of all the roads and let T be the set of all towns. For two towns u, v ∈ T, let (u→v)∈ R be the one-way road from u to v and let w(u, v) be the amount of gasoline required to travel along this road.

Let S ⊂ T be the set of towns which have gas stations. At a town u ∈ S, one can choose to pay c(u) dollars to fill up the gas tank. Note that the cost does not change depending on how much gas must be bought; if you need to buy gas, fill up the whole tank. The cost is only affected by which town u is.

The car’s tank can hold k units of gas and it is full at the start.

My ideas:

I believe this uses a shortest path graph algorithm, but I am unsure how to implement it. I believe it uses Dijkstra's algorithm. I also recognize that the run-time depends on |T|, |R| and |S|.

Any advice will help! thanks :)

We note that we can assume that the source node has a gas station with refilling cost as $0$, even if it doesn't. It just makes the algorithm cleaner, as we start out with a full tank, and we note that no optimal solution is ever going to come back to the source again and refill. Similarly, we also assume that the $\text{target}$ also has a gas station with some arbitrary cost of refilling - the cost here wouldn't matter. So in effect, we set $S = S \cup \{\text{source, target}\}$.

In the first phase of the algorithm, for every $s \in S$, we want to find all the other towns in $S$ that we can reach without refueling, if we start out with a full tank from $s$. For this, we can take two approaches:

Run Floyd–Warshall using $w(u, v)$ as the weight of every edge, to find the shortest distance from any town to any other. Now, for every $s \in S$, we iterate through every other $t \in S$ and if the shortest distance from $s$ to $t$ is $\leq k$, then we can reach $t$ from $s$ without refueling. So we create a new graph $G'$, whose vertex set is $S$, and add a directed edge $(s, t)$ with a weight of $c(s)$. This approach takes $\mathcal{O}(|T|^3)$ time and $\mathcal{O}(|T|^2)$ space.
Another way to construct the same $G'$, would be to start a Dijkstra's from every $s \in S$, and stop when the distance is more than $k$, which in the worst case wouldn't help our complexity. This approach would require $\mathcal{O}(|S| \times (|R| + |T|\log|T|)$ time and $\mathcal{O}(|T|^2)$ space.

The second approach is asymptotically better than the first one, but the first one is easier to implement. So you can decide which fits your needs better.

Now on to the second phase of the algorithm, where we have the graph $G'$ with us, which again is a directed weight graph, but now the weights are costs of refilling. So all we have to do is run a Dijkstra's on this graph starting from $\text{source}$. The answer is the shortest distance to $\text{target}$.

So the total algorithm needs $\mathcal{O}(|S| \times (|R| + |T|\log|T|)$ time and $\mathcal{O}(|T|^2)$ space.


Compression of Random Data is Impossible? A few days ago this appeared on HN http://www.patrickcraig.co.uk/other/compression.htm. This refers to a challenge from 2001 - where someone was offering a prize of \$5000 for any kind of reduction to the size of randomly generated data (the entrance cost would be \$100 and the contestant could choose the file-size).

I understand the result which shows it is impossible to compress all files of size >= N to a smaller size (http://en.wikipedia.org/wiki/Kolmogorov_complexity#Compression).

But in the challenge question the idea is to only compress a single randomly generated file. A simple approach is to find $l$ the longest recurring substring in a file and substitute that with $s$ the shortest non-occuring substring which would give a saving of $l-s$ (since the decompresser only needs one l,s pair).

To obtain an approximation for the single shortest non-occurring substring as Usul pointed using the approximation for the coupon problem: $$E(t) = nlog(n) + \gamma n + (1/2n)$$

In this case $t$ is the number of possible substrings and using bytes for simplicity that's respectively:

275 megabytes for 3 byte strings ($n=256^3$)

91 gigabytes for 4 byte strings ($n=256^4$)

The probability of a recurring substring in the random data is equivalent to the birthday problem over the size of the random data,
$p = 1-e^{-((n^2)/2d)}$, for example at 91 gigabytes one can expect to find a recurring 9 byte substring with: $d=256^9$, $n = 91*1024^3$. $p \approx .636$

With $5000:100$ odds it should be possible to optimize a little more. Of course the cost of sed delimiters will be 3 bytes, if the cost of the command counts this method isn't enough to be successful - but this is without doing anything particularly clever.

Am I missing something (It would seem that the majority of random data should not be in fact incompressible)? What is the basis on which someone offers such a challenge and presumes it is entirely unwinnable for the player?

Edit (updated calculations up top as well): Also I think its possible to have a savings of precisely $l-s$ without having to pay for a delimiter. This is because it is known that substring $s$ did not exist prior to insertion - therefore the pair can be arranged with $sl$ contiguously written in memory and either the length of $s$ is known ahead of time (by estimating the shortest substring) or the next byte following $s$ in the file does not collide with the first byte of $l$ with at least probability $255/256$ (this gets better actually by having a choice which non-occuring $s$ to substitute for which recurring $l$).

Here's the Kolmogorov complexity argument that @YuvalFilmus mentions in his answer.

Your input here is a sed script of some size plus an input file of some size.  Say the total size of the sed script plus the file is $n$ bits.

There can be only $2^n$ inputs of size $n$ bits.  Even if I let you have a sed script of less than $n$ bits (and don't charge you for telling me how long the input is) there can only be $2^{n+1}$ possible inputs.  But there are $2^{n+8}$ possible strings of length $n+8$ bits, so you can produce at most $1/128$th of the possible $2^{n+8}$ bit strings.  That's less than .01, so paying 50:1 my expected value for the bet would be positive (about 0.60).  (And that's only giving you 1 byte to play with.)

In short, random strings that are compressible at all must be extremely rare.

Why your scheme is broken

Your probability calculations look fine to me.  And the idea of a birthday attack is so appealingly clever, it took me quite a while to see the real problem.

Your basic scheme doesn't compress.

Suppose you find a 4-byte substring that doesn't occur in the original string, and an 8-byte substring that occurs twice in the original string.

Then you are going to produce a "compressed" string of length $n$ bytes - 8 bytes - 8 bytes + 4 bytes + 4 bytes, plus a sed replacement script which must be of length at least 4 bytes + 8 bytes.  Add that all together and we get $n+4$.

If the longer string is length $l$ and repeats $r$ times and the shorter string is of length $s$ then in general your scheme reduces the string length by

$$ (l-s) r - (l+s).$$
So $l=7$, $r=3$, $s=4$ "works" (saves 2 bytes), but the probability of finding a 7 byte substring that repeats 3 times is infinitesimal.


complexity of dividing set of number with constraints I've been thinking about a division problem for groups that I haven't found a dynamic programming solution and I'm trying to analyze the complexity of the problem.
There is a set of $n$ positive numbers ($S$), a vector of group sizes (let's call it $Sizes$), and a parameter $Y$. Find a way for divide the $n$ numbers into groups that their size describes in $Sizes$ s.t. the $constraint$ in close as possible to $Y$.
For example, $ S = \{1,1,2,2,3,4,4,7,9,11\}$, $Sizes = [2,2,3,3]$, $Y=2$ and $constraint =$ the variance of the group. Of course that the $constraint$ could be changed in other cases. But this is representative example.
Has this problem any dynamic programming solution? or that the complexity is exponential (which means $NP$ problem)?
Which approximation approaches can help me in this case?
Thanks in advance!

The difficulty of your problem heavily depends on "constraint".
For example if $n=3k$, $\text{size}=[\underbrace{3,3,3,...}_{k\text{ times}}]$, and the constraint is that the sum of the numbers each group must be equal, then your problem is strongly NP-hard since it is exactly $3$-partition.
The same problem with groups of size $2$ is polynomial.
Notice that both problems are in $\mathsf{NP}$ and that being in $\mathsf{NP}$ does not mean that the complexity to solve it is exponential.


Complexity class that properly included in DLOGTIME Is there any decision problem that is in a complexity class properly included in DLOGTIME? (except $O(1)$, of course)

If there is, can we create complete problems for DLOGTIME? So, can there be reduction by $O(\log(\log n))$ or smaller?

Regan & Vollmer suggest in the conclusion of the linked paper that such classes are constructible (though fiddly). The paper itself is about LOGTIME, and mentions where changes have to be made to adapt the results to LOGLOGTIME, LOGLOGLOGTIME etc., but don't explicitly demonstrate the results.


Finding edges with minimal weight sum, such that every simple cycle contain at least one edge Given simple, udirected and connected graph with $n$ verticies. Every edge in this graph has some weight. I have to find (in polynomial time) a set of edges such that :

1.every simple cycle in graph contains at least one edge from this set
2.sum of weights of these edges is the least possible

I have derived the following algorithm to solve this problem.

First, apply DFS algorithm, starting from 1. vertex, to get all back edges. It is known that every simple cycle in this graph will contain at least one back edge, so 1. condition will be satisfied. To satisfy the 2. condition, we must apply DFS algorithm starting from 2. vertex, 3. vertex .... n. vertex, to get different sets of back edges, that all satisfy 1. condition, and choose set with the least sum of weights.

My question is will this algorithm give the right answer ? And if it won't, then why?

I have some doubdts about it, for example, is the set of back edges, given by DFS algorithm, is least possible to satisfy the condition that every simple cycle in the graph contain at least one edge from this set? For example, DFS has given me that $BE =  \left\{ e_1, e_2, e_3, e_4 \right\}$ are the back edges of graph. So every simple cycyle will contain at least one edge from $BE$. But, is it possible that we can throw out, say, $e_3$ and still every simple cycle in graph will contain at least one edge from $\left\{ e_1, e_2, e_4 \right\}$ ?

To turn some of my hints into an answer, the problem with your solution is that the DFS phase doesn't do anything to optimize the weight of the complement of the tree.  Here is a solution.

Let $G=(V,E)$ be your graph, $w : E\to \mathbb{Z}$ the weight function, which we extend linearly to $2^E$.  Call the set we are looking for $B$.

Property (1) implies that $C := E\setminus B$ is acyclic.  Otherwise, $C$ contains some cycle, contradicting the fact that $B\cap X\neq \emptyset$ for every cycle $X$ in $G$.

Property (2) implies that $w(C)$ should be as large as possible.  Since $w(B) = w(E) - w(C)$, minimizing $w(B)$ is just maximizing $w(C)$.

So, the algorithm is just to compute the maximum weight forest in $G$, and return the complement.  (The MWF isn't necessarily a spanning tree if there are negative weights.)


Inviting an optimal subset of persons such that all friends of a person invited are invited Let's say that you want to invite a person $u$ in party $P$. The
person $u$ will join the party if and only if all the friends of $u$ will join the party as well. Otherwise, $u$ will reject your invitation. Hence, we have two sets: $P$ with all the persons, and $F$ with the friend relations. Suppose $(u, v)$ belongs to $F$. This means that $u$ treats $v$
as a friend of $u$, and thus $u$ will reject your invitation if $v$ does not join the party. Note that $(u, v) \in F$ doesn’t mean that $v$ treats $u$ as a friend of $v$. Also, every person $u$ in $P$ has a quality measure, $p_u$ (this can be positive or negative and is given). Now I need to find a subset of $P$, such that all those in the subset won't reject my invitation and the qualities among the people is maximized.

Here is an example of a feasible and non-feasible subset:
$P = \{a, b, c, d\}, F = \{(a, b),(a, c),(b, d),(b, c)\}, p_a = 10, p_b =
1, p_c = 1, p_d = −20$.
A subset $\{a, b, c\}$ is not feasible because $d$ is not
invited and thus $b$ rejects your invitation.
A subset $\{b, c, d\}$ is feasible with total quality is $p_b + p_c + p_d = −18$ which is not maximized. The optimal
subset $A$ of this example is $\{c\}$ with total quality is $p_c = 1$.

Now I need to design an algorithm that finds this optimal subset in $O(|P|(|P| + |F|)^2)$ time.
My thoughts:
The elements in $F$ are directed edges, and the elements in $P$ are the nodes. As we are kind of dealing with a maximum flow problem, and as the required running time resembles the running time of the Ford Fulkerson algorithm $O(VE^2)$, I thought, that $(|P| + |F|)$ should be the amount of edges in the graph. Hence, my thought was to split each node $u$ into two nodes, say $u(\mathrm{in})$ and $u(\mathrm{out})$ with the directed arc $u(\mathrm{in})\rightarrow u(\mathrm{out})$ and edge weight the $p_u$. This way we have $(|P| + |F|)$ edges. However, the max flow algorithm doesn't necessarily saturate the edges it travels. However, in my case, whenever a node is reached (person is invited)/edge is travelled it adds the full flow $p_u$.

How would you approach this problem? And what are your thoughts on how the algorithm should work?

This is known as the closure problem. I quote the Wikipedia paragraph describing the reduction to the max flow problem here.

As Picard (1976) [1] showed, a maximum-weight closure may be obtained from $G$ by solving a maximum flow problem on a graph $H$ constructed from $G$ by adding to it two additional vertices $s$ and $t$. For each vertex $v$ with positive weight in $G$, the augmented graph $H$ contains an edge from $s$ to $v$ with capacity equal to the weight of $v$, and for each vertex $v$ with negative weight in $G$, the augmented graph $H$ contains an edge from $v$ to $t$ whose capacity is the negation of the weight of $v$. All of the edges in $G$ are given infinite capacity in $H$.
A minimum cut separating $s$ from $t$ in this graph cannot have any edges of $G$ passing in the forward direction across the cut: a cut with such an edge would have infinite capacity and would not be minimum. Therefore, the set of vertices on the same side of the cut as $s$ automatically forms a closure $C$. The capacity of the cut equals the weight of all positive-weight vertices minus the weight of the vertices in $C$, which is minimized when the weight of $C$ is maximized. By the max-flow min-cut theorem, a minimum cut, and the optimal closure derived from it, can be found by solving a maximum flow problem.

[1]  Picard, Jean-Claude (1976), "Maximal closure of a graph and applications to combinatorial problems", Management Science, 22 (11): 1268–1272, doi:10.1287/mnsc.22.11.1268, MR 0403596.


NP-Completeness - Proof by Restriction I'm reading Garey & Johnsons "Computers and Intractability" and I'm at the part "Some techniques for solving NP-Completeness". Here's the text about Proof by Restriction:

  Proof by restriction is the simplest, and perhaps most frequently
  applicable, of our three proof types. An NP-completeness proof by
  restriction for a given problem $L \in NP$ consists simply of showing that
  $L$ contains a known NP-complete problem $L'$ as a special case. The heart
  of such a proof lies in the specification of the additional
  restrictions to be placed on the instances of $L$ so that the resulting
  restricted problem will be identical to $L'$. We do not require that the
  restricted problem and the known NP-complete problem be exact
  duplicates of one another, but rather that there be an "obvious"
  one-to-one correspondence between their instances that preserves "yes"
  and "no" answers."

And I'm trying to learn this technique by example, but need some help.

(If you have the book, my example is on page 65, 27th printing)

They prove that Multiprocessor Scheduling is NP-complete with the following proof:

(Paraphrasing):

  Restrict to PARTITION by allowing only instances in which $m = 2$ and $D$
  $=$ half the total sum of the "lengths".

Here $m$ is the number of processors and $D$ is the maximum allowed sum of "lengths" per processor.

This is obviously a special case of multiprocessor scheduling which is solvable by solving the PARTITION problem, and there's no confusion there.

But, I'm not sure why this proof holds.

Excerpt from above: "The heart of such a proof lies in the specification of additional restrictions to be placed on the instances of $L$ so that the resulting restricted problem will be identical to $L'$ ".

The way I see it that means we have to find the special case, and then find restrictions that show us that this problem can always be reduced to the special case. What we're trying to do here is show that Problem $A$ (MS) is at least as hard as Problem $B$ (PARTITION), so why would a simple special case be enough here? Is it because there's an obvious way to map to this special case that I'm missing? Or perhaps because $m = 1$ is trivial and we know that the problem will only get harder with a higher $m$, and that $D$ is always arbitrary, therefore $A$ must be at least as hard as $B$ (I feel like I'm just guessing now :p)

I hope it is clear where I get lost.

TLDR; Why is it enough to find a special case that is solvable by an NP-Complete problem? Don't we need some reduction to complete the proof?

There is an implicit (trivial) reduction, from each instance of the restricted version to itself, really just relabelling it as an instance of the unrestricted problem.

To give an example that I think is more illuminating than Partition and Multiprocessor Scheduling, we can look at Vertex Cover and Hitting Set:

  Vertex Cover
  Input: A graph $G=(V,E)$, a positive integer $k$.
  Question: Is there a set $V'\subset V$ of size at most $k$ such that for every $uv \in E$ either $u\in V'$ or $v\in V'$ or both?

  Hitting Set
  Input: A hypergraph $H=(X,E)$, a positive integer $k$.
  Question: Is there a subset $X'\subseteq X$ of size at most $k$ such that for every $e \in E$ there exists an $x \in X'$ such that $x \in e$?

So we can easily see that Vertex Cover is just Hitting Set where the size of the edges is exactly two. As Vertex Cover is NP-hard (indeed, complete), Hitting Set must also be NP-hard. As Hitting Set is also in NP, it is therefore NP-complete.

So we have a "reduction" from Vertex Cover to Hitting Set, but it's just the identity mapping. The graph remains unchanged (as does $k$), we just call it a hypergraph, and call the edges hyperedges.

To think about it from the other end, if we have a problem $\Pi$ where a restricted subproblem $\Pi'$ is already NP-hard, and we had a PTIME algorithm for $\Pi$, then we could use it to solve all the instances of $\Pi'$ in polynomial time and hence everything in NP would have a polynomial time algorithm. Thus $\Pi$ must be NP-hard (and if $\Pi \in$ NP, NP-complete).


Which language families admit inductive definitions? I am self-learning about formal languages. I learned that the family of the regular languages can be defined inductively, in terms of the operations they are closed under (namely the smallest fix-point). This definition doesn't rely on regular grammars or finite state machines.

I wonder which other families of formal languages can be defined inductively; in particular, I am interested in the classic classes of the Chomsky hierarchy but also the (semi-)decidable languages.

We can study families of languages in terms of their closure properties, it then makes sense to consider languages which generate the family under those closure properties.

Some work in this area has been done (particularly for cones/AFLs) and there may be known results for some or all of the families of languages that you mention but the only result which I know off the top of my head is for the context-free languages:

The context-free languages are the smallest cone generated by the Dyck language on two symbols.

For a proof of this theorem and some similar results for other language classes within context-free see Berstel's book which is now freely available on his website here.


Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight? If a weighted graph $G$ has two different minimum spanning trees $T_1 = (V_1, E_1)$ and $T_2 = (V_2, E_2)$, then is it true that for any edge $e$ in $E_1$, the number of edges in $E_1$ with the same weight as $e$ (including $e$ itself) is the same as the number of edges in $E_2$ with the same weight as $e$? If the statement is true, then how can we prove it?

Claim: Yes, that statement is true.

Proof Sketch: Let $T_1,T_2$ be two minimal spanning trees with edge-weight multisets $W_1,W_2$. Assume $W_1 \neq W_2$ and denote their symmetric difference with $W = W_1 \mathop{\Delta} W_2$.

Choose edge $e \in T_1 \mathop{\Delta} T_2$ with $w(e) = \min W$, that is $e$ is an edge that occurs in only one of the trees and has minimum disagreeing weight. Such an edge, that is in particular $e \in T_1 \mathop{\Delta} T_2$, always exists: clearly, not all edges of weight $\min W$ can be in both trees, otherwise $\min W \notin W$. W.l.o.g. let $e \in T_1$ and assume $T_1$ has more edges of weight $\min W$ than $T_2$.

Now consider all edges in $T_2$ that are also in the cut $C_{T_1}(e)$ that is induced by $e$ in $T_1$. If there is an edge $e'$ in there that has the same weight as $e$, update $T_1$ by using $e'$ instead of $e$; note that the new tree is still a minimal spanning tree with the same edge-weight multiset as $T_1$. We iterate this argument, shrinking $W$ by two elements and thereby removing one edge from the set of candidates for $e$ in every step. Therefore, we get after finitely many steps to a setting where all edges in $T_2 \cap C_{T_1}(e)$ (where $T_1$ is the updated version) have weights other than $w(e)$.

Now we can always choose $e' \in C_{T_1}(e) \cap T_2$ such that we can swap $e$ and $e'$¹, that is we can create a new spanning tree

$\qquad \displaystyle T_3 = \begin{cases}
  (T_1 \setminus \{e\}) \cup \{e'\},  &w(e') \lt w(e) \\[.5em]
  (T_2 \setminus \{e'\}) \cup \{e\},  &w(e') \gt w(e)
\end{cases}$

which has smaller weight than $T_1$ and $T_2$; this contradicts the choice of $T_1,T_2$ as minimal spanning trees. Therefore, $W_1 = W_2$.

The nodes incident of $e$ are in $T_2$ connected by a path $P$; $e'$ is the unique edge in $P \cap C_{T_1}(e)$.


Solving $T(n) = T(n/2) + T (n/3) + n $ with recurrence tree I am trying to solve the following recurrence relation:
$$T(n) = T(n/2) + T (n/3) + n $$ $$T(1) = Θ(1) $$

I guess that the time complexity is $T(n)=Θ(n)$ since $\frac{n}{2} + \frac{n}{3} < n$

I am trying to prove it using a recurrence tree.

The tree is not balanced. Particularly, the longest path from the root to a leaf is the leftmost one  with a length of $\log_2n$ when the shortest path is the rightmost one with a length of  $\log_3n$.

We get that at each level,except the first one, the cost is $< n$. In more detail,the first level has a cost of $n$. The nodes on the second level add to a $\frac{5}{6}\cdot n$ cost, the third level has a cost equal to $\left (\frac{5}{6}  \right )^2\cdot n$ and so on...

So, untill the height of $\log_3n$ we have a cost of $$n\sum_{i=0}^{\log_3n-1}\left (\frac{5}{6}   \right )^i = n\cdot \frac{\left (\frac{5}{6}\right)^{\log_3n}-1}{\left (\frac{5}{6}\right)-1}$$

So, the result above seems to be a lower bound for my function $T(n)$

Is my approach correct? If yes, then how do I go on in order to prove that the time complexity is $T(n)=Θ(n)$.Thanks in advance!

On the one hand, clearly $T(n) \geq n$ (see detailed proof below). On the other hand, let us find prove by induction that $T(n) \leq Cn$, for large enough $C$. The base case trivially holds for $C \geq T(1)$. For the inductive step, we have
$$
T(n) = T(n/2) + T(n/3) + n \leq C\cdot (n/2) + C\cdot (n/3) + n = [\tfrac{5}{6}C+1]n.
$$
(We're cheating here a bit since $n$ isn't necessarily a multiple of 6.) If $C \geq 6$, then $\tfrac{5}{6}C+1 \leq C$, and so we can conclude that $T(n) \leq Cn$, thus completing the inductive step. In total, if we take $C = \max(T(1),6)$ then the proof goes through, hence
$$ n \leq T(n) \leq \max(T(1),6) n. $$
This implies that $T(n) = \Theta(n)$.

Finally, let us prove that $T(n) \geq n$. We first prove that $T(n) \geq 0$. The proof by induction. The base case clearly holds, and the inductive step is a consequence of
$$ T(n) = T(n/2) + T(n/3) + n \geq 0 + 0 + 0, $$
using the inductive hypothesis twice. Finally,
$$ T(n) = T(n/2) + T(n/3) + n \geq 0 + 0 + n = n. $$


Can a transcript change dependent random variables into independent variables? Let's say $X, Y$ are dependent random variables. Can I find an example such that for a transcript $t$ conditioned on a communication protocol $\Pi=t$, the variables become independent?

Yes. Consider the following protocol.  Alice flips a coin, and sets $X$ and $Y$ to be equal to the outcome of the coin flip.  She then sends $X,Y$ to Bob.  Note that the transcript will include the value of $X,Y$.

Now unconditionally, $X,Y$ are dependent (there is probability $1/2$ that they are Heads,Heads and probability $1/2$ that they are Tails,Tails). But conditioned on the transcript, $X,Y$ are independent (e.g., if the transcript says they are Heads, then with conditional probability $1$ they are Heads,Heads and all other cases have conditional probability $0$; that meets the definition for independence).


Why isn't there just one "keystone" activation function in Neural Networks? This article says the following:

Deciding between the sigmoid or tanh will depend on your requirement of gradient strength.

I have seen (so far in my learning) 7 activation functions/curves. Each one seems to be building on the last. But then like the quote above, I have read in many places essentially that "based on your requirements, select your activation function and tune it to your specific use case".
This doesn't seem scalable. From an engineering perspective, a human has to come in and tinker around with each neural network to find the right or optimal activation function, which seems like it would take a lot of time and effort. I've seen papers which seem to describe people working on automatically finding the "best" activation function for a particular data set too. From an abstraction standpoint, it's like writing code to handle each user individually on a website, independently of the others, rather than just writing one user authentication system that works for everyone (as an analogy).
What all these are papers/articles are missing is an explanation of why. Why can't you just have one activation function that works in all cases optimally? This would make it so engineers don't have to tinker with each new dataset and neural network, they just create one generalized neural network and it works well for all the common tasks today's and tomorrow's neural networks are applied to. If someone finds a more optimal one, then that would be beneficial, but until the next optimal one is found, why can't you just use one neural network activation function for all situations? I am missing this key piece of information from my current readings.
What are some examples of why it's not possible to have a keystone activation function?

Those are old articles.  Tinkering with activation functions probably isn't your best use of time, in most cases.  Today, the standard engineering practice is (to a first order of approximation): use ReLU and don't stress over it.  ReLU is clearly superior to sigmoid and tanh for most cases, so if you read older articles they'll talk about sigmoid and tanh, but today, ReLU has replaced them.  There are fancier newer activation functions that in some cases are slightly better than ReLU and in some cases are slightly worse but the short version is ReLU is good enough and don't worry about the others at this stage in your learning and knowledge; just use ReLU and call it a day.
This is a crude simplification and there are absolutely exceptions but I'm giving you a rule of thumb that will be pretty reasonable in practice.
Why?  My main answer is that you will need to get used to the fact that when working with neural networks, we don't really know the answer to most "why" questions.  Sometimes we have intuition and theories but at its heart this is an empirical science: we don't really understand why neural networks work well.  There are papers that give some explanation of why ReLU seems to do better than sigmoid/tanh -- in particular, sigmoid/tanh suffer from vanishing gradients when their inputs are in the tails of the sigmoid/tanh (as then their output is exponentially small, so the gradient is essentially zero), and then training gets stuck or proceeds very slowly -- but don't expect great theory that is going to tell you what to do.  Instead, this is largely an empirical science, and if we're lucky, we have experiments and theory that helps us understand the empirical data we see.
I don't see any reason to expect there to be a single activation function that is optimal for all tasks, so I'm not bothered if that isn't true and don't feel that we need a "reason" for it to be false.


Finding a negative cycle in a bipartite graph The Bellman-Ford algorithm can be used to find a negative cycle in a general graph, in time $O(|V||E|)$. Is there a faster algorithm for finding a negative cycle in a bipartite directed graph, where the edges in one direction (from X to Y) are all positive and the edges in the other direction (from Y to X) are all negative?

One idea that I considered is to solve two instances of the minimum-weight assignment problem: one with only the edges from X to Y, and one with only the edges from Y to X. Combining the two assignments gives a directed cycle in the original graph. However there are two problems with this idea:

The computational problem of finding a minimum-weight assignment is not necessarily smaller than Bellman-Ford, for example the Hungarian algorithm requires time $O(|V|^3)$.
The directed cycle found in this way is not necessarily minimum-weight in the original graph; it is possible that the original graph has a negative cycle while this algorithm will yield only a positive cycle. For example, consider a graph with four vertices in each side, with the following weights:
\begin{align*}
w(x_1\to y_1) = w(x_2\to y_2) &= 1
\\
w(y_2\to x_1) = w(y_1\to x_2) &= -2
\\
w(x_3\to y_3) = w(x_4\to y_4) &= 5
\\
w(y_4\to x_3) = w(y_3\to x_4) &= -3
\end{align*}
and all other weights are $+\infty$.

There is a negative cycle $x_1\to y_1\to x_2\to y_2$ (total weight -2). However, the minimum-weight assignment from X to Y has weight 12 and the  minimum-weight assignment from Y to X has weight -10 so the total is positive.

Given a directed graph, turn each edge $(u,v)$ into two edges $(u, x)$ and $(x,v)$ with the same weight where $x$ is a newly added vertex. Now the graph becomes a bipartite graph, and there is a negative cycle in the original graph if and only if there is a negative cycle in the new bipartite graph.

Suppose the two parts of the bipartite graph are $X$ and $Y$. We increase the weights of all edges from $X$ to $Y$ by $r$ and decrease the weights of all edges from $Y$ to $X$ by $r$, where $r$ is a large enough positive integer. Now we get a new bipartite graph where all edges from $X$ to $Y$ have positive weights and all edges from $Y$ to $X$ have negative weights. In addition, there is a negative cycle in the original bipartite graph if and only if there is a negative cycle in the new bipartite graph.

So if there is an $O(f(|V|,|E|))$ algorithm to solve your problem, we can solve the problem on general directed graphs in $O(|E|+f(|V|,|E|))=O(f(|V|,|E|))$ (since $f(|V|,|E|)\in \Omega(|E|)$) time by applying the algorithm on the bipartite graph obtained from the conversion above. This means your problem is asymptotically no easier than the problem on general directed graphs.


Reduction between these two languages I'm given $L_\cap=\{\langle M_1\rangle\#\langle M_2\rangle\mid L(M_1)\cap L(M_2)\neq\emptyset\}$ and $L_U=\{\langle M\rangle\#w|M \text{ accepts } w\}$.

How can I reduce the former to the latter: $L_\cap\leq_RL_U$? My idea was to build a machine $M$ simulating $M_1$ and $M_2$  in series. $M$ accepts a word if and only if both $M_1$ and $M_2$ do. So we feed all words to the machine taking $M$ and words until we find one, otherwise keep running. But the proplem is the machine is not halting guaranteed since it can run forever. What will be the correct solution?

Your solution is almost there: I do not think it is necessary to construct a machine that always halts. The problem running $M$ on input $w$ does not always halt either.

Running $M_1$ and $M_2$ over all input strings $x$ is tricky: indeed,if one of the machines does not halt on a particular input, then the new machine $M$ will not consider the next input. The solution for that is usually called dove tiling, where more and more inputs are simulated step by step.

This can be avoided (or better: hidden) by assuming non-deterministic machines. $M$ guesses an input $x$ and simulates both $M_1$ and $M_2$ on that input $x$. Now $M$ halts (on the empty input) whenever the languages of $M_1$ and $M_2$ intersect.


DFA to regular expression how to deal with 'sink state' Didn't find a clear statement on this so I just want to make sure I'm right. If I have DFA with edges leading to a 'sink state' (non-accepting state we don't get out of) the edges leading to the sink state and the edge from the sink to itself won't get any representation in the regular expression right? We can just remove those edges and stated at the beginning.. Am I right?

Yes, if you have a DFA with a state $q_{rej}$  acting as a sink state, then it is there only for the formal definition of the DFA, so that our DFA will "know"  to reject any other inputs that loop in there. An NFA on the other hand, does have to have a sink state, and you can just erase it. A DFA must describe what to do on each input, whether it is an input that will be accepted or whether rejected. An NFA describes which words you will accept, it has no need to describe which you reject. A regular expression works on the same principal, it only describes which inputs you accept, it does not describe which are rejected.

Hope this clarified your question.

(note that you cannot remove those edges and the sink state in the DFA, because, as stated above, a DFA must decide an answer on each input, even if it loops in a sink state. Removing it will result in an NFA)


Suffix array construction algorithm linear complexity constant A non-recursive linear Suffix Array construction algorithm is presented in this thesis: Linear-time Suffix Sorting. The author claims that, overall, the algorithm runs at $O(n)$. While it is well explained, there are only hints that this is case. The implementation of the algorithm is in this GitHub repository written in C.

My question is: What are the complexity constants (say $O(\alpha n + \beta)$ where $\alpha$ and $\beta$ are constants) for C code between lines 92 and 186?

Constants like this are generally not calculated for the run time of algorithms, because it's not clear what they would count - would they count the number of some sort of primitive C operation executed, or the number of x86-64 operations, or the number of arm64 operations, or the microcode operations, or ...?

More frequently than calculating the constants, people measure the run time and show the $\alpha$ that fits best. They will also sometimes calculate the number of times a specific operation is executed, like comparisons or swaps in a sorting algorithm.


What's the fastest known algorithm for generating $k$-subsets of an $n$-set? We are given a set of $n$ elements and we'd like to generate all $k$-subsets of this set. For example, if $S=\{1,2,3\}$ and $k=2$, then the answer would be $\{1,2\}, \{1,3\}, \{2,3\}$ (order not important).

There are $\binom{n}{k}$ $k$-subsets of an $n$-set (by definition :-), which is $O(n^k)$ (although this is not tight). Obviously any algorithm for the problem will have to run in time $\Omega(\binom{n}{k})$.

What is the currently fastest known algorithm for this problem? Can the lower bound of $\binom{n}{k}$ actually be achieved (so that we have an essentially optimal algorithm)?

(Note: I reposted this from StackOverflow as the question seems better suited for CS StackExchange.)

Knuth's Algorithm R Revolving-Door combinations is generally accepted as the current best for algorithms and time complexity for generating combinations.


Transforming TM with useless state(s) I'm new to Computation Theory and trying to figure out the undecidability problems. Last night, I came up with the language of TM with a useless state:

  $\text{USELESS_TM} = \{ \langle M, q \rangle\mid q\text{ is a useless state in TM }M\}$

where q is a state that M never enters on any input w. The problem is simply defined as: "determining whether a Turing machine has any useless states".

The question wanted me to show that this language is undecidable using a reduction argument. I thought it would be logical to reduce EMPTY_TM to USELESS_TM, and using contradiction show that if USELESS_TM is decidable, then EMPTY_TM will be decidable (which we know it's not).

I wanted to step a little bit forward in grasping the concepts of USELESS_TM. Is it possible to modify this Turing Machine to another TM M without useless states in such a way that L(USELESS) = L(M)? I thought about just removing the useless states, as the machine never gets into those states, so the language won't change. But, is there another way by like modifying a TM's definition to ensure that it has no useless states?

UPDATE . I borrowed the first example from  Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Problems 5.13 --Textbook

This question is refreshing. Answers are given in the headers below.

There exists a Turing machine (TM) without useless states that accepts the same language as an arbitrary given TM.
Let TM $M=⟨Q,\Gamma, b,\Sigma, \delta, q_0, F⟩$ where
$$\delta: (Q\setminus F)\times \Gamma\not\to Q\times\Gamma\times\{L,R\}$$
is the transition function, where $L$ is left shift, $R$ is the right shift. For each state $q\in Q$, $q$ is either useful (reachable) or useless (non-reachable).
Let $Q'$ be the set of all useful states. Let $\delta'$ be the restriction of $\delta$ on $(Q'\setminus F)\times \Gamma$. Then we can check $M'=⟨Q',\Gamma, b,\Sigma, \delta, q_0, F\cap Q'⟩$ is a well-defined TM without useless states that accepts the same language as $M$.
Intuitively, $M'$ is simply $M$ with all useless states removed.

Exercise 3.19 indicates none of the following two languages is decidable.
$$\text{USELESS_STATES}=\{⟨M, g⟩\mid M \text{ is a TM with a useless state } g \}$$
$$\{⟨M, M'⟩\mid M \text{ is a TM and }M'\text{ is defined based on M as above} \}$$

No algorithm can produce a TM without useless states that accepts the same language as an arbitrary given TM.
For the sake of contradiction, suppose there is a such an algorithm $A$.
Let $M$ be a given TM. Applying $A$, we can construct another TM $M'$ without useless states that accepts the same language as $M$.
What is $F'$, the set of final states (a.k.a. accepting states) of $M'$?

If $F'$ is empty, then $M'$ never accepts any word. That is, $L(M')$ is empty.
If $F'$ is not empty, then $M'$ does accept some word since the states in $F'$ are reachable. That is, $L(M')$ is not empty.

Just by checking whether $F$ is empty or not, we will know whether $L(M')$ is empty or not. Since $L(M')$ is the same as $L(M)$, we will also know whether $L(M)$ is empty or not. Hence, we can decide whether $L(M)$ is empty or not.
However, it is well-known that it is undecidable to determine whether an arbitrary given TM accepts no words or not. This is a contradiction.
What we have used in the proof above is the following obvious property of TMs without useless states. Such a TM accepts at least one word if and only if it has at least one final state.
Intuitively, there is no algorithm to determine whether a final state in a TM is useless or not.

Here are two easy related exercise.
Exercise 1. Show the following language is not decidable.
$$\{⟨M⟩\mid M \text{ is a TM that accepts no words}\}$$

Exercise 2. Show the following language is not decidable.
$$\{⟨M, M'⟩\mid M \text{ is a TM and }\\ M' \text{ is a TM without useless states such that } L(M)=L(M')\}$$


Pure type systems and let-expressions I can not find any simple and detailed source of how to add non-recursive let-expressions to pure type systems.

The best I found is the Henk paper by Simon Peyton Jones, but his explanation of this point is very brief.

Can someone link some references about this topic (source code is accepted)?

EDIT

The let I want to add has the following syntax:

let x : T = M in N

where x is the variable name, T is its type, M is the expression with which all free occurrences of x in expression N will be replaced. It can only introduce nested definitions, so recursion is impossible.

In untyped lambda calculus it is syntactic sugar. By analogy it should be equivalent to (λ(x : T) -> N) M, but as you know this conversion does not type-check in PTS, so new type rules must be included.

There is a definite dearth of literature on how to add let bindings to PTSes or dependently typed systems, though I do seem to recall this reference:

Paolo Severi, Pure Type Systems with Definitions.

From a theoretical perspective, you want to have the intuitive rule:

$$\frac{\Gamma\vdash t[M/x] : A[M/x]\qquad \Gamma\vdash M:B}{\Gamma\vdash\mbox{let}\ x :B :=M\ \mbox{in}\ t\ :\ A} $$

But this doesn't help explain much about how to perform type checking and conversion, which is a quite subtle subject.


How does the OS handle multiple stacks in its physical memory? Without assuming ASLR...
Processes have virtual addresses, and they manage stacks & heaps of their own. However, these all get mapped to physical addresses somewhere on the memory.
Let's say we have Process A and Process B. Process A starts before Process B. Process A puts some stuff on the stack. We switch to Process B. It puts some stuff on the stack.
However, Process A finishes, and all its elements need to be removed off the stack. However, Process B's elements are still on the stack, so we can't just force the stack pointer down.
How is this relieved? Or is physical memory really all heap?

The point you make at the very end of your question is the right one.
No modern computer has a stack. In hardware terms it turns out to be superfluous, wasteful and useless.
A stack is superfluous because one can easily perform the operations “write a value”, “retrieve the last value written”, and so on by having a pointer to a memory location. “Push” can be implemented by advancing the pointer and writing to the location it points to; “pop” by reading the pointed-to location and undoing the advance of the pointer. (On Intel architectures the pointer is a register called SP, and “advancing” decrements SP before writing to memory). This emulation of a stack requires no hardware at all - only memory, which exists already.
A hardware stack is wasteful because it requires special mechanisms over above the “read at location”, “write at location” which we already have because we have RAM. (Some early or embedded microprocessor architectures have gone the other way, having a very few levels of stack on-chip).
A hardware stack is useless because fashionable computer languages such as C cannot function with a stack in the strict sense - they need to access not just the last pushed value (such as a return address) but values pushed earlier on, which can be the arguments to a subroutine, for example.
Returning therefore to your main question: among the memory assigned to a process there is an area of memory which the process will use for its stack. Its stack pointer will point into that area. Switching from one process to another involves saving the whole state of the old process including the stack pointer and loading the whole state of the new process including the stack pointer. Because there is no special stack as such, on process termination everything is simply forgotten: nothing else needs to be done.


Algorithms : most lightweight circle in directed graph that goes through specific vertex I have directed Graph G(V,E) with weight function w. so that weight of each (u,v) is a positive value.
I need to find the most lightweight circle in the graph that vertex k' is part of it.

I've also given an algorithm i can use which can find the most lightweight path for a graph with positives weights ( i can use it only once).

I thought about creating a sub graph G' where all vertices and edges that are strongly connected components. find the graph which k' is part of it. then find for the most lightweight adjacent edge from k' to some v of vertices. from that v i can run the algorithm given and find the lightweight path then add the weight of the vertex missing ( (k',v) ).

is that seems correct ? I'm in the beginning of this course and I feel i'm not there yet.

Just add a node k1 to your graph, that has exactly the same connections as k, with the same weights (you can keep only the edges going to k1 if you'd like), and query the shortest path from k to k1 in your (slightly) extended graph. Your cycle is exactly this path, only replacing back k1 with k at the end of the path.

Your algorithm would be slower and would not always give the right answer: even if v is the closest node to k, maybe it is not in the best cycle (you could for instance have k->v cost 1, v->k cost 100, and k->u and u->k both cost 2 or some u).