# Question
Title: Since the halting problem is undecidable, does that mean that there exists an always undecidable program?
The usual demonstration of the halting problem's undecidability involves positing an adversarial machine (call it $A\_0$) that runs the decider machine (call it $D\_0$) on itself and performs the opposite of the answer it gets. But it would be possible to construct a machine $D\_1$, that checked for the exact source code of $A\_0$ and output the correct answer. Of course then another machine $A\_1$ that runs $D\_1$ instead of $D\_0$ could also be constructed. And so on to any finite $n$.

So it seems like any given adversarial machine can be thwarted by another larger-indexed decider machine. So it appears that it does not directly follow from that demonstration that there is any single machine that there cannot be a decider machine constructed for. The proposition that there is no single machine that can decide for all cases still holds of course, but I'm interested in that slightly different question of whether there exists a machine that no decider machine can correctly identify whether it halts. Is the answer to that question known?

I can imagine a possible answer that any given machine must either halt or not so one of the trivial decider programs that always says the same answer would be correct. But it seems to me that there is a sensible notion of "non-trivially deciding" that would exclude examples like that. But maybe the fact I'm currently unable to describe that notion precisely indicates I'm wrong about that?

Edit: I think I now have a way of describing a notion of "non-trivially deciding", although now that name does not fit as well. First we need to change the problem slightly. In this version the decider machines output one of $halts$, $continues$, or $unknown$, indicating that the machine halts, does not halt, or the decider machine does not "know" respectively. So we can call decider machines that are correct in all of the cases that they output $halts$ or $continues$ "correct" or "honest" decider machines.

So now my question is, is there a machine that no single honest decider machine would identify correctly? By "identify correctly" I mean the decider outputs either $halts$ or $continues$ and that the outputs correctly correspond to the machine under examination's behaviour. By the definition of honest, if the machine under examination halts and the decider outputs $continues$ or the machine under examination does not halt, and the decider outputs $halts$ then the decider is not honest. So this definition excludes the decider machines that always output the same answer, including the one that always outputs $unknown$ by my definition of "identify correctly".

Edit 2: To elaborate on my notion of a decider machine correctly identifying a machine's behaviour, we can break the definition into two parts gaining some more vocabulary in the process.

First we have the criterion that the decider outputs $halts$ or $continues$ for that machine. We can call that criterion the identification criterion, and we can say of decider machines that they identify a machine if and only if they out one of $halts$ or $continues$ on that machine.

Second we have the criterion that the decider's output correspond to the to the machine under examination's behaviour. So if the examined machine halts and the decider outputs $halts$ the decider is correct about that machine. Similarly if the examined machine does not halt, a decider that outputs $continues$ would be correct. It seems useful to include outputting $unknown$ as "technically correct". So the full rules would be a decider is correct about a given examined machine if one of the following is true:

* The examined machine halts and the decider outputs $halts$ or $unknown$
* The examined machine does not halt and the decider outputs $continues$ or $unknown$

We can call this the "correctness" criterion, and say that a decider is correct about a given machine if and only if the above condition is true.

We can put the vocabulary back together and say that a decider correctly identifies a given machine if they identify that machine, and they are correct about that machine. So now we can state that the always $unknown$ decider does not correctly identify every machine since, while it is always correct about every machine, it does not identify any machines!

# Answer
Suppose you've come up with a machine $P\_0$ which you claim decides the halting problem. I create a $Q\_0$ that makes it malfunction somehow (your $P\_0$ either ends up diverging or gives the wrong answer). The proof of the Halting Problem shows that I can always create such a $Q\_0$.

"Aha!" you say. "But now I can create $P\_1$, which is exactly like $P\_0$—except that it checks whether its input is $Q\_0$ and gives a hardcoded answer if so." Sure, you can do this. But then I can just create a $Q\_1$ in exactly the same way that I created $Q\_0$. This is always possible—that's how the proof works.

You can show by induction that you can always create a $P\_n$ that has $n$ hardcoded special cases, protecting it against $n$ different $Q$s. In fact, for any "undecidable program" $Q$ I create, you can create a special $P$ that can decide it:

```
DoesItHalt(X):
    if X = Q, return [hardcode whichever answer is correct]
    else, return true

```

