# Question
Title: How to estimate T(2N) from T(N) of mergesort?
This question is from Exercise 1.7 in the book *An Introduction to the Analysis of Algorithms* by Robert Sedgewick and Kevin Wayne.

> Assume that the running time of mergesort is $cN\lg{N}+ dN$, where $c$ and $d$ are machine-dependent constants. Show that if we implement the program on a particular machine and observe a running time $t\_N$ for some value of $N$, then we can accurately estimate the running time for $2N$ by $2t\_N(1 + 1/\lg{N})$ independent of the machine.

The following is my thought sketch:

Given the fact that $t\_N = cN\lg{N} + dN$, then we have \begin{equation\*} \begin{split} T\_{2N} & = 2cN\lg{2N} + 2dN \\ & = 2cN(\lg{N} + 1) + 2dN \\ & = 2(cN\lg{N} + dN + cN) \\ & = 2(t\_N + \frac{t\_N - dN}{\lg{N}}) \\ & \approx 2(t\_N + \frac{t\_N}{\lg{N}}) \\ & = 2t\_N(1 + 1/\lg{N}). \end{split} \end{equation\*}

Is it safe to discard $-dN/\lg{N}$, and why?

# Answer
> 0 votes
$$\frac{t\_{2N}}{2t\_N}=\frac{2cN\lg(2N)+2dN}{2cN\lg(N)+2dN}=\frac{c\lg(N)+c+d}{c\lg(N)+d}=1+\frac1{\lg(N)+\dfrac dc}$$ and the claim seems wrong.

---

Assuming that $c=d$, for the error to be less than $1\\%$, $N$ should be at least $2^{99}$ !

# Answer
> 0 votes
2 T(N) is exactly the time that you need to create two sorted subarrays of size N each from 2N items. Then you need to make one more pass to turn the two subarrays into one array. Since we need log(N) passes, one more pass is a factor (1 + 1 / log (N)).

In practice, this last pass is the pass that is most likely to exceed some cache limit, and therefore may run slower than other passes. Say you have 2MB of data and 1MB of fast cache. One half of the data is read from memory and sorted in the cache using maybe 15 passes, then that half is written back to memory, the other half is read and sorted in the cache. and then the last pass has to read and write two MB of memory, as much as the other 15 passes together.

---
Tags: time-complexity
---


# Question
Title: How to prove that $L = \{{a^{n} b^{n} c^{j} | n,j \geq 0}\}$ is a CFL?
In the text of my book it says that this language is context-free so I tried to prove that the conditions of the Pumping Lemma are fulfilled.

If, for example, I take the word $aaabbbc$

I can divide it like this:

$u = ε, v = a, x = a, y = ab, z = bbc$

So the conditions: $|vy| \> 0$ $|vxy| \<= p$ (if I consider p = 3) are satisfied.

I have to prove that $uv^{i}xy^{i}z$ still belongs to the language.

But for $uv^{2}xy^{2}z$ I will have a string of the type:

$aa a abab bbc$ That should not belong to the language...

I'm probably missing something.

# Answer
> 2 votes
Proving that the pumping lemma (for context free languages) holds for some language $L$ provides no information on whether $L$ is context-free (since the pumping lemma is just a necessary condition).

One way to prove that a language $L$ is context free is that of showing a context-free grammar that generates $L$. Here is a possible grammar for your particular language: $$ S \to \varepsilon \mid X \mid C \mid XC \\ X \to ab \mid aXb \\ C \to c \mid cC $$

---
Tags: context-free, pumping-lemma
---


# Question
Title: Algorithm that generates verification program from solution program of NP problem
I don't know complexity class theory well so I might make some categorical errors, but I will try to ask this question anyways.

Suppose you have written a function in some programming language which solves an NP-complete problem. There must exist an algorithm which can verify the correctness of an (input, output) pair in polynomial time. Does there exists an algorithm which takes the code of your solution function and produces code for a verification function? In other words, can a efficient polynomial time verification program be constructed from any solution program?

Alternatively, if this is impossible, suppose the solution function is written in a strongly typed language like Lean or Agda which can formalize mathematics. Now suppose you are given not only a function which solves an NP-complete problem, but also a formalization of the problem as well as a proof of correctness of the function. Can you construct a polynomial time verification function from that?

My motivation is that it would be interesting if one could "super-compile" a program in such a way that it is enriched with verification functions. Then one may attempt to skip certain parts of the program during execution by guessing the output of a function and using the generated verification to check.

# Answer
> 2 votes
Yes: The certificate (checked by the verifier) simply encodes the non-deterministic choices made by the non-deterministic program. You then run the original non-deterministic program, resolving the non-determinism using the certificate.

Remember that each "NP verifier" receives two inputs: The original problem instance, and a certificate. The verifier must always output "no" when given a no-instance; when given a yes-instance, it must output "yes" for at least one certificate.

If you are still confused why this certificate is needed, see e.g. this anwer: Certificates and NP?

---

However, the way your question is written makes me fear that you mean something very non-standard when you say "verifier." What do you mean by "verifier"? And how should dependent types help here? (Executing the correctness proof is usually not more meaningful than executing the original solver..)

# Answer
> 2 votes
Generally speaking, we don't need compiler support to implement the verifier. Implementing a verifier for a NP-problem is usually easy; far easier than implementing an efficient solver. So I doubt that your idea is going to prove very useful.

That said, if you want to do it, if you have a formal specification of a NP problem, it should be possible to auto-generate a verifier. If you look at the formal definition of NP, you will see that the way we specify a NP problem is by specifying the verification method. If you look at informal definitions of NP problems, typically they specify a list of conditions for a solution $y$ to count as a valid solution to a problem instance $x$. Those conditions are the verifier; all that you need to do to build a verifier is to write code to check all of those conditions. Given a formal specification of those conditions, I expect it will typically be trivial to synthesize code that checks those conditions (you basically just have to execute the specification).

I don't know of any good way to automatically generate a verifier given code for a deterministic solver, like a SAT solver or ILP solver.

It's not clear why you want a verifier. If your goal is to use the verifier to check the output of the solver, because you are worried that the solver might have bugs, then you don't want to auto-generate the verifier from the solver code anyway, because then bugs in the solver would imply bugs in the verifier. If you want to check for bugs in the solver, then you should independently implement the verifier, not auto-generate it from the solver.

Most NP-complete problems are hard to solve, so typically there isn't any good solver. Many of the problems we solve in practice are not NP-complete, but rather are in P. In that case, you might be interested in the CS literature on "program checking". That literature devises algorithms to check whether the results of a program are correct, for certain specific problems (which typically are not NP-complete). See, e.g., https://en.wikipedia.org/wiki/Freivalds%27\_algorithm for one example.

---
Tags: complexity-theory, turing-machines, optimization, np-complete, type-theory
---


# Question
Title: Applications of ω-automaton in engineering
Finite automaton is a well-known topic which finds applications in software engineering (e.g. pattern matching or regular expressions in general).

ω-automaton are another kind of automaton, defined similarly to finite automaton except that they are designed to be run on infinite words (which can be thought of as *streams*) and have an *acceptance condition* instead of *accepting states*.

**I am looking for usage of ω-automaton in engineering. In particular, do you know some software that rely on some kind of ω-automata?**

# Answer
> 4 votes
Sure. They are used in model checking. Specifically, if we want to check liveness properties of systems, then typically we use $\omega$-automata (e.g., Büchi automata) to formalize the property we are trying to verify, and to model the composition of property + system under verification. For example, a standard way to do model checking of LTL formulas is to convert LTL to a Büchi automaton, then work with these automata. A classic paper is An Automata-Theoretic Approach to Automatic Program Verification by Vardi and Wolper.

I believe one good example of a software tool is SPIN, a very widely used model checker that takes this approach.

If you want to look for more examples, you could check Google Scholar to look for tool papers that cite the Vardi-Wolper paper. Also, I *think* TLA+ might use $\omega$-automata for checking liveness but I'm not sure.

---
Tags: automata, finite-automata, software-engineering, applications
---


# Question
Title: Is explicitly explaining the case where the Turing Machine loops forever essential to proving reducibility?
I am asking this in the context of the following question:

> Let *N* be a non-deterministic Turing Machine. We say that N faces a dilemma if at some point in its working, it encounters a situation where the finite control is in the state *p*, the head scans the tape *a*, and $\delta (p, a)$ offers multiple (two or more) possibilities, where *p* is neither the accept state nor the reject state. Consider the following language $$ \text{DILLEMA}\_{ALL} = \\{\langle N\rangle| N \text{ is a NTM which faces a dilemma at least once on each input}\\} $$ Prove that $\text{DILLEMA}\_{ALL}$ is not recursively enumerable

Here is how I have attempted this problem

To prove that $\text{DILLEMA}\_{ALL}$ is not recursively enumerable, we prove that $\bar{A}\_{TM} \le\_m \text{DILLEMA}\_{ALL}$.

Here is how we construct the proof for reducibility.

For any input $\langle M, w\rangle$ we have to return an output $N$ for our reducibility function.

1. Construct a deterministic Turing machine N which gets an input $x$ and run $M$ on $w$.
2. If $M$ accepts, accept $x$ ie. $L(N) = \Sigma^\*$
3. If $M$ rejects, take any state $q$ in the Turing machine $N$ which is not accept or reject state and copy the succeeding computational graph from this state. Rename the copied states to say $q\_1$ and $q\_2$ and make a non-deterministic transition from $q$ to $q\_1$ and $q\_2$.
4. Output $\langle N \rangle$.

Proof of correctness:

1. When $w \not \in L(M) \Leftrightarrow \langle N \rangle \in \text{DILLEMA}\_{ALL}$
2. When $w \in L(M) \Leftrightarrow \langle N \rangle \not \in \text{DILLEMA}\_{ALL}$

Thus it has been proven that $\bar{A}\_{TM} \le\_m \text{DILLEMA}\_{ALL}$ and hence $\text{DILLEMA}\_{ALL}$ is not recursively enumerable.

What I have essentially done is to introduce non-determinism in a deterministic turing machine by adding a compatible transition which doesn't affect the behaviour of the machine other than making it non-deterministic.

My professor however disagrees with my proof, and claims that I did not include the case where the turing machine neither rejects nor accepts ie. loops forever in my proof of correctness for reducibility. I believe that the case is implicit since if $M$ loops forever then $N$ is obviously not giving any output ie. it is also looping forever.

Could anyone please validate my proof or explain my professor's criticisms in more detail since I was not able to understand his reasoning? I couldn't find any mention of explicitly writing the looping case even for non recursively enumerable languages in textbooks or anywhere else.

# Answer
> 2 votes
Not only your professor is correct, but also the reduction is not well-written. Specifically, you did one of the following (and both are wrong):

* The reduction simulates the run of $M$ on $w$, and then decides which $N$ to output: this cannot be done as the machine that computes the reduction may not halt.
* The reduction always halts and outputs a description of a machine $N$ that operates as follows. On input $x$ for $N$, $N$ neglects $x$ and simulates the run of $M$ on $w$. Then, depending on what happens during the simulation, you change the definition of $N$ on the fly. This is not well-defined, as the state-space of $N$ depends on how it behaves on its input $x$ -- you see now that you have a circular definition. You should define the nondeterministic state q in the machine $N$, regardless of what happens in the simulation of $M$ on $w$, meaning the nondeterministic state is always defined in $N$, and the question is whether it is not reached on some inputs only when $M$ accepts $w$.

Here is how to do it properly, and how to fix the problem of non-halting:

**The reduction:** on input $\langle M, w\rangle$, the reduction outputs $\langle N\rangle$, where $N$ is a nondeterministic machine that operates as follows. $N$ has a single nondeterministic state $q\_{N}$ from which it guesses to move to $q\_{rej}$ or move to $q\_{acc}$: $\delta(q\_{N}, \gamma) = \\{ \langle q\_{acc}, \gamma, R \rangle, \langle q\_{rej}, \gamma, R \rangle \\}$, forall $\gamma \in \Gamma$. Then, on input $x$, $N$ computes $|x|$ and simulates the run of $M$ on $w$ for $|x|$ steps, if during the simulation $M$ did not accept $w$, then $N$ moves to the state $q\_{N}$. Otherwise, if during the simulation $M$ accepted $w$, then $N$ moves to $q\_{reject}$.

Clearly, for all $x$, $N$ faces a dilemma when it runs on $x$ only if it reaches the state $q\_{N}$, which happens only when $M$ does not accept $w$ within $|x|$ steps.

**For the correctness:** if $\langle M, w\rangle \in \overline{A\_{TM}}$, then $M$ does not accept $w$, in particular, $M$ does not accept $w$ within $|x|$ steps for all $x$. Hence, for all $x$, the run of $N$ on $x$ reaches $q\_{N}$, and thus $\langle N\rangle\in DILEMMA\_{ALL}$. Conversely, if $\langle M, w\rangle\in A\_{TM}$, then $M$ accepts $w$ after $t$ steps. Then for all $x$ with $|x|\geq t$, $N$ moves to $q\_{rej}$ and never visits $q\_{N}$, and so $\langle N\rangle \notin DILEMMA\_{ALL}$.

**Notes:**

1- If we allow the simulation to not halt, then on input $x$, $N$ does not accept or reject, and we do not know whether it will accept in the future or not halt. Thus, it never reaches a dilemma, but we want it to reach a dilemma in this case -- for this reason we bound the number of steps when we simulate.

2- The main thing is whether we visit $q\_{N}$ or not. The fact that we sometimes accept or reject in some cases is not important.

---
Tags: turing-machines, undecidability, turing-recognizable
---


# Question
Title: Useful algorithm not primitive recursive
The Ackermann function is the textbook example of a function which is total recursive but not primitive recursive.

If we want to implement it in some programming language we will need to use a priori unbounded loops (generally using `while` or `goto`).

