Decision problems vs "real" problems that aren't yes-or-no I read in many places that some problems are difficult to approximate (it is  NP-hard to approximate  them). But approximation is not a decision problem: the answer is a real number and not Yes or No. Also for each desired approximation factor, there are many answers that are correct and many that are wrong, and this changes with the desired approximation factor!

So how can one say that this problem is NP-hard?

(inspired by the second bullet in How hard is counting the number of simple paths between two nodes in a directed graph?)

As you said, there is no decision to make, so new complexity classes and new types of reductions are needed to arrive at a suitable definition of NP-hardness for optimization-problems.

One way of doing this is to have two new classes NPO and PO that contain optimizations problems and they mimic of course the classes NP and P for decision problems. New reductions are needed as well. Then we can recreate a version of NP-hardness for optimization problems along the lines that was successful for decision problems. But first we have to agree what an optimization-problem is.

Definition: Let $O=(X,L,f,opt)$ be an optimization-problem. $X$ is the set of inputs or instances suitable encoded as strings. $L$ is a function that maps each instance $x\in X$ onto a set of strings, the feasible solutions of instance $x$. It is a set because there are many solutions to an optimization-problem. Thus we haven an objective function $f$ that tells us for every pair $(x, y)$ $y\in L(x)$ of instance and solution its cost or value. $opt$ tells us whether we are maximizing or minimizing.

