STCON in L using matrix multipication algorithm? I'm trying to understand why the following is incorrect.

Given a $STCON$ problem, specifically a graph and nodes $(G, s, t)$, we can assume we are given it's adjacency matrix, $A$. By adding self-loop (filling the main diagonal with $1$'s) we can multiple this matrix with itself n times, each time checking if the $s,t$ entry is $1$, and if so returning true.

We know multiplying binary matrices is in $L$ (need to "save" only couple of indices), and by also saving $n$ (number of total matrix multiplications) one can solve $STCON$ also in $L$.

Where am I wrong here?

A machine runs in logarithmic space if the working space it requires (excluding the read-only input and the write-only output) is at most logarithmic in the number of bits required to represent the input.

For matrix multiplication, the input is the two matrices, and the output is their product. The only working space is, as you say, the "loop counters" for stepping through the current row and column to compute the next bit of the output.

For graph connectivity, the input is the adjacency matrix of the graph, along with the two vertices of interest, and the output is the single bit "yes" or "no". Your proposed algorithm requires remembering the matrix of paths you've discovered so far, which has size $n^2$, and that's not logarithmic.


is duality principle in boolean algebra is true for every expression Let say A = 1 and B = 1
and then A+B = 1
now by using duality(replacing or gate by and gate and 1 by 0) we can say that, A.B = 0
but this is not 0, because 1.1 = 1, so please anyone clear my misunderstanding here, Thank in advance

Negation gives you $\overline{A}=0,\overline{B}=0$, so everything is ok in "and".


Help with Time Complexity Suppose we have the function below:

def func(n):
    for i in range(n):
        for j in range(n - i):
            for k in range(n - j):
                if i + j + k == 0:
                    break
            if i + j == 0:
                break
        if i == 0:
            break
    return n + 1

We have three nested for-loops and the total number of elements evaluated appears to be: (n)(n-1)(n-2). However, this cannot be correct, as I know the time complexity of this function is not O(n^3). What is the proper way to evaluate the time complexity of this function?

Your function has constant running time (or linear running time, depending on how range is implemented). I suggest running it step-by-step and seeing what happens.


Literature about a naive approach to graph isomorphism by inspecting polynomials of adjacency matrices I describe an approach to graph isomorphism which probably has false positives, and I am curious whether there is literature indicating that it does not work.

Given two adjacency matrices $G, H$, an admittedly naive method of checking for isomorphism is to check whether for each row $u$ of $G$, there is a row $v$ of $G$ which is a permutation of row $u$, denoted by $G[u] \sim H[v]$. Slightly more strict is the question, is there a "local isomorphism" $\pi$ for which $G[u] \sim H[\pi(u)]$ for all rows. Producing a local isomorphism can be done in polynomial time by building an $n\times n$ matrix $A$ with $A[u,v] = (G[u]\sim H[v])$; then $G$ and $H$ are locally isomorphic iff $A$ has a cycle cover, and every cycle cover is a local isomorphism.

All regular graphs fool this method, obviously, so a slightly less naive approach is to compute powers $G^2, H^2, G^3, H^3,\ldots$ of the matrices and checking them for local isomorphism, exploiting the fact that you have multiple matrices by setting $A[u,v] = 0$ when you find any power such that $G^k[u]\not\sim H^k[v]$, and checking for cycle cover only at the end. An even less naive approach is to find a set of polynomials, indeed a set of arithmetic circuits, and setting $A[u,v]=0$ when we find any polynomial $p$ with $p(G)[u]\not\sim p(H)[v]$.

This looks to me like an incredibly naive approach to graph isomorphism, so I am sure somebody has already investigated it and proved a theorem such as

Thm For infinitely many $n$ there are nonisomorphic $n\times n$ matrices $G, H$ and a permutation $\pi$ such that for every polynomial $p$, $p(G)$ and $p(H)$ are locally isomorphic by that permutation: $p(G)\overset{\pi}{\sim}p(H)$.

Question: Is there such a theorem? I have looked in the literature and cannot find it.

If there is a bound on the degree $k$ that is polynomial in $n$ such that for every two nonisomorphic matrices, local isomorphism is refuted by computing $G^1, H^1, \ldots, G^{poly(n)}, H^{poly(n)}$, or if there is an easily computable family of polynomials $p_1, \ldots ,p_k$, each having polynomially-bounded length but possibly exponential degree, then we have a P algorithm for graph isomorphism. If such polynomials (or arithmetic circuits) are easy to guess, then we have a coRP algorithm. If there always exists a (family of) arithmetic circuits to witness non local isomorphism, then this gives a coNP algorithm.

Note that we can avoid the problem that the entries of high-power matrices grow too large by computing the polynomials over small fields, e.g. by computing them modulo small primes. In a coNP algorithm, the prover can provide these primes.

Yes, there is such a theorem, more or less. It basically states that the k-dimensional Weisfeiler-Lehman procedure subsumes (i.e. dominates) all known combinatorial approaches to graph isomorphism testing. (Your concrete proposal should be subsumed by the 2-dimensional Weisfeiler-Lehman procedure, if I am not mistaken.) For each fixed k, there is a class of counterexamples to the k-dimensional Weisfeiler-Lehman procedure known as the Cai-Fürer-Immmerman construction.

I first learned the basics of the Weisfeiler-Lehman procedure and the Cai-Fürer-Immmerman construction from

  http://users.cecs.anu.edu.au/~pascal/docs/thesis_pascal_schweitzer.pdf

There is much more to learn about the Weisfeiler-Lehman procedure than described there, but at least the treatment of the Cai-Fürer-Immmerman construction is complete and sufficient for your purpose. "The Weisfeiler-Lehman Procedure", by Vikraman Arvind is a recent brief essay meant as an invitation to the topic.

Perhaps the crucial point to take away from my answer is that if you would find a purely combinatorial isomorphism testing method (like the one describe in your question), which is not subsumed (i.e. dominated) by the k-dimensional Weisfeiler-Lehman procedure, then this would be a breakthrough by itself, independent of whether the method would be actually useful.


Understanding the Linear speedup theorem and how strong it is Let $k \in \mathbb{N} $ and define the language $L = \{ n,m | n^k = m \}$

Consider a (deterministic) TM deciding $L$ then it has to compute $k$'th power which will take $f(|n|+|m|) + h(k)$ time in worse case for some polynomials $f,h$. now, by the Linear speedup theorem we can improve this to $\frac{f(|n|+|m|) + h(k)}{h(k)} = O(f(|n|+|m|))$
This means that for whatever $k$ we choose there is a (deterministic) TM deciding it in $O(f(|n|+|m|))$ even for cases $|n+m|<<k$. And this seemingly doesn't make sense, because it leads me to the fact that for every two choises of $k$ there are TM's deciding the corresponding languages in the same running time. What am I missing here?

The linear speedup theorem says that, for any constant $c$, you can decide the language $c$ times faster. It does not say that you can make it faster by some non-constant function.

The speedup theorem works by defining a new Turing machine that writes $c$ characters of the old Turing machine in a single tape cell, and then adjusting the transition function so that it simulates in a single step everything that the original machine did between entering and leaving each $c$-character block.  If $c$ is a constant, it doesn't depend on the input, so you just compute the new machine once and use it on whatever input you want. But if you want $c$ to be some non-constant function, then you have to figure out what the new machine is every time you run it. That takes exponentially long, since there are exponentially many possible $c$-character blocks that you have to figure out the transition function for.


Having trouble understanding a proof of Mahaney’s theorem I am reading a blog post of Lance Fortnow, which includes a proof of Mahaney's theorem.

I am not sure why $a’$ cannot be in between $w_i$ and $w_j$ in Case 1, and also why $a’$ cannot be in between $w_0$ and $w_1$ in Case 2.

Can anyone give me some explanation?

Let me recap the proof. We are given a sparse NP-hard language $A$: for each length $n$, there are at most $n^c$ strings of length $n$ in $A$.

For a satisfiable CNF $\varphi$, let $a(\varphi)$ be the lexicographically first satisfying assignment for $\varphi$. We consider the NP language $B$, which consists of all pairs $(\varphi,w)$ such that $\varphi$ is satisfiable and $a(\varphi) \leq w$ (in lexicographic order).

Since $B$ is in NP, there is a polytime reduction $f$ such that $(\varphi,w) \in B$ iff $f(\varphi,w) \in A$. Since $f$ runs in polytime, $|f(\varphi,w)|$ is polynomially bounded, say $|f(\varphi,w)| \leq N$ (where $N$ depends on $n = |(\varphi,w)|$). Since $A$ is sparse, we can bound
$$
 |\{f(\varphi,w) : w \text{ is an assignment for $\varphi$}\} \cap A| \leq \sum_{k \leq N} k^c =: m,
$$
where $m$ is also polynomial in $n$.

We will show how to use $f$ to decide SAT in polynomial time. Given a CNF $\varphi$, we will assume that $\varphi$ is satisfiable, and will attempt to verify it. That is, under the assumption that $\varphi$ is satisfiable, we will run an algorithm that is guaranteed to find a satisfying assignment for $\varphi$. If it succeeds, we can conclude that $\varphi$ is indeed satisfiable (since we have found a satisfying assignment). If it fails, then $\varphi$ couldn't have been satisfiable.

We will use $f$ to determine $a(\varphi)$ using some sort of binary search.
The idea is to pick $m+1$ many assignments $w_1,\ldots,w_{m+1}$, equally spaced in assignment space, and to calculate $f(\varphi,w_1), \ldots, f(\varphi,w_{m+1})$. We now consider two cases:

$f(\varphi,w_i) = f(\varphi,w_j)$ for some $i < j$. If $f(\varphi,w_i) \notin A$ then this means that $a(\varphi) > w_i,w_j$. If $f(\varphi,w_i) \in A$ then this means that $a(\varphi) \leq w_i,w_j$. In both cases, it is clear that $a(\varphi) \notin \{w_i+1,\ldots,w_j\}$ (where $w_i+1$ is the successor assignment in lexicographic order).
All $f(\varphi,w_i)$ are distinct. By construction, at least one of them is outside of $A$, say $f(\varphi,w_i)$. Then $a(\varphi) > w_i \geq w_1$. In particular, $a(\varphi) \notin \{0,\ldots,w_1\}$, where $0$ is the first assignment in lexicographic order.

Since we chose the $w_i$ to be evenly spaced, in both cases we eliminate a (roughly) $1/m$ fraction of the search space. After $O(nm)$ such iterations, we will be left with only $\operatorname{poly}(n)$ potential values of $a(\varphi)$, and can check them one by one (in order), thereby finding $a(\varphi)$ (if it is there to be found). (I am sketching this part since your question is about the preceding part.)


Can the isomorphic graph problem be solved in deterministic polynomial time? Here is a recent homework problem of mine:

  Call graphs G and H isomorphic if the nodes of G may be reordered so
  that it is identical to H. Let ISO = {⟨G,H⟩| G and H are isomorphic
  graphs}. Show that ISO ∈ NP.

In order to solve this problem, I created a non-deterministic Turing machine that did the following:

Check if each graph has the same number of nodes
Non-deterministically arrange the edges of G in a permutation that matches H
Verify that each edge in the permutation of G matches the corresponding edge in H

As far as I know, this approach is acceptable for solving this problem with non-determinism.

