# Question
Title: Is this a Traveling salesman problem? If so, how to solve it?
Given a group of cities and a starting city, we have to find a path that covers all the cities. The path doesn't need to end at the starting city. Is this a TSP problem? What is the solution for it?

This is not a homework problem or an interview question. I asked ChatGPT to find the shortest paths covering 5 random cities in my area and it told me that it is a TSP problem. I was thinking that this is more of a minimum spanning tree question. Can someone confirm this for me?

# Answer
> 0 votes
Take your TSP problem, then add a city X which has a distance of 0 from the starting city, and a T miles from any other city, where T is more than all other distances added.

If you solve the modified TSP instance, X must be one of the neighbours of the starting city, otherwise the tour would have a length of 2T. The distance of the shortest tour will be less than 2T, and exactly T longer than the optimal solution of the original problem. So you found the shortest tour that starts with the given start city and ends at another city. Compare this to the solution of the original problem, and you get the best tour that *may* end not at the starting city.

If no starting city is given, then add a city X that has the same long distance T from *each* city and solve the modified problem. The optimal tour for the modified problem is exactly 2T longer than the optimal tour that starts anywhere, and ends anywhere at another place.

Summary: To solve "May start anywhere, must end elsewhere" you add X with distance T from every other city, solve TSP, remove the two paths A -\> X -\> B, then take the route from B to A.

To solve "Must start at start city A, must end elsewhere" you add X with distance T from every other city except distance 0 from the start city, solve TSP starting at A, remove the two paths from some city to X.

---
Tags: minimum-spanning-tree, traveling-salesman
---


# Question
Title: This is an exercise in CLRS 4th Edition. I am not sure how to solve this question, and I am not even sure how I would use equation 3.14
Use equation (3.14) or other means to show that $(n+o(n))^{k}=\Theta\left(n^{k}\right)$ for any real constant $k$. Conclude that $\lceil n\rceil^{k}=\Theta\left(n^{k}\right)$ and $\lfloor n\rfloor^{k}=\Theta\left(n^{k}\right)$.

Where equation (3.14) is:

$1+x \leq e^{x}$

# Answer
Let $f(n) \in o(n)$ and consider sufficiently large values of $n$. There is some constant $c$ s.t. $f(n) \le cn$. Defining $c' = (1+c)^k$ (notice that $c'$ is a constant): $$ n^k \le (n+ f(n))^k \le (n(1+c))^k = n^k (1+c)^k = c' n^k $$

Then you just need to observe that: $$ n^k \le \lceil n \rceil^k \le (n+1)^k = O(n^k) $$ and (since $k$ is a constant): $$ n^k \ge\lfloor n \rfloor^k \ge \left(\frac{n}{2}\right)^k = \frac{n^k}{2^k} = \Omega(n^k) $$
> 0 votes

---
Tags: algorithms, algorithm-analysis, discrete-mathematics
---


# Question
Title: Complexity of this variant of the Monotone(+,2−) -SAT problem?
In this post,Monotone$(+, 2^-)$-SAT problem is defined as follows:

Given a monotone CNF formula $F^+$, where each variable appears exactly once (as a positive literal), and a monotone 2-CNF formula $F\_2^-$ defined on the same variables as $F^+$, where all variables are negated. Is $F^+ \land F\_2^-$ satisfiable ?), let us define the Monotone$(+, 2^-)$-SAT problem:

Given a monotone CNF formula $F^+$, where each variable appears exactly once (as a positive literal), and a monotone 2-CNF formula $F\_2^-$ defined on the same variables as $F^+$, where all variables are negated. Is $F^+ \land F\_2^-$ satisfiable ?

Consider this variant of Monotone(+,2−)-SAT problem where we restrict the number of clause of $F^+$ to be 2 and the width of these 2 clause can be anything ,that means that every instance of positive literal appears in only 2 clause.

Is this variant also NP-complete? I don't see any direct reduction from the main problem to this variant ,so does there exist any reduction or is it solvable in polynomial time?

# Answer
> 1 votes
It is in P. Suppose the first clause of $F^+$ has $k\_1$ variables, and the second clause has $k\_2$ variables. Then there are $k\_1 k\_2$ ways to pick one variable from the first clause, and one variable from the second clause. For each such way, set those variables to true in $F\_2^-$ (i.e., replace those variables with true, and simplify). The result is a 2-CNF formula, and you can test satisfiability of it in linear time. Check whether the result is satisfiable. If it is, then you obtain a satisfying assignment for $F^+ \land F\_2^-$. Repeat once for each of these $k\_1 k\_2$ possibilities.

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


# Question
Title: What is the proper way to write logic formula, say concerning graph theory?
Say for example I'd like to state that there exists a pair of vertices such that they form an edge in one graph but not some other graph. I'd go about it as follows:

$$ \exists u, v \in V, (u,v) \in G, (u,v) \not\in H $$

My main question here is: Is my use of commas fine (it seems odd, since there's commas between $u$ and $v$ already which don't seem to be used in the same manner), or should I use vertical lines, colons, semicolons, logical $\land$ ... and if so where exactly? Is there a proper way to do this which I just haven't found or is me assuming everyone has their own distinct way correct?

# Answer
The standard logical notation I have seen among computer scientists for saying there exists $x \in X$ such that $\varphi(x)$ holds is to write

$$\exists x \in X . \varphi(x).$$

In other words, we use a period. Sometimes people will instead write

$$\exists x \in X \\; \varphi(x)$$

i.e., they use no separator (just some space). There are many more variants, for instance I have seen $(\exists x \in X) (\varphi(x))$ in communities that are more focused on mathematics or logic.

So, in short, there are many conventions. Ultimately, I think if you use a comma, people will understand what you mean.

If it were me, I would write something like

$$\exists u,v \in V . (u,v) \in G \land (u,v) \notin H,$$

and use logical connectives (like $\land$) to express a series of statements that must be true, rather than listing them with commas. But I think people will understand what you wrote.

See also https://math.stackexchange.com/q/197554/14578 and https://math.stackexchange.com/q/79190/14578.
> 2 votes

---
Tags: graphs, logic, syntax
---


# Question
Title: Find the shortest distance path in a weighted graph, where the weight of each edge is non-negative and less than a constant C = 500 in linear time
The problem is to find the shortest distance in a weighted graph, where the weight of each edge is non-negative and it is given that the weight of each edge is less than a constant C. For example, C = 500.

I know that I can solve this problem using Dijkstra, however, the time complexity would be high. The problem should be solved in linear time in terms of the vertices and edges of the graph.

I think this has to do with some linear graph traversal, BFS or DFS

A direction would be appreciated on how to solve this problem in linear time.

# Answer
**Algorithm:**

1. Build a new graph $G' = (V', E')$, where for every edge $e = (u,v) \in E$ with weight $w(e) \> 1$:

Replace the edge by a path P (simple) of length $w(e)$, where each edge in path $P$ has weight of 1. Meaning, path $P$ will have $w(e)-1$ nodes and $w(e)$ edges. $P = (u, x\_1, x\_2,..,x\_{w(e)}, v)$
2. Run BFS on the new graph $G'$.

* **Time Complexity:**

Let's look at $G' = (V', E')$.

At most, our new graph has **at most** $C\times|E|$ vertices and $C\times|V|$ edges. Thus, the time complexity linear in terms of $G=(V,E)$, since BFS requires a linear time complexity.

* **Proof of correctness:**

It is enough to prove that our new graph $G'$ is equivalent to our original graph $G$. That means, for each two nodes $(u,v)$ which had a path between them, there still exists a path between them with the same weight as in our original graph $G$. By proving this, you would've also proved that for every node $v$ which was reachable from node $u$ in $G$, the node $v$ is still reachable from node $u$ in our new graph $G'$.
> 1 votes

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


# Question
Title: Proving that there is no solution to the PCP problem using induction
I'm studying for the Algorithms and Computability course. I have encountered a problem that I cannot solve and cannot find any materials to help me solve it. It's the following PCP problem:

We have two sets:

A = (b, a, ca, bac)

B = (ca, ab, a, c).

The task is to find a solution to the given PCP problem or prove that there is none. I know that there will be no solutions, as after choosing elements of the sets with the following indices: 2, 1, 3, 2, 2, 1, 2... we'll end up in a situation where the string formed using set B will always be longer than the first one. Our lecturer wants us to prove it using induction, but unfortunately, I have no clue how to do that. I tried two times on exams and failed every time.

Could anybody show me, what is the correct way to form such a proof or link me to some source that shows that? I will be very grateful.

# Answer
> 2 votes
There is no solution.

#### Proof by induction

Here is one-line summary: the bottom string is always longer than the top string by a string in the form $(abca\mid abcaaa\mid abcaaab)^+$.

---

Suppose we try to construct a solution by adding dominos one by one, keeping the string on the top row (the top string) and the strong on the bottom row (the bottom string) consistent all the time. "Consistent" means either the top string is a prefix of the bottom string or the bottom string is a prefix of the top string.

Initially both strings are empty. Then, however far we may try, as you have noticed, the bottom string is always longer than the top string.

However, we cannot prove that simple statement by straightforward induction since, when considered as the induction hypothesis, it is too weak to support the induction step.

---

Let us observe **the overhang, the extra part of the bottom string**. It changes as follows: $b\to ca \to a\to ab\to bab\to abca\to abcaa\to\cdots$

Continuing, we find the overhang grows as follow: $$\begin{aligned} &\to^\*\underline{abca}\\ &\to^\*\underline{abcaa}\\ &\to^\*\underline{abcaaab}\\ &\to^\*\underline{abcaaab}\\,\underline{abca}\\ &\to^\*\underline{abca}\\,\underline{abcaaab}\\,\underline{abca}\\ &\to^\*\underline{abcaaab}\\,\underline{abca} \\,\underline{abcaa}\\ &\to^\*\cdots \end{aligned}$$ where $o\_1\to^\* o\_2$ means overhang $o\_1$ is transformed to overhang $o\_2$ in several steps without ever being empty.

---

**Claim (decomposition of the overhang)**: The overhang is $abca$ when there are 6 dominos. Suppose the overhang is in the form $(abca\mid abcaa\mid abcaaab)^+$. Then it will be transformed to the same form when $3$, $4$ or $6$ dominos are added.
**Proof**: In the following $W$ stands for some string. The overhang is transformed by the following rules.

* If it is $aW$, the next domino can be and can only be $\begin{bmatrix}a\\ ab\end{bmatrix}$.
The new overhang will be $Wab$.
* If it is $caW$, the next domino can be and can only be $\begin{bmatrix}ca\\ a\end{bmatrix}$.
The new overhang will be $Wa$.
* If it is $bW$, where $W$ does not start with $ac$, the next domino can be and can only be $\begin{bmatrix}b\\ ca\end{bmatrix}$.
The new overhang will be $Wab$.

Hence, we can verify that

* if the overhang is $\underline{abca}W$, then it will become $W\underline{abcaa}$ when $3$ dominos are added.
* if the overhang is $\underline{abcaa}W$, then it will become $W\underline{abcaaab}$ when $4$ dominos are added.
* if the overhang is $\underline{abcaaab}W$, then it will become $W\underline{abcaaab}\\,\underline{abca}$ when $6$ dominos are added.

---

With the claim, it is straightforward to use induction to show that the overhang is never empty. That means the bottom string is always longer than the top string. There is no solution to the PCP problem.

#### Proof by counting

