Find proportion of 'important' edge among all edges in a graph I met this problem when dealing with a social network problem. It is a subproblem of that. The problem is like that:

We look at a graph $G(V,E)$, where $V$ is the set of vertices and $E$ set of edges. We define $x \in V$ as an 'important' vertex if at least $\frac 1 3 deg(x)$ ($deg(x)$ refers to the degree of $x$)of the vertices in $x$'s neighborhood have degree no more than degree of $x$. We then define 'important ' edge as the edge when either one of the two vertices of the edge or both are 'important' vertices. We define the set of 'important' edge as $E_1$.

We want to show $|E_1| \geq \frac 1 2 |E|$. I cannot really think out any method. Could anyone provide some suggestions?

Many thanks.

The problem you asked can be actually generalized to an arbitrary total order $\mathcal{O}$ on the vertices: a vertex $x$ is important iff at least $\frac{1}{3}$ of its neighbors are smaller than $x$ according to $\mathcal{O}$. For the order on degrees we can break the ties arbitrarily, which will only make important vertices and thus important edges less.

We prove it by the adjacency matrix $M$. Suppose the vertices are ordered: $x_1<_\mathcal{O}\cdots<_\mathcal{O}x_n$, where $n=|V|$. Then $M\in\{0,1\}^{n\times n}$ with $M_{i,j}=1$ iff $(x_i,x_j)\in E$. In the rest part of the proof we abuse the notation of $M_{i,j}$ to represent the grid in the matrix $M$, and for a set of grids $S$ we use $|S|$ to denote the number of $1$'s among these grids.

The matrix $M$ is naturally divided into two triangles:
$$L=\{M_{i,j}\mid i>j\},\quad U=\{M_{i,j}\mid i<j\}.$$
Denote the $i$-th row by $R_i$, so $|R_i|=\deg(x_i)$. Now $x_i$ is important iff $|L\cap R_i|\geq \frac{1}{2}|U\cap R_i|$. On the other hand, since $|L|=|U|=|E|$ which means $\sum_i |L\cap R_i|=\sum_i |U\cap R_i|=|E|$, we know
$$\begin{align*}
|E_1|&\geq\sum_i\left\{\,|L\cap R_i|\;\middle|\; |L\cap R_i|\geq \textstyle\frac{1}{2}|U\cap R_i|\,\right\}\\
&=|E|-\sum_i\left\{\,|L\cap R_i|\;\middle|\; |L\cap R_i|<\textstyle\frac{1}{2}|U\cap R_i|\,\right\}\\
&>|E|-\frac{1}{2}\sum_{i=1}^n|U\cap R_i|=\frac{1}{2}|E|.
\end{align*}$$


The meaning of relativization I don't understand the notion of relativization. I expose with an example. Consider a class $A$ that contains $P$, e.g. $NP$. Why $P^A$ is not necessarily equal to $A$? I can naively think that if one can decide any problem in $A$, one can also decide any problem that uses polynomially many steps in a Turing machine plus calls to $A$. One can have at most polynomially many calls to $A$, thus $P^A$ seems there is only a polynomial overhead compare to $A$. If $A$ is $NP$, I could give a certification for all the (polinomially many) oracle calls, and also easily give a certification of the polynomial rest of the computation.
I understand that if it is true, then $NP$ is the same as $coNP$, both being contained in $P^{NP}$ from the polynomial hierarchy. So, where is the error in my naive argument?

Take $A=NP$, as you requested.  $P^{NP}$ is not necessarily equal to $NP$.

Let me give an example why not.  Consider TAUTOLOGY (given a boolean formula $\varphi$, is it true for all possible assignments to the variables?).  TAUTOLOGY is known to be co-NP-complete.  Therefore, TAUTOLOGY most likely is not in NP, since if TAUTOLOGY were in NP, it would follow that NP = co-NP, which is widely suspected not to be the case.

However, TAUTOLOGY is certainly in $P^{NP}$.  Here's why.  Given an oracle for SAT, we can solve TAUTOLOGY as follows: query whether $\varphi$ is in SAT; then flip the answer (if $\varphi$ is in SAT, answer "no, $\varphi$ is not in TAUTOLOGY"; if $\varphi$ is not in SAT, answer "yes, $\varphi$ is in TAUTOLOGY").  This shows how to solve TAUTOLOGY in polynomial time given an oracle for SAT, and SAT is in NP, so this shows that TAUTOLOGY is in $P^{NP}$.

So TAUTOLOGY is an example of a problem that is in $P^{NP}$, but probably isn't in NP (unless NP = co-NP).  Hopefully this helps illustrate why NP is not the same as $P^{NP}$.

If not, here's a little more intuition.  NP is a particular class.  $P^{NP}$ is the class of problems that can be solved by querying an oracle for NP, possibly many times.   The "many times" part is the key difference between NP and $P^{NP}$.  A (many-one) reduction between two NP problems can only query a NP-oracle once, while $P^{NP}$ allows you to query the oracle as many times as you like.  That seems to be a lot more powerful,  and it's the reason why $P^{NP}$ seems to be a bigger class than NP.


How to draw a graph to disprove this statement? The Problem: Indicate whether the following statements are true or false:

     a. If e is a minimum-weight edge in a connected weighted graph, it must be among edges of at least one minimum spanning tree of the graph.
     b. If e is a minimum-weight edge in a connected weighted graph, it must be among edges of each minimum spanning tree of the graph
     c. If edge weights of a connected weighted graph are all distinct, the graph must have exactly one minimum spanning tree
     d. If edge weights of a connected weighted graph are not all distinct, the graph must have more than one minimum spanning tree

I read from Min Edge that every MST must contain the minimum weighted edge and from Partial Solutions that two of the assertions are true while the rest of the two are false.
From those two statements, I concluded that the first two statements(a, b) are true while the last two statements(c,d) are false.

Here is the diagram I used to illustrate that the last option, d, is false.

The edge weights are not distinct(two twos) and there is only one minimum spanning tree.
Can anyone give a counterexample graph to choice option c? I tried some examples(too many to include in here) but each time with distinct weights, using Prim's algorithm, I only found one MST.

You have made a mistake interpreting the wording of the question compared to the Stackoverflow question (link in case of later editing).

Notice that in options (a) and (b), the phrasing is a minimum weight edge, whereas in the Stackoverflow question the phrasing is the minimum weight edge. In your question, there's no guarantee that the edge is the only edge with that weight, in the Stackoverflow question, there is exactly one edge with the lowest weight.

Thus the mistake is assuming that (b) is true, when in fact it is false. The two true options are (a) and (c), which is why you can't find a counter example to (c).

In both (a) and (c) however, the proof is very similar to that in the Stackoverflow question. In fact (c) is given by applying that proof inductively. (a) is given by basically the same argument, but you show that the tree made by adding the given edge and removing some other edge from the cycle can't have higher weight (because the new edge has minimum weight).

To see that (b) is false, just take the graph $K_{n}$ where all edge weights are the same. Any spanning tree is a minimum spanning tree.

For (d), consider the following graph; take a tree on $n$ vertices, give all these edges weight $1$. Then add all non-edges, give these new edges weight $2$.  Clearly there's only one MST, but there's $\binom{n}{2} - n + 1$ edges with the same weight.


How do I prove that a language is regular? In order to prove that the following language is regular, would I use a pumping lemma?

The set $A$ of all strings that are substrings of some string in $L$, where $L \subseteq\Sigma^*$. $L$ Must be regular.

Here's a hint. Since $L$ is regular, there is a finite automaton $M$ that accepts all and only those strings in $L$. Suppose you only wanted those substrings that start with the same character as a string in $L$. Could you somehow modify $M$ (perhaps by making some states final) so that it would accept all substrings starting with the same character as a string accepted by $L$?

Having done that, could extend this (perhaps with $\epsilon$-moves) so that you could jump from the start state of $M$ to a string along an accepting path in $M$?


What happens if we add denormalized number and normalized number? Denormalized numbers can represent numbers smaller than 2^(-1022) whereas normalized number cannot. So I'm curious what happens if we add denormalized number and normalized number. Actually, I have tried some tests and it seems that the computer converts denormalized number to 0. Is my thought correct?

The result depends on the difference between the normal and denormal numbers you are adding.
 $1 + [denormal]$ is rounded to $1$.

But if the range difference between your numbers is inferior to $2^{52}$ for doubles, or $2^{23}$ for singles, you will get a real addition. There is nothing special about denormals here : $1 + 2^{-200}$ is rounded to $1$ as well.

To implement a floating point adder (as hardware or software), you shift right the smaller number to equalize the exponents before doing an integer addition to the aligned mantissas. If the range difference is too large, the smaller number is entirely shifted out.


First-order vs Higher-order Programs Can someone explain the difference between first-order programs and higher-order programs in the context of programming languages?

My understanding so far is that Functional Languages (most) use higher order programs. Plus, higher functions either a) take other functions as arguments, or b) return functions as results.

Any correction, or further elaboration would on the difference between the two would be very appreciated.

Your assessment is correct.

A higher-order program takes programs as input or produces a program as output.
A first-order program takes values of base types as inputs and produces a value of base type as output.

In functional programming, functions are identified with programs, so we talk more about higher-order functions than higher-order programs.

This use of the word "higher-order" is common. For example, higher-order logics allow predicates to the arguments of other predicates.


When are range-based for loops better than regular for loops? Is it when you need faster performance, to iterate over a container, or when you don't need an index variable?

From my understanding it should be when you need to iterate over a container.

Am I understanding this properly?

In my experience, if you don't need an index variable and don't need to iterate over the objects in a particular order, then range-based for loops can be easier to understand, and less verbose. Outside of those conditions, it's usually a matter of taste. You're basically saying, "for each object in the container, do this," as opposed to saying, "for each index in the container, retrieve the object at the index, and for each object you've retrieved, do this."


Do we have knowledge bases only because the logics are not automated enough? Do we have knowledge bases only because the logics are not automated enough? I.e. - is it true, that the ideal situation would be that we use the set of logical formulas as the knowledge base together with the deduction services of the relevant logic as the reasoning services for this "knowledge base". But not all the logics are automated enough and that is why we are seeking approximations and representation and reasoning services for the more restricted deductive systems.

Most logical systems in use are automated enough in principle. That is, there are algorithms which find the proof of a statement, if such a proof exists. The problem is computational complexity. Such algorithms are very, very, very, very, very slow. We only know efficient algorithms for special, easy cases.

More generally, knowledge representation is not just about logical deduction. You cannot logically deduce the fact that after Monday comes Tuesday and that tigers have legs, that is something that the machine has to be told, and it has to then store such knowledge. How do we store knowledge? That is a question of expressivity of the symbolic representation (the thing you call "logic"), and it is an issue that is largely separate logical deduction.


