Is it NP-hard to fill up bins with minimum moves? There are $n$ bins and $m$ type of balls.
The $i$th bin has labels $a_{i,j}$ for $1\leq j\leq m$, it is the expected number of balls of type $j$.

You start with $b_j$ balls of type $j$. Each ball of type $j$ has weight $w_j$, and want to put the balls into the bins such that bin $i$ has weight $c_i$. A distribution of balls such that previous condition holds is called a feasible solution.

Consider a feasible solution with $x_{i,j}$ balls of type $j$ in bin $i$, then the cost is $\sum_{i=1}^n \sum_{j=1}^m |a_{i,j}-x_{i,j}|$. We want to find a minimum cost feasible solution.

This problem is clearly NP-hard if there is no restriction on $\{w_j\}$. The subset sum problem reduces to the existence of a feasible solution.

However, if we add the condition that $w_j$ divides $w_{j+1}$ for every $j$, then the subset sum reduction no longer works, so it's not clear whether the resulting problem remains NP-hard. Checking for the existence of a feasible solution takes only $O(n\,m)$ time (attached at the end of the question), but this does not give us the minimum-cost feasible solution.

The problem has an equivalent integer program formulation.
Given $a_{i,j},c_i,b_j,w_j$ for $1\leq i\leq n,1\leq j\leq m$:
\begin{align*}
\text{Minimize:} & \sum_{i=1}^n \sum_{j=1}^m |a_{i,j}-x_{i,j}| \\
\text{subject to:} & \sum_{j=1}^m x_{i,j}w_j = c_i \text{ for all } 1\leq i\leq n\\
& \sum_{i=1}^n x_{i,j} \leq b_j \text{ for all } 1\leq j \leq m\\
& x_{i,j}\geq 0 \text{ for all } 1 \leq i\leq n, 1\leq j \leq m\\
\end{align*}

My question is,

  Is the above integer program NP-hard when $w_j$ divides $w_{j+1}$ for all
  $j$?

An algorithm to decide if there is a feasible solution in $O(n\,m)$ time:

Define $w_{m+1}=w_m(\max_{j} c_j + 1)$ and $d_j = w_{j+1}/w_j$. Let $a\%b$ be the remainer when $a$ is divided by $b$.

If there exists a $c_i$ that's not divisible by $w_1$, return "no feasible solution". (the invariant $c_i$ divides $w_j$ will always be maintained in the following loop)
for $j$ from $1$ to $m$:

$k \gets \sum_{i=1}^n (c_i/w_j)\%d_j$. (the minimum of balls of weight $w_j$ required)
If $b_j<k$, return "no feasible solution".
$c_i \gets c_i - ((c_i/w_j)\% d_j)$ for all $i$. (remove the minimum number of required balls of weight $w_j$)
$b_{j+1} \gets \lfloor (b_j-k)/d_j \rfloor$. (group smaller balls into a larger ball)

return "there is a feasible solution".

A polynomial time solution to the special case where $n=1$, and $w_j$ are power of $2$s

It is known that if $n=1$ and all $w_j$ are powers of $2$, then this special case can be solved in polynomial time.
\begin{align*}
\text{Minimize:} & \sum_{j=1}^m |a_j-x_j| \\
\text{subject to:} & \sum_{j=1}^m w_j x_j = c\\
& 0 \leq x_j \leq b_j \text{ for all } 1\leq j \leq m\\
\end{align*}

The solution was hinted at by Yuzhou Gu, and a write up may be found here.

Some background.  The above problem is the knapsack problem with restrictions.  The most efficient knapsack problem solution with or without restrictions can be solved in pseudopolynomial time, still NP-Hard.  For some variations, see https://en.wikipedia.org/wiki/Knapsack_problem#Definition.  The first restriction in this variation is that the value of items (balls) to be placed in the knapsack (bins) does not matter.  The problem is then restricted to the amount of time it takes to put the items in the knapsack.  The original problem requires the most valuable items to be placed in as short amount of time possible.  Another restriction with this version is that the weights and all other arguments are integers.  And the restriction of interest is that the weights $w_j$ divide $w_{j+1}$ for all $j$.  Note: the fractional knapsack problem can be solved in polynomial time, but does not present the most practical solutions to the original problem.  This problem uses integers that divide evenly (no rational solutions).  Perhaps see What's the big deal with the knapsack problem?.

The main question perhaps should be "is this problem still NP-Hard when $w_j$ is unbounded by a polynomial corresponding to $i$, as the problem is less complex (in P) when it is bounded?  The reason I say this is because the problem can be shown to be in P when $w_j$ is bounded and NP-Hard when $w_j$ does not necessarily divide $w_{j+1}$ evenly (the weights are simply random), all restrictions limit the complexity of this problem to these two conditions.  These conditions (1. the random weight knapsack problem without the item-value restriction and 2. divisible weight knapsack problem without the item-value restriction) negate each other in terms of reducing complexity, as the quotients of the weights may be random themselves (especially when unbounded), thus imposing exponential time calculations (this will be shown in the example below).  Additionally, because $w_j$ divides $w_{j+1}$, $w_j$ increases in size exponentially for each $j$.  This is because instead of using random weighted items (balls whose unit weight may all be limited to unit weights under 100 or 50 or even 10), the restriction instead causes the time complexity to depend on the number of digits of $w_j$, the same as trial division, which is exponential.

So yes, the above integer program remains NP-hard even when $w_j$ divides $w_{j+1}$ for all $j$.  And this is easily observed.

Example 1: let $n = 1$ and $w_p$ be powers of two.  Because of constant two, the entire problem is solved in quadratic time, as your example shows.  The weights are not random and therefore the calculation is solved efficiently.

Example 2: let $w_{j+1}$ be defined as $w_j * p$, where $p$ is the prime number corresponding to $j$, such that $p=2, j=1: p=3, j=2, p=5, j=3, p=7, j=4,...,P, J$.  This is applicable, as $w_j$ divides $w_{j+1}$ for all $j$.  We get each $w_j$ is the product of all the primes up to $j$.  The values of the unit weights increase as such: $1, 2, 6, 30, 210, 2310, 30030, ...$.  Since there is a bound ($p_j$ ~ $j log (j)$, via the prime number theorem), as the quotients are all primes, we get the complexity NP-Intermediate.

Example 3: let $w_{j+1}$ be defined as $w_j * R_p$, where $R_p$ is a randomly chosen prime number from two to infinity, corresponding to $j$.  This is applicable to this problem, as $w_j$ divides $w_{j+1}$ for all $j$.  We get the first 5 quotients (randomly falling from two to infinity), as $101, 2657, 7, 3169, 2$.  We see that even at the 5th ball, the weight has eleven digits.  Fortunately, the fifth quotient was two and not a prime in the order of $10^{100}$ or larger.

Example three above is what happens when $w_j$ is not bounded (random weights) by a polynomial corresponding to $i$.  The time complexity is exponential, NP-Hard.  For some perspective, just add up all the weights, see if they fit. But there isn’t a solution to solving it significantly faster by making the weights divisible than trying each subset to see if it works. After a few dozen balls, you are still entering the realm of even the trillions of subsets or trillions of digits.


Reducing lambda expression to normal form Can someone explain the steps to reduce
  $$ (\lambda n. \lambda m. \lambda f. \lambda x.\ n\ (m\ f)\ x)\ (\lambda f. \lambda x.\ f\ (f\ x))\ (\lambda f. \lambda x.\ f\ x) $$
to $\lambda y. \lambda z.\ y\ (y\ z)$?

$\lambda$-calculus is a rewriting system, but it's power to express all partial recursive functions makes it equivalent to Turing machines, in the sense that it is a universal model of computation. Means of computation in $\lambda$-calculus are conversions and reductions, of which the main ones are $\beta$-reduction and $\alpha$-conversion. You can learn a lot about $\lambda$-calculus on Wikipedia alone.

$\alpha$-conversion
Take for example $\lambda$-expressions $(\lambda x. x)$ and $(\lambda y. y)$. We say they are $\alpha$-equivalent because they clearly represent the same function. In short, we can rename variables (and sometimes have to).

$\beta$-reduction
This relation is the one that "gives life" to $\lambda$-expressions and reduces them to normal forms. We use $\beta$-reduction on terms of the form $(\lambda x. M)\ N$, i.e. when applying abstraction to some term $N$, and we call that construction a redex. What this expression becomes after $\beta$-reduction is written $M[x:=N]$ and it means that we replaced all free occurrences of $x$ in $M$ with $N$. For example:
$$ (\lambda x. x\ x)\ N \rightarrow_\beta N\ N$$

We will be reducing leftmost outermost redex in each step. This strategy garantees that we will get to normal form if it exists.

Now let us dive into this...
Let's find a leftmost outermost redex (underlined) in your expression:
  $$\underline{\Bigl(\lambda n.\lambda m.\lambda f.\lambda x. n\ (m\ f)\ x\Bigr)\ \Bigl(\lambda f. \lambda x. f\ (f\ x)\Bigr)}\ (\lambda f. \lambda x. f\ x)$$

We have $\Bigl(\lambda n.\lambda m.\lambda f.\lambda x. n\ (m\ f)\ x\Bigr)$, which is an abstraction (it is of the form $\lambda n. M$), that is applied to $\Bigl(\lambda f. \lambda x. f\ (f\ x)\Bigr)$, so ($\beta$-reduction) we have to replace all free occurences of $n$ in $M$ with $\Bigl(\lambda f. \lambda x. f\ (f\ x)\Bigr)$. We get $\biggl(\lambda m.\lambda f.\lambda x. \Bigl(\lambda f. \lambda x. f\ (f\ x)\Bigr)\ (m\ f)\ x\biggr)$, so entire expression is now (where I already underlined next outermost redex):
  $$\underline{\biggl(\lambda m.\lambda f.\lambda x. \Bigl(\lambda f. \lambda x. f\ (f\ x)\Bigr)\ (m\ f)\ x\biggr)\ (\lambda f. \lambda x. f\ x)}$$
We now have to substitute $(\lambda f. \lambda x. f\ x)$ for $m$ in $\biggl(\lambda f.\lambda x. \Bigl(\lambda f. \lambda x. f\ (f\ x)\Bigr)\ (m\ f)\ x\biggr)$ and get
  $$\lambda f.\lambda x. \underline{\Bigl(\lambda f. \lambda x. f\ (f\ x)\Bigr)\ \Bigl((\lambda f. \lambda x. f\ x)\ f\Bigr)}\ x$$
Now just keep reducing
  $$\lambda f.\lambda x. \underline{\Bigl(\lambda x. ((\lambda f. \lambda x. f\ x)\ f)\ (((\lambda f. \lambda x. f\ x)\ f)\ x)\Bigr)\ x}$$
  $$\lambda f.\lambda x. \Bigl(\underline{(\lambda f. \lambda x. f\ x)\ f}\Bigr)\ \biggl(\Bigl((\lambda f. \lambda x. f\ x)\ f\Bigr)\ x\biggr)$$
  $$\lambda f.\lambda x. \underline{(\lambda x. f\ x)\ \biggl(\Bigl((\lambda f. \lambda x. f\ x)\ f\Bigr)\ x\biggr)}$$
  $$\lambda f.\lambda x. f\ \biggl(\Bigl(\underline{(\lambda f. \lambda x. f\ x)\ f}\Bigr)\ x\biggr)$$
  $$\lambda f.\lambda x. f\ \Bigr(\underline{(\lambda x. f\ x)\ x}\Bigr)$$
  $$\lambda f.\lambda x. f\ (f\ x)$$
