Find the number using binary search against one possible lie We all know this classic problem,  "there is some hidden number and you have to interactively guess it.", which could be solved using binary search when we know that maximum number that we can guess.

But what if the interactor may lie to us in one case? For example, the number is $3$ and the maximum number we can guess is $10$, but when we ask whether it is greater than $5$ and it replies yes and for the rest of queries it answers correctly. A simple binary search would fail.

How to proceed in this case? What is the minimum number of query in the worst case?

A generalization of this class of problems is widely studied. See, e.g., this paper for a survey.

In your particular case, the problem can be easily solved without any asymptotic change in the computational complexity. Run the binary search three times. At least two of the three results must be equal to the hidden number. Return the majority result.

There are other elegant ways to handle up to $k$ of lies by only using $O(\log n + k)$ time (where $k$ might be a function of $n$).


Why does Coq include let-expressions in its core language Coq includes let-expressions in its core language.
We can translate let-expressions to applications like this:
let x : t = v in b ~> (\(x:t). b) v
I understand that this does not always work because the value v would not be available when typechecking b. However this can be easily fixed by special casing the typechecking of applications of the form (\(x:t). b) v. This allows us to remove let-expressions at the cost of a special case while typechecking. Why does Coq include still include let-expressions? Do they have other advantages (besides not needing the special case)?

It is a common misconception that we can translate let-expresions to applications. The difference between let x : t := b in v and (fun x : t => v) b is that in the let-expression, during type-checking of v we know that x is equal to b, but in the application we do not (the subexpression fun x : t => v has to make sense on its own).

Here is an example:

(* Dependent type of vectors. *)
Inductive Vector {A : Type} : nat -> Type :=
  | nil : Vector 0
  | cons : forall n, A -> Vector n -> Vector (S n).

(* This works. *)
Check (let n := 0 in cons n 42 nil).

(* This fails. *)
Check ((fun (n : nat) => cons n 42 nil) 0).

Your suggestion to make application (fun x : t => v) b a special case does not really work. Let us think about it more carefully.

For example, how would you deal with this, continuing the above example?

Definition a := (fun (n : nat) => cons n 42 nil).
Check a 0.

Presumably this will not work because a cannot be typed, but if we unfold its definition, we get a well-typed expression. Do you think the users will love us, or hate us for our design decision?

You need to think carefully what it means to have the "special case". If I have an application e₁ e₂, should I normalize e₁ before I decide whether it is a $\lambda$-abstraction? If yes, this means I will be normalizing ill-typed expressions, and those might cycle. If no, the usability of your proposal seems questionable.

You would also break the fundamental theorem which says that every sub-expression of a well-typed expression is well-typed. That's as sensible as introducing null into Java.


Probability that a random graph will remain planar after adding an edge According to this answer, a random graph on $n$ vertices is a graph which has each of the $n\choose2$ edges independently with probability $1/2$ each. The probability of at most $3n-6$ edges (which is a necessary condition for planarity) is: $$2^{-n(n-1)/2}\sum_{k=0}^{3n-6}{n(n-1)/2\choose k}$$

Therefore, the plot for this equation is:

  If I choose a random graph with 10 vertices, what is the probability
  that it will remain planar after adding an edge between two randomly
  chosen vertices?

To be more clear:

Consider event $P_{1}$, the event of choosing a planar graph $G_{1}$ in the universe $U_{10}$ of graphs with 10 vertices.

Consider a subset $S$ of the universe of graphs with 11 vertices $U_{11}$ conditionally defined by the graph $G_{1}$ we got in event $P_{1}$ in this way: $S$ is formed by all possible graphs that can result from adding one edge to $G_{1}$.

And then finally consider event $P_{2}$, the event of choosing a planar graph in the universe $S$ defined in the previous step.

Therefore I want to know what is the probability of event $P_{2}$.

Possible solution:

I followed D.W.'s advice below and wrote a small simulation. According to the code, the probability of choosing a planar graph of 10 vertices is 0.0915 ( 9,15% ) and the probability of a given planar graph of 10 vertices remaining planar after adding one random edge is 0.6140 ( 61,40% ).

#!/usr/bin/python3
import planarity
from itertools import combinations
import random
from multiprocessing import Process, Manager, Pool, cpu_count
import json

nodes = [str(x) for x in range(10)]
edges = list(combinations(nodes,2))
tests = 10**6
filename = 'results.json'
runs = 100

def make_test():
    while 1:
        chosen_edges = list(filter(lambda x: x != None, [x if random.choice([0,1]) else None for x in edges]))
        if planarity.is_planar(chosen_edges):
            break
    extra_edge = random.choice( list(set(edges) - set(chosen_edges)) )
    chosen_edges += [extra_edge]
    return planarity.is_planar(chosen_edges)

if __name__ == '__main__':

    for i in range(runs):
        with Pool(processes=cpu_count()) as pool:
            results = [ pool.apply_async(make_test, ()) for i in range(tests) ]
            lst = [ res.get(timeout=1) for res in results ]
        pool.close()
        pool.join()

        n = len(lst)
        p = len(list(filter(lambda x: x != False, lst)))
        prob = ( p / n )
        print(prob)

        try:
            with open(filename,'r') as f:
                file_lst = json.load(f)
        except:
            open(filename,'w+').close()
            file_lst = []
        file_lst += [prob]
        with open(filename,'w') as f:
            json.dump(file_lst,f)