My question is this: if we can compare the edges in the permutation of G against H, why can't we simply check to see if each edge in the original list of edges in G (a maximum of $n^2$ nodes) has a matching edge in H (which also has a maximum of $n^2$ nodes) for a total big O of O($n^4$)?  If this is possible, does that mean that this problem is in P?

Your approach sounds intuitively appealing on first glance, but it doesn't work.  It's not enough that each edge in $G$ has a matching edge in $H$, when taken one at a time.  There has to be a way to provide a single matching (isomorphism) that matches every edge of $G$ to a (different) edge of $H$, in a way that preserves the connectivity.

Examples:

Suppose you discover that it is possible to match edge $(a,b)$ from $G$ with edge $(u,v)$ from $H$; and you also discover that it is possible to match edge $(c,d)$ from $G$ with $(u,v)$ from $H$.  This doesn't mean there will necessarily be a way to stitch this into a complete isomorphism that describes how all vertices and edges are matched.  For instance, trying to simultaneously match both $(a,b)$ and $(c,d)$ to the same edge $(u,v)$ does not correspond to any legal graph isomorphism (different vertices have to map to different vertices, and different edges to different edges).
Suppose you discover that it is possible to match edge $(a,b)$ from $G$ with edge $(u,v)$ from $H$; and you also discover that it is possible to match edge $(b,c)$ from $G$ with $(w,x)$ from $H$, where $v \ne w$.  This doesn't mean there will necessarily be a way to stitch this into a complete isomorphism that describes how all vertices and edges are matched.  For instance, trying to simultaneously match $(a,b)$ to $(u,v)$ and $(b,c)$ to $(w,x)$ doesn't work, since you need $b$ to be consistently matched to the same vertex in both (e.g., either to $v$ both times, or to $w$ both times).

For these reasons, your approach will indeed run in polynomial time but will not compute the correct result: there will be some graphs $G,H$ where your algorithm outputs "isomorphic" but where the correct answer is "not isomorphic".

If we try to fix this problem, the naive approach is to try to find all ways to match the set of $n$ vertices in $G$ to a re-ordering of the set of vertices in $H$ (i.e., a matching that simultaneously describes what every vertex in $G$ corresponds to, in $H$).  However, there are $n!$ such candidates to try, and $n!$ is exponential in $n$, so this leads to an exponential-time algorithm.  It's a famous open problem whether the graph isomorphism problem is in P or not.  See https://en.wikipedia.org/wiki/Graph_isomorphism.


Summing two array using FFT: time complexity analysis This is the problem :

  Given two arrays of $n$ elements A and B, let's define their sum as
  $$ A + B = \{ a + b \mid a \in A \text{ and } b \in B \}. $$
  Calculate $A + A$ in optimal time given that $A[i] \in [1,10n^{1.5}]$ for all $i$.

In order to solve this problem I used FFT by representing a polynomial in the following way:

$$ p(x) = \sum_{i=0}^n x^{A[i]}. $$

After multiplying this polynomial with itself using FFT in linear time, I get the desired result in $\Theta(n^{1.5} \log n)$ time.

However, basic combinatorics gives us that there are $O(n^2)$ elements in the sum of $A + A$, How can I possibly produce them and copy them to a result array all in less than $O(n^2)$ using FFT?

Since all elements are in the range $[1,10n^{1.5}]$, all elements $A+A$ are in the range $[2,20n^{1.5}]$. So there are $O(n^{1.5})$ distinct elements in the sum. Some of them will be obtained more than once.


On certificates in BPP (avoiding majority vote) Assume that we have a $BPP$ algorithm $A$ for a problem $\Pi$. Given input $x$ we run $A$ on $\Pi$ polynomially many times and take majority output.

However if the problem $\Pi$ is also in $NP$ instead of running $A$ so many times why cant we after every run verify the certificate that $A$ produces is correct? If correct after a particular run and the answer is $Yes$ and the certificate is accepted then declare answer as $Yes$ else if the answer is $Yes$ and the certificate is not accepted then declare answer as $No$.

This should be much faster than taking majority vote.

A randomized algorithm $A$ does not produce any sort of "certificate" in any useful sense. Even if $A$ is a correct BPP algorithm, all that you know by running $A$ once is that it gives this particular outcome on this particular set of coin tosses. How would you use this fact as a witness that the input is or is not in the language? A correct BPP algorithm may give the right or wrong answer on this particular run.

In contrast, a correct deterministic algorithm does give a certificate from only running it once because it will give the same (correct) answer every time. Whereas you would need to run $A$ on all possible coin tosses and concatenate these answers to get any sort of "proof" about the input.

Another approach to your question: you could also start from the fact that a problem is in NP and try to design a randomized algorithm that both solves it and produces witnesses when it does. Here, however, as Yuval says, the issue is that witnesses may be very unlikely to guess so we do not know how to do this in general. If we could show that a randomized polynomial-time algorithm can reliably guess witnesses when they exist, we will essentially have shown $NP \subseteq BPP$.


Matching with specific cardinality In a weighted graph $G(\mathcal{V},\mathcal{E})$ where $w(i,j)$ is the weight of the edge $(i,j) \in \mathcal{E}$. How can I find a maximum weighted matching with a specific size (i.e specific cardinality).

Let me start by answering a slightly different question:
Given a weighted graph $G=(V,E)$ on $n=|V|$ vertices, we want to find a maximum-weight matching of cardinality at most $k$.
Let $L$ be the largest edge weight in $G$, and define $L' = 2nL$. Transform the graph $G$ by adding $\ell =n-2k$ new vertices $v_1, \dots, v_\ell$, and all edges in $\{v_1, \dots, v_\ell\} \times V$. Each new edge has weight $2nL$. Let $G'$ be the new graph.
Compute a maximum matching $M$ of $G'$ and return the matching $M \cap E$.
If there is a matching $M$ of weight $\ell L' + x$ in $G'$ then there is a matching of weight $x$ and size at most $k$ in $G$.
There are exactly $\ell$ edges in $M' = M \cap (\{v_1, \dots, v_\ell\} \times V)$ since at most $\ell$ edges in $\{v_1, \dots, v_\ell\} \times V$ can belong to any single matching and, if $|M| < \ell$, the weight of $M$ would be at most $(\ell-1)L' + \frac{n+\ell}{2}L < (\ell-1)L' + nL < \ell L'$.
Then, there are at most $k$ edges in $M'' = M \setminus M' = M \cap E$ as otherwise we would have $|M| = |M'| + |M''|  > \ell + k = \frac{\ell}{2} + \frac{\ell}{2} + k = \frac{\ell}{2} + \frac{n}{2} - k + k =  \frac{\ell + n}{2}$, which is a contradiction.
Since the weight of $M'$ is exactly $\ell L'$, the weight of $M'' \subseteq E$ must be $x$.
If there is a matching $M''$ of weight $x$ and size at most $k$ in $G$ then there is a matching $M$ of weight $\ell L' + x$ in $G'$.
Since $|M''| \le k$, there are at least $n-2k= \ell$ distinct unmatched vertices $u_1, \dots, u_\ell$ in $V$ (w.r.t. $M''$).
Choose $M = M'' \cup \{ (v_i, u_i)  \mid i=1, \dots, \ell\}$. The weight of $M$ is $\ell L' + x$.

