# Question
Title: Why do we need the valid-invalid bit in a page table?
I'm reading about memory management in *Operating System Concepts*, by A. Silberschatz. The author says:

> \[...\] the user process by definition is unable to access memory it does not own. It has no way of addressing memory outside of its page table, and the table includes only those pages that the process owns.

Then, the author explains the need of having a **valid-invalid bit**:

> One additional bit is generally attached to each entry in the page table: a **valid–invalid** bit. When this bit is set to *valid*, the associated page is in the process’s logical address space and is thus a legal (or valid) page. When the bit is set to *invalid*, the page is not in the process’s logical address space.

Why do we also need a valid-invalid bit, if a process is by definition able to access only memory addresses stored in its own page table?

The two quoted sentences appear to be contradictory, in my opinion. There must be something I am missing here.

This exact same question has been already asked a few times; however, none of the answers clarified my doubt. Source:

The answers that other users have given don’t explain why the validity bit is needed to protect address spaces. The page table of a process contains *only* those pages that are valid for that process (i.e., that the process actually owns), so why do we need to replicate a security feature that is already present thanks to the way the page table is implemented?

# Answer
As David Richerby says, it’s not clear what you don't understand. Most of my answer here has already been presented in answers (or comments) to the questions you linked to.

I’ll admit, though, that the *Operating System Concepts* book is probably not as clear as it should be.

The book (going back to Figure 8.6 (Hardware support for relocation and limit registers) on page 361) suggests that the processor knows the maximum user virtual address for a context (process), so if the process tries to access an address above this **limit**, the access fails with an addressing error. This concept seems to erode over the following pages; for example, Section 8.4.2 (Segmentation Hardware) (pages 365 and 366) introduces a **limit** field in each segment table *entry*, but waves its hands over the question of specifying the maximum virtual address (and, correspondingly, the length of the entire segment table).

I would argue that Figure 8.9 (Example of segmentation), on page 367:

\[images copied from this 944-page PDF of the book\]
adds to the confusion:

* It’s clearly not to scale. It says that Segment 0 is 1000* bytes long — both explicitly, in the segment table, and in the map of physical memory $(2400-1400=1000)$. Likewise, it says that Segment 4 is 1000 bytes long — both explicitly, in the segment table, and in the memory map $(5700-4700=1000)$. But Segment 4 is clearly larger than Segment 0 in the memory map, while Segment 0 is clearly larger than Segment 4 in the nebulous logical address space on the left.
* Why are the segments *colored* inconsistently? Segments 2 and 3 are gray on the left and white on the right. Does this mean something?
* How do we know which “segment” a given address is in?
* How do we know the length of the segment table?

Wandering Logic addresses the fourth bullet with their statement, “Typically the page table is a tree *of **fixed size pages**.*” (emphasis added). So, looking at Figure 8.15 (“Valid (v) or invalid (i) bit in a page table”), excerpted here,

it might be that the system has no way of knowing which pages are valid (0-5) and which ones are invalid (6 and 7) other than *marking* the entries for the invalid pages with an invalid flag.

But also, while Figure 8.9 is somewhat confusing, it also contains the kernel of part of the answer to your question: The user virtual address space may be segmented / fragmented / sparse / discontiguous. In other words, just because the maximum virtual address is $N$, that doesn’t mean that every $M$ such that $0 \le M \le N$ is a valid address. Just as the segments are explicitly shown as being discontiguous (and out of order) in the physical memory (on the right), and are implicitly shown as disassociated in the logical address space on the left, with order being irrelevant\**, they may actually ***be*** discontiguous in the logical address space. In fact, the book (somewhat) explicitly (but not clearly) tells us that they are discontiguous, in the last paragraph of Section 8.4.2:

> A reference to byte 1222 of segment 0 would result in a trap to the operating system, as this segment is only 1,000 bytes long.

So the 1222nd byte of the logical address space is not the 222nd byte of segment 1, but rather falls in the gap between segment 0 and segment 1. If we assume that the segments occur in numeric order in the logical address space with addresses at multiples of 2000, starting at 0, then the complete (logical and physical) segment map/table might look something like this:

```
segment               logical                                  physical
   #    | base  limit          range       ...     base  limit          range
--------------------------------------     ...     ----------------------------
   0    |    0   1000           0-999              1400   1000        1400-2399
   1    | 2000    400        2000-2399             6300    400        6300-6699
   2    | 4000    400        4000-4399             4300    400        4300-4699
   3    | 6000   1100        6000-7099             3200   1100        3200-4299
   4    | 8000   1000        8000-8999             4700   1000        4700-5699

```

(I’m sorry, but I just don’t see any reason to display the **limit** to the *left* of the **base**, as the authors do.) So, pretending that the page size is 100 bytes, using a format inspired by Figure 8.15, we would get a page table that looks like this:

```
virtual physical ┃ virtual physical ┃ virtual physical ┃ virtual physical ┃ virtual physical
page # | page #  ┃ page # | page #  ┃ page # | page #  ┃ page # | page #  ┃ page # | page #
   0   |   14    ┃   18   | invalid ┃   36   | invalid ┃   54   | invalid ┃   72   | invalid
   1   |   15    ┃   19   | invalid ┃   37   | invalid ┃   55   | invalid ┃   73   | invalid
   2   |   16    ┃   20   |   63    ┃   38   | invalid ┃   56   | invalid ┃   74   | invalid
   3   |   17    ┃   21   |   64    ┃   39   | invalid ┃   57   | invalid ┃   75   | invalid
   4   |   18    ┃   22   |   65    ┃   40   |   43    ┃   58   | invalid ┃   76   | invalid
   5   |   19    ┃   23   |   66    ┃   41   |   44    ┃   59   | invalid ┃   77   | invalid
   6   |   20    ┃   24   | invalid ┃   42   |   45    ┃   60   |   32    ┃   78   | invalid
   7   |   21    ┃   25   | invalid ┃   43   |   46    ┃   61   |   33    ┃   79   | invalid
   8   |   22    ┃   26   | invalid ┃   44   | invalid ┃   62   |   34    ┃   80   |   47
   9   |   23    ┃   27   | invalid ┃   45   | invalid ┃   63   |   35    ┃   81   |   48
  10   | invalid ┃   28   | invalid ┃   46   | invalid ┃   64   |   36    ┃   82   |   49
  11   | invalid ┃   29   | invalid ┃   47   | invalid ┃   65   |   37    ┃   83   |   50
  12   | invalid ┃   30   | invalid ┃   48   | invalid ┃   66   |   38    ┃   84   |   51
  13   | invalid ┃   31   | invalid ┃   49   | invalid ┃   67   |   39    ┃   85   |   52
  14   | invalid ┃   32   | invalid ┃   50   | invalid ┃   68   |   40    ┃   86   |   53
  15   | invalid ┃   33   | invalid ┃   51   | invalid ┃   69   |   41    ┃   87   |   54
  16   | invalid ┃   34   | invalid ┃   52   | invalid ┃   70   |   42    ┃   88   |   55
  17   | invalid ┃   35   | invalid ┃   53   | invalid ┃   71   | invalid ┃   89   |   56
                                                                              90   | invalid
                                                                              91   |    ︙

```

(Consider all entries that have physical page numbers (not flagged “invalid”) to be flagged “valid” — I left that out to save space.) See also What is stored in the first memory address? Why can’t I print the contents?, where Scott provides an answer that includes a hypothetical (example) virtual (logical) → physical memory map

Maybe Silberschatz, et. al., should have used something like that instead of their Figure 8.9. (Their Figure 8.17 comes close, but, IMO, it is *too* complex and confusing, and not really the same thing in any case.)

***Also****,* as Pseudonym points out, pages that are valid addresses in the process's virtual address space might not be OK for the CPU to access:

* A page might be swapped/paged out to secondary storage (disk or SSD), or it might be located in a memory-mapped file. The operating system would need to trap the access so it can fetch the page from secondary storage.
* A page might have been allocated to the process, but not yet zero-filled. The operating system would need to trap an access to such a page so it can set it to all zeroes.
(Note: I’m not sure the OS would use an “invalid” flag for that; it should be possible to flag the entry as “valid”, but turn off read, write, and execute permissions, so any access to any address in the page will cause a trap to the OS.)
* The conventional wisdom is that `fork()` copies a process’s memory image. In reality, it probably copies the page table, so both parent and child are pointing to the same physical memory. If/when the child process does an `exec()`, it relinquishes its claim on the memory, and everything is cool. But you don’t want it to ***appear*** (behave) as though the processes are sharing memory, so, as soon as either process makes any attempt to *modify* any memory, the kernel wants to intercede and make a copy of the page (so each process can have its own copy). This is the “copy-on-write” paradigm that Pseudonym refers to.
(Although, again, I’m not sure the OS would use an “invalid” flag for that; it should be possible to flag the entry as “valid”, but turn off write permission, so any write access to any address in the page will cause a trap to the OS.)

So, the answer to your question,

> Why do we need a validity bit when the process has no way of addressing memory outside its page table?

is that there can be addresses within the process’s page table that are not valid addresses to access.

---

> Why do we \[also\] need a valid-invalid bit?

Good question. As Silberschatz’s Figure 8.15 suggests, it might be good enough just to set the physical page address (or frame number) to 0. But, notwithstanding the issue raised in the What is stored in the first memory address? Why can’t I print the contents? question (which Pseudonym also mentions: “The first few pages of the address space of a process are deliberately left invalid so that any attempt to access memory through a NULL pointer is trapped by the operating system.”), page 0 is a valid physical page address. To say that “0” means “invalid” would make page 0 of physical memory inaccessible — even to the OS. Pretty much by definition, anything that can fit into a field that is sized to a physical page number will be a (theoretically) valid page number. Sure, you could use an all-ones value (e.g., 0xFFFFFFFF), but even that could result in a situation where a machine that had 128 terabytes\*** of physical memory might be unable to access the last 512 or 1024 bytes; that would be silly.

Consider also what Daniel Jour points out:

> Because the \[page number\] entry isn't used by the MMU \[if the entry is flagged as invalid,\] the operating system can use it to store its own information, like for example a reference to the filesystem entity (for example inode number) where it stored the data to free the main memory for some other processes (it swapped that page out).

So that’s why a page table entry contains a physical page number ***and*** a valid/invalid flag.

\___________________
* Apparently these numbers *are **decimal**!* — see the last paragraph of Section 8.4.2 (Segmentation Hardware). This is, of course, totally unrealistic, but I guess it doesn't matter as long as the numbers are handled consistently.
\** which is nonsense — they are numbers, so they have an order.
\*** I'm pulling a large number out of my hat here; I haven’t checked that the math on this *exactly* makes sense.
> 7 votes

# Answer
Think of a simple scenario, where you have process A's page table. OS **swaps out** some of the pages, hence some of the page table entries will be **invalidated** and invalid bit has to be set.

From Silberchatz, Section 9.4 Page replacement (Page 360): *We can free a frame by writing its contents to swap space and changing the page table (and all other tables) to indicate that the page is no longer in memory.*
> 4 votes