This allows us to define what an optimal solution is: Let $y_{opt}\in L(x)$ be the optimal solution of an instance $x\in X$ of an optimization-problem $O=(X,L,f,opt)$ with $$f(x,y_{opt})=opt\{f(x,y')\mid y'\in L(x)\}.$$ The optimal solution is often denoted by $y^*$.

Now we can define the class NPO: Let $NPO$ be the set of all optimization-problems $O=(X,L,f,opt)$ with:

$X\in P$
There is a polynomial $p$ with $|y|\le p(|x|)$ for all instances $x\in X$ and all feasible solutions $y\in L(x)$. Furthermore there is an deterministic algorithm that decides in polynomial time whether $y\in L(x)$.
$f$ can be evaluated in polynomial time.

The intuition behind it is:

We can verify efficiently if $x$ is actually a valid instance of our optimization problem.
The size of the feasible solutions is bounded polynomially in the size of the inputs, And we can verify efficiently if $y\in L(x)$ is a fesible solution of the instance $x$.
The value of a solution $y\in L(x)$ can be determined efficiently.

This mirrors how $NP$ is defined, now for PO: Let $PO$ be the set of all problems from $NPO$ that can be solved by an deterministic algorithm in polynomial time.

Now we are able to define what we want to call an approximation-algorithm: An approximation-algorithm of an optimization-problem $O=(X,L,f,opt)$ is an algorithm that computes a feasible solution $y\in L(x)$ for an instance $x\in X$.

Note: That we don’t ask for an optimal solution we only what to have a feasible one.

Now we have two types of errors: The absolute error of a feasible solution $y\in L(x)$ of an instance $x\in X$ of the optimization-problem $O=(X,L,f,opt)$ is $|f(x,y)-f(x,y^*)|$.

We call the absolute error of an approximation-algorithm $A$ for the optimization-problem $O$ bounded by $k$ if the algorithm $A$ computes for every instance $x\in X$ a feasible solution with an absolute error bounded by $k$.

Example: According to the Theorem of Vizing the chromatic index of a graph (the number of colours in the edge coloring with the fewest number of colors used) is either $\Delta$ or $\Delta+1$, where $\Delta$ is the maximal node degree. From the proof of the theorem an approximation-algorithm can be devised that computes an edge coloring with $\Delta+1$ colours. Accordingly we have an approximation-algorithm for the $\mathsf{Minimum-EdgeColoring}$-Problem where the absolute error is bounded by $1$.

This example is an exception, small absolute errors are rare, thus we define the relative error $\epsilon_A(x)$ of the approximation-algorithm $A$ on instance $x$ of the optimization-problem $O=(X,L,f,opt)$ with $f(x,y)>0$ for all $x\in X$ and $y\in L(x)$ to be

$$\epsilon_A(x):=\begin{cases}0&f(x,A(x))=f(x,y^*)\\\frac{|f(x,A(x))-f(x,y^*)|}{\max\{f(x,A(x)),f(x,y^*)\}}&f(x,A(x))\ne f(x,y^*)\end{cases}$$

where $A(x)=y\in L(x)$ is the feasible solution computed by the approximation-algorithm $A$.

We can now define approximation-algorithm $A$ for the optimization-problem $O=(X,L,f,opt)$ to be a $\delta$-approximation-algorithm for $O$ if the relative error $\epsilon_A(x)$ is bounded by $\delta\ge 0$ for every instance $x\in X$, thus
$$\epsilon_A(x)\le \delta\qquad \forall x\in X.$$

The choice of $\max\{f(x,A(x)),f(x,y^*)\}$ in the denominator of the definition of the relative error was selected to make the definition symmetric for maximizing and minimizing. The value of the relative error $\epsilon_A(x)\in[0,1]$. In case of a maximizing problem the value of the solution is never less than $(1-\epsilon_A(x))\cdot f(x,y^*)$ and never larger than $1/(1-\epsilon_A(x))\cdot f(x,y^*)$ for a minimizing problem.

Now we can call an optimization-problem $\delta$-approximable if there is a $\delta$-approximation-algorithm $A$ for $O$ that runs in polynomial time.

We do not want to look at the error for every instance $x$, we look only at the worst-case. Thus we define $\epsilon_A(n)$, the maximal relativ error of the approximation-algorithm $A$ for the optimization-problem $O$ to be
$$\epsilon_A(n)=\sup\{\epsilon_A(x)\mid |x|\le n\}.$$

Where $|x|$ should be the size of the instance.

Example: A maximal matching in a graph can be transformed in to a minimal node cover $C$ by adding all incident nodes from the matching to the vertex cover. Thus $1/2\cdot |C|$ edges are covered. As each vertex cover including the optimal one must have one of the nodes of each covered edge, otherwise it could be improved, we have $1/2\cdot |C|\cdot f(x,y^*)$. It follows that $$\frac{|C|-f(x,y^*)}{|C|}\le\frac{1}{2}$$
Thus the greedy algorithm for a maximal matching is a $1/2$-approximatio-algorithm for $\mathsf{Minimal-VertexCover}$. Hence $\mathsf{Minimal-VertexCover}$ is $1/2$-approximable.

Unfortunately the relative error is not always the best notion of quality for an approximation as the following example demonstrates:

Example: A simple greedy-algorithm can approximate $\mathsf{Minimum-SetCover}$. An analysis shows that $$\frac{|C|}{|C^*|}\le H_n\le 1+\ln(n)$$ and thus $\mathsf{Minimum-SetCover}$ would be $\frac{\ln(n)}{1+\ln(n)}$-approximable.

If the relative error is close to $1$ the following definition is advantageous.

Let $O=(X,L,f,opt)$ be an optimization-problem with $f(x, y)>0$ for all $x\in X$ and $y\in L(x)$ and $A$ an approximation-algorithm for $O$. The approximation-ratio $r_A(x)$ of feasible solution $A(x)=y\in L(x)$ of the instance $x\in X$ is
$$r_A(x)=\begin{cases}1&f(x,A(x))=f(x,y^*)\\\max\left\{
\frac{f(x,A(x))}{f(x, y^*)},\frac{f(x, y^*)}{f(x, A(x))}\right\}&f(x,A(x))\ne f(x,y^*)\end{cases}$$

As before we call an approximation-algorithm $A$ an $r$-approximation-algorithm for the optimization-problem $O$ if the approximation-ratio $r_A(x)$ is bounded by $r\ge1$ for every input $x\in X$.
$$r_A(x)\le r$$
And yet again if we have an $r$-approximation-algorithm $A$ for the optimization-problem $O$ then $O$ is called $r$-approximable. Again we only care about to the worst-case and define the maximal approximation-ratio $r_A(n)$ to be
$$r_A(n)=\sup\{r_A(x)\mid |x|\le n\}.$$
Accordingly the approximation-ratio is larger than $1$ for suboptimal solutions. Thus better solutions have smaller ratios. For $\mathsf{Minimum-SetCover}$ we can now write that it is $(1+\ln(n))$-approximable. And in case of $\mathsf{Minimum-VertexCover}$ we know from the previous example that it is $2$-approximable. Between relative error and approximation-ratio we have simple relations:
$$r_A(x)=\frac{1}{1-\epsilon_A(x)}\qquad \epsilon_A(x)=1-\frac{1}{r_A(x)}.$$

For small deviations from the optimum $\epsilon<1/2$ and $r<2$ the relative error is advantageous over the approximation-ratio, that shows its strengths for large deviations $\epsilon\ge 1/2$ and $r\ge 2$.

The two versions of $\alpha$-approximable don’t overlap as one version has always $\alpha\le 1$ and the other $\alpha\ge 1$. The case $\alpha=1$ is not problematic as this is only reached by algorithms that produce an exact solution and consequentially need not be treated as approximation-algorithms.

Another class appears often APX. It is define as the set of all optimization-problems $O$ from $NPO$ that haven an $r$-approximation-algorithm with $r\ge1$ that runs in polynomial time.

We are almost through. We would like to copy the successful ideas of reductions and completness from complexity theory. The observation is that many NP-hard decision variants of optimization-problems are reducible to each other while their optimization variants have different properties regarding their approximability. This is due to the polynomialtime-Karp-reduction used in NP-completness reductions, which does not preserve the objective function. And even if the objective functions is preserved the polynomialtime-Karp-reduction may change the quality of the solution.

What we need is a stronger version of the reduction, which not only maps instances from optimization-problem $O_1$ to instances of $O_2$, but also good solutions from $O_2$ back to good solutions from $O_1$.

Hence we define the approximation-preserving-reduction for two optimization-problems $O_1=(X_1,L_1,f_1,opt_1)$ and $O_2=(X_2,L_2,f_2,opt_2)$ from $NPO$. We call $O_1$ $AP$-reducible to $O_2$, written as $O_1\le_{AP} O_2$, if there are two functions $g$ and $h$ and a constant $c$ with:

$g(x_1, r)\in X_2$ for all $x_1\in X_1$ and rational $r>1$
$L_2(g(x, r_1))\ne\emptyset$ if $L_1(x_1)\ne\emptyset$ for all $x_1\in X_1$ and rational $r>1$
$h(x_1, y_2, r)\in L_1(x_1)$ for all $x_1\in X_1$ and rational $r>1$ and for all $y_2\in L_2(g(x_1,r))$
For fixed $r$ both functions $g$ and $h$ can be computed by two algorithms in polynomial time in the length of their inputs.
We have $$f_2(g(x_1,r),y_2)\le r \Rightarrow f_1(x_1,h(x_1,y_2,r))\le 1+c\cdot(r-1) $$ for all $x_1\in X_1$ and rational $r>1$ and for all $y_2\in L_2(g(x_1,r))$

In this definition $g$ and $h$ depend on the quality of the solution $r$. Thus for different qualities the functions can differ. This generality is not always needed and we just work with $g(x_1)$ and $h(x_1, y_2)$.

Now that we have a notion of a reduction for optimization-problems we finally can transfer many things we know from complexity theory. For example if we know that $O_2\in APX$ and we show that $O_1\le_{AP} O_2$ it follows that $O_1\in APX$ too.

Finally we can define what we mean by $\mathcal{C}$-hard and $\mathcal{C}$-complete for optimization-problems:

Let $O$ be an optimization-problem from $NPO$ and $\mathcal{C}$ a class of optimization-problems from $NPO$ then $O$ is called $\mathcal{C}$-hard with respect to $\le_{AP}$ if for all $O'\in\mathcal{C}$ $O'\le_{AP} O$ holds.

Thus once more we have a notion of a hardest problem in the class. Not surprising a $\mathcal{C}$-hard problem is called $\mathcal{C}$-complete with respect to $\le_{AP}$ if it is an element of $\mathcal{C}$.

Thus we can now talk about $NPO$-completness and $APX$-completness etc. And of course we are now asked to exhibit a first $NPO$-complete problem that takes over the role of $\mathsf{SAT}$. It comes almost naturally, that $\mathsf{Weighted-Satisfiability}$ can be shown to be $NPO$-complete. With the help of the PCP-Theorem one can even show that $\mathsf{Maximum-3SAT}$ is $APX$-complete.


How does IEEE 754 decimal encoding work? This may be a silly question, but if a computer works in binary how can you encript numbers using decimal?

Fair question. First of all, it's worth noting that the IEEE decimal formats are fairly modern and not used particularly often—they're meant for the rare use cases where things need to round in a specific way, mostly in finances.

But, there are various ways to encode a truly decimal number (i.e. a number stored as a series of base-10 digits) in binary. The simplest is called BCD (Binary Coded Decimal), which uses four bits to represent each digit. Many early computers used this system because humans are used to decimal and found it more intuitive.

BCD is kind of wasteful, because four bits can represent any number from 0 to 15, and a single digit only need to represent a number from 0 to 9. So IEEE uses slightly different packings, called Binary Integer Decimal and Densely Packed Decimal. They're somewhat more complicated, but the idea is the same: you have a one-to-one mapping between decimal digits and binary bits, wasting as few bits as possible.


How is the optimal number of hashes is derived in bloom filter? As mentioned in several resources such as Wikipedia the optimal number of hash functions for a bloom filter is known to be $$k=\frac{m}{n} \ln 2$$ but how is this number derived? It seems that it's the number that minimizes the false positive rate which is equal to $$(1-(1-\frac{1}{m})^{kn})^k$$
Can anybody explain the steps to find the argmin of the FP rate?

We want to find the value of $k$ that minimizes the function
$$
f(k) = \left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k.
$$
When $m$ is large, $1 - 1/m \approx e^{-m}$, and so
$$
f(k) \approx \left(1 - e^{-kn/m}\right)^k.
$$
The logarithm of this is
$$
\log f(k) \approx k \log(1-e^{-kn/m}).
$$
The derivative of this approximation is
$$
\log(1 - e^{-kn/m}) + k \frac{\frac{n}{m}e^{-kn/m}}{1-e^{-kn/m}} =
\log(1 - e^{-kn/m}) + \frac{kn}{m} \frac{e^{-kn/m}}{1-e^{-kn/m}}.
$$
Let $x = e^{-kn/m} \in (0,1)$. The derivative is thus
$$
\log (1-x) - \log x \frac{x}{1-x} = \frac{(1-x)\log(1-x)-x\log x}{1-x}.
$$
It is not hard to check that the numerator is positive for $x<1/2$, zero at $x=1/2$, and negative for $x>1/2$. This means that when $k < \frac{m}{n}\log 2$, the approximation to $f(k)$ is decreasing, and when $k > \frac{m}{n}\log 2$, it is increasing. It thus reaches a minimum when $k = \frac{m}{n} \log 2$.


What is a distributed algorithm for generating random "private" pair-matchings? Say you have 2N named peers (agents) able to address each other by their name and communicate freely among them.
What distributed algorithm could they use in order to randomly pair up? The final situation would be that the agents were able to organize themselves in N random couples. On different runs the random couples should be different.
Important: the algorithm should be "private" in the following sense: at the end of the round, each agent should only know the name of agent it was paired with.
It's also important that the agents have no possible way to influence who they end up paired with.

Let's assume the agents are labeled $[0, n)$. Let $w > 2$ be a small constant, e.g. 4. Let $F_k(x)$ be an oblivious pseudo-random function (OPRF).
Let each agent generate random value $s_i$, announce $H(s_i)$ and then choose $r = \bigoplus_i s_i$ to ensure  a fair random shared seed (peers checking the hashes).
Initially agent $i$ chooses $X_i = i$. Then, some rounds take place. Use the chosen seed to derive a different $P_r$ and $w$ agents $A_{r,0}, A_{r,1}, \cdots, A_{r,w-1}$ for each round. Then, in round $r$ every agent computes
$$X'_i = (P_r - X_i) \bmod n$$
$$\hat X_i = \max(X_i, X'_i)$$
$$p = H(\hat X_i) \bmod  w$$
$$b =\text{get-secret}\left(p, r, \hat{X_i}\right) \bmod 2$$
where $\text{get-secret}(p, r, \hat{X})$ securely contacts agent $A_{r,p}$ and uses the OPRF primitive to compute $F_{K_{p,r}}(\hat{X})$, where $K_{p,r}$ is some never-shared secret round key generated (and stored) by agent $A_{r,p}$. Then, at the end of the round iff $b = 1$ the agent replaces $X_i$ with $X'_i$.
After the round is over the $w$ chosen agents $A$ can (and should) communicate to ensure no one cheated and asked for more than one secret. This ensures everyone only has partial information. If you force the $\text{get-secret}$ requests to be signed by agent $i$ one can even provide evidence another agent tried to cheat.
Do this for a sufficient* number of rounds and the result is that each agent $i$ has a value $X_i$ such that there is a permutation $\sigma(i) = X_i$, yet every agent only knows their own $\sigma(i)$, and is deeply unsure about anyone else's $\sigma(j)$.
However, this just gives us a secret random permutation. But we can use this to get a pairing. Note that if we let $g(i) = i \oplus 1$ (where $\oplus$ is XOR) then $f(i) = \sigma^{-1}(g(i))$ is a pairing (assuming zero-indexed permutations).
How can we compute $\sigma^{-1}$? By noting that each round is it's own inverse, each agent sets $X_i = g(X_i)$, and we run all the rounds again, in reverse order (with the same $P,A$ and $K$ values), again ensuring that no agent requests too many secrets. The end result is that $X_i$ contains the partner for each agent.

* The technique above is inspired by sometimes recurse shuffle. Read the paper for more ideas, and to get some bounds for what is sufficient.


How to prove a LTL formula correct in a specific model? I have been learning Verification by model checking recently and I get the following question:

$Whether\ the\ LTL\ formula\ M, q_3\ \models (X\ \lnot a) \rightarrow (F\ G\ \lnot a)\ is\ established\ or\ not\ in\ this\ model\ M?$

And there is the description of the model.
.

I think it is correct, because the next state of $q_3$ is $q_1$ or $q_2$ and the next state of $q_1$ is $q_2$. So I get an infinite loop about $q_2$, which satisfies $F\ G\ \lnot a$. But I only can give the thought of my prove in natural language not mathematical rigor way.

if not mind, could anyone tell me my thought is right or wrong and prove it in a mathematical rigor way?

Thanks in advances

Your intuition is correct.

Consider an arbitrary path starting from $q_3$: let it be $q_3\, q\, q'\, q'' \ldots$. We need to prove it satisfies $\varphi = (X\lnot a)\rightarrow (FG \lnot a)$.

We proceed by cases on the second state $q$ in the path. It can be  one of $q_1,q_2,q_4$.

If $q=q_4$ then $X\lnot a$ is false in the path, hence $\varphi$ is true in the path.

If $q=q_1$ or $q_2$ then we must have $q'=q''=\cdots=q_2$. The whole path is of the form
$q_3\, q\, q_2\, q_2\, q_2 \ldots$. This path makes $FG\lnot a$ true, since there exists a suffix (namely, $q_2\, q_2\, q_2 \ldots$) where $G\lnot a$ is true ($a$ is false in each state of the suffix). Hence, $\varphi$ is true in the path.

You could make this even more formal by explicitly referring to the definition of validity.


how pseudo direct addressing works? In pseudo direct addressing mode (For the MIPS architecture) the 26 bit of the jump instruction are joined to the upper 4 bits of the PC .

how could this help in jumping to relative positions suppose I want to jump backward instead of forward ( i.e. if i want to jump to the beginning of a loop after executing it's body ),
What I get is this will limit the jump to be 2^28 from the following instruction but Is this applicable backward too ?
I am really confused by this so excuse me for such a silly question...

In MIPS-speak, these areas of memory of 28 (26+2; the +2 is because instructions are four bytes in size) bit address space (256MB) are referred to as "superblocks". Pseudo-direct addressing allows you to jump anywhere within the same superblock. It doesn't matter if it's forwards or backwards.

This was never a problem in practice because it's very rare for a single binary (whether it's an executable or a shared library) to have more than 256MB of code. IIRC, the MIPS linker could handle it if it ever occurred by generating a trampoline. Suppose that the compiler generated a jal, for example, where the linker discovered that the target was in a different superblock. Then the linker would generate a couple of instructions to do the full jump, and point the jal to that.


Word tiling, where you must use each tile exactly once Given words $w_1,\ldots,w_n$ in binary alphabet and another word $w$, decide if $w$ can be written as a product $w = w_{i_1} \cdots w_{i_n}$ (in the monoid $\{0,1\}^\ast$) for some permutation of indices.
Is this a known problem? Is it NP-complete?
Details:

The words $w_1,\dots,w_n$ are part of the input.  Therefore, there is no a priori upper bound on $n$, $|w_i|$, or $|w|$.  However, we may assume that $|w|=\sum |w_i|$.

If we restrict the problem to instances with $|w_i|\le k$ (where $k$ is a fixed constant), we obtain a new problem $WT_k$.  $WT_k$ belongs to $P$.  It's possible to build a polynomial-time algorithm for $WT_k$, using dynamic programming.  Indeed, in this case the number of different words $w_i$ is bounded by $2^k$. Hence any sequence $\{w_1,\ldots,w_n\}$ can be encoded by a $2^k$-tuple of integers (an element of $\mathbb{Z}^{2^k}$). It is convenient to assume that $w_i\ne  \varepsilon$.
Now with every initial segment $w'$ of $w$ we associate a set of tuples in $\mathbb{Z}^{2^k}$ that describe sequences of $w_i$'s resulting in $w'$. For instance, with $\varepsilon$ we associate a single tuple $(0,\ldots,0)$ and $\varepsilon$ is considered processed. Then for every processed segment $w'$ we go over its tuples and see which ones we can append to $w'$ (which $w_i$'s are still available).  For instance, if $w' w_i$ gives another initial segment $w''$ of $w$ then we add the corresponding tuple for $w''$. Eventually, all initial segments will be covered.  Here it is crucial that $k$ is fixed, as it ensures that the sets of tuples associated with every $w'$ is polynomially bounded (with a very large degree).

I suspect that the general problem is NP-complete and I'd appreciate any suggestions.

Clearly the problem can be viewed as a sort of a bounded Post correspondence problem with a fixed collection of pairs $(w,\varepsilon),(\varepsilon,w_1),\ldots,(\varepsilon,w_n)$. Not sure if this helps, though.

Clearly, the restriction to a binary alphabet is irrelevant. One can work with any countable alphabet. Need to be careful though: the item 2 does not hold when the alphabet is unbounded.

I can't speak to whether it's a known problem, but it is NP-complete.

It's clearly in NP, so we just have to show NP-hardness. The following reduction is from the strongly NP-hard 3-partition problem, which asks, given a multiset of positive integers $[x_1,\ldots,x_{3m}]$, whether there exists a partition into $m$ submultisets such that the sum of each submultiset is equal to the integer $s=\frac{1}{m}\sum_{i=1}^{3m}x_i$. For each $i\in\{1,\ldots,3m\}$, make a string $a^{x_i}$. Make $m-1$ strings $b$. The target word $w$ is

$$a^sba^sb\cdots ba^s.$$


Is Equality problem decidable in DCFL and CFL? Equality problem is checking if 2 DCFL's or CFL's are producing same language.

I read that it is decidable for DCFL and undecidable for CFL.

If we consider a DCFL like a^n b^2n / n>=1, here we can draw a PDA for this in two ways.
So how can we check if 2 DCFL's produce the same language by just looking at the PDA as they are not unique?

We can't. Infinitely many different PDAs for the same DCFL exist.

In 1997, Géraud Sénizergues proved that equivalence of DCFLs is decidable, and he was awarded the Gödel Prize for it.

For general context-free languages, it is undecidable.
As a matter of fact, it is already undecidable for linear context-free languages.


De Casteljau's algorithm without temporaries / stack De Casteljau's algorithm is a method for calculating a point on an order $N$ Bezier curve at time $t$ by performing a linear interpolation between two order $N-1$ Bezier curves at time $t$.  You do this recursively until you reach order 0 which is single point / data value.

Calculating a point on an order 1 (linear) Bezier curve with control points $A$ and $B$ at time $t$ is done like this:

$\overline{AB} = A(1-t) + Bt$

Which you can see is just a linear interpolation between $A$ and $B$ at time $t$.

Calculating an order 2 (quadratic) Bezier curve with control points $A$,$B$ and $C$ is done by interpolating between $A$ and $B$, interpolating between $B$ and $C$ and interpolating between those results:

$\overline{AB} = A(1-t) + Bt$

$\overline{BC} = B(1-t) + Ct$

$\overline{ABC} = \overline{AB}(1-t) + \overline{BC}t$

Note that you could expand that out algebraically to get a polynomial in Bernstein form that doesn't use interpolation, but instead can be evaluated directly in one step:

$\overline{ABC} = A(1-t)^2 + 2B(1-t)t+Ct^2$

Calculating an order 3 (cubic) Bezier curve with control points $A$,$B$,$C$,$D$ at time $t$ would continue the pattern by doing a linear interpolation between $\overline{ABC}$ and $\overline{BCD}$ at time $t$.

When evaluating a curve using the De Casteljau algorithm, you need temporary storage.  In the $\overline{ABC}$ case you need to first calculate $\overline{AB}$ and $\overline{BC}$ and then you combine those results.  The storage needs get larger as the curve order increases.

My question is this:

Is there a way to reformulate the De Casteljau algorithm such that you can still use lerps to evaluate a point on the curve, but without the temporary storage needed?

The OP has indicated in the comments that they are only interested in a specific time $t$. De Casteljau's algorithm can be described as follows:

Input: order $N$, points $A_0,\ldots,A_N$, time $t \in (0,1)$.
Calculate $\overline{A_i A_{i+1}} = A_i(1-t) + A_{i+1}t$ for $0 \leq i \leq N-1$.
Calculate $\overline{A_i A_{i+1} A_{i+2}} = \overline{A_i A_{i+1}} (1-t) + \overline{A_{i+1} A_{i+2}} t$ for $0 \leq i \leq N-2$.
Continue similarly for $N-2$ more steps.
Output $\overline{A_0 A_1 \ldots A_n}$.

It is not completely clear what it does it meant to "implement" De Casteljau's algorithm. However, a reasonable informal interpretation of this statement is as follows:

  Schedule the computations in De Casteljau's algorithm in a way that uses the least amount of space and the least amount of computations.

Note that the two efficiency measures could potentially conflict.

There is an area of theoretical computer science covering exactly such questions, namely pebbling. See Jakob Nordström's survey-in-making. Your task exactly corresponds to pebbling a height $N$ pyramid. On the one hand, this is known to require $N+2$ pebbles (roughly temporary memory locations). On the other hand, there is a pebbling strategy using $N+2$ pebbles and a linear number of steps (a linear number of computations — we are allowing computing each node, i.e. $\overline{A_i \ldots A_j}$, more than once).

Here is how this pebbling strategy looks like in the case $N=2$:

$T_1 \gets A_0$.
$T_2 \gets A_1$.
$T_3 \gets T_1(1-t) + T_2t$.
$T_1 \gets A_2$.
$T_4 \gets T_2(1-t) + T_0t$.
$T_1 \gets T_3(1-t) + T_4t$.

The output is in $T_1$.


Is the statement "Control unit controls overall operations of computer." true or false I was tutoring a grade 4 student about CPU and I got confused as there are also the other units of a cpu like arithmetic and logic unit and memory unit. So, is the above statement actually true even if ALU is the one which does the arithmetic and logical operations?

Well true, sort of.

In simple terms: The control unit, regardless of how it is implemented, directs the activities of all of the other processor units.

However: It does so by decoding the instructions fetched from memory, the program.

So ultimately the program controls what gets done.


Having a problem understanding the execution of I/O in Von Neumann model I might have gone too deep in my search after the answer which might be much easier than what I figured.

Essentially I wanted to figure out how I/O are executed in a Von Neumann machine, but more I read, the more confused I became.

What they are saying in "Introduction to computing systems" (Patt and Patel) and other websites covering this is that I/O devices in the VN machine has an I/O controller which works as a liaison between the I/O device(s) and the CPU which will interrupt the CPU once the I/O operation is finished.
(1. it receives the write/read request, 2. notifies the cpu and let it go back to doing whatever task it was doing, 3. interrupts it once the I/O operation is finished).

So this is some kind of Interrupt-driven I/O, but is that enough to explain how I/O are executed in VN machine?
How does a program communicate with an I/O device?
How will you explain the data transfer between memory and I/O devices?

You are not wrong in stating that you went too deep in your search.

To counter these confusions, you might want to study how instructions are executed electronically in a computer.

The one thing worth remembering is: In a computer everything is controlled by the CPU. That includes the IO devices, their interfaces, the instructions put forth by them and the ones relegated to them.

Typically, what happens is that a program or a facility in your machine generates interrupts. Generally, the interrupt itself is an instruction to the CPU coming from the memory, loaded in the memory by the CPU itself at a prior time. When the CPU executes the interrupt, it checks the status of I/O device (like a key press), registers it and manipulates it as per instructions that follow. When modern computers turn on, BIOS - Basic Input Output System, that is - is used for generating interrupts and is used as an interface/liaison between the CPU and I/O devices. BIOS itself is a program (set of instructions) that resides on ROM and is read by the CPU at time zero. After the boot up is complete and OS is loaded to the memory, this facility is provided by the Operating System.

  How does a program communicate with an I/O device?

That depends upon the level of abstraction you are working on. If you want to see the program as a single and lone set of instructions to the CPU then the I/O interrupts are a part of the program. They are executed and tell the processor which device is to be contacted and in what manner. A little knowledge of assembly would be helpful for clarification in this context. But a small example of instructions to CPU is as follows:

1. Load integer 8 in Register 1.  //Instruction 'Load', Data '8'
2. Check keyboard for key press.  //An interrupt to Keyboard
3. Store key press value in Register 2.
4. Add contents of Register 1 and Register 2 in Register 3.
5. Pass contents of Register 3 to Display. //An output interrupt.

In the case of an operating system like Windows, the interrupts are a part of operating system program and are used to call the CPU's attention not only to I/O devices, but also to other programs in the memory. The IO interrupts here are in driver domain present in the memory as an interface. The user applications or the other programs in memory make calls to the operating system to make these interrupts, they can not directly make interrupts. Following is an example of a simple program in MSIL assembly.

.maxstack 2
.entrypoint   //begins here.
ldc.i4 8      //load integer 8 to stack.
ldc.i4 9      //load integer 9 to stack too.
add           //Add last two integers.
call void [mscorlib]System.Console.WriteLine(int32)  //A call to windows to
              //display the answer in console. Windows does the rest.

  How will you explain the data transfer between memory and I/O devices?

An instruction by a program to check the status of IO device. An instruction to get the data from the device and store it into a register. An instruction to store the value of that register into a memory location at a certain address in RAM. That location can be read by the program when required.


Why is backpropagation called backwards propagation of error, when it back propagates error derivatives? Wikipedia says:

  The backward propagation of errors or backpropagation, is a common method of training artificial neural networks and used in conjunction with an optimization method such as gradient descent.

Ultimately, backward propagation is used to get the partial derivates of the weights and biases of the network, so that gradient descent can be used.

This means you end up with $\frac{\partial TotalError}{\partial weight_i}$ and $\frac{\partial TotalError}{\partial bias_i}$ at the end, for all weights and biases, but you don't actualy end up with any sort of specific error value for the neurons.

With that in mind, why is it called back propagation of errors, instead of backpropagation of error gradient or something similar?

It's actually the error for the neurons. The actual reason for derivation is this:

You find an error then you find the derivative of the error according to some differential equation.
Gradients you obtain using that derivative is basically to determine how much one single neuron in the network made mistake. Gradient at one neuron means if you update the weights or biases according to that you decrease the error network makes.

Backpropagation is the mathematical system for assesing how much one neuron made mistake so you can improve it. Definition is true in that sense.


Given $n$ items with $k$ properties, construct a query that contains between $\frac {n} 3$ to $\frac {2n} 3$ items I have $n$ items that have a total of $k$ properties. Each item can have any number of properties, from $1$ to $k$. There is no upper limit to k (the lower limit is $\lceil log(n) \rceil$). The items are distinct, so they have different properties.

The query must only contain AND logical operators. For example, a query can be property A and NOT property B and property C.

Obviously, I must construct a query that has an intersection of properties such that the search space is reduced by $1/3$. Is there a faster way of doing this than simply doing a $O(2^k)$ brute force algorithm?

You are missing a condition – no two elements have exactly the same set of properties. Consider for example the extreme case in which no item has any properties – any query will get either all elements or none of them. We can also assume that $n>1$.

A simple iterative procedure constructs such a query. Let the properties be $P_1,\ldots,P_k$.

Let $x_1$ be the setting of $P_1$ which maximizes the number of elements satisfying $P_1=x_1$.
Let $x_2$ be the setting of $P_2$ which maximizes the number of elements satisfying $P_1=x_1$ and $P_2=x_2$.
And so on.

Denote by $N_i$ the number of elements satisfying $P_1=x_1,\ldots,P_i=x_i$. Thus $N_0 = n$ and $N_k = 1$ (by the missing condition). Let $i>0$ bet the minimal index such that $N_i < 2n/3$ (such an index exists since $N_k=1 < 2n/3$). Thus $N_{i-1} \geq 2n/3$. By construction, $N_i \geq N_{i-1}/2 \geq n/3$. It follows that $n/3 \leq N_i < 2n/3$.


Conversion of FA to Regular Expression If there is a transition with no input in the FA, when it is converted to a regular expression should it be accepted as ɛ transition? As an example picture shown below, should regular expression showing possible transitions between 1 and 3 (1-2-3 , 1-3) be accepted (ab+ɛ) or just ab?

The regular expression is supposed to match (exactly) all of the words that the automaton accepts. If you pretend that some of the transitions of the automaton don't exist, you're effectively converting a different automaton, and that automaton probably accepts different strings from the ones you're supposed to accept.

In this specific case, pretending that there's no $\varepsilon$-transition from the first state to the third one means that the automaton no longer accepts the word $c$.


Using the Consequence Rule I have the following example that I have to prove

{a>7 ^ b>=0} n:=a-b {n<a ^ a+b>=0}

Using the Consequence Rule I assumed that the P is true

{true} n=a-b {n<a ^ a+b>=0}

so logically, the Q should be true, but I'm not sure if that'd be enough.

Here is what you need to prove:

  If $a > 7$, $b \geq 0$ and $n = a-b$ then $n < a$ and $a+b \geq 0$.

By the way, this is actually false, since if $b = 0$ then $n = a$. Perhaps you miscopied?


What is sub graph isomorphism? I am confused about the definition of sub graph isomorphism, wikipedia says that the subgraph isomorphism problem is a computational task in which two graphs $G$ and $H$ are given as input, and one must determine whether $G$ contains a subgraph that is isomorphic to $H$.

Is this the correct statement or is it whether $G$ contains a subgraph that is isomorphic to a subgraph in $H$?

No, that is not the correct statement.

Every graph contains the empty graph as a subgraph, the problem as you define it would return TRUE for all pairs of graphs, which isn't very interesting.

Finding the largest common subgraph of two graphs would be an interesting problem, and it is at least as hard as the actual subgraph isomorphism problem (since $G$ contains a subgraph isomorphic to $H$ if and only if the largest common subgraph is isomorphic to $H$.)


Check whether a directed, rooted spanning tree is actually some shortest-paths tree in $O(V + E)$ time Given a directed graph $G = (V, E)$, with all edge weights being non-negative, someone has written a program that he/she claims implements Dijkstra's algorithm.
For a fixed starting vertex $s$, the program produces $v.d$ (shortest distance from $s$) and $v.\pi$ (immediate predecessor in the shortest path) for each vertex $v \in V$.

  Question: How to check whether the $d$ and $\pi$ values match those of some shortest-paths tree of $G$ in linear time (i.e., $O(V + E)$)?

My attempts:

Feed the $d$ and $\pi$ values into a running instance of our real Dijkstra algorithm and check if some step would go wrong.
The key point here is how to reduce the running time of the real Dijkstra algorithm from $O(E \log V)$ to $O(V + E)$, taking advantage of the existing $v.d$ and $v.\pi$ values.
To check the triangle inequality condition: For all edges $(u,v) \in E$, we have $d(s,v) \le d(s,u) + w(u,v)$.

  Question: However, is the triangle inequality condition a sufficient one for some directed, rooted spanning tree to be a shortest-paths tree?

Hint:

This question is telling us to find an algorithm in $O(V+E)$ which immediately suggests us some kind of search in the graph, i.e, DFS.
Using $\pi$ we should be able to build a candidate tree $T$ rooted in $s$ to test if it's shortest-path tree.
In each shortest-path tree, we have that for every $v \in V(T)$, $v \neq s$, the equality $d(\pi(v)) + w(\pi(v), v) = d(v)$ holds.


How does one end up with a non-integer exponent in time complexity? (e.g., $O(n^{2.81})$) Periodically I come across sentences like

"Winograd's variant [20] of this algorithm, whose asymptotic complexity is
also $O(n^{2.81})$ are considered" (from https://www.cise.ufl.edu/~sahni/papers/strassen.pdf)

I understand intuitively how we end up with complexities like $O(n^2)$ and $O(n \log n)$ because I can see how the loops and trees work.  But I've got no idea of how one ends up deriving a complexity with a decimal. Can someone give me an example how this happens?

The running time complexity of Strassen's algorithm is given by the recurrence
$$
T(n) = 7T(n/2) + O(n^2).
$$
(With a suitable base case.) The solution of this recurrence is $T(n) = O(n^{\log_2 7})$.

Strassen's algorithm multiplies two $n \times n$ matrices $A,B$ by decomposing them into four $(n/2)\times(n/2)$ matrices each, computing seven linear combinations of the smaller matrices each, say $(A_i,B_i)_{i=1,\dots,7}$, recursively computing $C_i = A_i B_i$, and computing the four $(n/2)\times(n/2)$ matrices of the result by taking linear combinations of the matrices $C_i$. That's how this running time came to be. If you want to learn more, there is a lot of information out there on Strassen's algorithm. There are, by the way, asymptotically faster algorithms for matrix multiplication, the current champion being Le Gall.


Exclusion in a context-free language? I am learning automata theory, and I am confused about this exercise:

Give context free grammar to create the following language where the
input  alphabet is $\{a,b\}$
$L = \{w \text{ where }w\text{ is NOT of the form }b^n a^n\}$

So, I understand how to create $\{b^n a^n, n\in\mathbb{N}\}$:

$$S \to bSa \mid \epsilon$$

But I am lost as to how to generate a language that is $\{w \text{ where }w\text{ is NOT of the form }b^n a^n\}$.
Help would be appreciated.

A word in $L$ must either be of the form $b^i a^j$ with $i \neq j$ or it must have $ab$ as a substring.
Therefore you can write a context-free grammar $G$ for $L$ as the union of two context-free grammars $G_1$ and $G_2$ for $L_1 = \{b^i a^j \mid i \neq j\}$ and $L_2 = \{w \in \{a,b\}^* \mid ab \mbox{ is a substring of } w\}$.
It is easy to come up with a context-free grammar $G_2$. In fact, it is even easy to come up with a regular expression for $L_2$: $(a \mid b)^*ab(a \mid b)^*$. Therefore I will only focus building $G_1$.
A word in $w=b^ia^j \in L_1$ can be written as $w = b^k \alpha a^k$, where $k = \min \{i,j \}$ and $\alpha$ is a non-empty string containing only $a$s or only $b$s. Conversely, all words of the form $b^k \alpha a^k$ belong to $L_1$. Then, this is a valid grammar $G_1$:
$$
\begin{align*}
S &\to bSa \mid A \mid B \\
A & \to aA \mid a \\
B & \to bB \mid b
\end{align*}
$$


Solve every problem with recursion Is it possible to solve every problem (solvable with turing machine) with only recursion ?
If yes, which principles or theories assure this ?
Thanks

Can you define what it means to solve a problem "only" with recursion?

Would your definition allow an algorithm like this:

int foo(int n) {
    if (n==1) return 1;
    while(someCondition) {
        do something
        foo(n-1);
    }
}

If your definition would wllow this, then it would be easy to transform every algorithm in such a recursive form (you could do all your calculations in the outermost function call and do nothing in the recursive calls).


What are the pros and cons of RANSAC versus Hough Transform? A friend needs to find the pool balls in an image of a pool table. Would a Hough transform be a good idea? Why/why not? Would RANSAC be better?

The question comes from this study guide (http://www.cc.gatech.edu/~afb/classes/CS4495-Spring2015-OMS/), is not homework, and I am not currently taking this class.

What I know: RANSAC is least-squares plus a system with voting. We pick the least squares solution that has the least outliers. Hough transform is about finding parametric shapes. You can transform something into Hough space. For a circle you might want to know the radius. If you know more information about your circle (the pool ball) you'll not have as much space to search.

I think it makes sense to use Hough transforms in the case of finding pool balls so I am wondering how and why you'd even use RANSAC.

Edit: I think you could use RANSAC if you had another image to match to that you knew had pool balls in it. The images would be matched against each other, and the features that came out would be the pool balls. But again, it seems like RANSAC isn't a good idea because it could only fit one model to the whole image.

The Hough transform would be a reasonable approach for this.  Another reasonable approach would be to find connected regions of similar hue, and for each, test if it is approximately pool-ball-shaped.

RANSAC doesn't seem like a good tool for this purpose.  RANSAC is commonly used to find, e.g., a line that approximately  goes through a bunch of points (but possibly with a few outliers that might not fit the line).  Here, the pool balls are spheres, not lines.

RANSAC is typically used for other tasks: e.g., for aligning two images.  However, here image alignment probably isn't a good way to find pool balls on a pool table.


Is the following NP-complete? I have encountered the following problem.

We have $N$ points in discrete coordinates,distributed through a plane with vertical axis $[1..Y]$ and horizontal axis $[1..X]$.
We can perform the action of removing all points with vertical coordinate $y$, in short removing $y$.

What is the least number of $y$'$s$ we must remove so that the number of $x$ that have points is less than $X/2$.
For example in the graph above removing 1 and 2 leaves points only in 1,3,6,9.

This seems like a NP-complete problem to me so the only solution I have developed is removing all combinations of $y'$s. I would be grateful if someone experienced in computation-theory could point me to a similar known problem (or maybe a problem this could be reduced to), any suggestion is welcome.

If you mean by "the number of $x$ that have points" that the number of distinct values $x$ such that there is a point $(x, y)$ such that $y$ has not been removed is at most $X/2$, then your problem is extremely similar to Set Cover, which is $\mathbf{NP}$-complete.

Your problem would be the variant in which you ask for the minimum number of sets needed to cover half the elements of your universe. I would be very surprised if this was not $\mathbf{NP}$-complete. I'll think about it some more and update this if I think up a proof of $\mathbf{NP}$-completeness.


Rate Monotonic First Fit vs. Rate Monotonic Next Fit vs. Proportionate Fair What would an example of a set of tasks be, where RMFF, RMNF and P-Fair all result in a different number of processors required?

Look at it this way.

RMFF- Places Task one after the other until the processor goes beyond the bound

RMNF - Looks at all the processors and see where the task will fit

P-Fair - Uses max utilization of 1 for each processor.

RM can only use N(2^(1/N)-1), this means that both RM will have a different value than P-Fair when utilization is between that value and its upper bound.

As for the RMFF, RMNF just think about it and play with the numbers and you will find answer. Make up task and start placing them according to both methods.

P.S: 2 more hours? Hope it helped.


How does one go about designing a system that never crashes? I read somewhere that the Apollo Guidance Computer was designed in such a way, that, although it is hugely less powerful than the average smartphone, it was dependable to the point that it "never crashed". My questions pertaining to this were:

Is designing such a digital system possible, even in the '60's ?
What are the constraints that one would want to look out for when attempting to design such a digital system that "never crashed", using today's technology?

It wasn't possible back then, in the absolute sense. What you're essentially looking for when you say "never crashes" is a system that always makes progress towards its goals. Today, we can prove that a computer program does that, but the relevant methods to construct such proofs were only developed starting in the 70's - years after the Apollo Guidance Computer was developed.

Practically speaking, today we would formulate the requirements on the guidance computer using a formal specification language. In particular, we'd identify each task of the computer, and specify that each task finishes n a bound number of steps. We also define a task scheduler that never halts and chooses the right tasks for each stage of the mission. With a bit of work, we then prove that every task that needs to be executed is executed on time. We then transform the specification into code, in a way that allows us to verify the proof still holds.


$k$-coloring in BPP, implies $k$-coloring in ZPP Consider the next problem:

$k$-COL: Given a graph $G=(V,E)$, does it have a valid $k$-coloring?

I need to prove that if $k$-COL is  in BPP, then it is also in ZPP. In other words, show that if there is a probabilistic polytime algorithm that decides whether a graph has a valid $k$-coloring or not with bounded error, then there is also a probabilistic polytime algorithm that does that with zero error.

My attempt

I've managed to prove it assuming that we are allowed to call an oracle that solves the above problem in polynomial time (see below).
But is there a way to show this without assuming $k$-COL $\in$ P?

Let $\mathcal{A}$ be a polynomial time machine with access to an oracle for $k$-COL.

Let $G$ be a graph and let $M$ be the BPP NTM that makes $k$-COL be in BPP. Let's define the following NTM $M'$:

If $G \in$ $k$-COL, execute $M$ on $G$.

If $M(G) = 1$, execute $\mathcal{A}$ on $G$. For sure, $\mathcal{A}(G)=1$.
If $M(G) = 0$, output $?$.

If $G \notin$ $k$-COL, execute $M$ on $G$.

If $M(G) = 1$, output $?$.
If $M(G) = 0$, execute $\mathcal{A}$ on $G$. For sure, $\mathcal{A}(G)=0$.

Definitions (for reference)

We define the class of languages Bounded-error Probabilistic Polynomial-time (BPP) as all $L \subseteq \{  0,1\}^*$ for which there exists a NTM $M$ and $c \geq 0$ such that $t_M=\mathcal{O}(n^c)$ and that for all $x \in \{ 0,1 \}^*$:

$Pr[M(x) \in \{0,1\}] = 1$,
if $x \in L$, then $Pr[M(x) = 1] \geq 3/4$,
if $x \notin L$, then $Pr[M(x) = 1] \leq 1/4$.

We define the class of languages Zero-error Probabilistic Polynomial-time (ZPP) as all $L \subseteq \{  0,1\}^*$ for which there exists a NTM $M$ and $c \geq 0$ such that $t_M=\mathcal{O}(n^c)$ and that for all $x \in \{ 0,1 \}^*$:

$Pr[M(x) \in \{0,1,\text{?}\}] = 1$ and $Pr[M(x) = \text{?}] \leq 1/2$,
if $x \in L$, then $Pr[M(x) = 0] = 0$,
if $x \notin L$, then $Pr[M(x) = 1] = 0$.

This statement is to my knowledge unknown. If this is an exercise, then it is likely an error: did they mean $RP$ instead of $ZPP$?

Since $k$-coloring is NP-complete, what you are asked to show is:

  If $NP \subseteq BPP$, then $NP = ZPP$.

First, let's review what is known: the basic inclusions are the following:
\begin{align*}
P \subseteq ZPP \subseteq RP &\subseteq NP \\
P \subseteq ZPP \subseteq coRP &\subseteq coNP \\
                          RP &\subseteq BPP \\
                          coRP &\subseteq BPP.
\end{align*}

That is, $P$ is contained in $ZPP = RP \cap coRP$, which is contained in $BPP$. Moreover, $RP$ is contained in $NP$ and $coRP$ is contained in $coNP$.
But we don't know how $NP$ and $coNP$ relate to $BPP$ (it is conjectured that $P = ZPP = BPP$, which implies that $NP$ and $coNP$ contain $BPP$).

Now, what happens if (as in your exercise) $NP \subseteq BPP$? It follows (and is a common exercise to show) that
$$
NP = RP.
$$

(see e.g. here).
That means that
$$
coRP = coNP \\
ZPP = NP \cap coNP \\
$$
So basically in this case, we have $P$, which contains $NP$ and $coNP$, and those are both contained in $BPP$ (which also equals the polynomial hierarchy $PH$).

But there is no reason to believe that this implies that $NP = coNP$, which is what you would need to then show that your $NP$-complete language, $k$-col, is in $ZPP = NP \cap coNP$. In particular, we can imagine that $BPP$ is equal to the second level of the polynomial hierarchy (you don't need to be familiar with this, but it's just some level that contains both $NP$ and $coNP$). That would imply that $NP$ is contained in $BPP$, but it doesn't mean that $NP$ and $coNP$ are equal.

TL;DR The statement you are trying to show appears to be unknown.


How can P =? NP enhance integer factorization If ${\sf P}$ does in fact equal ${\sf NP}$, how would this enhance our algorithms to factor integers faster. In other words, what kind of insight would this fact give us in understanding integer factorization better?

If $P=NP$, and we have an algorithm that can solve the k-SAT problem in polynomial time, then integer factorization can simply be reduced to k-SAT by describing factoring as a problem in k-SAT.

Essentially it works as follows: You make a bunch of variables each representing the bits of $p$, and $q$, and $n$. Then you formulate the k-SAT problem as $p*q=n$. Since $n$ is known, you can set those values. Then a satisfying assignment will describe a valid $p$ and $q$. To describe the multiplication in k-SAT, you can use any of the known multiplication algorithms and describe it's logical circuit in k-SAT. For more info on reducing factoring to k-SAT, see here.

As for understanding factoring better, that would probably require more research and analyzing the magic algorithm (that can solve NP-complete problems in deterministic polynomial time), and perhaps specializing it to the integer-factoring formulation of k-SAT problem (which obviously has a very specific structure, depending on the multiplication algorithm used).


Interesting logic problems I've just began a course on logic and learned the following :

De Morgan's laws

Normal forms

How to represent a logical formula (using or, and, not operators) using binary trees

How to get the conjunctive normal form  of a formula

It's obviously not much, but the subject interested me a lot and it was enough to study the 2-SAT and the 3-SAT problems. These two problems were very interesting to study.
I am wondering if there are other classical/interesting algorithms problem in logic (just as 2-SAT, 3-SAT) that can be studied with the little I know about logic?

Rather than going to talk about algorithms and more about SAT, this answer tries to show that there is more than just one kind of logic and that there are also different kinds of approaches.

I won't go into detail much but rather provide a list with some topics and keywords that should form a good basis to do some research:

Higher order logic

There are many ways of extending the propositional logic as you know it, for example (first order logic) with the quantifiers $\forall$ and $\exists$ quantifiers.

Keywords: First/second order logic (with equality), free/bound variables, Skolem normal form

Type theory

This is basically just another higher order logic, but it's a very rich topic and in my opinion deserves its own category since it plays a special role in CS.

Keywords: $\Pi$-/$\Sigma$-types, subtypes, quotient types, Curry-Howard correspondence, (un)typed $\lambda$-calculus, System F, Martin-Löf type theory, $\lambda$-cube

Proof systems

These can vary from classical logic as you know, but can be more abstract working with other syntactical objects than Boolean values or predicates. Generally they define some set $\mathcal{X}$ of objects (formulas/syntax), a truth-assigning function $t: \mathcal{X} \to \{\texttt{false},\texttt{true}\}$ (defines semantics), some notion of proofs and a way to (efficiently) check whether a proof is valid.

Keywords: Completeness & soundness, Gentzen/Hilbert style proofs, resolution calculus, Sequent calculus, Intuitionistic logic, Formal verification, temporal logic etc.

If this was not specific enough, here is one thing I found fascinating when I first learned about logic:

$$
\lnot \exists x . \forall y . \bigl ( F(x,y) \longleftrightarrow \lnot F(y,y) \bigr )
$$

The above formula is a tautology (ie. always true) for any domain $\mathcal{U}$ and predicate $F$. Now usually this is not very interesting, but

define $\mathcal{U}$ as the set of all sets, $F(x,y) = y \in x$ and we get Russell's paradox, or
define $\mathcal{U}$ some fixed enumeration of $\{0,1\}^\infty$, $F(x,y) = \text{$x$th bit of $y$}$ (now interpreting $\longleftrightarrow$ as equality on $\{0,1\}$) and we get Cantor's diagonalisation argument

which I find quite interesting.


$k$ vertex-disjoint paths cover in Directed Acyclic Graph The problem is that: in a directed acyclic graph $G$, I want to know the maximum vertices that can be covered by $k$ vertex-disjoint paths.

Obviously, the value of $k$ is smaller than the minimum path coverage of $G$. Are there any approximation algorithms that can solve this problem?

TL;DR- The problem can be solve optimally using min-cost flow algorithms, such as the Successive Shortest Path (SSP) algorithm. The run time of the algorithm is $O(k\cdot (|E|+|V|\log |V|))$, which is polynomial by the size of the graph (note that $k \in O(|V|)$).

First, note that the problem can be converted into finding $k$ edge-disjointed paths problem, covering the maximum number of vertices. We simply split every vertex $v$ into $v^{in}$ and $v^{out}$ such that: 1) If $(u,v)\in E$ was in the original graph $G=(V,E)$, than $(u^{out},v^{in})\in E'$ is in the transformed graph $G'=(V',E')$. 2) There is an edge  $(v^{in},v^{out})\in E'$ for every vertex $v \in V$.  A set of $k$ edge-disjointed paths, covering the maximum number of vertices in $G'$ is equivalent to a set of $k$ vertex-disjointed paths, covering the maximum number of vertices in $G$.

