# Question
Title: Why is this SAT problem hard and what can I do about it?
For a graph theory problem I need to solve hundreds of millions of CNF problems that typically have around 200 variables and 15,000 clauses no larger than 10.

By default I use glucose, which usually takes a fraction of one second. However, in about one case out of a million, glucose doesn't want to finish and I don't see what is different about those cases.

I put one example here . There are 214 variables and 16466 clauses, which is small by the standards of the SAT competitions. I also ran it for more than 3 days in kissat without result.

An example of an easy CNF, slightly smaller but not by much is here . Both glucose and kissat take 4-5 seconds.

Incidentally both the hard and easy examples are unsatisfiable.

Any advice would be appreciated.

# Answer
> 6 votes
> **Why is this SAT problem hard?**

A change in perspective may be helpful. It is expected that some SAT problems are extraordinarily hard: if the strong exponential time hypothesis is true, then for *any* SAT solver $A$, there are some specific formulas $\varphi$ that $A$ takes exponential time on. Plug in $A = \mathsf{glucose}$ or $\mathsf{kissat}$ to this statement, and you have chanced upon one such example $\varphi$. The fact this only occurs in 1 in a million cases is just a testament to how strong SAT solvers have become on average cases.

In fact, it is typically not hard to come up with formulas to stump even the best SAT solvers, and all SAT solver users encounter such formulas sooner or later. In my experience, this often happens when taking a sufficiently "mathematically complex" statement and encoding it as a SAT problem. For example, for a long time, the pigeonhole principle, when encoded directly into SAT, was very difficult for SAT solvers to figure out. (I know there was active research on the pigeonhole case, so it's possible that modern SAT solvers no longer suffer from that particular barrier.)

Regarding the number of variables and clauses: for "hard" instances $\varphi$, the time required to solve will be exponential in the number of variables and clauses. So you can't necessarily expect that just because there are a small number of variables or clauses, the problem will be tractable.

> **What can I do about it?**

This one I have a much more positive answer for! Researchers working on SAT solvers typically **love** examples like this as they are very interesting case studies for improving their tools. So what you can and should do is:

* Post the example publicly (you have already done this, but consider also posting it on, e.g. GitHub or Pastebin)
* Share the example with the solvers you have tried as a hard instance, for example by posting an issue or by sending an email to active maintainers. Be sure to explain your use case/application to make the example interesting. You've already formed a more "minimal" instance, which is great as it will help them to isolate the difficulty.

Finally, the other thing you can do is try to leverage your own domain expertise to simplify the problem at formula generation time. As one example of an optimization to try, **symmetry breaking** can be very useful. That is, find an encoding of your graph theory problem which hardcodes constraints on the solution and avoids sources of exponential blowup in the number of cases to check.

---
Tags: sat-solvers
---


# Question
Title: Is Self-Modifying Turing Machine equivalent to NTM or TM?
Let SMTM be Turing Machine, but the commands recorded in which can change to others in some random way (for example, choose with a 50/50 probability the command to move to the right or move to the left), and SM-NTM be non-deterministic Turing Machine with same property (note that NTM non-deterministic in sense of choosing next action, but not the rule, which describes this actions). A difference between a self-modifying Turing machine and TM/NTM: instead of one command for any given situation, or a set of commands in a non-deterministic Turing machine, there is a fuzzy set of commands.

In addition to the question from the title: Is there any papers which describes these sort of theoretical models of computation? In particular, I am interested in the applicability of Rice's theorem for a given computational model. Maybe, there is some connection to quantum computers, NP-hardness, etc.?

The problem that prompted me to this question:

There are neural networks that have an element of non-determinism, where at a certain stage the numbers change by adding random numbers (obtained, for example, from weather observations or observation of the decay of unstable atoms, that is, really random numbers) - do such models have restrictions superimposed on a Turing machine?

# Answer
> 3 votes
Randomness is not the same as non-determinism -- at least, not the non-determinism that is referred to when people talk about non-deterministic Turing machines.

See Can an algorithm be truly non-deterministic?, Differences and relationships between randomized and nondeterministic algorithms?, https://cstheory.stackexchange.com/q/632/5038, Are nondeterministic algorithm and randomized algorithms algorithms on a deterministic Turing machine?.

There is plenty of study of randomized algorithms and the power of randomness. You can read about BPP, the open question whether BPP = P, etc.

There is plenty of study of non-deterministic algorithms and the power of non-determinism, too. For instance, you can read about the open question whether P = NP.

One common hypothesis/guess/speculation right now is that probably randomness doesn't add much power (maybe P = BPP) but non-determinism is very powerful (probably P != NP).

---
Tags: complexity-theory, turing-machines, np-complete, neural-networks, fuzzy-logic
---


# Question
Title: Analysis of a calculation of expected number of collisions in hashing
For a formal problem statement, I quote from the text *Introduction to Algorithms* by *Cormen et. al*

> Suppose we use a hash function $h$ to hash $n$ distinct keys into an array $T$ of length $m$. Assuming simple uniform hashing, what is the expected number of collisions? More precisely, what is the expected cardinality of $\\{\\{k, l\\} : k\neq l \text{ and } h(k)= h(l)\\}$ ?

---

Quite intuitive I proceeded as follows:

Let $X$ be the random variable indicating the number of collisions. Let us define an indicator random variable $X\_{ij}$ which indicates whether the $i$th element ($e\_i$) already in the table collides with the $j$ th element ($e\_j$) when the $j$ th element is to be inserted.

$Pr\\{h(e\_i)=h(e\_j)\\}=\frac{1}{m}$. So $E\[X\_{ij}\]=\frac{1}{m}$.

So based on that we have:

$$X= \sum\_{i=1}^n \sum\_{j=i+1}^n X\_{ij}$$

Taking expectation on both sides we have: $$E\[X\]= E\left\[\sum\_{i=1}^n \sum\_{j=i+1}^n X\_{ij}\right\]$$

Using linearity of expectation:

$$E\[X\]= \sum\_{i=1}^n \sum\_{j=i+1}^n E\[X\_{ij}\]$$

But, $E\[X\_{ij}\]=\frac{1}{m}$ , which is already found above.

So,

$$E\[X\]= \sum\_{i=1}^n \sum\_{j=i+1}^n \frac{1}{m}$$

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

---

Below is how my peer approached:

Let $X$ be the random variable indicating the number of collisions. Let $X\_i$ be the indicator random variable indicating collision during the $i$ th insertion of the element, $i=1,2,3,..,n$

So, $$X=\sum\_{i=1}^n X\_i$$

taking expectation on both sides, we have:

$$E\[X\]=E\left\[\sum\_{i=1}^n X\_i\right\]$$

Using linearity of expectation:

$$E\[X\]=\sum\_{i=1}^n E\[X\_i\]$$

Now let us find $Pr\\{X\_i=1\\}$ then by the property of indicator random variable we shall have $E\[X\_i\]=Pr\\{X\_i=1\\}$.

Probability that there is collision during the first insertion =$0$ \[First element is inserted without any collision.\]

Probability that there is collision during the second insertion= $\frac{1}{m}$ \[Assuming open addressing, $1$ slot is already occupied.\]

Probability that there is collision during the third insertion= $\frac{2}{m}$ \[Assuming open addressing, $2$ slots are already occupied.\]

.

.

.

Probability that there is collision during the $i$th insertion= $\frac{i-1}{m}$ \[Assuming open addressing, $i-1$ slots are already occupied.\]

So,$$E\[X\]=\sum\_{i=1}^n \frac{i-1}{m}=\frac{n(n-1)}{2m}$$

---

Though the final answer obtained by my peer is same as that of mine, but I guess there are quite a lot of issues with the approach. First it assumes open addressing, while my approach is a generalized one. Secondly, as per the formal problem statement given in the text, in the worst case if all elements hash to the same slot then we shall have $X=\binom{n}{2}$. So the spectrum of $X$ is , $X=0,1,2,..,\binom{n}{2}$

But the spectrum of $X$ as per my peer's method is $X=0,1,2..,n$. Is my peer's method actually correct?

# Answer
Both methods are correct in terms of probability analysis. It is just that the probability distributions of the two approaches are different. For example, take $n = m = 3$.

In the first approach, the probability distribution is as follows:

**Pr** $\[\textrm{No. of Collisions} = 0 \] = 2/9$

**Pr** $\[\textrm{No. of Collisions} = 1 \] = 6/9$

**Pr** $\[\textrm{No. of Collisions} = 2 \] = 0$

**Pr** $\[\textrm{No. of Collisions} = 3 \] = 1/9$

In the second approach, the probability distribution is as follows:

**Pr** $\[\textrm{No. of Collisions} = 0 \] = 2/9$

**Pr** $\[\textrm{No. of Collisions} = 1 \] = 5/9$

**Pr** $\[\textrm{No. of Collisions} = 2 \] = 2/9$

**Pr** $\[\textrm{No. of Collisions} = 3 \] = 0$

The expected costs in both the cases is $1$
> 0 votes

---
Tags: probability-theory, hash, hash-tables, hashing
---


# Question
Title: Small Turing machine accepting single complicated input?
This imprecise question is about a simple example for the following problem.

> I would like a Turing machine with few states that accepts only inputs which look complicated to the naked eye.

Of course the Kolmogorov complexity of the lexicographically smallest such input would be at most a constant more than the size of the Turing machine, so this makes the question impossible to define presicely, but hopefully it is clear what I mean. For example, a TM that accepts only Carmichael numbers would do, but I'm looking for a TM with very few states.

# Answer
> 1 votes
Here is an algorithm that can be implemented with a Turing machine using a small number of states, and that only accepts inputs that I suspect are likely to look complicated to most humans. Let the bits on the tape be $T\[1,\dots,n\]$:

* For $i:= 1,2,\dots,8$:
    1. For $j:= 3,4,\dots,n$:
        + Set $T\[j\] := T\[j\] \oplus (T\[j-1\] \land T\[j-2\]) \oplus C\[i\]$.
    2. For $j:= n-2,n-3,\dots,1$:
        + Set $T\[j\] := T\[j\] \oplus (T\[j+1\] \land T\[j+2\]) \oplus C\[i+8\]$.
* If $T\[1\]=0$, accept, otherwise reject.

Above $\oplus$ represents xor, $\land$ represents logical-and, and $C\[1..16\]$ represents a constant that is filled with random bits at design time.

Notice that this algorithm can be implemented in a Turing machine with about 64 states.

(How does this work? It is implementing an unbalanced Feistel network. So, you can think of it as roughly approximating the following conceptual approach: fix a random permutation $\pi$ on $n$-bit strings, then apply $\pi$ to the input and accept if the first bit of the result is 0.)

Probably "8" above is overkill, so I'm guessing you can significantly reduce the number of states needed. It will be subjective how small you can make it and still have the accepted inputs look random to the human eye, but I'd bet that "2" is enough, which would leave you with a Turing machine that uses only 16 states.

---
Tags: turing-machines, kolmogorov-complexity, busy-beaver
---


# Question
Title: what is the name for the space between the leaves of a tree
I am trying to write a data-type not for a tree, but for the spaces *in between* the leaves of thee tree. In number theory (a part of math) this is known as a **topograph** does it have a name in CS?

# Answer
> -1 votes
Each 3 leaves form a glob so I just figured out what a cluster means.

# Answer
> -2 votes
The empty space is called "OTIOSE". Pronounced "oh-she-ohs"

otiosity

Synonyms & Antonyms for otiose Synonyms abortive, barren, bootless, empty, fruitless, futile, ineffective, ineffectual, inefficacious, profitless, unavailing, unproductive, unprofitable, unsuccessful, useless, vain

---
Tags: terminology, trees, binary-trees, number-theory
---


title: Interval Tree by Augmenting an AVL Tree

text:
# Question
Title: Interval Tree by Augmenting an AVL Tree
According to Wikipedia: *An augmented tree can be built from a simple ordered tree, for example a binary search tree or self-balancing binary search tree, ordered by the 'low' values of the intervals. An extra annotation is then added to every node, recording the maximum upper value among all the intervals from this node down. Maintaining this attribute involves updating all ancestors of the node from the bottom up whenever a node is added or deleted. This takes only O(h) steps per node addition or removal, where h is the height of the node added or removed in the tree. If there are any tree rotations during insertion and deletion, the affected nodes may need updating as well.*

I am bit puzzled: Why can't one just update its ancestors after the new node (in case of insertion) has found its proper place in the tree after the rotations?

Also, I am not quite sure how to approach deletion.

# Answer
> 1 votes
You can update the ancestors. The Wikipedia article explains the running time to do so.

If you've done a rotation, you might need to update all nodes that participated in the rotation and all of their ancestors.

---
Tags: data-structures, balanced-search-trees, binary-search-trees, intervals, avl-trees
---


title: Can you compare large numbers this way?

text:
# Question
Title: Can you compare large numbers this way?
If you created two very large numbers represented by binary data (perhaps using sha512 with random input for each hash) could you determine what binary block is numerically larger by iterating over bytes from left (largest bit) to right (smallest bit)? If at any point the left has a 0 bit where the right has a 1, you’d know the right is larger. Where the bytes are the same, you eliminate them and continue iterating to the right.

Would this work?

# Answer
> 1 votes
Yes, this is exactly how a comparison is done. It works for unsigned integers of a fixed length. It is also called lexicographic order.

# Answer
> 0 votes
I think this would work, I just found memcmp in c++, and I think that is how memcnp works

---
Tags: binary, comparison
---


title: Algorithm to check if path exists

text:
# Question
Title: Algorithm to check if path exists
Suppose that I have a 2D array $B\[i,j\], 1 \le i,j \le n,$ such that $B\[i,j\]=X$ or $B\[i,j\] = O$. I want to write a program to check if there is a path that exists from $B\[1,1\]$ to $B\[n,n\]$ that only consist of $O$'s. The path must only consist of the 4 directions: North, South, East, West and does not include the diagonal direction. The algorithm is not necessarily looking for the shortest path, if such a path exists, just the existence of the path is needed.

I haven't formally studied algorithms but I think that this problem is a standard one in that area of study. I am not sure what to search in google though. Can anyone direct me to references on how to solve this problem?

Thanks!

# Answer
Read about depth-first search, breadth-first search, and reachability in undirected graphs. That will show you how to solve your problem.
> 1 votes

---
Tags: algorithms
---


# Question
Title: How are data structures used along databases?
I just completed a Data structures and Algorithms course in my university. I know how data structures work and how different DS are used to solve specific and to improve efficiency. I have also started to work with databases to develop CRUD applications.

My question is: If I have to for example, use a tree data structure (like a max heap) or maybe a linked list, would I just store it in a plain table and then fetch it and re form that data structure? This seems like a lot of work when you have larger data sets, and the same goes with appending data to that data structure and saving it in database.

I have seen a lot of online explanations here and on stackoverflow, but I couldn't get a satisfactory answer to clear my understanding. I would be grateful if anyone answers it thoroughly and doesn't marks it duplicate. Thanks :)

