# Question
Title: Time Complexity of Quicksort when using Median Pivot in sorted array
I am looking for any literature or reference for the worst case complexity of using quicksort on a sorted array with median as pivot. Different internet sources give conflicting answers and often skip this exact question or don't give logic for their answer

Can someone explain whether is it O(nlogn) or O(n^2) and why so when the array is sorted and we pick the middle element as pivot in constant time

I looked at a lot of questions on quicksort and I don't believe this has been asked before in the current form fairly close questions have been addressed

# Answer
Here is another "worst case" that isn't a sorted array, so the algorithm won't be making useless partitions, which seemed to be your concern. Consider the array $\[10,30,50,70,90,100,80,60,40,20\]$

Picking the median (100) as the pivot, the first partition of elements clearly takes $n$ time. If we pick the median (now 90) as the pivot again then the second partition will take $n-1$ time since the subarrays to the left and right are divided in the most unbalanced possible way. Observe how this is simply arranging one element at a time, as all the remaining elements only go to one side of the partition. With this logic, the next partition takes $n-2$ time, and so on. In such a worst case, we will have to do this for $n$ steps to finish the algorithm, making the time complexity equal to $$n+(n-1)+(n-2)+ \dots + 2=\frac{n(n-1)}{2}-1=O(n^2).$$

Interestingly, this is analogous to Selection Sort, which indeed takes $O(n^2) $ time.

As many would have mentioned, a way to improve quicksort in order to avoid such cases would be to pick a pivot uniformly at random. Note that this too, will have some *worst* case, but it can be shown that the probability of such a "bad" event happening every time is small.
> 2 votes

# Answer
"the array is sorted and we pick the middle element as pivot in constant time" -- If the array is *known* to be sorted, you don't need to do anything! What is typically being considered is the case when the array *happens* to be sorted, and the program still has to work correctly no matter what order the array is in.

As for the time complexity, it depends on the details. Using the Median of medians algorithm (note that this gives an *approximate* median) results in an overall time complexity of $O(n \log n)$ (but as that page notes, this is not often used in practise because of its large constant factor).

There are some common versions of quicksort that use the median *of a small number of elements* (as opposed to the median *of the whole array*) as the pivot; these have $O(n^2)$ worst-case time complexity, occurring when the small number of elements considered are always the lowest or highest. On an already sorted array, using the median of the first, middle, and last elements (one common choice) will select an optimal pivot and have $O(n \log n)$ time complexity in this case, whereas using the median of the first three elements, say, will have $O(n^2)$ time complexity in this case.
> 1 votes

# Answer
Because of your input array $A\[1...n\]$ already sorted:

First check the size of the $A$ in constant time, so if size of array is odd then the median is $A\[\lfloor\frac{n}{2}\rfloor\]$ that can be obtain in constant time, because you have access to each indices of array $A$ in $\mathcal{O}(1)$. But if the size of array is even, you free to choose $A\[\frac{n}{2}\]$ as median or $A\[\frac{n}{2}+1\]$ as median, so we compute median in $\mathcal{O}(1)$, hence the running time of Quick sort is $$T(n)=2T(\frac{n}{2})+\mathcal{O}(1)=\mathcal{O}(n).$$

**Note that, because the algorithm choose median as pivot then it partition input to half, so the worst case isn't occur.**
> 1 votes

---
Tags: quicksort
---


# Question
Title: Are there any specific problems known to be undecidable for reasons other than diagonalization, self-reference, or reducibility?
Every undecidable problem that I know of falls into one of the following categories:

1. Problems that are undecidable because of diagonalization (indirect self-reference). These problems, like the halting problem, are undecidable because you could use a purported decider for the language to construct a TM whose behavior leads to a contradiction. You could also lump many undecidable problems about Kolmogorov complexity into this camp.
2. Problems that are undecidable due to direct self-reference. For example, the universal language can be shown to be undecidable for the following reason: if it were decidable, then it would be possible to use Kleene's recursion theorem to build a TM that gets its own encoding, ask whether it will accept its own input, then does the opposite.
3. Problems that are undecidable due to reductions from existing undecidable problems. Good examples here include the Post Correspondence Problem (reduction from the halting problem) and the Entscheidungsproblem.

When I teach computability theory to my students, many students pick up on this as well and often ask me if there are any problems we can prove are undecidable without ultimately tracing back to some kind of self-reference trickery. I can prove nonconstructively that there are infinitely many undecidable problems by a simple cardinality argument relating the number of TMs to the number of languages, but this doesn't give a specific example of an undecidable language.

Are there any languages known to be undecidable for reasons that aren't listed above? If so, what are they and what techniques were used to show their undecidability?

# Answer
Yes, there are such proofs. They are based on the Low Basis Theorem.

See this answer to Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization? question on cstheory for more.
> 11 votes

# Answer
this is not exactly an affirmative answer, but an attempt at something nearby to what is asked for via a creative angle. there are quite a few problems in physics now that are "far distant" from mathematical/ theoretical formulations of undecidability, and they seem increasingly "remote" from and "bear little resemblance to" the original formulations involving the halting problem etc.; of course they use the halting problem at the root but the chains of reasoning have become increasingly distant and also have a strong "applied" aspect/ nature. unfortunately there do not seem to be any great surveys in this area yet. a recent problem that was "surprisingly" proven undecidable in physics that has attracted a lot of attention:

> The spectral gap—the energy difference between the ground state and first excited state of a system—is central to quantum many-body physics. Many challenging open problems, such as the Haldane conjecture, the question of the existence of gapped topological spin liquid phases, and the Yang–Mills gap conjecture, concern spectral gaps. These and other problems are particular cases of the general spectral gap problem: given the Hamiltonian of a quantum many-body system, is it gapped or gapless? Here we prove that this is an undecidable problem. Specifically, we construct families of quantum spin systems on a two-dimensional lattice with translationally invariant, nearest-neighbour interactions, for which the spectral gap problem is undecidable. This result extends to undecidability of other low-energy properties, such as the existence of algebraically decaying ground-state correlations.

what you seem to be observing in the question is that (informally) undecidability proofs all have a certain "self-referential" structure, and this has been formally proven in even more advanced mathematics, such that both the Turing halting problem and Godels theorem can be seen as instances of the same underlying phenomenon. see eg:

> The halting theorem, Cantor's theorem (the non-isomorphism of a set and its powerset), and Goedel's incompleteness theorem are all instances of the Lawvere fixed point theorem, which says that for any cartesian closed category, if there is an epimorphic map e:A→(A⇒B) then every f:B→B has a fixed point.

there is also a long meditation on this theme of the (intrinsic?) interconnectedness of self-referentiality and undecidability in the books by Hofstadter. another area where undecidability results are common and were initially somewhat "surprising" is with fractal phenomena. the crosscutting appearance/ significance of undecidable phenomena across nature is nearly a recognized physical principle at this point, first observed by Wolfram as "principle of computational equivalence".
> 0 votes

# Answer
This is a really interesting question and I also had this question before when I learn computability theory. Here I give an alternative angle to view this question. In the following paragraphs I assume that the formal system that I use is first-order logic.

If you can prove that a problem P is undecidable, then you have at least one “proof” showing that “P is undecidable”. Since the set of all possible proofs is countable, we can conclude that the set of undecidable problems that you can formally prove the undecidability is also countable. But the set of all undecidable problems is uncountable, which means most undecidable problems cannot be proved to be undecidable at all.

On the other hand, if you can show a countably infinite set of undecidable problems where each problem’s undecidability can be proved via self-reference, you can at least show that the cardinality of the set of “provably undecidable problems” and the cardinality of the set of “undecidable problems provable by self-reference” are the same. This might not be an interesting result, but if we can go one step further and prove something like “all/almost all provably undecidable problems could be proved to be undecidable by self-reference”, I think that will be interesting enough.

Regarding specific proof techniques, I don’t know non-self-reference techniques for proving undecidability but I can make an informal argument stating that those techniques may not exist for certain undecidable problems. In program analysis, which is a research area trying to design (incomplete) analyzers to inform programs’ non-trivial properties, according to Rice’s theorem, non-trivial extensional properties of programs are undecidable. For such undecidable problems, different program analyzers give different “precisions” (e.g. the number of programs that they can precisely analyze). This might imply that the undecidability indeed depends on the analyzer itself because for a specific program, whether its property could be precisely analyzed via a given analyzer depends on the analyzer itself. As a result, I feel that a proof showing the undecidability of program analysis (the non-existence of complete program analyzers) tends to somehow mention the analyzer itself, which constitutes a “self-reference”. Of course I’m talking about the prove-by-contradiction route “assuming that a complete analyzer exists”.
> 0 votes

---
Tags: computability, proof-techniques, undecidability
---


# Question
Title: How to prove that the generalized assignment problem (GAP) is NP-hard?
Specifically, what NP-hard problem can we reduce (the decisions version of) GAP to and how do we prove its correctness?

The decision version of the generalized assignment problem is to determine whether there exists an assignment where every job is fulfilled (as opposed to maximizing the number of jobs that can be fulfilled).

# Answer
Copied from Wikipedia:

> In the special case in which all the agents' budgets and all tasks' costs are equal to 1, this problem reduces to the assignment problem. When the costs and profits of all tasks do not vary between different agents, this problem reduces to the multiple knapsack problem. If there is a single agent, then, this problem reduces to the knapsack problem.
> 1 votes

---
Tags: np-complete, np-hard, np, decision-problem, assignment-problem
---


# Question
Title: Finding a maximum subarray in worst-case linear time
Here's a problem of CLRS:

Use the following ideas to develop a nonrecursive, linear-time algorithm for the maximum-subarray problem. Start at the left end of the array, and progress toward the right, keeping track of the maximum subarray seen so far. Knowing a maximum subarray of $A\[1..j\]$, extend the answer to find a maximum subarray ending at index $j + 1$ by using the following observation: a maximum subarray of $A\[1..j + 1\]$ is either a maximum subarray of $A\[1..j\]$ or a subarray $A\[i..j + 1\]$, for some $1 \leq i \leq j + 1$. Determine a maximum subarray of the form $A\[i..j + 1\]$ in constant time based on knowing a maximum subarray ending at index $j$.

Now this is a solution to it:

```
ITERATIVE-FIND-MAXIMUM-SUBARRAY(A)
 n = A.length
 max-sum = -∞
 sum = -∞
 for j = 1 to n:
     currentHigh = j
     if sum > 0:
         sum = sum + A[j]
     else
         currentLow = j
         sum = A[j]
     if sum > max-sum:
         max-sum = sum
         low = currentLow
         high = currentHigh
 return (low, high, max-sum)

```

I understand how `max-sum` is indeed the sum of a maximum subarray but I can't figure out how `low` and `high` are the indices of such a subarray. I don't know what the procedure is and how it updates these variables in each iteration. Any ideas?

# Answer
> 1 votes
`sum` computes the value of maximum subarray of the form $A\[i..j+1\]$. And, `currentlow` is $i$ and `currenthigh` is $j+1$. Note that `currenthigh` is incrementing in every iteration by $1$ that means it is pointing to current $j$ always.

If `sum>0` (value of maximum subarray of the form $A\[i..j\]$), then it is always better to make `new-sum = sum + A[j+1]` because then `sum + A[j+1] > A[j+1,j+1]` irrespective of whether $A\[j+1\]$ is negative or positive. Here, `new-sum`: value of maximum subarray of the form $A\[i..j+1\]$.

