# Question
Title: How do you prove that a solution to the 0-1 knapsack problem is optimal?
Given a boolean vector b representing a solution to the knapsack problem with n elements k capacity and where each element has integer weight and value.

Proving that the solution is a solution is trivial. You add all the weights multiplied by the selection coefficient and check if it adds to more than the capacity.

But how do I verify that the solution given is *optimal*?

# Answer
You can't, not efficiently (unless P=NP).

Suppose there was a polynomial-time algorithm $A$ to check whether a given solution is optimal.

Then there would be a polynomial-time algorithm to solve the knapsack decision problem, i.e., given a problem instance and a value $V$, check whether there exists any solution with value $\>V$. Here is how: you add a single extra element with value $V$ and weight equal to the capacity; this then gives a trivial solution of value $V$; and now you run $A$ on this modified problem instance. If $A$ says "not optimal", then there exists a solution of value $\>V$ to the original instance; otherwise, there does not.

This would also imply that there exists a polynomial-time algorithm to find the optimal solution for a knapsack problem. Here is how: you use binary search on $V$, and apply the algorithm for the decision problem in each iteration of binary search.

That would imply that $P=NP$.

So if there exists a polynomial-time algorithm to check optimality, we obtain a proof that $P=NP$. Conversely, if we assume $P \ne NP$, then there does not exist any polynomial-time algorithm to check optimality.
> 2 votes

---
Tags: optimization, discrete-mathematics, knapsack-problems
---


# Question
Title: What are the job names for researching neural networks & deep learning?
I am a student who wishes to research neural networks (ANN, CNN, RNN) and deep learning, write papers on those topics, and actively participate in forums like CVPR.

My question is:

Which professions are dedicated to researching the theories behind, and developing models of, deep learning and neural networks?

Taking the example of Geoffrey Hinton, do those researchers work primarily in the academia as professors?

I know that at some tech companies, there are teams that specifically focus on researching those fields, but are the people on those teams called "deep learning researchers/engineers" in general? Or are there any other titles aside from those?

Also, from what I know, this is probably not the case, but do data scientists also research deep learning models?

# Answer
These terms don't have a precise meaning. It depends on the company/lab. I know of people who are "data analysts" yet do research in machine learning but also "data scientists" who don't do any research.

In fact, machine learning and deep learning are probably the hottest and the most hyped research areas currently. As such, and also given their practical usefulness, they are researched and developed in both the academia and industry. These researchers include professors, postdocs & other students, and also data scientists, data analysts, deep learning researchers/engineers and whatever a particular company might want to call them.

Your best bet is to study the topics at a university, and go from there. Also, you should talk to the professors and other researchers at your local institution and perhaps ask them the same question.
> 2 votes

---
Tags: machine-learning, career
---


# Question
Title: Complexity of the maximal minimum size problem
Here is a question that I do not understand:

> There is a list of items $E = e\_1,\dots,e\_m$. Suppose we have two players (the first and second).
>
> Each item $e\_j$ has a value $v(e\_j) \ge 0$. The values are not necessarily integers.
>
> The value of a set of items $A \subseteq E$ is $v(A) = \sum\_{e\_j \in A} v(e\_j)$.
>
> Let's look at the MMS problem in two players. Our goal is to partition the items between the two players.
>
> Let $P\_{i,1},P\_{i\_2}$ be an enumeration of all partitions. Let $Z\_i = \min(v(P\_{i,1}),v(P\_{i,2})$. The *minimum-maximum value* or *maximal minimum size* is $\max\_i Z\_i$.

For example, suppose that there are four items $e\_1,e\_2,e\_3,e\_4$ whose values are $$ v(e\_1) = 3, v(e\_2) = 5, v(e\_3) = 4, v(e\_4) = 2. $$ The possible partitions (stated in terms of values) are:

* $\emptyset, \\{2,3,4,5\\}$ – the minimum value of a set is 0.
* $\\{2\\}, \\{3,4,5\\}$ – the minimum value of a set is 2.
* $\\{3\\}, \\{2,4,5\\}$ – the minimum value of a set is 3.
* $\\{4\\}, \\{2,3,5\\}$ – the minimum value of a set is 4.
* $\\{5\\}, \\{2,3,4\\}$ – the minimum value of a set is 5.
* $\\{2,3\\}, \\{4,5\\}$ – the minimum value of a set is 5.
* $\\{2,4\\}, \\{3,5\\}$ – the minimum value of a set is 6.
* $\\{2,5\\}, \\{3,4\\}$ – the minimum value of a set is 7.

As you can see, the to parts are not ordered, so this is an exhaustive list of the possible partitions. The minimum-maximum value is 7, attained by the partition $\\{2,5\\},\\{3,4\\}$.

> In the decision problem MMS we are given a list of items $E$ together with their value function $v$ and a non-negative number $z$, and the problem is to decide whether the maximum minimum size is equal to $z$.

> Question 1: To which complexity class does MMS belong?
>
> 1. MMS belongs to P
> 2. MMS belongs to NP
> 3. MMS belongs to coNP
> 4. It is not known whether MMS belongs to coNP

> Question 2: What is an appropriate witness or algorithm for the answer in question 1?
>
> 1. There is a polynomial time algorithm which partitions the items greedily.
> 2. There is an efficient algorithm that verifies negative instances. The witness is a partition $P\_1,P\_2$ such that $\min(v(P\_1),v(P\_2)) \> z$.
> 3. The witness is a partition $P\_1,P\_2$. If $z \< \min(v(P\_1),v(P\_2))$, then we know that the answer is negative. But when $z \> \min(v(P\_1),v(P\_2))$, we cannot conclude that the answer is negative.

I do not understand these two questions.

# Answer
> 1 votes
Regarding question 1. The decision version of MMS is NP-hard by a reduction from partition but it is currently unknown whether it belongs to $\mathsf{P}$, $\mathsf{NP}$, or $\mathsf{CO\\!-\\!NP}$.

Regarding question 2.

1. We don't know whether there exists a polynomial-time algorithm for MMS. I'm not aware of an argument that allows to rule out greedy algorithms (how would the class of greedy algorithms be formally defined in the first place?).
2. We don't know if there an efficient algorithm that verifies instances given that certificate. For example, if the problem is in $\mathsf{P}$, then the answer is trivially yes (regardless of the certificate).
3. This is correct, as far as we know. Notice that if MMS were in $\mathsf{P}$ then we would be able to conclude that the answer to a "no" instance is negative regardless of the certificate.

---
Tags: complexity-theory
---


# Question
Title: How can I prove that the empty string is the identity element with regards to the operation of concatenation?
Let $w$ be a string over an alphabet $\Sigma$. It is obvious that $w \circ \epsilon = \epsilon \circ w = w$. However I'm having a hard time coming up with a proof for that (which I assume should be fairly easy, I just don't know how to tackle it).

My first thought on how to do it is the following:

$\Sigma^{\*}$ is the smallest set that contains $\Sigma$ and is closed under the operation of concatenation. Thus $(\Sigma^{\*},\circ)$ is (at least) a magma. Now I would need to prove that $(\Sigma^{\*},\circ)$ is a monoid.

But I don't know how to take it further from there or if that approach is going to lead anywhere.

I thank you in advance for helping me out.

# Answer
Here is one way to define the set of words and the concatenation operation.

A word over $\Sigma$ is either $\epsilon$ or $\sigma.w$, where $\sigma \in \Sigma$ and $w$ is a word over $\Sigma$. This definition can be formalized in several ways, but what is important here is the induction principle: a property $P$ of words holds for all words over $\Sigma$ if (i) $P(\epsilon)$ and (ii) if $P(w)$ then $P(\sigma.w)$ for all $\sigma \in \Sigma$.

The concatenation $x \circ y$ of two words $x,y$ over $\Sigma$ is defined inductively as follows: $\epsilon \circ y = y$ and $(\sigma.x) \circ y = \sigma.(x \circ y)$.

This definition makes it clear that $\epsilon \circ y = y$. We can prove that $y \circ \epsilon = y$ by induction on $y$. First, $\epsilon \circ \epsilon = \epsilon$. Second, suppose that $y \circ \epsilon = y$. Then $(\sigma.y) \circ \epsilon = \sigma.(y \circ \epsilon) = \sigma.y$.
> 2 votes

---
Tags: strings, algebra
---


# Question
Title: What does it mean when asking to Convert 16-bit binary numbers to two 8-bit signed integers (two’s complement) in decimal
The question is

> Convert the following 16-bit binary numbers to two 8-bit signed integers (two’s complement) in decimal.
>
> i. 0b 0011 0110 1101 0100

I first flipped it and added 1 to it which equaled

0b 1100 1001 0011 1100 which is 51516 in decimal

Is this right? I don't really understand what the question is asking for when it says "two" 8-bit signed integers (two’s complement) in decimal.

# Answer
> 0 votes
That question is not the clearest, but I don't think that's what it asked you to do. "Two’s complement" means two things: a system of mapping between bit-strings and integers in a useful way, and an operation (which you performed) that corresponds to negation under that mapping. This question is not asking you to negate the number, it's asking you to "convert" it.

What sort of conversion we're supposed to be doing is not that clear, but a prime candidate for "converting" a 16 bit number into two 8 bit numbers is to split it down the middle.

So I think the question wants this:

Take `0011 0110`, interpret it as a signed 8-bit number, using the two's complement system. So eg `1111 1111` would mean -1, instead of -127 (in the sign and magnitude system) or -0 (in the ones' complement system) or something else. `0011 0110` would mean 54. `1101 0100` is more interesting since it's negative.

---
Tags: base-conversion
---


# Question
Title: What's so difficult about computer verifiable proofs?
What's so hard about creating a piece of software with as minimal as possible mathematical axioms, defining a formal language in which one can create new constructs based on the existing ones, and then all research papers could be written in that language and its correctness verified by a computer?

# Answer
> 1 votes
Computer-Assisted Proof is a rather old field of research, and programs of that kind have already been made. Most of them relied on brute-force approaches, or graph search algorithms (BFS, DFS).

The thing is, first of all, it would not be trivial to define a language that can describe every possible problem (see: incompleteness theorems), and also, assuming you defined that language and found an optimal way to catch up with the current state of research, what would happen if you fed your magic algorithm a paper describing the correctness of the magic algorithm itself?