Therefore there is no "universally halting-undecidable program" $Q\_\omega$. But I can also create a new $Q$ that defeats any $P$ you make, since you can have as many special cases as you like, but that number must be finite. Therefore there is no "universal halting-decider program" $P\_\omega$ either (which is the whole point of Turing's proof).
> 3 votes

# Answer
The question is wrong. The "usual demonstration" proves that the deciding machine $D\_0$ cannot exist, as that leads to contradiction. Therefore, the adversarial $A\_0$ cannot exist either, as it has $D\_0$ as a part/subroutine. It is then impossible to construct the discriminator $D\_1$, it cannot check for $A\_0$ source, when $A\_0$ source cannot exist.

And if ignoring the previous argument, $D\_1$ must now provide the correct hardcoded answer for $A\_0$. But what is that answer supposed to be? There is no correct answer for what the impossible $A\_0$ would do, so there is no useful answer to hardcode here. The "string of machines" doesn't happen.

Now to your question.

The proof of unsolvability says you cannot identify all machines, as some of them would simply use your identifier and then do the opposite of whatever it says. This cannot be sidestepped by hardcoding specific cases, as there is no correct answer for any such adversarial machine. You may recognize the source of a particular adversarial machine in finite time, but there is no hardcodable answer other than "unknown". There is also an infinite amount of variants of such machines (for example, by doing any simple calculation before the adversarial stuff), so you cannot recognize them all in finite time either.

You can have a machine that answers continues/stops/unknown in all cases though. It could simulate the machine to be tested for a million cycles. If it halts, the decider output "halts". If, during this time, the simulated machine and its tape gets to exactly the same state as observed in some earlier iteration, then we have proved it continues forever with some period less than a million iterations. So output "continues" then. In other cases, output "unknown". Honest and correct in all cases, but won't identify machines needing more than a million steps to repeat state. (And no machines that produce infinite output either.)

The proof of undecidability does not provide a particular machine that no turing machine can decide. All it does, is prove that you cannot identify all cases - as any perfect decider can be used as part of an adversarial machine that fools this perfect decider. It will necessarily fool all other perfect deciders too, as all perfect deciders must give the same answer in all cases!

Still, the proof does not provide a particular undecidable machine, as the given undecidable machine needs that perfect decider we cannot have. There may be other undecideable machines, but what they look like is currently unknown.
> 1 votes

# Answer
The answer to your question is yes. That is exactly the whole point of the Halting Problem: It is impossible to build a recognizer that correctly answers "Yes" or "No" in finite time to the question "Does P halt?" for all P. We don't need to exhibit a P for which all recognizers fail to be able to prove that it exists.
> 0 votes

# Answer
I take it that we are calling a *decider* a machine that takes in a natural number $n$ and then prints out either "yes" or "no", where as observers we interpret the output as the decider's opinion of whether Turing machine $n$ halts on an empty tape. Consider the decider $D\_y$ that always prints "yes," along with the one $D\_n$ that always prints "no." If someone presents me with a Turing machine called *always undecidable*, I will say that, to the contrary, one of $D\_y$ and $D\_n$ will correctly decide that machine.
> 0 votes

---
Tags: turing-machines, undecidability, halting-problem
---


# Question
Title: Strong NP-completeness of permuted kernel problem
The permuted kernel problem is NP-complete problem by simple reduction from partition problem. In fact, it is strongly NP-complete by reduction from 3-partition. The literature points to Garey and Johnson for the reduction from 3-partition. I checked G&J but did not find the reduction. Do you have a reference that contains the reduction?

Permuted kernel problem

Given a matrix A and vector X, Is there a permutation $P$ of vector X such that $A\*X\_P=0$

# Answer
> 2 votes
Let $S\_1,\dots,S\_{3m}$ denote the integers that form the 3-partition instance. Let $T=(S\_1+\dots + S\_n)/m$, so that $T$ is the target sum for each triple. As noted on Wikipedia, without loss of generality we may assume that $S\_i \in (T/4,T/2)$ for every $i$.

Let

$$A = \begin{pmatrix} 1&1&1 &0&0&0 &\cdots &0&0&0 &1 &0 &\cdots &0\\ 0&0&0 &1&1&1 &\cdots &0&0&0 &0 &1 &\cdots &0\\ & & & & & &\ddots & & & & & &\ddots &\\ 0&0&0 &0&0&0 &\cdots &1&1&1 &0 &0 &\cdots &1\\ \end{pmatrix}$$

where there are $m$ rows and $4m$ columns. Let

$$X = (S\_1,\dots,S\_{3m},-T,-T,\cdots,-T).$$

Then $A,X$ is an instance of the permuted kernel problem, and it has a solution iff the original 3-partition instance has a solution.

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


# Question
Title: Time complexity of T(n) = 1600T(n/4) + n!
I'm trying to find the time complexity of T(n) = 1600T(n/4) + n! . So far I have thought of changing n! to something usable by the master theorem. Stirling's approximation gives us the equation

$$\sqrt{2\pi n}\left(\frac{n}e\right)^n$$

I am confused on whether the value for d in the master theorem would become n or if I am looking at this the wrong way. Any advice on how to find the time complexity would be appreciated.

# Answer
> 1 votes
To apply the right case of the master theorem, in the relation $$T(n) = aT\left(\frac{n}b\right)+f(n)$$ you have to compare $n^{\log\_b a}$ and $f(n)$:

1. if $f(n) = \mathcal{O}(n^c)$ with $c\<\log\_b a$, then $T(n) = \Theta(n^{\log\_b a})$;
2. if $f(n) = \Omega(n^c)$ with $c \> \log\_b a$, then $T(n) = \Theta(f(n))$;
3. if $f(n) = \Theta(n^c)$ with $c=\log\_b a$, then $T(n) = \Theta(n^c \log n)$.

In this case, you have to compare $n^{\log\_b a}$ with $\log\_b a = \log\_4(1600) \simeq 5.32$ with $n!$. You can use Stirling approximation to compare those two functions.

---
Tags: time-complexity, factorial
---


# Question
Title: Finding Optimal Configuration of Formula without trying every Permutation
I have a math problem I need to solve so I can complete an optimisation in a computer program. My initial approach was just to brute force all the possible permutations but it got out of hand quite quickly for larger sets. Here's the problem

Let's say you want to take `n` bets each with odds `k`. We want to optimize the amount we should bet for each value of `k` denoted as `x(k)` such that in the worst case we loose the least amount of money. All the bets are mutually exclusive, so if one outcome happens all the rest are lost.

So far our bets would look something like

```
a . x(a)
b . b(a)
c . c(a)
... up to n bets

```

The bet amounts can only be made in discrete multiples of `10`. We have a maximum total betting amount of `total_bet_max` and a maximum amount per bet of `bet_max`. So essentially we are trying to optimize the following

```
worst_outcome = Min(a . x(a) - b - c - [...], b . x(b) - a - c - [...], c . x(c) - a - b - [...], [...])
a + b + c + [...] <= total_bet_max
a , b , c, [...] <= bet_max

--> optimize a, b, c, ... for the highest value of worst_outcome

```

I tried a greedy algorithm approach by iterating over and incrementing values and checking if the `worst_outcome` is improved, however, this doesn't actually work. Because sometimes it makes sense to increment two variables e.g. a and b together but not by themselves. Also I think some cases you would need to look ahead to see you need to increment by 3 units for a, 2 units for b and 1 unit of c, so greedy doesn't really work.

Any suggestion or solution on how to solve this? An approximation may also be suitable if the problem is not solvable.

# Answer
Notice that the equation $o = \min(a\_1 x(a\_1) - a\_2 - a\_3 - ..., a\_2 x(a\_2) - a\_1 - a\_3 - ..., ...)$ (I'm using $a\_1 , a\_2 , ...$ instead of $a, b, c, ...$) can be rewritten as $$o = \min(a\_1 (x(a\_1)+1) - \sum a\_i, a\_2 (x(a\_2)+1) - \sum a\_i, ...) = \min(a\_1 (x(a\_1)+1), a\_2 (x(a\_2)+1), ...) - \sum a\_i$$ We will use $b\_i = x(a\_i) + 1 $. Set $c = \min(a\_i b\_i)$, and notice that in the optimal solution $a\_i = 10 \lceil \frac{c}{10 b\_i} \rceil $, since if $a\_i \leq 10 (\lceil \frac{c}{10 b\_i} \rceil - 1)$ (remember that it must be divisable by 10) then $a\_i b\_i \< c$ and $c$ isn't the minimum, and if $a\_i \geq 10 (\lceil \frac{c}{10 b\_i} \rceil + 1)$ then $a\_i$ could be decreased by 10 without hurting the minimum but decreasing the sum.

Both requirements $\sum 10 \lceil \frac{c}{10 b\_i} \rceil = \sum a\_i \leq s\_{\max}$ and $10 \lceil \frac{c}{10 b\_i} \rceil = a\_i \leq a\_{\max}$ are monotone in $c$, so using binary searching we can find a value $c\_{\max}$ such that a solution is valid iff $c \leq c\_{\max} $.

We reduced the problem to maximizing $ c - \sum 10 \lceil \frac{c}{10 b\_i} \rceil $ subject to $0 \leq c \leq c\_{\max} $. If $c\_{\max}$ is small enough then we can search the entire range (note that we can reduce the time from $O(n c\_{\max})$ to $\tilde O(\sum \lceil \frac{c\_{\max}}{10 b\_i} \rceil)$, by marking points where $\sum \lceil \frac{c}{10 b\_i} \rceil$ increases).

Otherwise, while not a precise solution, we can argue that if $\sum \frac1{b\_i} \> 1$ then the general trend of the function is to decrease, so it is likely the optimal value of $c$ will be fairly small and we can check values of $c$ in the order $0, 1, 2, ...$ until we run out of time. In the same way, if $\sum \frac1{b\_i} \< 1$ then the general trend of the function is to increase, it is likely the optimal value will be fairly big, and we can check values in the order $c\_{\max} , c\_{\max} - 1, c\_{\max} - 2, ...$ until we run out of time. Here as well we can mark the points where $\sum \lceil \frac{c}{10 b\_i} \rceil$ increases to get a time of $\tilde O(\sum \lceil \frac{R}{10 b\_i} \rceil)$, with $R$ being the size of the range we are testing.

For example, suppose there are three bets with odds 1, 2 and 23 (so $b = 2, 3, 24$), with a maximum bet of 200, and a maximum total bet of 260. Then, with binary search, we can find that $c\_\max = 280$, which will produce the bets $140, 100, 20$, which are valid, while $281$ will give the bets $150, 100, 20$ which have too big of a sum. Now, we need to find the maximum value of $ c - \sum 10 \lceil \frac{c}{10 b\_i} \rceil $ for integer $0 \leq c \leq 280$. An exhaustive search gives $c = 240$, for which it is equal to 30, and the optimal bets will be $120, 80, 10$
> 2 votes

---
Tags: optimization, search-algorithms, search-trees, permutations, search-problem
---


# Question
Title: Finding the length of the longest palindrome in the given array
The problem that I'm trying to solve is: Given an array of length N, I want to find the length of the longest palindrome in the given array. With palindrome, we refer to a word, phrase, or sequence that reads the same backwards as forwards.

For example, if we give as input `"1234321789"` the algorithm should return 7.

I want the algorithm to have the smallest possible time complexity and efficiency.

# Answer
First, take a look at https://www.geeksforgeeks.org/length-of-longest-palindrome-substring/ This might answer your question completely.

This will give you $O(n^2)$ time and $O(n)$ space complexity.

Now here is another trick that I think will work. We already know to find the longest common subsequence given two strings, right? It is a very common algorithm that uses dynamic programming. Let's call that method $LCS$

Now given your array or string, call it $s$ and compute $reverse(s) = s'$

Now compute $LCS(s,s')$. The LCS of both strings is the longest palindrome.

Note that this method will work only if we are looking for substrings and not subsequences. ABCAB reversed is BACBA, and while ACA is a palindrome, ACB is also the longest LCSs and not a palindrome. But Neither ABCAB nor BACBA contains ACA or ACB. This method will output any of the letters A, B, or C as a solution (since ABCAB doesn't contain palindromes of length $\geq 2$)
> 1 votes

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


# Question
Title: Greedy Algorithm for Geometric Set Cover
Consider the geometric set cover problem https://en.wikipedia.org/wiki/Geometric\_set\_cover\_problem.

The Wiki article says there is a simple greedy algorithm for the one-dimension case, what is the analysis of that?

I have already asked this question before: Geometric Set Cover in one dimension which was answered. I asked a follow-up question in the comments, but I think it is better to post it as a new question.

Rather than trying the greedy algorithm mentioned in the answer to the question, if we try the standard greedy approach, i.e. Suppose we don't start from $x\_1$ and rather pick up the interval $I\_i$ that covers the largest number of elements( i.e. $x\_i$), take this $I\_i$ in our solution, delete all those $x\_i$ and reiterate, i.e. pick the next largest interval $I\_j$ and so on until none of $x\_i$ are left. This is also a greedy solution, but several examples can be found that this won't give an optimal solution. Will this be some constant times the optimal solution?

# Answer
Now suppose there are $k$ sets in the optimal solution and let that be $OPT = \\{O\_1,...,O\_k\\}$

Here the sets in the family look like intervals of integers because they contain only consecutive numbers.

Let $I\_1,...,I\_n$ be the given sets where $I\_i = \\{j+1,...,j+k\\}$. We define the left and right endpoints of any such interval as $L(I\_i) = j+1$ and $R(I\_i) = j+k$ and $|I\_i| = k$

Now let us fix one set from the optimal solution and without loss of generality, let's call it $O\_1$. We will show that $O\_1$ can intersect at most some constant number of sets $I\_j$s that we output from the greedy solution.

No set from the greedy solution can be a subset of $O\_1$, because $O\_1$ is a set in the family, and in that case, the greedy algorithm will pick $O\_1$ and not its subset in the first place.

Among the sets that are intersecting $O\_1$, one cannot be subset of another, i.e if $I\_1,I\_2$ intersect $O\_1$ at some points, then neither $I\_1 \subset I\_2$, nor $I\_2 \subset I\_1$. This is because the greedy solution will have picked up the bigger set in the first place.

The above two observations show that when some $I\_i$ intersect $O\_1$, $I\_i-O\_1 \neq \phi$. Now we consider two situations of some sets $I\_1, I\_2$ intersecting $O\_1$.

Suppose we have $I\_1,I\_2$ intersecting $O\_1$, such that $L(I\_1) \< L(O\_1) \< L(I\_2) \< R(I\_1) \< R(O\_1) \< R(I\_2)$.

This is the case where $I\_1, I\_2$ intersect each other. Depending on the sizes, both are taken up by the greedy algorithm. Now suppose $O\_1$ intersects with another set $I\_3$, we will try to figure out how this $I\_3$ will look like and what its range can be.

$I\_3$ can intersect only $I\_2$, or can intersect only $I\_1$ or can intersect both $I\_1,I\_2$. Let us first consider the case when $I\_1$ intersects $I\_2$, the case where $I\_3$ intersects $I\_1$ will be exactly similar.

So we know, we must have $L(I\_3) \> L(I\_2)$ and $R(I\_3) \> R(I\_2)$. Observe that $I\_3$ must be maximal of these types of sets, because if we have another $I\_4$ continuing this sequence with $L(I\_4) \> L(I\_4)$ and $R(I\_4) \> R(I\_4)$, then this contradicts the greedy algorithm. After we take up $I\_2$ by the algorithm, $I\_4$ covers more elements than $I\_3$, so $I\_3$ will not be taken up in the first place. So there can only be one set of that type, call it $I\_3$.

The argument when $I\_3$ intersects $I\_1$ and not $I\_2$ is exactly similar. This means we can have two more sets in each direction, we can call these $I\_3, I\_4$ that intersect $O\_1$ too. Now consider the set $I\_5$ where we have $L(I\_1) \< L(I\_5) \< L(O\_1)$ and $R(O\_1) \> R(I\_5) \> R(I\_2)$. Again we can repeat the same argument and say that $I\_5$ is the maximal in this type of set, we cannot have a sequence of such sets because after $I\_2, I\_1$, we will choose the maximal of these sets in the first place. But given that the greedy algorithm has already chosen $I\_3, I\_4$, it will not choose $I\_5$ anymore. If we have $L(I\_2) \< L(I\_5) \< R(I\_1)$ and $R(I\_5) \> R(I\_2)$, then the greedy algorithm will never pick $I\_2$. So $O\_1$ can intersect at most 4 sets in this case.

This is the case where $I\_1,I\_2$ do not intersect each other. In this case, as before we will have $I\_3, I\_4$ as usual in either direction, say $I\_3$ in direction of $I\_1$ and $I\_4$ in direction of $I\_2$. But in this case, we might not have any other set to cover between $R(I\_1)$ and $L(I\_2)$, apart from $O\_1$ which is itself in the family of sets. If there is a set larger than $O\_1$ satisfying the above analysis, the greedy algorithm will be taking that set to cover this part, else it will take $O\_1$ itself to cover this part. It might also be the case that $L(O\_1) \< R(I\_3) \< L(I\_5) \< R(I\_1) \< L(I\_2) \< L(I\_4) \< R(I\_5) \< R(I\_4)$, or it might be the case in the exact opposite direction, but any one of these sets will need to be chosen to cover the remaining part.

So $O\_1$ will be intersecting 5 sets from the greedy algorithm in this case.

The number of sets selected by the greedy algorithm is upper bounded by five times the number of sets in the optimal solution.

In the whole analysis above, we chose one set from the optimal solution called $O\_1$, it was an arbitrary set, so the whole analysis is true for any $O\_i \in OPT$. Here we have $|OPT| = k$.

We see that each $O\_i$ intersects at most 5 sets from the greedy solution, so if we output the sets from the greedy solution, we are overcounting the optimal solution by at most five times. So the number of sets in the greedy solution is at most $5k$

We must have $L(O\_1) \< L(O\_2) \< ... \< L(O\_k)$, given that the sets are ordered from left to right by the portions of the number line they cover. This is because if $L(O\_i) = L(O\_{i+1})$, then one of the sets will be a subset of another and so no more be an optimal set.

Pick any element from $1, ..., n$, say $i$, then it can belong to at most two of the optimal sets. If we have $i$ inside $O\_i, O\_{i+1}, O\_{i+2}$, then this means that we don't need $O\_{i+1}$ in the set cover, and the collection is no more optimal.

The best approximation factor $c$ can not be less than 2

We have $U = \\{1,...,n\\}$ and consider the given family of sets $F = \\{\[1,k\], \[k+1,2k\],..., \[n-k+1,n\]\\} \bigcup \\{\[1,k+1\],\[k+3,2k+3\],\[2k+5,3k+5\],...\\}$. This means the family contains $n/k$ intervals of size k which completely cover $U$. But the family also contains approximately $\frac{n}{k+1}$ intervals of size $k+1$ spaced apart by 1. Our standard greedy algorithm selects the latter subset of intervals since each one spans $k+1$ uncovered elements. But at the end it will be forced to add approximately $\frac{n}{k+2}$ more intervals to cover the numbers $k+2,2k+4,...$ and so on. So it ends up selecting twice the number of sets of the optimal.

Now I will try to reduce the approximation factor but I am not sure if this is right.

Consider a particular set $O$ from the optimal solution. Among all the sets from the greedy solution that intersect this set, consider only those whose leftmost endpoint lies in this set $O$. Then there can be at most two such sets.

Consider the optimal solution and lets order the sets in that solution as $O\_1,...,O\_k$. Now fix one such set $O\_i$. Suppose there is an interval $I\_1$ from the greedy solution, such that we have $L(I\_1)\> L(O\_i)$ and then we must have $R(I\_1) \> R(O\_i)$ because otherwise the interval will become a subset of $O\_i$ and the greedy solution will pick the optimal set instead of $I\_1$. So we charge $O\_i$ once for this $I\_1$.

Now note that we can have a sequence of such sets satisfying the exact conditions like $I\_1$. Let us look at two such sets $I\_2,I\_3$, where we have $L(O\_i)\< L(I\_3) \<L(I\_2)\<L(I\_1)$ and also $R(O\_i)\<R(I\_3) \<R(I\_2)\<R(I\_1)$, to prevent one interval to be subset of another.

But now observe that this cannot hold. Once $I\_1$ has been picked by the greedy algorithm, it will directly pick $I\_3$ and not $I\_2$ because it covers more elements. So there cannot be a sequence of such sets with their left endpoints inside $O\_i$, we can have at most two of them.

The only way that we can have another set $I\_4$ intersecting the $O\_i$ to the left of $I\_3$, apart from the sequence, will be to have $R(I\_4) \< L(I\_3)$, in which case $L(I\_4)$ is inside $O\_{i-1}$.

In the previous approach, we were charging each optimal set the number of times it has intersected any set from the greedy solution so that a maximal number of times any optimal set has been charged is the approximation factor. In this approach, we will only charge an optimal set by the number of times it intersects only the kind of sets whose left endpoint lies within it. Thus by the above lemma, we can charge at most twice. So this should give an approximation factor of 2.
> 0 votes

---
Tags: algorithms, combinatorics, greedy-algorithms, set-cover
---


# Question
Title: Is there a way to make a implication graph of the following expression?
Is there a way to make implication graph of expression of form :

$$ ((x\_1 \lor x\_2)\lor(x\_3 \lor x\_2))\land(x\_3 \lor x\_4)$$

I haven't been able to find any sort of text on this and the usual way to make implication graph like of 2-SAT doesn't really make sense because of the extra OR in between.

# Answer
> 1 votes
The formula $((x\_1 \lor x\_2) \lor (x\_3 \lor x\_2)) \land (x\_3 \lor x\_4)$ is equivalent to $(x\_1 \lor x\_2 \lor x\_3) \land (x\_3 \lor x\_4)$. Notice that the last formula contains the subformula $(x\_1 \lor x\_2 \lor x\_3)$. If we can convert this formula to a 2-CNF formula, then we are done (we can construct an implication graph of the original formula).

However, it is mathematically impossible to express $(x\_1 \lor x\_2 \lor x\_3)$ as 2-CNF formula, see this mathematical argument.

---
Tags: time-complexity, 2-sat
---


# Question
Title: Is There Any Shortest Path Algorithm That Finds The Shortest Path Between Only Two Nodes
The Dikstra shortest path algorithm on a weighted graph, directional or bidirectional, pretty quick. There is also the Bellman Ford algorithm. However, these two find the shortest path between one source to ***all*** vertices. However, if I only want to know the path between ***two*** vertices, is there a faster algorithm that only finds the distance between two nodes?

# Answer
> 3 votes
Nope. The best you can do is to use Dijkstra's or Bellman-Ford. With Dijkstra's algorithm, you can stop the iteration as soon as you reach the target node, but this doesn't improve the worst-case asymptotic running time.

# Answer
> 3 votes
Dijkstra's is the asymptotically fastest possible for arbitrarily graphs we know nothing about, but most graphs in the real world have some sort of structure.

For example, A\* is (usually) faster, but it requires a heuristic. Jump point search only works on fairly open grids, but for those cases it's an order-of-magnitude faster.

To tell you if there's a faster algorithm, we'd need to know more about your specific problem.

# Answer
> 1 votes
What you are looking for are Point-to-Point Shortest Path Algorithms, which are often needed in finding the shortest paths in street networks. I am speculating here about you specific problem. In this context the graphs are planar and have some sort of structure we can use.

The A\* algorithm is the most prominent one using some heuristic, such as the euclidean distance to limit the search space. However, we can do even better if we allow some kind of preprocessing of the graph.

One approach is using landmarks to improve the heuristic of the A\*. Another is Transit node routing to precompute certain often used paths (such as highways) A third would be Arc Routing, which adds information to the edges, which the shortest path algorithms can use.

A more recent overview in german can be found here alongside some experimental evaluation at the end

---
Tags: graphs, shortest-path
---


# Question
Title: Finding general time complexity for recurrence relation $T(n)=aT(n/\alpha)+bT(\beta n/\alpha)+f(n)$
I was given an assignment in which I had multiple recurrence relations and I had to find their Big-oh time complexities. Nearly all of the recurrence relations were of the form as under:

> $$T(n)=aT(n/\alpha)+bT(\beta n/\alpha)+f(n)$$

So I tried to find the general Big-oh complexity, so that I could solve each one just by substituting in the particular coefficient values. Here is what I did:

$$\begin{aligned} T(n)&=a\left(aT\left(\frac{n}{\alpha^{2}}\right)+bT\left(\frac{\beta n}{\alpha^{2}}\right)+f\left(\frac{n}{\alpha}\right)\right)+b\left(aT\left(\frac{\beta n}{\alpha^{2}}\right)+bT\left(\frac{\beta^{2} n}{\alpha^{2}}\right)+f\left(\frac{\beta n}{\alpha}\right)\right)+f(n)\\ &=\left(a^{2}T\left(\frac{n}{\alpha^{2}}\right)+2abT\left(\frac{\beta n}{\alpha^{2}}\right)+b^{2}T\left(\frac{\beta^{2}n}{\alpha^{2}}\right)\right)+\left(f(n)+af\left(\frac{n}{\alpha}\right)+bf\left(\frac{\beta n}{\alpha}\right)\right)\\ &=\sum\_{r=0}^{k}{k\choose r}a^{k-r}b^{r}T\left(\frac{\beta^{r}n}{\alpha^{k}}\right)+\sum\_{r=0}^{k-1}\sum\_{i=0}^{r}{r\choose i}a^{r-i}b^{i}f\left(\frac{\beta^{i}n}{\alpha^{r}}\right) \end{aligned}$$ $$\boxed{O\left\[\max\left(\sum\_{r=0}^{k}{k\choose r}a^{k-r}b^{r}T\left(\frac{\beta^{r}n}{\alpha^{k}}\right), \sum\_{r=0}^{k-1}\sum\_{i=0}^{r}{r\choose i}a^{r-i}b^{i}f\left(\frac{\beta^{i}n}{\alpha^{r}}\right)\right)\right\]\text{ where } k=\log\_{\alpha}n} $$

Is this correct? When I apply it on a specific example, I'm not sure if I get the right answer. Any help is appreciated. Thanks in anticipation.

# Answer
You can solve this (for well-behaved $f$) using the Akra–Bazzi theorem, a generalization of the master theorem. The answer will depend on the relation between the parameters $a,b,\alpha,\beta$ and the asymptotics of $f$.
> 1 votes

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


# Question
Title: Why is a LALR parser the correct choice for parsing mathematical content? (a question about Approach0)
This questions is about the work A novel similarity-search method for mathematical content in LaTeX markup and its implementation.

The parser used by Wei Zhong is LALR.

Now, supose I have to parse a function $func(foo)=bar$.

How is the parser able to understand the "$func$" as a whole string representing the name of a funciton and not several constants/variables $f,u$ and $n$ multiplying the function $c(foo)=bar$?

(please explain your answer using grammar rules)

The grammar rules are found on pages 54/55:

# Answer
> 2 votes
As @Dmitry said in a comment, the input is partitioned into tokens by the lexical analyser (or "scanner"), normally generated with (f)lex, and this stream of tokens becomes the input to the parser. The parser does not see the individual characters from the input.

Having said that, I don't believe that the parser can distinguish between different syntactic uses of juxtaposition. `n(\pi/2)` ($n(\pi/2)$) could be the product of $n$ with $\pi/2$, or it could be the application of the function $n$ to the argument $\pi/2$. Only semantic context could help the reader distinguish the two uses. (Was $n$ previously used as a variable or was it textually defined as a function or predicate?). \[Note 1\]

Since the goal of the cited thesis is to search a corpus of text for instances of mathematical equations *similar to* a given query, the precise parse is not required (and perhaps not even useful), so that resolving that ambiguity is not a goal of the project. Consequently, it's probably not a great witness for the question "What is the best parsing framework for parsing mathematical content?" In general, mathematicians tend to tolerate highly ambiguous syntaxes in presentations, relying on the common sense and semantic knowledge of the reader to disambiguate. (Much the same as our approach to human language in general.) But when logic and algebra are analysed theoretically, unambiguous syntaxes are required, and those are normally defined in such a way that they can be parsed with an LALR(1) parser. (Indeed, the usual syntactic definitions are defined recursively leading to the possibility of parsing with a recursive descent parser, which is not as powerful as LALR. But LALR might still be an appropriate pragmatic choice.)

The case of user-defined functions whose names contain more than one character is, perhaps, slightly interesting. LaTeX will always typeset juxtaposed letters in a manner consistent with the juxtaposition being a multiplication. Hence, $find(\pi/2)$ (`find(\pi/2)`) looks quite different from the use of predefined operator like `\sin` ($\sin(\pi/2)$). Note that the latter is written with a backslash; `\sin` is the keyword, not `sin`.

In LaTeX, you can define your own math operators with the `DeclareMathOperator` macro. That lets you write:

```
\DeclareMathOperator{\find}{find}

```

after which, you can use `\find` in your equations, producing $\DeclareMathOperator{\find}{find}\find(\pi/2)$. However, this feature is not handled by Wei Zhong's work, presumably because it was not useful for his problem (which does not require accurate parsing). Wei's parser only recognises specific LaTeX macros which have mathematical semantics. (These are listed in Appendix B of the thesis.) It ignores many other macros, more related to typography, as well as any user-defined macros. (Quote from page 37 of the thesis.)

> Our lexer omits all LATEX control sequences not matching any pattern of our defined tokens, most of them are considered unrelated to math formula semantics.

---

### Notes:

1. There is no universal convention to chose between $\textrm{foo}(\pi/2)$ and $\textit{foo}(\pi/2)$ (`\textrm{foo}` and `\textit{foo}`, respectively) to represent the application of a function named `foo`. But, at least in my opinion, $foo(\pi/2)$ (`foo(\pi/2)`) should never be used; the kerning is awful.

Apparently, there is an applicable ISO standard (ISO 80000-2:2019, in case you care) which seems to recommend the use of $\textrm{foo}(\pi/2)$ for cases where `foo` has been defined with a specific meaning. According to that document, cursive text ($f(x)$) should be used only for *generic* functions and variables.

I got the above information from this blog post by Nick Higham, which I found while I was writing this answer. Higham's post references the 2009 version of the standard, and includes a link to a more detailed summary by Claudio Becarri, written in 1997 and referencing a predecessor standard. Those resources are free, unlike the ISO standard, which costs CHF 166, or about five dollars per page.

---
Tags: parsers
---


# Question
Title: Why is flex the best choice for handling mathematical content? (a question about approach0)
This questions is about the work A novel similarity-search method for mathematical content in LaTeX markup and its implementation.

Mr. Wei Zhong uses flex lexer generator.

Now, supose I find an expression like $\pi(x)$, the Prime-counting function.

How to represent the prime-counting function correctly and not interpret $\pi$ as the number $3.14159$?

# Answer
The lexer doesn't interpret anything. It just separates the input into tokens. It's up to the parser to decide what the syntactic rôle of π is in that input.

It's possible that the thesis discusses that question; I didn't read it from end to end. But as far as I can see, the thesis never claims that the parsing tools used are "the best"; presumably, the author chose to use those particular tools because they were familiar with them, and saw how to apply them to the problem at hand. Moreover, the goal of the thesis is not to analyse arbitrary mathematical expressions in some abstract syntax; it is to analyse mathematical expressions written in LaTeX, and so the lexical analysis is, for better or worse, LaTeX specific.

Note that the "problem at hand" does not require accurate parsing of mathematical expressions. Wei's goal was to mine a large corpus for mathematical equations *similar to* a given search pattern, for some definition of "similarity". Presumably, in order to cope with the vagaries of mathematical expressions, the function application $f(\pi/2)$ is considered at least somewhat similar to the product $f\times(\pi/2)$.
> 1 votes

---
Tags: parsers
---


# Question
Title: What is the time complexity of removing among $N$ sets of size at most $n$ the sets which are subsets of another set?
A naïve solution would be to first sort all sets, taking time $O(N n \log n)$. Then, for every possible pair of sets, check if one is a subset of the other, and if applicable remove the subset. This checking and removing can all be done in time $O(N^2 n)$. The total time complexity would thus be $O(N n \log n + N^2 n)$, which if $N = \Theta(n)$ would be $O(n^3)$.

Is there a better way?

# Answer
> -1 votes
By Cunningham's law, this is the best possible time complexity.

---
Tags: algorithms, time-complexity, sets
---


# Question
Title: Example of preservation failing in Java - follow up question
This is a follow-up question to my previous question

I have been reading this post and it comes up with the following example showing how Java type system is unsound:

```
interface IFoo<T> {
    Number foo(T t);
}
class Foo<T extends Number> implements IFoo<T> {
    public Number foo(T t) { return t; }
}
Number bar(IFoo<String> foos) { return foos.foo("NaN"); }

```

And in the same post it talks about how we can never instantiate such `Foo<String>`. But does it really prove type system being unsound?

Also, based on the answer to the previous question, to prove type "Preservation" not happening, we need to prove type system being unsound. But this example can never be "evaluted" and then we check if after evaluation type is preserved because there is no such a `Foo<String>`. I am very confused.

# Answer
> -2 votes
The Java type system is strong. There are simply some errors that could, in theory, be reported at compile time that the Java Language Specification does not explicitly prohibit, and thus they are reported at run-time instead of compile time.

This really isn't that complicated, and it's all spelled out in the Java Language Specification and the Java Virtual Machine Specification. Please read those, then any of your remaining questions should be answerable.

https://docs.oracle.com/javase/specs/

---
Tags: programming-languages, lambda-calculus
---


# Question
Title: Definition of complexity of an algorithm
In a sorting algorithm, While computing the complexity of an algorithm why do we only account for the number of comparisons done but not the number of swappings done? And what's the formal definition of complexity?

# Answer
> 1 votes
The formal definition of complexity of an algorithm is the runtime in terms of the length of the input. Meaning, suppose you have a number with size n, to represent the number n you need $log\_2(n)$. Thus, the actual time complexity is the runtime relative to $log\_2(n)$ bits and not n.

For instance, when computing the complexity of an algorithm, it may run in a linear time in terms of the input size, however, not in terms of the input length.

I would encourage you to read about pseudo complexities. For example, say you have an algorithm that runs in $O(n^2)$, where $n$ is the size of the number. Since you need $log\_2(n)$ bits to represent the number n, the algorithm actually runs in an exponential time relative to its representational length in terms of bits.

Why an algorithm that runs in $O(n^2)$ in terms of the numerical value of the input is actually exponential?

As we said, to represent the number $n$, you need $x=log\_2(n)$ bits. Thus, this is equivalent to an exponential complexity in terms of x, where x is the number of bits of the numerical value. $O(2^{2x}) = O(2^{2log\_2(n)}) = O(n^2)$.

An algorithm that runs in a polynomial time relative to the size of the numerical value of the input, but runs in an exponential time in terms of the size of bits to represent the input are called pseudo-polynomial complexities.

This is why some algorithms which run in polynomial or even linear times aren't considered efficient.

As for your first question, as Yuval and Iqazra pointed out. In comparison-based sorting, the elementary operation is comparing between the input values.

In most comparison-based sorting algorithms, in order to swap two values with each other, you need to first compare them. Thus, in most cases, prior to swapping two values you will first need to compare them. You would need information about these two values in order to decide whether to swap them or not.

Take bubble sort for instance. The number of comparisons is $O(n^2)$, however, the number of swaps could be much less than that.

# Answer
> 1 votes
Good question. You are right, the running time of an algorithm is defined in terms of the total number of operations.

The reason is because in all standard comparison-based algorithms, the total running time $T$ is always at most some constant times the number of comparisons $P$. In other words, there is some constant $c$ such that

$$T \le c \cdot P.$$

Asymptotic running time ignores constant factors, so the two are basically equivalent as far as asymptotics are concerned.

For instance, if you have a comparison-based sorting algorithm that uses at most $P = O(n \log n)$ comparisons, then (assuming it satisfies the assumption above) the total running time will be $T = O(n \log n)$ as well. Usually it is the total running time we actually care about.

So, for these algorithms, whether you count the number of comparisons or the total running time (i.e., total number of operations), you get the same running time. It is often easier to count the number of comparisons.

---

Finally, there are lower bounds on the running time of comparison-based sorting algorithms. These work by lower-bounding the number of comparisons needed; they demonstrate that $P \ge \Omega(n \log n)$. It follows that $T \ge \Omega(n \log n)$ for all comparison-based sorting algorithms. The proof works by counting the number of comparisons, which is another, secondary reason why people may count the number of comparisons.

---
Tags: complexity-theory
---


# Question
Title: Find if there is more than one path between two vertices such that no vertices are used more than once
So I have an undirected graph G(V, E). We may assume there is always at least one path between any two vertices. I want to efficiently check if there are at least 2 different paths between *x* and *y* that have no vertices in common. (I'm pretty sure that) Equivalent problem would be to find if all paths between *x* and *y* go through a vertex (I don't need to know which one). My first idea was to just run a BFS, creating a list of paths and checking if all of the paths have a common vertex, however, I was wondering if there is a more efficient way.

# Answer
> 3 votes
You're asking about how to find a pair of vertex-disjoint paths from $x$ to $y$. You can use Suurballe's algorithm to solve this. See the "variations" part of that page for how to adapt it to find vertex-disjoint paths. Suurballe's algorithm works with directed graphs. You can convert an undirected graph to a directed graph by replacing each undirected edge $(u,v)$ with two directed edges $u \to v$, $v \to u$.

---
Tags: graphs
---


# Question
Title: What is the smallest NFA you can design for {a^n : n =/= 1003}
What is the smallest NFA that could be design for a^n where n!=1003?

I have been racking my brain at this for a while but still can't reduce the number of states required from 1004. Here state(1003) will be a rejecting state and all the other previous state will be accepting state. A transition from state(1003) to state(1004) will result in being in a Final state with a self loop on any concurrent a.

# Answer
> 1 votes
For each $i \in \\{0, \dots, 1003\\}$ let $p\_i = (a^i, a^{1003-i})$.

We can then invoke Theorem $1$ in \[1\] choosing $P = \\{p\_0, \dots, p\_{1003}\\}$ to conclude that a lower bound on the number of states of any NFA is $1004$.

It is easy to come up with a NFA that accepts the language using $1004$ states. Each state is labelled with an integer $i \in \\{0, \dots 1003\\}$ and, for each $i \< 1003$, there is a transition from $i$ to $i+1$ labeled "$a$".

See also this answer.

\[1\] Ian Glaister, Jeffrey Shallit. *A lower bound technique for the size of nondeterministic finite automata*, Information Processing Letters, Volume 59, Issue 2, 1996, Pages 75-77, ISSN 0020-0190, doi.org/10.1016/0020-0190(96)00095-6. Also accessible from the website of one of the authors.

---
Tags: turing-machines, finite-automata, nondeterminism
---


# Question
Title: Is there a name for this kind of binary tree?
While working on a math problem the following tree structure came up:

```
    o
     \
      o
     /
    o
   / \
  o   o
 / \ /

```

It is a binary tree with the following constraints:

* all nodes except the root have a left child
* all left-child nodes have a right child
* none of the right-child nodes have a right-child

It also has the following emerging properties:

* The nodes are indexable:
    + the root node has index `0`
    + for a given node indexed `n`, its left child has index `2n` and right child `n + 1`

```
    0
     \
      1
     /
    2
   / \
  4   3
 / \ /
8  5 6

```
* the number of edges at each level matches the fibonacci sequence:

```
    o
     \    1
      o
     /    1
    o
   / \    2
  o   o
 / \ /    3 // Then will be 5, 8 etc...

```

I would like to know more about this specific kind of tree, for example other emerging properties, what kind of problem it can help to solve or how is it typically used, but despite this seeming like a basic data structure I can't find any information on it. Searching for "fibonacci restricted tree" yields unrelated results such as Fibonacci Heaps.

# Questions:

* Is there an accepted name for this specific kind of binary tree?
* What are some examples of usage of this kind of tree in computer science?

# Answer
Just a quick association to your tree structures and Fibonacci numbers.

The numbering scheme and hence the tree structure seems related to the concept of *exponentiation by squaring*. The power of a number (or matrix) can be recursively computed as follows.

* $A^{2n} = A^n * A^n $
* $A^{2n+1} = A * A^{2n} $

In this formula you recognize the left and right branches of your trees.

Computer scientists usually learn this when they see the Fibonacci sequence in their programming course. Straightforward recursion of the Fibonacci numbers leads to an exponential number of recursive calls, much worse that computing the numbers iteratively from the bottom. The Fibonacci numbers can be computed using matrix squaring using the matrices $\left(\begin{array}{cc}1 & 1 \\ 1 & 0 \end{array}\right)^n = \left(\begin{array}{cc}F\_{n+1} & F\_{n} \\ F\_{n} & F\_{n-1} \end{array}\right)$.

The depth of the nodes is sequence A014701 in the On-Line Encyclopedia of Integer Sequences, "Number of multiplications to compute n-th power by the Chandah-sutra method".
> 3 votes

---
Tags: data-structures, trees, binary-trees
---


# Question
Title: Possibly Tractable Variation of Suguru Puzzles
I'm currently investigating the computational complexity of a modified one-dimensional Suguru puzzle. The general Suguru puzzles were recently proven to be NP-complete (see here). My investigation considers a modified one-dimensional Suguru puzzle played in a $1 \times N$ grid of cells. These cells are grouped into one or more regions of consecutive cells. Say there are $k$ regions, and let us label the region from left to right with $1,2,\dots,k$. Let us denote $s\_i$ as the size of the region $i$ (i.e., the number of cells in such a region). Initially, a cell is either empty or filled with a number ranging from 1 to $s\_r$, where $r$ is the region label where the cell belongs. Our goal is to fill all empty cells with numbers, such that region $i$ is filled with distinct numbers $1, 2, \dots s\_i$, and no two adjacent cells are filled with the same number. See the illustration below for example:

I have conducted some investigations. If all the cells in the grid are initially empty, then this problem can be easily solved in $O(N)$, where $N$ is the number of cells in the grid. The idea is to fill each region starting from the left-most cell with increasing numbers (starting from $1$). Then, we check for any adjacent cells with the same number and perform necessary swaps. I also found a particular case for this condition where we have no solution, that is, if there are two regions labeled with $L$ and $R$, such that $L \< R$, $s\_L = s\_R = 1$, and all regions between $L$ and $R$ (if any) are of size $2$.

If some cells are initially filled with numbers, I guess that finding a solution in polynomial time may be possible, but I have yet to find an algorithm for this case. My initial approach was to fill each region starting from the left-most cell using only available numbers, starting from the minimum available number (MEX), and do necessary swaps. See the illustration below for example:

However, performing the necessary swaps is not always easy, and things might get tricky. Consider the following case:

Moreover, there is also a case where the grid has no solution, similar to the case mentioned previously. See the illustration below:

Any ideas that might be helpful to solve this? Any help would be very much appreciated. If it is impossible to solve such a puzzle in polynomial time, is there any possible NP-complete problem that is reduced to this puzzle?

# Answer
> 2 votes
There is a simple linear-time algorithm that determines whether it is possible or find a possible way.

#### The algorithm for the decision problem

The idea is to collect the choices at the rightmost cell of each region, scanning regions from the leftmost region, i.e. region $1$ to the rightmost region, i.e. region $k$.

1. Check whether the initial configuration is valid, i.e., no two adjacent cells are filled with the same number. If not, return "NO".
2. Let $I\_i$ be the set of numbers from $1$ to $s\_i$ excluding the numbers given in the region $i$. $I\_i$ is the set of initial choices for each empty cell in region $i$. $|I\_i|$ is the number of empty cells in region $i$.
3. Consider region $1$. If its rightmost cell is empty, let $C\_1$ be $I\_1$. Otherwise, let $C\_1$ be the set of the only number that is in the rightmost cell.
4. Consider region $2$. All cells mentioned in this step are in region $2$.

We will construct $C\_2$ as the set of all possible numbers at the rightmost cell when we have filled regions up to region $2$ as required, i.e.,

* the numbers in region 2 are $1,2,\cdots,s\_2$ and
    * there is a number in $C\_1$ that is not the number in the leftmost cell.
    1. If $|I\_2|=1$, put the only number in $I\_2$ in the only empty cell.
    2. If $|C\_1|=1$ and the only number in $C\_1$ is in the leftmost cell, return "NO".
    3. If $|C\_1|=1$ and $|I\_2|=2$:
    Initialize $C\_2$ as an empty set. There are two ways to put the two numbers in $I\_2$ in the two empty cells. For each way, check if the number in the leftmost cell is the only number in $C\_1$. If not, add the number in the rightmost cell to $C\_2$.
    Skip step $4$ and $5$ right below (i.e., outer step 4 is done).
    4. If the rightmost cell is empty, let $C\_2$ be $I\_2$.
    5. Else the rightmost cell is not empty. Let $C\_2$ be the set of the only number that is in the rightmost cell.
5. Repeat step 4 above with each next region, replacing region $1$ with the current region and replacing region $2$ with the next region.
6. Return "YES".

#### Algorithm analysis

Note that whenever $C\_i$ has more than one element, we don't even have to construct it. All we need is to remember it has more than one element.

The time completely of the algorithm is $O(N)$ or, if implemented properly, about $O(n)$ where $n$ is the number of numbers that appear in the input.

If we add some bookkeeping to the algorithm, we can either find a way to fill the numbers as wanted or conclude there is no such way in linear time as well.

---
Tags: algorithms, time-complexity, np-complete, arrays, greedy-algorithms
---


# Question
Title: L is a recognizable undecidable language ,M is a Turing machine that recognizes L, does M reject or infinitely loop for s belonging to L-complement?
If $L$ is a decidable language, $M$ is a Turing machine that determines $L$. For $\forall s \in L$, M accepts, and for $\forall s \in \overline{L}$, M rejects

However, my question is that If $L$ is a recognizable undecidable language and $M$ is a Turing machine that recognizes $L$, for $\forall s \in L$, M accepts and for $\forall s \in \overline{L}$, M rejects or infinite loop? Or do both coexist, i.e., $\exists s \in \overline{L}$ and M rejects, and $\exists s \in \overline{L}$ and M infinitely loops?

# Answer
If $L$ is recognizable but not decidable, and $M$ is a Turing machine that recognizes $L$ then, for each $s \in \overline{L}$, $M(s)$ either rejects or it does not halt.

The behaviour of $M$ can differ for different choices of $s \in \overline{L}$, so it is definitely possible that there are $s\_1, s\_2 \in \overline{L}$ such that $M(s\_1)$ halts and rejects, while $M(s\_2)$ does not halt.
> 1 votes

---
Tags: turing-machines, decidability, turing-recognizable
---


title: Is this sorting problem NP-complete?

text:
# Question
Title: Is this sorting problem NP-complete?
Consider array $A=(a\_1,a\_2,...,a\_n)$ such that $a\_i$s are positive integers. Moreover, we have $k$ binary tuples, each with length $n$. In each iteration, we choose one of those tuples, and decrease it from the array. For example, if $A=(5,7,4,2)$ and we decrease $(1,0,0,1)$ from it, it will become $(4,7,4,1)$. We cannot use a tuple more than one time. Moreover, we know that sum of all those $k$ tuples is $A$. What is the minimum number of tuples we need to decrease from $A$, in order that $A$ be sorted in decreasing order?

I want to know whether it is an NP-hard problem.

Example: $A=\[2,3,4,5\]$

tuples=$(0,1,1,1),(0,0,1,1),(1,0,0,1),(1,0,1,1),(0,1,1,1),(0,1,0,0)$

The answer is 4. By subtracting (0,1,1,1),(0,1,1,1),(0,0,1,1) and (1,0,0,1), we will have \[1,1,1,1\] which is decreasingly sorted. We used 4 tuples, and it is not possible with fewer tuples(at least, I could not).

# Answer
> 1 votes
You can reduce from exact-cover by $3$-sets (X3C): given a set $X$ of $3n$ elements $x\_1, \dots, x\_n$, and a collection $S = \\{S\_1, \dots, S\_m\\}$ of $m$ sets each containing exactly $3$ elements, is there an exact cover, i.e., a subset $S'$ of $S$ such that $|S'|=n$ and $\cup\_{S\_j \in S'} S\_j = X$?

Consider the instance of your problem where:

* $A = (a\_0, a\_1, a\_2, a\_3, \dots a\_{3n}) = (3n, 3n, 3n-1, 3n-2, \dots 1)$ is an array of length $3n+1$ (for ease of notation I'm indexing the array from $0$) where $a\_0 = 3n$ and $a\_i = 3n-i$ for $i \ge 1$
* There is a tuple $t\_j$ for each set $S\_j$. The $i$-th entry (again, indexing from $0$) is set to $1$ in $t\_j$ if and only if $x\_i \in S\_j$.
* Suitably add a bunch of tuples, each with only a single entry set to $1$, in order to ensure that the sum of all tuples yields exactly $A$ (notice that only you need polynomially many tuples).

If there is an exact cover $S'$, then selecting all $t\_j$ such that $S\_j \in S'$ yields the array $(3n, 3n-1, 3n-2, \dots, 0)$.

If you can use $n$ tuples to transform $A$ into a decreasing vector, then each entry $a\_i$ with $i \ge 1$ is decreased at least once. Moreover, since each tuple has at most $3$ entries set to $1$, each entry $a\_i$ with $i \ge 1$ is decreased **exactly** once, while $a\_0$ is never decreased. This means that the collection of sets $S\_j$ such that $t\_j$ is a selected tuple is an exact cover.

To summarize, there is a solution to the instance of your problem using at most $n$ tuples if and only if there a solution to the X3C instance.

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


# Question
Title: Are the indices of variables in the formula variable?
Let $L$ be an arbitrary language in $\Sigma\_3$. Thus it can be written that $x \in L \Leftrightarrow \exists y^{p(|x|)} \forall z^{p(|x|)} \exists w^{p(|x|)} \langle x,y,z,w \rangle \in B$ where $p(\cdot)$ is some polynomial function and $B$ is some language in $P$.

While giving a reduction from $L$ to $\Sigma\_3$-SAT one uses Cook-Levin's idea to to create a formula $\phi$ s.t. $\phi$ is satisfiable $\Leftrightarrow$ $\langle x,y,z,w \rangle \in B$. But then the indices of variables in $\phi$ depend on $x,y,z,w$, i.e. $\phi$ changes with different values of $x,y,z,w$. Which does not make sense to me. Where am I going wrong ?

To elaborate the linked Cook-Levin proof uses the tableau method which creates new Boolean variables $T\_{isj}$ for each cell at index $i,j$ in the tableau, such that $T\_{isj}=1$ iff the cell has symbol $s$. While creating the formula $\phi$ one then adds unit clauses $T\_{0r\_11} \wedge T\_{0r\_22} \cdots \wedge T\_{0r\_kk}$ where $r\_1r\_2\cdots r\_k$ is the input string. Hence, the indices of the formula created depend on the input.

# Answer
> 1 votes
There seems to be a misunderstanding in the linked proof. If the input is $r\_1 \cdots r\_k$, then $T\_{i,r\_i,0}$ will be true for each $i=1,\dots,k$.

If $x\_i$ is the $i$th bit of $x$, so that $r\_i=x\_i$, then we have a clause $x\_i \Leftrightarrow T\_{i,1,0}$ and $\neg x\_i \Leftrightarrow T\_{i,0,0}$, both of which are easy to express as CNF clauses. You can do something similar for $y,z,w$.

---
Tags: complexity-theory, reductions, satisfiability, polynomial-time-reductions
---


# Question
Title: Logical vs physical address program loaded into RAM, how re-mapping done?
What are common primary mechanisms to "re-map" between physical memory in RAM, and the addresses used in a program before it is loaded into RAM? In image below for example, the LOAD 12 operation at address 01, must when program is running be loading the address 12 addresses from the "0 address" of the program (that in RAM could be anywhere I guess, depending on how much other shit is loaded into RAM. ) Is there something like a "0 equivalent", and then just a simple ADD operation to any address loaded, or, some other approach?

# Answer
What you are missing is that the addresses stored in an executable are actually virtual addresses. All processes have a full set of page tables filled with mostly zeroes to prevent one process from accessing the memory space of another process. They also "see" a full virtual address space that is several hundreds of TB on x86-64. The physical allocations are only limited by the amount of physical RAM + swap space to back the allocations.

There are lots of approaches to allocate physical memory. On x86-64 Linux for example, the page struct is used to keep track of the memory allocated and not allocated. The page structures are kept in kernel space in the upper half of the virtual address space. This portion of the virtual address space is marked as "global" in the page tables so they are shared among all processes and are most often not flushed from the cache (including TLB and page cache).

The page structures are arranged in an efficient binary structure and an efficient algorithm is used to determine during runtime what page is free and which isn't. Afterwards, it is simply a matter of building the page tables of the process by allocating space for these in the physical memory.

Since the process sees a full virtual address space, only the page tables determine where its memory accesses/instruction fetching will end up. Most executables today have a starting address but are mostly position-independent because they use RIP-relative addressing by default to access the data segment and everything else is "local" and is accessed from within the stack by using a relative negative offset from RBP. The starting address is often 0x400000 for some reason.

When the executable is loaded from the hard-disk, it actually contains the virtual addresses at which it will be loaded. For the operating-system, it is simply a matter of resolving where it will land in physical memory and to build the page tables so that the accesses won't mess with another executable's address space.
> 1 votes

# Answer
The program executes in its virtual address space, unaware of memory mapping. So READ 11 indeed reads from the virtual address 11.

Under the hood, address 11 is mapped somewhere in RAM (after the page has been mapped to RAM), and the exact location is irrelevant. It can change during program execution. How the mapping is done is the whole "virtual memory" story.

It is important to understand that the virtual spaces of all running programs do not interfere with each other, so they can use the same virtual locations.
> 1 votes

---
Tags: cpu, memory-hardware
---


# Question
Title: Encoding "all-except" constraints in CNF
I am looking for an efficient CNF encoding of the following situation: I have sets of boolean literals $A = \\{ a\_1, \ldots, a\_m \\}$, $B = \\{ b\_1,\ldots, b\_n \\}$ and subsets $B\_1, \ldots, B\_m$, where for all $i$ we have $B\_i \subseteq B$ and $|B\_i|\le 10$. I would like to encode the constraints $$ a\_i \to \bigwedge\_{b \in B \setminus B\_i} b\qquad (i = 1, \ldots, m) $$ into CNF. The arrow is logical implication. In other words: Each $a\_i$ should imply all elements of $B$ except those which are contained in the small set $B\_i$.

The naive encoding $\\{(\lnot a\_i \lor b)\\}\_{i = 1, \ldots, m,\ b \in B\setminus B\_i}$ requires $\mathcal{O}(n\cdot m)$ clauses. I am looking for an encoding that only requires $\mathcal{O}(n + m)$ clauses. I'm happy to introduce helper literals like in the Tseytin transformation.

## Progress

I have encodings using $\mathcal{O}(n + m\log n)$ and $\mathcal{O}(n\log n + m)$ clauses. Both constructions are inspired by tree data structures for Range-Minimum Queries.

### $\mathcal{O}(n + m\log n)$

Construct a binary tree of optimal height with $n$ leaves and assign one of the $a\_i$ to each leaf of the tree. Introduce a helper variable for each inner node of the tree. If $n$ is a literal assigned to an inner node of the tree and its children are assigned the literals $n'$ and $n''$, we have clauses $(\lnot n\lor n')$ and $(\lnot n\lor n'')$. Then it is easy to see that each "all-except" can be encoded using a logarithmic (in $n$) number of clauses of the form $(\lnot a\_i\lor n)$, where $n$ is the literal associated with a node in the tree.

### $\mathcal{O}(n \log n + m)$

This encoding is reminiscient of the sparse table data structure for RMQ.

We introduce helper literals $h\_{i, j}$ for $0\le j\le \log\_2 n$, $1 \le i\le n - 2^j + 1$ and have clauses $\\{(\lnot h\_{i, 0}\lor b\_i)\\}\_i$,$\\{(\lnot h\_{i, j + 1} \lor h\_{i, j})\\}\_{i, j}$, $\\{(\lnot h\_{i, j + 1}\lor h\_{i + 2^j, j})\\}\_{i, j}$. Using this, we can encode each constraint using at most 22 clauses, since it is possible to encode a rule of the form $a\_i \to b\_u \wedge b\_{u+1}\wedge \cdots \wedge b\_{v - 1} \wedge b\_v$ using only two additional clauses.

### Question

Is it possible to do it with $\mathcal{O}(n + m)$ clauses? I know that there are RMQ data structures with linear precomputation and constant queries, but it's not clear to me that their ideas are useful in my setting.

# Answer
> 1 votes
Let $\[b\]$ to denote $1$ if $b$ is true, $0$ if $b$ is false. We have $$ \begin{align} & \bigwedge\_{b \in B \setminus B\_i} b \\ \iff & \sum\_{b \in B \setminus B\_i} \[\neg b\] = 0 \\ \iff & \sum\_{b \in B} \[\neg b\] = \sum\_{b \in B\_i} \[\neg b\] \\ \end{align} $$

Therefore, an all-except constraint can be expressed in terms of sums of values $\[\neg b\]$. We can make variables of form $s\_{i,j} \iff \sum\_{b \in B\_i} \[\neg b\] = j$ for $j \leq |B\_i|$. Furthermore, variables for the LHS $t\_j \iff \sum\_{b \in B} b = j$ are needed only for $j \leq 10$. Therefore, the whole condition can be expressed using $O(n + m)$ auxiliary variables and clauses.

---
Tags: reference-request, satisfiability, constraint-satisfaction, modelling, constraint-programming
---


# Question
Title: How to find the standard theta notation of this?
Hi i am practising standard theta notation:

How could i find the standard theta notation of the following :

* `2n + 3n^2(log n)^3 + 2` and
* `((2n^2 + 7n+5)(7n+1))/7`

So far i have used the "drop constants and find dominating term" strategy where we remove the constants from the expressions and then we find the biggest and dominating value and i got:

* `Θ(n^2(logn)^3)` and
* `Θ(n^2)` respectively, however i am not sure if this is correct, could someone please help me out. Thank you.

# Answer
Perform this test:

* does $\dfrac{2n + 3n^2\log^3 n + 2}{3n^2\log^3n}$ tend to a constant ?
* does $\dfrac{(2n^2 + 7n+5)(7n+1)}{n^2}$ tend to a constant ?
> 1 votes

# Answer
* First Expression: $2n + 3n^2(log n)^3 + 2$ is indeed correct.
* Second Expression: $\dfrac{(2n^2 + 7n+5)(7n+1)}{7}$ is not correct. The leading expression of the second expression is $\dfrac{14}{7}$$n^3$ and not $2n^2$. It seems that you missed multiplying the two expressions by each other. Which give you the following: $\dfrac{14n^3 + 51n^2 + 42n + 5}{7}$. Thus, the leading expression is $\dfrac{14n^3}{7}$$=2n^3$.

Thus, the second expression would give you that it is $\Theta(2n^3)$.

I'd like to advise you to read more about the formal definition of the function $\Theta$, which requires you to know about the formal definitions of both $O$ and $\Omega$. In the expressions you gave, proving $\Theta(g(n))$ is easy. However, in many other expressions and algorithms , proving that $f(n) = \Theta(g(n))$ isn't easy. It would require you to prove both $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$.
> 0 votes

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


# Question
Title: Set of all vertices in a directed tree that are within distance of strictly larger than 2
As the title says, I'm trying to solve the question where:

Input: A directed tree $T = (V, E)$.

Output: The maximal subset $A \subseteq V$ of vertices such that there doesn't exist any two vertices $u, v \in A$ that have a directed path between of distance $2$ or less.

I thought of starting to append all of the leaves of the tree to the set $A$ and then start going upwards towards the root of the tree. However, I can't seem to solve the question.

# Answer
This question can be solved in 2 different approaches. The first approach is using Dynamic Programming, and the second approach this using Greedy algorithm approach.

* Greedy Approach:

$Algorithm$$:$

1. Create an empty set $A$.
2. Append all leaves $l \in T$ to $A$.
3. Remove all the leaves $l$, their parents, and their grandparents from $T$.
4. Repeat steps 2 and 3.

The correctness of this algorithm is classic. We can always prove that every leaf $l \in T$ is always in the set $A$.

This can be done using 'Proof by Contradiction'.

Assume that $A\_{OPT}$ is the maximal set of nodes that suffice the condition of the question. Denote the cardinality of $|A\_{OPT}| = c$. Assume by contradiction that there exist a leaf $l' \notin A$.

Consider the case where $l' \notin A\_{OPT}$, $parent(l') \notin A\_{OPT}$, and $grandParent(l') \notin A\_{OPT}$. Then, we can append $l'$ to the set $A\_{OPT}$ and get that $|A\_{OPT}| = c + 1$, thus contradicting the assumption that $A\_{OPT}$ was the maximal set of vertices that suffice the question's condition.

Consider the case where one of its grandparents is in A. Thus, we could remove its grandparent from $A\_{OPT}$ and append $l'$ to $A\_{OPT}$.
> 1 votes

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


# Question
Title: Solving recurrence relation with square root by reduction
This question has already been asked, but I still cannot understand how the substitution makes sense in the recurrence equation $$T(n)=2T(\sqrt{n})+1$$

Following the logic:

1. Substitute $n$ for $2^m$. This yields the equation:

$$ T(2^m)=2T(\sqrt{2^m})+1=2T(2^{m/2})+1 \\ \text{where } n = 2^m,\ m=\log\_2 n $$ Great, this makes sense because we can substitute $n$ back in for $2^m$ and then we get the original equation.

2. Now we introduce a new function $S(m)$ and we're going to say $S(m)$ = $T(2^m)$.
3. I don't believe this implies $m=2^m$, because that would not make sense. So we're saying we're defining a new function $S$ that takes parameter $m$ and simply returns the function $T$ with parameter $2^m$: $$S(m) \rightarrow T(2^m)=2T(\sqrt{2^m})+1=2T(2^{m/2})+1 $$
4. Fine, but since the $m$ is $S$ has no mathematical relationship to the $m$ in $T$, I'm going to rename $S(m)$ to be $S(x)$ to avoid confusion, so: $$S(x) \rightarrow T(2^m)=2T(\sqrt{2^m})+1=2T(2^{m/2})+1 $$
5. Now if we pass $x/2$ into $S$, we get: $$ S(x/2) \rightarrow T(2^{x/2})=2T(\sqrt{2^{x/2}})+1=2T(2^{{x/2}/2})+1=2T(2^{x/4})+1 \\ $$
6. Using the master theorem for $S(x/2)$, we get $O(\log x)$. However, since we have no equivalence of $x$ and $n$, then how do we substitute back to get $n$?

---

So this leads me to believe there must be some mathematical relationship between $S(m)$ and $T(2^m)$. If $2^m$ is substituted for $m$, I'm going to replace $x$ with $m$ again, because it doesn't make sense to me to use the same variable in a substitution and make it confusing.

1. Therefore: $$ S(x) = T(2^m)=2T(\sqrt{2^m})+1=2T(2^{m/2})+1 \\ S(x/2) = T(2^{x/2})=2T(\sqrt{2^{x/2}})+1=2T(2^{{x/2}/2})+1=2T(2^{x/4})+1 \\ \text{where } x=2^m $$
2. Now my problem with this is: If $x=2^m$, $m=\log x$, $m$ also equals $\log n$, therefore $\log x=\log n$, $n=x$.

If $x=n$ then $S(x/2)=\dots=2T(2^{n/4})+1$.

3. The master theorem says $S(x/2) = \Theta(log\_2(x))$.

Now $x=n$, so $\Theta(\log\_2 x)=\Theta(\log\_2 n)$, which is the right answer for $T(n)$. However: $$ 2T(2^{n/4})+1 \neq 2T(\sqrt{n})+1. $$ So, how can we say that the Big O of $S(x/2)$ is equivalent to the Big O of $T(n)$?

---

I obviously know I'm wrong. But the correct answer to this problem makes the math seem "hacky" and arbitrary. I can't seem to grasp how the logic maintains its equivalence?

Can someone help me understand how my thinking is wrong? If so, is there anyway to explain this without using $S(m)=T(2^m)$ because in either case I don't understand what this actually means.

# Answer
Here is the logical form of the argument.

1. The starting point is a function $T$ defined recursively.

(Comments: (1) Your definition misses a base case; (2) If you think of the input to $T$ as an integer, then $T$ is only defined for integers of the form $2^{2^k}$.)

2. Using $T$, we *define* another function $S$ by $S(m) = T(2^m)$. This function satisfies the recurrence $S(m) = 2S(m/2) + 1$, with base case $S(1) = T(2)$.

(Here we assume that the input to $S$ is an integer; so $S$ is only defined for integers of the form $2^k$.)

3. We find the asymptotic rate of growth of $S(m)$ to be $\Theta(m)$.

(In fact, $S(m)+1 = 2(S(m/2)+1)$, and so $S(m) = m(1 + S(1)) - 1$.)

4. Since $T(n) = S(\log\_2 n)$, we conclude that the asymptotic rate of growth of $T(n)$ is $\Theta(\log n)$.

(In fact, $T(2^m) = m(1 + T(2)) - 1$.)
> 0 votes

# Answer
The question is best answered with $n=2^{2^m}$ so that

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

This has the functional form

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

and it is no big deal to find the solution of the homogeneous recurrence $S\_h(m)=c\\,2^m$ and a particular solution $S\_p(m)=-1$.

Now,

$$S(m)=c\\,2^m-1$$ is another way to write

$$T(2^{2^m})=c\\,2^m-1$$ or

$$T(n)=c\\,\log\_2(n)-1.$$

---

As we can check,

$$2c\\,(\log\_2(\sqrt n)-1)+1=\frac22c\\,\log\_2(n)-2+1=c\\,\log\_2(n)-1.$$

---

The flaw in your reasoning is to think that "the $m$ in $S$ has no mathematical relationship to the $m$ in $T$". On the opposite it is the same variable, and $S(m)=T(2^{2^m})$ is an identity, also written $S(\log\_2(n))=T(2^n)$ or $S(\log\_2(\log\_2(n)))=T(n)$, which does define $S$ uniquely in terms of $T$.
> 0 votes

---
Tags: recurrence-relation
---


# Question
Title: Is this definition of the class P correct?
The definition of P is given by the union of all DTIME($n^k$) languages for $k \>= 0$, where DTIME($n^k$) is the set of languages for which there exist a TM time-bounded by $T(n) = O(n^k)$. However, this is where my confusion lies - if $T(n) = O(n^k)$, then $T(n) \<= c.n^k$ for $n \>= N$; but does this mean the TM can run in, i.e. exponential time for inputs smaller than $N$? So that would mean that a language can be considered to be in P even if it cannot get decided by a TM that runs in polynomial time on all inputs?

# Answer
> 1 votes
Suppose that $T(n) \le c \cdot n^k$ for all $n \ge n\_0$, where $n\_0$ is a constant and $k \ge 0$.

Define $c' = c+\max\_{n \<n\_0} T(n)$ and notice that, for all $n \ge 1$, the following holds: $$ T(n) \le c \cdot n^k + \max\_{n \<n\_0} T(n) \le \big(c + \max\_{n \<n\_0} T(n) \big) n^k = c' \cdot n^k. $$

# Answer
> 0 votes
In the definition of $O$, i.e. in the asymptotic sense, the behavior for $n\<N$ does not matter. What counts is the behavior towards infinity.

Think for a second: $n\<10\implies 10000\log(n+1)\>2^n$.

---
Tags: complexity-theory, turing-machines, polynomial-time
---


# Question
Title: Priority Queue - When Prioritizing Take Place?
In a Priority Queue we first enqueue according to the priority given to the element? Or we enqueue just like a queue but dequeue high the highest priority element first? Or both ways are acceptable?

# Answer
> 1 votes
The purpose of a priority queue is to get the elements by decreasing priority when they are initially unordered. So your first hypothesis does not hold.

(Of course you could enqueue in priority order, but then the queue can just be a FIFO.)

# Answer
> 0 votes
The underlying data structure is usually a heap, and the elements are partially ordered when it's initialized. At that point, the highest priority element is at the root of the heap ready to be popped next. When a new element is added to the heap it is added at the end and partial ordering is done bottom up; and when an element is removed the last element moved to the root and the partial ordering is done top down. So when implemented using a heap, the prioritization is maintained by partial ordering when initialized and when an element is added or removed.

---
Tags: data-structures
---


# Question
Title: Convert float array to lower or higher integer, find sum(integers) == round(sum(floats)), reducible to subset sum?
You have an array of floats, for example:

```
[74.45329758275943, 501.9063197679927, 172.59563201929095,
 307.1739798358187, 362.042263381624, 940.1282277740091,
 577.2604546481798, 63.201270419598224, 828.8081043649505, 31.1630295128974]

```

For each float, you can either call floor() or ceiling() to convert it to the nearest integer. The goal is to solve these two questions:

1. Choose floor or ceiling on each float to produce a set of integers where sum(integers) = round(sum(floats)).
2. Of the values that solve question 1, find the floor or ceiling choice that produces min(abs(float - int)), for each float/integer pair.

I *think* this is reducible to subset sum, and indicated as much during the quiz I just completed, but I wanted to check with people who have done reductions more frequently than me.

* Compute round(sum(floats) and subtract this value from each float in the array.
* Then for each of these "subtracted" floats, compute both floor and ceiling and put them in a new array with 2x the length of the old array.
* You now need to find a subset of these values, including both positive and negative integers, that sums to 0. However, you either need to choose the floor or the ceiling value for each of the original inputs, which limits the number of subsets that need to be searched.

I have not done an algorithms class in some time; is the analysis above correct, or am I missing something? Is this problem NP complete or is there a polynomial time solution?

# Answer
> 1 votes
Here is how I would solve this:

Denote $A$ as the array, which has $n$ values $A\_1,\dots,A\_n$. Without loss of generality, I will assume that there is no integer in $A$ (think of how to deal with the case that there is one!)

Lets start by computing $d:=round\left(\sum\_{i=1}^NA\_i\right)-\sum\_{i=1}^n{\lfloor A\_i \rfloor}$. Notice, that this tells us exactly for how many values we need to choose "ceiling" instead of floor: since each time we choose "ceiling" instead of "floor", we increase the total sum by $1$.

Therefore, for question $1$, the answer should be "choose any $d$ values you want to round up, and the rest to round down".

For question $2$, even though we already know we need exactly $d$ "round up"s, we need to choose them carefully in order to minimize the differences. But first, I want to clarify how I understood the question: The question, as I see it - asks us to minimize $\sum\_{i=1}^n { |A\_i-R\_i| }$ where $R\_i$ is the rounded $A\_i$, and also the solution has to satisfy that $\sum\_{i=1}^n R\_i = round \left(\sum\_{i=1}^n A\_i\right)$. The latter, we already saw how to achieve. Now whats left is to choose which things we round up correctly so we will minimize $\sum\_{i=1}^n |A\_i-R\_i|$.

For this task, let us compute a value $v\_i$ for every index $1\le i\le n$, such that $v\_i:= (A\_i - \lfloor A\_i \rfloor) - (\lceil A\_i \rceil - A\_i)$. Please take a moment to understand why $v\_i$ is the "loss" (or "gain") when we choose to round $A\_i$ up instead of down.

Now, we can rewrite the cost for $A\_i$ when we choose to round it up, as $|A\_i-\lfloor A\_i\rfloor | +v\_i $, and when we choose to round it down, the cost is $|A\_i-\lfloor A\_i \rfloor|$. Notice, how in both cases we had $|A\_i-\lfloor A\_i \rfloor |$. This means, that we can rewrite the total cost as follows: $Total~cost=\sum\_{i=1}^n { |A\_i-R\_i| }=\sum\_{i=1}^n |A\_i - \lfloor A\_i \rfloor| + s\_iv\_i$, where $s\_i\in \\{0,1\\}$ is $1$ if we choose to round $A\_i$ up, and $0$ if we choose to round it down.

In this sum, we cannot control the value of $|A\_i-\lfloor A\_i \rfloor |$ whatsoever, so when minimizing, all such terms disappear. This makes us now minimize the value of $\sum\_{i=1}^n s\_iv\_i$ (with exactly $d$ values of $s\_i$ being $1$, and the rest being $0$), which is equivalent to finding the $d$ smallest $v\_i$s, and choosing to round up the $A\_i$s that correspond to them - rounding down the rest of the values.

---

As you can see, this is a polynomial solution to the question. The problem with your reduction is that you did it the wrong direction. To show that a problem $L$ is NP-hard, using reductions - you need to show a reduction **from** subset sum, **to** $L$. What you showed is the other direction, hence the reduction doesn't imply that your problem is hard.

# Answer
> 0 votes
It's really quite simple.

Step 1: Calculate the target sum, which is round (sum (x\_i)). Let's say you get a value of 597.

Step 2: Calculate the sum that you get if you round every number down, that is sum (floor (x\_i)). Let's say you get a value of 594.

Step 3: Calculate how many values must be rounded up. In this case, 597 - 594 = 3 x\_i must be rounded up to get the required sum of 597.

Step 4: Determine which values to round up. You do this by finding (in this case) the three values where ceil (x\_i) - x\_i is largest.

Each of these steps is easily done in O (n) steps. So if you mentioned "subset-sum" problem to me and started to talk about NP and NP-complete, I'd be quite suspicious about your job application.

You would get bonus points if you talked about rounding errors and how to make sure that round (sum (x\_i)) is calculated correctly in the face of rounding errors. Or if you improved the speed and reduced rounding errors by combining my Step 1 and Step 2 into one (that's what nir shahar's solution does).

# Answer
> 0 votes
As stated, the part 2 may easily fail to be possible.

Take the numbers $0.2, 0.3, 0.4$. The rounded sum is $1$, but "min(abs(float - int))" rounds all three to $0$.

---
Tags: algorithms, complexity-theory, reductions, subset-sum
---


title: Dijkstra's shortest path algorithm

text:
# Question
Title: Dijkstra's shortest path algorithm
I am reading about algorithms to find the shortest path on a graph with one source, and I have a doubt about Dijkstra's algorithm about the negative weights on edges. In this case is Bellman-Ford algorithm a better solution for this part?

# Answer
Dijkstra's algorithm might solve some cases where there are negative edges in the graph. However, it doesn't solve for every graph that has a negative edge. For instance, if you have a negative cycle, Dijkstra won't work.

For graphs with negative weighted edges, you should use Bellman-Ford's algorithm.

If you want to find the shortest path from one source, then use Bellman-Ford on graphs with negative edges, and Dijkstra on graphs with non-negative edges.

If you want to find the shortest path for every pair of vertices $(u, v)$, then you can use Floyd-Warshall algorithm

I will leave you to determine, whether on graphs with non-negative edges, whether it is more efficient to run Dijkstra $n$ times where $n = |V|$, or to run Floyd-Warshall.
> 1 votes

---
Tags: shortest-path, dijkstras-algorithm
---


title: Data Structure And Algorithm

text:
# Question
Title: Data Structure And Algorithm
Given any singly linked-list L storing n real keys, that is, each key in L belongs to R, design an algorithm (either in words or in pseudocode) that computes the sum of the negative keys in L. What is the running time of your algorithm, in the worst-case, using O notation?

# Answer
> 0 votes
This is a basic question on linked lists.

You have to understand that for these types of problems, there are 2 different solutions. The iterative approach, or the recursive approach. Here, the iterative approach is easier.

* Iterative Approach:

1. Define a new variable, $Sum = 0$.
    2. Iterate through the list.
    3. Check the data of the list. If it's negative, add it to sum. $Sum$ $-$$=$ $list\rightarrow data$.
    4. Else, iterate to the next node in the list.
    5. Exit once you reach the last node. (last node means that $list\rightarrow next=NULL$

---
Tags: algorithms, time-complexity, data-structures, linked-lists
---


# Question
Title: How to make LR(1) grammar for sequence that cannot have more "Up" than "Down" for any given prefix?
I am working on a problem that asks me to write an LR(1) grammar that satisfies the following rules:

Consider a robot arm that accepts two commands: $\triangledown$ puts an apple in the bag and $\triangle$ takes an apple out of the bag. Assume the robot arm starts with an empty bag. A valid command sequence for the robot arm should have no prefix that contains more $\triangle$ commands than $\triangledown$ commands. As examples, $\triangledown$$\triangledown$$\triangle$$\triangle$ and $\triangledown$$\triangle$$\triangledown$ are valid command sequences, but $\triangledown$$\triangle$$\triangle$$\triangledown$ and $\triangledown$$\triangle$$\triangledown$$\triangle$$\triangle$ are not.

My first attempt considered the net number of motions of the robot arm. ZeroMotion is a sequence of steps that produce an equal number of $\triangle$ and $\triangledown$ steps, while DownMotion represents a sequence with more $\triangledown$ than $\triangle$. I'm almost certain that it's ambiguous.

Goal ----------\> DownMotion $\triangledown$
ZeroMotion ----\> ZeroMotion DownMotion $\triangle$ | DownMotion ZeroMotion $\triangle$ | $\triangledown$ $\triangle$
DownMotion ----\> $\triangledown$ ZeroMotion | $\triangledown$ DownMotion
where {$\triangledown$, $\triangle$} $\epsilon$ T, and {Goal, ZeroMotion, DownMotion} $\epsilon$ NT

I started anew, and came up with the new grammar below, which is closer, but also incorrect as it does not "keep track" of the number of surplus $\triangle$'s:

Goal ----------\> Goal DownMotion | DownMotion
ZeroMotion ----\> DownMotion $\triangle$ | $\epsilon$
DownMotion ----\> ZeroMotion DownMotion ZeroMotion | $\triangledown$
where {$\triangle$, $\triangledown$} $\epsilon$ T, and {Goal, ZeroMotion, DownMotion} $\epsilon$ NT

Can someone provide me with the correct answer?

\*** This problem is taken from Engineering a Compiler (Keith Cooper, Linda Torczon), 2nd edition, Chapter 3, exercise 11. \***

\** Yes, I posted a question about the same problem last night. But errors in my description made my problem unsolvable.

# Answer
> 1 votes
An earlier exercise in the same textbook asks you (in effect) to create a grammar for the balanced parenthesis language (disguised as a question about elevator motions) and then prove that your grammar is LL(1). The answer to that exercise is an important prerequisite for this one, so if you haven't done it yet, go back and try it now before you read this answer.

A language of balanced parentheses is called a *Dyck language* (named for the German mathematician Walther von Dyck, 1856-1934), and Dyck languages (which include the elevator language) are an important abstraction in almost every useful context-free grammar, since nesting sublanguages inside balanced delimiters is what context-free grammars excel at. (For a less informal description of why Dyck languages are fundamental, see the Chomsky-Schützenberger representation theorem.)

An obvious context-free grammar for it is: $$\begin{align}S\to\\;&\varepsilon\\ |\\;&(\\;S\\;)\\ |\\;&S\\;S \end{align} $$ But that grammar is ambigous (as is any CFG with a production of the form $N\to N...N$). Fortunately, it's easy to do better: $$\begin{align}S\to\\;&\varepsilon\\ |\\;&(\\;S\\;)\\;S \end{align} $$ That's the answer to the earlier question, leaving out the proof of unambiguity of the grammar. (Or, equivalently in this case, the proof that it's LL(1).)

Now, let's go to the exercise you are currently working on. An important insight is that the robotic apple language is nothing other than the language of *prefixes* of a Dyck language. In other words, you can turn it into a perfect Dyck language simply by emptying the bag at the end. (Or returning the elevator to the ground floor.) There are other ways to insert closing parentheses (or $\triangle$s), but adding them all at the end is the canonical solution. That corresponds to the idea that when we parse β the prefix of a Dyck language, we will match each close parenthesis with the most recent as-yet-unmatched open parenthesis, which is canonical in the sense that it is the way that the parentheses would be matched in any Dyck expression for which β is a prefix.

That might make you think about the classic "dangling-else" parsing problem, which is about how **else** keywords are matched with **if** keywords in a language in which **else** is optional and there is no end-marker for an **if** statement. (For example, C, although the issue goes back much further in the history of programming languages.)

(This particular ambiguity, along with the resolution shown below, is described in your textbook, in Chapter 3, so you should already be familiar with it. But I typed the following paragraph before checking the textbook.)

Now, there is a classic solution to the dangling-else problem, which has precisely to do with enforcing the matching rule described above: each **else** is matched with the most recent as-yet-unmatched **if**. The way this is enforced in a grammar is to insist that what comes between the **if** and the **else** in an *if-statement* cannot itself contain an unmatched **if**. If you have `if condition then if condition ... else`, the **else** can only match the first **if** in the case that the `...` includes an **else** so that the second **if** is matched. Otherwise, the **else** would have to match the second **if** because that one is more recent, and has not yet been matched.

Grammatically, that is written (in part): $$\begin{align} \textit{Statement}\to\\;&\textit{Matched-Statement}\\ |\\;&\textit{Unmatched-Statement}\\ \textit{Matched-Statement}\to\\;&\textbf{if}\\;\textit{Expression}\\;\textbf{then}\\;\textit{Matched-Stmt}\\;\textbf{else}\\;\textit{Matched-Statement}\\ |\\;&\textit{Other-Statement}\\ \textit{Unmatched-Statement}\to\\;&\textbf{if}\\;\textit{Expression}\\;\textbf{then}\\;\textit{Matched-Stmt}\\;\textbf{else}\\;\textit{Unmatched-Statement}\\ |\\;&\textbf{if}\\;\textit{Expression}\\;\textbf{then}\\;\textit{Statement}\\ \end{align} $$

The Dyck prefix language is not exactly the same. But it is similar enough that the solution should be evident from the above. So I suggest, again, that you try it yourself. But here is the slightly obscured solution:

> $$\begin{align}S\to\\;&B \mid I\\B\to\\;&\varepsilon\\\|\\;&\bigtriangledown\\;B\\;\bigtriangleup\\;B\\I\to\\;&\bigtriangledown\\;S\end{align}$$ (B = Balanced; I = Imbalanced (i.e. proper prefix)

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


# Question
Title: Detecting Data and Control Hazards for a mips 5 stage pipeline
I'm practicing data and control dependencies, but having trouble detecting them. For this example, I'm assuming this pipeline is fully bypassed (with forwarding). I think the only data dependency is i3 on i2. Is this correct? I also don't know how to detect the control dependency. I know there will be one because of the bne, but not sure how and on which one...

```
i1: lw $t0, 10($t1)
i2: lw $t4, 3($t2)
i3: addiu $t0, $t4, 3
i4: addu $t0, $t0, $t2
i5: addiu $t2, $t2, -8
i6: addiu $t1, $t1, -4
i7: bne $t1, $0, i1

```

# Answer
> 1 votes
There are no control dependencies in the code fragment. The non-transitive true (read-after-write) dependencies are:

* $i\_2\ \delta^f\ i\_3$ via register $t\_4$
* $i\_3\ \delta^f\ i\_4$ via register $t\_0$
* $i\_6\ \delta^f\ i\_7$ via register $t\_1$

There are also output (write-after-write) dependencies:

* $i\_1\ \delta^o\ i\_3$ via register $t\_0$
* $i\_3\ \delta^o\ i\_4$ via register $t\_0$

---
Tags: computer-architecture, cpu-pipelines, mips, assembly
---


title: Z-Specification = Routes

text:
# Question
Title: Z-Specification = Routes
Im trying to make an invariant for this Z schema about routes.

1) The invariant should express that each route should contain at least 20 different places. First of all i thought of doing a universal quantification such as:

∀x : ran routes • ( #x\>20 ∧ x ≠ x')

However i'm really not sure if thats correct that implying 20 different places.

# Answer
If you say

$\forall x, x': ran\ routes . x\<\>x'$

You're only saying that the sequences are different. For example

$\<London, Berlin, Paris\>$ would be different to $\<London, Paris, Berlin\>$

Instead, you need two quantifiers

$\forall x: ran\ routes . \\#x\>20$

and

$\forall p,p': Place • p \in ran\ (ran\ routes) \land p' \in ran\ (ran\ routes) \implies p\<\>p'$

One for the length as you had and one for the condition that all elements must be unique. Note the double $ran$ expression since a sequence is defined as a function between its indexes and its values (the range).
> 0 votes

# Answer
Reading this as "a route may have repeated places but it should have at least 20 different places", I'd formalise the invariant as follows, using that sequences themselves are finite maps from prefixes of the positive integers to the element type.

$\forall x: \mathrm{ran}~\mathit{routes} \cdot \\# (\mathrm{ran}~x) \geq 20$
> 0 votes

---
Tags: logic, first-order-logic, formal-methods
---


# Question
Title: Is Horn-SAT with XOR-relations NP-complete?
I was wondering if the combination of Horn-SAT and XOR-SAT is solvable in polynomial time or not.

It seems they can be solved in polynomial time as both are in class P and also that Horn-SAT is P-complete thus XOR-SAT must be reducible to HORN-SAT .

Just want to clarify if that's the case.

By,HORN-sat with XOR relation I mean a set of clause of the form :

$$ (\neg b \lor\neg d \neg c) \land (a \lor \neg b \lor \neg c) \land (b \oplus c \oplus d).$$ Is the set of clause of the form above solvable in polynomial time?

Reductions exist as shown in this question : https://cstheory.stackexchange.com/q/36704/67865 .

But this post shows that its impossible that such a reuction can exist : https://cstheory.stackexchange.com/q/46088/67865.

that;s why i wanted to clarify if they really can be solved in polynomial time and aren't those two post cotradicting each other?

# Answer
Note that we can express variable negation with XOR-clauses, that is, if we have a variable $x$, we can introduce a variable $x'$ and a XOR-clause $(x \oplus x')$, and now $x' = \lnot x$. Therefore, we can write arbitrary CNF:s as conjuctions of clauses with only negative literals and XOR-clauses, and therefore Horn-SAT with XOR-clauses is NP-complete.
> 2 votes

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


# Question
Title: Calculating XOR of all numbers from 1 to n: Why does this method work?
Given a number n, the task is to find the XOR of every number from 1 to n. Why does the following algorithm work?

1. Find the remainder of n by moduling it with 4.
2. If rem = 0, then XOR will be same as n.
3. If rem = 1, then XOR will be 1.
4. If rem = 2, then XOR will be n+1.
5. If rem = 3, then XOR will be 0.

# Answer
Here are two different ways to see this, first a more "direct reasoning" way and second by induction. Let $\oplus$ denote the XOR operation.

### Direct reasoning:

If $x$ is an even number, then what is $x \oplus (x + 1)$? Notice that because $x$ is even (ends in a $0$), $x + 1$ only modifies the last bit, so that all the other bits will be the same as $x$, and so they cancel out. Therefore, $x \oplus (x + 1) = 1$.

From this, we can "pair up" all the numbers in the whole compuation $1 \oplus 2 \oplus 3 \oplus ... \oplus n$: \begin{align\*} 0 \oplus 1 = 1 \\ 2 \oplus 3 = 1 \\ 4 \oplus 5 = 1 \\ \cdots \end{align\*} Here we have $\lfloor \frac{n+1}{2} \rfloor$ pairs which XOR out to $1$, and then possibly one lone $n$ left at the end. The result follows from this computation. For example, if $n$ is a multiple of $4$, there will be one number left at the end ($n$), and otherwise an even number of pairs with xor $1$, so all of those xor out to $0$, and we are left with $n$. If $n$ has remainder $3$ mod $4$, the pairing is exact and there are an even number of pairs, so the answer is $0$.

### Induction:

We can also see this by an induction argument. In the base case, $n = 0$, there are no numbers to xor so the xor is $0$. Or you can do $n = 1$ as a base case, to get xor $1$.

For the induction step, it depends on the case. For example: going from remainder 0 to remainder 1, we know that the previous answer was $(n-1)$, so now the answer is $(n-1) \oplus n = 1$ because $n-1$ only differs in the last bit. Going from remainder $1$ to remainder $2$, we know that the previous answer was $1$, and now we xor with $n$ so we will get $n \oplus 1$, which is the same as $n + 1$ since $n$ is even. The other cases are similar.
> 19 votes

# Answer
The process can be summarized by the four rules below (the right operand is the bitwise XOR up to the left operand minus one):

$$\begin{align} (4n+0)&\oplus0=4n\\ (4n+1)&\oplus4n=1\\ (4n+2)&\oplus1=4n+3\\ (4n+3)&\oplus(4n+3)=0\end{align}$$

E.g.

$$\begin{align} 101101|00&\oplus000000|00=101101|00\\ 101101|01&\oplus101101|00=000000|01\\ 101101|10&\oplus000000|01=101101|11\\ 101101|11&\oplus101101|11=000000|00\end{align}$$
> 10 votes

# Answer
Add 0 to the xor sum, which doesn't change it.

Then split the sum into groups of four from 4k to 4k+3, which will always have an xor of 0.

Depending on n modulo 4, these groups cover everything, or there is n = 4k left, or n, n+1 = 4k, 4k+1 left, or n, n+1, n+2 = 4k, 4k+1 and 4k+2 left. Calculate the xor of these 1, 2, or 3 numbers, and you have the result.
> 6 votes

---
Tags: bit-manipulation, xor
---