Similarly, if `sum<0`, then it is always better to make the `new-sum = A[j+1,j+1]` because `sum + A[j+1] < A[j+1][j+1]` irrespective of whether $A\[j+1\]$ is negative or positive.

Therefore, the correct `sum` is computed in the first `if else` statement.

After that, you are right that `max-sum` is the value of maximum subarray of $A\[1,j+1\]$. And, `low` and `high` are its indices. Note that they do not change unless `sum` \> `max-sum` that should be the case as per the DP method.

---
Tags: maximum-subarray
---


# Question
Title: Complexity of LTL realizability of safety games with Next operator only
It is known that the computational complexity of deciding whether an LTL specification is realizable in a safety game is **2EXP**-complete (that is, you receive an LTL formula, where some variables belong to the *environment* and some to the *system*, and you ask if it's possible for the system to always satisfy the specification, at every point in time, no matter what the environment does).

I am interested in the particular case where the specification contains Next as the only temporal operator. Given such a restricted specification, where X is the only temporal operator, what is the complexity of deciding realizability? Is it known?

I am considering here a temporal formula $\psi$ containing X as the only temporal operator, and where we ask for $\psi$ to be satisfied at every point in time, i.e., $\text{G }\psi$.

My intuition is that this should be **EXP**-complete, but I do not have a proof.

EDIT: as mentioned in the answers below, I am interested in safety specifications of the form $\alpha \land \text{G } \psi$ where $\alpha$ is a Boolean formula over system variables specifying the initial conditions (no temporal operators here) and $\psi$ contains X as the only temporal operator, so that the only instance of G is the one at the front of $\psi$. The question is about the complexity of checking realizability of $\alpha \land \text{G } \psi$.

# Answer
Indeed, the complexity of the reactive synthesis problem is lower if the only temporal operator allowed in the LTL specification is the Next-Time operation.

Let's consider the case that there is no occurrence of the "globally" operator first. Your complexity estimate can be refined to PSPACE-completeness then.

The canonical problem for PSPACE-completeness is the validity problem for quantified Boolean formulas (QBF). It is essentially equivalent to your problem, from which the claimed computational complexity follows.

In a QBF problem, you are given a Boolean formula $\psi$ over a set of variables $\\{x^1\_1, \ldots, x^1\_{n\_1}, y^2\_1, \ldots, y^2\_{n\_2}, \ldots, x^m\_{1}, \ldots, x^m\_{n\_m}\\}$ and you ask the question if

$$\exists x^1\_1, \ldots, x^1\_{n\_1} \forall y^2\_1, \ldots, y^2\_{n\_2} \exists \ldots \exists x^m\_{1}, \ldots, x^m\_{n\_m}. \psi$$

is $\mathbf{true}$ or $\mathbf{false}$. This is very similar to your LTL-with-only-next realizability problem. If you have such a specification, you can compute the number $k$ representing the deepest Next-nesting. After both environment and system decided their first $k$ input and output variable values, it is fixed whether the specification is satisfied on any (infinite) extension of their decisions. If you store the decisions of the environment and the system in the first $k$ steps into separate Boolean variables, then you can modify the LTL formula to replace all variable names by their respective new variable names in the step of the execution they refer to. The next-time operator occurrences can then be removed. Then you have a problem that looks exactly like the QBF problem above.

Note that you can also do this translation in the reverse direction. The only non-straight-forward aspect is that on every quantification level, the number of variables in constant in the reactive synthesis problem. But by using sufficiently many input/output variables in the synthesis problem and ignoring the unused variable values in the specification, this aspect can be addressed.

I am not aware of this complexity result being mentioned in any paper - it's certainly not a result that is sufficient for a paper on its own. The paper "Deterministic Generators and Games for LTL Fragments" by Alur and La Torre (2001) does not seem to discuss your particular case, and it probably the most well-known one discussing syntactic LTL restrictions in the scope of reactive synthesis. There may be some paper proving PSPACE-completeness of your result as a lemma, though.

Now let's consider the case that there is a globally operator spanning the most of the LTL formula. The problem becomes APSPACE=EXPTIME-complete in this case. You can encode the acceptance of a alternating polynomial-space Turing machine into the realizability problem restricted to this case and vice versa.

Let's consider containment in APSPACE first. For this, you reduce the non-realizability of an LTL specification of your particular shape to the acceptance by an alternating Turing machine with a polynomail space bound. Starting from your specification, you can compute the maximal number of nesting of the next-time operator. Let this number be $k$. You then encode a polynomially space-bounded Turing machine that always keeps track of the last $k$ values of the input and output variables. This allows you to check $\psi$ locally on these values. You assign the task to choose input proposition values to the existential non-determinism, and output proposition values to the universal non-determinism. You encode the Turing machine to accept if eventually the specification is violated, i.e., if the last $k$ variable valuations do not satisfy $\psi$. If the specification is realizable, the Turing machine does not accept. If it's realizable, it accepts.

Now let's consider APSPACE-hardness. For this, you encode the non-acceptance of the empty word of an alternating Turing machine to the realizability problem of your particular shape. Let's assume that the specification shape should be $\alpha \wedge \mathbf{G}(\psi)$. You allocate enough output propositions to output the complete tape content of the Turing machine (times two) along with the state of the Turing machine and the position on the tape. In $\alpha$, you encode that initially, the machine should be in the middle of the tape in the initial state. You use an input proposition to resolve universal non-determinism of the Turing machine. In $\psi$, you encode that the output proposition value changes encode the transition function/relation of the Turing machine, where the input propositions are used to choose successor state/value combinations for universal non-determinism. Finally, you add a conjunct in $\psi$ requiring that accepting states in the Turing machine are never visited.

If your specification is of the form $\mathbf{G}(\psi)$ and not $\alpha \wedge \mathbf{G}(\psi)$, you need to apply a little trick. You add an input proposition for resetting the execution. Whenever the reset proposition is 1, the Turing tape content and machine start is reset to the start. Otherwise, simulation of the Turing machine works as before. In this way, you don't need the $\alpha$ component for EXPTIME-hardness.

Doing the latter proof fully precise is tricky, as it requires you to also reason about executions of the Turing machine on which the tape boundaries are exceeded. There are some details that make a full formal proof rather lenghty.
> 1 votes

---
Tags: complexity-theory, time-complexity, game-theory, linear-temporal-logic
---


# Question
Title: What is the original input for the halting question
I was reading about the halting problem recently, but I couldn't quite figure something out. We take $H(x,y)$ to be a program which works out if program $x$ with input $y$ halts, and $H\_2(x,y)$ to be a program which works out $H(x,y)$ and then does the opposite (if $x$ halts, $H\_2$ loops, else $H\_2$ ends). The halting problem as I understand it goes $H\_2(x,x)$, $H\_2$ will do the opposite of $x(x)$, thus $H\_2(H\_2)$ will do the opposite of itself and hence a contradiction. My issue here is that the inner $H\_2$ requires an input as well, so what is that? If it has no input then the whole proof seems to be flawed, as it is equivalent to saying "What is $x^2$ if $x$ is orange". If the inner $H\_2$'s input is another set of the same ($H\_2(H\_2(H\_2))$) then what is the new innermost one's input? And so on and so forth.

Furthermore, does the proof not assume that both $H\_2$ (outside brackets) and $H\_2$ (inside brackets) are the same, as $H\_2(H\_2)$ does the opposite of what is inside of its brackets, meaning that $H\_2$ (code form) and $H\_2$ (function form) are two fundamentally different things and so properties of one are not the same as properties of another?

# Answer
> 0 votes
The halting problem was a mathematical problem proposed by Hilbert & Ackermann. What you are studying is the classic proof of the halting problem's undecidabilty as given by Turing. To better understand the proof's formal structure, you might read this summary, beginning at "Is the Halting Problem Decidable?"

That will answer your question. And the gist of it is, the machine that induces the contradiction only needs one argument because the argument is a program which takes itself as its own input.

# Answer
> 0 votes
You actually define $H\_2$ to get only one input $x$, and simulate what you said when running with $H(x,x)$. Basically, $H\_2(x)$ loops if $H(x,x)="true"$ and otherwise halts. Then, the proof continues by asking what value $H\_2(\langle H\_2\rangle)$ gets, where $\langle H\_2 \rangle$ is the *text* representing the turing machine $H\_2$.

---
Tags: halting-problem
---


# Question
Title: Apparently weaker form of big O notation
If instead of saying there exists some $C \in \mathbb{R}^{+}$ and $N \in \mathbb{N}$ such that for any $n \geq N$ we have $f(n) \leq Cg(n)$ we say that there is some $C \in \mathbb{R}^{+}$ and some subsequence $(f(n\_{k}))\_{k \in \mathbb{N}}$ with $(n\_{k})\_{k \in \mathbb{N}}$ strictly increasing such that for any $k \in \mathbb{N}$ $f(n\_{k}) \leq Cg(n\_{k})$, Is it a weaker condition? Or is it equivalent to $f(n) = O(g(n))$? Let it be or not, it reminds me of some theorems about sequences in mathematical analysis. Technique of change of variables made me ask this question.

# Answer
> 3 votes
Let's get the terminology straight: when we have $A \Leftrightarrow B$, then we call $A$ and $B$ equivalent and its natural to say, that they are equally stronger. When we have $A \Rightarrow B$, but not $B \Rightarrow A$ ($B\nRightarrow A$), then we call $A$ more strong (look here or here).

Outgoing from stated, your suggestion gives more weaker condition, because, $f\in O(g)$ in usual sense implies $f\in O(g)$ in new sense, but not reverse, as shows example: $$f(n)=\begin{cases}1, n \text{ is odd}\\ n, n \text{ is even} \end{cases}$$ this function will be in "new" $O(1)$, but not in usual $O(1)$.

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


title: Why does IP = PSPACE

text:
# Question
Title: Why does IP = PSPACE
Can anyone give an intuitive explanation to why IP = PSPACE, or at least one direction of it?

I looked at many research papers but its very hard to understand the formalism unless you have a solid background in Turing machines and complexity theory. I'm an undergraduate.

# Answer
> 1 votes
I found it most easy to understand according to reference here for undergrad level:

> It's easy to show that IP $\subseteq$ PSPACE . Suppose L ∈ IP . Then we have some verifier V for L. The PSPACE algorithm we use to decide L is to compute z = max Pr\[V ↔ P accepts w\] . By the definition of IP , if z ≥ 2/3 , then we know that w ∈ L. If z ≤ 1/3 , then we know that w !∈ L. Note that if V is a verifier for L, 1/3 \< z \< 2/3 will never occur.

> Now we need to show that it's possible to compute z in PSPACE. Suppose V runs in p(n) steps, where n = |w|. Then any given response by P is no longer than p(n). Also, V chooses at most p(n) random numbers. We may recursively simulate V while branching for each random number, and each possible response by P. Therefore, the recursion depth is *polynomial*, so we can perform such a recursion in PSPACE. We keep a count of the accepting branches produced by P's optimal responses, as well as the total number of branches. These numbers will be *exponential* in n, but the length of the numerical representation is *polynomial* in n. The ratio computed by this PSPACE algorithm is z, therefore IP $\subseteq$ PSPACE.

Another related intuition is imagine a limit case where a subset of IP is the deterministic Interactive Proof class, which is similar to IP but has a deterministic verifier. This class is equal to NP and thus we can kind of intuited this subset of IP = NP $\subseteq$ PSPACE. The other direction, however, is much harder from the same reference:

> Recall that TQBF, the language of true quantified boolean formulas, is PSPACE-complete. Therefore, PSPACE ⇔ TQBF ∈ IP. The goal of this paper will be to show TQBF ∈ IP, hence IP = PSPACE...

I'm no expert here, hope this will be somewhat helpful.

---
Tags: complexity-theory, space-complexity, lower-bounds, upper-bound, interactive-proof-systems
---


title: Algorithm notation

text:
# Question
Title: Algorithm notation
I am reading Nancy Lynch's Distributed Algorithms.

In page 103, there is the FloodSet algorithm. Can anyone please explain what Uj mean in W := W U Uj xj (line 3 of transition function)?

# Answer
is the *n-ary union* operator, similar to how  is the *n-ary addition* operator.

So, in the same way that *j someExpressionDependingOnJ* means "add the values of all the different instances of *someExpressionDependingOnJ* ranging over all *j*s together", *j someExpressionDependingOnJ* means "union the values of all the different instances of *someExpressionDependingOnJ* ranging over all *j*s together".

*X* here is the dictionary of all messages indexed by the message sender, *Xj* is the message from sender *j* in the dictionary.

Putting all of that together, *j Xj* is the union of all messages.
> 6 votes

# Answer
Possibly suitable is also to bring general formal definition of union with respect to indexed family:

Suppose we have set $X$, called indices set, and for each $\alpha \in X$ is defined some $U\_\alpha$ set. Then, by definition, set $$\bigcup\limits\_{\alpha \in X}U\_\alpha=\\{x\colon \exists \alpha \in X, x\in U\_\alpha\\}$$
is called union with respect to indexed family $\\{U\_\alpha\\}\_{\alpha \in X}$. If, for example, we take $X=\\{1,2\\}$, then we obtain usual union of two sets. For $X=\\{1, \cdots, n\\}$ it is union with respect to $n$ sets asked OP.
> 2 votes

---
Tags: algorithms, distributed-systems, consensus
---


# Question
Title: What is the approximation ratio of this bin-backing algorithm?
Consider the following algorithm for bin packing:

0. Initially, sort the items by their size.
1. Put the largest item in a new bin.
2. Fill the bin with small items in ascending order of size, up to the largest item that fits.
3. Close the bin. If some items remain, go back to step 1.

There is a very similar algorithm for the dual problem of bin covering, and its approximation ratio for that problem is 3/2. However, I did not find this algorithm discussed in the context of bin packing.

Is anything known about its approximation ratio - how close it is to the optimal solution?

# Answer
> 2 votes
We show that $\mathrm{ALG} \le (3/2) \mathrm{OPT} + 1$, and in some cases $\mathrm{ALG} \ge (3/2) \mathrm{OPT} -1/2$ even when the number of items is big enough. There is still a gap between the two results. Hope someone else can improve this result.

Consider an instance produced by your algorithm. Suppose the bins are opened in order $b\_1,\ldots, b\_n$. Let $b\_i$ be the bin such that $i=\max\\{i\neq n\mid b\_i\text{ contains exactly one item}\\}$. Then we can conclude that for each bin $b\_j$ where $j\le i$, there exists one item with size greater than 1/2. We call these items big items. In any optimal solution, we must also use $i$ bins to pack these big items. Suppose, besides these big items, there are also $k$ items $t\_1,\ldots,t\_k$ in the first $i$ bins. Observing that $t\_1,\ldots,t\_k$ are the smallest $k$ items and the $(k+1)$-th smallest item cannot be fit in any bin with a big item, we can conclude the items in the first $i$ bins are packed in an optimal way. In the rest of the proof, we will assume each bin, except the last one, contains at least two items.

Suppose the items used in step 1 are $h\_1,\cdots, h\_n$ in order and the rest items from small to big are $t\_1,\ldots,t\_m$. We have $t\_1\le\cdots\le t\_m\le h\_n\le\cdots \le h\_1$. Suppose bin $b\_i$ has a space of $s\_i$ that are not used. Recall that we assume each of $b\_1,\ldots,b\_{n-1}$ contains at least two items. We have $s\_1+\cdots+s\_{n-1}\<t\_1+\cdots+t\_m+h\_n$ due to step 2 of your algorithm, thus $s\_1+\cdots+s\_n\<t\_1+\cdots+t\_m+1$. Note $s\_1+\cdots+s\_n+t\_1+\cdots+t\_m+h\_1+\cdots+h\_n=n$ and $s\_i\<h\_{i+1}$ for $i\<n$, we have $s\_1+\cdots+s\_n\<(n+2)/3$. This means $\mathrm{ALG} \le (3/2) \mathrm{OPT} + 1$.

On the other hand, consider an instance with the following items (from small to large), where $\epsilon$ is a small number:

$$ \left\\{\frac{1}{3}-6^k\epsilon,~~\frac{1}{3}-6^{k-1}\epsilon,~~\frac{1}{3}-6^{k-1}\epsilon, ~~ \text{ for } k = n, n-1,\ldots, 1\right\\}, \\ \frac{1}{3}-\epsilon, \\ \left\\{\frac{1}{3}+2\times 6^{k-1}\epsilon,~~ \frac{1}{3}+3\times 6^{k-1}\epsilon,~~\frac{1}{3}+3\times 6^{k-1}\epsilon ~~ \text{ for } k = 1,\ldots, n\right\\}, \\ \frac{1}{3}+2\times 6^n\epsilon. $$

The optimal solution uses $2n+1$ bins: $$ \left\\{\frac{1}{3}-6^{k}\epsilon,~~ \frac{1}{3}+3\times 6^{k-1}\epsilon,~~\frac{1}{3}+3\times 6^{k-1}\epsilon ~~ \text{ for } k = 1,\ldots, n\right\\}, \\ \left\\{\frac{1}{3}-6^{k-1}\epsilon,~~ \frac{1}{3}-6^{k-1}\epsilon,~~\frac{1}{3}+2\times 6^{k-1}\epsilon ~~ \text{ for } k = 1,\ldots, n\right\\}, \\ \frac{1}{3}-\epsilon, \frac{1}{3}+2\times 6^n\epsilon. $$ But your algorithm uses $3n+1$ bins (each bin contains two items). Hence in this case $\mathrm{ALG} = (3/2) \mathrm{OPT} -1/2$.

---
Tags: algorithms, optimization, approximation, heuristics, packing
---


# Question
Title: Can partially observable MDPs be fully observable nonetheless?
I've read through a few definitions of a partially observable environment/MDP, and I need confirmation whether the *partial observability* is really a *generalization* of a MDP (misnomer) and not a *required* feature, just like when we call nondeterministic automata the union of a) deterministic automata and b) (what I like to call) the actually nondeterministic automata.

The question can be satisfied simply by answering: Is tic-tac-toe partially observable?

# Answer
> 1 votes
Every MDP can be transformed into a POMDP (partially observable MDP), such that the signal (observation) is the state itself. There is no benefit in doing so, but it is still a valid transformation.

In this sense, Tic-Tac-Toe is fully observable (you see the entire state you are in, and not a partial signal from it), and hence can be transformed into a partially observable MDP.

---
Tags: terminology
---


title: Recursive Prefix-Sums K times

text:
# Question
Title: Recursive Prefix-Sums K times
I have been wondering about the following question for quite some time:

You are given an array $x$. Define f(x) as the prefix sums of this array.

For example, f(\[1,0,1\]) = \[1,1,2\] and f(f(\[1,0,1\])) = \[1,2,4\].

Define $k$ to be the recursive depths of a series of f(x) (how many times it is nested).

For example, f(f(x)) has $k$ = 2, and f(f(f(f(x)))) has $k$ = 4.

Given an array $x$, calculate f(x) with $k$ depth.

Any ideas?

# Answer
A simple solution will take $O(nK)$ time where $n$ is length of array. Just repeat $K$ iterations over the array.

But you can be clever if $K$ is large. View this as a matrix multiplication. The matrix will be just lower triangular with all entries one.

Now matrix multiplication is associative, so you can take product of matrix multiplications even before you know the array.

Furthermore, you don't need to naively take product of matrices $K$ times, just use the idea of repeated squaring.
> 1 votes

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


# Question
Title: An Alternative History of Haskell: being lazy without class?
\[The q is a play on the title of this 2007 survey of Haskell.\]

tl;dr I have a couple of connected questions about Haskell's overloading mechanisms. I'll ask first then explain why. I'm looking at the discussions when overloading was 'discovered' around 1988/1989, and imagining how would some of the alternative designs have worked out, if we knew then what we know now. (I'll maybe add more material/references if commenters ask.)