**Edit:** As mentioned by Steven, the obvious problem with this is that one would have to insert each and every proof by hand, so I assumed OP wanted to generate those proofs in a less "manual" way. Either way, the problem of defining such a language would still be a thing (an example of a failed attempt at that might be Russell's *Principia*).

---
Tags: software-verification, proof-assistants
---


# Question
Title: Reduction from vertex-coloring problem to edge-coloring problem
A few days ago I had a test and could not pass it. This is a question I did not understand in the test.

> We will look at the Edge-Coloring problem, in which, as is well known, 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?". Remember, 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}

> Determine which of the following statements is correct:
>
> 1. The language is in P. An algorithm can be constructed running at time O (| V | * | E |), by reduction to the vertex-Coloring problem and then verifying that each color is ≤ k.
> 2. The language is in NP (and it is also possible that it is NP-complete, but this is not due to the question data)
> 3. The language is NP-complete, which is why vertex-Coloring is NP-complete and also $Edge-coloring \leq \_pvertex-coloring $ can be performed by converting each arc to a vertex.
> 4. The language is NP-complete but not in NP
> 5. None of the above claims are true.

I think 3 is true, because in my opinion a reduction is made from the vertex-coloring problem which is NPC, and also the edge-coloring problem should be in NPC.

But I can not rule out 4, 2 and 5.

# Answer
> 2 votes
1. We don't know whether this is true.
2. This is true, a certificate is an edge coloring with at most $k$ colors.
3. This is true. Edge coloring is a well-known NP-hard problem (see here for a reduction from 3-SAT) and hence there is Karp reduction from every problem in NP to it. In particular there must also be a reduction from vertex coloring (which is NP-hard) to edge coloring. The reduction from edge coloring to vertex coloring creates a vertex $v\_e$ for every edge $e$ in $G$ and an edge $(v\_e, v\_f)$ for every pair of distinct edges $e$ and $f$ in $G$ that share an endpoint.
4. This statement is clearly false since all NP-complete languages are in NP by definition.
5. This is false since, e.g., 2 is true.

# Answer
> 1 votes
* For (3), you are correct, i.e., the problem is NP-complete. As a side note, you might also like to know that you can solve edge coloring by using vertex coloring algorithms by taking the line graph. Note that this in itself does not prove NP-completeness.
* For (2), you need to show that if you given a certificate, then you can verify it in polynomial time. In this case, the certificate is the coloring, i.e., a color per edge. Given that certificate, you can easily check in polynomial time whether the given coloring is a proper edge-coloring. I encourage you to check the details.
* For (4), you should check the definition of NP-completeness. If a problem is NP-complete, then by definition it is also in NP.
* Question (5) is now trivial.

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


# Question
Title: How to setup the Bellman Equation as a linear system of equation
I was watching a video on Reinforcement Learning by Andrew Ng, and at about minute 23 of the video he mentions that we can represent the Bellman equation as a linear system of equations. I am talking about the Hamilton-Jacobi-Bellman equation, used for discrete control problems or discrete reinforcement learning problems.

The equation as he posts it is:

$$ V^\pi(s) = R(s) + \gamma\sum\_{s\`}P\_{s,\pi(s)}V^\pi(s\`) $$

$V^\pi(s)$ represents the "value" at state $s$. So the idea is simple enough. But I was not clear on how to really represent this as a system of equation. I have a notion of this, but I was hoping that someone could help fill in the correct answer.

So in the linear system, the $V^\pi(s)$ is the unknown. A linear system looks like $Ku = f$. Now, I know that in some Markov Decision Process, I have a probability of the subsequent states $s'$ given the action $a$ that is chosen. So if the policy indicates go "North", then I have an 80% chance of going north, with a 10% chance of going East, and a 10% chance of going West. That is the reason for the probability.

Now for convenience I will write $v\_1, v\_2$, instead of $V^\pi(s\_1), V^\pi(s\_2),...$. **The biggest point of confusion is how to handle the immediate reward $R(v\_i)$.** I would basically have a system like the following, (I left out the $\gamma$ just to simplify the notation).

$$ -v\_1 + 0.8v\_2 + 0.1v\_3 + 0.1v\_4 + 0 + 0 + ... + R(v\_1) = 0 \\ 0.8v\_1 - v\_2 + 0.1v\_3 + 0 + 0.1v\_5 + ... + R(v\_2) = 0 \\ ... $$

So I could express this as a system with a vector of $\[v\_1, v\_2, ..., v\_n\]$, and a matrix of coefficients like :

$$ \begin{bmatrix} -1 & 0.8 & 0.1 & 0.1 & 0 & 0 & 0 & ... \\ 0.8 & -1 & 0.1 & 0 & 0.1 & 0 & 0 & ... \\ \vdots \\ \end{bmatrix} * \begin{bmatrix} v\_1 \\ v\_2 \\ \vdots \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ \vdots \\ \end{bmatrix} $$

Or is the reward $R(v\_1) = v\_1$ in which case I would have 0's on the diagonal of the coefficient matrix.

Again, Ng did not write this out completely, so I am just trying to figure it out. I think I am just about there, but missing the last 10 percent.

# Answer
> 3 votes
I found the full answer in a video by David Silver. The idea is easy enough.

The underlying matrix equation is

$$ v = R^\pi + \gamma P^\pi\_{s, s'} v $$

Where $v$ is the value function, $R^\pi$ is the immediate reward under policy $\pi$, $\gamma$ is the discount factor, and $P^\pi\_{s, s'}$ is the transition matrix.

I can write out the system of equations as below. *For the sake of convenience, I omit the $\pi$ and the $\\{s, s'\\}$ subscripts*.

$$ \begin{bmatrix} v\_1 \\ v\_2 \\ \vdots \\ v\_n \end{bmatrix} = \begin{bmatrix} R\_1 \\ R\_2 \\ \vdots \\ R\_n \end{bmatrix} + \gamma \begin{bmatrix} p\_{11} & p\_{12} & \cdots & p\_{1n} \\ p\_{21} & p\_{22} & \cdots & p\_{2n} \\ \vdots \\ p\_{n1} & \cdots & \cdots & p\_{nn} \end{bmatrix} \begin{bmatrix} v\_1 \\ v\_2 \\ \vdots \\ v\_n \end{bmatrix} $$

I can solve the matrix equation with some simple linear algebra:

$$ \begin{align\*} v &= R + \gamma P v \\ v - \gamma P v &= R \\ (I - \gamma P)v &= R \\ v &= (I - \gamma P)^{-1}R \end{align\*} $$

Now of course this solution involves inverting a matrix and that is not easy to do except in very small cases. So we can use iterative methods to solve for $v$. But iterative methods just alter the above equation such that.

$$ v^{k+1} = R^\pi + \gamma P^\pi\_{s, s'} v^{k} $$

# Answer
> 1 votes
It seems that you confused yourself about this a bit too much. Lets start from the beggining:

First, we want to note that in Bellman's equations, the rewards $R(v)$ are defined as the expected value of the immediate reward (since it could be a random variable). That is, $R(s):=\mathbb{E}\[R\_{immediate}(s,\pi(s))\]$. The important part to note here, is that $R(s)$ is some *known constant!*. Our variables in this system, as you said, are the $V^\pi (s)$ for all states $s$. So, for every such state $s$ we have one linear equation, that is described by bellman's equation: The equations depend *linearly* on the values $V(s')$. Combine the equations together (put them as a system of equations), and viola! You will get a system of linear equations!

You don't really need to express that as a matrix multiplication to know its linear, but if you still want to: We will treat the states as indices that range between 1 and $n$ (the number of total states). Now, start from replacing $V(s)$ with a variable $x\_s$ you solve for. Then, write the $$P\[\text{next state is }s'\mid \text{ we are in }s\text{ and do action }\pi(s)\]$$ As $A\_{s,s'}$. Then, write $R(s)$ as $b\_s$, and rewrite the system as a matrix multiplication system: $Ax=b$.

---
Tags: linear-algebra, reinforcement-learning
---


# Question
Title: Deteremine if $L = \{\langle M\rangle : L(M) \text{ consits of all words of prime length}\}$ is in $R$ or in $RE\setminus R$ or not in $RE$
> Deteremine if $L = \\{\langle M\rangle : L(M) \text{ consits of all words of prime length}\\}$ is in $R$ or in $RE\setminus R$ or not in $RE$

I am trying to prove that $L$ is not in $RE$ by reduction from $L\_{acc}^c = \\{M,w: w\notin L(M)\\}$ to $L$, but I it seems not works for one side and I have no idea how can I fix it.

if $x=\langle M,w\rangle$ in $L\_{acc}^c$ then for any input $z$, I will check if $|z|$ is prime (it can be done by TM) and if it is, then my machine says yes. if not then we will run $M$ on $w$ and answer what we got. In this situation our language will consist of all the words with prime length.

but in the following way we have an issue since our language will be all the words, i.e $\Sigma^\*$

If $x=\langle M,w\rangle$ not in $L\_{acc}^c$ then for any input $z$ our machine will say yes since if $|z|$ is prime we say yes and if not then $w\in L(M)$ and therefore we say yes, so we say yes for any input. and that cant work since we need to prove that $f(x)\notin L$ to out reduction work.

I have no idea how to fix the this, any ideas?

# Answer
The "key" here is to make $f$ construct a new machine $M'$ that will contain all of the primes assuming that $w\notin L(M)$, and otherwise, there will be at least one prime it rejects.

Now, the reduction $f$ will work by taking $\langle M, w\rangle$ and outputting the following TM $M'$:

1. On input $z$, run the following:
2. Emulate $M$ on $w$ for $|z|$ steps.
3. Accept if $M$ didn't halt in time, or if $M$ rejected $w$.

Clearly, if $w\notin L(M)$ then $L(M')=\Sigma^\*$, hence $\langle M'\rangle$ is in the language you reducte to. However, if $w\in L(M)$, then there is some positive number $t\in \mathbb{N}$ such that $M$ accepted $w$ in $t$ steps. Therefore, $M'$ will reject all inputs $z$ with $|z|\>t$. In particular, since there are an infinite number of primes, there is some prime $p$ with $p\>t$. Then, choose some word $v$ with $|v|=p$, and viola! $v\notin L(M')$, hence $\langle M'\rangle $ is not in the language you reduce to, since it doesn't contain all words with prime length.
> 1 votes

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


title: Reduction from SAT to 3SAT

text:
# Question
Title: Reduction from SAT to 3SAT
a few days ago I had a test and could not pass it. This is a question I did not understand in the test.

> Recall the reduction we saw $SAT \leq \_p 3SAT$. Given verse $\varphi$ in the form of $CNF$, we converted each fragment $C\_i$ in $\varphi$ to verse $D\_i$ in the form of $CNF$ by adding new variables. Then, we returned:

$f(\varphi )= \wedge \_{i=1}^{m}D\_i$, for m is the number of verses in $\varphi$.

Let there be some verse $\varphi= C\_1\wedge C\_2 \wedge \cdots \wedge C\_m$.

> Find a bound on the number of verses in $f(\varphi)$:
>
> 1. Between $m$ and $m^2$
> 2. Between $2m$ and $m^2$
> 3. If we denote by $h$ the amount of variables in the longest verse in $\varphi$ then: $(h-2)\cdot m$.
> 4. This cannot be determined because we do not know the size of each verse $C\_i$
> 5. None of the above claims are true.

I can not find the answer. I can not find a relationship between m and h and the size of the number of verses

# Answer
This question refers to a specific transformation that you have seen during the course but we are not given, so we can only guess.

A standard transformation from a SAT clause $C$ to a collection of 3-SAT clauses is as follows:

* If $C$ already contains $3$ literals, then $C$ is left unchanged.
* If $C$ contains $1$ (resp. $2$) literals, then add $2$ (resp. $1$) copies of a literal from $C$ to $C$ itself.
* If $C$ contains $k \ge 4$ literals, then let $C = \ell\_1 \vee \ell\_2 \vee \dots \vee \ell\_k$. Add $k-3$ new variables $x\_3, \dots, x\_{k-1}$ andeplace $C$ with: $$ (\ell\_1 \vee \ell\_2 \vee x\_3) \wedge \left( \bigwedge\_{i=3}^{k-2}(\overline{x}\_i \vee \ell\_i \vee x\_{i+1}) \right) \wedge (\overline{x}\_{k-1}, \ell\_{k-1}, \ell\_k) $$

Notice how the above subformula contains 2 original literals in the first and in the last clauses, and 1 original literal in each of the intermediate clauses. Therefore the overall number of 3-SAT clauses needed to represent $C$ is $2 + (k-4) = k-2$.

This shows you that option 3 is correct.

Regarding the other options:

* 1 Is incorrect. Think of a formula with a single clause with $4$ variables.
* 2 Is incorrect. Think of a SAT formula that is also already a 3-SAT formula.
* Regarding 4, we can certainly find upper and lower bounds. In fact we can even find the exact number of clauses. If there are $m$ clauses and the number of variables in the $i$-th clause is $m\_i$ then the final number of clauses will be $\sum\_{i=1}^m \max\\{m\_i-2, 1\\}$.
* 5 is false since 3 is true.
> 1 votes

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


# Question
Title: Design the finite DFA where 5 divides 2i+3j
> a) For $\sum =\\{0,1\\}$ , design a deterministic finite automaton $M$ accepting the language $L=\\{a^ib^j:i,j\ge 1, \text{5 divides (2i+3j)}\\}$

> b) Prove that ypur automaton exactly accepts the language $L,$ i.e $L=L(M)$

---

I first find $i,j$ relation . since $5|(2i+3j) \Rightarrow j=i+5k, k\ge 0(\in \mathbb{N})$

Therefore $L=\\{a^ib^j:i,j\ge 1, \text{5 divides (2i+3j)}\\}=\\{a^ib^{i+5k}:i\ge 1, k\ge 0(\mathbb{N})\\}=\\{ab,ab^6,ab^{11},a^2b^2,a^2b^7,a^2b^{12},a^3b^3a^3b^8,...\\}$
But i can't design DFA .

# Answer
> 0 votes
Let's consider the language $L' = \\{a^ib^j \mid i \ge 0, j \ge 1, \mbox{5 divides $2i+3j$}\\}$ for a second. To design a DFA for $L'$ you can essentially keep a counter $x$ for $2i+3j$. This counter is stored modulo $5$.

The states of DFA will be all pairs $(x,y)$ with $x \in \\{0,1,2,3,4\\}$ and $y \in \\{0,1\\}$. Intuitively, $y=0$ will mean that we have not read a $b$ symbol yet, while $y=1$ means that we have already read a $b$ and hence we expect all the following symbols to be $b$.

The transitions are as follows:

* $(x,0) \overset{a}{\to} ((x+2) \bmod 5, 0)$, for all $x \in \\{0,1,2,3,4\\}$.
* $(x,0) \overset{b}{\to} ((x+3) \bmod 5, 1)$, for all $x \in \\{0,1,2,3,4\\}$.
* $(x,1) \overset{b}{\to} ((x+3) \bmod 5, 1)$, for all $x \in \\{0,1,2,3,4\\}$.

The initial state is $(0,0)$ and the accepting state is $(0,1)$.

The only difference between $L'$ and $L$ is that words in $L$ must contain at least one $a$ symbol.

You can enforce this constraint by adding a new state $s$, making it the initial state (instead of $(0,0)$) and adding the transition $s \overset{a}{\to} (2, 0)$.

---
Tags: automata
---


# Question
Title: Can someone explain intuitively why union find works to find a cycle in an undirected graph?
I understand how the UF algorithm works to detect a cycle in an undirected graph, but I don't understand why it always works. Could someone explain that intuitively?

Specifically, I don't understand why if you come across an edge that between nodes $u, v$, and if you see that $u$ and $v$ are already in the same disjoint set, it means there is a cycle.

# Answer
Union find is a data structure (not an algorithm!) that maintains a collection of disjoint sets $\mathcal{S} = \\{ S\_1, S\_2, \dots \\}$ under union operations (i.e., replace two sets with their union) and find operations (given an element $x$, report the set $S\_i$ containing $x$).

Hopefully it is already clear to you that if, at any point in time, two distinct vertices $u$ and $v$ lie in the same set $S\_i \in \mathcal{S}$ then there must be a path $\pi$ from $u$ to $v$ in your input graph $G$.

Suppose then that you are examining a new edge $e=(u,v)$ and you discover that both $u$ and $v$ lie in the same set. We can obtain a cycle $C$ by adding edge $e$ to the path $\pi$. Notice that $C$ lies entirely in $G$, as desired.
> 2 votes

---
Tags: graph-traversal, union-find
---


# Question
Title: Efficiently check if removing an edge splits a strongly connected component
I have a strongly connected component (SCC) of $n$ vertices. Let $n\_1n\_2$ be an edge between two vertices $n\_1$ and $n\_2$ in this SCC. Is there an efficient algorithm to check if removing the edge $n\_1n\_2$ splits the SCC into two SCCs or not? The graph I am using is a directed graph.

# Answer
> 3 votes
An arc is said to be a *bridge* if its removal increases the number of connected components of the graph. Further, an arc is a *strong bridge* if its removal increases the number of strongly connected components. In your case, you are likely interested in finding all strong bridges in a digraph.

A simple $O(n+m)$-time algorithm, where $n$ is the number of vertices and $m$ the number of arcs is given in \[1\] which identifies *all* strong bridges. Section 4 of the paper gives the algorithm.

---

\[1\] Italiano, Giuseppe F., Luigi Laura, and Federico Santaroni. "Finding strong bridges and strong articulation points in linear time." Theoretical Computer Science 447 (2012): 74-84.

# Answer
> 0 votes
Yes, there is a linear time algorithm. After removing $e=(n\_1,n\_2)$ we run DFS twice as follow

First, run DFS from $n\_1$ and check, $n\_2$ reachable from $n\_1$ or not.

Second, run DFS from $n\_2$ and check whether $n\_1$ reachable from $n\_2$ or not.

If after running DFS twice, $n\_1$ reachable from $n\_2$ and $n\_2$ reachable from $n\_1$ we conclude that removing edge $e=(n\_1,n\_2)$ can't change our SCC, but otherwise SCC changed and number of SCC has increased that you can compute SCC again from scratch in linear time. So the running time of DFS is linear and finding SCC is linear, total time is $\mathcal{O}(E+V)$.

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


# Question
Title: sort array with some of the elements in a known range
Let $A$ be an array of n elements. We know that $n - \lfloor \sqrt n \rfloor$ elements are integers in range $\sqrt n$ to $n\sqrt n$ (the other $\lfloor \sqrt n \rfloor$ elements may or may not be in the range). I need to sort the array in $\Theta (n)$.

I thought of partitioning the array to 3 subarray:

1. elements smaller than $\sqrt n$
2. element in range $\sqrt n$ to $n\sqrt n$
3. element bigger than $n\sqrt n$

the first and last subarrays can be sorted with insertion sort in $O(n)$ because there are at most $\lfloor \sqrt n \rfloor$ elements in those arrays. The second array have between $n - \lfloor \sqrt n \rfloor$ to $n$ elements in range $\sqrt n$ to $n\sqrt n$ so using counting sort will run in $O(n\sqrt n)$. Using bucket sort where each bucket has all the elements in subrange with n integers each bucket can be sorted with counting sort in O(n) and there are $\sqrt n$ buckets so the sort will also take $O(n\sqrt n)$.

My problem is how to sort that second array in $O(n)$? I assume it is something to do with the amount of buckets or maybe the subrange of each bucket, as sorting the second array costs $O(number\\\_ of\\\_buckets * O(number\\\_of\\\_elements\\\_in\\\_bucket + number\\\_of\\\_integers\\\_in\\\_range))$

# Answer
Using radix sort, the second subarray can be sorted in $\Theta(log\_{b}(n\sqrt n)(n + b)$ where $b$ is the base with which the numbers are represented. If $n$ is chosen as the base, radix sort sort the array in $\Theta(log\_{n}(n\sqrt n)(n + n)) = \Theta(\frac{3}{2}(n + n)) = \Theta(n)$. Now all 3 subarrays can be sorted in $\Theta(n)$ thus the array is sorted in $\Theta(n)$
> 0 votes

# Answer
It's possible to sort your array in linear time by using a method that use comparison based and non-comparison based sorting algorithms as subroutines.

First, do a linear scan to find all integer number in range $\[\sqrt{n},n\sqrt{n}\]$ and put those elements into array $A'$, and put $\sqrt{n}$ remaining elements into an array $A^{''}$. The running time of this linear scan of the array $A$ is $\Theta(n)$.

So by comparison based algorithm, such as merge sort, sort $A^{''}$ in $\sqrt{n}\log \sqrt{n}$.

Now by using Radix-Sort, you can sort $A'$ in linear time, if you set the base $d=\log\_x $ to $n$ then the running time of radix-sort is $\mathcal{O}\left(\frac{3}{2}\log\_n n(n+n)\right)=\mathcal{O}(n).$

So you have to merge two sorted arrays $A',A^{''}$ that can be merged in $\mathcal{O}(n)$. Consequently, overall running time is $$\mathcal{O}\left(\sqrt{n}\log \sqrt{n}+n\right)=\mathcal{O}(n)$$
> 0 votes

---
Tags: time-complexity, sorting
---


# Question
Title: Is it possible to prove that this algorithm is big Omega $n^2logn$ time complexity?
Considering the following recursive algorithm: $ T(n)= T(\frac{n}{2})+c\_1(\frac {n}{2})^2+c\_2n$. I was able to prove that this algorithm is $O(n^2 logn)$ I was trying to understand whether it is a tight bound or not, yet I was unable to prove that $ T(n)\in \Omega(n^2logn)$ Is it possible or maybe the algorithm's lower bound is $n^2$ ? Any assistance would help a lot as I am trying to crack this for a while now.

# Answer
Your recurrence can be written as: $ T(n) = T(n/2) + f(n) $, where $f(n) \in \Theta(n^2)$.

Then, by case 3 of the Master theorem, you have $T(n)=\Theta(n^2)$. This means that you won't be able to prove a lower bound of $\Omega(n^2 \log n)$.
> 1 votes

# Answer
It's possible that, describe your recurrence as summation:

$$T(n)=T(1)+\sum\_{i=0}^{\log n}c\_1\left(\frac{n}{2}\right)^2\times\left(\frac{1}{2^i}\right)+ \sum\_{i=0}^{\log n}c\_2\left(\frac{n}{2^i}\right)$$ $$=\hspace{4pt}T(1)+\sum\_{i=0}^{\log n}c\_1\left(\frac{n^2}{2^{2+i}}\right)+ \sum\_{i=0}^{\log n}c\_2\left(\frac{n}{2^i}\right)$$

$$=\hspace{4pt}T(1)+c\_1n^2\sum\_{i=0}^{\log n}\left(\frac{1}{2^{2+i}}\right)+ c\_2n\sum\_{i=0}^{\log n}c\_2\left(\frac{1}{2^i}\right)=\Theta(n^2).$$
> 0 votes

# Answer
Your “algorithm” runs in O(log n) time. The function that it calculates is O(n^2).
> -1 votes

---
Tags: time-complexity, lower-bounds, upper-bound
---


title: Reduction with NPH

text:
# Question
Title: Reduction with NPH
I have a question in complexities that I could not do.

There will be D, E, F, three languages belonging to NPH. Suppose that the reductions exist $D \leq \_P E$ and $E \leq \_P F$. Determine which of the following statements is correct:

1. Inevitably there is a reduction $F \leq \_P D$
2. If there was an $F \leq \_P D$ reduction then F, E and D are all in the NPC class.
3. Even if there was an $F \leq \_P D$ reduction, it is still possible that $D \notin NP$.
4. if $F \in CoNP$ then $NP \neq CoNP$
5. None of the above claims are true.

I think the answer is probably 2, because there are reductions between all the problems. So everyone should be in $NPH$, and if a problem is in $NPH$ then it is also in $NPC$. I can not understand why 4 is not true, it also seems logical.

# Answer
> if a problem is in $NPH$ then it is also in $NPC$

This statement is incorrect. A language is in $NPC$ if it is in $NPH$ **and** it is in $NP$.

Answer 4 is incorrect as well since that would imply that any language $L\in NP$ can be reduced to $F$, hence $L\le\_p F$ and since $F\in coNP$ then $L\in coNP$. Hence, $NP\subseteq coNP$. Its not hard to show the other way around, and conclude that this means $NP=coNP$.

Answer 3 is correct. There are $NPH$ problems that is not in $NP$ (for example, take any $NEXP$-complete problem). If you choose $D=E=F\in NPH\setminus NP$ then the reductions are trivial, but they are still not in $NP$.
> 2 votes

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


# Question
Title: Calculation of Inorder Traversal Complexity
I want to analyze complexity of traversing a BST. I directly thought that its complexity as $O(2^n)$ because there are two recursive cases. I mean $T(n) = constants + 2T(n-1)$. However, AFAI research it is $O(n)$. Can you show it how come and my wrong?

```
void printInorder(Node node)
    {
        if (node == null)     // I think it is T(0) = 1
            return;           // constant c

        /* first recur on left child */
        printInorder(node.left);     // T(n-1)

        /* then print the data of node */
        System.out.print(node.key + " "); //constant(c)

        /* now recur on right child */
        printInorder(node.right); //T(n-1)
    }

```

# Answer
> 3 votes
In order to analyse the time complexity of a tree traversal you have to think in the terms of number of nodes visited. If a tree has $n$ nodes, then each node is visited only once in inorder traversal and hence the complexity is $O(n)$.

Here, the input is in terms of number of nodes in the tree and hence the complexity.

The notion that each recursive call is $T(n-1)$ is wrong. Let say we have a tree that has three children to the left of root and three children to the right of root. So n = 7. Now when you visit root then you have two paths. One to left which has 3 children and one to right which also has 3 children. But $7-1 \neq 3$. Hence this notion of 2 recursive calls of $T(n-1)$ is wrong.

It totally depends on the structure of the tree. In worst case a tree may degenerate to linked list (a skew tree having children on only one side either left or right) and we know well that traversal of linked list is $O(n)$, for a list of n elements. Hence, also the worst case is $O(n)$.

# Answer
> 0 votes
The Big-O notation in simple terms could be said as the number of operations performed.

In the recursive function of yours, there are no internal loopings that add to an additional degree of operations. You may trace out this function and see how many times the function call happens which will make you more clear on understanding the recursive function.

Breaking down your function, for each time `printInorder(n)` is called,

* checks if `n` is `null`
* calls `printInorder` on `n -> leftNode`
* prints `n -> value`
* calls `printInorder` on `n -> right node`

So for every call of this function with a particular `n` a maximum of 4 operations are performed. (it will either be 4 if `n != null` and 1 if `n == null`). When you trace down the function on any binary tree, you may notice that the function call happens for (only) a single time on each node in the tree. So you can say a max of `k*n` operations (k \<\< n, k \<= 4 in this case) have been done in this function and so in terms of Big-O has an `O(n)` complexity.

# Answer
> 0 votes
Let $\ell\_x$ be the left sub tree at node $x$, Let $r\_x$ be the right sub tree at node $x$. So the size of $\ell\_x$ is $\mid\ell\_x\mid$, and size of $r\_x$ is $\mid r\_x\mid$.

Let $T(n)$ be number of nodes our procedure visited during in-order traversal.

So when you recurs on the left sub tree at node $x$, the size of problem is $T(n-1-\mid r\_x\mid)$, because we discard right sub tree at node $x$ and just recurs on left sub tree at node $x$. Additionally, we don't traverse $x$, so the recursive formula to describe the time complexity of this line of your code is

```
/* first recur on left child */
        printInorder(node.left);

```

$T(n-1-\mid \ell\_{node}\mid)$.

consequently, recursive formula to describe the next recurs in your code is

```
/* now recur on right child */
        printInorder(node.right);

```

$T(n-1-\mid r\_{node}\mid)$.

The line

```
/* then print the data of node */
        System.out.print(node.key + " "); //constant(c)

```

needs constant time. As a result we can write $T(n)$ as follow:

$$T(n)=T(n-1-\mid r\_{node}\mid)+T(n-1-\mid \ell\_{node}\mid)+1$$

I think above relation can be proved that $T(n)=\Theta(n)$, by induction. But i have no idea at this point.

So it not as the same recurrence relation that you write.

A simply analysis for such a situation is, the procedure visit each node only at once, So the running time is $\Theta(n)$.

---
Tags: graphs, time-complexity, asymptotics, graph-traversal, binary-search-trees
---


# Question
Title: Declarative, interrogative, imperative, and exclamative sentences in computer languages
The following English sentences have different forms (syntax):

* *Declarative:* You are my friend.
* *Interrogative:* Are you my friend?
* *Imperative:* Be my friend!
* *Exclamative:* What a good friend you are!

They also have different meanings (semantics):

* *Statement:* You are my friend.
* *Question:* Are you my friend?
* *Command:* Be my friend!
* *Exclamation:* What a good friend you are!

The form and meaning of a sentence usually match, but not always, as professor of English linguistics Bas Aarts explained:

> Incidentally, you might be interested to know that sometimes we have a mismatch between the structure of a sentence, and how it is used. If I say to you at dinner Can you pass me the salt? then this is technically a question that has ‘yes’ or ‘no’ as possible answers, but in fact the pattern is used here to tell you to do something. It’s because of these possible mismatches that linguists prefer to use two sets of terms to describe the phenomena above. For the sentence patterns they use **declarative,** **interrogative,** **imperative** and **exclamative.** Corresponding to this are **statement,** **question,** **command** and **exclamation** to describe how these patterns are used.

The grammars of *human* languages such as English are flexible enough to allow the four forms of sentences (declarative, interrogative, imperative, and exclamative). I wonder if this also holds true for *computer* languages such as Python, HTTP, SQL, HTML, and CSS.

Are the following sentences declarative? (This seems to exclude HTTP and SQL.)

* Python: `assert x == 3`
* HTTP: ?
* SQL: ?
* HTML: `<!DOCTYPE html><html lang=""><title>x</title>`
* CSS: `h1 { font-size: 3rem; }`

Are the following sentences interrogative? (This seems to exclude HTML and CSS.)

* Python: `x == 3`
* HTTP: `GET / HTTP/1.1\r\nHost: domain.org`
* SQL: `SELECT x FROM relation;`
* HTML: ?
* CSS: ?

Are the following sentences imperative? (This seems to exclude HTML and CSS.)

* Python: `x = 3`
* HTTP: `PUT / HTTP/1.1\r\nHost: domain.org\r\n\r\n{"x": 3}`
* SQL: `INSERT INTO relation (x) VALUES (3);`
* HTML: ?
* CSS: ?

Are the following sentences exclamative? (This seems to exclude all languages.)

* Python: ?
* HTTP: ?
* SQL: ?
* HTML: ?
* CSS: ?

If that is so, it means that Python is the most flexible computer language (declarative, interrogative, and imperative), followed by HTTP and SQL (interrogative and imperative), and HTML and CSS are the least flexible (only declarative).

# Answer
The grammatical classification of the sentence types you're asking about isn't well-defined for programming languages because they refer to common ways humans respond to being talked to, which don't apply closely to computers.

The declarative, interrogative, imperative and exclamative grammatical forms are so named because those are the purposes to which they are usually put by people using them. An interrogative form may often carry a connotation that its content is a question, but compared to programming languages the semantics of natural language are so vastly complex that it's difficult to assign a singular meaning to any syntactic property of sentences.

Statements of programming languages on the other hand are generally held to have specifically identifiable meanings, ie. the machine instructions that are executed as a result of entering them. But if the Church-Turing thesis is to be believed, there is some possible computer whose behaviour (in terms of input-output) is the same as any given human mind's, and for that computer there is an exact mapping of natural language inputs to machine instructions\*. So why do we not say that natural languages are programming languages for brains? Because it may be true that speaking to someone is an attempt to use the effect of language to change how they act, but people are too complex for that to be a useful way of looking at it. You may as well try to describe the growth of a plant in terms of the subatomic particles that make it up.

A computer on the other hand is simple enough to be predictable. When you 'speak to' a computer, you know with considerable accuracy (maybe total exactness if you happen to be an expert on a particularly simple system) what effect that will have on the 'listener', and so have near-total control over what the 'listener' 'thinks'. If *communication is violence*, programming is premeditated murder.

\*Accounting for the fact that successive inputs can change state. This is true of computers as well, it just happens that the changes are limited and predictable and there are convenient ways to reset to a known state.
> 2 votes

# Answer
I see the misconception. We have a name collision, where the same word is used to mean two different things in two different contexts.

When Wikipedia says that SQL is a declarative programming language, that has little or nothing to do with the notion of a declarative sentence in English / natural language. Despite both appearing to use the same word "declarative", the meaning of "declarative" is entirely different in these two contexts.

In computer science, we make a loose distinction between declarative programming languages vs imperative programming languages. In a declarative programming language, the programmer specifies what should be accomplished (the goal) without specifying how to achieve it. In an imperative programming language, the programmer specifies how to achieve it. It would be like the difference between saying "Give me a 1-pound cake that is round and tastes like chocolate" vs "Mix 1 cup flour, 2 eggs, 1 cup sugar, 1/2 cup cocoa powder, etc., cook in oven at 350 degrees, etc. etc.".

The word "language" is another of these that might cause problems. While we use the word "language" to describe both a programming language (like Python) and a natural language (like English), the analogy between those two is a bit loose, and I encourage you to not put too much weight on it. Computer programming languages have some similarities, but also many differences, from human natural languages.
> 1 votes

---
Tags: formal-languages, imperative-programming
---


# Question
Title: Relationship between complexity classes W[1] and NP?
I am trying to understand the connection between *The W-hierarchy* as presented in chapter 13 of this book by Cygan et al. and the notion of the *NP* problems.

Is the existence of an FPT algorithm for a problem in *W\[1\]* suggests that *P=NP*? Why?

For example, assuming I have an FPT algorithm for the *k-Clique problem*. Can I prove the *P=NP*? The algorithm run time will still be exponential. Only now, it will depend on $k$.

# Answer
Because $k$-CLIQUE is W\[1\]-hard, your result would imply that FPT = W\[1\], which by the result of Downey and Fellows \[1\] implies that the Exponential Time Hypothesis (ETH) is false, i.e., that 3-SAT *can* be solved in $2^{o(n)}$ time. But ETH is stronger than P not equal to NP, so its falsification doesn't settle P = NP (but of course, if true, ETH would imply that P is not equal to NP).

As far as I know, FPT = W\[1\] is not known to imply anything else regarding the W-hierarchy.

---

\[1\] Downey, Rodney G., and Michael Fellows. Parameterized complexity. Springer Science & Business Media, 2012.
> 2 votes

# Answer
If $\mathrm{FPT}=W\[1\]$, then we will not directly get an answer to $\mathrm{P}$ vs. $\mathrm{NP}$ (or at least, not that we know). The assumption that $\mathrm{FPT} \neq W\[1\]$ is a weaker claim than $\mathrm{P}\neq \mathrm{NP}$:

If $\mathrm{P} = \mathrm{NP}$, then there is polynomial time algorithm for the $W\[1\]$-complete problem $k$-Clique, so $\mathrm{FPT}= W\[1\]$. Taking the contrapositive, we get that $\mathrm{FPT}\neq W\[1\]$ implies $\mathrm{P}\neq \mathrm{NP}$.

Taking a step back, the entire concept of fixed parameter tractability implicitly assumes that there are problems for which we cannot obtain a polynomial time algorithm. By applying this concept to NP-complete problems, we make the assumption that we are unable to prove $\mathrm{P} = \mathrm{NP}$. While this argument does not rule out a proof of $\mathrm{FPT}=W\[1\]$ implies $\mathrm{P} = \mathrm{NP}$, it does not seem natural that a collapse of complexity classes designed to give more fine-grained results when $\mathrm{P}\neq \mathrm{NP}$ would imply $\mathrm{P} = \mathrm{NP}$.
> 2 votes

---
Tags: np, parameterized-complexity
---


# Question
Title: What is the origin of the Bottom Type notation? Why does it look like... a bottom?
I couldn't help but notice the opening summary in Wikipedia's article on Bottom Types:

> In type theory, a theory within mathematical logic, the bottom type is the type that has no values. It is also called the zero or empty type, and is sometimes denoted with the up tack (⊥) symbol.

Is the visual similarity to an *actual* bottom intentional? Or just an amusing coincidence?

# Answer
The symbol $(\bot)$ usually represents **the** **least element** of a lattice. The least element often goes at the bottom part of a Hasse diagram. That is maybe the reason you're looking for. For example, in a Hasse diagram containing propositions with the logical consequence relation, one usually put falsehood, ***at the bottom of the diagram***, mostly because from a falsity, any statement follows.
> 2 votes

---
Tags: type-theory, notation
---


# Question
Title: What is the best hash functions for millions of String keys?
I have a situation where there are a million Keys of type String and I want to use the Symbol table to store the key and the value.

The problem that the retrieval process is too slow and I want to improve the retrieval. I wonder if there is a good hash function to help me with this task.

I am using `Separate Channing` for resolving the collision

the current hash function

```
hash = 0
for i = 0 : strlen
    hash = hash * 31 + getChar(strlen, i)

```

So My question: Is there a better hash function to minimize the collision between the keys?

# Answer
> 2 votes
It's impossible to say without knowing the properties of your keys. Programming language symbol tables tend to need to store a bunch of strings that look like `i`, `j`, `x1`, `x2`, `y1`, `y2`, etc. Simple hash functions often don't disambiguate these well.

There are plenty of hash functions out there. PJW hash/ElfHash is popular for programming languages because it was designed to handle the above cases well.

If you do have millions of keys, probably the best way to do it is to measure the hash chain lengths and see if they follow a Poisson distribution. If you are storing $m$ items in $n$ hash slots, then the number of hash slots with $k$ elements should follow a Poisson distribution with parameter $\lambda = \frac{m}{n}$.

You can test to see if a measured distribution follows an expected distribution using the Pearson $\chi^2$ test.

# Answer
> 1 votes
The best way to avoid collisions is to keep the number of slots large enough. You say "retrieval is too slow" - how slow? You need at the minimum one calculation of a hash key, one comparison, plus one comparison per collision. If you have more than one collision on average, either your hash table doesn't have enough slots, or something is very wrong with your hash function, or something is strange about your data.

BTW. Your hash function will be awful if you add 255 x 255 x 255 strings of three characters to your hash table. I hope you can figure out why, and why Bulat's is a lot better in that case.

But then there is the question: Have you profiled your code? If not, you are operating blindly. Measure how long your code takes, and how long what parts of the code take.

PS. Some standard libraries for various languages have started to use randomised hashes. So every time you start your application, you get a new set of hash functions. (As a consequence, you shouldn't ever store hash codes permanently, because they are invalid if your application starts again). This seems to have some significant advantages, mostly that worst case behaviour won't be permanent. Image 20 of your 25 employees have names whose hash functions collide - randomisation makes sure this will only happen once, and the next time your app is fine.

# Answer
> 0 votes
hash = (hash + getChar(strlen, i)) * 123456791

# Answer
> 0 votes
Hash calculation could be accelerated, if string was interpreted as int array (using word-sized type), striding with int until the end of string, doing rest with char.

Omiting possible need for strlen, I estimate effect comparable with simd, used for number crunching. Any string with less length than int size would not need any calculations at all. Though even with strlen - acceleration should be notable, especially with complex hash functions.

```
char s[] = "...";
unsigned long long hash = 0;

char     *c = s;
unsigned *i = (void *)s;
int stride = 0;

while (; *c; ++c) {
  stride++;
  if (stride == sizeof(*i))
  {
    hash = ((void*)i > (void*)) ? i[0] : hash * 31 + i[0];
    i++, stride=0;
  }
}

c = (void *)i;

while (; *c; ++c)
  hash = hash * 31 + c[0];

```

I did not try to even compile it, so don't mindless copy-paste.

Update: simpler approach with length, calculated separately

```
#include <stdlib.h>

char s[] = "...";
unsigned long long hash = 0;

int len = strlen(s);
unsigned long *u = (void *)s;

ldiv_t len_u = ldiv (len, sizeof(*u));

for (int i = 0; i < len_u.quot; i++)
    hash = hash * 31 + u[0];

for (int i = len - len_u.rem - 1; i < len; i++)
    hash = hash * 31 + s[i];

```

And using unsigned auto variable as some kind of buffer

char s[] = "...";
unsigned long long hash = 0;

unsigned buf; // processing unit
char *sp, c;  // string pointer & current string
int i;        // position in buf

sp = s;
i = 0;

while (( c = *sp ))
{
  ((char *)&buf)[i] = c;
  i = (i + 1) % sizeof(buf);
  if (!i) {
    hash = hash * 31 + buf;
    buf = 0;
  }
}
if (buf)
  hash = hash * 31 + buf;
```

---
Tags: optimization, hash, hash-tables
---


# Question
Title: Reducing subsetsum to {<G, l, u> | G is a weighted graph that has a spanning tree with weight between l and u}
How can I reduce Subsetsum (or maybe other np-complete problem) problem to the problem below?

**input :** a weighted graph $G$ and numbers $l$ and $u$.
**output :** Does $G$ has spanning tree, $S$, such that $l \leq \mathrm{weight}(S) \leq u$?

# Answer
Let $X = \\{ x\_1, x\_2, \dots, x\_n \\}$ be the (multi-)set of elements in your subset-sum instance and let $t$ be the target value.

Create the undirected graph $G=(V,E)$ where $V=\\{a,b\\} \cup X$ and $E = ( \\{a,b\\} \times X) \cup \\{(a,b)\\}$. The weight of edge $(a, x\_i)$, for $x\_i \in X$, is $x\_i$. The weight of edge $(b, z)$ for $z \in \\{a\\} \cup X$ is $0$. Finally, pick $l=u=t$.

There is some $Y \subset X$ such that $\sum\_{x\_i \in Y} x\_i = t$ if and only if there is a spanning tree $T$ of $G$ of total weight between $l$ and $u$.

Indeed, given $Y$, you can select $T$ as the tree induced by the edges in $\\{(a,x\_i) \mid x\_i \in Y\\} \cup \\{(b,z) \mid z \in V \setminus Y\\}$. Moreover, given a tree $T=(V,F)$ of total weight between $l$ and $u$, you can select $Y = \\{ x\_i \mid (a,x\_i) \in F \\}$.
> 0 votes

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


title: Language in NPC and CoNP

text:
# Question
Title: Language in NPC and CoNP
A few days ago I had a test that I failed to pass, and it had a question that I failed to do.

the question:

given:

$A \in NPC$

$A \in CoNP$

Determine which of the following statements is correct:

1. $P\neq NP$
2. $P\neq CoNP$
3. $NP\neq CoNP$
4. $NP=CoNP$
5. None of the above claims are true.

My idea to solve this, is to choose a language $B \in P$. From language $B$ it is possible to make a reduction to both problems to $CoNP$ and $NPC$. And take the complementary B language, $B^{'}$, which also belongs to the 2 groups.

Because B and B complement an identity then, it is possible to get that $NP = CoNP$ and $NPC = CoNPC$ , but I do not know if I am right in this solution.

I think 4 is the correct answer, but I do not know why the other answers are incorrect.

# Answer
Let $L\in NP$. Thus, $L\le\_p A$. Since $A\in coNP$, then $L\in coNP$. Hence, $NP\subseteq coNP$.

Now, let $L\in coNP$. Thus, $\overline{L} \in NP$ and therefore $\overline{L}\le\_p A$. From reduction properties, we know that $L\le\_p \overline{A}$ holds as well. Now, since $A\in coNP$ then $\overline{A}\in NP$. Hence, $L\in NP$, and therefore we get that $coNP\subseteq NP$

Now we can conclude that $NP\subseteq coNP$ and $coNP\subseteq NP$ and hence $NP=coNP$.
> 2 votes

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


title: edge-coloring reduction problem

text:
# Question
Title: edge-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 3 parts, but they are related to each other, so I can not ask each question separately.*

Section A

If the G edges can be painted in k colors, in how many colors the vertices can be painted in $\widetilde{G}$

1. k
2. 3k
3. k^2
4. |V|+1
5. none of the answers is correct.

*`I think the correct answer is k, in graph G we have to color the edges, every edge in G becomes a vertex in`*  $\widetilde{G}$, *`and every vertex in G becomes an edge in`* $\widetilde{G}$, *`which means there is symmetry. If in G the edges need to be painted in K colors then in`*  $\widetilde{G}$ *`the vertices need to be painted in K colors`*

Section B

Is this a polynomial reduction?

1. yes.
2. No, the amount of edges may be quadratic as a function of the amount of vertices.
3. No, the amount of edges may be exponential as a function of the amount of vertices.
4. You can not tell, depending on the size of the graph
5. none of the answers is correct.

*`I think the correct answer is Yes , Each adge in G becomes a vertex in`*  $\widetilde{G}$ , *`a polynomial runtime as the size of the | E |. After this each edge in E can be connected to 2 vertices, and each vertex can be connected to all the other edges. For each edge we will check if it is connected to the other edges, running time of | E |^2.`*

Section C Is the reduction correct and well defined?

1. Yes, reduction correct and well defined
2. Although the reduction is correct, but it does not deal with cases where the original graph G was empty (without edges)
3. Although the reduction is well defined for all graphs, it is incorrect when the number of edges is evaluated as a function of the number of vertices.
4. No
5. none of the answers is correct.

*`I feel like the answer is 1., but I have no explanation for it, here I actually think I'm stuck. How can you check that reduction correct and well defined?`*

*`I think this is a very easy question, but I could not answer it, thank you very much.`*

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

# Answer
To see whether a "reduction is correct and well-defined", first look at the definition: what is a reduction? In this case, you require a so-called Karp reduction or a polynomial-time reduction from Edge-Coloring to Vertex-Coloring. In particular, it must hold that (i) the process runs in polynomial time and (ii) an instance $G$ of Edge-Coloring has a solution precisely when the instance $G'$ of Vertex-Coloring has a solution.

Let's consider the questions A, B and C:

* Question A: You should have a look at my answer to question C here first. Your intuition looks promising, but you should formalize (i.e., prove) it.
* Question B: You are correct, the reduction is easily doable in polynomial time.
* Question C: The construction is describing the construction of the line graph of $G$. Your task is to prove that $G$ has an edge $k$-coloring if and only if $G'$ has a vertex $k$-coloring. Do this in two parts: given an edge $k$-coloring of $G$, show how you can build a vertex $k$-coloring for $G'$. Then show the reverse direction, i.e., that a vertex $k$-coloring for $G'$ gives you an edge $k$-coloring for $G$. This is a good exercise, so I won't ruin (all) the details for you. **Hint**: in the first direction, start by giving the vertices $x\_e$ the color on $e$. In the reverse reduction, what can you say about the coloring if you restrict it to the vertices $x\_e$, i.e., what does this imply for the edges $e$ in $G$?

If you feel stuck, look at examples of some other reductions to get the idea.
> 2 votes

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


# Question
Title: Complexity of the language that enters an infinite loop
A few days ago I had a test that I failed to pass, and it had a question that I failed to do.

This is the question

Let's look at the language $L\_\mathrm{loop} = ${ $\left \langle M,w \right \rangle$ | When $M$ is activated on the input $w$, the machine $M$ enters an infinite loop }

We will mark our input length: $|\left \langle M,w \right \rangle| = n$. Determine which of the claims is correct:

1. The language is in $\mathsf{P}$
2. The language is not in $\mathsf{NP}$ or $\mathsf{CoNP}$.
3. The language is in $\mathsf{NP}$ but not in $\mathsf{NPC}$.
4. The language belongs to $\mathsf{CoNP}$.
5. None of the above claims are true.

From what I understand in the question, there is a language that accepts Turing machines that go into an endless loop.

1. It cannot be, if the machine works infinitely, it is impossible to know in polynomial time when we will get yes and when we will get no. It has no algorithm.
2. Probably can not either. A problem will be in $\mathsf{NP}$ if it has a non-deterministic guessing algorithm. If a witness gives input, it is not possible to say yes to the answer, because it is infinite.
3. Do not know about it, maybe he is right
4. Language should belong to $\mathsf{CoNP}$ only when a guessing algorithm should say no. And I do not know if here should be said no and then it's $\mathsf{CoNP}$ or say yes and then it's $\mathsf{NP}$.

I tried to figure out what the answer might be, but I could not figure out the answers to the question.

Maybe 5 is right, because I could not tell everyone else that they were right

# Answer
> From what I understand in the question, there is a language that accepts Turing machines that go into an endless loop.

We do not say a language "accepts" something. Rather the language contains all pairs of turing machines and words, where the TM runs forever (which I take "infinite loop" to mean) on the word.

Also, note that you can define any language, but there doesn't necessarily exist a TM that accepts that language.

$L\_{Loop}$ is undecidable because you can reduce the halting problem of a TM $A$ on $w$ to it. Clearly, $\langle A, w \rangle \not\in L\_{Loop}$ iff $A$ halts on $w$.

We know that the halting problem is undecidable. If $L\_{Loop}$ was decidable, so would be the halting problem. Therefore, $L\_{Loop}$ is undecidable, i.e. there exists no algorithm to decide for all words whether they are in the language.

If there's no algorithm, the language can't be in NP, thus 1 and 3 are wrong immediately. As we have just seen, the complement of $L\_{Loop}$ is the halting problem, so 4 is wrong too. The rest should be clear.
> 2 votes

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


title: Generating Unique Ids for Objects

text:
# Question
Title: Generating Unique Ids for Objects
I have an Object Pool and I will be using it to create Objects. I want to generate an unique id for each object. id should be an integer starting from 0. Ids should be continuous. When an object is deleted that id should be reusable. So that next object created can reuse that id instead of a new id.

And also if there are too many objects deleted this can result in too many reusable ids. For example we created 10 objects. with id 0 to 9. Lets say object with id 2 and object with id 4 are deleted. So ids 2 and 4 are now reusable. And it would be nice if it was possible to shift ids such that object with id 3 will use id 2. and object with id 5 will use id 3 like that. So in the end last id will be 7. Is there any algorithm which makes it possible to do this efficiently? Id generation in O(1) and id shifting in O(n)

# Answer
A simple observation is that when an object is assigned an id, that id never increases, i.e., it either stays the same or decreases. So keep a global counter $g$ for giving ids, initially set to 0.

Let $A$ be your list of indices (or objects). Consider a deletion event $D$ consisting of ids you want to delete. To reindex, scan $A$ starting from the 0th index. Whenever $i \in D$, delete the corresponding entry in $A$ and increment a counter, say $d$, initially set to zero. For each subsequent index $j \> i$, decrement each entry by $d$ (again, if you encounter an index you must delete, you decrement $d$ etc.).

So let me describe the basic idea with $A = \[0,1,\ldots,9\]$. Let $D = \[2,4\]$. Scan $A$, and at $i = 2$ set $d = 1$ and $A = \[0,1,x,3,4,5,6,7,8,9\]$. Continuing from $i=3$, we get $A=\[0,1,x,2,4,5,6,7,8,9\]$. Next, at $i = 4$, we mark $A\[i\]$ deleted and get $d = 2$. Thus, we are left with $A=\[0,1,x,2,x,3,4,5,6,7\]$. As $d = 2$, we update $g$ to $g - d$.

We can implement the above by looping over the elements in $D$. If $i'$ is the index in $D$, mark $A\[i'\] = x$, increment $d$ by one, and scan $A$ until $j' \> i'$ where $j'$ is the next index in $D$ (or if there is no $j'$, scan until the end of $A$), and decrement each element of $A$ by $d$. You can implement this scheme to run in $\Theta(n)$ time, where $n$ is the number of elements in $A$. Indeed, we scan over $D$ once (and note that $|D| \leq |A|$ as it only contains indices to $A$) and also scan over $A$ once, essentially only skipping as many elements from the beginning of $A$ as the first index $i'$ in $D$ lets us. Finally, as $g$ is always kept up to date, you can generate new ids in $O(1)$ time too.

So with this implementation, the above example becomes as follows. Loop over $D$, i.e., start at $i' = 2$. Mark $A\[i'\] = x$. Check that $j' = 4$, so decrement $A\[3\]$ by one and mark $A\[j'\] = x$. Now, we see that there is no $j'' \> j'$, so decrement each $A\[\ell\]$ by two, for $j' + 1 \leq \ell \leq n$. Set $g := g - 2$ and halt.
> 2 votes