Let $S$ be the set of planar graphs on $n$ vertices, and let $E(S,\overline{S})$ be the set of edges between $S$ and its complement, that is, the set of pairs $(G,e)$ where $G \in S$ and $G \cup \{e\} \notin S$. The edge-isoperimetric inequality states that
$$
\frac{|E(S,\overline{S})|}{|S|} \geq \binom{n}{2} - \log_2 |S|.
$$
It follows that the probability that you're after is at most
$$
\frac{\log_2 |S|}{\binom{n}{2}-(3n-6)}.
$$
It is known that $\log_2 |S| = O(n \log n)$ (see for example Gimenez and Noy, The number of planar graphs and properties of random
planar graphs, and so we conclude that your probability is at most $O\left(\frac{\log n}{n}\right)$.

On the other hand, the same paper shows that with constant probability, a random planar graph has an isolated vertex. When this happens, there is $\Omega\left(\frac{1}{n}\right)$ probability to add an edge adjacent to it, leaving the graph planar. Hence your probability is at least $\Omega\left(\frac{1}{n}\right)$.


Are all computational complexity results oracle results? When talking about the complexity of a given operation, say multiplication of numbers, one usually counts the number of "elementary operations" that are required.

For example, a common argument says that multiplying two $n$-digit numbers with the schoolbook standard method takes $O(n^2)$ operations, while more sophisticated techniques give complexities closer to $O(n)$.

In these examples, what is counted is the number of single-digit operations, but then the complexity of those operations themselves is not taken into account.
Isn't this then essentially an oracular result, in the sense that it tells us the number of operations we have to perform, provided we have a magical box solving single-digit operations?

The issue you are highlighting is that of computation model, which is how we measure the resource consumption of an algorithm. The computation model specifies how to assign time complexity, space complexity, and so on to a given program (whose syntax it also specifies). There are three popular computation models:

Turing machines, of various sorts.
Boolean circuits.
RAM machines, of various variants.

A variant of the RAM machine can be specified in terms of the allowable basic operations, which is the issue that you encountered. For Boolean circuits, the analog is the set of allowable gates, and for Turing machines there seems to be no such analog.

In contrast, here is an actual example of how oracles are used in theoretical computer science.

A submodular function is a set function $f\colon 2^U \to \mathbb{R}$ (i.e., a function that accepts a subset of $U$ as input, and returns a real output) that satisfies a technical constraint known as submodularity.

Submodular optimization is the field which studies how to optimize submodular functions relative to various constraints (including no constraints).

A typical problem is:

  Given a submodular function, find its minimum.

How is the submodular function "given" to us? It could be given to us as a truth table (i.e., the value of $f(A)$ for any $A \subseteq U$), but this is not a realtistic assumption. Rather, there is often an efficient algorithm that computes $f$. In most cases we are interested in an algorithm which is oblivious to the exact algorithm used to compute $f$. In these cases, we are looking for an algorithm which has oracle access to $f$, that is, the function $f$ is provided as an input oracle.

(In other cases we would like to use the code for $f$. This happens usually when $f$ has a particular structure, for example if it is a coverage function. In cryptography we sometimes want to "open the black box" even when $f$ has no particular structure.)


Does linear programming admit a strongly polynomial-time algorithm? The linear programming problem: find a strongly-polynomial time algorithm which for given matrix A ∈ Rm×n and b ∈ Rm decides whether there exists x ∈ Rn with Ax ≥ b.

I know that Steve Smale's lists some of the unsolved problems in mathematics. But such a linear programming problem is it until now not-solvable ?

This problem is still open. See for example Wikipedia, which while not a dependable source in general, will probably be updated if a strongly polynomial time algorithm is ever found.


Sorting strings with "before" and "after" constraints I'm trying to solve a constraint-satisfaction problem for a project of mine that seems like it should have a well-known solution, but I can't for the life of me seem to find it described anywhere.

I've been poring over what literature I can find about CSP's and none of the general stuff seems to be clicking. I feel like maybe my CS chops just aren't quite up to the task, so feel free to point me to some tutorial that will make me feel stupid for even asking this, if such a thing exists.

What I'm looking to do is this:

Given a list of unique strings, where each string may have either, both, or neither of the following constraints associated with it:

before, which references another string in the list, and ensures that this string occurs before that one in the final sorting.
after, which also references another string in the list, and ensures that this string occurs after that one in the final sorting.

Sort the strings in a way that can guarantee satisfaction of all constraints.

Something like this:

'bar', no constraints
'foo', before 'bar'
'baz', no constraints
'qux', after 'baz'
'quux' before 'baz', after 'foo'

Will result in a final sort like this:

'foo'
'bar'
'quux'
'baz'
'qux'

Though it isn't a hard requirement, I would prefer the result be deterministic. There are several alternate answers to the problem above, as 'bar' has no constraints besides being after 'foo'. Of course, I don't really care which one I get back as long as the algorithm reliably produces the same result each time.

I wouldn't be surprised to learn that such determinism is impossible since it seems to be one of the biggest reasons I keep running into blocks, but I've thus far been unable to prove to myself that it can't be done.

Of course, I'll also need to be able to detect sets of constraints that are impossible to satisfy-- such as this one:

'foo', no constraints
'bar', after 'foo'
'baz', after 'bar', before 'foo'

In cases like this I don't need any kind of answer. I just need to detect it so I can throw an exception.

So far may natural inclination has been to bust out a genetic algorithm, but that of course kills the determinism and would be wasteful if there is a better solution that just requires me to know what the heck I'm doing, lol. So I want to see if I can rule out that possibility before proceeding.

Thanks ahead of time!

Construct a directed graph in which $a \to b$ if $a$ is constrained to appear before $b$. Run a topological search. If it finds a directed cycle, there is no solution. Otherwise, it gives you some canonical solution.


Using substitution method to prove asymptotic lower bound of $T(n) = T(n-1) + \Theta (n)$ I try to prove that the asymptotics of the recurrence
$
T(n) = T(n-1) + \Theta (n)
$
is
$
T(n) = \Theta(n^2)
$.

By $\Theta$, I mean tight bound from above and below.

I can write the equation like this:
$$
T(n) = T(n-1) + \Theta (n) = T(n-1) + cn.
$$

I'm having a hard time proving the lower bound with this method, do you have any idea how?

What I did for Upper bound is:

Assume:
$$
T(n-1) \leq c(n-1)^2, \quad c \in R
$$

Therefore:
$$
T(n) \leq c(n-1)^2 + cn = cn^2 - 2cn + c + cn = cn^2 - cn + c \leq cn^2
$$

Therefore I get:
$$
T(n) \leq O(n^2)
$$

For $O$, by which I mean just an upper bound.

So, how do I prove a matching lower bound using this method?

Let $f(n) = \Theta(n)$. Thus there are $N,a,b>0$ such that for $n \geq N$, we have $an \leq f(n) \leq bn$.

Now suppose that $T(n) = T(n-1) + f(n)$, with some base case $T(0) = C$. Unrolling the sum,
$$
T(n) = C + f(1) + \cdots + f(n).
$$
Let $D = C + f(1) + \cdots + f(N-1)$. For $n \geq N$,
$$
T(n) \leq D + b(N + \cdots + n) = D + b\frac{(n-N+1)(n+N)}{2} = O(n^2).
$$
Similarly,
$$
T(n) \geq D + a(N + \cdots + n) = D + a\frac{(n-N+1)(n+N)}{2} = \Omega(n^2).
$$


Motivation for Inverse Reinforcement Learning Learning a policy from sparse reward information (a reward function where a positive reward is only generated at the goal state) is challenging due to the resulting sparse feedback.
One solution is to shape the reward to enrich feedback during learning. Unfortunately, shaping the reward is challenging and often leads to unusual behavior or even situations where the learning agent just harvests intermediate rewards rather than achieving the task.
A proposed solution is to have an expert generate demonstrations of the desired task and have the learning agent learn a reward function that is consistent with the demonstrated behavior. The learning agent can then use this learned reward function to learn an optimal policy.
This last point is where I am confused. The whole motivation for IRL is learning, that is, finding a policy when the model is unknown, but why would the learning agent not know its own transition model? On the other hand, if the transition model is known, then finding the optimal policy from the learned reward function is not actually a learning problem.

Often the transition model is not known in advance.  For instance, consider a complex system like flying a helicopter or surfing a surfboard.  It's not easy to characterize in advance what the behavior of the system will be, in response to certain control inputs; the relationship may be highly nonlinear and complex.


Which Is a Better Way of Obtaining Scales, Gaussian Blur or Down Sampling? In computer vision, scales are important when we carry out a scene analysis. Choosing different scales affect the result of the analysis. For example, if a face is relatively small in the scene, then the details including nose, eyes will be omitted. On the other hand, details on larger faces become relatively more salient.

I know both Gaussian Blur with different sigmas and Down Sampling on the image can generate different scales. Which is more reasonable on a cognitive sense?

Down sampling may discard relevant features, while blurring should not.

As a toy example, a down sample may remove a pixel which is a local maxima, while a blur operation will preserve the maxima by increasing the values of nearby pixels. If the local maxima corresponds to an interesting feature, it may still be discernible by the human eye after blurring.

From a computational sense, Laplacian pyramids are able to reconstruct an image precisely because a blur-subtract operation preserves the "information" in the scene.


Term rewrite system is non-confluent, but cannot find different normal forms of term I wrote a simple TRS that I believe is non-confluent, but I'm not able to find a term with two normal forms for it.

The TRS is defined on the signature $\mathcal F=\{f,\ l,\ s,\ o\}$ and the rewrite rules $\mathcal R$ are defined as follows:

$l\to s(o)$
$t(x,\ l)\to s(x)$
$t(l,\ x)\to s(x)$.

This TRS is clearly finite and terminating.

For the first two rules, we have a critical pair $(t(x,\ s(o)),\ s(x))$ which is not joinable. Therefore, the TRS is not confluent.

It seems that for such a simple example I should be able to find a term with two normal forms. What am I missing?

$t(o,l)$ has two normal forms: $t(o,l)\to s(o)$ and $t(o,l)\to t(o,s(o))$.


weight constrained shortest path problem variants Given a graph $G=(V,E)$, metric spaces $\delta:E\rightarrow \mathbb{Z}^{+}$ and $w:E\rightarrow \mathbb{Z}^{+}$, terminal vertices $s,t\in V$, do there exists $s\rightarrow t$ path $P=(V_{p},E_{p})$ such that $\sum_{e\in E_{p}} w(e) \leq W$ and $\sum_{e\in E_{p}} \delta(e) \leq K$, where $W,K\in Z^{+}$.

This is Weight constrained Shortest Path Problem, and known to be NP-complete for undirected as well as directed even acyclic graphs. as long as $\delta$ and $w$ is not equal for all edges. Now if we move weight from edges to vertices and change $\leq$ of total weight constraint to $=$ then the new problem is:

Given a directed acyclic graph $G=(V,E)$, metric spaces $\delta:E\rightarrow \mathbb{Z}^{+}$ and $w:V\rightarrow \mathbb{Z}^{+}$, terminal vertices $s,t\in V$, do there exists $s\rightarrow t$ path $P=(V_{p},E_{p})$ such that $\sum_{v\in V_{p}} w(v) = W$ and $\sum_{e\in E_{p}} \delta(e) \leq K$.

Is this problem known ? is this solvable in P time ? or this is NP-complete too ? I think even if we replace $\mathbb{Z}^{+}$ with $\mathbb{R}^{+}$ it will not change nature of the problem.

If we set $W=\vert V \vert$ then it tries to reach all the vertices which looks like hamiltonian path problem, but it is a DAG.

Update

I was trying to reduce it from Subset Sum as suggested by @D.W.

Given $X=\{1,2,3\}$ of size $\vert X \vert = n$ I can convert that to a graph of $n^{2}+n+2$ vertices. We can make $n$ layers of $X$ and connect every vertex with all vertices of next layer except itself. Keep a vertex with 0 weight on each layer. As show below.

But this reduction has 2 restrictions.

Every Layer is not complete bipartite (e.g. $2_{i}$ does not connect to $2_{i+1}$).
Every layer must have a vertex with 0 weight.

Now this does not prove the second problem for General purpose DAG. I can not connect $x_{i}\rightarrow x_{i+1}$ because that will change the original problem. So if there is a DAG that looks very similar to this one but have $n^{2}$ edges between each layer and have no 0 weight vertex this reduction does not apply to that graph.

Also in this formulation I can take the same element twice $1_{1}\rightarrow 2_{2}\rightarrow 1_{3}$ which will add to $4$. Which I should not be allowed

Check the definition of reduction again.  A reduction that works for general dags is a perfectly valid reduction.  It meets all of the conditions in the definition.  I suggest working through the definition -- that should help you see what is going on.

Or, to put it another way: The problem for "general DAG" is at least as hard as the problem for "a particular type of DAG", so if you've proved the problem is NP-hard for a particular type of DAG, you've also proven it is NP-hard for general DAGs, too.


Star notation for context-free language alphabet? I noticed that some "design-the-grammar" problems say verbally

Alphabet is $\mathbf{\{0,1\}}$.
$\{w \mid w \text{ contains at least three 1s}\}$

and some problems list it as

$\{ w ∈ \mathbf{\{0,1\}}^* \mid w \text{ contains at least three 1s} \}$

So, my question is: Is the in-line notation with the asterisk star '*' (as in "$\{0,1\}^*$") equivalent to saying "alphabet is $\{0,1\}$", or are those alphabets different?

It is equivalent (usually, otherwise it would be explicitly stated).
The "star-operation" is called a Kleene-star, and it is an operation that basically takes the set and creats the set of all combinations of items from the original set. In the example of $\{0,1\}$, we would have that $\{0,1\}^*=\{0^{k_1}1^{k_2}0^{k_3}\dots\mid k_1,k_2,\dots\in \mathbb{N}\}$, and intuitively speaking, this is the set of all words created from the alphabet $\{0,1\}$. This obviously is also true for any other alphabet $\Sigma$ you would want.


How to prove that a language is context-free? There are many techniques to prove that a language is not context-free, but how do I prove that a language is context-free?

What techniques are there to prove this?  Obviously, one way is to exhibit a context-free grammar for the language.  Are there any systematic techniques to find a context-free grammar for a given language?

For regular languages, there are systematic ways to derive a regular grammar / finite-state automaton: for instance, the Myhill-Nerode theorem provides one way.  Is there any corresponding technique for context-free languages?

My motivation here is to (hopefully) build up a reference question that contains a list of techniques that are often helpful, when trying to prove that a given language is context-free.  Since we have many questions here that are special cases of this, it would be nice if we could document the general approach or general techniques that one can use when facing this sort of problem.

A practical approach that in many examples works [but not always, I know] is trying to find the nesting structure of the strings in the language. "Nested dependencies" have to be generated at the same time in different parts of the string.
Also we have the basic toolbox:

concatenation: $S\to S_1S_2$ if you can split the language in two consecutive parts use this production

union: $S\to S_1 \mid S_2$ split into disjoint parts

iteration: $S\to S_1S \mid \varepsilon$

Example 1
Unequal numbers can be handled using a simple trick.
$L= \{ a^mb^n \mid m\neq n \}$
Now clearly
$L= \{ a^mb^n \mid m< n \} \cup  \{ a^mb^n \mid m> n \}$.
Consider first half: $L_1 = \{ a^mb^n \mid m< n \}$. If there must be more $b$'s we can generate an equal numbers of $a$'s and $b$'s on the one and and add at least one extra $b$:
$L_1 = \{ a^mb^m b^i \mid m\ge 0, i>0 \} = \{ a^mb^m \mid m\ge 0 \}\cdot \{ b^i \mid i>0\}$. This we can handle with concatenation from the basic toolbox.
Now the complete language also deal with the case we have more $a$'s. This we handle by using union.
$S \to S_1 \mid S_2$ (choose which part)
$S_1 \to XB$ (extra $b$ part)
$X\to aXb\mid \varepsilon$ (equal number of $a$ and $b$)
$B \to Bb \mid b$ (one or more $b$'s)
$S_2 \to AX$ (extra $a$ part)
$A \to Aa \mid a$ (one or more $a$'s)
Example 2
Here an example for the nesting (thank you Raphael).
$L=\{b^ka^l(bc)^ma^nb^o \mid k,l,m,n,o\in {\Bbb N},k\neq o,2l=n,m\ge 2 \}$
Replace $n$ by $2l$. We can now drop $n$ in conditions.
Replace $k \neq o$ by $k > o \text{ or } k < o$ (confused? $o$ is 'oh' not 'zero'). Apply tools for union. We work with $k > o$ here. Also $k>o$ iff $k=s+o$ and $s>0$ where $s$ is a new variable. Replace $k$ by $s+o$.
$L_1 =\{b^{s+o}a^l(bc)^ma^{2l}b^o \mid l,m,o,s\in {\Bbb N},s>0,m\ge 2 \}$
Some simple rewrites.
$L_1 =\{bb^sb^o a^l bcbc(bc)^m (aa)^{l}b^o \mid l,m,o,s\in {\Bbb N}  \}$
Now we see the nesting structure, and start building a grammar.
$S_1 \to TV$, $T\to bU$, $U\to bU \mid \varepsilon$ (see: concatenation and iteration here)
$V \to bVb \mid W$ (we generate $o$ $b$'s on both sides)
$W \to aWaa\mid X$
$X\to YZ$, $Y\to bcbc$, $Z\to bcZ\mid \varepsilon$
Example 3
$K =\{ a^kb^lc^m \mid l=m+k\}$
A first "obvious" rewrite.
$K =\{ a^kb^{m+k}c^m \mid m,k\ge 0\} = \{ a^kb^mb^kc^m \mid m,k\ge 0\}$
In linguistice this is called "cross-serial dependency": the interleaving $k,m,k,m$ (usually) strongly indicates non-contextfreeness. Of course $m+k=k+m$ and we are saved.
$K =\{ a^kb^{k+m}c^m \mid m,k\ge 0\} = \{ a^kb^kb^mc^m \mid m,k\ge 0\}$
with productions $S\to XY$, $X\to aXb\mid \varepsilon$, $Y\to bYc\mid \varepsilon$
Similarly $K'= \{ a^kb^lc^m \mid m=k+l\} = \{ a^kb^lc^lc^k \mid k,l\ge 0\}$
with productions $S\to aSc \mid X$, $X\to bXc\mid \varepsilon$

Final comment: these techniques help you come up with a candidate context-free grammar that will hopefully recognize your language.  A correctness proof may still be needed, to ensure that the grammar really works to recognize your language (nothing more, and nothing less).


If $f$ and $g$ are increasing functions, are we guaranteed that $f=O(g)$ or $g=O(f)$? Given two increasing functions $f$ and $g$ with values in the natural numbers, is it always the case that either $f\in O(g)$ or $g\in O(f)$.

If the statement is true, then can anyone provide a counterexample for when any of the two conditions in bold are relaxed.

If the statement is false, can someone provide a counterexample to show why

I believe that the statement is true and my attempt at the proof is by assuming without loss of generality that $f\notin O(g)$

$f\notin O(g)\implies\neg(\exists N\in\mathbb{N}$ s.t $f(n)\leq Cg(n)$, for some $C>0$ and $\forall n>N)$

$\implies\forall N\in\mathbb{N}\space,\space f(n)>Cg(n)$, for some $C>0$ and $\forall n>N$

Have I negated the expression correctly, because I can't see how I can get $g\in O(f)$ from this expression

If $f = O(g)$, then

$$\exists n_0. \exists c. \forall n. (n > n_0 \rightarrow f(n) \le c g(n))$$

The negation of this statement is

$$\forall n_0. \forall c. \exists n. (n > n_0 \land f(n) > c g(n))$$

This doesn't match your negation, so I believe your proof is incorrect.

I actually think the statement you're trying to prove is false. Try constructing functions f and g so that f is double g for a while, then g overtakes f and is triple f for a while, the f overtakes g and is quadruple g for a while, etc. Could you show that neither function is O of the other?

Hope this helps!


Verify correctness of quantifier elimination, using SAT Let $x=(x_1,\dots,x_n)$ and $y=(y_1,\dots,y_n)$ be $n$-vectors of boolean variables.  I have a boolean predicate $Q(x,y)$ on $x,y$.  I give my friend Priscilla $Q(x,y)$.  In response, she gives me $P(x)$, a boolean predicate on $x$, and she claims that

$$P(x) \equiv \exists y . Q(x,y),$$

or in other words, that

$$\forall x . [P(x) \Leftrightarrow \exists y . Q(x,y)].$$

I would like to verify her claim somehow.  How can Priscilla help me verify this claim?

You can assume that both $P$ and $Q$ are represented as CNF formulas, and that they're not too large (polynomial size, or something).

In an ideal world, it'd be awesome if I could reduce the problem of verifying this claim to SAT: I have a SAT solver, and it'd be great if I can use the SAT solver to verify this claim.  However, I'm pretty sure that it's not going to be possible to formulate the problem of verifying this claim directly as a SAT instance; testing the validity of a 2QBF formula is almost certainly harder than SAT.  (The $\Leftarrow$ direction is easy to formulate as a SAT instance, but the $\Rightarrow$ direction is hard because it inherently involves two alternating quantifiers.)

But suppose Priscilla could give me some additional evidence to support her claim.  Is there some additional evidence or witness Priscilla could give me, which would make it easy for me to verify her claim?  In particular, is there some additional evidence or witness she could give me, which would make it easy for me to formulate the problem of verifying her claim as an instance of SAT (which I can then apply my SAT solver to)?

One unusual aspect of my setting is that I'm assuming (heuristically) that I have an oracle for SAT.  If you like complexity theory, you can think about it this way: I am taking the role of a machine that can compute things in $P^{NP}$ (i.e., in $\Delta^P_2$), and I'm looking to verify Priscilla's claim using an algorithm in $P^{NP}$.  My thanks to mdx for this way of thinking about things.

My motivation/application: I'm looking to do formal verification of a system (e.g., symbolic model checking), and a key step in the reasoning involves quantifier elimination (i.e., starting from $Q$, obtain $P$).  I'm hoping for some clean way to verify that the quantifier elimination was done correctly.

If there's no solution that works for all possible $P,Q$, feel free to suggest a solution that is "sound but not complete", i.e., a technique that for many $P,Q$ lets me verify the claimed equivalence. (Even if it fails to verify the claim on some $P,Q$ that do satisfy the claim, I can still try this as a heuristic, as long as it never inappropriately claims to have verified a false claim.  On any given $P,Q$, it might work, or it might not; if it doesn't work, I'm no worse off than where I started.)

Here are two techniques I've been able to identify:

Identify an explicit Skolem function. Suppose Priscilla can identify an explicit function $f$ such that

$$\forall x . P(x) \Leftrightarrow Q(x,f(x))$$

holds.  Then it follows that Priscilla's claim is correct.

This means that Priscilla can help us verify her claim by providing a function $f$ so that the above proposition holds.  We can confirm that the above proposition holds by testing the following formula for satisfiability:

$$\neg (P(x) \Leftrightarrow Q(x,f(x))).$$

If this formula is not satisfiable, then Priscilla's claim has been verified.

One caveat is that Priscilla needs to be able to identify a suitable function $f$.  A further caveat is that we need $f$ to be concretely representable in some concise form, say, as a polynomial-sized boolean circuit.  However, if those conditions are met, then this technique should work.
A hybrid argument.  Consider the special case of this problem, where we are quantifying over a one-bit variable (rather than a $n$-bit variable); it turns out the problem is easy to solve in this case.  This suggests that we try to chain that technique $n$ times, each time removing one more bit of $y$.  It turns out that this idea will sometimes work, but not always.

Let me explain how to verify Priscilla's claim in the case where $y=(y_1)$ is a one-bit variable.  Then $\exists y . Q(x,y)$ is equivalent to $Q(x,\text{False}) \lor Q(x,\text{True})$.  The latter formula is at most twice as large as $Q$, so still polynomial sized.  Now we can use our SAT solver to test whether $Q(x,\text{False}) \lor Q(x,\text{True})$ is equivalent to $P(x)$; the equivalence holds exactly if the following formula is not satisfiable:

$$\neg (P(x) \Leftrightarrow (Q(x,\text{False}) \lor Q(x,\text{True}))).$$

So, if we're quantifying over a single bit, this gives a way to verify that the quantifier elimination was done correctly.

To solve the original problem, apply this multiple times.  Priscilla's job will be to give us $n+1$ boolean predicates $R_0,R_1,R_2,\dots,R_n$ such that

$$R_i(x,(y_{i+1},\dots,y_n)) \equiv \exists y_1,y_2,\dots,y_i . Q(x,y).$$

Our task will be to verify whether all of these boolean predicates were correctly generated.  We can do this by testing whether $Q(x,y) \equiv R_0(x,y)$, $P(x) \equiv R_n(x)$,

$$R_{i+1}(x,(y_{i+2},\dots,y_n)) \equiv \exists y_{i+1} . R_i(x,(y_{i+1},\dots,y_n)) \qquad \text{for $i=1,2,\dots,n-1$}.$$

Notice that the latter is an instance of quantifier elimination with a single bit, so we've already described how to test it was done correctly using a SAT solver.  We can also test whether $Q \equiv R_0$ and $P \equiv R$ using a SAT solver straightforwardly.  So, we can check whether Priscilla generated $R_0,\dots,R_n$ correctly.  If she did, then we've verified that $P$ was generated suitably.

One caveat is that Priscilla needs to be able to generate the $R_i$'s.  A bigger caveat is that the size of all the $R_i$'s needs to be reasonable (say, polynomial-sized).  If Priscilla generates the $R_i$'s naively, their size might grow exponentially with $i$, which is no good.  So, Priscilla will need a way to simplify at each stage; there needs to exist some sequence of $R_0,\dots,R_n$ that are all polynomial-sized, and Priscilla needs to be able to find such a sequence.  That is by no means guaranteed.  That said, if Priscilla can do this, then this technique should work.

I'm not fully satisfied with these techniques -- they are incomplete heuristics, and they might fail on some/many problem instances -- so I would still be interested to see other ways of approaching this problem.


Show that the Turing Machine domain can be viewed as a classical planning domain This is one of my assignments. I am not able to comprehend how to reduce the Turing machine domain to Classical planning domain. My understanding is that we have to essentially perform complexity analysis of classical planning domain. So I have defined these two languages

a)  PLAN-EXISTENCE(D) = {P : P is the statement of a planning problem that has a solution}

b)  PLAN-LENGTH(D) = {(P,n) : P is the statement of a planning problem that has a  solution that contains no more than n actions (length ≤ n) }

And then I proceed to prove that both these are decidable in classical planning domain.

Is this the correct approach? Please help me

In order to show that the computation of a Turing machine can be modeled as a planning problem, you can encode the tape symbols, the head position and state, and the execution of a transition using states:

symb(i,x)   : i-th cell of the tape contains symbol x
head(i,q)   : head is over cell i in state q
exec(i,q,x) : execute the transition at i-th cell in state q over symbol x
accept      : accept the input

At the beginning symb(i,x) are true/false according to tape content; head(1, q0) is true; and all other states are false. The goal G is {accept}.

Actions are built using the transition table of the Turing machine; suppose that you have the transition:

 a, q0 -> b, q1, Left

Then for every cell i of the tape you can add the actions:

 symb(i,a) AND head(i,q0) => !head(i,a) AND exec(i,q0,a)
 exec(i,q0,a) AND symb(i,a) => !symb(i,a) AND symb(i,b)
 exec(i,q0,a) AND symb(i,b) => !exec(i,q0,a) AND head(i+1,q1)

The actions for the transitions to accepting states are similar.

Note that actions with only 2 positive preconditions and two postconditions are enough to "simulate" the behaviour of a Turing machine.


Log-Space Reduction $USTCON\le_L CO-2Col$ I want to show that $USTCON\le_L CO-2Col$ (Log-Space reduction)

$USTCON$
The $s-t$ connectivity problem for undirected graphs is
called $USTCON$.

Input: An undirected graph $G=(V,E)$, $s,t \in V$. Output: 1 iff $s$ is connected to $t$ in $G$.

$CO-2Col$
A graph is $2$-colorable if there is a way to color the vertices
of $G$ with $2$ colors, such that for every edge the two vertices
on the edge are colored differently. $CO-2Col$ is the following
problem:

Input: An undirected graph $G$. Output: 1 iff $G$ is NOT $2$-colorable.

I know this can be solved by simply using the $USTCON$ decision algorithm and then output a bipartite or non-bipartite graph accordingly. But is there any other reduction that actually changes the input graph?

Let USTCON2 be the following problem: given a graph $G$ and two vertices $s,t$, decide whether there is a walk from $s$ to $t$ of even length. Let us show first that USTCON2 reduces to co2COL.

Given a graph $G = (V,E)$ and two vertices $s,t$, construct a new graph whose vertex set consists of two copies of $V$. For every $(a,b) \in E$, connect $a$ in the first copy to $b$ in the second copy, and $a$ in the second copy to $b$ in the first copy. So far the graph is bipartite. Now connect $s$ and $t$ in the first copy. The new graph is bipartite iff there is no path of even length from $s$ to $t$ in the original graph.

Now let us reduce USTCON to USTCON2. Given a graph $G = (V,E)$ and two vertices $s,t$, add two new vertices $x,y$, and edges $(s,x),(x,y),(y,s)$. There is a walk from $s$ to $t$ in the original graph iff there is a walk of even length from $s$ to $t$ in the new graph.


Finding odd directed circuit I want to write an algorithm to find whether a directed circuit whose length is odd exists in a strongly connected digraph.

Can anyone help me how to proceed with this problem???

Firstly:

  König's Theorem (1936): A graph is 2-colorable iff it has no circuits of odd length.

  ― www-math.ucdenver.edu

Also:

  A graph is bipartite if and only if it does not contain an odd cycle.
  A graph is bipartite if and only if it is 2-colorable, (i.e. its chromatic number is less than or equal to 2).

  ― wikipedia

So we see we are looking for a 2-colorable graph, or a bipartite graph. These are all the same thing.

Edit:

  A digraph has an odd-length directed cycle if and only if one (or more) of its strong components is nonbipartite (when treated as an undirected graph).

  ― algs4.cs.princeton.edu

Since your graph is strongly connected, we can treat it as an undirected graph and test for bipartiteness using the regular testing algorithms.

The wikipedia article gives an example algorithm to test bipartiteness using Breadth First Search. A presentation explaining the algorithm is available from The University of Maryland website.


Finding a path crossing minimum number of distinct colors Given a set $\cal D$ of unit disks in the plane and a set $C$ of colors. Every disk in $\cal D$ is colored with one of the colors in $C$. Note that multiple disks may be colored with the same color. Every color $c_i \in C$ is associated with a weight $w_i$.

for every path $p$ in the plane, we define the weight of $p$ as the sum of the weights of the colors that at least one of the circles with that color is crossed by $p$.

In addition, two points $s$ and $t$ is given in the plane and the goal is to find a path between $s$ and $t$ with the minimum total weight. What is the best approximation factor we can guarantee?

For a constant number of colors, the problem can be solved by considering all possible subsets of colors. The rest can be solved using a shortest path with memoization.

You can reduce set cover to this problem: Build a grid with $m+2$ rows and $n+2$ columns. Also assume all points in one column are connected, but connect the points in rows based on the following rule:

Each column represents a member of the universal set and each row a set. The boundary is a color with weight zero. Let $s$ be the leftmost uppermost point and $t$ be the rightmost and lowest point and remove the other two corners of the grid. Color the point $i,j$ with color $i$ if set $S_i$ contains $u_j$ and remove it otherwise. The minimum weight path in this graph is the same as the minimum set cover.

This subset of a grid, is a unit disk graph: allow the columns to be $cn$ apart from each other, where $c$ is the vertical distance between the first row and last row.
So $\theta(\log n)$ is tight.


Robustness of non-context-free proof against trivial manipulation First, we state here a theorem that is well-known in computability theory:

  $L=\{xx\mid x\in\Sigma^*\}\notin CFL$ for every fixed $|\Sigma|\geq2$

And, the standard proof is using pumping lemma. At first sight, we rarely face the language $L$ exactly as defined above in a broader theoretical research. Instead, what might be more frequent is $$L'=\{\text{some-simple-manipulation}(x)x\mid x\in\Sigma^*\}$$ Perhaps, those simple manipulation are necessary for unambiguous encoding. For example, symbol doubling, prefix, postfix, etc. Those are quite frequent and unavoidable.

Now, the question is: Can the above theorem still hold under these simple manipulations?

Symbol doubling (as commented below) is a good starter, if one feels the question too broad.

Or even worse, there may be some simple manipulation that push $L$ down to CFL again.

Note $\left\{x^{\mathrm{R}}x\mid x\in\Sigma^*\right\}$ is context free, where $x^{\mathrm{R}}$ means the reverse of $x$.

  Or even worse, there may be some simple manipulation that push $L$ down to CFL again.

So if you consider reversing as a simple manipulation, the answer is indeed yes.


What is an edge hop? I've tried googling it, but found nothing. Here is the context it's in:

From Bayesian Reasoning and Machine Learning:

Adjacency matrices may seem wasteful since many of the entries are zero. However, they have a useful property that more than redeems them. For an N x N adjacency matrix A, powers of the adjacency matrix $[A^k]_i$$_j$ specify how many paths there are from node i to node j in k edge hops. If we include 1's on the diagonal of A then $[A^{N-1}]_i$$_j$ is non-zero when there is a path connecting i to j in the graph. If A corresponds to a DAG the non-zero entries of the jth row of $[A^{N-1}]_i$$_j$ correspond to the descendants of node j.

An "edge hop" is the "act" of crossing an edge. It's a figurative term. The entry $[A^k]_{ij}$ counts how many paths there are from $i$ to $j$ of length $k$. A path of length $k$ entails traversing $k$ edges, hence the $k$ edge hops.


How the closure properties of the formal languages dictate decidability of their problem Consider the following problem:

Is $L_1 * L_2$ is of $LType$?
where we know that both  $L_1$ and $L_2$ are of type $LType$ and $LType$ is  closed under $*$ operation.

Above, by $LType$, I mean any type of language that is known to belong to any type of Chomsky hierarchy. So it may be regular (Chomsky Type 3), CFL or DCFL (Chomsky Type 2) etc.
Also by operation $*$, I mean any binary operation that results in another language, say intersection $\cap$, union $\cup$, difference $-$ etc.
Given all these pre-information of the type of languages and their closure under the specified operation, is the above problem decidable?
For example

Does the problem:

"Given that $R_1$ and $R_2$ are regular, is $R_1 \cap R_2$ too a regular language?"

is decidable, especially when we know that regular languages are closed under intersection?

Also can we comment in the same manner about undecidability of operation when  we know that the type of operand languages is not closed under that operation? That is

Does the problem

Is $L_1*L_2$ is of $LType$?

is undecidable?, especially when we know that $LType$ is not closed under the operation $*$ and that $L_1$ and $L_2$ are of type $LType$?

For example

Does the problem

Is $CFL_1\cap CFL_2$ is CFL?

is undecidable?, especially when we know that CFLs are not closed under intersection.

I feel both of above facts are correct/obvious/intuitive. But I am confused because no book on the theory of automata states it clearly.

If a family $\mathcal F$ of languages is closed under some operation, say intersection, then you are right that it is decidable whether the intersection of any two particular languages from $\mathcal F$ also belongs to $\mathcal F$. The answer is always Yes.

The converse, however, isn't true. Consider the family $\mathcal F_m$ of all regular languages which are accepted by some DFA having at most $m$ states, for some parameter $m$. When $m > 1$, this language family isn't closed under intersection, but given any two languages from $\mathcal F_m$ (in any reasonable encoding), it is decidable (depending on the encoding, efficiently) whether their intersection belongs to $\mathcal F_m$.


The Potential function for Fibonacci heaps I am trying to get a better understanding of Fibonacci Heaps. I noticed the
following definition for the potential function.
$$ \Phi(F)=|W| +2\cdot \text{# marks}. $$
I do not understand why it is defined that way, or what its significant is. I am hoping somebody can explain it to me.

Because it works.

In amortized analysis, you pick the potential function. While it's usually related to some insight about the data structure or algorithm work, is it per se completely arbitrary. The only important thing is that if you write down the telescoping sum -- which is always set up in the same way! -- you can derive a good estimate.


What is the name of this logistic variant of TSP? I have a logistic problem that can be seen as a variant of $\text{TSP}$. It is so natural, I'm sure it has been studied in Operations research or something similar. Here's one way of looking at the problem.

I have $P$ warehouses on the Cartesian plane. There's a path from a warehouse to every other warehouse and the distance metric used is the Euclidean distance. In addition, there are $n$ different items. Each item $1 \leq i \leq n$ can be present in any number of warehouses. We have a collector and we are given a starting point $s$ for it, say the origin $(0,0)$. The collector is given an order, so a list of items. Here, we can assume that the list only contains distinct items and only one of each. We must determine the shortest tour starting at $s$ visiting some number of warehouses so that the we pick up every item on the order.

Here's a visualization of a randomly generated instance with $P = 35$. Warehouses are represented with circles. Red ones contain item $1$, blue ones item $2$ and green ones item $3$. Given some starting point $s$ and the order ($1,2,3$), we must pick one red, one blue and one green warehouse so the order can be completed. By accident, there are no multi-colored warehouses in this example so they all contain exactly one item. This particular instance is a case of set-TSP.

I can show that the problem is indeed $\mathcal{NP}$-hard. Consider an instance where each item $i$ is located in a different warehouse $P_i$. The order is such that it contains every item. Now we must visit every warehouse $P_i$ and find the shortest tour doing so. This is equivalent of solving an instance of $\text{TSP}$.

Being so obviously useful at least in the context of logistic, routing and planning, I'm sure this has been studied before. I have two questions:

What is the name of the problem?
How well can one hope to approximate the problem (assuming $\mathcal{P} \neq \mathcal{NP}$)?

I'm quite happy with the name and/or reference(s) to the problem. Maybe the answer to the second point follows easily or I can find out that myself.

The problem is in $\mathrm{P}$ if the number of items is constant.

Let $K$ be the number of items (independent of $n$). For every ordering of items, use backtracking to try all allowed routes: you first go through some warehouse for the first item (trying all warehouses), then one for the second item and so on.

There are $O(K!)$ orderings of the items. Let $W_i$ be the number of warehouses for item $i$. The number of routes is $\prod_{i=1}^K W_i \leq \prod_{i=1}^K n = n^K$. Therefore, the running time of the above algorithm is $O(K! n^K)$, which is polynomial for fixed $K$.

If the number of items can be linear in $n$, the problem is at least as hard to approximate as $TSP$: you can take an instance of $TSP$, make an item for every vertex as you noted, and then add extra vertices very far away from all other vertices to inflate $n$ (and therefore allow for enough items that every vertex of the $TSP$ instance has a different item), without destroying the hardness of approxability of $TSP$. Note that if your points are in the Euclidian plane, then this doesn't really help you as there is a $PTAS$ for planar $TSP$.


How to make a "Secure by Design" client-server communication? Is there a way to have a secure by design client-server communication in a sense that the server can check if the client is not a modified version?

What I'd like to do is give the user access to both the client's and the server's source code, but keep him from communicating with a modified version.

As a practical example, let's suppose a multiplayer race game. Is there a way to give the user access to the source (and to compiling it and playing it on the server if he wants) but keeping him from, let's say, altering the speed of his car to 2x normal speed and using this new version to play?

As I understand, the compiled program could generate some hash and send it together for the server to verify. But then there also comes stuff like being able to get this code and making another version send it, etc.

If this is a known problem, please also provide further information about it.
(Any recommendations on books or papers related to that are also welcome)

The short answer is: No, you can't verify what code is running on the client.  As a result, you should never trust what is running on the client.

You could use all sorts of hashes, but nothing prevents a malicious client from lying to you about its hash and telling you what you want to hear.  Asking the client to hash itself and tell you its hash would be like having airport security ask passengers "Are you a terrorist?" and then believing them when they say "No".

In principle this problem could be solved with trusted hardware on the client, such as a a TPM.  Currently, a TPM is about the only way to check that the client is running unmodified code.  However, in practice using TPMs for this has major issues that typically render it not deployable in practice for the purpose you have in mind.

Therefore, in practice the answer is basically "no, there's no way to check".  See https://security.stackexchange.com/q/72091/971 for an explanation why there is no way to do this without trusted hardware (like a TPM).  As a result, the standard mantra is "you can't trust the client".  See e.g., https://security.stackexchange.com/q/40378/971 for some discussion of alternative architectures don't rely on trusting the client.

For a partial explanation why TPM-based solutions are not really deployable in practice, see https://security.stackexchange.com/q/2459/971.

If you want to explore the TPM approach, see https://security.stackexchange.com/q/5570/971 and https://security.stackexchange.com/q/4008/971.  However, I don't recommend it as a promising avenue.  In the future, Intel will be releasing SGX technology, which might be a better way to achieve this -- but it has not yet been released, so it will be quite some time before you can count on all your clients to run on hardware that supports SGX.


Are self-stabilizing algorithms guaranteed to work in parallel? Self-stabilizing algorithms are extremely useful in distributed systems,
  but can the algorithm be applied concurrently to each computational node?

My instinct is to say yes, but I can't help but imagine a 'Game Of Life' scenario
  where the state of the graph toggles between two states.
What keeps the question alive in my mind is the possibility that both such states would be considered 'correct', but then if the state were correct, wouldn't the graph stabilize?

If they are not guaranteed to work in parallel,
  can you provide an example where absolute convergence doesn't exist?

A self-stabilizing algorithm is an algorithm (in all my experience, applied to arbitrary graphs and graph structures exclusively) that, upon repeated applications, guarantees convergence onto a correct state—one that meets a set of requirements.  Consider a simple example:

  You maintain a network of hospitals and data centers.
  Each hospital must be connected to exactly one data center, and each data center must be connected to exactly two other data centers.  (You can imagine also attempting to minimize latency.)
  When you set up the network, it is in a correct state—all requirements are met.

  Weeks pass, and a giant storm takes out one of your data centers.
  Being the forth-dimensional thinker you are, you planned for situations like this by putting into place a self-stabilizing algorithm that will automatically reconfigure the network to get back to a correct state.
  You set up a daemon to oversee the operation.  It picks arbitrary nodes in your network and asks them if they are in a correct state.  If not, the daemon corrects that part of the network.

  All is well and you can stay asleep in bed (because everything catastrophic happens at 3am).

The trick is, the daemon isn't a necessary part of this system—it's just easier to think about it like this.
In reality, each node is its own computational unit—constantly evaluating its own state and taking steps to correct itself if necessary.

The introductory paragraphs of the Wikipedia article on the subject give a very good technical overview:

  Self-stabilization is a concept of fault-tolerance in distributed computing. A distributed system that is self-stabilizing will end up in a correct state no matter what state it is initialized with. That correct state is reached after a finite number of execution steps.

Just as a piece of requested information that doesn't fit in well above:

  When the graph is stable, no node has any faults with it.  Since no predicates apply to it, no actions are taken, and the graph remains stable.

I suggest you look for a textbook that provides an introduction to self-stabilizing algorithms (with some definitions, examples, etc.), and work through that textbook.  I think that will provide you a much better understanding, and you'll be able to answer this kind of question yourself.  Trying to learn a subject by reading Wikipedia and asking questions on StackExchange sites is not the way to go.

For instance, I think you'll find that, yes, of course each distributed node is working concurrently (in parallel); that's what it means for a system to be a distributed system.   And yes, for a self-stabilizing algorithm to be correct, one must show that it will never enter an infinite loop of the sort you describe; this is the convergence property.

Designing an algorithm with these properties is non-trivial, but in general, designing self-stabilizing systems is not easy.  No one ever promised this stuff would be easy.


Examples of interesting semantics to study during a small project for a graduate Semantics course I have been following the course Concrete Semantics with Isabelle/HOL. At some point we are given the task to verify a program/extend some semantic construction/prove some mathematical fact. I personally prefer to dive a little bit more into operational semantics, so adding new features to the IMP language is the way to go.

The classical extensions are non-determinism/parallel execution. These are described in a variety of books (Winskel, Hennessy or Nielson to cite only classical authors). However, I feel the treatment is rather limited and I'm not sure that can be turned into project, it looks more like a bunch of exercises.

So my question is  are you aware of any simple but interesting extensions of the operational semantics approach to the study of a simple WHILE-program (such as IMP)? I would be looking specially for significant properties that can be proved in that semantics and illustrative examples that may be relevant.

You could add more flow control to IMP, like (simple) exceptions, or break to exit early from a while loop.

You could some partial operators (division, square root) requiring you to handle runtime errors.

You could add more complex data types, like pairs. Make it so that e.g. projecting a value out of a non-pair value causes a runtime error. Craft a (first-order) simple type system e.g. using T ::= int | (T*T) as types, and prove that "typeable programs do not go wrong", i.e. executing them never lead to runtime errors.

You could add functions / procedures. This is not so trivial at first, especially if you want to consider several ways for parameter passing (e.g. pass-by-value, pass-by-reference).

You could prove that a suitable restriction of IMP (say, sans while, or with a constrained while) is always terminating.


Does Halts reduce to all other undecidable languages? In a CS theory class I'm taking, we showed Halts was undecidable via a diagonalization argument. All other undecidable problems we looked at we either got by reducing Halts to them, or some chain of reductions that started with Halts.
Are there any undecidable languages which Halts does not reduce to?

Recall that $A \leq_m B$ iff $\bar A \leq_m \bar B$. Indeed, the same reduction function works for both cases.

So, let $H$ be the halting problem. Both $H,\bar H$ are undecidable. We prove $H \not\leq_m \bar H$.

By contradiction, assume $H \leq_m \bar H$. Hence, by the property above, $\bar H \leq_m H$. Hence $\bar H$ reduces to some RE problem, making $\bar H$ RE as well. Since $H,\bar H$ are both RE, we conclude that both are decidable. Contradiction.


How to label a video for supervised learning? I have just started discovering the machine learning world! I found many tutorials showing how to deal with different types of data. I walked through some tensorFlow tutorials and I think they have very good way for showing how the (x, y) pair for supervised learning is "formed".

I was not able to find a way for representing the (x, y) pair for a video though. Are there any resources that can help me get started with labeling video sequences?

Try Computer Vision Algorithms and Applications by Richard Szeliski and label propagation in video sequences.
To get a good grasp on the topic also Supervised Sequence Labeling with Recurrent Neural Networks. I proposed these resources as they cover the labeling, machine learning and are very in-depth materials (book, dissertation and the paper about propagating labels).

Video is the natural extension of the image, but to get fully working methods we also have to account for scene movement and changes. And I belive that in the video point is referenced by $x, y, t$.


Slow MIS Distributed Algorithm I am interested in precise time complexity of distributed algorithm for finding MIS (Maximum Independent Set) of a given graph $G$.

I investigate the Slow MIS distributed algorithm (from these lecture notes, page 2).

Following is the more detailed version than in lecture notes.

Every node sends its UID to it's neighbors.
Run procedure join

on event: getting a message decide(1)  from a neighbor $w$ do

Set $b = 0$ - flag that node terminates and not participating in further phases.
Send decide(0) to all neighbors

on event: getting a message decide(0) from a neighbor $w$ do:

Invoke procedure join.

Procedure Join

if every neighbor $w$ of $v$ with a larger identifier has decided $b(w) = 0$, then do

Set $b = 1$.
Send decided(1) to all neighbors.

The question is what's time complexity of the algorithm $\Theta(n)$ or $\Theta(D)$, where $D$ is a diameter of $G$.

In the lecture notes linked above, they say that time complexity is $O(n)$. I  think that in our case it can be expressed as $\Theta(D)$ (simultaneously $O(D)$ and $\Omega(D)$) for special cases.

The problem is how to prove that that time complexity in general is $O(D)$ and there are special cases when time complexity is $\Omega(D)$ if it's right at all.

Let's take a look at the example I have in mind.

$D=1$ and $n=4$, and as I understood the algorithm every vertex will decide to join MIS on the first round.

If you have an idea how to show that, please, share it with us.

It is not actually the diameter. It is the longest chain in the partial order $P$ of the input graph $G = (V,E)$. The poset $P$ is constructed as follows. Given an input graph $G = (V,E)$ such that each vertex has a unique identifier. Build an oriented graph $G' = (V,E')$ such that an edge $(u,v) \in E'$ if $(u,v) \in E$ and $u \succ v$. Then build a partial order $P$ of $G'$ by taking the transitive closure of $G'$. Let $l$ be the length the longest chain of $P$, then the time complexity of your algorithm is exactly $l$  (assuming here that the time complexity is measured by the number of communication rounds and in each round a node can send/receive a message to/from all its neighbors). Note that $l$ is $\in O(n)$ and in $\Omega(1)$.

What about average complexity ?
Let's $G(n,p)$ be a random graph of $n$ vertices and an edge between any pair of nodes exist with probability $p \in [0,1]$. Then, if you build a partial order $P$ of this graph (called random graph order), you will find that the longest chain $l$ is in $\Theta(n)$. This result is proven in [1].

[1]: Albert, Michael H., and Alan M. Frieze. "Random graph orders." Order 6.1 (1989): 19-30.

(This is for additional knowledge)
It is possible that assigning identifiers on the input graph such that the complexity of this MIS algorithm is minimized (that is, minimize $l$).  The problem is NP-Hard as it is reducible to minimum coloring. This NP-Hard problem was given in: [2] and [3].

[2]: Deming, R. W. "Acyclic orientations of a graph and chromatic and independence numbers." Journal of Combinatorial Theory, Series B 26.1 (1979): 101-110.

[3]: Chvátal, Vašek, and Carsten Thomassen. "Distances in orientations of
graphs." Journal of Combinatorial Theory, Series B 24.1 (1978): 61-75.

(Ok this is just for fun, and you can skip it)
Now assume that you want to measure time with a different metric. And let's add a restriction to the definition of communication rounds (found in [4]). And let's say that a node 1) can send a message to only neighbor in a communication round, and 2) can receive a messages (more than one) from all its neighbors In such case, the order that a node follow to send a message to its neighbors will affect the time complexity. Let's consider three strategies that a node $v$ follows to visit its neighbors (with smaller identifiers) which are $\{u _1, ..., u _k\}$ such that $u _i \succ u _j$ if $i > j$. Then:

Strategy 1: $v$ sends messages in an order from $u _k$, to $u _{k-1}$ ..., $u _1$ etc .. . This strategy leads to $\Theta(n)$ time complexity.
Strategy 2: $v$ sends messages in an order from $u _1$, to $u _{2}$ ..., $u _k$ etc .. . This strategy leads to $\Theta(n^2)$ time complexity.
Strategy 3: $v$ sends messages to its neighbors in a uniformly random order. This strategy will also lead to $\Theta(n^2)$ in expectation.

(Why I am interested in all that ?) - because it was found in some practical wireless networks (Bluetooth networks), that this slow MIS algorithm is the fastest although not being the theoretically fastest one. It was found that this type of networks follow the modified communication model I defined above.

[4]: Peleg, David. Distributed computing: a locality-sensitive approach. Vol. 5. Society for Industrial Mathematics, 1987.


How to reduce to an NP-hard problem? For an assignment I have to program an application to schedule conversations.
There is an event where representatives of the elementary schools talks with the representatives of high schools. They will talk about the students that will be transferred to the highschool. There are approximately 200 elementary schools and 40 high schools that will be participating in this event. The schools already know which student is transferring to which high school. The conversations will only be between representatives of E and H from student that will be transferring to H.

The rules are:

The duration of each conversation is based on the amount of
students per representatives.Each conversation last 5 minutes per student. If a group consist of 1 student, this conversation last 10 minutes.
No timeclashes
All the students of the same group will be scheduled together, so, a
representatives will only face the same representative once.
Timespan is 13.00-19.00
The waiting time of a representative is at most 20% of his time. A
waiting time is an empty timeslot between the 1st and last
conversation.
Schedules for 2 days
Each representatives participate for 1 day.

