title: Prove a lower bound

text:
# Question
Title: Prove a lower bound
> Prove: $n^{5}-3n^{4}+\log\left(n^{10}\right)∈\ Ω\left(n^{5}\right)$.

I always get stuck in these types of questions, where there is a $"-(xy^{z})"$ in the expression. Whenever I see the solutions for these type of questions, I can't identify a single method that works every time and it's frustrating. How do I approach these types of questions?

# Answer
### Definitions

I'm using the definition of big-omega from Wikipedia and making it more explicit:

$$\left\[ f(n) \in \Omega(g(n)) \right\] \\:\Longleftrightarrow\\: \left\[ \exists k \in \mathbb{R}^+, \exists n\_0 \in \mathbb{N}, \forall n \in \mathbb{N}, \left\[(n \> n\_0) \Rightarrow (f(n) \ge k \cdot g(n)) \right\] \right\]$$

In your statement you have $f(n) = n^5 - 3n^4 + \log(n^{10})$, and $g(n) = n^5$.

### Intuitions

As $n$ gets larger, $f(n)$ essentially behaves like $n^5$ (which matches $g(n)$). This is because both the $-3n^4$ and $\log(n^{10})$ terms grow more slowly (see big-O theory). So the value of $k$ to satisfy the big-omega definition should be somewhere around $1$.

We (probably) can't choose $k = 1$ because $n^5 - 3n^4 \< n^5$ for all $n \> 0$, which means $f(n) \< k \cdot g(n)$. We can disregard the $\log(n^{10})$ term because it grows slower than $-3n^4$. So we'll choose some $0 \< k \< 1$.

### Solution

Let's choose $k = \frac{1}{2}$. (Actually any $k$ slightly less than $1$ will also work.)

Solve for the break-even point of $n^5 - 3n^4 = k \cdot n^5$, and we get $n = 6$. Choose $n\_0 = 6$.

Now to confirm: Is it true that for all $n \> 6$, we have $n^5 - 3n^4 \ge \frac{1}{2} n^5$? Yes, because:

$n \> 6$ (left side of implication)
$\Rightarrow\\: n \cdot n^4 \> 6 \cdot n^4$ (multiply by $n^4$)
$\Rightarrow\\: n^5 \> 6n^4$ (simplify)
$\Rightarrow\\: \frac{1}{2} n^5 \> \frac{1}{2} 6n^4$ (multiply by $\frac{1}{2}$)
$\Rightarrow\\: \frac{1}{2} n^5 \> 3n^4$ (simplify)
$\Rightarrow\\: \frac{1}{2} n^5 - 3n^4 \> 3n^4 - 3n^4$ (subtract $3n^4$)
$\Rightarrow\\: \frac{1}{2} n^5 - 3n^4 \> 0$ (simplify)
$\Rightarrow\\: \frac{1}{2} n^5 - 3n^4 + \frac{1}{2} n^5 \> \frac{1}{2} n^5$ (subtract $\frac{1}{2} n^5$)
$\Rightarrow\\: n^5 - 3n^4 \> \frac{1}{2} n^5$ (simplify)
$\Rightarrow\\: n^5 - 3n^4 \ge \frac{1}{2} n^5$. (weaken inequality)

Finally, because for all $n \> 0$, we have $\log(n^{10}) \> 0$, therefore $n^5 - 3n^4 + \log(n^{10}) \> n^5 - 3n^4 \ge \frac{1}{2} n^5$.

### Formal proof

Let $k = \frac{1}{2} \in \mathbb{R}^+$.
Let $n\_0 = 6 \in \mathbb{N}$.
Let $n \in \mathbb{N}$ be arbitrary.
Assume $n \> n\_0$.
$\therefore n \> 6$.
$\therefore \log(n^{10}) \> 0$.
$\therefore \frac{1}{2} n^5 \> 3n^4$.
$\therefore n^5 - 3n^4 \> \frac{1}{2} n^5$.
$\therefore n^5 - 3n^4 + \log(n^{10}) \ge \frac{1}{2} n^5$.
$\therefore f(n) \ge k \cdot g(n)$.
$\therefore (n \> n\_0) \Rightarrow (f(n) \ge k \cdot g(n))$.
$\therefore \forall n \in \mathbb{N}, \left\[ (n \> n\_0) \Rightarrow (f(n) \ge k \cdot g(n)) \right\]$.
$\therefore \exists n\_0 \in \mathbb{N}, \forall n \in \mathbb{N}, \left\[ (n \> n\_0) \Rightarrow (f(n) \ge k \cdot g(n)) \right\]$.
$\therefore \exists k \in \mathbb{R}^+, \exists n\_0 \in \mathbb{N}, \forall n \in \mathbb{N}, \left\[ (n \> n\_0) \Rightarrow (f(n) \ge k \cdot g(n)) \right\]$.
$\therefore f(n) \in \Omega(g(n))$.
> 4 votes

# Answer
Let me suggest direct simple solution: definition of $\Omega$ contains $2$ bound variables $c$ and $N$. In simple cases, as is in OP, we can choose one and solve second from expression obtained from definition. Obviously for left side we need constant less then one, so taking, for example, $c=\frac{1}{10}$ we have $$n^{5}-3n^{4}+\log\left(n^{10}\right) \geqslant \frac{1}{10} n^{5}$$ which gives $$9n^{5} \geqslant 30n^{4}-10\log\left(n^{10}\right) $$ It is enough to find $N$ for inequality $9n^{5} \geqslant 30n^{4}$, which gives $N= \left\lceil \frac{30}{9} \right\rceil$.
> 6 votes

# Answer
Just apply the definition. So in this case, we must have that $\lim\_{n \to \infty} f(n) / g(n) \> 0$ in order for $f(n) = \Omega(g(n))$.

Let's plug in what you have and observe that

$$\lim\_{n \to \infty} \frac{n^{5}-3n^{4}+\log(n^{10})}{n^5} = 1 \> 0.$$

This completes the proof.
> 5 votes

# Answer
Here is a quick formal proof without limits. Choose $c=\frac{1}{4}$ and $n\_0=4$. For $n \ge n\_0$: $$ n^{5}-3n^{4}+\log n^{10} \> n^5 - 3n^{4} = n^4 \cdot (n-3) \ge n^4 \cdot \frac{n}{4} = \frac{n^5}{4} =c n^5, $$ where we used the inequality $n-3 \ge \frac{n}{4}$ or, equivalently, $\frac{3}{4}n \ge 3$.
> 1 votes

# Answer
With small $n$ Big $\Omega$ it is just about useless and it's the hidden constants, so we suppose $n\to \infty$. At this situation, the term $n^5$ dominate other terms, and we can conclude that $n^5=\Omega(n^5)$.

**Note that, if number of functions are constant ( in the below $k$ is constant) that has below form:** $$f\_1(n)+\dots+f\_k(n)$$ and suppose $f(n)$ is a term that dominate other:

$$f(n)=\max\\{f\_1(n),\dots,f\_k(n)\\}$$
> 0 votes

---
Tags: time-complexity, asymptotics, lower-bounds
---


title: Reduction from TSP to even TSP

text:
# Question
Title: Reduction from TSP to even TSP
I have a question from a test that I failed to pass, I failed to do the question.

**The question:**

Let's look at the problem of the even-length traveling agent. Given graph $G = (V,E)$ and a weight function on the arcs of the graph $W:E \rightarrow \mathbb{R} ^ {+}$ we would like to find an easier route (of the routes of even length) that passes through all the vertices of the graph and ends at the vertex where it started. We will be interested in the decisive version of the problem. That is, given a natural number $d$, we are asked: "Is there such an even-length route weighing ≤ $d$?"

**Formally:**

$ETSP = ${ $\left \langle G,w,d \right \rangle$ | There is a path of even length, which passes through all the vertices of G and ends at the point where it started and weighs ≤ $d$ }

Determine which of the following statements is correct:

1. The language is in P since a polynomial algorithm can be constructed bypassing all the neighbors at a distance of less than 6 from each vertex in G.
2. The language is in P, as a greedy polynomial algorithm can be constructed which will solve the problem. For each vertex, the algorithm will look at the neighbor with the minimum weight edge each time. This will ensure that the route that passes through all the vertices will be at a very small weight. Finally, he will check whether the length of the route is even and if not - he will start again.
3. $TSP \leq \_P ETSP$ can be reduced so the language is in NPC
4. The language is not in NP, since if there is no such route then we can not verify it.
5. None of the above claims are true.

I think 3 is the correct answer.

1. Does not make sense
2. A greedy algorithm does not help with such problems
3. That's the answer, in my opinion, I'm not sure
4. I think it's not true, you can check it in polynomial time, just go over the witness' solution and see that it is even in length

# Answer
Option 1 is odd. We don't know whether a polynomial algorithm can be constructed. The "passing all the neighbors at a distance of less than 6 from each vertex in $G$" is unclear. Any algorithm solving the TSP problem must visit **all** vertices. Therefore it must also visit all neighbors of each vertex and, in particular, all neighbors at distance less than $6$. If a polynomial-time algorithm exists, the second part of option 1, as I read it, is trivially satisfied.

Regarding option $2$. It is unclear what "will look at the neighbor with the minimum weight edge each time" means. In particular, what is meant by *look*? If the algorithm is just required to examine that neighbor in some way then this condition becomes trivial to satisfy (since the algorithm is still free to pick whatever tour) but we don't know if the language is in $P$. If the algorithm is required to build a tour by iteratively going from the current vertex to its closest neighbor, then this algorithm could even not produce a valid tour. If the algorithm goes to the closest **unvisted** neighbor, then it produces a tour but doesn't ensure that the length is even nor minimized.

Option 3 is true. Simply multiply all edge weights (and the target upper bound on the tour length) by $2$ (or any positive even constant). Notice that the language is in NP since a certificate is the tour itself.

Option $4$ and $5$ are false (this is implied by the fact that option 3 is true).
> 2 votes

---
Tags: complexity-theory, computability, reductions, np
---


# Question
Title: edge-coloring and vertex-coloring reduction problem
I study complexity and computation independently. I have a problem that I can not solve.

**That's the problem:**

> Edge-Coloring problem, we get as input graph G = (V, E) and natural number k and ask "Is there a coloration in arcs of G which uses at most k colors?". While painting vertices to two neighboring vertices must not have the same color, painting arcs to two neighboring arcs (i.e., having a common vertex) must not be The same color. That is, the language is: Edge-Coloring = {\<G,k\>|G can be arcuated by coloring using ≤ k colors} Let's look at reduction, Edge-Coloring $\leq \_p$ Vertex-Coloring According to the graph G = (V, E), built new vertices Group: $\widetilde{V}$ = {$x\_e | e \in E$} We will define a new edge between two vertices, $x\_{e\_1}$ and $x\_{e\_2}$, if there is a common vertex between edges $e\_1$ and $e\_2$. $\widetilde{E}$ = {$(x\_{e\_1},x\_{e\_2}) | e\_1 \cap e\_2 \neq \phi $} Finally we will define: $\widetilde{G}$ = ($\widetilde{V}$ , $\widetilde{E}$)

*The question has 2 parts, but they are related to each other, so I can not ask each question separately.*

Section A

We will mark the maximum degree (of all the vertices of G) in $\Delta$ . Which of the following is the closest bound (or barrier) to the maximum degree of $\widetilde{G}$

1. $\Delta $
2. 2$\Delta $ -2
3. $\Delta ^{2}$
4. |V|
5. none of the answers is correct.

*`I think the answer is 2, if there is a vertex in`* $G$, *`with degree`* $\Delta$. *`When doing a reduction to`* $\widetilde{G}$ *`each edge becomes a vertex, because an edge can be connected to 2 vertices, and these 2 vertices are connected to the other edges, so it makes sense. But I can not rule out the answer 3, because it has a bigger bound(or barrier) and I can not rule out it.`*

*`Answer 1 is incorrect, because in my opinion 2 is correct. Answer 4 is incorrect, but fails to explain it logically.`*

Section B

Recall that the maximum degree $D \leq | V | - 1$. Which of the following is the closest bound (or barrier) to the number of edges in $\widetilde{E}$

1. $| V | - 1$
2. $| E | - 1$
3. $|E| \cdot (| V | - 1)$
4. $|E|^{2} \cdot | V |$
5. none of the answers is correct.

*`I think the answer is 3. If in G there is a complete graph, that all the vertices are connected to all the other vertices, the degree of each vertex is`* $D = |V|-1$, *`so in`* $\widetilde{G}$ *`there will be up to`* $|V|-1$ *`for each vertex of G. The number of vertices in G is |E|, so the answer comes out 3. In my opinion`*

*`But I can not say why answer 4. is incorrect.`*