---
Tags: algorithms, ordering
---


title: Finding largest elements

text:
# Question
Title: Finding largest elements
I was asked to find write a pseudocode of an algorithm that extracts the Log(N) largest elements in an array and return them in a sorted list, my attempt is

```
largestLogn(Arr)

n = Arr.length
j = 0
ans = new array of size Log(n)

Arr = Quicksort(Arr,1,a)

for i=(a-log(n)) ➜ a
ans[j] = Arr[i]
j++

return ans

```

From my limited understanding, the time complexity of this algorithm is $O(n\log n)$ for the QuickSort and $O(\log n)$ for the loop but in the question they hinted that the time complexity has something to do with the fact that $(\log(n))^{a}=O(n^{b})$ for any $a,b\>0$ and now I'm not sure of my answer.

# Answer
The second loop in your solution requires time $O(\log n)$ and can be safely ignored since its time complexity is dominated by the previous sorting step.

The call to Quicksort requires time $O(n \log n)$ in expectation and $O(n^2)$ in the worst case.

You can solve your problem in $O(n)$ worst-case time as follows: create a max-heap with the elements in the array. Then, perform $\log n$ extract-max operations. Creating the heap takes $O(n)$ time while each of the maximum extractions requires $O(\log n)$ time, for a total time of $O(n + \log^2 n) = O(n)$.
> 2 votes