The problem is that I know that this is hard to solve, but I dont know if it's NP-hard. Right now I only know this problem is similar to a Job Shop Problem. What can I do to proof that my problem is NP-hard? I read that I need to reduce a known problem to my problem. But how do I do this? I have read different articles and books, but I still don't understand the steps to do it.

Just an extended comment.

I think that before trying to find a reduction, you should try to better formalize the problem:

define exactly what the parameters of the problem are, formalize their constraints, and formalize the question;
try to simplify (or remove) the details;

For example:

If a group consist of 1 student, this conversation last 10 minutes. $\rightarrow$ it is equivalent to a group of two students, so you can remove it;
Timespan is 13.00-19.00 $\rightarrow$ in the other rules you use minutes, so convert the "timespan" to $T$ minutes;
try to think if a simplified version of the problem has a quick solution or it can be still hard (e.g. if the event last only one day rules 7 and 8 can be dropped)
express the rules with a math formula: e.g "if an elementary group $E$ of $n$ students talk with a high school group $H$ of $m$ students then the total time $TT$ required is $TT(E,H)=....$"; "the total max wait time $WT$ for group $E$ is $WT = ...$"

Furthermore there is a point that it is not clear (to me):

suppose you have an elementary school group $E$ having $n$ students that talk with a high school group $H$ having $m$ students; what is the total time required? (1) $5 * n$ (the talk is public) or (2) $5 * ( n / m)$ (each student of E talks with a single student of H). If the talk is public, then the number of students is redundant, and you can think only in terms of total time required by a school group.