Second, we add a source $s$ and a sink $t$ to $G'$. Then, we connect $s$ to all vertices with zero indegree ($d^{in}(v^{in})=0$), and connect all vertices with zero outdegree ($d^{out}(v^{out})=0$) to $t$. We associate every edge $e$ in $G'$ to have capacity $c(e)=1$, and the cost of every edge $e=(v^{in},v^{out})$ is equal to $w(e)=-1$, and for every other edge the cost is $w(e)=0$. We set the required flow between source $s$ and sink $t$  to be equal to $k$.  The corresponding min cost flow is simply a union of $k$ edge-disjointed paths in $G'$, which cover the maximum number of vertices. Thus, deriving the min cost flow will imply  the corresponding $k$ vertex-disjointed paths in $G$, which cover the maximum number of vertices, as required.

The graph $G'$ is acyclic, even after adding $s$ and $t$. Thus,  we can use the SSP algorithm for acyclic graphs with negative weights (more information can be in [1]). The run time of the algorithm will be $O(k\cdot (|E|+|V|\log |V|))$.

[1]-https://www.cs.tau.ac.il/~yuvalroc/YuvalRochmanThesis.pdf, page 70.


Why do we need two variables for implementing kleene star operation on a language using context free grammars? I have a Context-Free Grammar (CFG) G which has a S for generating a language L. Now to produce a grammar for L*, another variable T (which is not present in the variable set of G) is taken and the grammar is produced in the following way:
                                 G' = (V, A, T, P)