And now, if you are still alive, remember $\alpha$-equivalence. We can change the names of variables, say $f$ to $y$ and $x$ to $z$, and obtain your wanted solution.

What have we computed?
We computed that $2 \cdot 1 = 2$, in $\lambda$-calculus using Church numerals:

$c_0 = \lambda f. \lambda x. x$
$c_1 = \lambda f. \lambda x. f\ x$
$c_2 = \lambda f. \lambda x. f\ (f\ x)$
$\vdots$

Expression $\lambda n.\lambda m.\lambda f.\lambda x. n\ (m\ f)\ x$ is the multiplication operator, and other two expressions (on which this operator was applied) are Church numerals for $2$ and $1$.


Checking whether an integer is a square or higher power Is there an algorithm to check whether an integer $n$ is a square?  What about higher powers, e.g., testing whether $n$ is a $k$th power?

I understand that the Jacobi symbol $\left(\frac{b}{n}\right)$ can be computed in $O(\log n)$ without needing to know the prime factorization of $n$ but then this seems to be useful only for squares (not higher powers), and even then, it can still be inconclusive.

Maybe there is some way of refining the use of the Jacobi symbol for my question?

The standard algorithm for determining whether an integer $n$ is a perfect power goes like this. We check whether it is a perfect $k$th power for $k \in \{2,\ldots,\log n\}$; as an optimization, it suffices to consider only prime $k$. Given $k$, we compute $\sqrt[k]{n}$ using binary search or using some fixed-point iteration such as Newton's method. Either way, we find a candidate for $\sqrt[k]{n}$, and can check whether $(\sqrt[k]{n})^k = n$ or not. For more details on computing $\sqrt[k]{n}$, consult for example this paper (mentioned in Ricky Demer's deleted answer), Step 1.


Computing mod inverse? How might one compute $4^{-1} \mod 17$ I know the answer is 13. I'm just not sure how to arrive at that number, and can't find any good explanations. Any help would be great

In order to compute the inverse of $a$ modulo $n$, use the extended Euclidean algorithm to find the GCD of $a$ and $n$ (which should be 1), together with coefficients $x,y$ such that $ax + ny = 1$. The inverse of $a$ modulo $n$ is thus $x$.

The extended Euclidean algorithm gives a constructive proof of Bézout's identity, which states that for all integers $a,b$ there exist integers $x,y$ such that $ax+by = \mathrm{gcd}(a,b)$. A different proof shows that the minimal positive value of $ax+by$ (over all $x,y$) is $\mathrm{gcd}(a,b)$.

The extended Euclidean algorithm works in greater generality, for any Euclidean domain. An important example is the ring of polynomials over a field.


Language of balanced parentheses; Biconditional proof about parentheses Let L be language of balanced parentheses.