Is there a proof of the recursive algorithm for generating all permutations of a sequence? For clarity, I attach below a concise implementation of the algorithm in Python. I understand that it checks all possible element swaps, but I don't see how that necessarily means that all possible orderings of the elements will be reached, and/or that no ordering will be duplicated.

For example, what if the elements at index 0 and 1 are swapped, then 1 and 2 are swapped?  How does the algorithm guarantee this won't result in a duplicate ordering?

P = []
def permute(l, n=0):
    if n == len(l):
        return P.append(list(l))
    for i in xrange(n, len(l)):
        l[i], l[n] = l[n], l[i]
        permute(l, n+1)
        l[i], l[n] = l[n], l[i]

Hint: Prove by induction that $\mathrm{permute}(l,n)$:

Adds to $P$ all permutations obtained from $l$ by permuting coordinates $n,\ldots,|l|$.
Leaves $l$ unchanged. That is, the value of $l$ after running the function is the same as its value before running it.


Theta Manipulation to show $N = \Theta(n/\log N)=\Theta(n/\log n)$ I am studying different models of computation and how algorithms can be interpreted under different models.

Here is a math(?) question that has been bugging me.

Suppose we have $n = \Theta(N\log N)$ bits as the size of input and there are N elements in the input. (The implied assumption is each element has $\Theta(\log N)$ bits).