*The question was translated from Hebrew. So I have no source for the question. I have asked a similar question before, but there are other questions here, so I ask again*

# Answer
> 2 votes
Regarding the first part.

Answer 1 is incorrect. Consider the graph $G = (\\{1,2,3,4,5,6\\}, \\{(1,2), (1,3), (2,3), (3,4), (4, 5), (4,6) \\})$. The maximum degree of $G$ is $3$ but the degree of $x\_{(3,4)}$ in $\widetilde{G}$ is $4$.

Answer 2 is correct. Consider an edge $e=(u,v)$ of $G$. The number edges distinct from $e$ that are incident to $u$ (resp. $v$) is at most $\Delta-1$, therefore the degree of $x\_e$ in $\widetilde{G}$ is at most $2(\Delta-1)$.

Answers 3 is incorrect because the question asks for the tightest upper bound and, for $\Delta \ge 1$, $2\Delta -2 = 2(\Delta-1) \le \Delta(\Delta-1) \< \Delta^2$.

Answer $4$ is incorrect. Consider the graph $G = (\\{1,2,3,4,5\\}, \\{ (1,2), (1,3), (2,3), (4, 5), (4,1), (4,2), (4,3), (5,1), (5,2), (5,3) \\})$. Here $|V|=5$ but the degree of $x\_{(4,5)}$ in $\widetilde{G}$ is $6$.

Regarding the second part:

Answer 1 is incorrect, as shown by the second counterexample above.

Answer 2 is incorrect, as shown by the fist counterexample above (the degree of $x\_{(1,2)}$ is $2$, the degree of $x\_{(1,4)}$ is $4$, $x\_{(1,2)}$ and $x\_{(1,4)}$ are not neighbors, therefore the number of edge of $\widetilde{G}$ is at least $6$, but $|E|-1=5$).

Answer 3 immediately follows from part $1$. The sum of degrees is $\widetilde{G}$ is at most $|E|(2\Delta - 2)$. Since the number of edges is exactly half the sum of the degrees you get the desired bound.

Answer $4$ is not the tightest bound among the options given since, for graphs with at least one edge, $|E|^2 \cdot |V| \> |E|(V-1)$.

# Answer
> 2 votes
Let's check these in reverse order.

* Question B: your reasoning looks good as it demonstrates that both (1) and (2) are not strong enough. The choice (4) is a possible bound, but it's not as tight as it can be. Your example is extremal in a sense that you can't make the degrees any larger, meaning that your bound is, as the question asks, "closest possible".
* Question A: You are right that $2\Delta-2$ is the closest bound. Again, other bounds might also be possible, but they are not as tight.

---
Tags: graphs, data-structures, computability, reductions
---


# Question
Title: For any direct graph $G(V,E)$, there is always an iteration of DFS algorithm on $G$ so the result does not have any cross trees
I suspect that it is not true but I came across with the following statement:

> For any direct graph $G(V,E)$, there is always an iteration of DFS algorithm on $G$ so the result does not have any cross edges.

Is it possible to show an example to disprove it?

# Answer
Consider the following graph:

A possible DFS starting from $a$ visits the vertices in this order: $\langle a, b, c, d \rangle$ producing the cross-edge $(c,b)$.

A possible DFS starting from $b$ visits the vertices in this order: $\langle b, a, c, d \rangle$ producing the cross-edge $(d,c)$.

A possible DFS starting from $c$ visits the vertices in this order: $\langle c, a, b, d \rangle$ producing the cross-edge $(d,b)$.

A possible DFS starting from $d$ visits the vertices in this order: $\langle d, a, b, c \rangle$ producing the cross-edge $(c,b)$.
> 2 votes

---
Tags: algorithms, graphs, depth-first-search
---


# Question
Title: Reduction from language in P to another language in NP
I have a question I was unable to do, from a last test I had.

**This is the question:**

Will be $A \in NP$ Let $c \in P$ be a language so that there exists $C \leq \_pA$. Determine which of the following statements is correct:

1. $C \notin CoNP$
2. $A \in P$ if and only if $C \in P$
3. There is at least one case in which $A \in P$. In addition, there is at least one case in which $A \notin P$.
4. $A \cap C \in P$
5. None of the above claims are true

I can not understand what reduction helps at all, any problem with P can be reduced to NP.

1. I do not think there is any reference to complementary language at all, in my opinion not true.
2. It is not true, if A belongs to p then c must also belong, but in the opposite direction it is not true.
3. Do not know how to disqualify it, it is not clear to me how reduction can help here.
4. I think this is the correct answer, if C belongs to P then the cut between A and C also maybe belongs to P.
5. In my opinion maybe answer 4 is correct

I can not understand what the answer can be, and I can not understand what reduction can actually help, even without the reduction it is possible to know that p belongs to np

# Answer
> 2 votes
Alright, we are given a language $C \in \mathrm{P}$ and a language $A \in \mathrm{NP}$, and we are promised that $C \leq\_p A$. What can we conclude?

First a side remark: The reduction $C \leq\_p A$ tells us very little since we know $C \in \mathrm{P}$. The only extra information we get is that if $A$ is empty, then so is $C$, and if $A = \Sigma^\*$, then $C = \Sigma^\*$, too. And this is irrelevant for all of the questions you were asked.

1. Since $\mathrm{P} \subseteq \mathrm{coNP}$, it is definitely true that $C \in \mathrm{coNP}$.
2. We know that $C \in \mathrm{P}$, hence the claim here is that $A \in \mathrm{P}$. Since we are only told that $A \in \mathrm{NP}$; the truth of this point is equivalent to the $\mathrm{P} =? \mathrm{NP}$ question, meaning that noone knows whether this is true (but most of us think this is false).
3. Nothing we were told contradicts that $A \in \mathrm{P}$ could be true. But whether $A \notin \mathrm{P}$ could be true once more is just another way of asking if $\mathrm{P} =? \mathrm{NP}$.
4. As pointed out by nir shahar in the comments, we can't draw conclusions about $A \cap C$ beynd $A \cap C \in \mathrm{NP}$. But if $\mathrm{P} = \mathrm{NP}$, the answer here would indeed be *true*.

To summarize, if $\mathrm{P} = \mathrm{NP}$ the answers are false, true, false, true. If $\mathrm{P} \neq \mathrm{NP}$, the answers are false, false, true, false.

---
Tags: complexity-theory, time-complexity, computability, reductions, np
---


title: Time Complexity - Palindrome Partition

text:
# Question
Title: Time Complexity - Palindrome Partition
I am solving an interview practice question:

*Partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.*

My solution is as below, and was accepted.

```
def partition(self, s: str) -> List[List[str]]:

    ans = []

    def bt(w, curr):
        if not w:
            ans.append(curr)
        else:
            for l in range(1, len(w)+1):
                chunk = w[:l]
                if ''.join(reversed(chunk)) != chunk:
                    continue
                bt(w[l:], curr + [chunk])

    bt(s, [])
    return ans

```

The time complexity given in the solutions is O(N * 2^N) I do not understand that.

I understand that:

* there are 2^(N-1) possible partitions,
* in the worst case any partition yields palindromes,
* checking for palindrome is linear in the size of the input.

But I am struggling to estimate the amount of work done in the for loop. Why are we multiplying 2^N with just N? What about the linear amount of work done within the body of the loop?

Any insight/hints would be helpful. In conjunction with this, I am unable to write a recurrence relation ..

Thank you very much!!

# Answer
Lets look at the (worst-case) recurrence for **bt**:

$$ T(n) = \sum\_{l = 1}^{n} (O(l) + T(n-l)) $$

Here $n$ measures the length of the string passed to bt. The sum basically represents the complexity of the loop; for every $l$ you do a $O(l)$ compare operation and in the worst-case call **bt** with a string of length $n-l$. However we can simplify the above relation in a couple simple steps (using Gauss sum): $$ T(n) = \sum\_{l = 1}^{n} (O(l) + T(n-l)) = O(n^2) + \sum\_{l = 1}^{n} T(n-l) $$ We can simplify further (we now look at $T(n+1)$): $$ T(n+1) = O((n+1)^2) + \underbrace{\sum\_{l = 1}^{n+1} T(n+1-l)}\_{\text{index-shift}} \\ = O(n^2+n) + \sum\_{l = 0}^{n} T(n-l) \\ = O(n) + T(n) + \underbrace{O(n^2)+ \sum\_{l = 1}^{n} T(n-l)}\_{ = T(n)} = O(n) + 2T(n) $$ From the recurrence $T(n+1)= cn +2T(n)$ you can maybe already see that we get $O(n2^n)$. Quick proof by induction: Assume $T(n) \leq cn2^n$: $$ T(n+1) = cn + 2T(n) \leq cn + c2n2^n = cn + cn2^{n+1} \\ \leq c2^{n+1}+ cn2^{n+1} = c(n+1)2^{n+1}$$
> 0 votes

---
Tags: time-complexity, backtracking
---


title: Reduction with CoNP and CoNPC

text:
# Question
Title: Reduction with CoNP and CoNPC
I have a question I was unable to do, from a last test I had.

This is the question:

> Suppose that there is a language $A \neq \emptyset ,\sum{\_{}}^{\*}$ such that $A \in CoNP - CoNPC$.

> Determine which of the following statements is correct:

> 1. In this case it is possible to find a language $B$ such that $B \in CoNPC\cap P$, since it follows that $CoNPC\cap P \neq \emptyset $, and therefore $P=NP$.
> 2. The existence of the language $A \in CoNP - CoNPC$ assures us that there is at least one $B \in CoNP$ so that $B \nleq \_p A $, so if we assume in the negative that $B \in P$, we can have a contradiction to the non-existence of conversion $B \nleq \_p A $, because there can always be a conversion from a problem in $P$ to a $CoNP$ problem. That is, $B \in CoNP$ and also $B \notin P$, and therefore $P \neq CoNP$.
> 3. Since there is a language $A \in CoNP$ such that $A \notin CoNPC$ derives as $CoNP - CoNPC \neq \emptyset $, therefore any problem $B$ in $CoNP$ can be solved by converting to problem $C\in P$. That is, it follows that $CoNP \subseteq P $. The bride in the other direction we have already seen, so $P = CoNP$.
> 4. Nothing can be determined from the data regarding equality or inequality between $P$ and $NP$
> 5. None of the above claims are true.

In the question I am told that:

$A \neq \emptyset ,\sum{\_{}}^{\*}$ and $A \in CoNP - CoNPC$

And according to this you have to choose one of the 5 options.

I understood the question like this: A, it's some language, not empty. Which belongs only to CoNP.

The answer I think is correct is 2.

1. There is no connection between language B and language A, so it is disqualified.
2. True, B can also belong to CoNPC, and there can be no reduction from CoNPC to A.
3. Can't figure out that answer
4. It could also be true that they did not talk about it in question.
5. Disqualified maybe 2 or 4 are correct

I can not figure out if the answer is 2 or 4.

# Answer
> 2 votes
We start with the assumption that there is a non-trivial language $A$ which is in $\mathrm{coNP}$, but not $\mathrm{coNP}$-complete. We note that it is rather straight-forward to see that if $\mathrm{P} = \mathrm{coNP}$, then every non-trivial language in $\mathrm{coNP}$ is $\mathrm{coNP}$-complete. Conversely, Ladner's theorem states that if $\mathrm{P} \neq \mathrm{coNP}$, then there are even $\mathrm{coNP}$-intermediate languages, i.e. languages in $\mathrm{coNP}$ which are neither $\mathrm{coNP}$-complete nor in $\mathrm{P}$. (This is typically stated for $\mathrm{NP}$ rather than $\mathrm{coNP}$, but by symmetry that doesn't matter.

Thus, we conclude that the assumption we are starting with is equivalent to $\mathrm{P} \neq \mathrm{NP}$.

1. This is claiming that $\mathrm{P} = \mathrm{NP}$, and our assumption states the opposite.
2. I find the formulation a bit awkward, but this is true. Note that "$A$ is not $\mathrm{coNP}$-hard" is just saying that there is some language in $\mathrm{coNP}$ not reducible to it.
3. The *therefore* in this statement is a complete non-sequiture.
4. As explained above, the assumption made is equivalent to $\mathrm{P} \neq \mathrm{NP}$, so the claim is false.

# Answer
> 0 votes
It is 2 that is correct. Here is an alternative explanation:

Notice that any language in $P$ has to be $P$-complete. In addition to that, if $P=NP$ then $NPC=P$-complete. Combining both arguments implies that $NP=P=P\text{-complete}=NPC$. Therefore, if $NP\neq NPC$ then $P\neq NP$.

---
Tags: complexity-theory, computability, np-complete, reductions, np
---