We can now look for a maximum-weight matching of cardinality exactly $k$ in $G$.
We can reduce this problem to the one of finding a maximum-weight matching of cardinality at most $k$.
Given $G=(V,E)$ let $L$ be its largest edge weight.
Modify $G$ by changing the weight $w(u,v)$ of each edge $(u,v)$ to $w'(u,v) = w(u,v) + kL$. Call $G'$ the resulting graph. Find a maximum-weight matching $M$ of cardinality at most $k$ in $G'$. If $|M| < k$, the instance has no feasible solution, otherwise return $M$.
Clearly a matching $M$ of size $k$ in $G'$ weighs $kL + x$ if and only if $M$ weighs $x$ in $G$. We only need to show that: 1) if a matching of size $k$ exists in $G$, $M$ contains exactly $k$ edges, and 2) if no feasible matching exists in $G$, $M$ contains less than $k$ edges.
The second claim is immediate since any matching in $G'$ is also a matching in $G$. We then focus on the first claim:
If $G$ admits a matching of size $k$, $M$ contains exactly $k$ edges
By construction $|M| \le k$. We now show  that $|M| \ge k$. Suppose towards a contradiction that $M < k$. Then the weight of $M$ is at most
$\sum_{(u,v) \in M} w'(u,v) \le  (k+1) |M| L \le (k+1)(k-1)L = (k^2 - 1)L < k^2 L$. Since a weight of at least $k^2 L$ is attainable by selecting the edges in any matching of size $k$ in $G'$ (such a matching exists in $G$ and hence in $G'$), this contradicts the fact that $M$ is a maximum-weight matching.
.


Doubts about Baker-Gill-Solovay How am I supposed to read the P=?NP relativization proof? I am reading the classical paper Relativization of the P=?NP problem by Baker, Gill and Solovay, in particular the proof that there exist an oracle $B$ such that $\mathsf{P}^B \neq \mathsf{NP}^B$ on page 436. I have some questions and your help will be appreciated.

The procedure does not seem to be an oracle but a deterministic algorithm.
Is this construction a counterexample to P = NP?
What does this mean "Run query machine $P_i$ with oracle $B_i$ on input $x_i = 0^n$?" Does it mean that $P_i$ asks

if $B_i$ accepts $0^n$
if $B_i$ accepts any string of length $n$
ONE BY ONE if $B_i$ accepts a string of length $n$ from the canonical enumeration?

I assume that the set $B$ or $B_i$ is initially empty. Does it mean that the FIRST string of length $n$ from the canonical enumeration will always be added?

Let me answer your concrete questions:

An oracle is a language. One way to describe a language is to give a procedure for constructing it.
The construction is not a counterexample to P=NP. It shows that there exists an oracle relative to which P and NP are different. It also gives another oracle relative to which they are the same. Later, it was shown that P is different from NP relative to a random oracle (almost surely); recently this was extended to the entire polynomial hierarchy. The modern interpretation of such results is that diagonalizing techniques (techniques that would also work relative to an arbitrary oracle) cannot be used to settle the P vs NP question.
"Run query machine $P_i$ with oracle $B_i$ on input $x_i = 0^n$" has the following meaning. The machine $P_i$ is an oracle machine — it is a Turing machine that has a special mechanism allowing it to access the oracle. We run $P_i$ on the input $0^n$, i.e., the string of length $n$ consisting entirely of zeroes. Whenever $P_i$ makes an oracle access, we answer according to $B_i$.
Your final question is a bit specific. I suggest trying to read the proof again, and if you fail, check a more modern account. Note that the result can be proved in several ways, so a proof appearing in a different source might be different.


k-means clustered data: how to label newly incoming data I have a data set with labels that were produced by a $k$-means clustering
algorithm. Now there is some data (with the same data structure) from another
source and I wonder what is the most sensible way to label this new, yet unseen
data? I was thinking about either

calculating the distance to the prior $k$-means centroids and label the data to the the nearest centroids accordingly
run a new algorithm (e.g. SVM) on the new data using the old data as the training set

Unfortunately, I couldn't find anything about this particular problem. There are
only a few questions about the general use of $k$-means as a classification model:

Can $k$-means clustering do classification?
How to segment new data with existing $k$-means model?

This is not answerable without knowing something about the data itself and where it comes from and what it means.  But it sounds like you're trying to do something awfully dubious.

It sounds like you're trying to come up with labels for free, with a purely automated method.  That usually doesn't work.  There's no free lunch.  You'll need to obtain labels from some ground-truth source of data (e.g., human labelling; retrospective analysis); no amount of pure algorithms can replace that.  See Efficiently labelling training data in machine learning.

Using distance computations might give you a plausible approximation, or it might work poorly.  It all depends on the meaning and distribution of the data.  There will be some datasets where it will work well enough, and others where it will work terribly.  There is no single answer, and no special algorithm that eliminates the need to obtain known-correct labels for your data.


Understanding DPLL algorithm I'm trying to understand DPLL algorithm for solving SAT problem. And here it is:

Algorithm DPLL
  Input: A set of clauses Φ.
  Output: A Truth Value.
function DPLL(Φ)
   if Φ is a consistent set of literals
       then return true;
   if Φ contains an empty clause
       then return false;
   for every unit clause l in Φ
      Φ ← unit-propagate(l, Φ);
   for every literal l that occurs pure in Φ
      Φ ← pure-literal-assign(l, Φ);
   l ← choose-literal(Φ);
   return DPLL(Φ ∧ l) or DPLL(Φ ∧ not(l));

At first, I don't clearly understand how unit-propagate(l, Φ), pure-literal-assign(l, Φ) and choose-literal(Φ) work. I'll try to guess on particular examples. Correct me please if I do something wrong.

For the first one

unit-propagate(a, (0 v -a) ∧ (a v b) ∧ (b v d) ∧ (f v g) v ...)

we will have

((0 v -0) ∧ (0 or 1) ∧ (1 v d) ∧ (f v g) ∧ ... = (f v g) v ...,

having a = 0, b = 1.
For second procedure

pure-literal-assign(a, (a v b v c) ∧ (d v -b v a) ∧ (-d v b))

result is

(b v c) ∧ (d v -b) ∧ (-d v b),

assigning a = 1.
And finally choose-literal(Φ) just returns some random (in common case) unassigned literal for further computations.

Now, I don't understand why algorithm has such strange conditions for finishing? Why does it work?

Thanks!

It works because the three cases you mention will remove every non-pure variable after some number of steps, but it is crucial that you also consider the recursive step, namely $\mbox{dpll}(\phi \land l) \lor \mbox{dpll}(\phi \land \neg l)$.

After a recursive step, you are guaranteed to have at least one unit clause, so the unit clause will be set to its value and hence all the variable will in the end be assigned a value.

I think your misunderstanding must arise from the recursive calls.  Observe that if you have any formula $\phi = ((a \lor b \lor c) \land \cdots)$, then $\mbox{choose-literal}(\phi)$ will return some unassigned variable, say $a$.  The recursive call will then be with $\phi \land a$ which will be $(a \lor b \lor c) \land \cdots) \land (a)$.  And then $\mbox{unit-literal}(\phi)$ will return $a$ and set it to true.  The other recursive call is equivalent, but with $\phi \land (\neg a)$ so $\mbox{unit-literal}(\phi)$ will still return $a$ and set $a$ to false.


recurrence - Iteration method T(n)=T(n-a)+n I really need help to solve the following: T(n)=T(n-a)+n where a is a constant greather or equal 1.

So I started to iterate
T(n)=T(n-a)+n
    =T(((n-a)+n)-a)+n
    =T(3n-3a)+n
    =T(((3n-3a)+n)-a)+n
    =T(4n-4a)+n

this brings me to the Basic: T(kn-ka)+n.

Is it right ? I am not sure how to solve such Terms with a constant ?
thank you for your help !!

Hint: Let's solve the case $a = 1$; I'll leave the generalization to you:
$$
\begin{align*}
T(n) &= n + T(n-1) \\ &=
n + (n-1) + T(n-2) \\ &=
n + (n-1) + (n-2) + T(n-3) \\ &= \cdots \\ &=
n + (n-1) + (n-2) + \cdots + (1) + T(0) \\ &=
\frac{n(n+1)}{2} + T(0).
\end{align*}
$$
In the general case, if $n = ma$ then you'll get $am(m+1)/2 + T(0) \approx n^2/(2a) + T(0)$.


Why does Travelling Salesman Problem pose the restriction that each vertex can only be visited once? According to the wiki page of TSP as a graph problem,

  It is a minimization problem starting and finishing at a specified vertex after having visited each other vertex exactly once

Then what if a triangle is given, with two edges weighed $1$ and the third weighed $100$,obviously, the shortest path to visit all three vertices are passing the two $1$-weighed edges twice.

So what's the meaning of such a restriction?

This mostly comes down to what makes an interesting problem, and what can be easily analyzed.

The restriction of visiting each vertex once is common in these sorts of problems. A traversal that visits each vertex no more than once is called a "path", and these are well-studied in graph theory, so there are quite a few existing theorems based on them.

The version where you can visit vertices more than once can be readily reduced to the version where you can't (and in poly-time): for every pair of nodes, calculate the shortest distance between them, remove the edge directly between them (if any), and add an edge between them with weight equal to that shortest distance. (In your example graph, this would replace the 100 edge with a 2.)

So your modified version both doesn't play into existing graph theory problems, and can be easily reduced to the standard one. It's easier just to analyze the standard one instead.

TL;DR: It's because of precedent in graph analysis. See also the Hamiltonian cycle problem, which is very closely related, and the longest path, which is a bit more distantly related.


Computing maximum-cost subtree that uses at most k edges I'm looking for an efficient algorithm for the following problem:

Input: a binary, complete tree with a cost on each edge, an integer $k$
Output: the maximum-cost subtree containing $\le k$ edges

For purposes of this problem, a subtree is defined to be a connected subset of edges.  Each edge of the tree has a cost, and the cost of a subtree is the sum of the costs of the edges in the subtree.

Only edges have a cost, which is always positive. The tree always has a root node from which only one path originates and from which we must search, in the example it is the node numbered 1. I read somewhere that it's possible to use a hashing function to compute it, but there was no explanation given.

I would also be interested to learn of an algorithm that works for graphs that aren't just binary trees.

Here's an example, with the desired subtree marked in yellow:

Say our tree is $T = (V, E)$ with weight function $w : E \to \mathbb{Q}$ and $|V| = n$, and we are looking for the maximum-weight subtree with at most $k$ edges.
There is a $\Theta(nk^2)$-time and $\Theta(nk)$-space algorithm for binary trees that uses ideas from dynamic programming.
Idea: Store in every node $v$ the maximum weight obtainable using $i \in 1, \dots, k$ edges for a subtree rooted in $v$, as well as two pairs $(b_l, k_l)$ and $(b_r, k_r)$ for each $i$ that indicate if the left resp. right edges is chosen, and how many edges are chosen from each subtree; that is, $b_l + k_l + b_r + k_r = i$. Compute these numbers bottom-up; the leaves initialize with all zeroes.
Details:
for v ∈ V {
  for i ∈ [1..k] {
    v.maxWeight[i]   = 0
    v.chooseLeft[i]  = 0
    v.edgesLeft[i]   = 0
    v.chooseRight[i] = 0
    v.edgesRight[i]  = 0
  }
}

globalMax = [null, 0, -1]

def annotate(v) {
  if v is not a leaf {
    annotate(v.left)
    annotate(v.right)

    for i ∈ [1..k] {
      for j ∈ [0..i] {
        w  =   [j > 0]   * w((v, v.left))  + v.left.maxWeight[max(0,j-1)]
             + [i-j > 0] * w((v, v.right)) + v.right.maxWeight[max(0,i-j-1)]

        if w > v.maxWeight[i] {
          v.maxWeight[i]   = w
          v.chooseLeft[i]  = min(j,1)
          v.edgesLeft[i]   = max(0,j-1)
          v.chooseRight[i] = min(i-j,1)
          v.edgesRight[i]  = max(0,i-j-1)
        }
      }

      if v.maxWeight[i] > globalMax[2] {
        globalMax = [v, i, v.maxWeight[i]]
      }
    }
  }
}

annotate(T.root)

What remains then is to move top-down from globalMax[0] and follow the chooseX[_] links with edgesX[_] to construct the optimal subtree with globalMax[1] edges and weight globalMax[2].
Proof of correctness (by induction) and analysis are elementary.
The idea extends to trees of higher degree but then the factor $k^2$ changes to something more vicious; every node contributes something of the order of $k^{\operatorname{deg}(v)}$ then, if implemented naively.


Understanding implemetation of the Toffoli gate using other gates I have a system with three qubits as input and I want to demonstrate this equality:

where the left part of the equal is the circuit representation of the Toffoli gate where the first two lines are the control qubits and the third one is the target. On the right side we have the CNOT gate whose matrix representation is

$$
CNOT=\left(\begin{array}{cccc}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 0 & 1\\
0 & 0 & 1 & 0
\end{array}\right)$$

T,S and H are the $\dfrac{\pi}{8}$ gate,phase gate and Hadamard gate, respectively, represented by the matrixes

$$H=\dfrac{1}{\sqrt{2}}\left(\begin{array}{cc}
1 & 1\\
1 & -1
\end{array}\right), S=\left(\begin{array}{cc}
1 & 0\\
0 & i
\end{array}\right), T=\left(\begin{array}{cc}
1 & 0\\
0 & exp(i\pi/4)
\end{array}\right)$$

The Toffoli gate is supposed to do this

My problem is that I don't know how, given some input, for example, the three qubits in the state |1>, the circuit acts on the input. For example, in the second control qubit there is a CNOT gate, so what I have to do is calculate the direct sum of |1> and the qubit which is below it once it has passed through the H gate? This is, before the target qubit reach $T^{\dagger}$, we have the state $|1>|1\oplus H|1>>=-\dfrac{1}{\sqrt{2}}|1>(|0>-|1>)$

Is this correct?

When applying quantum operations you always:

Simplify everything down to individual self-contained cases.
Apply the operation separately to each case.
Recombine the answers.

So, in the case of applying a CNOT to the state $|1\rangle \otimes (H \cdot |1\rangle)$, you:

Simplify things. We don't want that $H$ in the way. Apply it. The state is $|1\rangle \otimes (\frac{1}{\sqrt 2}|0\rangle - \frac{1}{\sqrt 2}|1\rangle)$.
Separate things. Distribute the tensor product over the subtraction. The state is $\frac{1}{\sqrt 2}|1\rangle \otimes |0\rangle  - \frac{1}{\sqrt 2}|1\rangle \otimes |1\rangle$. Or, for short, just $\frac{1}{\sqrt 2}|10\rangle  - \frac{1}{\sqrt 2}|11\rangle$.
Apply the operation separately to each case. If the second bit is our control, then in $|10\rangle$ the control isn't satisfied and nothing happens while in $|11\rangle$ the control is satisfied and we toggled to $|01\rangle$. Apply that to each part of $\frac{1}{\sqrt 2}|10\rangle  - \frac{1}{\sqrt 2}|11\rangle$ and you end up with $\frac{1}{\sqrt 2}|10\rangle  - \frac{1}{\sqrt 2}|01\rangle$.
None of our output cases overlapped when being added together, so there's no need to combine anything.

You might get a sense of this by adding state displays to Quirk while it cycles through the inputs into your Toffoli circuit.


Minimum number of steps to sort 3x3 matrix in a given way So I started practicing some algorithms and programming before university starts and I ran into this problem:

Given a 3x3 matrix containing the numbers from 0 to 8, find the minimum number of steps required to sort the matrix in the following format:

1 2 3
4 5 6
7 8 0

In one move it is only allowed to pick a cell that is adjacent to the cell which contains the 0 and swap those two cells.

Now, I am really stuck with this one and have no idea how to begin. Any tips and ideas to get me started are appreciated.

Since you are looking for minimal number of moves without any tricks, there is old good pattern for small exact problems.

0) treat your starting matrix as root.
1) enumerate possible moves, and perform them (copy matrix, save steps etc.).
2) keep performing step one for every resulting matrix until you find them ordered. This is minimal number of moves.
1+) optimization possible is to ignore the same matrices that you already have, block sliding ply in direction it came from.