Now we know Insertion Sort has running time of $\Theta(N^2)$ in the worst case with respect to N, the number of elements in the input.

Under the RAM model, the input is $n = \Theta(N\log N)$ bits. So we can say $N = \Theta\left(\frac{n}{\log N}\right)$. I want to show that the running time $T = \Theta\left(\frac{n^2}{\log^2n}\right)$ by first showing that $N = \Theta\left(\frac{n}{\log n}\right)$.

Since $N \leq n$, $N = \Theta\left(\frac{n}{\log N}\right)=\Omega\left(\frac{n}{\log n}\right)$. I am having trouble showing $ N = \Theta\left(\frac{n}{\log N}\right)= O\left(\frac{n}{\log n}\right)$ to be able to use the $\Theta$ notation.

In general, I am not so sure what kind of manipulations are allowed inside $\Theta$ so that its definition is intact.

There is not any strange thing here. As:

$$\frac{n}{\log(n)} = \frac{n}{\log(N\log(N))} = \frac{n}{\log(N)+\log(\log(N))} = \Theta\left(\frac{n}{\log(N)}\right) = O\left(\frac{n}{\log(N)}\right)$$

Therefore, all of them are true.


Pick matrices such that each partial sum is positive There is a sequence of $n$ sets, each set contains a constant number of constant-size vectors, e.g:

$\{M_{1,1},M_{1,2},M_{1,3},M_{1,4}\}$
$\{M_{2,1},M_{2,2},M_{2,3},M_{2,4}\}$
...
$\{M_{n,1},M_{n,2},M_{n,3},M_{n,4}\}$

The task is to pick, from each set, a single vector, such that the sum of vectors and all the partial sums have no negative elements, i.e, select $i1,i2,...,in$ such that the following vectors:

$M_{1,i1}$,
$M_{1,i1} + M_{2,i2}$,
$M_{1,i1} + M_{2,i2} + M_{3,i3}$,
...

have only non-negative elements.

Is anything known about this problem?

I'll represent you problem as:

  Let $S_1, \dots, S_n$ be sets of $p$ vectors of size $d$. Find a vector $v_i$ in each $S_i$ so that for every $k\le n$, $\displaystyle \sum\limits_{0\le i \le k}v_i$ has only non-negative coordinates.

Prop: This problem is in NP.

Proof: Once we have the set of indices / vectors, it's easy to check that they work in polynomial time.

Prop: For $d\ge 2$ constant and $p\ge 2$ constant, the problem (where $n$ is not bounded) is NP-hard.

Proof: We take an instance of the subset-sum problem, which is NP-hard. We have integers $i_1, \dots, i_n$. We define $M=|i_1|+\dots + |i_n|$.

We take $S_0=\{[M,M]\}$. For $1\le k\le n$, $S_k=\{[i_k, -i_k],[0, 0]\}$ and $S_{n+1}=\{[-|M|, -|M|]\}$.

All the partial sums will clearly be $\ge 0$ except maybe the last one. The last one will be $\ge 0$ iff $\sum i_k\ge 0$ and $\sum -i_k\ge 0$, i.e. iff $\sum i_k = 0$. So there is a solution iff the subset sum instance has one.

The following is a weaker result but it's written so I leave it here.

Prop: This problem with $2n$ sets of $p$ vectors of size $2d$ is at least as hard as $CNF-SAT$ on $n$ clauses with $p$ literals per clause and $d$ variables.

Proof: Take a set $C_1,\dots, C_n$ of clauses on $d$ variables, with $p$ literals per clause. $C_i=l_{i,1}\lor \dots \lor l_{i,p}$.

We write $v_k$ for the $k$th variable. To a positive literal $l_{i,j}=v_k$, we associate the vector $\phi(v_k)$ of dimension $2d$ that has a $1$ at the $k$th position and $0$s everywhere else. To a negative literal $l_{i,j}=\lnot v_j$ we associate the vector $\phi(v_k)$ of dimension $2d$ with a $1$ in $d+k$th position and zeros everywhere else.

Now, for $1\le k \le n$, we set $S_i=\{n\phi(v_k),n\phi(\lnot v_k)\}$ (and we add some useless vectors with big negative values if you really want the set to have size $p$). For $1\le i\le n$, we set $S_{n+k}=\{-\phi(l_{i,j}) / j\in\{1,\dots,n\}\}$.

The idea is the following. In the first $n$ coordinates, we store how many times we can use each of the variable, and in the next $n$ coordinates, we store how many times we can use each of the negation of variables. Then, at the beginning, in the first $n$ sets, we pick for each variable if it's true or false (by adding $n$ to the number of times we can use the variable, or to the number of times we can use its negation). The last $n$ sets then use the variables / negations to make the clause true. To make a clause true, you need to make one literal true, and the true ltterals will be exactly those for which the corresponding coordinate is $>0$ so that you can subtract $1$ while remaining $\ge 0$. If you chose $v_k$ to be false, the corresponding coordinate will remain $0$ for the whole thing so if you try to use it, it will become $<0$. And we add $n$ at the beginning because since there are $n$ clauses, we won't subtract more than $n$.

Prop: For $p\ge 3$, the problem (where $d$ and $n$ are not bounded) is $NP$-hard.

Proof: The reduction given above reduces $3-SAT$ to it in polynomial time. And $3-SAT$ is NP-hard.


What is the type theory judgement symbol? In type theory judgements are often presented with the following syntax:

My question is what is that symbol in the middle called? All the papers I've found seem to use an image rather than a unicode character so I can't look it up. I've also not found any type-theory reference which says what that symbol is (they explain what it means however).

So what character is that symbol and what is its proper name?

It's called a "turnstile". See the Wikipedia article.


Is there a difference between using $n$ and $\Theta(n)$ in recurrences? Is there a difference between $T(n)=2T(n/2)+n$ and $T(n)=2T(n/2)+Θ(n)$ when using the master theorem? I've seen it both ways and am a little confused. (Looking for the answer $nlogn$).

A recurrence of the form
$$
T(n) = 2T(n/2) + \Theta(n)
$$
is really a shorthand for a recurrence of the form
$$
T(n) = 2T(n/2) + f(n), \text{ where } f(n) = \Theta(n).
$$

Let us consider a recurrence of this form, and let us suppose that $an \leq f(n) \leq bn$, where $a,b > 0$. Consider the more general recurrence
$$
T_c(n) = 2T_c(n/2) + cn,
$$
with the same initial values as the $T(n)$ recurrence. You can prove by induction on $n$ that
$$
T_a(n) \leq T(n) \leq T_b(n).
$$
Therefore, if you can show that $T_c(n) = \Theta(n\log n)$ for all $c$ (where the hidden constant could depend on $c$), then it would follow that also $T(n) = \Theta(n\log n)$.


