Find a simple path visiting all marked vertices

This problem is close to Steiner tree problem, just by two restriction:

Instead of tree we have path.
Is not necessary to have shortest path which contains required node.

There is a recent work1 on similar topic, the only difference with your problem statement is they are looking for shortest path which contains all required vertices. They name it Steiner Path problem.

1:
Shanti Swaroop Moharana, Ankit Joshi, and Swapnil Vijay. Steiner path
for trees. International Journal of Computer Applications, August
2013. Published by Foundation of Computer Science, New York, USA. (doi)


In the Curry-Howard isomorphism as applied to Hindley-Milner types, what proposition corresponds to a -> [a]?

One way to interpret types as logic is as the existence conditions for values of the return type. So f :: a -> [a] us the theorem that, if there exists a value of type a, there exists a value of type [a]. The implementation of the function is the proof of the proposition.

Here's a more detailed explanation:

Basically, data constructors let us build similar things to sums and products (OR and AND), but we can have multiple variants, and we can specially "tag" the type with a name to distinguish it (like the name List).

They also let us build them recursively: for a proposition $a$, the proposition $[a]$ can be viewed as a solution to the equation
$x(a) \iff \top \vee (a \wedge x(a) ) $

Things become a bit clearer when you write the definition of List using GADT-style, pseudocode similar to what you'd see in Agda:

data List : Type -> Type where
    Nil : ∀ a . List a
    Cons : ∀ a . a -> List a -> List a

This gives us two things: the constructors (or functions), which act as axioms for the propositions of List, and axioms for pattern-matching or deconstructing them.

Roughly speaking, it introduces the following axioms into the logic:

For any proposition $a$, $[a]$ holds.
If $a$ holds, and $[a]$ holds, then $[a]$ holds
If $[a]$ holds, then either $\top$ holds, or $a \wedge [a]$ holds.

These are pretty useless when interpreted as logic, since we always know $\top$ holds, deconstructing there doesn't give us much useful information

Without quantifiers or more powerful type extensions (GADTs, Type Families, dependent types, etc.), you can see that we can't really prove interesting things, which is why you often don't see much about interpreting standard Haskell types as logic.


Hint: Convert the input into $n/m < m$ chunks of length $m$ and sort the chunks. Then use your heap idea. Note that you're using the assumption $m > \sqrt{n}$ so that the heap fits in memory.


Models of computation: the arithmetic model, Turing machine (and ...)

3. There are algorithms which run in polynomial time in the Turing machine model, but not in the arithmetic model. The Euclidean algorithm for computing the greatest common divisor of two integers is one example. If an algorithm runs in polynomial time in the Turing machine, will it run in polynomial time in the arithmetic model?

Polynomial TM running time does not imply polynomial arithmetic running time, nor vice-a-versa.

The issue in the above question lies in the definition of the running time that we are trying to bound. If we expand, we have to say: "...runs (or doesn't run) in the number of steps that is polynomial in the length of encoded input". The catch is that the "steps" and "length of encoded input" are defined differently for the two models.

For a Turing Machine, the encoded input is taken as some concatenation of the binary representations of the input integers with separators. A step is an action of the TM head.
For an arithmetic model, the length of encoded input is defined as the number of numbers occurring in the input. A step is an arithmetic operation.

1. "Polynomial time under TM, but not under AM"

Euclid's GCD is indeed an example. For $a,b, a>b$, input integers, regardless of the model the algorithm takes $O(\log b)$ iterations, with a division at each iteration.

TM: Length of encoded input is then $l_{TM} = 2\log a + 1$ where $a$ is the larger of the two integers. The division in a TM takes $O(\log^2 a)$ steps. Hence, the total number of TM steps is $O(\log^2 a\log b)=O(l_{TM}^3)$ (conservatively speaking). That is, the polynomial $P_{TM}(l_{TM})=l_{TM}^3$ in the length of encoded input bounds the TM running time.
AM: Length of encoded input is constant $l_{AM}=2$. The number of steps is equal to the number of divisions $O(\log b)$. Since the value of any polynomial $P(l_{AM})$ is constant, for any choice of $P(l_{AM})$ we can always find a problem instance that takes more divisions than $P(l_{AM})$. That is, we cannot bound the running time with a polynomial in the length of encoded input.

2. "Polynomial time under AM, but not under TM"

One example is the algorithm that computes $2^{2^n}$ using repeated-squaring where $n$ is given as input in unary encoding (and we treat each unary "tick" as an input number). For both models, input length is $n$ and we need $\log 2^n = n$ multiplications and each multiplication will eventually be multiplying $2^n$-bit numbers.

AM: $P(n)=n$ is a polynomial bound on the number of arithmetic operations
TM: $O(n2^{2n})$ steps, since each $2^n$-bit multiplication takes $O(2^{2n})$

Drawn from a reading of Wikipedia's primary source (and corrected Wikipedia accordingly):

[1] Grötschel, Martin; László Lovász, Alexander Schrijver (1988). "Complexity, Oracles, and Numerical Computation". Geometric Algorithms and Combinatorial Optimization. Springer. ISBN 0-387-13624-X.


design a strange data structure, is it possible?

Let us denote four data structure: $Q$, $PQ$, $R_Q$, and $R_{PQ}$. $Q$ is a FIFO queue. $PQ$ is a priority queue implemented using a Fibonacci heap. $R_Q$ and $R_{PQ}$ are hash-sets. $R_Q$ stores elements that have been removed from the queue but not removed from the priority-queue yet; $R_{PQ}$ stores elements that have been removed from the priority-queue but not the queue yet.
Our operations are insert, delete, and extract-min. For insert, we insert the element into $Q$ and $PQ$.
We implement delete and extract-min lazily. For delete, let x=Q.front().  If $x$ exists within $R_{PQ}$, that means it has been removed from the priority-queue already. We pop $x$ and remove $x$ from $R_{PQ}$. Then, we set x=Q.front() and try again. If $x$ is not within $R_{PQ}$, then this is the element we should remove. We pop $x$ and insert it into $R_Q$.
For extract-min, we essentially do the reverse. We take x=PQ.top() until $x$ does not exist within $R_Q$, and when it does we pop $x$ and insert it into $R_{PQ}$.
Time complexity for insert: $O(1)$ (since we are using Fibonacci heap)
Time complexity for delete: amortized $O(1)$ (hash-sets work in amortized constant, and all our operations are either the deletion or lazy extract-min deletions.)
Time complexity for extract-min: amortized $O(logn)$ (hash-sets work in amortized constant, all our operations are either the deletion or lazy extract-min deletions, but logn factor due to PQ)
Update Code (C++):
struct strange_ds{
    queue<int> q;
    priority_queue<int> pq;
    unordered_set<int> rq, rpq;

    void insert(int x){
        pq.push(x); q.push(x);
    }

    void delete_ele(){
        while(true){
            int t = q.front();
            if(rpq.count(t)){ //already removed from pq
                q.pop();
                rpq.erase(t);
                continue;
            }
            q.pop();
            rq.insert(t);
            return;
        }
    }

    int extract_min(){
        while(true){
            int t = pq.top();
            if(rq.count(t)){ //already remove from q
                pq.pop();
                rq.erase(t);
                continue;
            }
            pq.pop();
            rpq.insert(t);
            return t;
        }
    }
};

Note that the code uses a standard C++ priority queue, which is not a Fibonacci heap, but this can be straight-swapped in. Also, the code assumes that element values are unique, but this can be accounted for in the case that they are not (by associating elements with unique IDs).


The proof is not correct nor complete. You have to show that for every possible splitting of the string to be pumped, where the constraints of the lemma hold, the pumped string does not belong to the language.

You have only showed for one case that the string does not belong to the language and hence that the language is not regular.

But what about this case:

$$ z = x^py^pz^p, take \ i = 0 \ , uv = x^p, \ then \ z = uv^0w \ does \ not \ belong \ to \ the \ language, \ the \ condition \ i+ k > j \ is \ violated $$

You have to show that for every possible splitting of the string to be pumped, where the constraints hold, for some i, the string does not belong to the language.


That's because for the numbers from 10,000 to 99,999 the first digit is equally likely, same for numbers from 1,000 to 9,999 etc.
Benford's law depends on random numbers whose logarithm has a linear distribution over a not too small range. Take random numbers x from 0 to 999,999, then calculate 10^(x/200000) and you'll find that Benford's law will hold.
But measure the height of adult people in feet, and 95% start with 5 or 6, a few percent start with 4, and very few with 7 or 3. It's not a law that applies to every set of numbers. (Measure people in meters, and 98% start with 1, a few with 2, and very few start with a 9 or even 8. )


Median-of-Medians proof for time complexity

Assuming that you got the base covered, here is the inductive step:
$$
T(n) \leq T(n/5) + T(7n/10) + cn \leq 10c(n/5) + 10c(7n/10) + cn = 10cn.
$$
(Cheating a bit, since $n$ isn't necessarily divisible by 10; but that's a problem in the recurrence.)

You can also just apply the Akra–Bazzi theorem.


How do the following Hash Functions compare?

Your question is a bit confusing. These two "hashes" are incomparable.

The reason is that your second function is a specific hash function, while the first formulation is a family of hash functions  (indexed by $a$).

How can you compare the two? Choose $a$ in random and compare the two instances? Compare for the best/worst $a$, maybe? Compare on average (for a uniform $a$)?

Remark: Just to complete the details: Usually (at least, within the crypto-community), when people say "hash function" they actually mean a family of hash function, out of which you pick one instance uniformly. The properties of the hash function is (also) over the probability of selecting the specific function out of the family

As for your other question, the answer is no, in the second hash, the probability is not equal $1/n$ to be in each bucket. Assume that each $x_i$ is uniform in [0..255], then $x_1+x_2$ is not uniform in [0..510]. For instance $P(0)=1/256^2$ (both are 0) while $P(4) = P(0,4) + P(1,3) + P(2,2) + P(3,1) + P(4,0) = 5/256^2$. There's no reason that the sum will be uniform $\mod n$.

Last comment: As explained above, for the first hash, a probability of $1/n$ is over the choice of $a$.


Is solving a quadratic equation using Turing machine impossible?

The problem is not clear enough. Turing Machines can or cannot solve problems if those problems are languages, that means, sets of strings over a finite alphabet. You cannot represent all reals in this way, so it is not even a problem that a TM could even attempt to solve. In the same fashion that world hunger is not a problem in the precise sense that a computational complexity requires it to be.

The problem is obviously solvable if you define it as the sets of words that encode three rational numbers a, b and c in a standard way.  How do you solve this? Well, the construction of the machine that does this is rather complicated, but you know how to do this in let's say, Python, right? So you can always compile your Python code into a TM.


Combining two infinite algorithms to create a single infinite algortihm

Is this idea correct?

(I apologize for my initial, poorly thought-out response to this question, and thank the commentors for pointing out the flaws.)

Your solution will work if $g(\cdot)$ is differentiable around $f(x)$.

Since $G(y)$ converges to $g(y)$, for any constant $\epsilon_G>0$ there exists some $N_G>0$ such that for any $y$ and all $i>N_G$,
$$-\epsilon_G < G_i(y)-g(y) < \epsilon_G.$$