# Question
Title: Difference between a regular and a non-regular language
Suppose $L\_1$ is a regular language and $L\_2$ a non-regular one, then:

is $L\_1\setminus L\_2$ REGULAR/NON REGULAR/BOTH OF THEM?

is $L\_2\setminus L\_1$ REGULAR/NON REGULAR/BOTH OF THEM?

# Answer
First, we know that, $L$ is a regular language if and only if its complement be regular language.

On the other hand, $$L\_1\setminus L\_2=L\_1\cap L\_2^c.$$

Suppose $\Sigma=\\{a,b\\}$, Let $L\_1=\Sigma^\*$ , and $L\_2=\Sigma^\*\setminus \\{a^nb^n\\}$, obviously, $L\_2$ isn't regular, so

$$L\_1\setminus L\_2=\\{a^nb^n\\} $$ consequently, $L\_1\setminus L\_2$ can be a non-regular.

Let $L\_1=\emptyset$, and $L\_2$ be any non-regular language, so

$$L\_1\setminus L\_2=\emptyset$$

consequently, $L\_1\setminus L\_2$ can be regular.

for the second proposition, let $L\_1=\emptyset$, and $L\_2$ be a non-regular language, so $L\_2\setminus L\_1$ is non-regular, and if we set $L\_1=\Sigma^\*$, and $L\_2$ be a non-regular language, then $L\_2\setminus L\_1=\emptyset$ that show us $L\_2\setminus L\_1$ can be regular.

**Note that, difference between two non-regular, regular languages can be regular or not.**
> 1 votes

# Answer
Be $\Sigma$ an alphabet, consider $L\_1=\Sigma^\*$ and $L\_2$ a non-regular language, then also its complement, i.e. $L\_1\setminus L\_2$, is non-regular (remember that the family of regular language is closed under complement). On the other hand, if $L\_1=\varnothing$ (which is regular), then $L\_1\setminus L\_2$ is regular even if $L\_2$ is not.

For $L\_2\setminus L\_1$, first consider $L\_1=\Sigma^\*$ and $L\_2$ any (non-regular) language, then $L\_2\setminus L\_1$ is regular. On the other hand, if $L\_1=\varnothing$ and $L\_2$ is a non-regular language, then $L\_2\setminus L\_1$ is non-regular.
> 0 votes

# Answer
$L\_1 - L\_2$ and $L\_2 - L\_1$ are both non regular since $L\_2$ cannot be decided by finite automata. Intuitively, to know whether a string is in $L\_2$ or not, we need something more powerful than a finite automata.
> -1 votes

---
Tags: formal-languages, regular-languages
---


# Question
Title: I can't get the commands? each of which includes $~\$~$ instead of $~\epsilon~$ of the pushdown automaton
The pushdown automaton is given as the below diagram.

What I know are as below.

$$ 1,0 ~\texttt{-\>}~ \epsilon\_{} ~~ \leftarrow~~ \text{As 1 is inputted then 0 will be popped from the stack} $$

$$ 0,1 ~\texttt{-\>}~ \epsilon\_{} ~~ \leftarrow~~ \text{As 0 is inputted then 1 will be popped from the stack} $$

$$ 0, \epsilon\_{} ~\texttt{-\>}~0 ~~ \leftarrow~~ \text{As 0 is inputted then 0 will be pushed into the stack(Nonexists in the above list)} $$

What I don't know are as below.

$$ 0, $ ~\texttt{-\>}~ 0 $ $$

$$ 1, $ ~\texttt{-\>}~ 1 $ $$

$$ 0,0 ~\texttt{-\>}~ 00 $$

$$ 1,1 ~\texttt{-\>}~ 11 $$

What are them?

# Answer
I could make this post of the answer because of comments of Hendrik Jan.

Thank you.

If we assume the input is given as $~ 111000 ~~~$,

The state is moved to $~ q\_{1} ~$ without before input since $~ \epsilon\_{} ~$ exists.

And after the arrival at $~ q\_{1} ~$,$ is pushed at bottom of the stack.

Nextly the procedures of 111000 begin.

At first "1" , the command $~ 1, \\\\$ ~ ~\texttt{-\>}~ 1~$ is done. Which command means that as 1 is inputted, and as a dollar exists at top of the stack, the dollar is replaced by 1 dollar.

This means that 1 is at the top-notch and the second depth element is a dollar.

Nextly we handle the second "1" of the input.

At this time , the command $~ 1,1 ~\texttt{-\>}~ 11 ~$ is done .

So if we assume the leftmost is top-notch and the rightmost takes the bottom of the stack,

Then newly the stack is seen as like below.

$$ 11\\\\$ ~~ \leftarrow~~ \text{1 is replaced by 11} $$

As 3rd operation is done ,

$$ 111\\\\$ ~~ \leftarrow~~ \text{leftmost(top notch) 1 is replaced by 11} $$

As of now, the remaining sequence is 000.

$$~ 0,1 ~\texttt{-\>}~ \epsilon\_{} ~~ \leftarrow~~ \text{This will be done triple times} ~$$

So the three "1" continues from leftmost in the stack,

So after the 3 operations are done, the stack is

$$ \\\\$ $$

After the processings of 111000 are done, then the above right command in the diagram is done and finally, the stack is the same as $~ \epsilon\_{} ~$
> 0 votes

---
Tags: automata, pushdown-automata
---


# Question
Title: Solving a recurrence relation involving square roots
> Give an asymptotic upper bound for $$T(n) = \sqrt{n}·T(\sqrt{n})+n+n/\log n. $$

How can I solve this recurrence relation, which involves square roots?

# Answer
Dividing both sides by $n$ then introducing $S(m):=\frac{T(2^n)}{2^n}$ yields:

$$S(m)=S(m/2)+1+\frac{1}{m}$$

It follows that: $$1\<S(m)-S(m/2)\leq 2$$ And further: $$\forall k, 1\<S(m/2^k)-S(m/2^{k+1})\leq 2$$ Now summing for $k=1\dots \log(m)-1$ gives us: $$S(m)=\Theta(\log(m))$$ And so: $$T(n)=\Theta(n\cdot\log\log n)$$
> 1 votes

# Answer
Suppose $n=2^k$. Because of $lim\_{n\to \infty}\frac{n}{\frac{n}{\log n}}=\infty$, you can rewrite $T(n)$ as follow:

$$T(n)=\sqrt{n}T(\sqrt{n})+\mathcal{O}(n).$$ By substitution method: $$T(n)=\sqrt{n}T\left(\sqrt{n}\right)+\mathcal{O}(n)$$ $$=\sqrt{n}\left(\sqrt{\sqrt{n}}T\left(\sqrt{\sqrt{n}}\right)+\sqrt{n}\right)+n$$ $$\dots$$ $$=n^{\frac{1}{2}+\frac{1}{4}+\dots+\frac{1}{2^k}}T\left(2^{\frac{1}{2^k}}\right)+\underbrace{n+\dots+n}\_{k \text{ times}}$$

So we should find the value of $k$ : $$2^{\frac{1}{2^k}}=1$$ $$\implies k=\log\log n$$ Therefore $$T(n)=n^{1-2^{-\log\log n}}T(1)+n\log\log n$$ $$=\Theta(n\log\log n).$$
> 0 votes

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: What will you do if multiple users access your application at the same time?
I'm an experienced Software Engineer but very weak in concurrency because of no prior experience in that. I've been interviewing with several companies in which I was asked similar kinds of questions as given below:

1. If you are designing a fantasy sports application in which there's a contest that can handle only 100 users. If 99 users are already registered for the contest and multiple users hit the PARTICIPATE button at the same time to become the 100th user, then how will you handle this in your application?
2. If you are designing a chess game, where multiple users are selecting the users of the same level of competence to play with them. Then suppose at the same time, users A and B choose user C (to play with) at the same time, then how will you handle this?

I usually answer this by saying that I'll use synchronized block in Java or on the Database side, I'll use the Locking concept. But I'm not sure of either of them. So, can anyone tell here how do you answer such questions? Should one answer this in terms of Java Multithreading or DBMS or both? Please can anyone also tell me any resources to understand the theory to answer such types of questions or any website or YouTube channel where solutions are given to these kinds of questions?

# Answer
my answer to the first problem would go like this:

From a logical perspective, it depends on the actual purpose of the application, however, we should at least ensure safety and liveness, therefore some locking algorithms are appropriate. Since the contest could be very serious (legal consequences in case of booking failure) I would opt for a mutual exclusive (ensures safety, namely at most one user will book as the 100th competitor), starvation free (ensures everybody will eventually access the lock), fifo (ensures that users can not overcome each other at booking time and they are served in the order they show up) lock.

From a programming perspective, I would first ask about precise requirements because mentioned use-cases seem to be easily manageable through simple and famous (but not scalable) locking algorithms. The Bakery Lock (Wikipage) satisfies all the properties I mentioned earlier but comes with several disadvantages, namely, it must read as many variables as participant processes. Its implementation in Java should be easy and there are several examples on the Internet.

The philosophy of my answer is the one employed in "The garbage collection handbook", namely: safety properties must be honored but your design decisions should depend on use-cases; provided hard requirements are to be met more sophisticated algorithms are to be employed.

If you are interested in learning more about concurrency there exist several books about it, I name just two: The Art of Multiprocessor Programming (chapters from 1 to 10 should suffice), by Shavit & Herlihy Distributed Algorithms (chapter 10 is about locking), by Nancy Lynch

Regards,
> 1 votes

---
Tags: concurrency, synchronization, semaphore, database-concurrency
---


title: Proving upper/lower bound

text:
# Question
Title: Proving upper/lower bound
> $f (n) = Θ(f (n/2))$

The counter example in the solutions was $f(n)=\sqrt{n}$.

But then we get for every $n\ge n\_{0}$

$\sqrt{n}\le c\_{0}\sqrt{\frac{n}{2}}\ \ -\>\ \ n\le c\_{0}^{2}\cdot\frac{n}{2}\ \ \ -\>\ \ 2n\le c\_{0}^{2}\cdot n\ \ -\>\ 2\le c\_{0}^{2}$

and I don't see a problem with that, as we can choose $c\_{0}=2$. Same with the omega definition. So what am I missing?

# Answer
Your counter-example isn't true.

Let $f(n)=2^n$, we see that $$f(\frac{n}{2})=2^\frac{n}{2}=\sqrt{2}^n.$$

As a result we show that $f(n)\neq\Theta(f(\frac{n}{2}))$ $$\lim\_{n\to \infty}\frac{f(n)}{f(\frac{n}{2})}=\frac{2^n}{\sqrt{2}^n}$$ $$=\frac{2}{\sqrt{2}}\times\dots\times\frac{2}{\sqrt{2}}$$ $$=\frac{\sqrt{2}}{1}\times\dots\times\frac{\sqrt{2}}{1}$$ $$=\frac{\sqrt{2}^n}{1}=\infty.$$ So, $f(n)\neq\Theta(f(\frac{n}{2}))$.
> 1 votes

---
Tags: time-complexity, asymptotics, correctness-proof
---


# Question
Title: How to solve modulo math equation in RSA algorithm?
$(3 \cdot d) \mod 8=1$. I know the answer is $d=3$ by common sense. But what is the mathematical approach to solve this problem? How do I solve this mathematically?

How do we get this value of 125^107 mod 187=5?

# Answer
> 1 votes
Use Extended gcd algorithm. The time complexity is $O(\log n)$.

# Answer
> 0 votes
We know that $gcd(3,8)=1$ since $3$ is a prime, and therefore $3$ has one and *unique* inverse under multiplication modulo $8$.

As you have seen, its not hard to guess that $3$ is its own inverse, that is, $x=3$ is the solution for the equation: $$3x\equiv1 \mod 8$$

Since there is only one and unique solution, we know that $3$ is the only solution.

Its important to note that "guessing" a solution and verifying it, is a totally fine thing to do, and it is totally "mathematical".

---
Tags: computer-networks
---


title: Is there a TM that halts iff P = NP?

text:
# Question
Title: Is there a TM that halts iff P = NP?
Is there a Turing machine that halts iff P = NP? There are Turing machines that halt iff the Goldbach conjecture is false, or the Riemann hypothesis is false. How about the P vs. NP question? This is an expressiveness question, but I have not seen such a construction before.

Update: There are competitions to construct the smallest TM that halts iff Goldbach is false. The current record is 27 states. Basically the TM puts successively larger even numbers in unary on the tape and checks if there is a cut dividing the unary even number into two primes. This is the spirit that I intended; my question is not about existential, nonconstructive arguments or provability from ZFC.