Give a specific case where calling a polynomial time function n times gives an exponential time algorithm We were asked this question in exam and I am not satisfied with the answer the teacher gave.

Let me justify my point of view. Let there be a polynomial time function having time complexity $n^{c_1}$. If we call the function polynomial times, say $n^{c_2}$ times, then the time complexity of the algorithm becomes $n^{c_1+c_2}$. Which is clearly polynomial.

Now the answer our teacher gave. Let there be a subroutine $S_i$ with time complexity $2^{i-1}n$ where $n$ is the input size. Therefore the time complexity of $S_n$ is $2^{n-1}n$. Which is exponential.

I am not satisfied with this answer because firstly the variable $i$ seems shady. We are not even calling any subroutines polynomial times, we are just assigning some value arbitrarily.

If our teacher's answer is correct could someone elaborate? If not, is there any answer to this question?

A concrete example is repeated squaring. Squaring an integer of length $n$ takes time $O(n^2)$ (using the naive algorithm; you can do much better with more complicated algorithms). If you square an $n$-bit integer $i$ times in a row, its length becomes $2^i n$. So if you square it $n$ times in a row, the complexity is $O(4^n n^2)$, which is exponential.

The source for confusion is the input length. If the polynomial time function increases the length, then the behavior can be exponential. If it doesn't, the behavior stays polynomial.


Find the average number of steps to sort an array by randomly selecting two elements I have sequence of an unique numbers from 1 to 10 in randomly order (for example: list = [7, 5, 3, 4, 2, 6, 10, 1, 9, 8]). I can choose two random number and if the list from left number larger then right number I swap them (for example 2 and 5  list[2] larger then list[5] so I'll swap them and etc).
Need to find average number of all choosings to order the sequence.
The algorithm should executed less then 1 second.
Can anybody help me?

The average number is hard, an upper bound isn’t.
You have n numbers, therefore n(n-1) / 2 pairs of numbers. On average half of those pairs are in the wrong order. You need to figure out the distribution for that.
Now if you have k pairs in the wrong order, the probability of picking two random numbers in the wrong order is 2k / n / (n-1). If you pick two numbers in the wrong order and exchange them, the number of incorrectly ordered pairs goes down at least by one. So you expect n(n-1)/2k picks to go from k inversions to k-1 or fewer. (The “fewer” makes it hard to analyse).


Can POSIX BRE express all regular languages? It appears that "Basic Regular Expressions" as defined by POSIX.1-2008 do not support alternation, a|b (although some grep implementations recognize the escaped version, \|).

Since the regular languages are closed under union by definition, does this mean that POSIX BRE has less expressive power than a finite automaton? Or is there some way to simulate alternation using other constructs?

Indeed the POSIX BRE language cannot express all regular expressions because it lacks alternation. It can't even recognize all finite languages, let alone all regular languages.

For example, $\{ab, ba\}$ is not recognizable as a BRE. To prove this, consider what the toplevel syntactic form could be:

It can't be one of the single-character forms since the language has words of length $\gt 1$.
It can't be $R^*$ because that would match the empty string.
It can't be $R^{\{m,n\}}$ except with $m=n=1$ (in which case we're back to the original problem) because that would match strings of different lengths or the empty string.
So it has to be concatenation: $R_1 R_2$. Now consider how $ab$ is recognized:

If $R_1$ recognizes $ab$ then $R_2$ must not recognize anything anything other than the empty string. So $R_1$ must recognize $\{ab,ba\}$ and we're back to the original problem.
If $R_1$ recognizes $a$ but not $ab$ then $R_2$ must recognize $b$. But then $R_1R_2$ recognizes all words of the form $u b$ where $R_1$ recognizes $u$, so $R_1$ must not recognize anything other than $a$. There's no way to recognize $ba$.
If $R_1$ recognizes neither $ab$ nor $a$ then the only way for $R$ to recognize $ab$ is if $R_1$ recognizes the empty string, in which case we're back to the original problem as above, but for $R_2$ this time.

When “we're back to the original problem”, that means that the only solution to find a BRE recognizes the language is to find a smaller BRE that has the same property. This is an infinite descent, so there's no BRE that has the desired property.

I don't think there's a “nice” characterization of BRE-recognizable languages, for example as languages recognizable by a “nice” class of automata.

Note that BRE-recognizable languages are actually not a subclass of regular languages, since backreferences add expressive power. For example $\{w w \mid w \in \{a,b\}^*\}$ is recognized by the BRE \(.*\)\1 but is famously not regular. BRE without backreferences are just syntactic sugar over regular expressions so the languages they can recognize are a subclass of the regular languages.


Given a moving ball in a grid, which squares does the ball reach? You are given an m x n grid. A dimensionless ball is placed at the centre of one of the grid squares and starts moving in one of 4 directions: north-east, north-west, south-east, or south-west. The ball continues moving until it reaches the edge of the board at which point, it bounces back in accordance with the laws of Physics.

Given m, n, the initial position and direction (NE / NW / SE / SW) of the ball, is it possible to determine whether the ball will ever reach a specified target grid square (x0, y0)?

It is possible to answer the question by exhaustively tracing the movement of
the ball, but is there any easier more efficient alternative? Any pointers to related literature would also be much appreciated.

Exhaustively tracing the movement of the ball is the easiest to program, and also not too bad on efficiency grounds.  You should keep a hash table of all states of the ball that have been seen before (where the state of a ball is the grid square it is in, and which direction it is heading); if you see it repeat a past state, then you know it will loop forever and you can stop tracing the movement any further.  With this way, tracing the ball's movement will take at most $O(mn)$ time in the worst case.

This can be sped up by using a little bit of simple algebra to calculate "given the current state, what's the next wall the ball will hit?" in $O(1)$ time -- that will be faster, but not easier.

There is a more elegant and efficient solution, based upon number theory and on Tom Van der Zanden's technique of extending the grid infinitely.

Imagine a parallel universe where ball travels in a straight line in an infinite grid; as Tom says, bouncing off the walls in our universe is equivalent to continuing in a straight line in the parallel universe.  This is the first insight we will use.

Let's work out the implications of this insight.  In our universe the ball starts at some initial coordinate $(x_0,y_0)$, moving NE, and we want to know if will ever reach coordinate $(x',y')$.  What does this mean in the infinite universe?  Well, imagine placing mines at coordinates $(x',y')$, $(x',2n-y')$, $(x',y'+2n)$, $(x',4n-y')$, ..., $(2m-x',y')$, $(2m-x',2n-y')$, ... -- in particular, at coordinates $(2im \pm x',2jn \pm y')$ where $i,j$ range over all integers.  Then I claim that the ball will eventually reach coordinate $(x',y')$ in our universe if and only if the ball will eventually hit a mine in the parallel universe.  So our problem reduces to asking: in the parallel universe, will the ball ever hit a mine?

The second insight is that we can use number theory to answer that question.  In particular, after $t$ units of time, the ball will be at position $(x_0+t,y_0+t)$ in the parallel universe.  We want to know whether there exists any integers $t,i,j$ such that $x_0+t = 2im \pm x'$ and $y_0+t = 2jn \pm y'$.  Re-arranging these equations and using the language of modular arithmetic, we are asking whether there exists an integer $t$ such that both of the following equations hold:

$$\begin{align*}t &\equiv \pm x' - x_0 \pmod{2m},\\
t &\equiv \pm y' - y_0 \pmod{2n}.\end{align*}$$

Now we're all set to apply number theory.  In particular, this is set up perfectly to apply the Chinese remainder theorem.  Define $g = 2 \gcd(m,n)$.  Then the above system of equations has a solution in the integers if and only if

$$\pm x' - x_0 \equiv \pm y' - y_0 \pmod{g}.$$

In other words, we should check the following four conditions:

$x'-x_0 \equiv y' - y_0 \pmod{g}$
$-x'-x_0 \equiv y' - y_0 \pmod{g}$
$x'-x_0 \equiv -y' - y_0 \pmod{g}$
$-x'-x_0 \equiv -y' - y_0 \pmod{g}$

If any of those four conditions holds, then there is a solution to the above system of equations and thus in the parallel universe the ball will hit some mine; if none of those four conditions holds, then the ball will never hit any mine.  (These 4 conditions are the relevant conditions if the ball is initially travelling NE.  The other directions can be handled symmetrically with a similar set of 4 conditions.)

Rephrasing in terms of the original problem, we get a solution to the original problem that is easy to implement and runs in $O(1)$ time.  We compute $g=2 \gcd(m,n)$ and check the four conditions in the bullet list above.  If any of the four conditions holds, then the answer is yes: the ball will eventually reach the point $(x',y')$.  If none of the four conditions holds, then the answer is no: the ball will never reach the point $(x',y')$.


Reduction to a vertex cover problem-like with weighted vertices and edges Description

Let us define a new problem with an instance $I = (G = (V, E), K, L)$, whereas:

$G$ is an undirected graph
$K \le |V|$
$L > 0$ is the maximum limit
Each vertex $v \in V$ has a weight $W(v)$
Each edge $e \in E$ has a length $W(e)$

Let $P(v)$ be a function that returns the minimum length of a path (basically shortest path) from vertex $v$ to a vertex in $V'$.

The decision question is whether there exists a vertex set $V' \subseteq V, |V'| \le K$, such that:

$$
\sum_{v \in V} W(v) \cdot P(v) \le L
$$

Example

Consider the following graph $G$, with $K = 1$ and $L = 9$:

Taking the set $\{v_3\}$ as $V'$ would be the solution to the question, because the total cost is:

$$
3 \cdot 0 + 2 \cdot 2 + 1 \cdot 5 = 9
$$

Therefore, this is a yes-instance.

Question

How do I prove that this problem is in $\mathsf{NPC}$? I tried reducing a $\text{VC}$-instance to this, but that does not seem to work.

What I have tried as well is by converting the above undirected graph to a directed graph with the weighted paths already computed (this is polynomial computable):

$$
\begin{array}{l|l|l}
        & v_1 & v_2 & v_3 \\
\hline
    v_1 & 0   & 3   & 5   \\
\hline
    v_2 & 6   & 0   & 4   \\
\hline
    v_3 & 15  & 6   & 0
\end{array}
$$

However, I'm not entirely sure what $\mathsf{NPC}$ problem to reduce from. I got the tip to use the $\text{CLIQUE}$ problem from this answer, but I do not see how to perform the reduction, so that seems unlikely. To me, this looks more like something that can be reduced from the $\text{KNAPSACK}$-problem or the $\text{SET COVER}$-problem, using the weights from the transformed directed graph, but I fail to see how exactly to this. I am starting to think that the transformed directed graph is of no use here.

What $\mathsf{NPC}$-problem can I use for the reduction?

This problem is a generalization of Dominating Set, and if you let weights of vertices and edges be 1, then you have exactly Dominating Set.

The problem definition of Dominating Set is:

  Given a graph $G = (V, E)$ and an integer $k$, is there a set $V' \subseteq V$ of size at most $k$ such that the distance of any vertex $v \in V \setminus V'$  to $V'$ is 1.