If $g(\cdot)$ is differentiable around $f(x)$, there exists constant $\epsilon_f>0$ such that $g(y)$ slopes toward $g(f(x))$ for all $y \in \left(f(x)-\epsilon_f, f(x)+\delta_g\right)$. Because $F$ converges to $f(x)$, there exists some $N_F>0$ such that for all $i>N_F$,
$$-\epsilon_f< F_i(x) - f(x) < \epsilon_f.$$

Since $g(\cdot)$ slopes toward $f(x)$ in the neighborhood containing all $F_i(x)$ for $i>N_F$, as $F(x)$ approaches $f(x)$, $g(F(x))$ approaches $g(f(x))$; i.e., $g(F_i(x))$ converges to $g(f(x))$. That is, for any $\epsilon_g>0$, there exists some $N_g>N_F$ such that for all $i>N_g$,
$$-\epsilon_g < g(F_i(x)) - g(f(x)) < \epsilon_g.$$

Now let $y=F_i(x)$. For any $\epsilon>0$, set $\epsilon_G = \epsilon_g = \frac{\epsilon}{2}$. Then for all $i>N$ (where $N=\max(N_G, N_F, N_g)$),
$$-\epsilon = -(\epsilon_G+\epsilon_g) < G_i(F_i(x))-g(F_i(x)) + g(F_i(x)) - g(f(x)) < (\epsilon_G+\epsilon_g) = \epsilon,$$
or,
$$-\epsilon < G_i(F_i(x)) - g(f(x))) < \epsilon.$$
That is, $G_i(F_i(x))$ converges to $g(f(x))$.

Is there a better idea?

Probably. Your algorithm generates $O(i)$ numbers to create the $i$th output number.

Consider if the algorithms were finite (i.e., you stopped at the $n$th output). Then, you would run $F$ to $F_n(x)$, then run $G$ using this as your input. This would only take generating $O(n)$ numbers. Your problem is not finite, though.

However, you can choose some constant $c$ and only restart $G$ after every $c$ steps. That is, the $i$th output will be $G_i(F_{c\lfloor i/c\rfloor}(x))$. This will make the convergence less smooth, but it will help your running time; it will now only generate $O(i/c)$ (amortized) numbers to create the $i$th output number.


What untyped term inhabits induction on natural numbers in CoC?

Yes, there is such an untyped function, and it turns out that it is equivalent to the untyped erasure of iteration for church numerals.

The Cedille project has been doing lots to give types to these functions, and the core concept there is the dependent intersection, which provides a limited form of self reference that is enough to derive induction principles.
This paper will probably interest you.

If you have $fix$ you can definitely implement induction principles, using structural recursion on the natural number. This is how they do it in CiC and Coq, with an extra restriction that the recursive calls must be on a structurally smaller value. Without this condition, you can write induction, but you also can write nonterminating terms with the same type as an induction principle.


Number of MUX required for Cache Mapping

A multiplexer can output only a single bit on output line.
So, to output one complete tag to the comparator ,

Number of multiplexers required = Number of bits in the tag. (say T)

If there are k lines in one set, then number of tags to output = K,

thus ,

number of multiplexers required = Number of lines in one set (K) x Number of bits in the tag(T).

TOTAL MUX REQUIRED = K*T


Why polynomial time is called "efficient"?

Another perspective on "efficiency" is that polynomial time allows us to define a notion of "efficiency" that doesn't depend on machine models. Specifically, there's a variant of the Church-Turing thesis called the "effective Church-Turing Thesis" that says that any problem that runs in polynomial time on on kind of machine model will also run in polynomial time on another equally powerful machine model.

This is a weaker statement to the general C-T thesis, and is 'sort of' violated by both randomized algorithms and quantum algorithms, but has not been violated in the sense of being able to solve an NP-hard problem in poly-time by changing the machine model.

This is ultimately the reason why polynomial time is a popular notion in theoryCS. However, most people realize that this does not reflect "practical efficiency". For more on this, Dick Lipton's post on 'galactic algorithms' is a great read.


It's not answerable in the abstract, without a lot more specifics.  It depends on intimate specifics of the computer architecture, what counts as "one" operation, how the tree is represented, and many other details that are usually considered a distraction for purposes of analysis of algorithms.  And it wouldn't really be useful in practice anyway; these days, the time it takes for an algorithm to complete depends on a lot more than the number of operations.  Not all operations take the same amount of time, and more importantly, the memory hierarchy plays a huge role in influencing the running time, and you can't measure its impact by counting operations.


You can solve this with DP. Let $DP[n][k][m]$ denote the number of partitions of $n$ into $k$ numbers, all of which are distinct and at most $m$. Then we have the recurrence

\begin{align}
DP[n][k][m] &= \sum_{v = 1}^{m} DP[n-v][k-1][v-1]\\
&= DP[n][k][m-1] + DP[n-m][k-1][v-m]
\end{align}

Since we can take the numbers forming the partition from largest to smallest, so whenever we take some number, all numbers we take after it must be strictly smaller. The base case is $DP[0][0][m] = 1$ for any $m$ and $DP[x][y][m] = 0$ whenever $x < 0$ or $y < 0$. If you care about the order of the elements in the partition, multiply the result by $k!$.

We can calculate this recurrence in $\mathcal{O}(n^{2} k)$, but tighter analysis gives an even better bound:

For a state $(n', k', m')$ to be reachable by this recurrence from $DP[n][k][n]$, we must have $m' \leq \frac{n-n'}{k-k'} \leq \frac{n}{k-k'}$ (since our number decreased by $n - n'$, so some number in the current partition of sum $n - n'$ and size $k - k'$ must be at most $\frac{n - n'}{k - k'}$). But this means that for any fixed $k'$, there are at most $\frac{n^{2}}{k-k'}$ reachable DP states, and

\begin{equation*}
\sum_{k' = 0}^{k-1} \frac{n^2}{k-k'} = \mathcal{O}(n^2 \log k)
\end{equation*}

Thus the actual complexity is $\mathcal{O}(n^2 \log k)$.


Exploration in reinforcement learning when state space is huge