# Answer
You are asking whether there is a concrete TM for which we know that its halting is equivalent to $\mathrm{P} = \mathrm{NP}$. An alternative phrasing is whether we know $\mathrm{P} = \mathrm{NP}$ to be equivalent to specific $\Sigma\_1$-statement. The answer is **no**.

We know that $\mathrm{P} = \mathrm{NP}$ is equivalent to "There exists a polynomial-time algorithm that solves SAT." So we might hope to obtain our hypothetical TM by searching through all possible polytime algorithms and halt if we find one that solves SAT. The problem is that we can not decide whether a given polytime algorithm solves SAT or not.

So to see the actual complexity of $\mathrm{P} = \mathrm{NP}$ we should phrase it as:

"There exists ($\exists$) a polytime algorithm $A$ such that for all ($\forall$) propositional formulas $\phi$ the algorithm $A$ correctly determines whether or not $\phi$ is satisfiable".

Hence, $\mathrm{P} = \mathrm{NP}$ is $\Sigma\_2$, and we can easily built a TM that will definitely run forever, and output finitely many $1$'s iff $\mathrm{P} = \mathrm{NP}$. Maybe someone will prove $\mathrm{P} = \mathrm{NP}$ to be equivalent to a concrete $\Sigma\_1$ or $\Pi\_1$ question before it is resolved. but to date no such result is known.
> 3 votes

# Answer
The answer to your question is formally "yes". This is because one possible Turing machine that halts iff P=NP is either (i) a Turning machine that always halts or (ii) a Turing machine that never halts (regardless of its input).

However, the following argument might be closer in spirit to what you are asking: Assume that $P=NP$ is not independent from the axioms you are (implicitly) using. Since proofs are enumerable you could build a Turing machine $T$ that iterates over all "candidate proofs" that P=NP. When a candidate proof $\pi$ is considered, $T$ checks whether $\pi$ is an anctual proof. If it is, $T$ halts immediately. If it isn't, $T$ continues with the next candidate proof. It follows that $T$ halts iff $P=NP$.
> 1 votes

# Answer
1 The problem is somewhat more complicated in spirit to Goldbach and similar problems (FLT, ZFC): You certainly can invent a TM that solves instances of 3-SAT (in exp time) as you can check instances of Goldbach.

2 You want to know however whether there is a faster TM and which is the fastest one. Since there are faster and faster machines (eg by recoding) none of which are subexponential though, this does not constitute proof of N=NP, neither does it yield a lower bound on time complexity.

3 Hence, what you can do is

(a) fix an encoding of 3-SAT formulae.

(b) test for satisfiability (in exp time)

(c) run "all" TMs (ie all algorithms, all proofs) against larger and larger instances of 3-SAT. these

* (i) will provide wrong answers: discard
* (ii) will provide correct answers: check time behaviour for larger and larger instances
* (iii) will not halt sometimes, the (in)famous halting problem: keep in list and simulate further (will eventually drop out by exceeding any time bound).

From (ii) you obtain upper bounds on the timing behaviour. Discard any machines with $T(d) \> n\cdot |d|^n$, $d$ the description of the 3-SAT instance, n a growing parameter.

Ingeniously mix TMs, 3-SAT instances, time bound parameter values $n$ ... Eventually you have no machine left for a given fixed $n$, with $n\to\infty$ discarding P=NP, or else some TM (require $n \> |TM|$ or so) is the solution for all say $|d| \leq n^{n^n}$, P$\doteq$NP. You are famous!

(Well, almost: you will have a machine that correctly decides 3-Sat in poly time for some (not so) small instances, $|d| \leq n^{n^n}$ ... and $|TM|$ far smaller - it is then up to you to mathematically prove the correctness (and speed) for any $|d|$. But you have an algorithm to begin with.)

Same problem here as with Goldbach: Showing P=NP is OK (like a counterexample to Goldbach), disproving it requires "infinite time" - you actually never disprove. You have an $P\neq NP$-checker (for a finite, but arbitrary large, set of instances!) as you have a Goldbach-checker (which is what you are asking for in your question).
> -1 votes

---
Tags: turing-machines, p-vs-np
---


# Question
Title: Is there a good algorithm to divide two integers without using division directly?
**Problem.** Given positive integers $a$ and $b$, obtain $\frac{a}{b}$ without using division ($/$) directly, though addition ($+$), subtraction ($-$), multiplication ($\times$) and bit-shifts ($\gg$ and $\ll$) are allowed.

---

Is there a good algorithm to solve the aforementioned problem? This algorithm does not have to be very accurate and $4$ decimal places would be good enough, e.g.,

$$\frac{222}{103} \approx 2.1553$$

Could anyone please give some advice or references?

# Answer
Newton's method is pretty good for this. Specifically, a good strategy is to first calculate an approximation $x \approx \dfrac{1}{b}$ so that $ax$ is then a good approximation for $\dfrac{a}{b}$. To do this, we will use Newton's method to approximate a root of the function $f(x) = \dfrac{1}{x} - b$.

Newton's method asks us to recursively calculate approximations $x\_n$ given by the formula $$x\_{n+1} = x\_n - \frac{f(x\_n)}{f'(x\_n)}$$ A priori, this looks like using division but since $f'(x) = \dfrac{-1}{x^2}$, the formula boils down to $$x\_{n+1} = x\_n + x\_n^2\left(\frac{1}{x\_n} - b\right) = x\_n + (x\_n - bx\_n^2) = (2 - bx\_n)x\_n,\tag{$\*$}$$ which only involves addition and multiplication.

In order to ensure good convergence of this method, it helps to have $b$ very close to $1$. Of course, there are very few integers that are close to $1$. However, if $b$ is an $n$-bit integer then $b\_0 = \dfrac{b}{2^{n-1}}$ is between $1$ and $2$. Since the denominator is a power of $2$ this is really just a bit shift and not a division per se. Incorporating this in the formula ($\*$) we obtain the iteration $$ x\_{n+1} = (2 - b\_0x\_n)x\_n = \left(2 - \frac{bx\_n}{2^{n-1}}\right)x\_n = \frac{(2^n - bx\_n)x\_n}{2^{n-1}} \tag{$\dagger$}$$ which still involves no division. Note that this gives a method for approximating $1/b\_0$ but we can recover a good approximation to $\dfrac{1}{b} = \dfrac{1/b\_0}{2^{n-1}}$ by shifting.

Further analysis shows that, starting with $x\_0 = 0.75$, the absolute error $\varepsilon\_n = \left|x\_n - \dfrac{2^{n-1}}{b}\right|$ for $(\dagger)$ satisfies $\varepsilon\_{n+1} \leq \varepsilon\_n^2$. So the number of correct bits doubles at each step!

Let's illustrate by approximating $22/7$. Then $n=3$ and $b\_0 = 7/4 = 1.75$. Then $(\dagger)$ gives the approximations $$\begin{aligned} x\_0 &= 0.750\\,000\\,000 \\ x\_1 &= 0.515\\,625\\,000 \\ x\_2 &= 0.565\\,979\\,004 \\ x\_3 &= 0.571\\,376\\,600 \\ x\_4 &= 0.571\\,428\\,567 \\ x\_5 &= 0.571\\,428\\,571 \\ \end{aligned}$$ All the digits shown for $x\_5$ are exact for $$ \frac{1}{b\_0} = \frac{4}{7} = 0.571\\,428\\,571\\,428\\,571\\,428\\,571\\,428\ldots $$ Thus $$ \frac{22x\_5}{4} = 3.142\\,857\\,141 $$ is a good approximation to $$ \frac{22}{7} = 3.142\\,857\\,142\\,857\\,142\\,857\\,142\\,857\ldots $$
> 5 votes

# Answer
There certainly are division algorithms around, check e.g. Knuth's "Seminumerical Algorithms" or the book describing how libtommath works (this library was written more to explain how to do things than for utmost speed).

With today's machines, where the speed is more limited by memory access than computation as such, brilliant hacks like the fast inverse square root are (fortunately) not in much demand anymore.
> 2 votes

---
Tags: algorithms, reference-request, arithmetic
---


title: Adding Links to Reduce Diameter

text:
# Question
Title: Adding Links to Reduce Diameter
Given an unweighted graph $G$, the problem is to add links to the graph with total minimum cost such that the diameter of the graph becomes at most a constant $k$? The cost of adding a link $(u,v)$ is the shortest path length between $u$ and $v$ in $G$.

Has the above problem been looked at? Is it NP-complete?

# Answer
> 3 votes
This paper seems closely related. The authors study the same problem you define with the exception that edge costs are uniform and do not depend on the distance of the endpoints. This version of the problem is NP-hard.

The paper provides references to variants of the problem, some involving costs and lengths. Perhaps you can see if one of the NP-hardness proofs can be easily adapted to your case.

# Answer
> 0 votes
Thanks. The earlier paper addresses pretty much the asked problem.

---
Tags: graphs, path
---


# Question
Title: What is wrong with this argument that if A is NP Complete, but B is in P, then A\B is NP Complete and B\A is NP Complete as well?
The following seems to me to be relevant to this question, but to me is an interesting exercise, especially since I have not formally worked with complexity before, but I want to learn more:

Suppose that A is NP-Complete, but B is in P. I claim that A\B is NP-Complete and B\A is NP-Complete as well. To see this, assume first that A\B is in P, and let X and Y be polynomial-time algorithms for B and for A\B, respectively. "Concatenating" X and Y as follows yields an algorithm Z for A:

Given L, test L using X; if X outputs "yes", test using Y; if Y yields "yes", output "no" and stop; if X yields "no", output "no" and stop; output "yes" otherwise and stop.

This algorithm Z runs in polynomial time, because if the (polynomial time) complexity exponent of X is k and the (polynomial time) complexity exponent of Y is n, then this algorithm clearly has (polynomial time) complexity exponent m=max(k,n). This would provide proof that P=NP, so A\B is NP-Complete.

Now suppose that B\A is in P. This time, let Y' be a polynomial-time algorithm for B\A and let X be as above. We construct an algorithm Z' for A, as follows:

Given L, test L using X; if X outputs "yes", test using Y'; if Y yields "no", output "yes" and stop; if X yields "no", test using Y'; if Y yields "no", output "yes" and stop; output "no" otherwise and stop.

This yields a polynomial-time algorithm for A, and so again, this would entail that P=NP, so B\A also is NP-Complete.

+++++++++End of Example++++++++++++

While I don't see anything wrong with the above at the moment, perhaps I have a mistake or complexity miscalculation? ...because for a while, as I was writing the second algorithm, I began to think it was odd and perhaps impossible that I can be right about B\A also being NP-Complete...

As I said, I'm somewhat new to this area, so feedback would be appreciated.

# Answer
> 1 votes
Let $C$ be any language in $NP \setminus \\{ \emptyset \\}$. Notice that such a $C$ exists (e.g., $C = \Sigma^\*$).

The claim "if $A$ is $NP$-Complete and $B$ is in $P$ then $A \setminus B$ is $NP$-complete" is false (regardless of whether $P=NP$). To see this pick $B=\Sigma^\*$. Then $A \setminus B = \emptyset$. Since there is no polynomial-time reduction from $C$ to $A \setminus B $, we know that $A \setminus B$ cannot be $NP$-hard and hence cannot be $NP$-complete.

Substituting $B=\Sigma^\*$ in your argument, you obtain an algorithm $Z$ that accepts $\Sigma^\*$, but $\Sigma^\* \neq A$ (since $A$ is $NP$-complete). This shows that your claim that $Z$ is an algorithm for $A$ is wrong.

The claim "if $A$ is $NP$-Complete and $B$ is in $P$ then $B \setminus A$ is $NP$-complete" is also false (regardless of whether $P=NP$). To see this simply pick $B = \emptyset$. Since there is no polynomial-time reduction from $C$ to $B \setminus A$ we know that $B \setminus A$ cannot be $NP$-hard and hence cannot be $NP$-complete.

Substituting $B=\emptyset$ in your argument, you obtain an algorithm $Z'$ that accepts $\Sigma^\*$, hence $Z'$ is not an algorithm for $A \neq \Sigma^\*$.

Another logical error that you have in your proof is assuming that the complement of "$A \setminus B$ (resp. $B \setminus A$) is in $P$" is "$A \setminus B$ (resp. $B \setminus A$) is $NP$-complete". If $P \neq NP$ then there are problems in $NP \setminus P$ that are not $NP$-complete. See Ladner's theorem and the class $NP$-Intermediate.

# Answer
> 1 votes
Take $B=\Sigma^\*$. Obviously, $A\setminus B=\emptyset$ is not NP-complete. I'm not sure how concatenation has anything to do with set subtraction, but obviously, concatenating $B=\Sigma^\*$ to $A\setminus B=\emptyset$ won't yield $A$ back, since $\Sigma^\* \emptyset=\emptyset$ as $\emptyset$ doesn't contain any words.