Expressing partial decidability using existential quantification def.
A predicate M(x,y) is partially decidable if the function f given by " f(x,y) = 1(if M(x,y) holds), f(x,y) = undefined(otherwise) " is computable.

Thm.
If M(x,y) is partially decidable, then so is the predicate ∃yM(x,y).

proof.
 Take a decidable predicate R(x,y,z) such that M(x,y) iff ∃zR(x,y,z).
Then...

I can not imagine the R(x,y,z)...
Please explain the way of thinking.

( Page115, Computability by Nigel Cutland)

The predicate $R(x,y,z)$ states that "$M$ accepts the input $x,y$ within $z$ steps". It is computable since we can simulate a given machine on a given input for a bounded number of steps.


Query Regarding Direct cache mapping Thank you for looking into this, I have a problem regarding direct cache mapping, My problem really though is with the question formation itself and the problem I am about to present seems to have inconsistency and has unclear description. So the problem is as follows ( I am presenting exactly as given )

32 bit architecture
Main memory size = 8GB
cache size = 512KB
Block size = 32 words
To Find

Number of bits required for Byte Offset = ?
Number of bits required for main memory address = ?
Number of bits required for main memory block number = ?
Cache Index bits = ?
Tag-bits = ?
Size of Tag Directory = ?

Now My Interpretation of the solution is as follows

As it is 32 bit architecture which means Word size is 4 Byte ( I am confused about this part the most as the question states cache block size in Words but expects to calculate Byte offset ) but for the sake of this problem, moving on main memory size is 8GB that's 233Bytes, cache size ( blocks only, this does not include tag directory which is part of cache controller ) Block size of 32 Words or 128 Bytes, now If you agree with me on this much, or else this is probably where I am wrong so please correct me right here. Now assuming I am correct so far, I will first calculate main memory address bits, that will be, first let's calculate it's size then let's do binary log, that will be  233Bytes / 4 Bytes per word this comes out to be 231 Words means 31 bits for memory address and our second answer, next I calculate number of main memory blocks that will be  233Bytes / 128 Bytes per block this comes out to be 226 Blocks of main memory so the number of bits required for main memory block number would be 26 bits, so this gives our third answer, moving forward as I assume a single cache/main memory block to be of 128 Bytes and not Words. So for byte offset within a block it must be 7 bits ( Point of highest concern ) and this should be our first answer according to the question. Now let's calculate number of cache blocks that will be 219Bytes / 128 Bytes per block which is 212 Blocks so cache index size will be 12 bits which is our fourth answer, we're almost done ! Now Tag bits should be and since it's direct mapped it should be memory address size - ( cache index + Word or Byte offset ) that is ( 31 - (12 + 7)) = 12 bits that is our fifth answer and finally size of tag directory will be  212Cache Blocks * 12bits per tag, Now not going into exact answer in KB's is this approach right or have I made a mistake or is the problem formulation incorrect ( as I think the mistake must be with cache blocks being in bytes or words ) ?

I am going to talk about the cache - related questions:

Block size is $$32 \text{words} = 2^5$$ . That, means that you need, 5 bits for offset.
$$\#\text{blocks}=\frac{2^{19}}{2^5}=2^{14}$$, so you need 14 bits for the index ( to indentify which block in cache is going to represent your wanted memory adresss )
For a 32 - bit adress, tag is the rest : $$32 - 14- 5 = 13$$ bits.


Obtaining a computational history of a Turing Machine I am currently reading the proof presented in Sipser's "Theory of Computation" for the undecidability of the problem of checking whether the language accepted by a linear bounded automata is empty. In this proof, a contradiction is derived via a reduction from the problem of checking whether a Turing machine, $M$ accepts a given input, $w$. The proof seems to use the fact that from an input in the form $\langle M,w \rangle$, it is always possible to get a computational history, $C$, of $w$ when run on $M$. Then, $C$ is fed into some LBA, $B$, which checks if its input is an accepting configuration of $M$.

It seems to me that in order to obtain $C$ in the first place, we must simulate $M$ on $w$. However, if $M$ does not halt (and since $M$ is not an LBA, it is not guaranteed that there are a finite number of configurations), then we will never obtain $C$ (and $C$ would not be finite). It seems that the problem of obtaining a computational history of a Turing machine is equivalent to checking whether a Turing machine accepts its input. So what is the method used to always obtain $C$ from $M$ and $w$? Don't we need to prove the existence of such a method if we are going to use it to derive a contradiction?

It is correct that you cannot compute $C$ in case $M$ does not halt on $w$.

What can be done is to query $C$, that is for a given time $t$ to compute the $t$-th configuration of $M$ on input $w$. Also, you can compute finite prefixes of $C$ of given length. Possibly, these operations are already sufficient for the proof in the book that you read (which I did not read).

Also, from the outline you give it seems that it is not necessary to compute $C$ at all. If $M$ accepts $w$, there is a finite $C$ which will be recognized by $B$. The reduction has to compute $B$ from $M$ and $w$, not $C$ itself. $C$ is just the input that would witness non-emptyness of $L(B)$.


Sorting an array of length $n$ in $O(m+n)$ time I need to find a method to sort an array in $O(m+n)$ time complexity.
I understand it should be a variation on Radix sort, however I am not familiar with it or its implementation...

Input: an array $A$ of length $n$, containing values from $-m$ to $m$
Output: a sorted array $A$

Any suggestions will be appreciated, thanks!

Use counting sort. In $O(n)$, count the number of elements of each value, and then in $O(m+n)$ go over the histogram and translate it to the sorted array.


Truth and lie in infomation theory: negative amount of information How does information theory deal with truth?

Does disinformation or lie have negative amount of bits of information?

How does information theory deal with truth?

It doesn't. It deals with messages drawn from probability distributions, not with knowledge.

  Does disinformation or lie have negative amount of bits of information?

No, because that's not what information theory is about.


Time complexity of the following the code for(i = 1; i<=n;i++){for(int j=i+1;j<n-i;j++)} for(int i = 1;i<=n;i++){
      for(int j = i+1;j<=n-i;j++){
        print("hello");
      }
    }

The first loop has time complexity of n and second for loop is dependent on i. That means for every i, the number of time inner for loop gets executed is: $\sum_{k=1}^{n/2}(n-2k)$ After doing some algebra, I get: $\frac{n^2}{2}-\frac{n^2}{4}-\frac{n}{2}$. This is the time complexity for inner for loop. Now we multiplying outer loop  $n*(\frac{n^2}{2}-\frac{n^2}{4}-\frac{n}{2})$. Therefore, time complexity is $\Theta (n^3)$.
But this can't be right? It should max be $\Theta n^2$. Cause inner loop doesnt get executed for every i value.$\forall i \; \; \;i>n/2$ inner loop doesnt get executed at all.

Suppose $i=1$ then inner loop get executed $n-2$ times because of $2\leq j\leq n-1$ and $j $increment each step by one, As a result $n-1-2+1=n-2$ times inner loop executed.
If $i=2$ then inner loop executed $n-4$ times ... until $i=\frac{n}{2}$ inner loop executed 1 time.

Value of $i$
#inner loop executed

$i=1$
$n-2$

$i=2$
$n-4$

$i=3$
$ n-6$

...
...

$i=\frac{n}{2}$
$n-(n-1)$

It's equal to following summation:
$\frac{n}{2}\times n-2\sum_{i=1}^{\frac{n}{2}}i=\frac{n^2}{2}-\frac{n\times(\frac{n}{2}+1)}{2}=O(n^2)$


Questions regarding CPU scheduling algorithms ( Round Robin and Priority scheduling ) Consider the following processes :

1) My First Question is if we need to schedule them using preemptive priority scheduling with Round-Robin for equal processes priorities with a quantum of 3. Here is my answer to this problem :

Sorry about that bad drawing. My problem here is at time 13. At this time we have two processes of equal priority ( p1 and p3 ) that we need to schedule them using RR with a quantum of 3 . My question is what process we will start scheduling it here ? I have started with p1 as it was already being executed by the CPU . Also is the rest of the answer is right ?

2) Now for the second question. Let's consider that We need to schedule the same process with a round-robin with a quantum of 4 . I have used this website to check my answer http://cpuburst.com/ and here its answer :

According to this answer, at time 20 p4 should be executed, but according to my answer p1 is the process that should be executed ?? And due to this difference, the rest of the answer is different to mine.

You had to make assumptions. Your problem is that “priority scheduling with round robin for equal priority” is not enough to specify exactly what happens.

Your scheduler will consider a change in the schedule when the running process finishes, when a new process is started with priority same or higher than the currently running process, or if the quantum is elapsed - but it’s not obvious if this is every three seconds, or three seconds after the last change in schedule. And exactly what “round robin” would pick isn’t clear.

You’d need the exact details of the scheduling algorithm.


Why do servers use ECC memory? I understand that ECC checks for errors and corrects them automatically without the knowledge of the operating system or user. I don't understand however why servers often use ECC memory?

The idea of ECC memory is that sometimes memory bits spontaneously flip --- this is rare but happens with noticeable probability, especially if memory is large. Using ECC memory, you can recover from such errors, at a certain cost (overhead).


How does Tarjan's pseudocode work (explained to someone familiar with C or Java)? The Short Story

A famous computer scientist, Tarjan, wrote a book years ago. It contains absolutely bizarre pseudocode. Would someone please explain it?

The Long Story

Tarjan is known for many accomplishments, including the fact that he was the coinventor of splay trees. He published a book, "Data Structures and Network Algorithms," during the 1980s.

All of the pseudo-code in Tarjan's book is written in a language of his own devising. The pseudo-code conventions are very regimented. It's almost a true language, and one could imagine writing a compiler for it. Tarjan writes that his language is based upon the following three:

Dijkstra's Guarded Command Language
SETL
ALGOL

I am hoping that someone familiar with one or two of the above languages, or the work of Tarjan, will be able to answer my question.

An example of a function written in Tarjan's language is shown below:

heap function mesh (heap nodes h1, h2);

    if key(h1) > key(h2) → h1 ⟷  h2 fi;

    right (h1) := if right(h1) = null → h2

                  |right(h1) ≠ null → mesh (right(h1), h2) fi;

    if rank (left (h1)) < rank (right (h1)) → left(h1) ⟷ right(h1) fi;

rank (h1) := rank(right(h1)) + 1;

return h1,

end mesh;