1. Is it essential for typeclasses to be able to bundle together more than one method? Or would it work to have each method in a separate class, with superclass constraints to link methods (as for example `Eq` is a superclass of `Num`)?
2. If we have one method per class, do we really need classes? Or could we just express overloading direct over the methods?

**1. One method per class?**

A frequent complaint about the `Prelude` class `Num` is that it bundles together all arithmetic operators. But mathematical purity says we should have an Additive class, a Multiplicative class, etc, etc, with Additive being a superclass of Multiplicative.

If we make an `instance Num` for some datatype, we must define an implementation for every operator whether or not it makes sense. (Or if you don't declare an implementation, the compiler gives you one anyway, that returns `undefined` *at run time*.) What we want for operators that don't make sense over that datatype is a rejection at compile time.

Aside from Mathematical purity, there's a particularly down to earth problem/source of much puzzlement on StackOverflow: `Num` includes method `fromInteger`. There's a hidden call to `fromInteger` built into every integer literal. (Which is to say that what looks like a literal in any other programming language is not a literal in Haskell.) Say your `Num` instance is for arithmetic over vectors or matrixes. If you put

```
x :: Vector
x = 10

```

Most newbies expect a compile fail: they forgot to wrap the literal in a constructor to turn it into a vector. Instead, it compiles and if you're lucky, fails at run time with `undefined`; or perhaps happily executes and gives puzzling results.

Changing the design of `Num` now is just too hard, so we live with it; but what if we could start afresh and separate concerns for the operators? Would we end up with each operator in a separate class?

And similar questions for the other `Prelude` classes with multiple methods. (Plenty of them have a single method anyway. But for example there's grumbling from people who want a `Monad` without `return`.)

**2. Overload the methods; don't need no `class`**

The very first design for overloading section 1 of Wadler's 1988 memo -- and I mean before the early 1989 paper with Blott -- doesn't mention `class`. It just wades right in and declares a bunch of operators as overloadable, with their type signature; then gives instances for them.

I read section 1 as setting up something of a straw man: at the end it points out some difficulties, which section 2 remedies (with `class`). But I see some mis-steps in section 1, so the difficulties can be avoided without introducing a new entity into the language IMHO. (This is no criticism of Wadler: it's amazing how much he anticipated so early on.)

The term `class` Wadler draws straight from OOP. But oh woe!

Haskell classes are not very like OOP classes: there's no class inheritance/subtyping; there's no encapsulation of data; there's no information hiding. (Haskell can do all those things, but the concerns are separated into other mechanisms.)

And the confusion it causes learners coming to Haskell from OOP languages is immense. Perhaps Haskell could use another term.

But rather: with only one method per class, just cut out the middle man. We still implement as dictionary-passing (after all, the dictionary gets passed to a version of the method, as an extra invisible argument); the class gets type-erased anyway; we can attach the evidence-passing to the method rather than the class(?)

In type inference, we express constraints (wanted or given) as "needs an overload for `(+)` at type `Vector`", etc. (I won't deflect into pondering syntax: it would need method names appearing in type signatures; which would probably have caused palpitations in 1988; but nowadays we're happy to put types in terms with explicit type application; so why not *vice versa*?)

# Answer
I was thinking about lots of these things. I do consider typeclasses one of the less principled parts of Haskell, in that they don't derive directly from theoretical ideas, being more pragmatic.

One nitpick:

> with superclass constraints to link methods (as for example Eq is a superclass of Num)?

If a typeclass is not a grouping of multiple methods, what is the point of subclassing? It seems a bit awkward to have typeclasses that contain multiple methods, but can only be implemented one at a time. Direct method overloading seems to make more sense.

As mentioned in the comments, typeclasses group methods together conveniently. Amongst other things, this prevents context blowup: you'd have to enumerate every method you use in the context.

I think you'd only gain, not lose in expressiveness by having overloading over methods.

My proposal for overloading in a future Haskell would be as follows:

## Overloading idea

1. Individual **methods** declared as abstract and overloadable - type signature only, no implementation.
2. **Constraints** which group zero or more of the following:

* Superclass constraints
    * (Already declared) methods
    * Laws over the methods - you can then enable automatic testing.

(Combinations of) types would then be declared/**asserted** as implementing a constraint, to ensure their method instances are law-abiding.

Functions can then be constrained on `Constraint` or `Has(method)`.

It would also be convenient to include **implications** \- if a (combination of) types implements a constraint *A*, this is what implementation it will have for methods `a...n`. This would make it easier to define constraints such that *'If a type implements *A*, its *B* instance looks like this'*. We have a few of these, even in `base`, and no convenient way of expressing them. However, I have no idea if these implications would be decidable.

This would allow unlawful types like `Set` to implement `map` but not `Functor`, and you choose which one to constrain on depending on whether you need (or want) the laws.

As a bonus, it will also make it easier to implement 'burning bridges' changes like Foldable Traversable and Applicative Monad while breaking less code.
> 1 votes

---
Tags: type-theory, haskell
---


# Question
Title: Is this explanation confusing NP-hard and NP-complete?
My notes on P vs NP say the following:

> Every problem x in the NP-hard class has the following properties:
> – There is no known polynomial-time algorithm for x.
> – The only known algorithms take exponential time.
> – If you could solve x in polynomial-time, then you could solve them all in polynomial-time.

The last point sounds like it's confusing NP-hard with NP-complete. I would appreciate it if someone would please clarify this.

# Answer
The text is indeed incorrect for NP-hard problems and correct for NP-complete problems.

NP is the class of decision problems for which, given a problem instance and a candidate solution, the correctness of the solution can be verified with a polynomial-time algorithm. Another equivalent definition is that NP is the class of decision problems that can be solved in polynomial time by a Non-deterministic Turing Machine.

NP-hard problems are informally "decision problems at least as hard as the hardest problems in NP". A more rigorous definition is that a problem $P$ is NP-hard if every problem in NP can be reduced to $P$ in polynomial time: that is, knowing a polynomial-time algorithm for solving $P$ would allow us to solve any problem in NP in polynomial time by reduction to $P$. The text you provided suggests that this would extend to solving all problems in NP-hard in polynomial time, which is incorrect: notably NP-hard includes decision problems that are not solvable in the first place, such as the famous Halting problem. The text would be correct if it said "...then you could solve any problem in NP in polynomial time".

NP-complete problems are problems that are both NP and NP-hard: informally, they are the hardest problems of NP. Since they are in NP, it would indeed hold that solving one of them in polynomial time would imply the possibility of solving any of them in polynomial time.
> 1 votes

# Answer
The last part is wrong. Should be "If you could solve x in polynomial-time, then you could solve **every NP-complete problem** in polynomial-time"

And the difference between NP-complete and NP-hard is: If an instance of an NP-complete problem has the answer YES, then you can guess a proof that can be verified in polynomial time. That's not (necessarily) true for NP-hard problems.

All NP-complete problems are essentially equally hard (up to polynomial changes in size and execution time); NP-hard problems are not.
> 1 votes

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


title: HDD and SSD addressing

text:
# Question
Title: HDD and SSD addressing
I have a doubt about HDD and SSD addressing. Could someone explain me what is the minimum addressable unity for HDD and SSD? In the case of RAM, we can address the single byte. But I presume that HDD and SSD have a a different behavior. Thank you

# Answer
This is all about physics.

On an SSD drive you can read blocks, usually 4K, in constant time. You can set non-zero bits in a block in constant time. And you can set a larger block, often 128 or 256 Kbyte, to all bits zero. That means, to modify a block, you either need to know that it is all bits zero, or find a new location for the block in a zeroed area, or erase a larger block first.

On a hard drive, you can read or write a complete sector. The time needed depends on how long it takes for the physical sector to appear under the read head. To make access faster, the firmware of the drive will cache blocks in RAM, start reading a track once it is under the read head in case the data is used later, and cache data to be written to combine multiple writes if possible.

There's a new technology called "shingled drives", where you gain data density, but only can write in places where the next inner track is not used, because a write operation writes over the inner track. This is fine when you write gigabytes of consecutive data, but not when you constantly modify single blocks.
> 1 votes

# Answer
An operating system can address and access any external storage (like HDD or SSD) at the individual byte level - such way is usually called a Raw Disk. However, the actual reading and writing data at the **hardware** level normally happens in blocks.

Each RAM data byte passes through many software and hardware **levels** before it's stored on the magnetic surface (or anywhere else), and these levels may differ for different operating systems and hardware - so it's impossible to talk about general behavior of HDD and SSD without clearly defining this abstraction level.
> 0 votes

---
Tags: memory-management
---


# Question
Title: Can reading a value of a variable kill the definition of the variable?
I was going through the concept of *reaching definitions* from the red dragon book.

The authors define *reaching definitions* as follows:

> Definition: We say a definition $d$ reaches a point $p$ if there is a path from the point immediately following $d$ to $p$, such that $d$ is not "killed" along that path.

Then the authors consider a flow graph and explain the definition with an example as follows:

> For example, both the definitions `i:=m-1` and `j:=n` in block $B\_1$ in Fig. above reach the beginning of block $B\_2$, as does the definition `j:=j-1`, provided there are no assignments to or ***reads of `j`*** in $B\_4$, $B\_5$, or the portion of $B\_3$ following that definition.

I can understand that in $B\_4$, $B\_5$, or the portion of $B\_3$ following that definition `j:=j-1` if there is an assignment to `j` then the definition $d\_5$ is killed. But what problem shall be there if there is simply a **read of the value `j`**? How does it kill the definition $d\_5$ and prevent it from reaching the top of $B\_2$?

# Answer
> 1 votes
I can't find the errata sheet for the 1st edition (this came from the first ed, right? That diagram is so 1980's) but it sure looks like a mistake. The 2nd edition says

> "We say a definition d reaches a point p if there is a path from the point immediately following d to p such that d is not "killed" along that path. We kill a definition of a variable x if there is any other definition of x anywhere along the path. ... A definition of a variable x is a statement that assigns, or may assign, a value to x"

So I agree with your doubts, pretty certainly a read can't kill (just reading a variable can't change program state).

---
Tags: compilers, data-flow-analysis
---


# Question
Title: Why {${xww|x,w∈(a+b)^*}$} is regular but {${ww|w∈(a+b)^*}$} is not $? $
I read this site example 12 that {${xww|x,w∈(a+b)^\*}$} the set of strings generated by language $L$ is {${ϵ,a,b,aa,ab,ba,bb,aaa,…}$} by taking always $w$ as $\epsilon$ and $x$$(a+b)^∗$. But my question is why they taking always $w$ as $\epsilon$ to prove it is regular. In that same logic why $ww$ isn't regular by taking $w$ as $\epsilon$?

# Answer
If you take $w=\varepsilon$ in the second language, you can only create the word $ww = \varepsilon \varepsilon = \varepsilon$. This is not the case in the first language because of the $x$ factor that gives you all the freedom of choice you need.
> 5 votes

# Answer
We know that , any language is a subset of $\Sigma^\*$. Hence union $\Sigma^\*$ with any other languages is $\Sigma^\*$. Note that $x$ is $\Sigma^\*$, and one of the strings that can be obtained from $ww$ is $\epsilon$, so concatenation $x$ with $ww$ can be as bellow:

$$\Sigma^\*\cup \dots=\Sigma^\*.$$

So actually $L$ is $\Sigma^\*$ that already we know it's regular, because there is DFA for it.
> 1 votes

---
Tags: turing-machines, regular-languages, finite-automata, context-free, pushdown-automata
---


# Question
Title: Why are Recursive Enumerable Languages closed under union?
Union of two REL is closed under union. I don't understand how is it closed. I followed this link. The have stated:

> Here the trick is to simulate both M1 and M2 “simultaneously”. In other words, we design a machine that executes one step of M1, followed by one step of M2, then again one step of M1 and so on.

My question is if the word doesn't belong to either of the machines then how did they decide that the output will be closed? Both the machines can be in an infinite loop and we cannot decide if the word belongs to the language accepted by M1 of M2.

What am I missing here? Also, is there any relation between halting and closure properties of turning recognizable languages?

# Answer
"Closed under union" means that if $L\_1,L\_2\in RE$, then $L\_1\cup L\_2\in RE$.

The machine you described will indeed accept a word $w$ if $w\in L\_1\cup L\_2$. If $w\notin L\_1\cup L\_2$, then machine might not halt. But that is fine, since we only want to show that the language is in $RE$, not $R$.
> 3 votes

---
Tags: turing-machines, closure-properties
---


# Question
Title: A program which works "digitally" and a program that works "analogue"
I have noted that in several very unrelated human natural languages, people often confuse the term "virtual" with "digital".

As for Computer Science, is it correct to categorize all software whatsoever to "digital" or "analogue" (by means of how programs work)?

# Answer
> 1 votes
In Computer Science, we don't really talk about "software". But we *do* talk about *algorithms* and *models of computation*, and also sometimes about *computing machines*.

When we think about *algorithms*, there are two ways in which they can operate over either discrete or continuous domains:

* The algorithm can operate on *discrete* values (for example, integers or bits) or *continuous* values (for example real numbers).
* The algorithm can consist of *discrete* "steps", or it can operate in a *continuous* manner.

All four combinations are possible: algorithms that operate on discrete values in steps, algorithms that operate on continuous values in steps, algorithms that operate continuously on discrete values, and algorithms that operate continuously on continuous values.

Algorithms that operate on discrete values in discrete steps are called *digital algorithms*. Computing machines that work in discrete steps on discrete values are called *digital computers*. A digital computer can only execute digital algorithms. All "typical" computers are digital computers: your phone, your laptop, your desktop, the various cloud services, supercomputers, it doesn't matter. All of them are digital computers and thus can only execute digital algorithms.

For example, "computers" (by which I mean what the layperson would recognize as a computer) *cannot* work with real numbers. You would need infinite storage, infinite time, or both. Instead, we use floating point numbers, for example, which are a limited precision *approximation* of real numbers.

Algorithms that operate continuously on continuous values are called *analog algorithms*. And computing machines that work continuously on continuous values are called *analog computers*. The most famous analog computer, and probably one of the oldest computers in general, is the *Antikythera Mechanism*, a 2000+ year old computer for astronomical predictions. The most widely-used analog computer, and one that (depending on your age) you may have even used yourself, is a *slide rule*.

I don't think the other two combinations have specific names.

So, in short, we can call a program for a digital computer (i.e. what we normally think about as a "computer") a *digital program*, and we can call a program for an analog computer an *analog program*. Although most analog computers are not programmable, they are fixed-purpose computing machines, so the idea of a "program" doesn't really make sense for them. (Unless you consider the way that the parts are put together, e.g. in a slide rule, the "program". Or you could consider the instructions for a human how to operate a slide rule the "program".)

---
Tags: terminology
---


# Question
Title: Context free grammar for strings with more $a$'s than $b$'s
I would like to prove that the grammar $G$ with the rules $$ S \to SS \mid aSb \mid bSa \mid a \mid \varepsilon $$ generates the language $L = \\{w \mid \text{$w$ has at least as many $a$'s as $b$'s}\\}$.

### Question

My proof is below, but it feels rather clunky and unintuitive. Does anyone have an alternative proof and/or suggestions for how I can improve what I have?

### Proof

**Step 1.** First, we will show that $\mathcal{L}(G) \subseteq L$. This is immediate from the fact that no rule generates more $b$'s than $a$'s. Let $w \in \mathcal{L}(G)$, generated by $G$ via $S = u\_1 \Rightarrow \dots \Rightarrow u\_n = w$. In each step where a $b$ is added, an $a$ must also be added. Because $w\_1$ has an equal number of $a$'s and $b$'s, each subsequent $w\_i$ must have at least many $a$'s than $b$'s. Therefore, $w\_n \in L$, and so $\mathcal{L}(G) \subseteq L$.

**Step 2.** Next, we will show that $G$ generates all strings with an equal number of $a$'s and $b$'s. Let $K$ be the set of all such strings. We argue by induction to show that $K \subseteq \mathcal{L}(G)$.

*Base step.* Let $w \in K$ such that $|w| = 0$. Then $w$ can be generated by $G$ via $S \Rightarrow \varepsilon$.

*Inductive step.* Suppose $G$ can generate any string in $K$ length less than or equal to $n$. Let $w \in K$ such that $|w| = n + 1$. We distinguish several cases:

1. $w = aub$ for some string $u$. Because $w$ has an equal number of $a$'s and $b$'s, $u$ must also have an equal number of $a$'s and $b$'s. This implies $u \in K$, and by the inductive hypothesis, $S \Rightarrow^\* u$. Thus, $w$ is generated by $G$ via $S \Rightarrow aSb \Rightarrow^\* aub$.
2. $w = bua$ for some string $u$. This is the same as the previous case.
3. $w$ starts and ends with $a$. But because $w$ has the same number of $a$'s and $b$'s, there must be a point where the number of $b$'s “catches up” with the number of $a$'s. This implies $w = uv$, where $u, v \in K$ are non-empty. By the inductive hypothesis, $S \Rightarrow^\* u$ and $S \Rightarrow^\* v$. Thus, $w$ is generated by $G$ via $S \Rightarrow SS \Rightarrow^\* uS \Rightarrow^\* uv$.

By induction, we conclude that $K \subseteq \mathcal{L}(G)$.

**Step 3.** Finally, we will show that $L \subseteq \mathcal{L}(G)$. Let $w \in L$. Consider the first occurrence of $b$ in $w$. I claim that this occurrence of $b$ must be contained in some substring of $w$ that has an equal number of $a$'s and $b$'s. To see this, we consider several cases:

1. $w$ starts with $a$. Then there is an $a$ to the left of $w$, so $ab$ is a substring of $w$ that contains the first occurrence of $b$.
2. $w$ starts with $b$. Because $w$ has at least as many $a$'s as $b$'s, there must be some prefix of $w$ that has an equal number of $a$'s and $b$'s.

Identify the largest possible substring and call it $v\_1$. Note that $v\_1 \in K$. Then $w = u\_1v\_1x$, where $u\_1$ consists solely of $a$'s. Note that $x$ must have at least as many $a$'s as $b$'s. If not, then one can write $u\_1 = y\_1y\_2$ and construct a substring $y\_2v\_1x \in K$. But because $v\_1$ was the largest possible substring, this is a contradiction.

Repeat this procedure for the first occurrence of $b$ within $x$ to get $x = u\_2v\_2y$. Then repeat this procedure for the first occurrence of $b$ within $y$. Doing this until no more $b$'s remain, we can write $w$ as $u\_1v\_1u\_2v\_2\dots u\_nv\_nu\_{n+1}$, where each $u\_i$ contains only $a$'s and each $x\_i \in K$. Because $K \subseteq \mathcal{L}(G)$ and $G$ can clearly generate any string consisting solely of $a$'s, $w$ can be generated by $G$ via

$$ S \Rightarrow^\* \underbrace{S\dots S}\_{2n + 1} \Rightarrow^\* u\_1v\_1u\_2v\_2\dots u\_nv\_nu\_{n+1} = w. $$

So $w \in \mathcal{L}(G)$, completing the proof.

# Answer
Here is a somewhat simpler proof for $L \subseteq \mathcal{L}(G)$.

Apply induction directly to the claim that any string in $L$ can be generated by $G$.

As before, the base case is done by $S \rightarrow \varepsilon$.

For a nonempty string, counting $a$ as +1 and $b$ as -1, consider the partial sums:

If any intermediate (i.e., not first or last) partial sum is 0, break the string at that point, and apply $S \rightarrow SS$, and apply the induction hypothesis to both parts.

If no intermediate partial sum is 0 and the last partial sum (which is the full sum) is 0, then the first and last symbols must be different. Apply $S \rightarrow aSb$ or $S \rightarrow bSa$ as appropriate, and apply the induction hypothesis to the middle (the string with the first and last symbols removed).

If no intermediate partial sum is 0 and the last partial sum (which is the full sum) is positive (it cannot be negative), then the first symbol must be $a$. Apply $S \rightarrow SS$ and then apply $S \rightarrow a$ to the first of the two $S$; apply the induction hypothesis to the string with the starting $a$ removed.
> 3 votes

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


# Question
Title: Converting non-deterministic TM to deterministic TM using poly time SAT solver
Suppose there exist deterministic turing machine $M$ that could solve SAT in polynomial time. How can we construct a deterministic TM $N$ **,by using SAT solver $M$**, that take as input a non-deterministic TM for language $L$ and output a deterministic TM for $L$.

I know we can convert NTM to TM but im looking for a way with help of a SAT solver turing machine.

# Answer
> 2 votes
You can already convert a non-deterministic TM into a deterministic TM, even without a polynomial-time SAT solver. The deterministic TM will be much slower.

Having a polynomial-time SAT solver doesn't help with this process, except in very special cases, like for non-deterministic TMs that always output yes in polynomial time (which you would be able to convert to equivalent deterministic TMs that always output yes/no in polynomial time).

# Answer
> 0 votes
So i just add my Solution maybe somebody find it useful. We construct $N$ as fallows

```
N : on input T which is a turing machine
    construct T' such that on input w :
        it converts T,w to logical formula f as in Cook–Levin theorem
        Run M on f and  output whatever M decides

```

---
Tags: turing-machines, satisfiability, nondeterminism
---


# Question
Title: If primary server's UTC source fails, how will synchronization be possible in NTP(network time protocol)?
> If a primary server's UTC source fails, then it can become a stratum 2 secondary server. If a secondary server's normal source of synchronization fails or becomes unreachable, then it may synchronize with another server.

I have made a picture based on what I understood. I don't understand how will synchronization be possible when primary server source fails? Shed some light please here.

# Answer
> 1 votes
> I don't understand how will synchronization be possible when primary server source fails?

It will happen exactly as before, except the time will not be accurate.

---
Tags: distributed-systems, computer-networks
---


# Question
Title: What is the fastest classical "period-finding" algorithm that can replace the Quantum Fourier Transform in Shor's algorithm?
Shor's algorithm uses the Quantum Fourier Transform to find the period the function `a^x mod N` with "a" being a constant integer less than N and N being a semiprime. This function is periodic and has both a domain and image of all integers from 2 to N.

What is the fastest classical algorithm that could be used in place of the Quantum Fourier Transform in Shor's algorithm?

# Answer
It depends on what preconditions you know about the function, as pointed out by @nir shahir in the comments.

You might be interested in the Sparse Fourier Transform, which works when the periodic portion of the signal accounts for a significant portion of the total signal power.

The paper that broke this field open is:

> A. C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. J. Strauss, Near-Optimal Sparse Fourier Representations via Sampling, *Proc. of the 2002 ACM Symposium on Theory of Computing* (STOC-2002):152--161.

There's a more recent survey paper of later developments that looks like it might be a good starting point:

> Anna C. Gilbert, Piotr Indyk, Mark Iwen, Ludwig Schmidt, “Recent Developments in the Sparse Fourier Transform: A compressed Fourier transform for big data”, *IEEE Signal Process. Mag.*, 31(5): 91-100, 2014.

Edited To Add:

The question was originally about finding the period of arbitrary functions. OP later clarified that they mainly care about the function `a^x mod N`, which is not sufficiently sparse that you could use the Sparse Fourier Transform. (At least, you wouldn't get anything useful out of the Sparse Fourier Transform with only $O((\log N)^k)$ samples.) For `a^x mod N` the way `N` is defined in Shor's algorithm, you end up with a signal with $O(\sqrt N)$ harmonics, each of which contributes only approximately $O(1/\sqrt N$ of the total power.
> 3 votes

---
Tags: algorithms, complexity-theory, quantum-computing
---


# Question
Title: Polynomial and fully polynomial time approximation scheme
How to notice the type of algorithm whether it is polynomial or fully polynomial time approximation from the resulting running time ( execution time) of the program?

Is there any other way to decide?

# Answer
> 1 votes
You can't. "Polynomial time" is a statement about asymptotics. Observing the running time on various finite values of the input size can't tell you the asymptotic running time.

See How to fool the plot inspection heuristic?.

---
Tags: algorithm-analysis, runtime-analysis, approximation, polynomial-time
---


# Question
Title: What is the intepretation of the top & bottom elements of a lattice?
(moved from stackoverflow to here)

I'm trying to understand dataflow stuff for program analysis. Transfer functions move lattice elements up (towards top ⊤) and down (towards bottom ⊥). Sometimes the direction confuses me a bit (I'd do it in the other direction), so

* do the top and bottom elements of a lattice have any intrinsic mathematical meaning other than "I'm greater/smaller than everything else", respectively? (I suspect not)
* do the top and bottom elements have any meaning *by common human convention*? By this I mean moving up towards top means 'more information has been found' or 'we know more about this thing', and moving down towards bottom means 'less is known' or 'useful information has been lost'

# Answer
No, there is no intrinsic meaning. Their meaning depends on the specific data analysis and how it uses the particular lattice or what interpretation we put on them.

Often, bottom is used for uninitialized values (it is the most restrictive element) and top to represent values where nothing is known (it is the least restrictive element, i.e., if conveys the least information about the corresponding value), but this is not mandatory.
> 2 votes

---
Tags: data-flow-analysis, lattices
---


title: Random splitting with fixed size range

text:
# Question
Title: Random splitting with fixed size range
I ran into this problem while trying to create a procedural texture algorithm. I ended up using a greedy approximation and shuffling it to hide the bias, but I was wondering if there was a way to find a uniform solution.

# The Problem

Divide a wall of a height $H$ into a layers whose individual sizes range from $L\_{min}$ to $L\_{max}$. The algorithm should choose a random solution from the set of all possible layer counts and sizes that satisfy the constraints.

To put it another way, I'm looking for a way to randomly select a set $S$ from the sets that satisfy the constraints for the given $H$, $L\_{min}$, and $L\_{max}$: $$\sum\_iS\_i = H$$ $$\forall i | L\_{min} \le S\_i \le L\_{max}$$

It seems similar to a combinatorial optimization problem, but over an infinite set rather than a finite one. Looking at the Wikipedia article, it could be expressed as a knapsack problem whose items are all real numbers in the size interval and whose values are random with the additional constraint that the weight must exactly equal the limit.

# Examples

Setting the input parameters $H=10, L\_{min}=2, L\_{max}=3$ yields an infinite number of possible solutions:

* $\\{2, 2, 2, 2, 2\\}$
* $\\{2, 2, 3, 3\\}$
* $\\{2.1, 2.5, 2.6, 2.8\\}$
* ... and many more

The goal is to choose one of these solutions at random. In this case, the chosen solution would almost certainly have four elements (layers), as there is only one five element option and an uncountable number of four element options.

If we increase $H$ to $10.1$, we suddenly have an uncountable number of five-element solutions:

* $\\{2, 2, 2, 2, 2.1\\}$
* $\\{2.01, 2.03, 2.05, 2.07, 2.09\\}$
* etc… In this case, four-element solutions would still be more common, but the random algorithm should occasionally produce a five-element solution.

# My Analysis

I wrote a quick program to count up solutions using fixed steps in layer sizes in the hopes that there were exploitable patterns in the distribution. When grouped by layer count, the first layer's size followed a combination counting function with $n$ equal to the number of layers and $k$ linearly related to layer size, but I couldn't find a consistent pattern to how the scale or offset were determined.

*Edit: Added examples section. Minor changes to wording.*

# Answer
The number of solution sets of size $k$ is either uncountably infinite (and in particular has the same cardinality as $\mathbb{R}^{k-1}$), 1, or 0.

So, the following algorithm works:

1. If there is any $k$ so that there are uncountably infinitely many solution sets of size $k$:

1. Find the largest $k$ such that there are uncountably many solution sets of size $k$.
    2. Randomly pick a solution set of size $k$.
2. Otherwise, find any solution and output it. (Unless there is no solution; in that case, output that no solution exists.)

Steps 1.1 and 2 can be implemented efficiently. If $k L\_\min = H$ or $k L\_\max = H$, there is only one solution of size $k$. If $H \< k L\_\max$ or $H \> k L\_\min$, there are 0 solutions of size $k$. Otherwise, there are uncountably many solutions of size $k$, and in that case, you can reduce the sampling problem in Step 1.2 to the following (by rescaling appropriately):

> Given $u$ and $k$, sample $r\_1,\dots,r\_k$ uniformly at random such that $\sum r\_i = 1$ and $0 \le r\_i \le u$.

(Proof: Set $u = (L\_\max - L\_\min) / (H - k L\_\min)$ and $x\_i = L\_\min + r\_i (L\_\max - L\_\min)/u$.)

This problem is a generalization of sampling from the unit simplex. Unfortunately, I don't know an efficient solution to it.
> 3 votes

---
Tags: algorithms, randomized-algorithms, knapsack-problems
---


# Question
Title: How to convert a Complete Binary Tree to a Priority Search Tree in O(n)?
I would like to know if there is a linear-time algorithm ($\mathcal{O(n)}$ time) to convert a Complete Binary Tree with data left-to-right increasing stored in external nodes, to a Priority Search Tree.

By conversion, my aim is to create a "Priority Search Tree" with all of the elements of some "Complete Binary Tree", or to modify the original "Complete Binary Tree" such that it has all of the properties of a "Priority Search Tree".

# Answer
> 2 votes
No. If you could, you'd obtain a sorting algorithm that would run in $O(n)$ time (construct the priority search tree, then traverse the nodes in increasing order of key), but you can't sort in $O(n)$ time.

# Answer
> 0 votes
An algorithm with amortized time of O(n) is possible. The algorithm below runs bottom-up and the average case running time is O(n) \[visiting each node in the tree once\] with fixes on broken child nodes running only on external nodes. The Algorithm has a worst-case time complexity of nlog*n as the worst-case child node fix will run through at most one branch of the tree starting on its third rank, with subsequent fixes taking one branch of the previous tree starting on its third rank iteratively (hence log*n).

Here is an implementation in python.

```
def bubble(node):
    # base case: leaf node
    if node.left is None and node.right is None:
        data = node.data
        return data
    else:
        leftData, rightData = None, None
        if node.left is not None:
            if node.left.data is not None:
                leftData = node.left.data
            else:
                leftData = bubble(node.left)
        if node.right is not None:
            if node.right.data is not None:
                rightData = node.right.data
            else:
                rightData = bubble(node.right)
        if leftData is None:
            node.data = rightData
            node.right = None
        elif rightData is None:
            node.data = leftData
            node.left = None
        else:
            if leftData > rightData:
                node.data = leftData
                node.left.data = None
                data = bubble(node.left)
                if data is None:
                    node.left = None
            else:
                node.data = rightData
                node.right.data = None
                data = bubble(node.right)
                if data is None:
                    node.right = None
        return node.data

```

# Answer
> 0 votes
By a reduction form sorting problem to your problem, in polynomial time, we can find a lower bound for your problem.

Suppose you want to sort $n$ numbers, then set the priority of all numbers be an equal value, so we reduce Sorting problem to your problem, hence the problem at least hard as Sorting problem, therefore we can't solve your problem in $o(n\log n)$ because the lower bound of Sorting problem is $\Omega(n\log n)$.

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


# Question
Title: Differences between Polynomial and fully polynomial time approximation scheme
I have a confusion on understanding the relation between:

The input n ,The relative error and The running time of the program In both PTAS and FPTAS. In "The running time of PTAS must be polynomial in terms of n, however, it can be exponential in terms of ε.

In PTAS algorithms, the exponent of the polynomial can increase dramatically as ε reduces, for example if the runtime is O(n(1/ε)!) which is a problem. There is a stricter scheme, Fully Polynomial Time Approximation Scheme (FPTAS). In FPTAS, algorithm need to polynomial in both the problem size n and 1/ε."

My questions are: 1) How to decide if my polynomial algorithm is an approximation? Is testing all benchmarks from literature is a pre proof to continue in searching the proof?

2) How to decide the relation between the input n and the relative error, according to question 1?

# Answer
You can't verify an algorithm is a FPTAS using benchmarks. To be a FPTAS, the algorithm must provide a good approximation for all possible inputs. There are infinitely many input sizes. Observing whether it works on finitely many inputs can never tell you whether it works on all possible inputs.

Instead, you must come up with a mathematical proof that it is a FPTAS.
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis, approximation, polynomial-time
---


# Question
Title: Details wanted on the reduction from Circuit Value to CFG Membership
Consider a Boolean Circuit $C$ which takes $n$ inputs and has one output. Notation: Let $\textit{size}(C)$ be the size of circuit $C$: the total number of gates in $C$. Let $G = (V,\Sigma,R,S)$ be a context-free grammar where $V$ is the set of non-terminals. **Circuit-Value** is the circuit value problem, and **CFGM** is the context-free grammar membership problem. Let $c$ and $k$ be constants.

EDIT: For this question, let's say that a context-free grammar $G$ is *recursive* if there is some $N \in V$ and some sequence of derivations from $R$ such that $N \rightarrow^\* \cdots N \cdots$, that is, where $N$ appears on the right-hand side of a derivation from $N$. If there is no such $N$, let's call $G$ *non-recursive*.

Since CFGM is a P-Complete problem, there is a reduction from **Circuit-Value** to **CFGM**. So we can run $C$ through the reduction to get a context-free grammar G. In the questions below, we assume that $\textit{size}(C) = O(n^c)$, that is, the size of $C$ is polynomial in $n$.

Two questions arise since the reductions I've seen (EDIT: here and here) don't address these directly:

1. Is $|V| = O(n^k)$? That is, is $|V|$ polynomial in $n$?
2. Is $G$ non-recursive?

# Answer
In the Circuit Value Problem the task is to evaluate a Boolean circuit with given input values. The circuit can be modelled as a directed acyclic graph. The inputs have no incoming edges, the other nodes represent Boolean gates. Here we will assume the gates are AND, OR and NOT, and we also assume these gates are binary (unary for NOT).

We start with monotone circuits, where the connection to context-free grammars is rather direct. In a monotone circuit we have no NOT gates. (Every circuit is easily translated in a monotone circuit, using De Morgan's rules, pushing the negations down to the inputs.)

For each node in the circuit (inputs and gates) we set a unique variable for the CFG. If AND gate $A$ has inputs $B$ and $C$, then production $A\to BC$ simulates AND: $A$ only generates a string if both $B$ and $C$ do. Likewise productions $A\to B$, $A\to C$ simulate OR. Then for the inputs, only if input $I$ is evaluated TRUE we introduce production $I\to \varepsilon$. Finally we choose the output-gate variable $S$ as axiom for the grammar. Now for each variable $A\Rightarrow^\* \varepsilon$ iff gate/input $A$ evaluates to TRUE. In particular this holds for $S$.

This is Problem A.7.4 "Context-Free Grammar $\varepsilon$-Membership" from your linked document "A Compendium of Problems Complete for P". The authors have extended this to a book "Limits to Parallel Computation: P-Completeness Theory" (1995).

(1) As we can see, the number of variables in the grammar equals the number of "nodes" in the circuit, i.e., inputs and gates.

(2) Productions run "backwards" in the circuit (from output gate to inputs). As the circuit is acyclic, no variable derives itself, i.e., the grammar is non-recursive in your terminology.

We can extend this to circuits that include NOT. For this we take two copies of each variable: $A^0$ and $A^1$, with the intended meaning that $A^v\Rightarrow^\* \varepsilon$ iff input/gate $A$ evaluates to TRUE (when $v=1$) or evaluates to FALSE (when $v=0$). Starting with the inputs, we have production $I^1\to \varepsilon$ if $I$ evaluates TRUE (respectively, $I^0\to \varepsilon$ when $I$ evaluates FALSE).

The productions again model the gates. For AND gate $A$ with inputs $B,C$ we have four produtions $A^{u\land v}\to B^u C^v$ for $u,v\in \\{0,1\\}$. Similarly for OR gates $A^{u\lor v}\to B^u C^v$. And of course, for a NOT gate $A$ with input $B$ we get two productions $A^{\lnot v}\to B^v$ for $v\in \\{0,1\\}$. The circuit evaluates to TRUE iff the grammar generates $\varepsilon$ if we take $S^1$ as axiom.
> 1 votes

---
Tags: complexity-theory, context-free, circuits
---


# Question
Title: Halts for all rejects, but might accept/loop otherwise?
If a Turing machine halts for all rejects of L but might accept/loop otherwise, how is L's recognizability classified?

| Recognizability | Decidability | ${\langle L\rangle}$ | ${\langle \overline{L}\rangle}$ |
| --- | --- | --- | --- |
| Turing-Unrecognizable | Undecidable | loop or reject | loop or reject |
| Turing-Recognizable | Undecidable | accept | reject or loop |
| Turing-Recognizable | Decidable | accept | reject |
| Co-Turing-Recognizable | Undecidable | reject or loop | accept |
| **Turing-???** | Undecidable | accept or loop | reject |
| **Co-Turing-???** | Undecidable | reject | accept or loop |

# Answer
To answer the question

> If a Turing machine halts for all rejects of L but might accept/loop otherwise, how is L's recognizability classified?

$L$ is Turing-unrecognizable, but $\overline{L}$ is Turing-recognizable.

To see this, let $L=\overline{A\_{TM}}$ and $\overline{L}=A\_{TM}$, where $A\_{TM} = \\{(M,w)|\space M \space \text{is a TM that accepts} \space w\\}$.

We can create a TM $M\_L$ for $L$ that simulates the execution of the input $M$ on $w$. This TM will always halt and rejects when $M$ accepts but it is not guaranteed to always halt when $M$ does not accept. This is still a valid TM but **not** a recognizer. In Sipser it was proven that $L$ is unrecognizable but $\overline{L} $ is recognizable.

I think your table is a little misleading since it somehow hides the possibility of $L$ or its complement being TM-recognizable but not TM-decidable. Or maybe you overlooked the possibility that there are TM that are not recognizers. I am not sure what is the proper term to be used for them, though.
> 1 votes

---
Tags: turing-machines, terminology, undecidability
---


# Question
Title: How can a Turing machine compare two strings without modifying them?
In Sipser's *Introduction to the Theory of Computation*, the author explains that two strings can be compared by “zigzagging” back and forth between them and “crossing off” one symbol at a time (i.e., replacing them with a symbol such as $x$). This process is displayed in the following figure (from Sipser):

However, this process modifies the strings being compared, which would be problematic if the Turing machine needs to access these strings in the future. What are ways of performing a string comparison *without* modifying the strings?

# Answer
Create two new types of marks: $\dot{0}, \dot 1$. Those two will act "like" $x$, but can still keep the information about the string.

So when you cross-off a letter, add a "dot" to it at the top instead of fully replacing it with $x$.

Then, if you want the original strings back, after you are done comparing, go through the entire strings and remove the "dots": replace $\dot 0$ with $0$ and $\dot 1$ with $1$.
> 29 votes

# Answer
One simple way is to create a copy of the entire input right after the original input, if your TM only has a single tape. To distinguish the original from the copy you can use ## as separator. So the first step is to scan the entire input to reach the end, add ##, go back to copy the entire input to the right side of ## and finally apply the comparison used in Sipser to the copy.
> 24 votes

# Answer
Here is an alternative solution using the original binary alphabet of $\\{0,1\\}$ (without adding extra letters, apart from $x$ which can also be replaced with $\sqcup$), that also manages to work without allocating extra memory from its tape:

We only keep one "$x$" per string, moving it one right for each comparison we did. That being said, to know *what* letter was there before we replaced it with $x$, we can utilize the fact that its possible to encode it within the turing machine's internal state.
> 9 votes

# Answer
In general, it can't be done.

E.g., if the strings are length-prefixed, and writing to the cells containing the strings is not allowed, then there is no way that a machine of $n$ internal states can traverse a string longer than $n$ from end to end, and so there is no single program that can compare strings of arbitrary length (or do much of anything with them).

You have to be able to "bring information with you" on the tape, since there isn't enough memory in the internal state space to store anything of interest. Unless the input is encoded in a way that gives you some working space – leaving alternate cells blank, for example – you have no alternative but to rewrite the tape to create space for yourself.

You can always modify the strings in a reversible way, and restore them to their original positions after you've worked out and recorded the answer. But Turing machines aren't normally expected to do that.
> 3 votes

# Answer
You *can* get along without a copy and without more symbols than used in the strike-out solution - at the cost of increasing the number of states. That is, you only ever have one $x$ per string and (per additional states) keep in mind what was under them, thus allowing you to restore the info upon the next round.
> 2 votes

---
Tags: turing-machines
---


# Question
Title: What is the most efficient algorithm for calculating factorials?
Calculating the factorial n! by the algorithm that defines it is of O(n) complexity because it requires n-1 multiplications to find the solution. Is there an algorithm that is any faster than that?

# Answer
> 2 votes
If you want to get into technicalities, computing the factorial actually takes more than $O(n)$ time: One way to notice this is that $n!$ as a number has $\Theta(n \log n)$ digits. It will therefore take at least $\Theta(n \log n)$ time to even write the answer, so computing the answer will take at least that long.

That being said, can you compute $n!$ in $O(n \log n)$ time? Yes, but you have to be a little careful. The pseudocode

```
product = 1
for i from 1 to n:
    product = product * i

```

Is too slow, because at during the second half of the for loop, you end up multiplying $O(n)$-digit numbers $O(n)$ times, and you would end up with an algorithm that is at least quadratic.

A more efficient way is to divide and conquer: Starting with a list of numbers $1$ through $n$, pair the numbers up and multiply. Then do this again and again until you have a single number. In the $i^{\text{th}}$ iteration, you multiply $O(n/2^i)$ pairs of $O(2^i \log n)$-digit numbers. If we use a multiplication algorithm which takes $O(d \log d)$ time for $d$-digit numbers, then the $i$th iteration takes $O(n (\log n) \cdot \log(2^i \log n)) = O(n (\log n) i + n (\log n) (\log (\log n)))$ time. Summing for $i$ going from 1 to $\log n$, we get $O(n \log(n)^2 (\log (\log n)))$.

Even faster is to decompose the prime factors of the numbers below $n$. More details in this paper

---

By the way you are asking the question though, it seems like you are more interested in a model of computation where multiplication of integers takes a single step, and you want the answer to the question "How many multiplications do you have to do to compute the factorial?". In this case the answer is O(n), simply because if we treat the numbers we have to multiply as given and the multiplication algorithm as a black box, each multiplication has two inputs and one output, so it only reduces the list of numbers we have to multiply by 1.

---
Tags: algorithms, complexity-theory, factorial
---


# Question
Title: How to convert any recursive solution to a Dynamic programming table? Is there any tricks/tips to follow?
I've been able to form a recurrence relation with memoization in a recursive approach for most problems but the online coding rounds exceed the time limit or stack overflow occurs in all these problems. An iterative approach seems to be the only way out. But coming up with logic for filling the DP table is frustrating and difficult. Are there steps with which we can convert any recurrence relation into a DP table calculation?

# Answer
> 2 votes
* Analyse the problem and find out which values you have to compute and how they depend on each other.
* Make a table that can hold these values with somewhat intuitive indices, and fill it in an order that is easy to follow, but doesn't conflict with the dependencies.

I'm afraid it's hard to be any more specific here, as the values, their enumeration and the dependencies between them, all vary widely between problems.

---
Tags: algorithms, dynamic-programming, recursion, memoization
---


# Question
Title: Coming up with an adversary strategy for a clique of maximum size
I’m having trouble coming up with a good adversary strategy for this problem:

Input: a graph G

Output: the maximum size of any clique in G

Where the algorithm asks each time, “are vertices x and y adjacent?” and it could ask about any random pair of vertices in the graph.

So, I need an adversary strategy to force the algorithm to work for as long as possible. Here’s what I have so far:

* for any graph with n vertices, there exists n(n-1)/2 unique vertex pairs the algorithm can ask about
* Adversary could use a grid to keep track of questions asked? Through an adjacency matrix?

I’m kind of stumped on a possible strategy, any help? Would it be better for the adversary to answer “no” to the algorithm, or “yes”?

# Answer
> 2 votes
Following is a simple adversary strategy that makes the algorithm make $\frac{n(n-1)}{2}$ queries:

> For every pair $(x,y)$, adversary answers "no", i.e., $x$ and $y$ are not adjacent.

**Proof:** Since the adversary is maintaining an empty graph, the answer is trivially a clique of size $0$. However, if the algorithm says "$0$" before making all $\frac{n(n-1)}{2}$ queries, then for any non-queried vertex pair $(x,y)$ the adversary can make $x$ and $y$ adjacent; hence forming a clique of size $2$, and thus proving the algorithm wrong.

---
Tags: graphs, lower-bounds, clique, adversary
---


# Question
Title: Search algorithm for an expensive boolean function
I have the following problem. We have a boolean function $f$ that is expensive to compute for a given input. We need to find the smallest positive integer $n$ such that $f(n)$ is true. We don't know anything about $f$, i.e., there could be multiple inputs that produce true. We only know that $n \< M$, where $M$ is some maximum limit.

Obviously we could search for $n$ one step at a time starting from $1$, but this is expensive. Is there a better algorithm?

I tried implementing a nested binary search, but it was very slow for some inputs. The idea is to run binary search between $1$ and $M$. Say we get some answer $n'$ then we know that $n \< n'$. So now I run a binary search between $1$ and $n'-1$. I repeat this process until I find the smallest answer from all the binary searches. What am I doing wrong?

# Answer
The direct search is in fact the best possible algorithm.

To know for sure that $n$ is the answer, it is necessary to know all the values $f(1), \dotsc, f(n)$. Using the direct search, upon reaching $n$, those values will have been obtained, and no other values of $f$ will have been obtained.
> 4 votes

---
Tags: optimization, search-algorithms, binary-search
---


# Question
Title: Regular expression and Right Regular grammar for decimals starting with 1 ending with 9?
I was trying to do the following:

> Consider the set of all strings over the alphabet {0,1,2,9} that are decimal numbers beginning with 1 and ending with 9 and having exactly one decimal point (.). For example 12.9, would be a valid decimal number while 0.129 would be not since it does not begin with 1.

but it didn't seem to work:

```
1(0|1|2|9)*.(0|1|2|9)*9

```

or

```
S::=1X
X::=E|0X|1X|2X|9X|Y
Y::=.Z
Z::=E|0Z|1Z|2Z|9Z|A
A::=9

```

Why? Whats the correct answer?

# Answer
> 1 votes
Your regular expression is correct, however, your grammar isn't. Assuming $E = \varepsilon$, you can derive words like $S \to \mathtt{1}\\,X \to \mathtt{1}\\,\varepsilon = \mathtt{1}$.

A right regular grammar might look like this: \begin{align} S &::= \mathtt{1}\\,A\\ A &::= \mathtt{0}\\,A \mid \mathtt{1}\\,A \mid \mathtt{2}\\,A \mid \mathtt{9}\\,A \mid B\\ B &::= \mathtt{.}\\,C\\ C &::= \mathtt{0}\\,C \mid \mathtt{1}\\,C \mid \mathtt{2}\\,C \mid \mathtt{9}\\,C \mid D\\ D &::= \mathtt{9} \end{align}

# Answer
> 0 votes
A regular expression for your language is: $$ 1(0\cup\ 1\cup 2\cup 9)^\*.(0\cup\ 1\cup 2\cup 9)^\*9.$$

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


# Question
Title: Is the emptiness problem for PEGs decidable?
The emptiness problem for Context Free Grammars is decidable. Does the same hold for Parsing Expression Grammars (PEGs)? That is, is it decidable given a PEG $G$ to find whether $L(G) = \emptyset$ or not.

My intuition says no, as PEGs are closed under intersection, allowing one to construct hard instances of intersection, but I haven't given the proof a lot more thought. The classic reduction to the PCP doesn't work I believe - at least simply replacing choice with ordered choice - as this changes what languages are accepted.

# Answer
> 6 votes
I should have done my research better before asking. The original paper introducing PEGs (*Parsing Expression Grammars: A Recognition-Based Syntactic Foundation* by Bryan Ford) actually contains a proof that emptiness is undecidable, indeed using the post correspondence problem.

---
Tags: formal-grammars
---


# Question
Title: Is $n\log_{2}\log_{2}n = O(n\log_{3}\log_{3}n)$?
I've proven that $n\log\_{2}\log\_{2}n = \Omega (n\log\_{3}\log\_{3}n)$ but is $n\log\_{2}\log\_{2}n = O(n\log\_{3}\log\_{3}n)$ also true? Looks like it's not and actually $n\log\_{2}\log\_{2}n = \omega(n\log\_{3}\log\_{3}n)$. A problem of CLRS led me ask this.

# Answer
Yes, also we can get a tighter result that show us $ n\log\_2\log\_2n=\Theta(n\log\_3\log\_3n)$ .Suppose $c',c''\>0$ is a constant, hence

$$\lim\_{n\to\infty}\frac{n\log\log n}{n\log\_{3}\log\_{3}n} = \frac{n\log\log n}{cn\frac{\log\left(\frac{\log n}{\log 3}\right)}{\log 3}}=c'$$ Also $$\lim\_{n\to\infty}\frac{n\log\_{3}\log\_{3}n}{n\log\log n} = \frac{cn\frac{\log\left(\frac{\log n}{\log 3}\right)}{\log 3}}{n\log\log n}=c''.$$

**Note that constant factor have no effect on the growth rate of asymptotic functions, therefore**

$$n\log\_2\log\_2n=\Theta(n\log\_3\log\_3n).$$
> 2 votes

---
Tags: asymptotics
---


# Question
Title: How does the Linux kernel build its symbol lookup table?
I am writing a small x86-64 OS. I am trying to make sense of how Linux loads modules at runtime by linking them into the kernel.

I understand that Linux builds a symbol lookup table. Basically, a module is compiled with a special utility which keeps all the symbols intact. Then, the Linux kernel will read the symbols and compare these to the symbol lookup table. Once it has got the address for the symbol, it links the symbol in the module to the actual address of the function in the virtual address space.

This seems quite easy to implement but I wonder how, in C++, you can implement such a symbol lookup table. I know that you can easily get the address of a function with `&function`. How do you get the symbol of the function in the form of ASCII letters?

Basically, how does Linux build its symbol lookup table? Is it during compilation or at boot? Also, I know that C++ is not the best tool for this because it mangles function names a lot.

# Answer
I did find this wiki article: https://en.wikipedia.org/wiki/System.map. It states that the `nm` utility is used to get the System.map file that is then used by the kernel as the symbol lookup table.

I also found this System.map file on my boot partition on my Linux hard-disk. A sample:

```
user@user-System-Product-Name:/boot$ sudo gedit System.map-5.11.0-25-generic
ffffffff810d4ac0 t perf_trace_sched_numa_pair_template
ffffffff810d4c60 t __bpf_trace_sched_kthread_stop
ffffffff810d4c70 t __bpf_trace_sched_kthread_stop_ret
ffffffff810d4c80 t __bpf_trace_sched_kthread_work_execute_start
ffffffff810d4c90 t __bpf_trace_sched_process_wait
ffffffff810d4ca0 t __bpf_trace_sched_kthread_work_queue_work
ffffffff810d4cb0 t __bpf_trace_sched_kthread_work_execute_end
ffffffff810d4cc0 t __bpf_trace_sched_migrate_task
ffffffff810d4cd0 t __bpf_trace_sched_process_fork
ffffffff810d4ce0 t __bpf_trace_sched_stat_template
ffffffff810d4cf0 t __bpf_trace_sched_switch
ffffffff810d4d00 t __bpf_trace_sched_process_exec
ffffffff810d4d10 t __bpf_trace_sched_stat_runtime
ffffffff810d4d20 t __bpf_trace_sched_move_numa
ffffffff810d4d30 t __bpf_trace_sched_numa_pair_template
ffffffff810d4d40 T preempt_notifier_register
ffffffff810d4d90 t check_same_owner
ffffffff810d4de0 t is_cpu_allowed
ffffffff810d4e60 t cpumask_weight
ffffffff810d4e80 t set_load_weight
ffffffff810d4ef0 t __sched_fork
ffffffff810d5040 T preempt_notifier_inc
ffffffff810d5060 T preempt_notifier_dec
ffffffff810d5080 t __schedule_bug
ffffffff810d50a0 t sched_copy_attr
ffffffff810d5260 T __ia32_sys_sched_getscheduler
ffffffff810d52e0 T __ia32_sys_sched_getparam
ffffffff810d53d0 t nohz_csd_func
ffffffff810d5470 t sched_free_group
ffffffff810d54b0 t sched_free_group_rcu
ffffffff810d54d0 t cpu_cgroup_css_free
ffffffff810d54e0 t cpu_uclamp_min_show
ffffffff810d5590 t cpu_cfs_stat_show
ffffffff810d5650 t cpu_max_show
ffffffff810d5700 t cpu_extra_stat_show

```

Linux seems to relocate the kernel to 0xffffffff80000000.
> 1 votes

---
Tags: operating-systems, os-kernel
---


title: Prove that $(L^R)^* = (L^*)^R$

text:
# Question
Title: Prove that $(L^R)^* = (L^*)^R$
> Prove that $(L^R)^\* = (L^\*)^R$ for all languages $L$.

My attempt: Suppose $w \in (L^R)^\*$. So, $w = w\_1\dots w\_l$, for some $w\_1, \dots , w\_l \in L^R$. Since $w^R \in L$, then $w^R = w\_l\dots w\_1$, for some $w\_l, \dots , w\_1 \in L^\*$. Therefore, $(L^R)^\* \subseteq (L^\*)^R$.

Honestly, I don't know how to proceed onwards, because this part doesn't sound right. I feel like I messed up with those symbols as this topic is really abstract. Any help? Thanks in advance.

# Answer
> 1 votes
If $w \in (L^R)^\*$, then $w = w\_1 \ldots w\_\ell$ for some $w\_1,\ldots,w\_\ell \in L^R$. Hence $w\_1^R,\ldots,w\_\ell^R \in L$, and so $w\_\ell^R \ldots w\_1^R \in L^\*$. This shows that $w = (w\_\ell^R \ldots w\_1^R)^R \in (L^\*)^R$.

Similarly, if $w \in (L^\*)^R$ then $w = x^R$ for $x \in L^\*$. Since $x \in L^\*$, $x = x\_1 \ldots x\_\ell$ for some $x\_1,\ldots,x\_\ell \in L$. Then $x\_1^R,\ldots,x\_\ell^R \in L^R$, and so $w = (x\_1 \ldots x\_\ell)^R = x\_\ell^R \ldots x\_1^R \in (L^R)^\*$.

# Answer
> 0 votes
**Edited:**

First of all, we prove that $$\forall n\geq 0\hspace{6pt}(L\_1\cup L\_2)^R=(L\_1^R\cup L\_2^R).$$

First we should show that all strings in $S= (L\_1\cup L\_2)^R$ are in $S'=(L\_1^R\cup L\_2^R)$, and all strings in $S'=(L\_1^R\cup L\_2^R)$ are in $S= (L\_1\cup L\_2)^R$. Assume $s\in S $ then $s^R\in (L\_1\cup L\_2)$, hence $s\in (L\_1^R\cup L\_2^R)$, assume $s\in S' $ then $s^R\in (L\_1\cup L\_2)$, hence $s\in (L\_1\cup L\_2)^R$. Therefore $$\forall n\geq 0\hspace{6pt}(L\_1\cup L\_2)^R=(L\_1^R\cup L\_2^R).$$

We can show that $$(L^R)^n = (L^n)^R$$ By definition of Kleene star $$(L^R)^0\cup (L^R)^1\cup(L^R)^2\cup\dots=(L^0\cup L^1\cup L^2\cup\dots)^R$$

By applying former part $$(L^R)^0\cup (L^R)^1\cup(L^R)^2\cup\dots=(L^0\cup L^1\cup L^2\cup\dots)^R$$ $$=(L^0)^R\cup (L^1)^R\cup (L^2)^R\cup\dots$$

We should show that $\forall k\geq 0 \hspace{6pt}(L^R)^k=(L^k)^R$.

By Induction:

The basis $k=0$ is

$$(L^R)^k=(L^k)^R=\lambda.$$ For induction hypothesis, suppose $$\forall k\leq n\hspace{6pt}(L^R)^k=(L^k)^R.$$ Consequently, for induction step, when $k=n+1$ $$(L^R)^{n+1}=(L^{n+1})^{R}$$ $$\implies (L^R)^{n}\cdot L^R=(L^n\cdot L)^R$$ $$\implies (L^R)^{n}\cdot L^R=(L^n)^R\cdot L^R$$

Hence the last result, follow the induction hypothesis. So statement $$(L^R)^n = (L^n)^R$$ holds for any $n$.

---
Tags: formal-languages
---


# Question
Title: Question about the proof of the undecidability of the Halting Problem
From what I can see, the proof of the undecidability of the Halting Problem relies on a fairly basic self-referential paradox, the simplified version being (from Wikipedia):

```
def g():
    if halts(g):
         loop_forever()

```

Obviously, in this case there can not be any output for halts(g) as the output of g itself depends on halts(g). However, I don't really see the point of this proof because you can create this phenomena for literally any arbitrary function. For example, let us a consider a function `returns_true` that returns true if the given input returns true and false otherwise:

```
def g():
    return !returns_true(g)

```

We once again arrive at the same conclusion: `returns_true(g)` doesn't return true or false. Does that mean that there is no function `returns_true` that works on all inputs? Technically yes, but obviously that isn't really the point of the question, it works on all non-obviously-malformed inputs. Since the same can be said for the halting problem, what exactly is the point?

# Answer
You said:

> you can create this phenomena for literally any arbitrary function

but the example you provided of `returns_true` is very far from a typical function, and is rather a higher-order function very similar to the one used in the halting problem, which seems to require running/analysing its input function in its entirety. And given that the attempt to do so might itself run into the halting problem, it seems natural to me that the same proof method applies against `returns_true`.

In particular, I believe the problem in this case lies in the fact that by the way you defined `g`, it immediately leads to an infinite mutual recursion between `g` and `returns_true`, so it doesn't halt, and will not return any value.

So it appears to me that your statement:

> it works on all non-obviously-malformed inputs

translates into something like "it works on all inputs that are guaranteed to halt", but sadly, given the halting problem, we don't actually know which inputs these are (at least on a theoretical Turing Machine with unlimited memory).
> 2 votes

# Answer
Notice, that the code you wrote isn't well defined. That is, the code:

```
def g():
    if halts(g):
        loop_forever()

```

Is actually not well defined. The problem here is with the second line, where you referenced $g$ inside itself. Think about it, you need the entire definition of $g$, in order to write the definition of $g$? Not really a great idea.

To fix this, take a look at how *actually* this self-reference is created:

```
def g(func_code):
    if halts(func_code(func_code)):
        loop_forever()

```

And now the definition of $g$ doesn't depend on itself, while we can still create the self-referential problem by asking what will happen when we pass $g$ as an argument to itself: $g(g)$. Notice that there is `func_code(func_code)` since `func_code` must need exactly one input argument if we want that $g(g)$ will be well defined.

In the same sense as the way we "fix" this proof for the halting problem, we will try to "fix" the "proof" for general functions:

```
def g(func_text):
    return not returns_true(func_text(func_text))

```

And now notice that the very *definition* of $g$, requires an input which is a function that gets one argument.

If we say our functions were all from a set $A$ into a set $B$, then also $g$ has to be so, and thus $A$ must somehow be able to "encapsulate" all functions from $A$ to $B$ \- which is clearly impossible (there are more functions than there are elements in $A$).

Hence, this claim - while making "intuitional" sense, breaks down when taking a look at it more carefully.
> 0 votes

---
Tags: algorithms, halting-problem
---