# Question
Title: Computing the set of points nearest to a point in a polygon boundary
Let $P$ be a polygon. For each point $x$ on the boundary of $P$, denote by $N\_P(x)$ the set of points in $P$, that are nearer to $x$ than to any other point on the boundary of $P$.

Given a subset $X$ of the boundary (e.g. an interval contained in one of the sides of $P$), what is an algorithm for computing $N\_P(X)$?

Here is an example: $X$ is the blue interval at the bottom, and $N\_P(X)$ is the blue polygon.

# Answer
> 2 votes
The following ideas might help.

The set $X$ can be partitioned into a set of disjoint intervals such that each interval is continuous and lies on one of the sides of polygon. For each interval $I$, we can find $N\_{P}(I)$ and union of all $N\_{P}(I)'s$ would give the required set $N\_{P}(X)$. Now, let us find $N\_{P}(I)$ for an interval $I$:

1. For ease of simplification, orient the polygon such that interval $I$ lies on the $x$-axis; similar to the one shown in your figure.
2. Let $a$ and $b$ be the two endpoints of $I$ such that $a\leq b$. It is easy to see that the polygon region that lies within the region $y \in (-\infty,\infty)$ and $x \in (-\infty,a) \cup (b,\infty)$ does not belongs to $N\_{P}(I)$.
3. This leaves us with the region $R$ defined as $y \in (-\infty,\infty)$ and $x \in \[a,b\]$. Find all the segments of the polygon that lies in this region. You can do this by taking each side of the polygon and keeping its that part that lies in $R$. Suppose $S$ be this set of segments that we obtain.
4. For every $q \in \[a,b\]$, we will find the region $N\_{P}(q)$. Let $S\_{q} \subseteq S$ be the set of segments that intersects with the line $x = q$. The segment in $S\_{q}$ that is closest to the $x$-axis will be the main competitor. Let this segment be $S\_{q}^{c}$ and suppose it has height $h$. If the point $(q,h/2)$ lies in the polygon, then all the points: $(q,y)$, where $y\leq|h|/2$ lies in $N\_{P}(q)$; otherwise not. If we can follows this process for every $q \in \[a,b\]$, then the union of $N\_{P}(q)$'s will give $N\_{P}(I)$.

Now, how can we perform step $4$ efficiently? In other words, we need obtain the segment $S\_{q}^{c}$ for every $q \in \[a,b\]$? It is simple. Run the sweep line algorithm on $S$ with event points being the start and end points of the segments. Keep track of the line segments that are closest to the $x$-axis. In that way, you will find $N\_{P}(I)$.

---
Tags: computational-geometry
---


# Question
Title: Show that a language is decidable iff some enumerator enumerates the language in decreasing order
> Show that a language is decidable iff some enumerator enumerates the language in decreasing order.

I know a language is decidable iff some enumerator enumerates the language in the standard string order (increasing order), but I am not sure if this makes sense in decreasing order. I carefully think if some enumerator enumerates the language in decreasing order, then a language is not decidable. For infinite languages, we cannot assure which comes first in the enumerator. However, are all finite languages decidable? If so, I think the given statement is true for finite languages.

# Answer
> 3 votes
If there is an enumerator in decreasing order then the language is finite and hence decidable.

But that means any infinite language wont have such an enumerator, and in particular there is some infinite language that is decidable (such as $\Sigma^\*$) and it wont have such an enumerator.

So, this theorem is **incorrect**

# Answer
> 3 votes
An enumerator for a set will start by generating some item, then another item, and so on, in a way that every element of the set will eventually be listed. If the set is empty, then it won't even generate the first item. If the set is non-empty but finite, then it will eventually generate the last item and stop.

What does it mean to enumerate a set in decreasing order? You would start with an existing enumerator that defines some order. And whenever that enumerator generates A followed by B, the enumerator "in decreasing order" will generate B followed by A.

If the set is empty, then "decreasing order" is just an empty enumerator. If the set is non-empty but finite, then "decreasing order" means we enumerate the last element in the original enumerator first, then the element that was enumerated before the last element, until the first element of the original enumerator is generated, and then the enumerator "in decreasing order" stops.

But what if the set is infinite? The new enumerator must generate some set element A first. The original enumerator would generate A followed by some element B. In decreasing order, B would have to precede A, but it can't because there cannot be anything before the first item. For example, you can't generate the primes in descending order.

So if a generator can enumerate a language in reverse order, this means that the language must have been finite in the first place. And every finite language is decidable. Infinite languages cannot be enumerated in reverse order. But that doesn't say anything about being decidable or not.

---
Tags: undecidability, enumeration
---


title: What is "invariants of the code"?

text:
# Question
Title: What is "invariants of the code"?
The Wikipedia page for strong and weak typing says:

> "Strong typing" generally refers to use of programming language types in order to both capture invariants of the code

What is "invariants of the code"? There is no link for that

# Answer
An invariant is a statement that holds during the execution of a piece a code. For instance, you might often encounter loop invariants (statements that hold on every iteration of some loop) or class invariants (statements preserved by every method call).

In particular, what I believe the article is referring to here is static type checking, i.e., statements which enforce conditions on the types of variables. Indeed, saying it "excludes certain classes of programming errors" would include errors stemming from (the lack of) type safety. For example, if you have weak typing, a function expecting an argument `n` to be an integer will only fail at runtime if you pass it a string. With strong typing, you can catch such errors before running the program.
> 2 votes

---
Tags: programming-languages, typing
---


# Question
Title: Can the worst-case analysis of $f(n)$ be $\Omega(g(n))$ but not $O(g(n))$?
I am struggling to wrap my head around using $\Omega$-notation to describe worst-case running time of an algorithm, or $O$-notation to describe the best-case running time. Specifically, I struggle to understand how a given function $f(n)$ can have a worst-case lower-bound of $\Omega(g(n))$ *without also having $O(g(n))$ as the worst-case upper bound*--that is to say, shouldn't all best-case and worst-case complexities be $\Theta(g(n))$?

The core of the issue for me is that once you are describing a case (eg worst-case), you are fixing some characteristic about the nature of the input: *this is the kind of input that makes it take as long as possible*. How can there be multiple analyses of this one type of input?

# Answer
Let me split the answer to three parts, so it will hopefully clear all misundestandings you have on the concepts.

---

## What are big-O and big-$\Omega$?

Big-O and big-$\Omega$ are two *mqthematical* properties of functions over natural numvers. Their formal definition state that:

* $f=O(g)\iff \exists c\>0:\forall n: f(n)\le c\cdot g(n)$
* $f=\Omega(g) \iff \exists c\>0:\forall n:f(n)\ge c\cdot g(n)$

See the difference? Big-O talks about bounding a function from **above** and big-$\Omega$ bounds it from **below**.

When we say $f=\Theta(g)$ we actually mean that $f=O(g)$ and $f=\Omega(g)$: $f$ is bounded from above it and below it, by $g$, hence it is "equivalent" to $g$.

---

## Measuring running time

When we measure the *running time* of an algorithm, we usually mean "measure the number of steps it takes to compute the **worst case scenario** when the input is of size $n$". Practically, this means that we want to know what value $T(n)$ is, where $T(n)$ is define as the worst case running time.

Now you can think of $T$ as any other function. Giving a big-O bound to $T$ just means expressing an upper bound on $T(n)$ in nice terms. And giving a big-$\Omega$ bound is just nicely writing a lower bound on $T(n)$.

So essentially, if your running time is both $O(n)$ and $\Omega(n)$, then the time your algorithm takes in the worst case is "equivalent" to a linear function.

---

## Intuitively, what does it say?

Im sure that a big-O bound to the running time of your algorithm is intuitive. However, what does $\Omega(n)$ represent?

Essentially what it says, is that your big-O bound is strict. It means that you have proved your analysis cannot give a better bound on the running time. This property is less useful usually, but becomes more useful the more you are unsure if the big-O bound you gave is strict enough.

For example, try to consider the running time of `heapify` that converts a list of numbers to a heap. Its easy to show an $O(n\log(n))$ bound, and with a little more effort you can even show an $O(n)$ bound. So how can you be sure that you cant get to, say a $O(\log(n))$ bound with even more effort? The answer is simple: we can show an $\Omega(n)$ bound on the running time of the algorithm.
> 2 votes

# Answer
Consider $f(n) = n^2$. Then we have $f(n) \in \Omega(n)$ but not $f(n) \in O(n)$.

However, as you stated it, it is better to give a tight bound for best and worst cases, with the $\Theta$-notation, because saying "the worst case is exactly $n^2$ operations" is a better information than "the worst case is at least $n$ operations".
> 1 votes

# Answer
Take a look at my other answer for a long explanation on the topic.

---

However, the short answer would be: yes, every function $f$ is $\Theta(f)$, but we want to know what that value actually is. Is that $\Theta(n)$? Or maybe its $\Theta(n^2)$? The idea is that we want some simple function that will represent the (more complex) function of the running time.
> 0 votes

---
Tags: time-complexity, algorithm-analysis, asymptotics, big-o-notation
---


title: If $NP \neq coNP$ then $BPP \neq NP$

text:
# Question
Title: If $NP \neq coNP$ then $BPP \neq NP$
I am new in complexity theory and I am trying as part of an assignment to prove or disprove this.

I am thinking this is a true statement but I am not sure how to prove or disprove it or what the implications of $NP \neq coNP$ are to randomized complexity classes.

# Answer
Take a look here for an explanation on why $BPP=co-BPP$.

I'm sure you can solve from here :)
> 3 votes

---
Tags: complexity-theory
---


title: Mapping reductions for dummies

text:
# Question
Title: Mapping reductions for dummies
I am having trouble understanding a mapping reduction and I would appreciate your help. Define

$\quad \begin{align} A\_{TM} &= \\{ \langle M, w \rangle \mid M \text{ Turing machine}, w \in \mathcal{L}(M)\\} \\ S\_{TM} &= \\{ \langle M,w \rangle \mid M \text{ Turing machine}, w \in \mathcal{L}(M) \implies w^R \in \mathcal{L}(M)\\} \\ \end{align}$

and consider the reduction of $A\_{TM}$ to $S\_{TM}$ as follows.

Given $\langle M, w \rangle$ the following Turing machine $M'$ is defined:

```
M' on input x:
  if x = 01 then accept
  else run M on w and accept x if M accepts w

```

I don't understand the reduction entirely, this reduction is supposed to solve $S\_{TM}$ using $A\_{TM}$. Why do I need to check if `x = 01`? There is no need to check anything about the reverse of $w$? How is that covered by the reduction?

# Answer
> 1 votes
The idea of the reduction you give in your question is the following:

I) If $\langle M,w\rangle \in A\_{tm}$, then $L(M')=\Sigma^\*$.
II) If $\langle M,w\rangle \notin A\_{tm}$, then $L(M')=\\{10\\}$.

thus, for any $w$, $\langle M,w\rangle \in A\_{tm}$ **iff** $\langle M',w\rangle \in S\_{tm}$.
In case (I), for any $w\in L(M')$ also $w^R\in L(M')$ hence $\langle M',w \rangle S\_{TM}$ for any $w$. For case (II), there is no $w\in L(M')$ such that $w^R\in L(M')$ as well, thus for any $w$, $\langle M',w \rangle S\_{TM}$.

Now for your question about accepting "10" no matter what: Assume we avoid this step. Then, in case (II), $L(M')=\emptyset$, hence $\langle M',w\rangle \in S\_{tm}$ for **any** $w$, since the condition on $w,w^R$ vacuously holds. Now the mapping cannot map inputs $\langle M,w\rangle \notin A\_{tm}$ to inputs outside $S\_{TM}$ (since none exists).

The value "10" is arbitrary. Any other non-palindromic string will do.

# Answer
> 0 votes
Here's a possible reduction for $A\_{tm} \le S\_{tm}$.

Map input $\langle M,w\rangle$ to $\langle M', 0w1\rangle$ such that

> $M'$ on input $x$:
> 0. if $x$ can be written as $1x'0$ for some $x'$, accept. Otherwise,
> 1. if $x$ can be written as $0x'1$ for some $x'$, run $M$ on $x'$ and output the same.
> 2. Otherwise, accept (or reject, it doesn't matter).

*proof.*
If $\langle M,w\rangle \in A\_{TM}$ then $M$ accepts $w$. Observe that $M'$ accepts both $0w1$ (rule 1) and $1w^r0$ (rule 0), thus $\langle M', 0w1\rangle \in S\_{TM}$.
On the other hand, if $\langle M,w\rangle \notin A\_{TM}$, then also $M'$ doesn't accept $0w1$, and $\langle M', 0w1\rangle \notin S\_{TM}$.

Observe that both $A\_{TM}$ and $S\_{TM}$ are $RE$ languages (which are not in $R$). You can also prove a reduction $S\_{TM} \le A\_{TM}$, by mapping $\langle M,w\rangle$ to $\langle M',w\rangle$, with $M'$ that runs $M$ on $w$ and then on $w'$. The proof is straightforward.

# Answer
> 0 votes
Ran has a good short answer, so I'll do a semi-formal proof for this based on the provided $M'$:
The goal of a mapping reduction is to show that for some function F \begin{equation} \forall x \in \Sigma^\*, x \in A\_{TM} \Longleftrightarrow F(x) \in S\_{TM} \end{equation} In other words, every x (encodings of M with a string w) in $A\_{TM}$ has to be in $S\_{TM}$ and every x that is not in $A\_{TM}$ must not be in $S\_{TM}$
Case 1: $ \langle M,w\rangle \in A\_{TM} \implies \langle M'\rangle \in S\_{TM} $
$\quad$ $M'$ will accept x if it is 01 of course. For anything that is not 01, it will
$\quad$ proceed to run $M$ on it, and since we're assuming that $\langle M,w\rangle \in A\_{TM}$,
$\quad$ every other x will also be accepted by $M'$. Therefore, $L(M') = \Sigma^\*$
$\quad$ which implies that every word $w$ has a $w^R$ in it, meaning that $ \langle M'\rangle \in S\_{TM}$.

Case 2: $\langle M,w\rangle \notin A\_{TM} \implies \langle M'\rangle \notin S\_{TM}$
$\quad$ Case 2.1: $\langle M,w\rangle$ fails the input typecheck (assuming we have one) so we output a $const\_{out}$ which is
$\quad \quad$ guaranteed to not be in $S\_{TM}$.
$ \quad$ Case 2.2: $M$ halts and rejects on $w$
$\quad \quad$ We always accept 01 since that is given. But now when we run $M$ on any input x that is not 01, we will
$\quad \quad$ reject that x since $w$ is not in $M$. Therefore, $L(M') = \\{01\\}$
$\quad \quad$ which is not in $S\_{TM}$ since the reverse word, 10, is not present in $L(M')$.
$\quad$ Case 2.3: $M$ loops on $w$
$\quad \quad$ Same idea as when it halts and rejects, since $w \notin M$ we only have the word 01 ever begin accepted
$\quad \quad$ and so $\langle M'\rangle$ will not be in $S\_{TM}$
(We can also conclude this now!). Since we've shown that we can decide $S\_{TM}$, we can also decide $A\_{TM}$ since we can map any input of $A\_{TM}$ to $S\_{TM}$. But this is a contradiction since $A\_{TM}$ is undecidable. Therefore, $S\_{TM}$ is undecidable as well.

---
Tags: computability, turing-machines, reductions
---


# Question
Title: If $S\in\left(NP\bigcup coNP\right)$ then $\overline{S}\in NP\bigcap coNP$?
Is it true that if $S\in\left(NP\bigcup coNP\right)$ then $\overline{S}\in NP\bigcap coNP$?

I couldn't find any answer to that question.

My attempt at proving it:

If $S\in\left(NP\bigcup coNP\right)$, then, by set theory, $S=A\bigcup B$ for some $A\in NP\wedge B\in coNP$.

Therefore the complement of $S$ is $\overline{S}=\overline{A\bigcup B}=\overline{A}\bigcap\overline{B}\in NP\bigcap coNP$

# Answer
Your attempt **isn't** correct.

There is a distinction between $S\in (NP\cup co-NP)$, and $S\in (NP\lor co-NP):=\\{A\cup B|A\in NP, B\in co-NP\\}$

You assumed both are the same, however the first talks about $S$ being in either $NP$ or $co-NP$, while the second talks about $S$ being a union of something from $NP$ and something else from $co-NP$.

---

About the question in title, we actually don't know. If $NP\neq co-NP$, then there is some $L\in NP\setminus co-NP$ (or the other way around), which means that $L\in (NP\cup co-NP)$ but $\overline{L}\notin (NP\cap co-NP)$ (since $L\notin NP$ then $\overline{L}\notin co-NP$)

But if $NP=co-NP$, then clearly what you stated would be trivially true.

So essentially, what you tried to prove is equivalent to the open problem "Is $NP=co-NP$ or not?".
> 0 votes

---
Tags: complexity-theory, np, co-np
---


# Question
Title: Map two arrays given a map of possible mappings
Given two integer arrays `a` and `b` and a map `m` which for each element `e` of the array `a` returns an array `p` of possible mappings, map every `e` of `a` to an element `k` of `b` so that `m[e]` contains `k`, no element of `a` or `b` is mapped twice and the number of non-mapped integers in `a` is minimal. Note that both `a` and `b` may have repetitive elements.

For example:

> a = \[1,2\], b = \[3,4\], m = \[1 =\> \[3,4\], 2 =\> \[3\]\]

We see that 1 can be mapped both to 3 and to 4. However since we want the number of mapped elements to be maximal we must map 1 to 4 because 2 can only be mapped to 3. So the result here would be:

> 1 =\> 4, 2 =\> 3

So far I've only come up with the bruteforce solution which is to just try every possible mapping for every value in `a`. However this solution has a time complexity of `O(n) = !n * k` where `n` is the number of elements in `a` and `k` is the number of possible mappings.

How could you optimize this further to get the most efficient algorithm for solving the problem?

# Answer
> 1 votes
This problem can be transformed to a maximum flow problem.

**Transformation to a flow network**
Consider each element in either array $A$ or $B$ as a distinct node.
If element $e$ in $A$ can be mapped to element $k$ in $B$, add an edge from $e$ to $k$.
Add source node $s$. Add an edge from $s$ to each element in $A$.
Add sink node $t$. Add an edge from each element in $B$ to $t$.
Let the capacity of every edge be 1.
We have obtained $G$, a flow network.

We can verify that the maximum number of mapped element in $A$ is exactly the maximal flow of $G$.

---

There are many polynomial-time algorithms to compute the maximum flow of a flow-network. Edmonds–Karp algorithm and Dinic's algorithm are taught in many introductory course in graph algorithms. Implementations in various programming languages can be found readily online.

---

**Exercise 1.** Verify the maximum number of mapped element in $A$ is the maximal flow of $G$.

**Exercise 2.** The flow network that we constructed above, using one node for each element, is a unit-capacity flow network. To increase efficiency, describe how we can construct a new flow network using one node for each group of repeated elements instead, so that the maximum number of mapped element in $A$ is the maximal flow of the new flow network still.

---
Tags: algorithms, time-complexity, arrays
---


# Question
Title: List the lengths of all the prefix-suffixes in $O(n^{1+\epsilon})$ time
A proper prefix of a string $s$ that is also equal to a suffix of $s$ is called a PS (prefix-suffix).

Given a string $s$ of length $n$ is there an algorithm listing the lengths of all the PSs in $O(n^{1+\epsilon})$ time?

KMP can find the *longest* PS in linear time. Then we can note that the second longest PS is the longest PS of the longest PS so we can apply KMP iteratively but that is $O(n^2)$ in the worst case (e.g. if $s=aaaa\dots a$).

# Answer
> 1 votes
Simply note that KMP is incremental: it finds the longest PS (also known as *border*) for every prefix of the string. If you don't throw away that information, you don't need to re-run KMP for every prefix.

---
Tags: algorithms, search-algorithms, strings
---


# Question
Title: Prove SubsetSum is polyequivalent to SubsetSum with surplus
I'm solving problem 13.17 of What can be computed?, which is asking to prove $\text{SubsetSum} \equiv\_{P} \text{SubsetSumWithFives}$. Here is the definition of SubsetSumWithFives.

> SUBSETSUMWITHFIVES: it is identical to the decision variant of SUBSETSUM, except that we may use up to 10 extra packages with weight 5 when constructing the desired subset.

I thought I could show $\text{SubsetSumWithFives} \le\_{P} \text{SubsetSum}$ by adding 10 extra 5 weights. However, I have no idea to show $\text{SubsetSum}\le\_{P} \text{SubsetSumWithFives}$

Is there any suggestion to solve this problem?

# Answer
> 1 votes
You can transform the Subset Sum instance by multiplying all the weights of the "packages" and the target weight by 51.

Notice how, in the modified instance, adding any additional weight between 0 and 50 cannot change whether the target weight can be attained. If up to 10 packages with weight 5 were available, then you could only add weights up to 50. Therefore this modified instance can be immediately thought as an instance of Subset Sum with Fives.

---
Tags: subset-sum, polynomial-time-reductions
---


# Question
Title: NP-completeness of variant SAT: SAT-5Clauses
I'm solving Problem 14.4 of What can be computed?.

> 14.4 Define the decision problem SAT-5CLAUSES as follows. The input is a Boolean formula B in CNF. The solution is “yes” if it is possible to simultaneously satisfy at least 5 of B’s clauses. Is SAT-5CLAUSES NP-complete? Give a rigorous proof of your answer.

Is there any suggestion to solve this problem?

# Answer
> 2 votes
It is unknown whether the problem is $NP$-complete. In particular, you problem is non-trivial and it is in $P$. Therefore it is $NP$-complete if and only if $P=NP$.

To see that your problem is in $P$ you can consider the following "brute-force" algorithm. Let $n$ be the number of variables and $n$ be the number of clauses.

If it is possible to simultaneously satisfy $5$ clauses, then there are $5$ literals that are true and belong to different clauses.

You can then explicitly consider all subsets of $\min\\{n, 5\\}$ variables and, for each subset $S$, try all possible (constantly many) truth assignments to the variables in $S$.

For each of these $O(n^5)$ (partial) truth assignments, check whether at least $5$ clauses are satisfied. This can be done in constant time after a linear-time preprocessing of the input instance.

The overall time required is then $O(mn + n^5)$ where $O(mn)$ is an upper bound on the size of the instance.

---
Tags: np-complete, satisfiability
---


# Question
Title: What are some problems that have higher degree of unsolvalbilty than $\Pi^0_2$-complete problems?
I'm looking for some problems that have higher degree of unsolvalbilty in term of arithmetical hierarchy that requires more than 2 quantifiers like $\Pi^0\_3$ ,$\Pi^0\_4$ etc.

# Answer
If memory serves, Soare's old book *Recursively enumerable sets and degrees* gives a few examples. Here are a couple off the top of my head (below I fix some standard enumeration $(W\_e)\_{e\in\mathbb{N}}$ of the r.e. sets):

* The set of $e$ such that $W\_e$ is recursive is $\Sigma^0\_3$-complete.
* The set of $e$ such that $W\_e$ is co-infinite (= has infinite complement) is $\Pi^0\_3$-complete.
* Let $G\_e$ be the directed graph on $\mathbb{N}$ with an edge from $a$ to $b$ iff $\langle a,b\rangle\in W\_e$ (where "$\langle\cdot,\cdot\rangle$" is your favorite pairing function). Then we can ask about index sets corresponding to graph properties, e.g. the set of $e$ such that $G\_e$ is connected and so forth. This gives rise to an **extremely** complicated index set: the set of $e$ such that $G\_e$ has no infinite path is $\Pi^1\_1$-complete. **Note the superscript** \- "$\Pi^1\_1$" takes us well outside the entire arithmetic hierarchy!
> 2 votes

---
Tags: computability, undecidability
---


title: Prove Edited Algorithm of Bellman–Ford?

text:
# Question
Title: Prove Edited Algorithm of Bellman–Ford?
**Please Note:** I forgot a small detail which caused the algorithm to be incorrect, please read the new version and thanks for pointing that.

---

I am stuck on this question for a week and hope to get some help:

Algorithm:

> Given 2 sided Graph ie bipartite graph *G(L,R,E)*, a weight function and a root vertex *s*:
>
> 1. Define *E1* as the group of edges connecting vertex from *L* to *R*
> (the rest are in *E2* Group).
> 2. For each vertex *v*, let
> *d(v) = ∞* except *d(s) = 0*
> 3. Do *(|L|+|R|)/2* (round floor) iterations of the following:
>
> Check **Every** edge in the graph, while finishing all edges \> in *E1* **and only then** moving on to *E2*: if *d(v)\>d(u)+w(u,v)* then let *d(v)=d(u)+w(u,v)*
>
> Prove that if there is no circular path with total negative weight in *G*, then the given algorithm returns for each vertex *v* the minimal weight of a path from *s* to *v*.

---

My try:

* For every vertex *v* we can conclude that there is a shortest path from *s* which is simple (no vertex appears twice, else we are getting a contradiction to the fact that there is no negative circular paths)
* The difference between number of edges from E1 and E2 is no more than 1
* For every simple and short path *P* there is no more than *(|L|+|R|)/2* (round floor) edges from *E1* (and the same for *E2*).

Claim: For every vertex *v* if there is a shortest path $P$ from *s* to *v* , which contains $k$ edges from $E1$ then at the end of *k*-th iteration *d(v)=|P|* ie the algorithm's calculation is correct.

Proof: By induction on *k*.

---

But as I progressed it seemed that the claim doesn't cover all cases (Thus it's wrong). For example, it worked when *v* is in *R* group but failed To help prove the case when *v* is in *L* group.

Thanks in advance for any help

# Answer
> 1 votes
Let $D(t,i)$ denote the length of the shortest among the path from $s$ to $t$ in $G$ that use at most $i$ edges.

We will focus on the generic $i$-th iteration of the algorithm and show that:

* (i) after all the edges in $E\_1$ have been considered, we must have $d(t) \le D(t, 2i)$ for each vertex $t \in R$.
* (ii) after all the edges in $E\_2$ have been considered, we must have $d(t) \le D(t, 2i)$ for each vertex $t \in L$.

As an edge case we consider the $0$-th iteration to be completed immediately before the start of the for loop.

The proof is by induction on $i$. The base case $i=0$ is trivially true since the only vertex at hop-distance $0$ from $s$ is $s \in L$ itself and the algorithm explicitly sets $d(s) = 0 = D(s, 0)$.

Consider now $i \> 0$. If $t=s$ we know, by induction hypothesis, that after iteration $0$ we have $d(s) \le D(s,0) \le D(s, 2i)$. Therefore, we restrict ourselves to the case in which $t \neq $ s and $D(t, 2i)$ is finite. Let $(v,t)$ be the last edge in any shortest path from $s$ to $t$ in $G$ that uses at most $2i$ edges.

If $t \in R$ then $v \in L$ and all paths to $v$ have even hop-length. Therefore, when $(v,t) \in E\_1$ is considered, we have $d(v) \le D(v, 2(i-1))$ by induction hypothesis and hence: $$ D(t, 2i) = D(v, 2i-1) + w(v,t) = D(v, 2(i-1)) + w(v,t) \ge d(v)+w(t). $$ This ensures that, after examining $(v,t)$ in iteration $i$ we must have $d(t) \le d(v)+w(t) \le D(t, 2i)$ and proves (i).

If $t \in L$ then $v \in R$ and all paths to $v$ have odd hop-length. When $(v,t) \in E\_2$ is considered we have $d(v) \le D(v, 2i)$ (this follows from (i), which we just proved). Therefore: $$ D(t, 2i) = D(v, 2i-1) + w(v,t) = D(v, 2i) + w(v,t) \ge d(v) + w(v,t). $$ Therefore, after $(v,t)$ is examined, we must have $d(t) \le D(t, 2i)$. This proves (ii) and concludes the proof by induction.

At this point we just need to notice that, the above claim, implies that at the end of the algorithm $d(t)$ is at most $D(t, 2 \lfloor (|L|+|R|)/2\rfloor) \le D(t, |L|+|R|-1)$, where $D(t, |L|+|R|-1)$ is exactly the distance from $s$ to $t$ in $G$. Moreover, all (finite) distances $d(t)$ computed by the algorithm correspond to the length of an actual path to $t$ in $G$, showing that $d(t)$ is also not smaller than the distance from $s$ to $t$ in $G$.

---

**This part of the answer refers to a previous version of the question in which the Algotithm did not prescribe any particular order in which to consider the edges**

If by 2-sided graph you mean bipartite graph, then the algorithm is wrong.

As a counterexample consider the graph $G=(L \cup R, E)$ where $L = \\{s, \ell\\}$, $R =\\{r\\}$ $E=\\{(s,r), (r, \ell)\\}$, and all edge weights are $1$. The algorithm will perform $\left\lfloor \frac{|L|+|R|}{2} \right\rfloor = 1$ iteration. Since there is no prescribed order in which the edges are considered, we can look at the case in which $(r, \ell)$ is considered before $(s, \ell)$.

When $(r, \ell)$ is examined, the condition of the if statement is not satisfied, so $d(\ell)$ is not updated. Moreover, when $(s, r)$ is considered only $d(r)$ can possibly be updated, so $d(\ell)$ is unchanged.

This shows that at the end of the algorithm $d(\ell) = + \infty$ but the distance between $s$ and $\ell$ in $G$ is $2$.

---
Tags: algorithms, graphs, shortest-path, correctness-proof, weighted-graphs
---


# Question
Title: How compiler optimizations create irreducible control flow graph?
I've been looking through research papers and the internet and found many claims that "compiler optimizations can cause irreducible control flow". However, I was not able to find a single example of how that can happen. In particular, in \[1\], there is written that tail recursion elimination in combination with inlining can yield an irreducible control flow graph. I can imagine some transformations that could create irreducible control flow, but I cannot come up with an example of how tail recursion elimination with inlining can do that?

Does anybody have a pointer here?

Thanks

\[1\] J. Stainer, D. Watson. A study of irreducibility in C programs.

# Answer
> 5 votes
Steele and Sussman's "LAMBDA The Ultimate Imperative", AI Memo 353, 1976 explains that a (tail) procedure call is just a `goto` statement and the name of the procedure is just a label.

So the classic irreducible flow graph:

(copy pasted from http://staff.cs.upt.ro/~chirila/teaching/upt/c51-pt/aamcij/7113/Fly0135.html)

Can be written:

```
procedure1():
  if (some-condition):
    return procedure2()
  else:
    return procedure3()

procedure2():
  if (some-other-condition):
    return True
  else
    return procedure3()

procedure3():
  return procedure2()

```

---
Tags: graphs, programming-languages, compilers
---


# Question
Title: Finding 2 nodes which sum equals twice their common ancestor in RBT in $\Theta(n\lg n)$
I have a red black tree, $T$, and I need to write an algorithm to find 2 nodes $x$ and $y$ so that $key\[x\] + key\[y\] = 2 \cdot key\[p(x, y)\]$, where $p(x, y)$ is the lowest common ancestor of $x$ and $y$, i.e $x$ is a node on $p(x, y)$'s left subtree and $y$ a node on the right subtree (or the other way around)

My original solution:

```
FIND-XY(root)
 1. x <- TREE-MIN(root)
 2. y <- TREE-MAX(root)
 3. sum <- x + y
 4. while x != root and y != root and sum != 2 * key[root]
 5.   if sum < 2 * key[root[T]]
 6.    x <- TREE-SUCCESSOR(x)
 7.   else
 8.    y <- TREE-PREDECESSOR(y)
 9.   sum <- x + y
 10. if sum = 2 * key[root]
 11.   return x, y
 12. return null

```

then for every node in the tree that isn't a leaf I will run FIND-XY with himself as root. FIND-XY runs in $\Theta(n)$ but there are $O(n)$ nodes that aren't leaves so the total run time is $O(n ^ 2)$

I know that there are $O(n)$ nodes that can be $p(x, y)$ so if I can change FIND-XY to run in $O(\lg n)$ then my original algorithm will run in $O(n\lg n)$, but this seems unlikely as finding these $x$, $y$ for the entire tree requires traversing in-order on all $n$ nodes in the tree which is $O(n)$

# Answer
Your algorithm is correct (it runs in time $O(n\log n)$). What you need is a tighter analysis of the runtime.

Look at the *depth* of each node in the tree. If two nodes has the same depth, then one can clearly not be the ancestor of the other, and their respective subtrees are also disjoint. Therefore, if you look at all the nodes at a given depth $k$, the sum of the sizes of all subtrees under these nodes can not exceed $n$. Thus, running your algorithm on all of these nodes can also be done in time $O(n)$.

Secondly, as you are working on a red-black tree, the maximum depth of any node is $O(\log n)$. The runtime follows easily.
> 1 votes

---
Tags: search-algorithms, binary-search-trees, red-black-trees
---


# Question
Title: Is there CIRCUIT-SAT algorithms that slightly depends on gates count?
For 3CNF-SAT problems exists a lot of algorithms that still have exponential complexity, but work faster than brute force. The complexity of this algorithm based on a number of variables or the number of clauses (they can't differ a lot because polynomially bounded to each other in 3CNF).

But for CIRCUIT-SAT size of the problem (number of inputs + number of gates) may differ much more - a number of gates may be exponentially larger than the number of inputs. So, after the conversation to 3-CNF (Tseytin transformation which creates new clauses and new variable for each gate), SAT-solvers will be overperformed by naive brute force algorithm, because its complexity only linear depends on gates count (to check SAT need to iterate over all input combinations which count exponentially depends on inputs count and compute outputs for each gate which is constant time operation for each gate).

So, the question is - is there exist CIRCUIT-SAT algorithms that slightly (polynomially or better) depend on gates count and can overperform brute force on cases where gates count much larger than inputs?

# Answer
Yes, such an algorithm exists, but it is the same algorithm used for SAT solving in general.

While the Tseytin extension variables associated with gates do appear in the CNF transformation of the original circuit, a minimally competent SAT solver will rarely branch on them. This is because one of the earliest heuristics discovered for speeding up searches was choosing decision variables based on how often they appear in clauses. The one-per-subformula Tseytin extension variables appear in only a few clauses, while the original input variables will be involved in many clauses as the leaves of the tree of Tseytin extensions. So the Tseytin variables will all have low scores and won't be used often as decision variables. The solver will therefore iterate through assignments of the input variables much like a brute-force search would, except that it will also take advantage of unit propagation, clause learning and all the other features of a modern SAT solver to get through the search space faster.

I say "minimally competent SAT solver" above because a really competent solver would take advantage of well-known CNF preprocessing techniques that can remove most of these gate variables before the actual solver search even starts. So CIRCUIT-SAT solvers are generally just SAT solvers. You *can* gain speed in some circumstances by having access to the original circuit in addition to the CNF result, but the gate variables don't much factor into that.
> 1 votes

---
Tags: complexity-theory, satisfiability
---


# Question
Title: What Is the Currently-Known Simplest NOR-node Directed Cyclic Graph That Produces Pi?
Any directed graph (including a directed cyclic graph or DCG) has a complexity measure. We know that NOR is a universal logic gate, in the sense that a DCG whose nodes are n-input NOR gates can represent any computable number. We also know that Pi is computable. Hence there are an infinite number of NOR DCGs that compute Pi.

What is the current record holder for the simplest (lowest complexity measure) of such DCGs?

# Answer
> 2 votes
Finite graphs don't compute pi; circuits do.

No single circuit computes pi. Rather, when we say that pi is computable, this means that there exists an infinite family of circuits $C\_1,C\_2,\dots$ such that $C\_i$ outputs the first $i$ digits of pi.

A standard measure of complexity for a circuit is its size: specifically, let $f(i)$ denote the size of $C\_i$, then its complexity is given by the function $f$ (we often care only about the asymptotic behavior of $f$). This is related to the running time of an algorithm for computing pi. You could take any standard algorithm for computing pi, convert it to a circuit and evaluate its size.

---
Tags: graphs, automata, logic
---


# Question
Title: Find an algorithm which returns the weight of a lightest path between all paths with a weight divided by three
Question: Find an algorithm which returns the weight of a lightest path between all paths with a weight divided by three in a graph with natural weights of the edges.

My instructor has given me a hint of doing calculations modulo three and creating a new graph and applying Dijkstra's algorithm on it.

I have no idea how to solve this question and I would be happy to get your help with a hint or a direction.

Thank you

# Answer
Since you asked for a hint: study the answer to How hard is finding the shortest path in a graph matching a given regular language? and understand it deeply. Then think about how to apply similar ideas.
> 2 votes

---
Tags: graphs, dijkstras-algorithm
---


# Question
Title: Divide members into multiple teams without overlap
I'm trying to separate people from a pool into several smaller groups. The group-size should always remain the same. People can be part of several groups - but no two people can be part of more than one group.

```
members = [A,B,C,D,E]

group1 = [A,B,C]
group2 = [A,D,E]

```

There aren't anymore valid groups possible. `A` can't be part of any more groups. `B` can't be in a group with `C` anymore (because they're already members of `group1`. `B` can be in a group with `D`, however `E` cannot be part of that group, because it can't be in a group with `E` \- since they're both already in `group2`.

So my question is, is there an algorithm where I can figure out all the possible team combinations for every members-size and group-size?

# Answer
> 0 votes
I've solved my own problem and wanted to share it with everybody

First, I need this helper-function that checks if any of the members of a current team have already been part of a previous team before:

```
def part_of_prev_teams(current_team):
    for member_i in range(0, len(current_team)):
        for member_j in range(member_i, len(current_team)):
            for team in teams:
                if member_i != member_j:
                    if current_team[member_i] in team and current_team[member_j] in team:
                        return True

```

The actual function looks like this:

```
pool = ["A", "B", "C", "D", "E", "F", "G", "H", "I"]
team_size = 3
teams = []

for member_i in range(0, len(pool)-1):              # iterate every member
    current_team = [pool[member_i]]                 # add the current member to current team
    for member_j in range(member_i, len(pool)):
        if len(current_team) >= team_size:          # team full
            break
        if pool[member_j] in current_team:          # member_i == member_j
            pass
        else:
            current_team.append(pool[member_j])     # add current member into the current_team
            if len(current_team) > 1:               # team has at least 2 members
                if part_of_prev_teams(current_team):# check for conflicts
                    current_team.pop()              # member was incorrectly added. remove it again
    if len(current_team) == team_size:              # team size has been reached. Finalize result
        print(current_team)
        teams.append(current_team)

```

For 9 members and a team-size of 3, this is what the result looks like:

```
['A', 'B', 'C']
['B', 'D', 'E']
['C', 'D', 'F']
['D', 'G', 'H']
['E', 'F', 'G']
['F', 'H', 'I']

```

Additionally, I've written this print-function to count the membership count of every member:

```
def print_memberships(teams):
    for member in pool:
        member_count = 0
        for team in teams:
            member_count += team.count(member)
        print(member + ": " + str(member_count))

```

Which prints the following result:

memberships:

```
A: 1
B: 2
C: 2
D: 3
E: 2
F: 3
G: 2
H: 2
I: 1

```

So, these are very "unfair" results. I was expecting every member to be part of an equal amount of teams, which isn't the case.

So then I went back to the pool-array and added another A/I (because it was in the least number of teams) and got much better results:

```
pool = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "A"]  # 2x "A" in list

['A', 'B', 'C']
['B', 'D', 'E']
['C', 'D', 'F']
['D', 'G', 'H']
['E', 'F', 'G']
['F', 'H', 'I']
['G', 'I', 'A']

memberships:
A: 2
B: 2
C: 2
D: 3
E: 2
F: 3
G: 3
H: 2
I: 2
A: 2
I: 2

```

---
Tags: combinatorics
---


# Question
Title: Fibonacci Heap: Could i always consolidate?
Right now I am learning about Fibonacci heaps for the first time. After the minimum Node of a Fibonacci heap is extracted you consolidate it, to give it a better structure and execute future operations faster. But why don't you consolidate the Heap more often, like after the insertion of 10 nodes with no consolidation in the meantime? Is it even possible to Consolidate whenever the heap feels like it? The consolidation would never break the structure, even if it is not executed after the ExtractMin()-Operation, am I right? Assuming that, I am right why is the consolidation not executed more often? Because it just makes no sense, as it doesn't make it faster or could it make it even slower?

Best regards, Alex

# Answer
In a Fibonacci heap, `delete-min` takes $O(\log n)$ amortised time, and `insert`, `find-min`, and `decrease-key` all take $O(1)$ amortised time. You could consolidate when you `insert` or `decrease-key`, but then they would take $O(\log n)$ amortised time.

To see why this is an advantage, consider what you would typically use a priority queue with `decrease-key` for, such as shortest path through a graph, or A\* search. For each step, you `delete-min` an item, then you process it, then you `insert` or `decrease-key` its successor items.

With a Fibonacci heap, you pay $O(\log n)$ amortised cost per entry that you *process*. The operations that you perform on the *successor* entries have constant-time cost.

Dijkstra's shortest paths algorithm in a case in point. If `insert` and `decrease-key` had $O(\log n)$ cost, then its complexity would be $\Theta((V + E) \log V)$. Using a Fibonacci heap, its complexity is $\Theta(E + V \log V)$.
> 1 votes

---
Tags: heaps
---


title: Time complexity of a power

text:
# Question
Title: Time complexity of a power
I am trying to work out the time complexity of my function but I'm not sure how it works with powers. I've got $y=(\frac{x}{3})^n$ as one of my lines. How many basic operations is this? Would it be $2(n-1)$ for the power then $1$ for the division and $1$ for the assignment of $y$?

Also, is the square root of a number just $1$ basic operation?

# Answer
*You* get to pick your model of computation. If you intend to run your algorithm on a computer, then it is appropriate to pick the model of computation that best fits the way your algorithm will be implemented. For example, in floating point arithmetic, computing $(x/3)^n$ takes $O(1)$, whereas in rational arithmetic you use the repeated squaring algorithm, but since the numbers involved get large, the running time isn't quite $O(\log n)$ (in particular, the end result is $\Omega(n)$ bits long). In practice, if we are computing $(x/3)^n$ exactly, then we're probably using modular arithmetic (i.e., computing everything modulo some number $m$), in which case the running time is $O(\log n \cdot \log m)$ bit operations.

In theoretical work, the most common model is some form of the RAM machine, or possibly the real RAM, which is common in computational geometry. In both cases, there isn't really a well-defined model that everybody agrees on, but in most cases it makes no difference. Analyzing an algorithm is model is important so we can compare the asymptotic running time of different algorithms.
> 1 votes

---
Tags: time-complexity
---


# Question
Title: Free variables in constraint-typing derivation?
In *Types and Programming Language*'s constraint typing rules (Figure 22-1), is it possible for any part of the typing derivation to contain free type variables that aren’t part of the fresh variables? Because the typing rules are based on the simply-typed lambda calculus with an infinite number of base types, a naïve reading would allow for $\Gamma$, $t$, or $T$ to contain type variables not mentioned in $\chi$. However, given that TAPL hasn't introduced polymorphism yet, I wonder if this case should implicitly be considered "invalid."

For a concrete example: Should $\varnothing \vdash (\lambda \\, x : X \rightarrow X, \\, 0) \\, (\lambda \\, x : X, \\, x) : \mathbb{N}$ be considered to have a "valid" constraint typing derivation, even though $X$ wouldn't be mentioned in the resulting $\chi$?

---

Figure 22-1 from *TAPL*, for reference:

---

**EDIT:** This question has been significantly edited in response to @frabala's answer, which made me realize that I hadn't been very clear initially. Hopefully it makes more sense now: See the edits and comments on @frabala's answer for a targeted answer to my question as currently written.

# Answer
> 3 votes
Not sure whether I completely understand the question, but here is my attempt:

> a naïve reading would allow for Γ, t, or T to contain type variables not mentioned in χ.

$\Gamma$, $t$ and $T$ may contain type variables not mentioned in $\mathcal{X}$. The set $\mathcal{X}$ contains only unification variables. That is, fresh variables generated by the typing process (in particular, by rule CT-App, where it is explicitly stated that the new unification variable $X$ should **not** appear in $\Gamma$, $t$, $T$, etc). Try exercise 22.3.3. In the process of building a derivation for the judgment shown there, $\Gamma$ will end-up containing the type variables $X$, $Y$ and $Z$ (which initially are part of the term $t$) and those variables will not belong in $\mathcal{X}$ at any point of the derivation.

> I think my question is actually if any of Γ, t, or T can have free type variables (i.e. that haven't been introduced by the type-inference rules).

$\Gamma$ can have type variables not introduced by the rules. For example, the term $(\lambda y : B.y)$ of the polymorphic type $B \to B$ is typable under some environment like $\Gamma = x:A$ (and to avoid ambiguity, one needs to make sure that the identifiers $x$ and $y$ are distinct). This would be another way to encode constants in a language. For example, instead of having the rule CT-Zero, we could always type a term under the unvironment $\Gamma\_0 = 0 : \mathrm{Nat}$.

Regarding the term $t$, this term is given and therefore, so are the type variables that it contains. So, the type variables in $t$ are certainly not introduced by the rules. The rules only manipulate the environment $\Gamma$, the type $T$, the unification variables $\mathcal{X}$ and the constraint set $\mathcal{C}$. The term $t$ is only being read.

Regarding the type $T$, it can also contain type variables not mentioned in $\mathcal{X}$. For example, try typing the term $(\lambda f: A \to A. f\\,0)$. When you reach rule CT-Var, the type $T$ in the conclusion of the rule will be $A\to A$, where $A$ will not appear in $\mathcal{X}$.

### Edit 1

I still don't fully understand the question. What do you mean by "standalone" derivations? Anyway, there is something I'd like to add:

> e.g. I can apply CT-App to two subderivations for which ₂ contains type variables in χ₁.

First, note that the typing rules are such that every new unification variable is recorded in $\mathcal{X}$.

Now, indeed rule CT-App loses some information. In particular, the derivation for $t\_1$ does not keep track of the fresh unification variables introduced in the derivation for $t\_2$, and vice versa. So, it could happen that $\mathcal{C}\_2$ contains unification variables that are mentioned in $\mathcal{X}\_1$.

However, any unification variable in $\mathcal{C}\_2$ is recorded in $\mathcal{X}\_2$. Thus, if $\mathcal{C}\_2$ contains unification variables mentioned in $\mathcal{X}\_1$, then $\mathcal{X}\_1\cap \mathcal{X}\_2 \neq \emptyset$. Because of this, applying CT-App on the two subderivations will fail in this problematic scenario, since the rule requires that $\mathcal{X}\_1\cap \mathcal{X}\_2 = \emptyset$.

This does not mean that the term application $t\_1\\, t\_2$ is not typable. Instead, this condition forces you to rename your unification variables accordingly, so that overlaps between the names of variables contained in $\mathcal{X}\_1$ and $\mathcal{X}\_2$ do not occur.

To sum up, two variables that have the same name and belong to both $\mathcal{X}\_1$ and $\mathcal{X}\_2$ should not be considered as the same variable. Instead, they should be considered as distinct variables that "coincidentally" were given the same identifier. Thus, an appropriate renaming solves the problem and rule CT-App can be applied.

Maybe now I do understand the question:

> if there are any implicit meta-constraints that disallow "standalone" type derivations from containing free type variables.

First, let's clarify that all type variables appear free, because the language has no type abstraction in its syntax. There are no $\Lambda$ or $\forall$ binders as those in System F. Now, every type variable $P$ that appears in $\Gamma$, $T$ or $\mathcal{C}$ has one and only one of the following two origins: either a) $P$ originates from the term $t$ (in the type of a $\lambda$-binder), and thus was given by the programmer, or b) $P$ is a freshly generated type variable. The set $\mathcal{X}$ keeps track of these type variables.

So given that we start our typing process with an empty $\Gamma$, all type variables that appear in a derivation are free and necessarily have one of these two origins. There can be no type variables of some other origin and this is not an implicit constraint. It is enforced by the typing rules. You can try proving the following:

$\text{If }\Gamma\vdash t: T\mid\_{\mathcal{X}} \mathcal{C}\text{, then }\forall P,\\,P\in\mathsf{FT}(T)\cup\mathsf{FT}(\mathcal{C})\implies P\in\mathcal{X}\cup\mathsf{FT}(\Gamma)\cup\mathsf{FT}(t).$

This statement also takes into account the case where we start the typing process with a non-empty $\Gamma$. I believe the proof can work by induction on the typing judgment.

Wow, I wrote a lot! :D

### Edit 2

Yes, your example is well-typed. In the application of rule CT-App, type $T\_1$ (from the rule in the figure) is actually $(X\to X)\to \mathbb{N}$ and type $T\_2$ is $X\to X$. This rule generates a fresh variable. The name of this variable should be distinct from those that appear in $\mathcal{X}\_1$, $\mathcal{X}\_2$, $T\_1$, $T\_2$, ... (3rd line of the rule's premises). So, because $X$ already appears in $T\_1$, we should come up with another name. Say, Y. The conclusion of the rule will be:

$$ \emptyset \vdash t\_1\\,t\_2 : Y \mid\_{\\{Y\\}} \\{(X\to X)\to\mathbb{N} = (X\to X)\to Y\\}$$

where $t\_1 = (\lambda x : X\to X. 0)$ and $t\_2 = (\lambda x : X. x)$. The rest of the derivation is more straight-forward to build.

---
Tags: type-theory, type-inference, types-and-programming-languages
---


# Question
Title: Which is (if any) the generic fastest method to perform modular exponentiation?
After a bit of surfing, I have found that Schönhage–Strassen (without taking in consideration recent optimizations) seems to be the base algorithm to perform the requested operation. Anyways, this algorithm is focused on "raw" multiplication of two integers $a$ and $b$, if a sufficiently large $N$ is chosen (the multiplication is modulus $2^N+1$.

A first question would be: how is this algorithm abstracted to perform exponentiation?

Say, we want to perform $$c^k \pmod{n},$$ how we proceed? A naive approach would be to use the Schönhage–Strassen with $a = c$, $b = c$ and $N$ such that $2^N+1 = n$, as many times as needed (in this case, $k-1$ times). Am I in the good direction? If not, how does it works? Is this algorithm the best one yet known?

# Answer
The standard method is exponentiation by repeated squaring: To calculate say x^11 modulo p, you start with x modulo p, then calculate x^2 modulo p, x^4 modulo p, x^5 modulo p, x^10 modulo p, x^11 modulo p. You won't get anything asymptotically faster than this.

For fixed exponents, you can find methods that take slightly fewer multiplications, but finding the right way will be very expensive, and this will only be worthwhile for smallish exponents that are used a lot.

You can save some multiplications if x is small compared to p. Let's say x^15 \< p, and you want to calculate x^255 modulo p. The normal method takes 14 multiplications. But we can calculate x^15 without any modular operations. Then instead of exponents 30, 31, 62, 63, 126, 127, 254, 255 we square five times to get exponents 30, 60, 120, 240 then multiply by x^15 modulo p. It's not asymptotically faster, but maybe 30 or 40% faster. For situations like a probabilistic primality test with small numbers to be exponentiated to huge exponenets this is quite useful.

Calculating (a * b) modulo p correctly may be time consuming; it may be significantly quicker to calculate (a * b) modulo p, plus some small multiple of p. Let reduce (a, b, p) be (a * b) modulo p + k\*p for some small unknown k. If you can show that for a, b \< x (put possible \>= p) reduce (a, b, x) produces a result less than x, in a shorter time than needed for (a * b) modulo p, then the whole exponentiation can be performed faster using the "reduce" function instead of modulo. Only the final result must be forced into the range from 0 to p-1. This can again bring significant percents in savings.

And obviously you should check whether a^2 modulo p can be found sligtly faster than a general (a\*b) modulo p.

PS. Didn't notice your requirement that the modulus is $2^N + 1$. This will make the calculation a lot easier.
> 1 votes

---
Tags: multiplication, modular-arithmetic
---


# Question
Title: Is an AND gate which is noisy 1/3 of the time on only one of its inputs universal?
Imagine you have a noise-free NOT gate, and an AND gate with the usual truth table

```
00 0
01 0
10 0    (*)
11 1

```

but such that the case (\*) is **wrong 1/3 of the time**, i.e. it gives 1 with probability 1/3, and 0 with probability 2/3.

Is this gate family universal, in the sense that one can write a logic formula with these gates only, and that the probability of obtaining the right outcome is \>1/2? (You also have noise-free SWAP and FANOUT, in case that helps).

Thanks!

# Answer
> 4 votes
Let $\land\_p$ be a gate with error $p$ only when the inputs are $1$ and $0$. What can we say about $$ (x \land\_p y) \land\_p (x \land\_p y)? $$ If $x=y=1$ then we always get $1$. If $x = 0$ then we always get $0$. When $x = 1$ and $y = 0$, we get the wrong answer $1$ with probability $$ p \cdot p + p \cdot (1-p) \cdot p = p^2(2-p). $$ Call that function $f(p)$. We conclude that this construction results in an $\land\_{f(p)}$ gate.

The function $f(p)$ is monotone increasing over $\[0,1\]$, and satisfies $f(p) \leq 2p^2 = (2p)^2/2$. Therefore $f(f(p)) = (2f(p))^2/2 = (2p)^4/2$. More generally, $f^{(t)}(p) = (2p)^{2^t}/2$. Consequently, if we apply this construction recursively $O(\log\log(1/\epsilon))$ times to your $\land\_{1/3}$ gate, we get an $\land\_q$ gate with error $q \leq \epsilon$. This requires a gadget of size $2^{O(\log\log(1/\epsilon))} = \operatorname{polylog}(1/\epsilon)$.

To handle a circuit of size $S$, you need to choose $\epsilon = 1/(2S)$, which results in a blowup of $\operatorname{polylog}(S)$.

---
Tags: logic, circuits, error-correcting-codes, fuzzy-logic
---


title: Easy proof for $Primes \in NP$

text:
# Question
Title: Easy proof for $Primes \in NP$
I want to show that $Primes \in NP$ an I've seen multiple proofs that use facts from number theory, like this one.

But isn't it much easier to proof $$Composites=\\{x\in \mathbb{N}\cup\\{0\\}:x=1 \vee\exists p,q\>1: x=pq\\} \in NP$$ first and then doing a polynomial reduction on $Primes$?

Because I can make a simple Turin-Machine Verifier that goes like this...

TM M on input $(n, (p,q))$

* Check if $1\<p,q\<n$
* Check if $n=1$ or $n=pq$
* Check if $n\geq 1$
* If all the checks above are true, then accept. Else decline.

All the number specifications are clearly polynomial, multiplication is also polynomial $\Rightarrow Composites \in NP$

Now I want to find a polynomial reduction i.e. $Primes \leq\_p Composites$

Clearly, $\overline{Primes}=Composites$, so we have $n \in Primes \Leftrightarrow n\notin Composites$

I define the function (Turing-Machine) $N$ on input $n$ simply as: If $n\in Primes$, decline. Else accept. (This TM runs in constant time)

Then, $n \in Primes \Leftrightarrow N(n) \in Composites$

Since $Primes \leq\_p Composites$ and $Composites\in NP$ $\Rightarrow Primes\in NP$

# Answer
As you have stated, $Composites\in NP$ and $\overline{Primes}=Composites$.

Hence, what you proved is that $Primes\in co-NP$.

There is no easy reduction $Primes\le\_p Composites$, since you will have to do the following task: given a number $n$, return another number $n'$ such that $n$ is prime if and only if $n'$ is composite.

What you did wasn't a reduction, since it didn't return a new number $n'$, but rather tried to directly build a TM for the problem. But you have to be wary that in the non-deterministic realm, you can't simply say "if some (non-deterministic) machine $M$ rejects, then \[...\]", since $M$ only verifies that something is *true* \- it **doesn't** verify when something *isn't true*.
> 3 votes

# Answer
Here is the definition of NP:

> A language $L$ is in NP if there is a polytime machine $T$ and a polynomial $p$ such that:
>
> * If $x \in L$ then there exists $y$ of size at most $p(|x|)$ such that $T(x,y) = 1$.
> * If $x \notin L$ then for all $y$ of size at most $p(|x|)$, $T(x,y) = 0$.

We think of $y$ as a *witness*.

*Composites* is in NP since $y$ could be a nontrivial factorization of $x$, and $T$ just checks that $y$ is indeed a factorization of $x$. Let $p$ be a polynomial such that there is always a factorization of size at most $p(|x|)$.

You're suggesting to define $S(x,y) = 1 - T(x,y)$. Let's see what this $S$ satisfies:

* If $x$ is prime then for all $y$ of size at most $p(|x|)$, $T(x,y) = 1$.
* If $x$ is composite then there exists $y$ of size at most $p(|x|)$ such that $T(x,y) = 0$.

This is not quite what we want in the definition of NP. In fact, the language that $S$ accepts nondeterministically is probably $\Sigma^\*$, since for every $x$ we can find a non-factorization $y$.
> 3 votes

# Answer
Your reduction was polynomial in the number N. To show that Primes is in NP, you need a reduction that is polynomial in the size of N, not in the number N itself. For example, one trillion stored in binary only takes 40 bits. So you are not allowed "polynomial in one trillion" but only "polynomial in 40" to show that a number around one trillion is a prime.
> 1 votes

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


# Question
Title: Efficient algorithm to find a rejecting input of an NFA
I cannot think of a PTIME algorithm to find a rejecting input of an NFA. While it is possible to efficiently find a rejecting input for a DFA, converting an NFA to DFA is too expensive.

The algorithm should have the following behavior: Given an NFA $A = (Q, \Sigma, \Delta, q\_0, F)$, if $L(A) = \Sigma^\*$, then return the error state $Err$, otherwise return any $w \in \Sigma^\* \setminus L(A)$.

Ideally, $w$ should be as short as possible.

Is this possible?

---

What I tried:

I thought of using a modified version of Thompson's algorithm. In Thompson's algorithm, the current input character is used to determine the next set of states from the current set of states. Thompson's algorithm will reject an input string if (1) the next set of states is empty or (2) if the string ended and the current set of states does not contain a final state.

Let $N\_T: P(Q) \times \Sigma \to P(Q)$ be the function from Thompson's algorithm that given the current set of states and an input character determines the next set of states.

By repeatedly using all characters $c \in \Sigma$ as input characters to create the next set of states, the algorithm can approximate simulating all input strings. The function determining the next set of states is defined as:

$$N: P(Q) \to P(Q); \\ N(S) = \bigcup\_{c \in \Sigma} N\_T(S, c)$$

The current set of states for a given iteration $k$ is defined as: $$S\_k = \begin{cases} \\{q\_0\\}, & \text{if } k = 0 \\ N(S\_{k-1}), & \text{otherwise} \end{cases} $$

In each iteration $k$, the following conditions (corresponding to the rejection conditions of Thompson's algorithm) are checked:

1. If $\exists c \in \Sigma$ such that $N\_T(c)=\emptyset$, then all $w \in \Sigma^k c$ will be rejected by $A$. Return any $w$.
2. If $S\_k \cap F = \emptyset$, then all $w \in \Sigma^k$ will be rejected by $A$. Return any $w$.

Lastly, if an already seen set of states is seen again, the algorithm returns $Err$. This ensures that the algorithm terminates.

However, there are 2 problems with this algorithm:

1. It's only an approximation. There are some NFA for which this algorithm returns $Err$ even though the NFA doesn't accept all inputs.
2. It terminates after at most $2^{O(n)}$ many steps. This isn't PTIME.

# Answer
Keith Ellul, Bryan Krawetz, Jeffrey Shallit and Ming-wei Wang constructed, in their paper Regular Expressions: New Results and Open Problem, a regular expression of size $O(n)$ for which the minimal rejected word has size $\Omega(n2^n)$; here $n$ is an arbitrary parameter. The regular expression can be converted to an NFA with $O(n)$ states and transitions with similar properties.

This shows that you need exponential time just to output $w$.
> 4 votes

---
Tags: regular-languages, finite-automata, nondeterminism
---


# Question
Title: What is the relations between $\mathsf{DTIME}(2^{O(n)})$ and $\mathsf{DTIME}(n^{O(\log n)})$
What is the relations between $\mathsf{DTIME}(2^{O(n)})$ and $\mathsf{DTIME}(n^{O(\log n)})$? Is one contained in the other?

# Answer
> 1 votes
Since $n = 2^{\log n}$, that means that $n^{\log n} = 2^{(\log n)^2}$. Now you just need to compare $n$ and $(\log n)^2$.

---
Tags: complexity-theory
---


title: Modified Union Find Data Structure

text:
# Question
Title: Modified Union Find Data Structure
The task is to make data structure with the following operations:

query: takes two arguments s and t and returns true if they are in the same set and false otherwise.

union: takes two arguments s and t and creates a union of the two sets that contain s and t such that if s is in S and t is in T it removes S and T and replaces it with the union of S and T.

move: takes two arguments s and t and takes s out of its current set and moves s and only s to the set containing t.

union and move don't do anything if s and t are in the same set.

My question is: how do you make an efficient version of this data structure that is \< O(n²)?

# Answer
> 1 votes
You want Union-Find with deletions (Kaplan et al. 2002, and Alstrup et al. 2005). You can do deletion in constant time, but it's non-trivial.

---
Tags: data-structures, union-find
---


title: Simplification of regex

text:
# Question
Title: Simplification of regex
I have a regex $R=\epsilon+1+(\epsilon+1)(\epsilon+1)^\*(\epsilon+1)$ which has to be simplified by algebraic operations. As we can do,

$\epsilon+1+(\epsilon+1)(\epsilon+1)^\*(\epsilon+1)=\epsilon+1+(\epsilon+1)^+=(\epsilon+1)^+$ but the answer is $1^\*$.

Can anyone please help me to find this with step by step solution?

# Answer
No. I'm not going to give a step-by-step solution, but here's a hint or two: $(\epsilon + 1)$ can generate either nothing or a 1; $(\epsilon + 1)(\epsilon + 1)$ can generate 0, 1, or 2 copies of 1. Take it from there.
> 1 votes

---
Tags: regular-expressions
---


# Question
Title: an algorithm to find the shortest path between two vertices whose weight is divided by 3?
I am trying to think of an algorithm such that giving a graph $G(V,E)$, and a weight function $w\colon E \to \mathbb{N}\_+$ (which means giving every edge in the graph a positive weight), and a source vertex $S$, the algorithm finds the shortest path between each $v \in V$ and $S$, such that the weight of the path is divided by 3 . (The weight of the path means the sum of all the weights of the edges that are on the path.)

In some solutions, I found that for this problem they built a new auxiliary graph which will "maintain the weight modulo 3" so that when we get from $S$ to any vertex we will be interested in the path that starts and ends with remainder 0 and this is through duplicating the graph to 3 copies which will allow switching between different copies.

I don’t understand how to build such a graph and how it is going to help me with this problem, any help would be appreciated.

# Answer
Given $G=(V,E,w)$ the auxiliary graph you want to build is $H=(V', E', w')$ where:

* $V' = V \times \\{0,1,2\\}$
* Given $(u,i), (v,j) \in V'$, $( (u,i), (v,j) ) \in E'$ if and only if $(u,v) \in E$ and $i+w(u,v) \equiv j \pmod{3}$.
* For any $e' =( (u,i), (v,j) ) \in E'$, $w'(e') = w(u,v)$.

For any vertex $v \in V$, a shortest path $\pi'$ between $(S,0)$ and $(v, 0)$ in $H$ induces a path $\pi$ from $S$ to $v$ in $G$ that is shortest among those having length divisible by $3$. In details, let $\langle v'\_0, v'\_1, \dots, v'\_k \rangle$ be the vertices traversed by $\pi'$, where $v'\_j = (v\_j, i\_j)$. The path $\pi$ traverses the vertices $\langle v\_0, v\_1, \dots, v\_k\rangle$, in order.
> 0 votes

---
Tags: algorithms, graphs, algorithm-analysis
---


# Question
Title: Inapproximability of graph problems on a restricted setting
I am considering the following problem $\mathcal{P}$.

$\mathcal{P}$: Given an undirected graph $G$, and an integer $k$, find a set of vertices $S \subseteq V(G)$, with $|S| = k$, such that the number of edges in the subgraph induced by $S$ is minimized.

which is clearly NP-hard, as the answer is 0 iff there is an independent set of size $k$ in $G$. So I am interested in studying whether the problem can be approximated assuming $\mathrm{P} \neq \mathrm{NP}$ (assumption implicit from now on). More precisely, saying that $\mathcal{P}$ cannot be approximated by a factor better than $\rho$ means that there is no constant $\alpha \< \rho$ for which a polytime algorithm $A$ can guarantee that $A(G, k) \leq \alpha \mathrm{OPT}(G,k)$ for every input $G, k$.

Now, for the restricted setting, imagine $c \> 0$ is an arbitrary constant, and then define $c\mathcal{P}$ as the same problem but with the restriction that $|V(G)| \geq c \cdot k$. The question I am wondering is whether, given the following claims 1) and 2), it is true that 1) implies 2).

1. There is a constant $\rho \> 1$ such that $\mathcal{P}$ cannot be approximated by a factor better than $\rho$.
2. There is a constant $\rho' \> 1$ such that for any constant $c \> 0$ the problem $c\mathcal{P}$ cannot be approximated by a factor better than $\rho'$.

I would appreciate any help, or pointers to problems when something like that is proven.

# Answer
> 1 votes
Yes, $(1) \implies (2)$. Suppose towards contradiction that $(1)$ is true but $(2)$ is false. Negating $(2)$ gives

$\forall \rho' \> 1 \exists c \> 0$ such that the problem $cP$ can be approximated by a factor better than $\rho'$ in time polynomial in the vertex count.

(I added "in time polynomial in the vertex count", since without a restriction like this you could of course solve the problem exactly in exponential time.)

Let $c\_{\rho'}$ be a value of $c$ that works for $\rho'$ (the negation of $(2)$ makes this well-defined for each $\rho'$). Now arbitrarily good $\rho'$-approximations can be made to the original problem in time polynomial in the number of vertices: Just keep adding vertices that are adjacent to every other vertex until $|V(G)| \ge c\_{\rho'}k$ and then solve using the approximation algorithm for the restricted problem. If the solution contains any of the added vertices, swap each one with any original vertex -- this cannot make the solution worse.

Note that the above approximation algorithm is polynomial in the original number $n$ of vertices even if $c\_{\rho'}$ is very large, e.g., superexponential in $\rho'$, because for $k, \rho'$ fixed and $n$ large enough, $n \ge c\_{\rho'}k$ so no vertices need to be added.

The existence of a poly-time $\rho'$-approximation for the original unrestricted problem and for arbitrary $\rho'$ contradicts $(1)$ (specifically, you could choose, e.g., $\rho' = (1+\rho)/2$), so it must be that $(1) \implies (2)$.

(Aside: It's not necessary for $(1)$ to hold for the above proof to go through, but if $\textrm P \ne \textrm{NP}$, it does anyway, since if a poly-time $\rho$-approximate algorithm for your problem for arbitrary $\rho \> 1$ existed, you could use it to solve Maximum Independent Set *exactly* in poly-time: Choose any $\rho \> 1$ and run the $\rho$-approximate algorithm for your problem inside a binary search on $k$ until we find the largest $k$ for which it reports an answer of 0. Since the approximation ratio is defined multiplicatively, the true answer for this $k$ must also be 0, and since $A(G, k) \ge OPT(G, k)$, the true answer for $k+1$ is $\> 0$, so $k$ is the size of a largest IS.)

---
Tags: complexity-theory, np-hard, approximation
---


title: Marks that are impossible to obtain?

text:
# Question
Title: Marks that are impossible to obtain?
There is an exam and the marking pattern is -

```
0 marks - Unattempted

4 marks - Correct Answer

-1 marks - Incorrect Answer

```

And total number of question is 30. Find the total marks ( in integer ) which are not possible to obtain in the exam. eg.,119 , 118 , 117 etc are the marks that I can think of. Is there any way to approach such question.

# Answer
If you need a computational way, you can use dynamic programming.

Let $C(i, s)$ be an indicator whether you can achieve a mark $s$ by $i$ questions. This means $C(i, s) = 1$ if there is a way to achieve a mark $s$ by $i$ questions, and $0$ otherwise. Clearly for $i = 0$ we have $C(0, 0) = 1$ and $C(0, j) = 0$ for all $j \neq 0$. Now the recursive formula is given by $C(i, j) = \bigvee\limits\_{k \in \\{0, -1, 4\\}} c(i-1, j-k)$.

Clearly, you can implement this by iterating over all $i \in \[30\]$ and for each $i$ over each value $s \in \[-30, 120\]$.

This is a pseudo-polynomial algorithm, which means it runs in polynomial time in the input itself and not its size. However, since you need to output these values, we can assume that the input is given in unary and hence the algorithm runs in polynomial time (else the output itself might have exponential size).

However, if you want a more straightforward (mathematical) way to know whether a given mark is achievable, I would suggest you look up the extended euclidean algorithm. Specifically, the part where they put an upper and lower bound on the coefficients. Note that the sum of the coefficients, in this case, is at most $30$.
> 2 votes

---
Tags: discrete-mathematics
---


# Question
Title: Prove that grammar accepting arithmetic expressions is not regular
I created a grammar which accepts all arithmetic expressions consisting of $+,-,\*,/, (, )$.

I created the following grammar:

> $S \rightarrow M+-M$
>
> $+-M \rightarrow +M+-M$
>
> $+-M \rightarrow -M+-M$
>
> $+-M \rightarrow \epsilon $
>
> $M \rightarrow E\*/E$
>
> $\*/E \rightarrow \*E\*/E$
>
> $\*/E \rightarrow /E\*/E$
>
> $\*/E \rightarrow \epsilon$
>
> $E \rightarrow a$
>
> $E \rightarrow (S)$

Where S is sum and our starting symbol, +,-,\*,/,(,),a are terminal symbols and S,M, +-M, E, \*/E, () are nonterminals.

Now the question is, how do I prove that such grammar can't be regular?

# Answer
> 2 votes
Lets call this language $L$ and assume towards contradiction that it is regular.

We build the following homomorphism $h:\Sigma\rightarrow \\{0,1\\}^\*$ by:

$$h(x)=\cases{0&$x=\`(\`$\\1 &$x=\`)\`$\\\epsilon&otherwise}$$

Since regular languages are closed under homomorphism, then $h(L)$ is regular as well. Now, lets take a look at the following language: $\hat L:=h(L)\cap L(0^\*1^\*)$.

Clearly, $\hat L$ is regular as the intersection of two regular languages. But also, its not hard to see that $\hat L=\\{0^n1^n|n\in \mathbb{N}\\}$ and we know this language isn't regular.

Hence we got a contradiction, meaning that $L$ couldn't have been regular.

---
Tags: automata, formal-grammars, pushdown-automata
---


title: prove language is decidable

text:
# Question
Title: prove language is decidable
The question is:

The language L contains $DFAs$ which can accept languages equal to $\Sigma$*

prove this language is decidable.

I'm new to the Decidability topic and I don't know where should I start proving this?

reduce? Rice theorem? or we don't need things like reducing and...I would appreciate it if someone teaches me the way of thinking and proving these questions. thanks in advance.

# Answer
> 2 votes
Your task is to prove that the language is decidable.

Rice's theorem shows only when a language is *not* decidable, hence it can't be used.

About reduction: for as long as you can reduce this problem to some other decidable problem, its fine. That is, you can show that $L\le\_p L'$ for some decidable $L'$ and this would ensure that $L$ is also decidable.

However, the best way to do this (in my opinion) is to directly build an algorithm that decides the question. If you want a small hint, try to answer the following: how would you decide the language of all $DFA$s that accept $\emptyset$?

# Answer
> 2 votes
If you have an algorithm which decides "Does DFA $M$ accept $\Sigma^\*$?" you just need to check if the input is a DFA (in whatever reasonable notation you specify), if not, reject; if it is a DFA, apply the above algorithm. This decides your language.

---
Tags: undecidability
---


title: Is this graph Hamiltonian?

text:
# Question
Title: Is this graph Hamiltonian?
My case is a *directed* graph with $n$ nodes with $(n-1)^2+1$ edges. I have done the following till now.

We know that the maximum number of edges for a directed graph $K\_n$ on $n$ nodes is $n(n-1)$ edges. The graph in my problem statement is $G(V,E)$ with $|V| = n$ and $|E|$ = $(n-1)^2+1$.

Now, $n(n-1) - ((n-1)^2 + 1) = n-2$, so any such graph can be obtained from $K\_n$ by deleting exactly $n-2$ edges from $K\_n$.

> Is my approach correct till now? How can I apply induction to prove the graph is Hamiltonian? I'm new to graph theory and inductions. As such, a comprehensive simple explanation would be much appreciated.
>
> If not induction, is there any other way to prove this?

# Answer
The complete digraph of $n$ nodes, $K\_n$ has $n(n-1)$ edges. Describe a digraph of $n$ nodes with $n(n-1)-\delta$ edges as a digraph "with $\delta$ edges removed".

### A proof by induction

The following is an outline to prove by induction that every digraph of $n$ nodes with $n-2$ edges removed contains a Hamiltonian cycle.

The base case, when $n=2$ or $n=3$ is obviously correct.

Suppose $n\gt3$. Let $G$ be such a graph. There are two cases.

* There is one node with exactly one edge from it or to it removed.
Let that node be $u$. By induction hypothesis, there is one Hamiltonian cycle for the induced subgraph of the remaining nodes. Verify that cycle can be modified to pass $u$ as well, hence becoming a Hamiltonian cycle of $G$.
* Otherwise, for each node, either no edge from it or to it are removed, or at least two edges from it or to it are removed.
Let $v$ be a node of the former kind and $w$ be a node of the latter kind. Let $G'$ be the induced subgraph of the remaining $n-2$ nodes. Since $2(n-2)\gt n-2$ and there are $2(n-2)$ possible edges between $w$ and a node in $G'$, there must be one edge of $G'$ that is between $w$ and some node of $G'$. By induction hypothesis, $G'$ contains a Hamiltonian cycle. Verify $C$ can be modified to include that edge as well as pass $v$, becoming a Hamiltonian cycle of $G$.

### Explanation of Yuval's neat answer

Consider **all (directed) Hamiltonian cycles in $K\_n$**. What is the total number of edges in them, with duplicity counted?

* Let $f$ be the number of all Hamiltonian cycles. Since each cycle contains $n$ edges, that total number is $nf$.
* The number of times an edge appearing in those cycles is the same for each edge, thanks to symmetry. Denote it by $p$. Since there are $n(n-1)$ distinct edges, that total number is $n(n-1)p$.

We have, $$ nf = n(n-1)p,\ \ \text{ i.e., }\ \ f= (n-1)p $$

Let us remove edges from $K\_n$ so as to obtain the given graph $G$. Since removing an edge affects only Hamiltonian cycles in which that edge appears, removing $n-2$ edges will affect at most $(n-2)p$ Hamiltonian cycles. Since $f=(n-1)p \> (n-2)p$, at least one Hamiltonian cycle will not be affected after removing $n-2$ edges. That is, there is at least one Hamiltonian cycle in $G$. $\quad\checkmark$

Stating the explanation in terms of probability and expectation, we shall obtain Yuval's answer.

---

The only facts about Hamiltonian cycle used in this proof are that it has $n$ edges and that the concept is symmetric to each edge. We have, in fact, proved the following remarkable proposition.

*Given $n\ge2$, digraph $G$ of $n$ nodes with $n-2$ edges removed and digraph $D$ of $n$ nodes with $n$ edges, $G$ must contain a subgraph that is isomorphic to $D$.*
> 4 votes

# Answer
If you choose a Hamiltonian cycle at random, the expected number of edges missing is strictly less than $1$.
> 2 votes

---
Tags: graphs, induction, hamiltonian-path
---


title: concurrency vs parallelism

text:
# Question
Title: concurrency vs parallelism
I am so confused between concurrency vs parallelism in multi-core processors.

If a **concurrent process** has many threads and if the **processor is multi-core** then can each thread run on multiple cores? If the answer is YES then multiple threads are running in parallel but the process is concurrent. How is it possible and where is the concept of concurrency applied?

but if your **answer is no** then why do we even need **concurrency concept**. Why cant all processes be based on **parallelism concept**?

If I assume that **multiple threads of the concurrent process run in parallel**.

Then which is better performance-wise concurrency in multi-core vs parallelism in multi-core and why?

# Answer
A simple re-look at the terms used in question will provide the answer.

A process is a program in execution.

Often a process consist of multiple software threads. The work of the process is divided among the threads. If the work done by threads is relatively independent, they can execute concurrently on available processor cores.

Most modern processor consist of multiple core, where each core is capable of executing, **at-least** one software thread. So if the processor consist of n cores, n different software threads can execute concurrently on n cores. It is not necessary that all n threads belong to same process. The number of software threads **can be higher than n (the number of cores)**, if the threads perform a lot of relatively slower memory access and/or I/O operations. So more than one thread can share a core, running alternately, giving a user the impression that they are running concurrently. They are actually executing in time-sliced manner. One thread run for few cycles then it is removed from the processor and another thread execute for few cycles and so no.

No parallel execution of a multi-threaded process is possible unless threads of the process execute concurrently.
> 1 votes

# Answer
I agree the usage of the terms *concurrent* and *parallel* in computing is confusing. Part of the confusion is because the English word *concurrent* means: "at the same time", but the usage in computing is slightly different.

In computing we say two threads have the *potential* to run concurrently if there are no dependencies between them. When we say two threads *are* running concurrently, we *might* mean that they are running in parallel on two different physical cpu cores. But we also might mean this in the virtual sense of multitasking. For example a single cpu core might be running both threads using preemptive multitasking to switch back and forth between them every 1/100th of a second. So over a timespan of an entire second it *appears* the two threads are running simultaneously, while in fact only one of them is running at a time and we're just switching back and forth between them very quickly.

I try to use the word *concurrency* to refer only to *potential* concurrency. I try to use the word *parallel* when I want to indicate that two (potentially) concurrent threads are actually running simultaneously on different cpu cores. And I try to use the term *multitasked* or *interleaved* when I want to indicate that two (potentially) concurrent threads are sharing the same cpu core over a long period of time, with the cpu core switching back and forth between the two threads.
> 1 votes

# Answer
The exact use of such terms depends on context and author, but generally speaking, I would say that concurrency is a much broader term than parallelism; parallelism is a form of concurrency.

The term *concurrency* is generally used to describe a situation in which processing doesn't necessarily happen in strict sequential order. The things in question can be events, or processes, or actions performed by humans, by computers, by nature, or whatever else ... it really is a very broad term. Examples of concurrent processes:

* a chemical reaction
* shopping at Amazon (including the customer placing an order)
* cars driving around
* you watching a YouTube video

The antonym of *concurrency* is *sequentiality*. In a sequential process, everything happens in a strict sequential order: no step starts before the previous step has finished.

The term *parallelism* is generally used to describe a very specific kind of concurrent process, in which all processing in question is executed by processors within one computer, and multiple processors or threads run at the same time, using shared resources.

The antonym of *parallelism* is *distributed computing*; in distributed computing, we still describe processes executed entirely on computer processors, but in contrast to parallel computing, the processors have their own resources, and they need to communicate, usually by means of some form of message passing over dedicated message passing channels, in order to cooperate.

So both parallelism and distributed computing are two specific forms of concurrency, in which all processing is executed on computer processors.

Your question assumes a context in which we're talking about parallelism, and then asks why we use the term *concurrency* at all, when *parallelism* will do. Yes, it will, when referring to parallelism; it won't do in general.
> -1 votes

---
Tags: operating-systems, parallel-computing, concurrency, threads
---


# Question
Title: Communication complexity of equality gap problem
I'm interested to know what is the biggest known $0\le \epsilon\le 1$ such that the $gap-EQUALITY$ problem that is defined by:

$$f\_\text{GEQ}(x,y)=\cases{1&$x=y$\\0 & $x$ and $y$ differ in at least $\epsilon\cdot n$ positions\\\text{undefined}&otherwise}$$

Still requires $\Omega(n)$ communication bits?

Thanks!

# Answer
When $\epsilon \< 1/2$, you can pick a code with exponentially many codewords and minimum distance $\epsilon n$. If the inputs are promised to be in the code, your problem becomes EQUALITY, and so requires $\Omega(n)$ communication.

When $\epsilon = 1$, the problem becomes easy (send the first bit).
> 2 votes

---
Tags: approximation, lower-bounds, communication-complexity
---


title: Find non common numbers in two arrays

text:
# Question
Title: Find non common numbers in two arrays
Given two arrays of integers, please write a function that returns all elements present in one of the two arrays but not both. E.g. f(\[ 1, 3, 5 \], \[ 1, 2, 4, 5 \]) -\> \[ 2, 3, 4 \]

I know I can do this with two for loops that is O(n^2) but is there any better way ? Please help

# Answer
One simple solution is to merge the two arrays, sort them, and then remove the duplicate elements that belong to different arrays. It takes $O(n \log n)$ time.

---

Implementation:

1. For every element $e$ in array $1$, make a pair $(e,1)$. Let the array of these pairs be $P\_{1}$. For every element $e$ in array $2$, make a pair $(e,2)$. Let the array of these pairs be $P\_{2}$.
2. Merge $P\_{1}$ and $P\_{2}$. Let the merged array be $P\_{m}$.
3. Sort $P\_{m}$ in ascending order on the basis of the first value of a pair. If there is a tie then use the second value for comparison. You can employ merge sort since it takes $O(n \log n)$ time.
4. Keep only one copy of a pair that appears multiple times in the array. It takes $O(n)$ time.
5. Traverse the array from left to right. If any two consecutive pairs in the array have the same first value, remove them from the array.

The resulting array gives the required solution.
> 2 votes

---
Tags: algorithms, time-complexity, space-complexity, big-o-notation, c++
---


title: What is the comparator circuit?

text:
# Question
Title: What is the comparator circuit?
The standard circuits $AC^i$, $NC^i$ are constructed using $AND$, $OR$ and $NOT$ of various fan-ins, fan-outs and depths.

What is the comparator gate constituted from?

Structurally why is it believed $NC^i$ is not in any $CC^j$ if $i\geq 1$ and why is it believed $CC^i$ is not in any $NC^j$ if $i\geq 1$ (refer https://arxiv.org/abs/1208.2721 for the conjecture $NC$ and $CC$ are incomparable)?

# Answer
A comparator circuit is a circuit computing a function on $x\_1,\ldots,x\_n \in \\{0,1\\}^n$. The inputs to the circuit are labeled with either constants ($0$ or $1$), inputs ($x\_1,\ldots,x\_n$) or negated inputs ($\lnot x\_1,\ldots,\lnot x\_n$). The only allowed gate is a comparator gate, which has two inputs $a,b$ and two outputs $a\land b,a\lor b$. The circuit has no *fan-out*, that is, an output cannot be duplicated. One of the "wires" is designated as an output (just like a usual circuit).

Equivalently, we can represent a comparator circuit as a "straight-line program" with $m$ variables $z\_1,\ldots,z\_m$, each initialized by a constant, an input, or a negated input. The program itself is a sequence of instructions of the form $$ z\_i,z\_j \gets z\_i \land z\_j,z\_i \lor z\_j. $$ One of the variables $z\_o$ is the output of the circuit.

It is believed that CC and NC are incomparable since nobody managed to show that one of them is contained in the other. Usually, such inclusions are either easy or false, though sometimes this intuition is wrong (the best example is SL=L).
> 1 votes

---
Tags: complexity-theory, sorting, complexity-classes, circuits, matching
---


title: Minimum number of moves puzzle

text:
# Question
Title: Minimum number of moves puzzle
Let K players be among N towns in a circular position.

* On each turn, only one player can move.
* A player cannot move if he is the one who moved in the previous turn.
* A player can only move clockwise to the next town, ex from town 0 to town 1, from town T to town T + 1, from town N - 1 to town 0.
* Each town at any point can have 0, 1, or more players.

What is the minimum number of turns, so all the players end up in the same town (if that's possible)?

Any algorithm for solving this puzzle? It is a school assignment.

# Answer
You can determine simply if there is no solution. Case $K=2$ with the players on different and non-adjacent cities (thanks orlp to point it).

Let's first assume a simpler problem where players may move several time in a row. Then you know the arrival point is necessarily one of the initial position of a player. Indeed, a city just before one with no player on it is reached $K$ turns before.

Let's call :

* $D(i)$, the number of turns needed to meet all players on starting city $i$.
* $S$ is the number of starting cities ($S \le K$ and $S \le N$).
* $p\_i$ is the clockwise position of starting city $i$.
* $s\_i$ is the number of players on starting city $i$.

First of all, you need to find all starting cities and the number of player on it. Depending on input format, It may be done in $O(K)$, $O(S)$ or $O(N)$. So the solution is the minimum of $D$. You may compute all $D(k)$ with the trivial sum in $O(S^2)$ :

$D(k) = \sum\_{i=0}^{S-1} ((p\_k-p\_i) \mod{N}) s\_i$.

But it is more efficient to do it by difference with the sum of the previous city, achieving $O(S)$:

$D(k+1) - D(k) = (K-s\_{k+1}) \times((p\_{k+1}-p\_{k}) \mod{N}) - s\_{k+1} \times (p\_{k+1}-p\_{k}) \mod{N})$

So now, to consider the "turn alternation" constraint, you have an additional computation to do, let's call it $A\_k$, the number of turns needed to advance all players some more cities so they can meet respecting alternation. Let's also define $L(k)$, the longest distance a player may have to do to reach starting city $k$.

Note that $L(k) = p(k+1)-p(k) \mod{N}$.

all $A(k)$ are computed in $O(S)$ :

if $L(k) \le \frac{D(k)+1}{2}$ then $A(k) = 0$, basic alternation let you finish on starting city $k$.

else $A(k) = K \times ceil( \frac{L(k)-(\frac{D(k)+1}{2})}{K-2} )$, as you may alternate with the $K-1$ other players.

And the solution to your problem is $\min(D(k)+A(k))$ that you find in $O(S)$ = $O(min(N, K))$ with an adapted input format, else probably something like $O(max(N, K))$.

EDIT: exemple with :

* $N=13, K=5$
* $p=\[0, 10, 11\]$
* $s=\[1, 3, 1\]$
* $S=3$

$D(0) = 0\times1 + 3\times3 + 2\times1 = 11$

$D(10) = D(0) + 2\times10 - 3\times3 = 22$

$D(11) = D(10) + 4\times1 - 1\times12 = 14$

$L(0)= 3 \implies A(0) = 0$

$L(10) = 10 \implies A(10) = 0$

$L(11) = 11 \implies A(11) = K \times ceil(\frac{4.5}{K-2}) = 2\times K = 10$

It means you cannot chose city 11 as arrival but city 0 instead making players advancing 2 extra cities, which would take a total of 24 turns (as the player starting at 0 would have done a full cycle). Of course, the answer to the problem, is the first one going to city 0 without moving the player on it in 11 turns.
> 2 votes

# Answer
Quite simple if time complexity O(K\*N) is acceptable:

For each of the N towns, you calculate how long it takes for everyone to reach that town. First, you add everyone's distance to that town. That's one minimum requirement. Second, since nobody can do two turns in a row, find the person furthest away. If the person is X steps away, then they can't reach that town earlier than after 2X-1 moves. So you calculate max (sum of all distances, 2\*largest distance - 1). You do that for each town and chose the smallest value.

You can get the time complexitiy a lot lower by counting how many players are in each town initially, calculating the numbers for the first time, and for each of the following towns calculate the numbers in constant time by using the numbers of the previous town. (For example if you know the sum of distances to town 3, then for town 4 you increase that sum by K since everyone goes one step further, then subtract N * number of players in town 4, because these don't move N steps but no steps at all. )
> 0 votes

---
Tags: algorithms, optimization, np-complete, space-complexity
---


title: Factor $n$ in RSA if we know $φ(n)$

text:
# Question
Title: Factor $n$ in RSA if we know $φ(n)$
If we know that $n = 1363$ and $φ(n) = 1288$, how can we factor $n$?

# Answer
If $n$ is the product of two distinct primes, say $n = pq$, then $\varphi(n) = (p-1)(q-1) = pq-(p+q)+1$. Therefore given $n$ and $\varphi(n)$ you can determine both $pq$ and $p+q$. By solving a quadratic equation, you can find both $p$ and $q$.
> 3 votes

---
Tags: algorithms, cryptography
---


title: Shortest path in a grid with turnstile

text:
# Question
Title: Shortest path in a grid with turnstile
This question is a simplification of the one about finding the shortest path in a grid with turnstile **and waypoints**. Since this simplification has dramatic consequences, I think it deserve its own question and answer.

Here's a reminder of how the turnstile tiles work.

* A turnstile tile has two bars on adjacent sides of the tile.
* You cannot step into a turnstile tile if it would mean crossing a bar.
* You can exit a turnstile tile in any direction.
* If you exit the tile in a direction where there was one of the bars, then the pair of bars *rotate* by a 1/4 turn such that there's no more bar in the direction you exited the tile from (see this video at 7:02).

Here's an example before and after exiting a turnstile tile:

How do we find the shortest path from A to B in a grid maze with turnstiles?

# Answer
> 2 votes
**Update:** I'm accepting my own answer for now. If anyone want to make an answer with the full proof, I'll glady accept it.

---

**Short answer:** Encode the maze as a directed graph and apply your usual Dijkstra or A\*, ignoring the state you leave the turnstiles in. The turnstiles can be encoded by having arcs both ways on the sides without bar, and only the out going arc for the sides with bars.

For instance, this turnstile:

Can be turned into this graph portion:

Of course, don't connect the center node to its neighbor if it's not reachable (like a wall).

**Long answer:**

The essential property that make it work is that shortest paths never include cycles, even with those turnstiles.

**Claim:** Shortest path don't include cycles.

**Idea of the proof:**

Let's assume the shortest path $P$ between nodes $A$ and $B$ visit the same node $N\_1$ twice. For $P$ to be the shortest path, there must be a node $N\_2$ that we can access on the second visit to $N\_1$ but not on the first visit. Otherwise reaching $N\_2$ from $N\_1$ on the first visit would lead to a path shorter than $P$.

But this situation cannot exist because unlocking the way between $N\_1$ and $N\_2$ requires visiting the blocking turnstile(s). Therefore there's no need to revisit $N\_1$ to access $N\_2$.

Then it follows that:

* When looking for a shortest path, there's no need to consider revisiting nodes.
* Thus the rotation of the turnstiles already visited can be completely ignored.
* Since there is no additional *state* to keep track of, the usual Dijkstra or A\* can be used.

---
Tags: shortest-path
---


# Question
Title: 2D version of LeetCode house robber problem
The house robber problem of leetcode can be described as followed :

> A robber enters a colony of houses numbered from 1 to n. Every house has a number printed on the top of it. That number is the amount of money inside that house. However, there is one constraint. If the robber robs the i-th house, he can't rob house no i-1 and house no i+1. How can the robber maximise his robbery?

Apparently, this is a classical problem in dynamic programming, which can be solved in linear complexity: See here and here.

My question : what about the 2D version ? if the houses are not on a line, but on a 2D grid ? Like for the 1D version, if you rob one house, you cannot rob the adjacent ones (see the following pattern) :

x x x
x o x
x x x

Can DP be used to solve that ? Is it even linearly solvable ?

# Answer
I found a question which is similar to the 2D version of house robber

If you observe carefully we can calculate the answer for each row independently and that leads us to our solution.

Here is my solution for it

```
class Solution {
    public int solve(int[][] matrix) {
        int N = matrix.length;
        if(N == 0)
        return 0;
        int[] arr = new int[N];
        for(int i = 0; i < N; i++)
        arr[i] = DP(matrix[i]);
        int ans = DP(arr);
        return ans;
    }

    public int DP(int[] arr) {
        int[] dp = new int[arr.length + 1];
        dp[0] = 0;
        dp[1] = arr[0];
        for(int i = 1; i < arr.length; i++) {
            dp[i + 1] = Math.max(dp[i],dp[i - 1] + arr[i]);
        }
        return dp[arr.length];
    }
}

```
> -1 votes

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


title: M + N log N running time for Dijkstra

text:
# Question
Title: M + N log N running time for Dijkstra
I'm taking the Design and Algorithms Part -II course in Coursera by professor Tim Roughgarden. In one of the classes, he mentioned that the running time for Dijkstra is $O(m \log n )$ using the heap data structure where $m$ is the number of edges and $n$ is the number of vertices. Also, he mentioned that using an exotic type of heap data structure the running time can be improved to $O(m + n \log n)$. I googled and couldn't find any relevant answers. It would be much helpful to know such data structures as its running time would be blazingly fast. Can anybody help?

# Answer
> 0 votes
Thanks to @nirshahar for pointing out the data structure is Fibonacci heap with a worst case running time of *O(a + b log n)* where a = number of inserts, b = number of deletions, n = maximum size of the heap. For Dijkstra's algorithm for shortest path we have to insert M number of edges initially followed by n number of deletions in each iteration. Hence it worst case is *O(m + n log m)*. In worst case for a dense graph m = n^2. Thus the worst case running time is transformed to O(m + n log n).

---
Tags: data-structures, shortest-path, heaps, dijkstras-algorithm
---