I have seen lots of pseudo-code, but I have never seen anything like Tarjan's. How does Tarjan's pseudocode work? How can examples of Tarjan's pseudocode be re-written as something which looks more like C or Java? It need not even be C or Java. The if-else construct in Tarjan's language is not only different from C-family languages, but also different from Python, MATLAB and many others.

Table of Contents

I will divide my explanation of Tarjan's pseudocode into the following sections:

Tarjan's If-else Blocks (the -> & | operators)
Assignment and Equality Tests (:= and =)
There is else if, but no else construct
Tarjan's Conditional Assignment Operator := if
Additional Examples of Tarjan's if and := if
5.5.
Tarjan Arrays (or Lists)
Summary of Operators
Tarjan's Double-pointed Arrow Operator (⟷)
Tarjan's do-loops are like C/Java while-loops
Tarjan's Conditional-assignment operator with all false conditions

(1) Tarjan's If-else Blocks

(the operators → and | )

The if-else construct is perhaps the most fundamental control structure in Tarjan's language. In addition to C-like if-blocks, if-else behavior is very nearly built-into in Tarjan's assignments and Tarjan's while loops. Tarjan's arrow operator -> (or →) is a delimiter between the condition of a if-statement and the execution block of an if-statement.

For example, in Tarjan's language we might have:

# Example One
if a = 4 → x := 9 fi

If we partially translate the line of Tarjan code above into C or Java, we get the following:

if (a = 4)
    x := 9
fi

Instead of a right curly braces (as in C and Java) Tarjan ends an if-block with an ALGOL-like backwards spelling of the key-word: fi

If we continue translating our above example, we get:

if (a = 4) {
    x := 9
}

(2) Assignment and Equality Tests (:= and =)

Tarjan takes these operators from ALGOL (later also seen in Pascal).

Tarjan uses = for equality tests, not assignments (so it works like Java ==).

For assignment, Tarjan uses :=, which works like Java =.

Thus, if we continue translating our example, we have:

if (a == 4) {
    x = 9
}

A vertical bar (or "pipe" or |) in Tarjan's language is equivalent to the else if keyword in C or Java.
For example, in Tarjan's language we might have:

# Example Two
if a = 4 → x := 9 |  a > 4  → y := 11 fi

The Tarjan-code above translates to:

if (a == 4) {
    x = 9
}
else if (a > 4)  {
    y = 11
}

(3) else if only and no else construct

Earlier, I covered the basics of if-statements without describing the nuances. However, we will now discuss a small detail. The last clause in a Tarjan-ian if-else block must always contain an arrow (→) operator. As such, there is no else in Tarjan's language, only else if. The closest thing to an else-block in Tarjan's language is to make the rightmost test-condition true.

if a = 4 → x := 9 |  a > 4  → y := 11 | true  → z := 99  fi

In C/Java, we would have:

if (a == 4) {
    x = 9
}

else if (a > 4)  {
    y = 11
}
else { // else if (true)
    z = 99
}

Examples are easier to understand than general descriptions. However, now that we have some examples under our belt, know that the general formal of a Tarjan's if-else construct is as follows:

if condition
    → stuff to do
 | condition
    → stuff to do
 [...]
 | condition
    → stuff to do
fi

The character  | is like if else

The character → separates the test-condition from the stuff-to-do.

(4) Tarjan's Conditional Assignment Operator := if

Tarjan's if can be used two very different ways. So far, we have only described one of the uses of the Tarjanian if.  Somewhat confusingly, Tarjan still uses the notation/syntax if for the second type of if-construct. Which if is being used is based on context. Analyzing the context is actually very easy to do as the second type of Tarjan-if is always pre-fixed by an assignment operator.

For example, we might have the following Tarjan code:

# Example Three
x := if a = 4 → 9 fi

Begin Digression

After working with Tarjan code for awhile, you get used to the order of operations. If we parenthesize test condition in the example above, we obtain:

x := if (a = 4) → 9 fi

a = 4 is not an assignment operation. a = 4 is like a == 4 -- it returns true or false.

End Digression

It can help to think of := if as syntax for a single operator, distinct from := and if In fact, we will refer to the := if operator as the "conditional assignment" operator.

For if we list (condition → action). For := if we list (condition → value) where value is teh right-hand-side value we might assign to the left-hand-side lhs

# Tarjan Example Four
lhs := if (a = 4) → rhs fi

in C or Java might look like:

# Example Four
if (a == 4) {
    lhs = rhs
}

Consider the following example of "conditional assignment" in Tarjanian code:

# Tarjan Instantiation of Example Five
x := if a = 4 → 9 |  a > 4  → 11 | true  → 99  fi

In C/Java, we would have:

// C/Java Instantiation of Example Five
if (a == 4) {
    x = 9
}
else if (a > 4)  {
    x = 11
}
else if (true) { // else
    x = 99
}

(5) Summary of Operators:

So far, we have:

:= ...... Assignment operator (C/Java=)
= ...... Equality test (C/Java ==)
→ ...... Delimiter between test-condition of an if-block and the body of an if-block
| ..... C/Java else-if
if ... fi ..... if-else block
:= if... fi ..... Conditional assignment based on an if-else block

(5.5) Tarjan Lists/Arrays:

Tarjan's Language has built-in array-like containers. The syntax for Tarjan arrays is much more intuitive than the notation for Tarjan if else statements.

list1  := ['lion', 'witch', 'wardrobe'];
list2a := [1, 2, 3, 4, 5];
list2b := [1, 2];
list3  := ["a", "b", "c", "d"];
list4  := [ ]; # an empty array

Tarjan array elements are accessed with parentheses (), not square-brackets []

Indexing begins at 1. Thus,

list3  := ["a", "b", "c", "d"]
# list3(1) == "a" returns true
# list3(2) == "b" return true

Below shows how to create a new array containing the 1st and 5th elements of [1, 2, 3, 4, 5, 6, 7]

nums := [1, 2, 3, 4, 5, 6, 7]
new_arr := [nums(1), nums(5)]

The equality operator is defined for arrays. The following code prints true

x := false
if [1, 2] = [1, 2, 3, 4, 5] --> x := true
print(x)

Tarjan's way to test if an array is empty is to compare it to an empty array

arr := [1, 2]
print(arr = [ ])
# `=` is equality test, not assignment

One can create a view (not copy) of a sub-array, by providing multiple indices to operator () combined with ..

list3  := ["a", "b", "c", "d"]

beg    := list3(.. 2)
# beg == ["a", "b"]
# beg(1) == "a"

end    := list3(3..)
# end == ["c", "d"]
# end(1) == "c"

mid    := list3(2..3)
# mid == ["b", "c"]
# mid(2) == "c"

# `list3(4)` is valid, but `mid(4)` is not

(6) Additional Examples of Tarjan's if and := if

The following is another examples of an Tarjan conditional assignment (:= if):

# Tarjan Example Six
a  := (false --> a | true --> b | false --> c1 + c2 |  (2 + 3 < 99) --> d)

(true --> b) is the leftmost (cond --> action) clause having a true condition.
Thus, the original assignment Example Six has the same assignment-behavior as a := b

Below is our most complicated example of Tarjan code thus far:

# Tarjan Example -- merge two sorted lists

list function merge (list s, t);

return if s =[] --> t
        | t = [ ] --> s
        | s != [ ] and t != [] and s(l) <= t(1) -->
            [s(1)]& merge(s[2..], t)
        | s != [ ]and t != [ ] and s(1) > r(l) -->
            [t(1)] & merge (s,t(2..))
       fi
end merge;

The following is a translation of Tarjan's code for merging two sorted lists. The following is not exactly C or Java, but it is much closer to C/Java than the Tarjan version.

list merge (list s, list t) {

    if (s is empty) {
        return t;
    }
    else if (t is empty){
        return s;
    }
    else if  (s[1] <= t[1]) {
        return CONCATENATE([s[1]], merge(s[2...], t));
    else  { // else if (s[1] > t[1])
        return CONCATENATE ([t[1]], merge(s,t[2..]);
    }
}

Below is yet another example of Tarjan-code and a translation in something similar to C or Java:

heap function meld (heap h1, h2);

    return if h1 = null --> h2
            | h2 = null --> h1
            | h1 not null and h2 not null --> mesh (h1, h2)
           fi
end meld;

Below is the C/Java translation:

HeapNode meld (HeapNode h1, HeapNode h2) {

    if (h1 == null) {
       return h2;
    }
    else if (h2 == null) {
        return h1;
    } else {
        mesh(h1, h2)
    }
} // end function

(7) Tarjan's Double-pointed Arrow Operator (<-->)

Below is an example of Tarjan code:

x <--> y

What Does a Double Arrow (⟷) Operator Do in Tarjan's Language?
Well, almost all variables in Tarjan's Language are pointers.
<--> is a swap operation. The following prints true

x_old := x
y_old := y
x <--> y
print(x == y_old) # prints true
print(y == x_old) # prints true

After performing x <--> y, x points to the object which y used to point to and y points to the object which x used to point to.

Below is a Tarjan statement using the <--> operator:

x := [1, 2, 3]
y := [4, 5, 6]
x <--> y

Below is a translation from the Tarjan code above to alternative pseudocode:

Pointer X     = address of array [1, 2, 3];
Pointer Y     = address of array [4, 5, 6];
Pointer X_OLD = address of whatever X points to;
X = address of whatever Y points to;
Y = address of whatever X_OLD points to;

Alternatively, we could have:

void operator_double_arrow(Array** lhs, Array** rhs) {

    // swap lhs and rhs

    int** old_lhs = 0;
    old_lhs = lhs;
    *lhs = *rhs;
    *rhs = *old_lhs;
    return;
}

int main() {

    Array* lhs = new Array<int>(1, 2, 3);
    Array* rhs = new Array<int>(4, 5, 6);
    operator_double_arrow(&lhs, &rhs);
    delete lhs;
    delete rhs;
    return 0;
}

Below is an example of one of Tarjan's functions using the ⟷ operator:

heap function mesh (heap nodes h1, h2);
    if key(h1) > key(h2) → h1 ⟷  h2 fi;
    right (h1) := if right(h1) = null → h2
                   |right(h1) ≠ null → mesh (right(h1), h2)
                  fi;

    if rank (left (h1)) < rank (right (h1))
        → left(h1) ⟷ right(h1)
    fi;

    rank (h1) := rank(right(h1)) + 1;
    return h1;
end mesh;

Below is a translation of Tarjan's mesh function into pseudo-code which is not C, but looks more like C (relatively speaking). The purpose of this is to illustrate how Tarjan's ⟷ operator works.

node pointer function mesh(node pointers h1, h2) {

    if (h1.key) > h2.key) {

         // swap h1 and h2
            node pointer temp;
            temp = h1;
            h1 = h2;
            h2 = temp;
    }

    // Now, h2.key <= h1.key

    if (h1.right == null) {
        h1.right = h2;

    } else // h1.key != null {
        h1.right = mesh(h1.right, h2);
    }

    if (h1.left.rank < h1.right.rank ) {
        // swap h1.left and h1.right

        node pointer temp;
        temp = h1;
        h1 = h2;
        h2 = temp;
    }

    h1.rank = h1.right.rank + 1;
    return h1;
}

(8) Tarjan's do-loops are like C/Java while-loops