In the Atari paper, an $\epsilon$-greedy strategy is used for state-space exploration. This means that the algorithm makes the deep network learn a greedy strategy to pick an action that maximises the $Q$-value of the current state ($a = max_a Q(s, a; \theta)$. At each time-step in a game, the agent picks an action as per this greedy strategy with probability $1-\epsilon$ and it picks a random action to explore the state-space with probability $\epsilon$.
The value of $\epsilon$ can be varied depending on whether we want the agent to explore more ($\epsilon$ value high) or learn from its past behaviour more ($\epsilon$ value low).
In the paper, the authors mention that $\epsilon$ is annealed linearly from 1 to 0.1 over the first million frames, and fixed at 0.1 thereafter.


Calculating attributes' values in the semantic analysis stage

The computer is using the rules in the left-hand column of your table. This amounts to a bottom up approach: to compute the value of a node you first compute (recursively) the values of all its children, and then you use the given rule to compute the value of the node itself.


Proving that the recurrence $T(n) = 2T\left(\frac{n}{2}\right) + 1$ with $T(2) = 1$ is asymptotically $O(n)$

If you can solve a recurrence exactly, then there isn't much motivation to solve it approximately, unless the solution is much easier.
Nevertheless, here is a trick that could actually be useful. Define
$$
S(n) = T(n)+1.
$$
Then
$$
S(n) = T(n) + 1 = 2T(n/2) + 2 = 2S(n/2),
$$
and so $S(2^k) \leq 2^k S(1)$ by induction.
Let's see what this trick gives you more generally.
Application 1
Consider the recurrence $A(n) = 2A(\lfloor n/2 \rfloor) + (-1)^n$, with base case $A(1)$.
Define a new recurrence $T(n) = 2T(\lfloor n/2 \rfloor) + 1$, with base case $T(1) = A(1)$. Prove by induction that $A(n) \leq T(n)$. The technique above shows that $T(n) = O(n)$, hence $A(n) = O(n)$.
Application 2
Consider the recurrence $B(n) = 2B(\lfloor n/2 \rfloor) + \log n$, with base case $B(1)$.
Define $R(n) = B(n) + \log n$. Then
$$
R(n) = B(n) + \log n = 2B(\lfloor n/2 \rfloor) + 2\log n = 2R(\lfloor n/2 \rfloor) - 2\log \lfloor n/2 \rfloor + 2\log n.
$$
You can check that $2\log n - 2\log \lfloor n/2 \rfloor = O(1)$, and so the previous technique shows that $R(n) = O(n)$. It follows that $B(n) = O(n)$.
Application 3
Consider the recurrence $C(n) = 2C(\lceil n/2 \rceil) + 1$, with base case $C(1)$.
Defining $D(n) = C(n) + 1$ with base case $D(1) = C(1)$, we see that
$$ D(n) = 2D(\lceil n/2 \rceil). $$
Let us try to prove by induction that $D(n) \leq Kn - L$. Since $\lceil n/2 \rceil \leq n/2 + 1/2$, if the induction hypothesis holds for $\lceil n/2 \rceil$ then
$$
D(n) \leq 2K(n/2 + 1/2) - 2L = Kn + K - 2L.
$$
Choosing $L = K$, we get $D(n) \leq Kn - L$. Choosing $K = D(2)$, the induction hypothesis holds in the base case $n=2$. Altogether, we have proved $D(n) \leq K(n-1)$ (for $n \geq 2$), and so $D(n) = O(n)$, implying $C(n) = O(n)$.


Degree Reduction in Max Cut and Vertex Cover

This is a counterexample.

Suppose you have this graph:

The maximum cut in this graph has four edges. If you follow the procedure used for vertex cover you get this cut:

In the image, the maximum cut has seven edges.


Is model checking PSpace-hard *in formula size*?

You are certainly right that the level of rigor found in old papers making such claims can be a bit low at times when viewed from today's perspective.

The claim is correct anyway, even if it does not follow from Sistla/Clarke's proof. The reason is that LTL satisfiability checking is also PSPACE-complete. You can see satisfiability checking as a special case of model checking.

More formally, you want to prove the following: There exists a fixed model such that given an LTL formula, checking if the formula holds on the model is PSPACE-hard. Now the satisfiability checking problem does not restrict the number of atomic propositions, so a fixed model does not do the trick. However, S. Demri and P. Schnoebelen show in the paper "The complexity of propositional linear temporal logics in simple cases" (Inf. Comput., 174(1):84–103, 2002) that the satisfiability problem is hard even if we only have a single atomic proposition.


Minimal number of comparisons - sorting $6$ elements

According to A036604, 10 comparisons are indeed optimal. The link probably contains a citation to a paper proving this.


Is a computer without RAM, but with a disk, equivalent to one with RAM?

Sure.  In principle, given appropriate hardware, you could have just a disk, with everything stored on disk.  Any time the CPU did a load or store instruction, there could be some hardware that turns that into a disk read or write.  It'd be extremely slow: on a magnetic disk, each seek takes about 10ms, so you could do about 100 random-access reads and writes per second.

Some systems have flash memory-mapped into their address space.  Flash memory provides non-volatile (persistent) storage.  So, in some ways this resembles what you mention -- though those systems usually also have RAM as well.


Turing machine deciding $\{1^{2^n} : n \geq 0 \}$

Here is the idea:

Go over the entire input, crossing out every other 1 encountered.

Reject if the number of 1s encountered was odd but more than 1.

Accept if the number of 1s encountered was exactly 1.

Otherwise, go back to step 1.


Finding numbers near the median in linear time

There is an algorithm that finds the $\ell$-th smallest element in an array of length $n$ in time $O(n)$. You can find the $(n-k)/2$-th smallest and the $(n+k)/2$-th smallest elements in $O(n)$ using this algorithm, and then, using an additional pass, find all elements in between.


Proving that $L=\{ w \mid \lvert w \rvert$ is prime $\}$* is a regular language

In fact this follows from a general property of the star operation. When we start with an arbitrary language $L$ of all strings of certain lengths, then the star $L^*$ of that language is always regular. More precisely:

Let $A\subseteq \mathbb N$, and $L = \{w\in \Sigma^*\mid |w|\in A\}$.
Then $L^*$ is regular.

This is a consequence of a property of unary languages, i.e., languages over a single symbol. See this question:
If $L$  is a subset of  $\{0\}^∗$ , then how can we show that  $L^∗$  is regular?
So for $\Sigma = \{0\}$ the statement above is true. For larger alphabets perform an alphabetic substitution (say $\Sigma = \{a,b\}$, then in a regular expression for $L^*$ replace every $0$ by $(a+b)$).


Why no DPDA can accept Palindrome? (according to this proof)

No sequence of moves may empty the stack, this is seen as follows. Since the PDA is deterministic, its computation is determined by its input. So we have to argue that the computation on $x$ will not empty the stack. If it would empty the stack, then the PDA blocks, and can no longer continue. But observe that $xx^R$ is a palindrome, so there should be an accepting computation on $xx^R$. This implies that the computation on the prefix $x$ should not block.

Your second question. For input $x$ we can look at all continuations $xy$. For each $y$ determine the stack height that is obtained. We choose an $y$ for which this is minimal and call this specific string $y_x$ (to indicate it depends on $x$).


Let me spell what $R$ being an equivalence relation means:

Reflexivity: for all $q \in Q$ there exists $a \in \Sigma$ such that $\delta(q,a) = \delta(q,a)$.
Symmetry: for all $q_1,q_2 \in Q$, if there exists $a \in \Sigma$ such that $\delta(q_1,a) = \delta(q_2,a)$ then there exists $b \in \Sigma$ such that $\delta(q_2,b) = \delta(q_1,b)$.
Transitivity: for all $q_1,q_2,q_3 \in Q$, if there exist $a,b \in \Sigma$ such that $\delta(q_1,a) = \delta(q_2,a)$ and $\delta(q_2,b) = \delta(q_3,b)$ then there exists $c \in \Sigma$ such that $\delta(q_1,c) = \delta(q_3,c)$.

Now it's no longer about DFAs. It's about functions $\delta\colon Q\times\Sigma \to Q$.


Proving NP-completeness of a surveilled graph problem

Let $\langle \mathcal{S}, \mathcal{I} \rangle$ be an instance of exact cover. Here $\mathcal{I}$ is a set of items and $\mathcal{S} \subseteq 2^\mathcal{I}$ is a collection of subsets of $\mathcal{I}$.

The goal is to decide whether there is a subset $S$ of $\mathcal{S}$ such that every item in $\mathcal{I}$ belongs to exactly one set in $S$. This is a well-known NP-complete problem.

To reduce exact cover to your problem create a graph $G = (V, E, A, g)$ as follows:

$V = \mathcal{S} \cup \mathcal{I}$.
$E = \{ (u,v) \in \mathcal{S} \times \mathcal{I} \mid v \in u \}$.
$A = \mathcal{I}$
$\forall u \in a, g(u)=1$.

If $S$ is an exact cover for $\langle \mathcal{S}, \mathcal{I} \rangle$, then $B=S$ is a solution for your original problem since $S \cap \mathcal{I} = B \cap A = \emptyset$ and each item in $\mathcal{I}=A$ has exactly one neighbor in $S = B$.

On the other hand, a solution $B$ to your original problem is such that $B \cap A = B \cap \mathcal{I} = \emptyset$. Hence $B \subseteq \mathcal{S}$ and eacn item in $A = \mathcal{I}$ has exactly one neighbor in $B$. Therefore $B$ is an exact cover for $\langle \mathcal{S}, \mathcal{I} \rangle$.


Is the credit assignment problem a well-posed one?

If you can do it well, it is useful.  If you can accurately identify which move was to blame for bad outcomes -- or which one is to credit for good outcomes -- that is useful in helping you learn to make better moves.  I'll let you decide whether that's enough for it to make sense to speak of it as a problem to be solved. I'm not very knowledgeable about philosophy, so I don't know whether that qualifies.


The main (and only) difference between DPDA and NPDA is that DPDAs are deterministic, whereas NPDAs are non-deterministic. With some abuse of notation, we can say that NPDAs are a generalization of DPDAs: every DPDA can be simulated by an NPDA, but the converse doesn't hold (there are context-free languages which cannot be accepted by a DPDA).

The main advantage of DPDAs is that we can simulate them much more easily with our deterministic computers (real hardware is always deterministic). In fact, simulating general DPDAs is not fast enough for most purposes, and so when parsing code we usually use LALR grammars which are weaker than DPDAs.


Concatenate multiple integer arrays such that number of inversions in resulting array is minimal

As an exercise to the reader, two lemmas:

Lemma 1. If $a, b$ are strings of symbols with a partial order, and
$\text{numinv}$ counts the number of inversions in a string of symbols then
$$\text{numinv}(ab) = \text{numinv}(a) + \text{numinv}(b) + \text{crossinv}(a, b)$$
where $$\text{crossinv}(a, b) = |\{(i,j) \in \{1,\dots,|a|\}\times\{1,\dots,|b|\} \mid a_i > b_j\}|.$$
Lemma 2. $\text{crossinv}$ has the distributive property over
concatenation, that is for strings $a, b, c$ we have
\begin{align}
\text{crossinv}(a, bc) &= \text{crossinv}(a, b) + \text{crossinv}(a, c)\\
\text{crossinv}(ab, c) &= \text{crossinv}(a, c) + \text{crossinv}(b, c).
\end{align}

You can use the above two lemmas repeatedly to generalize, and see that for a tuple of strings $(x_1, \dots, x_n)$
$$\text{numinv}(x_1x_2\dots x_n) = \sum_{i=1}^n \text{numinv}(x_i) + \sum_{i=1}^n\sum_{j=i+1}^n\text{crossinv}(x_i, x_j).$$
Since the first sum is constant for any re-ordering of $x$, we can ignore it for our problem. In fact, if we sort the symbols inside each $x_i$ you can compute $\text{crossinv}(x_i, x_j)$ in $O(|x_i| + |x_j|)$ time. So we only need to minimize the second sum by re-ordering $x$.
However, I do believe that this is a difficult problem to solve optimally. A greedy swapping approach won't work. As a counter-example (I apologize for the somewhat length counterexample, it's just one I found during experiments with randomly generated arrays) consider the following array of arrays:
$$(39, 23, 9, 31, 1, 44), (35, 41, 1, 49, 23, 38, 4, 11), (13, 10, 17, 5, 38, 50, 46), (28, 21), (45, 46, 33)$$
This has $102$ inversions when concatenated. The unique optimal concatenation order is
$$(28, 21), (39, 23, 9, 31, 1, 44), (35, 41, 1, 49, 23, 38, 4, 11), (13, 10, 17, 5, 38, 50, 46), (45, 46, 33)$$
with $100$ inversions. However this can't be generated with a simple swap. I've found similar counterexamples for single-symbol substring rotations.
A simple greedy growing approach won't work either. $(41, 3, 31), (16, 11, 47)$ is uniquely optimally ordered, but if we extend this with $(30, 20)$ the unique optimal ordering becomes
$$(16, 11, 47), (30, 20), (41, 3, 31)$$
Which is in no way a simple extension of the previous.
To go even further, Tim shows in this answer that if you view $\text{crossinv}$ as a black box function, and you don't exploit any of its special properties, then this problem is NP-complete and you're doomed to fail. So any efficient optimal algorithm must use some special property of $\text{crossinv}$.
For very large amount of arrays you will probably see the best real-world results using a non-deterministic technique such as genetic evolution to optimize the number of inversions, although this wouldn't guarantee optimality. Or perhaps I'm overestimating this problem's difficulty and someone comes along with a better answer.


Why is a deterministic Turing machine a special case of a probabilistic Turing machine?

Probabilistic Turing machines are similar to deterministic Turing machines, but have the additional power of tossing coins. If you never make use of this power, you get a deterministic Turing machine.

In a similar fashion, a non-deterministic Turing machine is allowed to make guesses, but if it doesn't it is just a deterministic Turing machine.


Is Datalog negation and the built-in predicate $ \neq $ similar?

There was a misunderstanding in regards to the evaluation algorithm/minimal model.

The derivation of new values is atomic e.g.:

step 1:

p = {}
q = {}

step 2:

p = r
q = r

In step 2 p and q only see the value that each other had at step 1(the old value). I thought p and q would have access to the value of the current step and thus, the order of evaluation would produce different results.

To answer the question:

p(X) :- r(X) & q(Y) & X ≠ Y.

q(X) :- r(X) & p(Y) & X ≠ Y.

only has one minimal model: p = r and q = r.


Can we prove that all CFLs can be recognized by a Turing Machine in polynomial time?

There are several misconceptions in this question and too many to cover in a comment.

We do not know that $\mathrm{P}=\mathrm{R}$ or that $\mathrm{NP}=\mathrm{RE}$. In fact, we know that both of these things are false. The time hierarchy theoreom tells us that both $\mathrm{P}$ and $\mathrm{NP}$ are strictly contained within the recursive languages.
$\mathrm{P}$ is not the class of languages accepted by any old deterministic Turing machines: they're DTMs running in polynomial time. Similarly, $\mathrm{NP}$ languages are accepted by NTMs running in polynomial time.
Without time bounds, the class of deterministic TMs and the class of nondeterministic TMs accept exactly the same languages: you can simulate nondeterminism deterministically but exponentially slower.
Also, we know that $\mathrm{REG}\subsetneq\mathrm{CFL}$, which is consistent with what you wrote but a stronger statement. Exercise: can you give an example of a context-free language that is not regular?
Another nitpick: you write "$\mathrm{P}\subseteq\mathrm{NP}$ or $\mathrm{P}=\mathrm{NP}$"; the second statement is already included in the first.


recursively enumerable sets closed under concatenation

What you need to show is that given an algorithm that enumerates a (possibly finite) sequence $a_1,a_2,a_3,\ldots$, and another algorithm that enumerates a (possibly finite) sequence $b_1,b_2,b_3,\ldots$, then you can come up with another algorithm which enumerates all words of the form $a_i b_j$.

The simplest approach is to use the same idea that Cantor used to prove that the rationals are equinumerous with the integers, namely to come up with an algorithm that enumerates $a_i b_j$ in the following order:
$$
a_1 b_1, a_1 b_2, a_2 b_1, a_1 b_3, a_2 b_2, a_3 b_1, \ldots
$$
I'll let you to fill in the details.


Simple explanation as to why certain computable functions cannot be represented by a typed term?

Given that you do not want to learn precise concepts, here is an intuitive explanation. In the discussion below "function" always refers to a function mapping natural numbers to natural numbers (possibly undefined at some arguments).

Any programming language which has

computable syntax and rules of evaluation, and
implements every total computable function

necessarily implements some partial functions.