(This is assuming that the distance from $v' \in V'$ to $V'$ is defined as 0.)

It follows that WVE is NP-hard.  This is occasionally called proof by generalization.


A certain submatrix of the correlation polytope I am kind of confused by the argument at the top of page 5 here, http://homes.cs.washington.edu/~jrl/notes/bonn-lecture-notes.pdf

Firstly given that the author wanted to look at quadratic multilinear functions on $\{0,1\}^n$ why is he finding it enough to look at functions of the form, $f(x) = a_0 + \sum_{i,j} A_{ij}(xx^T)_{ij}$ for some real symmetric matrix $A$ and a real number $a_0$?

These $f$s won't have any linear term and doesn't that mean a loss of generality?
The author defines the set $QML_n^+$ as the set of functions of the above type which are non-negative on the Boolean hypercube. Isn't this set an uncountably infinite set?

Because I don't understand how the author now hopes to define a matrix $M_n$ whose rows seem indexes by $f \in QML_n^+$ and the columns seem indexed by $x \in \{0,1\}^n$ and the entries are $M_n(f,x) = f(x)$.

How does this make sense as a matrix (of finite dimensions!)?
Given everything  above how is it obvious that this matrix $M_n$ is a submatrix of some slack matrix of the correlation polytope $conv(\{ xx^T \vert x \in\{0,1\}^n \})$ ?

Every quadratic multilinear polynomial can be written as
$$
a_0 + \sum_i a_{ii} x_i + \sum_{i \neq j} a_{ij} x_i x_j =
a_0 + \sum_i a_{ii} x_i^2 + \sum_{i \neq j} a_{ij} x_i x_j,
$$
using the fact that $x_i^2 = x_i$ for every $x_i \in \{0,1\}$. This clearly equals $a_0 + \sum_{ij} A_{ij} x_i x_j$, which in turn is the same as what you wrote.

Regarding the matrix $M_n$, it is indeed infinite. For the proof that it is a submatrix of some slack matrix of the correlation polytope, see Lemma 2.8 of these lecture notes by James Lee.

If you have any more questions on the Bonn lecture notes, I suggest looking in the cited lecture notes, which seem to be more thorough.


Does a computer do only two things? According to the book, Introduction to Computation And Programming Using Python by John V Guttag, a computer does only two things:

Store data
Manipulate data

But is this all? I mean, without I/O, can a computer be considered useful?

The statement is obviously false: my computer can make sounds and it's hard to see that that as either storing or manipulating data.  I suggest you just ignore it and move on, since producing this kind of list does nothing to help your understanding of computers, programming or anything else.


Are DFAs with a unary alphabet strictly less powerful than DFAs with a binary alphabet? Are DFAs with a unary alphabet strictly less powerful than DFAs with a binary alphabet? Is this even a meaningful question?

For example, if $\Sigma = \{\texttt{0}, \texttt{1}\}$, we can encode any larger alphabet using $\Sigma$, but if $\Sigma = \{\texttt{0}\}$, this can define a DFA (that say, recognizes $L = \{ \texttt{0}^k \mid k > 0\}$)... but such a DFA would never be able to recognize more "complex" regular expressions. For example, there is no way to encode $\texttt{0011}$ using a unary alphabet that a DFA would recognize (we could use, say, Godel numbering, but that would require a more powerful machine that could "count").

If DFAs with a unary alphabet less powerful than DFAs with a binary alphabet, is there a name for this language/grammar? I recognize this is kind of an odd question, since the DFA that recognizes $L = \{ \texttt{0}^k \mid k > 0\}$ recognizes all unary languages... but technically there still are a countably infinite number of DFAs in this class ($L = \{ \texttt{0}^1 \}$, $L=\{\texttt{0}^2\}$, etc.)

Note I am of course assuming that for $\Sigma = \{ \texttt{0} \}$, that it does not contain the empty symbol $\varepsilon$.

Take the set $A=\{2^k \mid k \ge 1\}$. The language
$$ L=\{ \text{bin}(a) \mid a \in A\} = \{10^k\mid k \ge 0 \}$$
is clearly a regular language, whereas
$$L=\{ 1^a \mid a \in A\} $$
is not regular. Proving the latter is a standard textbook application of the regular pumping lemma.


What complexity class is the TSP problem? Is the travelling salesman problem (TSP) $FNP$-complete or is it $FP^{NP}$-complete?

It has been proven that TSP is $FP^{NP}$-complete but it remains an open question whether TSP is a function problem in $FNP$ (it probably is not). The reason is that, in the case of TSP, the optimal solution is not an adequate certificate, as we do not know how to verify in polynomial time that it is optimal.

You can see a proof that TSP is $FP^{NP}$-complete here, starting on page 418.

Note: I don't know if it's allowed to put the link to that PDF although it's from a university. You can buy the full book searching for Computational Complexity by Christos H. Papadimitriou.


Finding loop invariant of Lowest common multiple function So I have the following function:

def lcm(a,b):
    x = a
    y = b
    while x != y:
        if x < y:
            x += a
        else:
           y += b
    return x

I'm not sure how I will go about finding the loop invariant of this question. I know I have to find some sort of relationship between $x$ and $y$ but nothing seems to hold or is helpful in actually proving correctness.

Well, a possible loop invariant is "$x$ is a multiple of $a$ and $y$ is a multiple of $b$".

Then this almost proves partial correctness, because we know that after the loop terminates $\neg(x \neq y) \to x = y$, thus $x$ must be a multiple of both $a$ and $b$.

What this loop invariant doesn't show is that $x$ is the smallest possible such number.

To solve this, we must complicate our loop invariant:

If $x \geq y$, $x$ is the smallest multiple of $a$ that is bigger than or equal to $y$.
If $y \geq x$, $y$ is the smallest multiple of $b$ that is bigger than or equal to $x$.

Now it's up to you to prove that this invariant is correct.


augmenting bst - is there exist pair (a,b) of numbers such that |b-a| = d? How to check if exist pair $(a,b)$ of numbers in BST such that $|a-b| = d$, where $d$ is given.
Example:
contain of tree: $1, 4, 5, 3, 8, 45, 532$
$d=5$,
answer: $yes$, there is pair $(5,8)$
$d=52$
answer: $no$.

I can solve it when number are in array - then I sort them, and in linear time I can find that pair. Neverthelress I can't idea how to augment BST in this task.
Can you give me a hint ?

By "in linear time I can find that pair" I assume you are using two-pointer technique, that using 2 pointers to traversal the array, trying to reduce the gap to the target by advancing one of the pointer.

An in-order traversal of BST outputs all values in order in linear time. So you can apply your linear-time algorithm similarly on BST, only the pointers advancing to the in-order next node.


Solving/mitigating the free rider problem without requiring identification? Is there any algorithm/protocol out there to solve/mitigate the free rider problem without requiring identification?

In a web system, I want to distribute exactly one virtual dollar per day to each person, without requiring identification when a person creates an account.

A solution of mitigation, would mean for example that a specific person may get up to $2 per day (in case he created more than one account), but not much more.

The algorithm needs to distribute to every person about the same amount of money per day. So the ratio between the money distributed to every two different people per day should be around 1.

The term for the problem you seem most focused on is a Sybil attack whose typical solution is some form of identity.

Another mitigation is a proof of work system that makes account creation expensive. The goal is to have the cost of creating multiple accounts not be worth the gains. This is more effective when one needs many Sybil accounts to really benefit. Anything that made getting two accounts disincentivizingly costly, probably makes getting one account too annoying for legitimate users.

The Wikipedia page list another approach to dealing with this that is a bit interesting, and is described, for example, in "Sybil Detection via Distributed Sparse Cut Monitoring" by Aditya Kurve and George Kesidis referenced there. This, however, requires some way for the users to interact in your system (or in a system you have visibility into). In particular, it requires users to implicitly or explicitly "vouch" for other users. This graph of "vouchings for" will usually have atypical properties for subgraphs of Sybil accounts (e.g. being fully connected rather than a small-world graph).

In your context, you could attempt to use techniques similar to the fraud detection banks do and try to find patterns that suggest abuse, e.g. a bunch of users all transferring virtual currency to a single user in a short time frame.

Alternatively, and this is somewhat in line with a proof of work scheme, you can only provide this virtual payment when the user is doing the intended behavior. As a simple baseline, you may provide it only to users who are active a certain amount in the day. This also leads into to the fraud detection angle as many online games have similar systems to detect bots that are just pretending to behave like normal users.


Out-Degree of a Configuration Graph In Chapter 4 in Computational Complexity by Arora and Barak it states, regarding the configuration graph of a Turing Machine, that

If M is deterministic, then the
graph has out-degree one, and if M is nondeterministic, then the graph has out-degree
at most two.

In the configuration graph, a directed edge is placed from the configurations $C$ to $C'$ if we can obtain $C'$ from $C$ via a single transition. Also, the authors assume we are working with two tape Turing machine with one read-only input tape and one read-write work tape. Here, the authors define a configuration by

A configuration of a TM M
consists of the contents of all nonblank entries of M’s tapes, along with its state and head
position, at a particular point in its execution.

I understand that the out-degree for a deterministic machine must be 1, but I do not see why the out-degree for the non-deterministic machine can be at most 2. Given that the authors assume that $\Gamma= \{0,1\}$, I would assume that the number of possible configurations reachable from any given configuration would be $|\Gamma||Q||\{L,R\}^2|$ for a two tape Turing machine, where $Q$ is the set of states and one head is on a read-only input tape. Why would the out-degree of this graph be at most $2$ instead?

Based on some research into other things related to TMs, I discovered that any NDTM that has at most $k$ possible branches at each step can be modified into an NDTM that has at most $2$ possible branches at each step at the cost of a $\log_2(k)$ slowdown. Though I can not find any mention of this anywhere in the textbook, I assume this is what the authors are assuming.


Why is there the regularity condition in the master theorem? I have been reading Introduction to Algorithms by Cormen et al. and I'm reading the statement of the Master theorem starting on page 73. In case 3 there is also a regularity condition that needs to be satisfied to use the theorem:

... 3. If
$\qquad \displaystyle f(n) = \Omega(n^{\log_b a + \varepsilon})$
for some constant $\varepsilon > 0$ and if
$\qquad \displaystyle af(n/b) \leq cf(n)$      [this is the regularity condition]
for some constant $c < 1$ and for all sufficiently large $n$, then ..

Can someone tell me why the regularity condition is needed? How does the theorem fail if the condition is not satisfied?

Not a rigorous proof, but a "from the top of my head" explanation.

Imagine the recurrence $aT(n/b)+f(n)$ as a tree. The third case covers the scenario when the root node dominates the running time asymptotically, i.e. most of the work is being done in measly node on top of the recurrence tree. Then the running time is $\Theta(f(n))$.

To make sure the root actually does more work you need the

  $a f(n/b) \leq cf(n)$.

This says that $f(n)$ (the amount of work done in the root) needs to be at least as big as the sum of the work done in the lower levels. (The recurrence is called $a$ times on $n/b$ of the input.)

E.g. for the recurrence $T(n)=2T(n/4)+n$ the work on the level below the root is one fourth as big and only done twice $(n/4+n/4)$ versus $n$ so the root dominates.

But what if the function didn't fulfill the regularity condition? E.g. $\cos(n)$ instead of $n$? Then the work done on the lower levels might be bigger than the work done in the root so you are not certain that the root dominates.