Tarjan's language if and for constructs are familiar for C/Java programmers. However, the Tarjan keyword for a while-loop is do. All do-loops end with the keyword od, which is the backwards spelling of do. Below is an example:

sum := 0
do  sum < 50 → sum := sum + 1

In C-style pseudocode, we have:

sum = 0;
while(sum < 50) {
    sum = sum + 1;
}

The above is actually not quite right. A Tarjan do-loop is really a C/Java while(true) with an if-else block nested inside. A more literal translation of the Tarjan code is as follows:

sum = 0;
while(true) {
    if (sum < 50) {
         sum = sum + 1;
         continue;
         // This `continue` statement is questionable
    }
    break;
}

Below, we have a more complicated Tarjan do-loop:

sum := 0
do  sum < 50 → sum := sum + 1 | sum < 99 → sum := sum + 5

C/Java-style pseudocode for the complicated Tarjan do-loop is as follows:

sum = 0;
while(true) {

    if (sum < 50) {
         sum = sum + 1;
         continue;
    }
    else if (sum < 99) {
         sum = sum + 5;
         continue;
    }
    break;
}

(9) Tarjan's Conditional-assignment operator with all false conditions

Although the lengthy explanation above covers most things, a few matters are still left unresolved.
I hope that someone else will someday write a new-improved answer based on mine which answers these quandries.

Notably, when the conditional assignment operator := if is used, and no condition is true, I am not what value is assigned to the variable.

x  := if (False --> 1| False --> 2 | (99 < 2) --> 3) fi

I am not sure, but it is possible that no assignment is made to x:

x = 0;
if (false) {
     x = 1;
}
else if (false) {
     x = 2;
}
else if (99 < 2) {
     x = 3;
}
// At this point (x == 0)

You could require that the left-hand-side variable seen in an := if statement be previously declared. In that case, even if all conditions are false, the variable will still have a value.

Alternatively, perhaps all-false conditions represents a runtime error. Another alternative is to return a special null value, and store null in the left-hand argument of the assignment.


How to study for the Algorithm courses I'm taking a fairly challenging Algorithm course, in which we are learning about algorithms such as Dijkstra, Bellman-Ford etc. as well as the algorithm design patterns such as recursions, DP and various graph construction techniques such as layering. Now I really have some trouble to design correct and efficient algorithm using stuff we learned in the class. To be specific, I'm having trouble with following:

Design an algorithm that's fast enough, i.e., I came up with a $O(n^2)$ algorithm but in fact there is a $O(n log n)$ algorithm.
To find the edge cases for the algorithm I designed. It happened a lot of times to me during exam that I designed some seemingly correct algorithm but will actual fail in some edge cases. I always have some hard time to find those edge cases and therefore falsely believe the algorithm is correct.

I would greatly appreciate any suggestions that can help me deal with my struggle. Also, just for reference, here are the links to the course I'm taking (schedule, and the homeworks)

Designing algorithms that are fast enough is probably a function of experience. There are strategies (recursion, divide-and-conquer, dynamic programming...) that can be used. Often a problem can be approached with multiple strategies but one is more efficient than the other. The more of these strategies you know, the better you are equipped for using them in your algorithms. Experience will also give you a feel for what is an appropriate approach; you may intuitively notice which problems are recursive in nature, which can be expressed as operations on a graph etc. Then you can use what you know to knead the challenge into a familiar shape. Do a Google search for "algorithm strategies" to find useful resources which list generic strategies. Learn about these and then consider for algorithms you encounter how they are instances of these generic approaches (or combinations thereof).

Edge cases tend to occur where assumptions are made, and for some situations those assumptions are incorrect. An algorithm attempts to resolve something for some structure which seems consistent; it breaks down where the structure suddenly differs or becomes inconsistent. Edge cases are the sort of place in a program where you need to test assumptions and where decisions branch.

For example, suppose I have some algorithm that takes a list of elements as input and performs a computation over it. You begin your design by stating that for each element in the list, in order, some action is performed. That's an assumption right there. "Each element in the list" assumes there are some. How will it behave for an empty list?

An example of this I encountered in some programming contest a while ago. You were given a list of numbers and had to find out how many ways there were to divide this into three lists, maintaining the original order of the numbers, in some way that satisfied some condition (the sums for the three sub-lists had to be equal). I got started but soon noticed some test inputs failed. It turned out that empty sub-lists were also valid. I had assumed that each sub-list had to have at least one element. And then, of course, I'd need to consider whether my fixed program would handle inputs of 0, 1 or 2 numbers correctly as well.


Irregularity of $\{a^ib^jc^k \mid \text{if } i=1 \text{ then } j=k \}$ I read on the site on how to use the pumping lemma but still I don't what is wrong with way I'm using it for proving that the following language is not a regular language:

$L = \{a^ib^jc^k \mid \text{if } i=1 \text{ then } j=k \}$

for $i\neq1$ the language is obviously regular but in the case which $i=1$ , we get that the language is $a^1b^nc^n$, now for every division $w=xyz$ such that $|y|>0 , |xy|< p$ where p is the pumping constant I get the word $a^1b^pc^p$ would be out of the language. since  $|xy|< p$
, $y$ may contains only $a's$ or $b's$ or both. if $x= \epsilon$ and $y=a$, pump it once and you're out of the language, if it contains only $b's$, pump it once and your'e out of the language, and if it contains both, pump it and you're out of the language again.

so, why does this language considered as not regular and cannot be proved for its irregularity by the pumping lemma? please point out my mistake.

The pumping lemma can only be used to show that a language is not regular, not that it is regular. This is, I think, the fundamental misunderstanding here... that you are unable to use the pumping lemma to prove a language irregular does not constitute a proof of irregularity.

A language is regular if, equivalently,

it can be accepted by an NFA
it can be generated by a regular grammar
it can be described by a regular expression
it can be partitioned into finitely many equivalence classes under the indistinguishability relationship (as per the Myhill-Nerode theorem)

This last point can usually be pretty helpful in cases where the pumping lemma fails. Here, you merely need to demonstrate that there are infinitely many equivalence classes for strings in your language; you could argue that strings of the form $ab^nc$ constitute separate classes for all $n$.