# Answer
> 1 votes
The data structures and algorithms you learnt are majorly dealing with a specific way of storing and accessing data which is stored in the **main memory**.

When you move to, **secondary memory** the same can't be applied as it wouldn't be efficient, simply because the cpu/main memory is much faster than the secodnary memory, and the OS is designed in such a way that anything it needs to access first need to be available in the main memory. This is done so that the cpu doesnt need to have to make an I/O call everytime it needs some data from the disk(main memory can be thought of as a cache of secondary memory). So the focus on data structures while dealing with secondary memory is to reduce calls and the time complexity to retrieve data since we are now dealing with a much higher volume of data.

**To answer your question**:If you are storing a data structure inside of a database, I am assuming its some sort of dump of a particular instance of that data structure. This is just adding to the existing complexity of the database and isn't actually very useful. For example, Relational databases are built upon the concepts of B+ trees, so why would you want to explicitly do the same thing. You could intelligently run queries instead which would give you the same functionality without having to get your hands dirty. Of course you can experiment and do anything but chances are, using the database functionalities efficiently will get more of your work done than you trying to do it.

---
Tags: data-structures, databases
---


# Question
Title: Why is $n^{1.98}$ an element of $O(n^2)$?
Why is option "(C) $n^{1.98}$ is $O(n^2)$" the question below correct? Is it because "Big $O$" is upper bound meaning worst case, therefore $n^{1.98}$ is not worst case $n^2$ ?

How is it still $O(n^2)$? Wouldn't it have to be equal to it, not $.02$ less?

Secondly, regarding (A), how do you work out if $2^{20} n$ is $O(n^2)$?

> QUESTION: Which of the following is not O(n^2)?
>
> * (A) $2^{20} n$
> * (B) $n^3 / \sqrt{n}$ (correct answer)
> * (C) $n^{1.98}$
>
> Answer: the order of growth of option B is $n^{2.5}$ which is higher than $n^2$.

# Answer
> 1 votes
The notation $f(n)\in \mathcal{O}(g(n))$ does **not** mean that $f(n)$ is *worst case $g(n)$*.

It means that there exists $A\>0$ such that for $n$ big enough, $f(n)$ is lesser or equal than $Ag(n)$.

This is clearly the case here, with $f(n) = n^{1.98}$ and $g(n) = n^2$, using $A = 1$.

---
Tags: asymptotics
---


# Question
Title: Comparing order of growth with n^(logn) - need to know where value comes from?
I'm trying to understand how you compare the following for order of growth.

With the below working out with $f\_4$ I don't get where the $x^5$ and $x^6$ come from at the end. With $f\_4$ you have $n^{\log n}$ when for example $\log 64$ doesn't equal 6? Can someone please explain where $x^5$ and $x^6$ come from?

Working out:

* $n = 32$, $f\_1 = 2^{32}$, $f\_4 = 32^5 = 2^{25}$
* $n = 64$, $f\_1 = 2^{64}$, $f\_4 = 64^6 = 2^{36}$

Compare these below

* $f\_1(n) = 2^n$
* $f\_2(n) = n^{3/2}$
* $f\_3(n) = n \log n$
* $f\_4(n) = n^{\log n}$

# Answer
When you want to evaluate $f\_4 = n^{\log\_2 n}$ for some number, let's say 256, you first evaluate the exponent, $\log\_2 n = \log\_2 256 = 8$, then you put it into the full formula as $n^8 = 256^8$. Of course, since $256^8 = \left( 2^{ 8 } \right)^8 = 2 ^ {8 \cdot 8 } = 2^ {64}$.

Let's now do the exercises you have: for $n=32$, we have that $\log\_2 n = \log\_2 32 = 5$, hence $n^{5} = 32 ^ 5 = \left(2^{5}\right)^5 = 2^{5 \cdot 5} = 2^{25}$.

For $n = 64$, we have that $\log\_2 n = \log\_2 64 = 6$, thus $n^{6} = 64 ^ 6 = \left(2^{6}\right)^6 = 2^{6 \cdot 6} = 2^{36}$.

It seems to me that $n^{\log\_2 n}$ follows the pattern of $2^{x^2}$ where $x = \log\_2 n$.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: How do I prove that the clique problem is polynomial-time reducible to the odd cycle transversal problem?
I have the following problem:

Let $H=(W, F)$ a graph and $k \in \mathbb{N^\*}$ be an instance for problem $\textbf{CMP}$ (i.e. the clique problem). Let $W'$ a set of new vertices, $|W'|=|H|=n$. We define the following graph, $G=(V, E)$: $V=W \cup W'$, $E=\\{xy | x, y \in V, xy \not\in F$ and $|W' \cap \\{x, y\\}| \leq 1\\}$. Show that $H$ contains a clique of cardinality at least $k$ if and only if $G$ contains a subset of vertices $U$, $|U| \leq p=n-k$, such that $G-U$ is bipartite.

I understand that I have to prove the clique problem is polynomially reducible to the odd cycle transversal problem in order to solve this, but that's all I've got. My professor said this was actually very easy to prove, and I feel like that's true and I'm missing something obvious, but I can't quite figure out how these two problems are connected. I thought I could assume that $G$ contains odd-length cycles and go from there, but according to the definition above, $G$ is already a bipartite graph, which means I can't do that so now I'm completely out of ideas.