# Answer
To understand the purpose of the valid bit, you need to first understand the layout of the page table. The page table is a table full of entries. The entries for some virtual addresses contain mappings to a physical address; the entries for other virtual addresses might contain no mapping. The latter is indicated by marking the entry as invalid, i.e., clearing the valid bit.

You ask:

> Why do we also need a valid-invalid bit, if a process is \[..\] able to access only memory addresses stored in its own page table?

The way we indicate whether a virtual address is stored in the page table or not is by setting the corresponding valid/invalid bit to valid or invalid. In other words, for each virtual address, there's a corresponding entry in the page table (its location is fixed and determined by the virtual address itself). Think of it like this: for every virtual address there is a corresponding entry somewhere in the page table -- and that is true regardless of whether the virtual address has a valid mapping to some physical address or not. Now we need a way to know whether that virtual address is valid. We do that using the 'valid' bit in the corresponding entry.

Ahh, you say, why do we have an entry for a virtual address that is invalid? That's because of how the page table is structured: it's a table. That means you have to use a slot for an entry even if the virtual address doesn't map to anything.

This is all easiest to think about with a one-level page table, so I suggest you start with that as your mental model.

To put it another way, when we say that "the page table contains a virtual address", that's a short-hand way of saying "the entry in the page table for that virtual address has its valid bit set". Every virtual address -- whether valid or not -- has an entry in the page table, so we need a way to indicate which ones are valid.
> 1 votes

# Answer
I think the confusion may be from this quote:

> One additional bit is generally attached to each entry in the page table: a valid–invalid bit. When this bit is set to valid, the associated page is in the process’s logical address space and is thus a legal (or valid) page. When the bit is set to invalid, the page is not in the process’s logical address space.

I think this is a bit misleading, or at least incomplete.

There are two views of a virtual address space: the CPU's view (which is implemented by the page table mechanism), and the operating system's view, which involves a bunch of additional data structures and concepts that the CPU's page translation hardware doesn't see.

The CPU has no concept of memory-mapped files, swapping, or anything like that, because that requires knowledge about filesystems and secondary storage devices. The only case it can handle directly is the case where a page of virtual address space maps correctly to a page frame of memory. Anything else requires the operating system to emulate it.

When the bit is set to invalid, *from the CPU's point of view*, it is not a valid mapping. The CPU's page translation hardware will not translate that virtual address to a physical address, and will instead trap to the operating system.

From there, it's up to the operating system to decide what to do with it. *From the operating system's point of view*, it may well be "correct" for a task to try to access that page, and in that sense it's not "invalid". It's only the hardware mapping that's invalid.

It may help to think of the "invalid" bit as meaning "cause a page fault". It's up to the operating system to decide what that means and what to do about it when it happens.
> 1 votes

# Answer
It is because , there are scenarios when **OS manually** needs to access a particular location , **lets say for I/O , it passes a buffer address** and hence has to convert **Logical addresses to physical** and hence **it keeps copy of page table**. Now let's a particular page is swapped for something else , then OS when try to access this location for I/O( Lets Say), it will access a Invalid Location and hence the valid/invalid bit is required
> 0 votes

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


# Question
Title: In algorithm analysis what does it mean for bounds to be "tight"
For example we could say alg(x) runs big omega(n) but this bound is not "tight".

What is meant by "tight"? Is it that the bound isn't at its maximum?

So maybe a tighter bound could be big omega (1)??

# Answer
> 6 votes
Generally speaking, a bound is tight if there is no "better" bound.

Take, for instance, $f(n) = \sin(n)$. Then, $-1.5 \leq f(n) \leq 2n$ are valid bounds on $f$ but they are not *tight* -- there are better bounds, e.g. $-1.2 \leq f(n) \leq 1.5n$.

Now, $-1 \leq f(n) \leq 1$ *are* tight bounds -- there are no tighter ones.

You will note that the range of $n$ is relevant here. I implicitly let $n \in \mathbb{N}$ (or $\mathbb{R}$ if you want) here; if we consider $n \in \\{ \pi i \mid i \in \mathbb{N} \\}$ there *are* better bounds.

Now, using Landau symbols the terminology is used similarly: $f \in \Omega(n)$ is a *tight* bound if there is no "better" $\Omega$-bound, i.e. one with a faster-growing parameter function. If we also know that $f \in O(n)$, then *both* bounds are tight and we have $f \in \Theta(n)$. It is, however, very possible that you have, say, $f \in \Omega(n)$ and $f \in O(n^2)$ and both bounds are tight.

Here, and in particular in the context of algorithm analysis, the range of (the implicit) parameters is relevant as well: are you talking about all inputs? Worst-case inputs? The average case? For instance, $\Omega(n)$ is a *tight* (lower) bound on the asymptotic running time of (improved) Bubblesort if you consider the best case, but not for average or worst case.

Note that "tight" can be relative to your goals. If you want to prove asymptotics of the form $f \sim g$, you wouldn't call a $\Theta$-bound "tight".

# Answer
> 2 votes
This definition from Wikipedia makes it simpler:

Tight bounds An upper bound is said to be a tight upper bound, a least upper bound, or a *supremum*, if no smaller value is an upper bound. Similarly, a lower bound is said to be a tight lower bound, a greatest lower bound, or an *infimum*, if no greater value is a lower bound.

https://en.wikipedia.org/wiki/Upper\_and\_lower\_bounds#Tight\_bounds

# Answer
> -2 votes
This question might be a duplicate of this question.

$O$ notation represents the upper bound of an algorithm and $\Omega$ the lower bound. $\it{\Theta}$ combines the two yielding an asymptotically tight bound.

---
Tags: algorithm-analysis, terminology, landau-notation
---


# Question
Title: What is the runtime/time complexity of Coq’s (Dependent) Type Inference?
I remember learning in a class that type inference is decidable but usually takes a long time (e.g. type inference in OCaml is EXPTIME).

I was wondering, since Coq allows programs/values themselves to be in the Type somehow my guess would be that type inference is either:

1. Doubly EXPTIME
2. Undecidable

Does someone know the answer to this? A reference and an intuition would be highly appreciated too.

---

Now that I think about it - I don’t think it should be undecidable. Given a program (or a proof object), computing its type should be decidable given that we have all the constructors of the object. It seems very similar to type checking, except that we need to construct the type. If it were undecidable it feels it would be very hard to check the proof objects Coq builds.

---

related:

# Answer
There are actually two questions here.

## Is the Coq type system decidable?

Long answer short, we hope so, as in it would be a bug if it were not.

It is not a universal requirement for a type theory to have decidable type-checking, but it is considered a desirable property. When type-checking is not decidable, one has to cheat to implement the theory as a proof assistant. There are two typical ways out.

* Only implement an approximation of the type-theory. So now there are two different type systems, the ideal-undecidable one, and the practical-decidable one. One can then try to relate these in some formal way, but usually it comes with its share of issues. Typically, the actual system breaks other good properties like e.g. subject reduction. This is the path taken by Lean.
* Implement type-checking as a back-and-forth process with an oracle (i.e. the user) and rely on the additional missing information to make type-checking decidable again. Once again there are two systems, but the link between enriched derivations and raw terms is clearer. This is what the Andromeda system does, or, in another style, the PRL family of provers.

By design, Coq wants to prevent both situations, for foundational reasons. It is thus a requirement that CIC, the underlying type theory of Coq, enjoys decidable type-checking. This is a subtle property that goes beyond mere consistency of the system, or even strong normalization. The standard proof of decidability critically relies on the latter, but in the abstract it does not seem like a sufficient condition for a type theory to enjoy decidable type-checking.

As of today, the *proofs* of decidability of type-checking for CIC are murky, to say the least. Even though it is widely believed, it is not even clear that CIC is strongly normalizing. Add atop of that the fact that CIC is not really a well-defined system but rather an ever-growing system reflecting the liveliness of the Coq proof assistant, and you get an even more opaque situation.

As a matter of fact, Coq as in "the actual code" is known to not be strongly normalizing for silly reasons. Thankfully it seems to be normalizing for weak head reduction *a priori*, and this is enough for consistency / decidability, but this is quite frightening from a theoretical perspective.

## What it the complexity of Coq type-checking algorithm?

Because Coq features dependent types, it is at least the complexity of the functions it can prove terminating. Indeed, if one can write e.g. a closed term `M : nat -> bool` such that `M` always answers `true`, it can be lifted in the type system by a reflexivity proof `refl : M n = true` for any closed natural number `n`. This always typechecks, but and cost of type-checking is obviously the one of reducing `M n` to a normal form.

Since we can write crazy functions in the logic of Coq (e.g. strong normalization of impredicative logics such as System F), typechecking complexity goes *really, really* beyond EXPTIME, or even ELEMENTARY as you seem to imply. CIC expressive power dwarves any complexity class you can think of.

Rather, it would be surprising to find a total function that cannot be written in Coq, barring standard Gödelian counterexamples like "an interpreter of CIC".
> 7 votes

# Answer
It is decidable, as a consequence of the usual consistency proof, tho the exact time bound is not well understood AFAICT.

You can encode really huge functions into Coq that can take long to normalize, for a nice example see Ralf Loader's famous entry in the Bignum Bakeoff contest:

http://djm.cc/bignum-results.txt
> 2 votes

# Answer
Spurred by comments in Pierre Marie's answer, I'll add some clarification on the difference between type **checking** and type **synthesis**.

Generally, type checking in a dependent type system is designed to be decidable up to normalization for **fully annotated terms**, that is, $\lambda x : T.t$ and $\Pi x : T. U$ for example (you need type annotations in other places as well, e.g. in constructors of $\Sigma$ types). The algorithm is notionally straightforward, just recurse on the structure of the type, with a conversion step at application time that depends on normalization: $t\ u$ is well typed if $t$ is of type $\Pi x : T. U$ and $u$ is of type $T' = T$, so we need to do some reduction.

If annotations are omitted, however, it's a whole different ball game. Now you're trying to (essentially) *guess* the annotations, which is quite hard. Already in the simply-typed case, it can be in EXPTIME, as you have noted. There are several subsystems of CIC for which we have proven that it is undecidable in general to reconstitute the annotations, as I mention here: https://cs.stackexchange.com/a/12957/988. This is often called **inference** in the PL community, but in the subcommunity of dependent types, it's often referred to as **synthesis**.

Now, interestingly, undecidability for a subsystem of CIC doesn't *automatically* imply undecidability for full CIC! Imagine the (admittedly stupid) system which is CIC with the new type $\mathrm{Any}$ and the further rule:

$$ \frac{}{\Gamma\vdash t:\mathrm{Any}}$$

Now type inference is trivially decidable in this extension! So the fact that System F and $\lambda\Pi$ are undecidable do not automatically imply that the CIC is undecidable.

That being said, it very probably is, since there is little chance that the difficulties that crop up in the sub-systems are resolved by the more powerful one (and indeed, probably many more difficulties appear).

It would probably be a simple undergraduate affair to prove this undecidability.

