# Question
Title: Clarifiaction on the NP-hardness of k-SUM-variants
I am currently looking into the $k$-Sum Problem and some of its variants. However i stumbled onto an inconsistency, that i can not seem to fix.

If we begin with $3$-Sum, the 'textbook'-definition goes something along the way of

> Let a set $S$ of $n$ integers be given. Are there $a,b,c\in S$ such that $a+b+c=0$.

From this definition however it is not immediatly clear, whether $a,b$ and $c$ have to be distinct. Compare this to this paper. In the Introduction they state

> The $k$-SUM problem is the parameterized version of the well known NP-complete problem SUBSET-SUM,and it asks if in a set of $n$ integers, there is a subset of size $k$ whose integers sum to $0$.

This seems to imply, that duplicates are not allowed, as sets usually dont permit duplicates. However in Section 2.2 of the same paper they reduce $k$-SUM to $k$-Table-SUM and link to Section 3.1 of this paper, where the reduction only works in the case, where duplicates *are* allowed.

Are these two variants equivalent? If so, are there possibly any sources on this? And furthermore, is $k$-Table-SUM NP-hard? Intuition and "closeness" to the $k$-SUM would suggest this, but i haven't found a proof for this apart from the linked sources with the noted inconsistencies.

Thanks!

Edit:

I finally found two sources that can answer this properly. The first contains a reduction from 'Perfect Code' to $k$-SUM without duplicates, however the k-SUM instance is constructed in a way, that allowing duplicates wouldn't find any other solution here (specifically at 22.5.3). In case anyone is not familiar with perfect code, at 22.2.1 the authors reduce Indepenent Set to Perfect Code.

The second source actually links to the first. They reduce $3$-SAT to $k$-SUM in Theorem 5.1. Note that the proof specifically states, that they seperate the instance into d blocks, and then make sure that $k$-SUM only finds one entry per block. This is exactly the same as $k$-Table-SUM and also easily reduced to $k$-SUM with duplicates, similar to the accepted answer.

# Answer
Yes in case of 3-sum problem they are equivalent. Let $P$ be the version where the three numbers have to be distinct and $P'$ the version where you can use the same number multiple times. The reduction $P'$ to $P$ is by solving the cases with overlapping in preprocessing (since both overlapping cases can be done in almost linear time).

The other direction is a bit more complicated. We will reduce $P$ to another variant $P''$ and from $P''$ to $P$. We start by defining $P''$: given three sets of integers $A,B,C$. Can we pick a number from each to sum to zero.

$P''$ to $P'$ is quite easy. Let $M$ be the largest number in all sets. Let $U := 3M + 1$ build the set $$S := \\{a+U:a\in A\\} \cup \\{b + 2U: b\in B\\} \cup \\{c-3U:c\in C\\}$$ as input to $P''$. Try to prove why the reduction is correct as an exercise.

Now the last reduction from $P$ to $P''$ is a bit more complicated. It is actually randomized. Fix a correct tripple in $S$. A random partition of $S := A\dot\cup B \dot \cup C$, we will have the numbers in the triple assigned to distinct sets with probability at least $2/3 \cdot 1/3 = 2/9$. By repeating a constant factor of $\log n$ you get a running time of $O(n\log n)$ reduction with high probability.
> 1 votes

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


title: Expected number of coins

text:
# Question
Title: Expected number of coins
Alice and bob play a game. Bob has a well-shuffled deck of $M=4999$ white cards and $N=4999$ green cards. Each permutation of cards in the deck is equally likely. Alice has set some rules for Bob.

* Every time Bob flips a white card he gets one coin, otherwise he loses one coin. At any moment (even at the beginning), Bob is allowed to stop playing the game and keep the number of coins that he has.
* During the game-play the balance of coins that Bob has may be negative.

If Bob plays optimally, what the expected amount of coins Bob will have?

Can any body give me an idea or a hint how to solve it.

# Answer
> 1 votes
Let $w(a,b)$ be the expected profit with $a$ positive cards and $b$ negative cards. Then $w(0,0) = 0$ and $$ w(a,b) = \max\bigl(0, \tfrac{a}{a+b} (w(a-1,b) + 1) + \tfrac{b}{a+b} (w(a,b-1) - 1)\bigr). $$ Indeed, if we stop the game immediately, the profit is zero. Otherwise, with probability $\tfrac{a}{a+b}$, we pull out a positive card, and with probability $\tfrac{b}{a+b}$, we pull out a negative card.

Using this recurrence, it is easy to compute $w(4999,4999)$. On my laptop it took less than a second.

---
Tags: algorithms, dynamic-programming, probability-theory, game-theory
---


# Question
Title: Why can't OSes swap out processes that are waiting for I/O?
In the book, *Operating System Concepts, 9th Edition*, there is this paragraph that I don't quite wrap my head around.

> Swapping is constrained by other factors as well. If we want to swap a process, we must be sure that it is completely idle. Of particular concern is any pending I/O. A process may be waiting for an I/O operation when we want to swap that process to free up memory. However, if the I/O is asynchronously accessing the user memory for I/O buffers, then the process cannot be swapped. Assume that the I/O operation is queued because the device is busy. If we were to swap out process P1 and swap in process P2, the I/O operation might then attempt to use memory that now belongs to process P2. There are two main solutions to this problem: never swap a process with pending I/O, or execute I/O operations only into operating-system buffers. Transfers between operating-system buffers and process memory then occur only when the process is swapped in. Note that this **double buffering** itself adds overhead. We now need to copy the data again, from kernel memory to user memory, before the user process can access it.

This is quite a handful for me to swallow for now. I have a lot of questions.

* What are I/O buffers? Are they located in the I/O device?
* How and why does the I/O asynchronously access user memory?
* Why would an I/O operation attempt to use P2 memory when P1 gets swapped with P2?

To probably generalize my questions, why shouldn't we swap processes with pending I/O? If we do so, would there be memory corruption or segmentation faults?