# Answer
> 1 votes
Your algorithm $Z$ doesn't decide $A$. If the input is in both $A$ and $B$, then it returns "no" even though the correct answer is "yes." The error can't be fixed, since it's generally impossible to deduce whether an input is in $A$ if you only know its membership status in $B$ and $A \setminus B$.

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


# Question
Title: Need the type of time complexity and its formula
If the complexity of my problem is $O(f\_n(n))$ begins at $n =4$ and increases in this sequence:

> At
>
> $n = 4$ the number of operations = $(n - 2)$,
>
> $n = 5$ the number of operations = $((n - 2) (n-2)(n-3)/2)$
>
> $n = 6$ the number of operations = $((n - 2) (n-2)(n-3) (n-3)(n-4)/4))$
>
> $n = 7$ the number of operations = $((n-2) (n-2)(n-3) (n-3)(n-4)(n-4)(n-5)/8)$

> $n = 8$ the number of operations = $((n-2) (n-2)(n-3) (n-3)(n-4)(n-4)(n-5)(n-5)(n-6)/16 )$ … etc.

1. How to formulate the $f\_n(n)$ for all $n$?
2. What is the type of its time complexity?

# Answer
**1.)**

If we look at $n=8$ then we see: $$\frac{1}{2^4}\times\left((n-6)(n-5)(n-4)(n-3)(n-2)\right)\times \left((n-5)(n-4)(n-3)(n-2)\right)$$ $$=\frac{((n-2)!)^2}{2^5}.$$

Therefore we can formulate $f\_n(n)$ as follow:

$$f\_n(n)=\frac{n-(n-2)}{2^{n-4}}\times \prod\_{i=3}^{n-2}i^2$$ $$=\frac{n-(n-2)}{2^{n-4}}\times \prod\_{i=3}^{n-2}i\times \prod\_{i=3}^{n-2}i$$ $$=\frac{2}{2^{n-4}}\times \frac{(n-2)!}{2}\times\frac{(n-2)!}{2}$$ $$=\frac{\left((n-2)!\right)^2}{2^{n-3}}.$$ So we find a closed formula for $f\_n(n)$.

**2.)**

Let $T(n)$ be the time complexity of computing $f\_n(n)$: $$T(n)=\Theta\left(\frac{\left((n-2)!\right)^2}{2^{n-3}}\right).$$ That you can estimate it by sterling's approximation.
> 0 votes

# Answer
It seems that: $$ f(n) = \left( 2\prod\_{i=3}^{n-2} i^2 \right) \cdot \frac{1}{2^{n-4}} = \frac{1}{2^{n-5}} \cdot \frac{1}{2^2} \cdot\prod\_{i=1}^{n-2}i^2 = \frac{1}{2^{n-3}} \cdot \left( \prod\_{i=1}^{n-2}i \right)^2 = 2^{3-n} ((n-2)!)^2. $$

This time complexity is superexponential. Indeed, using Stirling's approximation: $$ 2^{3-n} ((n-2)!)^2 \sim 2^{3-n} \cdot 2\pi n \left( \frac{n-2}{e} \right)^{2(n-2)} = \Theta\left(\left(\frac{n}{\sqrt{2} \\; e}\right)^{2(n-2)}\right). $$
> 2 votes

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


# Question
Title: Is ROM primary memory or secondary memory?
According to this picture ROM is classified under Main Memory , but isn’t ROM a secondary storage because it’s external and non volatile ? Any clarification with reference links will be highly appreciated. Thank you.

# Answer
The distinction between primary and secondary storage relies on several joint characteristics which the prototypical examples – RAM and hard drives – satisfy:

* **Primary storage** can be accessed directly by the CPU. Access is fast. Data is volatile – it is lost when power is turned off.
* **Secondary storage** cannot be accessed directly by the CPU. Access is slow. Data is non-volatile – it is retained even when power is turned off.
* **Tertiary storage** is similar to secondary storage, but can only be accessed via a network device. Access is even slower.

Where does ROM fall into this classification? The typical usage of ROM in computing (according to Wikipedia, now falling out of use), is for booting. When the computer is started, the CPU is directed to start running from some address, which is memory mapped to read-only memory\* containing instructions for booting the system. This kind of memory satisfies the first two properties of primary storage listed above, but not the third property.

(In reality, ROM can be writable – say it is really an EPROM – and sometimes it is really battery-backed RAM.)

Complicating the picture, some I/O devices are memory mapped, and so in this sense can be accessed directly by the CPU. This is (or at least, used to be) common for video. Does video memory count as primary storage or as secondary storage?

What these examples show is that the classification has its limits. The purpose of such classifications is to help us conceptualize how computers work. They shouldn't be taken too seriously – they don't apply in a clean way to all possible situations.
> 2 votes

# Answer
The terms “primary memory” and “secondary memory” are intended to distinguish between memory that is directly accessible from the main processor and memory that isn't. The basic idea is that the processor can read and write directly to primary memory. On the other hand, to access the contents of secondary memory, it needs to copy the content into primary memory and arrange for a data transfer, or to use peripheral input-output instructions rather than memory load-store instructions.