Now how do systems do it in practice? They use *heuristics* based on "classical" Hindley-Milner inference, along with a few bags of tricks from various constraint-solving and higher-order unification insights. One interesting question would be to identify a fragment that these tricks will *always* work on, in the style of e.g. Practical type inference for arbitrary-rank types, but I'm not aware of such work.
> 2 votes

---
Tags: time-complexity, type-theory, dependent-types, type-inference, coq
---


# Question
Title: Counting the number of squares in a graph
Given an undirected graph, how would one go about calculating the number of squares in the graph? That is, a square is a cycle of length 4.

I know that it is possible to count the number of triangles (cycles with length 3) in polynomial time. Is it possible to calculate the number of squares in polynomial time as well, and how would one go about doing this?

# Answer
There is a simple $O(n^4)$-time algorithm which I will let you discover yourself. A better algorithm follows from the following formula for the number of squares: $$ \frac{1}{8} \left( \operatorname{Tr} (A^4) - 2\sum\_i d\_i^2 + \sum\_i d\_i \right), $$ where $A$ is the adjacency matrix and $d\_i$ is the degree of the $i$th vertex. Using this formula you can compute the number of squares in $O(n^\omega)$, where $\omega \< 2.373$ is the matrix multiplication constant.

To prove the formula, let us expand $\operatorname{Tr} (A^4)$: $$ \operatorname{Tr}(A^4) = \sum\_{i,j,k,\ell} A\_{ij} A\_{jk} A\_{k\ell} A\_{\ell i} = \sum\_{\substack{i,j,k,\ell \\ \text{all different}}} A\_{ij} A\_{jk} A\_{k\ell} A\_{\ell i} + R, $$ where $R$ consists of bad terms that we would like to get rid of.

Let's see what these terms look like. Since the diagonal of $A$ consists of zeroes, we have $i \neq j \neq k \neq \ell \neq i$. Hence what could go wrong is $i = k$ or $j = \ell$, or both. Therefore $$ R = \underbrace{\sum\_{\substack{i,j,\ell \\ i \neq j \neq \ell \neq i}} A\_{ij} A\_{ji} A\_{i\ell} A\_{\ell i}}\_{R\_1} + \underbrace{\sum\_{\substack{i,j,k \\ i \neq j \neq k \neq i}} A\_{ij} A\_{jk} A\_{kj} A\_{ji}}\_{R\_2} + \underbrace{\sum\_{\substack{i,j \\ i \neq j}} A\_{ij} A\_{ji} A\_{ij} A\_{ji}}\_{R\_3}. $$ It is not hard to check that $$ \begin{align\*} R\_1 &= \sum\_i d\_i (d\_i - 1), \\ R\_2 &= \sum\_j d\_j (d\_j - 1), \\ R\_3 &= \sum\_i d\_i \end{align\*} $$ It follows that $$ \sum\_{\substack{i,j,k,\ell \\ \text{all different}}} A\_{ij} A\_{jk} A\_{k\ell} A\_{\ell i} = \operatorname{Tr}(A^4) - 2 \sum\_i d\_i^2 + \sum\_i d\_i $$ The sum on the left counts each square precisely eight times, leading to the formula stated above.

As an example, consider the square graph on four vertices $1,2,3,4$, which satisfy $d\_1 = d\_2 = d\_3 = d\_4 = 2$. Then $$\operatorname{Tr}(A^4) - 2 \sum\_i d\_i^2 + \sum\_i d\_i = 32 - 2 \cdot 4 \cdot 2^2 + 4 \cdot 2 = 8, $$ and indeed there is a single square.

Another example is the complete graph on $n$ vertices. The eigenvalues are $n-1,-1,\ldots,-1$, and so $$ \operatorname{Tr}(A^4) - 2 \sum\_i d\_i^2 + \sum\_i d\_i = (n-1)^4 + (n-1) - 2n(n-1)^2 + n(n-1) = n(n-1)(n-2)(n-3) = n^{\underline{4}}, $$ and indeed the number of squares is $n^{\underline{4}}/8$.
> 7 votes

# Answer
I'm not sure where Yuval got his formula from but when trying to replicate it I got a bit lost so I will share with you what I found. You can naively calculate the number of 4 cycles using $$\text{Tr}(A^4)=\sum\_{ijkl}A\_{ij}A\_{jk}A\_{kl}A\_{li}$$ which you can read as "test if vertex $i$ is connected to vertex $j$, vertex $j$ is connected to vertex $k$ etc." But there is an issue, consider the following graph:

```
1--2
|  |
4--3

```

In addition to counting the square (1-2-3-4) the naive algorithm will also count 2 cycles (1-2-1-2). If you don't want this you can add a term with a Kronecker Delta to ensure that vertex $i$ is distinct from vertex $k$ and node $j$ is distinct from vertex $l$. $$\sum\_{ijkl}A\_{ij}A\_{jk}A\_{kl}A\_{li}(1-\delta\_{ik})(1-\delta\_{jl})$$ You can expand this and use that $A\_{ij}^2=A\_{ij}$, $ A\_{ij}=A\_{ji}$ and $d\_i=\sum\_jA\_{ij}$. After simplifying this gives $$\text{Tr}(A^4)-2\sum\_id\_i^2+\sum\_i d\_i$$ I'm relatively sure this is correct. As a bonus you can also consider "pure squares", i.e. exclude squares with cross links:

```
1--2
|\ |
| \|
4--3

```

You can exclude this by adding two terms that don't count cross links. $$\sum\_{ijkl}A\_{ij}A\_{jk}A\_{kl}A\_{li}(1-\delta\_{ik})(1-\delta\_{jl})(1-A\_{ik})(1-A\_{jl})$$ But I don't know if it's possible to simplify this and as it is written right now this is really slow to compute. If you divide this final expression by $8$ you get exactly the number of squares in the graph. Each vertex that's in a square accounts for two squares (one clockwise, one anti-clockwise) and for four vertices this gives $2\*4=8$.
> 1 votes

---
Tags: graphs, combinatorics
---


# Question
Title: Why are $\sf{P} \ne \sf{NP}$ and $\sf{NP} \ne \sf{coNP}$ compatible?
If $\sf{P} \ne \sf{NP}$ and $\sf{NP} \ne \sf{coNP}$ are both true then $\sf{P}$, $\sf{NP}$ and $\sf{coNP}$ are three separate complexity classes. In other words, verifying a solution, finding a solution and proving there is no solution to a formula are three separate tasks.

However, if $\sf{P} \ne \sf{NP}$ then both $\sf{NP}$ and $\sf{coNP}$ are in $\sf{EXPTIME}$ and not better. If $\sf{P} \ne \sf{NP}$ then it makes sense that $\sf{NP} = \sf{coNP}$, both finding a solution and proving there is no solution are exponentially hard.

From wikipedia:

* It is suspected that $\sf{P} \ne \sf{NP}$
* It is suspected that $\sf{NP} \ne \sf{coNP}$

I'm having trouble understanding how those two suspicions are compatible/consistent? Is it suspected that regardless the exponential difficulty for both, finding a solution is still easier than proving there is none in the general case?

# Answer
> 11 votes
> However, if P != NP then both NP and coNP are in exptime and not better.

This is not neccesarily true. It just means that some NP (and coNP) problems cannot be solved in polynomial time. This is not necessarily the same as requiring exponential time (e.g. $n^{\log n}$ is not polynomial but also not exponential).

> If P != NP then it makes sense that NP = coNP, both finding a solution and proving there is no solution are exponentially hard.

It does not matter that they are "equally hard" in the sense of both requiring a similar (whether that be exponential or some other) amount of time to solve. NP and coNP are classes *of problems* and even if the problems in NP and coNP have exactly "the same time complexity" the problems can still be different. NP and coNP are not defined *in terms of time complexity*.

Recall that NP is the set of problems for which

* it can be proved (using an appropriate hint) that there is a solution in polynomial time

and coNP is the set of problems for which

* it can be proved (using an appropriate hint) that there is *no* solution in polynomial time

To show that SAT is in NP, we can easily see that, if given a satisfying assignment as "hint", we can easily (in polynomial time) check that a given formula is a yes-instance of SAT. However, it is not clear how we can easily give a similar "hint" to allow one to easily check that a given formula does not have any satisfying assignment (which would be needed to show that SAT is in coNP). If one were to prove that P $\not =$ NP, that wouldn't change that. Why would it suddenly become possible to find such hints that allow you to easily verify the non-existence of a satisfying assignment?

In fact, the exact opposite of your intuition is true. If it turns out that P=NP then it immediately follows that NP=coNP.

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


title: Projection syntax - relational algebra

text:
# Question
Title: Projection syntax - relational algebra
I'm trying to understand this paper and in Figure 1 page 389 there's a projection in the form of $\pi\_{d.id : s.id}$. What does the colon mean? Because usually projections are simply $\pi\_{name}(R)$

# Answer
Colon in Π (project) seems to be attribute rename after projecting a la SQL SELECT AS, but in the order new attribute : old attribute. This is similar to its use in Γ (group by) for new attribute : value per pseudo aggregation function call.

> Thus, the dependent join is executed on the projection of the students’ id only, i.e.:
>
> ```
> . . . Π d.id:s.id ((students s ⋈ s.id=e.sid exams e) ⧑
>     (Γ ∅;m:min(e2.grade)(σ d.id=e2.sid exams e2)))
>
> ```

This interpretation seems to be needed to make sense of Figure 1 as we follow relation attribute sets from the root down or leaves up.
> 1 votes

---
Tags: relational-algebra
---