(a) Prove If there are equal number of ('s and )'s and every prefix of w contains at least as many ('s as )'s, then w is in L.

(b) Prove If w is in L, then there are equal number of ('s and )'s and every prefix of w contains at least as many ('s as )'s.

After much thought, I don't seek what I'm supposed to be doing. All I know is that I'm supposed to be using induction.

Here is the grammar that generates L: $S\to SS|(S)|\epsilon$

You are given two different definitions of the language of balanced parentheses:

$w \in L$ iff $w$ contains an equal number of "(" and ")", and every prefix of $w$ contains at least as many "("s as ")"s.
$L$ is generated by the grammar $S \to SS | (S) | \epsilon$.

You need to show that both definitions are the same. The easy direction is showing that each word generated by the grammar satisfies property (1). You do this by induction - either induction on the length or "structural" induction, which in this case is induction on the number of derivation step (base case: $S \to \epsilon$, steps: $S \to SS$, $S \to (S)$). The other direction is more complicated. You need to use complete induction; given a word $w$ satisfying (1), figure out which production needs to be applied first, and which parts of the word it generates, and then appeal to the induction hypothesis.


How to solve the optimization of bin packing using the decision version Let us say the optimization version of the bin packing problem asks you to give a packing using the fewest bins possible and the decision version asks if it is possible to pack the bins into $k$ bins.

  How can you reduce the optimization version to the decision version?

If you only have to answer what the fewest bins possible is then it is clear you can use binary search. But if you actually have to give the packing, I can't see how to do it.

If you could solve the decision problem (do these items fit in k bins) you can obviously solve the optimisation problem (what is the minimum number of bins) using binary search. But you actually want to know what to put into each box. That’s easily done doing the decision problem at most n^2 times.

Let’s say you know k boxes are required and sufficient. Sort the item by descending size. Replace the biggest and second biggest item with one item of their combined size and check if the new items fit into k bins. If not, try the largest and third largest item, and so on. After n attempts, you either know two items that are in the same bin in an optimal solution, or you know the largest item is on its own. And you repeat that, each time you find that you can put two items in the same bin by solving at most n decision problems.


Show that the single-tape TMs that can not write on the portion the portion of the tape containing the input string recognize only regular languages Show that the single-tape TMs that can not write on the portion the portion of the tape containing the input string recognize only regular languages.

The first part of the answer in a book said that:

We give a DFA $A$ that is equivalent to TM $M$. Design $A$ in two stages.

We arrange the states and transitions of $A$ to simulate $M$ on the read-only input portion of the tape.
We assign the accept states of $A$ to correspond to the action of $M$ on the read/write portion of the tapeto the right of the input.

Given below the whole answer (sorry for using pictures but the answer was so long and I do not understand it and I have not enough time to write it):

But I do not understand many points:

Why the domain and the codomain of the defined function takes this form? and why only finitely many such functions exist as stated by the last line in the first paragraph?
Why the author wrote $F_{\epsilon}$ as in the third paragraph? did he used the idea of epsilon transitions?
The last paragraph in the solution I did not understand its idea at all?

Could anyone clarify the above questions for me please?

I saw an answer for the question here Single-tape Turing Machines with write-protected input recognize only Regular Languages but I did not understand it at all.

The general idea is that the TM has only finite memory while being in the input part of the tape. It can do arbitrary computations in the right part of the tape, but it can only observe a finite memory footprint of the input. It starts in the input part (on the left) and it can reenter the input part (from the right) arbitrarily often. But each time it enters the input part, the only thing that matters is the state it has when entering (or the fact that it starts from the left). And the only outcome of processing the (read-only) input part is the state it has when it exists (or the fact that it does not exit because it has accepted or rejected in the mean time).

1) That is already  the reason for the domain and codomain. The domain is everything that matters about entering the input part, the codomain is everything that matters about exiting that part. Hence the function completely describes the behaviour of the TM on the input part. In a sense, the function contains everything the TM will ever find out about the word $s$.

Both domain and codomain are finite, hence so is the set of functions. Although the definition is about infinitely many words $s$, there will only be a finite number of different functions $F_s$.

2) $F_{\varepsilon}$ is not about $\varepsilon$-transitions. And it does not expand the previous definition. It is just the special case $s=\varepsilon$, that is the case of the empty input word. Or rather, the case of the empty prefix. After all, the paragraph where this appears is all about how $F_s$ can be computed incrementally along prefixes of $s$.

3) By now we have fully defined the automaton, except for acceptance. And the automaton state fully describes what the TM can do with the word we have read. We have not yet said anything about the part of the TM's computation that happens outside of the input word. The trick is that we do not have to delve into that computation. We just say that the state $F_s$ is accepting, if the word $s$ belongs to the TM's language. The paragraph has an explanation why that is well-defined.


Pi Calculus: Restriction necessary for molecular (atomic) action? In "A Calculus of Mobile Processes, Part 1" [1], Milner et al. give an example for transmitting a pair of values $(u,v)$ from the process $P$ to either $R$ or $Q$ (see page 13). All three processes are assumed to run in parallel.

They present following solution:

$$
\begin{align}
P &= (w) (\bar{x}(w).P' | \bar{w}u.\bar{w}v.0) \\
Q &= x(w).w(y).w(z).Q' \\
R &= x(w).w(y).w(z).R'
\end{align}
$$

They claim that "it is vital to this idea that w (...) is indeed a private name". Why is this a necessity?

Wouldn't following solution without restriction work?

$$
\begin{align*}
P &= \bar{x}(w).P' | \bar{w}u.\bar{w}v.0 \\
Q &= x(\alpha).\alpha(y).\alpha(z).Q' \\
R &= x(\beta).\beta(y).\beta(z).R'
\end{align*}
$$

[1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.159.363&rep=rep1&type=pdf

Your solution would work only if you consider $P$, $Q$ and $R$ in parallel as a "closed system", i.e. a system which is not supposed to be composed and interact with an external environment but just to perform internal reactions.

In the context of your quotation, the translation of a polyadic action into a monadic one is supposed to be compositional and to yield a bisimilar labelled semantics.
The role of the restriction is to avoid exposing the actions on $w$ to the environment: what happens if the environment performs actions on the public channel in your solution?
For instance, consider the process $S$
$$
   S = w(y).S'
$$
If put in parallel with your version of $P$, $Q$ and $R$
it can "steal" the first/second component of the couple from $Q$ or $R$.
This is because you do not need to receive $w$ on $x$ to be able to use it if $w$ is a public name, while that is the only way to acquire it when it is restricted.


Why does not valiant's reduction show NP=RP? Valiant converts $SAT$ formula to a $0/1$ matrix such that $Permanent$ of the matrix is $4^m\#SAT$.

We know $Permanent$ can be approximated to $1+\epsilon$ factor with probability $1-\frac1\delta$ in time $poly(m|\epsilon|^{-1}\log\frac1\delta)$.

Why does not these two help me tell when number of witnesses to $SAT$ formula is $0$ in randomized polynomial time?

What do I miss?

As you state, Valiant shows how to construct, given a CNF $\varphi$, a polynomial size matrix whose permanent is a (known) multiple of the number of satisfying assignments of $\varphi$. Unfortunately, this matrix is not non-negative.

Given a non-negative matrix, you can determine whether its permanent is zero or not using an algorithm for bipartite perfect matching; and you can efficiently estimate its value. The same doesn't hold for general matrices.

Valiant further shows how to construct, given a CNF $\varphi$, a polynomial size 0/1 matrix, from whose permanent you can deduce the number of satisfying assignments of $\varphi$. However, the formula is not as simple as before, and in particular, neither bipartite perfect matching nor the efficient permanent estimation algorithms can determine whether $\varphi$ is satisfiable or not.

For details of a later version of this last reduction, see Section 5.1 of Ben-Dor and Halevi, Zero-One Permanent is #P-Complete, A Simpler Proof.


Kolmogorov complexity of strings in a given language Consider the language

$$L = \{1^i 0^j 1^k \mid i + j = 2k, k ≥ 1\}\,,$$

and let $x_n$ be the canonical $n$'th word in $L$. My problem involves proving that the Kolmogorov complexity of $x_n$ can be bounded by

$$K(x_n) \leq c + 2\log_2 |x_n|$$

for some constant $c$.

My ideas :

(please note that I'm not writing this in a formal way, I am neglecting some constants/factors)

we want to be able to compress the string given by x_n above, thus we could set :

$$K(x_n) = K(1^i) + K(0^j) + K(1^k)$$

(to do this compression I evaluate that only i, j and k need to be compressed, thus we only consider the length of the binary representation of i,j and k as the upper-bound of their corresponding Komolgorov Complexity)

$$ \leq log_2 (i) + log_2 (j) + log_2 ((i+j)/2) + C$$

$$ = log_2 (i) + log_2 (j) + log_2 (i+j) - 1 +  C$$

$$ = log_2 (i^2j + ij^2) + K$$

Now we might want to evaluate the length of X_n
$$|x_n| \leq i + j + k = i + j + (i + j)/2$$

now to show the supposition we just need to show that :

$$ log_2 (i^2j + ij^2) \leq 2log_2 |x_n| = log_2 (|x_n|^2) $$

and this is where I get stuck

You haven't explained what is meant by the canonical $n$th word, but I assume that there is an algorithm generating all words in $L$, and the canonical $n$th word is just the $n$th word in this list. One such algorithm could go over all possible words in size-lexicographic order, and check for each word whether it belongs to $L$, outputting the words that are in $L$ in size-lexicographic order.

Given such an algorithm, you can construct a new algorithm which gets $n$ and outputs $x_n$. Using the new algorithm, you can generate $x_n$ by running the new algorithm on the input $n$. Since the new algorithm is fixed, it has some size $C$. A prefix-free encoding of $n$ takes $2\log n$ (in fact, you can do almost twice as good), leading to a description length of $C + 2\log n$. (Depending on your definition of Kolmogorov complexity, you might be able to do away with prefix-freedom, and then you can replace $2\log n$ with $\log n$.)

Note that we have only used the fact that the canonical $n$th word is generated by some algorithm which gets $n$ as input. The particular form of $L$ wasn't important.


Showing a problem on a specific graph is NP-hard Maybe there is a trivial answer to my question or maybe there is not any. But I ask it here and appreciate if anyone can give me a clear answer.

We know that a set of problems like minimum clique cover problem, coloring problem, vertex cover, ... are NP-hard for general graphs, but maybe polynomial-time solvable for specific graphs.

My question is that, if we are given a graph $G=(V,E)$ (I am asking this generally but you can specifically assume the graph described here), and want to find for example minimum clique cover for this graph, how can we show that it is NP-hard (if it is)? Is there any method for that?

There's no such thing as a hard instance. You can always figure out the answer to that one instance and then hard-code that into an algorithm. For example, you can always have an algorithm for SAT that says

if input="(XvY)^(!Xv!YvZ)"
    return SATISFIABLE
else
    [loop through all possible variable assignments]

Incidentally, this is why nobody looks at "best-case complexity", since any algorithm can be adapted to run in best-case constant time in this way.  (Constant because you only have to read a fixed amount of the input to see if it's one of the ones that you have a hard-coded answer for.)

There's a category error in asking if an instance can be NP-complete. Recall the definition of what NP-completeness is:

  A language $L$ is NP-complete if is in NP and every other language in NP is polynomial-time many–one reducible to $L$.

First, that statement doesn't "type-check" if you try to make $L$ be a string rather than a language.  Second, the definition of many–one reductions requires that you have at least one "yes" instance and at least one "no" instance to use as targets for the reduction. One instance isn't enough to make these definitions work.


Sorting on non-linear topology Disclaimer. What I'm going to ask about below may seem to be "Topological sorting". To my understanding, it is not. The latter runs in linear time, while I'm looking for a modification of the regular sort, which is at $N\log N$.

Remark. I'm doing the sort in the reverse order, to use the analogy with heights and masses.

Let us reformulate the sorting problem in the following way. Let us introduce two sets:

A set of sites (positions) $s_a,\,a=1..N$. Those are assigned certain 'heights' $h[s_a]$, which in the case of usual sorting can be simply $h[s_a]=a$.
A set of objects (numbers) $x_i,\,i=1..N$ which are assigned numerical values $m[x_i]$ (according to which the sorting will be performed). In the case of usual sorting, $m[x_i]$ are the numbers to be sorted.

The problem of sorting can be viewed as assigning to each object $x_i$ a site $s_a$ in such a way that for all assignments $\{x_i\to s_a; x_j\to s_b\}$:
$$
h[s_a] > h[s_b] \Longrightarrow m[x_i]\leq m[x_j]
$$

The physical visualization of this problem is a vertical stack of massive balls. Sorting them is equivalent to arranging them in such a way that heavier ones have lower height.

I first wanted to generalize the problem to "higher dimensions", i.e. to assume that the balls can stay in a $2$-dimensional grid, in a bucket, etc. However, I realized that from the computational point of view these settings are equivalent. In other words, whether we have a $2d$ grid with $nm$ balls in each row or a box with $n\times m$ balls in each layer makes no difference.

So, I decided to generalize the problem to an arbitrary topology (which can be reduced to the $2$-dimensional problem actually).

A set of sites (positions) $s_a,\,a=1..N$. Those are assigned certain 'heights' $h[s_a]$. Repetitions are allowed: $h[s_a]=h[s_b]$ for $a\neq b$ is OK.
A set of objects (numbers) $x_i,\,i=1..N$ which are assigned numerical values $m[x_i]$.

Again, we want to assign to each object a site in accordance with the same requirement as above.

Clearly, the brute-force solution for the most general set of 'heights' and 'masses' runs in $N \log N$. One simply sorts the objects according to their 'mass', and then fills the sites, starting from the 'highest' or the 'lowest' one.

Question. Has there been done any research for some particular cases? Clearly, if all the 'heights' are equal, the problem is trivial (which, I guess, means that it is solved in linear time). The first thing coming to my mind would be considering the case of "levels of same lengths",
$$
h[s_a]=\lceil a/r\rceil,\,r\in\mathbb{N}
$$
I would actually expect that this can be done faster than $N\log N$ (I'd assume that $r$ should enter the answer).

If there are $k$ distinct heights, you can sort in $O(n \log k)$ time using a heap or balanced binary tree.  Even better, you can sort with expected time $O(n + k \log k)$, if you use a hashtable.

This leads to a solution to your problem with the corresponding complexity.


Given two data feeds, find out if they capture the same information Say, there are two camera feeds, how can I establish if they were filming the same scene? It seems plausible that there are algorithms that somehow calculate mutual information and detect "causality violations", determining that the other feed is most probably not another perspective of the same source, and that in the presence of noise.

If it is unknown what kind of properties (e.g. dimensionality, physics) the environment that the data feeds capture has, are there algorithms that can construct the transition logic from scratch?

In computer vision, this problem is apparently called 'image registration'.

The problem of finding the relationship between two scenes shot from two different angles is known as the correspondence problem and there is a lot of literature on how to approach it; I suggest you start by reviewing the research literature on methods for solving this.  In particular, I'd suggest that if you can consistently find a correspondence between the two images, you might conclude that they are from the same feed; and if you can't, you might conclude that they aren't.


Are degree and order the same thing when referring to a B-Tree I know the term order of a B-tree. Recently I heard a new term: B tree with minimum degree of 2.

We know that the degree is related to a node but what is the degree of a tree?
Does degree impose any kind of a restriction on height of a B-tree?

I don't think that degree of a tree is a standard term in either graph theory nor data structures. A degree is usually a property of a node/vertex of a graph, which denotes the number of its incident edges. For trees you sometimes consider only the edges to the children.

I suppose "B-tree with minimum degree of 2" means that every node has at least two children. In other words it is a lower bound for the number of children. On the other hand the order of a B-tree denotes the maximal node degree, and is therefore an upper bound.


What's the purpose of the "o(1-o)" in the back propagation algorithm I'm not sure what the purpose of the o(1-o) in the back propagation algorithm achieves? I'm guessing it's related to using the sigmoid function on the output but I'd like to have a proper understanding of the math behind it. Thanks!

Backpropagation is a gradient descent algorithm for minimizing the squared error of the learned network on the data given. In order to minimize by following the gradient, you need to know where the gradient points, this is done using calculus.

Along the way of calculating the gradient, you have to find the derivative of the activation function. When you take the most common activation function, i.e. the logistic rule or sigmoid function $o(z) = \frac{1}{1 - e^{-z}}$ and you differentiate it with respect to the neurons' input $z$ then you get $do/dz = o(1 - o)$. Hence, you are correct, this is related to the use of the sigmoid function, and figuring out in which direction the gradient points.

If you want a more thorough description then consult these notes (pdf).


Calculating fractions of accesses from various levels of memory? (L2 - Main) I'm currently studying computer architectures module, and during the workshop I came a across a series of questions that I struggled to being to answer.

The question goes;

*You have an L1 data cache, L2 cache, and main memory. The hit rates and hit times for
each are:
50% hit rate, 2 cycle hit time to L1.
70% hit rate, 15 cycle hit time to L2.
100% hit rate, 200 cycle hit time to main memory.

What fraction of accesses are serviced from L2? From main memory?

My answer: (200*0.7)/15 = 9.3

To be completely honest, I don't know how to approach these type's of questions, I'd be grateful if someone could point me to resources.

The order of accesses is L1 → L2 (→ L3) → main memory. The chance of missing is $1 - p$ where $p$ is the hit chance.

In order for an access to hit L2 cache, it must have missed the L1 cache, and hit the L2 cache. So the chance is $(1 - 0.5) \cdot 0.7 = 0.35$.

In order for an access to hit main memory, it must have missed the L1 cache, missed L2 cache and hit main memory. So the chance is $(1 - 0.5)\cdot (1 - 0.7) \cdot 1 = 0.15$.


How to solve this partial order reduction in $O(n^2)$? There are two orderings of numbers from the same set. Number $a$ is "immediately before" $b$ iff $a$ appears before $b$ in both sequences and there is no other number that appears between them in both sequences.

So in this example:

Seq 1: 1 2 3 4 5 6
Seq 2: 6 2 1 3 5 4

1 is not immediately before 2 because they appear in opposite orders.
1 is not immediately before 4 because 3 appears between them in both sequences.
2 is immediately before 3 and 3 is immediately before 4.

The problem is to find all pairs $a$, $b$ such that $a$ is immediately before $b$ in $O(n^2)$ time. How can this be done?

I understand that the naive solution can work in $O(n^3)$: For each pair in the first sequence ($n^2$ pairs) verify it using the second sequence ($O(n)$ time).

I think I am able to solve it.

First, have a lookup array for each sequence where array[element] = element's position in sequence [O(1)].

Phrased another way, this algorithm will find all "successors" for each of the elements in the first sequence. Finding successors for each element will take O(n) time.

For i in range(0,n):
    initialize most_recent_successor to None
    For j in range(i+1, n):
        if pos. of seq_1[j] > pos. of most_recent_successor in both sequences:
            advance j
        else:
            most_recent_successor = seq_1[j]
            add (seq_1[i], seq_1[j]) to result

Essentially, if a valid pair (seq_1[i], seq_1[j]) exists, then any pair (seq_1[i], seq_1[k]) will not be valid if the position of seq_1[k] in comes after the position of seq_1[j] in both sequences.

So, for the example in the question, (1, 3) is a valid pair. Therefore, (1,4) and (1, 5) are not valid pairs since 4 and 5 come after 3 in both sequences.

Edit: Please look at ruakh's insightful answer on lookup arrays I used here.


Function minimization as genetic algorithm stop condition I have implemented genetic algorithm for a problem where I have an objective function which I need to minimize:

Cost = ax + by + cz -> min

The genetic algorithm should have found the optimal solution if objective function is satisfied.

The function will never reach 0 or below, so I just need to minimize it. Now, since there are no objective values to be reached, how do I know whether the objective function is satisfied or not?

There are three typical stopping criteria:

You have reached a sufficient value
Your new optimal value hasn't changed for the past $n$ minutes/generations
Your time (and patience) runs out.

The best case scenario is Case 1.  These are the cases where you are looking for a good enough solution, and you have found a solution that is good enough.  This criterion depends on you actually being able to set such a value, of course.

Typically Case 2 is better than Case 3 when it works out.  Here you don't abort your simulation as long as "it's improving" and therefore hasn't found the optimal solution.

But some times you get to borrow the cluster for 2 weeks, and then that's when you shut it off.


the convention for declaring arrays in pseudocode I have a very simple question.
What is the right standard convention to use for declaring arrays?

I understand that for a simple declaration of a variable as an integer, this is the convention:

DECLARE myVar : INTEGER

What about for an integer array of 10 elements?

DECLARE myVar : ARRAY[1,10] of INT

or

DECLARE myVar[1,10] : ARRAY of INT

or something else?

Pseudocode is not a formal language. Declare your arrays however you want, as long as it's obvious what you mean. Including the full limits (as you have in both your array examples) is good, since it means the reader isn't worrying about whether you start your indices at 0 or 1.


Why do we use DAG rather than trees to represent search space of a search problem? I saw people use DAGs to represent the search space of a search problems like the travelling salesman problem. Why is this better than the tree representation? Is the reason to save memory space on the computer or can it reduce the computation time in some way?
I googled but I didn't find an answer, it would be great to have a simple explanation and a reference I can read as I would like to have a good understanding about why DAG approach is a better option.

A search algorithm is a recursive procedure which accepts an instance and a partial solution and attempts to extend it to a complete solution bit by bit. For example, consider a search algorithm trying to solve the eight queens puzzle. The search is initiated with an empty board. On any given position, the search algorithm attempts to place one more queen, in all possible ways. The search halts when a solution is reached.
We can describe the working of the algorithm as a tree. The root is "empty board". An internal node corresponds to a position with several non-attacking queens, and its children are positions with one more queen added. Leaves are solutions to the puzzle.
Consider a node at depth 2, consisting of queens at positions $x$ and $y$. This position can be reached in two ways: adding $x$ then $y$, or adding $y$ then $x$. This means that there are actually two identical subtrees at depth 2 describing the same board position. The second time we reach this position, there is no need to explore it any more. This can be implemented using memoization, a technique in which we remember that we have already explored this position, and now what the outcome is (memoization can be used more generally to compute functions). This corresponds to folding the search tree into a DAG by identifying nodes corresponding to identical positions.
Memoization is closely related to dynamic programming, which is one way to implement memoization. Roughly speaking, dynamic programming is a way of scanning the DAG in reverse topological order, so that whenever we get to an internal node, all of its children have already been explored.


Use the pumping lemma to prove that {www} is not context-free Use the pumping lemma to prove that the following language is not context-free.

$\qquad L = \{ w w w \mid w \in \{a,b\}^*\}$

I am studying for an exam and really trying to understand this question. For some reason the third w is throwing me off.

I first tried using the string $a^p b^p a^p b^p a^p b^p$ but didn't get very far.

The other string I tried to work through it with was $a^p b^p b^p$

Having a hard time figuring out how exactly to split it up.

Any guidance and explanation would be greatly appreciated.

You could take $w = a^m b a^m$, then you have that $uvxyz = a^m b a^m a^m b a^m a^m b a^m$
$vy = a^l$ with $1\le l\le m$ since there can't be more than one $b$, so you can't pump the $b$.
Since $vy$ can only contain $a^m$ without any $b$'s, it will obstruct the balance between the other $a^m$'s.
We've found a contradiction while applying the pumping lemma so the language is not Context-Free.


Show that $A_\mathrm{LBA}$ is PSPACE-Complete? I want to show that $A_\mathrm{LBA}$ is PSPACE-Compelte.

Say we proved it is in PSPACE. Now for PSPACE-HARD:

I had an idea, which was very similar to some solution i found on the web- say we have a TM M which decides some language A in PSPACE. Then given an x in A we can simulate M on x to determine the number of steps M makes.

Suppose the above simulation is defined as another TM M' and k steps are needed for M to run x.

Build a TM M'' which simulates M on "x, $space^{\mathrm{k}}$" - the word x concatenated with k spaces. return (M'', "x, $space^{\mathrm{k}}$")

What i don't understand - the input is only x and its length is |x| so how do we know that simulating M on x is poly-time(x) ? we don't know the size of the description of M, which must be fed to the single-tape LBA M''.

How come all the solutions i've encountered don't even mention that the size of the description of M might not be poly-time(x) ? then we have that the mere writing of M on M''s tape might be more than poly-time(x). (?)

No relation is given between |x| and |M| (the decider for A) because the input is only the word x...

As I understand, you are asking two questions. Let me address them separately:

You don't. Your assumption on $M$ did not require anything more than $L(M) = A$, which is too weak for such a proof. You need to use $A \in \textbf{PSPACE}$ and require the existence of a polynomial $p:  \mathbb{N} \to \mathbb{N}$ such that $M$ uses at most space $p(n)$ for any input of length $n$.Incidentally, you also need this to know what $k$ should be. In your proof, you give no explicit way of computing $k$ other than simulating $M'$, but you do not state why this could ever be done in poly-time. (In fact, this could only ever work for arbitrary $M$ if $\textbf{P} = \textbf{PSPACE}$.)
The description of $M$ remains constant as the length of the input $x$ increases, so it is negligible, asymptotically speaking.

The real issue

It appears your approach is based on fixing $A$ and $x$ and then constructing an LBA $M''$ to simulate $M$ on $x$. This is not how reductions work. $A$ and $M$ should be fixed, but you need to keep $x$ arbitrary, otherwise the proof is quite incorrect (since the result of running $M$ on $x$ could be simply hardcoded into a TM which produces the result immediately upon reading $x$ as input; this proves absolutely nothing).


What is the set of all maximal 3CNF formulas? Definition: A maximal 3CNF formula is satisfiable 3CNF formula, but if you conjuct it with another any new different 3 disjuctive literals clause, then the formula becomes unsatisfiable.

Please don't confuse with the definition of minimal 3CNF formula from my previous question What is the set of all minimal 3CNF formulas

This is not the same thing!

But my question about minimal 3CNF formulas in the above link is same for maximal 3CNF formulas here, i.e.

For some natural number n, where n is the number of atomic variables, what is the set of all maximal 3CNF formulas? Is it finite? If it is then what is it's cardinality, i.e. how many different maximal 3CNF formulas is possible?

Note that for k-cnf formula n≥k, so in 3CNF formula n≥3.

There are $2^n$ maximal 3CNFs; here I am assuming that each 3-clause contains at most three different literals (corresponding to different variables), and that the clauses are different and unordered (both within each clause, and across the formula). Indeed, I show below that if $\varphi$ is a maximal 3CNF then there is a truth assignment $\alpha$ such that $\varphi$ consists of all 3-clauses consistent with $\varphi$, and conversely, each such formula is maximal.

Indeed, let $\varphi$ be a maximal 3CNF. Suppose first that $\varphi$ has at least two different truth assignments $\alpha,\beta$. There is a variable $x_i$ whose truth value is different in $\alpha$ and $\beta$, say $x_i$ is true in $\alpha$ but false in $\beta$. In particular, the clause $x_i$ is not in $\varphi$ (since $\beta$ doesn't satisfy it), and if we add it then the formula remains satisfiable. We conclude that $\varphi$ has a unique satisfying assignment $\alpha$. If $\varphi$ doesn't contain all 3-clauses consistent with $\alpha$ then we can add the missing ones while keeping the formula satisfiable. Thus $\varphi$ must consist of all 3-clauses consistent with $\alpha$.

Conversely, suppose that $\varphi$ consists of all 3-clauses consistent with $\alpha$. Since $\varphi$ contains all clauses of width 1, $\alpha$ is the unique satisfying assignment. By definition, any other 3-clause is inconsistent with $\alpha$, and so $\varphi$ is maximal.

You might be interested in E3CNFs, in which each 3-clause contain exactly three literals, each corresponding to a different variables. These can probably be analyzed using the same approach - if you're interested, you're welcome to work it through.


Proving an algorithm exists to find independent set from a graph given an oracle This is the problem that I have been given:

Consider the Independent-Set problem, in which the input is an undirected graph $G = (V,E)$ and a
parameter $k$, and the goal is to determine if $G$ has an independent set of size $k$. Suppose we have an
oracle $O$ for solving this decision version of independent set (think of it as a library function that takes
input a graph $G$ and $k$ and answers YES/NO).
Prove that there exists an algorithm that can find an independent set of size $k$, if one exists, using a
polynomial number of calls to the oracle $O$, and possibly a polynomial amount of computation of its
own.

My first question is: Is there any way to prove that an algorithm exists without just giving a specific algorithm?

I'm sort of taking a crash course in computer science, so this is not my strongest subject. Any hints as to what direction to take this would be appreciated!

If the problem has the property that the decision version can be converted to the search version, it is self reducibility. You can show that all NP-complete problems are self reducible. The idea is to build the instance with the prefix of the verifier for NP-complete problem, and solve it based on the decision version. This is kinda well-known several lines proof.

I am not aware of any other methods to show the fact you asked for.


Oracle for an inverse function A. Let $F$ be a monotonically increasing real function from $[0,1]$ onto $[0,1]$. Given an oracle to $F$ and a number $y$, is there a way to calculate the inverse function $F^{-1}(y)$ in a finite number of calls to the oracle?

I think the answer is no, because of a simple counting argument: there are uncountably many possible answers, and with a finite number of calls we can get only countably many answers. Is this correct?

B. Let $F, G$ be two functions as above, and let $H$ be their average: $H(x)=[F(x)+G(x)]/2$. Given an oracle to $F^{-1}$ and an oracle to $G^{-1}$ and a number $y$, is there a way to calculate $H^{-1}(y)$ in a finite number of calls?

I think the answer is no, but how can I formalize the counting argument?

Is this possible to reduce to this problem from problem A? Or from another problem which provably cannot be solved in finite time?

NOTE: It can be argued that any function on reals is inherently infinite because even the output of a real number might take infinite time. So for this question, assume that we have a computer that can input, output and do arithmetics on real numbers in constant time per operation.

similar question was posted in math.SE, no answers yet.

I am skipping the first question, question A, as it is not clear to me
how it can make sense formally, since I am not familiar with the
formalizations the OP mentions in a comment: Are there established complexity classes with real numbers?

I am only adressing the relation between question A and question B,
proving that question B can be reduced to question A, which the OP considers of interest in itself. And since we are supposed to deal with only one question at a time, this follows the local rules. :)

Question B reduces to question A : B ≤ A

First I will rephrase both questions, so as to add a missing
hypothesis (bijectivity of the function, though existence of an
inverse implies it), and also to use notations that will make the proof
easier to state.

Question A: Let $F$ be a bijective, monotonically increasing real
function from $[0,1]$ onto $[0,1]$. Given an oracle to compute $F$ on
any input and a number $y\in[0,1]$, is there a way to calculate the
inverse function $F^{-1}(y)$ in a finite number of calls to the $F$
oracle?

Question B: Let $H, K$ be two functions like $F$ above, and let $G$ be
their average: $G(x)=[H(x)+K(x)]/2$. Given an oracle to compute
$H^{-1}$ and an oracle to compute $K^{-1}$ and a number $y\in[0,1]$,
is there a way to calculate $G^{-1}(y)$ in a finite number of calls to
the $H$ and $K$ oracles.?

Note: all functions considered are bijective monotonic, but for
readability we leave implicit the related arguments, though they do matter in some of the inferences below.

The idea of the proof is that, if $x=G^{-1}(y)$ is a solution to
problem B, then there are two numbers $h,k\in[0,1]$ such that

$y=(h+k)/2$, and
$h=H(x)$, and $k=K(x)$ for some $x\in [0,1]$

We try to resolve the problem by defining a variable $u\in[0,1]$, so
that $h$ and $k$ are computed from $u$ to take all possible values
while $u$ varies from $0$ to $1$.

From $y=(h+k)/2$ we get $h+k=2y$. So we define: $h_u=2yu$ and
$k_u=2y(1-u)$.
This ensures that $y=(h_u+k_u)/2$, but will let $h_u$ or $k_u$ become greater than $1$ when $y$ is greater than $1/2$.

So, we must actually consider two somewhat similar cases, depending on the value of $y$, after noting that $h_u$ and $k_u$ are both monotonically increasing functions of $u$.

case 1: $y\leq 1/2$

What we want is to find $h$ and $k$ such that $h=H(x)$ and $k=K(x)$
for some value $x$.

We define the function
$D(u)=H^{-1}(h_u)-K^{-1}(k_u)=H^{-1}(2yu)-K^{-1}(2y(1-u))$
Note that $H^{-1}(0)=K^{-1}(0)=0$.
Hence $D(0)=H^{-1}(0)-K^{-1}(2y)=-K^{-1}(2y)$,
and $D(1)=H^{-1}(2y)-K^{-1}(0)=H^{-1}(2y)$.

So the function $D(u)$ is increasing onto $[-K^{-1}(2y),H^{-1}(2y)]$,
and the solution to finding the value of $u$ that corresponds to the
right values of $h$ and $k$ is given by the equation $D(u)=0$.

However, we intend to resolve it using an algorithm to solve
question A, so we must normalize the interval to make it $[0,1]$.

For that we define
$F(u)=\frac{D(u)+K^{-1}(2y)}{H^{-1}(2y)+K^{-1}(2y)}$
The function $F$ satisfies the conditions of question A,
and we remark that $D(u)=0$ iff
$F(u)=\frac{K^{-1}(2y)}{H^{-1}(2y)+K^{-1}(2y)}$.
So we have to compute
$u_0=F^{-1}(\frac{K^{-1}(2y)}{H^{-1}(2y)+K^{-1}(2y)})$, which can be
done using the algorithm answering question A.
Then $G^{-1}(y)=H^{-1}(2yu_0)$, or to summarize in one formula:

$$G^{-1}(y)=H^{-1}(2yF^{-1}(\frac{K^{-1}(2y)}{H^{-1}(2y)+K^{-1}(2y)}))$$

Each computation of $F(u)$ uses only a finite (small) number of calls to the
oracles for $H^{-1}$ and $K^{-1}$. Thus a solution to question B can
be computed with a finite number of oracle calls if that is the case
for problem A.

case 2: $y>1/2$

This case is a bit more complicated, as different bounds must be found
for varying $u$ so that $h$ and $k$ do not get greater than $1$, since
the functions $H$ and $K$ are defined only onto $[0,1]$.

Since $y=(h_u+k_u)/2$, we have $h_u=2y-k_u$. Thus, $k_u\leq 1$ implies
$h_u\geq 2y-1$.

The same reasonning holds, exchanging $h$ and $k$, so that we have
$h_u,k_u\in [2y-1, 1]$. Since $u=h_u/(2y)$, we have $u\in[u_0,u_1]$
with $u_0=1-1/(2y)$ and $u_1=1/(2y)$.

In order to have a variable $v$ varying in $[0,1]$, we normalize by
defining $v=(u-u_0)/(u_1-u_0)$. But
$u_1-u_0=1/(2y)-(1-1/(2y))=(1-y)/y$
which gives $v=(u-u_0)y/(1-y)$.
Hence, with $u=v(1-y)/y+u_0$, $u$ is
a function of $v$ monotonically increasing onto $[u_0,u_1]$ when
$v\in[0,1]$.

Thus, considering $h$ and $k$ as functions of $v$ we have
$h_v=2y(v(1-y)/y+u_0)$ and $k_v=2y(1-(v(1-y)/y+u_0))$, with $u_0=1-1/(2y)$

Simplifying we get $h_v=2y-1+2v(1-y)$ and $k_v=1-2v(1-y)$, for $v\in[0,1]$

From here on the reasonning is the same as for the first case, since monotonically increasing functions are closed under composition, the variable being $v$ rather than $u$, considering the function:
$D(v)=H^{-1}(h_v)-K^{-1}(k_v)=H^{-1}(2y-1+2v(1-y))-K^{-1}(1-2v(1-y))$

I hope that there is no error in symbol manipulations, but the line of reasonning should not be affected if that were the case.

The proof can be simplified by using a lemma that generalizes the question A, which is here a hypothesis, to any strictly increasing function from any closed interval to any other closed interval.


On the definition of Error-Correcting Codes Let us start with the following well-known definition:

Definition 1. Let $C\subseteq A^n$ be a code over $A$ and let $t\in \Bbb Z^+$ be a positive integer.  We say that the code $C$ is
$\boldsymbol t$-error correcting if nearest neighbour decoding is
able to correct at most $t$ errors, assuming that if a tie occurs in
the decoding process, a decoding error is reported. That is, if
whenever $x \in C$ and $y\in A^n$ such that $\mathrm{d}(x,y)\leq t$, then $y$ is decoded to $x$
using nearest neighbour decoding.

Now let us make an observation.

Remark.  Recall that when there is no unique nearest codeword to $x\in C$, then
nearest neighbour decoding fails. So, a code $C\subseteq A^n$ is $t$-error correcting if and only if
whenever $y\in A^n$ is a word within distance $t$ of a codeword $x\in
  C$ (that is, $\mathrm{d}(x,y)\leq t$), then $$\mathrm{d}(x,y) <
  \mathrm{d}(z,y), \quad \text{for all } x\neq z \in C.$$

The Remark gives us a more abstract way to state the definition of $t$-error correcting without  mentioning nearest neighbour decoding.
However, I stumbled on another statement of the definition (which I found on some lecture notes on the web):

Definition 2. The code $C$ is $t$-error correcting if there do not exist $x,z \in C$ such that $x\neq z$ and $y\in A^n$ such that
$$\mathrm d(x, y)\leq t, \quad \mathrm d (z, y)\leq t.$$

My question is why the last definition is equivalent to the first one (given with the form of the remark).
Could you please give me a hand?

UPDATE: My attempt: Definition 1 tells us that
$$(\forall x\in C)(\forall z \in C)(\forall y\in A^n)(d(x,y)\leq t)(z\neq x \implies d(x,y)<d(z,y)).$$
Definition 2 tells us that
$$(\forall x\in C)(\forall z \in C)(\forall y\in A^n)(d(x,y)\leq t)(d(z,y)\leq t \implies z=x).$$
Equivalently,
$$(\forall x\in C)(\forall z \in C)(\forall y\in A^n)(d(x,y)\leq t)(z\neq x\implies d(z,y)>t ).$$
Equivalently,
$$(\forall x\in C)(\forall z \in C)(\forall y\in A^n)(d(x,y)\leq t)(z\neq x\implies d(z,y)>t\geq d(x,y)).$$
So the Def2 $\implies$ Def 1. Is that correct? How about $\Longleftarrow$?

Here is what the remark says:

A code $C \subseteq A^n$ is $t$-error-correcting if for all $x \in C$ and $y \in A^n$ such that $d(x,y) \leq t$, all $z \in C$ other than $x$ satisfy $d(x,y) < d(z,y)$.

When is a code not $t$-error-correcting according to this remark?

A code $C \subseteq A^n$ is not $t$-error-correcting if there exist $x,z \in C$ and $y \in A^n$ such that $x \neq z$ and $d(z,y) \leq d(x,y) \leq t$.

Given $x,y,z$, either $d(z,y) \leq d(x,y)$ or $d(x,y) \leq d(z,y)$, and so, since the other constraints on $x,z$ are symmetric in $x,z$, the above definition is equivalent to

A code $C \subseteq A^n$ is not $t$-error-correcting if there exist $x,z \in C$ and $y \in A^n$ such that $x \neq z$ and $d(x,y),d(z,y) \leq t$.

This is exactly Definition 2.


Formal Language Syntax Here is the question:

Show that $L = \{0^m1^n : m > 1, n > 1, n < m \}$ is not regular.

I am not sure what superscripts mean in this situation? Does it mean something like this:

$0^5 = 00000$ or $1^7 = 1111111$.

Yes, 0^n or $0^n$ denotes the string obtained by concatenating $n$ copies of the symbol $0$.


Big Omega of $n \log n$ While studying master method at recurrences topic I'm stacked at a point. It is written in the book as:

  $T(n) = 3T(n/4) + n \log n$,

  we have $a = 3, b = 4$,

  $f(n) = n \log n$, and

  $n^{\log_b(a)} = n^{\log_4 3} = O(n^{0.793})$.

  Since  $f(n) = \Omega(n^{\log_4( 3)+\varepsilon} )$, where  $\varepsilon \approx0.2$ ....

The authors means that the $n\log n = \Omega(n)$. How will we know this? Is $n \log n = \Omega(n)$ true? Or
something is wrong?

Yes, $ n\log n = \Omega(n) $ is true.

To see why, note that for this to be true, we have to show that $ n\log n \ge cn$ for all $n \gt n_0 $ and $ \exists c \gt 1 $. If we take $ c = 1 $ then, we get $n\log n \ge n$ for all $n \ge 2$. This shows that $ n\log n = \Omega(n) $ is true.


Finding path with minimum weight There is a river which can be considered as an infinitely long straight line with width W.

There are A piles on the river, and B types of wooden disks are available.
The location of the $i$-th pile is $(X_i, Y_i)$.

The $i$-th type of wooden disks has radius $R_i$, and its price is $C_i$ per disk.

Disks can be placed on the river such that for each wooden disk, its center must be one of the locations $(X_i, Y_i)$ of piles. We can only move on the wooden disks.

How to find the minimum cost such that we can cross the river.I am unable to approach questions like these. What would be the best method to approach this one?

I have come to realize that we can use Dijkstra's algorithm here. We treat this as a graph, with piles as the nodes. Start point can be $y=0$. and $y=W$ as the end point. But i am having implementation problems. There are multiple disks which can be used in going from on state to another. How to handle this?

I'm sure someone will manage to come up with a more efficient idea, but here's a basic one:

Have both sides of the river be nodes in the graph. Define the disk used for these nodes as having 0 cost and 0 radius.
Split each pile into B nodes in the graph, one for each type of disk.
Connect each pair of nodes where the sum of the radius of the 2 disks of these nodes is less than or equal to the distance between the nodes.
Define the cost of an edge as the cost of the disk of the destination node. The cost of the source node will already have been included in the previous step.
Note that this should be dynamically calculated - one can approach an edge from either side, thus it can take on the value of either node, thus could have different costs at different times.
Run Dijkstra's algorithm as per usual from the source side of the river.

One can get a more efficient but more complex algorithm by only having a single node for each pile and storing the radius of the chosen disk at each point.

Note that any disk type A with cost cA and radius rA can be discarded if there exists a disk type B with radius rB >= rA and cost cB <= cA, or, equivalently, if there's a bigger and cheaper disk type, since it would always be more efficient to use that one instead.


Graph isomorphism and the automorphism group A common approach to decide whether two given graphs are isomorphic is to compute the so-called canonical label (alternatively, canonical graph) of each graph and to check whether those match or not.

Tools such as Nauty compute the canonical graph via search trees that are pruned using some clever ideas that rely, among other, on graph automorphisms. Because of this, Nauty allows one to compute a generator of the graph automorphism group. However, as far as I understood the idea behind Nauty, the computation of the canonical graph does not require one to compute a generator of the graph automorphism group in general.

My question is therefore: is there a formal complexity-theoretical relation between GI and the computation of a generator set of the graph automorphism group?

Many thanks.

As the comments suggest there can be confusion over what you call "GI". But  the idea here is correct.  It is polynomial-time equivalent to find generators of an automorphism group as it is to find an isomorphism between two groups.  The idea is "classical" in that it appears in early work such as Luks' Group Isomorphism in bounded valence is in polynomial-time, and even there I think the idea was considered "well-known".

Claim. Let $G$ and $H$ be connected graphs.  Then $G\cong H$ if, and only if, every generating set $S$ of $\mathrm{Aut}(G\sqcup H)$ contains an element $g\in S$ such that $G^g=H$.

Remark Important here is that every generating set exchange the graphs as otherwise you would sometimes compute generators that don't solve the problem.  So for example, isomorphism of two groups does not so easily yield in this way.  That is because not all generating sets of $\mathrm{Aut}(G\times H)$ will interchange $G$ and $H$ when $G\cong H$.  instead they can go to diagonal copies.  That situation can be fixed, but it requires a stronger argument.  So the approach here is not one that applies in all categories.

Proof.  For the converse if every (or even if one) generating set of $\mathrm{Aut}(G\sqcup H)$ interchanges $G$ and $H$ then $G\cong H$ by the restriction of that function to $G$.  So this is all about the forward direction.  (But I mention this because the proof is by contrapositive so it can look like I'm about to go the same direction.)

Suppose $\mathrm{Aut}(G\sqcup H)$ is generated by a set $S$ all of whose elements send $G$ to $G$, and $H$ to $H$, (note by connectivity assumption if one vertex of $G$ is sent to one vertex of $H$ then the entire graph $G$ is sent to $H$ and so by pigeon hole some vertex in $H$ will be sent to $G$ and so $|G|=|H|$ and we will have interchanged the two graphs).  Since $S$ sends $G$ to $G$, then every composition of functions in $S$ sends $G$ to $G$, and so do inverses of these functions.  So every word in $S$ sends $G$ to $G$ (and also $H$ to $H$).  So no element of $\mathrm{Aut}(G\sqcup H)$ interchanges $G$ and $H$.

Finally if $G\cong H$ then an isomorphism $\phi:G\to H$ affords an automorphism $\phi\sqcup \phi^{-1}$ of $G\sqcup H$.  So the absence of elements in $\mathrm{Aut}(G\sqcup H)$ to interchange $G$ and $H$ implies $G\not\cong H$.  The result follows. $\Box$

But now the point to be clear on is that going from decision (Is $G\cong H$?) to search (Give me $\phi:G\to H$ or a certificate that $G\not\cong H$) has still to be argued (and can be).  Also from one isomorphism to generators of automorphisms is another argument (individualize the graphs and repeat the isomorphism test).  So all told you have a couple pages of argument to make these equivalences.  None will show canonical labeling though.  That is much harder (NP-hard if I recall).  Even though NAutY and Traces handle many examples quickly.


What is the simplest known NP-Complete problem for testing P=NP solutions? About a year and a half ago I asked this question regarding $\mathsf{P}=\mathsf{NP}$.  The answers have helped me understand the problem tremendously and since then I've dabbled further into the topic.

With that stated, it is my understanding that $\mathsf{NP}$-complete problems are such that if a solution for $\mathsf{P}=\mathsf{NP}$ were found for that specific problem, then all $\mathsf{NP}$ problems could be solved using the same rules for resolving $\mathsf{NP}$.

With that stated, what is the simplest $\mathsf{P}=\mathsf{NP}$ problem outlined to date that is $\mathsf{NP}$-complete?

In other words, what is the most basic of problems that one could test a theoretical $\mathsf{P}=\mathsf{NP}$ solution against?  I'm aware of many of the examples such as the Traveling Salesman or Knapsack problems but I assume there could be even simpler scenarios where all properties of the $\mathsf{P}=\mathsf{NP}$ or $\mathsf{P}\ne\mathsf{NP}$ dilemma are present.

Since all NP-complete problems are basically equivalent, it's hard to say which one is the easiest. SAT was one of the original problems and has important practical applications, so it is really well studied. Writing fast SAT-solvers seems like a reasonably interesting hobby to me and getting started is not terribly hard. Integer Linear Programming is similarly important and well studied.

The only objective way to discern NP-complete problems that I know of is their approximability. Some problems are hard to approximate, for others you can get almost arbitrarily good solutions in polynomial time.

Subset sum is both very simple to understand and "simple" to solve. Simple to solve means that it has an easy Pseudo-polynomial algorithm and is easy to approximate. However, I don't know about any research involving the problem.


Complexity of finding 7th smallest element in a min-heap? I don't know if it's allowed to traverse nodes in a min-heap.

Because, if traversal is allowed then for finding $7^{th}$ smallest element, only a constant number of nodes need to be checked, thus giving the complexity of $\Theta(1)$.

But if traversing is not allowed, then for finding $7^{th}$ smallest element, I'll need to call extract_min() 6 times, leading to a complexity of $\Theta(\log n)$, which I think should be correct, but not sure.

My understanding is, if I'm traversing, then it's not a min-heap, it will be an augmented min-heap. Is it correct?

If you had a "black-box" min heap where the only operations available to you are adding elements and extracting (reading and simultaneously removing) the smallest item, then the time complexity is O (n) obviously.

It is imaginable that you have a specific implementation where even finding the second smallest element cannot be done in constant time. You might have in your data structure O (log n) items that might be the second smallest, and the O (log n) operation to remove the smallest item will also determine the second largest. I find it hard to describe an algorithm that works that way, but I'm sure it's possible.

The way a min-heap is usually implemented (or the way it is implemented if I had to implement it, or the way it is implemented in a random text book), finding the 7th smallest element can be done in constant time.


List of algorithm problems in term of ideals I am new in algorithm and studied about some problems in algorithm related to graph theory. These problems we can transform to some polynomials and if for each set of polynomials related to a problem we have a solution then it means the problem has a question. For example we can transform the problem of MAx-Clique to the following set of polynomials

$P=\{x_i^2-x_i, x\in [n]\}\cup \{x_ix_j, (i,j)\notin E\}$

I want to know there is any list of problems like this? If you know any paper or book such that there lots of problems like the above one which can transform it to set of polynomials please let me know and have it.

We all know that 3SAT is NP-complete. Here is how to reduce 3SAT to your problem.

Suppose that the 3SAT instance has variables $x_1,\ldots,x_n$ and clauses $C_1,\ldots,C_m$. The new instance will have variables $x_1,\ldots,x_n,y_1,\ldots,y_m,z_1,\ldots,z_m$, and the following polynomials:

$x_i^2 - x_i$ for each $i \in [n]$ and $y_j^2 - y_j, z_j^2 - z_j$ for each $j \in [m]$.
For a clause $C_\ell$ of the form $x_i \lor x_j \lor x_k$: $x_i + x_j + x_k - y_\ell - z_\ell - 1$.
If a clause has negated variables, say $x_i$ appears as $\overline{x_i}$, then replace $x_i$ with $1-x_i$ in the polynomial stated above.

Why does this work, the first type of polynomials constrain all variables to be $0,1$. The polynomial $x_i + x_j + x_k - y_\ell - z_\ell - 1$ states that $x_i + x_j + x_k = 1 + y_\ell + z_\ell$, and since $y_\ell,z_\ell$ occur only in this polynomial, this is the same as $1 \leq x_i + x_j + x_k \leq 3$, that is, $x_i + x_j + x_k \geq 1$, or equivalently, $x_i \lor x_j \lor x_k$.


Consensus anomaly about read-write registers and test&set I read this answer below and got into another question.

Why is the consensus number for test-and-set, 2?

I also read that read/write registers have consensus number 1.

But I see that in test&set (also in compare&swap) by using read write registers alone, we still arrive at consensus.

I think I am missing something very fundamental here. Need help.

The protocol in the accepted answer of the link is as mentioned below

  Suppose that we have two threads 0 and 1 that need to reach consensus.
  We could do this by letting each thread follow the consensus protocol
  below:

  Write your proposed value to A[t], where t is the thread id and A is an array of size 2
  Perform the test-and-set instruction on some register R, with R initialised to 0.
  If the return value is 0, you were first: return A[t]. Otherwise, you were second: return A[|t−1|].

Consensus number and consensus hierarchy are defined in the classic paper "Wait-Free Synchronization" by Maurice Herlihy, 1991.

Note the keyword: wait-free.

Since you did not give the algorithms for test&set using read/write registers only, I guess that they are not wait-free. (They may be lock-free instead.)

Added:

After the discussions with the OP in the comments, I realize that the OP has not fully understood the difference between atomic test&set registers and atomic read/write registers. He/she thought that the protocol given in the post uses read/write registers only. In fact, it uses test&set registers/operations/instructions in the second step.

A test&set register supports the test&set operation, which is a combination of test and set that cannot be interrupted. See this wiki for more details.


Explanation of Tag, Index, and Offset in Direct Mapping Cache I'm going through an exercise trying to store address references into a direct mapped cache with 128 blocks and a block size of 32 bytes.  The address are 20000, 20004, 20008, and 20016 in base 10.

When I start to store them, I realize that the offset is the only value that changes.  All of the examples I find determine hits and misses based on the target and index values, without mention of offset.  What is the purpose of the offset?  If the tag and index are in the cache, is it a hit regardless of the offset? Or is the offset also looked at?

If the cache blocks are not sectored, then if the tag field matches any offset within the block will be a hit. With sectoring a cache block can have multiple valid bits, in which case the tag might match but the valid bit for the section corresponding to the offset might be cleared (indicating that the section is invalid).

In theory a valid bit could be provided for every smallest unit of access (commonly an 8-bit byte), but sectoring is more commonly used to allow an outer level of cache to use a larger block size than L1 caches without forcing all the data associated with a tag to be invalidated when the smaller unit needs to be. For an inclusive cache, this avoids unnecessary back-invalidation of L1 cache. (It would also be possible to include fully independent coherence state, e.g., MESI, rather than just validity. This could be used to avoid unnecessary writebacks, e.g.)

Sectoring can also be used to directly fill the cache and allow early restart; alternatives include using a side (fill) buffer with extra valid bits (similar to a write buffer) and waiting for the entire cache block is loaded before restarting execution.

To confuse matters, Intel uses cache line to indicate the smaller unit that shares a tag with other lines in a sector while some others use cache block/line for the larger unit with the term sector used for the portion that can be individually invalidated.

For the level of complexity for this type of exercise, one can reasonably assume that sectoring is not used, so a tag match would indicate a hit regardless of the offset.


Prove $\epsilon(S\cap T)\subseteq S \cap T$ Suppose there are sets $S\subseteq Q, T\subseteq Q$ such that $T=\epsilon (T),S=\epsilon (S)$.

  Prove $\epsilon(S\cap T)\subseteq S \cap T$

Definition of $\epsilon$- closure for epsilon NFA is:

  $\epsilon : 2^Q \rightarrow 2^Q $

  a) $S \subseteq \epsilon (S)$ Base case

  b) If $q \in \epsilon (S)$ then $\delta(q,\epsilon )\subseteq \epsilon (S)$ Recursive case

  c) and nothing else is in $\epsilon (S)$

  And also, S is a set of all states in epsilon-NFA.

My proof:

Is this a correct reasoning?

Since your definition of $\epsilon$-closure isn't really a definition, it is impossible to prove anything using it. Instead, let me use the following definition: the $\epsilon$-closure of a set $S \subseteq Q$ consists of all states $x \in Q$ which are reachable from a state in $S$ by a (possibly empty) $\epsilon$-path (which is a path consisting of $\epsilon$-transitions).

Suppose that $\epsilon(S) = S$ and $\epsilon(T) = T$, and let $q \in \epsilon(S \cap T)$. Thus $q$ is reachable by a state $r \in S \cap T$ via an $\epsilon$-path. Since $r \in S \cap T$, in particular $r \in S$, and so, by definition, $q \in \epsilon(S) = S$. Similarly, $q \in \epsilon(T) = T$. Therefore $q \in S \cap T$.


Can we make a problem harder than NP and coNP if they are not equal? Let us assume that $\mathsf{NP} \neq \mathsf{coNP}$. Consider the graph 3-colorability problem.

Since $\mathsf{NP} \neq \mathsf{coNP}$ implies $\mathsf{P} \neq \mathsf{NP}$ and 3-coloribility is $\mathsf{NP}$-complete and its complement is $\mathsf{coNP}$-complete , we have:

3-coloribility is not in $\mathsf{P}$, i.e. there are no polynomial-time algorithm for deciding if a given graph is 3-colorable.
non-3-coloribility is not in $\mathsf{NP}$, i.e. there are no polynomial-time verifier with polynomial-size certificatesfor non-3-colorability.

However, we know that for many classes of graphs, polynomial algorithms exists for 3-colorability and also they have polynomial-time verifiers with polynomial-size certificates for non-3-colorability. But this is not the case for all graphs since we we assumed that  $\mathsf{NP} \neq \mathsf{coNP}$.

We can define the following problem:

  Input: a graph $G$,
  Task: determine if $G$ is 3-colorable or non-3-colorable and provide a certificate for the answer. The certificate is either a 3-coloring or a non-3-colorability certificate.

What is the complexity of this problem?

YES version is in $\mathsf{NP}$ . And the NO version is in $\mathsf{coNP}$. Note that the answer is not always YES since $\mathsf{NP} \neq \mathsf{coNP}$.

Note: this answer was posted for the original post.

  Given a graph G: is there an algorithm, bounded by a polynomial of order k, that can determine if G is 3-colorable-or-non-3-colorable and provide a certificate?

If you fix the graph then the problem is trivial. There is always an algorithm that answers in constant time. There is no input.

If the graph is the input, then the answer is always YES. Any graph is either 3-colorable or not 3-colorable.

  Note that the answer is not alway yes since NP ≠ Co-NP

I don't see how this is relevant.


determine Eulerian or Hamiltonian I am a beginner in graph theory and just found this question in a book after completing few topics and I was wondering how you approach this questions.
For eulerian, I can say that the graph has vertex with odd degree hence not eulerian, but how can I determine if they are hamiltonian or not?

That's a very good question, and the easy answer is that checking whether a graph is Eulerian is much simpler than checking whether a graph is Hamiltonian.  You're diving head-first into the field of complexity theory and the famous question P vs NP.  (Further reading: What is the definition of P, NP, NP-complete and NP-hard.)
As you said, a graph is Eulerian if and only if the vertices have even degrees.
For checking if a graph is Hamiltonian, I could give you a "certificate" (or "witness") if it indeed was Hamiltonian.  However, there is no anti-certificate, or a certificate for showing that the graph is non-Hamiltonian;  Checking if a graph is not Hamiltonian is a co-NP-complete problem.
In fact, we believe that any certificate for non-Hamiltonian-ness needs to be exponentially large.

To answer the question:

Try every permutation of vertices, and if one of the permutations is a cycle, then the graph is Hamiltonian.  If so, you get a certificate.
If no permutation was a cycle, the graph is not Hamiltonian.  You cannot convince your friends that the graph is non-Hamiltonian without trying all permutations*.

(Ps, using algorithmic techniques (DP) you don't have to try every permutation, but still exponentially many.)


Context free grammer for $L = \{a^i b^j a^n b^m \mid i + j = n + m\}$ Find a CFG for the following language:

$$L = \{a^i b^j a^n b^m \mid i + j = n + m\}$$

I'm not sure how I can do that context free. I know that I have to borrow one char from the left group for each char from the right group. but not sure how.

The idea is to use non-terminals $X_{\alpha\beta}$, where $\alpha,\beta \in \{a,b\}$, that support the production $X_{\alpha\beta} \to \alpha X_{\alpha\beta} \beta$. You have to combine them somehow so that you obtain the language $L$, but I'll leave the details to you.


Countability of a binary tree Problem:

  We'll define a binary tree as a tree where the degree of every internal node is exactly 3. Show that the set of all binary trees is countable.

My attempt:

A set is countable if it is finite or there is a one-to-one correspondence with the natural numbers. So we need to show that a strategy for an enumeration exists. I'm not sure exactly how detailed I'm supposed to be here, but I just tried to give a general way in which one could enumerate the set of binary trees as defined above...

Assign the first k_0 positive integers for each binary tree with height 0, then assign the next positive integers for each binary tree having height 1, and so on. The set of all binary trees can be enumerated this way and is thus countable.

Is the above the right way to go about this problem? (I'm not sure if I'm supposed to provide a specific function for how many binary trees there are at any given height k.) Thanks.

To show countability we need not alway show one-to-one onto mapping to $\cal N$. We can instead show a one-to-one onto mapping to a subset of $\cal N$.


What is a Turing Machine in class coNP On the wikipedia article about the polynomial hierarchy http://en.wikipedia.org/wiki/Polynomial_hierarchy

it says "$A^B$ is the set of decision problems solvable by a Turing machine in class A augmented by an oracle for some complete problem in class B"

What is a "Turing machine in class A" for classes P, NP, and coNP?

I'm guessing a Turing machine in P is a deterministic Turing machine that can only run for polynomial time in the size of its input

and that a Turing machine in NP is a nondeterministic Turing machine that can only run for polynomial time in the size of its input

But I have no clue what is a Turing machine in class coNP ?

The easiest way (for me) to understand co-NP is as the class of problems where certificates for "No" answers can be quickly verified (i.e. certificates of non-membership).

So if we look at NP as a class of nondeterministic Turing Machines which quickly (in polynomial time) determine that their input satisfies some property $\Pi$, co-NP is the class of nondeterministic Turing Machines that quickly determine that their input does not satisfy $\Pi$ (or equivalently satisfies $\neg\Pi$).


Private IP and public IP What we see on our devices is essentially the private IP given to us by the ISP; thereby, whenever we access the internet, this private IP is first converted to public IP (by ISP through NAT), following which requests are made on the internet. If the assumptions above are right, then how does a website gets my private IP? Do websites/servers interact with me over my public IP or the private IP?

I am a bit confused over this topic as books often say that only private IP goes in the internet (i.e., the one assigned by the ISP) but websites/servers are able to make a log of your private IP. This gets me confused.

A private IP is not necessarily assigned by an ISP. It is actually a much more general concept: Any node (or cluster of nodes) realizing NAT separates two networks, a public and a private one. Most routers in home networks separate your internal network (private) from your ISP's or the wider internet (public). In the case of an ISP, it might be so that the ISP uses NAT to separate its own network of subscribers (private) from the wider internet (public), though not all ISPs have such a policy; actually some ISPs may even provide you with a reserved public IP (i.e., an IP which is accessible from the wider internet and which is statically assigned to you).

A private IP is only valid within its own network. In fact, the values for private IPs are standardized and are not routed in the wider internet. Thus, even if a node (e.g., a webserver) in the internet came to know the IP of your device in its private network—which, up to exploits, is unfeasible because of NAT—, it cannot really do anything with that IP unless it is also part of the device's private network: any packets sent to that IP will be immediately dropped (i.e., not routed) by the next node. Rather, what is logged in webservers and the like is the public IP of the NAT node through which you are accessing it.


How do I see SSL/TLS packet data in clear? Hey all I have a weird question (first time poster so forgive me if this is super newb)...

I am wanting to see the inner workings of a SSL/TLS connection between a client and a server at the packet level (in the clear) in order to learn. Is there a way to do this where I will see all of the traffic including the handshake?

Should I just setup a webserver that uses SSL/TLS and then use ssl strip & tcpdump to grab the packet capture? Will that even work in order to grab the full connection in the clear?

I am not super familiar with the SSL/TLS stack and I would like to do this in order to learn how it works at a lower level.

Sure.  Yes, you can capture the packets and view them.  That'll work.  It's a useful, informative exercise.

You can use Wireshark (or some other packet capture tool) to capture the packets involved in the TLS handshake and view the captured  packets.  It'll show you the raw bytes, and also decode the handshake messages for you.  Wireshark has a nice GUI that might make it easier to use, so I recommend that as your first choice, if you haven't done anything like this before.

I don't see any reason why you'd use SSL strip.


How to count near circular objects in image I have a image similar to below. In that I need to find all red circles and count them.
So, I am thinking to use MATLAB R2011a with Image Processing Toolkit for it. How could I possibly extract them?

A simple approach to start with is to extract just the red channel, do some binary thresholding (e.g., Otsu's method), and then use standard morphology operators to find the blobs. You could try applying a closing operation.  Then, you could apply the watershed transformation or region flooding to identify the blobs where the tomatoes are.

A possibly better approach could be to convert to HSV representation, then generate a binary image as follows: every pixel whose hue matches the hue of a tomato (from some range you manually determine) is colored white, the rest are colored black.  Then you could continue with morphology operators and watershed/region flooding.

How well this will work will depend upon your requirements (e.g., whether you need to deal with occlusion) and on application-specific details (e.g., how constant in color the tomatoes are).

Take a look at the following questions on StackOverflow; they are quite relevant and will be helpful to you:

https://stackoverflow.com/q/11631188/781723
https://stackoverflow.com/q/4063965/781723
https://stackoverflow.com/q/5298884/781723
https://stackoverflow.com/q/4387488/781723
https://stackoverflow.com/q/10480609/781723
https://stackoverflow.com/q/6416117/781723
https://stackoverflow.com/q/10313602/781723
https://stackoverflow.com/q/18972932/781723
https://stackoverflow.com/q/10168686/781723
https://stackoverflow.com/q/8593091/781723
https://stackoverflow.com/q/16100708/781723

and also these resources:

http://blogs.mathworks.com/steve/2006/06/02/cell-segmentation/
http://www.mathworks.com/products/image/examples.html?file=%2Fproducts%2Fdemos%2Fshipping%2Fimages%2Fipexcell.html
https://en.wikipedia.org/wiki/Blob_detection


Does the running-time of this push-relabel algorithm become zero if there are many edges? According to the Wikipedia page on the Push-relabel maximum flow algorithm:

  Subcubic $O(|V||E| \log\frac{|V|^2}{|E|})$ time complexity can be achieved using dynamic trees, although in practice it is less efficient.

What if $|E| = |V|^2$? Don't we then have this?

$$O(|V||E| \log\frac{|V|^2}{|V|^2})$$
$$O(|V||E| \log 1)$$
$$O(|V||E| 0)$$
$$O(0)$$

There's no way this can be right, so what am I misunderstanding?

First of all, we usually assume that there are no self-loops. As a consequence, $|E| \leq |V|(|V| - 1) < |V|^2$.

That aside, there is (probably) a misuse of Landau notation here.

The given bound is (probably) not correct for all (families of) graphs. For instance, if $|E| = 0$ the same arithmetic issue occurs but the algorithm will certainly have non-zero running time.

The authors probably simplified away terms of the order of, say, $\Theta(|V|)$ or $\Theta(|E|)$. They do this because they are asymptotically dominated by the given term -- if all quantities are non-zero. This is a fundamental problem with using Landau notation with more than one variable without being rigorous about it.

So, even if the leading term would become zero (which can certainly happen and be correct!) lower-order terms would be non-zero and lead to useful bounds.

Example

Consider this very simple algorithm:

1 def algo(n, m)
2   x = 0
3   for i = 1 .. n
4     for j = 1 .. m
5       x += 1
6   return x

A standard analysis tells you immediately that the running-time is in $\Theta(nm)$ as that is how often the line x += 1 will be executed. Now, if n or m is zero, does the algorithm have zero running time? No!

A more precise analysis leads to the running-time being

$\qquad c_1 + c_2 n + c_3 m + c_4 nm$

with suitable constants $c_1$ (cost of lines 2 and 6, setup of line 3), $c_2$ (management of line 3, setup of line 4), $c_3$ (management of line 4) and $c_4$ (line 5).

Background

Landau notation only makes sense if the parameters go to infinity in suitable ways. We can not just insert finite values for some parameters and expect it to behave well.

Refer to A general definition of the O-notation for algorithm analysis by Kalle Rutanen et al. for details.


What is the difference between a Neural Network, a Deep Learning System and a Deep Belief Network? What is the difference between a Neural Network, a Deep Learning System and a Deep Belief Network?

As I recall your basic neural network is a 3 layers kinda thing,
and I have had Deep Belief Systems described as being neural networks stacked on top of each other.

I've not til recently heard of a Deep Learning Systems, but i strongly suspect it is a synonym for Deep Belief System. Can anyone confirm this?

Artificial neural networks is a class of algorithms that include a lot of different kinds of algorithms based on graphs, so I won't detail here beyond what you asked because there's too much to say, since there are so many kinds of ANNs.

The first kind of artificial neural networks, the famous McCulloch-Pitts neurons, were linear, meaning that they could only solve linear decision problems (ie, datasets that could be linearly separable by drawing a line). Over time, this linear neural network model became known as the Perceptron or Adaline (depending on how you compute weights update).

Linear neural networks are just composed of a bipartite graph, where the left side nodes are the inputs and the right side nodes the output. Only the weights of the edges between these nodes are learnt (the nodes activation threshold can also be adjusted but this is rarely done).

A big step was taken when shallow neural networks were invented: instead of having only a bipartite graph, we use a 3partite graph: the input "layer", the output "layer", and one "hidden layer" between them. Thank's to the hidden layer, the network can now take non-linear decisions, and solve problems such as the canonical XOR.

Note that the "shallow" term was coined retrospectively when deep neural network (also called n-layers neural networks) were invented. This is to oppose neural networks with only one hidden layer, with deep neural networks with n hidden layers. As you can guess, using more hidden layers allow to decide on more complex datasets since there are more layers to modulate the decision (ie, in other words you're increasing the dimensionality of your decision boundary, which can lead to overfitting).

You may ask: why did no-one try to use multi-layered (deep) neural networks before? In fact, they did, as early as 1975 by Fukushima with the Cognitron and Neocognitron (which is in fact a convolutional neural network, but that's another story). However, the issue was that noone knew how to efficiently learn such networks, the big issue being the regularization. Hinton's AutoEncoders opened the way, and later the Rectified Linear Units of LeCun fixed the issue for good.

What about Deep Beliefs Networks (DBN)? They are just multi-layered semi-restricted Boltzmann machines. So they are a kind of deep neural network, but with a different basic network pattern (ie: the layer, this is the pattern that is repeated): Boltzmann machines are different from other networks in that they are generative, meaning that they are usually used to learn from your data to reproduce it ("generate" it), while usual deep neural networks are used to separate your data (by drawing a "decision boundary").

In other words, DNN are great to classify/predict a value from your dataset, while DBN are great to "repair" a corrupted data (when I say repair, it's not only from corrupted data, it can also be on a perfectly fine data that you just want to fix a little to be more stereotypical as to more easily recognize with another neural network, such as hand-written digits).

In fact, to neatly summarize, you can say that AutoEncoders are a simpler form of Deep Belief Network. Here is an example of a DBN trained to recognize faces but NOT numbers, the numbers are automatically faded away (this is the "fixing" effect of DBN):

So in the end, DBN and DNN are not opposite: they are complementary. For example, you can imagine a system to recognize hand-written characters that will first feed a character's image to a DBN to make it more stereotypical and then feed the stereotyped image to a DNN that will then output which character the image represents.

A last note: Deep Belief Nets are very close to Deep Boltzmann Machines: Deep Boltzmann Machines use layers of Boltzmann Machines (which are bidirectional neural networks, also called recurrent neural networks), while Deep Belief Nets use semi-restricted Boltzmann Machines (semi-restricted means that they are changed to unidirectional, thus it allows to use backpropagation to learn the network which is way more efficient than learning a reccurent network). Both networks are used for the same purpose (regenerating the dataset), but the computational cost is different (Deep Boltzmann Machines are significantly more costly to learn because of its recurrent nature: it is harder to "stabilize" the weights).

Bonus: about Convolutional Neural Networks (CNN), you will find a lot of contradictory and confusing claims, and usually you'll find that they are just deep neural networks. However, it seems the consensus is to use the original definition of Fukushima's Neocognitron: a CNN is a DNN that is forced to extract different features at different hierarchical levels by imposing a convolution before the activation (which a DNN can naturally do, but forcing it by setting a different convolution/activation function on different layers of the network may yield better result, at least that's the bet of CNN):

And finally, for a more rigorous timeline of Artificial Intelligence, see here.


One time pad, get plaintext using ciphers encoded with the same key I'm trying to solve a problem:

I have 11 ciphers encoded with the same key.
My aim is to decode target cipher.

If I do xor C1, C2 (ciphers encoded with the same key) I do get M1 xor M2 (where M1, M2 are plain text messages).

Please say what to do next. I don't understand how to get plain texts from M1 xor M2

UPD: it's a two time pad (i.e. the same key has been use more than one time)

So I've passed coursera Scala course and deciced to apply my fresh knowledge.
Here is my algo:

Xor ciphers with each other and collect xor result for each position.
As a result I got a Map[Int, List[String]] where Int is a position of char in chiper and List[String] are all xor results for current position.
I have an assumption that if xor in List[String] equals to UPPER ASCII alpha, it means that  source of this computation was: *space xor lower_alpha = UPPER_alpha*.
I can try to guess key value: c1 (char from 1st cipher), c2(char from 2nd cipher), xorRes (c1 xor c2 = xorRes) => c2 xor(c1 xor xorRes) or c1 xor(c2 xor xorRes) = *lower_alpha*.

Here is a part of code:

  /**
   * hex1 is a hex from 1st cipher
   * hex2 is a hex from second cipher
   * xor is ahex1 xor hex2
   * @return List with pos of possible key and possible key value else return empty list
   * */
  def getPossibleKey(hex1: String, hex2: String, xor: String, pos: Int): List[(Int, String)] = {
      if(isUpperAphpa(xor)){
          if( isLowerAphpa(xorHexStrings(xorWithSpace(hex1), hex2)) ){
            List( (pos, xorWithSpace(hex1)) )
          }else if( isLowerAphpa(xorHexStrings(xorWithSpace(hex2), hex1)) ){
            List( (pos, xorWithSpace(hex2)) )
      }else{
        List.empty
      }
  }else{
    List.empty
  }

}

As a result i got: List[Int, String] where String is the most popular lower_alpha got from getPossibleKey function.

Then i just applied collected key to each cipher and started to fix the key. I know that c1 xor m1 = k1 where c1 is a cipher fragment, k1 is a key fragment and m1 is a plain text.


A facility location problem Consider the following scenario. There are N localities in a town where population for locality $L_i$ is denoted by $P_i$, $i \in {1,\ldots,n}$. We need to place K hospitals around the town in a way that the cost of accessing the hospital is minimized.

We are basically trying to
$$\min_O(\sum_{i=1}^N P_i \times C(d(L_i,O(L_i))))$$
where, $$O(L_i) = \textrm{Nearest hospital's location to }L_i\\d=\textrm{Euclidean distance between 2 locations}\\C = \textrm{Cost function to travel distance }``d"$$

It doesn't seem we can use gradient descent. Consider 3 localities $L_1,L_2$ and $L_3$ and 2 hospitals $H_1,H_2$. If we initially put $H_1,H_2$ on $L_1,L_2$ e.g.

$$L_1H_1\ldots L_2H_2 \ldots L_3$$

If the gradient descent starts moving projects to the right, then we may find ourselves in the following situation. The final location of nearest hospital to $L_2$ would have changed from $H_2$ to $H_1$.

$$L_1\ldots H_1L_2 \ldots H_2L_3$$

So could you please give me some pointers on how to solve this problem?

This problem is known as Euclidean $k$-center problem and is known to be NP-complete. There are some approximation algorithms but we don't have any PTAS algorithm.

Of course for $K \geq N$, the solution is trivial, with optimal value 0.


Why and how geometric series are used for proofs? I often see that someone uses geometric series for proofs related to time complexity, but also I can't understand why they are used. Are they making proving easier? And how can I use this 'tool' for proofs? Can I transform problems to fit to geometric series?

For example the time complexity of this simple function to get a random prime is estimated by a geometric series, I don't see this is naturally (or rather intuitively) a geometric series.

The number of primes is guessed by $m / ln(m)$, so the expected value is
$$\sum_{i=1}^\infty i\left(1 - \frac{1}{\ln m}\right)^{i-1} \frac{1}{\ln m} = \frac{1}{\ln m} \cdot \frac{1}{1/(\ln m)^2} = \ln m.$$

Okay, this is the first case of my comment. This isn't a "tool"; this is simply the formula that comes up when you try to estimate the expected time complexity. Or more precisely, the expected number of iterations of the loop.

The $\frac{m}{\ln m}$ estimate for the number of primes less than $m$ comes from the prime number theorem. If we uniformly pick a number from $\{2,\dots,m\}$, then the probability that it will be prime is $\frac{1}{\ln m}$. The probability that it won't be prime is then $1-\frac{1}{\ln m}$. The probability that we will find a prime in exactly $i$ iterations is the probability that we fail to find a prime in the first $i-1$ iterations, and then find one on the $i$th iteration. Since the selection of the random numbers are (assumed) independent, this is $(1-\frac{1}{\ln m})^{i-1}\frac{1}{\ln m}$. Let $S$ be the number of iterations the algorithm takes. The probability that the algorithm takes exactly $i$ iterations, i.e. $S=i$, is $$P(S=i)=\left(1-\frac{1}{\ln m}\right)^{i-1}\frac{1}{\ln m}$$ except $P(S=0)=0$ since the algorithm always goes through at least one iteration.

By definition of expectation, the expected value of the number of steps is $$\mathsf{E}[S]=\sum_{i=0}^\infty SP(S=i)$$
Expanding this out, we get $$\mathsf{E}[S]=\sum_{i=1}^\infty i\left(1-\frac{1}{\ln m}\right)^{i-1}\frac{1}{\ln m}$$

In other words, exactly the geometric series you mention. At no point did I attempt to get the problem in the form of a geometric series, and there is no guarantee that it would be of that form. Instead, you can just start from the definition of expected value which is what you're trying to show. Then you see you need the probability of $S=i$ which happens to have a form that leads to the expectation being a geometric series. That said, if each iteration of a loop independently has a constant probability of terminating, which is common, then you will get a similar geometric series. If the probability changed with each iteration or the probabilities were correlated, then you would not end up with a geometric series in general, but the approach to the solution would be just the same, though actually simplifying the resulting infinite series in those cases might be quite difficult or impossible.