To see this, suppose it were the case that every definable function in this language were total. Because the language has computable syntax, we can enumerate all definitions of functions (just enumerate all strings and filter out those that cause syntactic errors). Because the rules of evaluation are computable, the second assumption allows us to conclude that in our language we can define the total function eval(n,m) which evaluates the n-th definable function on m (essentially this is an mini-interpreter written in the language itself). But then the function

λ k . (1 + eval(k,k))

is a total definable function which is different from every total definable function, a contradiction.

The simply typed $\lambda$-calculus satisfies the first condition and it defines only total functions. Therefore it does not satisfy the second condition.

As far as "standing on your head" is concerned, for a strongly-normalizing $\lambda$-calculus it is fairly easy to provide a total function which is not definable in the calculus, namely the normalization procedure itself. It is not very important how fancy your strongly normalizing calculus is, it could be the polymorphic $\lambda$-calculus, or Martin-Lof type theory, or the Calculus of constructions. (Exercise: if you could implement the normalization procedure, you could implement eval above.)


Encoding 1-out-of-n constraint for SAT solvers

For the special case of k out of n variables true where k = 1, there is commander variable encoding as described in Efficient CNF Encoding for Selecting 1 to N Objects by Klieber and Kwon.  Simplified: Divide the variables into small groups and add clauses that cause a commander variable's state to imply that a group of variables is either all false or all-but-one false.  Then recursively apply the same algorithm to the commander variables.  At the end of the process demand that the exactly one of the handful of final commander variables be true.  The result is O(n) new clauses and O(n) new variables.

Given the ubiquity of two-watched-literals in DPLL based solvers, I think the O(n) clause growth is a decisive advantage over encoding schemes that would add more clauses.


Are there name and literature for this SAT-like problem?

The problem, as specified, takes at least exponential time to solve: merely outputting a string $x$ that satisfies $f(x)=1$ takes $\Theta(n)$ time (since $x$ is $n$ bits long), and this is exponential in the length of the input in the worst case (if $f$ has a short description, then the input length is $\Theta(\lg n)$ bits.  This is a consequence of the fact that $n$ is specified in binary.

If $n$ is specified in unary and the running time of $f$ is guaranteed to be polynomial in $n$, the problem is NP-hard, and the corresponding decision problem is NP-complete.  It is at least as hard as SAT, because any SAT formula can be encoded as a program $f$.  Also, it is no harder than SAT, as any program whose running time is polynomial in $n$ can be expressed as a circuit of size polynomial in $n$; then the problem becomes equivalent to CircuitSAT, which is also NP-complete by a standard reduction (basically, the Tseitin transform).

So the unique aspects of this problem come from (a) the fact that $n$ is expressed in binary, and (b) the lack of any guarantee on the running time of $f$.

For your last question, you have to be a little bit careful.  If you fix $f$ and specify $n$ in unary, the problem seems unlikely to require $\Omega(2^n)$ time.  In particular, there is an infinite advice string $A$ such that the answer to the input $n$ is $A_n$.  This shows that there is a non-uniform polynomial time algorithm for this problem, if you fix $f$ and express $n$ in unary (i.e., the problem is in P/poly); this would be surprising, as it implies NP is contained in NP/poly, which is not expected to occur.  To avoid trivial situations like this, you might want to treat the description of $f$ as part of the input, rather than fixing $f$.

This suggests we ask whether there exists a class of functions $f$ such that the problem requires $\Omega(2^n)$ time, yet where every function $f$ in the class can be computed in $O(n)$ time.  I suspect the answer to that is likely to be yes if the strong exponential time hypothesis is true; simply take as your class of functions the set of SAT formulas of size $O(n)$.  Note that this doesn't follow immediately from the strong exponential time hypothesis, due to the extra restriction that the formulas have size $O(n)$, but I would venture a guess that this restriction does not help algorithms solve SAT more efficiently.  That said, the strong exponential time hypothesis is a very strong assumption.

Also, if we could prove that the answer to this question is yes, then I suspect we'd obtain a proof that the strong exponential time hypothesis is true.  In particular, since $f$ can be computed in $O(n)$ time, there is a circuit that computes it in $O(n)$ time, so it can be expressed as a SAT formulas with $O(n)$ variables (using the Tseitin transform).  If we knew that there was no algorithm to solve the resulting class of SAT instances in $O(2^n)$ time, then we'd know there is no algorithm to solve all SAT instances in $O(2^n)$ time, which implies the strong exponential time hypothesis.  I think.


Can I use the set of "used arguments values" as a memoization key for a deterministic function?

As long as $f$ is deterministic and depends only on its arguments (not on other global variables), yes, you can safely use that as a memoization key.  The bad case cannot happen.

You can see this by thinking about what happens as it reads the $t$th argument and using induction on $t$.  Let $i_1,i_2,i_3,\dots,i_t$ be the sequence of argument indices read (i.e., $f$ first reads $i_1$ when running on input $x$, then reads $i_2$, etc.).  For each $t$, if $f(x)$ and $f(y)$ have behaved the same up until just before they read the $t$th of these, then the next index examined by $f(x)$ and $f(y)$ will be the same, say $i_t$; if additionally $x_{i_t} = y_{i_t}$, then it follows $f(x)$ and $f(y)$ will behave the same up until just before they read the $t+1$st of their arguments.  Since $i_t \in U_X$, $x_{i_t} = y_{i_t}$ is guaranteed by your assumptions. Now use induction.

This assumes everything is deterministic.  For instance, $f$ had better not be allowed to read a random-number generator, the current time of day, or other global variables.  Beware that on some platforms there can be surprising sources of non-determinism, e.g., due to aspects of behavior that are unspecified and might depend on external factors.  For instance, I have a recollection that floating-point math in Java can introduce non-determinism in some cases, and so if you want to write code that is verifiably deterministic, you probably want to avoid all floating-point math.


Proving NP-completeness of a graph coloring problem

First of all, you haven't formulated your problem as a decision problem (a problem that has a YES/NO answer). The decision problem corresponding to your optimization problem is: Given a graph $G$, an integer $k$ and another integer $\ell$, is there a $k$-coloring of $G$ with at most $\ell$ monochromatic edges?

In order to show NP-completeness of a problem $P$, you need to do two things:

Show that $P$ is in NP. This is usually easy. It just means that a putative solution can be verified.
Show that $P$ is NP-hard. In practice, this is (almost) always done by showing that some other NP-hard problem $Q$ is many-one reducible to $P$. This implies that $P$ itself is NP-hard.

A many-one reduction from $Q$ to $P$ is a function $f$, computable in polynomial time, which maps an instance $x$ of $Q$ to an instance $f(x)$ of $P$ such that $x \in Q$ iff $f(x) \in P$.

In your case, it is easy to see that your problem (let's call it MIN-MONOCHROMATIC) is in NP: the NP machine guesses a $k$-coloring of $G$, and verifies (in polynomial time) that there are at most $\ell$ monochromatic edges. In order to show that it is NP-hard, we come up with a many-one reduction $f$ from the NP-hard problem K-COLORING to MIN-MONOCHROMATIC. The reduction $f$ takes a graph $G$ and an integer $k$, forming an instance of K-COLORING, to the instance $(G,k,0)$ of MIN-MONOCHROMATIC (i.e., with $\ell=0$). The definition of coloring implies that $(G,K)$ is in K-COLORING iff $(G,k,0)$ is in MIN-MONOCHROMATIC. Also, clearly $f$ can be computed in polynomial time. So $f$ is a polytime many-one reduction from an NP-hard problem K-COLORING to MIN-MONOCHROMATIC, so we conclude that the latter is NP-hard. Since it is also in NP, it is NP-complete.

As you see, this is the same proof as yours, only with a lot of fluff. At this stage of your education, this fluff is important, since you need to makes sure that you understand the definitions not only intuitively but also formally (both are important). Once you're past this stage, all the details you really need are the ones explained in your current proof.


What happens to a file after too many copy-pasting?

Once a single-bit error is introduced into a file, the file is corrupt.  File systems, disk drivers, and hardware on the disk itself have checksums, error correction codes, and facilities to detect bad sectors to limit the probability of write (or read) errors, but it's not 100% (but it better be close to 100%, otherwise my disk isn't reliable).

In general, the way to compute the probability of corruption:

Let's say the probability of a single bit error occurring during a file copy is P. (P should be really, really low, otherwise, the disk or media wouldn't be reliable).

And let's assume that a file has a size N measured in bits (e.g. a 1 GB file would be 8 billion bits or so).

So the probability of the first bit in the file not getting corrupted is: (1-P).  And so it follows that the probability of all bits not getting corrupted during a transfer is (1-P)N

Now let's say you copy the file X times.  Therefore the probability of the file not getting corrupted after X transfers is (1-P)NX.  Or rather, the probability of corruption after X transfers is 1 - (1-P)NX


Long multiplication school method: number of primitive operations to calculate first partial product?

Perhaps the following example will be useful. Suppose that $n = 3$, and we want to multiply $a_2 a_1 a_0$ by $b$. We first compute
$$
\begin{align*}
a_0 \times b &= c_0 d_0 \\
a_1 \times b &= c_1 d_1 \\
a_2 \times b &= c_2 d_2
\end{align*}
$$
(Here $c_0 d_0$ is a two-digit integer.)
So far we have done 3 operations (for general $n$, this will be $n$ operations).

Now we wish to perform the addition
$$
\begin{array}{cccc}
0&d_2&d_1&d_0\\
c_2&c_1&c_0&0 \\\hline
r_3&r_2&r_1&r_0
\end{array}
$$
The book states that you need 4 operations for this (and in general, $n+1$), though 2 are enough (in general, $n-1$):
$$
\begin{align*}
r_0 &= d_0 \\
s_1 r_1 &= d_1 + c_0 \\
s_2 r_2 &= d_2 + c_1 + s_1 \\
r_3 = s_2
\end{align*}
$$
Here $s_1,s_2$ are carry bits, and the first and last operations are for free (though the author charges one operation for each).

Summarizing, if you only charge addition and multiplication, only $2n-1$ operations are needed. If you also charge moves, $2n+1$ operations are needed. (The moves can be eliminated, though. Exercise.)


Is there a faster algorithm for my graph problem?

In practice, just as you can calculate g (u) for one particular u quite quickly, you can calculate g (u) for all $u \in V$ in parallel, operating with bit vectors of $|V|$ bits instead of boolean values - this changes the number of operations only be a constant, but by a rather large constant. This is quite useful if you actually want the number of bytes saved for every u.

If you are only interested in one u, then you only want to know for each function: 1. Can it be reached from u? 2. Can it be reached from any function other than u? To decide that, just combine all the other functions in V into one single function which calls everything that any of these functions calls. You don't need to know all the individual call graphs, just what can be reached from any of the functions in V other than u.