where,
  G'.V = G.V U {T} (V is the variable set)
  G'.A = G.A       (A is the alphabet here, I was't able to insert the symbol of capital sigma here)
  G'.T              is the starting variable
  G'.P = G.P U { T -> ST | NULL }   (P is a finite relation from V to (A U V)* )

My question is that why can't we use S-> SS | NULL instead of introducing T?
P.S. : This is my first question so apologies for incorrect formatting. Also I am new to Theory of Computation so a basic and simple explanation will help me more. Thank you.

In the general case, your grammar generates more words than those in $L^*$. Consider this grammar:
$$
\begin{array}{l}
    S \to A
\\
    A \to (S)\ |\ a
\end{array}
$$
The above grammar generates $L = \{ a, (a), ((a)), \ldots \}$.
Using Kleene's star, we get $L^* = \{a,aa,a(a), ((a))(a), \ldots \}$. Note that $(aa)\notin L^*$.
However, if we add your proposed productions, we get
$$
\begin{array}{l}
    S \to A\ |\ SS\ |\ \epsilon
\\
    A \to (S)\ |\ a
\end{array}
$$
whose language is $L' = \{a,(aa),((a)a)(a), \ldots \}$, and this is a strict superset of $L^*$.
Your construction looks correct in the cases where $S$ never occurs in the right-hand side of a production in the original grammar.