This is not a hard-and-fast distinction and there are a lot of ambiguous cases. Most types of memory (RAM, ROM, Flash, EEPROM, …) can either be primary or secondary, addressable or not, depending on the hardware architecture. Classifying memory like this is pointless, and it's wrong unless you're talking about a specific architecture (e.g. a PC's main processor, or a particular family of microcontrollers, etc.).

ROM and EPROM are non-volatile by definition. They aren't necessarily external: many chips contain a small amount of ROM. (E)EPROM and flash are more often external because the erasure process generates heat which is harder to dissipate if the memory is part of a multi-function chip – an engineering concern, not a scientific distinction. ROM is often primary memory because that's where the boot code is stored, and accessing secondary memory requires some code to run, so that can't be done until the boot code has run.
> 2 votes

---
Tags: memory-hardware, storage
---


# Question
Title: Reduction from problem A to another problem B
I have a question from a test that I failed to pass, I failed to do the question.

The question:

Let A and B have two languages so that there is a reduction function f: $A\leq \_pB$. Suppose that $A \in NP$. We will mark the verification algorithm for A in $M\_A$. We will now provide a verification algorithm showing that $B \in NP$.

1. Given a possible input y to problem B, we will non-deterministically guess the x string.
2. If there is $f(x) \neq Y$

2.1. Reject y.

3. Otherwise

3.1. Run $M\_A(X)$ and return like it

You must prove / disprove his correctness by choosing the appropriate claim. Determine which of the following statements is correct.

1. The verification algorithm is incorrect because the function f is not necessarily surjective. Therefore there may be a situation where the input is possible y for problem B so that $y \in B$ does not exist x so that $f (x) = y$, then the above algorithm will reject it while it is supposed to receive
2. The verification algorithm is incorrect because the function f is not injective. This can be a situation where two different values $x\_1 , x\_2$ are sent to the same y, and then the verification algorithm does not know which one to choose
3. Although the verification algorithm is correct, it is not polynomial
4. The verification algorithm is polynomial and correct
5. None of the above claims are true

*`I did not understand why the algorithm could be wrong. The algorithm must be polynomial, because it is written that there is a polynomial reduction. In terms of correctness, I do not see where there can be a problem, there is a problem A that is reduced to another problem B, and in this way B can also be solved with the help of A.`*

*`I think the answer should be 4, but I'm not sure.`*

# Answer
> 2 votes
Intuitively $A \le\_p B$ means that a polynomial-time algorithm for $B$ can be used to solve $A$ in polynomial-time, not vice-versa.

That said $f$ is not required to be surjective, think for example of $A=\Sigma^\*$ and $B=\\{0,1\\}$. Suppose that $f(x) = 0$ (i.e., $f$ is the constant function). Simulate the algorithm with $y=1$ and notice that it will reject since there is no $x$ such that $f(x)=1$.

Moreover, the (non-deterministic) algorithm must run in polynomial time. While you know that $|f(x)| \le \textrm{poly}(|x|)$, no upper bound for $|x|$ can be given as a function of $|f(x)|$. To run in polynomial time, the algorithm must (non-deterministically) guess strings $x$ of length $|x| \le p(|y|)$, for some polynomial $p$. What if $x$ exists but $|x|\>p(|y|)$? In short, how do you know when to stop guessing $x$?

---
Tags: complexity-theory, computability, reductions, np
---


# Question
Title: In every DFS run on $G$, in every step of DFS, the $G_{\pi}$ is a forest
Studying for my finals. So I'm reading the "Introduction to Algorithms (Third Edition)" book. In the DFS section there is the following section:

> Depth-first search yields valuable information about the structure of a graph. Perhaps the most basic property of depth-first search is that the **predecessor subgraph $G\_{\pi}$ does indeed form a forest of trees**, since the structure of the depth-first trees exactly mirrors the structure of recursive calls of `DFS-VISIT`. That is, $u=v.\pi$ if and only if `DFS-VISIT(G,v)` was called during a search of $u$’s adjacency list. Additionally, vertex $v$ is a descendant of vertex $u$ in the depth-first forest if and only if $v$ is discovered during the time in which $u$ is gray.

I'm trying to prove the following statement for myself:

> In every DFS run on $G$, in every step of DFS, the $G\_{\pi}$ is a forest.

This question is coming from a booklet published for studding for the finals (without solutions).

I understand the logic behind why it true (with the help of the statements from the book). But I struggle of writing a "formal proof" which shows the correctness of it. Do I need to use induction to prove it (since I need to show it for *every step*). How to prove this statement formally?

For the completeness of the question, the $G\_\pi=(V,E\_\pi)$ is the following graph: $$ E\_\pi=\\{(\pi\[v\],v)\\,:\\,\pi\[v\]\neq NULL \wedge v\in V\\} $$

# Answer
Yes use induction. You will assume that $G\_\pi$ is a forest, and you want to prove that $G\_{\pi'}$ is also a forest, where $\pi'$ is $\pi$ after one step of the DFS algorithm.

The key point, is that a forest is a graph without cycles. So basically, you want to show that no new cycles where created in the last step. To prove this, you will want to have a statement similar to this:

Assume towards contradiction that $G\_{\pi'}$ contains a cycle. Hence, the new node $u'$ that was added to $G\_{\pi}$ in order to create $G\_{\pi'}$ must be a part of the new cycle (since $G\_{\pi}$ was a forest). Therefore, there must be some node $u\in G\_\pi$ such that $\pi(u)=u'$, but this is impossible since it would mean that $u'$ would have been already visited in $G\_{\pi}$, but this is impossible since $u'$ was visited only after $G\_{\pi}$ was constructed.
> 2 votes

---
Tags: algorithms, graphs, depth-first-search
---


# Question
Title: Sharing a requested secret number not knowing which
Alice has a list of secret numbers. Alice wants to give Bob the opportunity to choose one of her secret numbers, and then Alice has to share that specific secret number, but in such a way that Alice can’t know which secret number Bob got to know. Is this known to be possible?

# Answer
> 4 votes
This is known as the oblivious transfer problem. You can find about it online if you are looking for zero-knowledge interactive proofs for it.

---
Tags: number-theory, security, encryption
---


# Question
Title: Which of the following languages can be represented by regular expressions?
The set of all words contained in $\\{0,1\\}^\*$ that have an even number of 0’s and an odd number of 1’s.

I came to discover that it is possible but not sure how. Can anyone express it in a regular expression?

# Answer
> 1 votes
Yes, an easy approach to find a regular expression for mentioned language is:

First, find a regular expression for $$L\_{even}=\\{w\in \Sigma^\*\mid \hspace{6pt}\mid w\mid\_0=2k,k\geq 0\\}$$ $$=1^\*(01^\*01^\*)^\*$$ Next, find a regular expression for $$L\_{odd}=\\{w\in \Sigma^\*\mid\hspace{6pt} \mid w\mid\_1=2k+1,k\geq 0\\}.$$ $$=0^\*1(0^\*10^\*1)^\*0^\*.$$ Now let $L$ be a language that, contain even number of $0's$, and odd number of $1's$. Therefore $$L=L\_{odd}\cap L\_{even}.$$ So we can express $L$ as the following regular expression :

$$\left(1\cup 0(00\cup 11)^\*(01\cup 10)\right)\left((01\cup 10)(00\cup 11)^\*(01\cup 10)\cup (00\cup 11)\right)^\*.$$

---
Tags: formal-languages, regular-expressions
---


# Question
Title: Is doing BFS over transitive reduction of a directed acyclic graph equivalent to topological ordering of that graph?
I have a directed acyclic graph. Where each node is a task and each edge denotes a dependency.

I want a method to effectively parallelize these tasks. One way would be to topological sort them based on depth. Node a which has no precedents will have depth 0. For other nodes, depth will be the depth of precedent with the highest depth +1. Like in the answer provided in this stack exchange question. But here I am not sure if we can get the most amount of parallelization. Tasks in each depth can be run in parallel. But to start processing tasks in a particular depth. All tasks in previous depth should be completed.

Then I came across the idea of transitive reduction of a DAG.

Transitive reduction reduces extra edges such that the same reach-ability relation in the original graph is maintained. Does this mean that transitive reduction is implicitly topological sorted? Does doing bfs over a transitively reduced task graph and executing tasks as they come in the bfs order equivalent to topological order?. For the input graph and its transitive reduced version, they seem equivalent. I don't know if there are any cases I am missing. What I want is a way to parallelize a task graph with maximum throughput.

# Answer
Yes, using the approach you sketched based on topological sorting gives you the maximum throughput, assuming you have an unlimited number of processes (there is no limit on the number of tasks you can solve in parallel).
> 0 votes

---
Tags: graphs, parallel-computing, topological-ordering
---


title: Reduction between CLIQUE to SUBSET SUM

text:
# Question
Title: Reduction between CLIQUE to SUBSET SUM
I have a question from a test that I failed to pass, I failed to do the question.

The question is about the reduction between Clique and Subset Sum. I tried to find an explanation for this on the internet and in the books but could not find anything.

Recall the expression problems:

* $Clique(G, k)$ \- Is there graph G with clique of size ≥ k?
* $SubsetSum(B, T)$ \- Given a set of integers ⊆ ℤ and an integer T ⊆ ℤ, is it possible to find a subgroup ′ of such that the sum of subgroup ′ is equal to-?

We want to show that the problems are of the same degree of difficulty. That is, we see two reductions, in both directions.

*The question consists of two sections that are related to each other, so I can not ask each question separately.*

**section A:**

First we see a proposal for a reduction $Clique ≤\_P SubetSum$ . Given graph $G = (V,E)$ and number d the group is constructed: $A =\\{a\_v| v \in V\\}$. Also, we will define: $a\_v = deg (v)$. That is, for each vertex we create a new element whose size is the number of neighbors it has. Sent to SubsetSum problem the $f(G,k) = \left \langle A,d \right \rangle$

> Determine which of the following statements is correct:
>
> 1. The reduction is correct and polynomial.
> 2. Although the reduction is correct, it is not polynomial, in the case where there is a vertex with an exponential rank.
> 3. Although the reduction is polynomial, it is incorrect.
> 4. The reduction is incorrect and not polynomial.
> 5. None of the above claims are true.

I think the correct answer should be 1 or 3. The reduction is polynomial. Because for each vertex it is possible to add a maximum of all the other vertices, that is $| V | ^ 2$. But I do not know if it is a correct reduction, I tried to look for an answer to it on the Internet and found nothing.

1. The reduction is polynomial but I do not know if it is also correct.
2. This is not true
3. Not sure if the reduction is correct.
4. This is not true

**section B:**

We will now consider the $ ≤\_ $ reduction proposal. Given number group B and number T for the SubsetSum problem, a new graph G\* was constructed as to:

* For each $b\_i \in B$ element, $b\_i$ vertices $v\_{i,1}, \cdots , v\_{i,b\_i}$ are constructed. For example, $b\_2 = 5$ constructed the vertices $v\_{2,1}, v\_{2,2} , v\_{2,3}, v\_{2,4}, v\_{2,5} $.
* All these vertices are connected in the edges to each other.
* The collection of all vertices from all the $b\_i$ is V\*
* The collection of all edges is E\*

Sent to Clique problem the $f(B,T) = \left \langle G\*,T \right \rangle$

> Determine which of the following statements is correct:
>
> 1. The reduction is correct and polynomial.
> 2. Although the reduction is correct, it is not polynomial.
> 3. Although the reduction is polynomial, it is incorrect, for each member from B a clique is created on its own, but the cliques are not connected to each other.
> 4. The reduction is incorrect and not polynomial, for each member from B a clique is created on its own, but the cliques are not connected to each other.
> 5. None of the above claims are true.

I can not see how the reduction works and leads to a solution in Clique. In terms of runtime, I can not calculate it, it seems complex.

Maybe the correct answer is 4, but I'm not sure why, it just seems very complex.

# Answer
The reduction from $Clique \leq\_P SubsetSum$ is incorrect. Take a graph $G$ with four vertices $(v\_1, ..., v\_4)$, edges $(v\_1, v\_2), (v\_3, v\_4$) and let $d = 4$. Then $A = \\{1,1,1,1\\}$ (assuming $A$ is a multiset). Clearly there is a subset in $A$ whose sum is 4 but there is no clique of size 4 in $G$.

As for the reduction $SubsetSum \leq\_P Clique$, your description doesn't make a whole lot of sense. Which vertices are connected? All of them? Also, you just copied the output of the reduction from the first part, so it's not entirely clear what size of clique the reduction uses.

As far as I can tell, the reduction is performed in $O\left(\left(\sum\_{b\in B} b\right)^2\right)$. Note that we are considering numeric values from the input, but not the input length. The reduction is therefore pseudo-polynomial.
> 1 votes

# Answer
I think one of an important parts of reduction for languages like Clique and Subset-sum is the integer we have given next to the input. That is $k$ for Clique which tells us which size of the clique we are looking for and $d$ in Subset-sum that tells us the sum of a collection of numbers.

I have drawn little pictures for you to see how this works. For section A, you have an input like $\<G,k\>$ and you have to map it to an output like $\<S, d\>$. If you have a graph as follows and $k=5$, then by the reduction that you have provided in section A, you have the collection $S$. It can be seen that we have some numbers whose sum is $5$ though we don't have a 5-clique in the graph. So the reduction is not correct since we wanted a reduction that $\<G,k\> \in \textbf{Clique} \iff \<S,d\> \in \textbf{Subset-sum}.$

And the reduction is indeed polynomial. You just need to look at every vertex to count its degree.

For section B, I did not get the reduction properly but I can think of it in two ways. The first way is to connect all vertices of a number $b\_i$ of the collection only. The second way is to connect all vertices of all $b\_i$. In the first way for the set $S=\\{2,2\\}$ we have a graph with two unconnected parts (The black edges only). In the second way, we have a full connected graph (both gray and black edges). In both of these ways, you do not have a correct reduction since in the first way you have $2+2 = 4$ and you do not have a 4-clique graph. In the second way, you do not have numbers that their sum is $3$ but you do have a 3-clique.

And for the complexity of this reduction, I have the same opinion as @idmean described in his answer.
> 1 votes

---
Tags: complexity-theory, graphs, computability, reductions, np
---


title: What makes a computer program modular?

text:
# Question
Title: What makes a computer program modular?
Consider:

* Constants and variables
* If-then-else-elseif statements
* Procedures and loops
* The very fact that a program is comprised of two or more files (instead just from one large file)

Each one of these features indicates "modularity" but what really makes a program modular by any rigorous standard of computer science (if there is one)?

# Answer
> 1 votes
Barbara Liskov has done research in the area of modularity:

> * A program is a collection of modules
> * Each module has an interface, described by a specification
>     + A module’s implementation is correct if it meets the specification
>     + A using module depends only on the specification

Modules provide the advantage of:

> * Local reasoning
> * Modifiability
> * Independent development

So modules is what make a program modular. You can identify modules by finding units of code that fulfill the above criteria.

For instance, a sort function that sorts an array is a module. The sort function has a clear specification (that can be stated formally easily). You should be able to shows its correctness or develop and modify it independently of the rest of the program and only by considering that specification.

If you have identified a module, you should also be able to replace the entire module with another implementation following the same specification without changing the semantics or correctness of your program.

However, not all programs feature equally good modularity. In the 70s the only type of modules were procedures and programs would often be hard to reason about.

According to Liskov this led to the development of Abstract Data Types:

> * Abstract data types
>     + A set of operations
>     + And a set of objects
>     + The operations provide the only way to use the objects

Obviously, these are also characteristics of object-oriented programming, which is indeed a later implementation of the same ideas.

To give another example: A class implementing a dictionary (hash table). You can specify which operations (e.g. set, get, delete) should be provided, what these operations do, what their time complexity is etc. and then develop this module independently of the rest of the program. Note, that you do not need classes to do that.

Liskov also somewhat famously said:

> Modularity based on abstraction is the way things are done.

Abstraction here means not exposing or requiring unnecessary details. For instance, a dictionary specification in a scripting language (Python for example) should not specify the exact number of bytes required to store each element. This doesn't help users of the module and makes it harder to develop the module.

However, the level of abstraction depends on the application. When developing a spacecraft the right level of abstraction might indeed require specifying the amount of bytes used.

When people speak about modularity in software development today, they will typically mean the "modularity based on abstraction" Liskov describes. If modules are not abstracted properly, it might even be almost impossible to identify them.

# Answer
> 0 votes
A remarkable definition of *modularity* from a paper about Ecology:

> Modularity is a system property which measures the degree to which densely connected compartments within a system can be decoupled into separate communities or clusters which interact more among themselves rather than other communities.

As for software design, this Wikipage says, that:

> ... modularity refers to a logical partitioning of the "software design" that allows complex software to be manageable for the purpose of implementation and maintenance. The logic of partitioning may be based on related functions, implementation considerations, data links, or other criteria.

---
Tags: terminology
---


# Question
Title: Reduction from the SAT problem to the NAE-SAT problem
I study complexity and computation independently. I have a problem that I can not solve.

**That's the problem:**

For the SAT problem, there is a version in which we receive as input phrase $\varphi$ in the form of CNF and we have to decide whether there is a placement in each of the closures $\varphi$ provides at least one literal and does not provide at least one literal. (This version is called NAE-SAT, where NAE is the acronym for Not All Equal).

for example:

* $( x\_1 \vee \overline{x\_2} \vee x\_3 )\wedge (\overline{x\_1} \vee \overline{x\_2} \vee x\_3) \in NAE-SAT$ because for the placement $s(x\_1)=T$ , $s(x\_2)=T$ and $s(x\_3)=T$ it holds that in each clause there is a literal about T and a literal about F, since it will show from the shape: $( T \vee F \vee T )\wedge (F \vee F \vee T )$
* $( x\_1 \vee x\_2 \vee x\_3 )\wedge (\overline{x\_1} \vee x\_2 \vee x\_3) \wedge (\overline{x\_1} \vee \overline{x\_2} \vee x\_3) \wedge (\overline{x\_1} \vee x\_2 \vee \overline{x\_3}) \notin NAE-SAT$. because in every placement for the phrase there will be at least one clause in which all the literals will be provided or all will not be provided, contrary to the requirements of the language.

We would like to show a reduction $ SAT \leq \_p NAE-SAT $. Given phrase $\varphi = c\_1 \wedge c\_2 \wedge \cdots \wedge c\_m$ (from the Boolean variables $x\_1 , x\_2 , \cdots , x\_n $) as an instance for the SAT problem, we will first create the new variables $ y\_1 , y\_2 , \cdots , y\_m , z$. Now, for each clause $C\_i = (l\_{i,1} \vee \cdots \vee l\_{i,k\_i})$ (which has $k\_i \geq 3$ literals) we construct the clauses: $D\_{i,1} = (l\_{i,1} \vee \cdots \vee l\_{i,k\_i-1} \vee y\_i) $ and $D\_{i,2} = ( \overline{y\_i} \vee l\_{i,k\_i} \vee z)$ . Finally, we will define the whole phrase to be $f(\varphi ) = D\_{1,1} \wedge D\_{1,2} \wedge D\_{2,1} \wedge D\_{2,2} \wedge \cdots \wedge D\_{m,1} \wedge D\_{m,2}$.

*The question has 3 sections, which are related to each other, so I can not ask each one separately*

Section A

For the phrase $\varphi = ( \overline{x\_1} \vee x\_2 \vee \overline{x\_3} \vee x\_4 )\wedge (x\_1 \vee x\_2 \vee x\_3)$, what is the phrase FP that will be constructed by the reduction?

1. $f(\varphi ) = ( \overline{x\_1} \vee x\_2 \vee \overline{x\_3} \vee y\_1 )\wedge (\overline{y\_1} \vee x\_4 \vee z) \wedge (x\_1 \vee x\_2 \vee y\_2) \wedge (\overline{y\_2} \vee x\_3 \vee z)$
2. $ f(\varphi ) = ( \overline{y\_1} \vee x\_4 \vee z) \wedge (x\_1 \vee \overline{x\_3} \vee y\_2) \wedge (y\_1 \vee y\_2 \vee y\_3) \wedge (\overline{y\_3} \vee \overline{x\_3} \vee z) $
3. none of the answers is correct.

*`I think the answer is 1, It's not complicated.`*

Section B

Is the reduction, as a function of the length of the phrase, polynomial?

1. Yes and also linear
2. Yes but it is not linear
3. This cannot be determined
4. No, since the number of new variables we add may increase exponentially depending on the number of original variables
5. none of the answers is correct.

*`I think the answer is yes, so 3 and 4 are certainly incorrect. The reduction takes a phrase in SAT and at most doubles it 2. If in SAT there were m clauses, at the moment there will be 2m clauses. And if in SAT there were n variables, currently in NAE-SAT there will be n + m variables. So in my opinion the correct answer is 1, but I'm not sure here.`*

Section C Is the reduction correct and defined on each input?

1. Yes and yes
2. Although the reduction is correct, in the description we do not refer to clauses with less than 3 liters. Nevertheless, it can be easily adapted to the case of 2 literals, and in the case of a single literal is simply rejected, as it will not be possible to simultaneously supply and not supply it.
3. The reduction is incorrect and is not defined on the entire input, which is why we do not handle clauses of even length
4. Although the reduction is defined on the entire input, it is incorrect.
5. none of the answers is correct.

*`I think the reduction is correct because it is polynomial. And I think it's also defined, because of every clause in SAT you can get 2 clauses in NAE-SAT, but I'm not sure about that. I stand out between answer 1 and answer 2`*

*The question was translated from Hebrew. So I have no source for the question.*

# Answer
As you correctly spotted, the reduction can be implemented in polynomial time, and the blowup in the formula size is indeed linear.

The reduction is also correct, with the caveat mentioned in item 2. It's not trivial to show, but we'll go at it slowly.

So first, let's assume we allow this construction also for 2 literals. As for 1 literal clauses -- we can assume those don't exist, since given a formula $\phi$, any 1-literal clause immediately forces a value of one of the variables $x$. So we can start by plugging in this value, and removing the clause and all occurrences of $x$ (more precisely - if $x$ was assigned True, we can remove all clauses containing $x$, and remove $\neg x$ from all other clauses, and vice-versa if $x$ was assigned False).

So now for the main reduction. We need to show two directions of correctness. First, let's assume $\phi\in SAT$. Then it has a satisfying assignment $\pi$.

We'll construct a NAE-satisfying assignment for $f(\phi)$ (note that it's called an "assignment", not "placement"). Consider some clause $C\_i$ of $\phi$. Since $\pi\models \phi$, then at least one literal in $C\_i$ is assigned True. If one of the literals in $D\_{i,1}$ is assigned True, then we assign $y\_i$ to False and $z$ to False, and now both clauses that result from $C\_i$ are NAE-satisfied. Otherwise, if all literals in $D\_{i,1}$ are assigned to False, then the remaining literal, which appears in $D\_{i,2}$ is assigned to True, so by assigning $y\_i$ to be True (and $z$ still False), we get again a NAE-satisfying assignment.

Note that we set $z$ to False globally, as it is a single variable.

So the first direction is correct. For the converse, we start with the following observation: if $\tau$ is a NAE-assignment, then the \`\`inverse'' assignment is also NAE. Thus, if $f(\phi)$ has a NAE-assignment, we can assume w.l.o.g. that $z$ is assigned to False (if not, we invert the assignment). From here we make a similar deduction to the above, to obtain a satisfying assignment for $\phi$. Try it and write if you get stuck.
> 3 votes

---
Tags: complexity-theory, computability, reductions, np, satisfiability
---


# Question
Title: Comparing asymptotic running time of two algorithms $\sqrt n$ and $2^{\sqrt{\log _{2}n}}$
Given two algorithms with their time-complexity $t\_a(n)=\sqrt{n}$ and $t\_b(n) = 2^{\sqrt{\log \_{2}n}}$ and i have to show $t\_b(n) = O(t\_a(n)) $.

I´ve made a program to check this statement and it seems that for any given $c\>0,\forall n\geq16$ it holds, however i don´t know how to formally proof this ,because i can´t find any simplification for $t\_b$.

I know that i must prove $ \exists c : \forall n \geq N:t\_b(n) \leq c \*t\_a(n)$ using big-O-Notation.

A hint/solution-idea would be really great.

# Answer
> 3 votes
In order to compare two quantities/expression, it is often easier if they are in the same form. Here try expressing $t\_a(n)$ as $2^{s\_a(n)}$ and compare $s\_a(n)$ with $\sqrt{\log\_2 n}$.

Additionally, beware of using a program to check asymptotic comparisons: e.g. $f(n)=n^{10^6}$ and $g(n)=(1,0000000000000001)^n$

# Answer
> 0 votes
We can simplify $t\_b(n): $ $$t\_b(n) =2^{\sqrt{\log \_{2}n}}$$ $$=\left(2^{\log \_{2}n}\right)^{\frac{1}{\sqrt{\log \_{2}n}}} $$ $$=\left(n^{\log \_{2}2}\right)^{\frac{1}{\sqrt{\log \_{2}n}}} $$ $$=n^{{\frac{1}{\sqrt{\log \_{2}n}}}}$$ $$=\sqrt\[\sqrt{\log\_2 n}\]{n}.$$

Therefore $$\left(\sqrt\[\sqrt{\log\_2 n}\]{n}\right)=\mathcal{O}\left(\sqrt{n}\right)$$ because $$\lim\_{n\to\infty}\frac{\left(\sqrt\[\sqrt{\log\_2 n}\]{n}\right)}{\left(\sqrt{n}\right)}=0.$$

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


# Question
Title: Can't understand the $O$ notation for runtime of algorithms
In my book,the $O$-notation is given as: $$O(g)=\\{f:\mathbb N\rightarrow \mathbb R\_{\geq 0}:\exists \alpha\in \mathbb R\_{\>0},\exists n\_0 \in \mathbb N : \forall n\geq n\_0 f(n)\leq \alpha g(n)\\}$$
The algorithm(in pseudocode) for simple primality is given as:
input: $n\in \mathbb N$
output: $result$
main code:
**if**($n\<2$)
result="no" **else**
for $i\rightarrow 2$ **to** $\lfloor {\sqrt n}\rfloor$ **do**
**if**($i|n$)
result="no"
**output** result
It says that if $g:n\rightarrow \sqrt n$ where $n\in \mathbb N $, and $f:\mathbb N\rightarrow R\_{\geq 0}$ which counts the number of elementary operations of the above given algorithm.Then $f \in O(g)$. I justified this as
No matter what $f(n)\leq \lfloor \sqrt n \rfloor-1 \< \lfloor \sqrt n \rfloor \leq g(n)$
and thus, we get the result.But then it states that

> One can even say in this case that the algorithm has running time $\Theta(\sqrt n)$, because the number of steps performed by the algorithm is also never less than $\sqrt n$

which is opposite to what I just said.

# Answer
You are looking at worst-case analysis in your book, i.e. how many steps does the algorithm perform in the worst-case. So the statement should at least be amended to say

> One can even say in this case that the algorithm has running time $\Theta(\sqrt n)$, because the number of steps performed by the algorithm **in worst-case** is also never less than $\sqrt n$

This is still not a good explanation. Consider first that we can define $\Omega$ analogously to $O$ as:

$$\Omega(g)=\\{f:\mathbb N\rightarrow \mathbb R\_{\geq 0}:\exists \alpha\in \mathbb R\_{\geq 0},\exists n\_0 \in \mathbb N : \forall n\geq n\_0 f(n)\geq \alpha g(n)\\}$$

Note the change from $\leq$ to $\geq$. We know that $f \in \Theta(g)$ if and only if $f \in \Omega(g)$ and $f \in O(g)$.

You have already justified $f \in O(g)$. To justify $f \in \Omega(g)$ note that for example for $\alpha = 0.5, n\_0 = 18$ we have $\lfloor \sqrt n \rfloor - 1 \geq \alpha g(n) = 0.5 \cdot \sqrt n$ for $\forall n \geq n\_0$.

To see this holds consider that $\sqrt n - (\lfloor \sqrt n \rfloor - 1) \< 2$ while $\sqrt n - 0.5 \cdot \sqrt n \> 2$ for $\forall n \geq n\_0$. Together this gives $2 + 0.5 \cdot \sqrt n \< \sqrt n \< 2 + (\lfloor \sqrt n \rfloor - 1)$, which finally yields $\lfloor \sqrt n \rfloor - 1 \geq 0.5 \cdot \sqrt n$.
> 2 votes

# Answer
As it come out from comments we are talking about book Stefan Hougardy, Jens Vygen - Algorithmic Mathematics-Springer International Publishing (2016), where algorithm in question is on page 8.

Confusing moment from page 10

> " ..the number of steps performed by the algorithm is also never less than $\sqrt{n}$ "

can be explained from page 9

> It is also not immediately clear whether computing the square root can be accomplished with an elementary operation; this can, however, easily be avoided by increasing i stepwise by 1 until $i \cdot i \gt n$.

Last sentence shows, the number of steps considered by the authors satisfies the condition $i \gt \sqrt{n}$.
> 1 votes

---
Tags: algorithms, big-o-notation
---


title: tautology vs satisfiability

text:
# Question
Title: tautology vs satisfiability
I had a test that I failed to pass, and it had a question that I failed to do.

**This is the question:**

Let us look at the language TAUTOLOGY: Collect all the phrases $\varphi$ so that each placement on the variables $\varphi$ will provide $\varphi$. We will denote the number of variables in n and the number of phrases in m. Determine which of the following statements is correct:

1. The language is in $P$
2. The language is in $NP$ but not in $NPC$.
3. The language is in $CoNPC$, since $SAT \in NPC$
4. None of the above claims are true.

I think the correct answer is 3, it makes sense, because it's a complementary language to SAT, but I do not know how to explain it.

1 does not seem right, 2 this is an illogical claim at all - If the language is in NP then it must also be in NPC in my opinion , probably the answer is 3 but I do not know why.

# Answer
While @nir shahar's answer is not wrong, your question is about the complexity of TAUTOLOGY when we have no assumptions on the structure of the formula. In the special case of Conjunctive Normal Form (CNF, a AND of OR clauses), you can solve TAUTOLOGY in polynomial time, as Shahar says. However, there are other special cases for which TAUTOLOGY is co-NP-complete. This, of course, implies that TAUTOLOGY also in the general case is co-NP-complete.

If you switch the AND's and OR's in some CNF formula $\varphi$, you get a new formula $\varphi'$ that is in Disjunctive Normal Form (DNF). It is not hard to see that some truth assignment makes $\varphi$ true if and only the "opposite" (i.e. make true variables false and vice versa) truth assignment makes $\varphi'$ false. This means that we have a reduction from SATISFIABILITY on CNF formulae to the "FALSIFIABILITY" problem on DNF formulae. Thus, the latter problem is NP-complete.

As TAUTOLOGY ("does every truth assignment make this formula true?") is the complementary problem to FALSIFIABILITY ("does *some* truth assignment make this formula false?"), TAUTOLOGY on DNF formulae must be co-NP-complete.
> 2 votes

# Answer
The main "key" here is to understand how a formula is structured. Assuming the formulas of TAUTOLOGY are in CNF, then there exists a polynomial algorithm:

Let $\varphi=\bigwedge\_{i=1}^{k}\limits C\_i$ where each $C\_i$ is described as an $\lor$ of multiple literals.

Notice, that in order for an assignment $\rho$ to satisfy $\varphi$, we need $\rho$ to satisfy all of the $C\_i$'s. Therefore, $\varphi$ is a tautology if and only if all $C\_i$'s are tautologies. Since $C\_i$ is described as a simple $\lor$ of multiple literals, its easy to check that it is a tautology (check to see if there is a literal and its negation. If there is, its a tautology. Otherwise, it isn't)

Thus, the algorithm will check that each of the clauses $C\_i$ is a tautology and will accept only if all of them are tautologies.

---

Here is a more detailed explanation of the algorithm. First, lets write the algorithm as pseudocode:

## The algorithm

1. Given $\varphi$, decompose it into $C\_i$'s such that $\varphi = \bigwedge\limits\_{i=1}^k C\_i$.
2. For each $1\le i\le k$, do the following:
    * Decompose $C\_i$ into $C\_i=l\_{i,1}\lor l\_{i,2}\lor\dots\lor l\_{i,m}$ where all $l\_{i,j}$'s are literals.
    * If there are some $j\_1,j\_2$ such that $l\_{i,j\_1}=\overline{l\_{i,j\_2}}$, mark $C\_i$ as a tautology
3. If all $C\_i$'s were marked as tautologies, accept. Otherwise, reject.

## Complexity

Clearly, the algorithm runs in polynomial time. It has a few nested loops, but thats it. Each loop can add a factor of $n$ into the running time, and hence the run-time is at most $n^c$ for some constant $c$ (in fact, it runs in $n^3$ if it is well-implemented).

## Correctness

We want to show that $\varphi\in TAUTOLOGY \iff A(\varphi)=true$ where $A$ is the algorithm described above.

We will start by showing that $\varphi\in TAUTOLOGY \implies A(\varphi)=true$. Indeed, $\varphi$ is satisfied by any assignment. In particular, since $\varphi=\bigwedge \limits\_{i=1}^k C\_i$, then for any assignment, $\varphi$ is satisfied only if all $C\_i$'s are satisfied, and since $\varphi\in TAUTOLOGY$ then we must have that $C\_i$ is a tautology as well, for all $i$.

Now, we want to show that all $C\_i$'s will be "marked". That is, for every $i$, there is some literal $l\_{i,j}$ and its negation in $C\_i$. Let us, assume towards contradiction that this isn't the case. Then, we know that all literals $l\_{i,j}$ in $C\_i$ have to be with some unique variable $x\_{i,j}$ (within $C\_i$ only. This variable can be used in some other clause $C\_{i'}$, but we aren't concerned with that). Let us define the following assignment $\rho$:

$$\rho(x\_{i,j}):=\begin{cases}False&l\_{i,j}="x\_{i,j}"\\True&l\_{i,j}="\overline{x\_{i,j}}"\end{cases}$$

In this way, we know that for any $j$, the assignment of $\rho$ for $x\_{i,j}$ is guaranteed to make $l\_{i,j}$ be assigned with $False$. Note, that since all $l\_{i,j}$ use some distinct variable $x\_{i,j}$, this assignment $\rho$ is well-defined.

But, this means that under the assignment given by $\rho$, $C\_i$ gets the value $False$. Now, this means that $\varphi = \bigwedge\limits\_{i=1}^k C\_i$ also gets the value $False$, in contradiction that any assignment on it must satisfy it, and hence must result in a $True$.

Therefore, we conclude that $C\_i$ *has* to be "marked", for all $i$, and therefore $A(\varphi)=True$ from the definition of the algorithm.

Showing the direction $A(\varphi)=True\implies \varphi\in TAUTOLOGY$ is a very similar process to the above proof.
> 5 votes

---
Tags: complexity-theory, turing-machines, computability, reductions, np
---


# Question
Title: What is this algorithm computing and how to prove it?
On Hackerrank I found a test that asks to check what the following algorithm computes:

1. If $x \> y$ then $x = x - y$
2. If $y \> x$ then $y = y - x$
3. If $x \neq y$ then goto 1
4. Print $x$

Constraints: $x$ and $y$ are greater than $0$

So I think/guess this algorithm returns the product of common factors, so 1 when they do not have any in common. I just guessed it by computation and by intuition, but I would like to prove it in a formal way.

How can this be proved?

# Answer
> 7 votes
The algorithm computes the greatest common divisor, or gcd for short. You are correct that the output is the product of common factors, since the gcd is known to be equivalent to it.

In fact, this algorithm is known as Euclid's algorithm.

---
Tags: factoring
---


# Question
Title: Is it possible to use a quantum computer simulation to perform a cyber attack?
Is it possible to use a quantum computer and or a simulation to perform a cyber attack on classic computers? This is part of a research objective I'm trying to figure out.

# Answer
> 1 votes
This depends on what your objective is. For example, if your objective is to break a factorization-based cryptography protocol, then you can use Shor's algorithm to quickly find the factorization and break the protocol.

However, there are many other cryptography protocols, many of which are believed to be secure even against a quantum computer.

**Note:** a simulation of a quantum computer in a regular computer won't help you at all. Simulating a quantum computer is much much more expensive than what it will allow you to do.

---
Tags: algorithms, quantum-computing
---


# Question
Title: How to determine whether this language is regular?
I've encountered this question recently: Given $\Sigma=\\{\sigma\_1, \sigma\_2, ..., \sigma\_n\\}$ and $n\ge 2$, determine whether the following language is regular or not: $$ L\_1=\\{w\in\Sigma^\*|for \ 1 \le i \le n, \ \\#\_{\sigma\_i}(w) \ is \ even \iff i \ is \ even \\} $$ And I need to use the Myhill-Nerode theorem to solve it. I tried constructing a finite automata that accepts this language but had some troubles with it. I'd really appreciate some help!

# Answer
For $x = (x\_1, \dots, x\_n) \in \\{0,1\\}^n$, define $C\_x = \\{ w \in \Sigma^\* \mid \forall i=1,\dots,n, \\;\\; \\#\_{\sigma\_i}(w) \equiv x\_i \pmod{2} \\}$. Notice that the collection $\mathcal{C} = \\{C\_x \mid x \in \\{0,1\\}^n\\}$ is a partition of $\Sigma^\*$ and that $|C| = 2^n$.

Let $\rho \subseteq \Sigma^\* \times \Sigma^\*$ be the equivalence relation "having no distinguishing extension" (see the Myhill-Nerode theorem for a definition of "distinguishing extension"). I claim that the quotient set of $\Sigma^\*$ by $\rho$ is exactly $\mathcal{C}$. By the Myhill-Nerode theorem, this immediately implies that $L\_1$ is regular since $\mathcal{C}$ is a finite set.

To see that the claim is true, let $w,w' \in C\_x$ for some $x \in \\{0,1\\}^n$. For any $z \in \Sigma^\*$ and any $i=1,\dots,n$ we have that $$ \\#\_{\sigma\_i}(wz) \equiv x\_i + \\#\_{\sigma\_i}(z) \equiv x\_i + \\#\_{\sigma\_i}(z) \equiv \\#\_{\sigma\_i}(w'z) \pmod{2},$$

showing that either both $wz$ and $w'z$ belong to $L\_1$ or neither does. This means that there exists no distinguishing extension for $w$ and $w'$, i.e., $w$ and $w'$ lie in the same equivalence class.

Conversely, let $w \in C\_x$ and $w' \in C\_y$ for some $x,y \in \\{0,1\\}^n$ with $x \neq y$. Let $j$ be any index such that $x\_j \neq y\_j$. We construct a distinguishing extension $z$ for $w$ and $w'$ as follows: $$ z= \sigma\_1^{1-x\_1}\\,\sigma\_2^{x\_2}\\,\sigma\_3^{1-x\_3}\\,\sigma\_4^{x\_4}\\,\dots $$

By construction $wz \in L\_1$. Moreover, $w'z \not\in L\_1$ since we must have: $$ \\#\_{\sigma\_j}(wz) \equiv x\_j + \\#\_{\sigma\_j}(z) \not\equiv y\_j + \\#\_{\sigma\_j}(z) \equiv \\#\_{\sigma\_j}(w'z) \pmod{2}. $$ This shows that $w$ and $w'$ belong to different equivalence classes and concludes the proof.
> 2 votes

---
Tags: regular-languages, decidability
---


# Question
Title: A non-CFL over {a,b,c} with a non-CFL complement?
I understand uncountably many such languages exist, and the rationale for it is clear to me. I just cannot think of one trivial, easy-to-prove example. For instance, the complement of a^nb^nc^n is CF, and for more complicated examples I'm often not even sure what the complement is.

# Answer
> 3 votes
In one of your comments you remark that for unary languages this is more intuitive for you. We can simply adapt a unary language to suit your goals by adding the other letters to the alphabet.

Consider $L\_1 = \\{a^{n^2} \mid n\ge 1 \\}$ to be a non-regular language over $\\{a\\}$ $-$ in fact we can consider *any* non-regular unary language, using the primes for example. By the closure under complement also $L\_1^c = \\{a\\}^\* \setminus L\_1$ is nonregular. Also for unary languages regular and contextfree are equivalent, so both $L\_1$ and $L\_1^c$ are not contextfree.

Note that $L\_1$ can be considered a language over $\\{a,b,c\\}$ too. We can be a little over-formal and write $L = \\{w\in \\{a,b,c\\}^\* \mid w=a^{n^2} \text{ for some } n\ge 1 \\}$. Clearly $L$ is non-contextfree, because that is $L\_1$.

Also the complement over the full alphabet $\\{a,b,c\\}$ is not context-free: we merely add the regular language of words containing either $b$ or $c$. $L^c = \\{a,b,c\\}^\* \setminus L = L\_1^c \cup \\{a,b,c\\}^\*\cdot\\{b,c\\}\cdot\\{a,b,c\\}^\*$. This (again) follows from closure properties. Assume $L^c$ is contextfree, then so would be $L\_1 = L\cap \\{a\\}^\*$.

# Answer
> 2 votes
Let $L = \\{a^n b^n c^n \mid n \ge 0\\}$. Define $L' = \\{aw \mid w \in L \\} \cup \\{ bw \mid w \in \overline{L}\\} \cup \\{\varepsilon\\}$.

Notice that $L'$ is not context free by an application of the pumping lemma on $a^{p+1}b^pc^p$ for sufficiently large $p$.

The complement of $L'$ is $$ \overline{L}' = \\{xw \mid x\in \\{b,c\\} \mbox{ or } w\not\in L \\} \cap \\{xw \mid x\in \\{a,c\\} \mbox{ or } w\in L \\}. $$

Consider some word $bw$, where $w \in \Sigma^\*$. Notice that $bw$ always belongs to $ \\{xw \mid x\in \\{b,c\\} \mbox{ or } w\not\in L \\}$, therefore it belongs to $\overline{L}'$ if and only if it also belongs to $\\{xw \mid x\in \\{a,c\\} \mbox{ or } w\in L \\}$. This is only true if $w \in L$.

We can once again use the pumping lemma on $ba^pb^pc^p$ to show that $\overline{L}'$ is not context free.

# Answer
> 1 votes
Suppose $$\ell=\\{(abc)^p\mid p\text{ is prime}\\}$$

According to Parikh's theorem, both $\ell$ and its complement $\ell^c$ aren't Context-free.

---
Tags: formal-languages, context-free, context-sensitive
---


# Question
Title: What is fastest algorithm for factoring out square from number
I have $n$-digit integer $N=a^2b$, $b$ is square-free. In other words, $a$ is maximal square which divides $N$.

What is fastest known algorithm to find $a$? I can write algorithm of $O(n^2\sqrt{N})$ simply trying all squares that are smaller than $N$ and checking for divisibility.

Is this problem as hard as factoring integer?

# Answer
Using state of the art factoring algorithms, you can substantially improve on the algorithm you state. It appears that no algorithm better than factoring is known at the moment. See this question on mathoverflow.
> 3 votes

# Answer
It's obviously not harder than factoring, because you can solve the problem by factoring N into primes, and taking pairs of prime factors. So trying all squares less than N is quite bad.

The question is whether we can solve this faster than factoring, which depends on the algorithm used.

For factoring using the naive algorithm, you would check if any primes up to $N^{1/2}$ divide N. But here we only need to check primes up to $N^{1/3}$: If there are no factors up to $N^{1/3}$ then N is prime or the product of two primes. So N is square free unless it is the square of a prime, which is easy to check. So you can solve the problem in $O(N^{1/3})$ instead of $O(N^{1/2})$ using the most basic factoring algorithm.

The Pollard-rho algorithm finds the smallest factor in $(p^{1/2})$ where p is the smallest factor. You use this to try to find factors. In the original Pollard-rho algorithm, once you have done about $N^{1/4}$ iterations of the algorithm, you can say "if there was a factor then I would have found it by now" and check whether N is a prime using some primality test. For this problem, you would say after $N^{1/6}$ iterations "if there was a square factor and another factor than I would have found a factor by now". So then you check if N is a square or a prime. Unfortunately, if N is the product of two large primes, Pollard-rho tells you quite quickly that N is *very likely* to be square free, in $O(N^{1/6})$, but a proof will take $O(N^{1/4})$.

And there's a link showing that for the fastest known factoring algorithm, looking for squares is not any faster.
> 0 votes

---
Tags: factoring
---


# Question
Title: Does finding a reversal of a regular expression by automata need automata to be a DFA?
If I want to find the reversal of a regular expression using an automata, Do I have to transform the automata to DFA if it wasn't ?

# Answer
No. Represent your automata as a directed graph where each edge is labelled as a symbol of the alphabet. Then:

* Reverse all edges.
* Change the former initial state to an non-initial accepting state.
* Add a new initial state $q\_0$, and add a transition (edge) $q\_0 \overset{\varepsilon}{\to}q$ towards every state (vertex) $q$ that formerly was an accepting state.

This works even if the starting automata is a NFA.
> 1 votes

---
Tags: automata, regular-expressions
---