Let us call $\begin{bmatrix}b\\ ca\end{bmatrix},$ $\begin{bmatrix}a\\ ab\end{bmatrix},$ $\begin{bmatrix}ca\\ a\end{bmatrix},$ $\begin{bmatrix}bac\\ c\end{bmatrix}$ type 1, 2, 3, 4 respectively.

**Lemma, more type-3 than type-4**: Suppose the list of $n$ dominos $d\_1, d\_2, \cdots, d\_n$, $n\ge3$ is a solution. Then there are more type-3 dominos than type-4 dominos in the list.
**Proof**: The first 3 dominos in the list must be $$\begin{bmatrix}a\\ ab\end{bmatrix} \begin{bmatrix}b\\ ca\end{bmatrix} \begin{bmatrix}ca\\ a\end{bmatrix},$$

where the third domino is $\begin{bmatrix}ca\\ a\end{bmatrix}$ but there is no $\begin{bmatrix}bac\\ c\end{bmatrix}$.

Suppose $d\_i$ is type-4. It presents a substring $bac$ on the top row. Since the given list is a solution, it corresponds to a substring $bac$ on the bottom row.

Consider *that* substring $bac$ on the bottom row. The letter $a$ in the middle is neither preceded by $c$ nor followed by $b$. Hence it can only be brought by some $d\_{x(i)}$ of type-3, $1\le x(i)\le n$. $d\_i\mapsto d\_{x(i)}$ is a correspondence from type-4 dominos to type-3 dominos in the list. Note that a different $d\_i$ must be mapped to a different $d\_{x(i)}$. Moreover, the third domino, which is type-3 is not mapped to by any type-4 domino.

---

**Claim**: There is no solution to this PCP problem.
**Proof**. Suppose there is a solution. Let $\\#1, \\#2, \\#3, \\#4$ be the number of type-1,2,3,4 dominos in the solution. The number of $a$s on the top row and on the bottom row are $\\#2+\\#3+\\#4$ and $\\#1 +\\#2+\\#3$ respectively. The number of $c$s on the top row and the bottom row are $\\#3+\\#4$ and $\\#1+\\#4$ respectively. So we have $$\begin{aligned} \\#2+\\#3+\\#4 &= \\#1+\\#2+\\#3,\\ \\#3+\\#4 &= \\#1+\\#4, \end{aligned}$$ which implies $\\#3=\\#4$.

On the other hand, there must be at least $3$ dominos in the solution. The lemma says $\\#3\>\\#4$. This contradiction means we do not have a solution.

# Answer
> 3 votes
**added.** See the answer by John L. for a formalization of my ideas here.

Your observation is correct. The second string is always longer than the first. Now you have to use induction to actually prove that intuition. This can be done by observing some kind of regularity in how those strings look.

For me it is helpful not to focus on the specific pair of strings, but on the *overhang*. In constructing the pair of strings that form a solution of PCP at any point one of the strings is longer than the other. The prefixes where both strings match can be forgotten, they are no longer relevant.

The regularity I observe is that the second string is always longer (like you said) and always consists of strings in $\\{a,b,ca\\}^\*$.

The induction-proof has to check the *basis* (at some point this is true) and the *induction step* (once this is true it will also be true in the next step). The basis you can do yourself.

The induction is in the following style. The overhang on the second component is $a{\cdot}w$ or $b{\cdot}w$ or $ca{\cdot}w$ for some $\\{a,b,ca\\}^\*$ (the induction assumption). If it is $a{\cdot}w$ we must use rule (2) and the new overhang equals $w{\cdot}ab$, which is the form we need in the next step. Similarly the other two cases. In this way we see that we never can loose the overhang as it never becomes empty.

Somehow we should also verify that the overhang never starts with $bac$, so we cannot apply rule (4). I did not consider that here, but it should be part of the inductive property.

---
Tags: automata, undecidability, induction
---


# Question
Title: Hard Drive Seek Time using FIFO, SSF, SCAN
A hard disk spins at 6000 rpm (revolutions per minute), and it takes 100 μs (on average) for the head to traverse one track. Consider the following sequence of disk track requests: 27, 129, 110, 186, 147, 41, 10, 64, 120. Assume that initially the head is at track 30 and is moving in the direction of decreasing track numbers. Compute the time it takes to serve the requests using (1) FIFO, (2) SSF (Shortest-Seek First), (3) SCAN.

I understand the difference between the different algorithms and I generally get how to calculate it.

My questions is, when I calculate the Average rotational time, i.e. (60/6000) / 2 = 5ms, **do I need to multiply this by the number of tracks moved?**

My FIFO calculation as an example:

(3+102+19+76+39+106+31+54+56) * (5ms + 0.1ms) = 2478.6ms

I add up the number of tracks moved and multiply this by the average rotational time + the time it takes to traverse each track.

Is this approach correct?

Thank you

# Answer
> 0 votes
@greybeard **why he divided by 2** on average we will **need to wait for half a rotation of the disk for the correct sector to come under the head**. Thus, on average, the rotational latency is half the time it takes the disk to make a complete revolution.

**do I need to multiply this by the number of tracks moved?** No. Because average rotational time is the time to move head from one sector to any other sector in same track. This movement is done by disk rotation.

In your question we will consider any sector in given track. So when track changes from 30 to 27, it takes 3 track movement and 1 average rotation so time 3\*0.1+5

In general, `total time = seek time + rotating latency`

Seek time : time to change track

### Edited

```
(3+102+19+76+39+106+31+54+56)*0.1 + number_of_time_movement_occured * rotational_latency
= 486 * 0.1 + 9 * 5
= 48.6 + 45
= 93.6

```

# Answer
> 0 votes
With sufficiently clever hardware, you can optimise the seek time: Assume that each read operation reads some portion of a track, and you know that portion. One full rotation takes 10ms, the same as moving 100 tracks. You can then take the rotation into consideration, and try to go to a track first where the data will arrive very shortly after the head arrives on that track.

In your situation, you might for example move tracks in order 30, 27, 10, 41 or in order 30, 10, 27, 41 and one might be faster.

---
Tags: memory-hardware, memory-access
---


# Question
Title: Bin packing with more than one parameter
Usually, in bin-packing, we have objects of sizes $a\_1,...a\_n$, and each bin has size 1, We need to minimize the number of bins, and for this, there are best fit/first-fit approximation algorithms.

What will happen if there are more parameters than just size, say 3 parameters? Each object $i$ has say parameters $(a\_i,b\_i,c\_i)$ and there are bins with all the three parameters equal to 1. How can we extend the best-fit/first-fit approximation algorithms, so that in each bin, we have $\sum a\_i \leq 1, \sum b\_i \leq 1,\sum c\_i \leq 1$ and we still have a constant approx factor?

# Answer
> 1 votes
Here is the solution when the vector is two-dimensional. This process can be extended exactly in the same way to higher dimensions. As mentioned in the comments https://link.springer.com/content/pdf/10.1007/BF02579456.pdf?pdf=button shows the general solution.

Z is the set of vectors given to us. Let $L\_i$ denote the set of indices of the vectors in $Z$ for each of which the largest component is the $ith$ one, breaking ties arbitrarily. Now consider all the vectors whose index has been put inside $L\_i$ and then let's call $Z\_i$ the list of the values of the $ith$ component of the vectors. An optimal packing of $Z\_i$ will be an optimal packing for the vectors inside $L\_i$. We already know that for 1-dimensional packing we can do a greedy best fit or first fit algorithm with an approximation factor of 2. We apply that greedy algorithm to this one-dimensional packing we got. Say we can optimally pack the $Z\_i$ in $Z\_i^\*$ bins. Then for the two-dimensional case, we will not need any more than $2 \cdot (Z\_1^\* + Z\_2^\*)$ bins for packing all the vectors in $Z$.

Again observe that all those vectors that have indexed in $L\_i$ cannot be packed in less than $Z\_i^\*$ bins. So if $Z^\*$ is the optimal number of bins for all the vectors(i.e. OPT in this case), then $Z^\* \geq max\\{Z\_1^\*, Z\_2^\*\\} \geq 1/2 \cdot (Z\_1^\* + Z\_2^\*)$. Combining both the inequalities, we see that our algorithm will obtain an approximation factor of 4, i.e. $2 \cdot (Z\_1^\* + Z\_2^\*) \leq 4 \cdot max\\{Z\_1^\*, Z\_2^\*\\} \leq 4 \cdot OPT$.

---
Tags: combinatorics, approximation, packing
---


# Question
Title: if L is CF does that mean L interaction L reverse is also CF?
if L is CF does that mean L interaction L reverse is also CF? thats the whole question since CF is clsoed for reverse it makes sense but there are alot of refute out there for interactions, so I was wondering how can i prove it ?

# Answer
i refuted it for example take L={a^i b^i a^j | i, j \>=0} means L^R = L={a^j b^i a^i | i, j \>=0} which leads us to L interaction L^R = {a^n b^n a^n | n\>= 0 } which is clearly not an CFL
> 0 votes

---
Tags: automata
---


# Question
Title: How manufacturers lock their devices to run only software by them? And how it is possible at all?
How do manufacturers lock their devices to run only software by them? And how is it possible at all? For example: upgradeable toothbrush, mobile device, smart watch

# Answer
Operating systems can verify that a particular code sequence originated from an authentic source using code signatures. This cryptographic technique verifies that a trusted entity - as identified by a public key - asserted the code sequence is authentic. To prevent a hardware device from being reprogrammed, the signature of the OS could be programmed into ROM and checked prior to boot. Thus, reprogramming the device would require intervening with the physical hardware. Realistically, most manufactures of low cost devices are not concerned with them being reprogrammed as this requires a lot of experience and devotion.
> 1 votes

# Answer
To run alternative software on a device, you need to be able to install the software somehow.

If the device runs software from a storage medium that can be removed, this is easy: attach the storage medium to a different computer, install the software onto this medium, and insert the medium back into the device. You can do that, for example, on a PC with a hard disk or detachable SSD drive. With this hardware configuration, if the device manufacturer wants to restrict permitted software, it has to boot on non-removable media (generally ROM or flash memory) which only runs software on other media under certain restrictions (generally requiring a cryptographic signature; this is commonly known as “secure boot”, though beware that terminology varies).

But embedded devices typically do not have a removable storage medium. Often they have a single chip with everything (main processor, RAM, flash memory, input-output controllers…), or at least a single board where all the components are soldered on. The only ways to access the device's storage medium are to interact with the software that's already there, or with costly physical methods (e.g. unsolder a component, or even shear the top off a chip).

Typically, if the manufacturer does not particularly care about updating the software after they've sold the device, they will not provide any easy way to update the software. It may still be possible, for example, to update the software through debug ports (if they're physically accessible), or through a generic operating system interface if the manufacturer has used an operating system with this capability.

If the manufacturer wants to be able to deploy updates, they will take care to make one method available to themselves. But if they didn't document it, it might take some effort to figure it out. And the manufacturer can put restrictions. For example, as above, the manufacturer might arrange that the device ships with functionality to download and install software updates, but this functionality checks that the software is cryptographically signed, so that only the manufacturer can make valid update images.

In all cases, there's a chain of the same form. What varies is the length of the parts.

1. When the processor starts, it runs code stored on a physically attached storage medium.
2. The code on this physically attached medium has restrictions on what other code it's willing to transfer control to.
> 1 votes

---
Tags: operating-systems
---