Locate all locations in a sorted array where arr[i]<arr[i+1] Suppose you are given an array of $n$ integers with duplicates in non-decreasing order. The goal is to find the locations where a value is different from its neighbor.
For example, given the array $arr={3,3,5,5,5,200,200,200,200,209}$, the output would be: ${2,5,9}$.
Obviously, this can be done in linear time. I am trying to improve upon this using a binary search.
Let $k$ be the number of output locations. In $O(k \log n)$ time we can get our answer. To find first location, check locations $2,4,8,$etc. Suppose you find that $arr[1]<arr[2^{j}$], recursively search the interval from $2^{j-1}$ to $2^j$-1.

My QUESTION: In the worst case, $k=O(n)$. I do NOT want to ever pay
$O(n \log n)$ since the naive algorithm is $O(n)$. However, I do not pay $O(n \log n)$ for $k=O(n)$ since the binary searches terminate in $O(1)$ time.
How do I prove that the algorithm is worst case $O(k \log n)$ when $k << n$ and never worse than $O(n)$?

Here is a fairly simple fix. Anytime you "overshoot" in your search (I.e. $A[i]=A[i+2^j]$ but $A[i] \neq A[i+2^{j+1}]$ when you backtrack to find the correct index, also keep track of elements in that range that satisfy the inequality (may as well if your scanning over them anyway). You can pick back up at $A[i+2^{j+1}]$. This way, your running time is $O(n)$ worst case.


LRU vs FIFO page replacement I am wondering if there is an instance where FIFO results in less page faults than LRU. For example:

2,6,5,7...

In this string, if I have to complete it by giving 3 additional terms, can I prove FIFO shows less page faults

I have proved how LRU can show less Page faults. But I cannot think of the initial problem statement solution. Any hints would really be great!

For anyone visiting this thread in the future, FIFO can have less page faults in some scenarios.

In this one ( <2, 6, 5, 7, ..., ..., ...> ), it can be completed with 2, 8, 6.

The access of 2 means that the least recently used page is 6, but the first page in is still 2.

The access of 8 replaces 2 in FIFO, but 6 in LRU.

The access of 6, therefore, is a hit with FIFO, but a miss with LRU.


Is the following language regular; context-free but not regular; or not context-free? Let $\Sigma=\{0, 1, \#\}$.
Is the following language regular; context-free but not regular; or not context-free?
Justify your answer
$$L=\{x\#y :\ x, y \in\{0, 1\}^∗\text{ and }\operatorname{bin}(x) + 1 = \operatorname{bin}(\operatorname{rev}(y))\}$$

Denote your language by $L$. Notice that
$$ L \cap 1^*\#0^*1 = \{ 1^n \# 0^n 1 : n \geq 0 \}, $$
which should suffice for showing that $L$ isn't regular.
On the other hand,
$$
L = \{ 0^a1^n \# 0^n 10^b : n,a,b \geq 0 \} \cup
\{ 0^ax01^n \# 0^n1x^R0^b : n,a,b \geq 0, x \in \{0,1\}^* \},
$$
which should suffice for showing that $L$ is context-free.


The total time require for a pipeline to execute The book says that a total time required for a pipeline with k stages to execute n instructions is as follows.

$T  _{k,n} =[pqnk+(1-pq)(k+n-1)] \tau$

p is the probability of encountering a branch instruction.

q is the probability that execution of a branch instruction I causes a jump to a nonconsecutive address.

(Each jump requires the pipeline to be cleared)

However, I can not understand why this makes sense. The formula indicates that

  "If there is a branch instruction and is taken, the number of stages is nk. And in the remaining cases, it is (1-pq)(k+n-1)

I can understand the second case, but why is the number of stages nk in the first case? I think that the result of nk stages never occurs unless every instruction is a branch instruction so that the pipeline is cleared every time each instruction is executed. Instructions after a branch instruction which is taken can be executed in the pipeline, so it must be less than nk.
What do I miss?

The exact time could be obtained as $\tau\sum p_i\,c_i$ where $p_i$ is the probability of taking $c_i$ cycles. Let's admit that by virtue of linearity, it ends up to be equivalent to $\tau\sum p_i\,C_i$ with two terms, $p_0=pq$,  thus $p_1=(1-pq)$. The two terms $C_0$ and $C_1$ must make the formula correct for the extreme cases $pq=1$ and $pq=0$.

The $C_0=nk$ term (the question's first case) is the number of cycles it would take to execute the $n$ instructions with each requiring $k$ cycles (because each jumps to a non-consecutive location and requires refilling the $k$ stages).

The $C_1=k+n−1$ term is the number of cycles it would take for linear code (either because there is no branch instruction, or none jumps to a non-consecutive address). The $n$ term is such that each additional instruction adds one cycle, and the other terms are such that for $n=1$, the outcome is the $k$ cycles necessary to fill the $k$ stages of pipeline.


Retrieve shortest path between two nodes using Bellman-Ford-Moore algorithm sequentially This is my first question here and I hope you can help mt clarifying a doubt.
Basically, I'm studying shortest path algorithms, for instance Dijkstra, Bellman-Ford-Moore, and I came up with a doubt.
From what I understood, given a node of a graph, these algorithms calculate all the shortest paths to the other nodes. So, if I block the execution when a specific condition is met, I can get just the shortest path between two nodes.
I don't have problems with Dijkstra but I can't prove this assumption with Bellman-Ford-Moore algorithm. Consider this example:
G = (V,E) directed graph where V = {1,2,3,4,5,6}, E = {(1,3),(1,2),(3,2),(3,4),(2,5),(5,4),(4,6),(5,6)} and each arch has the following costs, respectively: 2,1,3,3,1,2,2,5.

The shortest path between node 1 and node 4 is: 1 -> 2 -> 5 -> 4 whose cost is 4.
If I try to execute BFM on this graph, assuming nodes are added in the queue with this order: 1,3,2,4,5; the result is not what I'm expecting because the algorithm terminates returning the path 1 -> 3 -> 4, whose cost is 5.

This is the pseudocode I'm using:

bfm(GRAPH G, NODE r, NODE s, integer[] T)
   integer[] d <- new integer[1...G.n]
   boolean[] b <- new integer[1...G.n]

   foreach u in G.V() - {r} do
      T[u] <- nil
      d[u] <- inf
      b[u] <- false

   T[r] <- nil
   d[r] <- 0
   b[r] <- true

   QUEUE S <- new Queue()
   Q.enqueue(r)

   while not S.isEmpty() do
      NODE u <- S.dequeue()
      b[u] <- false
      if u = s then return

      foreach v in G.adj(u) do
         if d[u] + w(u,v) < d[v] then
            if not b[v] then
               S.enqueue(v)
               b[v] <- true

            T[v] <- u
            d[v] <- d[u] + w(u,v)

d is a vector to track distances, b is a vector to track which node is currently in the queue, T is a vector of fathers, G.adj(u) returns all nodes adjacent to node u and w(u,v) is the cost function.

Since Dijkstra and BFM algorithms are quite similar, I thought my assumption would be valid for both of them but it seems that I'm wrong. Can you please help me understanding if and how I can use BFM to get the shortest path between two specific nodes?

Thank you so much!

The correctness proof of the Bellman–Ford algorithm relies on the following lemma (compare Wikipedia):

  After $i$ iterations, $d[v]$ is at most the distance of the shortest path of length $i$ from the source vertex to $v$.

Indeed, if we perform all updates at a specific iteration in parallel, then $d[v]$ equals the distance of the shortest path of length $i$. When we perform the updates sequentially we might get lucky, and this depends on the order of vertices in the path.

This shows that in general you cannot stop Bellman–Ford early in the way you envision.


When binary search algorithm will be $O(1)$ I had an exam today, and there was a question that said:

  Based on the definition of binary search algorithm, discuss when the algorithm time will be $O(1)$ and when it will be $O(\log(n))$.

I'm not sure about my answer, but I answered randomly saying that, it can be $O(1)$ when the element I am searching for is at the middle of the array, and it will be $O(\log(n))$ when the element is at the end of the array.

I know my answer might be trivial, but how can I answer a question like this?

Based on the definition of binary search algorithm, discuss when the algorithm time will be $O(1)$ and when it will be $(\log n)$.

This is a nice open-ended question to test how well students understand the referred concepts. Here is how I could show my understanding about the conventional binary search.

First, the algorithm time is always $O(\log n)$ in its usually implementation, i.e, an (indexed) sorted array (SA) or a binary search tree (BST) in the RAM model + comparison model (the computation model that is usually used when we talk about binary search). Even if the algorithm happens to find the wanted element in the very first iteration, i.e., comparing the wanted element against the element in the middle of the SA or the root of the BST, it takes $O(\log n)$ time still. Even in the worst time, it takes $O(\log n)$ time still.

Second, the algorithm time will be $O(1)$ when its runs on some particular subsets of the searching problems in some particular ways as illustrated below.

The number of elements, i.e., the length of the array or the number of elements in BST is bounded by a constant. In this case, even a linear search algorithm will run in $O(1)$ time. Note that the wanted element may or may not be in the given elements.

Note this situation is different from the situation when the number of different values of the element (as used in the comparison) is bounded. We may need $\Theta(\log n)$ steps to find the index of a $2$ in an sorted sequence of $n$ numbers all of which are 1, 2, or 3.
The wanted element is in the middle of the SA, or in the one-quarter or three-quarter position of the SA, and so on but within a bounded times of iterations. The exact indices of these positions depend on the exact implementation of the binary search. An implementation might check the element at index $(n-1)/2$ first in an array with indices $0,1,\cdots, n$ and odd $n$ or check the element at index $(n+1)/2$ first. The former implementation might need $\Theta(\log n)$ to find the element at index $(n+1)/2$.
The wanted element is within a bounded depth away from the root of the BST.
We could construct various special set of searching situations where the time for a particular implementation of the algorithm will be $O(1)$ by reverse engineering. Specifying a constant $c$. Searching an array by binary search algorithm. If it ends with $c$ steps, we include that problem instance. All together we will find a set of problem instances   where the binary search algorithm will run within $c=O(1)$ steps.

Here is a shorter version that could be used as a reference answer to the question for grading. Again, only the conventional binary search algorithms are considered.

  The binary search algorithm always runs in $O(\log n)$ time in the usual computation model.

  If the wanted element is among the elements that could be possibly compared within $c$ comparisons for some constant $c$, then the algorithm time is $O(1)$. It happens when the number of total elements is bounded by a constant, when the wanted element is the element in the middle of a sorted array of odd length and when the depth of the wanted element is less than a constant where a binary search tree is used.


Sources on dictionary learning and related algorithms In the context of signal processing and sparse representation of signals, there is a topic called dictionary learning which is basically about how to's of the selection of basis functions used for sparse representation. I am looking for sources explaining the topic with a section on dictionary learning algorithms and probably a comparison made among them.

The best resource, in my opinion, is eDx - Sparse Representations in Signal and Image Processing: Fundamentals by Michael Elad.


First Order Logic, First Order Logic + Recurrence and SQL we know that SQL standard is equivalent to First Order Logic (FOL).  I've seen at my lecture that graph connectivity cannot be expressed by FOL, so in SQL as well. But we know that we can easily solve that problem in PTIME. And I've seem the following table:

Query Language   Data Comp.   Expression Comp.
FOL              LOGSPACE     PSPACE
FP               PTIME        EXPTIME

I am not sure what is FP. But, I suppose that it is FIXPOINT. I mean, a first order logic with recursion + fixpoint.

I don't understand that table. I understand the Data Comp. But, I cannot what Expression Comp. means and why Expression Comp. for FP requires so much time.

Yes, FP will be first-order fixed-point logic.

Data complexity is the maximum complexity of the problem of evaluating a fixed formula of the logic on a database, as a function of the size of the database.  Expression complexity (also known as formula complexity) is the complexity of evaluating a formula on a fixed database, as a function of the formula size (e.g., its length as a string of characters).  Combined complexity, which isn't mentioned in your table, is the complexity of evaluating a formula on a database as a function of the size of those two things.

The expression complexity of first-order logic is high because, for example, a formula $\forall x_1\dots \forall x_k$ requires time $n^k$ to evaluate on a database of size $n$, so a formula of length $\ell$ can take time $n^\ell$, which is an exponential function of $\ell$ when $n$ is treated as a fixed constant.  However, we can do this in polynomial space, since all we need to do is loop through potential values of variables and that requires storing just one value per variable.


Add a road to a network (Graph problem with Dijkstra) Recently i have found a problem stating:
There is a network of roads G=(V,E)(it is not directed) connecting a set of cities V. The length of each road e ∈ E is le. There is a proposal to add one new road to this network, and there is a list E′ of pairs of cities between which the new road can be built. Each such potential road e′∈ E has an associated length. As a designer for the public works department you are asked to determine the road e′ ∈ E whose addition to the existing network G would result in the maximum decrease in the driving distance between two fixed cities s and t in the network. Give an efficient algorithm for solving this problem.

The basic solution was to apply to 2 times Dijkstra (from s to city x and from t to a city y) and then try all the edges from E' which would result into

2*(Dijkstra) + (|E'|) = ((|V|+|E|)⋅ log |V|+|E’|)

But then on the web I found an altrenative solution:

  If you run Dijkstra for every edge in E’, the running time is (|E|⋅|E’|⋅ log |E|)

I do not understand this alternative. Could anybody explain this strategy to me?
Thanks in advance!

Who knows. You'd have to ask them; that doesn't provide enough details to narrow it down.

If I had to guess, I imagine that perhaps they had in mind that they would do Dijkstra's algorithm once to measure the distance from $s$ to each vertex; then for each candidate edge $(u,v) \in E'$, they would use Dijkstra's algorithm to find the distance from $u$ to $t$ assuming $(u,v)$ has been added to the graph; and use this to find the best edge to add.

In any case, their alternative solution is considerably slower, so it's a poor choice and should not be used.  It's far faster to use the first solution you listed.


Simplification of a multi-index Boolean expression towards computation in fewer steps Let $x_{ij} \in \{0,1\}$, $1 \leq i \leq M$ (typically, $M = 2000$), $1 \leq j \leq  N$ (typically, $N = 10$), be Boolean variables. If possible at all, I would like to simplify the following expression
$$
\bigvee_{i_1,\dots,i_N} \left(\bigwedge_{k=1}^N x_{i_k k} \right),
$$
where the join operation is taken over all indices $(i_1,\dots,i_N) \in \{1,\dots,M \}^N$, so that it can be computed faster instead of looping through all multi-indices.

Apologies if this is a well-known problem (with or without solution). This is very much outside of my field of expertise, so I am hoping someone around here could give some feedback on it. Feel free to edit the tags as you see more appropriate.

Thanks!

It is equivalent to

$$\bigwedge_{k=1}^{N} \bigvee_{i_k=1}^{M} x_{i_k k}.$$

This is a much simpler expression: $NM$ terms instead of $M^N$ terms, if you expand everything out.


Produce decision version of the problem An optimisation problem requires minimising some function $f(x)$, where $x$ is a
vector of integers. What is the corresponding decision version of the problem?

"Given $f(x)$, what is $\min(f(x))$?" becomes "Given $f(x)$, and $k$, decide if there is an $x$ such that $f(x)< k$?"


How logic programming (especially ASP) is related to the reasoning in (first-order) logic? How logic programming (https://en.wikipedia.org/wiki/Logic_programming, especially answer set programming) is related to the reasoning in the (first-order) logic? Maybe logic programming can be expressed using lambda calculus and then this connection between logic programming and logic and be exspressed as type of Curry-Howard isomorphism?

But maybe this connection can be established without this bypass?

Maybe such connection can not be established, as logical reasoning is monotonic (it just discovers consquences that are implicit in the initial premises), but logic programming is non-monotonic (it asserts new facts and knowledge). If so, then logic programming is generalization of logical reasoning and under what (syntactic) conditions logic program becomes set of logical formulas/logical theory?

Logic programming is proof search for some logic. Traditionally, this is the Horn clause fragment of first-order logic. Languages like lambdaProlog extend this to (intuitionistic) hereditary Harrop formulas. There are also languages like Lolli, LolliMon, and Olli that work in fragments of linear logic (ordered linear logic in the last case). The concepts here are the notion of uniform proofs, focused proofs, and polarization, which lead to the concept of an abstract logic programming language.

The other way of thinking about logic programming that is more common via the Datalog path is as finite model theory. The idea there is simple: just calculate what the model would be, i.e. literally the sets of tuples for each relation. For Datalog (with or without stratified negation), this is relatively simple; there is a single minimal model.

When non-stratified negation is allowed, the situation gets quite a bit more complex. There is no longer a unique minimal model. There are two ways of dealing with this situation. One is to move to 3-valued models and for things like $q\leftarrow\neg q$ we can assign the truth-value $U$ to $q$ representing an "undefined" third truth-value. This leads to well-founded semantics. Given this 3-valued model, we can create a set of 2-valued models by considering all ways of assigning $T$ or $F$ to the "undefined" tuples excluding models with unfounded propositions which gives stable model semantics. The recent paper Founded Semantics and Constraint Semantics of Logic Rules gives a nice way of generalizing, organizing, and understanding these various semantics and the details of what "unfounded" means. Answer set programming is often conceptualized as stable model semantics. The XSB implementation of tabled logic programming is capable of handling non-stratified negation and producing a well-founded semantics which can then be fed into an answer set programming system leading to a significant performance gain over directly applying answer set programming.

Returning to proof search, what's happening in answer set programming can be partially thought of with respect to disjunctive logic programming. Typical logic programming languages do not allow disjunction in the head. That is, you can't prove $p\lor q$ except by proving $p$ or $q$. The issue is clear. Given the (disjunctive) logic program $p\lor q.$, should $?{-}\,p$ succeed or not? More pointedly, what should be produced by $?{-}\,t(X)$ where $t(1)\leftarrow p\land\neg q. t(2)\leftarrow q\land\neg p.$ is appended to the earlier program? Finally, append $r\leftarrow t(1)\land t(2).$ and ask if $?{-}\,r$ holds. These examples illustrate that while we can find a model where $t(1)$ holds and a model where $t(2)$ holds, there's no model where both $t(1)$ and $t(2)$ hold. This can be related to the previous paragraph by noting the classical equivalence $p\lor q \equiv p \leftarrow \neg q$. In particular, the program $p\leftarrow\neg q. q\leftarrow\neg p.$ leads to both $p$ and $q$ being "undefined" in well-founded semantics and has two stable models, though this omits the model where both $p$ and $q$ hold. (One way to see why this happens is that there are implicitly completion rules that make the program look like $(p\leftrightarrow\neg q)\land(q\leftrightarrow\neg p)$.) In terms of proof search, there's simply no proof of $p$ from $p\lor q$. Via the soundness and completeness theorems of (classical) first-order logic, having a proof of some formula is equivalent to having it hold in all models. Answer set programming just enumerates the (stable) models. To see if answer set programming has proven something, you need to check to see if it's true in all the models the answer set program produces. Normal logic programming implicitly constructs a proof, so it can only talk about what holds in all models.

Finally, pure logic programming meaning logic programming omitting extra-logical features like cut (!), assert, retract, and others, is, as I said at the beginning, purely a matter of proof search. It does not "assert new facts and knowledge". It is the process of "discover[ing] consquences that are implicit in the initial premises". Most logic programming languages are restricted to a fragment of logic where this process is particularly amenable to computation. Indeed, they are often restricted to satisfy a much more stringent notion of "monotonicity" as is especially evident in Datalog. Datalog is usually implemented via forward chaining, which means starting from what is known and producing all immediate consequences. This is iterated until a fixed point is found. Monotonicity in this context means that once something is derived, you can never learn something later that will change your mind. Non-stratified uses of negation lead to non-monotonicity. For example, for the program $p\leftarrow\neg q. q\leftarrow\neg p.$, initially neither $p$ nor $q$ is true thus we may feel justified in deriving either or both of $p$ and $q$. If we pick both, then we scuttle our justification for picking either. Whichever we pick, we end up with a statement that isn't true in all models. Of course, in general there can be an arbitrary long chain of logic before we realize we're in this situation at which point we'll have already derived a bunch of things we should not have.


Is checking if regular languages are equivalent decidable? Is this problem algorithmically decidable?
L1 and L2 are both regular languages with alphabet $\Sigma$. Does L1 = L2?
I think that it is decidable because you can write regular expressions for each language and see if they are the same. But I'm not sure how to prove it since I see that you prove something is decidable by showing a Turing Machine

It is decidable, all you have to do is use the closure properties of finite automata + emptiness checking; let me know if you want me details.
I’m not sure exactly how you’d check the equivalence of two regular expressions, other than by converting to automata, so unless this is a practical issue you’re trying to resolve and you receive input in terms of regular expressions, I’d think about it in terms of automata.
As for creating the Turing machine that actually does this, it’s probably not strictly necessary to write out the formal description, as long as you can argue why it’s possible to do so.


Regular expression - every b preceded and followed by an even number of a's I'm trying to write a regular expression over the alphabet $\{a, b\}$ for the language in which every $b$ is preceded and followed by an even number of $a$'s.

I think the regular expression should include something like $((aa)^*b(aa)^*)^*$ but I don't know how to extend it in order to get to the correct form. Can anyone help me by providing a step-by-step solution?

The answer you already have covers almost all the cases: any time there's a $b$, there need to be an even number of $a$'s, so that covers all words containing a $b$.

However, there's an edge case where there are no $b$'s in your word, so you need to union your language with the case where the word has no $b$'s.

$((aa)^*b(aa)^*)^* \cup a^*$ should fit your final answer.


Implications of Halting Problem being unsolvable? I came across a confusing situation when reducing the Halting Problem (HP) to the Blank Tape Accepting Problem (BP).

We know that since HP can be reduced to BP, BP is decidable $\implies$ HP is solvable. By contrapositive, we get that if HP is undecidable, then BP is undecidable as well. But now this creates an issue.

BP is just a special case of HP where the input to HP is a Turing Machine and a blank tape. Also, HP is a harder version of BP since we can get all possible tapes as input. So, just because a harder problem is unsolvable, how can we conclude that the more general form is also unsolvable.

It might be possible that we have some TM that can solve BP but cannot solve HP.

I know that both BP and HP are undecidable, but my main question is that how can we conclude via reduction that BP $\implies$ HP?

I have a valid reduction below, but it is all very formal, and it's not the intuition I have for this kind of problem. When I consider, is this problem decidable/NP-Complete/etc, I frame it as a challenge: somebody says I bet BP is decidable!, and I reply Oh yeah?! Well, if that were true, then I could solve HP!. And then I show how I would do that: I suppose that BP is decidable, (i.e. I accept the challenge) and then I use that to solve HP. Granted, acknowledging this takes away some of your street cred, but it does work for me.

Here's a cheat sheet:

Show a reduction $f$ so that $HP \leq_f BP$: Hey I bet HP is decidable! Reply: Oh yeah?! Then I can solve BP like $f$
Show that Indset is NP-Complete by reduction from 3Sat, i.e. $3Sat \leq_f IndSet$: Hey I bet IndSet is easy! Reply: Oh yeah?! Well if it were easy, then I could solve 3SAT like so! I would take my arbitrary 3SAT instance $\phi$ and transform with $f$ to an IndSet instance $f(\phi)$ and then we'll let you solve $f(\phi)$ with your supposedly fast IndSet algorithm!

I hope that if these comments do not make you laugh, at least they help you internalize the notion of what a reduction is supposed to do, and how you are supposed to make one.

Now for a valid reduction. You have reduced HP to BP via a reduction $f$ (like the one I gave for your prevous question), so if somebody asked, does $M$ halt on $w$?, then you can reduce the HP instance $\langle M, w\rangle$ to the BP instance $A=f(M,w)$ (e.g. $A$ is a TM that simulates $M$ on $w$ given the blank tape), and ask your BP machine whether $A$ halts on the blank tape. So if BP were decidable, we would have an algorithm for HP, namely the one that I just described. But we don't. So BP is not decidable.


Complexity analysis of recurrence with multiple variables To give background, there's two ways to multiply two complex numbers:

Method A: requires 3 multiplications and 5 additions
Method B: requires 4 multiplications and 2 additions

And it's given that multiplying two $m$ bit numbers is $O(m^2)$ and that adding two $m$ bit numbers is $O(m)$.

Now given a list of complex numbers, we can multiply them together using a divide and conquer algorithm that looks like this:

function divideAndConquer(list, i, j) {
  if (i === j) {
    return list[i]
  }
  const m = i + (j - i) / 2
  return methodA(divideAndConquer(list, i, m), divideAndConquer(list, m + 1, j))
}

My goal is to find the complexity of the divide and conquer algorithm using methods A and B respectively. Using method A as an example, we could say that

List of size 1: $T(1) = 1$
List of size 2: $T(2) = 3am^2 + 5bm$ where $a > 0, b > 0$

because with one number you don't do anything, and with two numbers you do 3 multiplications and 5 additions.

However, now my issue is that I'm not quite sure that for $T(n)$ what I have is right because while it's quite obvious that it'll be something like

$$T(n) = T\left(\frac{n}{2}\right) + f(n)$$

I'm not really sure how to find out what $f(n)$ is because at each level $n$, $m$ will grow as a result of multiplication, meaning that $f(n) = 3am^2 + 5bm$ isn't accurate.

Essentially, the thing that confuses me is that there are two variables in play. The size of the list, $n$, and the size of the numbers in bits, $m$, that you're multiplying. So the heart of my question is really how do I solve a recurrence that has multiple variables? In this case $n$, and $m$.

Since you know only $O$-bounds for the basic operations, you can not derive more precise bounds for $f$, nor $T$. Furthermore, if you had exact cost functions for the basic operations, solving divide-and-conquer recurrences exactly is very hard.

So, what the exercise authors probably want you to do is to say,

$f \in \Theta(m^2)$ (assuming that the bound for multiplication is tight, which they probably wanted to imply but didn't express properly) in either case, and
solve the schematic recurrence using the Master theorem (e.g. by substituting $f(m)$ with $m^2$).

You'll get out the correct $\Theta$ bound that way.


LTL Logic Finally, Globally and Until to irreflexive Version my professor said that we can transform the reflexive Finally, Globally and Until into irreflexive Finally, Globally, Until.

Can someone explain me this?

For irreflexive Finally we have $w \models F^+ \varphi$ if $\exists i >= 1: w^{(i)} \models \varphi$
For irreflexive Globally we have $w \models G^+ \varphi$ if $\forall i >= 1: w^{(i)} \models \varphi$
For irreflexive Finally we have $w \models \varphi_1 U^+ \varphi_2$ if $\exists i >= 1: w^{(i)} \models \varphi_2$ and $\forall j, 1 \leq j < i w^{(i)} \models \varphi_1$

Sorry, I misread your question at first as wanting to express the irreflexive variant using the reflexive variant (which could be done with the next operator). You don't actually need the next for the other direction.

I'm making the following assumption: By $w^{(i)}$ you mean the suffix of $w$ starting at the $i$ symbol, so for $w = w_0 w_1 w_2 \dots$, you have $w^{(i)} = w_i w_{i+1} w_{i+2} ...$

Then for all $w \in L$, you have:

$w \models F\varphi \Leftrightarrow w \models \varphi \lor F^+ \varphi$.
$w \models G \varphi \Leftrightarrow w \models \varphi \land G^+ \varphi$.
$w \models \varphi_1 U \varphi_2 \Leftrightarrow w \models \varphi_2 \lor (\varphi_1 \land (\varphi_1 U^+ \varphi_2))$.

If you want to show this formally, it follows directly from the definitions:

For 1. you have:

$\begin{align*}w \models F \varphi &\Leftrightarrow \exists i \geq 0: w^{(i)} \models \varphi \\ &\Leftrightarrow \exists i > 0: w^{(i)} \models \varphi \quad \text{ or } \quad  w^{(0)} \models \varphi \\ &\Leftrightarrow  w \models F^+\varphi \text{ or } w \models \varphi \\ &\Leftrightarrow w \models \varphi \lor F^+\varphi \end{align*}$

The argument for 2. is symmetric to 1.

For 3. you have (pay attention to $\leq$ vs $<$):

$\begin{align*}w \models \varphi_1 U \varphi_2 \Leftrightarrow & \exists i \geq 0 \forall 0 \leq j < i: w^{(j)} \models \varphi_1, w^{(i)} \models \varphi_2 \\ \Leftrightarrow & \exists i > 0 \forall0 \leq j < i: w^{(j)} \models \varphi_1 , w^{(i)} \models \varphi_2 \quad \text{ or } \quad w^{(0)} \models \varphi_2\\
\Leftrightarrow (& \exists i > 0 \forall0 < j < i: w^{(j)} \models \varphi_1 , w^{(i)} \models \varphi_2 \quad \text{ and } \quad w^{(0)} \models \varphi_1) \quad \text{ or } \quad w^{(0)} \models \varphi_2 \\
\Leftrightarrow (&w \models \varphi_1 U^+ \varphi_2 \quad \text{ and } \quad w \models \varphi_1 )\quad \text{ or } \quad w \models \varphi_2 \\
\Leftrightarrow & w \models \varphi_2 \lor (\varphi_1 \land (\varphi_1 U^+ \varphi_2))\end{align*}$

If you would have wanted to do the other direction, as I thought initially:

$w \models F^+ \varphi \Leftrightarrow w \models XF \varphi$
$w \models G^+ \varphi \Leftrightarrow w \models XG \varphi$
$w \models \varphi_1 U^+ \varphi_2 \Leftrightarrow w \models X(\varphi_1 U \varphi_2)$.

To show this formally, the argument would be similar to before.

When you combine both directions, this transformation is sometimes referred to as "unrolling", i.e. expanding $F \varphi \equiv \varphi \lor X F\varphi \equiv \varphi \lor X \varphi \lor XXF \varphi \equiv ...$ and $G \varphi \equiv \varphi \land XG \varphi \equiv \varphi \land X \varphi \land XXG \varphi \equiv ...$ etc.

Regarding your comment (not 100% sure if you were joking): $\lnot X$ is not $-1$ or "going backwards". You have $w \models \lnot X \varphi \Leftrightarrow w^{(1)} \not \models \varphi$. In other words, if you think in terms of Kripke structures and of $w$ as the vertex-label sequence of a path in this transition system, then $\lnot X \varphi$ means "in the next state, $\varphi$ does not hold".


Why integer division is of equal complexity as multiplication I am trying to understand the fact that integer division is no more difficult than integer multiplication. I found some references - here and this lecture note. Wikipedia says if there is a way to multiply integers in time M(n), then we can divide them in CM(n). When I think of division a/b as finding
integers d and r such that a = bd + r, then this above fact somehow aligns with my intuition. But I could not find any way to mathematically prove this. Although the lecture note has proof, but I am not able to understand. Can anybody please give me a simple mathematical proof or any idea how to do it?

The wikipedia page suggests using Newton-Raphson Division to get  $O(M(n))$.

The way Newton-Raphson Division works is by finding the solution $x$ of $\frac{1}{x}-b=0$ (so that $x=1/b$), and then returning $ax$.

A Newton-Raphson iteration in general is

$$ x_{i+1} = x_i - \frac{f(x_i)}{f'(x_i)}. $$

In this case $f(x)=\frac{1}{x}-b$ and $f'(x)=\frac{-1}{x^2}$, so the iteration works out to

$$ x_{i+1} = x_i(2-bx_i), $$
which takes 2 multiplications per iteration.

Given a good enough starting guess, $x_0$, Newton-Raphson is guaranteed to double the number of accurate bits per iteration, so needs to be run for $O(\log n)$ iterations for $n$ bits of accuracy.

All of the above is for real $x$.  To make it work for integers the trick is to actually calculate $x=\frac{2^n}{b}$ instead of $x=\frac{1}{b}$, which (with a little bit of "normalization") lets you do all the arithmetic with integer multiplies, subtracts, and shifts.

And now how you do it in the same time as multiplication:

Say you want a 1024 bit result, and you have 16 correct bits.

You do one iteration step with 32 bit precision, getting a 32 bit result. Then you do an iteration with 64 bit precision, then 128 bits, then 256 bits, then 512, then 1024.

So the cost isn’t M(n) every time, it’s M(n/64), M(n/32), ..., M(n/2), M(n). Adding up to 2M(n).


Event Prediction through Machine Learning I have a large data set consisting of ca. 40 categorical data items and a few interval data items (real numbers, less than 5 such items). Most categories should have a lot of values that repeat themselves over and over, and very few that appear very rarely. Some categories are also overcategories of others (like country and city). The outcome of each data is either 1 if the event occurred, or 0 if it did not occur.

The idea is to calibrate a machine learning model or a statistical model that can predict for every given data row the probability that the outcome is 1. The data set I will use will have at least 1 million rows.

Which machine learning approaches and statistical models will perform well on such a task? My initial thoughts are logarithmic regression and support vector machines (with extensions like random forest).

How do I deal with the interval data items? The easiest approach is obviously to convert different ranges into categories, which I think will not be a problem.

What libraries and tools can I use when my data set has a size of 10 GB? I am interested in tools/libraries that include machine learning algorithms but also statistical tools to help me find attributes with significant influence on the outcome. I can code in Java and C++ at the moment. I looked into Root, a data analysis tool from CERN for large data sets, and its machine learning module TMVA, but it can only handle real numbers and integers as input as far as I know.

As usual in these kinds of situations, the best way to find out which machine learning approaches will perform best is to try them out and see which ones work best.  You can evaluate them using cross-validation.

It's unlikely that anyone here will be able to guess what will work best without knowing your data set.  So I recommend that you get to work trying some likely candidates.

The Orange software tool is very convenient for trying multiple different machine learning algorithms on the same data set.


Why does restricting size of input for NP complete problem imply a runtime of O(1)? I've seen this statement mentioned a few times here on cs.stackexchange and have not been able to follow the logic.  The statement is 'If you restrict the input size of the problem then solving that problem (even SAT) can be done in O(1)'.

So say I restrict the size of SAT to N = 1000, now that means that solving SAT for any N <= 1000 can be done in O(1)?  That doesn't quite follow.

Can someone shed some light on this concept?

If the input size is limited, then you can calculate the solutions to all problems. This will take a very, very, very long time. But once these solutions have been calculated, you can just lookup the solution of any problem in your list of solutions.

Even worse: Look at the definition of Big-O. The claim is that there is a constant $c > 0$, and an integer $N_0 > 0$ such that for every problem with a size $N > N_0$, the problem can be solved in less than $c * 1$ steps. If you restrict SAT to $N ≤ 1000$, then this is trivially true with $c = 1$ and $N_0 = 1001$. There are no problems with a size > 1000, therefore all the (nonexisting) problems with a size ≥ 1001 can be solved in one step.


Solve Travelling Salesman once you know the distance of the shortest possible route I am trying to solve the TSP (Travelling Salesman Problem), but not in a traditional way. I am following these steps.

  1) First I change the TSP to a true / false problem.

The definition of this problem is now: "Is there a route by all the cities with a total distance less or equals than k?" Let's assume I have an algorithm TSP_tf(k) to solve it.

  2) Then I search the minimum k.

This is, I search "which is the distance of the shortest possible route".

An efficient algorithm to solve it would be with a dichotomic search. I begin with k=1, and I call TSP_tf(k). If it returns false, I multiply k by 2, and keep calling TSP_tf until true is returned. When this happens, search the minimum k that returns true in the interval (k/2 - k], also with a dichotomic search.

I will get then the minimum distance min_k.

  3) Return the shortest route of the TSP knowing its distance is min_k.

And here is where my question comes. How would be an efficient algorithm to solve this? By efficient I mean a good approach :) It is obvious that TSP will remain being NP.

You try to find a tour of length ≤ K. What would likely happen: If K is very large then a tour is easy to find. If K is very small then it is easy to prove that a tour doesn't exist. The closer you move K to the critical point (where a tour of length K exists, but K-1 doesn't exist), the harder it will be to either find a tour or prove it doesn't exist. You don't beat NP-completeness that way.

And actually, since NP-completeness is about decision problems (problems with a yes/no answer), that's what the travelling salesman problem actually is: Deciding whether or not there is a tour of length K or ≤ K.