Furthermore, as pointed out in the comments, you can often use closure properties of language classes in order to demonstrate that a particular language isn't in the class. For instance, you know that regular languages are closed under intersection. Using that fact, you could show that your language can't be regular, since if it were, the language $ab^nc^n$ would be regular (a contradiction, since you know that language isn't regular... you could even prove this easier version with the pumping lemma).

EDIT: Just in case how to apply the pumping lemma here is unclear, I'll give an example.

Choose the string $uvw = ab^pc^p$. Since $|uv| < p$ and $v > 0$, $v$ must be some non-empty string possibly beginning with a single $a$, followed by multiple $b$'s. If $v$ contains the $a$, pumping will cause there to be a different number of $a$'s, so we get a string not in the language. If the string does not contain the $a$, it consists only of $b$'s, and pumping will cause the number of $b$'s to be different from $n$. The resulting string is not in the language since the number of $b$'s is not equal to the number of $c$'s. Therefore, this string cannot be pumped to another string in the language, a contradiction of the assumption the language was regular; hence, the language is not regular.


Working of PDA for $\{a^m b^n c^k \mid m=n \text{ or } n=k\}$ I understand that the language $L = \{ a^mb^nc^k \mid m=n \text{ or } n=k \}$ is context-free because it can be represented as the union of $L_1 = \{a^mb^mc^k\}$ and $L_2 = \{a^mb^kc^k\}$, which are both context-free. But I can't figure out the working of the PDA accepting $L$.
To check whether $m=n$, first of all $m$ many $a$'s will be pushed, then on every occurrence of $b$, one $a$ will be popped out, or if stack becomes empty, then remaining $b$'s will be pushed. After this, either stack will be empty, meaning $m=n$, or $m-n$ many $a$'s or $n-m$ many $b$'s will remain in the stack, meaning $m \neq n$. How can we check whether $n=k$ now?

The PDA first guesses whether $m=n$ or $n=k$. According to the guess, it either just checks that $m=n$, or just checks that $n=k$.
What your heuristic argument suggests is that this language cannot be accepted by a deterministic PDA. You can likely show this by adapting the proof here.


Reducing from 3-COLOR to 3-CNF SAT? I get how to reduce 3-SAT to 3-COLOR, but I'm not sure how to do it the other way around. Does anyone  have any hints or insight?

Hint: For each vertex $v$ and color $c$, have a variable $x_{v,c}$ which means "vertex $v$ gets color $c$". Now construct a 3SAT instance that states:

Each vertex gets some color.
Neighboring vertices get different colors.


Finding a loop invariant the following pseudo code returns the nth Fibonacci number:

 if n = 0 then
    return 0
 a ← 1
 b ← 1
 for i = 1 to n − 1 do
     c ← b − i
     b ← c + a
     a ← c + 2*i + 1
 return b

I am trying to find any loop invariant for the variables a and b, (as i understand it has to be valid before and after the loop, but i can't seem to be able to come up with anything, except maybe b >= i, but I'm not sure that counts as an invariant). As far as I get it, simply saying b = b - i + a wouldn't really mean anything. Any help on the subject would be greatly appreciated.

As we already know, the loop iteratively calculates the nth Fibonacci number, so it naturally follows that the loop invariant should contain $b = \mathsf{fib}(i)$ condition.
But that is not sufficient for us, because the computation depends on the variable a, and we don't need c, because it is initialized in the loop body.

The line b ← c + a actually gives us a hint as to what the condition on a should we impose: after this line $b$ must be equal to $\mathsf{fib}(i+1)$. Now, from the expression for c and the expression $\mathsf{fib}(i+1) = \mathsf{fib}(i) + \mathsf{fib}(i-1)$ we easily obtain the condition for a: $a = \mathsf{i + fib(i-1)}$.

If we rewrite the for loop into an equivalent while loop, we'll get a loop invariant:

$$a = i + \mathsf{fib}(i-1) \wedge b = \mathsf{fib}(i) \wedge i \le n.$$

Here is how we can prove that the loop actually does the job:

{a = i + fib(i-1) /\ b = fib(i) /\ i <= n}
while i < n do
  {a = i + fib(i-1) /\ b = fib(i) /\ i < n}
  {a = i + fib(i-1) /\ b = fib(i) /\ b − i = fib(i) - i /\ i < n}
  c ← b − i
  {a = i + fib(i-1) /\ b = fib(i) /\ c = fib(i) - i /\ i < n}
  {a = i + fib(i-1) /\ c + a = (fib(i) - i) + (i + fib(i-1)) /\ c = fib(i) - i /\ i < n}
  {a = i + fib(i-1) /\ c + a = fib(i+1) /\ c = fib(i) - i /\ i < n}
  b ← c + a
  {a = i + fib(i-1) /\ b = fib(i+1) /\ c = fib(i) - i /\ i < n}
  {c + 2*i + 1 = fib(i) - i + 2*i + 1 /\ b = fib(i+1) /\ c = fib(i) - i /\ i < n}
  {c + 2*i + 1 = fib(i) + (i+1) /\ b = fib(i+1) /\ c = fib(i) - i /\ i < n}
  a ← c + 2*i + 1
  {a = (i+1) + fib(i) /\ b = fib(i+1) /\ c = fib(i) - i /\ i < n}
  {a = (i+1) + fib((i+1)-1) /\ b = fib(i+1) /\ (i+1)-1 < n}
  i ← i + 1
  {a = i + fib(i-1) /\ b = fib(i) /\ i <= n}
{a = i + fib(i-1) /\ b = fib(i) /\ i <= n /\ i >= n}
{a = i + fib(i-1) /\ b = fib(i) /\ i = n}
{b = fib(n)}


How is it that programs can be identified with partial functions for programming language semantics? I was reading about denotational semantics

  Broadly speaking, denotational semantics is concerned with finding mathematical objects called domains that represent what programs do. For example, programs (or program phrases) might be represented by partial functions.

I was wondering, how does one map programs to partial functions? What is the mapping? What is the intuition and conceptual idea? I don't understand what the relationship (formally or conceptually) is between partial functions and program (or Turing Machines).

Partial functions from initial program states to final program states are a suitable model for deterministic sequential programs that do not interact with the environment while executing. Such programs just try to compute a result depending on what they find in their starting state. If program $P$'s attempted computation fails when starting from some initial state $\sigma$, then that means that the function describing $P$'s semantics doesn't yield a final state for $\sigma$.

Using functions (of the common type mentioned above) makes sense when the constructs of the programming language under consideration are deterministic. That is the case e.g. for a language made up of assignment statements, sequential composition, conditionals, and while loops.

Partial as opposed to total functions are chosen for two reasons. 1. to allow loops to diverge and 2. to model problems such as division by 0.


Polynomial time reductions using binary search There are many NP-complete decision problems that ask the question whether it holds for the optimal value that OPT=m (say bin packing asking whether all items of given sizes can fit into m bins of a given size).
Now, I am interested in the problem whether OPT>m. Is this a decision problem or an optimization problem? It seems to be that it lies in NP (a NTM can guess a solution and it can be verified in polynomial time that the bound is met). Is it also NP-complete?

I would have said yes, because having a polynomial algorithm, we could find a solution in polynomial time for the original problem (asking whether OPT=m) by using binary search and repeatedly using the polynomial algorithm to test if OPT larger than some bound.

However when I try to construct a proper solution, I always see the complication that the oracle (that asks whether OPT>m') would need to be queried more than once, and this is forbidden in the polynomial time Karp reduction.

Any solutions or remarks?
Would it make a difference if I ask whether OPT>=m?

Thanks in advance

Is OPT = m? is a coNP decision problem.  A "no" answer has a certificate verifiable in polynomial time, the certificate being a valid bin packing that uses fewer than $m$ bins.

The same is true for the question Is OPT > m?.  There is no polynomial-time verifiable certificate for the "yes" answer to either of these questions unless NP = coNP.

Is OPT < m? is an NP decision problem.  A "yes" answer has a certificate verifiable in polynomial time, the certificate being a valid bin packing that uses fewer than $m$ bins.


Can the output value be solved and/or written as Taylor expansion? imho this is not at all a duplicate, because the other question does
  not address the "recursive" case $T(d,n) = ....T(d-1,T(d-1,n))....$,
  which appears to be part of the Taylor expansion of this function.
  Also I don't know how to write this as a Taylor expansion. If I would,
  I would still not know how to solve this specific instance.

Consider the following function. Maybe it could be more efficient, but I'm only interested in the output value, not the runtime complexity. All variables are whole numbers.

function branch(currentDepth, maxDepth, n, k) {
    if (currentDepth == maxDepth) {
        return n;
    }
    sum = 0;
    for (i=0; i<=k; i++) {
        tmpN = branch(currentDepth+1, maxDepth, n, i);
        sum += branch(currentDepth+1, maxDepth, tmpN, k-i);
    }
    return sum;
}

For $2 < k << n$ and $2 < d = O(\log n)$, is there a formula in terms of $d$, $k$ and $n$ (either exact, big-O or Theta), that predicts the output for

branch(0, d, n, k);

Will it be exponential in $n$? Can we maybe solve this for small $k$? ($k\le7$).

Application: the output value is a factor of the runtime complexity of a Fixed Parameter algorithm I made up, but I don't think it will beat existing algorithms. However I still wanted this solved.

It is better to use as parameters maxDepth-currentDepth, n, k. Call the resulting function $f_k(d,n)$.

When $k = 0$,
$$
f_0(d,n) = \begin{cases}
n & d = 0, \\
f_0(d-1,f_0(d-1,n)) & d > 0.
\end{cases}
$$
You can prove by induction that the solution is $f_0(d,n) = n$.

When $k=1$,
$$
f_1(d,n) = \begin{cases}
n & d = 0, \\
f_1(d-1,f_0(d-1,n)) + f_0(d-1,f_1(d-1,n)) & d > 0,
\end{cases}
$$
which reduces to
$$
f_1(d,n) = \begin{cases}
n & d = 0, \\
2f_1(d-1,n) & d > 0.
\end{cases}
$$
The solution is
$$
f_1(d,n) = 2^d n.
$$
When $k = 2$, using the preceding formulas we get
$$
f_2(d,n) = \begin{cases}
n & d=0, \\
2f_2(d-1,n) + 4^{d-1} n & d > 0.
\end{cases}
$$
Unrolling the recursion gives
$$
\begin{align*}
f_2(d,n) &= 4^{d-1} n + 2\cdot 4^{d-2} n + 2^2 \cdot 4^{d-3} n + \cdots + 2^{d-1} n + 2^d n \\ &=
(2^{2d-2} + 2^{2d-3} + \cdots + 2^{d-1}+2^d) n \\ &=
(2^d+1)2^{d-1} n.
\end{align*}
$$
Let us approximate this by $2^{2d-1}n$.

When $k = 3$, the preceding formulas show that
$$
f_3(d,n) \approx
\begin{cases}
n & d = 0, \\
2f_3(d-1,n) + 2^{3d} n & d > 0.
\end{cases}
$$
Unrolling the recursion gives
$$
f_3(d,n) \approx (2^{3d} + 2^{3(d-1)+1} + 2^{3(d-2)+2} + \cdots + 2^{3(1)+d-1} + 2^d)n \approx \frac{4}{3} 2^{3d}n.
$$
Continuing in this way, we find that up to constants, if $f_k(d,n) = \Theta(2^{r_kd}n)$ then $r_{k+1} = \max_{1 \leq \ell \leq k} (r_\ell + r_{k+1-\ell})$ (except for the base cases $k \leq 1$). For example, we have
$$
\begin{align*}
&r_0 = 0 \\
&r_1 = 1 \\
&r_2 = 2 \\
&r_3 = 3 \\
&r_4 = 4
\end{align*}
$$
and so on. Indeed, induction shows that $f_k(d,n) = \Theta_k(2^{kd}n)$. With more effort, we could estimate the hidden constant.


binary max and binary min I'm reading a paper about constraint satisfaction problem and found a term "binary Max and binary Min" operations but I dont know the meaning. If someone know could you please explain for me? I googled it but didn't find nothing.

In theoretical computer science, in the context of operators or functions, "binary" usually means "taking two arguments", whereas "Boolean" means "taking one of two values", especially if those values are true and false or $0$ and $1$.

So, for example, the ordinary addition operator on the natural numbers is binary (it adds two things) but not Boolean (the arguments can take infinitely many different values).  Conversely, the function $f(x,y,z)=(x\lor y)\land z$ is Boolean (its arguments are true/false) but not binary (it takes three arguments, not two; it's ternary).

"Binary" is also used to denote the base-$2$ number system but that doesn't seem relevant, here: min and max operate on numbers as abstract quantities, and the representation of those numbers (binary, decimal, Egyptian hieroglyphs, ...) is irrelevant.


How to compute max jump distance I have a BNE-instruction (32 bits), which contains 16 bits for the jump field:

Opcode A[31:26]
RS A[25:21]
RT A[20:16]
Immed A[15:0]

Assuming the BNE-instruction will now be written in 64 bits format, what would be the (new) max jump distance this instruction can make?

I really have no clue, what to do, so I hope someone can help me. Thanks in advance.

Depending on the architecture, the immediate for branches may mean a byte address (x86) or a word address if fixed width instructions are mandated, which means that for a 16bits offset, the range is something like -2^17 to +2^17-1

Having fixed 64bits-wide instructions is quite rare (VLIW domain). If you add 32 bits, and if you keep the same number of registers (hence 5 bits for RS and RT) and the opcode part, I guess these extra bits would end in the offset part, so 16+32bits offset.
If instructions are fixed width, you may then have doubleword offsets : -2^-50 to +2^50-1

Practically, it does not make any sense to have such wide immediate offsets. No program is large enough to be several gigabyte long (I'm not counting libraries, which are generally called through indirect or direct branches over the full 32bits or 64bits address range, not conditional branches).

I could imagine that with 64bits instructions, some variants of the conditional branch instructions would offer 16 to 32bits immediate values, like : "BNE R1,#1234, @Somewhere" instead of using 48bits for the offset.


Clique-or-almost reduction to clique I saw the posted question here about a direct reduction from near-clique to clique.

Clique-or-almost is like near-clique but with the option for a complete clique of size $k$, I mean that perhaps an edge is missing and perhaps not.

I can't figure out how to change the proof in the link to fit to the reduction from Clique-or-almost to Clique.

  $$\text{CLIQUE-or-almost} = \{(G,k) \mid \text{ $G$ contains a $k$-clique with possibly one missing edge}\}.$$

Here is a reduction from CLIQUE to CLIQUE-or-almost.

Let $G$ be an arbitrary graph. Form a new graph $G'$ by adding two new vertices $x,y$ connected to all vertices of $G$, but not to each other. If $G$ contains a $k$-clique, then $G'$ contains a $(k+2)$-clique with a missing edge.

Conversely, suppose that $G'$ contains a $(k+2)$-clique $S$, possibly with a missing edge. If the clique doesn't contain a missing edge, then $S \setminus \{x,y\}$ is a clique of size at least $k$ in $G$. If $x,y \in S$ then the missing edge is $(x,y)$, and again $S \setminus \{x,y\}$ is a $k$-clique of $G$. In the remaining case, $|S \setminus \{x,y\}| \geq k+1$. Remove one vertex from the missing edge to obtain a clique of size at least $k$ in $G$.

For a reduction in the other direction, it is well-known that CLIQUE is NP-hard. Since CLIQUE-or-almost is clearly in NP, by definition there is a reduction from CLIQUE-or-almost to CLIQUE. One can construct such a reduction via the proof of the Cook-Levin theorem.


Does exist NP language that is Cook Levin deterministic reducible to xor satisfiability in polynomial time? We say that the language $L$ is Cook Levin deterministic reducible to xor satisfiability in polynomial time if and only if for each word $w\in\Sigma^*:w\in L\iff f(w)\in XORSAT$ where $\Sigma=\{0,1\}$ and $f:\Sigma^*\rightarrow\Sigma^*$ is the function in the Cook Levin reduction that was introduced in 1971.

In other words if the language $L$ is Cook Levin deterministic reducible to xor satisfiability in polynomial time and $M$ is non deterministic Turing machine that decides the language $L$ in polynomial time then for each word $w\in\Sigma^*:\Phi_{M,w}$ is satisfiable if and only if $M$ accepts $w$, according to Cook Levin theorem since 1971, and also $\Phi_{M,w}$ is in XNF, i.e. XOR Normal Form.

Every boolean formula is in XOR Normal Form or XNF if and only if it is conjunction of clauses and each clause is XOR of literals.

It's well known, according to Cook Levin theorem since 1971, that every NP language is Cook Levin deterministic reducible to CNF satisfiability in polynomial time, i.e. if $L$ is arbitrary NP language and $M$ is non deterministic Turing machine that decides $L$ in polynomial time then for each word $w\in\Sigma^*:w\in L\iff f(w)\in CNFSAT\land\Phi_{M,w}$ is satisfiable if and only if $M$ accepts $w$ and $\Phi_{M,w}$ is necessarily in CNF, i.e. conjunctive normal form, that is conjunction of clauses and each clause is disjunction of literals.

But I don't know if exists special language that is in NP and if we apply the Cook Levin reduction then not only SAT instance is produced, but actually CNFSAT instance is produced and not only just CNFSAT instance is produced, but actually   XORSAT instance is produced.

So my question is does exist special language in NP that after applying Cook Levin reduction, for each word $w\in\Sigma^*$, we get XORSAT instance?

Note that I don't want the function of the reduction to be identity and the NP language that needs to be found that it is Cook Levin reducible to XORSAT in polynomial time is not XORSAT itself.

Also the function of Cook Levin reduction isn't identity at all.

XORSAT is in P, so any such language would have to be in P as well.

As such, it is easy to exhibit such an example: the problem XORSAT itself satisfies all your requirements, as XORSAT is Cook-Levin reducible to XORSAT (let $f$ be the identity function).


How to Convert from Decimal to Qm.n format How would you convert decimal 0.0650 to 1.15 Q format 16-bit of course? I'm kinda stuck in this for 3 days, can someone kindly help me out in this

Convert $0.065$ in binary with 15 digits of precision in the fractional part (rounding to the nearest such number):

$$
(0.065)_{10} \approx ( 0.000100001010010)_2$$

Multiply $(0.000100001010010)_2$ by $(2^{15})_{10}$ (i.e., remove the fractional-part separator) to obtain $(0000100001010010)_2$.

If you want it in hexadecimal, as you have asked in another question, you can convert it:

$$
(0000100001010010)_2 = (0852)_{16}
$$.


Equivalence of logical Formula (Kripke structures) Can someone explain me how to find if these formulas are equivalent with Kripke structures?

AG(Fp or Fq) , A(GFp or GFq)

AGF(p and q) , A(GFp and GFq)

AFG(p and q) , A(FGp and FGq)

Thank you in advance for your help :)

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

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

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

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

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

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


Are there any problems in $APX - PTAS$ that are not $APX$-complete? I have a question about the structure of the complexity class $APX$. Obviously, unless $P=NP$, no problem in the class $PTAS$ can be $APX$-complete (under the AP-reduction). However, what about the rest of problems in $APX$? Are there any problems known that are in $APX$, do not have a $PTAS$ (unless $P=NP$) and at the same time are provably not $APX$-complete (unless $P=NP$)?

For the class $NP$, Ladner's Theorem guarantees the existence of problems in $NP - P$ that are not $NP$-complete (unless $P=NP$) - the so-called $NP$-intermediate problems. I am curious if any similar result has been proved for $APX - PTAS$ with respect to approximation preserving reductions.

It is possible that the answer to this question is trivial - to be honest, the only $APX$-complete problem I know is MAX-3-SAT. However, I wonder how hard it is with respect to other problems in $APX - PTAS$.

Yes, at least under some reasonable assumptions. Crescenzi, Kann, Silverstri & Trevisan show that Minimum Bin Packing, Mininum Degree Spanning Tree and Minimum Edge Coloring are APX-intermediate unless the polynomial hierarchy collapses.

Considering that the paper is from 1996, I'm sure there's now a significantly larger number of known APX-intermediate problems.


How can I prove the languages of incompressible words is undecidable? I have hard time understanding the proof by contradiction for the claim "$L=\{x : K(x) \ge |x| \}$" is undecidable ".

The proof is as follows :

  M' = " On input $n$

  Enumerate over all $n$-bit strings $x$ in lexicographical order
  Simulate M on each $x$, where $M$ is the Turing machine that decides $L$.
  Output first $x$ which $M$ accepts.
  "

  Since TM $M'$ produced incompressible using only $O(\log n)$ to specify $n$, we
  can compress incompressible strings which is a contradiction.

I understood the $M'$ construction. However, I do not understand where exactly is the contradiction happening? According to me, $M'$ outputs $x$ which is in-compressible(ensured by TM $M$) but how does it is also compressible at same time?

Consider the word $w_n$ that is the output of $M'$ given input $n$.

Note that description of $w_n$ is the description of $M'$, whose length is some constant $c$, plus the description of $n$, whose length is $O(\log n)$ since we can express $n$ in the binary representation. So $K(w_n)\le c + O(\log n)$. If $n$ is large enough, we get
$$K(w_n)\lt n = |w_n|.$$

That is a contradiction since, as you have noted, $w_n$ should be incompressible.


Why values can not be replaced with their extensionally equal values in an intensional system? Thomas Streicher states in Investigations into Intensional Type Theory(§Introduction p.5) that:

  Although in Intensional constructive set theory (Intensional Type Theory) one can do most of the things one wants to do... certain theorems simply do not hold due to the lack of extensionality. A typical example is that from $t\in B a$ and $p\in Id A ab$ one is not allowed t conclude that $t\in Bb$ where $A$ is a type and $B$ is a family of types indexed over $A$.(But of course one is allowed to infer $t\in Bb$ from $t\in Ba$ and $a=b\in A$ !)

An almost similar thin is mentioned in Definition of extensional and propositional equality in Martin-Lof extensional type theory
:

  The (Id-DefEq) means that extensional equality is baked into the type system: if you have a type constructor :((:)→)→ then you can use a value of type   in a context expecting   if  and  map equal inputs to equal outputs. Again this is not true in an intensional system, where   and  might be incompatible if they're syntactically different.

Why is that? Isn't it that two functions that are producing exactly same output for their inputs, equal? So why can't one be replaced with another in a context? What makes definitionally equal functions eligible to be replaced with each other, but not the extensionally equal ones?

Supposing we have $a$ and $b$ of type $A$ and $p : \mathrm{Id}_A(a,b)$, there simply is not any rule of type theory that would allow you to replace $b$ with $a$ arbitrarily. So one answer is "because type theory does not let you do that", and if you think that it can be done, please show me how. But I suppose that is a non-answer, what you really are asking is why is type theory designed in such a strange way.

There are many ways to understand equality. Students of mathematics are typically taught only one, namely the equality arising from set theory and classical mathematics. This kind of equality is very intuitive and easily understood. But as you learn more mathematics, you begin to understand that sometimes two objects are not really equal, but are "kind of equal". For example, they could be isomorphic, or connected by a path. So it makes sense to look for other explanations of equality that capture the idea of a more "relaxed" equality.

In mathematics it makes a lot of sense to say that functions are equal if they produce the same outputs, but this is not so in computer science. For example, if functions $f$ and $g$ produce the same outputs, but one is much faster than the other, then it is useless for a computer scientist to consider them equal.

Type theory is a formal system which allows us to express these ideas. The identity type $\mathrm{Id}_A(a,b)$ is not necessarily the "true equality" (the only one that a student of classical mathematics knows about, and therefore calls it "true") of $a$ and $b$, it could be one of these other notions of equality that you learn about when you study homotopy theory and computer science.

For instance, one way to undertand $p : \mathrm{Id}_A(a,b)$ is to say that $p$ is some sort of a "path" from $a$ to $b$. That is, $a$ and $b$ are not "really equal", but there is a way to get from $a$ to $b$. And so, if $P :A \to \mathrm{Type}$, we certainly would not expect $P a$ and $P b$ to be "exactly the same", but rather that "there is a way to get from $P a$ to $P b$". Indeed, this goes under name transport and it follows from the rules for the identity type: given $p : \mathrm{Id}_A(a,b)$, there is a isomorphism of types $\mathrm{transport}_p : P a \to P b$.


Approximating longest path on graphs with average degree n/2 I have a graph with average degree $n/2$. How I can find an approximation algorithm for the longest path problem with factor $1/4$?

Here is something to get you started.
Suppose that your graph were $n/2$-regular, and consider the following algorithm. Start at an arbitrary vertex $v_1$. Choose one of its $n/2$ neighbors $v_2$. Choose one of $v_2$'s $n/2$ neighbors $v_3 \neq v_1$. And so on. The process will continue for at least $n/2+1$ steps. Since every path has length at most $n$, this gives a $1/2$ approximation. In fact, this would work even if the minimal degree were at least $n/2$.


How does a race condition work? When two threads try to access the same resources at exactly the same time how does the computer decide which one gets the resource, or is it just decided at random?

On a single-processor system, it is impossible for two threads to access the same location simultaneously. Rather, if the threads access the same data outside of a critical section, it's possible for their execution to become interleaved, in which case the access order is undefined. Execution is concurrent and you might call the result "random", in that nothing obvious affects the choice of one thread's code over another's. Of course, the scheduler is making the choice somehow, but it's fairly opaque in terms of ordering for access to thread-shared memory.

In multiprocessor/multicore/distributed applications, the notion of ordering is a little hazier. We can define the happens-before partial relation based on causation of signals and use this to define time stamps that can be used for coordinating events across sites. Unrelated events are called concurrent, and any processes which care about the order of concurrent events need to agree amongst themselves.  Consistency is a well-studied problem in shared-memory distributed systems. If sites request access to shared memory over some medium (bus, interconnect, etc.) then the medium access protocol will, in an opaque fashion, determine which thread gets access first. Like scheduling, the result here may appear "random", since different decisions can be made on different executions.


Proving asymptotic notations for functions I recently started learning about asymptotic notations. While I was doing practice questions (not HW) I found various question that stumped me totally. So I just want some pointers on how to go by solving these type of questions. So here is a basic question.
Given the following,

  If $f(n) = \Omega(h(n))$ and $g(n) = O(h(n))$ then $f(n) = \Omega(g(n))$.

How can I solve this and see if that is true or false.
Here is what I have tried so far,
I tried to use definitions of big-$O$ and big-$\Omega$ on $f(n)$, $g(n)$ and $h(n)$ and then combining those resulting equations to prove/disprove the outcome but I got confused.

So I need explanation of this solutions so I can make it more clear for myself.
Any help would be appreciated.

The first thing to do is to try to develop an intuition for whether the claim is true or false. Very roughly, $f=\Omega(h)$ says that $f$ is bigger than $h$, and $g=O(h)$ says that $g$ is smaller than $h$.  In both of those statements, "bigger" really means "at least as big as" and I've left off the conditions of "up to a constant factor" and "for large enough inputs".

So, if $f$ is bigger than $h$ and $g$ is smaller than $h$, is $f$ bigger than $g$? Intuitively, it ought to be. Since we've simplified, we might have gone wrong, but our intuition is that we should try to prove that the statement is true, rather than trying to find a counterexample.

Apply the definitions and you get that (try it on your own, first!)...

   ... there are constants $c$ and $d$ such that, for all large enough $n$, $f(n)\geq c\,h(n)$ and $g(n)\leq d\,h(n)$. Therefore, $f(n)\geq \tfrac{c}{d}g(n)$ for all large enough $n$, which is to say that $f=\Omega(g)$.