# Answer
Though your definition of $E$ is not clear. I am assuming that $E = \\{(x,y) \mid x \in W \textrm{ and } y \in W'\\} \\, \cup \\{(x,y) \mid x,y \in W \textrm{ and } (x,y) \notin F\\}$. In other words, $E$ contain all edges between sets $W$ and $W'$, and the edges that are not in $F$.

**Proof Forward Direction:** Suppose $H$ contains a clique of size at most $k$. Let the vertices of this clique be the set $C\_W \subseteq W$. It is easy to see for the graph $G$, the set $W \setminus C\_W$ is an odd cycle traversal of $G$. And, the set $W \setminus C\_W$ has size $n-k$. This proves the forward direction.

**Proof Reverse Direction:** Suppose $G$ has an odd cycle traversal $V\_O$ of size at least $n-k$. Let us define its left side as $V\_L = W \cup V\_O$ and its right side as $V\_R = W' \cup V\_O$. Let $G'$ be the bipartite graph obtained by removing $V\_O$ from $G$.

Now, note the following observations:

1. Any vertex from $V\_L$ and any vertex from $V\_R$ can not be in the same partite set of $G'$
2. All vertices of $V\_R$ must be in the same partite set of $G'$.

Therefore, the graph $G'$ must contain the partite sets as: $V\_L$ and $V\_R$. It means, there is no edge within $V\_L$. Since $|V\_L| \geq k$. Therefore, in the original graph $H$, the set $V\_L$ forms a clique of size at least $k$. This completes the proof of the reverse direction.
> 1 votes

---
Tags: np-complete, decision-problem, polynomial-time-reductions
---


title: Prove TILING is NP-Complete

text:
# Question
Title: Prove TILING is NP-Complete
I have a homework task to show that $\mathrm{TILING} = \\{(T, 1^N) \mid \text{it is possible to cover } N \times N \text{ square with tiles from }T\\}$, where $t\in T$ is $C^4$ for some color set $C$, is NP-complete.

It is not hard to show that $\mathrm{TILING}$ is in NP.

How can I show that it is NP-Hard? Can I reduce some known language ($\mathrm{SAT}$, $\mathrm{3COL}$, $\mathrm{CLIQUE}$, etc) to it?

I have some idea of solution, similar to the proof of Cook-Levin theorem (to encode state of the Turing Machine), but it seems awkward to do it, since I have proved NP-Completeness of $\mathrm{SAT}$.

**UPDATE:**

1. A "color set" is just some set, e. g. {6, 13, 42}, {1, 2, 3, ..., 200}, then a tile can look like (6, 6, 6, 13), (6, 13, 42, 6) for the first and (1, 2, 3, 4), (8, 8, 8, 8) for the second.
2. Every neighbor side (order: up, left, down, right) must have the same color, but no restrictions for "outer" sides (edges), which doesn't have neighbors. And it's not possible to rotate tiles.

# Answer
> 4 votes
Instead of $\mathsf{TILING}$, I proved that $\mathsf{RectangleTILING}$ is $\mathsf{NP}$-complete by finding a reduction from $\mathsf{3SAT}$.

> Problem $\mathsf{RectangleTILING}$:
>
> * Input: a set $T$ of tiles, two dimensions $M$ and $N$ (in binary or unary, it doesn't matter);
> * Question: is it possible to cover a rectangle of size $N\times M$ with tiles of $T$?

If necessary, I will add some details to prove that $\mathsf{RectangleTILING}\leqslant\_m^p\mathsf{TILING}$, but I think it is not that hard to prove.

I consider a 3-CNF boolean formula $\varphi = \bigwedge\limits\_{i=0}^{m-1} C\_i$ where $\forall i \in \[\\!\[0,m-1\]\\!\]$, $C\_i = (\ell\_{i1}\vee \ell\_{i2}\vee\ell\_{i3})$ and $\ell\_{ij}$ is either $x$ or $\overline{x}$ with $x\in\mathcal{V} = \\{x\_0,…,x\_{n-1}\\}$. I construct an input $(T, 3m, 2n)$ of $\mathsf{RectangleTILING}$ such that $\varphi$ is satisfiable if and only if it is possible to cover a rectangle of size $2n\times 3m$ with tiles of $T$.

Note that it is possible to encode coordinates for tiles using the colors. For example, the following tile could be put only on column $c$ and row $r$.

It is also possible to encode multiple informations in colors, using tuples. For readability purposes, I will chose to write tiles coordinates outside of colors.

**Each tile will have only one choice of coordinates in the rectangle.**

Now the idea is to use two rows per variable:

* one row per variable $x\_j$ will keep track of the boolean assignment chosen for $x\_j$;
* the other row will permit to know which variable satisfies each clause;

and three columns per clause:

* one column per clause will sum up the boolean assignment of each variable;
* one column will chose a variable to satisfy the clause;
* the last column will pick a clause tile.

In details:

* for $i$ from $0$ to $m-1$:
    + for $j$ from $0$ to $n-1$:
        - in coordinates $(2j, 3i)$, two possible tiles, encoding $x\_j$ or $\overline{x\_j}$:
        - in coordinates $(2j, 3i+1)$:

        * for $k$ from $0$ to $n-1$, four tiles:
        - in coordinates $(2j, 3i+2)$, two possible tiles, encoding $x\_j$ or $\overline{x\_j}$:
        - in coordinates $(2j+1, 3i)$, encoding $x\_j$ or $\overline{x\_j}$, but no restriction on the left:
        - in coordinates $(2j+1, 3i+1)$:

        * for $k$ from $0$ to $n-1$, four tiles same as $(3i+1, 2j)$, but the restriction on the right depends on the vertical color:
        - in coordinates $(2j+1, 3i+2)$, if the clause $C\_i$ is $(x\vee y\vee z)$ ($x$, $y$ and $z$ being litterals), then three possible tiles:

Since the number of tiles is $(8n+9)mn$ and the dimension of the rectangle are $3m$ and $2n$, this input is constructible in polynomial time of the size of $\varphi$.

Now let us prove that the reduction is correct.

Suppose that $\varphi$ is satisfiable, and $\mu:\mathcal{V}\to \\{0, 1\\}$ a boolean assignment satisfying $\varphi$. Then it is possible to cover a rectangle of size $N\times M$ using tiles of $T$:

* for coordinates $(2j, 3i)$, $(2j, 3i+2)$ and $(2j+1, 3i)$, choose the tile of the litteral of value $1$ for $\mu$;
* for coordinates $(2j, 3i+1)$ and $(2j+1, 3i+1)$, choose the tile that can be put on the right of the previous one, with vertical color of a litteral satisfying the clause $C\_i$;
* for coordinates $(2j+1, 3i + 2)$, choose the only tile that can be put.

Conversely, if there is a possible tiling of a rectangle of size $N\times M$, then the first column gives a satisfying assignment of $\varphi$:

* the row $2j$ has the same horizontal color and insures that a variable cannot have two boolean assignments;
* the column $3i+1$ has the same vertical color, and the coordinates $(2i+1, 3i+2)$ has necessarily that same color (which is a satisfying litteral for $C\_i$);
* other tiles are for verification purposes.

Here's a possible tiling for the formula $(x\_1\vee \overline{x\_2}\vee x\_4)\wedge (x\_2 \vee x\_3\vee \overline{x\_4})$ (which is satisfiable).

---
Tags: complexity-theory, np-complete, np, satisfiability
---


# Question
Title: Efficiently Taking the Sums of all Pairs of Elements from a Set
I have a set of numbers and I want to find the sums of all possible pairs of elements. With the set $\\{1, 2, 3\\}$ for example, I would want $\\{1+2, 1+3, 2+3\\}$ as my answer. I could do that in n^2 time complexity by starting at the first element and adding all the other elements to it one-by-one and then moving to the second element, but is there an algorithm that would compute all the sums in a better time complexity?

# Answer
> 0 votes
Since the output could be of size $\Omega(n^2)$ for a set of size n, I doubt there is a better algorithm for the general case.

For example, consider $S = \\{1, 2, 4, …, 2^{n-1}\\}$. For $\\{i, j\\} \neq \\{k, \ell\\}$, $2^i+2^j \neq 2^k+2^{\ell}$, so the output will be of size $\frac{n(n-1)}{2}$.

---
Tags: time-complexity, summation
---


# Question
Title: What are some examples of problems in R but not in PR?
Also are there any R complete problems? These would be the hardest decidable problems to my knowledge. Sorry if this isn't specific enough.

# Answer
PR class is associated with primitive recursive functions but not every total recursive function is a primitive recursive function. The most famous example of such functions is the Ackermann function. If you need to specify a decision problem then you can use e.g. the language $L\_{A} =\\{ \langle m,n,k\rangle \mid m,n,k \in \mathbb{N}, A(m,n) \le k \\} \subset \\{0,1\\}^{\*}$, (A - Ackermann function and e.g. $\langle m,n,k\rangle = 1^{m}0^{n}1^{k}$ or use any other encoding scheme). In this way you can build other examples including partial recursive functions (assuming that $\bot \< 0 $) which are also not in PR. Class R is closed under $\le\_{m}$ reduction but any non-trivial language in R is R-complete under this reduction so you need to use some stronger reduction to find a specific set of the hardest problems in R.
> 2 votes

---
Tags: complexity-theory, time-complexity
---


# Question
Title: Find $k$ numbers that satisfy a condition from a sorted sequence
> Suppose given $T= a\_1\leq a\_2\leq\dots\leq a\_n $ that $a\_i$ is real number and given a number $k$. we want to find $k$ triples $x\_i\leq y\_i\leq z\_i\in T$ such that $$\sum\_{i=1}^ k (y\_i-x\_i)^2$$ minimized, also each $a\_i$ can belong to at most one triple.

How we can solve above problem in $O(nk)$? I think it's possible to use Dynamic programming but i can't find a recurrence relation for my problem. Above problem belong to my final exam that our TA didn't solve it for us and i want how we can solve it.

# Answer
Note that to minimize the sum, you can always chose $x\_i$ and $y\_i$ to be consecutive in $T$. The choice of $z\_i$ only obliges you to have enough "big values" after having chosen $x\_i$ and $y\_i$.

I think you could do some dynamic programming using a function like the following:

For $i = 1$ to $n-1$ and $\ell = 0$ to $k$, define $F(i, \ell)$ as the couple composed of:

* the set $S$ of $\ell$ values among $\\{1, 2, …, i\\}$ that minimizes $\sum\limits\_{j\in S} (a\_{j+1}-a\_j)^2$;
* the number of values that still need to be chosen among $\\{a\_{i+1}, …, a\_n\\}$ for $z\_1$, …, $z\_i$.

The second point is a bit informal and corresponds to the "big values" still needed after chosing as much as possible among $\\{a\_1, …, a\_i\\}$.
> 1 votes

---
Tags: algorithms, dynamic-programming
---


# Question
Title: Is the union of two CFLs minus their intersection a CFL?
I've seen the classical proofs of CFLs are not closed under intersection or complement, but I haven't been able to wrap my head around this. Intuitively, I think that this would be not a CFL but I can't think of any counterexamples.

# Answer
> 2 votes
If one of the languages is $\Sigma^\*$, what is the union minus the intersection?

Hope that gives you ideas.

---
Tags: context-free
---


# Question
Title: Why can't a LR(0) parser have GOTO and Reduce Items in the same canonical set?
I am talking in reference to this question from this compiler test. I think it is actually true that a GOTO and REDUCE can't be present in the same set, but am having a hard time coming up with an example or counterexample.

Pls provide and example and explanation to make me understand.

https://gateoverflow.in/299820/Go-compiler1-parsing-5

# Answer
> 1 votes
This isn't what you asked, but let me start by saying that I suspect the answer they're looking for in the question you link is (D), "A LR(0) parser can parse any regular grammar".

That statement is clearly false; an LR(0) grammar can only parse languages with the "prefix property", which holds if no sentence in the language is a prefix of another sentence in the language. Many regular languages do not have the prefix property, including, for example, $\\{a, aa\\}$. (You can create an augmented language by adding an explicit end-of-input marker –conventionally written $\\\\$$– to the end of every sentence. The language thus augmented is regular and has the prefix property. That still doesn't let you parse "any regular grammar" with LR(0); it just means that every augmented regular language has an LR(0) parser, which is quite a different statement.)

An LR(0) automaton has no lookahead; that's what the $(0)$ means. So if a language includes $u$ and $uv$, where $|v|\ge 1$ (in other words, it does not have the prefix property), then once the parser reads $u$, it cannot decide whether to accept or continue.

Another consequence of not having any lookahead is that if a REDUCE action is available in a state, it must be unconditional. No SHIFT action is possible for that state (that would be a shift/reduce conflict) and no other REDUCE action is possible (that would be a reduce/reduce conflict). None of those restrictions immediately implies the action of GOTO actions, though.

It's pretty common to see two claims about LR(0) grammars:

1. "If a reduce item is present in a LR(0) itemset it cannot have any other item." (That's option C from the question you linked to, with a small vocabularly change.)
2. "No grammar with an empty production can be LR(0)." (That's somewhere in the discussion of the question.)

In fact, neither of the above claims are strictly true. Consider the following simple grammar: $$\begin{align}S&\to M A\\ M&\to\\ A&\to a \end{align}$$

That grammar recognizes the language $\\{a\\}$, which is not a particularly interesting language, other than as an example. Of course, that *language* is LR(0) –any language whose sentences are all the same length are LR(0). That doesn't mean that all grammars for that language are LR(0), but the above grammar certainly is; here's the LR(0) state machine generated by the grammophone tool, which happily classifies the grammar as LR(0):

Looking at that state machine, it's evident that state 0 has a REDUCE action ($M\to$) and two GOTO actions, one on $M$ and the other on $S$. (Of course, it has no SHIFT actions. In an LR(0) grammar, the generated parser can't have both REDUCE and SHIFT actions in the same state.)

(Perhaps it's worth noting that you can tell what types of actions are possible for a state by looking at the symbol following each • in the itemset: if the • is at the end of a production, there is a REDUCE action; if the • comes before a terminal, there is a SHIFT action, and if the the • comes before a non-terminal, there is a GOTO action.)

Certainly, the "marker" non-terminal $M$ contributes nothing to the recognition of sentences. We could simply remove $M$ from the grammar without doing anything more than deleting every reference to it in every production, and if we did so, there would no longer be a reduction action for it.

The point of marker non-terminals is to attach some syntax-directed semantic action to a production which is evaluated before the production is reduced. (Parser generators which provide this facility automatically call these "mid-rule actions".) Marker non-terminals are always ε-productions, and they don't necessarily invalidate the LR(0) property. But they are not essential for recognition, and so possibly there is some way of rephrasing the "no ε-production" criterion which more precisely characterises LR(0) grammars. I haven't seen one, though, and my inclination is to think that the GATE question is not really correct (and it wouldn't be the first GATE question I've seen which has led me to think that).

---
Tags: compilers, parsers, lr-k
---


# Question
Title: The maximum matching of a bipartite graph $(S, T)$ is $|X|+\min\limits_{A \subseteq X} (\min\{0, |N_G(A)|-|A|\}$, where $X \in \{S, T\}$?
Here is the full version of the problem I'm dealing with.

> Let $G=(S,T;E)$ be a bipartite graph and let $X$ be one of the two classes of its bipartition (i.e., $X \in \\{S,T\\}$). For a subset $C \subseteq X$ we define: $$\sigma(C)=\min\\{0, |N\_G(C)|-|C|\\},$$ where $N\_G(C)$ is the neighbourhood of the subset $C$ in $G$) (note: $\sigma(\varnothing)=0$). We also define $\xi(S)=\min\limits\_{A \subseteq S} \sigma(A)$ and $\xi(T)=\min\limits\_{B \subseteq T} \sigma(B)$.
> Prove that $$\nu(G)=|S|+\xi(S)=|T|+\xi(T),$$where $\nu(G)$ is the size of a maximum matching in $G$).

The case in which $G$ has a perfect matching is easy to prove, but I'm having trouble with how to approach the other cases.

Using Hall's theorem, I can prove one half of the equality at a time (i.e., either $\nu(G)=|S|+\xi(S)$ or $\nu(G)=|T|+\xi(T)$) but when it comes to proving the other one, I'm lost. I thought about modifying $G$ by adding additional nodes and edges until it has a perfect matching and then proving the property for this new graph, let's say $G'$, but I'm unsure as to how that translates to my main graph $G$.

# Answer
You are on the right track. What you need is a nice way to construct $G'$ so that "the property for this new graph" can be translated to $G$ easily.

Here is my full proof.

---

Given the setup as in the question, let us prove $$\nu(G)=|S|+\xi(S).$$

* By definition of $\xi(S)$, there is some subset $C\_0$ of $S$ such that $N\_G(C\_0)= |C\_0| + \xi(S)$.

+ Any matching between $C\_0$ and $T$ can have at most $N\_G(C\_0)$ edges.
    + Any matching between $S\setminus C\_0$ and $T$ has at most $|S\setminus C\_0| = |S| - |C\_0|$ edges.

Hence any matching between $S$ and $T$ has at most $N\_G(C\_0) + (|S| - |C\_0|)= |S| +\xi(S)$ edges. That is, $\nu(G)\le |S| + \xi(S)$.
* Construct a new bipartite graph $G'=(S, T'; E')$, where $T'$ is $T$ with $-\xi(S)$ additional nodes and $E'$ is $E$ with $|S|\times (-\xi(S))$ additional edges that connect every node in $S$ with every additional node.
We can check that $G'$ satisfies Hall's condition, that is, for every subset $C\subseteq S$, we have $N\_{G'}(C)\ge |C|$.
Hence there is $m'$, a matching of $G'$ that matches each node in $S$ with a node in $T'$.
Remove the edges in $m'$ that end at additions nodes, we obtain a matching of $G$, which has $|S| - |{-}\xi(S)| = |S| + \xi(S)$ edges since $-\xi(S)$ edges are removed.
So, $\nu(G) \ge |S|+\xi(S)$.

---

Switching $S$ and $T$, we obtain $$\nu(G)=|T|+\xi(T).$$ $\checkmark$
> 2 votes

---
Tags: matching, bipartite-matching, bipartite-graph
---


title: Minimum spanning tree vs Shortest path

text:
# Question
Title: Minimum spanning tree vs Shortest path
What is the difference between minimum spanning tree algorithm and a shortest path algorithm?

In my data structures class we covered two minimum spanning tree algorithms (Prim's and Kruskal's) and one shortest path algorithm (Dijkstra's).

Minimum spanning tree is a tree in a graph that spans all the vertices and total weight of a tree is minimal. Shortest path is quite obvious, it is a shortest path from one vertex to another.

What I don't understand is since minimum spanning tree has a minimal total weight, wouldn't the paths in the tree be the shortest paths? Can anybody explain what I'm missing?

Any help is appreciated.

# Answer
> 60 votes
You are right that the two algorithms of **Dijkstra** (shortest paths from a single start node) and **Prim** (minimal weight spanning tree starting from a given node) have a very similar structure. They are both greedy (take the best edge from the present point of view) and build a tree spanning the graph.

The value they minimize however is different. Dijkstra selects as next edge the one that leads out from the tree to a node not yet chosen closest to the starting node. (Then with this choice, distances are recalculated.) Prim choses as edge the shortest one leading out of the tree constructed so far. So, both algorithms chose a "minimal edge". The main difference is the value chosen to be minimal. For Dijkstra it is the length of the complete path from start node to the candidate node, for Prim it is just the weight of that single edge.

To see the difference you should try to construct a few examples to see what happens, That is really instructive. The simplest example that shows different behaviour is a triangle $x,y,z$ with edges $\\{x,y\\}$ and $\\{x,z\\}$ of length 2, while $\\{y,z\\}$ has length 1. Starting in $x$ Dijkstra will choose $\\{x,y\\}$ and $\\{x,z\\}$ (giving two paths of length 2) while Prim chooses $\\{x,y\\}$ and $\\{y,z\\}$ (giving spanning tree of weight 3).

As for **Kruskal**, that is slightly different. It solves the minimal spanning tree, but during execution it chooses edge that may not form a tree, they just avoid cycles. So the partial solutions may be disconnected. In the end you get a tree.

# Answer
> 55 votes
Consider the triangle graph with unit weights - it has three vertices $x,y,z$, and all three edges $\\{x,y\\},\\{x,z\\},\\{y,z\\}$ have weight $1$. The shortest path between any two vertices is the direct path, but if you put all of them together you get a triangle rather than a tree. Every collection of two edges forms a minimum spanning tree in this graph, yet if (for example) you choose $\\{x,y\\},\\{y,z\\}$, then you miss the shortest path $\\{x,z\\}$.

In conclusion, if you put all shortest paths together, you don't necessarily get a tree.

# Answer
> 18 votes
Though Minimum Spanning Tree and Shortest Path algorithms computation looks similar they focus on 2 different requirements.

In MST, requirement is to reach each vertex once (create graph tree) and total (collective) cost of reaching each vertex is required to be minimum among all possible combinations.

In Shortest Path, requirement is to reach destination vertex from source vertex with lowest possible cost (shortest weight). So here we do not worry about reaching each vertex instead only focus on source and destination vertices and thats where lies the difference.

Here is the example to clarify why MST not necessarily gives shortest path between 2 vertices.

```
(A)----5---(B)----5---(C)
 |                     |
 |----------7----------|

```

In MST case, edges A-B. B-C will be on MST with total weight of 10. So cost of reaching A to C in MST is 10.

But in Shortest Path case, shortest path between A to C is A-C which is 7. A-C was never on MST.

# Answer
> 12 votes
I think an example will make it clearer..

The spanning tree looks like below. This is because if we add up the edges in this configuration, we get the **least total cost possible**: 2+5+14+4=25.

```
(1)   (4)
  \   /
   (2)
  /   \
(3)   (5)

```

By eyeballing the spanning tree you might falsely think that it gives you the shortest paths, but in practice it doesn't. As an example If we wanted to go from node `(1)` to `(4)` it would cost us 7. However if we used Dijkstra's algorithm on the original graph, we would find that we can go directly from node `(1)` to `(4)` with a cost of `5`.

# Answer
> 9 votes
The difference lies in what is the ultimate goal of this algorithms-

Dijkstra's - Here the goal is to reach from start to end. You are concerned about only this 2 points, and optimize your path accordingly.

Krusal's - Here you can start from any point and have to visit all other points in the graph. So, you may not always choose the shortest path for any two points. Instead the focus is to choose the path that will lead you to a shorter path for all the other points.

# Answer
> 4 votes
The key is to understand that they are different problems: The spanning tree looks to visit *all* nodes in one "tour", while shortest paths focuses on the the shortest path to *one* node at a time.

As an example, imagine you know the shortest route from your home to two different places A and B. Since the graph is directed, you can get to B from A but not vice versa. In this case, the route Home -\> B is shorter than Home -\> A -\> B, so you're allowed to skip A. But for spanning trees, you *must* visit all nodes, so Home -\> A -\> B is the solution (Assuming that Home -\> B -\> A is more expensive than Home -\> A -\> B.

# Answer
> 2 votes
Consider a simple example You are building a food delivery app, You want the driver to deliver food to all customers by covering the distance in optimal way with minimum possible time and fuel If you want to cover all the locations, you need minimum spanning tree. If you are targeting only a single location, you need the shortest path.

The shortest path will not guarantee covering all the vertices ( reaching to all the customers in the above example ). To cover all the customers, you have to find minimal spanning tree.

# Answer
> 1 votes
I think minimum spanning tree algorithm aims to extract a tree whose overall cost is minimized and it doesn't care about the minimum distance from a single node to the starting node, which is exactly what shortest path aims at. And that's why Prim colors the node which has minimum distance to any one of the colored nodes, while Dijkstra colors the node with minimum distance to the starting node.

# Answer
> -1 votes
They are based on two different properties. Minimum spanning tree is based on cut property whereas Shortest path is based on the edge relaxing property.

A cut splits a graph into two components. It may involve multiple edges. In MST, we select the edge with the least weight.

Edge relaxing says that given I know distance between A and B: dist(a,b) and dist between A and C: dist(a, c), if dist(a, b) + edge(b, c) is less than dist (a, c), then I can relax edge(a c). After relaxing all edges, we get the shortest path.

I highly recommend watching the video on graph algorithms from professor Robert Sedgewick.

# Answer
> -2 votes
Practical example to show the difference\>

Suppose you arrive by train in a town and want to get to your hotel.

Option 1: Get a taxi: The taxi will take the shortest path to you hotel form the station. If the driver should follow a path along the shortest path tree centred on the station.

Option 2: Take a bus. The bus company wants to cater for may people, not just you. The ideal path would take in all the key points in the town. So it will follow (\*) a path along the minimum spanning tree. That's why the bus is slower, but as costs are shared it is cheaper.

(\*) Actually people would complain if the minimum spanning tree was used (the bus journey would be too long). So in practice it would be a mixed solution and would use an Alpha-Tree (half way between a minimum spanning tree and a shortest path tree).

---
Tags: algorithms, shortest-path, spanning-trees
---


# Question
Title: What's the sum of heights of a random binary search tree
What's the sum of heights of a random binary search tree?

By a random binary search tree, I mean the usual definition: you have $n$ keys to be inserted, and all Permutations are equally likely.

The sum of heights is the sum of the heights of each node. similar to Sum of heights in a complete binary tree (induction)

My attempt: I know that a random binary tree has height $O(\log n)$, so $h = K \log n$ and the sum is bounded from above by the sum of heights of a perfectly balanced binary tree of height $k\log n$. which is $2^{k\log n} -1 = n^k - 1$. This leads me nowhere.

# Answer
According to Lemma 7.1 in these notes, if you construct a random BST on $\\{0,\ldots,n-1\\}$, then the expected depth of $x \in \\{0,\ldots,n-1\\}$ is $H\_{x+1} + H\_{n-x} - 2$, where $H\_m$ is the $m$'th harmonic number. Summing over all $x$, the expected sum of depths is $$ \sum\_{x=0}^{n-1} (H\_{x+1} + H\_{n-x} - 2) = 2 \sum\_{i=1}^n (H\_i - 1) = 2 \sum\_{i=1}^n \sum\_{j=2}^i \frac{1}{j} = \\2\sum\_{j=2}^n \frac{n-j+1}{j} = 2(n+1)(H\_n - 1) - 2(n-1), $$ which is $2n\ln n - O(n)$.
> 1 votes

---
Tags: randomness, binary-search-trees
---


# Question
Title: Differences between reliability and availability using an example
My definitions of reliability and availability are as below respectively .

reliability := property of failure interval .

availability := property of occupancy rate .

I want to show the differences between reliability and availability using some example but currently I've been failing to come up with it .

I came up with the below sentence .

The system which breaks in average per hour and the system cannot be used as break occurs for 0.1 hours .

Can this expression be used to show the differences between the 2 terms?

# Answer
On a airfield on the front line, the General is woried by the reliability of its fighter aircrafts, and hence the reliability is high , the availability is due to be high, . On the other hand if the general has at its disposition a vast number of low reliable aircraft, in the echonomics of the operations, the necesary number of aircraft required for missions, may be available.

You can take this concept and create your own scenarious involving the General and its aircraft fighters, and see if and when reliability and/or availability is a cost worth taking.
> 0 votes

---
Tags: operating-systems
---


# Question
Title: Counting number of swaps to make two strings equal in linear time
The input to our problem is a pair of strings, say $x$ and $y$. We treat our alphabet size as a constant, i.e., our input is effectively a pair of arrays with the values therein bounded by a constant.

The problem is to compute the number of adjacent swaps (done to either of the strings), to make the strings equal. It is easy to see that our problem is equivalent to making $y$ equal to $x$.

One simple approach that I can think of is that we can first compute the appropriate permutation that makes $y$ into $x$ (easy to do in linear time) and then count number of inversions therein. Straightforward algorithms for inversion counting yield us $\mathcal{O}(n \lg n)$ overall running time. Chan and Pătraşcu show that this can be improved to $\mathcal{O}(n\sqrt{\lg n})$ if we use the fact that we deal with the special case of a permutation.

However, in the case of strings, we still have a bit more information than in the aforementioned case: our permutation comes from a pair of arrays with a constant number of possible values, whereas in the case of a permutation, the numbers can be $\mathcal{O}(n)$.

For example, in the case of a binary alphabet, I believe that the maximum number of swaps needed (inversions) is $\frac{n(n-1)}{4}$, so half the number possible in case of an arbitary permutation.

Moreover, in the case of equal number of zeros and ones (which I'm guessing would be the most complicated one), we have only ~ ${n\choose{n/2}} = \frac{n!}{\left(\frac{n}{2}!\right)^2}$ possible inputs to our algorithm, instead of $n!$. Correspondingly, we have $\lg\left(\frac{n!}{\left(\frac{n}{2}!\right)^2}\right) = \Theta(n)$, in contrast to $\lg(n!) = \Theta(n\lg n)$. Therefore, simple counting lower bounds similar to that question would also not seem to apply.

Are better algorithms known for this special case?

# Answer
The answer is yes, as a linear-time algorithm is possible if the alphabet size is constant. I explain a $\Theta(k n)$-time algorithm here, where $k$ is the size of the alphabet.

It is easier to see the problem if the permutation is represented as a bipartite graph on the plane, like this image (ignore the upper graph). The edge set is $E = \\{(i,p\_i)\\}\_i$. The inversions are same as intersections between two edges: $\\{ (i,p\_i), (j, p\_j) \in E \mid i \< j \land p\_i \> p\_j \\}$.

First, notice that if the edge set is partitioned into $k$ sets for each alphabet, then each edge subset is *monotone*. That is, two edges can only intersect between different alphabets. Let $E^a$ to denote the edge subset of alphabet $a$.

We can count the number of intersections between two edge subsets $E^a, E^b$ in a linear time. The algorithm iterates the edges in a subset $E^a$. The edges in $E^b$ intersecting to an edge in $E^a$ can be represented as a (possibly empty) interval. Furthermore, the endpoints of the intervals can only go up during the iteration. Thus, by maintaining the endpoints of the intersecting interval, this subproblem can be solved in $\Theta(|E^a| + |E^b|)$ time.

Pseudocode is as follows:

```
def count_intersections(as, bs):
  # Loop invariant: (l, r) are endpoints of the intersecting interval such that
  # (l <= j < r) if and only if as[i] and bs[j] intersect.
  l, r = 0, 0
  total = 0
  for i in 0..len(as):
    while r < len(bs) && bs[r].1 < as[i].1:
      r += 1
    while l < r && !(as[i].0 < bs[l].0):
      l += 1
    total += r - l
  return total

```

The answer is the sum of all answers of such subproblems for each pair of edge sets. Because each edge occurs in at most $k$ subproblems, and the edge sets can be constructed in $O(n + k)$ time, the running time of the algorithm is $O(k n)$.
> 1 votes

---
Tags: complexity-theory, asymptotics, strings, lower-bounds, permutations
---


# Question
Title: How to match two point sets to minimize total distance?
Let's say we have two sets $X = \\{x\_1, \ldots, x\_n\\} \subset \mathbb R^d$, $Y =\\{y\_1,\ldots, y\_n\\} \subset \mathbb R^d$, how can we find a permutation $\pi$ such that

$$D = \sum\_{i=1}^n d(x\_i, y\_{\pi(i)})$$

is minimal? (Here $d$ is some distance function, for simplicity we can assume it is the Euclidean distance, or maybe the squared euclidean distance.)

As far as I remember this is a well studied problem, but can anyone tell me what it is called?

# Answer
> 6 votes
This is an instance of the assignment problem and can be solved with standard algorithms for that problem.

# Answer
> 3 votes
The planer (d = 2) version of the problem is called in several names such as *Euclidean bipartite matching problem*, *Euclidean bichromatic matching problem*, or *Bipartite matching of planar points*. The fastest known exact algorithm in the real RAM model is the $O(n^{2+\delta})$ time ($\delta \> 0$ is an arbitrary constant) algorithm due to Agarwal et al \[1\]. There are faster constant-factor approximation algorithms \[2\]. There is a sub-quadratic algorithm if the coordinates are bounded integers \[3\].

In general metric, the problem is also called as *Earth mover's distance* (EMD) or *Optimal transport*. Usually, EMD is formulated for a probabilistic distribution, but here we are concerned with a discrete distribution. Recently, both multiplicative and additive approximation algorithms are developed. Lahn et al \[4\] provide a great overview of the recent results.

* \[1\] Agarwal, Pankaj K., Alon Efrat, and Micha Sharir. "Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications." SIAM Journal on Computing 29.3 (2000): 912-953.
* \[2\] Indyk, Piotr. "A near linear time constant factor approximation for Euclidean bichromatic matching (cost)." SODA. Vol. 7. 2007.
* \[3\] Sharathkumar, R. "A sub-quadratic algorithm for bipartite matching of planar points with bounded integer coordinates." Proceedings of the twenty-ninth annual symposium on Computational geometry. 2013.
* \[4\] Lahn, Nathaniel, Deepika Mulchandani, and Sharath Raghvendra. "A graph theoretic additive approximation of optimal transport." Advances in Neural Information Processing Systems (2019): 13813–13823.

---
Tags: graphs, matching, bipartite-matching
---


# Question
Title: Why is a 4 KB alignment requirement imposed on Intel Core i7 page tables for Linux
I'm reading CSAPP and couldn't wrap my head around this part:

Summary of what the section says:

* Intel Core i7 support a 48-bit virtual address space and 52-bit physical address space.
* Core i7 uses a four-level page table hierarchy.

Then the book shows a picture of the breakdown of a PTE:

Please note the 40-bit PPN.

It goes on to say that "*the 40-bit PPN points to the beginning of the appropriate page table. **Notice that this imposes a 4 KB alignment requirement on page tables***".

My question is what does the bolded line mean? And why there is a 4 KB alignment requirement? I know (theoretically) how virtual memory and page tables work but don't get this alignment requirement.

To further explain my confusion: What does it mean to say "*...alignment requirement on page tables*"? Does it mean that the PTE has to be 4KB in chunk (this was described a page before and doesn't really seem to need any further proof), or something else?

# Answer
> 23 votes
The physical address for the start of a page frame or page table is obtained by taking the 40-bit PPN and appending 12 zero bits. That gives you a 52-bit physical address, which is the start of the frame or page table.

A consequence is that frames or page tables must start at a physical address that is a multiple of $2^{12}=4096$, i.e., that is aligned at a multiple of 4KB.

# Answer
> 11 votes
Alignment is required for page tables because there's literally nowhere to store the low address bits.

The bottom 12 bits of a page directory entry is flags like present, accessed, user/supervisor, whether this is actually a largepage instead of a pointer to a page table, etc. https://wiki.osdev.org/Paging#64-Bit\_Paging. Similar for the higher 2 levels of tables; see Why in x86-64 the virtual address are 4 bits shorter than physical (48 bits vs. 52 long)? for official names for different levels, and a nice diagram of how x86-64 4-level page tables work.

In theory the top-level page table pointer (set with `mov cr3, rax` or whatever) does have a full 64 bits, but the low 12 bits are ignored / reserved. Or with a control-register setting, repurposed as process-context ID (PCID) to tag non-global TLB entries so they can survive across CR3 updates, making frequent context switches somewhat less bad.

---

There'd be very little reason to want a misaligned page table, and it does simplify the HW: the physical address can just concatenate some bits together instead of adding with possible carry into the page-number bits. And since virt-\>phys mappings happen in aligned 4k blocks, free physical memory in *aligned* 4k blocks is what you want to track anyway.

(And with paging enabled, load/store instructions the kernel executes in functions that read and/or update page tables can only use virtual addresses. An aligned 4k of phys memory can be addressed through one virtual 4k page, instead of maybe costing the kernel multiple TLB misses when accessing 4kiB split across two virtual pages. Many kernels such as Linux will direct-map all of physical RAM, or large chunks of it, with 1G hugepages, but still...)

---

**Actual physical pages (page frames) should always be aligned**, so the offset-within-page virtual address bits are also the physical offset-from-4k-boundary address bits. Among other things, that lets an L1d cache have the speed of VIPT (indexing based on bits from the virt addr) without any aliasing problems if the cache is small enough and associative enough. The bits below the page offset effectively translate for free, without the TLB, so such a VIPT cache is effectively PIPT.

It also means two virtual pages can't *partially* overlap; they either map to the same physical page or not. (Not counting largepage / hugepage). And it would make each TLB entry larger, which is a Bad Thing. e.g. on an early x86-64 with 40-bit physical addresses, a 4k page's TLB entry only needs 28 bits of physical address, instead of 37 if we had only 8-byte alignment.

**So that means an actual PTE shouldn't waste space on low address bits. Having a page *directory* entry use an identical format makes a ton of sense.**

There are actually 11 unused high bits above the highest reserved bit (#52) in a PTE/PDE, so there actually is room if we didn't care about leaving more unused space for OSes to keep bookkeeping data. (They're fully ignore by HW.) So the HW page table design could have left only 3 physical bits implicitly zero (8-byte alignment), while still allowing up to 52-bit physical addresses, if anyone had thought that was worth doing.

Either by left-shifting the phys address field, or keeping flags at the top. Low bits are more efficient for software to manipulate on x86-64. But there's no good reason to make HW throw those bits around at all.

PAE and thus x86-64 use the same flag-bit layout at the bottom of each entry as 32-bit legacy page-tables (4 bytes per PTE, 2x 10-bit levels mapping 32-bit virt -\> 32-bit phys which only had 3 unused PTE bits, in bits \[11:9\]).

One of AMD's major goals was to reduce barriers to entry, making porting of OSes and toolchains easier, to increase the chance of getting traction and not becoming dead weight in their CPUs. Also keeping HW as similar as possible so they could share transistors in decoders and so on, which meant not fixing many x86 warts. Fortunately Intel's PAE format is very reasonable, so they could literally use it directly, just adding 2 more levels.

# Answer
> 2 votes
What's not shown in the little bit assignment table you looked at is:

1. The bits 51:12 of the PTE are *also* bits 51:12 of the **page table address**.
2. The complete page table address consists of bits 51:12 of the PTE in bit positions 51:12, and zeroes elsewhere.

Perhaps this picture will make it clearer:

---
Tags: computer-architecture, virtual-memory
---


# Question
Title: If someone has an encrypted message and it's original plaintext, could he guess the private key if it's the one used to encrypt the message?
In digital signatures, the private key is used to encrypt a (hashed) message and the public key is used to decrypt it. This made me wonder since the receiver has the cipher text (digital signature) and can easily reach the original plain text— by decrypting the digital signature using the sender's public key— if there is a way for him to guess the private key given the cipher text and its plain text.

# Answer
> 4 votes
There is a big confusion here;

> **In digital signatures, the private key is used to encrypt a (hashed) message and the public key is used to decrypt it.**

In a digital signature, we have a signature algorithm ($\mathsf{Sign}$) and a signature verification algorithm ($\mathsf{Vrfy}$). For the digital signature algorithm, the private key is used, and for the signature verification algorithm, the related public key is used.

**There is no encrypt and decrypt in Digital signatures** The common confusion comes from the RSA where it is one of the rare and simple systems that can be used for encryption/decryption and signature/verification.

This is true in the textbook RSA which is in no way secure. The encryption needs proper paddings like PKCS#1 v1.5 (RSAES-PKCS1-v1\_5) or OAEP (RSAES-OAEP) padding. For signature, one needs the PSS ( RSASSA-PSS). Follow the links from rfc8017 or read the from Cornell University's web page for this;

**Hashing before** a signature is also part of the secure signature scheme since the first true digital signature scheme, Rabin Signature. We don't prefer the term hash-then-sign paradigm since **it is part of the security**.

> **This made me wonder since the receiver has the ciphertext (digital signature) and can easily reach the original plain text— by decrypting the digital signature using the sender's public key— if there is a way for him to guess the private key given the ciphertext and its plain text.**

**The security of the signature scheme is not about accessing the message it is about forging a signature**. i.e given $(\sigma\_i,m\_i)$ pairs, the adversary must find another pair $(\sigma',m')$ such that $\mathsf{Vrfy}(\sigma',m')$ must return valid signature where $m\_i \neq m'$.

As we can see this is not talking about the encrypted message. This doesn't mean that we cannot sign encrypted messages, this is about the formal security game of the signature schemes and see some variants on Wikipedia

As we talked about earlier, the message is hashed for the signature therefore even you somehow access the hash of the message due to the very weak signature scheme you need to break the pre-image resistance of the applied hash function. All cryptographic hash functions including the MD5 and SHA-1 , where they have been broken in their collision resistance, are still pre-image resistant for any power in the near future and you will not have luck there for 256-bit output hash function even a Cryptographic Quantum Computer is built, the best they can have the Brassard's optimization over Grovers with around $2^{85}$-time and $2^{85}$-space. Using a hash function with 512-bit output is clearly quantum-safe ( this is applicable to$\left(\mathsf{Enc}(m)\mathbin\\| \mathsf{sign}(m)\right)$ that we don't prefer.)

What you saying is the **total break of the signature scheme** where the attacker **also gains the private key**. There are example signature scheme that has a total break given many $(\sigma\_i,m\_i)$ pairs;

Still, this doesn't give access to the message since we usually encrypt-then-sign. What you will get the signature key and even in the RSA case one needs two sets of keys; **one for encryption and one for signature**. We don't reuse the keys that are used for different aims.

**What you need to access the message is the break of the encryption scheme that usually AES-256 and ChaCha20-256** in nowadays and both are secure against Grover's algorithm, too.

**AES with a proper mode of operation like CTR and CBC is Ind-CPA secure.** ChaCha has a built-in CTR mode. More than IND-CPA we need integrity and currently, all cipher suites of TLS 1.3 use Authenticated Encryption Modes with Associated Data (AEAD) like AES-GCM and ChaCha20-Poly1305 (and AEAD \> Ind-CCAx).

**As long as the cipher suites are correctly used, the task is almost impossible.**

---

In RSA case, RSASSA-PPS is probably secure.

---

We don't have Ind-CPA or Ind-CCAx security for the signature schemes, those are for encryption. We have SUF-KMA or EUF-KMA like security games for the signature schemes.

> **If someone has an encrypted message and it's original plaintext, could he guess the private key if it's the one used to encrypt the message?**

In public-key scheme, the encryption oracle is free, that is once you know the target public key, then you can get as many as (plaintext, ciphertext) pairs as you want ( well polynomially bounded) then work on breaking the system. This simply implies that we need at least **Ind-CPA** secure public-key cryptosystem for encryption.

**RSA can achieve Ind-CPA with the proper paddings**. Many tried to break this ( yes we have come a long way \[1\]\[2\]\[3\]) but there is no failure if the proper padding scheme is used and implemented correctly. Any public key cryptosystem that fails to satisfy Ind-CPA is a direct way to the graveyard of broken schemes.

While using RSA for information encryption, your biggest concern is the GCD attack. Have a good random number generator to mitigate this.

And, **keep in mind that** we mostly use RSA for signatures. In general, we use hybrid-cryptosystems where the key exchange is performed with a public-key cryptosystem, and data encryption is performed with asymmetric system. One can use

* RSA-KEM with AES-GCM/ChaCha20-Poly1305
* DHKE with AES-GCM/ChaCha20-Poly1305
* Integreted Encryption Scheme (IES): Discrete Logarithm Integrated Encryption Scheme (DLIES) and Elliptic Curve Integrated Encryption Scheme (ECIES)

There are broken schemes or still safe schemes so future safe schemes against quantum attacks ( RSA and ECC is gone with that, welcome back Supersingular curves) that we did not list here.

---

**Abbreviations**

* IND-CPA: INDistinguishability under Chosen Plaintext Attack
* IND-CCA1: INDistinguishability under Chosen Ciphertext Attack
* IND-CCA2: INDistinguishability under adaptive Chosen Ciphertext Attack
* IND-CCA3: (authenticated) INDistinguishability under adaptive Chosen Ciphertext Attack

# Answer
> 2 votes
This is known as chosen plaintext attack, or at least known plaintext attack if he can't choose the plaintext.

Any real-world algorithm will of course have to protect against this kind of attack.

---
Tags: cryptography, encryption
---


# Question
Title: Is $\{\emptyset,a,\epsilon\}$ an algebraic structure with respect to $+$?
Let $R = \\{\emptyset,a,\epsilon\\}$ (the elements here are regular expressions) and let $+$ be the *or* operation, which can be applied over the regular expressions of $R$. Is $(R,+)$ some kind of an algebraic structure, such as a subgroup, a monoid, or a group?

I was told that it is monoid and that $(a+\epsilon)=a$, and so $R$ is closed under $+$. But if $R$ is a set of regular expressions then $(a+\epsilon)$ is itself a regular expression and it does not belong to $R$, so $R$ should not be closed under the $+$ operation. So is $R$ an algebraic structure or not? Please correct me if I am understanding it wrong.

# Answer
In all algebraic structures I am aware of, the set $R$ should be closed under the operation $+$. While you haven't provided a clear definition of $+$, there is no reasonable definition of $+$ which makes $R$ closed under $+$, since $a + \epsilon$ (interpreted either as a regular expression or as a language) does not belong to $R$.

If we add $a + \epsilon$ to $R$ and interpret $+$ as union of *languages*, then $R$ does become closed under $+$, and we can ask whether it satisfies the axioms of any interesting algebraic structure. For any such structure, we just need to check whether all axioms are satisfied. This is something that you can do on your own.
> 1 votes

---
Tags: discrete-mathematics, group-theory
---


# Question
Title: Archaeological Consistency: Graph Problem
So, I have an issue with the following problem (CS 161 Stanford 2013, Problem Set 2):

Suppose that you have found a collection of historical records indicating the relative order in which various people lived and died. Each record tells you one of the following:

• Person A and person B were alive at the same time.

• Person A died before person B was born.

Your task is to determine whether the historical records are consistent; that is, whether it was actually possible for all of these people to have lived and died in such a way that all of your records are accurate. Suppose that your records involve n total people and you have m records relating their lifespans.

I need to design an O(m + n)-time algorithm that determines whether or not the records are consistent with one another. The problem would be very simple if we only have statements that a person died before another person was born (we would simply need to look for a directed loop), however, the presence of statements that some people lived at the same time makes it more complex. I tried to understand what kinds of "inconsistencies" we can have, and it seems that there can be inconsistencies of the following four kinds ($A = B$ means that $A$ and $B$ lived at the same time, $A \< B$ means that $A$ died before $B$ was born:

\begin{equation} A = B ... \< = \< = ... \< E \< A \\ A \< B ... \< = \< = ... = E \< A \\ A \< B ... \< = \< = ... \< E \< A \\ A \< B ... \< = \< = ... \< E = A \end{equation} where $... \< = \< = ...$ represents some arbitrary sequence of people born after / living at the same time as the previous person. I also note that if we have two "equality signs" in a sequence after each other, this sequence cannot be a contradiction in and of itself. But I cannot see how to proceed from here.

# Answer
> 5 votes
Denote the time of birth of person $A$ by $b\_A$, and their time of death by $d\_A$, and suppose for simplicity that all of these times are different. We know that:

* For every person $A$, $b\_A \< d\_A$.
* If person $A$ died before person $B$ was born, then $d\_A \< b\_B$.
* If person $A$ and person $B$ were alive at the same time then $d\_A \> b\_B$ and $d\_B \> b\_A$, and these conditions characterize this property.

You take it from here.

---
Tags: algorithms, graphs, graph-traversal
---


title: Context switching and Program Counters

text:
# Question
Title: Context switching and Program Counters
This is a really short question and a straightforward one for anyone who knows the subject well. But its also super specific, so I can't find the answer online.

I know a program counter is saved when a context switch occurs. I can't seem to make sense of how this could happen in software. In order for the CPU to run the process that saves the program counter, it must load that program counter into the program counter register. So isn't the program counter that's suppose to be save now lost?

# Answer
> 2 votes
Good question! The answer is: this is implemented in hardware. When an interrupt occurs, the processor saves the program counter in a known place (typically, by pushing it onto the stack), then transfers control to the interrupt handler code (overwriting the prior program counter).

# Answer
> 2 votes
On x86-64, the OS sets up an interrupt descriptor table (IDT). For each device there is connected to the computer, there is one interrupt number that is reserved. This is especially true since the advent of the mandatory MSI-X capability of PCI-Express devices. Everything is PCI today. Since most devices on your computer are PCI and probably even PCI-Express, they throw interrupts using MSI-X or MSI.

MSI-X/MSI interrupts bypass the IOAPIC and throw an inter-processor interrupt. The local APIC of the CPU is programmed with memory mapped registers that are mapped into RAM to trigger a certain handler. For example, you could have an MSI-X interrupt that is mapped to interrupt number 48. When that interrupt handler runs, the OS is aware that a certain device was set to throw that interrupt so it can assume that, when this interrupt runs, it is that device which triggered the interrupt.

The scheduler mostly runs on interrupt on modern systems. The CPU pushes the RIP register (and sometimes other things) on the stack on interrupt so it allows the OS to find out what was the RIP register before the interrupt.

What is missing here is the timer. A timer can be programmed to trigger an interrupt after some time has elapsed. The OS can thus know the time slice of a process has finished and can thus call the scheduler to determine what other process will come next. The scheduler can also be called at different moments like on IO completion.

---
Tags: operating-systems
---


# Question
Title: We cannot recognize a set of languages as the language themselves
"We cannot recognize a set of languages as the language themselves" What is the meaning of the line and why we cannot do it and how is the encoding of TM is helping in that?

# Answer
> 2 votes
TMs accept *words* as input.

What this paragraph is saying is that you cannot encode arbitrary languages as finite strings (aka words), and hence you cannot easily describe a property over languages themselves (for instance, a property of "all languages that contain the empty word", is a property over languages).

Afterwards it represents a way to somewhat describe *some* of the languages: a description of a language can be defined as "any turing machine accepting (computing) that language".

# Answer
> 1 votes
Admittedly, the sentence you give is indeed a trifle obscure. Simply said, it is saying that if we have a property of a language, like "any string in the language has odd length", we can't hope to recognize the property by using a TM that will iterate over all strings of all possible languages to test, since that would clearly be an infinite input, which we know is a TM no-no.

It goes on to state a definition that works, namely given a property, we can look instead at the set of all TM descriptions of machines which accept some language that has the property.

---
Tags: complexity-theory, formal-languages, turing-machines, rice-theorem
---


# Question
Title: Undecidability of the language of PDAs that accept some ww
I'm trying to solve problem 5.33 from Sipser's *Introduction to the Theory of Computation*,

"Consider the problem of determining whether a PDA accepts some string of the form $\\{ww|w\in \\{0,1\\}^∗\\}$. Use the computation history method to show that this problem is undecidable."

I have an attempt at a solution but somehow I just feel kind of foggy on whether it's correct and would appreciate anyone finding flaws in the solution.

---

For reference, I'm trying to mimic or adapt the solution given earlier in the chapter to

$$ ALL\_{CFG}=\\{\langle G\rangle | G \text{ is a CFG and } L(G)=\Sigma^\*\\}$$

Theorem: $ALL\_{CFG}$ is undecidable.

The proof given there reduces from $A\_{TM}$ the decision problem of checking whether a TM called $M$ accepts a string called $w$. It does so by, for any fixed $M,w$, constructing a CFG $G$ which produces all possible strings if and only if $M$ accepts $w$. In particular $G$ is the CFG which generates all the strings that are NOT accepting histories for $M$ on $w$.

It then proceeds to show how to build such a $G$. For the purposes of the problem I'm asking about, I can just accept that this is possible.

---

Also for reference, there is this answer to a similar question on here: https://cs.stackexchange.com/q/6629

I particularly want to follow the textbook's guidance in order to practice this method of using a computation history, so I'm ignoring the first answer to the problem. However, I don't understand the answer given for computation histories. The CFG that he gives (or equivalent PDA) doesn't seem to generate strings with at least one $v!v$ if and only if $M$ accepts $w$. Supposing $M$ accepts $w$ I don't see a reason why $C\_0\\#...\\#m(C\_{2n})\\#C\_f = C\_1'\\#...\\#m(C\_n')$.

---

My solution is, like in the book's solution for $ALL\_{CFG}$, to try to use $M$ and $w$ to build a CFG such that $M$ accepts $w$ if and only if $G$ generates some string of the form $vv$. In particular $G$ is the grammar defined by the PDA $D$ which on input $x$ checks the first half to see if it's an accepting history of $M$ for $w$, and then checks the second half to see if it equals the first half. I believe each of these are things any PDA can do, and once built, $G$ will have the properties promised earlier. Am I making any mistake here?

# Answer
Your proposed idea doesn't work, because after you have checked the first half of the input with your PDA, you have popped them all so you cannot reaccess them for comparing with the second half.

The correct idea should be making a PDA that checks if odd number configurations leads to even numbered configurations in the first half and vice versa in the second half. Also, make sure the PDA handles the start and accepting state. Then convert the PDA to CFG and pass it to the decider for the language $\\{ww\\}$. Accepts if it accept and rejects otherwise.

This will work as you can show that the PDA as constructed above will recognize string of form $ww$ iff $M$ accepts $w$. This is because the parity checks of configurations only gives incomplete information, but when supplied with the fact that you have two equal computation history in some string, it tells you each half of that string is actually an accepting computation history of $M$ on $w$.
> 1 votes

# Answer
Another "cool" way to prove it is realizing that there is an immediate reduction from the Post Correspondence Problem to the problem of checking wether a CFG grammar accepts a palindrome (or equivalently checking wether 2 CFG grammars accept the same string).

Given a PCP instance; i.e. a set of tiles

$\\{ (x\_i / y\_i) \\}$ (wher $x\_i$ is the top string of the tile, and $y\_i$ is the bottom string of the tile.

Simply build the CFG grammar $G$ with productions:

$\\{ S \to AB\\} \cup \\{ A \to x\_i A a\_i \\} \cup \\{ B \to y\_i B a\_i \\} \cup \\{ A \to \epsilon \\} \cup \\{ B \to \epsilon \\}$

where $a\_i$ is a new unique terminal symbol that is associated with tile $i$

$G$ accepts a $ww$ string if and only if the original PCP problem has a solution.

And - of course - the undecidability of PCP proof uses the Halting problem and history of computation.

I found it myself after reasoning about a question on cstheory, but then I realized that it was not new :-); for further details see Post’s Correspondence Problem PCP is about context-free grammars.
> 1 votes

---
Tags: computability, undecidability
---


title: Simplifying regular expression

text:
# Question
Title: Simplifying regular expression
I'm having trouble understanding the simplification of the following regular expression

\begin{align} R = ε | 1 | (ε | 1)(ε | 1)^\*(ε | 1) = 1^\* \end{align}

In my lectures only the simplified solution was given but not the steps. I tried on my own but only came this far:

\begin{align} R & = (ε | 1) | (ε | 1)(ε | 1)^\*(ε | 1) \\ & = (ε | 1)\[ε | (ε | 1)^\*(ε | 1)\] \\ & = (ε | 1)(ε | 1)^\* \\ & = (ε | 1)^+ \end{align}

I only considered the following Kleene algebra equalities. Let $r$ be a regular expression:

\begin{align} ε | r(r)^\* = r^\* = ε | (r)^\*r \\ rr^\* = r^\*r = r^+ \end{align}

What am I missing here?

# Answer
> 1 votes
Solved it myself (kinda). As I already guessed, there were some essential laws I was missing.

In addition to regular expression $r$, let $L\_1, L\_2$ be regular languages:

\begin{align} (r | ε)^\* &= (r)^\* \\ (L\_1 | ε)(L\_2)^\* &= (L\_2)^\*, L\_1 \subseteq L\_2 \end{align}

Using these, we can continue as follows:

\begin{align} R & = (ε | 1)(ε | 1)^\* \\ & = (ε | 1)(1)^\* \\ & = (1)^\* \\ & = 1^\* \end{align}

I won't try to claim any credit, a regex simplifier I found online was a great help: http://ivanzuzak.info/noam/webapps/regex\_simplifier/

---
Tags: regular-expressions, kleene-star
---


# Question
Title: Could you solve co-RE problems with a halting oracle?
The halting problem is $RE$ complete. With an oracle for the halting problem could you decide problems in $co RE$ with an oracle for RE?

# Answer
Yes. In general - for a language $L$ an oracle to $L$ is equivalent to an oracle of $\overline L$.

Since the complement of the halting problem is co-RE complete (it is immediate from the fact that the halting is RE complete), then an oracle to it can solve all co-RE.
> 1 votes

---
Tags: computability, halting-problem, oracle-machines
---


# Question
Title: Is there an algorithm whose time complexity is between polynomial time and exponential time？
We often hear about some algorithms' running time that is polynomial, and some algorithms' running time that is exponential. But is there an algorithm whose time complexity is between polynomial time and exponential time?

# Answer
There is a category of time complexity called quasi-polynomial. It consists of a time complexity of $2^{\mathcal{O}(\log^cn)}$, for $c\> 1$. It is asymptoticaly greater than any polynomial function, but lesser than exponential time.

Another category is sub-exponential time which name speaks for itself. It is sometimes defined as $2^{o(n)}$.

The problem of graph isomorphism can be solved in sub-exponential time, but no algorithm in polynomial time is known.
> 27 votes

# Answer
The general number field sieve, the most efficient known algorithm for factoring large numbers, has a runtime that's roughly $\exp(n^{1/3})$, where $n$ is the number of digits in the number to be factored. This runtime grows with $n$ faster than any polynomial, but slower than exponential.

This class of runtimes is generally still considered "hard" for the purposes of practical computation (hence the security of RSA and other cryptography systems that depend on the difficulty of factoring). The cutoff for "practically efficient to compute" is generally taken to be right above polynomial growth, not right below exponential growth.
> 14 votes

# Answer
Other answers have given some specific examples of problems whose difficulty is conjectured to be between polynomial and exponential time, but the Time Hierarchy Theorem gives a general proof that for any time-constructible function $f(n)$, there is some decision problem which can be solved in time $f(n) \cdot log^2(n)$ but not in time $f(n)$.

Namely: Given an encoding of a Turing machine $M $and an input $x$, does $M$ accept $x$ within $f(|x|)$ steps?

So taking $f(n) = 2^{\sqrt{n}}$, the problem of deciding whether an arbitrary Turing machine halts within $2^{\sqrt{n}}$ is solvable in time $ n \cdot 2^{\sqrt{n}}$, but not solvable in time less than $2^{\sqrt{n}}$.
> 11 votes

# Answer
Sure, eg you can easily built an algorithm taking $\Theta(2^{\sqrt{n}})$ steps, and this is slower than polynomial but faster than exponential. For this, compute $\frac{2^{\sqrt{n}}}{\sqrt{n}}$ (in binary), and then count down from there, making sure to make a full pass through the array each time.

If you just want something intermediate, you can make it even simpler and just generate an array of length $\sqrt{n}$ and count up from $00\ldots 0$ to $11\ldots 1$. This clearly takes at least $2^{\sqrt{n}}$ steps, and at most $\sqrt{n}2^{\sqrt{n}}$.
> 2 votes

---
Tags: algorithms, time-complexity, polynomial-time
---


# Question
Title: Can distirbuted processing, OS processes or even threads be used to simulate a non deterministic turing machine adequately on small datasets?
For example for the traveling salesman problem which is a proven NP-Complete problem, if we spawn a thread at each node in the graph such that each of those threads will, in turn, spawn as many threads as needed, would this work as a simulation of Non-deterministic Turing machine. Are there any theoretical gaps in this simulation?

For input:

```
1,2
1,3
1,4
2,5

```
* Salesman starts at node 1 spawns 3 threads for 2,3,4
* Each of the nodes 2,3,4 spawn a new thread
* Threads spawned at 3,4 report that there is nothing more to do Nodes 3,4 therefore finish their respective processing and report to Node 1
* Node 2 spawns a thread for 5 which folds as above and Node 2 inturn folds and reports to Node 1 that it can visit 5 in the path 2-\> 5
* Node 1 now sees that there are 4 additional nodes in the graph 2,3,4 and 5 and that 2 fails to connect to 3 and 4 thus does not have a path that has complete coverage such that each node can be visited exactly once and the same is true for Node 3 and 4

Will the above be polynomial clock/duration time? (granted it is an extremely oversimplified approximation with possibly large multiplier constants. One may need to build sets at each node for accessible downstream nodes and this set is sent back to their parent)

this question is intended more as a thought experiment than as a question that has an exact yes/no answer. However, still posting it here as I thought there might be obvious reasons to say no because I am missing something fundamental.

Essentially would infinite compute capacity allow for arriving at a solution for NP problems in polynomial clock/duration time from start to finish?

# Answer
> 2 votes
You can of course simulate a non-deterministic TM in this way.

Is it polynomial time? It depends what you mean by that, but as a first approximation, the answer is no. The total amount of computation performed -- the total running time, summed across all threads -- will be exponential in general. For instance, the amount of energy used for this computation will be exponential. The wall-clock time -- i.e., the time until the last thread finishes -- may theoretically be polynomial, *if* you have a CPU with an unlimited number of cores, so that each thread can run on its own core. However you will need exponentially many CPU cores, so this is completely unrealistic and only a thought experiment.

In other words, in practice this is completely infeasible unless the size of the problem is exceptionally small -- and if the problem is exceptionally small there are many other ways to do it without needing to spawn multiple threads.

So conceptually this is a fine way to think about non-determinism. As a practical implementation strategy, normally it will not make sense.

---
Tags: turing-machines, nondeterminism
---


title: How random is Python's Random Module

text:
# Question
Title: How random is Python's Random Module
Recently i wrote a programme using random module of python. Then i realised that the same output was being repeated quite a number of times though it was supposed to be completely random.

# Answer
You need to understand that all of those libraries/functions won't really give you a truly random number. Why? because whatever algorithm it uses, would be taking input, and performing some predefined steps on it i.e. it is deterministic in nature. So in theory, if you know the exact input and algorithm used to generate random numbers you can replicate it.

Also, the distribution of the random numbers matter, for example, if it is a gaussian distribution, you might find some numbers repeating themselves which are closer to the mean for given range of values. The numbers are repeating themselves because they are generated that way, you might want to try seeding or shuffling to induce more randomness, or try implementing some of the algorithms yourself.

If you really want a truly random number sequence, the input would have to be truly random (variation in the path of Brownian motion, weather patterns, radioactive decay, etc).

You can start by looking at how a Linear congruential generator works. It's pretty easy to notice why numbers would repeat after a point.
> -1 votes

---
Tags: algorithms, random-number-generator
---


# Question
Title: How to create a DFA that accepts strings that are multiples of a number?
I particularly have a problem creating DFAs for multiples of larger numbers like 10, 11 ,12 etc. but I can create simple ones like 1, 2, 3 etc.

Even more so, I have a problem creating a minimized DFA for these problems. I think if a DFA has 10, 11 or so states, minimizing it properly could take a long time as there can be approx. pow(2,10) transitions. I am particularly having problem with the following:

> Minimum number of states in a deterministic finite automata that accepts the strings over the alphabet {0,1} beginning with a 1 and which, if interpreted as a binary number, is a multiple of 10.

This language has the strings = {0, 1010, 10100, 11110, ....} and there doesn't seem to be any pattern that is followed. Is there any universal approach that works for creating such counting DFAs and minimizing them?

# Answer
Instead of finding a pattern in their binary representation, observe how their remainder changes. A multiple of N would give a remainder 0 when divided by N, or equivalently 0 when you apply mod N operation.

For example, If want to check if 5 is a multiple of 0 or not, start with its binary representation, and assuming you are reading from MSB to LSB, the machine would encounter the first bit of 101 i.e. 1. At this point, your machine knows it has a 1 as input and 1mod10 is 1, so it will have a remainder state 1. Similarly, you will have a state for each remainder from 0-9. Now when it reads 0, the machine has an input 2 (10 in binary==2). So now you have to find out from the remainder state of 1, upon encountering a 0, what is the remainder state now. Do this for all states and you will have your DFA constructed. Remainder state 0 would be the accepting state.
> 1 votes

---
Tags: finite-automata
---


# Question
Title: walk / traverse a disjoint set that has union rank and path compression
I'm studying CLRS section 21.3, which introduces a union rank + path-compressed implementation of disjoint set. The implementations of MAKE-SET, UNION, LINK, and FIND-SET on p 571 of the book all work with nodes themselves, where each node has a `parent` pointer and `rank`.

Exercise 4 in that section claims that if you wanted to traverse all the nodes in the set (e.g. to print them) you only need **a single extra attribute** for each node, and the book claims that you can implement this *without* sacrificing the asymptotic complexity of union rank + path compression.

The data structure that immediately comes to mind is a circular list with single (not double) links. In this case, the "single extra attribute" the exercise asks for would be the `next` pointer of each node. We could just maintain that list in parallel with the disjoint-forest + union rank + path-compression.

However, the problem is that when trying to merge two sets, you would also need to merge their circular lists, and for a singly linked circular list, I'm pretty sure you **cannot combine them into one without traversing through one of them first**. This traversing would certainly destroy the asymptotic efficiency of union rank + path compression here.

Of course, you could slightly augment the circular list by keeping track of both its head *and* the node *before* the head, i.e. the tail. However, in order to do this, you can no longer work directly with the nodes, but would need to maintain a `circ-list` object (one for each set) with `head` and `tail` pointers. This would also mean that you can no longer call UNION on two nodes directly, but rather need to maintain a `set` object that has a pointer to its `circ-list` object as well as its `root`. All this seems to be somewhat more than the "exactly one extra attribute for each node\`, since you also need O(1) extra attributes for each set.

Is what the exercise asking for actually possible, or do I need to make one of the concessions above?

# Answer
None of the hacks in the question are necessary, since it's definitely possible to merge two singly linked circular lists without maintaining any additional tail pointers.

Suppose you have heads `x` and `y` of two separate circular lists. We first save `xn = x.next`. Then, set `x.next = y.next`. Then, set `y.next = xn`. After these, it's easy to see that the two circular lists have been merged.
> 1 votes

# Answer
Let `X` and `Y` be the two sets to merge. Each element has a `next` pointer that ensures that if you follow the pointers, you visit all elements before you get back to the start.

Let `tailX := root(X).next`, and `tailY := root(Y).next`.

Set `root(X).next := tailY` and `root(Y).next := tailX`.

As you can see, starting from `root(X)` now takes you to the end of `Y`, through `Y` to the end of `X` and back to `root(X)`.
> 0 votes

---
Tags: data-structures, linked-lists, union-find, disjoint-sets
---


# Question
Title: How to reduce SUBSET-SUM with integers to SUBSET-SUM with non-negative integers?
The subset sum problem is as follows:

> Given a sequence of integers $\mathcal S=(a\_1, ..., a\_n)$ with cardinality $n$ and an integer $T$, determine whether there is a subsequence of $\mathcal S$ whose sum equals $T$. Denote this problem $SSP$.

I was given a variant of the subset sum problem:

> Given a sequence of $\color{blue}{\mbox{non-negative}}$ integers $\mathcal S=(a\_1, ..., a\_n)$ with cardinality $n$ and an integer $T$, determine whether there is a subsequence of $\mathcal S$ whose sum equals $T$. Denote this problem $SSP\_+$.

My task is to prove that $$SSP\leq\_p SSP\_+$$ Therefore, I have to come up with a polynomial-time transformation $f$ between problem instances of $SSP$ and those of $SSP\_+$, and prove the correctness of my reduction. This is where I encounter difficulties. I was given a hint:

> Let $L=(a\_1,\cdots,a\_n;T)$ be a problem instance of $SSP$, then consider a transformation $f$ in the sense that $$f(a\_1,\cdots,a\_n;T)=(a\_1+K,\cdots,a\_n+K, \underbrace{K, \cdots,K}\_{n\\,K's};T+nK)$$ How do you choose $K$? And, when do you need to do the transformation? Don’t forget to justify that the answer to the problem instance $L$ is “yes” iff the answer to $f(L)$ is “yes”.

---

**My Thoughts**

I was thinking about assigning $K$ the value $$K=\sum\_{i=1}^n|a\_i|$$ so that there is no subsequence of $\mathcal S$ whose sum exceeds $K$. This $K$ ensures that $a\_i+K\geq 0$ for $1\leq i\leq n$.

To me it's rather straightforward to show that $$\mbox{answer to }L\mbox{ is "yes"}\implies \mbox{answer to }f(L)\mbox{ is "yes"}$$ but I encounter serious difficulties proving the other direction. That's why I come here to seek help.

---

**My Questions**

Is my choice of $K$ correct? If so, how do I prove the other direction?

---

Thanks for reading my post.

# Answer
> 2 votes
To prove the reverse direction you need to show that if there exist a subsequence $S\_1$ in $(a\_1+K,a\_2+K,\dotsc,a\_n+K,K,\dotsc,K)$ that sums to $T+nK$, then there is a subsequence $S\_2$ in $(a\_1,\dotsc,a\_n)$ that sums to $T$.

The proof would become easy if we assume that $S\_1$ only contains $n$ elements. If that happens, then the above statement holds. (hope you can prove this on your own).

Now, we need to make sure that $S\_1$ contains exactly $n$ elements for its sum to be $T+nK$. Note that it is possible when $K$ is super large. If $K$ is super large and $S\_1$ contains more than $n$ elements, then sum of $S\_1$ $\>$ $T+nK$. Similarly, if $K$ is super large and $S\_1$ contain less than $n$ elements, then sum of $S\_1$ $\<$ $T+nK$.

Therefore, better choose $K$ to be at least $|T| + \sum\_{i = 1}^n|a\_i|$.

---

Your choice of $K$ is problematic. For example, consider sequence $(-1,-1)$ and $T=2$ (which is a no instance). Here $K = \sum\_{i = 1}^n |a\_i| = 2$. This sequence reduces to sequence $(1,1,2,2)$ and $T = 6$, which is a yes instance.

---
Tags: np-complete, reductions
---


# Question
Title: Proving there exists no algorithm that can solve a basic problem
Consider the following basic problem, for which the statement is "obvious," but I can't seem to find totally convincing proof.

*Problem:* Let $S$ be a set of $n$ elements, where $n\geq 2$ is even. And let $f:S \rightarrow \\{0, 1\\}$ be a function that maps half of the elements in $S$ to $0$, and the other half to $1$. Suppose Alice picks an element from $S$ at random and passes it through $f$ to obtain a value $x \in \\{0, 1\\}$. Prove there exists no algorithm $A$ that can correctly predict the value $x$ given only $f$ and $S$ (Take $A$ to be a probabilistic polynomial-time algorithm for example).

I understand that this statement seems entirely trivial, but I cannot really form an argument that feels rigorous. What is the basic proof I am missing, or the definition I need to use?

# Answer
> 0 votes
Assuming you are sampling from $S$ uniformly, let $X$ be the random variable you are sampling.

Then the random variable $f(X)$ is a Bernoulli distribution with probability 0.5 to get either $0$ or $1$.

Thus, $\Pr\[f(x)=a\]=0.5$ for any $a\in\\{0,1\\}$. So no matter which outcome the algorithm predicts (it has to be independent of the choice of $x$), the probability it is right is exactly $0.5$ \- meaning that it cannot predict anything.

---
Tags: computability, randomized-algorithms
---