# Question
Title: Are the definitions of loop in CS and in programming (standard/common) identical?
Are the definitions of loop in CS and in programming (standard/common) identical?
If not, what is the main difference / what are the main differences?

# Answer
> 1 votes
Dijkstra's do loop as defined in the abstract language of guarded commands, which is a non-deterministic construct, is not found in the programming languages.

$$\begin{align}\underline{do}&\\ &\text{\[\] condition }1\to\text{instruction }1\\ &\text{\[\] condition }2\to\text{instruction }2\\ &\cdots\\ &\text{\[\] condition }n\to\text{instruction }n\\ \underline{od}\end{align}$$

The semantic is to

* evaluate all guards;
* choose one that is true and execute the associated instruction;
* repeat.

If no guard is true, the loop terminates.

# Answer
> -1 votes
In Mathematics and computer science, *looping* is generally associated with either some repetitive work, or with accumulated summation (bitwise, or higher logic operations).

Looping is more of an abstract view of iteration, in, say, programming - where it is very specific and depends on the language and associated compiler with programming point of view.

---

Sidenote: it is also a convenient way of writing programs to have loops rather than call some functions multiple times which is not good practice.

---
Tags: terminology, recursion
---


# Question
Title: Why does page size affect page table size?
I am revising operating systems theory (I'm Italian, forgive me for bad English) and there is a slide that states:

> If page size is small then we avoid internal fragmentation (I get that) but **we have larger size of page table and therefore larger cost of managing this page table**".
> If page size is large then we have a larger amount of internal fragmentation **but we do have a decreased page table size that's easier to manage.**

I don't understand how page size could affect size of page table. Page table (expect from TLB) is saved in memory. **I assume that, the amount of free memory we have for a page table is fixed (am I right?)** (because we also need memory for OS, processes, and a bunch of other things).

**Size of adress in system is also fixed , isn't it?** So if we use for instance 32 bits for addresses then we need $2^{32}$ entries in the page table no matter what. (Expect of course, if we use COW: "Copy on write" then we probably need less.)

Anyway, if page size is smaller, the size of page table should be: $$\\#\text{entries}\*page\_{size}$$ where #entries stands for number of entries in the page table. So to me it seems like **page size and page table size are analogous.**

I am totally missing something here. Could you help?

# Answer
Suppose you have a virtual address space of say $32$ bits. Then the virtual address space for each and every process is fixed and it ranges from the byte $0$ to $2^{32}-1$.

Now the for the ease of memory management the main memory is divided into frames of certain size say $2^k$ bytes. Also, our virtual address space of the process is divided into chunks or pages each of size $2^k$ bytes. Each page of the process maps to a particular frame of the main memory as a part of memory management/memory mapping of the virtual address space of the process to the physical memory.

Now for a $32$ bit virtual address system, if the page size is $2^k$ the $k$ least significant bits of the virtual address are offsets of the bytes belonging to a particular page and the remaining $32-k$ bits indicate the page number.

The page table has as many entries as there are pages in the virtual address space of the process. So in our generalized running example, the page table has $2^{32-k}$ entries. Suppose that each page table entry is of $4B$, then size of the page table is :

$$\text{No. of page table entries $\times$ size of each page table entry} = 2^{32-k}\times 4 \text{ Bytes} = 2^{34-k} \text{ Bytes}$$

So higher the value of $k$, higher is our page size and smaller is our page table size.

As a specific example:

If page size is $4\text{ KB} = 2^{12}\ B$ we have $k=12$ and hence page table size is $2^{34-12}\ B=2^{22}\ B=4\text{ MB}$

If page size is $4\text{ MB} = 2^{22}\ B$ we have $k=22$ and hence page table size is $2^{34-22}\ B=2^{12}\ B=4\text{ KB}$
> 6 votes

# Answer
The page table isn't a fixed size. Assuming all memory of the system is in use, and no clever tricks to group pages are used, the page table has a size equal to the amount of memory divided by the page size.
> 2 votes

# Answer
As the page size increases, the number of pages in memory decreases. Now, each entry in a page table is an address translation of a page. So, the page table will have fewer entries when the number of pages decreases. Hence, page table size decreases with an increase in page size.
> 0 votes

---
Tags: operating-systems, memory-management, virtual-memory, paging
---


# Question
Title: Complexity of counting odd node in an undirected graph?
I want to know if there exist a algorithm to efficiently compute the number of odd vertex in an undirected graph?

A graph vertex in a graph is said to be an odd vertex if its vertex degree is odd, degree of a graph vertex ***v*** of a graph **G** is the number of graph edges which touch vertex ***v***.

This post conclusion seems to be that this is #P-hard but this doesn't seem that hard to me but I don't have any direct argument against it ,that's why I want to know if there exist a reduction from this problem to some #P-complete problem or is it polynomially solvable?

What I didn't understand from linked post is why counting odd vertex is related to counting number of satisfiable instance of SAT.

Also counting the number of odd vertex seems to be solvable in linear time ,all we'd have to do is check each vertex to see if they have a odd degree if yes add **1** to the **odd\_vertex\_number** variable ,this way we can solve it in linear time ,that's why I can't understand why this is #P-hard?

# Answer
You are indeed correct : Given a graph $G$ in the form of its adjacency matrix, you can find all the odd degree vertices in polynomial time of the number of vertices.

The post that you mention does something different. Notice that you may decide to mention the graph in some form other than the adjacency matrix. Assuming the graph has $n$ vertices, you only need $\log n$ bits to state the number of vertices. However now that you want to state the edges, you do not do the adjacency matrix representation (this representation would take up $n^2$ bits). Instead you decide to create a circuit of $\log n$ size. The circuit's job is to take as input a vertex and output its neighbours. Now notice that you have given the entire $n$ vertex graph in $O(\log n)$ bits. Not all graphs may be represented like this, but given a graph in this format you now want to find odd degree vertices. Since the input size is $O(\log n)$, you want to make the computation in polynomial of $O(\log n)$ and now your algorithm is exponential in this setting.
> 2 votes

---
Tags: algorithms, complexity-theory, graphs
---


title: Deterministic Finite Automaton

text:
# Question
Title: Deterministic Finite Automaton
design a DFA accepting the set of strings over the alphabet {0, 1} that when interpreted in reverse as a binary integer, are divisible by 3

# Answer
This is a DFA for binary numbers divisible by three. your desirable language is reverse of this language.

For reversion of language of a DFA, you must reverse all of its transitions and change its initial state with its final state. in this case initial and final states are same, also its language is symmetric so all of transitions are symmetric.
Therefore you need only reverse all of its transitions are symmetric; so you don't need to do anything. above DFA is above.
> 1 votes

# Answer
Take a look here
https://stackoverflow.com/questions/39385971/how-to-know-if-a-binary-number-divides-by-3

This means that while your DFA consumes the number from right to left, you should keep track (by using different states) of whether your difference is divisible by three or not. Also, your DFA must keep track of whether you are in an odd or even position (again, using different states).
> 0 votes

# Answer
I tried the same question to check divisibility by 5. As @m.farokhian said, this doesn’t need to be reversed, but for the strings 10011 & 1001100, it doesn’t seem to work.

Ps. I couldn’t comment due to my contribution. That's why added it as an answer.
> 0 votes

---
Tags: finite-automata
---


# Question
Title: Finding an inhabitant of $\Pi x: A.\Pi y:B(x). \ast$
Let $\ast$ stand for "type" and $\square$ stand for "kind" so that $\ast:\square$. Suppose I want to find an inhabitant of $\Pi x: A.\Pi y:B(x). \ast$. The derivation rules are given here.

Intuitively, as far as I understand, this inhabitant should have the form $\lambda x:A.\lambda y:B(x). P(x,y)$ for some $P: A\to B(x)\to \ast$. (If this is not right, let me know.)

Formally, I got to this point. So I proved that $\lambda y:B(x). P(x,y) : \Pi y:B(x).\ast$ in a certain context. But then I cannot abstract over $x:A$ because the "flag" (assumption) $P:A\to B(x)\to \ast$ doesn't let me do so. And I cannot move this flag before the flag "$x:A$" because I must assume $x:A$ before assuming $P: A\to B(x) \to \ast$ since $B(x)$ depends on $x:A$. What should I do in this situation?

# Answer
> 0 votes
Since you are asking to find *any* inhabitant, how about $\lambda (x : A). \lambda y : B(x). A$?

In other words, we take $P := \lambda (u : A) . \lambda (v : B u) . A$. It looks like part of your problem is that you want somehow to use an unspecified $P$.

---
Tags: logic, lambda-calculus, type-theory, dependent-types
---


# Question
Title: How do I prove the following relationship between big-theta notation and logarithms?
Prove that:

$\lg (\Theta(n))=\Theta(\lg n)$

# Answer
I think the correct approach to questions of this sort that try to give a better understanding of definitions is first to look at the,

$\displaystyle f\in\Theta(\lg n)\Rightarrow c\_1\lg(n)\leq f\leq c\_2\lg(n)$

We want to show that $\lg(\Theta(n))$ satisfies this requirement. I think the best way would be to show that :

$\lg(\Theta(n))\leq c\_1\cdot\lg(n^2)$

$\lg(\Theta(n))\geq c\_2\cdot\lg(\sqrt n )$

Hope this is helpful.
> 0 votes

---
Tags: algorithms, algorithm-analysis, asymptotics
---


title: Shell's Increments Worst Case Analysis

text:
# Question
Title: Shell's Increments Worst Case Analysis
My textbook claims the worst-case running time of Shellsort with Shell's increments is $Ω(N^2)$, but this analysis is done when $N = 2^m$ for a positive integer $m$. I see why the proof would work for those cases of $N$. The reasoning for the proof does not appear to, in general, hold for arbitrary $N$. However, the definition of $Ω$ requires that the running time be above a multiple of $N^2$ for all $N \>$ (some) $k$, which it didn't prove.

I also checked online, and every proof I've seen uses this exact same reasoning. Why is it OK to claim Shell's increment worst case is $Ω(N^2)$? What about the $N$ in between $2^m$ and $2^{m+1}$? How can I show their running time doesn't fall below some multiple of $N^2$ (if it is even possible)?

A similar proof can be found here: https://codeahoy.com/learn/sortingalgorithmsa/shellsort/ (not my textbook)

Maybe the reasoning extends to arbitrary $N$, but I just don't see it?

# Answer
> 0 votes
Every value of $N$ is within a factor of two of a power of two.

In particular, given any $N$, let $N\_0$ be the largest power of two such that $N\_0 \le N$. Your textbook apparently proves that the worst-case running time on an input of length $N\_0$ is at least $c \cdot N\_0^2$. The worst-case running time only increases with the length of the input (never decreases), so it follows that the worst-case running time on an input of length $N$ is at least $c \cdot N\_0^2$. Notice that $N\_0 \ge N/2$, so it follows that the worst-case running time on an input of length $N$ is at least $c \cdot (N/2)^2 \ge (c/4) \cdot N^2$. Notice that this holds for all $N$. It follows that the worst-case running time is $\Omega(N^2)$.

---
Tags: asymptotics, sorting
---


# Question
Title: Eligibility trace and the role of gamma and lambda
From R.Sutton's book, the eligibility trace update rule is: $$ E\_t(s)\leftarrow\gamma~\lambda~ E\_{t-1}(s)+\mathbb{1}(S\_t=s) $$ I wonder why do we need both $\gamma$ and $\lambda$ to assign credit to most recent states.

# Answer
At least for gamma I can answer it generally without looking in the book:

Gamma is commonly used as the discount factor. That is a number in (0, 1) which defines how much of the reward you got in step i will be also given to step (i - n). Commonly, the reward is discounted exponentially (like gamma^n)
> 1 votes

# Answer
I was also wondering that, I think I understand it, but I'm having a difficult time proving it.

The principle of using eligibility is that over a large sum you get the same result going backward as you would if you went forward (but you get the additional bonus of being able to update online).

Concerning λ: You use λ the same way as with the forward looking TD(λ) - as a exponential coefficient in a geometric series .

Concerning γ : Looking at the expression for the change in value: $$ \delta\_t(s) = R\_{t+1} + \gamma\*V\_t(s\_{t+1}) - V\_t(s\_t) $$ and $$ V\_{t+1}(s) = V\_t(s) + \alpha\* \delta\_{t+1}\*e\_{t+1}(s) $$ And you do that for EVERY step at EVERY time step, but there's no discount in δ nor in V. So, the future rewards get a discount only if γ is included in the E\[s\].

I'm also pretty sure that it makes all the other expressions cancel each other out in the sum (except for the rewards and the latest V\[s\]) , because for #lambda = 1 this should be the same as Monte Carlo:

$$ (\lambda = 1): V\_{t+1}(s) = V\_t(s) + \alpha\* \delta\_{t+1}\*e\_{t+1}(s)=V\_t(s) + \alpha\* \Sigma \gamma^nR\_{n}(s) $$

But I can't prove that yet.
> 0 votes

# Answer
I was also thinking about this and eventually understood it this way:

Gamma is a parameter of the environment the agent is operating in (yes we can change it, but policies can only be evaluated and improved in relation to a single value of gamma).

In order for the backwards update to accurately reflect the amount of reward that a previous state will will be able to reach in the future, that reward must be discounted my gamma the appropriate number of times to accurately reflect the environment.

Lambda is used to determine how easily a signal from the current state can propagate backwards through previous states.

Essentially gamma determines how quickly reward decays, and lambda determines how quickly credit decays. We need to use both to determine how much to attenuate the reward signal we send backwards in time.
> 0 votes

---
Tags: machine-learning, reinforcement-learning
---


# Question
Title: Best C++ STL container to store bodies in an N-body simulation?
I am writing an N-body simulation in C++ that has to be able to deal with large N ($N \le 10^6$).

Everything has been going well so far, but now that I have started to code in collisions between bodies (which can result in mergers - which means that one body is added to the system and two are removed) I cannot help but wonder whether there is a more suitable data structure than the `std::vector` (which I have been using so far).

Given that each body in the system has a unique ID, I have thought of storing all bodies in an `std::map` (to allow fast lookup by ID), but, at the same time, I have to repeatedly iterate over all bodies (in direct integration methods) and consider each pairwise interaction ($n\_{interactions}=\frac{N(N-1)}{2}$), for which (I believe) the `std::vector` is faster than the `std::map`.

What would be the best data structure for this, given that I have to iterate repeatedly over all bodies, but also have to be able to add and remove bodies?

# Answer
> 1 votes
Presumably all the accesses to the bodies that you need to perform are sequential, so a linked list would be a good candidate. (By the way, I would not delete two bodies and insert a new one, but update one and delete the other.)

Anyway, before rushing to replace the data structure, I would compare the cost of the integration step ($O(n^2)$) and that of the vector update ($O(n)$ or less) to check if it is worth the effort.

Should I add that *if order does not matter*, insertions/deletions in an array are made in constant time ?

---

Though the difference between direct and indirect accesses will be tiny, I would expect a non-vector solution to be slower.

# Answer
> 2 votes
Why choose? You can have it both ways:

1. a vector that contains all the bodies, and,
2. a map from ID to index in that vector

Any simple modification of the vector (push\_back, swap, pop\_back) would also only require a simple modification of the map, and you can use these operations to remove an element from the middle of the vector by doing an unordered-remove (swap the removed element with the last element, then pop\_back)

# Answer
> 2 votes
With $N=10^6$ bodies, the obvious method to track their movements by having a system of simultaneous differential equations taking $\mathcal{O}(N^2)$ operations per step with a rather large constant will take you ages.

There is a faster method, as far as I know, that takes $\mathcal{O}(Nlog(N))$ operations; I've only read about it, so you'll have to look it up yourself. You then design your data structures so that the implementation is as fast as possible.

# Answer
> 2 votes
If you want to find collision pairs for $10^6$ objects, I would suggest using a spatial data structure (as suggested by @D.W. in the comments).

For collision detection, some useful structures are quadtrees, R-trees and BVH.

For collision detection you usually want window queries (rectangular query windows) and **not** nearest neighbor queries (which technically can be used but are usually much slower).

As far as I can tell R-Trees (e.g. Boost R-Tree) have the best performance for window queries, however they are quite slow to update. Quadtrees are much faster to update.

There is for example the Point Cloud Library and libSpatialIndex which both provide several implementations of spatial indexes.

A special type of quadtree is the PH-tree for C++ (disclaimer: self advertisement), for a 1M point dataset it allows around 1M updates per seconds and 500K small window queries per second on my 5 year old desktop. Smaller datasets are obviously faster. For 10K points it would be 5-10M updates per second and 5M queries per second.

---
Tags: data-structures, trees, memory-management, c++, physics
---


title: How executable binary can be signed?

text:
# Question
Title: How executable binary can be signed?
Some devices (for example Android devices) are "locked", the bootloader checks following bootloader/software sign, right? Chain of trust. Signing technically means that the file must be encrypt with one (private) key and decrypted with another (public) key.

The software is compiled to executable binary and if we then sign/encrypt it, it's a mess (not machine code); so how hardware can execute it after verifying the sign?

How an executable binary can be signed and working machine code at the same time?

# Answer
Let's start with a simple approach: Stored on your hard drive is a 1 to 1 image of an executable file. Your operating system allocates space for the executable file, reads it from the hard drive, and transfers control to the address where the executable file should start execution. That works just fine.

Now we can make it more complicated: When we create the executable file on the hard drive, compiler and linker create an image of the executable file, then they compress the executable file, then they encrypt it with your public key, then create a checksum using their private key. No loading the executable file into memory is just slightly more difficult:

Your operating system reads what is on the hard drive. Then it uses the compilers public key to check if the checksum is correct. If it is correct, then the operating system knows that only the genuine compiler could have created the checksum, so the data is genuine and not forged by a hacker.

Then the data is decrypted using your private key. This will only work if the compiler used your public key to encrypt the data. So if a hacker manages to get a copy of the encrypted data, they cannot decrypt it without your private key. So the compiler is now sure that the executable file didn't fall into the wrong hands.

Next the data is decompressed - that's only done to save time to transmit the executable. There are actually computers where reading say 1MB of data and decompressing it to 2MB is both faster, and saves space on your hard drive. That's the reason for this step, to save some space.

Well, and at that point the data is in RAM and execution can start, just as before. The only difference with the three steps (compression, encryption, checksum) is that we save some space and possibly time due to the compression, that the compiler knows the code didn't go to some hacker, and that your computer knows it wasn't a hacker producing the code.
> 1 votes

---
Tags: operating-systems, binary
---


# Question
Title: Reversible computing as a path to a useful PRNG or hash function?
There's a question I've long had about reversible computing: do non-trivial algorithms usually end up generating strongly pseudorandom data as an artifact of the computation?

The most straightforward example of this would be if you used Fredkin gates or equivalent to wire together a binary multiplier circuit. My understanding is that implementing this, along with most reversible computing tasks, necessitates generating "junk bits" as a byproduct which get channeled along but ultimately ignored.

In the case of a multiplier, if the junk bits had any straightforward or simplistic correlation to the output value, there would potentially be a mechanism for fast factorization of semiprimes; you could essentially run the program in reverse, filling in the product and the junk bits and discovering the factors.

Of course, the problem is determining the junk bits. Presumably a semiprime product must have virtually no bearing on what the junk bits have to be to successfully reverse the program, aside from maybe the conservation of overall bit count. If this is the case, it seems like that could provide a strong method for the generation of pseudorandom data or hash values.

This seems like something that has surely been thoroughly studied, but I haven't been able to find anything in my searching. I'm hoping someone can either explain whether this does or doesn't work as I suspect, or point me towards relevant reading material. I'm mostly interested in something like the specific example I provided, but also any general results about the degree of randomness of junk data in reversible computing would be nice as well.

# Answer
> 2 votes
I am not aware of any reason to believe that the junk bits will be strongly pseudorandom (for instance, in the sense of polynomial-time indistinguishability from random or cryptographic pseudorandomness), and I would be surprised if they were for most algorithms. I would not expect this to provide a strong method for generation of pseudorandom values.

---
Tags: hash, number-theory, cryptography, one-way-functions, reversible-computing
---


title: Using undecidability to prove P != NP

text:
# Question
Title: Using undecidability to prove P != NP
Given the challenge of proving algorithmic bounds on the likes of 3-SAT to resolve P versus NP, I wondered whether it might be possible to use undecidability **within** an NP problem to ensure that we can never find **any** algorithm as an alternative to brute force. I couldn't find any references on this type of idea.

After playing with a number of problems I ended up back at a version of the halting problem as follows: **for a given machine M, is there an n-bit input x such that M halts after n steps?** Any particular solution can be checked in O(n) polynomial time by running the input on M and seeing if it halts after n steps.

However, to find a solution x out of a possible 2^n, the undecidability of the halting problem says in general we cannot know in advance if M will halt on any particular input, and the probability of halting cannot be known because it would contract this (Chaitin). Therefore we have to go through all possible O(2^n) programs until we find one that halts after n steps, while stopping all other candidate solutions after n+1 steps. This might therefore be an NP problem where undecidability ensures there is no polynomial time algorithm to solve it.

I'm new to complexity theory so would appreciate any feedback on potential flaws people see in this approach. Any related references also gratefully received. Thanks

# Answer
> 1 votes
I don't think the approach you outline is valid.

> Therefore we have to go through all possible

Your "Therefore" does not follow. This is not an accurate deduction.

For one thing, the halting problem talks about decidability, i.e., existence of an algorithm that has unlimited time. Your problem asks about the case where the running time is limited to 2^n.

For another thing, there is no reason to believe one has to go through every possible input. It might be possible to quickly rule out some inputs, e.g., because they don't have the correct format and are rejected within the first few steps of the algorithm.

---
Tags: complexity-theory, np, halting-problem, p-vs-np
---


title: the size of nice tree decomposition

text:
# Question
Title: the size of nice tree decomposition
Recently, I am reading paper An Upper Bound for Resolution Size: Characterization of Tractable SAT Instances, which use tree decomposition to give an upper bound for SAT resolution refutation.

For a given nice tree decomposition $T=(V(T),G(T))$.

**My question:** Why $O(3^{treewidth})\*V(T)$ is still $O(3^{treewidth})$

my question comes from the process of proving Theorem 3 from Lemma 2

# Answer
> 1 votes
I don't see the claim that $O(3^{tw}) \cdot |V(T)| = O(3^{tw})$, as you mention.

Instead, $O^\*(3^{tw}) \cdot |V(T)| = O^\*(3^{tw})$. The notation $O^\*$ is a shorthand used to suppress polynomial factors in the input size $n$. You should read $O^\*(3^{tw})$ as $O(3^{tw} \cdot \text{poly}(n))$.

---
Tags: trees, satisfiability, big-o-notation
---


# Question
Title: Solving a recurrence relation formula with squared
I hope someone can help me with that: $$T(n)=T(2^{\sqrt{\log n}})+1$$

I will be asked to answer what is the runtime complexity of the algorithm.
I tried to set m=2^ and still failed.

# Answer
> 2 votes
Assuming base-$2$ logarithms, we set

$$n=2^{2^{2^m}}$$ and transform

$$T\left(2^{2^{2^m}}\right)=\\ T\left(2^{\sqrt{\log\left(2^{2^{2^m}}\right)}}\right)+1 =T\left(2^{\sqrt{{2^{2^m}}}}\right)+1 =T\left(2^{2^{\left(2^m\right)}/2}\right)+1 =T\left(2^{2^{2^{m-1}}}\right)+1 .$$

This is of the form

$$S(m)=S(m-1)+1$$ and has the simple solution

$$S(m)=S\_0+m.$$

Hence,

$$T(n)=T\_4+\log(\log(\log(n))).$$

---
Tags: algorithms, runtime-analysis, recurrence-relation
---


# Question
Title: Polynomially many instances imply a polynomial reduction?
I have a language $L$ which is NP-hard and I have another language $L\_1$, s.t. if I take an instance $q$ of the decision problem corresponding to $L$, and if one of polynomially many instances, $f\_1(q),\ldots,f\_{p(|q|)}(q)$ is in $L\_1$, then $q\in L$.

Is this enough to say that $L\_1$ is NP-hard?

# Answer
> 1 votes
Do you have a polynomial-time algorithm to construct those polynomially instances? If you can construct those polynomially many instances in polynomial time, then you have a Cook reduction (also known as a polynomial-time Turing reduction), not a many-one reduction. So your question then becomes: if we have a Cook reduction from $L$ to $L\_1$, and if $L$ is NP-hard, then does it follow that $L\_1$ is NP-hard?

The answer depends on the definition of NP-hard that you use, which is a little tricky, so let me start with a simpler question:

If we have a Cook reduction from $L$ to $L\_1$, and if $L$ is NP-complete, then does it follow that $L\_1$ is NP-complete? Answer: No. But it is strong evidence, if it is also known that $L\_1$ is in NP. NP-completeness is defined in terms of many-one reductions, not Cook reductions. The existence of a Cook reduction is not currently known to imply the existence of a many-one reduction (it is a famous open problem, and it might be true - we don't know of any counterexamples - but we don't have a proof of such an implication). See Graph problem known to be $NP$-complete only under Cook reduction, Can we construct a Karp reduction from a Cook reduction between NP problems?.

Back to the question about NP-hardness. That is harder to answer, because there is not universal agreement about what precisely NP-hard means. There are multiple reasonable ways to define NP-hard. One definition is in terms of many-one reductions ($H$ is NP-hard if for every $G$ in NP, there is a many-one reduction from $G$ to $H$), and another definition is in terms of Cook reductions ($H$ is NP-hard if for every $G$ in NP, there is a Cook reduction from $G$ to $H$). The answer to the question is "no" for the first, "yes" for the second.

In particular, if we have a Cook reduction from $L$ to $L\_1$, and if $L$ is NP-hard under Cook reductions, then it does follow that $L\_1$ is NP-hard under Cook reductions. If we have a Cook reduction from $L$ to $L\_1$, and if $L$ is NP-hard under many-one reductions, then it is not known whether this implies $L\_1$ is NP-hard under many-one reductions (in particular consider $L$ to be SAT and $L\_1$ to be the complement of SAT; then if NP $\ne$ co-NP, as is widely conjectured, then $L$ is NP-hard under many-one reductions but the complement of SAT is not NP-hard under many-one reductions). See also If a problem is Cook-NP hard, and this problem is in NP, does it prove that the problem is Karp-NP-complete?.

Finally, if you don't have a polynomial-time algorithm to construct those polynomially instances, then you cannot conclude anything at all. For instance, consider the case where $L\_1$ is a language in P, and $L$ is 3SAT; if you have exponential time, you can determine whether $q$ is in $L$, and then let $f\_1(q)$ be a member of $L\_1$ if $q$ is in $L$ or a non-member of $L\_1$ if $q$ is not in $L$.

---
Tags: np-complete, np-hard, polynomial-time-reductions
---


# Question
Title: Why do some "common sense" $P \ne NP$ arguments seem to disregard high-degree polynomials?
I've seen arguments for $P \ne NP$ that rely on certain intuitions about how the real world actually is, generally making the point that it "makes sense" that there exist problems which have an *easily verifiable* solution that's *hard to find.*

For example, on his blog, Scott Aaronson has a "Reasons to believe" entry which contains (among others) the following points:

> **8. The Self-Referential Argument.** If P=NP, then by that very fact, one would on general grounds expect a proof of P=NP to be easy to find. On the other hand, if P!=NP, then one would on general grounds expect a proof of P!=NP to be difficult to find. So believing P!=NP seems to yield a more ‘consistent’ picture of mathematical reality.

> **9. The Philosophical Argument.** If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett. It’s possible to put the point in Darwinian terms: if this is the sort of universe we inhabited, why wouldn’t we already have evolved to take advantage of it? (Indeed, this is an argument not only for P!=NP, but for NP-complete problems not being efficiently solvable in the physical world.)

> **10. The Utilitarian Argument.** \[$^1$\] Suppose you believe P!=NP. Then there are only two possibilities, both of which are deeply gratifying: either you’re right, or else there’s a way to solve NP-complete problems in polynomial time. (I realize that I’ve given a general argument for pessimism.)

But the way I see it, once you step down from the abstractions of complexity theory and start talking about actual reality, then the concept of "polinomiality" seems to lose most of its weight and $P$ feels unimportant. Instead of supporting the idea that $P \ne NP$, these arguments could just as well merely support the idea that any $NPC$ problem has a lower-bound of $\Omega(n^k)$, for a *decently sized* $k$.

But I am not an expert, so I am missing some context; for example, nuanced analyses of "real" algorithms on "real sizes" of inputs. So is there something more to the robustness of this kind of arguments, or are they overblown?

---

$^1$ point 10 is worded in such a way that doesn't really fit my selection, but I feel that in the given context, the author did intend to conflate "solve in polynomial time" with "feasibly solve", hence why that would be gratifying.

# Answer
> 1 votes
The $P/NP$ conjecture is about theoretical complexity classes. It is *not* about practical running times. You cannot run a $\Theta (n^{10})$ algorithm on with $n=40$ elements in reasonable time, and you can very well run a $\Theta(2^n)$ algorithm with $n=40$.

The distinction is more qualitative than quantitative, and the border is neat.

---

Said differently, if you push a polynomial algorithm to the largest $n$ that can be handled in your time frame, in general $n+1$ won't make a real difference. For an exponential or super-exponential algorithm, $n+1$ could be out of reach.

# Answer
> 0 votes
> Why do some "common sense" ... arguments ...

I'm not sure if this question is on topic here, however ...

"Common sense" arguments often lead to completely wrong results:

This is not only the case for proofs but also for estimations of values that are only very difficult to calculate. The birthday paradox is one example for this.

And the arguments you cited do not only disregard high-order polynomials (like $\Omega(n^{1000})$) but they already don't work for $\Omega(n^1)$:

Argument 8 for example assumes that some $\Omega(n)$ task is "easy" if it is easy to prove the correct result.

However, both German and English languages even have a proverb based on a counterexample:

> Finding a needle in a haystack ...

... has a time complexity of $\Omega(n)$ and proving the "positive" result is very easy.

# Answer
> 0 votes
Of course it is a possibility that $\mathrm{P} = \mathrm{NP}$, and the best algorithm for SAT takes $O(n^{1000!})$. However, this feels much ***weirder*** than having an $O(n^3)$ algorithm for SAT (with reasonable coefficients). The reason for this feeling weird is the following heuristic:

> Naturally occurring natural numbers tend to be $0$, $1$ or $2$, but at most $4$.

Obviously, this doesn't apply to all fields, but it works out quite well for complexity theory and adjacent fields. For example, when we do find a polynomial-time algorithm for an interesting problem, it really tends to have at most cubic runtime. For kSAT, only the $k = 1,2,3$ cases really matter. Planar graphs are special, but we don't care about whether a graph embeds into $\mathbb{R}^{10}$ or not. In computability theory, interesting problems are decidable, equivalent to the Halting problem or equivalent to the Halting problem iterated once. Once we talk about stuff computable relative to $\emptyset'''''$ it has gotten very weird.

# Answer
> -1 votes
It seems that all the mass in the universe, converted to energy, is not enough to perform $2^{256}$ state changes. So an $n^{256}$ algorithm cannot even finish for n = 2.

But assume we find an algorithm that solves instances of size n in $n^{10}$ nanoseconds. Then we can solve instances of size 8 in a second, size 25 in a day, size 45 in a year, size 340 in a billion years.

So we would have a polynomial algorithm that isn’t really satisfactory. A $2^n$ nanosecond algorithm could solve problems of size 30 in a second, 46 in a day, 55 in a year, 85 in a billion year. This exponential time algorithm beats the $n^{10}$ algorithm for cases taking many years.

So even moderately high degree polynomials are not really helpful in many cases.

---
Tags: complexity-theory, p-vs-np, philosophy
---


# Question
Title: Finding the nodes in the source and sink side of a min-cut
We are learning of the Ford-Fulkerson Algorithm for max-flow/min-cut, and I have been wondering of the following question:

How do we exactly find which nodes are on the "sink" side of the min-cut produced using the algorithm?

I have read here https://www.geeksforgeeks.org/minimum-cut-in-a-directed-graph/ that all nodes reachable from the source node on the final residual graph using a BFS/DFS are on one side of the min-cut.

Then, will all nodes not reachable from the source node on the final residual graph be on the other side of the min cut? Is there any way of finding these nodes using a search algorithm of some sort - for example, reversing the edges of the final residual graph and running a BFS/DFS on the sink node?

Thanks a lot!

# Answer
You can prove that any minimal s-t-cut results in two connected components, the one with s in, and the one with t in. Call them S and T.

Then the actual cut is all the edges that go from S to T.
> 2 votes

---
Tags: network-flow, minimum-cuts, ford-fulkerson
---


# Question
Title: What is the complexity for the universality problem for a NFA with all states accepting?
It is well known that the universality problem for NFA (deciding whether $L(A)=\Sigma^\*$) is $PSPACE$-complete. However, what if every state of the NFA is known to be accepting? It seems to me that the problem is at most in $co$-$NP$, as a counterexample (unlike in the case of a general NFA) is polynomial (even linear) in the size of the input (the number of states). What is the complexity of this problem?

# Answer
> 5 votes
You problem is PSPACE-complete. I prove that it's PSPACE-hard by reducing universality of NFAs to universality of NFAs with all states accepting.

---

Let $A$ be a NFA. Add a new final state $q\_\\$$ to it and for every accepting state $q$, add a transition $q\overset{\\$}{\to}q\_\\$$ where $\\$$ is a fresh letter. For every letter $a\in \Sigma\sqcup \\{\\$\\}$, also add a transition $q\_\\$\overset{a}{\to}q\_\\$$. And then make all states accepting. The new automaton accepts $L(A)\\$ (\Sigma\sqcup \\{\\$\\})^\* \sqcup L'$ for some $L'\subseteq \Sigma^\*$.

Now, add some automaton (with all states final) that recognizes the language $\Sigma ^\*$ (i.e. the language of words that don't contain $\\$$) in parallel. The new automaton will recognize $L(A)\\$ (\Sigma\sqcup \\{\\$\\})^\* \sqcup (L' \cup \Sigma ^\*)=L(A)\\$ (\Sigma\sqcup \\{\\$\\})^\* \sqcup \Sigma ^\*$.

Now, notice that we have $L(A)=\Sigma^\*$ iff $L(A)\\$ (\Sigma\sqcup \\{\\$\\})^\* \sqcup \Sigma ^\*=(\Sigma\sqcup\\{\\$\\})^\*$. I.e. the process I described is a reduction from universality of a NFA to universality of a NFA with all states accepting. Since the reduction is polynomial, your problem is PSPACE-hard.

# Answer
> 4 votes
As mentioned in the comments, @xavierm02's answer has a bug. One can try and fix it, but here is a simpler construction \[Kao, Rampersad, Shallit\]. Given an NFA $A = (\Sigma, Q, q\_0, \delta, F)$ with a single initial state, one can return the NFA $B$ that is obtained from A by turning all of its states to accepting states, and by adding #-labeled transitions from every state in F to the initial state $q\_0$, where # is a new letter.

If $L(A) = \Sigma^\*$, then it is easy to prove that $L(B) = (\Sigma \cup \\{\\#\\})^\* $. An accepting run of $B$ on an input $x$ with no #'s follows an accepting run of $A$ on $x$. Otherwise, we can write $x = z\_1\cdot \\# \cdot z\_2 \cdot \\#\cdots \\# \cdot z\_{n-1}\cdot \\# z\_n$, where all the $z\_i$'s are words over $\Sigma$. Then, an accepting run $r$ of $B$ on $x$ operates as follows. Upon reading an infix $z\_i$, $r$ follows an accepting run of $A$ on $z\_i$, and then goes back to $q\_0$ upon reading the next #.

Conversely, if $L(B) = (\Sigma \cup \\{\\#\\})^\*$, then in particular for all words $x$ over $\Sigma$, $B$ has an accepting $r$ run on the word $x\cdot \\#$. Consider the last transition that $r$ traverses, it must be a transition of the form $\langle q\_f, \\#, q\_0 \rangle$, where $q\_f$ is some state in $F$. So, since non-# transitions in $B$ are transitions of $A$, then $r$ starts by following an accepting run of $A$ on $x$, and thus $x\in L(A)$.

# Answer
> 0 votes
It should be noted that **Unary** ($|\Sigma|=1$) **all-accepting NFA universality** becomes a **Directed Graph cycle-detection problem** and is in P

---
Tags: complexity-theory, regular-languages, finite-automata
---


# Question
Title: Definition of the term "small systems" in computer science
What is the definition of the term "small systems" in the context of computer science? My professor didn't really define the term, they just gave examples of some small systems. I'm having a hard time finding a concrete definition of the term online. This is not a homework question. I just want to know the definition so I can better understand the course.

# Answer
> 1 votes
There is not a precise, standard, accepted definition of that phrase. What counts as "small" is likely a subjective matter, and probably depends on context.

---
Tags: definitions
---


# Question
Title: Is there a practical algorithm for estimating antichain coverage of a superset?
Suppose I'm given a set $S$ and antichain $A \subset 2^S$ ($\forall a\_1,a\_2\in A: a\_1\neq a\_2 \iff a\_1 \nsubseteq a\_2$).
Let's call subset $b \in 2^S$ *covered by* $A$ if $\exists a \in A :b \subseteq a $.

I'm looking for a way to answer "**What part/what percentage of $2^S$ is covered by $A$?**"

Due to $|S|\>100$, it's infeasible to check all subsets.
Due to $|A|\>100$, it's infeasible to euler-diagram all cover intersections.

Randomly generating subsets is a solution, but
a) it won't be useful on extremely low and extremely high coverage (like $A$ consisting of only 1 subset containing half of $S$ will be undetectable)
and
b) quantitively comparing coverage of different antichains may be complicated due to noise

I've tried looking in literature, but my scholar-googling skills aren't great.
I hope you have any ideas.

# Answer
> 1 votes
I suggest you use inclusion-exclusion.

Let $A=\\{a\_1,\dots,a\_n\\}$. Let $B\_i$ denote the set of all subsets of $a\_i$, i.e., $B\_i=\\{b \in 2^S \mid b \subseteq a\_i\\}$. The inclusion-exclusion principle says that

$$\Big| \bigcup\_i B\_i \Big| = \sum\_i |B\_i| - \sum\_{i\<j} |B\_i \cap B\_j| + \sum\_{i\<j\<k} |B\_i \cap B\_j \cap B\_k| - \cdots$$

If you truncate this after $k$ terms, you get an approximation to the left-hand side, and you can compute this approximation in $O(n^k)$ time. Here you should use the fact that $|X|=2^{|X|}$, so we can efficiently compute

$$|B\_i \cap B\_j \cap B\_k| = |2^{a\_i \cap b\_i \cap b\_k}| = 2^{|a\_i \cap b\_i \cap b\_k|}.$$

If you truncate after 3 or 4 or 5 terms, you'll probably get a pretty good approximation, and I'm guessing it'll be tractable to compute.

---
Tags: sets
---


# Question
Title: Will the Ford-Fulkerson Algorithm always return the same min-cut for any source-sink from one side of the min-cut to the other?
I was playing around with https://visualgo.net/en/maxflow when I realized a pattern:

Take this graph, for example. We notice that the min-cut divides the graph into two sets of nodes: {0, 2, 3, 6} and {1, 4, 5, 7}.

I noticed that choosing any node within {0, 2, 3, 6} as a source and {1, 4, 5, 7} as a sink, or vice versa, produces the same min-cut edges.

Is this true in general? As in, will the min-cut produced be the same for any source-sink pair from one-side of a min cut to the other?

# Answer
> 1 votes
That is an interesting observation.

However, the propostion is not true in general. For a counterexample, consider the flow network with capacities $c(\overrightarrow{AB})=2$, $c(\overrightarrow{BC})=1$ and $c(\overrightarrow{AC})=1$.

Let $A$ be the source and $C$ be the sink. The unique min-$A$-$C$-cut is $(\\{A,B\\}, \\{C\\})$.

Let $B$ be the source and $C$ be the sink. The unique min-$B$-$C$-cut is $(\\{B\\}, \\{A,C\\})$.

---
Tags: network-flow, minimum-cuts, ford-fulkerson
---


# Question
Title: Is deciding whether a graph admits two vertex-disjoint spanning trees of bounded size difference NP-hard?
I'd like to decide whether, given a connected graph $G = (V, E)$ and an integer $k$ as input, $G$ admits two vertex-disjoint subgraphs $T\_1 = (V\_1, E\_1)$ and $T\_2 = (V\_2, E\_2)$ such that $T\_1$ and $T\_2$ are trees, $V\_1 \cup V\_2 = V$ (so in some way they are spanning), and $|V\_1 - V\_2| \leq k$ (they aren't too different in size).

Some graphs, such as perfect binary trees or Hamiltonian graphs, do admit such balanced spanning trees ($k=o(1)$), whereas others do not, such as star graphs ($k = n - 2$).

Is this NP-hard? Is it already NP-hard when fixing $k=0$? Also, is the smallest $k$ for which such trees can be found a known parameter, like maybe \`\`balanced vertex-disjoint spanning tree distance'' or something? I did not find any information on vertex-disjoint spanning trees like this, I always end up with an article on edge-disjoint spanning trees (which each individually are spanning).

EDIT: vertex-arboricity (*resp.* equitable vertex-arboricity) seems quite close, but here one aims to partition the vertices such that their induced subgraph is a forest (*resp.* forests of the same size). They don't seem interested in the exact number of partitions (whereas I fix it to two) and I'm not interested in induced subgraphs or forests.

# Answer
For $k = 0$, this problem is equivalent to the problem known as *Balanced Connected Vertex 2-Partition problem*: given a graph $G = (V,E)$, find a partition of the vertex set $V = V\_1 \cup V\_2$ such that $|V\_1| = |V\_2| = |V|/2$ and the induced subgraphs $G\[V\_1\]$ and $G\[V\_2\]$ are connected. Note that if an induced subgraph $G\[V\_i\]$ is connected then we can take a spanning tree of it as $T\_i$.

This problem is NP-hard even for bipartite graphs \[1 Theorem 2.2\]. For the approximation version of this problem, see this question on TCS.SE Partition a graph into 2 connected subgraphs.
> 2 votes

---
Tags: graphs, partitions, spanning-trees
---


title: pairing numbers and intervals

text:
# Question
Title: pairing numbers and intervals
subject: pairing numbers and intervals

Let `NUMBERS` be a list of `n` integer numbers. The numbers are listed in no specific order. Duplicates are possible.

Let `INTERVALS` be a list of `m` intervals. The low and high limits of the intervals are integer numbers. The intervals are listed in no specific order. Duplicates are possible.

We want to pair the numbers and intervals as thus:

* A number can only be paired with an interval to which it belongs. For example, `4` and `[3, 10]` can be paired, `4` and `[5, 10]` cannot.
* A number cannot be paired with more than one interval.
* An interval cannot be paired with more than one number.
* The number of pairs is maximal.
* We are not interested in the pairs themselves, only in the (maximal) number of pairs.

To summarize:

* input = `NUMBERS`, `INTERVALS`
* output = maximal number of pairs

Example 1:

* `NUMBERS` = `2`
* `INTERVALS` = `[4, 10]`
* output = `0`

Example 2:

* `NUMBERS` = `2`
* `INTERVALS` = `[2, 10]`
* output = `1`

Example 3:

* `NUMBERS` = `3, 7, 8, 12`
* `INTERVALS` = `[0, 10], [5, 15], [20, 25]`
* output = `2`

It is relatively simple to devise an `O(n*m)` algorithm to solve this problem. I seriously doubt that there exist any `O(n) + O(m)` algorithm, but what about an `O(max(n*log(n), m*log(m), n*log(m), m*log(n)))` algorithm?

# Answer
Your problem is equivalent to the problem of finding a maximum matching in a *convex bipartite graph* (a bipartite graph $G=(A,B,E)$ where the vertices on one side, say $A$, admit an ordering $a\_1,\ldots,a\_n$ such that each vertex in $B$ is adjacent to an interval $a\_i,\ldots,a\_j$ for some $1\leq i\leq j\leq n$). Googling "maximum matching convex graphs" I found this paper: A Linear Time Algorithm for Maximum Matchings in Convex, Bipartite Graphs (by G. Steiner and J. S. Yeomans) that claims the problem is actually solvable in time proportional to $|B|$! So, in your case, the problem is solvable in time $O(m)$.

EDIT: Both this paper and others require you to represent the neighborhood of each vertex $b$ in $B$ by the first and last (in the implied ordering) vertex in $A$ that is adjacent to $b$. This requires you to sort the integers (in $O(n \log n)$ time) and replacing each interval with the indices of the first and last integer that is contained in the interval (in $O(m \log n)$ time). Thus we reach your guessed time-bound (unless, of course, there is some clever way to accomplish this without sorting). My bad for not spotting this right away.
> 0 votes

---
Tags: algorithms, matching, intervals
---


# Question
Title: Convex polygon triangulation with stabbing number O(log n)
The stabbing number of a triangulated simple polygon P is the maximum number of diagonals intersected by any line segment interior to P. Give an algorithm that computes a convex polygon triangulation with stabbing number O(log n).

A convex polygon with n vertex is given, assuming n is even for simplicity. I've already triangulate the polygon taking the vertex v(1) and linking it to the vertex v(3) and so on v(3) to v(5) with the logic of v(i) to v(i+2). In this way I generate a sub polygon using n/2 diagonals and then repeat this process with the sub polygon until I get a triangle. In this way I always triangulate the polygon using n/2 diagonals where n is the number of vertex of the sub polygon.

Now that the polygon in triangulated in O(log*n*), I got stuck. If I draw a segment inside the triangulated polygon, with the aim of intersect the maximum possible number of diagonals, I always intersect more than log*n* diagonals. So I assume that what the problem is asking is not to have a precise log*n* stubbing number, but still I don't have an answer.

# Answer
> 1 votes
In the recursive triangulation you consider, you roughly divide the number of vertices by $2$ at each level of recursion. Thus, there are $O(\log n)$ levels of recursion. Consider some segment $S$. Among all the diagonals added at some level of recursion, $S$ can intersect at most $2$ (try to prove it!), so in total it intersects at most $2\cdot O(\log n) = O(\log n)$ diagonals.

# Answer
> 1 votes
By linking every other vertex, you create an inner convex polygon of $\left\lceil\dfrac n2\right\rceil$ sides, which can only be intersected twice by a line segment. By induction, there will be $O(\log n)$ intersections.

---
Tags: algorithms, computational-geometry, polygons, triangulation
---


# Question
Title: Local minimum in array, find $O(\log n)$ algorithm
## Main Problem

Given an array $A\[1...n\]$ ($n \geq 3$) of distinct integers with at least a local minimum, output a local minimum. A local minimum is an integer $1 \< i \< n$ such that $A\[i-1\] \> A\[i\] \< A\[i+1\]$.

Find an $O(\log n)$ algorithm or prove such an algorithm doesn't exist

### Notes

It could be useful to have an $O(1)$ property to know if $A\[i...j\]$ has a local minimum. So far I know that:

1. if $\[\]\>\[+1\]$ and $\[−1\]\<\[\]$ then $\[...\]$ has a local minimum

### Related Problems

1. $1$ and $n$ are also considered a local minimum

Certainly, in this case, the absolute minimum is also a local minimum

A solution is

```
int fun(int[] A, int i, int j)
------------------------------
 if i == j then
  | return i
 else
  | int m = floor((i+j)/2)
  | if A[m-1] > A[m] < A[m+1] then
  |  | return m
  | else if A[m] > A[m+1] then
  |  | return fun(A, m+1, j)
  | else
  |  | return fun(A, i, m-1)
  |  -
  -

```

The intuitive idea behind this algorithm is that:

```
    .
   /
  .
 /
.

=> local minimum on the left

```

```
.
 \
  .
   \
    .
=> local minimum on the right

```

```
  .
 / \
.   .
=> local minimum on both sides

```
2. $A\[1\] \> A\[2\]$ and $A\[n-1\] \< A\[n\]$

The previous solution also works in this case, but the proof is different

# Answer
Considering the case where A\[1\] \< A\[2\] \< A\[m-1\] \< A\[m\] \< A\[m+1\] \< A\[n-1\] \< A\[n\]

```
              o
             /.
            o .
         ...  .
         o    .
        /     .
       o      .
      /.      .
     o .      .
   ... .      .
  o    .      .
 /     .      .
o      .      .
.      .      .
.      .      .
1      m      n

```

Suppose p.a. that there exists a property that in $O(1)$ allows us to determine on which half to recur, i.e., by accessing the elements at index $l\_1, l\_2, ..., l\_k$ we determine whether $A\[1...m\]$ has a local minimum or not. If the adversary uses the strategy $l'\<l'' \implies A\[l'\] \< A\[l''\]$, certainly the algorithm concludes that $l$ are not a local minimum.

If the algorithm concludes that $A\[1...m\]$ has a local minimum $h$, then $1 \< h \< m$ and $h \neq l ~ \forall l$. The adversary can always make $h$ not be a local minimum (i.e. with the different strategy $l'\<l'' \implies A\[l'\] + n \< A\[l'\]$ and $A\[h\]$ such that it forms an increasing sequence).

Any other non-constant property $\Theta(f(n))$ makes the algorithm greater than $\Omega(\log n)$

$T(n) = T(n/2) + \Theta(f(n))$

Also, note that even with $k=m-4=\Theta(n)$ (that is, by accessing all elements in $A\[1...m\]$ except a certain $h$) the same absurdity applies, so a lower bound of the problem is $\Omega(n)$

By defining as a local minimum $1 \leq h \leq n$ the algorithm wins by choosing $h=1$.
> 0 votes

# Answer
In the general case, it is impossible to solve this in time $O(\log(n))$, as is shown by an adversary argument.

Take *any* minimum finding algorithm, and for every $A\[i\]$ value it queries, the value is $i$, except for the very last, which forms the only local minimum configuration. This obviously has complexity $\Theta(n)$, which is the worst case.

\[You can replace the $i$ sequence by any other growing sequence of any length $\Omega(n)$.\]
> 1 votes

---
Tags: algorithms, arrays
---


# Question
Title: A Problem with Solving a Recurrence relation
I Hope someone Can help me with that:

* $T(1)=2$
* $T(n)=\left(T(\frac{n}{2})\right)^2\cdot2^n $

what is the runtime complexity of the algorithm (base 2) Thanks a Lot!

# Answer
Let $n:=2^m$ and take the logarithm.

$$\log(T(2^m))=2\log(T(2^{m-1}))+2^m$$

or

$$S(m)=2S(m-1)+2^m.$$

By educated guess (or alternative methods), the solution is

$$S(m)=(m+S\_0)2^m$$

so that

$$T(n)=2^{(\log(n)+\log(T\_1))n}=\left(T\_1n\right)^n$$
> 1 votes

---
Tags: runtime-analysis, recurrence-relation
---


# Question
Title: Difficulty Understanding a Quick Method for Finding the Two's Complement of a Binary Number
This is more for my curiosity than anything else as I understand how to find the two's complement of a binary number via the standard approach which is to convert all 0s to 1s and 1s to 0s and then add $1\_2$, but this "quick method" truly puzzles me. I see that the author of the book I am going through suggests that this method be skipped but I am wondering whether anyone understands what is going on here because I am truly lost.

This is all the description that is given. I don't understand why the first six bits are left alone while the last eight bits are changed. I would be much obliged if someone could provide some background to this methodology.

# Answer
> 0 votes
In that shortcut, let that right-most 1 bit left unchanged be $b$. Since $b$ is the right-most 1 bit all other bits on its right are 0s.

In the standard two's complement, when you first do the one's complement, $b$ will be the right-most zero and everything else that follows it on the right will be 1s. Then, if you add 1, that will result in a sequence of carry overs that will only stop when the carry bit is added to $b$ because $b$ is zero. This simply put $b$ and everything on its right back to their original value, but everything else on $b$'s left will be in their inverted value.

# Answer
> 0 votes
To add one to a binary number, you start from the right and zero out every one until you reach a zero. The you are done.

E.g. 0101110001111 + 1 = 0101110010000.

Notice that the last ones plus the first zero were changed and the next digits were unchanged.

Two's complement is bit flipping followed by incrementation. Hence the first zeroes plus the first one remain zero, and the next digits are changed.

---
Tags: binary
---


# Question
Title: How do I calculate offset from virtual address?
If the page size is 4Kbyte and the physical size of the main memory is 32Kbyte. Now if I consider virtual address of 37064..

The page number is then 37064/4096 = 9

And according to my diagram page 9 is mapped to frame 6

But how do I calculate the offset? According to exercise it should be 200. Thank you

# Answer
> 1 votes
The page size indicates how much bits represent the offset in the physical frame. In this case you have pages of 4KB that means you need 12 bits because 2^12 = 4096. The offset in the physical frame always starts at the least significant bits. So for your example with

```
37064 = 0b1001 0000 1100 1000,

```

0000 1100 1000 = 200 in decimal is the offset in the physical frame. Since you have only one level of page tables, the rest of the bits to the left represent the actual physical page. You should not see it as a division even though it works. So the offset in the page table is 1001 = 9.

# Answer
> 0 votes
The offset is 37064 % 4096 = 200.

% is modulo operator to calculate for remainder of a division.

So to get the offset, the formula is: offset = \[virtual address\] % \[page size\].

2 Years late but hopefully it helps someone looking for this in the future.

---
Tags: memory-management, virtual-memory
---


# Question
Title: What time complexity relative to input size is that?
If an algorithm takes two numbers $b$ and $n$ and its input size satisfies $O(\log\_2{n} + \log\_2{b})$ plus its time complexity satisfies $O(b \log\_{2}{n})$, what is the time complexity relative to the input size? Can we say it is exponential?

> An algorithm is said to be exponential time, if $T(n)$ is upper bounded by $2^{poly(n)}$, where $poly(n)$ is some polynomial in $n$. More formally, an algorithm is exponential time if $T(n)$ is bounded by $O(2^{n^{k}})$ for some constant k.

Source

In that case, we can get the same input size with different combinations of $n$ and $b$, and by keeping $n$ fixed and changing $b$ the time grows much faster, so it's not directly possible to express time as a function of input size as it depends on what particular $b$ and $n$ constitute the input size.

By substituting $\log\_{2}{b}$ with $b$ and $\log\_2{n}$ with $n$, the input size is bounded by $O(b + n)$ and time by $O(2^b + n^2)$.

# Answer
First of all, if all you're given is an *upper bound* on the input length, then you can't conclude anything. But I suspect that you meant that the input length is $\Theta(\log\_2 n + \log\_2 b)$. If there are no other constraints, then the best bound on the time complexity as a function of the input length $N$ is $O(2^N)$, since this is what happens when $n$ is constant.
> 0 votes

# Answer
Such an algorithm would run in pseudo-polynomial time.
> 0 votes

# Answer
With input size $O(n+m)$, the time complexity is $O(n2^b)$, which is linear in $n$ and exponential in $b$.
> 0 votes

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


# Question
Title: Solution for the path-finding problem which visits multiple sequences of nodes
### Summary

Recently I have had a path-finding puzzle that has some complex constraints (currently, I don't have any solution for this one)

* A 2D matrix represented the graph. The length of a path is the number of traversed cells.
* One or more **number sequences** are to be found inside the matrix. Each sequence is scored with a value.
* Maximum length of the path in the graph. The number of picked cells must not exceed this value.
* At any given moment, you can only choose cells in a specific column or row.
* On each turn, you need to switch between column and row and stay on the same line as the last cell you picked. You have to move at right angles. (**The direction is like the Snake game**).
* Always start with picking the first cell from the top row, then go vertically down to pick the second cell, and then continue switching between column and row as usual.
* You can't choose the same cell twice. The resulting path must not contain duplicated cells.

For example:

The task is to find the **shortest path, if possible** in the graph that **contains one or more sequences** with the **highest total score** and **the path's length is not exceed the provided maximum length**.

The picture below demonstrates the solved puzzle with the resulting path marked in red:

Here, we have a path **3A-10-9B**. This path contains the given sequence **3A-10-9B** so, which earns 10pts. More complex graphs typically have longer paths containing various sequences at once.

### More complex examples

#### Multiple Sequences

You can complete sequences in any order. The order in which the sequences are listed doesn't matter.

#### Wasted Moves

Sometimes we are forced to waste moves and choose different cells that don't belong to any sequence. Here are the rules:

* Able to waste 1 or 2 moves before the first sequence.
* Able to waste 1 or 2 moves between any neighboring sequences.
* However, you cannot break sequences and waste moves in the middle of them.

Here, we must waste one move before the sequence **3A-9B** and two moves between sequences **3A-9B** and **72-D4**. Also, notice how red lines between **3A** and **9B** as well as between **72** and **D4** "cross" previously selected cells **D4** and **9B**, respectively. You can pick different cells from the same row or column multiple times.

#### Optimal Sequences

Sometimes, it is not possible to have a path that contains all of the provided sequences. In this case, choose the way which achieved the most significant score.

In the above example, we can complete either **9B-3A-72-D4** or **72-D4-3A** but not both due to the maximum path length of 5 cells. We have chosen the sequence **9B-3A-72-D4** since it grants more score points than **72-D4-3A**.

#### Unsolvable solution

The first sequence **3A-D4** can't be completed since the code matrix doesn't contain code **D4** at all. The second sequence, **72-10**, can't be completed for another reason: codes **72** and **10** aren't located in the same row or column anywhere in the matrix and, therefore, can't form a sequence.

### Conclusion

I am looking for any advice for this puzzle since I have no idea what keywords to look for. A pseudo-code or hints would be helpful for me, and I appreciate that. What has come to my mind is just Dijkstra:

* For each sequence, since the order doesn't matter, I have to find all get all possible paths with every permutation, then find the highest score path that contains other input sequences
* After that, choose the best of the best.

In this case, I doubt the performance will be the issue.

# Answer
I believe the problem is, in the worst case, NP-hard. In particular, finding a Hamiltonian path in an induced subgraph of a grid graph is NP-hard. (See https://cs.stackexchange.com/a/68600/755.) Moreover, it seems like it is possible to construct an instance of such a problem in your setting, by putting the same value in all cells in the vertex set of the induced subgraph, and choosing a sequence and a minimum length that requires visiting everyone of those cells exactly once.

The problem is clearly in NP. Therefore, one approach is to solve it with a SAT solver. You should be able to formulate this as an instance of SAT, with boolean variables that capture the path taken through the graph and which cells are picked and which sequences have been scored. Then, you could use an off-the-shelf SAT solver to search for a solution. It is possible this might work for your situation. It's hard to know for sure without trying it.
> 1 votes

---
Tags: algorithms, shortest-path
---


# Question
Title: Multi-Armed Bandit - Reward Probabilities
I am new to reinforcement learning, and recently came across the following issue. When implementing a multi-armed bandit algorithm, we assume we have k machines with reward probabilities \[p\_1,..., p\_k\] which we try to approximate. While these probabilities are clearly unknown to the player himself, they must still be encoded in the algorithm in the sense that we have to specify:

""" return 1 with the arm's predefined probability """

```
    if np.random.random() < self.p:
       return 1
    else:
       return 0

```

My question is how we can set those predefined probabilities (e.g. for ad optimisation).

# Answer
> 1 votes
As pointed out by @D.W. you are not required to hardcode these probabilities in the algorithm to obtain an optimal strategy, but you do need to know them if you want to model the scenario.

A big step towards optimal solutions to the Multi-Armed Bandit problem (where a player doesn't know the underlying probability distribution of rewards) was given in 1996 by Burnetas and Katehakis in their paper "Optimal adaptive policies for sequential allocation problems". In particular they include the case in which the distributions of outcomes depend on unknown parameters (see section Optimal solutions in the Wikipedia page of Multi-armed bandit for example).

Thompson's sampling allows to do this in a simple way following the steps described here. Initially you assume a prior $P(\theta)$ and then update it into your posterior $P(\theta|\\{a,x,r\\})$, as you get more information after every action. An action $a^\*$ is then chosen, each with probability

$$ \mathbb{P}(a^\*) = \int\_{\Theta} \mathbb{1}\_{\[\mathbb{E}(r|a^\*,x,\theta)\ =\ \max\_{a}\mathbb{E}(r|a,x,\theta )\]}P(\theta|\\{a,x,r\\})d\theta. $$

Of course, if $a^\*$ maximises the reward under the *assumed* parameters then it's chosen with probability 1. Eventually we hope for $P(\theta|\\{a,x,r\\})$ to converge to the underlying true (unknown) distribution of parameters. Notice that to choose an action in practice, sampling techniques are usually implemented.

Going back to the initial comment on modelling the scenario, if you want to code a game to test Thompson's algorithm, then the \`\`casino'' must give a reward on every round after an action is chosen and this reward is indeed the true one, so you must input the hidden distribution. This will still not be seen by the player applying the algorithm. In the case of add placement, the underlying true distribution is inherent to the user while the company placing the add wishes to obtain the highest reward.

# Answer
> 0 votes
Thompson sampling doesn't require knowing the true success probability of each arm. I'm not clear on why you suggest it does. Quite to the contrary, it computes an integral over all possibilities for what that probability could be (or, it estimates this integral by sampling from the distribution over such probabilities).

Responding to the revised question: The question contains an incorrect claim. Thompson sampling does not require hardcoding those probabilities in the algorithm. I am not sure where you obtained that code from or what the variables are intended to represent, so it is hard to comment on that specific code.

---
Tags: reinforcement-learning
---


# Question
Title: If P=NP then all languages in P are NP-complete?
I know that if $P=NP$ then all of the languages in $NP$ are $NP-Complete$, but what about those in $P$?

I assume yes, because $P \subseteq NP$, but I just want to check.

Thanks!

# Answer
Both facts are wrong. The empty problem $\emptyset$ (the decision problem whose answer is always *false*) is in both $\mathsf{P}$ and $\mathsf{NP}$, and is not $\mathsf{NP}$-complete.

See here for some details.
> 1 votes

---
Tags: complexity-theory, np-complete, p-vs-np
---


title: Infinite Graph with Finite Degree

text:
# Question
Title: Infinite Graph with Finite Degree
Let $G$ be an undirected graph with an infinite number of vertices (and edges), and assume it is connected in the sense every $u,v$ have at least one path connecting them. Assume each vertex has a finite degree. My question is: Is it possible for a pair of vertices to exist, such that they will have an infinite number of paths?

Ofcourse, if we allow a path to contain a cycle, the answer is positive. However, I am interested in what happens when we forbid paths that contain cycles.

In other words: Is it possible for a pair of vertices to exist, such that they will have an infinite amount of **simple** paths?

# Answer
> 3 votes
The lattice $\mathbb{Z}^2$ gives an example. Take $u=(0,0)$ and $v=(0,1)$. For every $n$ we can construct the path $u = (0,0) \to (n, 0) \to (n, 1) \to (0, 1)=v$ of length $2n+1$. Each of these paths is distinct and contains no cycle.

The same works for any selection of vertices $u$ and $v$.

---
Tags: graphs, connected-components
---


# Question
Title: Compute the maximum length of an increasing digital subsequence given an array of digits
Consider the following exercise from chapter *Dynamic Programming* in the book *Algorithms* by Jeff Erickson.

> Let $D\[1 .. n\]$ be an array of digits, each an integer between $0$ and $9$. A **digital subsequence** of $D$ is a sequence of positive integers composed in the usual way from disjoint substrings of $D$. For example, $3, 4, 5, 6, 8, 9, 32, 38, 46, 64, 83, 279$ is a digital subsequence of the first several digits of $\pi$:$$ \underline 3 , 1, \underline 4 , 1, \underline 5 , 9, 2, \underline 6 , 5, 3, 5, \underline 8 , \underline 9 , 7, 9, \underline{3, 2} , 3, 8, \underline{4, 6} , 2, \underline{6, 4} , 3, 3, \underline{8, 3 }, \underline {2, 7, 9}$$ The length of a digital subsequence is the number of integers it contains, not the number of digits; the preceding example has length $12$. As usual, a digital subsequence is **increasing** if each number is larger than its predecessor.
>
> Describe and analyze an efficient algorithm to compute the longest increasing digital subsequence of $D$. \[*Hint: Be careful about your computational assumptions. How long does it take to compare two k-digit numbers?*\]
>
> For full credit, your algorithm should run in $O(n^4)$ time; faster algorithms are worth extra credit. The fastest algorithm I know for this problem runs in $O(n^{3/2}log n)$ time; achieving this bound requires several tricks, both in the design of the algorithm and in its analysis, but nothing outside the scope of this class.

My main question is how I can define my subproblems? I guess we must have an 3D array like: $$DP\[i\]\[j\]\[k\]$$ but I can't define $DP\[i\]\[j\]\[k\]$ very well.

# Answer
> 2 votes
Let $\overline{D\[i..j\]}$ denote the number formed by the digits $D\[i..j\]$. For example, if $D=(1,5,7,4,8,3)$, then $\overline{D\[2..2\]}=5$ and $\overline{D\[2..4\]}=574$.

#### The subprolems

Let $DP\[i\]\[j\]$ with $1\le i\le j\le n$ be the maximum length of a digital subsequence of $D$ the last number of which is $\overline{D\[i..j\]}$.

The recurrence relation is

$$DP\[i\]\[j\]=1+\max\_{\ell\<i,\\, \overline{D\[k..l\]}\<\overline{D\[i..j\]}} DP\[k\]\[\ell\]$$ where the default value of $\max$ is $0$, i.e., if there is no arguments, $\max$ is $0$.

The answer is the maximum of all $DP\[i\]\[j\]$'s.

#### Analysis on time-complexity

Since both $i$ and $j$ range from $1$ to at most $n$, there are at most $n^2$ $DP\[i\]\[j\]$'s (subproblems).

Let us check how much computation is needed to compute one entry $DP\[i\]\[j\]$.

We need to list all $k,l$ such that $\ell\<i$ and $\overline{D\[k..l\]}\<\overline{D\[i..j\]}$. Compute the actual number of digits in $\overline{D\[i..j\]}$, i.e., without the leading zeros. let it be $p$.

* For each $gap=0,1,2,\cdots, p-1$, we can let $(k,l)=(s, s+gap)$, where $s=0, 1, \cdots, i-gap-1$. $\overline{D\[k..l\]}$ is a number of less than $p$ digit, which must be smaller than $\overline{D\[i..j\]}$.
There are at most $n$ choices for the gap with at most $n$ possible choices for $s$ for each gap. It takes $O(n^2)$ to list them.
* For each $s=0, 1, \cdots, i-p-1$, we can check whether $\overline{D\[s..s+p\]}\<\overline{D\[i,j\]}$ in $O(n)$ time by comparing their digits one by one starting from the most significant digit.
There are at most $n$ choices for $s$. So we can list all $(s,s+p)$'s such that $\overline{D\[s..s+gap\]}\<\overline{D\[i,j\]}$ in $O(n^2)$ time.

Once we know all possible $(k,l)$'s, it takes $O(n^2)$ time to compute $DP\[i\]\[j\]$ using the recurrence relation.

Hence it takes $O(n^2)\cdot O(n^2)=O(n^4)$ time to compute all subproblems. It takes $O(n^2)$ to compute the final answer. Hence, it takes $O(n^4)$ time to run the algorithm.

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