# Answer
Assume the array elements are in random order. Create a sorted array of size log n. Insert the first log n items. Then insert the next elements if they are larger than the smallest element in that array.

Estimate how often the k-th element of a random array is within the (log n) largest elements so far, and how much work is done in that case. You’ll find the total time for this is quite small and the total time is O(n).
> 1 votes

# Answer
 Below method, solve your problem in $\mathcal{O}(n)$, and additional space $\mathcal{O}(n)$.

Use Selection algorithm to find $(\log n)^{th}$ largest element in worst case $\mathcal{O}(n)$.

Then your array become below form :

That we partition the array in term of $(\log n)^{th}$ largest element. Now all elements in $L$ are greater equal to $(\log n)^{th}$ largest element. On the other hand, all elements in $R$ are smaller than $(\log n)^{th}$ largest element, so we can discard $R$. now we have $\lg n$ largest elements that can be sorted in camparision model in $\mathcal{O}(\log n\log\log n)$ by algorithm such as merge sort. But because we need $\mathcal{O}(n)$ to partition the array, So the term $\mathcal{O}(n)$ dominate other terms and the running time is $\mathcal{O}(n)$ that is better than your idea in large datasets, but for small datasets, it has constant factor that maybe not worth.

**Note that, the lower bound for solving you problem is $\Omega(n)$ because we need at least once read all $n$ elements, so you can't do better.**
> 0 votes

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