I am looking for an algorithm used in real situations (e.g. in computational geometry or whatever field) that would implement a recursive function which is not primitive recursive (it doesn't need to be total). Such an algorithm would inherently require using a `while` loop.

Does such an algorithm exist?

# Answer
> 1 votes
This question comes up from time to time, but I couldn't find an answer that I entirely loved so here's a take:

The main source of examples of non-primitive recursive functions that are still somehow total are *evaluators for total languages* which include primitive recursion!

This comes up whenever we want to give users the ability to express a wide range of programs, but want to prevent non-termination for whatever reason. The evaluator can easily be seen to be non-p-r for diagonalization reasons.

An example is in the Coq (soon to be Rocq) programing and proof language: with dependent types it may be necessary to evaluate a program at compile time, but the set of programs expressible includes much more than primitive recursive functions.

For example here is a program that evaluates factorial 5 at type-checking time:

```
Fixpoint fact (n : nat) :=
  match n with
  | 0 => 1
  | S k => n * (fact k)
  end.

/* This doesn't type-check with any other value than 120. */
Definition compute_fact_5 : fact 5 = 120 := eq_refl 120.

```

---
Tags: algorithms, computability, recursion, primitive-recursion
---


title: Is the square-root sum problem convex?

text:
# Question
Title: Is the square-root sum problem convex?
The square-root sum problem is: given positive integers $a\_1,\ldots,a\_k$ and $b\_1,\ldots,b\_k$, decide if $\sum\_i \sqrt{a\_i} \> \sum\_i \sqrt{b\_i}$. The exact run-time complexity of this problem is an open problem, as far as I know.

Can this problem be solved approximately using convex programming? I thought of the following formulation:

$$ \text{maximize } \sum\_i x\_i - \sum\_i y\_i $$

$$ \text{subject to } x\_i^2 -a\_i \leq 0 \text{ and } y\_i^2 - b\_i \geq 0. $$ If the optimal value is positive then the answer is "yes", otherwise the answer is "no".

But there is a problem: the constraint $y\_i^2-b\_i\geq 0$ is not convex.

Is there another way to solve the problem using convex programming?

# Answer
The problem is not where you think it is.

To decide this, you would normally just add up the square roots and compare the sums. The problem arises when both sums are close together, so you cannot easily prove which sum is larger. Now consider that all we know is that the numbers are integers. They could be 100 digit integers, and with some effort one could find two sets that produce sums equal to 100s of digits.

So the problem is that we cannot find upper limits for the precision needed to decide which sum is larger.
> 0 votes

---
Tags: optimization
---


# Question
Title: What is the name of this search algorithm?
I was thinking about an efficient binary search for unsorted arrays with $n$ entirely unique elements, and came up with something that probably already exists. Here's how it works:

At each level of recursion (starting with $k=1$), you have $2^{k-1}$ pairs of searchers, taking up some $O(1)$ memory each. In each pair, there's one that searches to the left, and one that searches to the right, like so:

`|` denotes a searcher, `<>` for direction

`|> <|`

These two searchers look for the element in question until they meet in the middle. You could probably implement the recursive step iteratively, so you're not using memory on idle searchers.

If the distance between the two is large, you can subdivide:

`|> <||> <|`

And so on until the element is found. This could be parallelized, since each searcher has a computable range of indices it searches over. You would have to synchronize in some way to prevent the "other" branches from continuing to search once you found the element, which is probably difficult to pull off in practice.

I believe this could find the element in $O(\log(n))$ time, using $O(\log{n} \cdot 2^{\log{n}}) \approx O(n \log{n})$ memory (which is a lot, but it's unsorted).

What's the name of this algorithm?

# Answer
> 3 votes
It's a parallel linear search, with an over-complicated way to divide up the array into a power-of-2 number of chunks. (Since you only split in half with multiple levels of recursion, instead of the usual `chunk_size = n/cores_available` which can keep all cores busy even if their number isn't a power of 2.)

**In terms of algorithmic complexity, it's the same as a typical parallel linear search with `cores_available` rounded down to a power of 2**. The differences are in the engineering choices for starting threads and looping over a chunk of an array in two directions.

It doesn't require any extra space, unless you count the overhead of the OS tracking extra threads. Or if you're counting how much memory in the existing array it *touches* that a simple linear search from the start wouldn't. (But with cancellation, if the match is uniformly placed, on average it will touch about the same amount since it'll typically be found about half-way through each thread's search chunk. So cancellation latency will let them touch a bit more.)

### Looping both ways vs. the standard increasing-address direction

**If bidirectional meet-in-the-middle looping was a faster on real CPUs, we'd hopefully already be doing it for all kinds of problems** like array sums and dot-products, and `a[i] = f(b[i])` problems like level 1 BLAS operations. (And compilers would be optimizing simple loops into loops that went both ways.) It's worth measuring to see if this has any advantages on any mainstream CPUs; perhaps this *is* something compilers should start doing!

(Compilers probably won't auto-vectorize as easily if you write the source code to loop both ways. Current compilers won't auto-vectorize search loops at all, only loops whose trip-count can be calculated ahead of the first iteration. So they only auto-vectorize loops where they can already tell that the loop touches every element in a range once; other loop optimizations could be conditional on that. You *can* write a search that always touches all elements, updating a found\_position you check at the end. That can be appropriate for tiny arrays, especially fixed-size, both to avoid branch misprediction and to work around the inability of current compilers to make asm that searches efficiently the way hand-written libc `memchr` does, e.g. with x86 `pcmpeqb` / `pmovmskb` to get a bitmask of 16 byte-compare results that you can branch on. SIMD linear search with no data-dependent branching can even be optimal for small *sorted* arrays, although that enables tricks like counting elements where `a[i] < key` which is faster than blending match positions.)

Searching both ways from the starting point makes sure you read the whole cache line while it's still hot. But doing so from different CPU cores (thread) only benefits from an outer level of shared cache (e.g. L3) if the two cores share any cache at all. (Which they might not on a multi-socket system, or on an AMD with cores in different CCX clusters). You'd like to benefit from per-core private caches (L1d and L2 in many modern CPUs.) So you'd more likely want to align your boundaries to cache-block boundaries. Or page boundaries (e.g. 4k) for TLB locality.

IIRC, Intel's L1d hardware prefetcher does work better for increasing address (looping "forward").

For memory bandwidth after starting, looping forwards and backwards is probably not harmful on modern x86 CPUs at least: Intel's L2 streamer HW prefetcher can track one forward and one backward stream per 4K page; see a quote from Intel's optimization manual.
It *might* even help memory-level parallelism to be crossing a 4K boundary in one part but not the other (where HW prefetch stops because contiguous virtual addresses might not be contiguous in physical address space). So one HW prefetch stream can still be working and keeping the memory pipeline fully utilized. (But we're parallelizing, and multiple cores can already saturate DRAM controllers, or with L3 hits, probably the interconnect between cores.) Out-of-order exec usually sees far enough ahead to get demand loads in flight from across the 4K boundary. The limiting factor in per-core memory bandwidth is usually latency and the number of outstanding requests one core can track, or DRAM bandwidth if you miss in last-level cache for huge arrays.

---

### Thread creation

Normally you don't need to parallelize the thread-starting part, you just loop in the main thread until you've started all the workers. If that's significant compared to the actual work being done, use fewer threads (set a minimum chunk size) and/or have a pool of worker threads to reduce overhead of assigning work to them for jobs other than the first.

Maybe on an architecture that's significantly different from modern mainstream CPUs, where vastly more cores are available and it's cheaper to create threads. (But you still have to do so one at a time, unlike a GPU where things naturally run in parallel.)

Starting threads as you recurse probably makes it harder in practice to keep track of them for when you want to `.join()` them to make sure they've finished, or send them notifications or signals.

If you were going to do any rounding of the number of tasks or whatever, you might round the chunk size to a multiple of the page size so each thread makes the most use of its dTLB coverage. Or maybe work in somewhat smaller chunks like OpenMP "dynamic" scheduling so differences in CPU speed or scheduling don't leave one thread with a lot of work to do while the others are done. (Normally that's most useful for problems where the amount of work per chunk is actually variable, not just because of competing with other load on the system. `n/k` chunk size is what OpenMP calls "static" scheduling, where all the work is handed out to worker threads right away.)

---

### Cancelling after one thread finds a match:

CPUs and OSes can do this easily and efficiently, it's just a question of whether the necessary tools are exposed in the high-level language you're using. It's often the case that the CPU being able to do something efficiently doesn't mean it's easy to write a portable program that does it efficiently, but I think we're ok in modern C++ for this.

One way is to have each thread check a shared atomic flag (like C++ `std::atomic<bool>` with `memory_order_relaxed`) every 1K or 4K bytes. It will normally stay hot in the L1d cache of all cores, invalidated (MESI) only when it's written by the thread that found the match. If the search speed is limited by cache or memory bandwidth, that won't slow us down. (Modern x86 can search faster than L2 cache bandwidth, if you use SIMD effectively like AVX2 to check 32 bytes at once, and aggregate some results to branch maybe every 64 or 128 bytes, like glibc `memchr` does. Or an example with intrinsics of searching for either of two bytes at odd positions.)

Or ask the OS to interrupt or kill the other threads, like via `C++20` `std::jthread` which has a request\_stop, or POSIX `pthread_cancel` with async cancellation enabled. (Or `pthread_kill` to send `SIG_USR1` or something and exit the thread in the signal handler, or go to sleep to wait for the next batch of work if you're starting a pool of worker threads instead of creating/destroying OS-level threads for every parallel operation.) This has literally no overhead during the actual search work.

# Answer
> 10 votes
I do not think there is a name for that particular algorithm, but I think it will achieve similar performance to much simpler parallel algorithms for this task. In general when designing parallel algorithms, you assume that you have $k$ cores at your disposal. Then, if a task can be accomplished in time $O(f(n))$ using one core, the gold standard for a parallel algorithm is to accomplish the same task in time $O(f(n)/k)$. The algorithm which you describe will search a list in time $O(n/k)$, so in that sense it is optimal because non parallel search requires $O(n)$ time with one core. It is worth noting though that you do not need to run the backward and forward search. If you just break the list up into $k$ chunks, and search them individually, that will also get you a runtime of $O(n/k)$. Making the other cores stop working after the desired element is found will not affect the runtime in theory, and is not too difficult to do in practice if parallelism is implemented in a reasonable way.

---
Tags: algorithm-analysis, runtime-analysis, search-algorithms
---


title: Determining the language of a DFA

text:
# Question
Title: Determining the language of a DFA
I've tried quite a large amount of examples, starting from 1 bit all the way up to 5 bits yet I couldn't put my finger on any recurring pattern of words that are accepted.

the DFA is as such:

The only language I could come up with that sort of covers this, is:

$L=\\{w: \\#\_1(w)\geq 1 \\; \\& \\; ends\\;with\\;even\\;no.\\;of\\; '0'\\;or\\;ends\\;with\\;'1'\\}$

yet this formulation for $L$ seems really off to me.

is there a better way to formulate this? or perhaps my answer is incorrect?

# Answer
> 1 votes
Your answer is correct. $L = \\{ w \\; | \\; w \text{ has at least one 1 and ends with an even number of 0s or ends with a 1 } \\;\\}$

Sketch of Proof in one direction: Because there's at least one 1, somewhere we find a 1 and get to $q\_2$. To end in $q\_2$, either the last word was a 1; or it was zero and last state was $q\_3$. Everytime we're in $q\_3$, we have an odd number of zeros at the end.

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


# Question
Title: Query about LRU Replacement Strategy - Confusion on Page Selection
I've been exploring the Least Recently Used (LRU) page replacement strategy, and I've come across a point of confusion that I would appreciate some clarification on.

As I understand it, in LRU, the page with the lowest (oldest) last access time is considered the least recently used and is a candidate for replacement. However, when I examine the provided page table with last access times:

* Page 1: Last accessed time - 94
* Page 2: Last accessed time - 23
* Page 3: Last accessed time - 101
* Page 4: Last accessed time - 44
* Page 5: Last accessed time - 23
* Page 6: Last accessed time - 64

It seems that Page 5 has the more recent last access time (23) compared to Page 3 (101). According to my understanding, a lower value in last access time implies a more recent access.

Could someone kindly help me understand why Page 3 is considered the correct answer for replacement instead of Page 5? I want to make sure I have a clear grasp of the LRU strategy.

# Answer
Time starts at zero. Page 5 was last accessed at $t=23$, while page 3 was last accessed at $t=101$. Suppose rn is $t=102$, which do you think is the least recently used page?
> 0 votes

---
Tags: page-replacement
---


# Question
Title: Proving $A_{TM}$ is mapping reducible to certain language
I've been asked to prove that the language $A\_{TM} = \\{ \langle M,w\rangle \mid M$ is a TM that accepts $w\\}$ is mapping reducible to the language $LOOP-ONE = \\{\langle M \rangle \mid M$ is a Turing machine that doesn't halt on **exactly one** input$\\}$.

I came up with the following idea :

> F = "On input \<M,w\>:
>
> 1. Construct the following machine M':
> M' = "On input x:
> 1.If $x=w \cdot 1$, enter a loop. (assuming $1 \in \Sigma$ )
> 2.Run M on w.
> 3.If M accepts, accept. otherwise, enter a loop."
> 2. Output \<M'\>."

As for the correctness of the reduction above we can see that :
If $\<M,w\> \in A\_{TM} \implies M$ accepts $w$ therefore by the construction above $M'$ accepts any input $x$ (besides $w\cdot1$) therefore in particular $M'$ halts on any input other than $w\cdot1$.
On the other hand,
If $\<M,w\> \notin A\_{TM} \implies M$ doesn't accepts $w$ therefore $M$ either loops on $w$ or rejects $w$.
If $M$ loops on $w$ then $\<M'\> \notin LOOP-ONE$ as $M'$ doesn't halts on $w$ and on $w\cdot1$.
If $M$ rejects $w$ then $M'$ will loop on any input $x$ and therefore $\<M'\> \notin LOOP-ONE$.

I was asked to make sure that the function that the TM F is computing is indeed computable, and I'm struggling to see what it practically means. What are the things that make a mapping reduction not computable (besides maybe the fact that the Turing machine F may not halt on some input, which is not the case here) ?

# Answer
For a reduction $f$ to be computable, there must be a TM that for all inputs $y$ halts with $f(y)$ written on its tape. The reduction you suggested is indeed computable. Here, your input $y$ is assumed to be of the form $\langle M, w \rangle$, then the reduction outputs a description of a machine $\langle M'\rangle$. The crux of the idea here is to notice that the reduction $f$ (or the machine that tries to implement it) does not really simulate the run of $M$ on $w$, and does not simulate the run of $M'$ on some input. It just outputs the description of $M'$ and then halts. So you only need to convince the reader that there is a TM $T\_{f}$ that can output the description of $\langle M'\rangle$ based only on the description of $\langle M, w\rangle$, and then halt. This is doable as you can take the description of $M'$ to be a description of a universal TM that has the description of $M$ and $w$ encoded in it (for example in its state-space). Also $M'$ has a state $q\_{loop}$ that forces it to inter a loop. Then, on input $x$, what $M'$ should be able to do is:

* Apply a simple check of the input's format: it is easy to describe a machine that does that and halt.
* Simulate the run of $M$ on $w$: we can describe also this component (or part) of the machine $M'$ similarly to the description of a universal TM.
* Enter a loop: we can encode the transition function of $M'$ to enter $q\_{loop}$ in some scenarios.

So the main thing here is to note that the description of $M'$ can be obtained by manipulating the description of $M$ and $w$ and putting that together with a description of universal TM that does simple checks. So you can think of $M$ ia a python code, and $w$ is its input. Then, you (the reduction), given this code and input, have to output a python code $M'$ that behaves in a way that depends on $M$ and $w$. That is doable, as long as you (the reduction) sew the codes together without really running them, and so the risk of you non-halting is avoided.
> 1 votes

---
Tags: turing-machines, reductions, mapreduce
---


title: Is the set of all DFAs countable?

text:
# Question
Title: Is the set of all DFAs countable?
Let $\Sigma$ be a finite nonempty alphabet. Is the set of all DFAs over $\Sigma$ countable?

I know the set of all regular languages is countable, however, it is impossible to build an injection from the DFAs to the regular languages since a regular language isn't necessarily accepted by only a single DFA.

# Answer
There are several ways to prove this. Here is a formal one:

You can encode the set of DFAs over $\Sigma$ as words over the constant alphabet $\Sigma' = \\{0, 1, \\#\\}$. This can be done as follows. Let $A = \langle \Sigma, Q, q\_0, \delta, F\rangle$ be a DFA over $\Sigma$. We define the encoding of $A$, denoted $\langle A\rangle$, as follows: $$ \langle A\rangle = \langle \Sigma\rangle \\#\\# \langle Q\rangle \\#\\# \langle q\_0\rangle \\#\\# \langle \delta\rangle\\#\\# \langle F\rangle,$$ where $\langle C\rangle$ is an encoding of $C$ over $\Sigma'$, for all $C\in \\{ \Sigma, Q, q\_0, \delta, F \\}$, to be defined below.

We distinguish between several cases:

* $C = \Sigma$: we can encode the letters in $\Sigma$ as increasing binary numbers over $\\{ 0, 1\\}$. For example, if $\Sigma = \\{ a\_0, a\_1, \ldots, a\_7\\}$, then we encode $a\_i$ as the binary representation of the number $i$, and so $\langle a\_i \rangle = \text{the binary representation of the number $i$}$. Then, we take $$\langle \Sigma \rangle = \langle a\_0\rangle\\# \langle a\_1\rangle \\# \cdots \\# \langle a\_7\rangle = 000\\# 001 \\# \cdots \\#111$$ so the $\\#$'s seprate between different letters.
* $C = Q$: also here, we can encode the states in $Q$ as increasing binary numbers.
* $C = q\_0$: already encoded in the previous item. Let's say we encoded $q\_0$ as the number 0 in binary.
* $C = \delta$: the encoding of $\delta$ can be simply a list of the transitions in $\delta$ separated by $\\#\\#\\#$: $$ \langle \delta\rangle = \langle t\_1\rangle \\#\\#\\#\langle t\_2\rangle\\#\\#\\# \cdots \\#\\#\\# \langle t\_k \rangle,$$ where $t\_i$ is the $i$'th transition of $A$. So it remains to show how we encode a general transition. A transition $t = q \xrightarrow{a} s$ can be encoded as $\langle t\rangle=\langle q \rangle \\# \langle a\rangle\\# \langle s\rangle$. Note that we already encoded states and letters, so the latter is well-defined.
* $C = F$: since we already encoded the set of states $Q$, $\langle F\rangle$ can be simply encoded as the list of numbers describing the states in $F$ separated by $\\#$'s.

What we've in total is a description of the DFA $A$ as a finite word over the constant alphabet $\Sigma'$. As the set $\Sigma'$ is countable, then there are at most $\aleph\_0$ DFAs over $\Sigma$.

**Note:** the format of the encoding can be different. Its just one naive way to do it. The idea is to encode a DFA by an object that you know has countably many instances.
> 2 votes

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


# Question
Title: Seeking a reference for NP-hardness of optimization problems
Most optimization textbooks **do not** cover the concept of NP-hardness. Some examples include:

* "Convex optimization" by Boyd and Vandenberghe
* "Numerical Optimization" by Nocedal and Wright
* "An Introduction to Optimization" by Chong and Zak

and half a dozen more well-known optimization textbooks.

Yet, in discussion on optimization problem, I frequently see people referring to some problems as NP-hard (or not).

The definition I've learned regarding complexity theory started from things like language, string, Kleene star operator, Turing machines, which are also things that are not mentioned in typical optimization textbooks.

So is there some type of reference in bridging the gap between complexity theory and optimization?

# Answer
In my opinion, monographs on approximation algorithms come closest to what you are seeking:

If you are still struggling with understanding NP-hardness theory, the classic monograph is:

* Computers and Intractability, by Michael Garey and David S. Johnson.
> 2 votes

---
Tags: complexity-theory, reference-request, np-hard, definitions, reference-question
---


# Question
Title: How to find an example for a case in the metric k-center problem
Given $n$ points in a 2d metric space, the $k$-center problem asks us to find a subset of size $k$ of the points which we will call centers. The task is to pick these centers to minimize the maximum distance from any point to its closest center.

A classic greedy algorithm repeatedly picks points which are furthest from any existing center until $k$ have been chosen and adds them to the set of centers.

An analysis of this $2$-approximation algorithm has two cases that relate the chosen centers to those from an optimal solution. One of those two cases is when two chosen centers are closest to the same center in an optimal $k$-center solution. But how can this ever occur? Is there a concrete example to show this occurring?

# Answer
> 4 votes
The following is a simple example:

Consider six points on a line: $p\_1, \dotsc, p\_6$. Let $k = 2$. The points $p\_4, p\_5, p\_6$ are at the same position (or you can consider them very close to each other).

Then, there is an optimal solution $\\{p\_2, p\_5\\}$ with cost $2$.

Suppose, the greedy algorithm chooses the first center as $p\_3$. Then, the next chosen center will be $p\_1$, which is from the same optimal cluster. And, the cost of the greedy solution is $d(p\_3, p\_4) \approx 4 = 2 \cdot OPT$.

# Answer
> 4 votes
Take five equidistant points, $p\_1, ..., p\_5$ on a line and let $k=2$. The optimal solution picks points $p\_2$ and $p\_4$ with quality $\text{OPT}=d$.

Now, suppose the arbitrarily chosen center is point $p\_3$, the central point. The next point will (wlog) be $p\_1$. The quality of this solution is $\text{dist}(p\_3, p\_5) = 2d$.

---
Tags: algorithms, np-hard, approximation
---


# Question
Title: Number of stops during trip - Dynamic programming algorithm
I am attending a course about algorithm design, and I have found an old test which has once been submitted. However, I don't have the solutions to it, and I am having some trouble with one specific excersise. This is the text:

Matt is planning a road trip from City A to City B, and he wants to minimize the number of breaks during the journey. He has a limit of n kilometers he can drive before needing a break. His map includes the distances between rest stops along the route.

The problem is simalar to the one appearing in this question, but the answers do not really go in depth about the actual algorithm

I am trying to build the algorithm with dynamic programming. The main idea is that for each possible stop, I check what is more convenient between stopping and not stopping. This is what I have come up with:

$$ OPT(km, i) = \left\\{\begin{matrix} 1+OPT(km, i+1) & d\_i \> km \\ min(1+OPT(km, i+1), OPT(n-d\_i, i+1)) & d\_i\leq km\\ 0 & i=n \end{matrix}\right. $$

Where $i$ is the number of the station, $n$ is the total number of stations, $km$ is the maximum drivable distance without stopping and $d\_i$ is the distance between the $i$'th station and the previous one.

I have thought about making it more efficient by using memoization, but I don't see how this could be done since the number of km left might vary between every call to $OPT$. I have no clue about how to prove that this algorithm actually gives the best possible solution, nor do I know what its time complexity is. I guess each call to $OPT$ is constant time, but the number of subproblems seems big.

Any help will be gratly appreciated!

# Answer
As it turns out, you don't need any dynamic programming to solve this problem, and a greedy solution works great. The greedy solution is: go as far as possible without taking a break from City $A$ (i.e. go to the furthest rest stop which is less than $n$ kilometers away). Repeat this process until you reach City $B$. This runs in time $O(n)$ by using, say, two pointers.

Why can we do this? Well, let $f(i)$ be the minimum number of breaks you need to reach rest stop $i$ (let's define City $A$ to be rest stop $0$ and City $B$ to be rest stop $m$). Then, $f(0) \le f(1)\le f(2) \le \ldots \le f(m)$.

Now, let's suppose we have computed $f(0), f(1), \ldots, f(i - 1)$. How can we compute $f(i)$? We may write $f(i) = 1 + \min\_{j \< i, d(i, j) \le n} f(j)$, where $d(i, j) = d(i, 0) - d(j, 0)$ is the distance between rest stops $i$ and $j$. By the increasing assumption on $f(j)$, it follows that $f(i)$ only depends on the single furthest before it coordinate $j$, which is identical to the greedy approach in the first paragraph.

Your dynamic programming approach looks fairly similar to this in many respects (just with a bit more casework, maybe).
> 1 votes

---
Tags: algorithms, time-complexity, algorithm-analysis, dynamic-programming, greedy-algorithms
---


# Question
Title: Does the Master Theorem apply to T(n) = 3T(n/3) + n/log2(n)?
Id say this is the first case of Master Theorem, but when I try to prove that the limit of f(n)/ n ^ (1-E) is 0, I cannot do it. Does anyone have a solution?

# Answer
This is Case 2b from the Wikipedia article: here $a = b = 3$ and $f(n) = n/\log n = n^{\log\_b a} \cdot \log^{k}(n)$ for $k = -1$. Thus, the solution is $\Theta(n\log \log n)$.
> 0 votes

---
Tags: algorithm-analysis, master-theorem
---


# Question
Title: If mergesort takes 30 sec to sort 64 elements in worst case, how many elements can be sorted at worst case by using it in 6 minutes?
# To sort 64 elements

Time required is $n\*log\_2{n}$ units

The equivalent posteriori time is 30 sec.

# In 6 minutes

I get 768 elements sorted.

But the answer is not 768 and is instead 512, I wonder why?

# Answer
> 1 votes
Disregarding the fact that these calculations make no sense in real world, here is what we get:

$n \cdot log\_2 n \cdot T = 30$

where $T$ is the time for single operation. We substitute $n=64$ and we get

$64 \cdot 6 \cdot T = 30$

this gives $T=0.078125$

We can now solve the following:

$n \cdot log\_2n \cdot 0.078125 = 360$

You can verify the solution is $512$.

# Answer
> 1 votes
6 minutes to 30 seconds is a factor of 12, so you want: $$ \frac{N\cdot\text{log}(N)}{64\cdot\text{log}(64)} = 12 $$ You can easily verify that for N=512, the result is indeed 12. For N=768 the result is 19.17, which is the wrong answer. Note that it doesn't matter which logarithm (binary, natural, ...) you use, the result is always the same.

While verifying the equation for a given N is easy, finding N is much harder. You can just try different values of N until you find one where the result is 12. You would have found that N=768 is too large (result 19.17) and tried smaller values until you found the correct one.

---
Tags: algorithms, mergesort
---


# Question
Title: Iteration scheduling vs processor scheduling
In parallel programming the iteration scheduling is defined as the determination of the logical execution time for each loop iteration, while in operating systems, the processor scheduling (FCFS etc) is defined as the ordering in which the processes get the CPU to execute. Since the execution of a loop is a process itself, i wonder if these terms describe the same thing even though a process is more general than a simple loop that perform pure calculations since, for example, it generally requires additional resources, such as hard disk access. Generally speaking, is there any connection between these terms, or they can used independently of each other? Thanks.

# Answer
They are different problems in practice. Task scheduling is about fulfilling constraints, computation scheduling is about minimizing work.

In computing, we know the entire problem in advance and we want to find the optimal schedule (order of operations, split between multiple machines) and then execute it. If we have a product of four matrices `ABCD` we can solve this as `((AB)C)D` or `(AB)(CD)` or `(A(BC))D` or `A((BC)D)` or `A(B(CD))`. Depending on the shape of the matrices, some of these calculations produce much larger intermediate results than others and consequently run slower. For database queries, we can chose which filter to apply first and this will have a massive performance impact. How to split work between multiple machines for parallel computing (to minimize communication overhead and exploit locality) also falls into this category of scheduling.

Scheduling tasks in an operating system is different. Less science, more practical engineering. The scheduler doesn't know in advance what resources will be requested in the future, so it cannot make optimal decisions. Often a notion of optimality doesn't exist at all, the scheduler just needs to be 'good enough' i.e. not violate any deadlines on the critical tasks.

Strictly speaking, scheduling tasks is also 'scheduling the order of operations' as in my matrix example above, but in practice it's a very different problem: 'find a solution that fulfills all constraints' versus 'unconstrained optimization for least amount of floating point operations.' The goal is different, the constraints are different and the information you have is different.
> 1 votes

---
Tags: scheduling, loops
---


# Question
Title: Turing degree of some functions related to Rice's theorem
Rice's theorem asserts that as soon as $f$ is non-trivial (i.e., non-constant), and extensional (i.e., $f(M) = f(M')$ as soon as $M$ and $M'$ are codes of Turing machines with the same behavior, in the sense that both halt and return the same output or both don't halt), $f$ is uncomputable.

One classic way to prove this is by reduction from the halting problem. The key observation is that all machines that don't terminate are sent by $f$ to the same value (by extensionality), and there is a Turing machine $P$ such that $P(f)$ is a different value (by non-triviality). The reduction takes a Turing machine $M$ and builds a machine $E$ that runs $M$ and ignores the output, then runs $P$ and returns the output. One sees that $E$ has the same behavior as machines that don't halt, or the same behavior as $P$, depending on the termination of $M$, thus the value of $f$ on $E$ allows to decide the termination of $M$.

I'm interested in \[edit: *total*\] functions $f$ that verify a weaker condition:

* If $M$ is (the code of) a Turing machine that halts and returns 0, then $f(M) = 0$,
* If $M$ is a Turing machine that halts and returns 1, then $f(M) = 1$.

There is no guarantee on the value of $f(M)$ if $M$ doesn't terminate, or if it terminates but returns a value other than 0 or 1.

The motivation is a riddle proposed by David Madore (see http://www.madore.org/~david/weblog/d.2023-12-24.2774.dragon-riddle.html in French).

I am able to prove that such a function $f$ is uncomputable, by a diagonalization argument: assuming it is computed by a Turing machine $F$, use Kleene's recursion theorem to build the program

$E : \text{if}\ F(E) = 0\ \text{then return}\ 1\ \text{else return}\ 0$

Since $F$ halts, $E$ halts and returns 0 or 1. Either way, we get a contradiction.

However, the proof of Rice's theorem by reduction actually gives a slightly stronger statement than "$f$ is uncomputable": it also proves that the halting problem is reducible to $f$, or in other words, the Turing degree of $f$ is $≥ 0'$. I could not find a similar proof with the weakened assumption.

**Question:** Is it true that any function $f$ verifying this weaker assumption has Turing degree $≥ 0'$?

# Answer
Just to clarify the question, you are demanding that $f$ be *total*, i.e. that $f(M)$ terminate in all cases, even if $M$ does not terminate (otherwise we can simply run $M$ and return its output).

**Relation to another question:** This being said, question turns out to be the same as the one I asked here on MathOverflow about Turing degrees of sets separating theorems and negations-of-theorems (of Peano arithmetic), i.e., I was asking about a function that must return $1$ on a theorem, $0$ on a negation-of-theorem, and can return anything on undecidable statements (or indeed non-well-formed ones, but that's not interesting because well-formedness is trivially decidable anyway). Allowing it to return anything other than $0$ or $1$ is obviously irrelevant because we can always convert any other answer to $0$ (say).

The reasons why the question you ask (about terminating of Turing Machines) and the one I asked (about separating theorems and negations-of-theorems) are equivalent is that we can convert a machine $M$ to the ($\Sigma\_1$) arithmetical statement “$M$ halts and returns $1$”, which is a theorem (of Peano arithmetic) if indeed $M$ halts and returns $1$ and its negation is a theorem (of Peano arithmetic) if $M$ halts and returns $0$; and conversely, we can convert a statement $\varphi$ (of arithmetic) to the Turing machine which searches for proofs of $\varphi$ and $\neg\varphi$ in parallel and returns $1$ if the former is found and $0$ if the latter is found.

**The answer proper:** Now the quick answer I received is that $f$ is not necessarily of degree $\geq\mathbf{0}'$, indeed **it can be of low degree** (that is $\deg(f)' = \mathbf{0}'$, which clearly implies $\deg(f) \not\geq \mathbf{0}'$) as follows from Jockush-Soare *low basis* theorem which states that every infinite computable subtree of the infinite binary tree $\lbrace 0,1\rbrace^\*$ has a low infinite branch. (See, e.g., Cooper, *Computability Theory* (2004), theorem 15.4.3, or Soare, *Turing Computability and Applications* (2016), theorem 3.7.2, for proof and further explanations.)

So in the context of your question, you would do this: enumerate all Turing Machines in a sequence $(M\_n)$ and then define a binary subtree $\mathscr{T}$ of $\lbrace 0,1\rbrace^\*$ as follows: to decide whether a length $n$ binary word $w$ is part of $\mathscr{T}$, you run $M\_0,\ldots,M\_{n-1}$ for $n$ steps: if $M\_i$ terminates during that time and returned $0$ or $1$, then the $i$-th letter of $w$ must equal that result (otherwise, the $i$-th letter of $w$ has no constraint). Clearly this is decidable, and clearly this is a tree (as constraints are only ever added); it is sometimes known as the (a?) **Kleene tree**. Now given an infinite branch of the tree, seen as an infinite binary word, we simply let $f$ on $M\_n$ return the $n$-th letter of that word: this satisfies your constraints, because if $M\_n$ terminates after $k\geq n$ steps, then no word of length $k$ in $\mathscr{T}$ will have an $n$-th letter that disagrees with the output of $M\_n$, and in particular the infinite branch cannot have made that choice. So by the low basis theorem, there is an $f$ of low degree.

**Further remarks:** From Laurent Bienvenu's answer on MathOverflow, we also learn that the possible degrees of functions $f$ as you defined are known as PA degrees and that a number of things are known about them.

I guess this example disproves the common wisdom that proving uncomputability of something (already known to be computably enumerable) is always done by reducing the Halting Problem to that something (wisdom “justified” by the difficulty of exhibiting a natural degree intermediate between $\mathbf{0}$ and $\mathbf{0}'$, especially a c.e. one, a problem solved by the Friedberg-Mučnik theorem). The thing is that here $f$ is unconstrained at many values, so we're not defining a single degree but a class of them.

Note that in some generalizations of Turing degrees (I like to refer to Kihara's paper “Lawvere-Tierney topologies for computability theorists”, which I tried to give an account of on my blog (in French) and which generalizes Turing degrees in various ways up to Lawvere-Tieney topologies on the effective topos), we can define degrees for nondeterministic functions like this, and then we *do* have a natural intermediate degree between $\mathbf{0}$ and $\mathbf{0}'$, namely the one you defined (if we just say that $f$ is a nondeterministic function returning $0$ and $1$ when $M$ does not terminate returning $0$ or $1$), and is (equivalent to the one) called $\mathtt{LLPO}$ in Kihara's aforementioned paper (because of its relation to a principle of constructive mathematics).
> 5 votes

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


title: Fast string-to-integer algorithm

text:
# Question
Title: Fast string-to-integer algorithm
I work with big integers that I need to convert to and from strings, and to and from different bases.

In JavaScript, BigInt allows to convert an integer to a string in a chosen base by doing:

```
12345n.toString(9)

```

Unfortunately, when parsing a string to convert it to an integer, BigInt only accepts bases 2, 8, 10, and 16. It isn't possible to parse with a base of 9 (there is a proposal for this, but it's not getting much traction).

So, I've written the algorithm myself:

```
const ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
const fromString = (text, base) => {
    let result = 0n;

    for (let i = 0; i < text.length; i++) {
        result = result * base + BigInt(ALPHABET.indexOf(text.charAt(i)));
    }

    return result;
};

```

It works correctly, but it's very slow.

For example, with the number `1×10^500,000` (a string containing a `1` followed by `500,000` zeros):

* `BigInt(str)` takes about 50ms on my machine
* `fromString(str, 10n)` takes 15s, 300 times longer!

The fact that BigInt is implemented in C++ is not enough to explain this enormous difference, I believe.

The algorithm must be much more efficient. It seems to be `FromStringLarge`, in V8. However, I do not understand how it works and I didn't find any other references to this algorithm.

**Would someone be able to explain the `FromStringLarge` algorithm, or suggest another algorithm?**

# Answer
> 0 votes
Given a string of length $n$, your own algorithm will loop $n$ times, and each addition grows in the order of $O(n)$, yielding a total of $O(n^2)$.

`result = result * base + digit`

With length $n = 10^6$, in the beginning we add one single-digit number, in the end we add one million-digit number, yielding $1 + 2 + 3 + ... + n = n^2$ single-digit operations.

Instead, using the efficient `FromStringLarge` divide-and-conquer algorithm, we may accomplish $O(n \log n)$. How might this be achieved? According to the documentation: Multiply-and-add neighboring pairs of parts, then loop, until only one part is left.

`result = left * multiplier + right`

With length $n = 10^6$, in the beginning we add one million single-digit numbers, in the end we add one million-digit number, yielding $n * 1 + n / 2 * 2 + n / 4 * 4 + ... + 1 * n = n \log n$ single-digit operations.

# Answer
> 1 votes
I'm adding an answer to share my rough JavaScript version of V8's `FromStringLarge` algorithm:

```
const fromBase = (text: string, base: bigint): bigint => {
    let parts = text.split("").map((part) => [BigInt(part), base]);

    if (parts.length === 1) {
        return parts[0][0];
    }

    let pairFull: boolean;
    while (parts.length > 2) {
        pairFull = false;
        parts = parts.reduce<bigint[][]>((acc, cur, i) => {
            if (!pairFull) {
                if (i === parts.length - 1) {
                    acc.push(cur);
                } else {
                    acc.push([
                        cur[0] * parts[i + 1][1] + parts[i + 1][0],
                        cur[1] * parts[i + 1][1],
                    ]);
                    pairFull = true;
                }
            } else {
                pairFull = false;
            }
            return acc;
        }, []);
    }

    return parts[0][0] * parts[1][1] + parts[1][0];
};

```

It now takes 120ms to do the conversion a string containing 500,000 random digits in base 10! Just slightly slower than BigInt, and without any optimisations.

---
Tags: integers, base-conversion
---


title: ALL_{NFA} is PSPACE-complete

text:
# Question
Title: ALL_{NFA} is PSPACE-complete
Show that $ALL\_{NFA}$ = {$\langle M\rangle : M$ is $NFA$ and $L(M) = \Sigma^\*$} is $\text{PSPACE-complete}$. I've manged to prove that the langauge is in $\text{PSPACE}$. Indeed, it is easy to see that $\overline{ALL\_{NFA}}\in \text{NPSPACE}$ (the machine just nondeterministically guess a word rejected by the automaton and this process is bounded by an appropriate space). Then, using the fact that $\text{NPSPACE} = \text{PSPACE}$, we get that $\overline{ALL\_{NFA}}\in PSPACE$. Finally, as $\text{PSPACE}$ is closed under complement, we get that $ALL\_{NFA} \in PSPACE$. But I did not manage to show that $ALL\_{NFA}$ is $\text{PSPACE-hard}$.

# Answer
Let's show a generic PTIME reduction from any language in $\text{PSPACE}$ to $ALL\_{NFA}$. Let $L \subseteq \Sigma^\*$ be a language in PSPACE, and let $T$ be a TM that decides $L$ with polynomial space-complexity $s: \mathbb{N} \to \mathbb{N}$. We need to show that $L\leq\_p ALL\_{NFA}$. So we need to define a polynomial-time reduction that on input $x$, outputs an NFA $A\_x$ such that $T$ accepts $x$ iff $A\_x$ accepts all its inputs.
We actually show that we can construct $A\_x$ in time polynomial in $|T|$ and $s(|x|)$. Let $n = s(|x|)$, and so each configuration in the computation of $T$ on $x$ uses at most $n$ tape cells.

We define $A\_x$ so that it accepts an input $y$ iff one of the following holds:

(C1) $y$ does not describe an encoding of a legal computation of $T$ on $x$, or

(C2) $y$ starts with an encoding of the initial configuration of $T$ on $x$, and contains an encoding of the accepting state of $T$.

It is not hard to see that $T$ accepts $x$ iff $A\_x$ accepts all its inputs. Indeed, if $T$ accepts $x$, then for all inputs $y$ of $A\_x$, either $y$ does not describe an encoding of a legal computation of $T$ on $x$, and thus accepted by $A\_x$ (due to (C1)), or $y$ describes an encoding of a legal computation of $T$ on $x$, and since $T$ accepts $x$, then $y$ encodes an accepting computation of $T$ on $x$, and thus is accepted by $A\_x$ (due to (C2)). Conversely, if $T$ rejects $x$, then the word $y$ that encodes the rejecting computation of $T$ on $x$ is rejected by $A\_x$ as it does not satisfy (C1) nor (C2).

We now describe the construction of $A\_x$. This is a tedious technical part, and I am taking the encoding part of it from here with minor changes:

We can write $T=\langle{\Gamma,Q,\Delta,q\_0,q\_{acc},q\_{rej}\rangle}$, where $\Gamma$ is the tape-alphabet, $Q$ is the set of states, $\Delta \subseteq Q \times \Gamma \times Q \times \Gamma \times \\{L,R\\}$ is the transition relation (we use $(q,a,q',b,D)\in \Delta$ to indicate that when $T$ is in state $q$ and it reads the input $a$ in the current tape cell, it moves to state $q'$, writes $b$ in the current tape cell, and its reading head moves one cell to the left/right, according to $D$), $q\_0$ is the initial state, $q\_{acc}$ is the accepting state, and $q\_{rej}$ is the rejecting one.

We encode a configuration of $T$ that uses at most $n = s(|x|)$ tape cells by a word of the form $\\# \gamma\_1 \gamma\_2 \ldots (q,\gamma\_i) \ldots \gamma\_{n}$. That is, the encoding of a configuration starts with a special letter $\\#$, and all its other letters are in $\Gamma$, except for one letter in $Q \times \Gamma$. The meaning of such a configuration is that the $j$'th cell in $T$, for $1 \leq j \leq n$, is $\gamma\_j$-labeled, the head of $T$ points at $i$'th cell, and $T$ is in the state $q$. For example, the initial configuration of $T$ on the input word $x$ is encoded as $\\# (q\_0,x\_1) x\_2 \cdots x\_{|x|} b b \cdots b$ (with $n-|x|$ occurrences of $b$'s) where $b$ stands for an empty cell. We can now encode a computation of $T$ as a sequence of configurations.

Let $\Sigma'=\\{\\#\\} \cup \Gamma \cup (Q \times \Gamma)$, and let $\\# \sigma\_1 \ldots \sigma\_{n} \\# \sigma'\_1 \ldots \sigma'\_{n}$ be two successive configurations of $T$. We also set $\sigma\_0$, $\sigma'\_0$, and $\sigma\_{n+1}$ to $\\#$. For each triple $\langle{\sigma\_{i-1},\sigma\_i,\sigma\_{i+1}\rangle}$ with $1 \leq i \leq n$, we know, by the transition relation of $T$, what $\sigma'\_i$ should be. In addition, the letter $\\#$ should repeat exactly every $n+1$ letters. Let $next(\sigma\_{i-1},\sigma\_i,\sigma\_{i+1})$ denote our expectation for $\sigma'\_i$. For example,

* $next(\sigma\_{i-1},\sigma\_i,\sigma\_{i+1})=\sigma\_i$ if $\sigma\_i=\\#$, or if non of $\sigma\_{i-1},\sigma\_i$ and $\sigma\_{i+1}$ are in $Q\times\Gamma$.
* $next((q,\gamma\_{i-1}),\gamma\_i,\gamma\_{i+1})= next((q,\gamma\_{i-1}),\gamma\_i,\\#)=$ $ \left\[ \begin{array}{ll} \gamma\_i & \mbox{If $(q,\gamma\_{i-1}, q',\gamma'\_{i-1},L) \in \Delta$}\\ (q',\gamma\_i) & \mbox{If $(q,\gamma\_{i-1}, q',\gamma'\_{i-1},R)\in \Delta$} \end{array}\right\]$
* $next(\gamma\_{i-1},\gamma\_i,(q,\gamma\_{i+1}))= next(\\#,\gamma\_i,(q,\gamma\_{i+1}))=$ $ \left\[ \begin{array}{ll} \gamma\_i & \mbox{If $(q,\gamma\_{i+1}, q',\gamma'\_{i+1},R)\in \Delta$}\\ (q',\gamma\_i) & \mbox{If $(q,\gamma\_{i+1}, q',\gamma'\_{i+1},L)\in \Delta$} \end{array}\right\]$
* etc...

I won't detail all the cases, but you got the idea. Also note that we have a few edge cases that we need to consider, for example, since the machine does not use more than $n$ tape cells then the case where $i = n$ and we move to the right is impossible. etc.

Now back to the answer. The idea is that every word $y$ that encodes a computation that does not contain violations of the transition function of $T$, when it uses at most $n$ tape cells, must be consistent with $next$. So the NFA $A\_x$, when it reads an input $y$, guesses from its initial state to check whether $y$ satisfies $(C1)$ or $(C2)$.

When $A\_x$ guesses to check condition (C1), it checks whether $y$ does not describe an encoding of a legal computation of $T$ on $x$. We check whether $y$ is a word that satisfies at least one of the following:

* $y$ does not start with the initial configuration of $T$ on $x$, or
* $y$ is of length at least $n + 2$ and describes a violation of $next$, where $A\_x$ guesses a position in $y$ and checks whether the guessed position starts with three letters $\sigma\_{i-1},\sigma\_{i}, \sigma\_{i+1}$ describing three successive letters in the encoding and ends with a letter $\sigma'\_2$, which comes $n+1$ letters after $\sigma\_i$ in the encoding, yet is different than $next(\sigma\_{i-1},\sigma\_{i}, \sigma\_{i+1})$.

When $A\_x$ guesses to check condition (2), it checks whether $y$ starts with the initial configuration of $T$ on $x$, and checks whether $y$ contains a letter of the form $(q\_{acc}, \gamma)$.

It is not hard to see that $A\_x$ can be constructed using at most a number of states that is polynomial in $|T|$ and $n = s(|x|)$. Indeed, the length of the description of the initial configuration of $T$ on $x$ is linear in $n$. Also, the number of triples $(\sigma\_{i\_1}, \sigma\_i, \sigma\_{i+1})$ is polynomial in $|\Sigma'|$.

**Note:** the crux of the proof here is that we can check whether a computation violates the transition function of $T$ by performing a local check -- this is what $next$ does: it is sufficient to guess a window of length 3 around some position in $T$'s tape, and check whether this portion of the tape is problematic.
> 2 votes

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


# Question
Title: Representing Determinstic Infinite Automata
Does there exist a general approach in mainstream academia for representing a deterministic infinite automata? Unlike the finite kind, this one with infinite number of states.

Although there is infinite state. There is a finite number of types of states. E.g. state $inBrackets\_k$ goes to state has an edge leading to $inBrackets\_{k+1}$ when receiving input **'('**. $inBrackets$ can be considered the class/type of those infinity many states. (Thats a language of balanced brackets handle by deterministic infinite state machine example).

Further more. Could deterministic infinite automata be minimised. I.E. Minimise the number of types of states, using the same approach we use for the finite kind?

# Answer
As Yuval Filmus explains, every language can be recognized by an infinite-state DFA. So, it is not a concept that is of much interest in computability and automata theory.

Of course you can represent an infinite-state DFA using the same mathematical formulation as a finite-state DFA. The standard definition of a DFA says that it is a tuple $(Q,\Sigma,\delta,q\_0,F)$ where $Q$ is a finite set of states, etc. If you simply allow $Q$ to be infinite but keep everything else the same, you can use the same formulation to represent an infinite-state DFA. So no special approach is needed.

Minimization requires some care to define, as all countably infinite sets have the same cardinality.

I wonder if you're actually looking for the notion of a pushdown automaton.
> 3 votes

# Answer
Besides what has been said, I wonder: what kind of real physical device would such a thing (a deterministic infinite automata) modelize?

I mean, a Turing machine has an infinity of possible states but at least you can start running it with a bounded memory (limiting it to $n$ reachable states), then after some run time if you have exhausted the memory you can "buy more RAM" and rerun the machine with $n^2$ reachable states and so on.

That's why it is sometimes called an *unbounded* memory model of computation (not *infinite*).

Unless you assume more about the infinite states automata (like you have a function which bounds the number of accessible states after n steps), you would have to provide an infinite amount of memory right from the start... and that is not physically possible.
> 0 votes

---
Tags: finite-automata
---


# Question
Title: Why are non-deterministic Buchi automata factorially succinct when compared to deterministic Rabin Automata?
I am trying to demonstrate the following idea without success.

> There are infinitely many $n \in \mathbb{N}$ such that: There is a non-deterministic Buchi automata of size $n$ such that a deterministic Rabin Automata accepting the same language has at least $n!$ states.

Any help would be appreciated

# Answer
> 5 votes
This is Theorem 1.30 in the chapter "Omega-Automata" in the book "Automata, Logics, and Infinite Games: A Guide to Current Research" edited by Erich Grädel, Wolfgang Thomas and Thomas Wilke. They have a proof as well (and a literature referene to the original publication).

Note that instead of the nondeterminstic Buchi automaton having $n$ states, it needs to have $O(n)$ states to make the proof work. The problem is then defined slightly differently to make this precise.

Note that it is a bit confusing if you write "Buchi automata" and "deterministic Rabin automata" in the same question if the former are meant to be "nondeterministic Buchi automata". There is ample work both on deterministic and non-deterministic Buchi automata, so spelling out which variant is meant is important.

# Answer
> 2 votes
Usually, when defining the size of a Rabin automaton, we take into consideration the automaton's index (the number of Rabin pairs) and not only the number of states. What you asked for is well-known, and here are the known lower bounds of the $NBW \to DRW$ translation. Where $NBWs$ is an abbreviation for nondeterministic Buchi word automata, and $DRWs$ is for deterministic Rabin word automata.

In 1988 Max Michel showed a lower bound of $2^{\Omega(nlogn)}$ states and index in $O(n)$. Then, later in 1999 Christof Löding extended the result, and showed that there is no equivalent DRW with less than $2^{\Omega(nlogn)}$ states regardless of the index. Finally, in 2009, Thomas Colcombet and Konard Zdanowski, gave a tight lower bound of $\Omega((1.64n)^n)$, for a large alphabet.

# Answer
> -2 votes
Are you sure you didn't get them mixed up?

It seems like for any Buchi automaton with accepting states F, we can build the equivalent Rabin automaton with accepting conditions $\Omega = \\{(\\{\\}, F)\\}$ that accepts the same language.

(I.e., any infinite sequence $\rho$ has to intersect some state in $F$ infinitely often and has no restrictions on what states it can't hit infinitely often.)

I'm using the acceptance condition here https://en.wikipedia.org/wiki/Ω-automaton#Acceptance\_conditions. Was there a different formulation you had in mind?

---
Tags: automata, buchi-automata
---


# Question
Title: Does the pumping lemma for context-free languages really require accepting a string with zero levels of nesting?
In the pumping lemma conditions for context-free grammar we have that the string can be divided into $uv^{i}xy^{i}z$, but in the case of $i = 0$, why does it still belong to the language?, is it possible to have an example with a string? Should it be $i = 1$ is one repetition and for $i = 0$?

In the case $i = 0$ the word $w = uxz$?

# Answer
> 2 votes
While the answer by Hendrik Jan is correct. Here is a concrete example. Consider a CFG $G$ with the following rules $S \to aSb|\epsilon$. It is not hard to see that $L(G) = \\{a^n b^n: n\geq 0\\}$, and that for example, $p = 4$ is a pumping constant for $L(G)$. Indeed, every word $d$ in $L(G)$ of length at least $4$, is of the form $d = a^k \cdot a \cdot \epsilon \cdot b \cdot b^k$, where $k\geq 1$. Hence, we can write $d$ as $d = uvxyz$, where $ u = a^k, v = a $, $x =\epsilon, y = b$, and $z=b^k$. Clearly, $|vxy| =2 \leq p$. Also, it is easy to verify that for all $i\geq 0$, the word $uv^ix y^i z$ is in $L(G)$. Indeed, by pumping $v$ and $y$ $i$ times, we add/remove the same number of $a$'s and $b$'s in the appropriate places.

Now you can consider the word $u = a^2b^2 \in L(G)$ of length at least $4$, and write it as $uv x y z$, where $u = v = a, x = \epsilon, \text{and }y =z =b$. Then, you can pump down with $i = 0$ and get the word $u\cdot v^0 x y^0 z = a \cdot \epsilon^3 \cdot b = ab \in L(G)$.

# Answer
> 3 votes
If the string generated by the grammar is long enough then somewhere in the derivation tree we will find a path with a repeated variable. Below that is $A$. This induces the devision $vwxyz$ of the generated string into substrings, following the subtrees in the derivation.

Using the rules of the grammar we can play with the derivations $S\Rightarrow^\* vAz$ (outer part of the tree), $A \Rightarrow^\* wAy $ (middle part, which can be repeated) and $A \Rightarrow^\* x$ (under the lowest $A$). In that way we find derivations for all strings $vw^ixy^iz$, including the case $i=0$, where we indeed obtain $vxz$.

Sorry my symbols are a little off. I reused an old picture.

---
Tags: context-free, pumping-lemma
---


# Question
Title: Prove that the number of comparisons between elements in binary heap build is at most (2n-2)
## Question

Prove that the number of comparisons between elements in binary heap build is at most $2n-2$.

$n$ is the total number of the nodes.

---

## Pseudocode

```
BUILD-MAX-HEAP (A)
1 heap-size [A] < - length[A]
2 for i <- Length[A]/2| downto 1
3 do MAX-HEAPIFY (A, i)

```

```
MAX-HEAPIFY (A, i)
1 l <- LEFT (i)
2 r <- RIGHT (i)
3 if l <= heap-size [A] and A[l] > Ali]
4    then largest <- l
5    else largest <- i
6 if r <= heap-size [A] and A[r] > A[largest]
7    then largest <- r
8 if largest ‡ i
9    then exchange A[i] with A[largest]
10   MAX-HEAPIFY (A, largest)

```

---

## What I tried

I know that the number of comparisons between elements in binary heap build is at most:

$$ \sum\_{i=0}^{\lfloor \log\_{2}{n} \rfloor} \bigg \lceil \frac{n}{2^{i+1}} \bigg \rceil \cdot 2i $$

where $n \in \mathbb{N}$.

Because the number of nodes of height $i$ is at most$ \bigg \lceil \frac{n}{2^{i+1}} \bigg \rceil $, for each node there are at most $2i$ comparisons. Since the height of the tree is $\lfloor \log\_{2}{n} \rfloor$ we can claim what I claimed above.

I want to claim that: $$ \sum\_{i=0}^{\lfloor \log\_{2}{n} \rfloor} \bigg \lceil \frac{n}{2^{i+1}} \bigg \rceil \cdot 2i \le 2n-2 $$

However, there exists a counterexample $n = 9$.

I have 2 questions:

* Is this claim is true?
* How can I deduce that? (I tried)

---

A similar question has been asked in here. I didn’t understand the solution which also assumed tree is full.

# Answer
The first two proofs only work for a fully populated heap of height **h**, which contains **n=2h-1** items. The third proof also works for partial heaps. Throughout this answer, i will use two functions called **BuildCost** and **MergeCost**. The build cost is the cost for constructing a heap of height **h** from scratch. The merge cost is for merging two heaps of height **h** and one unsorted item into a single heap of height **h+1**.

### Your approach, revisited

I used **h-1** and **n+1** instead of floor/ceiling, so my proof is only valid for a fully populated heap as described in the intro. All divisions and logarithms are exact in my solution. $$ \begin{align\*} \text{BuildCost}(h) &= \sum\_{i=0}^{h-1}\frac{2^{h-1}}{2^{i+1}}\cdot\text{MergeCost}(i) \\ &= \sum\_{i=0}^{h-1}\frac{2^{h-1}}{2^{i+1}}\cdot2i \\ &= 2^h\sum\_{i=0}^{h-1}\frac{i}{2^i} \\ &= (n+1)\sum\_{i=0}^{h-1}\frac{i}{2^i} \end{align\*} $$ At this point, we can use the identity: $$\sum\_{m=0}^M\frac{m}{2^m} = 2-\frac{M+2}{2^M}$$ to solve the build cost as: $$ \begin{align\*} \text{BuildCost}(h) &= 2^h\sum\_{i=0}^{h-1}\frac{i}{2^i} \\ &= 2^h\left(2 - \frac{h-1+2}{2^{h-1}} \right)\\ &= 2\cdot2^h - 2h -2 \\ &= 2(n+1) - 2h - 2 \\ &= 2n - 2h \\ \end{align\*} $$

### Alternative: proof by induction

Here is a proof by induction, which confirms the results above. I like it better because it doesn't rely on a non-obvious identity like the other proof.

Induction hypothesis: $$ \begin{align\*} \text{BuildCost}(h) &= 2n - 2h\\ \text{MergeCost}(h) &= 2h \\ n &= 2^h-1 \end{align\*} $$ The base case is a heap of height one, which requires zero comparisons to build: $$ \text{BuildCost}(1) = 2(2^1-1) - 2\cdot1 = 0 $$ The induction step is: $$ \begin{align\*} \text{BuildCost}(h+1) &= 2(2^{h+1}-1) - 2(h+1)\\ &= 4\cdot2^h -2h -4 \\ &= 4\cdot2^h -4h -4 &+& 2h \\ &= 2(2\cdot2^h -2h -2) &+& 2h \\ &= 2\cdot(2(2^h-1)-2h) &+& 2h \\ &= 2\cdot\text{BuildCost}(h) &+& \text{MergeCost}(h) \end{align\*} $$

### Extension to partial heaps

The build cost for a full heap is **2n-2h**. We can think of the **-2h** term as a "merge budget" so that when we merge the heap, we're still below the **2n** limit. If we merge two heaps of the same height, both sides bring a budget of **2h** and the unsorted item brings a budget of **2**, so we end up with **4h+2** of which the merge itself consumes **2h**. What remains is **2(h+1)** and this is exactly the merge budget that we want to pass up the tree. So far, this paragraph is a repeat of the induction step.

Now let's do the induction step again, but this time the left child has height **h** and the right child has height **h-1**. The left child has **nl** items (fully populated or not) and build cost of **2nl-2h**. The right child has **nr** items (fully populated or not) and build cost of **2nr-2(h-1)**. My working hypothesis is that all heaps of height **h** have a build cost of **2n-2h** regardless if fully populated or not. This is false, but for now let's pretend it's true. $$ \begin{align\*} \text{BuildCost} &= \text{BuildCost}(h) + \text{BuildCost}(h-1) + \text{MergeCost}(h)\\ &= 2n\_l - 2h + 2n\_r - 2(h-1) + 2h \\ &= 2n\_l + 2n\_r + 2 - 2h \\ &= 2(n\_l + n\_r + 1) - 2h \\ &\neq 2(n\_l + n\_r + 1) - 2(h+1) \end{align\*} $$ The merged heap has **nl+nr+1** items and height **h+1**. According to my working hypothesis, it should have a build cost of **2(nl+nr+1)-2(h+1)**. This is wrong, the actual build cost requires two extra comparisons. Using the terminology of "merge budget" again, we can clearly see what went wrong: The shorter child's merge budget was only **2(h-1)**, yet the merge required **2h** comparisons in the worst case (recursion into the taller child) and we're now two comparisons short of a balanced budget. In conclusion, a heap of **n** items has a build cost of: $$\text{BuildCost} = 2n-2h+2k $$ where **h** is the height and **k** is the number of asymmetric mergers (left child one taller than right child) that occurred during construction of the heap. Now we have to prove that **k\<h** or, in other words, that there is at most one asymmetric merger per (non-leaf) layer. This is indeed true. Here is a small example of a heap with **n=10**, **h=4**. The letter **x** denotes a missing leaf (compared to a fully populated heap).

```
         1
    2         3
 4     5    6   7
8 9  10 x  x x x x

```

Since we populate the heap breadth first and from left to right, there can be only one partially populated node per layer. In this example, only nodes 1 and 5 have children of unequal height, so **k=2**. Here's another example where nodes 1, 2, and 4 have children of unequal height, so **k=3**. That's the maximum asymmetry we can achieve in a heap of height 4.

```
         1
    2         3
 4     5    6   7
8 x   x x  x x x x

```

But wait, there's more. We can find the asymmetric mergers from the binary representation of the number of missing leafs. In the **n=10** example, we had 5 missing leafs. 5 is 101 in binary, which tells us there's an asymmetric merger in the top and bottom layer but not in the middle layer (we ignore the leaf layer here, so top/middle/bottom refers to the non-leaf layers). The **n=8** example had 7 missing leafs, which is 111 in binary. I think you can see a pattern. Finally, the build cost of an arbitrary heap is: $$\text{BuildCost} = 2n-2h+2\cdot\text{PopCount}(2^h-1-n) \le 2n-2 $$
> 2 votes

---
Tags: algorithms, data-structures, algorithm-analysis, binary-trees, heaps
---


# Question
Title: Is the language accepted by a DFA with a fixed word on the stack after consuming it a deterministic context free language?
Let $\cal M$ be a deterministic stack automaton ${\cal M } = (Q, \Sigma, \Gamma, \delta, q\_0, F, Z\_0 )$. Let $\gamma \in \Gamma^\* $ a word on the stack alphabet. Is it true that the language $$L = \\{ w \in \Sigma^\* \mid (q\_0,w,Z\_0) \vdash^\* (q,\epsilon, \gamma),\ q \in F \\}$$ is a deterministic context free language? Is this family different from the family of deterministic context free languages? If so, how is this family of languages called in the literature? I was particullary interested in the case of $\gamma = Z\_0$.

*Commentary*: This question was migrated from TCS stack exchange.

# Answer
Yes, $L$ is a deterministic context-free language.

I will describe how to build a deterministic pushdown automaton $\mathcal{M}'$ to recognize $L$. The stack alphabet of $\mathcal{M}'$ is $\Gamma' = \Gamma \times \\{0,1,\dots,|\gamma|,\bot\\}$. When the stack of $\mathcal{M}$ contains the word $\beta=(\beta\_1,\beta\_2,\dots,\beta\_k)$, the stack of $\mathcal{M}'$ contains the word

$$\beta'=((\beta\_1,m\_1),(\beta\_1,m\_2),\dots,(\beta\_k,m\_k)),$$

where $m\_i=i$ if $i \le |\gamma|$ and $(\gamma\_1,\dots,\gamma\_i)=(\beta\_1,\dots,\beta\_i)$, or $m\_i=\bot$ otherwise. Also, the states $Q'$ of $\mathcal{M}'$ are given by $Q'=Q \times \\{0,1\\}$. When $\mathcal{M}$ is in state $q$, $\mathcal{M}'$ is in state $(q,1)$ if the top of $\mathcal{M}'s$ stack is of the form $(\cdot,|\gamma|)$, or in state $(q,0)$ otherwise. The accepting states of $\mathcal{M'}$ are $F'=\\{(q,1) \mid q \in F\\}$. You should be able to figure out how to adjust the transitions to ensure that $\mathcal{M}'$ behaves as described.

Then $\mathcal{M}'$ accepts exactly $L$, and is deterministic. I'll let you fill in the details of the proof.

You can generalize this to allow any $\gamma$ such that $\gamma \in R$, where $R$ is a regular language. (We modify the proof above by replacing $\\{0,1,\dots,|\gamma|,\bot\\}$ with the states of a DFA recognizing $R$.)
> 2 votes

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


title: Proving that DCONN is NL-Complete

text:
# Question
Title: Proving that DCONN is NL-Complete
I am having trouble with some homework regarding proving that DCONN is NL-Complete. As part of the exercise, the fact that RCH is NL-Complete can be assumed.

Problem definitions:

> RCH: Given a directed graph G and nodes x, y , is there a path from x to y?

> DCONN: given a directed graph G, is it connected?

To my understanding we have have to prove two things:

1. $ DCONN \leq RCH$
2. $RCH \leq DCONN$

**Reduction** $\leq $ in this case is defined as: $L$ is logspace-reducible to $L^{'}$ ($L \leq\_{log} L{'})$ iff there is a LOGSPACE function f such that: $x \in L$ iff $f(x) \in L{'}$.

To be honest I have no idea where to even start. The following is my naive attempt to tackle the first issue. For the first part I thought that running $n^2$ RCH questions to see if node $y$ is reachable from node $x$ for all $x,y \in G, x \neq y$ will be sufficient to prove that $G$ is connected or not. But I am not sure if that is sufficient to be considered a reduction.

When it comes to the second part I have no idea where to even start. Any help or pointers would be appreciated.

# Answer
Don't know if you've solved the problem but here's some of my thoughts:

For the first part, running $n^2$ $RCH$ should be a log space reduction since you only require $O(logn)$ extra space to record which pair you are currently checking.

For the second part, for each $\<G,s,t\>$ you can construct a graph $G'$ where:

* For each vertice $x\neq s$, add the edge $(x,s)$
* For each vertice $y\neq t$, add the edge $(t,y)$

Then run $DCONN$ on $\<G',s,t\>$. You can see $RCH(\<G,s,t\>)=1$ if and only if $DCONN(\<G',s,t\>)=1$. As for the reduction (the extra cost for $G'$ construction), since the vertices remain the same and the edges are at most tripled, this should also be a log space reduction. You can think of it as a polynomial change to the $DCONN$ input.
> 1 votes

# Answer
**To show that $\text{DCONN}$ is in $\text{NL}$:** you can use the fact that $RCH\in \text{NL}$ and the fact that $\text{NL} = \text{coNL}$. So we have a nondeterministic TM $T$ that decides $\overline{RCH}$ using at most logarithmic space. Now note that a directed graph $G = \langle V, E\rangle$ is not connected iff there are distinct nodes $u, v\in V$ such that there is no path from $u$ to $v$. Hence, we can decide $\overline{\text{DCONN}}$ in nondeterministic logspace by guessing two vertices $u$ and $v$, and then operate as the machine $T$ to check whether there is no path from $u$ to $v$. So we got that $\overline{\text{DCONN}}\in \text{NL}$, and as $\text{NL}=\text{coNL}$, we conclude that $\text{DCONN}\in \text{NL}$. Note that guessing and writing the vertices $u$ and $v$ takes at most logspace since we can write the address or the number that corresponds to a vertex in binary.

**To show that $\text{DCONN}$ is in $\text{NL-hard}$:** we define a logspace reduction from $\text{RHC}$ to $\text{DCONN}$: on input $\langle G, x, y\rangle$, the reduction outputs the graph $G'$ that is obtained from $G$ by adding the directed edges $(v, x)$ and $(y, v)$ for every vertex $v$ of $G$. Clearly, the reduction is correct. Indeed, if there is a path $p$ from $x$ to $y$ in $G$, the for all $u, v\in V$, $v, p, u$ is a path from $u$ to $v$ in $G'$, and thus $G'$ is connected. Conversely, if there is no path from $x$ to $y$ in $G$, then there is no path from $x$ to $y$ in $G'$ and thus $G'$ is not connected. Indeed, if by contradiction there is a path $p$ from $x$ to $y$ in $G'$, then we can assume that $p$ is simple by omitting cycles from it. Now as $p$ is simple, starts with $x$ and ends with $y$, we get that $p$ does not use any of the new added edges as these edges are directed to $x$ or directed from $y$. Hence, $p$ exists also in $G$, and we've reached a contradiction.

Also note that the reduction can be implemented using at most logspace as follows. The Turing machine $M$ the computes the reduction follows the standard 3-Tape model, thus we have an input, work, and output tape, and the space complexity is defined w.r.t work tape. $M$ operates as follows. On input $\langle G = \langle V, E\rangle, x, y\rangle$, $M$ copies $\langle G\rangle$ to its output tape without using any space at all. Then, $M$, loops over all vertices $v\in V$ and appends the edges $(v, x), (y, v)$ to the description of $G$ in its output tape. So the only space that $M$ uses is the binary address for the current vertex $v$. So in a sense, $M$ keeps track only of the number of the current vertex in its loop.
> 1 votes

---
Tags: reductions, decision-problem
---


# Question
Title: Partition an array in two groups while keeping the relative order within both groups
I came across the following problem in the book "Elements of Programming Interviews in Python".

> Given an array A of n objects with Boolean-valued keys, reorder the array so that objects that have the key false appear first. The relative ordering of objects with key $true$ should not change. Use $O(1)$ additional space and $O(n)$ times.

My question is, is there an algorithm with $O(1)$ additional space and $O(n)$ time to keep the relative ordering for element with $true$ AND $false$ keys? If so, what is the algorithm? If not, how can I prove it is not possible?

The algorithms I could think about were either $O(n^2)$ or used $O(n)$ additional space.

# Answer
Yes, there is such an algorithm. Hint:

> Scan from right to left (from the end of the array towards the front).
> 1 votes

# Answer
There is no solution for both stable, but I provide the solution for the original book problem.

$false$ stable: let $i = 0$, go through every element from left to right, and each time we see a $false$ element, swap it to index $i$, and increment $i$.

$true$ stable: let $i = n - 1$, go through every element from right to left, and each time we see a $true$ element, swap it to index $i$, and decrement $i$.
> 0 votes

# Answer
**Hint:**

$$\color{blue}1\color{blue}2\color{red}3\color{blue}4\color{red}5\color{blue}6\color{red}7\color{red}8\color{blue}9$$

$$\color{blue}1\color{blue}2\color{red}3\color{blue}4\color{red}5\color{red}8\color{red}7\color{blue}6\color{blue}9$$

$$\color{blue}1\color{blue}2\color{red}3\color{red}7\color{red}5\color{red}8\color{blue}4\color{blue}6\color{blue}9$$

$$\cdots$$
> -1 votes

---
Tags: algorithms, mergesort, ordering
---


# Question
Title: Proof that a union of two non-regular languages may be regular
Let $L\_1 = \\{ a^{n}b^{m} \mid n \> m \> 0 \\} $. Describe a non-regular language $L\_2$ such that $L\_3 = L\_1 \cup L\_2$ is regular and $L\_3 ≠ A^{\*}$ (where $A = \\{ a, b \\} $)

From the trace, I cannot prove this with the simple language of $L= \\{ a^{n}b^{m} \mid n,m \> 0 \\} $ since it must be different from $A^{\*}$.

I had thought of $L\_2 = \\{ a^{n}b^{m} \mid n ≤ m \\} \setminus \\{ aab \\} $, so in this way we do not consider a string of $L\_1$ and the union is different from $A^{\*}$

# Answer
Let $L\_2 = A^\* \setminus (L\_1\cup \\{\varepsilon\\})$. Then $L\_1 \cup L\_2 = A^\*\setminus \\{\varepsilon\\}$ which is regular and not equal to $A^\*$.
> 6 votes

# Answer
Nowhere does the question state that the intersection of $L1$ and $L2$ must be empty.

Also for L1 to contain the empty string it must be that $m = n =0$ in the description, however $m,n \>0$, therefore $L1$ doesn't contain the empty string.

The obvious solution is for $L3 = \\{ a^\*b^\* \\}$ (using kleene star) And then figuring out which non-regular language is a superset of $L3\setminus L1$.

Though technically saying $L2 = \\{ a^\*b^\* \\} \setminus L1$ is a sufficient solution assuming they can prove that it is non-regular (which you can do using the fact that intersection, complement and union operations are closed under regular languages). But it's simpler to simply take the $\\{ a^{n}b^{m} | n \<= m\\}$ because that fills in all missing pairs of n and m that are missing from $L1$.
> 5 votes

# Answer
If you don't want $L\_2$ to be the complement of $L\_1$ (as then $L\_3$ would the set of all words), then you can simply choose $L\_2$ to be $\overline{L\_1}\setminus L$, where $L$ is a nonempty finite language that is contained in $\overline{L\_1}$.

Correctness follows from standard closure properties of regular languages, and from the fact that every finite language is regular. So you get in total that $$(\overline{L\_1}\setminus L) \cup L = \overline{L\_1}$$ Hence, since $L\in \text{REG}$ and $\overline{L\_1}\notin \text{REG}$, we get from regular languages being closed under union that $\overline{L\_1}\setminus L\notin \text{REG}$. Then, the union $(\overline{L\_1}\setminus L) \cup L\_1 = A^\* \setminus L = \overline{L}$ is regular.

**Note:** In any problem where you are asked to come up with a regular or a non-regular language, then adding or subtracting a finite language from the answer won't change it as regular languages are closed under complementation, intersection (and hence difference -- think why) and union. This is useful in particular for this annoying edge cases where you get a correct answer up to a finite number of words.
> 3 votes

---
Tags: regular-languages
---


# Question
Title: Has there been a processor architecture that included commands that move arrays of data in the memory with one opcode?
In traditional processors one move operation can at most move one word between memory locations and optionally increment or decrement the registers which point to those memory locations. In x86 architecture it is realized with `movs` operation, in PDP-11 as `mov` with auto-increment or auto-decrement addressing.

But I wonder whether there is any architecture that has an opcode for moving the entire memory area, like "mov *source, destination, length*"?

It seems to me that having such opcode in the architecture would allow to reduce load on the CPU by relegating array move job to the low-level circuits, maybe, memory controller. This increases parallelism and improves performance since the memory controller is located closer to the physical memory.

After encountering such opcode the CPU would send message to the memory controller and continue with further commands after this one. Once the moving job is done, the memory controller may set or clear certain bit of processor flags register so that the program to know that the memory move task is done or would trigger an interrupt.

Has this idea been ever realized? If not, why?

# Answer
> 1 votes
X86 does the actual move with one op code. A highly complex instruction that sets the source and destination address and the number of bytes would be unnecessary. Specifying registers with these three items is complicated enough.

Now your comments indicate that you want an asynchronous instruction. If I want an asynchronous memcpy then I call memcpy to run in a background thread. And if I want more I can call 8 memcpy’s to run on 8 background threads, and any processor does that without any complicated hardware changes.

---
Tags: computer-architecture, cpu
---


# Question
Title: Analysis of QuickSort Expected Time Complexity: Without Counting the Number of Comparisons
While reading *CLRS (4th ed.)* regarding the analysis of the expected time for QuickSort, I encountered an alternative approach. The analysis involves the following steps:

1. Given an array of size $n$, the probability of choosing any particular element as a pivot is $1/n$. To formalize this, an indicator random variable $X\_i$ is introduced, defined as $X\_i = I\\{i\text{-th smallest element is chosen as the pivot}\\}$. It is evident that the expected value of $X\_i$, denoted as $\mathbb{E}\[X\_i\]$, is equal to the probability of $X\_i$ being $1$, which is $\frac{1}{n}$.
2. Let $T(n)$ be a random variable representing the running time of QuickSort on an array of size $n$. The expected running time, denoted as $\mathbb{E}\[T(n)\]$, is expressed as:

$$\mathbb{E}\[T(n)\] = \mathbb{E}\left\[\sum\_{q=1}^{n}{X\_q (T(q-1) + T(n-q) + Θ(n))}\right\]$$

This part is clear and understandable.

3. The goal is to demonstrate that: $$\mathbb{E}\[T(n)\] = Θ(n) + \frac{2}{n}\sum\_{q=1}^{n-1}{\mathbb{E}\[T(q)\]}.$$

In proving part 3, encountering challenges arises. Attempting to use the linearity property of expectation faces an obstacle due to the presence of multiplication, as seen in $\mathbb{E}\[X\_q T(q-1)\]$. Unlike independent variables, these cannot be expressed as the product of their individual expectations ($\mathbb{E}\[X\_q\]\mathbb{E}\[T(q-1)\]$), since the choice of the pivot element affects the algorithm's running time.

To address this issue and prove the statement, a different strategy or method needs to be employed.

# Answer
> 3 votes
This exercise is indeed wrong as written, I don't think there is any reasonable probability space on which variables $T(k)$ for all $k$ can be defined in such a way that it works.

But the idea can be made to work. The Quicksort algorithm consists of 4 steps:

* Random choice of a pivot
* Partition
* Sorting the left part
* Sorting the right part

Let $T\_n$ be the random variable representing the runtime of Quicksort on an array of length $n$ with distinct elements, and $P\_n$, $L\_n$, $R\_n$ are runtimes for partition, left sort and right sort respectively. Let $A\_i$ be the event "the $i$-th smallest element is chosen as a pivot". The main idea is that if the $i$-th element is chosen as a pivot, then the left sort works exactly as quicksort on $i-1$ elements, and the right sort - as quicksort on $n-i$ elements. This means that the *conditional* distribution $\mathbb{P}(L\_n = t|A\_i)$ coincides with the distribution $\mathbb{P}(T\_{i - 1}=t)$, and the same for the right: $\mathbb{P}(R\_n = t|A\_i) = \mathbb{P}(T\_{n-i}=t)$. In particular, the conditional expectations are $\mathbb{E}(L\_n|A\_i) = \mathbb{E}T\_{i - 1}$, $\mathbb{E}(R\_n|A\_i) = \mathbb{E}T\_{n - i}$. This means that $$\mathbb{E}(P\_n + L\_n + R\_n|A\_i) = \Theta(n) + \mathbb{E}T\_{i - 1} + \mathbb{E}T\_{n - i},$$ and from the total expectation law we obtain $$\mathbb{E}(T\_n) = \mathbb{E}(P\_n+L\_n+R\_n) = \sum\_{i = 1}^n \mathbb{E}(P\_n+L\_n+R\_n|A\_i) \mathbb{P}(A\_i) =$$$$= \Theta(n) + \frac1n\sum\_{i=1}^n (\mathbb{E}T\_{i - 1} + \mathbb{E}T\_{n - i})$$

# Answer
> 0 votes
Let's start with the equation you wrote in part 2:

$\begin{aligned} E\[T(n)\] & =E\left\[\sum\_{q=1}^{n} X\_q(T(q-1)+T(n-q)+\Theta(n))\right\] \\ & =\sum\_{q=1}^{n} E\left\[X\_q(T(q-1)+T(n-q)+\Theta(n))\right\] \end{aligned}$

by linearity of the expectation. Now, since $X\_q$ is independent from other random choices in the recursive calls (note that there are no functional dependencies between the choice of the pivot in one recursive call and in the next recursive calls: the pivot is always chosen in the same random way in each recursive call, without taking into account how a pivot has been chosen in previous recursive calls; moreover, the pivot is selected with the same probability in each recursive call, owing to the fact that the elements are assumed to be distinct):

$E\[T(n)\] =\sum\_{q=1}^{n} E\left\[X\_q\right\] \cdot E\[T(q-1)+T(n-q)+\Theta(n)\]$

and, reusing again linearity of expectation and the fact that $E\[X\_q\] = 1/n$ (this is because we are assuming the $n$ elements are all distinct, so that the expectation is equal to the probability of $X\_q$ of being equal to 1):

$E\[T(n)\] =\frac{1}{n} \sum\_{q=1}^{n} E\[T(q-1)\]+\frac{1}{n} \sum\_{q=1}^{n} E\[T(n-q)\]+\frac{1}{n} \sum\_{q=1}^{n} \Theta(n)$

Now, note that the first two summations have identical terms, obtained varying $q$ form 1 to $n$, so that we can conclude

$E\[T(n)\] =\frac{2}{n} \sum\_{q=1}^{n} E\[T(q)\]+\Theta(n)$

Starting from this equation it is possible to prove that

$E\[T(n)\] \leq c n \lg n$ for a positive constant $c \> 0$.

---
Tags: time-complexity, probability-theory, randomized-algorithms, quicksort
---