Second comment: I thought that you wanted to know how many bytes are saved by removing one function. That took you O (|V| * (|V| + |U|) by calculating all g (u). Which looks quite bad and can be improved if you want to know the answer for one function. If you want to answer the question for all functions, then calculating all g (u) is fine. It still takes O (|V| * (|V| + |U|), but the work can be reused for every function.

That's a very common situation, where solving n problems can be done a lot quicker than n times solving one problem.


Which is the proper algorithm to figure repeated substrings of longest total length?

You might want to check out the literature on the longest repeated substring problem, which is closely related but is trying to optimize a different metric.  There are many algorithms and techniques; it's possible some of them could be adjusted to apply to your problem.

For instance, one can find the optimum solution to your problem in $O(nr)$ time using Rabin-Karp's method, where $r$ is the length of the longest repeated substring in $S$.  First, we compute $r$ using any standard method.  Then, for each $i$ in the range $1,2,\dots,r$, we look for the substring $T$ of length $i$ that is repeated the most number of times (without counting overlaps).  This can be done in $O(n)$ time for a fixed value of $i$, by using a rolling hash to compute the hash of all length-$i$ substrings of $S$ and for each such length-$i$ substring, compute the number of times it is repeated (without counting overlaps).  This can be done using a hashtable and a greedy algorithm (each time you see a substring $T$, if it doesn't overlap with the last accepted occurrence of $T$, increment the count for $T$ and accept this occurrence, otherwise reject it).

For many distributions on input strings, $r$ is relatively small compared to $n$: e.g., $r = O(\lg n)$.  If that applies to your situation, then this Rabin-Karp-based method will be easy to implement and perform reasonably well.

You could also look at suffix trees or suffix arrays.  Each internal node in the suffix tree represents a candidate for the substring (a substring that occurs more than once in $S$).  However, it's not quite clear to me at the moment how to efficiently account for overlap according to your problem statement, so I don't have a specific algorithm to suggest.


At a high level, the process for building an Aho-Corasick automaton is:

Build a trie for the pattern strings.
Add suffix links (also called failure links) from each node to its longest proper suffix that's still in the trie.
Add output links to any patterns that are reachable from each node via suffix links.

Build the trie

Create a root node, then go through each pattern character by character. Starting from the root, try and follow an edge for the current character. If one does not exist, create an edge to a new node for that character.

Using P = {vine, vincent, cent, center}, say we start with the pattern 'vine'. When we go and add the next pattern 'vincent', we first follow the existing edges for v-i-n, and then add in new edges for c-e-n-t:

(I'm marking the ends of each pattern with a double circle). Continue this process until the whole trie is built:

Add suffix links

Now to add the suffix links, we perform a breadth first search of the tree, adding an edge for each node except the root. If a node is one hop away from the root, its suffix link goes to the root. Adding suffix links in blue, the suffix links for the nodes corresponding to 'v' and 'c' are:

Otherwise, the node corresponds to some string wx, where x is the final character. For example, if we look at the string 'vi', w='v' and x='i'. Now follow w's suffix link and let the node you arrive at be called n.

If this node has an edge for x, then set wx's suffix link to point at nx. Else if n is the root node, set wx's suffix link to point at n. Otherwise, follow n's suffix link, let this node be the new n, and repeat. In this case, the node for n does not have an edge for 'i'. Here's another example adding in the suffix link for 'vinc', where w='vin' and x='c':

Add output links

As you are performing the BFS to fill in the suffix links, you can also fill in the output links (all initially null). Let the current node be n. Follow n's suffix link and let the node you arrive at be called m.

If m corresponds to one of the pattern strings (is marked with a double circle), set n's output link to point at m. Else set n's output link to point at the same node as m's output link, or null if m has no output link. In our example there is only one output link, shown here in green:


This problem is the 3-dimensional variant of the Euclidean min-cost perfect matching problem (MCPM), and I don't know if it has been studied.  The general problem (min-cost maximum-cardinality matching) can be solved in time $O(\sqrt n \cdot m )$ [^1].
However, the 2-dimensional version can be solved in time $O(n^{3/2} \log^5 n)$.  Reading the article by Varadarajan [^2], I cannot see any issues lifting the result to 3-dimensional points.
[^1] Micali, Silvio, and Vijay V. Vazirani. "An $O(\sqrt{|v|} \cdot |E|)$ algorithm for finding maximum matching in general graphs." 21st Annual Symposium on Foundations of Computer Science (sfcs 1980). IEEE, 1980.
[^2] Varadarajan, Kasturi R. "A divide-and-conquer algorithm for min-cost perfect matching in the plane." Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280). IEEE, 1998.


The answer should be the following:

$$
\begin{align}
&S \to WQ  \mid XY \\
&W \to aW  \mid ε \\
&Q \to bQc \mid ε \\
&X \to aXb \mid ε \\
&Y \to cY  \mid ε
\end{align}
$$


Where to find published research papers?

As AJed mentioned, ACM digital library and IEEE xplorer would be near the top of list.

Additionally Goggling with advanced search for the name of the reference with the option to search for PDF or PS increases the change of a hit.

Sometimes limiting the search to cs.xyz or xyz.edu increases the quality of results.

If you are just starting out on a subject, try adding the word survey as a search term because many researchers write survey papers so that someone new to the subject has an informed person guiding the way.

I also like to hit CitSeerX, WorldCat and Google Scholar

Don't forget to look at the patents in Google Scholar, I don't usually but every now and then companies have to give out something good they may not publish anywhere else.

If you don't attend school, you can see if a school provides access to their library for outside third parties. I found out that I can do this for Princeton University for $300 a year.

Added 3/2/2013

Microsoft Academic Search

This can also visualize publication trends in computer

Added 1/1/20016

arxiv.org - Open access to 1,106,143 e-prints in Physics, Mathematics, Computer Science, Quantitative Biology, Quantitative Finance and Statistics.

semanticscholar.org

This has a nice feature that list survey papers which is useful when you are starting on something new.


Decide if there is a sbugroup of edges in graph that every vertex meets exactly k edges from subgroup

The question is a bit misleading, since the proposed algorithm finds whether there is a "multisubset" of the edges set which is $k$-regular — that is, you are allowed to take the same edge several times, if it helps. Deciding whether the graph contains a bona fide $k$-factor (a $k$-regular subgraph which touches all vertices) is much more tricky — see Meijer, Núñez-Rodríguez, and Rappaport, An algorithm for computing simple $k$-factors.


Select the maximum number of links to satisfy the constraint on each link. How to prove is NP-hard?

This problem can be solved in polynomial time.  Therefore, it's likely not NP-hard (unless P = NP).

After a little bit of algebraic manipulation, we find that the condition on $S$ is equivalent to requiring that

$$2 P_i \ge \varepsilon + \sum_{j \in S} P_j \quad \text{for all $i \in S$}.$$

This, in turn, is equivalent to requiring

$$2 \min \{P_i : i \in S\} \ge \varepsilon + \sum_{j \in S} P_j.$$

For convenience, sort the $P_i$'s into increasing order, so $P_1 \le P_2 \le \dots \le P_n$.

Now one can prove that if there is any set of cardinality $k$ that satisfies this equation, then there's a set of the form $S = \{t,t+1,t+2,\dots,t+k-1\}$ that satisfies this equation, for some $t$.  (This can be proven using an exchange argument, swapping pairs of indices as needed and showing that the swap leaves the left-hand side unchanged and only decreases the right-hand side.)

Now you can try all possible values of $t$ and see whether the corresponding set satisfies the condition.  There are only $n$ possible values of $t$, so this can certainly be tested in polynomial time.  In fact, with clever programming (prefix sums, etc.), you can implement this in $O(n \lg n)$ time, or in $O(n)$ time if the $P_i$'s are already provided in sorted order.

More generally, if you want to find the set $S$ of maximum cardinality that satisfies the equation, such a set will have the form $S=\{t,t+1,t+2,t+3,\dots,u\}$ for some $t,u$.  Therefore, you can try all such possibilities and see which has largest cardinality.  This too can be done in $O(n \lg n)$ time using appropriate methods (binary search, prefix sums).  Alternatively, you can do binary search on $k$, and apply the decision algorithm of the previous paragraph for each candidate value of $k$ to find the largest $k$ for which a solution exists.  The running time is again $O(n \lg n)$.


Turing Machine That Accepts Machines With Undecidable Languages

The language you are describing is called an "index-set", which means that it is accepting languages, rather than machines specifically. More formally, if we have two machines $M_1, M_2$, and $L(M_1) = L(M_2)$, then $M_1 \in Undecidable \iff M_2 \in Undecidable$.

There's a theorem called Rice's Theorem that says that index sets are always undecidable. The proof on the Wikipedia page shows how you can reduce the halting problem to any index set.


How many minimal spanning trees are there when all edge costs are distinct?

Consider Kruskal's or Prim's algorithms to get minimal spanning trees. They consider arcs in increasing order of cost. If all costs are different, the order in which they are added is fixed, and so is the spanning tree constructed. It is unique in this case.


As I understand it this means that taking $d := Yc$ it translates to $f(d)=φ_{c}(d)=cd=d$, ie. $f$ having a fixed point.

Not every recursive function has a fixed point in the sense of $f(n)=n$ - for example, $f(n)=n+1$. Therefore, there must be something wrong with this proof. As noted in comments, this proof works only if $d=Y c$ is defined.

As you've noticed, you can work around this issue by using a variant of the Y combinator:

  Just taking Ycc′=c(Yc)c′ doesn't seem to make your problem any better

But it does! To avoid confusion, I'll call this combinator Z. We have

$Zcc′=c(Zc)c′$.

Let's take a function $f=\varphi_c$ and let $d = Z c$, just like in the previous proof. Now, $d$ is guaranteed to be defined. We have

$d c' \equiv c d c'$

By the definition of application in the Kleene's first algebra this means:

$\varphi_{d}(c')$ $ \simeq \varphi_{\varphi_{c}(d)}(c')$

$\varphi_{d}(c')$ $ \simeq \varphi_{f(d)}(c')$

$\varphi_{d}$ $ \simeq \varphi_{f(d)}$

which is the Kleene's recursion theorem.

  Well, literally the same problem arises in the proof of the Recursion theorem in Odifreddi's Classical Recursion Theory, Theorem II.2.10. There he takes $b$ to be a code satisfying $\varphi_{b}(e) \simeq f(\varphi_e(e))$.

No, $b$ is defined in Theorem II.2.10 using the equation:

$\varphi_{\varphi_{b}(e)} \simeq \varphi_{f(\varphi_e(e))}$

Importantly, $b$ is a code - it is a well-defined natural number that encodes a specific program. Furthermore, for every $e$, $\varphi_b(e)$ is also a code - it is not the result of running $f(\varphi_e(e))$, it is merely a code of a function which given $n$, runs the function $\varphi_{f(\varphi_e(e))}$ on $n$. (This difference mirrors the difference between Y and Z combinators.)


How to analyse the worst-case time complexity of this algorithm(a mix of Bubble Sort and Merge Sort)?

Let $f(n)$ the maximum number of elementary operations performed by the algorithm when the number of elements to sort is $n$.
An upper bound to the worst-case complexity of the algorithm is $O(n^2)$ since there exists some $n_0$ and some constant $c>0$ such that for every $n \ge n_0$, $f(n) \le c n^2$.
Moreover, given some other function $g(n) = o(n^2)$ it is false that $f(n) \in O(g(n))$ since for all $c>0$, there always exists a sufficiently large $n$ for which $f(n) \ge c g(n)$.  In this sense, $O(n^2)$ is the smallest asymptotic upper bound you can hope to obtain.
Notice however that with this choice of $f(n)$ it is not true that $f(n) = \Omega(n^2)$ according to Knuth's definition of big Omega, while it is true in the Hardy–Littlewood definition.
The "problem" here is that $f(n)$ is not monotonically non-decreasing, while the functions considered in algorithm analysis usually are.
Of course you can define $F(n) = \max_{0 \le n' \le n} f(n')$ to get a monotonically non-decreasing function, which is probably what you have in mind when you think of the worst-case running time of the algorithm.
Then you have:
$F(n) = O(n^2)$ and $F(n)= \Omega(n^2)$ showing that $F(n) = \Theta(n^2)$.


Amortize time for a counter with the operations INCREMENT and DECREMENT

Your solution is on track. As you comment, if you increment a counter $2^k-1$ times and then do $m$ increment/decrement operations, in total you must have modified at least $km$ array positions (this will serve as our lower bound on the running time). In your case $N = 2^k-1 + m$. If you choose, for example, $m = 2^k+1$, then $N = 2^{k+1}$ while the lower bound is $km \geq \log_2 N \cdot (N/2) = \Omega(N\log N)$. This shows that the amortized running time is $\Omega(\log N)$, which is certainly superconstant.

We can easily get a matching (non-amortized) upper bound. If we only perform $N$ operations, then the value of the counter is in the range $[-N,N]$, and so takes $O(\log N)$ bits to represent. It is not difficult to implement increment and decrement so that they take time linear in the length of the representation, so $O(\log N)$ in this case.


Why encoding of graph in adjacency matrix is $\Omega (\sqrt n)$?

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.


Your idea is correct (or at least one way of doing it), though it may be "easier" to add a third tape, where you just write the current PDA state. Your transition function just needs to simulate the PDA. The alphabet for the input tape is just the PDA's input alphabet plus the blank, the alphabet for the stack tape is the stack alphabet plus the blank symbol. You read a symbol on the input tape, the PDA state and the current symbol on the stack, move the input head right and maybe write a symbol on the stack tape and stay put, write a symbol and move right, or erase a symbol and move left. The state tape head just stays put and writes the new state on the tape. If you read a blank on the input tape, and the current PDA state is accepting, move to the TM's accept state, if you otherwise read a blank on the input tape, then move to the TM's reject state.

Given a PDA transition $\delta_{PDA}(q_{i}, \sigma, \tau) = (q_{j}, \rho) $ (so moving from state $q_{i}$ to $q_{j}$, with $\sigma$ in the input, popping $\tau$ and pushing $\rho$), the TM transition looks something like $\delta_{TM}(q_{p}, \sigma, \tau, q_{i}) = (q_{p}, (\sigma, R), (\rho, S), (q_{j},S))$ - the notation here is somewhat abused, mostly to group each tapes actions together in order. Transitions that have one or more $\varepsilon$/$\lambda$ in them complicate things a little, the input tape head would not move on an $\varepsilon$, the stack tape head might move left or right, depending on whether it was a pop or push that had the $\varepsilon$.

This gives you a TM with a single state that does all the real work, and the accept and reject states.


In the very next paragraph of that book (see HoTT, p. 2) they give an informal characterization of what qualifies a language system (or logic) as a type system, namely that: in it all terms are typed.

By "Church's type system" they're referring to the simply typed lambda calculus (introduced in 1940).

  In 1930s, in particular while preparing his negative solution to the decision problem, Church had introduced a system of untyped lambda calculus. This, of course, was not a type theory.

The 1940 system, however, is a type theory, because in it all terms are typed (see, for example (T&S), Section 1.2 for how exactly this is done). By "lambda-calculus as a type system" they're referring to this second, simply typed version of lambda calculus.

(T&S) Troelstra, A.S. & Schwichtenberg, H. Basic Proof Theory, 1996.


Is there a programming language that is not a formal language

No, at least not a reasonable programming language by what we commonly understand under that term.

As soon as you have a compiler (or an interpreter), you have an algorithm that decides whether a given string is a valid program. This compiler then defines the language. (Not a good way to define a programming language, but a workable one.)


Fastest algorithm for connectivity problem

If I understand you correctly, you want to maximize the number of pairs of vertices that are connected.
In a connected (undirected) graph, all vertices are reachable from each other, so the number is always $n^2$.
You can always connect to components with an edge by placing it arbitrarily between the components, and this will increase the number from $a^2 + b^2 \leq (a+b)^2$ to $(a+b)^2$.
If $a \geq b \geq c$, then
$$(a + b)^2 - a^2 - b^2 \geq \max((b+c)^2 - b^2 - c^2 , (a+c)^2 - a^2 - c^2).$$
It follows that the optimal solution is to iteratively connect the two largest components in your graph, which corresponds to, given $k$ edges, connecting the $k+1$ largest components of your graph.
Finding the $k+1$ largest components can be done in $O(n+m)$ time.


Generating uniform random connected graphs: doubt about Wilson's algorithm

Here are two alternative algorithms. There are probably better ones.

Large $m$ When $m \gg \frac{1}{2} n\log n$, it is very likely that a $G(n,m)$ random graph will be connected. Generate $G(n,m)$ graphs until one of them is connected.

Small $m$ When $m$ is small, you can try the following algorithm, which however might be a bit slow (or perhaps very slow). Generate a random graph according to the stackoverflow procedure, calculate the number of $T$ spanning trees it has, and accept with probability $1/T$. You can check that this produces a uniform sample, though the expected running time is $n^{n-2}\binom{(n-1)(n-2)/2}{m-n+1}/G_{n,m}$, where $G_{n,m}$ is the number of connected graphs on $n$ vertices and $m$ edges.

You can speed up the algorithm by sacrificing the accuracy of the sample. Find a number $M$ such that "most" graphs generated by the stackoverflow algorithm have at least $M$ spanning trees, and accept with probability $\min(M/T,1)$. You can estimate $M$ by sampling.


If you just care about termination of the algorithm not the tight analysis then you can say that it will terminates within $a+b$ steps as inside the while loop you are decreasing either $a$ or $b$ depending on some condition, so your while loop have to terminate within $a+b$ iterations.


Query about FP Divide latency and Initiation Interval

You can think latency as the time (# intervening clock cycles here) required to get a result from a producer instruction to a consumer instruction. For FP divider it is required 25 cycles and the unit is unpipelined. So, the #intervening CC = 24.
On the other hand, initiation interval is the duration of time that is required to issue two similar type instruction. As FP divider is unpipelined, so you can issue another FP divider after finishing the previous one which requires 25 clock cycles. If it was pipelined, I guess it would be 1.


What will i obtain if i apply a xor-ing a one way function and it's input?

Let $h$ be any one-way function, and define $f(x) = 0^{|x|} h(x)$. Note that $f$ is also one-way: it is easy to compute, and if you can invert $f$ you can invert $h$ (so since $h$ is hard to invert, so is $f$). But $g(x) = xh(x)$ is easy to invert.


Reducing the infinite language problem to halting problem

Your language is actually $\Pi_2^0$-complete, and in particular even harder than the halting problem.

We can show that $\mathrm{INF}$ is $\Pi_2^0$-hard by reduction from $\mathrm{TOT} = \{ w : L(M_w) = \Sigma^* \}$. Indeed, given a Turing machine $M$, we can construct a Turing machine $M'$ which on input $x$, simulates $M$ sequentially on all inputs $y \leq x$ (using lexicographic order). It is not hard to check that $M'$ halts on infinitely many inputs iff $M$ halts on all inputs.

To show that $\mathrm{INF}$ is in $\Pi_2^0$, notice that a machine $M$ halts on infinitely many inputs if and only if for all inputs $x$ there exists an input $y \geq x$ and a number $n$ such that $M$ halts on $y$ within $n$ steps. Since the last condition is decidable, it follows that $\mathrm{INF}$ is in $\Pi_2^0$.

To answer the question you are interested in, all you need to do is to find a reduction from the halting problem to $\mathrm{TOT}$.


Polynomial Complexity (Relative to the Size of the Input)

The statement meant to say that "if b is asymptotically smaller than n" i.e. $b=o(n) \space or \space b=O(n)$.
If $b$ was asymptotically larger than $n$, i.e. $b=\omega (n) \space or \space b=\Omega(n)$, then the complexity would become, $O(b^3)$, i.e. not polynomial in $n$.

For example, lets consider two cases.

$b$ is asymptotically smaller than $n$, i.e. $b=O(n)$.
$$O((n+mb)^3) = O(n^3 + 3n^2mb + 3nm^2b^2 + m^3b^3)$$
$$ = max(O(n^3),O(3n^2mb),O(3nm^2b^2),O(m^3b^3))$$
We know that $b=O(n) \implies bn=O(n^2),\space bn^2=O(n^3) \space and \space b^2n=O(n^3). $
From this, we can conclude that, $m^3b^3=O(3nm^2b^2)$, $3nm^2b^2=O(3n^2mb)$, and $3n^2mb = O(n^3)$.
$$\implies O((n+mb)^3)=O(n^3)$$
$b$ is asymptotically larger than $n$, i.e. $b=\Omega(n) \space or \space n=O(b)$.
$$O((n+mb)^3) = O(n^3 + 3n^2mb + 3nm^2b^2 + m^3b^3)$$
$$ = max(O(n^3),O(3n^2mb),O(3nm^2b^2),O(m^3b^3))$$
We know that $n=O(b) \implies nb=O(b^2),\space nb^2=O(b^3) \space and \space n^2b=O(b^3). $
From this, we can conclude that, $n^3=O(3n^2mb)$, $3n^2mb=O(3nm^2b^2)$, and $3nm^2b^2 = O(b^3)$.
$$\implies O((n+mb)^3)=O(b^3)$$

In your approach, assuming $b$ to be numerically smaller than $n$ would lead to correct analysis. But what the statement means is that $b$ is asymptotically smaller than $n$. Like, $b=log(n) \space or \space b=\sqrt{n} \space or \space b=log(log(n))$


Does the language of TM's that repeat a configuration infinite times semi-decidable or not?

$L_1$ is indeed recursively enumerable. Suppose for simplicity that the input consists of a pair $M,w$ and you want to know whether $M$ repeats a configuration during its computation on $w$. You can then loop over the integers, and for each $n\in\mathbb{N}$ check if $M$ repeats a configuration with input $w$ during the first $n$ steps. This is possible since during the first $n$ steps $M$ uses at most $n$ cells from the tape, hence the number of possible configurations is finite (you can store them in memory and mark those which were seen).

Now, you want to add an additional existential quantifier over the words $w$, and this can be achieved by dovetailing. Simultaneously scan words and computations length, i.e. for each $n$ and for all words of length $\le n$, check if $M$ repeats a configuration during its first $n$ steps.

The additional universal quantifier prevents $L_2$ from being recursively enumerable, you can show this by reduction from the complement of the halting problem. Given $(M,w)$, your reduction outputs a machine which on input $x$ simulates $M$ on $w$ for $|x|$ steps, and enters a loop iff $M$ did not halt in this time.


In your loop, $j$ will take the values $1, 2, 4, 8, \dotsc, 2^k$ where $2^k<n$. You need to know how many times this will iterate. In other words, what will be the largest $k$ for which we have $2^k < n$? Take the log to the base 2 of each side of the inequality and you're asking what the largest $k$ will be for which $k<\log_2n$. What this means is that you're right in your comment: the loop will iterate no more than $\log_2n$ times.


One standard approach is to use object detection / objection recognition / object localization on each individual frame of the video.  This means we can apply algorithms for doing that on a single image.  For speed, once you have detected an object in one frame, we can use object tracking to keep track of where it moves to in the next frames, and we don't need to use an expensive object detection algorithm on the next frame.  For instance, we might apply object detection on every 10th frame, and then use object tracking to track its motion for the next 9 frames.

That should give you enough keywords that you can search and find lots of information on each of those techniques.


Schaefer's dichotomy theorem and reformulating 3-literal clauses

Schaefer's dichotomy theorem doesn't purport to claim anything about what transformations might be possible / not possible.

However, as Yuval says, we don't need Schaefer's theorem.  We already know that 3SAT is NP-complete.  Therefore, we know that if there is a polynomial-time transformation that transforms a 3SAT instance into an equisatisfiable 2SAT instance, then P = NP.  Put another way, if P $\ne$ NP (as many researchers suspect to be the case), then there is no polynomial-time transformation that transforms a 3SAT instance into an equisatisfiable 2SAT instance.  Put yet another way, finding such a transformation that provably works is at least as hard as proving that P = NP.

The same holds for a transformation to any other set of formulas that are known to have a polynomial-time algorithm for testing satisfiable (e.g., the conjunction of Horn clauses).


Time complexity of function vs return value

Here is a correct version of your original problem.

  Find the time complexity of an algorithm which takes $T(n)$ time/operations to finish when the input size is $n$, where $T(n)$ satisfies the below initial condition,

  $$T(1) = C$$
  and the below recurrence relation,
  $$T(n) = 2T(n/2)+C\ \text{ if } n>1$$
  for some constant $C>0$.

Another correct version would be "Find the asymptotics in term of big $O$ or $\Omega$ notation for the function $T(n)$ that ...".

My answer is based on the above editions of the your original problem.

Your question and much more beyond have been answered in more generality in this reference question and answer and in particular, by the first case of the master theorem.

Assume throughout this answer and the question that $n$ is a positive integer and "/" is the integer division when it is applied to two positive integers as in Python/Java/C/C++/C#. Without these assumptions, $T(1.5)$ and $T(3)$ may not be defined.

Here is a correct computation.
Suppose $2^h\le n\lt 2^{h+1}$ for some nonnegative integer $h$.
\begin{align}
T(n) & = 2T(n/2) + (2^1-1)C\\
     & = 2(2T(n/4) +C)+ (2^1-1)C\\
     & = 2^2T(n/2^2) + (2^2-1)C\\
     & \cdots\\
     & = 2^hT(1) + (2^h-1)C\\
     & = (2^{h+1}-1)C\\
     & = \Omega(n)
\end{align}
The last equality stands from the fact that $Cn\le (2^{h+1}-1)C\lt 2Cn$.


Equivalence of logical Formula (Kripke structures)

First, these can all be looked at as LTL formulas. Therefore, their equivalence can be determined by their behaviour on traces (no need for Kripke structures with a complicated structure).

This answer is just a bunch of spoilers, so read only if you already tried your best.

For the first pair - they are equivalent.  Intuitively, this is because there are infinitely many p's or infinitely many q's iff there are infinitely many (p's or q's).
Foramlly,

$\pi\models G(Fp \vee Fq)$ iff at every index $i$, $\pi^i\models (Fp\vee Fq)$, meaning that in every index, there is eventually a $p$ or a $q$. Equivalently, this means that there are infinitely many $p$'s or $q$'s, which is equivalent to $\pi\models GFp\vee GFq$.

For the second pair - they are not equivalent. Try and think of a counter example. If you really can't - leave a comment.

The third pair are also equivalent. Informally - this is because they both state that after a finite prefix, both $p$ and $q$ always hold. The formal argument just follows from the semantics.


Why do we use DAG rather than trees to represent search space of a search problem?

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


Does an algorithm with complexity $\Theta(2^\sqrt{n})$ to solve any NP problem count as "good" and practical as any other polynomial algorithm?

Complexity is how an algorithm increases its number of steps in comparison to $n$ when we scale $n$ to a large value.

For very small $n$ , an algorithm with complexity $\Theta(2^\sqrt{n})$ can behave nearly as good as an algorithm running in polynomial time.But if we increase the $n$ , then certainly the algorithm with polynomial time will give much faster results.That's how algorithms are compared.One important thing to remember is that your $n$ is a variable related to input size and if this occurs as a power of something in time complexity then you can be sure that the algorithm is going to take a lot of time for large values of $n$.

$\Theta(2^\sqrt{n})$ is not as good as $\Theta(n\log n)$


Complexity calculations, assumptions on basic costs

It is generally referred to as "Random Access Machine" or RAM model. This model assumes that accessing any unit of data, irrespective of its position or type, takes the same constant amount of time. Now, what you take as a "unit" of data is important. For all practical purposes, we may consider the primitive data types, integer, float and characters (but not strings) as a unit of data. A single instruction on unit data is considered to take constant amount of time.


One approach would be to solve this using orthogonal range trees.  Orthogonal range trees allow range queries in $k$ dimensions.

Store the $n$ values of $Y$ in an orthogonal range tree.  The space complexity is $O(n (\lg n)^{k-1})$.

Next, for each $x=(x_1,\dots,x_k) \in X$, we're going to search for a matching $y \in Y$.  Notice that for $y$ to match this particular $x$, we must have $l_i - x_i \le y_i \le u_i - x_i$ for each $i$.  This means that $y$ must fall into the $k$-dimensional box $[l_1-x_1,u_1-x_1] \times \cdots \times [l_k-x_k,u_k-x_k]$.  So, we want to know if there is any element of $Y$ that falls within this box.  That's a $k$-dimension range query, which an orthogonal range tree can handle.

The time complexity is $O((\lg n)^k)$ for each range query.  We do $m$ range queries, so the total running time of this algorithm is $O(n (\lg n)^{k-1} + m (\lg n)^k)$.  Of course, there is a symmetry between $X$ and $Y$, so you can swap $m,n$ if that reduces the running time.

It is possible to reduce the asymptotic running time slightly further by using more sophisticated data structures and algorithms, but I don't know if they will actually help in practice.

Bottom line: A slightly pessimistic bound is that the running time is $O((n+m) (\lg n)^k)$ (but the preceding discussion shows you how to get a slightly tighter bound).  If $k$ is small enough this might be better than the $O(nmk)$ running time of the naive ("quadratic") algorithm.

Independently: Here is a heuristic that might help you in practice (even though it might not offer any guarantees in worst-case complexity).

Pick some value $k'$ such that $k'< k$.  Now randomly select a subset of $k'$ of the $k$ dimensions, and project everything to those $k'$ dimensions (so we temporarily ignore all of the other $k-k'$ coordinates).  That reduces the problem from a $k$-dimensional problem to a $k'$-dimensional problem.  In lower dimensions, the problem becomes easier, so you can solve the $k'$-dimensional problem to find all pairs $x\in X, y \in Y$ such that $x+y$ is correct in those particular $k'$ dimensions.  Then, you can test each such pair to see whether $x+y$ is correct in all $k$ dimensions.  The total running time will be the running time to solve the $k'$-dimensional problem, plus the running time to examine all pairs that survive the first phase.  You can then try to choose $k'$ to balance these two contributions to the total running time.

I suspect that if you experiment with this sort of idea, then in practice this might significantly improve performance (at least if you start with a large value of $k$).


Practical Implementation for Refinement Order on Integer Partitions

I suggest you try using integer linear programming.  Introduce $k\ell$ zero-or-one variables $x_{i,j}$, with the constraints

$$\sum_j x_{i,j} \lambda_j = \mu_i$$

and

$$\sum_i x_{i,j} = 1.$$

Feed it to an off-the-shelf ILP solver.  If it can find a feasible solution for you, then you know that $\lambda \le \mu$.  If it can determine that no solution exists, then you know that $\lambda \not\le \mu$.


How can we construct a TM with a Halt1 Oracle that decides if a TM halts on all inputs?

I think that I have an answer to this, putting together my question helped me clarify things enough to come up with this idea
def X(T : TM0):
   for n = 0 and up:
      if !Halt0('T(n)')
        return

Now if we ask Halt1('X(T)') we should get an answer

yes => T diverges on some input
no => T halts on all inputs

Does this all make sense logically?


Why do non regular languages have infinitely many equivalence classes?

There are at least two ways. The first way is to give infinitely many pairwise inequivalent words. In the case of your language, you can take $\{ a^n : n \geq 0 \}$, for example (exercise).

The second way is to prove that the language is not regular. The Myhill–Nerode theorem then implies that it has infinitely many equivalence classes. The reason is that for any language, we can construct a DFA (finite or infinite!) for the language whose states are the equivalence classes. If there are finitely many then this is a bona fide DFA, and we get that the language is regular. Conversely, for every regular language, the states of the minimal DFA correspond to the equivalence classes.


What's the difference between the rank and the degree of a type function?

The book states that the rank of a term is the number of $\Pi$'s in its (normal) form. But doesn't the number of such $\Pi$'s correspond exactly to the number of arguments it takes? That is, if a type function takes $n$ arguments, then doesn't that just mean there must be $n$ $\Pi$ symbols to capture those $n$ arguments?

Nope. Let $\sigma, \tau$ be types (i.e., type functions with degree=rank=$0$). The type
$$
\prod_{x:\sigma} \tau
$$
is the type of functions $\sigma \to \tau$, which do not take type arguments -- they take value arguments (of type $\sigma$). So, the degree is $0$ (not $1$), while the rank is $1$.


How to find the nearest point in the coordinate system

So, if I understand correctly, you have a set $S$ of points in some space (do you have a specific dimension ?), and a point $x$, and you want to find the point of $S$ that is the closest to $x$ ?

If this is indeed what you are trying to do, have a look at K-d trees and Voronoï tesselation. These methods are based on space partitioning to make queries faster.


Help writing a dynamic programming algorithm in English

Since this problem is a learning exercise of yours, I will just write the ordered subproblems used in dynamic programming. In general, I consider it is about more than half way through a nontrivial problem that can be solved by dynamic programming when the ordered subproblems have been specified clearly, at least in term of "difficult" thinking since the rest are more routine.

The subproblems are computing $v[i]$, the maximal total value you can get when you just finished party $P_i$. To help computing these subproblems, that is, from earlier subproblems to later subproblems, you may sort the parties by their ending times so that $P_1,P_2,\cdots,P_n$ end in order of time. After the sorting, $v[i]$ will only depend on those $v[j]$ where $j<i$ or, to be more precise, those $P_j$ whose ending time is before $P_i$'s starting time. (This condition can be made even more restrictive, which may be unnecessary for your exercise and which may be necessary to get a better grade.)  There are several more details such as the base case and the recurrence relation, which I will leave for you to fill in.


Turing degree incomparable with any countable-ordinal jump of another Turing degree?

The answer to your question is a resounding: IT DEPENDS! This takes us into some set theory, which - while interesting - is a bit off the beaten track perhaps for CS; to address this, I've made the first part of my answer strictly about the computability theory, and then added a separate section on the set theory side of things.

Before we can even address your question, it turns out that there is a surprising subtlety here:

  For $\alpha$ an arbitrary countable ordinal, it is not always clear how to define $0^{(\alpha)}$.

This is treated variously at mathoverflow and math.stackexchange; what I've written below should be self-contained, however.

The issue is that of presentations (or, essentially identically, fundamental sequences). In general, suppose $\lambda$ is a limit ordinal, we've defined $0^{(\alpha)}$ for each $\alpha<\lambda$, and we want to define $0^{(\lambda)}$ as the set $$Z_\lambda=\{(i, \alpha):i\in\omega,\alpha<\lambda,  i\in0^{(\alpha)}\}.$$ However, this set isn't a set of natural numbers. Fixing a map $f:\lambda\rightarrow\omega$, we can "interpret" $Z_\lambda$ along $f$ in a natural way: $$Z_\lambda^f=\{(i, j): i\in\omega, j\in ran(f), i\in 0^{(f^{-1}(j))}\}.$$ Here's the problem: what $f$ do we want to use? Different choices of $f$ will yield different sets, and potentially different Turing degrees. This wasn't an issue in cooking up $0^{(\omega)}$, since there was only one obvious thing to do, but when we try to go further the problem rears its head.

As a quick aside, there's an alternate approach here which seems promising at first: simply define $0^{(\lambda)}$ for $\lambda$ a limit ordinal to be the least upper bound of $\{0^{(\alpha)}:\alpha<\lambda\}$! Combined with the clause $0^{(\beta+1)}=(0^{(\beta)})'$, this would seem to give a recursive definition which works for all countable ordinals. However, it turns out that this entire attack is built on a false assumption: $0^{(\omega)}$ is not the least upper bound of $\{0^{(n)}:n<\omega\}$ in the Turing degrees, and in fact nontrivial least upper bounds never exist (this is the "exact pair theorem" of Spector). So we do necessarily have to do some work.

At this point it's a good idea to go back and try to develop a theory of iterated jumps "from scratch" as it were. This is hyperarithmetic theory due to Kleene, and is presented in detail in the beginning of Sacks' book; I'll just give a rapid (and ahistorical) gloss.

The sets $Z_\lambda^f$ defined above are intuitively what we get if we iterate the jump not along a mere ordinal but along an explicit well-ordering of a set of natural numbers (that is, a copy of the ordinal "labelled" appropriately). To make this precise, suppose $R$ is a well-ordering of some set $D$ of natural numbers (note that $R$ determines $D$). It's easy to show that there is a unique set $J_R$ of ordered pairs of natural numbers with the following properties:

$(x,y)\in J_R$ only if $x\in D$.
If $u$ is the $R$-successor of $v$, then $(u, y)\in J_R$ iff $\Phi_y^{J_R[v]}$ halts, where $J_R[v]=\{z: (v, z)\in J_R\}$.
If $u$ is an $R$-limit, then $J_R[u]=\{(v, y): v<_Ru, y\in J_R[v]\}.$

This is what you get, intuitively, if you iterate the jump along $R$ starting with the emptyset (the fact that we started with the emptyset was built in secretly to the last bulletpoint, since if $u$ is the $R$-least element then $J_R[u]$ is forced to be empty; we can relativize by starting with a non-empty column).

If $R$ is "nice," this is extremely well-behaved:

  Suppose $R_0, R_1$ are well-orderings of sets $D_0, D_1$ of natural numbers such that each $R_i$ is computable, their respective successor operations are computable, and their respective sets of limit elements are computable. Then if $R_0$ and $R_1$ have the same ordertype we have $J_{R_0}\equiv_TJ_{R_1}$.

The conditions above are stronger than merely demanding that the orderings be computable, but in fact every computable well-ordering is (non-computably!) order-isomorphic to such a "nice" computable well-ordering. So based on this, it makes sense to define $0^{(\alpha)}$ for $\alpha$ a "computable ordinal" as the unique Turing degree of a "jump sequence" along a "nice presentation" of $\alpha$. More generally, for any Turing degree $d$ it makes sense to talk about the degree $d^{(\alpha)}$ for any ordinal $\alpha$ with an $d$-computable presentation.

The sets computable from $0^{(\alpha)}$ for some computable $\alpha$ are the hyperarithmetic sets; hyperarithmeticity has a number of equivalent characterizations and is one of the fundamental notions of modern computability theory, and is also very important in descriptive set theory. But this only gets us through countably many ordinals; most countable ordinals don't have computable presentations! The supremum of the computable ordinals is denoted "$\omega_1^{CK}$" - it's much bigger than other popular ordinals like $\epsilon_0$, $\Gamma_0$, etc., but still countable, and indeed quite small among countable ordinals from various perspectives within logic. And it's not very hard to cook up two Turing degrees, neither of which is hyperarithmetic relative to the other, since we've only reached "countably high." Can we do better?

To go further, we need to get into set theory, so I'll put a horizontal line here:

Alright, let's talk about set theory. It turns out that we can continue the jump in a natural way past $\omega_1^{CK}$. However, this gets complicated pretty quickly. The idea comes from Godel's constructible universe, the idea being that each additional step in the $L$-hierarchy is like taking $\omega$-many jumps of what you have so far (since you're looking at everything first-order definable in what you have so far). Teasing this out precisely gets us the notion of mastercodes. I won't define them precisely here, but Hodes has an excellent paper on the topic.

Now, mastercodes have many subtle and annoying features,$^*$ but they let us unproblematically(ish) iterate the jump starting with the emptyset all the way up to $\omega_1^L$, the first ordinal which the constructible universe thinks is uncountable. (More generally, given a degree $d$ we can unproblemantically "do mastercodes" up to $\omega_1^{L[d]}$, the first orderinal that the smallest inner model of ZFC containing $d$ thinks is uncountable.)

If the constructible universe happens to be all there is - that is, if V=L - then we're peachy:

  Every real in $L$ is computable from some $0^{(\alpha)}$ - in the sense of mastercodes - for some $\alpha<\omega_1^L$.

More generally, "reachable via mastercodes" just gives us the notion of relative constructibility: $x\le_Ly$ iff $x\in L[y]$ iff $x$ is in every inner model containing $y$ iff $x$ is computable from some $y^{(\alpha)}$ for $\alpha<\omega_1^{L[y]}$.

However, it's quite possible - that is, consistent relative to ZFC - that $V$ is very far from $L$. For example, $\omega_1^L$ might be countable, and indeed the "real" $\omega_1$ could appear to be quite large from the perspective of $L$! Indeed, it turns out that strong set-theoretic hypotheses can prevent us from getting very far at all with this idea:

  Broadly speaking, if large cardinals exist then there are no easily-definable increasing $\omega_1$-sequences of Turing degrees. (This is parameterized: ramp up the large cardinals and we get more and more necessary undefinability.)

Even assuming $\omega_1^L=\omega_1$ and ruling out anything (like large cardinals) that will bump up consistency strength, the $\le_L$-degrees could still be quite wild, via forcing. In particular, if $c_0, c_1$ are mutually Cohen generic (say) over $L$, then $c_0\not\in L[c_1]$ and $c_1\not\in L[c_0]$; we can get Cohen generics without changing $\omega_1$, so in this case neither is reachable from the other via countably many jumps, assuming we buy the "mastercode picture" (and if we don't, we need to cook up another picture!).

$^*$They really only make sense at the level of degrees, not sets of naturals, so in that sense the "presentation issue" hasn't been avoided; see the middle of page 207 of Hodes' paper. More obnoxiously, Theorem 8 (and see the bottom of page 204 for the relevant definition) shows that ... OK, there's just no nice way to say this, and I can't put it off anymore: mastercode-jumps aren't fully monotone. We can have $\alpha<\beta$ but $a^{(\beta)}=0^{(\alpha)}$ for some degree $a$. Aaargh.


Asymptotic approximation of a recurrence relation (Akra-Bazzi doesn't seem to apply)

One possible approach might be by analogy to differential equations.  Let $T'(n) = T(n)-T(n-1)$.  Here $T'(n)$ is a discrete analog of the first derivative of $T(n)$.  We get the following relationship:
$$T'(n) = T(\lfloor \delta n \rfloor) + g(n).$$
The continuous analog of this is the differential equation
$$t'(x) = t(\delta x) + g(x),$$
or, if you prefer to see it written differently:
$${d \over dx} t(x) = t(\delta x) + g(x).$$
That's a differential equation.

Now you could try to solve the differential equation for the continuous function $t(x)$, then hypothesize that a similar function will be the solution to your original recurrence relation, and try to prove your hypothesis.  At least, this is one general approach you could follow.

I've forgotten everything I once knew about differential equations, so I don't know the solution that differential equation, but maybe you will be able to solve it by reviewing all the techniques for solving differential equations.


All four problems are NP-complete.

Let me start by proving two easy results:

Your problem #3 is NP-complete, even when the matrix has only a single row, as explained here: Complexity of a subset sum variant.
This implies that #4 is NP-complete as well, as #3 is a special case of #4.

Now for the strong result: Your problem #1 is NP-complete.  The proof of this is a bit more involved, but I'll show a reduction from ZOE to your #1, where ZOE is a problem that is known to be NP-complete.

In particular, here is the definition of ZOE:

ZERO-ONE EQUATIONS (ZOE)
Input: a $m\times n$ matrix $A$, all of whose entries are 0 or 1
Goal: Find a $n$-vector $x$, all of whose entries are 0 or 1, such that $Ax=1$, where $1$ denotes the all-ones vector

The ZOE problem is NP-complete.  This is proven in Chapter 8.3 of Algorithms (Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani).  The proof proceeds by reducing 3SAT to 3D Matching, and then reducing 3D Matching to ZOE.

Now we can reduce ZOE to #1, as follows.  If we have an instance of ZOE $A$, we transform it as follows.  For each variable $x_i$ of the ZOE instance, we add another variable $x^*_i$ and an equation $x_i + x^*_i = 1$.  (This has the effect of forcing $x_i$ to be either 0 or 1, since we'll require $x_i \ge 0$ and $x^*_i \ge 0$ and $x_i,x^*_i$ are integers.)  Thus, if the ZOE instance had a $m\times n$ matrix $A$, we now obtain $m+n$ equations in $2n$ unknowns, corresponding to some matrix $A'$.  In other words, we obtain a problem instance $A'x' = b$ where $b=1$ is the all-ones vector, and where every entry of $A'$ is 0 or 1.  This is now an instance of your problem #1.  This instance of your problem #1 has a feasible solution if and only if the original ZOE instance has a feasible solution.  This proves that any efficient algorithm to your #1 in turn yields an efficient algorithm for ZOE -- but since ZOE is NP-complete, it follows that #1 is NP-complete as well.

It follows from this result that #2, #3, and #4 are NP-complete as well, as #1 is a special case of them.


Network flow - minimum flow through edge

Yes, it is possible to solve such problems efficiently.  The minimum-cost circulation problem is a generalization of the standard network flow problem, which allows you to set both lower bounds and upper bounds on the flow through each edge.  (You can set all costs equal to 1.)  There are polynomial-time algorithms to solve instances of the minimum-cost circulation problem.

I don't know if there's a simple way to do with a standard algorithm for network flow.


How do processors fetch instructions that are longer than the word length?

In general there is not relation between the processor register size (32-bit for x86, 64-bit for x86_64) and the instruction size. Instructions are fetched by a dedicated hardware unit and the current instruction is stored the instruction register, but this register does not need to (and usually does not) have the same size as the data registers. On x86, this register must be able to hold 15 bytes. Instructions are fetched like everything else by issuing read commands to the memory. In general to speed up things, the CPU has an instruction cache so it will not just fetch one instruction at a time but rather an entire cache line at once.


Dinur and Steurer [1] showed that assuming $P \neq NP$, there is no polynomial time algorithm which approximates set cover by a $(1-\epsilon)\ln(n)$ factor, for any constant $\epsilon > 0$.
[1] https://arxiv.org/pdf/1305.1979.pdf