# Answer
One scenario that can explain this more obviously is as follow: Suppose that a process wanted to read a disk block to a buffer in its address space (An I/O buffer is just a portion of the processe's memory. eg. `char[1024]`). The process will make a system call to ask the OS to issue an I/O to read the corresponding disk block into that buffer in the memory of the process and then the process sleeps waiting for this I/O operation to complete (Because it may take some time before the operation is completed by the device and at that time we can schedule another process for execution instead of letting the CPU idle). Now, to execute that I/O, the OS will probably program some kind of DMA (Direct Memory Access) device to automatically copy the data from the disk controller to the the buffer in the memory of the process without having to interrupt the CPU (Hence, the name direct access to memory). Now, if it happens that the process is swapped out, its physical memory will be freed (the memory where the buffer that receives the disk block content from the DMA is situated) and it will probably be allocated for another process. Which means that, when the DMA starts to copy the disk block content to the initially provided memory buffer (Initial buffer that was later freed and given to another process while the disk block was being read), that content is not actually being copied to the sleeping process's memory but some other process memory. And that's why the OS should not swap a process waiting for I/O. Otherwise, don't program the DMA to copy the disk content directly to the process's memory buffer but instead copy everything into some kernel buffer (Kernel memory) and then copy that content into the process memory again once it's ready (Swapped in) but this is a double duty and may incur some overhead.

Hence:- So we can say that resources generated after the i/o processing for the original requesting process might be swapped with some other process, due to swapping of memory spaces between the processes.
> 4 votes

# Answer
Your OS book seems to be a bit of an antique.

Here’s where you need to be careful: You can’t remove the _ address space\_ for an application. But with a 64 bit OS, you have tons of address space at practically no cost. And you need active I/O buffers to stay in memory where you are, which is also no problem whatsoever.
> 0 votes

---
Tags: operating-systems, memory-management
---


# Question
Title: Finding C-convex holes in a planar point set
I am looking for an efficient algorithm to find convex holes in a given point set. The problem is

> Given $n$ points in the Euclidan plane, and a constant $c$, determine how many empty convex polygons $P\_1, \dots, P\_k$ there are, such that for each $i = 1,\dots,k$; $P\_i$ has exactly $c$ vertices from the given point set.

Although there are some papers that considers finding possibly non convex holes \[1\] \[2\] \[3\], and some others that show existence of such holes \[4\] \[5\], I could not find a paper that describes an algorithm to find them.

Obviously, a naive algorithm that runs in $\mathcal{O}(n^c)$ comes to mind, where each $c$-subset is traversed. However, I would like to know whether there exists a more efficient algorithm.

# Answer
> 2 votes
In "Counting Convex Polygons in Planar Point Sets" (link) Mitchell et al. show an algorithm which can do this in time $O(cn^3)$.

Note however that if you need to report those polygons then you can't do better than $O(n^c)$ as there might be $\Omega(n^c)$ such polygons to begin with (consider for example $n$ points in convex position).

---
Tags: algorithms, reference-request, computational-geometry
---


# Question
Title: How to sort objects based only on "less than" relationships?
Say I have n objects, each with an unknown value, and a n by n matrix Z. Such that Z(i,j)=1 if the value of object i is less than the value of object j, and Z(i,j)=0 otherwise. How can I sort these n objects, given only the matrix Z?

# Answer
What you are looking for is a comparison sort. Please take a look at that article.

---

Let us state clearly the requirement for any two given objects, object i and object j when they appear in the final sorted list. Object i should occur before object j if Z(i, j) = 1. Object i can occur before or after object j if Z(i, j) = Z(j, i) = 0.

As vonbrand mentioned, we should assume that the matrix Z specifies a well-defined "less than" relation or, in terms of math, a total strict-order on the values of the objects. Otherwise, the given objects may not be sorted.

* Z\[i, j\] = 0 if Z\[j, i\] = 1. Otherwise, we cannot sort object i and object j.
* Z\[j, i\] = 0 if Z\[i, k\] = 1 and Z\[k, j\] = 1 for some k. Otherwise, we cannot sort object i, j and k (think of paper-scissors-rock).

---

Assume that Z specifies a well-defined "less than" relation. Then it also defines a "$\le$" comparison operation naturally. Namely, if Z(j, i) = 0, then object i $\le$ object j. So we can apply any comparison sort to sort the given $n$ object.

Almost all sorting algorithms are comparison sorts. For example, quicksort, mergesort, insertion sort, selection sort and bubble sort. A notable exception is counting sort.
> 2 votes

---
Tags: algorithms, sorting, ordering
---


# Question
Title: Is there such a notion as "effectively computable reductions" or would this be not useful
Most reductions for NP-hardness proofs I encountered are effective in the sense that given an instance of our hard problem, they give a polynomial time algorithm for our problem under question by using reductions. All reductions in the 21 classic problems considered by R. Karp work this way. A very simple example might be reduction from INDEPENDENT\_SET to CLIQUE, just built the complement graph of your input.

But when considering the proof of the famous Cook-Levin Theorem that SAT is NP-complete, the reduction starts from a non-deterministic TM and some polynomial, that exists by definition. But to me it is not clear how to get this polynomial effectively, meaning given an non-deterministic TM from which I know it runs in polynomial time, it is not clear how to compute this polynomial, and I highly suspect it is not computable at all.

So soley from the encoding of NP-complete problems by the class of non-deterministic polynomial time TMs (the polynomial itself is not encoded as far as I know) I see no way how to give a reduction in an effective way, the aforementioned proof just shows that there exists some, but not how to get it.

Maybe I have understood something wrong, but I have the impression that usually the reductions given are stronger in the sense that they are indeed computable, i.e. given a problem we can compute our reduction, and not merely know its existence.

Has this ever been noted? And if so, is there such a notion as "effectively computable reduction", or would it be impractical to restrict reductions to be itself computable? For me, from a more practical perspective, and also the way I sometimes see reductions introduced ("like we have an algorithm to convert one instance to another") it would be highly desirable to know how to get this algorithm/reduction, so actually it seems more natural to demand it, but why is it not done?

# Answer
Nice question! I think that your notion of an "effectively computable reduction" is interesting and worth studying, but not as fundamental as standard reductions. Let me provide some observations about this notion that may be illuminating:

### Observation 1: it does not make sense to talk about effectively computable reductions from one language to another; only from a family of languages to another.

In particular, you seem to be mixed up when you write this:

> Most reductions for NP-hardness proofs I encountered are effective in the sense that given an instance of our hard problem, they give a polynomial time algorithm for our problem under question by using reductions. All reductions in the 21 classic problems considered by R. Karp work this way.

A reduction from, say, VertexCover to 3SAT is a Turing machine $f$ that transforms instances of VertexCover into instances of 3SAT. Since it is a Turing machine, it is effectively computable by definition. So it is not surprising that all reductions you have seen of this form are effectively computable.

In other words, if we just look at reductions from one language to another, then every reduction is effectively computable!

This is different from the case of the Cook-Levin theorem, where we have to show a reduction $f$ from an arbitrary NP language to SAT. Then it might make sense to consider whether this reduction -- parameterized by the language in NP -- is effective or not. But that brings us to my second point:

### Observation 2: What counts as an *effectively computable reduction* depends on the representation of languages.

This is important because standard reductions (either many-to-one reductions or Turing reductions) do not depend on the way the language is represented. For a reduction from $L$ to $L'$, I consider $L$ and $L'$ to be subsets of $\\{0, 1\\}^\*$. But for your notion of effectively computable to make sense, we need to have access to a *representation* of $L$ (we probably don't need a representation of $L'$).

To make this point clearer, consider the reduction in the proof of the Cook-Levin theorem, which you brought up. The proof considers a language $L$, *represented by* a polynomial-time nondeterministic Turing machine $N$. Then it shows that $L$ is reducible to SAT. You say that this reduction is not effectively computable, but that depends on how $N$ is represented, i.e., the definition of a polynomial-time nondeterminstic Turing machine $N$:

* **Definition 1:** A polynomial-time NTM is a nondeterministic Turing machine such that there exists a polynomial $p(n)$, such that the TM always halts in time at most $p(n)$.
* **Definition 2:** A polynomial-time NTM consists of a nondeterministic Turing machine, together with a polynomial $p(n)$. The way it runs is that, on any branch, it is only executed for $p(n)$ steps; if it does not halt in this time, then that branch is ignored.

It may seem that I am making Definition 2 up and that the definition is not natural, but actually both of these are perfectly valid definitions of a polynomial-time NTM that both have their merits. And for the classical theory of P, NP, and NP-completeness, both of these definitions are equivalent. The nice thing about Definition 2 is that an NTM is allowed to diverge on certain branches; you don't worry about that because the execution semantics says that we just forget about it once the running time goes above $p(n)$.

However, the definitions become inequivalent when it comes to effectively computable reductions. Note that, according to Definition 1, when we are given a language defined by an NTM $N$, we have no idea what its running time is, so we may not be able to reduce it to SAT (more on this below). But according to Definition 2, part of the NTM $N$ is that it comes with a polynomial, and so we know its running time. Therefore, we can effectively reduce all NP languages to SAT if we are using Definition 2.

Also, we have only considered nondeterministic Turing machines; we could equivalently define NP using verifier Turing machines. Then the definition of an effectively computable reduction could be something else!

**TL;DR:** Depending on how a language in NP is represented, and in particular depending on the definition of a polynomial-time NTM, it may be either true or false that every language in NP is effectively reducible to SAT. In other words, The set of effectively computable reductions changes depending on the model of computation used to represent languages in NP.

---

Now at this point, given points (1) and (2), a question still remains: can the reduction in the Cook-Levin theorem be made to be effective? In particular, suppose we fix the following definitions:

* Languages in NP are represented by nondeterministic Turing machines whose runtime is bounded by an unknown polynomial $p$ (i.e. Definition 1).
* Given a language $L$, we say that the class of languages NP is *effectively poly-time reducible* to $L$ if the following holds: there is a TM $f$ that takes as input $\langle N, w \rangle$, where $N$ is a polynomial-time NTM and $w$ is any input to $N$, such that $w \in L(N)$ if and only if $f(\langle N, w \rangle) \in L$. Also, $f$ must run in polynomial time (in its input $\langle N, w \rangle$).

In other words, to address point (1), we are assuming that languages in NP are represented by nondeterministic Turing machines *without* an explicit polynomial bound. And to address point (2), in our definition of effectively reducible, we are talking about a reduction from a *class of languages*, in this case NP, to a single language. Now we have the following observation:

### Observation 3: (Cook-Levin is not effective) The class NP is NOT effectively reducible to SAT.

Let us see why this is true. Assume towards a contradiction that an effective reduction $f$ exists. The idea is that we will try to solve a difficult (say, doubly-exponential-time) problem by taking its instance, turning it into a polynomial-time NTM, and asking $f$ to reduce it to SAT. So, let $L\_{hard}$ be some problem that requires doubly-exponential time to solve (this exists by the Time Hierarchy theorem), and let $M\_{hard}$ be a (deterministic) TM that solves it. Given any instance $w$ of the problem, define the following NTM $N\_w$: \begin{align\*} N\_w := &\text{"On any input $a$, first run } M\_{hard} \\ &\text{on input } w \text{. When it halts, accept if} \\ &\text{it accepts and reject if it rejects."} \end{align\*}

Now we can use this to solve $L\_{hard}$ in exponential time (not double exponential), as follows. On input $w$, we first construct $N\_w$, which has size only a constant more than $w$. Then we pass $\langle N\_w, \epsilon \rangle$ (the second argument, $\epsilon$, is just a placeholder here) to $f$ to reduce it to SAT. $f$ gives us back an instance of SAT that is at most polynomial size in $N\_w$, and $f$ takes only polynomial time to run. So we end up with an instance of SAT of polynomial size in $w$; now we solve it in exponential time in $w$ using brute-force search.

---

This point (3) seems to suggest that most of the time, no interesting class of languages will be reducible in this effectively computable sense to a single language. It will just be too hard, because you can exploit this computability to then solve hard problems by encoding them as part of a TM input to the effective reduction. However, something is a bit fishy here, because if we feed the TMs $N\_w$ into the Cook-Levin theorem reduction, we would end up with very large SAT formulas, exponential in $w$. So perhaps our definition needs to be tweaked so that $f$ runs in time polynomial in the *running time of* $N\_w$, not just polynomial in the input $\langle N\_w, \epsilon \rangle$.

### Observation 4: If we allow Turing (many to many) reductions, then Cook-Levin can be made effective.

As D.W. says in a comment:

> I think one can construct an effective Cook reduction, by iterative doubling. Does that help?

I also believe this is true. In particular, we can change our definition of an "effective reduction" from NP to a language $L$ by saying that the reduction does not just return an instance of $L$, but returns many instances of $L$ in sequence, and uses an oracle for $L$ to solve the original problem. Then to solve a general problem in NP, you could try larger and larger polynomials $p$ until you get the right one which bounds the running time. You can detect whether a particular polynomial bounds the running time on all branches of the NTM by a separate reduction to SAT.

### Disclaimer

I am not an expert in this topic. These are just some preliminary notes on the idea, and I am not sure if someone has studied this in the literature.

P.S. Although it may not be directly related, your question about considering effective reductions reminds me of an idea I had, about considering not just whether languages are in P or in NP, but whether they are *provably so.* This is related to the idea of developing a complexity theory that is effective or constructive. I asked and later answered question about defining provably P and provably NP languages here.
> 6 votes

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


# Question
Title: Are weakly polynomial time algorithms truly polynomial?
I've been looking through a ton of sources to try and understand the definitions of strongly and weakly polynomial time algorithms. Wikipedia states an algorithm runs in strongly polynomial time if

> 1. the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input instance; and
> 2. the space used by the algorithm is bounded by a polynomial in the size of the input.

A weakly polynomial time algorithm is then just an "algorithm that runs in polynomial time but that is not strongly polynomial."

What I'm confused about is how weakly polynomial time algorithms can actually be said to be polynomial. As stated in this post in reference to weakly polynomial time algorithms,

> The algorithm is already polynomial time in the arithmetic model, so as long as its space is bounded in the TM model then the rest of the algorithm is still polynomial time in the TM model. Think of it like this, when converting from the arithmetic model to the TM model, the only thing that can go wrong is the space. The numbers you produce need to be representable in a number of bits that is polynomial in the number of bits in the input. So long as that holds, the rest of the algorithm is still polynomial time in the TM model.

I understand the difference between the arithmetic model and the TM model. But this quote and the wikipedia definition itself seem to imply that ***a weakly polynomial time algorithm will not run in polynomial time on a TM.*** This being because (to my understanding) if the space being used isn't bound by a polynomial in the size of the input, just the time spent allocating the space necessary to run the algorithm on a TM eliminates any hope of polynomial time. The classic example is in the post I linked above and the Wikipedia article and involves calculating $2^{2^n}$ given $2^n$.

***So how can we say weakly polynomial algorithms are still polynomial?*** There seems to be a consensus that weakly polynomial is better than pseudo-polynomial, but aren't they both not polynomial on a TM?

**Edit:** I would also like to add that confusingly this post states that

> Consider running either one on a Turing Machine. Both will run in a number of steps polynomial in the length of binary-encoded input.

This seems to contradict the previous post I linked which states

> Any strongly-polynomial time algorithm can be converted into a polynomial time algorithm on a TM by replacing the arithmetic operations with equivalent algorithms in the TM model.

suggesting that the difference is weakly polynomial time algorithms don't run in polynomial time on a TM. Either I'm missing something fundamental or multiple definitions seem to be floating around.

# Answer
As Wikipedia says, there are two conditions for strongly polynomial time algorithms:

> 1. the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input instance; and
> 2. the space used by the algorithm is bounded by a polynomial in the size of the input.

I will simply call these two conditions as condition 1 and condition 2 in this answer.

---

> The algorithm is already polynomial time in the arithmetic model, so as long as its space is bounded in the TM model then the rest of the algorithm is still polynomial time in the TM model. Think of it like this, when converting from the arithmetic model to the TM model, the only thing that can go wrong is the space. The numbers you produce need to be representable in a number of bits that is polynomial in the number of bits in the input. So long as that holds, the rest of the algorithm is still polynomial time in the TM model.

This paragraphs is describing why condition 2 is necessary for strongly polynomial time algorithm, it is not stating the difference between strongly and weakly polynomial time algorithms. In fact, condition 2 is also necessary for weakly polynomial time algorithm, and the example algorithm that computes $2^{2^n}$ given $2^n$ is NOT weakly polynomial (and is even not a polynomial time algorithm).

In fact, it is condition 1 that describes the difference between strongly and weakly polynomial time algorithms. Note the definition of strongly polynomial time algorithms is equivalent to

> * condition 1; and
> * the algorithm is a polynomial time algorithm (in the TM model)

While the definition of weakly polynomial time algorithms is equivalent to

> * condition 1 is not satisfied; and
> * the algorithm is a polynomial time algorithm (in the TM model)

It is more clear to see the difference between strongly and weakly polynomial time algorithms with these two redefinitions.

---

This post is wrong to suggest the difference is weakly polynomial time algorithms don't run in polynomial time on a TM. I have added a comment on that post addressing this issue.
> 6 votes

---
Tags: algorithms, complexity-theory, turing-machines, computation-models
---


# Question
Title: determine if a turing machine halts in less than n step, in less than n step
I would like to know if there is a turing machine which can do the following:

take as input a turing machine T and integer n:
return true if the turing machine halts before time n and false otherwise

Clearly such a TM (turning machine) exists. Take the TM that simply runs T for n steps, then if it has halted return true and return false otherwise, however what I would like to know is if there exists a TM that can do better than this. I'm not sure how to formalize this question exactly. so hopefully it is clear what I am asking. Thanks

# Answer
> 3 votes
Maybe the Turing Machine Linear Speed Up Theorem will answer your doubt (https://en.wikipedia.org/wiki/Linear\_speedup\_theorem)

Counter-intuitively or maybe intuitively, this states that given a Turing Machine which does something in say $n$ steps there are Turing Machines which can solve the same problem in $n/k$ steps for any constant $k$ independent of $n$. These Turing Machines would basically run $k$ steps of the original TM as $1$ step, hence having more state space, but linearly faster.

Was this your question?

---
Tags: turing-machines
---


# Question
Title: Is there a physical analogy to the Turing Machine?
Recently in my CS class I've been introduced to the Turing Machine.

After the class, I spent over 2 hours trying to figure out what is the relationship between a tape and a machine.

I was completely unaware of the existence of computer tapes or how tapes and machines interacted until today. I still can't see why a machine would read tapes but a scanner is perhaps a closer conception to the Turing machine where paper is considered a tape and whatever goes inside of a scanner is whatever a Turing machine would do.

But in any case, isn't the idea of a Turing machine quite archaic? We have so many physical (rather than hypothetical) devices in our office or living room that seems to do what the Turing Machine does.

Can someone provide a better example drawing from reality so that the essential functionalities of this hypothetical conception is captured?

# Answer
Turing machines are one of the "original" Turing-complete computation models, along with the $\lambda$ calculus and the recursively defined recursive functions. Nowadays in many areas of theoretical computer science a different model is used, the RAM machine, which is much closer to actual computers. Since both models are p-equivalent (they simulate each other with at most polynomial blow-up), from the point of view of questions like P vs. NP, both models are equivalent.
> 25 votes

# Answer
AFAIK the Turing Machine is modeled on the idea of a human with a pen and paper. The human has a certain state in the brain, looks at the paper like the machine looks at the tape, and writes something on the paper or moves to look at a different place, just as the machine does.

TM is archaic as Peano natural number arithmetic. TM is useless for practical computation, and it is of course not intended to be used for that. It is just a simple way to axiomatize computation so we can reason about what's computable and what isn't - just as Peano arithmetic is useful for defining from first principles what natural numbers are, and what are their properties - but it would be ridiculous to try to do arithmetic by manipulating Peano numbers by hand according to the theoretical definitions.

Just think how difficult it would be to prove different theorems from complexity and computability theory (e.g. prove that the Halting Problem is undecidable), if you had to prove them using the semantics of the C++ programming language instead of the Turing Machine. Your proofs would be ridiculous or impossible - as ridiculous as proving associativity of natural number multiplication by using the grade-school method applied to decimal integers as your definition of what multiplication is.
> 42 votes

# Answer
Imagine a newcomer to geometry asking:

***Is there a physical analogy to the triangle?***

***Isn't the idea of a triangle quite archaic? We have so many physical (rather than hypothetical) shapes in our office or living room that seem to do what the triangle does.***

What would you answer?

You might say that these questions reveal two fundamental misconceptions about triangles:

1. *"Triangles are purely hypothetical."* Wrong! While they are mathematical entities, Platonic ideals, and hypothetical in that sense, *triangles are real*: we can actually construct them in the real world. Granted, what we construct will never be a perfect triangle, but our mathematical theory about them does apply to the real world, the laws we can derive do apply to shapes in the real world, the theory can be used as a basis for designing, constructing and measuring shapes in the real world; this is the reason the theory was developed in the first place.
2. *"Triangles are useless because they don't describe the shapes we normally use."* Wrong! Describing actual shapes you find in the real world is not their purpose. If your whole office or living room doesn't contain a single triangle, that doesn't mean the concept of triangle is unrealistic or outdated and had better be replaced with something else. Their main purpose is as an elementary construct from which all more complex shapes can be constructed in principle - and for which we can therefore derive laws that apply to shapes in general. Reasoning about triangles allows us to reason about shapes in general. Your living room is subject to the same laws that we have derived for triangles, and our knowledge of these laws was used, directly or indirectly, to construct it. The living room probably doesn't have a single triangle in it, let alone a perfect one, but we don't care about finding triangles there; we can, however, build a description of the shapes in there by approximating them with triangles, and this - triangulation - is a popular and useful thing to do. So triangles are building blocks to help us think about shapes in general.

The same is true for Turing machines.

It's been so long since I was introduced to geometry, I really can't recall whether any newcomer actually has these misconceptions about triangles. But when it comes to Turing machines, I encounter these misconceptions *all the time*. So often, in fact, that there seems to be something fundamentally wrong with how they are usually taught. Perhaps a *show and tell* approach is in order!

So, for the sake of completeness:

1. *"Turing Machines are purely hypothetical."* Wrong! While they are mathematical entities, Platonic ideals, and hypothetical in that sense, *Turing Machines are real*: we can actually construct them in the real world. Granted, what we construct will never be a perfect Turing Machine, but our mathematical theory about them does apply to the real world, the laws we can derive do apply to computation devices in the real world, the theory can be used as a basis for designing, constructing and measuring computation devices in the real world; this is the reason the theory was developed in the first place.
2. *"Turing Machines are useless because they don't describe the computing devices we normally use."* Wrong! Describing actual computation devices you find in the real world is not their purpose. If your whole back office or home entertainment studio doesn't contain a single Turing Machine, that doesn't mean the concept of Turing Machine is unrealistic or outdated and had better be replaced with something else. Their main purpose is as an elementary construct from which all more complex computation devices can be constructed in principle - and for which we can therefore derive laws that apply to computation devices in general. Reasoning about Turing Machines allows us to reason about computation devices in general. Your computer hardware and software are subject to the same laws that we have derived for Turing Machines, and our knowledge of these laws was used, directly or indirectly, to construct them - even though they probably don't have a single Turing Machine in them. It's the laws we're interested in.
> 10 votes

# Answer
Many very different Turing complete computation model are physically realizable (up to considering infinity as standing for unboundedness). Thus that cannot the point for choosing a model.

The answer by @jkff is appropriate in remarking that the Turing Machine is intended as a theoretical device for the mathematical purpose of studying computability and provability (arising actually in the context of Hilbert's Entscheidungsproblem). But it is not quite accurate in the reasons for choosing a simple formalism.

Proving in principle the Halting problem is not that much harder with more advanced models. In fact, our "proofs" are often just construction of a solution. We do not go much into the actual (very tedious) arguments that these constructions are correct. But anyone who writes an interpreter for a Turing complete language does as much as any construction a universal machine. Well, C can be a bit intricate, and we might want to streamline it a bit for such a purpose.

The importance of having a simple model resides much more in the use that can be made of the model, than in establishing its properties (such as the Halting Problem, to take the example given by @jkff).

Typically, great theorem are often theorems that can be expressed very simply and are applicable to a wide range of problems. But they are not necessarily theorems that are easy to prove.

In the case of TM, the importance of simplicity is because many results are established by reducing the Halting Problem, or other TM problems, to problems we are interested in (such as ambiguty of Context-free languages), thus establishing inherent limitations to solving these problems.

In fact, though very intuitive (which is probably the main reason for its popularity), the TM model is often not simple enough for use in such proofs. That is one reason for the importance of some other, even simpler models, such as the Post Correspondence Problem, less intuitive to analyse, but easier to use. But this is because these computational models are often used to prove negative results (which goes back to the original Entscheidungsproblem).

However, when we want to prove positive results, such as the existence of an algorithm to solve some given problem, the TM is much too simplistic a device. It is much easier to consider mode advanced models such as the RAM computer, or an associative memory computer, or one of many other models, or even simply one of the many programming languages.

Then the TM model comes only as a reference point, in particular for complexity analysis, given the complexity of reducing these models to the TM model (usually polynomial).The simplicity of the TM model lends then much credibility to complexity measures (as opposed, to take an extreme example, to the reductions of Lambda-calculus).

**In other words, the TM model is often too simplistic for designing and studying algorithms (positive results), and often too complex for studying computability (negative results).**

But **it seems to be at about the right place to serve as a central link** to connect it all together, with the great advantage of being rather intuitive.

Regarding physical analogies, there is no reason to choose one model over another. **Many Turing complete computation model are physically realizable** (up to unboundedness for memory infinity), since there is no reason to consider a computer together with its software as less physical than a "naked" computer. After all, the software has a physical representation, which is part of the programmed computer. So, since all computation models are equivalent from that point of view, we might as well chose one that is convenient for the organization of knowledge.
> 9 votes

# Answer
The physical analogy that Turing seems to have had in mind is a computer working out problems with pencil, paper, and eraser. You should understand that in 1936, a "computer" was a person employed to compute. Of course in 1936 most computers would have been using adding machines, but Turing doesn't mention these since they are inessential. Here is what he does say, with regard to the tape, in trying to justify that "the 'computable' numbers \[i.e. those that a Turing machine could compute\] include all numbers which would naturally be regarded as computable"

> Computing is normally done by writing certain symbols on paper. We may suppose this paper is divided into squares like a child's arithmetic book. In elementary arithmetic the two-dimensional character of the paper is sometimes used. But such a use is always avoidable, and I think that it will be agreed that the two-dimensional character of paper is no essential of computation. I assume then that the computation is carried out on one-dimensional paper, i.e. on a tape divided into squares.

Although computer is no longer a trade, the last time I checked, kids were still being taught to execute algorithms using pencil and paper as a storage medium. So, although this analogy may seems old-fashioned or even archaic, it is not yet obsolete.

For more see On computable numbers with an application to the entscheidungsproblem, especially sections 1 and 9.
> 4 votes

# Answer
@jkff has the idea about `the Turing Machine is modeled on the idea of a human with a pen and paper` is not entirely correct. But there are many situations where it can be considered correct.

Think about the human as a Turing machine under certain projection of the states. In other words, if you see a human only during his work hours, then during his work hours he performs certain tasks. These tasks are the basic tasks for the job.

If you don't care about his personal life, what he does at home, in his room etc.. Then you can consider this as projecting his transition function into a new transition function in which non-work-related states are ignored. In other words, you can skip over all the states and tasks that have nothing to do with your concern and perspective.

In this model, then the Turing machine is modeled after a human with a pen, paper doing a fixed task (ie view in a fixed perspective). The tape is what he writes down on the paper (ignoring all the papers or writing on some paper that he does not write for the task)

Now if you take into account other tasks that he does then what you have is you have a union of many Turing machines in a human. But then what if he changes his job and he does different task. Then his brain state changes to a different Turing machine when view under different perspective in different time frame.

If you want a good answer to your question, then I think Yuval Filmus answered it well. Use the RAM model. Stick with it.
> 1 votes

# Answer
I want to add two points, not mentioned in earlier examples, to supplement them.

1. The Church-Turing thesis was made clear when Turing invented the Turing machine: It's valuable to have one or more concepts that means something roughly like "possible to calculate algorithmically, in principle". If a problem is not of this kind, then it's not the sort of thing that can be solved with a computer. Alonzo Church argued that his lambda calculus formalism captured just such a concept, but some of his peers (notable Kurt Gödel) were sceptical. Turing proposed a similar concept, defined in terms of (what we now call) a Turing machine, and proved that Turing machine computability was equivalent to lambda-calculus computability. This convinced sceptics such as Gödel that lambda calculus and Turing machines capture a basic, intuitive idea of what can be done with an algorithm. That's roughly the Church-Turing thesis. (I am not being very precise, and I'm ignoring debates about different versions of the C-T thesis and what the original version was.) The beauty of the idea of a Turing machine, as opposed to a purely mathematical formalism like the lambda calculus, is that everyone can see how simple its operation is partly *because* you can easily imagine something like it being physically implemented. Of course it is inefficient, but the obvious potential for physical realization is what makes it intuitively clear that anything that can be proved to be computed by a Turing machine, can be computed on any computer (if you have time and space for it), and that anything that can't be computed on a Turing machine, can't be computed on any of the computers we use today (putting aside some corner cases like computers with true random number generators).
2. The idea of a Turing machine is absolutely central to algorithmic information theory, which, among other things, defines a variety of concepts of randomness that help to guide our understanding of randomness in some scientific and practical computing contexts. (Why is 110101010010011010 more random than 101010101010101010?) I discuss this in an answer to the related question mentioned above.

I would guess that there are other areas of research that have also benefited from the availability of the concept of a Turing machine.
> 0 votes

---
Tags: turing-machines, computation-models
---


# Question
Title: Set-theoretic difference of two languages in CFL - REG
Let $L\_1,L\_2\in$ CFL $-$ REG, with $L\_1\subset L\_2$. Which of the following always holds?

1. $L\_1-L\_2\in$ CFL $-$ REG and $L\_1-L\_2\in$ REG.
2. $L\_1-L\_2\in$ REG and $L\_2-L\_1\in$ CFL $-$ REG.
3. $L\_1-L\_2\in$ REG. $L\_2-L\_1\in$ REG.
4. $L\_1-L\_2\in$ REG. As to $L\_2-L\_1$, it may be in REG or not.
5. None of the above.

# Answer
> 0 votes
Since $L\_1-L\_2=\emptyset\in$ REG, we only need to consider $L\_2-L\_1$.

Consider $L\_1=\\{a^nb^n\mid n\text{ is a positive integer}\\}, L\_2=\\{a^nb^n\mid n\text{ is a non-negative integer}\\}$, then $L\_2-L\_1=\\{\epsilon\\}\in$ REG.

Consider $L\_1=\\{a^nb^n\mid n\text{ is a positive odd integer}\\}, L\_2=\\{a^nb^n\mid n\text{ is a positive integer}\\}$, then $L\_2-L\_1=\\{a^nb^n\mid n\text{ is a positive even integer}\\}\in$ CFL $-$ REG.

Hence, the correct answer is 4.

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


# Question
Title: Solving the min edge cover using the maximum matching algorithm
To solve an instance of an edge cover, we can use the maximum matching algorithm.

*Edge Cover*: an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set \[from Wikipedia\].

*Maximum matching*: a matching or independent edge set in a graph is a set of edges without common vertices \[from Wikipedia\].

For example to find the min edge cover of the example below, we can:

1- Find a maximum matching.

2- Extending it greedily so that all vertices are covered.

The image below present this solution:

My question is why this reduction works, is there a proof for that result? or at least an intuition to help me undestand!

How can be sure that the final solution is the min edge cover of the graph and there is no other edge cover with size less than the founded solution.

# Answer
Assume, w.l.o.g., that G=(V,E) is a graph without isolated vertex. Let's denote by $\mathcal{A}$ the algorithm you describe in your question. We seek to prove that given $G$, $\mathcal{A}$ outputs a minimum edge cover. Before we do that, it can be benifical to make some simple observations. First, both edge cover and matching are set of edges, and the subset of an edge cover can be a matching. Given a *minimal* edge cover $C$(not necessarily the minimum), we denote by $M\_C \subseteq C$ the maximum matching containing in $C$ . Note that $M\_C$ is the matching of maximum size whose edges are all in $C$. We call any edge in $M\_C$ the *matched edge*. We use $V(M\_C)$ to denote the vertices of edges in $M\_C$

**Observation 1** Every vertex in $V\setminus V(M\_C)$ must be covered by an edge which is incident to an edge in $M\_{C}$. Otherwise we could find a larger matching in $C$.

**Observation 2** Every edge in $C$ covers 1 or 2 vertices. Specifically, an edge in $M\_C$ covers two vertices, an edge in $C\setminus M\_C$ covers 1 vertex.

**Theorem 1** $|V|=|C|+|M\_C|$

*Proof $\\;$* By observation 2 and the definition of edge cover, we have $2|M\_C|+|C-M\_C|=|V|$.

By observation 1 we have that algorithm $\mathcal{A}$ outputs a minimal edge cover. Then he correctness of algorithm $\mathcal{A}$ is obvious from theorem 1: when $|M\_C|$ is maximized, $|C|$ is minimized since they sum to a fixed number $|V|$. In such situation, theorem 1 is called Gallai’s theorem
> 7 votes

# Answer
Every edge connects exactly two vertex, thus for $n$ vertices, the minimum edge cover uses between $n/2$ and $n$ edges. In fact every new edge you add to your subset covers either 1 new vertex, or 2 new vertices. When it is 2 new vertices, the edge is part of the maximum matching.

$k$ the number of edge needed for the cover is:

$k = n - a$

with $a$, the number of edges in the maximum matching (at most $a = n/2$).

Starting from the maximum matching, you cannot have any new edge covering 2 vertices (or a re-arrangement of edges that augment $a$). Either it would not be a "maximum matching".

The greedy part of the algorithm just collects the 1 vertex covering edges needed to complete the problem.
> 1 votes

# Answer
Suppose a maximum matching, of size r say, is removed from the graph, along with the endpoints of edges of the matching and edges incident to these endpoints. Suppose k vertices remain. These k vertices form an independent set (otherwise the graph would have had a larger matching, a contradiction)and so covering them requires k separate edges. So a minimum edge cover has size r+k.

Intuitively, you want a maximum matching because then you get to cover the most number (ie two) of distinct vertices with each edge of the cover, thereby using few edges.
> 0 votes

---
Tags: algorithms, graphs, reductions
---


# Question
Title: Is it possible to include numerical values or constants within brackets(time complexity)?
I am currently trying to learn a bit more about the theoretical side of computer science and I have stumbled upon this example I found online:

> $5n^2 + 5n = O(0.5n^2)$

I do have basic understanding of how time complexity works but it is the only example I have found that has a number attached to the $n$ (right side). Does it mean that the person writing that article made a mistake or it is possible to include values this way (like in the definition: $0 ≤ f(n) ≤ cg(n)$ where $c = 0.5$ in this case)?

Sorry if I missed an obvious aspect of this concept but I try learning this stuff on my own and have nobody apart from the internet to ask for help. :)

# Answer
> 1 votes
What you read is slightly unusual, but absolutely correct. Follow the definition of Big-O literally: It means there is a c \> 0 such that for large n, f(n) \<= c * 0.5 * n^2. It’s exactly the same as O(n^2), except that the constant c is different (twice as big will work).

In your example, for n \>= 5 we have 5n \<= n^2 and therefore 5n^2 + 5n \<= 6n^2. So f(n) \<= 12 * 0.5 n^2 and f(n) \<= 6\*n^2, c=12 instead of c=6.

---
Tags: time-complexity
---


title: Time complexity of a 3 nested for-loop

text:
# Question
Title: Time complexity of a 3 nested for-loop
```
for(i = 0; i<n; i++) {
    for(j = 1; j<i*i; j++) {
        if(j % i == 0) {
            for(k = 0; k<j; k++) {
                //statement;
            }
        }
    }
}

```

Here, it's been asked to find the time complexity. I think it's O(n^4), but prof. said it's wrong. Can someone explain how this works ?

# Answer
> 1 votes
First, to get some idea add code to your program that counts the operations and prints the total, then try with n=1, 10, 100 and 1000. That’s not exactly scientific but is a hint about the correct answer. If n= 1000 takes too long, try 200, 300, 400.

Now: How many steps does the innermost loop perform at most, depending on I? And for a given I, how often is the whole loop performed? And how many values of i are there? That together gives you an upper bound, and guess what - it looks like O(n^4) to me.

I’ve just typed this on my phone, so you do it *much* more carefully and you may show be able to show your professor that you are indeed right. If the code is exactly what you wrote.

A bit more precise: The inner loop for k has j iterations. j % i == 0 is true when j is a multiple of i, that is j = i, j = 2i, j = 3i, ..., j = (i-1) i. So for a given i, the executions of the inner loop are i, multiplied by the sum over j for 1 ≤ j ≤ i-1. That sum is (i-1)(i-2) / 2, so the inner loop executes i (i-1) (i-2) / 2 times, which is quite exactly $(i-1)^3 / 2$ times.

We have 0 ≤ i ≤ n-1. Ignoring i = 0 and i = 1, 1 ≤ i-1 ≤ n-2. So the number of executions of the inner loop is about $((n-3)(n-2))^2 / 8$.

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


# Question
Title: Is cubical type theory still consistent with univalent excluded middle and univalent choice?
I want to formalize some undergraduate maths in cubical agda, and learning cubical type theory in the proccess. The problem is that I will need univalent excluded middle and univalent choice (and maybe propositional resizing). I know these are consistent with homotopy type theory (although computation is lost when axiom are used), but cubical that type theory is stronger (in the sense that univalence is a theorem). Are this axiom still consistent in the cubical setting? Is there a better way of doing classical theorems in cubical type theory?

# Answer
> 2 votes
I decided to rewrite my answer, because I thought I could explain the details better. I'd still defer to someone more knowledgeable should they happen to come along.

I think it is relatively safe to say that cubical type theory as an approach *on the whole* is compatible with the classical axioms you want. The reasons for this are:

1. The differences people *usually* point out, like the $\mathsf{Glue}$ type, are just a way of making univalence hold *for all types*, independent of their belonging to a universe. This is (in my view) merely fixing a limitation of the HoTT approach of minimally extending Martin-löf type theory, where it's impossible to state the univalence axiom except by reference to a universe. However, if you have enough universes with univalence axioms, every type is in a universe, and so univalence holds for all types. In fact, this is how Agda actually works directly; the universes are primary, and all types are declared as part of a universe, similar to a pure type system.
2. There is (I've heard) a cubical set model (discovered by Emily Riehl) that is completely compatible with the standard simplicial set model, and I believe it has been shown to be adequate for doing cubical type theory. I think what this means is that if you add EM (and maybe choice), you get the same homotopy theory as the classical simplicial set model. I've also heard that there are constructive analogues of the simplicial set model, so it is not inherently classical.

Now, what you have to worry about are other details. For instance, cubical Agda uses the sort of cubes with inversions and connections. So, if `i` and `j` are dimension variables, then `~ i` is a dimension, and so is `i ∨ j`. There are also Cartesian cubes that don't have  but have other similar constructions. These affect the details of how you are able to construct paths. Having more of them is convenient for easily constructing compositions of paths and whatnot, but my understanding is that the model that matches the classical simplicial model lacks most of these things.

Now, more specifically, I've also heard that most of these other cubical set models *are* anti-classical (I'd forgotten that earlier). I've not been able to work out the details of how you demonstrate this *inside* implemented cubical type theories, but my understanding is that, using `~` as an example, you try to construct some contradictory scenario using a point `i` on the interval such that `i = ~i`. There's no way given in the type theory to construct such a point, and somehow it's inconsistent to presume that you can tell whether any abstract point is or is not like that.

So, I guess the answer to your specific question is that there is *probably* a way to refute excluded middle in cubical Agda (although I don't know how), and every other computer implemented cubical type theory. But it's also likely that a cubical type theory could be implemented that is consistent with classical axioms (and homotopy theory) and supports all the reasoning desired (although maybe it's more difficult to construct certain things). Unfortunately, you'll probably have to wait until the details are fleshed out more and some implementation decides to pick up the compatible version of the theory.

Another option, I suppose, is to not worry about the anti-classical part too much. If you use the cubical primitives to implement something similar to reasoning in the HoTT book, and avoid working directly with the cubical operations, you can probably be reasonably confident (I think) that you haven't relied on any paradoxes. I think there are efforts to provide a HoTT interface on top of cubical type theory in some of the libraries available. You could also dabble in learning the direct cubical parts, even though you don't use them directly, although I don't know exactly which parts are still part of the 'proper' model.

Edit: by the way, here is a presentation about cubical set models of homotopy type theory that mentions the anti-classical properties of many cubical set models. It describes, vaguely, what you have to do to refute excluded middle, but it's all in terms of looking at the models from the outside, hence some of the difficulty of translating that to a refutation within cubical type theory (for me).

Edit 2: here's a potential more positive answer. It's been pointed out to me that the constructions in the above video may not be possible to carry out inside cubical type theory. They are constructions that can be carried out in the 'intended' cubical set models, but just like Martin-löf type theory has other models than the intended one (which is how you get to HoTT), the cubical set models aren't necessarily the only model of the corresponding cubical type theory. So it's possible that cubical type theories are compatible with excluded middle and choice, even though their most obvious models are not.

---
Tags: homotopy-type-theory, cubical-type-theory
---


# Question
Title: Existence of walk in undirected connected graph where nodes must end with assigned value
We have a graph with $N$ nodes and $N-1$ undirected edges, where it's possible to reach one node from any other node. Each node will get assigned a value randomly from \[1,...,10\]. We want the value of every node to end up at 10. The way we update is as follows, whenever we visit a node, we increment the value of that node by 1 with wraparound (e.g. 7 -\> 8 and 10 -\> 1). We can revisit nodes and edges as we please. We don't initially advance the counter in our node we start from. Return the number of possible nodes we can start from, such that every node ends with value 10.

I tried just doing simple backtracking search on the states, but the complexity is way too high, and I don't know when I can say "not possible", since we can cycle from 10 to 1.

# Answer
Let $k$ be the value where we wrap around, in this case $10$. Then the problem can be solved in $\mathcal{O}(n^2 k^2)$ with DP. With some tricks we will improve this to $\mathcal{O}(n k^2 \log n)$. For fixed $k$ this complexity is nearly linear, $\mathcal{O}(n \log n)$. Both algorithms work even on worst-case inputs: the assumption of random assignment of values is unnecessary.

---

We start from the $\mathcal{O}(n^2 k^2)$ algorithm. A connected graph with $n$ vertices and $n-1$ edges is a tree. To check if we can start from some vertex $r$, root the tree at that vertex. We will store the dp states $DP\[i\]\[t\]$, which will denote if the subtree of vertex $i$ can be made to contain only the value $k$, if we cross the edge between $i$ and its parent $t$ times $(\text{mod}\ 2k)$, and our path starts from an ancestor of $i$. After calculating the $DP$, we know that the path may begin from $r$ iff $DP\[r\]\[2k-1\] = 1$.

Note that we may assume that all edges are traversed at least once, since traversing any path back and forth $k$ times changes nothing. Additionally, crossing some edge $2k$ more or less times doesn't change whether a solution exists as long as we still cross it at least once, as we can re-connect the tours visiting these vertices such that we get a path that visits every vertex the same amount of times $(\text{mod}\ k)$.

Let $C\_{i, j}$ denote the $j$th child of vertex $i$. Let $V\_i$ denote the number of times we have to visit the vertex $(\text{mod}\ k)$ for its value to equal $k$. We have the requrrences

\begin{gather} DP\[i\]\[2t\_0\] = \max\_{\sum\_{j} t\_j = V\_i\ (\text{mod}\ k)} \min\_{j = 1, \dots, |C\_i|}DP\[C\_{i, j}\]\[2t\_j\]\\ DP\[i\]\[2t\_0 - 1\] = \max\_{\sum\_{j} t\_j = V\_i\ (\text{mod}\ k)} \max\_{r = 0, \dots, |C\_i|} \min\_{j = 1, \dots, |C\_i|}DP\[C\_{i, j}\]\[2t\_j + \mathbb{I}\_{r}(j)\] \end{gather} where $\mathbb{I}\_{r}(j) = 1$ iff $r = j$.

The first recurrence holds, since if we cross the edge from $i$ to its parent $2t\_0$ times and the edge from $i$ to its $j$th child $2t\_j$ times, we visit $i$ exactly $\sum\_j t\_j$ times, which must equal $V\_i\ (\text{mod}\ k)$. On the other hand, since the edges crossed an odd number of times form a path starting from $r$, and we cross the edge from $i$ to its parent an even number of times, we must likewise cross the edges from $i$ to its children an even number of times.

The second recurrence similarly holds, since if we cross the edge from $i$s parent to $i$ $2t\_0 - 1$ times, $t\_0$ of those crossings end in $i$, and if we cross the edge from $i$ to its $j$th child $2t\_j + 1$ times, $t\_j$ of those crossings end in $i$. Thus this sum must equal $V\_i\ (\text{mod}\ k)$. The same path argument gives us that we may cross at most one edge from $i$ to its children an odd number of times.

These recurrences can be computed in $\mathcal{O}(|C\_i| k^2)$ by initialising $DP\[i\]\[t\] = \mathbb{I}\_{0}(t)$, then looping over the children, at child $j$ assigning \begin{gather} DP\[i\]\[2t-1\] \gets \max\_{0 \leq t\_1 \< 2k} \max\_{r = 0, 1} \min(DP\[i\]\[2t - 2t\_1 - r\],\ DP\[C\_{i, j}\]\[2t\_1 + (1 - r)\])\\ DP\[i\]\[2t\] \gets \max\_{0 \leq t\_1 \< 2k} \min(DP\[i\]\[2t - 2t\_1\],\ DP\[C\_{i, j}\]\[2t\_1\])\\ \end{gather} At this point, $DP\[i\]\[2t-r\]$, for $r \in {0, 1}$, is one if we can visit $i$ in total $t$ times, crossing the edge from $i$s parent to $i$ exactly $-r$ times $(\text{mod}\ 2k)$, but we need the amount of visits to equal $V\_i$, so we finally assign \begin{gather} DP\[i\]\[2t\] \gets DP\[i\]\[2V\_i - 2t\]\\ DP\[i\]\[2t-1\] \gets DP\[i\]\[2V\_i - 2t - 1\]\\ \end{gather}

The complexity of checking one $r$ is thus $\mathcal{O}(\sum\_i |C\_i| k^2) = \mathcal{O}(n k^2)$, giving the complexity $\mathcal{O}(n^2 k^2)$.

---

We can optimise this by noticing that we calculate the same $DP$ values multiple times. However, the straightforward approach of leveraging this fails: calculating $DP'\[i\]\[p\]\[t\]$, where $p$ is the neighbour of $i$ that is an ancestor of $i$ might take $\mathcal{O}(n^2 k^2)$ time, even though there are only $4(n-1)k$ states: consider the star graph. To fix this issue, we use centroid decomposition.

The centroid is a vertex of the tree, such that if we root the tree at that vertex, every subtree will have size at most $\frac{n}{2}$. Such a vertex always exists. Our algorithm will work as follows:

1. Root the tree at the centroid $r$
2. Calculate $DP'\[C\_{r,j}\]\[i\]\[t\]$ for all $j, t$ in $\mathcal{O}(nk^{2})$. This gives us the answer for $r$
3. Using these values, calculate $DP'\[i\]\[C\_{r,j}\]\[t\]$ for all $j, t$ in $\mathcal{O}(|C\_r| \log |C\_r| k^2)$
4. Disable vertex $r$ and recurse to the remaining subtrees. Whenever we try to visit vertex $r$, just return the already calculated $DP$ values.

Before addressing how to do step 3, we'll calculate the complexity of this approach. At the $m$th (0-indexed) round, the size of every remaining subtree is at most $n2^{-m}$. Thus there are at most $\log n$ rounds. During the $m$th round, every remaining subtree is adjacent to at most $m \leq \log n$ already handled vertices. If $n\_r$ is the size of the remaining subtree $r$ is in when $r$ is picked centroid, then steps 1-3 for that subtree take $\mathcal{O}((n\_i + \log n) k^2 + |C\_r| \log |C\_r| k^2)$ time (due to the already handled at most $\log n$ vertices).

Since there are at most $\log n$ rounds, and the sum of $n\_r$ of $r$ participating in that round is at most $n$, we have $\sum\_{i} n\_i \leq n \log n$. Thus the total complexity is

\begin{equation} \mathcal{O}(\sum\_{i} n\_i k^2 + k^2 \log n + |C\_i| \log |C\_i| k^2) = \mathcal{O}(n k^2 \log n) \end{equation}

since each term sums to at most this.

It remains to show how to do step 3. Note that our approach to calculating $DP\[i\]\[t\]$ doesn't care about the processing order of the children. Say $|C\_r| = 2^{m}$. First, using our approach, calculate the intermediate values for children with index in $\[1, 2^{m-1}\]$ and in $\[2^{m-1} + 1, 2^{m}\]$. At the $s$th (1-indexed) step, using the previously calculated values, calculate the values for children with index not in $\[x 2^{m-s} + 1, (x+1) 2^{m-s}\]$, for all $x$, in $\mathcal{O}(2^{m-s} k^2)$ time per interval (by including the other $2^{m-s}$ indices not in this inteval but in the interval in the previous step containing this interval). After the last step, we get $DP'\[C\_{r, j}\]\[r\]$ from the intermediate value for all children but $C\_{r, j}$. This is indeed $\mathcal{O}(|C\_r| \log |C\_r| k^2)$.
> 1 votes

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


title: Complexity of recursive algorithm

text:
# Question
Title: Complexity of recursive algorithm
I'm having hard time understanding time complexity of my solution for combination sum problem. The problem is as follows:

> Given a set of candidate numbers (`candidates`) (without duplicates) and a target number (`target`), find all unique combinations in candidates where the candidate numbers sums to `target`.
>
> The same repeated number may be chosen from candidates unlimited number of times.

Below is my solution written in Java using recursion:

```
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    Arrays.sort(candidates);
    List<List<Integer>> results = new ArrayList<>();
    recurse(results, candidates, target, 0, new ArrayList<>());
    return results;
}

private void recurse(List<List<Integer>> results, int[] candidates, int target, int idx, List<Integer> acc) {
    if (target == 0) {
        results.add(new ArrayList<>(acc));
        return;
    }
    for (int i = idx; i < candidates.length; i++) {
        if (candidates[i] > target) {
            return;
        }
        acc.add(candidates[i]);
        recurse(results, candidates, target - candidates[i], i, acc);
        acc.remove(acc.size() - 1);
    }
}

```

One can observe that the problem size of each recursive step is potentially not changed and the depth of the recursion is bound by `target` value e.g. if the `candidates` array contains number 1 the recursion will happen `target` times. If I simplify the code the interesting part is:

```
private void recurse(List<List<Integer>> results, int[] candidates, int target, int idx, List<Integer> acc) {
    if (target == 0) {
        results.add(new ArrayList<>(acc));
        return;
    }
    for (int i = idx; i < candidates.length; i++) {
        acc.add(candidates[i]);
        recurse(results, candidates, target - candidates[i], i, acc);
        acc.remove(acc.size() - 1);
    }
}

```

Which feels like `O(candidates.length * target)` for the most pessimistic `candidates` input with number 1.

Since my solution is not really a divide and conquer algorithm I guess that I can't apply the master theorem. It feels like a backtracking algorithm but I'm not familiar with finding upper bound for that type of algorithms.

Can someone please advise how to approach complexity analysis of above code?

# Answer
The obvious algorithm tries all subsets, i.e., is $O(2^n)$ if you have $n$ elements to select. And your algorithm does that (try with first element, try without first element).

Complexity is given by the recurrence:

$$T(n) = 2 T(n - 1), T(0) \text{ given}$$

(try two posibilities for first one, recurse on the $n - 1$ others for each).
> 1 votes

---
Tags: complexity-theory
---


title: The hardness of solving $x^2=2$

text:
# Question
Title: The hardness of solving $x^2=2$
What's the hardness of the following problem: $\textbf{argmin}\_x\\{|x^2-2|\\}$.

By analytical calculation, I know the solution is $\pm \sqrt{2}$. But I am quite confused about whether it is hard with regarding to its computation complexity.

# Answer
> 6 votes
> What's the hardness of the following problem: $\textbf{argmin}\_x\\{|x^2-2|\\}$.

It is $O(1)$. There is a single answer: $x = \sqrt{2}$. That means that, regardless of how that answer is represented, a computer can just output the answer and it solves your problem.

In general, to consider the *hardness* or *complexity* of a problem, you need there to be at least one variable as input; in particular, you need **infinitely many possible input values.** Otherwise, every problem can be solved trivially by just outputting the answer.

---
Tags: time-complexity
---


# Question
Title: Flajolet-Martin Algorithm : question about use of certain hash functions
this is a question given in a PDF about streaming algorithms (this isnt an assignment but im trying to understand)

> **Exercise 4.4.1** : Suppose our stream consists of the integers 3, 1, 4, 1, 5, 9, 2, 6, 5. Our hash functions will all be of the form h(x) = ax+ b mod 32 for some a and b. You should treat the result as a 5-bit binary integer. Determine the tail length for each stream element and the resulting estimate of the number of distinct elements if the hash function is:
>
> (a) h(x) = 2x + 1 mod 32.
>
> (b) h(x) = 3x + 7 mod 32.
>
> (c) h(x) = 4x mod 32.
>
> **! Exercise 4.4.2** : Do you see any problems with the choice of hash functions in Exercise 4.4.1? What advice could you give someone who was going to use a hash function of the form h(x) = ax + b mod 2k ?

I have already resolved the first exercise, finding a max R tail length of 0 for (a) and 4 for (b) and (c), therefore the resulting estimation of distinct elements is respectively 1,16,16. (it is not asked to do averages/medians of the hash functions to find a better value)

However, I can't seem to figure the answer to the second exercice ? Is it simply to choose 'a' and 'b' in a certain manner ? or are these functions not good to generate equally randomly numbers with trailing 0s and no trailing 0s ?

Thank you in advance

you can observe the results of each hash functions by running this code : https://onlinegdb.com/rJXC4f4VL

# Answer
> 1 votes
> However, I can't seem to figure the answer to the second exercice ? Is it simply to choose 'a' and 'b' in a certain manner ? or are these functions not good to generate equally randomly numbers with trailing 0s and no trailing 0s ?

You have the right idea. I believe what the question is trying to suggest is that this hash function has a problem with certain values of $a$ and $b$. Consider, in particular, $a = 16$. What will happen to the hash function in that case? How many possible values are there?

So, to pick a good value of $a$, we should probably make sure that $a = 16$ is not allowed. $a = 8$ is not good either. What do you suggest is a good choice for $a$?

---
Tags: hashing, streaming-algorithm
---


title: How many times is a for loop executed?

text:
# Question
Title: How many times is a for loop executed?
Consider the following code snippet:

```
for(int i=0;i<n;i++)

```

The question I have is: whether this loop is executed $n$ times or $(n+1)$ times?

According to what I understand: when $i=n$, the for loop would increment $i$ to $n+1$ and check if $i\<n$ which would evaluate to false and the loop will be exited.

So the increment would be performed a total of $(n+1)$ times. Is this correct? Should we count $(n+1)$ as the number of increment operations performed during algorithm analysis?

I know this would not make any difference to the complexity since $O(n+1) = O(n)$, linear time. But I was just curious to know if my understanding is correct or not.

# Answer
> 4 votes
> Consider the following code snippet:
>
> ```
> for(int i=0;i<n;i++)
>
> ```
>
> The question I have is: whether this loop is executed $n$ times or $(n+1)$ times?

This loop executes $n$ times, not $n+1$ times. The first iteration of the loop has $i = 0$; the second has $i = 1$, and so on, up to the last iteration of the loop $i = (n-1)$. Then let us see what happens after that:

* We get to the bottom of the loop when $i = (n-1)$.
* At this point, we jump up to the top and execute `i++`. So now $i = n$.
* Next, we check the loop condition. We see that `i < n` is false, so the loop condition is false. That means we exit the loop.

So in total, we executed the loop for $i = 0$, $i = 1$, $i = 2$, up to $i = n-1$. That is in total $n$ times.

Your misconception was that the loop is terminated once $i$ gets to $n + 1$; but actually it is terminated when $i = n$, because $n$ is already not less than $n$.

> I know this would not make any difference to the complexity since $O(n+1)=O(n)$, linear time.

That is correct!

# Answer
> 1 votes
A for loop contains a header specifying the iteration and body that executed once per iteration. What you consider is the header. You must run at least the assignment and comparison once to decide to enter the loop or not. A clever compiler can skip a loop if it is not entering if the values are available on the compile time.

In general, we consider how many times the body is run when we look at the Big-Oh notation. We expect that the most time-consuming part of the loop is the body. As you noted, it will be in the same complexity class. The operations are the assignment $1$, increment $n$ and check run $n+1$ times;

$$Assign \to \[Check \to Run body \to Increment\]^\* \to Check \to Exit$$ i.e. The for loop body run $n$ times, check runs $n+1$ times.

For exact timing, you need more than that. See Knuth's first volume where he calculated it exactly. Also, see Corman et al., they made a similar calculation for the loop.

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


title: Data structure for handling intervals

text:
# Question
Title: Data structure for handling intervals
I am trying to create a data structure for handling the subsets of the real line of the form $\[x,y)$. That is, suppose $X \subseteq \mathbb{R}$ and the data structure supports two types of operations: $add(X, \[x,y))$ and $remove(X,\[x,y))$. Each of these two queries return the number of disjoint semi-intervals in $X$. For instance,

```
> add(X, [2, 10))
> 1
> add(X, [3, 9))
> 1
> add(X, [-1, 1))
> 2
> remove(X, [2, 10))
> 1

```

I suspect that this can be realised with binary search tree, however I could not properly invent the behaviour. I still suspect this can be done in such a way that each query works in $O(\log n)$ time, where $n$ is the total number of queries. Can you please suggest anything?

# Answer
Since all intervals are non-overlapping, the use of an interval tree is unnecessary. We will store our intervals in an AVL tree $T$ sorted by start points and use the fact that *bulk deletion* of a set of contiguous keys $q\_i,...q\_{i+k-1}$ can be done in $O(\log n + \log k)$ amortized time (see non-open access and open access).

Let $x=\[a,b)$ be an interval and $begin(x)=a$, $end(x)=b$. We define $pred(x)$ and $succ(x)$ to be the previous and next intervals. Both functions have $O(\log n)$ complexity, where $n$ is the number of intervals in the tree. The number of disjoint intervals is the number of leaves in $T$.

### Insertion

Let us first examine what happens when we insert an interval $x$ into the tree. When inserting $x$, we can determine the range of intervals it overlaps with in $O(\log n)$ time by performing predecessor and successor queries. When inserting $x$, we need to perform one of the following three operations on $T$

1. Add a new disjoint interval.
2. Extend an existing interval.
3. Combine and potentially extend $k$ existing intervals.

**(1a)** The first case happens if the inserted query $q$ doesn't overlap with any of the intervals in our set i.e. $ end(pred(x)) \leq start(x) \land begin(succ(x)) \geq end(x)$ Since no intervals need to be updated, we simply insert $x$ into $T$.

**(2a)** The second case happens if $x$ overlaps with or contains one other interval $q$. In order to update the interval, delete $q$ and reinsert $q'$ where $$q'=\[\min(start(x), start(q)), \max(end(x), end(q)))$$

**(3a)** In the third case, let $Q=\\{q\_i, q\_{i+1}, ... q\_{i+k-1}\\}$ be all $k$ of the intervals that $x$ intersects. $Q$ can be obtained by finding the predecessor and successor of $x$. We can again update the tree by deleting all of $Q$ from $T$ and reinserting an interval $$q'=\[\min(start(x), start(q\_i)), \max(end(x), end(q\_{i+k-1})))$$

The first and second cases have $O(\log n)$ time complexity. The third case at first looks like $O(k\log n)$ time which is undesirable as $k=O(n)$. However, it has been shown that *bulk deletion* of a set of keys in the range $\[L, R\]=\\{q\_i, q\_{i+1}, ... ,q\_{i+k-1}\\}$ can be done in amortized $O(\log n + \log k)$ time. Therefore, for insert we have amortized $O(\log n)$ complexity. Note that the number of leaves (disjoint intervals) in the tree can be updated after each insertion in constant time.

### Deletion

By deleting an interval $x$, we either

1. Split an interval into two
2. Shorten 1 or 2 intervals and delete those in between (if any).

**(1b)** The first case happens if $x$ is nested within an interval $q$ i.e. $$start(q) \leq start(x) \land end(x) \leq end(q) $$ Therefore, we delete $q$ and insert the two resulting intervals $\[start(q), start(x))$ and $\[end(x), end(q))$

**(2b)** In the second case, let $Q=\\{q\_i, q\_{i+1}, ... q\_{i+k-1}\\}$ be the intervals that $x$ overlaps with. We can delete all of $Q$ from the tree and update and reinsert the the trimmed versions of $q\_i$ and $q\_{i+k-1}$ if they were not completely nested in $x$. As in case (3a), this is a bulk deletion that can be done in amortized $O(\log n + \log k)$ time.

Similar to insertions, we can keep track of the number of leaves after each deletion in constant time.

Amortized Complexity of Bulk Updates in AVL-Trees

Bulk Updates and Cache Sensitivity in Search Trees
> 3 votes

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


# Question
Title: Cont: NP-hard or not: partition with irrational input or parameter
Please take a look at NP-hard or not: partition with irrational input or parameter first.

In Will irrational parameters make a problem not well-defined on complexity, I got an answer of "No". Then I checked that some well-defined problems indeed have irrational paprameters(e.g., In the sum of square root problem, it has square roots).

Now I want to use this "property" (irrational parameters donot make a problem ill-defined on complexity) to modify **method 1** such that determining the complexity of original problem is well-defined in some cases and it is NP-complete.

More concretely, suppose that $x\_\*$ in **method 1** is actually $0.52+\sqrt{2}\times 10^{-10}$. Then we ask such a problem:

> Given a set $N=\\{a\_1,...,a\_{n+2}\\}$ with $n+2$ numbers where
>
> * $a\_1,...,a\_{n+2}$ are positive and rational,
>
> find a set $S\subseteq N$, such that $f(S)=0.52+\sqrt{2}\times 10^{-10}$, where $f(S)=\sum\_{i=1}^n a\_i \textbf{I}\_{i \in S} + (0.51+\sqrt{a\_{n+1}}\times 10^{-10})\textbf{I}\_{n+1 \in S}+ (0.47-\sqrt{a\_{n+2}}\times 10^{-10})\textbf{I}\_{n+2 \in S}$ and $\textbf{I}$ is an indicator function.

Then for such a problem, we can argue that it is NP-complete, since there is one instance with rational inputs satisfying

> $\sum\_{i=1}^n a\_i = 0.02$ and $a\_{n+1}=a\_{n+2}=2$.

Is this correct?

# Answer
> 3 votes
Without answering your specific question, let me comment on a basic matter that I see appearing in several of your questions. Trying to reason about this as "irrational parameters do or don't make the problem ill-defined" seems likely to be confusing.

Instead, back up and understand the fundamentals. The fundamentals are that we need to specify a problem precisely before we can ask for its running time. How do we specify a problem? The most fundamental way is as a decision problem, and a decision problem is a formal language: a subset of $\\{0,1\\}^\*$. Thus, the problem is: given a string $x \in \\{0,1\\}^\*$, answer whether it is in the language $L$. More generally, if you want to discuss algorithms for problems that produce multiple bits of output, a *problem* specifies a function $f:\\{0,1\\}^\* \to \\{0,1\\}^\*$. In other words, given any bit-string that is the input, the function $f$ tells us a bit-string that is the desired output.

So, to specify a problem carefully, you specify that mapping $f$. Usually, this is done by specifying the input *and how it is represented as a binary string* (as a convenience, this latter step is often omitted if it is obvious how to do it, but it's exactly this step that is tripping you up, so for you, do not omit it), and by specifying the correct output (as a function of the input) *and how it is represented as a binary string* (again, you better not omit this).

When you start talking about irrational numbers, you are going to run into the problem that *irrational numbers cannot be represented as a binary string*. There is no encoding of numbers that enables you to encode all possible irrational numbers *and* that ensures that all encodings are finite. Thus, if your problem statement says "the input is an irrational number...", you are going to have a problem.

Then, to prove that a question is NP-complete, you construct a reduction. So, go do that. Don't try to prove it with one line ("there is one instance with rational inputs satisfying..") constructed in an ad-hoc way -- instead, explicitly construct the reduction. If you understand the concepts, you should be able to tell whether your reduction is correct or not, without needing to ask us.

Before asking another in this line of questions, I suggest that you study basic material on P, NP, reductions, and complexity classes. Make sure you understand it at the basic level, before trying to apply it to your specific problem. Textbooks are written to make it easier to understand these concepts in the context of some simpler problems, and that will make it easier to pick up than to try to both learn the concepts and apply it to your harder problem at the same time.

---
Tags: complexity-theory
---


# Question
Title: Color coding to get an FPT algoirthm for $k$ disjoint triangles
Consider the following problem:

**Input**: A graph $G=(V,E)$ and an integer $k \in \mathbb{N}$

**Output**: Are there $k$ vertex-disjoint triangles in $G$?

Assume we want to use color coding to develop an FPT Algorithm for that, as done here (starting from slide 60). The reference material proposes the following method:

1. Choose a random coloring $V \rightarrow \[3k\]$
2. Check if there is a colorful solution where the $3k$ vertices of the $k$ triangles use distinct colors.

For 2. it proposes this, amongst others, this method:

Try every permutation $\pi$ of $\[3k\]$ and check if there are triangles with colors $(\pi(1), \pi(2), \pi(3)), (\pi(4),\pi(5),\pi(6), \dots)$

I don't understand why we have to check every permutation $\pi$ of the colors. Wouldn't it be enough to just to check each triple of vertices, see if there are a triangle and if so, only count this triangle if it only uses colors we have not seen before? So like so:

1. For each triple $x,y,z \in V$:
2. If $x,y,z$ form a triangle and colors ${c(x),c(y),c(z)}$ not in colors\_seen\_so\_far:

2.1 colors\_seen\_so\_far += $\\{c(x), c(y), c(z)\\}$

2.2 num\_triangles += 1

where we initialize colors\_seen\_so\_far = $\emptyset$ and num\_triangles = $0$

# Answer
No, this is not correct.

As a counterexample, suppose we have a graph consisting of a central triangle, together with 3 outer triangles, such that each outer triangle is joined to the central triangle by one shared vertex (i.e., each vertex of the central triangle is identified with one vertex of one of the outer triangles).

Clearly, a solution for $k=3$ would take the three outer triangles and not take the inner triangle.

Assume the random coloring assigns a distinct color to every vertex (otherwise there is no colorful solution).

If your *greedy* algorithm considers the central triangle first it will always take it, but this is incorrect.
> 2 votes

---
Tags: complexity-theory, np-hard, randomized-algorithms
---


title: Primality testing algorithm

text:
# Question
Title: Primality testing algorithm
Say, I would like to check a hypothesis concerning primes. Something like "there exists a prime between $n$ and $2n$ for every choice of $n$". I would like to run a code in MATLAB for choices of $n$ upto $2^{32}$ and then use that data and publish the conjecture in a journal.

The question is, what should I use to check primality. Obviously, AKS is an option but it is really really slow. I can use the in-built MATLAB function $isprime()$ which I think uses $10$ instances of Miller-Rabin. This will be way faster but the journal might reject this saying that Miller Rabin is probabilistic and that I should instead use a deterministicalgorithm since one exists.

What should I do? Use AKS? Go with MATLAB's inbuilt Miller-Rabin? Or look at other deterministic algorithms?

I don't think this is the best place to ask this. However I could not find where else to ask. Any suggestions?

# Answer
> 2 votes
A pragmatic answer: Use the Miller-Rabin test with 50 iterations. The probability that a composite number will be wrongly declared prime by this test is at most $2^{-100}$ (see, e.g., here). This is smaller than the chance of a cosmic ray causing a bitflip error that causes your program to output an erroneous result. So, if you're not worried about cosmic rays, you shouldn't be worried about probabilistic algorithms.

An alternative: use any probabilistic algorithm to rule out composite numbers. If the probabilistic algorithm claims the number is prime, use a deterministic primality test, or use a test that produces a primality certificate. There are many such algorithms, and you can study the literature and find one which leads the best tradeoff between complexity of implementation vs speed on numbers of the size you care about.

# Answer
> 1 votes
"There is a prime between $n$ and $2 n$" is known as Bertrand's postulate, proven by Chebyshev.

# Answer
> 0 votes
You don't need many primality checks.

The conjecture is obviously false for n = 1. Now you let n = 2 and find the largest prime p in the range n \< p \< 2n. If no p is found, the conjecture is false. Otherwise, the conjecture is true for all n \< p. We set n = p, again find the largest prime p in the range n \< p \< 2n, which proves the conjecture for all n \< p, and so on. So the primes we need to find are:

```
n = 2 -> p = 3.
n = 3 -> p = 5.
n = 5 -> p = 7.
n = 7 -> p = 13.
n = 13 -> p = 23.
n = 23 -> p = 43.
n = 43 -> p = 83.
n = 83 -> p = 163.
n = 163 -> p = 317.
n = 317 -> ...

```

The range of integers n for which the conjecture is proven almost doubles with each step, so to cover n ≤ 2^32 we will only have to find 24 or 25 more primes, to cover n ≤ 2^64 we need to find 32 more primes,

---
Tags: algorithms, algorithm-analysis, primes
---


title: RAM and ROM confusion

text:
# Question
Title: RAM and ROM confusion
we know RAM contains instruction for we ask computer to do operations we know ROM contains instructions which for computer to work

does this mean RAM contains address of instruction sitting in ROM? ROM tell how to add and RAM points to that address of ROM which tells cpu to add

# Answer
> 2 votes
"ROM" stands for "read only memory". This usually means that you can read any location in ROM, but you can't change what is already in ROM. (Data in ROM is written when the ROM chip is constructed, or using special hardware operations in exceptional situations.)

"RAM" stands for "random access memory". In practice, what this means is that you can read any location in RAM, and you can overwrite any location in RAM. So this differs from ROM in that you are allowed to write into locations in RAM. (Originally, "memory" could only be accessed in specific locations at specific times. For example, if all of your storage is on a tape, then you can't read or write locations on the tape that are not under the read/write head; you have to move the tape first. RAM was better because the access was "random", in the sense that you could easily access any location in RAM at any time.)

Both RAM and ROM can contain any information that can be translated into in binary form. This can include (a) machine language or assembler instructions, (b) addresses of locations in RAM or ROM, (c) data. It can include high-level programming language function representations as well. Whether we call that data or instructions depends on the context.

---
Tags: assembly
---


# Question
Title: Cover interval with minimum sum intervals - DP recursion depth problem
**READ ME FIRST:**
I have just found the official solutions online (have been looking for them for a while, but after posting this I quickly found it), and I'm currently trying to understand it. As I can tell, it uses a much simpler DP, which only uses an O(N) array.
**EDIT 2**
I kinda figured out what and how it does, but I still do not understand why it gives the correct answer. It uses a `dp[index] -> weight sum if we select that interval and previous ones to cover [A, start_of_current]`. It sorts the intervals by end time, than process each one in order. If it's start is `A`, we 'select' it and set it's `dp[i]` to it's weight. If not, it tries to find the previous selected interval whose end is closest to the current intervals start, but there is no gap in between. If found one, we 'select' the current and set it's `dp[i]=it's weight + dp[j]` where `j` is the found previous interval. If we can not find any previous, `dp[i] = inf`. We keep a list of the 'selected' intervals, which is, as we only push items to it, is sorted by the interval's end. When we selected one, we delete all the others from the end of this list whose cost (`dp[i]`) is bigger than the current one's.
What I do not get from this, is why this searching-the-closest-end yields the smallest overall weight sum, and also, why we delete all those intervals from the selection list?

**Story:**
This year I attended a programming competition, where we had a few interesting problems. I had trouble with some of them, and since the next round approaches, I want to clear them up.

**The problem in a nutshell**
We are given `N` weighted intervals, and a `[A,B]` interval. We have to **cover** the `[A,B]` interval with the given ones, in such a way, that we **minimize the overall weight sum** (and then the number of required intervals). We need to print the sum, the number of intervals, and then the intervals themselves. If we can not cover `[A, B]`, we need to report that as a special value (-1).

**First thoughts**
If we sort the intervals by begin time, then we can do simple 0-1 Knapsack-like DP and solve the problem. Also, if the priorities were swapped (minimize count THAN sum), a simple greedy would do it.

**The limits**
Basically, all interval **starts and ends are in the range `1-1 000 000`**, and **N\<=100 000**. **All intervals lie within \[A,B\].**

**My approach**
I wrote a recursive algorithm like the `0-1 Knapsack` one in python, that also stored the last selected interval - thus allowing the recovering of the selection list from the DP array later. It was a `(current_interval, last_covered_day) -> (cost, last_selected_interval, last_covered_day')`-like function. I used a `dict` as a DP array, as a regular array that big would have violated memory constraints and filling it fully would also increase runtime (at least that's what I thought - but a 1000000 * 100000 array would certainly would!). I wrote the function as a recursive one so it would not fill in the entire DP array and be faster & more memory-efficient.

**The problem with this**
Simply, I got `RecursionError: maximum recursion depth exceeded`s on larger datasets - 100k deep recursion was simply too much. I read since on GeeksForGeeks that it should be possible to increase it, but I am still not confident that it would be safe. My recursive function is also not tail-call optimizatiable, so that would also not work.

**So my questions**
Is there a way of solving this problem without DP? If no, is filling in a full table an option with those *high* limits? Maybe we can come up with a different DP approach that does not use such big tables? Is it safe to just increase recursion depth limits with this kinds of problems?

# Answer
> 2 votes
You can always convert any recursive algorithm (that uses the call stack) into a iterative algorithm where you explicitly push and pop onto a stack that you manage. This should eliminate recursion depth exceeded errors.

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