Find nearest neighbour in a radius I have a set of points A in my space (geo points but I can assume they are on a 2D plane).

I have another set of points B.

For every point in B I want to find every point in A inside a radius R with center in the considered point from B set.

I did it with KDTree, this provide me a very fast and easy algorithm to create the data structure and find neighbours but it doens't find every point in a radius because it could avoid a path which contains element in my radius but not in the same subset of the radius center.

Minimal example of KDTree failing:

While exploring KDTree the target point (red) is under the line of point number 1. This will proceed to exploration of point under the line, this will miss the real point inside the red point radius.

What algorithm or data structure allow 100% correctness?

I know for sure I will performe worse but I am look for a balance between search speed and full correctness.

The K-D tree is a good data structure for solving this. However you can't blindly apply the search procedure only to the center point, you must be a bit smarter.

While searching the K-D tree for your points, every time you must choose the left or right child to search in, check whether the splitting plane is to the left of your circle, intersects it, or is to the right of the circle.

If the splitting plane is to the left of your circle you must continue searching in the right child, and vice versa. However when the splitting plane intersects your circle you must search both children.


Optimizing for maximum intervals given a distance bound Given an interval set $X = \{(s_1, e_1), \dotsc, (s_N, e_N)\}$ ordered such that $s_i \leq s_j$ and $e_i \leq e_j$ for all $i < j$ and an integer $b$, I would like to find a maximum sized subset $X' \subseteq X$ such that $\text{end}(X') - \text{start}(X') \leq b$. Here the $\text{start}, \text{end}$ functions are defined to be the start position of the first interval and the end position of the final interval.

A simple $O(N^2)$ solution would be to set $b' = b + s_i$ and scan all elements to see how many fit within the new bound $b'$. However, given the sorted structure of the problem it seems amenable to a fast solution.

First we can built an interval tree and perform the same set of queries as earlier, but result in an $O(N \log N)$ runtime.

I am curious if this is still suboptimal given that the data already are sorted. Is there a linear time dynamic programming solution?

A simple double pointer $O(n)$ linear scan suffices. Initialize $i = j = 1$.

Increment $j$ until the next step would make $e_j - s_i > b$. Check if $j - i$ is better than the best found result, if yes, store $(i, j)$ (the boundaries of your subset).
Increment $i$. Terminate if we reached the end of the set.

The key observation here is that if a certain $j$ for $i$ is optimal, then for $i' = i+1$, it must be that $j' \geq j$, so we only ever have to scan forwards.


“Left identity” of Monad laws in Haskell is wrong Monad laws in Haskell

Left identity:  return a >>= f ≡ f a
Right identity: m >>= return ≡ m
Associativity: (m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)

is widely known, and I think the "Left identity" rule does not make sense.

In category theory, it is true that Monads corresponds to Monoid, but this "Left identity" is twisting things around.

the binary operator >>= is a notation, so is f a or f(x) etc..

f(x)
f a
m >>= f
monad.bind(f)

In program semantics, all are the same, especially, when we define f always returns a monad value.

It's like "1" and "One" means the same entity in mathematics.

1 ≡ "One"  // Some Identity!
// this rule must be satisfied in terms of category theory!??

So-called "Left identity" in Haskell Monad law: return a >>= f ≡ f a is nothing to do with category theory but simply notation.

On the other hand "Right identity": m >>= return ≡ m makes sense because according to the notation replacement, it can be rewritten to return m ≡ m, and surely this defines one of monad feature or a rule of identity.

(edit)

TTX = TX
unit(unit(a)) = unit(a)
return m ≡ m

whatever, the semantics is the same.

In the later part of [Monad laws in Haskell][1], it makes an excuse saying

  Not in this form, no. To see precisely why they're called "identity laws" and an "associative law", you have to change your notation slightly.

then, it introduces "Kleisli composition operator" : >=>.

What?? The different operator is introduced, then they concluds:

  This is a very important way to express the three monad laws, because they are precisely the laws that are required for monads to form a mathematical category.

The widely known "Haskell monad laws" are based on the bind binary operator: >>=, but in fact, the "left identity" rule is nothing to do with catrgory theory but merely programming notation replacement, then later, by replacing the bind operator to "Kleisli composition operator" : >=>, it claims the notation replacement is based on category theory.

I think this fools the readers and is the source of confusion of Monad concept to beginers or all of us.

Probably, I also need to mention that this Monad laws are firstly fomalized  in Monads for functional programming by Philip Wadler

EDIT:

Well, I do not deny return a >>= f ≡ f a is a binary operator definition. It's a replacement of notation, and here is the thing.

notation replacement is nothing to do with category theory or "Left identity"  `

You should be more precise. When you say that f(x), f a and m >>= f are "the same", that does not make sense as written. f(x) and f a cannot be the same, they do not even use the same variables. Did you mean to compare f(u), f u and u >>= f? It is true that f(u) and f u are the same thing, but u >>= f is not. If f has type a -> m b (where m is the monad) then

in f u the type of u must be a, but
in u >>= f the type of u must be m a

So the types don't even match. Furthermore, if you look at concrete examples, you will see that >>= is not "just notation". It actually does things.

If we now look at the left identity law

return u >>= f  ≣  f u

we see that we cannot just rewrite the left-hand side to f u, or even f (return u). We must take into account what return and >>= do in a specific case. For instance, in the list monad we define

return x = [x]

and

(xs >>= f) = concat (map f xs)

The left identity law holds because of how concat and map work:

return x >>= f      ≣
[x] >>= f           ≣
concat (map f [x])  ≣
concat [f x]        ≣
f x

The above calculation was not just "notation"!


Reweight general weighted graph to distinct graph for using Borůvka's Is it possible to re-weight a generally-weighted graph to a distinctly-weighted graph to apply Borůvka's algorithm (wiki) for minimum spanning tree to it?

I can't seem to think of a way to make a distinction between the same weights, it feels unnatural.

Though the Borůvka's algorithm (wiki) for minimum spanning tree is (sometimes? often?) described for weighted graphs with distinct edge weights, this treatment is only for convenience.

If we have an algorithm that assumes the edge weights are unique, we can use it on graphs where multiple edges have the same weight, as long as we have some way of breaking the ties. For example, in graphs where edges have identical weights, edges with equal weights can be ordered based on the lexicographic order of their endpoints (suggested by the wiki article).

To apply the lexicographic order, assume two edges $(a,b)$ and $(c,d)$ have the same weight $w(a,b) = w(c,d)$, where $a,b,c,d$ are (not necessarily distinct) vertices. Then we can decide which of $w(a,b)$ and $w(c,d)$ have the "smaller" weight by comparing the pair $(a,b)$ and $(c,d)$ in their lexicographic order.

Therefore, you don't need to re-weight the equally-weighted edges. You only need to mark them  distinct.


Why encoding of graph in adjacency matrix is $\Omega (\sqrt n)$? in the textbook of CLRS, p.1062 he says the following:

  if we use "reasonable" encoding of a graph as its adjacency matrix, the number m of vertices in the graph is $\Omega (\sqrt n)$, where n = |$\langle G\rangle|$ is the length of the encoding of G.

I want to know why $\Omega (\sqrt n)$? I mean it is adjacency matrix which takes $m^2$ but I don't know how he calculates it, so I would like someone to explain to me how we get this time complexity?

Thank you!

An $m\times m$ adjacency matrix requires $m^2$ bits, and $m=\sqrt{n}$ is just the solution to $m^2 = |\langle G\rangle| = n$.

The point of the $\Omega$ is that a reasonable encoding doesn't have fewer than $\sqrt{n}$ vertices in a description of length $n$.  For example "Write out the $k\times k$ adjacency matrix followed by $2^k$ zeroes" isn't "reasonable" and a string of length $n$ would encode a graph with only about $\log n$ vertices.


How to prove that ($56n^2+106n+48)(\log(264n^2+200)) = Θ(^2\log n)$ I understand that essentially we have to prove that

$$c_1(n^2\log n)\le
   (56n^2+106n+48)(\log(264n^2+200))
       \le c_2(n^2\log n)\,.$$

I am confused on how to simplify this further? And correctly find a c value.


Derivation of implicational propositional axioms Is there a way to subtract and add properties of axioms to generate new axioms?

For example:

{L} = {P S K} // natural deduction

{P S K} = {P H K I} // natural deduction

{S K} = {?} // constructive logic

{K I} = {?}

Where:

L = ((A -> B) -> C) -> ((C -> A) -> (D -> A)) // Łukasiewicz's axiom system

P = ((A -> B) -> A) -> A // Piece's Law

H = (A -> B) -> ((B -> C) -> (A -> C)) // Weak hypothetical syllogism

S = (A -> (B -> C)) -> ((A -> B) -> (A -> C))

K = A -> (B -> A)

I = A -> A

I want to be able to be able to add and subtract axioms such that
P + S + K = P + H + K + I implies S encodes the properties of H + I

I'm probably using unjustified assumptions here. For example, I assume you can derive S from H and I, without using P or K. Ideally, there would be a way to automate the process of constructing and destructing axioms (though it'd probably be NP hard).

The natural way to define your addition operation is as set intersection. The value of a single axiom is the set of all models satisfying the axiom. The sum of several axioms is then the set of all models satisfying all the axioms.

A similar definition is $\mathbf{A} + \mathbf{B} = \mathbf{A} \land \mathbf{B}$, but then you need to interpret equality as logical equivalence. The definitions then become completely equivalent.

However, you can't "cancel" axioms. If you know that $\mathbf{A}+\mathbf{B} = \mathbf{A}+\mathbf{C}$ then all you can conclude is that in the presence of $\mathbf{A}$, $\mathbf{B}$ and $\mathbf{C}$ are equivalent. As an example, let $\mathbf{A}$ be $x=0$, let $\mathbf{B}$ be $y=1$, and let $\mathbf{C}$ be $x+y=1$. In the presence of $\mathbf{A}$, the axioms $\mathbf{B}$ and $\mathbf{C}$ are equivalent, but in general they aren't.

If are are really keen on the cancellation law, you can always take formal sums. It is then true that $\mathbf{A}+\mathbf{B} = \mathbf{A}+\mathbf{C}$ implies $\mathbf{B}=\mathbf{C}$, but at the cost of $\mathbf{A}+\mathbf{B}$ having no other meaning than the formal sum of $\mathbf{A}$ and $\mathbf{B}$.


Is the multiplicative constant in the Big O notation are ignored because of Linear Speed-Up theorem? I just want to know if Big O notation was used as a consequences of the Linear speed up theorem or not. For me I guess the answer is yes.
For example, if we didn't have a linear speed-up theorem, then does it mean that we would have a different measure of time/space complexity? i.e. multiplicative constants does makes different. For example, $f(n) = 100 n$ isn't the same as $g(n)=10^{82}n$. Therefore, in this regard, Big O notation is not useful. So, probably we have another way to measure algorithms.

Please note that the big O notation was invented before the proof of the linear speedup theorem, and even before Turing machines.
Also, the big O notation often gives an information independant of the multiplicative constant: "if I multiply the input by $k$, then the total computing time will not be multiplied by more than …".
Finally, keep in mind that the linear speedup theorem gives a way to reduce the number of steps in the execution of a Turing Machine, but if you implement it on a real computer, it often also means that each step may be longer, so the real total time may not decrease.
The big O notation is a convenient way to compare asymptotic time complexity, but it is not always sufficient. For example, mergesort have an asymptotic complexity $\Theta(n\log n)$, but considering the multiplicative constant, it is often better to use insertion sort to sort small data, even if the asymptotic complexity of insertion sort is $\Theta(n^2)$ in average. Another example are Fibonacci heaps.


Minimum path between two vertices passing through a given set exactly once Suppose I have a source node $S$, destination node $D$ and a set $A$ of intermediate nodes $P_1, P_2, \dots$ in an edge-weighted undirected graph. I want to find the vertex $P_i\in A$ that minimizes $\mathrm{dist}(S, P_i) + \mathrm{dist}(D, P_i)$?  In addition, the overall path from $S$ to $D$ should contain only one node from the set $A$.  What is an efficient algorithm for this? I don't want to go with brute-force approach.

The following answers the variant which requires passing through the set exactly once.

Make two copies of the graph. Remove all edges incident to two vertices of $A$. Orient all edges incident to $A$ in the first copy toward $A$, and all edges incident to $A$ in the second copy from $A$; other edges are bidirectional. Connect both copies of each vertex in $A$ with a zero-weight edge going from the first copy to the second copy. Now look for a shortest path between the first copy of $S$ and the second copy of $T$.

Using Dijkstra's algorithm, the complexity of this approach is $O(E+V\log V)$. In comparison, the trivial algorithm that tests all vertices in $|A|$ one at a time needs to run Dijkstra's algorithm $|A|$ times, unless the graph is unweighted, in which case one can use BFS instead in time $O(E|A|)$.

Here is an alternative solution, using only undirected graphs. Start by deleting all edges inside $A$. Add $M$ to the weight of all other edges incident to $A$, where $M$ is larger than the sum of all weights in the graph. Run Dijkstra's algorithm twice to find the shortest path between $S$ and any vertex in $A$, and between $T$ and any vertex in $A$; in both cases, the shortest path passes through no other vertex in $A$, due to our adjustment of the weights. Now go over all vertices $A$ and find the shortest path from $S$ to $T$ via a vertex in $A$.

This algorithm also runs in time $O(E+V\log V)$.

The following answers the variant which requires passing through the set at least once.

Make two copies of the graph. Connect both copies of each vertex in $A$ with an edge of zero weight. Now look for a shortest path between the first copy of $S$ and the second copy of $T$.

The complexity is $O(E+V\log V)$, or $O(E+V)$ if the original graph is unweighted (in this case, we modify the construction so that the parallel $A$-edges have unit weight; this is harmless in terms of computing the shortest path).


Asymptotic complexity of Combination sum problem vs Coin change problem I've been looking at the following combination sum problem:

Given a set of candidate numbers (candidates) (without duplicates) and a target number
(target), find all unique combinations in candidates where the candidate numbers sums to
target.

The same repeated number may be chosen from candidates unlimited number of times.

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

Most of the solutions I encountered for this problem were some variant of the following backtracking solution:-

public List<List<Integer>> combinationSum(int[] nums, int target) {
    List<List<Integer>> list = new ArrayList<>();
    backtrack(list, new ArrayList<>(), nums, target, 0);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int
remain, int start){
    if(remain < 0) return;
    else if(remain == 0) list.add(new ArrayList<>(tempList));
    else{
        for(int i = start; i < nums.length; i++){
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
            tempList.remove(tempList.size() - 1);
        }
    }
}

Most of the comments of these solutions implied an asymptotic complexity of O(2^N) due to this code potentially building up all subsets in the worst case.

However, this problem statement seems very similar (if not identical) to the Coin change problem

You are given coins of different denominations and a total amount of money. Write a function
to compute the number of combinations that make up that amount. You may assume that you have
infinite number of each kind of coin.

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

The most common solution I've found to this problem is the following O(N*amount) dynamic programming solution:

class Solution {
  public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;

    for (int coin : coins) {
      for (int x = coin; x < amount + 1; ++x) {
        dp[x] += dp[x - coin];
      }
    }
    return dp[amount];
  }
}

It seems to me that the first solution is just the top down variant of this algorithm.

I can't seem to figure out why the first solution is exponential and the second one is not.
Where have I gone wrong in my understanding?

Is it actually printing the subsets vs counting that makes the difference here?

Is there any way print all combinations whilst preserving polynomial time?

The solution to the coin counting problem uses memoization as a way to decrease the exponential nature into just polynomial time.

The trick here, is that the amount, is always decreasing and can be computed from all of the smaller leftover amounts. this ensures that we need to compute up to amount values, that every next value is easy to compute from the ones before it.

Now for the main question: you are right in that getting the subsets themselves is what makes the difference - now the amount of 'values' you need to compute is the number you can calculate from the coin problem (for example, calculating there are 150 possible ways to distribute the coins, means you need to actually find all of the 150 solutions).
this number is not as small as amount and can be exponentially big in it

Shortly: calculating the number of solutions can be easily bounded by poly time, but calculating every solution means doing at least O(number of solutions) operations

I hope that helped! im new here :p


State of the art time complexity for getting (tree) descendants by type/attribute Let's say I have a tree comprised of nodes where each node is of some type (T), where there is a known/fixed number of types (i.e. similar to attributes in an xml document), and where a node can only have one type. Let's also assume that our tree is somewhat balanced, and that there are far more nodes in the tree than there are unique types. Assuming I have already created some sort of index on the tree, I need to know the state of the art time complexity for the following types of queries (using whatever type of index / data structure you like):

Where A is some arbitrary node in the tree and T is some arbitrary type:

find all descendants of node A that are of type T
find the number of descendants of node A that are of type T

If the tree is static and no updates to the index are required, I have a data structure that will do 1 and 2 in $O(1)$. If the tree can have nodes added/removed, I also have a data structure that will do 1 and 2 in $O(\log m)$ where m is the total number of nodes of type T in the tree ($m << n$), and that can update the index when changes are made to the tree in $O(k\log m)$ where k is the number of nodes affected.

Are my data structures state of the art for these types of queries, or on par with state of the art? What existing work is out there that can match or beat this performance, if any?

(assume that any indexing structure we use must take less than $O(n^2)$ time and memory to construct)

(assume that any indexing structure we use for the case where the tree/index can be modified, that modifications can be handled in better than $O(n)$)

My understanding is that XML indexing generally has the state-of-the-art indexing schemes for dealing with trees where there are typed nodes, so I assume something with XML indexing will crop up here. I've tried looking through a number of papers myself but it's very difficult to get actual time complexities out of people in that field for some reason.

For the static case, if you have a solution with $O(1)$ running time, I can't see any opportunity for improvement in the running time, as you can't do better than $O(1)$.  So I'll focus on the dynamic case, i.e., where we want to support insertions and deletions.

One strategy is to augment the tree, so that for each type $T$ each node $x$ contains:

A count of the number of descendants of type $T$
A pointer to each immediate type-$T$ descendant of $x$ (i.e., a link to each $z$ such that $z$ has type $T$, $z$ is a descendant of $x$, and there is no descendant $y$ of $x$ such that $y$ has type $T$ and $z$ is a descendant of $y$)
A pointer to the immediate type-$T$ parent of $x$ (i.e., the lowest ancestor of $x$ that has type $T$)

This allows 'count' queries to run in essentially $O(1)$ time: given a node $x$, you can count the number of type-$T$ descendants of $x$ in $O(1)$ time.  (Simply find $x$'s immediate type-$T$ parent, then use the field in the parent that stores the count of number of type-$T$ descendants.)

Also, 'enumerate' queries run in $O(k)$ time: given a node $x$, you can enumerate all type-$T$ descendants of $x$ in $O(k)$ time, where $k$ is the number of type-$T$ descendants of $x$.  (Simply find $x$'s immediate type-$T$ parent, then traverse the fields that list the immediate type-$T$ descendants, recursively.)

The running time to insert a new leaf at depth $d$ in $O(d)$ time, since you only need to update the fields in the nodes along the path from that leaf to the root.  If the tree is balanced, this is $O(\log n)$ time.

The running time to delete a leaf at depth $d$ is the same, for the same reasons.

This is the best I know how to do.  I don't know if it is possible to do better.


Functor laws and natural transformations in Haskell As I've been struggling to get a deeper understanding of monads in Haskell, I started reading about functors and their counterparts in category theory. Keep in mind that I have no background on the latter.

According to Milewski(1), any polymorphic function of the type F a -> G a, where F and G are functors, automatically satisfies the naturality condition, although I have yet to figure out why. Anyways, this should hold in particular when F is the identity functor, which if understand correctly would correspond to the aforesaid function having the type a -> G a. Now, for simplicity let:

data G a = C a

If G is a functor, then since C :: a -> G a, C is a natural transformation. Viceversa, suppose C is a natural transformation. Thus, for all functions f:

(fmap f) . C == C . f

which I imagine is what leads to the wrapping-unwrapping analogy. In fact, if we render C x as {x} as in "wrapped x", then the previous can be re-written as:

(fmap f) {x} == {f x}

which quite literally means that applying the transformed f to the wrapped value is the same as unwrapping, applying f to the unwrapped value and re-wrap it. By the previous equality:

law 1) (fmap id) {x}      == {id x}
                          == {x}

law 2) (fmap (f . g)) {x} == {(f . g) x}
                          == {f (g x)}
                          == (fmap f) {g x}
                          == (fmap f) ((fmap g) {x})
                          == ((fmap f) . (fmap g)) {x}

It follows that G is a functor.

So is it correct to say that requiring the functor laws on a type constructor is equivalent to requiring that its data constructors satisfy the naturality conditions, or something along these lines? And if not, then what is the purpose of the functor laws from a "practical" point of view?

Edit: I just wanted to clarify that I don't really need an answer to the previous question. What really troubles me is that most tutorials on Haskell's functors make it seem like their wrapper-like nature (on which the intuition behind applicatives and monads is often based) stems from their laws when in reality it seems to be a consequence of the naturality conditions due to Wadler's free theorems(2), unless I'm completely mistaken. What role do the functor laws play in their interpretation as abstractions of some functional programming pattern?

(1) Milewski, B.; Category Theory for Programmers; 164
(2) reasonablypolymorphic.com/blog/theorems-for-free/

I'm having a little trouble exactly what question you're asking, but I think it might help if we went through the connection between homomorphisms and free theorems.

But here's the executive summary of what I think you want to know:

The fmap laws are not redundant when you have free theorems. On the contrary, you need fmap to state the free theorem for any function that involves a Haskell Functor.
Specifically, if a function has the type of a natural transformation, its free theorem is the naturality condition expressed in terms of fmap.

First off, let's get a bit of intuition about what the parametricity theorem states. An informal way of stating it is this: For any function which has a "forall" in its type, that "forall" really does mean "for all types". The function cannot make any assumptions whatsoever about the type.

To explain what this means when we involve types with an algebra, we need the language of homomorphisms. So let's review what a homomorphism is. (Sorry if this is revision for you, but I think it's worth going through this.)

Let's consider monoids. A monoid is a set $M$ along with two operations $0_M$ and $+_M$ which obeys the laws:

$$\forall x \in M, x +_M 0_M = 0_M +_M x = x$$
$$\forall x,y,z \in M, x +_M (y +_M z) = (x +_M y) +_M z$$

A monoid homomorphism is a function between two monoids $f : M \rightarrow N$ which "respects" the two operations:

$$f(0_M) = 0_M$$
$$f(x +_M y) = f(x) +_N f(y)$$

In Haskell, we might represent monoids as a type class:

class Monoid m where
    mzero :: m
    mplus :: m -> m -> m

If M1 and M2 are instances of Monoid, a Monoid homomorphism f :: M1 -> M2 must obey the laws:

f mzero = mzero
f (mplus x y) = mplus (f x) (f y)

Remember that the monoid operations on the left-hand side of these "laws" are different from the monoid operations on the right-hand side. The left-hand side are the operations for M1 and the right-hand side are the operations for M2.

Now consider the following typeclass (which isn't the same as Haskell's Ord typeclass, but is close enough):

class Ordered a where
    lessThan :: a -> a -> Bool

Again, there are laws that any reasonable "less than" operator must obey. But what I want to concentrate on here is the Bool part.

What does it mean for a function to "respect" this algebra? It essentially means that the Bool has to be the same. That is, if A and B are both instances of Ordered, an Ordered homomorphism f :: A -> B must obey the law:

lessThan (f x) (f y) = lessThan x y

Think about what this means semantically: this law is stating that for any two elements, f doesn't change their relative ordering. That is what it means for f to "respect" the ordering algebra.

OK, now back to the parametricity theorem. The free theorem for the function:

sortBy :: forall a. (a -> a -> Bool) -> [a] -> [a]

is this, written out in a slightly fuller form:

for all f :: A -> B,
If lt :: A -> A -> Bool is a function such that
    for all x, y :: A, lt x y = lt (f x) (f y)
Then
    for all xs :: [A], sortBy lt . map f = map f . sortBy lt

We can say the same thing with type classes:

sort :: forall a. Ordered a => [a] -> [a]

The free theorem here is, essentially:

for all f :: A -> B,
if f is an Ordered homomorphism
then sort . map f = map f . sort

Which is, of course, just that f doesn't change the ordering of elements, then performing the substitution map f and then sorting is the same thing as sorting them performing the substitution.

The complication with Functor is that it's a constructor class, so the intuition about what a Functor homomorphism should be is a little less clear. But let's step back a moment and talk about category homomorphisms.

Categories are algebras just like any other. A category has two operations, $1$ and $\circ$, which satisfies the laws that you know and love. So a category homomorphism $F$ is a function which satisfies:

$$F(\hbox{id}) = \hbox{id}$$
$$F(g \circ f) = F(g) \circ F(f)$$

If you think of a functor between the "Haskell category" (objects are Haskell types, morphisms are Haskell functions) and a Haskell Functor category (objects are Haskell functors and morphisms are Haskell functions between these objects), then this is exactly the Functor laws.

fmap id = id
fmap (g . f) = fmap g . fmap f

Now here's the important part: The fmap operation is the homomorphism precondition that you need for free theorems involving Functor.

Consider, for example, something with the same type as fmap but isn't necessarily fmap:

instance Functor F where ...

somethingLikeFmap :: forall a b. (a -> b) -> (F a -> F b)

The free theorem for this function is:

if q . f = g . p,
then somethingLikeFmap q . fmap f = fmap g . somethingLikeFmap p

From this you can conclude a bunch of interesting things, such as that if somethingLikeFmap id = id then fmap = somethingLikeFmap. In particular, somethingLikeFmap can be characterised entirely by what it does with id.

This has to be the case. The parametricity theorem, which generates these free theorems, states the "forall" in a parametric type really does mean "for all types".

If the functor is a container-like type, for example, the function cannot make any decision about what to do based on the value of an element in the container. But it could do anything with the structure of the container which doesn't depend on the values in it.

somethingLikeMap1 f = reverse . map f
somethingLikeMap2 f = map f . tail
somethingLikeMap3 f = []

If a polymorphic function does has a way to make decisions based on the values (e.g. lessThan in the case of sort), then the free theorem states that this is the only way that it can make a decision about what to do, so if the mapping doesn't affect the decisions (e.g. the values returned by lessThan), then it doesn't affect the operation of the polymorphic function (e.g what sort does).

So this is why the fmap laws are not redundant with respect to free theorems: they define the homomorphism between the Haskell category and the (endo-) functor category that you need to state the free theorems.

Finally, what is the free theorem of a function which has the type of a natural transformation?

instance Functor F where ...
instance Functor G where ...

eta :: forall a. F a -> G a

It is:

fmap_G f . eta = eta . fmap_F f

This is exactly the naturality condition. This a good way to think about what's so "natural" about a natural transformation.


NFA to DFA final states proof When translating an NFA into an equivalent DFA, we can say that all
  states that contain the final states of NFA, is the final state of
  DFA.

What should my arguments be in order to prove this?

Your statement is incorrect for two reasons.

First, there are in general several final states in the DFA corresponding to an NFA and not a single one. Next a set in the DFA is final if and only if it contains at least one final state of the DNA (and not all of them as you wrote). Furthermore, the initial state of the DFA is the set of all initial states of the DFA.

You can find the formal proof in any textbook on automata, but here is the intuition.

Let $\mathcal{A} = (Q, A, E, I, F)$ be a NFA. Let us call successful a path in $\mathcal{A}$ starting in $I$ and ending in $F$.
By definition, a word $u$ is accepted by $\mathcal{A}$ if and only if there exists a
successful path with label $u$.

Now, what happens when you use the subset construction to compute a DFA $\mathcal{B}$ equivalent to $\mathcal{A}$? You know that the states of $\mathcal{B}$ are subsets of $Q$. Furthermore, there is a path from $P$ to $R$ with label $u$ (where $P$ and $R$ are subsets of $Q$) if and only if
$$
\text{for each $r \in R$, there is a state $p \in P$ and a path in $\mathcal{A}$ from $p$ to $r$ with label $u$.}
$$
Thus intuitively, this path $P \xrightarrow{u}_{*} R$ in the DFA encodes all the possible paths in the DNA from a state of $P$ to a state of $R$.

Suppose now that $P = I$ and that $R$ contains a final state of $\mathcal{A}$, say $f$.
Then there is a state $p \in I$ and a path in $\mathcal{A}$ from $p$ to $f$ with label $u$. Thus this path is successful and $u$ is accepted by $\mathcal{A}$.

In the opposite direction, suppose that $u$ is accepted by $\mathcal{A}$. Then $u$ is the label of a successful path in $\mathcal{A}$, say from $p \in I$ to $f \in F$. Let $R = I \cdot u$ (in the DFA $\mathcal{B}$). Then $f \in R$ by construction and thus $R$ contains a final state.


What's the difference between Adaptive Control and Hierarchical Reinforcement Learning? After watching Travis DeWolf presentation on scaling neural computation, I'm a bit confused about the difference between Reinforcement Learning (whether hierarchical or not) and Adaptive Control. They both seem to be exploring environments and minimizing error through learning, but they're obviously used for very different applications. Can someone explain to me what's the difference between these two tasks and based off that difference, what would be a good way to combine them?

The difference between the two tasks really comes down to the level of continuity assumed in the models of the problem.

In adaptive control, continuity is assumed at all levels; the problem space and the actions to be executed are all continuous.

In hierarchical reinforcement learning, although the problem space is continuous, the actions to execute upon the space are discrete.

A good analogy for this is the robot arm trying to move to a certain goal. Adaptive control would work with Jacobian to find a continuous solution to this problem. Reinforcement learning would select actions (up, down, left, right) to learn the problem space and find a solution.

Hierarchical reinforcement learning and adaptive control are really complements of each other. When the problem gets too complex to compute with Adaptive Control, hierarchical learning steps in to make it discrete and more scalable.

For another perspective, especially since my explanation breaks down when you consider continuous HRL (which does exist), consider this explanation from my personal correspondence with Daniel Rasumussan:

  Practically, there are many differences between how they [Adaptive Control and HRL in a continuous space] are
  implemented; they use different algorithms, different learning rules,
  different representations, etc.  For example, adaptive control is not
  typically hierarchical.  You could arguably call it a hierarchy with a
  depth of 1 (with e.g. the "high level" being control in the x,y space
  and "low level" being control in the motor space).  But there's no
  temporal abstraction in that hierarchy; the high level isn't trying to
  encapsulate low level decisions, the problem is how to find a nice
  reliable one-to-one mapping between those two spaces.  Of course you
  could make adaptive control hierarchical, as you can make pretty much
  anything hierarchical, but that isn't typically what they're
  interested in.  Perhaps a more critical difference is that in motor
  control typically it is assumed that the transition and reward
  functions are known to the agent.  There may be some unknown
  variability in the case of adaptive control, but by and large the
  agent has a pretty good idea what the effects of its actions will be,
  and what the goal is that it is trying to achieve.  It's one of the
  key principle of reinforcement learning that that information is not
  known, and must be figured out by the agent by exploring the
  environment.  Now again here, you could come up with a motor control
  problem where the agent doesn't assume that information is known, but
  that just isn't the kind of problem those techniques are designed for,
  in general.  So, to sum up, there certainly is a gradient between HRL
  and adaptive control, and by tweaking various assumptions you can
  bring them closer together or farther apart.  But just implementing
  continuous actions in HRL would still leave you quite a ways from
  adaptive control.

As for an example combination this, one might imagine using hierarchical reinforcement learning to play a video game like Pong and then changing the physics of the game (Pong on slippery ice!) so that Adaptive Control might step in.


Cofiniteness is $Σ_3^0$-complete How can we prove that the language $COF=\{M\mid L(M)\text{ is cofinite}\}$ is m-complete for the class $ Σ_3^0$ ?
I have shown that $COF\inΣ_3^0$ but I can't prove that $COF$ is m-hard for $Σ_3^0$ which means that every other problem $L\in Σ_3^0$ satisfies $L\leq_m COF$.

Your problem is not so trivial, though classical. See the proof of Corollary 11.9 in lecture notes of Kevin T. Kelly.


PDA for { xy : |x| = |y|, x ≠ y} from its grammar, and intuition behind it I know the grammar for the language $\{ xy : |x| = |y|, x ≠ y \}$ if $\Sigma=\{a,b\}$:

$$
\begin{align*}
&S→AB∣BA \\
&A→a∣aAa∣aAb∣bAa∣bAb \\
&B→b∣aBa∣aBb∣bBa∣bBb
\end{align*}
$$

I know this is a grammar, but I need a PDA for this language, and intuition how $\{xy: |x|=|y|,x \neq y\}$ is a CFL while $\{xy: |x|=|y|,x=y\}$ is a CSL but not a CFL. How is this possible?

You are asking two questions: how to construct a PDA for the language, and why this language is context-free while the same language with the condition $x \neq y$ replaced by the condition $x = y$, is not. I will only answer the second, since for the first question there are known algorithms.

The reason that your language is context-free is that we can rewrite it as follows:
$$
\{ \Sigma^i a \Sigma^i \Sigma^j b \Sigma^j : i,j \neq 0 \} \cup
\{ \Sigma^i b \Sigma^i \Sigma^j a \Sigma^j : i,j \neq 0 \}.
$$
This gives a different description of the language as the union of concatenations of context-free languages. A similar trick just doesn't work for the language $\{ xy : x=y \}$.

Here is a different example. Consider the following two collections of natural numbers (without zero):

$A = \{ x \cdot y : x \neq y \}$.
$B = \{ x \cdot y : x = y \}$.

The set $A$ consists of all natural numbers other than $1$, whereas the set $B$ consists of all squares. Even though we defined them in a similar way, the set $A$ has a much simpler description, while $B$ doesn't.


The minimization operator is an effective operator Assume $\{f_i^{(n)}\}_{i=0}^\infty$ is a Gödel enumeration of the $\mu$-recursive functions of $n$ arguments, such that the $S^m_n$ theorem and the universal function theorem hold. Denote the set of (total and partial) functions $\{f:\mathbb N^k\to\mathbb N\
\}$ by $\mathfrak F^k$

Definition: We call an operator $G:\mathfrak F^n\to\mathfrak F^k$ effective, if $(\forall j\in\mathbb N)(G(f^{(n)}_j)=f^{(k)}_{g(j)})$ for some total recursive function $g$.

Claim: The minimization operator $\mu:\mathfrak F^{k+1}\to\mathfrak F^k$ defined by $$\mu(f)(\overline x)=\mu y[f(y,\overline x)=0]=y\iff (f(y,\overline x)=0\land(\forall i<y) (f(i,\overline x)>0))$$ is an effective operator.

Question: How can I go about proving the statement? Hints are welcome.

Thought: By definition the $\mu$-recursive functions are closed with respect to the $\mu$-operator. Therefore, $\mu(f^{(k+1)}_j)=f^{(k)}_{h(j)}$, for some unique total function $h$. But why is $h$ a computable function?

Note that I would really like to stay within the Partial Recursive Functions Formalism. Pseudo code means nothing to me. I cannot read it. I am not familiar with most of the notation from the programming world. I would also prefer not go into Register Machine Formalisms.

The best way to solve such problems is to understand what they amount to in real programming code. All the stuff about Gödel encoding is very mathy and fancy but uneccessary in this day and age.

We can think of Gödel codes of $\mu$-recursive functions as source code. The fact that an enumeration satisfies the smn theorems amounts to the fact that, given the source code of a function on $k$ arguments, we can calculate the source code of the same function with one of the arguments fixed to a particular value. The utm theorem just says that there is an intepreter for the source code.

An operator $G$ is effective if there is a program which converts the source code of a function $f$ to the source code of $G(f)$. This program must work for all valid inputs (is total). To see that the minimization operator is effective we thus have to write a program p which does the following:

Input: source code $S$ of a function $f$
Output: source code for the function $\bar{x} \mapsto \mu \, y [f(y,\bar{x}) = 0]$

Our program converts some source code to some other source code. It should not try to minimize anything, or simulate $f$, or anything like that. At this point you should stop reading and do the exercise yourself, in whatever your favorite programming language is.

Really, stop reading and do it yourself.

Here is my solution:

def p(k, s):
    """Convert source code s of a function in k+1 arguments to a function in k arguments which
       minimizes in the first argument. We assume that the source code s for the function
       is given in the following form (had we chosen a more decent programming language,
       we could have used anonymous functions instead):

              "def f(x0, ..., xk):
                 <body of function>
              "

       The output is given as a source code of a function in the following format:

              "def f(x1, ..., xk):
                  <body of function>
              "
    """

    # The string "x1, ..., xk"
    xs = ", ".join(["x{0}".format(k) for k in range(1,k+1)])
    # The source code s indended by 4 characters
    s4 = "\n".join("    " + l for l in s.split("\n"))
    # Now we can generate the output
    return ("""def f({0}):
{1}
    y = 0
    while True:
       if f(y, {0}) == 0: return y
       else: y = y + 1
    """.format(xs, s4))

Our program p corresponds to a primitive recursive function because it contains only for loops with prescribed bounds (the while True is not part of our program because it is inside a string and so is really part of the source code that our program outputs).

Let us try an example:

## We look for the least y such that x <= 2 * y.

s = """def f(y,x):
   return (1 if x <= 2 * y else 0)
"""

t = p(1,s)

print(t)

The output printed is:

def f(x1):
    def f(y,x):
       return (1 if x <= 2 * y else 0)

    y = 0
    while True:
       if f(y, x1) == 0: return y
       else: y = y + 1


Kleene algebra - powerset class vs class of all regular subsets I am currently studying materials for my uni subject. There are two examples of Kleene algebras, but I don't see what is the difference between them.

Class ${2^{\Sigma}}^{*}$ of all subsets of $\Sigma^{*}$ with constants $\emptyset$ and $\{\varepsilon\}$ and operations $\cup$, $\cdot$ and $*$.
Class of all regular subsets of $\Sigma^{*}$ with constants $\emptyset$ and $\{\varepsilon\}$ and operations $\cup$, $\cdot$ and $*$.

What is the difference between ${2^{\Sigma}}^{*}$ and all regular subsets of $\Sigma^{*}$? What is that difference I don't see? Thanks in advance.

The difference between the two is that $2^{\Sigma^*}$ contains all languages over $\Sigma$, whereas the class of all regular subsets of $\Sigma^*$ contains only the regular languages over $\Sigma^*$. So if $L$ is a non-regular language over $\Sigma$ then $L \in 2^{\Sigma^*}$ while $L$ doesn't belong to the set of all regular languages over $\Sigma$. For any $\sigma \in \Sigma$, you can take $L = \{ \sigma^{n^2} : n \geq 0 \}$, for example.


Why increasing the beam width does not necessarily improve the beam search solution? Normally increasing the beam width is a better solution, but I have read that this is not necessarily true, is there any proof of this?

Imagine your tree looks as follows:

You are looking for the leaf with minimum label and the label of each internal nodes represents the heuristic value associated with the subtree routed at that node.

If the width of your beam is just $1$, you start at the root and then go $\rightarrow 5\rightarrow7\rightarrow0$.

If the width of your beam is $2$, you first take $[5,6]$ as potential candidates. Look at $5's$ children, so your best candidates at that point for the next level are $[7,8]$. Look at $6's$ children, both better candidates, so your potential candidates become $[3,4]$. Then you'll find only $9$'s going down, which is worse than the solution found with a beam width of $1$.

But if your heuristic is well behaved enough, you might be able to guarantee that increasing the beam width can not degrade the quality of the solution that is found.


How would one reduce HaltTM to ATM Assuming that ATM is decidable, how to build a TM S that uses a TM R that takes as input  and decides if M accepts w, to decide HaltTM, which we already know is undecidable, hence ATM isn't decidable.   So how exactly do we go about this?

For the sake of argument we will assume ATM is decidable. Now we are going to show a way to decide HaltTM using ATM decider, and thus reach a contradiction, since we know HaltTM is undecidable.
Details:
Since ATM is decidable then ATM(Complement) is also decidable, We take TM R that decides ATM and another S that decides ATM(Complement), we use those to build X,
given input < M, w > a turing machine description and it's input w, Run R on given input if accepts accept, if rejects then run S on input, if accepts accept, if rejects reject. This way we have insured that X will reject only machines that do not halt,and accepts all others. So we have used ATM decider to decide HALT but HaltTM is undecidable so we conclude that ATM wasn't from the start decidable.


Need help regarding random password generator: Urgent I had generated a random password from a website which unfortunately has put me into trouble.

The password contains 26 characters which includes alphabets, numbers and special characters. My trouble started when it was found that among the 26 characters there was a 4 letter Malayalam word (spelled in English) which is interpreted to be abusive, followed by an exclamation mark and then again followed by 3 alphabets which unfortunately consists of the initials of the person to whom I had sent the password.

How can I make others believe that this can be auto generated using a random password/string generator algorithm?

I request those people who are acquainted with such algorithms to please help me in this regard. Those who can help me may please reply at the earliest.

There's really no way to do this. First, the website generating the password would need to be open source, or at least publish what algorithm they use. Supposing they do that, then we would need to know the "inputs" to the algorithm. That would depend on their source of randomness: it might be the microsecond that your query was submitted, or it might be random mouse movements, or it might be random atmospheric data. It's also possible that the website uses some "secret salt" in addition to the randomness source, so that their results can't be replicated from the randomness alone.

Really, we have two situations. Either the password can't be recovered/explained, because the website is using proper security to make sure that your password is secret. Or, you can fully recreate the inputs to the algorithm, in which case someone else could, meaning that your password isn't very secure.

There is a third possibility, which is that this website isn't legitimate, and it's deliberately returning things with Malay profanity. I'd try generating another password to see. But in all likelihood you're just terribly unlucky.


Find path to point and avoid bear I'm so far a self taught programmer who's mostly been working on simple web and app development. But now my teacher wants me to enter a school competition in programming.
Of course the competition is based on problem solving and such, areas I'm guessing counts as computer science.
Even though I don't have much experience with this kind of problem solving I have been getting along quite well through the exercise problems.

Unfortunately I'm now completely stuck on one of the harder exercises and I could really use some help.

The problem is as follows:
You're in a cave which can be represented as a grid which size is defined by w and h, the cave also has walls inside it. Your goal is to get to the exit without the bear, who's also in the cave, reaching you.
You are able to move only one step at a time and you have to move every tick. The bear is able to two steps at a time to reach you.

But the bear is a bit stupid. First it moves horizontally until it's in the same column as you and then it continues by moving vertically until it reaches you. The bear is not aware of the walls and simply walks right into them.

The output should be a sequence of movements defined as U: up, L: left, D: down and R: right.

I'm currently programming in python but I'm not to interested in a real implementation. I would much rather have directions on how to think and reason to solve these kinds of problems.

I have a few test-cases if needed.

The obvious approach for typical path finding problems such as this one is that you store the state of the problem in a data structure, usually a lookup array.

In this case, you will have 2 variables, one for your position and one for the bear's position. Since the bear's movement is dependent on other factor, you can do a top down search approach and recursively check your options.

The running time will be polynomial to the size of the grid which will be $O((wh)^2)$.
There might be other optimizations, but this will be the general direction.


Recurrence of T(n) = T(n/3) + T(2n/3) I've searched online for this but I only seem to find answers for a similar equation:

T(n) = T(n/3) + T(2n/3) + cn

But the one I'm trying to solve is:

T(n) = T(n/3) + T(2n/3)

Base case: We can assume T(a) = Theta(1) for any constant a.

I've succeeded in proving (by induction) that T(n) = O(n*log(n)). I thought the answer should be Theta(n*log(n)), but I cannot prove that T(n) = Omega(n*log(n)).

So my question is - am I correct that the answer is O(n*log(n)), and NOT Theta(n*log(n))? IF that's true that would really be great...

If I'm wrong I will of course explain where I'm stuck in the induction process...

Thanks!

P.S. If you need to, please try to explain using induction, because I haven't learned all methods for solving these problems yet.

Hint: Suppose that $T(m) \leq Cm$ for all $m < n$, and that $n$ is divisible by $3$. Then
$$ T(n) = T(n/3) + T(2n/3) \leq C(n/3) + C(2n/3) = Cn. $$
Use this to obtain a good bound on $T(n)$ when $n$ is a power of $3$.


How is conditional jump implemented in the CPU? After reading the question I'm still not sure how CPU does branching.
I understand that we have an instruction counter which points to the current instruction. And after performing conditional jump it either stays the same (increments as usual) or increases (jumps) and points to another branch, that's clear.
The problem: to define conditional jump we need a conditional jump? I mean in order to evaluate an IF the processor has to evaluate condition and IF it's true, then jump, otherwise not. It's an endless recursion.
So how does the conditional jump work on the lowest level?

The problem: to define conditional jump we need a conditional jump? I mean in order to evaluate an IF the processor has to evaluate condition and IF it's true, then jump, otherwise not. It's an endless recursion.

Processors have some level of code that is directly executed, by hardware circuits. That might not be the same level that they expose as their ISA, processors may translate ISA-level instructions into some other form before really executing them or even treat ISA-level instructions as small subroutines that are implemented in micro-code, but there is still some level is not interpreted in terms of something else and built into the physical structure of the hardware.
Below is a diagram of a simple processor. The "if" in the logic of "if we need to branch then take PC+offset as next PC, otherwise take PC+4" is implemented by the top left multiplexer (labeled Mux). A multiplexer does not actually "do one thing or the other", it combines two signals and a control signal via the formula: (~condition & a) | (condition & b). That's just a boolean formula that can be implemented easily as a physical circuit.


Approaches to Solve PDA There is a saying by Computer Science Professor's everywhere :

PDA Checks the intelligence of Students, as certainly there is no approach except power and imagination
of mind to solve problems and design PDA...

While thinking today i thought How can we design automata of a^2n b^(2n-1)

I tried my best :
For example let q0 is initial state and top of the empty stack has Z.

So, Let say Transition of (q0, a , Z) = (q1,Z)

            Transition of (q1, a , a) = (q1,a)

            Transition of (q1, b , a) = (q2,-)

            Transition of (q2, $ , Z) = (qf,Z)

I was able to solve this problem all of a sudden...

My doubt is still the same, How to be the best in solving PDA problems and Is there any way
to define a strategy to solve problems ?

P.S. Your comments are welcome if i did something wrong in above stated question

One technique is to start out with a context-free grammar, and apply an algorithm to get a corresponding PDA. Often, writing a grammar might be a bit easier than writing the PDA directly. In this case, it seems (to me) to be fairly easy to arrive at the grammar $S \rightarrow aaSbb \mid aab$, from which a PDA follows by construction (see this, for example, for some info on how to do such a conversion, if this is new to you)

If you want to build the PDA directly, another way to think about it is to start from the end of strings, and ask yourself what needs to be on the stack to make it easy to tell you need to accept the string. In your case, if you're looking at the last part of the string - say, you've started seeing $b$'s, what would it be really helpful to have on the stack? Well, the easiest thing would be to have $2n-1$ symbols on the stack. If we can arrange that, then when we get to $b$'s we can simply pop one symbol off the stack for every $b$ we read, and accept if the stack is empty when we're done with the input. How can we leave $2n-1$ symbols on the stack after reading $2n$ of the $a$ symbol? Well, we could put a symbol on the stack each time we read an $a$, and then, before we start reading $b$'s, remove one symbol from the stack. We get three phases to the computation: (1) read an even number of $a$'s and push a symbol onto the stack for each $a$ you read; (2) remove one symbol from the stack; (3) read $b$'s until the stack is empty and/or you run out of input. We'd get a PDA like this:

q    s    e    q'    s'
--   --   --   --    --
q0   Z    a    q1    aZ
q0   a    a    q1    aa
q0   a    -    q2    -
q1   a    a    q0    aa
q2   a    b    q2    -
q2   Z    -    q3    Z

We have start state q0 and accepting state q3. Entries of - in the e column indicate $\lambda$-transitions, whereas entries of - in s' indicate popping a symbol off the stack.


Does every undecidable problem contain a decidable subset? I know being a decidable language doesn't necessarily mean that every subset is of it is decidable, but does every undecidable language contain a decidable subset?

Yes. The empty language is decidable and subset of every other language.
You can also say that every undecidable language has a superset which is decidable ($\Sigma^\ast$ for example).


Why Iterative-Deepening-DFS requires O(b*d) memory? After reading about iterative deepening depth-first search on Wikipedia, I could understand that it just limits the depth upto which dfs can go in one iteration/call.

However, I could not understand why it is said that it requires $O(b \times d)$ memory, where $b$ is fan-out of nodes i.e. children and $d$ is max-depth.

Since it is just doing DFS multiple times, it should also only need $O(d)$ memory.

Thinking more, I thought that may be the entire graph can not be put in memory and $O(b\times d)$ is the part of graph required to be kept in memory. But does that make DFS also have $O(b\times d)$ memory requirement ? But even this does not like a good argument, because since during traversal if we are fetching the new nodes from some storage, we can do so also with $O(d)$ memory.

Also the Wikipedia page examples lead me to infer that it does not store visited[node_id] information about the nodes which stores whether node with id node_id is visited till now or not. This made me infer that graph is big.

Edit: After thinking further i think that it is right about $O(b \times d)$, since it is iterative-dfs rather than recursive-dfs. In recursive-dfs we usually take memory used by function call stack for granted. In iterative-dfs, we can find right memory-requirements. Since, now we can not implicitly remember back-tracking, we have to put all children on the stack and hence if we are going to $d$ levels, we need $O(b\times d)$ memory.

You need $\Theta(d \lg b)$ memory in order to store where in the tree you are: a position at depth $d$ in the tree is given by $d$ integers in the range $1\ldots b$ indicating for each branch in the tree which particular child you're looking at.

You could think of it as a set of directions of how to get from the root node to the current child. For example: at the root, take the 2nd child, then take the 5th child of that node, and so on.

When you're doing DFS, you need this information: once you've considered all children of a node at depth $d$, you need to go back to the previous node at depth $d-1$ and consider its next child, but you can only get to its next child by knowing what child you're currently looking at.

It's not clear why Wikipedia says $O(bd)$.  Perhaps this is a mistake in the Wikipedia page.


Clever memory management with constant time operations? Let's consider a memory segment (whose size can grow or shrink, like a file, when needed) on which you can perform two basic memory allocation operations involving fixed size blocks:

allocation of one block
freeing a previously  allocated block which is not used anymore.

Also, as a requirement, the memory management system is not allowed to move around currently allocated blocks: their index/address must remain unchanged.

The most naive memory management algorithm would increment a global counter (with initial value 0) and use its new value as an address for the next allocation.
However this will never allow to shorten the segment when only a few allocated blocks remain.

Better approach: Keep the counter, but maintain a list of deallocated blocks (which can be done in constant time) and use it as a source for new allocations as long as it's not empty.

What next? Is there something clever that can be done, still with constraints of constant time allocation and deallocation, that would keep the memory segment as short as possible?

(A goal could be to track the currently non-allocated block with the smallest address, but it doesn't seem to be feasible in constant time…)

With fixed-size blocks, what you have described is a free list. This is a very common technique, with the following twist: the list of free blocks is stored in the free blocks themselves. In C code, it would look like this:

static void *alloc_ptr = START_OF_BIG_SEGMENT;
static void *free_list_head = NULL;

static void *
allocate(void)
{
    void *x;

    if (free_list_head == NULL) {
        x = alloc_ptr;
        alloc_ptr = (char *)alloc_ptr + SIZE_OF_BLOCK;
    } else {
        x = free_list_head;
        free_list_head = *(void **)free_list_head;
    }
    return x;
}

static void
release(void *x)
{
    *(void **)x = free_list_head;
    free_list_head = x;
}

This works well as long as all allocated blocks have the same size, and that size is a multiple of the size of a pointer, so that alignment is preserved. Allocation and deallocation are constant-time (that is, as constant-time as memory accesses and elementary additions -- in a modern computer, a memory access can involve cache misses and even virtual memory, hence disk accesses, so the "constant time" can be quite big). There is no memory overhead (no extra per-block pointers or things like that; the allocated blocks are contiguous). Also, the allocation pointer reaches a given point only if, at one time, that many blocks had to be allocated: since the allocation prefers using the free list, the allocation pointer is increased only if the space below the current pointer is clock full. In that sense, this is an optimal technique.

Decreasing the allocation pointer after a release can be more complex, since free blocks can be reliably identified only by following the free list, which goes through them in unpredictable order. If decreasing the big segment size when possible is important to you, you could want to use an alternate technique, with more overhead: between any two allocated blocks, you put a "hole". The holes are linked together with a doubly-linked list, in memory order. You need a data format for a hole such that you can locate the hole start address by knowing where it ends, and also the hole size if you know where the hole begins in memory. Then, when you release a block, you create a hole which you merge with the next and the previous holes, rebuilding (still in constant time) the ordered list of all holes. The overhead is then about two pointer-sized words per allocated block; but, at that price, you can reliably detect the occurrence of a "final hole", i.e. an occasion to decrease the big segment size.

There are many possible variations. A good introductory paper is Dynamic Storage Allocation: A Survey and Critical Review by Wilson et al.


All finite languages can be decribed using a regular expression? I have a question.
All finite languages can be decribed using a regular expression?

Suppose that a finite language consists of words $w_1, w_2, \dots, w_n$.

Then what do you think the regular expression ^(w1 | w2 | ... | wn)$ matches?


Find all nodes on simple paths between two nodes in cyclic directed graph Given two nodes U and V in a cyclic directed graph, how can I find the set of nodes that are part of a simple path from U to V?

Attempt 1

I've tried using a DFS from U that stores the set of visited nodes when V is reached, and backtracks when a cycle is detected. But this algorithm must traverse all paths, and can hence be very slow for large graphs.

I cannot stop the DFS early when a node that has already been deemed to be part of a simple path is reached:

If the DFS goes U -> A -> B -> C -> D -> E -> V, those nodes are deemed to be part of a simple path. After backtracking to E and traversing to F and A, a cycle is found. After backtracking to U and traversing to C, a node that is already part of a simple path is found, but the DFS cannot stop, since further traversal is necessary to figure out that F is also part of a simple path: U -> C -> D -> E -> F -> A -> V.

The same argument shows that I can't stop the DFS early when a node that has already been deemed to be part of a cycle is reached.

Attempt 2

Another idea I've tried is to store on the edges sets of potential cycle root nodes that must be traversed in order to reach V from the edge's sink. For instance for the edge E -> F, A must be traversed in order to reach V. Hence the DFS does not have to traverse this edge if A has already been visited.

It is not straight-forward to decide which nodes are potential cycle roots, and on which edges they need to be stored. My implementation attempts have unfortunately been too slow for large and complex graphs. After the potential cycle roots have been calculated, however, performing the DFS has been fast.

Question

Are there any efficient algorithms for finding the set of nodes that are part of a simple path between two nodes?

Examples

Just to make things really clear, these are the outputs I am looking for for a few different graphs:

Example 1

Nodes that are part of simple paths: U, A and V.

Example 2

Nodes that are part of simple paths: U, A, B, C, D, E and V.

Example 3

Nodes that are part of simple paths: U, A, C, D, E, F and V.

Example 4

Nodes that are part of simple paths: U, A, B, C, D, E, F and V.

This problem is NP-hard. It is actually NP-Hard to prove if a vertex $w$ lays on a simple path from $u$ to $v$. Here is a prove of hardness through a reduction from the two disjoint paths problem.

Given a directed graph $G = (V, E)$ and two pairs of vertices $(s_1, t_1)$ and $(s_2, t_2)$, we build the new graph $G'$ by adding a new vertex $w$ to $G$ and add an edge from $t_1$ to $w$ and an edge from $w$ to $s_2$. The new graph admits an $s_1, t_2$ simple path passing through $w$ if and only if the original graph admits two disjoint paths one from $s_1$ to $t_1$ and the other from $s_2$ to $t_2$. Try to prove this claim as an exercise!


Path with least max-weight, in an undirected connected graph The problem we were given, states that we have graph, where vertices are cities, and edges are roads. Each edge has a weight equal to the kilometers of the corresponding road. We want to get from city $A$ to city $B$, with a car that can last up to $M$ kilometers in one go, but we can refuel, every time we go to a city. It isn't mentioned, but i guess we can't suppose that the graph is acyclic, since it represents a country's map.

We need to find two algorithms that give as the least $M$ our car needs to have to get from a city $A$ to city $B$. One should have time complexity $m\log m$, and the other one linear (where $m$ is the number of edges).

I thought that we could use BFS/DFS for that, but they aren't what we are looking for, because of the complexity. The only other thing I came up with is using Kruskal algorithm somehow, because it has the complexity we want, and also the graph is connected, so maybe we have less things to worry about. As for the linear one, I can't find anything.

This problem is known as the minimax path problem. A linear time algorithm is given in this note. I quote it here. Note the note solves the bottleneck shortest path problem, and to solve your original minimax path problem, you should reverse the sense of all the weight comparisons performed by the algorithm, or equivalently replace every edge weight by its negation.

  The correctness of Algorithm 1 (for undirected graphs) is rather obvious: If in line 6 it turns out that the graph still is $s$–$t$–connected, than hiding the edges of weights less than $M$ in line 5 did not affect the optimal solution. Otherwise, in each subgraph to be shrunken in line 9, every vertex can be connected to every other one by a path with capacity at least $M$; thus the bottleneck of $t$ (being smaller than $M$) will remain the same in the shrunken graph.

  Furthermore, the algorithm runs in time $O(m)$, where $m = |E|$ denotes the number of edges: The crucial observation is that in every iteration of the loop in lines 3–11 half of the edges are removed from the graph, either by shrinking all "thick" edges (in line 9) or by dropping all "thin" edges (in line 5). As all steps inside that loop can be done in linear time in the size of the current graph, the total running time is bounded by
  $$O(m)+O\left(\frac{m}{2}\right)+O\left(\frac{m}{4}\right)+\cdots=O(m).$$
  This shows the following result.


Software to hardware I am a layman in computer science.
How do the command we input in a computer, which is a software component, changes into a hardware component. For example, if I want to play a song, I will just click the song and the audio starts to emit from the speakers. So how does in general these things happen?

First you move your mouse. Most mice now in days works using a laser, the laser is able to tell it's moving over a surface, inside the mouse the data from the laser is being turned into digital signals, that are then sent through the cord or through Bluetooth or whatever system you use to the computer. The computer meanwhile is expecting to get signals like these, it's constantly checking to see if it's gotten a new signal from the mouse, and when it does it knows how to interpret those signals to move the pointer on your screen.

Now you click on an icon, and that is then the mouse sending a different signal for a click or double click, the computer registers the click and then figures out what do to handle the click, since your mouse was above an icon, lets say a music file you have sitting on your desktop, it knows to try and open or run that file.

To determine what exactly it means to open or run the file it may look at a few different things, you may have some settings for that file that you've set which tell it how to open, but more generally it goes based on the extension. Let's say it's a .mp3 file, well you probably have a default music player app, and the computer knows to open that app and gives it some information about the file you clicked, I'm not sure on the format, but it probably gives it the name and location of the file you clicked on. The music player app now takes that file and assuming it's correctly formatted as an mp3 then it will know how to read the data in the file, and it will parse through that data and start to send messages back to the operating system telling it to output sound.

The OS now will send data about what sound needs to be played to whatever the default or current audio device you have, lets say they are speakers. The speakers will receive these signals and know what sort of sounds to put out, and then they have components in them that can vibrate in different ways, and they are told how to vibrate by the singles that were sent and thus sound is emitted.


Is it possible to find a supersequence of a single array? In Jeff Erickson's Algorithms textbook, the chapter on Dynamic Programming asks you to "Describe an efficient algorithm to compute the length of the shortest
oscillating supersequence of an arbitrary array A of integers".

A supersequence contains all of the elements from the original array X[1...n], and oscillating is defined as X [i] < X [i + 1] for all even i, and X [i] > X [i + 1] for all odd i.

However, I am not asking about the answer to this problem. I am just wondering if this question even is sound. How can you find a supersequence of a single array? Wouldn't the answer just be the length of the original array if all elements are oscillating? Else, 0. Usually, a supersequence is found between multiple arrays.

What about the array $[1, 3, 5]$? The supersequence $[0,1,0,3,0,5]$ is oscillating while the original sequence isn’t. In fact you can make an oscillating supersequence of any array by inserting $\min(arr)-1$ before every element of the original array.


Heap down - What is math logic and intuition behind $\sum_{i=1}^{\log n}(\log n - i) \times 2^i $ In heap (bubble down) we have the formula :
\begin{eqnarray*}
  \sum_{i=1}^{\log n}(\log n - i)\times 2^i & = & \log n\sum_{i=1}^{\log n}2^i -\log n\sum_{i=1}^{\log n}i\times2^i \\
& = & \log n\times2^{\log n+1}-(\log n\times2^{\log n+1}-(2^{\log n+1}−2)) \\
& = & 2n−2\in Θ(n)
\end{eqnarray*}

Why we have $\sum_{i=1}^{log(n)}(\log n - i)\times2^i$ ?
How we get to $2−2\in Θ()$ ?

Please explain details!

So I guess you are showing that a complete binary tree can be made a heap in linear time.

$(\log n - i)$
counts the maximum number of swaps that a node may require, starting at level $i$, and descending to its final level; at most it could become a leaf. For instance if it starts at level $0$, then it could possibly require $\log n$ swaps; this would happen if the node placed at the root position becomes a leaf, since $\log n$ is the full height of the binary tree. And since level $i$ has up to $2^i$ nodes, $(\log n - i)2^i$ counts the maximum number of swaps for all nodes from level $i$, and $\sum\limits_i (\log n - i)2^i$ counts the maximum number of swaps for all nodes in the tree.
$2n-2$ is asymptotically $\leq 2n$ and $\geq n$; for instance $n\geq 2$ suffices. This is exactly the definition of $\Theta$.


Algorithm to generate all planar graphs Is there an algorithm which provides a sequence of all simple planar graphs, unique by graph isomorphism? For instance: first all planar graphs with 1 node, then all planar graphs with 2 nodes, etc.

Note: It is okay if it generates only graphs with a minimal node degree of 1 or 2.

One approach would be to enumerate all graphs of a given size, then test each one to see if it is planar and filter out the non-planar ones.  This might work acceptably if you only want very small graphs.

Brendan McKay has a collection that enumerates all non-isomorphic planar graphs of size up to 11, which you could download and use directly.  There are about 16 million different planar graphs of size up to 11, so if you're lucky you might not need to consider anything larger and that collection will be adequate.


Proving $({L_A}^* L_B)^+ = (L_A \cup L_B)^*L_B$ I'm trying to prove the following identity:
$$ ({L_A}^*\  L_B)^+ = (L_A \cup L_B)^*L_B $$

which is clearly true as both sides will exactly match "any sequence of A and B ending with B" :

$$ B, AB,AAB, ABBABAB, ... $$

I tried thinking about the set properties and even tried to reasoning about the NFA constructed by the the two sides of the equation but to no avail so far.

Does anyone know how to prove it?

Although I can't do the proof completely right now, maybe looking at $(L_A^* L_B)^+ \subseteq (L_A \cup L_B)^*L_B$ and $(L_A \cup L_B)^*L_B \subseteq (L_A^* L_B)^+$ helps here. So from left to right: If you take a word $w \in (L_A^* L_B)^+$, can you split it up into $0..m$ subwords of the form $(L_A \cup L_B)$ and one postfix-subword of form $L_B$? I hope this helps you.


Why do we prove X is in NP to prove it is NP-complete? The steps to show something is NP-complete is to show it is a member of NP, and then show an NP-complete problem reduces to it in polynomial-time. Why is the first step necessary? Is it possible to reduce an NP-hard problem to an NP-complete problem in polynomial time? Because that would be the only instance in which this is important.

The short answer is that it's because that's the definition of being $\mathsf{NP}$-complete.

Recall that for a problem $\Pi$ to be $\mathsf{NP}$-complete we need the following:

$\Pi \in \mathsf{NP}$.
There exists an $\mathsf{NP}$-hard problem $\Phi$ such that $\Phi \leq^{P}_{m} \Pi$ (where $\leq^{P}_{m}$ is a polynomial time many-one mapping).

What happens then if we leave out condition 1?

In that case "all" we've shown is that $\Pi$ is $\mathsf{NP}$-hard.

Even if we restrict $\Phi$ to being an $\mathsf{NP}$-complete problem, we can still reduce it to problems that are much harder. For example it's trivial to map 3-SAT to QBF-SAT, but QBF-SAT is compete for $\mathsf{PSPACE}$, so definitely not $\mathsf{NP}$-complete unless there's a rather large collapse (at least $\mathsf{NP} = \mathsf{PSPACE}$).

Going further (and thanks to David Richerby for being sensible), there are versions of $\mathsf{NP}$-complete problems that are $\textsf{NEXP}$-complete, for example SUCCINCT 3-SAT is a generalisation of 3-SAT (the reduction from 3-SAT to SUCCINCT 3-SAT is less obvious, but not tricky). However we know unconditionally that $\mathsf{NP}\neq \mathsf{NEXP}$, so SUCCINCT 3-SAT is not in $\mathsf{NP}$.

As you note, it is unlikely that we can reduce, in polynomial time, an $\mathsf{NP}$-hard problem that's unlikely to be in $\mathsf{NP}$ to a problem in $\mathsf{NP}$ (again, it would imply some collapse in complexity classes). Where you went off track is identifying this as the only important case.


Is a finite Solomonoff learner worse than human learning? An elegant program for a bitstring is the shortest program on a universal Turing machine that outputs this bitstring.  According to Kolmogorov complexity, the length of the elegant program is independent of the Turing machine implementation.

Solomonoff induction uses the elegant program for a bitstring to predict the next digit.
This is a universal prior given the minimal assumption the output is generated by a Turing machine.

We can use this insight to build a machine learning algorithm called a finite Solmonoff learner.
The difference between a finite Solomonoff learner and the original Solmonoff induction algorithm is the finite learner does not have access to all elegant programs.
There is no algorithm that can generate all the elegant programs, so the elegant programs the finite learner can use must be stored in memory.
With a finite amount of memory, there is a limit to the elegant programs that can be stored and consequently used by the finite learner for prediction.

The limit exists because there are a finite number of elegant programs of a certain length L.  When the bitstring of 1s becomes long enough, it is not possible for there to be an elegant program representing the bitstring to be of length L or shorter.
If L is the amount of memory available, then eventually the elegant programs will all be longer than L, and none will fit in memory.

Now let's assume we have a very long string of 1s, and we remove one digit to make a prediction problem.

As a concrete example, our bitstring is:

11111111111111111111

We remove a 1 at random:

111111111111111_1111

The learner must figure out the most likely digit to go in the empty spot.

For a given amount of memory we can make the bitstring of 1s long enough that its elegant program cannot fit in memory.
In this case, the finite Solomonoff learner will not be able to access the elegant program for the bitstring, and will thus be incapable of predicting the digit that goes in the empty slot.

To continue the example, assume the elegant program that generates the 1s is:

10001011

Furthermore, the amount of memory available is 7 bits.  Consequently, the 8 bit elegant program cannot be stored in memory, and the finite learner cannot figure out what goes in the empty slot.

On the other hand, regardless of how long the bitstring of 1s becomes, a human will have no problem identifying the missing digit.  A human has finite memory and cannot access all elegant programs to make predictions.  Despite having the same handicap as a finite learner, the human can outperform the finite learner infinitely often.

Does this demonstrate Solomonoff learning is less powerful than human learning?

Your suppositions are wrong.  A finite Solomonoff learner can learn the all-1's string.  There does exist a learning algorithm that can output a program for the all-1's string.

Consequently, this example does not demonstrate that Solomonoff learners are necessarily worse than a human being.  They might be; but this example doesn't prove that.

For instance, consider the following learning algorithm: if the inputs is all-1's, then output a program that only outputs 1's (e.g., 10001011 in your example), otherwise do something arbitrary.  This is a trivial algorithm, but it demonstrates that there does exist a learning algorithm that can learn that sequence.  In other words, you've given an example of an input sequence that both a human can learn and a finite Solomonoff learner can learn.

What you might have shown is that if we restrict the learner to a very limited amount of memory, then the learner might not be able to learn some things that a human can.  But that's a rather uninteresting conclusion.  Of course we know that if you severely restrict the memory of the computer, that limits what it can compute.  For instance, if we limit the memory of the algorithm to only 7 bits, then the algorithm must act like a finite-state machine with at most 128 states, which severely limits the patterns it can find.  A human can learn sequences that can't be recognized by a finite-state machine with 128 states.  That's not surprising, and doesn't really have any interesting implications for whether finite Solomonoff learners are worse than human learning.

There's no point in comparing a human to a computer algorithm that has been massively handicapped.  To make the comparison interesting, you must allow the computer algorithm to have reasonable access to the resources that any computer would have; otherwise you have trivialized the question.  This means allowing the computer learner a non-trivial amount of memory.  And once you do that, the learner no longer has any difficulties with your sequence.

There are other issues in your post.  If you are assuming that the only possible approach is to try all possible algorithms until you find one that works, that's not the case.  More seriously, the problem of "given a sequence, find the elegant program for it" is not computable, so if you require the learner to find the shortest possible program, you've created an impossible problem.  Finally, where you say that "According to Kolmogorov complexity, the length of the elegant program is independent of the Turing machine implementation.", but that's not correct.  What is true is that changing the universal Turing machine will change the length by only a constant... but if you care about constants, that might be important.


Two-way Hash Functions While I'm aware most (good) hash functions are one-way (or at least mostly so), I'm wondering if there's any construct (not necessarily called a hash function) which behaves in many ways like a hash function, but can be easily reversed.

For example, a function $f$ takes an arbitrary string $x$ and maps it to $y$, where $|y| = c$ for some constant $c$ (i.e. $y$ is always the same length), and collisions are infrequent, so in general, $f(x) = y$.

In this case, I'm wondering if it's possible to construct a function $f$ matching the criteria above, but where $f^{-1}(y) = x$ is as easily calculable as $f(x) = y$, in a computational complexity sense.

In the case of collisions, where $\forall x \in S$,  $f(x) = y$,  $f^{-1}(y)$ might give you either the entire set $S$, some subset of $S$, or even a single element from $S$

In the case that this is not theoretically possible, possibly due to the fact that $f$ allows strings of arbitrary lengths and $|y| = c$, so infinite collisions must occur(?), then what if we only allow $|x| < C$, such that the number of possible collisions are finite?

Obviously, you wouldn't use this kind of function for anything security related, but it might be useful for something like reverse image searching?

Yes, this is possible.  Here are two examples of such a function.

One function is $f(x)=x$.  This has no collisions, and the function is easy to invert.

Here is another function:  define $f(x) = x$ if $x$ is 256 bits long, otherwise $f(x) = \operatorname{SHA256}(x)$.  Then it is very hard to find collisions for $f$ (since SHA256 is collision-resistant).  At the same time, given $y$, it is easy to find an $x$ such that $f(x)=y$, so we might be willing to say that $f^{-1}(y)$ is easily computable.  To put it another way, given $y=f(x)$ where we are told $y$ but not told $x$, it is easy to find $x'$ such that $f(x')=y$.  The catch is that $x'$ might be different from the original $x$.


Request for examples to show various types of subproblems in dynamic programming Chapter 6 of "Algorithms" by Dasgupta, Papadimitriou, and Vazirani summarizes four types of subproblems that are quite common in dynamic programming. They are

prefix/postfix of a string/sequence/array
both prefixes/postfixes of a pair of strings/sequences/arrays
an interval of a string/sequence/array
a rooted subtree

What are the other types of subproblems (and examples/references) for dynamic programming?

Added: In a comment on this post, JeffE mentioned:

  Tables are sometimes used. Dynamic programming over trees (for example: maximum independent set) doesn't normally use a table [=array] to memoize the recurrence; it uses a tree, or in some cases a tree of arrays, or an array of trees, or in some cases a Cartesian product of trees. Similarly for dynamic programming over dags or dynamic programming over tree decompositions for graphs of bounded treewidth.

I would like to know dynamic programming examples over, e.g., a tree of arrays, an array of trees, a Cartesian product of trees, tree decompositions, or more general graphs.

Everything you need could be found on Topcoder.com (TCC for short).
Start with Dumitru's tutorial.
Done that, you should be able to integrate the DP technique on various structures, like 2D grids, narrow ribbons, convex polygons, etc. to name just a few.
An archive of DP problem on TCC: https://www.topcoder.com/tc?module=ProblemArchive&sc=2&sd=desc&cat=Dynamic+Programming
And the match editorial is the best collection: https://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=archive
I have learnt so much from these. Unfortunately, this editorial series stopped since 2008. From that time on, the SRMs are only discussed in the forum like these more recent SRMs:
https://www.topcoder.com/blog/single-round-match-735-editorials/
A tagged search produces this: https://www.topcoder.com/blog/tag/srm-editorials/
So you may easily access all the recent SRMs.
SRM: Single Round Match (TCC is the arena of online competitive programming)

Please note that TCC has been gone through various reconstruction (since the integration with Data Science market). As a (unwanted) consequence, many links are broken but can be fixed by modifying some middle parts (as often the cases for decades-old websites)