# Question
Title: Data transfer between CPU, RAM and secondary storage
Could someone explain me how the CPU address the secondary storage? If the CPU needs data that are stored on a HDD (for example), could the CPU address the HDD directly? And the data are transfered directly to the CPU or are first copied into RAM? I'm talking about a system without DMA. Thank you

# Answer
> 2 votes
When you say that a system doesn't have DMA, you are talking about very old hardware that isn't very pertinent today.

The newest system without DMA I know of is PIO mode that all ATA (including SATA) drives must support to be compliant (https://wiki.osdev.org/ATA\_PIO\_Mode).

In PIO mode, the drive is controlled using some IO ports. These are small registers apart from RAM that the CPU writes with some values to trigger read/write cycles. This is why the CPU is involved in the operation. The CPU needs to read an IO port to get the data that have been read. This is as opposed to a system with DMA where the disk controller (AHCI) reads and writes to/from RAM directly.

The AHCI from intel is a PCI device connected to the PCI bus. It is a DMA device. All disk transfers today are DMA

**EDIT**

I recommend you read the article about PIO mode (Programmed Input/Ouput) of ATA disks. This article takes you step by step to understand how to address the hard-disk in PIO mode with LBA (Logical Block Addressing).

I'll answer for x86 since I am more aware. Basically, the CPU has special instructions which allow a programmer to output or input data to small registers (IO ports) on the motherboard which have conventional numbers. There instructions are the `out` and `in` instructions. These instructions have special opcodes in the CPU.

These IO ports are connected to the disk controller of the hard-drive and, when you write certain values to them, the hard-drive reacts in certain ways. For example, you can write 0x24 to IO port 0x1f7 to trigger read/write cycles to/from an any ATA drive with the following:

```
mov dx, 0x1f7
mov al, 0x24
out dx, al

```

Once the transfer is complete, an interrupt is fired. The CPU then needs to read a specific IO port several times to transfer the data in one of its registers. It then needs to use a `mov` instruction to move the data from the register to RAM. The part in the PIO mode article which does the reading is the following:

```
.data_rdy:
; if BSY and ERR are clear then DRQ must be set -- go and read the data
    sub dl, 7       ; read from data port (ie. 0x1f0)
    mov cx, 256
    rep insw        ; gulp one 512b sector into edi
    or dl, 7        ; "point" dx back at the status register
    in al, dx       ; delay 400ns to allow drive to set new values of BSY and DRQ
    in al, dx
    in al, dx
    in al, dx

```

Again, this is how is used to work. Today, things get more complex. Today, all systems ship with a separate PCI (Peripheral Component Interconnect) compliant chip called AHCI (Advanced Host Controller Interface). The AHCI (https://www.intel.ca/content/www/ca/en/io/serial-ata/serial-ata-ahci-spec-rev1-3-1.html) is a PCI device used to control modern SATA drives. As stated on the link I provided:

> This specification defines the functional behavior and software interface of the Advanced Host Controller Interface (ACHI), which is a hardware mechanism that allows software to communicate with Serial ATA devices. AHCI is a PCI class device that acts as a data movement engine between system memory and Serial ATA devices.

The AHCI chip is present on most if not all x86 computers today and is manufactured by Intel. I am pretty confident you have an AHCI on your computer currently and that this is what your OS is using to communicate with your hard-drive. PCI works with MMIO (Memory Mapped IO). When the CPU sets certain lines of its address bus and outputs data on the data bus, it will write the data to PCI devices instead. Basically, you write to some conventional position in RAM to write to the PCI devices.

To find an AHCI, you:

1. Find the base address of the PCI configuration space using the MCFG ACPI table;
2. Use the PCI registers there to determine if there are several PCI host controllers. If there is only one, you scan bus 0 only. Otherwise, you scan each function of the first PCI host controller to determine if there is something there and scan the bus associated with the other controllers (most often you will scan only bus 0 because there will be only one host controller). Every PCI device (including host controllers) are present on a PCI bus and each bus can have up to 32 devices and each device can have up to 8 functions. Read my answer here for more info: When are a controller's registers loaded and ready to inform an I/O Operation?
3. Determine the function is an AHCI by reading the class id and subclass id fields of each function on the buses you find.

Once you found an AHCI, you will read/write to some registers in its configuration space to trigger read/write cycles directly to/from RAM. The AHCI specification is quite simple compared to the xHCI (USB controller). Maybe start by reading it and you'll have a good understanding. Once a transfer is done, the AHCI will trigger an interrupt using the MSI-X capability of PCI devices.

---
Tags: cpu
---


# Question
Title: What kind of binary compatibility is present for 2 processors sharing an Instruction Set?
Consider Intel x86 and AMD x86 Processors. As I understand, since they use the same Instruction Set, in theory an application compiled for Intel x86 processor would run without any modification on AMD x86 processor, even though these processors have different microarchitectures. Is my understanding correct? Or is there any exception to this rule?

# Answer
Most binaries compiled for x86 will work on x86 because all x86 processors have the same binary instruction format.

Instruction set extensions are quite rare and happen after several consultations between the different vendors. For example, one of the most famous extension is the AES encryption extension to the x86 instruction set called AES-NI and developed by Intel. Both AMD and Intel added the extension to their processors in 2010.

> The AES-NI instruction set extensions are used to optimize encryption and decryption algorithms on select Intel and AMD processors. Intel announced AES-NI in 2008 and released supported CPUs late 2010 with the Westmere architecture. AMD announced and shipped AES-NI support in 2010, starting with Bulldozer.

It isn't really true that extensions make x86 CPUs non-compatible because most extensions will be adopted by major vendors in the same year or so.

> Code written to take advantage of extensions usually run only under compilers written by the vendor. For example, to take advantage of Intel Extensions you need to use the Intel Compiler, which won't work for AMD processors.

This is not really true. There is no "Intel compiler". Instead, you use an existing compiler with extensions in the compiler. It is up to the compiler to support an extension or not. Most of the time when developing software, you know the CPU you target and you assume that most clients won't be using a very old CPU. You thus simply assume that the targeted CPU supports a certain extension. For example, as to AES, most CPUs support AES-NI. You can safely assume that a user of your code has this extension on their processor and can thus use the extension.

In g++, you have the `-maes` flag which allows to enable the AES-NI extension. You will thus be able to use these instructions either in inline assembly or let the compiler do it using certain optimization levels. This probably requires looking at the assembly output and doing some testing and reading g++ documentation. I'm not this much aware so I can't tell how that works exactly but you can have a look at an actual implementation here: https://stackoverflow.com/questions/32297088/how-to-implement-aes128-encryption-decryption-using-aes-ni-instructions-and-gcc.

The micro-architecture is how the ISA is implemented in the processor. It varies greatly between vendors. Both AMD and Intel have the same registers though (which could be considered a part of the micro-architecture). There exists several Model Specific Registers (MSR) and these are called differently from Intel or AMD. For example, there exists an MSR to do a system call in the kernel (https://stackoverflow.com/questions/66853510/who-sets-the-rip-register-when-you-call-the-clone-syscall/66863181#66863181). In Intel documentation it will be called IA32-LSTAR while for AMD it will be called LSTAR or STAR64. Both registers have the same number tough. Again, you have a good compatibility.

In your answer at first, you assumed that instructions to "talk to hardware" were different (for device drivers). This is also not commonly true. Today, most devices have very strong conventions that they must follow in order to be compatible with the computers they will be plugged in. For example, you have PCI for most peripherals, SATA for hard-drives, DDR3 for RAM, USB for other peripherals, ACPI for hardware detection and power management etc.

In most computers today, the only difference between using an AMD processor or an Intel processor is in the detection of the different hardware and the base addresses you are going to use to "talk" to this hardware. This could be considered a difference. For example, the base address of the PCI configuration space could be different between an AMD or an Intel processor. I'm not a hardware engineer but this is not necessarily due to the processor but mostly due to the motherboard or other components. Again, there is very good compatibility. The only difference it makes is that code written to detect PCI devices should take in consideration that the base address could change between computer and only use "relative" code as opposed to "absolute" code (use relative addresses instead of absolute and not assume that the address will be the same everywhere).
> 2 votes

# Answer
As a trivial problem, you can write a program that will try to print on which processor it is running, how many cores, how much memory etc. Such a program should obviously produce different results on an x86 and an AMD CPU.

On the other hand, it is quite possible to write code that runs correctly on a variety of very similar processors. AMD and x86 being "very similar" and not identical.

Many processors are based on some basic architecture, plus some extensions. Many developers check what extensions are available, and use them in order to get faster code by using those extensions. Now the set of bugs in the code that runs when the extension is available, and when it's not available, can be different, so behaviour could change.
> 0 votes

---
Tags: computer-architecture, compilers, instruction-set
---


title: Reduction to a parameterized problem

text:
# Question
Title: Reduction to a parameterized problem
I'm trying the following question from my homework:

We're given a graph $G$ and parameters $k,\hat{P}, \hat{W}\in \mathbb{N}$. Additionally, each $v \in V(G)$ has a profit and weight: $p\_v, w\_v\in \mathbb{N}$.

Suppose you're given an $f(k) \cdot n^{O(1)}$-time algorithm $\mathcal{A}$ which finds whether there is a vertex cover $X\subseteq V$ with: $$|X| \leq k,\quad \sum\_{v\in X} P(v)\geq \hat{P},\quad \sum\_{v\in X} W(v)\leq \hat{W}$$ where $$P(v) = \sum\_{s\in \\{v\\}\cup N(v)} p\_s $$ $$W(v) = \sum\_{s\in \\{v\\}\cup N(v)} w\_s $$

The task is to find a polynomial-time algorithm that solves Knapsack (the decision version) using $\mathcal{A}$.

My attempts - given n items with profits and weights, $p\_i, w\_i$:

1. Define a graph $G$ with 0 edges, where each vertex corresponds to an item. Now run $\mathcal{A}$ on $G$ with $k=n$. Clearly, the problem here is that the running time would be $f(n) \cdot n^{O(1)}$ \- depends of $f$ whether the time is polynomial.
2. In this attempt we'll try to run $\mathcal{A}$ multiple times. Define a graph $G$, where each vertex corresponds to an item. Now we'll consider every possible option for edges between $v\_1$ to the other vertices and for each option we run $\mathcal{A}$ with these graphs and $k=1$. Now do the same for all possible edges between $v\_2$ and all other vertices, and so on. This will take $n\cdot 2^{n-1}\cdot f(1)\cdot n^{O(1)} = 2^{n-1}\cdot f(1)\cdot n^{O(1)}$ \- again, not polynomial.

Is it even possible to come up with a polynomial-time algorithm using $\mathcal{A}$?

Any idea (even if not an exact solution) would be very appreciated!

# Answer
Showing such an algorithm exists would prove $P = NP$.

We show that an algorithm $\mathcal{A}$ does indeed exist. An algorithm to decide vertex cover in $O(2^kkn)$ is known. We can modify it for the extended vertex cover from the question:

```
Ext-Vertex-Cover(G, k) {
    S = new k-sized stack
    return Ext-Vertex-Cover-Rec(G, k, S)
}

Ext-Vertex-Cover-Rec(G, k, S) {
   if (G contains no edges) return (check if S fulfills sum constraints)
   if (G contains ≥ kn edges) return false

   let (u, v) be any edge of G
   push u onto S
   a = Ext-Vertex-Cover-Rec(G - {u}, k-1, S)
   pop S
   push v onto S
   b = Ext-Vertex-Cover-Rec(G - {v}, k-1, S)
   pop S
   return a or b
}

```

Push and pop is $O(1)$. Checking the sum constraints takes additional $O(kn)$ per invocation, keeping overall run-time at $O(2^kkn)$. Thus, for $f(k) = 2^kk$ this is a suitable algorithm $\mathcal{A}$.

Then, since knapsack is NP-complete, finding a polynomial-time algorithm for knapsack using $\mathcal{A}$ would imply $P = NP$.
> 1 votes

---
Tags: undecidability
---


# Question
Title: Prove that $f(n)$ is $= \Omega(g(n))$ but not $= O(g(n))$
I am trying to prove the following statement.

if $\displaystyle \lim\_{n\rightarrow\infty}\frac{f(n)}{g(n)}= \infty$, then $f(n) = \Omega(g(n))$ but $f(n) \neq O(g(n))$

---

## What I've done so far

---

Using the definition of limit: $\forall M\>0 \quad \exists n\_0 : \forall n \ge n\_0 \quad \displaystyle\frac{f(n)}{g(n)} \> M$
So I multiplied both halves by $g(n)$ obtaining $f(n) \> M\cdot g(n)$
I therefore chose a value $c\_1$ that respect the condition $0 \le M \le c\_1$ in order to define the relation $0 \le c\_1g(n)\le f(n)$ that proves that $f(n) = \Omega(g(n))$

---

So now my questions are:

* Is the (first part of the) solution mathematically right?
* How can I *mathematically* prove that $f(n) \neq O(g(n))$?

I'm struggling a bit to prove the second part of the demonstration.
The main idea I had is to do a *reductio ad absurdum* where I state that the value $c\_2$ I get (following the definition of $O(g(n))$) leads me to a contradiction. But I'm not entirely sure it makes sense.

Thank you in advance for your time.

# Answer
Your basic idea is good. Here is how you would approach it:

Let us assume towards contradiction that $\exists c\_2,n\_0:\forall n\>n\_0:f(n)\le c\_2\cdot g(n)$

In particular, we can re-write this as:

$$\exists c\_2,n\_0:\forall n\>n\_0:\frac{f(n)}{g(n)}\le c\_2$$

Now, since $\lim\_{n\rightarrow \infty}\frac{f(n)}{g(n)}=\infty$, then we know by definition of the limit that $$\forall M\>0:\exists n\_0:\forall n\>n\_0:\frac{f(n)}{g(n)}\>M$$

In particular, for any $c\_2$ and $n\_0$, there is some $n\>n\_0$ with $f(n)\>c\_2\cdot g(n)$. Hence, we get a contradiction to the assumption.
> 1 votes

# Answer
Suppose $f(n)=n^4,g(n)=n$, so

$$\lim\_{n\to\infty}\frac{f(n)}{g(n)}=\frac{n^4}{n^3}=\frac{n^3}{1}=\infty.$$

That means $f(n)=\Omega(g(n))$ and $f(n)\neq\mathcal{O}(g(n)).$ As a result, if $f(n)=\omega(g(n))$, then we can conclude that, $f(n)=\Omega(g(n))$ and $f(n)\neq \mathcal{O}(g(n)).$

Note that in a such case that

$$\lim\_{n\to\infty}\frac{f(n)}{g(n)}=\infty$$ easily we can conclude that $f(n)=\omega(g(n))$.
> 1 votes

---
Tags: algorithms, asymptotics, check-my-answer
---


# Question
Title: Complications of a language that reaches a state of reject
I have a question that is not clear to me, and I have not been able to answer it from a test I had.

This is the question

Let's look at the language $L\_\mathrm{reject} = ${ $\left \langle M,w \right \rangle$ | When $M$ is activated on the input $w$, the machine $M$ reach to reject state }

We will mark our input length: $|\left \langle M,w \right \rangle| = n$. Determine which of the claims is correct:

1. The language is not in $\mathsf{NPH}$ or $\mathsf{CoNPH}$.
2. The language is in $\mathsf{NP}$ but not in $\mathsf{NPC}$.
3. The language is in $\mathsf{P}$
4. The language belongs to $\mathsf{NPH}$.
5. None of the above claims are true.

I think the language should be CoNPH, or CoNPC because the language is in a reject state every time, and this is what is tested in CoNPC if it is possible to build an algorithm that returns a failure.

1. I think this is not true, in my opinion, the language should be in CoNPC because the machine always gets into a reject state, which is always a failure.
2. I do not think it is in NP, because it is not possible to write a non-deterministic algorithm that will say yes
3. If it's not in NP then surely it's not in P
4. I think the language belongs to CoNPH, because there is a machine that leads to a reject state, so there is a guessing algorithm, which checks when the language is not accepted - that it is related to CoNPH and not NPH.
5. I will probably choose this one because I could not find an answer that leads to CoNPC or CoNPH

*I can not understand, what it means to have a machine $M$ that gets a word $w$, and then straight goes to reject mode. What does it say about the language it belongs to.*

# Answer
> 1 votes
Saying that a "language reaches the state of reject" is meaningless. Languages don't have states. Turing machines and automatons do.

That said, your language is undecidable. Given $\langle M,w \rangle$ you can compute the pair $\langle M',w \rangle$ where $M'$ behaves exactly as $M$ except for the following: every transition that halts the machine and accepts is replaced with a transition that halts the machine and rejects.

Then $\langle M', w \rangle \in L\_{\text{reject}}$ if and only if $M$ halts on input $w$. Therefore if $L\_{\text{reject}}$ were decidable so would be the halting problem.

As a consequence $L\_{\text{reject}}$ is not in $NP$ nor in Co-$NP$ (which only contain decidable problems). This means that 2 is false, and 3 is false (since $P \subseteq NP$).

We can actually build a Karp reduction $f(\cdot)$ from a NP-Hard problem to $L\_{\text{reject}}$. Consider for example an instance $\phi$ of $3$-SAT. Construct a Turing Machine $T$ that expects (a suitable encoding of) $w$ of $\phi$ as input and then tries all possible variable assignments. If a satisfying assignment is found then $T$ rejects. Otherwise $T$ enters in an infinite loop. Choose $f(\phi) = \langle T, w \rangle$ and notice that $f$ can be computed in polynomial-time w.r.t. the encoding of $\phi$ (in particular $T$ can be fixed once for all). Then $\phi \in 3\text{-SAT} \iff f(\phi) \in L\_{\text{reject}}$. This shows that $L\_{\text{reject}}$ is NP-hard, 4 is true, 1 is false, and 5 is false.

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


# Question
Title: Is $\{w_1xw_2\mid w_1,w_2\in \{a,b\}^* \text{ and } x \in \{a,b\}\}$ regular or not?
The language given is $L = \\{w\_1xw\_2\mid w\_1,w\_2\in \\{a,b\\}^\* \text{ and } x \in \\{a,b\\}\\}$. Is this language regular or not?

Since there is no pattern, so it should be non-regular?

Kindly help!

# Answer
> 17 votes
It's regular because your language is equal to (suppose $\Sigma=\\{a,b\\}$) $$L=\Sigma^\*\Sigma\Sigma^\*$$ $$=\Sigma^+.$$ So we can represent $L$ by regular expression: $$(a+b)^\*(a+b)(a+b)^\*$$ $$=(a+b)^+.$$

# Answer
> 17 votes
The language is regular and a possible regular expression for $L$ is $(a\mid b)^\* (a \mid b) (a \mid b)^\* = (a \mid b)^+$.

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


# Question
Title: If $L_1,\,L_1L_2$ are regular languages with $L_1\neq \emptyset,\,\lambda\notin L_1,\,\lambda\notin L_2,$ is $L_2$ regular?
If $L\_1,\\,L\_1L\_2$ are regular languages with $L\_1\neq \emptyset,\\,\lambda\notin L\_1,\\,\lambda\notin L\_2,$ is $L\_2$ regular?

I think I found a correct proof for this question but my professor says it cannot work. Her issue is with the right quotient step but I cannot see why it is incorrect. Can anyone shed some light on this?

$$ L\_1L\_2 = \\{ w\_1w\_2 : w\_1 \in L\_1,\\, w\_2 \in L\_2 \\} \qquad \vert w\_1 \vert \ge 1,\\, \vert w\_2 \vert \ge1 $$

$$ \left( L\_1L\_2 \right)^R = \\{ w\_2^Rw\_1^R : w\_1 \in L\_1,\\, w\_2 \in L\_2 \\} $$

$$ \left( L\_1L\_2 \right)^R / L\_1^R = \\{ w\_2^R : w\_2 \in L\_2 \\} \qquad (w\_1^R \in L\_1^R)(\forall w\_2^Rw\_1^R) \implies w\_2^R \in \left( L\_1L\_2 \right)^R / L\_1^R $$

$$ \left( \left( L\_1L\_2 \right)^R / L\_1^R \right)^R = \\{ w\_2 : w\_2 \in L\_2 \\} = L\_2 $$

$$ L\_2 \\, \text{is regular by closure of reversal and right quotient on regular languages.} $$

# Answer
How about this? $L\_1=\\{a^n\mid n\>0\\}$, $L\_2 = \\{a^{m^2}\mid m\>0\\}$. Certainly $L\_1$ and $L\_1L\_2$ are regular, but $L\_2$ certainly isn't.
> 2 votes

# Answer
Hint #1:

> Try to find a counterexample.

Hint #2:

> What happens in the special case where $L\_1 = \Sigma^+$? Can you solve that special case?
> 1 votes

# Answer
Suppose $\Sigma=\\{a\\}$. Let $L\_1=\ell\_{reg}=\\{a^n\mid n\>1\\},L\_2=\ell\_{prime}=\\{a^m\mid m\text{ is prime number}\\}.$

According to this link, $\ell\_{prime}$ isn't regular. But $$\ell\_{reg}\cdot\ell\_{prime}=\ell\_{reg}\cdot\\{a^2,a^3,a^5,\dots\\}.$$ So we can conclude that $$ \ell\_{reg}\cdot\ell\_{prime}=a^+a^2.$$

But $\ell\_{prime}$ isn't regular,as a result, $L\_2$ can be non-regular.
> 0 votes

---
Tags: regular-languages
---


# Question
Title: There exists some number $x$ so in any run of BFS from vertex $w$, so the distance from $u$ to $v$ in BFS tree is always $x$
Studying for my finals and stuck on the following question:

> Prove or disprove: Given an undirected and connected graph $G=(V,E)$ and three different vertices $u,v,w\in V$ then there exists some number $x$ so in any run of BFS from vertex $w$, the distance from $u$ to $v$ in BFS tree is always $x$.

I think it's not true but could not think about a good example to disprove it.

# Answer
The statement is false. Take a look at the following graph:

In one BFS run, you will get the following tree:

That has a distance of $1$ between $u$ and $v$, while in a different run, you could get another tree:

Which has a distance of $3$ between $u$ and $v$
> 3 votes

# Answer
Because you run BFS from $w$, The BFS produce a shortest path tree $\mathcal{T}$ that contain shortest path from $w$ to other vertices. On the other hand the claim say that: any tree $\mathcal{T}$ that produced by BFS, the distance between $u,v$ is $x$, clearly it's not true, because the BFS guarantee the distance between $w$ and $\forall v\in V\setminus w$ that by multiple running BFS from $w$ not changed, but the distance between any two other vertices can be changed. BFS can't guarantee that distance between any two other vertices $u,v\in \\{V\setminus w\\}$ remain as the same previous run of BFS. Look at the counter-example **nir shahar**.
> 0 votes

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


# Question
Title: Reduction from the Clique problem to the Odd Clique problem
I have a question that is not clear to me, and I have not been able to answer it from a test I had.

This is the question:

Let's look at the problem $Oclique$ , In it we get a graph $G = (V,E)$ , And an odd natural number $k \in N$ ( You can mark: $k = 2d + 1$ for $d \in N $) And ask: "Is there a $U \subseteq V$ clique so that $| U | = k$?"

The language is:

$OClique = ${ $\left \langle G,k \right \rangle$ | There a $U \subseteq V$ clique so that $| U | = k$ and also $k = 2d + 1$ for $d \in N $ and for every $u\_1,u\_2 \in U$ there is an $(u\_1,u\_2 )\in E$.}

Determine which of the claims is correct:

1. The language is in $\mathsf{NP}$ but not in $\mathsf{NPH}$ and not in $\mathsf{NPC}$.
2. The language is in $\mathsf{P}$ because an algorithm can be constructed running at time O (| V | * | E |), by reduction to the IS problem.
3. The language is in $\mathsf{NPC}$ And this is why $Clique \leq \_p OClique$ conversion can be found.
4. The language is in $\mathsf{NPH}$ but not in $\mathsf{NP}$ and not in $\mathsf{NPC}$.
5. None of the above claims are true.

I think the answer is 3, but I'm not sure how to do the reduction.

1. Wrong, I think it is possible to make a reduction from the Clique problem
2. Does not make sense in any way. It does not belong to P. Reduction from IS which is NPC, will also lead to OClique in NPC.
3. I think this is true, it is possible to convert any instance from the Clique problem to the OClique problem and vice versa. Each graph in Clique, you can multiply by 2 the amount of vertices, and connect the vertices to all the other vertices, then add one more vertex to all the other vertices. I think this is a complete, correct, and polynomial time reduction, but I'm not sure if I explained it properly.
4. It does not make sense, if the language is in NPH then it is also in NP.
5. maybe 3 is true.

*`I think the answer is 3, I'm not sure then explain it properly.`*

# Answer
1 is wrong. The problem is NP-Complete by an easy reduction $f$ from the clique problem. Let $\langle G,k \rangle$ with $G=(V,E)$ be an instance of (the decision version of) clique. If $k$ is odd then the reduction is the identity function, i.e., $f(\langle G,k \rangle)=\langle G,k \rangle$. Otherwise create a new graph $G=(V', E')$ with $V' = V \cup \\{v\\}$ and $E'= E \cup (\\{v\\} \times V)$ and let $f(\langle G,k \rangle)=\langle G',k+1 \rangle$. This also shows that 3 is true (a certificate for $OClique$ is the list of vertices in a clique of size at least $k$).

We currently don't know whether 2 is true or false. It if were true it would prove $P=NP$.

Regarding 4. The language is in NP so this is false. Notice however that, in general, a NP-hard problem does not necessarily need to be in NP.
> 2 votes

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


# Question
Title: Question on Erickson 'momselect' algorithm
In the Erickson Algorithms textbook (file:///C:/Users/G068078/OneDrive%20-%20Kaiser%20Permanente/Algorithms\_Technique\_and\_Theory\_CS\_388G/Undergraduate\_CS331/Algorithms-JeffE.pdf) it has pseudocode for 'momselect':

This is probably a really basic question but I do not get how it ever gets past the red part. It recurses to eventually find the "median of medians" (mom), but once it gets below 25, it simply used brute force. How does it ever reach the "Partition" step?

# Answer
> 2 votes
In the pseudocode "use brute force" means "compute the median of the input sequence (with any algorithm) and **return it** (to the caller)".

Eventually all the children calls in the recursion tree starting at the red call to "MomSelect" will terminate and the control will return to the current execution of the algorithm, that will move to the next (black) instruction.

---
Tags: sorting, recursion
---