# Question
Title: Why is tail recursion better than regular recursion?
There is the axiom you should always prefer tail-recursion over regular recursion whenever possible. (I'm not considering tabulation as an alternative in this question).

I understand the idea by why is that the case? Is it only because of the compiler can optimize the recursive call in case of tail recursion? if that is the only reason, why the compiler would not be able to optimize the regular recursive call?

# Answer
> if that is the only reason, why the compiler would not be able to optimize the regular recursive call?

You are focusing on the wrong thing here: the reason the optimization works is because of the *tail* part, not because of the *recursion* part.

Tail-recursion elimination is a special case of tail-call elimination, not a special case of some form of recursion optimization.

*Normally*, when you call a subroutine, you have to "remember" where you called from and what the current state is, so that you can continue the execution when you come back from the `return`.

So, for example, if you have something like:

```
function foo() {
    bar();
    baz();
    qux();
}

```

Then before the call to `bar()` and before the call to `baz()`, you have to store the current state and restore it after `bar()` returns and after `baz()` returns. *But*, since the call to `qux()` is a *tail-call*, you know that there is nothing that will be executed after you return back, so you can skip the whole "remember and restore" bit. Instead, you can simply jump to `qux`. It is literally equivalent to a `GOTO`.

*Tail-recursion* is the intersection of a tail-call and a recursive call: it is a recursive call that also is in tail position, or a tail-call that also is a recursive call. This means that a tail-recursive call can be optimized the same way as a tail-call.

Now, an obvious question is: if a tail-recursive call can be optimized the same way as a tail-call, why do we care *specifically* about tail-recursive calls and not just about tail-calls in general?

Well, first of all: we *do* care about tail-calls in general. Tail-calls allow writing some code in a very elegant manner that is hard to express otherwise. For example, if you have tail-calls, then you can simply express a state machine using subroutine calls: every state is a subroutine and every transition is a call – this makes the code look like a direct translation of how you would draw the state machine on paper, and the control flow graph of the code matches exactly the state machine. Since these calls never return, you would quickly run out of stack space if tail-calls weren't optimized. Without tail-calls, state machines are typically implemented as state tables, with `GOTO`s, and that code does not look at all like the drawing of a state machine.

The reason why we care about tail-recursion as distinct from general tail-calls, and specifically why we care about *direct tail-recursion*, i.e. where a subroutine directly tail-calls itself (`foo` calls `foo`) instead of indirectly via another subroutine (`foo` calls `bar`, `bar` calls `foo`) is because some widely-used platforms do not support generalized non-local control constructs such as `GOTO`, which are needed to efficiently implement tail-calls. In other words: optimizing tail-recursion is the same as a loop (which most target languages support), optimizing tail-calls is the same as an unrestricted `GOTO` (which many target platforms, e.g. JVM, ECMAScript, CLI) do not support.

For example, on the JVM, it is *possible* to implement tail-calls, but it is complex and slow and hinders interoperability with other JVM languages, because the JVM does not have unrestricted `GOTO` or the ability to reflectively manipulate the stack or Continuations or something similar.

The JVM *does*, however, have a `GOTO` that allows to jump to a different location *within the same method*. Java uses this to implement loops for example, but it can also be used to implement *direct tail-recursion*. So, the reason why we care about direct tail-recursion specially, is because there are widely-used platforms where implementing *direct tail-recursion* is easy but implementing *general tail-calls* is infeasible (meaning, it is technically possible but it wouldn't make sense because it negates the reasons why you chose that platform in the first place – e.g. on the JVM, it makes your language slow or badly interoperable with other JVM languages, but the performance of the JVM and the ability to interoperate with other languages are precisely the reasons why you chose the JVM as a platform in the first place).

An important sidenote: in your question, you used the term "optimization", as did I in my answer. However, it is important to distinguish between an *optimization* and a *language feature*. An *optimization* is a private internal implementation detail of a particular version of a particular implementation of the language. It is entirely optional. For example, compiler A may perform a particular optimization but compiler B may not. A real-world instance of this is that the Oracle HotSpot JVM performs Escape Analysis but no Escape Detection whereas the Azul Zing JVM *does* perform *both* EA and ED. And neither the Oracle HotSpot JVM nor Azul Zing JVM perform tail-call optimization but the Eclipse OpenJ9 JVM (formerly IBM J9) *does* eliminate *some* tail-calls under *some* conditions.

So, an optimization may or may not be implemented at all by a particular implementation, and it may or may not be performed in a particular situation.

A *language feature*, however, *must* be implemented by all conforming implementations. *Tail-Call optimization (TCO)* is, as the name implies, an *optimization*. It is not mandatory. The corresponding *language feature* is typically called *Proper Tail-Calls* or *Properly Implemented Tail-Call Handling (PITCH)*. A language with Proper Tail-Calls or PITCH basically has a section in its language specification that says "all implementations must perform TCO under these conditions", and so in some sense, PITCH is simply just "language-mandated TCO", but it is important to distinguish between an *optional optimization* that may or may not exist in a particular implementation and may or may not be performed in a particular situation, and a *mandatory feature* that *must* be implemented by all implementations and *must* be performed under all circumstances prescribed in the specification.

For example, many C and C++ compilers will perform TCO under some limited set of circumstances, but there is no guarantee *if* or *when* they will do it. So, you cannot write code that relies on it (like the state machine example above) because you cannot know when you write the code whether the optimization will actually happen or not.

The same thing applies to *Tail-Recursion Elimination (TRE)*. TRE is an optimization that is not guaranteed to happen. As far as I know, there is no common name for the language feature that corresponds to the optimization (like there is with PITCH / Proper Tail-Calls for TCO). It is typically just called *Tail-Recursion*, although I call it *Proper Tail-Recursion* in analogy to the Proper Tail-Calls.
> 48 votes

# Answer
The way a standard function/procedure (from now on I'll just say "function") call works is that the caller needs to store onto the stack whatever state it needs for computations that occur after the call, and then the call occurs. Calling a function may also require manipulating the stack; on many current CPUs, issuing a call involves pushing the return address onto the stack. When the call returns, the state is retrieved from the stack, then any following computations are performed.

If the call is a tail call (i.e. it is the last thing to happen in the caller), however, then by definition *no* computation follows. So if everything is right and the stars align, the tail call can be implemented as a *jump* instruction. And in the case where the tail call is to the function itself (i.e. tail recursion), this can be implemented as a loop.

Programming language semantics do not always allow this optimisation; in C++, for example, destructors or code to manipulate the exception state may need to run after a tail call. However, it is needed in programming languages without a loop statement, because that is the only way to implement a loop using constant stack space. It is so important that in some languages, most notably Scheme, tail call optimisation is written into the language definition.

There are other options. The Mercury programming language implements something called "middle recursion", which you can read all about here:

(Full disclosure: I'm one of the original Mercury developers.)

It's also not unheard of for compilers to give a function more than one entry point, one for "real" calls and one for "tail" calls, if that is more convenient for the ABI (e.g. to handle callee-save registers correctly).
> 13 votes

# Answer
tail recustion is better becaus a good compiler can optimise it into a goto, thus it doesn't consume any stack space fro the recusrion or waste time returning.

```
 foo(a){
     m=bar(a);
     if(z) return foo(a-1);
     return m;
 }

```

becomes

```
 foo(a){
     refoo:
     m=bar(a);
     if(z){
         a=a-1;
         goto re_foo;
     }
     return m;
 }

```
> 1 votes

# Answer
Tail-recursive calls are better than other recursive calls because you can optimize away the return. Let’s say you try to write

```
fibonacci n =
  fibonacci (n-1) +
  fibonacci (n-2)

```

Can either call be optimized? No, because it'll turn into something like

```
push n on the stack
push the argument n-1
call fibonacci and save the return value
retrieve n from the stack and push n-2
call fibonacci and save the return value
add the two return values
return

```

You can’t just transfer control to either function you’re calling, because there’s always something to be done afterwards, and you can’t re-use the same stack frame for the call, because you have something saved on the stack that you will need after it returns.

Tail-recursive calls are also better than most tail calls (although not all other tail calls) because you’re calling the same function. So, you will always be passing the same number of arguments in the same format. You also won’t be returning, so you can throw away anything else on the stack or registers and re-use the exact same stack frame. Often, you’ll be passing the tail-recursive call some of the same parameters unchanged, and the function body doesn’t have to insert any code to pass them.

In fact, making a tail-recursive call optimizes to exactly the same code as optimizing and jumping back to the start of the code block. Which is exactly the same code as a loop. If you check out the assembly that a `while` loop and its equivalent as a tail-recursive function compile to, you will see that this is nearly identical. Decades ago, computer scientists often believed that they should start out by writing a recursive algorithm, since those are easier to understand and prove correct, then turn it into a tight loop, because those were faster. But now, if you write it tail-recursively, the compiler does that transformation for you, and you get the best of both.

Tail-recursion also lets you use functional programming. Loop variables have to be mutable, so it’s hard for the compiler to check that they haven’t been updated too often, or not updated when they should have been. Not only for humans. It’s also harder for the compiler to figure out what optimizations are safe to make.

With tail recursion, if you make your function’s input immutable, the state is only updated once per recursion, when you make a call, and all local state is updated once and only once, all together. There is no other local state that can creep in. It’s easy to reason about, prove correct, and optimize.
> 0 votes

---
Tags: recursion, tail-recursion
---


# Question
Title: Proof that if the residual network of a max flow has no cycles then the max flow is unique
Let $G = (V,E)$ be a directed graph with source $s$ and sink $t$ and $s \neq t$. For each edge $e \in E$, we have $c(e) \in \Bbb N$.

After running Ford-Fulkerson algorithm a flow function $f$ returned a max flow.

Let $R\_f$ be the residual network that represents the max-flow $f$.

I would like to prove that if $R\_f$ has no cycles then there is no other max flow function. I tried assuming that $R\_f$ has no cycle and assuming towards contradiction that another flow function exists but I was stuck trying to find a cycle, thus reaching the contradiction. Any help will be appreciated.

# Answer
> 2 votes
Suppose there is a max-flow $f'\neq f$. Then,

1. The function $\Delta f= f'-f$ is a nontrivial flow of flow value $0$ in $R\_f$. (Nontrivial just means $\Delta f$ is not zero on some edge.
2. There is a cycle in a $0$-valued nontrivial flow.

How do we prove point 2? Start with any edge with non-zero flow. Visit vertexes by following an outgoing edge with non-zero flow repeatedly. That following action is always possible since

* we will never encounter the source nor the sink since this is a $0$-valued flow, and
* for any vertex that is not source nor sink, the sum of outgoing flow value from that vertex is equal to the sum of incoming flow values to that vertex.

Since there are finitely many vertexes, we will go back to some vertex that we have visited before, at which time we have found a cycle.

---

**Exercise 1.** Verify point 1.

**Exercise 2.** Prove that we can decompose a $0$-valued flow into at most $m$ cycle flows, where $m$ is the number of edges excluding the edges from the source and the edges to the sink. (A cycle flow is a flow where the flow function is zero everywhere except on all edges of one cycle.)

---
Tags: network-flow
---


# Question
Title: Why does the hash function in Rabin—Karp produce unique hashes?
The Rabin–Karp algorithm uses a rolling hash function to find a substring matching a pattern:

$$ H = c\_1a^{k-1} + c\_2 a^{k-2} + c\_3 a^{k-3} + \cdots + c\_k a^0, $$

where $a$ is a constant, $c\_1\ldots c\_k$ are the input characters, and $k$ is the number of characters there are in the pattern we are trying to find in the main string.

I know this function makes it easy to recompute the hash at the next character using the previous one. What is the basis for using this function which looks like we're converting to a number system - does that guarantee uniqueness? Maybe I'm asking an axiomatic question - is the expression of a number in a base unique given digits?

# Answer
> What is the basis for using this function which looks like we're converting to a number system - does that guarantee uniqueness?

No, it's not possible to guarantee uniqueness if H is of a fixed size and the needle is of unbounded length. But we want something "close" to uniqueness; different strings shouldn't have the same hash "more often than necessary", because every false match means extra work. To satisify that,

1. Every character of the input should count towards H. No problem with the polynomial construction here.
2. H should depend on ordering. If we let `a = 1` then we would have a very cheap hash function, but `H("santa")` would equal `H("satan")`, resulting in excess false positives. By multiplying each position by a different power of `a`, permutations of a given string will (usually) have different hashes.
3. The available hash space should be covered evenly. This function isn't perfect, but it's close enough as long as the base and modulus are chosen sensibly and the needle isn't too short (if the needle is very short, another algorithm would be better anyhow).

At the same time, the hash has to be cheap enough to compute that it's worth bothering with in the first place. That means it should have the rolling-hash property (the new hash can be computed given the previous hash and the next character) and it should use a small number of simple operations. For the given hash function, the update operation is a couple of multiplies and a couple of adds (and usually a modulus, which is missing from your description), which is about as cheap as you can possibly get and still have a suitable hash function. If updating the hash was too expensive, then it would be more efficient to just `memcmp` every possible offset.
> 1 votes

# Answer
The hash need not be unique. From wikipedia:

> The Rabin–Karp algorithm proceeds by computing, at each position of the text, the hash value of a string starting at that position with the same length as the pattern. If this hash value equals the hash value of the pattern, it performs a full comparison at that position.
> 0 votes

---
Tags: number-theory, hashing, base-conversion
---


# Question
Title: Is it accurate to contrast a Turing machine with finite automata by claiming the former is stateful and the latter is pure?
Recently, I was having a debate with a friend about what it would mean to create a machine that ZKSnarks (proves) itself. I tossed the word pure machine out there while describing what I hypothesized would be the manner of state transition for such a machine, alluding to the notion of a pure function. I didn't really know if such a term existed and later decided to read up on automata theory. In doing so, I found the following statement on a Stanford CS page:

> Therefore, the major difference between a Turing machine and two-way finite automata (FSM) lies in the fact that the Turing machine is capable of changing symbols on its tape and simulating computer execution and storage.

I understand that finite automata have some machine state. But, with the above in mind, would it be accurate to describe a Turing machine as a stateful system and finite-automata as pure? Is there a better shorthand for the difference as it might pertain to my initial premise?

# Answer
> 5 votes
No. The difference between a Turing machine and a finite automaton is in the amount of available work space:

> *Finite automata are equivalent to Turing machines with finite tapes.*

Indeed, any finite automaton can be encoded as a Turing machine that requires no additional work tape. Conversely, a Turing machine whose work tape has finitely many cells has a finite number of possible state-tape configurations and can therefore be encoded as a finite state automaton.

# Answer
> 2 votes
It depends what you mean by "pure". Without knowing what you mean by it, it seems hard to say. See https://en.wikipedia.org/wiki/Pure\_function for one possible meaning. That notion relates to the input-output behavior of the system, and Turing machines and finite-state automata can be viewed as systems that meet those requirements.

It is true that when you look at the sequence of transitions, Turing machines are stateful. So too are finite-state automata: the state is contained in which state of the automaton you are currently in. The overall input-output behavior can still be pure, even if the system modifies internal temporary variables as part of the process of obtaining the final output.

But this may or may not reflect the meaning of "pure" you have in mind, so it may or may not be useful to you.

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


title: Cycle detection and Iterated function

text:
# Question
Title: Cycle detection and Iterated function
I try to understand algorithm from this Wikipedia article. Initially it is talking about some function **f**. I specifically getting problem in that part. Below is the paragraph which is quite mathematical. Can anyone explain me that?

> For any function $f$ that maps a finite set $S$ to itself, and any initial value $x\_0$ in $S$, the sequence of iterated function values
>
> $x\_0, x\_1 = f(x\_0), x\_2 = f(x\_1), ..., x\_i $
>
> must eventually use the same vale twice: there must be some pair of distinct indices $i$ and $j$ such that $x\_i$ = $x\_j$. Once this happens, the sequence must continue periodically, by repeating the same sequence of values from $x\_i$ to $x\_{j−1}$. Cycle detection is the problem of finding $i$ and $j$, given $f$ and $x\_0$.

# Answer
Suppose $S$ is a set of size $n$. Then considering the values $x\_0$, $x\_1$, …, $x\_n$, using the pigeonhole principle, there must be $0\leqslant i \< j \leqslant n$ such that $x\_i = x\_j$ (because all values $x\_k$ are in the set $S$, which contains $n$ distinct values).

Therefore, $x\_{j+1} = f(x\_j) = f(x\_i) = x\_{i+1}$, $x\_{j+2} = f(x\_{j+1}) = f(x\_{i+1}) = x\_{i+2}$, and so on.

It means that the values $x\_j$, $x\_{j+1}$, …, $x\_{2j-i-1}$ will be exactly the values $x\_i$, $x\_{i+1}$, …, $x\_{j-1}$. There is indeed a cycle of length $j-i$ starting at index $i$.
> 0 votes

---
Tags: algorithms
---


title: The Halting problem proof is wrong?

text:
# Question
Title: The Halting problem proof is wrong?
First, let's see the pseudocode proof of halting problem:

```
P(x) =
  run H(x, x)
  if H(x, x) answers "yes"
      loop forever
  else
      halt

```

Then we have a problem:

When param x is the encoding string of P itself, the code line `run H(x, x)` will go to an infinite loop.

Because:

How does H know whether x halts on x?

The answer is H must simulate x on x, then it will call P(x) again and again, then go to an infinite recursive calling. So the pseudocode will stuck in this line `run H(x, x)`, and never can continue. So I think the pseudocode proof is not correct.

Edit:

H seems like a future teller of P. no matter what H says about P, when P actually act x on x, P does the opposite of what H says, which shows that the future teller of P does not exist.

We know that future teller does not exist. so the H does not exist.

# Answer
> 19 votes
You are committing a logical error. This question has nothing whatsoever to do with computability and machines. It is entirely about how to prove that something does not exist. Namely, to show the statement $$\lnot \exists x . \phi(x)$$ we do as follows:

1. Assume that there is $x$ such that $\phi(x)$. We assume this even though perhaps we have no idea how to get such an $x$. We may even be of the opinion that there is no such $x$, but we assume there is one anyway, for the purposes of proving that there isn't one.
2. Working *under the assumption* that there is $x$ such that $\phi(x)$ we derive a contradiction. While deriving the contradiction, we need not worry where $x$ came from, or whether it is possible to have one, because we already assumed that there is one.

The proof of non-existence of the halting oracle takes this exact form: $$\lnot \exists H . \text{$H$ is a halting oracle}.$$ I apologize in advance for the ensuing bold text.

First **we assume there exists a halting oracle $H$**, that is a program $H$ which always terminates and correctly determines for every program and input whether the program run on the input will halt. We now **work under the assumption that $H$ exists**. We do not ask whether the assumption is actually correct, or how $H$ might look like. If our intuitions tell us that $H$ cannot exist, we disregrad them. In particular, we assumed ahead of time that $H$ works for *all* programs, including the ones that we might construct subsequently using $H$ itself. This is what it means to "work under a hypothesis".

Now, **using the assumption that $H$ exists**, we define $P$ and derive a contradiction. While we construct $P$ and think about how it works, we can use the standing assumption that $H$ always terminates and that it always answers correctly. It has to do so for $P$ as well because we assumed that it does for *all* programs. No amount of arguing will deny that assumption, no matter how counter-intuitive it is, because **we assumed so**.

Since our initial assumption of existence of $H$ lead to a contradiction, we may now **drop the assumption** that $H$ exists (we stop "working under a hypothesis") and conclude that $H$ does not exist.

# Answer
> 9 votes
First, let us see what the halting proof attempts to prove:

> There is no program $H$ that, on input $(x,y)$, always halts, and returns whether the program encoded by $x$ halts when run on the input $y$.

We call the function which $H$ is supposed to compute the *halting predicate*.

The program you are suggesting, which consists of simulating a run of program $x$ on input $y$, definitely doesn't always halt. What we are attempting to show is that there is no other devious way to computing the halting predicate in a way which does always halt.

The proof you are describing is a proof by contradiction. We *assume* that there is a program $H$ that always halts and computes the halting predicate correctly. Under this assumption, we reach a contradiction. Hence the conclusion is that no such program exists.

> How does $H$ know whether $x$ halts on $x$?

The assumption that the proof by contradiction is making is that there does exist an $H$ which computes the halting predicate. What the proof shows is that $H$ actually doesn't compute the halting predicate correctly. So $H$ cannot tell whether $x$ halts on $x$, and that is exactly what the proof shows.

> The answer is $H$ must simulate $x$ on $x$.

This is not true. There are similar predicates which can be computed. For example, we can decide whether a program halts on all inputs within 100 steps. We can do so even though there are infinitely many potential inputs, and so the naive solution, which is to run the program on all inputs for 100 steps, can be improved.

What the proof shows is that there is no computable way to decide whether a given program $x$ halts on a given input $y$. It doesn't show that $H$ must simulate $x$ on $y$; indeed, $H$ could store the answers for selected pairs $(x,y)$ in a table, and for these pairs it could just return the correct answer by doing a table lookup. This approach can only handle finitely many pairs $(x,y)$, and the proof shows that no other computable approach works.

# Answer
> 3 votes
In your "pseudo-code proof", you left out an essential bit. We try to prove that there is no machine H, which for every input x, y halts and outputs "yes" if the machine x halts with input y, and halts and outputs "no" if the machine x doesn't halt with input y.

We do a proof by contradiction: We assume that H exists, and we show this leads to a contradiction. And because the assumption that h exists leads to a contradiction, the assumption must be false, so we proved that H didn't exist.

So the question "How does H know whether x halts on x?" doesn't make sense. We *assume* that H correctly decides whether x halts on x. We have no idea how H might do that. Actually, we want to *prove* that H cannot do this for every x. But for our indirect proof, we assume H *can* do this.

Next you say "H must emulate x". Well, emulating a turing machine to see whether it halts or not won't let you decide if the turing machine doesn't halt because the emulation won't ever finish. So that's not a good approach. Whatever H does, it's not going to emulate x. It must do something clever. As intelligent humans, we can use intelligence to decide for many x, y whether program x halts with input y. Sometimes we fail. But that might be because of lack of intelligence, not a problem with the input. We could imagine that there is a H that is intelligent enough to make the correct decision for every x, y.

So now we run H(x,x) where x is the encoding of P.

Due to our assumption, we *know* that H (x, x) halts, and it returns "yes" if P(x) halts and "no" if P(x) doesn't halt. How do we know this? Because that's our assumption that we use for the contradiction proof.

Does P(x) halt or not halt? It either halts or it doesn't.

If P(x) halts, then it first calls H(x,x). H(x, x) figures out correctly that P(x) halts, so H(x,x) outputs "yes", P(x) detects that H(x,x) did output "yes", so P(x) loops forever and doesn't halt. There we have a contradiction.

If P(x) doesn't halt, then it first calls H(x,x). H(x, x) figures out correctly that P(x) doesn't halt, so H(x,x) outputs "no" and then halts, P(x) detects that H(x,x) did output "no", not "yes", so P(x) stops immediately and halts. There we have again a contradiction.

So both "P(x) halts" and "P(x) doesn't halt" lead to a contradiction, therefore our assumption is wrong, therefore H doesn't exist. Bingo.

Two mistakes in your proof: 1. You assume that a halting checker would have to simulate a Turing machine. That’s not necessary. Actually it would be unlikely to work. 2. You assume that a non-halting program would end in a repeating pattern. That isn’t true at all. A Turing machine has an infinite state, so it can continue running without any pattern emerging.

# Answer
> 2 votes
If H(x,x) goes into an infinite loop, then that fact *already* proves that H does not solve the halting problem. If H solves the halting problem, then it never goes into an infinite loop.

If we are trying to figure out whether it's possible to solve the halting problem, we can ignore all the functions that sometimes enter infinite loops. They obviously don't solve the halting problem. Then only the ones that *don't* enter infinite loops are left, and those ones are disproved using the function P that you showed.

---
Tags: complexity-theory, turing-machines, computability, halting-problem
---


# Question
Title: Why is M^e mod N the ciphertext and not just M^e
I watched a video on why the RSA algorithm works and it said that $(M^e \bmod N)^d \mod N = M^{ed} \bmod N$ which makes sense if $M^e$ is smaller than $N$.

Would $M^e$ not be smaller than $N$, the decryption wouldn't work(I know why but there's no reason to explain it here).

So why do we say that the ciphertext is $M^e \bmod N$ when $\bmod N$ falls away anyway.

And I've also seen examples where $M^e$ is way bigger than $N$ which leads me to believe that I misunderstood something.

Can someone help me out here?

# Answer
> 2 votes
If the ciphertext was just M^e, then

* The ciphertext would be much longer (e times more bits)
* Anyone with the public key could decrypt the message by calculating the e-th root, for example using the bisection method.

# Answer
> 1 votes
Suppose that $N = 11$, $M = 10$, and $e = 2$. You can see clearly that $M^e \> N$.

What does hold is that $(x \bmod N)^d \bmod N = x^d \bmod N$. This follows from the more general $(x \bmod N)(y \bmod N) \bmod N = xy \bmod N$, which you can try proving from the definitions.

# Answer
> 1 votes
First of all, an encryption scheme must have the **correctness requirement** $$Dec\_k (Enc\_k (m)) = m$$ In other words, whatever data you encrypted, you must get it back after the decryption. Otherwise, there is no use.

---

In RSA, we have the relation between public exponent $e$ and private exponent $d$ $$e \cdot d = 1 \bmod \varphi(N)$$ where $\varphi(N)= (p-1)(q-1)$, with $\varphi(N)$ is the Euler's Toitent function.

From Euler theorem we know that $a^x = x^{x \bmod \phi(n)} \bmod N$. This help to calculate the power faster $$M^{ed} \bmod N \equiv M^{ed \bmod \varphi(N)} \bmod N$$

> $(M^e \bmod N)^d \bmod N = M^{ed} \bmod N $

To see this, we can use the modulus property $a \equiv b \bmod n$ then there is $k \in \mathbb{Z}$ such that $ a = b + nk$.

With $M^e = t \bmod N$ we have $M^e - N\cdot k = t$ and then with $(M^e - N\cdot k)^d \bmod N$. If we expand the power this simplifies $$M^{ed} \bmod N$$ since, except this term, all others will vanish as they contain at least one $N$.

So, we don't care it is small or not during the calculation, it satisfies the correctness requirement.

---

**Note:** For TextBook RSA the small $e$ can make big problems like in the case $e=3$ (enables fast encryption or signature verification), this is commonly known as the cube-root attack. In practice, however, the textbook RSA is not used. It must be used with proper encryption paddings like PKCS#1 v1.5 (RSAES-PKCS1-v1\_5) or OAEP (RSAES-OAEP). With this padding, there is no problem with using small $e$'s like the common ones. $\\{3, 5, 17, 257, 65537\\}$. Similarly, for the RSA signature, we have RSASSA-PSS.

---
Tags: algorithms, cryptography
---


# Question
Title: Sum of a function Θ(g) with a function that is not O(g)
Consider g a function of n: $g(n)$.

Knowing that the function $f(n) \in Θ(g(n))$ and the function $h(n) \notin O(g(n))$, could we conclude anything, related to it's asymptotic behaviour, about $f(n) + h(n)$ with respect to $g(n)$?

Given that $f(n)$ is $Θ(g(n))$, I have that $f(n)$ grows *the same way as* $g(n)$.
Given that $h(n)$ is not $O(g(n))$, I have that $h(n)$ grows *more rapidly* compared to $g(n)$.

In my mind, at least, it seems like these two above observations are sufficient to conclude that $f(n) + h(n)$ grows (just like $h(n)$) more rapidly than $g(n)$ and, thus, $ f(n) + h(n) \in O(g(n))$, but I'm afraid it's a counterintuitive case or I'm missing something.

# Answer
> 0 votes
Suppose $f\in \Theta(g)$ and $h\notin \mathcal{O}(g)$. That means: $$\exists A\>0, B\>0, \forall n\geqslant 0, Ag(n) \leqslant f(n) \leqslant Bg(n)$$ and $$\forall C\>0, \exists n\geqslant 0, h(n) \> Cg(n)$$

Therefore, for all $C\>0$, there exists $n\geqslant 0$ such that $h(n) \> (C-A)g(n)$. We conclude that $f(n) + h(n) \> Ag(n) + (C-A)g(n) = Cg(n)$.

We just proved that $f +h\notin\mathcal{O}(g)$.

Note that I supposed here that all functions are positive.

---
Tags: complexity-theory, algorithm-analysis, asymptotics
---


# Question
Title: Trivial Proof that EXP = PSPACE(im 99% sure i'm doing somthing wrong.)
Generalized chess is EXPTIME complete\[1\]. Generalized chess is also PSPACE complete\[2\]. Therefore $EXPTIME = PSPACE$. This implies that $P \neq PSPACE$

This proof is probably wrong. I want to know what I did wrong. They are probably referring to different problems regarding chess. But here are my sources. I can't say if they are. Reading the first bit of the papers it sounds like they are describing problems that are similar if not the exact same, But they probably are not. Hopefully someone proves me wrong and I learn something.

If i'm not wrong then how did actual scientists miss this?

EDIT 1: The EXP-TIME paper says that it is determining a perfect strategy, the P SPACE paper is determining if a player has wining moves. IF you look at the start position of NXN chess, determining if a player has a series of winning moves is the same as a perfect strategy I think. Forgive any trivial errors here. I'm, very new to this. But want to learn.

---

references

\[1\]

Aviezri S. Fraenkel, David Lichtenstein

Computing a perfect strategy for n×n chess requires time exponential in n

https://link.springer.com/chapter/10.1007/3-540-10843-2\_23

\[2\]

http://rohitsharma.net/wp-content/uploads/2019/09/1-s2.0-0022000083900302-main.pdf

# Answer
> 2 votes
The first step is to read and understand the papers. It's not always enough to read just the introduction -- you often need to read the full paper, particularly the precise statement of results and their discussion. Reading the papers will help you discover what they each actually prove, and then you will discover why the two papers are actually consistent with each other. The researchers didn't miss anything; they already explained the answer to your question in their paper. Each paper considers a problem that is related to or can be considered as a generalization of chess; but they don't both consider the same problem.

In particular, the Storer paper specifically mentions Fraenkel's work and explains the difference between their two results. To quote:

> Although we have taken the view that exponentially long generalized chess games are not in the spirit of the 50-move draw rule, recently, Fraenkel and Lichtenstein \[4\] have shown that when exponentially long games are allowed, generalized chess is exponential-time complete.

See also the surrounding sentences for more explanation.

In short, it's not entirely clear what is the right way to generalize the 50-move rule, and what choice you make affects the complexity of the problem.

---
Tags: time-complexity, space-complexity
---


title: Expressivity of Polysize Decision Trees

text:
# Question
Title: Expressivity of Polysize Decision Trees
A *binary decision tree* (DT) is a binary tree whose internal nodes are labelled by boolean variables (with repetitions), and whose leaves are labelled either $0$ or $1$. The *size of a decision tree* is the number of branches (or equivalently the number of leaves).

A DT determines a unique Boolean function of the variables labelling the internal nodes: given an assignment of these variables, start at the root of the tree and take the left branch if the label is assigned $0$ and the right branch otherwise, and repeat until a leaf is reached; the value of the function is the label of the leaf. Any boolean function $f\colon \\{0,1\\}^n\to\\{0,1\\}$ can be represented by a DT with size $2^n$ (a complete tree where the $i^\text{th}$ level of internal nodes is labelled by variable $x\_i$).

---

**Question:** Is the class of languages recognisable by a family of polynomial-size decision trees known to be related to a ''natural'' class of single-output boolean circuits (*e.g.* **NC$^0$**, **TC$^0$**...)?

I am hoping for something analogous to Barrington's theorem \[Bar89\] for branching programs (which can be seen as an extension of DTs where ''tree'' is replaced by ''DAG'').

> The class of decision problems solvable by a family of polynomial-size, constant-width ($\geq 5$) branching programs is exactly (non-uniform) **NC$^1$**.

However, the existence of strong learning algorithms for DTs \[BLQT21\] leads me to believe I'm looking for far less expressive classes.

---

\[Bar89\] D. A. M. Barrington. Bounded-width polynomial-size branching programs can recognize exactly those languages in NC1, Journal of Computer and System Sciences 38:150-164, 1989.

\[BLQT21\] Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan: Properly learning decision trees in almost polynomial time. CoRR abs/2109.00637 (2021).

# Answer
> 2 votes
This is not an exact characterization, but the class of languages recognizable by poly-size DT is included in $\mathrm{AC}^0$, specifically within its second level: that is, any DT can be converted to a polynomially larger CNF and DNF. To see this, take $$\bigvee\_i\bigwedge\_jp\_{i,j},$$ where $i$ runs over all accepting leaves of the DT, and for each $i$, $p\_{i,j}$ enumerates literals corresponding to the decisions made on the path from the root to $i$.

---
Tags: circuits, decision-tree
---


title: Importance of $\Sigma^P_2=PSPACE$

text:
# Question
Title: Importance of $\Sigma^P_2=PSPACE$
Assuming (the unlikely scenario) that the Polynomial Hierarchy collapses to second level. Thus, $\Sigma\_2^p=PSPACE$.

How significant this result would be (broad consensus) as compared to the other open problems in TCS (the most important two being $P$ vs $NP$ and $NP$ vs $coNP$).

Most of the sources rightly point to the above two problems being the most important but despite most of the classes in complexity hierarchy falling under $PSPACE$, I am somewhat surprised not much has been discussed about it.

Is it something that is at the Turing Award or Breakthrough Prize level?

# Answer
> 1 votes
Since $\Sigma^{P}\_2 \subseteq PH \subseteq PSPACE$, then showing this will prove that $PH=PSPACE$, showing, for example, this important implication.

In addition, another immediate but important implication is that the polynomial hirarchy collapses to $\Sigma^P\_2$ \- which shows that there is no gain in "strength" by adding more alternations above only 3 alternations (using the definition of $\Sigma^P\_k$ as an alternating turing machine).

As $IP=PSPACE$, this might lead for some more room of thought whether the same statement can be said about interactive protocols - can it be said there exists some $r$ such that all of IP is contained in Arthur-Merlin protocols with only $r$ rounds (basically, is IP collapsing to AM with $r$ rounds)?

Therefore, yes - it definitely would be considered a big breakthrough.

---
Tags: complexity-theory
---


# Question
Title: Turing machine with infinite tape alphabet
Given is the modified definition of a TM where everything is equal except for one change: $\Gamma=\Sigma\cup \mathbb{N}\cup\\{\square\\}$

How do I prove that there is a TM $M$ for any language $L\subseteq\Sigma^\*$ while $\Sigma=\\{a,b\\}$ and $\Sigma\cap\mathbb{N}=\emptyset$ so that $T(M)=L$?

# Answer
> 1 votes
**First hint:** construct a TM that converts the input into a unique natural number

**Second hint:** encode the language directly in the turing machine, by specifying which natural number is considered a part of the language and which one isn't.

---
Tags: turing-machines
---


# Question
Title: What is the name of this content-addressing scheme?
Git seems to use the two most significant hex digits of a content hash as a directory name for content-addressable objects. The same two digits are left out of normal file names. I'm assuming the intent is to limit the size of directory listings, while maintaining a relationship between names and content.

```
objects
├── 01
│   └── db1550e888941883a96b63394f0fe65e892635
├── 02
│   └── 98cc41b182fca79597e9c3fa3fa033eb2673f1
├── 03
│   ├── aa0112ac4942a3f9c64cb6358a7319273e7a33
│   ├── af3aeb71ea5f86af5296f0825c15677c5923ad
│   └── ccc7640a6a7479b2cf566ba14ff4dc7fe773a9
├── 04
│   └── 5e0398efb428a5cfbaa9b65eaca82201638146
...

```

Does this pattern for content-addressable storage have a name independent of the hash function used?

# Answer
> 1 votes
This is a trie that is truncated to two levels.

---
Tags: terminology
---


# Question
Title: Unintuitive case in finding loop in linked list
Finding a loop in a linked list is a classic algorithm but I found an off-by one case that is making me question my sanity, this first solution works:

```
def findLoop(head):
    def p(s, f):
        print(f'slow: {s.value}, fast: {f.value}')

    slow = head.next
    fast = head.next.next

    while slow is not fast:
        p(slow, fast)
        slow = slow.next
        fast = fast.next.next

    p(slow, fast)
    slow = head
    while slow is not fast:
        p(slow, fast)
        slow = slow.next
        fast = fast.next
    return slow

```

This second one goes into an infinite loop since on the second while loop, the pointers never meet:

```
def findLoop(head):
    def p(s, f):
        print(f'slow: {s.value}, fast: {f.value}')

    slow = head
    fast = head.next

    while slow is not fast:
        p(slow, fast)
        slow = slow.next
        fast = fast.next.next

    p(slow, fast)
    slow = head
    while slow is not fast:
        p(slow, fast)
        slow = slow.next
        fast = fast.next
    return slow

```

Note that all that changed is the starting conditions: in the working solution we have `slow = head.next; fast = head.next.next`; while in the breaking solution we have: `slow = head; fast = head.next`. This change should not have a breaking effect and even though I can walk through it by had, I don't understand why it should happen, given that we only shift the starting conditions by one.

**Supplementary Material**

Ready to run example for experimenting:

```
class LinkedList:
    def __init__(self, value):
        self.value = value
        self.next = None

def findLoop(head):
    def p(s, f):
        print(f'slow: {s.value}, fast: {f.value}')

    slow = head.next
    fast = head.next.next

    while slow is not fast:
        p(slow, fast)
        slow = slow.next
        fast = fast.next.next

    p(slow, fast)
    slow = head
    while slow is not fast:
        p(slow, fast)
        slow = slow.next
        fast = fast.next
    return slow

case =  [
      {"id": "0", "next": "1", "value": 0},
      {"id": "1", "next": "2", "value": 1},
      {"id": "2", "next": "3", "value": 2},
      {"id": "3", "next": "4", "value": 3},
      {"id": "4", "next": "5", "value": 4},
      {"id": "5", "next": "6", "value": 5},
      {"id": "6", "next": "7", "value": 6},
      {"id": "7", "next": "8", "value": 7},
      {"id": "8", "next": "9", "value": 8},
      {"id": "9", "next": "4", "value": 9}
    ]

def create(case):
    for c in case:
        c['node'] = LinkedList(c['value'])
    for c in case:
        c['node'].next = case[int(c['next'])]['node']
    return case[0]['node']

def test():
    head = create(case)
    findLoop(head)

test()

```

# Answer
I am delighted to see another example of the infamous off-by-one error.

---

"All that changed is the starting conditions". "This change should not have a breaking effect" since "we only shift the starting conditions by one." Well, as D.W. implied in his comment, that change does have a breaking effect!

With that shifting change, the node where `slow` and `fast` meet at the end of first `while` in the right version of `findLoop` is not the same as that in the wrong version of `findLoop`. In fact, they meet one node earlier in the wrong version than in the correction version. That means, the distance between `head` and `fast` at the end of the first `while` in the wrong version is one less than that distance in the right version. Since `slow` is reset to `head` before the start of the second `while` in both version, the distance between `slow` and `fast` at the start of the second `while` in the wrong version is one less than that distance in the right version.

For the second `while` to end, the distance between `slow` and `fast` must be a multiple of the period of the loop of the linked list. So the second `while` will go forever in the wrong version of `findLoop`, as long as the period is not $1$.

---

**Exercise** (easy): Assume that there is a loop in the linked list and that `head.next != head.next.next`. Explain why the node where `slow` and `fast` meet at the end of first `while` in the wrong version of `findLoop` is one node earlier than that node in the correction version, i.e. the next node of the former node is the latter node.
> 2 votes

---
Tags: algorithms
---


# Question
Title: What are the fundamentals of calculating space complexity in loops?
Imagine you loop n times, and every iteration you create a string of space n with scope only within that iteration (thus it is no longer accessible in the next iteration). I would look and say that I use O(n^2) space because, for n iterations, I use n space.

However, logically, if every loop you destroy the previous iteration's string (of n space) and overwrite it with this iteration's string (of n space), throughout the entire loop, you would only be using O(n) space. I am confused about whether to confirm O(n) or O(n^2) space?

Take this example:

```
s = "hello"
for _ in range(len(s)):
    newString = s[:]
return newString

```

I am primarily asking this question for the space of a DS + Algo interview.

# Answer
> 6 votes
I can't answer that question reliably, because it depends on the behavior of the memory allocator in Python, and I don't think we're provided any guarantees about that. The memory allocator might deallocate the space after the function returns, or it might deallocate in every iteration.

What we can say is that it is possible to implement this algorithm using $O(n)$ space, and it is possible to implement it in a way that uses $O(n^2)$ space. If we were presented with an algorithm (not with code) and we cared about space, one might reasonably make the implicit assumption that you will implement it in a way that uses $O(n)$ space and thus describe the algorithm as having $O(n)$ space complexity.

---
Tags: algorithms, data-structures, space-complexity, python
---


# Question
Title: Combination of two Languages in a arbitrary complexity class
Given two unrelated languages $L\_0$ and $L\_1$ contained in some complexity class $C$. Is the language $L\_x=L\_0\times L\_1= \\{(x,y)|x\in L\_0, y\in L\_1\\}$ always contained in $C$?

And if that is the case, can we just extend this recursively and create a single language $(L\_{All})$ from all other languages contained in $C$ (even if the count of languages in $C$ is infinite)? Is the language $L\_{All}$ always contained in $C$ as well?

# Answer
The answer depends on the class $C$. Many classes will be closed under your operation, but some are not. For example, DCFL, the class of all deterministic context-free language, is not. To show this, we slightly adapt the counterexample in this answer. Define $$ L\_A = \\{ a^i b^j c^k : i \neq j \\}; L\_B = \\{ a^i b^j c^k : j \neq k \\}; L\_1 = \\{ ,w : w \in L\_A \\} \cup L\_B; L\_0 = \\; ,^\* $$ The languages $L\_0$ and $L\_1$ are both DCFL. Let $L\_x = L\_0 \times L\_1$ be their product. Suppose that $L\_x$ were DCFL. Then so would $L\_y = \\{ w : (w) \in L\_x \\}$ be, since DCFL is closed under quotient. Since DCFL is closed under intersection with a regular language, $L\_z = L\_y \cap \\, ,,(a+b+c)^\*$ would be DCFL. Notice that $L\_z = \\, ,, (L\_A \cup L\_B)$. Again using closure under quotient, it would follow that $L\_A \cup L\_B$ is DCFL, but that is known to be false.
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Max-flow from a to c is at least the minimum of max-flow from a to b and max-flow from b to c
Given a directed weighted graph $G = (V, E, w)$, we refer to the max flow when $x$ is the source and $y$ is the sink in the flow network of the graph $G$ as $f\_{x,y}$.

I'm searching for a formal proof for the following inequality:

$$f\_{a,c} \ge \min (f\_{a,b},\\,f\_{b,c}).$$

I'm pretty sure that the proof relies on the max-flow min-cut sentence but I just don't know how to write the proof or formalize it.

# Answer
> 2 votes
Here is a formal proof, thanks to your hint of the max-flow min-cut theorem.

---

Let us treat $G$ directly as a network with capacity function $w$.

Suppose we are given three arbitrary nodes $a, b, c$ in $V$. Select a minimum $a$-$c$ cut of $G$, $(S, T)$. Let $w(S,T)$ be the capacity of $(S,T)$ as a cut of $G$, i.e. $$w(S,T)=\sum\_{u\in S, v\in T} w(u,v).$$ Note that $w(S,T)$ is exactly the same as the capacity of $(S,T)$ as an $s$-$t$ cut for whichever choice of node $s$ in $S$ and whichever choice of node $t$ in $T$.

Consider $G$ as a flow network with source $a$ and sink $c$. Since $(S,T)$ is a minimum $a$-$c$ cut, the max-flow min-cut theorem tells us $$ f\_{a,c}=w(S,T).$$

Since $S$ and $T$ together include all nodes, $b$ must be either in $S$ or in $T$.

* $b\in S$. Then $(S,T)$ is also a $b$-$c$ cut. Consider $G$ as a flow network with source $b$ and sink $c$. The max-flow min-cut theorem tells us $$ f\_{b,c}\le w(S,T).$$
* $b\in T$. Then $(S,T)$ is also an $a$-$b$ cut. Consider $G$ as a flow network with source $a$ and sink $b$. The max-flow min-cut theorem tells us $$ f\_{a,b}\le w(S,T).$$

So, in all cases, we have $$\min(f\_{a,b}, f\_{b,c})\le w(S,T)=f\_{a,c}.$$

---
Tags: network-flow, minimum-cuts
---


# Question
Title: Are there any algorithms that decide if a PDA (pushdown automaton) accepts a sentence?
Most computation theory textbooks just mention the equivalence of PDAs and Context Free Grammars. I'm able to construct a PDA from a given CFG, but find it very difficult to write an algo to check if a PDA accepts a string or not. Some would recommend the CYK algorithm, but that's for a CFG in CNF, not for a PDA. If there is no algorithm for us to use it, why would we need to invent PDAs? I also find that materials on this subject is suprisingly scarce on the Internet.

Some would suggest me to run the PDA by feeding input symbol to it and see if it accepts by empty stack or final state. But because a PDA may contain multiple transitions relevant to an input symbol, it's us who have to choose among these transitions and that's not an algorithm (which must be completely automatic). That's utilizing our own observation and thinking.

# Answer
> 3 votes
Yes, there are. There is an algorithm that, given any PDA $P$ and any input word $x$, directly checks whether $x$ is accepted by $P$, without first converting $P$ to a CFG. The algorithm takes running time $O(n^3)$ (treating the size of $P$ as a constant that is absorbed into the big-O notation).

The idea is that, given a PDA $P$, we can compute a representation of the set of all possible configurations of the PDA on all possible inputs. This set is traditionally denoted $\text{post}^\*(P)$. It is typically an infinite set (thanks to the $\epsilon$-transitions in $P$), but we are rescued by the following beautiful property: $\text{post}^\*(P)$ is always a regular language. Therefore, it can be represented by a NFA. Moreover, there is an efficient algorithm to compute a NFA that represents $\text{post}^\*(P)$, given $P$.

Now, given an input word $x$, we construct a DFA $D$ that accepts only $x$ and no other word. Then, we use the product construction to construct a PDA $Q$ that accepts an input word iff both $P$ and $D$ accept that word. Next, we compute $\text{post}^\*(Q)$ using the aforementioned algorithm. Finally, we check whether $\text{post}^\*(Q)$ contains any accepting configuration (i.e., a configuration where both $P$ and $D$ accept); this is straightforward since we have a representation of $\text{post}^\*(Q)$ as a NFA.

The theory has been worked out in the model checking community. You can find an overview of the foundations and references where you can learn more, in Section 2.2.2 (Pushdown Systems) of the following survey paper (there are probably many other expositions as well):

Analysis Techniques for Information Security. Anupam Datta, Somesh Jha, Ninghui Li, David Melski, and Thomas Reps. Synthesis Lectures on Information Security, Privacy, and Trust, 2010 April 27, vol 5, no 1, pages 1--164. (access via Springer, Google Books, or Internet Archive)

The resulting algorithm has various nice properties. For instance, if you work through what the construction is doing, you can convert it to an online algorithm that reads one symbol of the input at a time and then updates the set of reachable configurations, in case that is helpful to you. It is possible to view this as a generalization of Tomita's algorithm for GLR parsing, except that Tomita's algorithm only works if the PDA is a LR parser, while the above works for any PDA.

# Answer
> 0 votes
Given a pushdown automaton $A = (Q, \Sigma, \Gamma, \delta, q\_0, Z\_0, F)$, define a *configuration* as a couple $(q, \gamma)$, with $q\in Q$ and $\gamma\in \Gamma^\*$. A configuration represents the state $q$ of the PDA, and the stack word $\gamma$.

If there are no $\varepsilon$-transition (and you can always find such a PDA), given a word $u$, you can decide if $u$ is accepted by $A$ by computing the **set** of possible configurations reachable from $(q\_0, Z\_0)$ by reading $u$, and verifying if this set contains an accepting configuration (either by final state or empty stack, depending on the PDA).

This can be done in polynomial time in the size of $u$.

This is a similar method to the one to decide if a word is accepted by a non-deterministic finite automaton.

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


# Question
Title: Minimum steps needed to partially cover a sequence of points on a grid
**Problem statement:** You are in a 2D grid where you can move in any of the 4 directions, no obstacles. You start at position (0, 0).

We say that you partially cover a point $(x,y)$ if your position has the same abscissa or the same ordinate (or both).

You are given an ordered sequence of n points $(x\_1,y\_1), ..., (x\_n,y\_n)$, which you need to partially cover in that order. Find the distance of shortest path which partially covers the sequence of points.

Constraints (just to give an order of magnitude): $n=20 000$ and $0\<=x,y\<=5000$, and time execution should be \<5s.

**My approach:**

At first I thought this might be a dynamic programming problem. But now I just don't see how it could be applied.

*Brute force approach*: Starting from $(0, 0)$ there are only two good paths that cover the first point $(x\_1, y\_1)$: go to $(x\_1, 0)$ or $(0, y\_1)$.

Then there are only four paths that are good candidates to cover the 1st, and 2nd point:

* $(x\_1, 0)-\>(x\_2,0)$
* $(x\_1, 0)-\>(x\_2,y\_1)$
* $(0, y\_1)-\>(0, y\_2)$
* $(0, y\_1)-\>(x\_1, y\_2)$.

And so on. We can explore the tree of all good possible paths, where at the step n, we can choose between $2^n$ paths. Of course we only need to keep track for each path of its final position and the total distance.

*Pruning exploration approach*: Now my idea is to do this exploration, in breadth-first order (BFS exploration), but with some pruning. At each step I can eliminate some possibilities. Indeed consider two paths, which both cover the first $n$ points.

* path $p$ with last position $(p\_x, p\_y)$ and total distance $p\_d$,
* and path $q$ with last position $(q\_x, q\_y)$ and total distance $q\_d$,
* If $p\_d \> q\_d + abs(q\_x-p\_x)+abs(q\_y-p\_y)$, then we know for certain that the path $p$ is worse than path $q$, no matter what is the position of the next point $(x\_{n+1}, y\_{n+1})$
* I can then eliminate at each depth of the BFS all the possibilities for which that last condition is true
* Issue: this pruning does eliminate a lot of possibilities, but not enough it seems.

**Question1**: Does this problem have a name? I think it can be re-stated as a linear integer programming optimisation problem. Or it may be re-formulated as some kind of vertex cover problem?

**Question2**: Can I improve my solution? More clever pruning, change exploration strategy (Depth-first-search, something else)? Is there a different, better approach?

# Answer
There is a straightforward dynamic programming algorithm. You only need to know, for each $i,j$, the length of the shortest path to $(x\_i,y\_j)$ that covers the first $i$ points, and the length of the shortest path to $(x\_j,y\_i)$ that covers the first $i$ points. I'll let you discover why that suffices.

You should be able to take it from here. See our resources on dynamic programming for a systematic framework for approaching dynamic programming algorithms: https://cs.stackexchange.com/tags/dynamic-programming/info
> 1 votes

---
Tags: algorithms, optimization, dynamic-programming, combinatorics, depth-first-search
---


# Question
Title: Where is actually ASCII is stored in computer?
1. I am learning some basics in computer. In that in ASCII I read if 65 is A .
2. When we pressing key A what is happening next? Is the electric signal is passing as on & off & reaching to decimal part 65 (or) directly converted to binary?
3. If it is reaching 65 then which location character map (or) encoding is available?

Please clarify. I have more questions in computer basics. I want to understand computer basics.

# Answer
Your keyboard isn't going to send anything indicating the letter "a". It will send for example that the second key in the fourth row of my keyboard has been pressed.

Your keyboard is most likely connected through USB. Part of the USB standard is describing how a USB device identifies itself as a keyboard, and how a USB keyboard tells the device on the other end what keys were pressed. It will also tell the computer the physical layout of the keys.

The operating system on your computer will take multiple bits of information: What physical keyboard layout, what keyboard language the user has chosen (if the language is set to French, a different key is used for the letter a), what other keys are pressed at the same time (shift, shift-lock, control, option, command, function), what keys have been pressed before (pressing the "a" key together with the shift-key after pressing option and "u" will create a letter "Ä" on my computer).

Oh, by the way, "Ä" is not an ASCII character. And there are letters like ®†¥øπ etc.
> 1 votes

# Answer
Everything *always* works in binary. ASCII, is just a way to interpret the binary into letters and numbers.

The decimal part of ascii (such as the value $65$ being equivalent to $a$) is just for the purpose of human readability, since binary isn't as natural to humans as decimal numbers
> 0 votes

# Answer
The basic element of computing machines as we know them, is an array of binary digits - a series of 0s or 1s. These binary digit arrays are the *only* symbols that a general purpose computer is capable of storing or processing at the hardware level.

All of us are presumably familiar with decimal numbers and with mathematical operations done in decimal. Implementing the mechanics of the decimal system using binary is relatively straightforward.

The problem is that working consistently in binary - inputting binary on keyboards, and reading binary on display screens - is not convenient for the human users of computers.

A computer is efficient at working with just two digits - 0 and 1 - in a variety of sequential configurations. Humans prefer to work with a wider variety of characters in much shorter sequences, and binary is very inefficient to process by any other means than a computer.

The question then is how you represent a wider variety of characters, such as those we use for natural language, and also decimal digits, using a computer?

The answer is that native binary symbols are assigned to represent characters on a fairly arbitrary basis.

Using the ASCII encoding, the native symbol `1000001` (which rendered as a decimal number would be 65) is assigned to represent the character `A`.

When you press `A` on the keyboard, the native symbol `1000001` is submitted to and stored by the computer. And when the computer stores `1000001` in the video memory on a text-based terminal, the display renders that native symbol back out to the screen as character `A`.

Similarly, for a printer like a dot-matrix or a daisy-wheel, sending the symbol `1000001` causes them to imprint the pattern, or strike the character, of `A`.

By being consistent at all times, end-to-end, the user never sees any native binary symbols - he simply reads and writes in the characters he is familiar with.

For graphical (non-text based) interfaces and modern printers, the actual process is somewhat more complicated, involving many more layers of translation. But the essential situation is still the same - you press `A` on the keyboard and that will likely find its way into main memory (or disk storage) represented natively as `1000001`. And when the same symbol is displayed or printed, it's translated back into a visual representation of the character `A`.
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: How do I determine the time and space complexity of the following algorithm?
I need to compute the time and space complexity in Big O notation for this algorithm I constructed for binary multiplication.

```
mul(a, b) =

 - 0 if a = 0 or b = 0
 - (b + p) if lowest(a) != 0
 - p if lowest(a) = 0

```

where

* **p = join(mul(higher(a), b), 0)**
* **lowest(a) returns the lowest order bit of a binary numeral a**

e.g. lowest(1001101) = 1

* **higher(a) returns the binary numeral excluding the lowest order bit of binary numeral a**

e.g. higher(1001101) = 100110

* **join(a, b) appends bit b at the end of binary numeral a**

e.g. join(1101, 1) = 11011

# Answer
It's a recursive algorithm. Each time you call mul (through the use of p) you decrease the number of bits of 'a' by one. So the time complexity is the number of bit in 'a'. And since the number of bits equals the log of the value of 'a', so the recursion depth is Log(a).

In each step of the recursion you might perform an add operation of Max(Log(b),Log(a)) bits.

So the time complexity is O(Log(a)\*Max(Log(b), Log(a)))

If a and b are roughly the same size you will get O(Log(a)^2)
> 0 votes

---
Tags: algorithms, time-complexity, space-complexity, arithmetic, binary
---