title: Is C actually Turing-complete?

text:
# Question
Title: Is C actually Turing-complete?
I was trying to explain to someone that C is Turing-complete, and realized that I don't actually know if it is, indeed, technically Turing-complete. (C as in the abstract semantics, not as in an actual implementation.)

The "obvious" answer (roughly: it can address an arbitrary amount of memory, so it can emulate a RAM machine, so it's Turing-complete) isn't actually correct, as far as I can tell, as although the C standard allows for size\_t to be arbitrarily large, it must be fixed at some length, and no matter what length it is fixed at it is still finite. (In other words, although you could, given an arbitrary halting Turing machine, pick a length of size\_t such that it will run "properly", there is no way to pick a length of size\_t such that all halting Turing machines will run properly)

So: is C99 Turing-complete?

# Answer
> 41 votes
I'm not sure but I think the answer is no, for rather subtle reasons. I asked on Theoretical Computer Science a few years ago and didn't get an answer that goes beyond what I'll present here.

In most programming languages, you can simulate a Turing machine by:

* simulating the finite automaton with a program that uses a finite amount of memory;
* simulating the tape with a pair of linked lists of integers, representing the content of the tape before and after the current position. Moving the pointer means transferring the head of one of the lists onto the other list.

A concrete implementation running on a computer would run out of memory if the tape got too long, but an ideal implementation could execute the Turing machine program faithfully. This can be done with pen and paper, or by buying a computer with more memory, and a compiler targeting an architecture with more bits per word and so on if the program ever runs out of memory.

This doesn't work in C because it's impossible to have a linked list that can grow forever: there's always some limit on the number of nodes.

To explain why, I first need to explain what a C implementation is. C is actually a family of programming languages. The ISO C standard (more precisely, a specific version of this standard) defines (with the level of formality that English allows) the syntax and semantics a family of programming languages. C has a lot of *undefined behavior* and *implementation-defined behavior*. An “implementation” of C codifies all the implementation-defined behavior (the list of things to codify is in appendix J for C99). Each implementation of C is a separate programming language. Note that the meaning of the word “implementation” is a bit peculiar: what it really means is a language variant, there can be multiple different compiler programs that implement the same language variant.

In a given implementation of C, a byte has $2^{\texttt{CHAR\_BIT}}$ possible values. All data can represented as an array of bytes: a type `t` has at most $2^{\texttt{CHAR\_BIT} \times \texttt{sizeof(t)}}$ possible values. This number varies in different implementations of C, but for a given implementation of C, it's a constant.

In particular, pointers can only take at most $2^{\texttt{CHAR\_BIT} \times \texttt{sizeof(void\*)}}$ values. This means that there is a finite maximum number of addressable objects.

The values of `CHAR_BIT` and `sizeof(void*)` are observable, so if you run out of memory, you can't just resume running your program with larger values for those parameters. You would be running the program under a different programming language — a different C implementation.

If programs in a language can only have a bounded number of states, then the programming language is no more expressive than finite automata. The fragment of C that's restricted to addressable storage only allows at most $n \times 2^{\texttt{CHAR\_BIT} \times \texttt{sizeof(void\*)}}$ program states where $n$ is the size of the abstract syntax tree of the program (representing the state of the control flow), therefore this program can be simulated by a finite automaton with that many states. If C is more expressive, it has to be through the use of other features.

C does not directly impose a maximum recursion depth. An implementation is allowed to have a maximum, but it's also allowed not to have one. But how do we communicate between a function call and its parent? Arguments are no good if they're addressable, because that would indirectly limit the depth of recursion: if you have a function `int f(int x) { … f(…) …}` then all the occurrences of `x` on active frames of `f` have their own address and so the number of nested calls is bounded by the number of possible addresses for `x`.

A C program can use non-addressable storage in the form of `register` variables. “Normal” implementations can only have a small, finite number of variables that don't have an address, but in theory an implementation could allow an unbounded amount of `register` storage. In such an implementation, you can make an unbounded amount of recursive calls to a function, as long as its argument are `register`. But since the arguments are `register`, you can't make a pointer to them, and so you need to copy their data around explicitly: you can only pass around a finite amount of data, not an arbitrary-sized data structure that's made of pointers.

With unbounded recursion depth, and the restriction that a function can only get data from its direct caller (`register` arguments) and return data to its direct caller (the function return value), you get the power of **deterministic pushdown automata**.

I can't find a way to go further.

(Of course you could make the program store the tape content externally, through file input/output functions. But then you wouldn't be asking whether C is Turing-complete, but whether C plus an infinite storage system is Turing-complete, to which the answer is a boring “yes”. You might as well define the storage to be a Turing oracle — call `fopen("oracle", "r+")`, `fwrite` the initial tape content to it and `fread` back the final tape content.)

# Answer
> 14 votes
C99's addition of `va_copy` to the variadic argument API may give us a back door to Turing-completeness. Since it becomes possible to iterate through a variadic arguments list more than once in a function other than the one that originally received the arguments, `va_args` can be used to implement a pointerless pointer.

Of course, a real implementation of the variadic argument API is probably going to have a pointer somewhere, but in our abstract machine it can be implemented using magic instead.

Here's a demo implementing a 2-stack pushdown automaton with arbitrary transition rules:

```
#include <stdarg.h>
typedef struct { va_list va; } wrapped_stack; // Struct wrapper needed if va_list is an array type.
#define NUM_SYMBOLS /* ... */
#define NUM_STATES /* ... */
typedef enum { NOP, POP1, POP2, PUSH1, PUSH2 } operation_type;
typedef struct { int next_state; operation_type optype; int opsymbol; } transition;
transition transition_table[NUM_STATES][NUM_SYMBOLS][NUM_SYMBOLS] = { /* ... */ };

void step(int state, va_list stack1, va_list stack2);
void push1(va_list stack2, int next_state, ...) {
    va_list stack1;
    va_start(stack1, next_state);
    step(next_state, stack1, stack2);
}
void push2(va_list stack1, int next_state, ...) {
    va_list stack2;
    va_start(stack2, next_state);
    step(next_state, stack1, stack2);
}
void step(int state, va_list stack1, va_list stack2) {
    va_list stack1_copy, stack2_copy;
    va_copy(stack1_copy, stack1); va_copy(stack2_copy, stack2);
    int symbol1 = va_arg(stack1_copy, int), symbol2 = va_arg(stack2_copy, int);
    transition tr = transition_table[state][symbol1][symbol2];
    wrapped_stack ws;
    switch(tr.optype) {
        case NOP: step(tr.next_state, stack1, stack2);
        // Note: attempting to pop the stack's bottom value results in undefined behavior.
        case POP1: ws = va_arg(stack1_copy, wrapped_stack); step(tr.next_state, ws.va, stack2);
        case POP2: ws = va_arg(stack2_copy, wrapped_stack); step(tr.next_state, stack1, ws.va);
        case PUSH1: va_copy(ws.va, stack1); push1(stack2, tr.next_state, tr.opsymbol, ws);
        case PUSH2: va_copy(ws.va, stack2); push2(stack1, tr.next_state, tr.opsymbol, ws);
    }
}
void start_helper1(va_list stack1, int dummy, ...) {
    va_list stack2;
    va_start(stack2, dummy);
    step(0, stack1, stack2);
}
void start_helper0(int dummy, ...) {
    va_list stack1;
    va_start(stack1, dummy);
    start_helper1(stack1, 0, 0);
}
// Begin execution in state 0 with each stack initialized to {0}
void start() {
    start_helper0(0, 0);
}

```

Note: If `va_list` is an array type, then there are actually hidden pointer parameters to the functions. So it would probably be better to change the types of all `va_list` arguments to `wrapped_stack`.

# Answer
> 3 votes
## Nonstandard arithmetic, maybe?

So, it seems that the issue is the finite size of `sizeof(t)`. However, I think I know a work around.

As far as I know, C does not require an implementation to use the standard integers for its integer type. Therefore, we could use a non-standard model of arithmetic. Then, we would set `sizeof(t)` to some nonstandard number, and now we will never reach it in a finite number of steps. Therefore, the length of the Turing machines tape will always be less than the "maximum", since the maximum is literally impossible to reach. `sizeof(t)` simply is not a number in the regular sense of the word.

This is one technicality of course: Tennenbaum's theorem. It states that the only computable model of Peano arithmetic is the standard one, which obviously would not do. However, as far as I know, C does not require implementations to use data types that satisfy the Peano axioms, nor does it require the implementation to be computable, so this should not be an issue.

What should happen if you try to output a nonstandard integer? Well, you can represent any nonstandard integer using a nonstandard string, so just stream digits from the front of that string.

# Answer
> 2 votes
The answer is yes, but for an unexpected reason.

I believe the above comments are correct — given `size_t` is bounded, you cannot represent a turing machine with unbounded states by using C *as intended*. However, we can use C in a way which completely circumvents the `size_t` issue — using only the C preprocessor.

I will not go over the whole proof here — this answer explains it best. Essentially, using deferred expressions it is possible to create recursively expanding macros that expand **forever.** In this way, the depth of the recursion becomes limited only to the number of scans which the machine executes — this is a physical limitation, but in theory the machine could scan forever. The answer also explains how logical operations can be constructed.

So in conclusion: yes, C is turing-complete, but you have to totally misuse the preprocessor.

# Answer
> 1 votes
IMO, a strong limitation is that the addressable space (via the pointer size) is finite, and this is unrecoverable.

One could advocate that memory can be "swapped to disk", but at some point the address information will itself exceed the addressable size.

# Answer
> 0 votes
You could define a language quite similar to C, where it is allowed to change sizeof, for example by assigning

```
sizeof(int) = 20;
sizeof(void*) += 4;

```

etc. That would be Turing complete. As your requirements go up, you would just modify sizeof(void\*) to be sufficiently large, same with sizeof(size\_t), and then you can use realloc to make your arrays bigger.

# Answer
> -1 votes
Removable media allows us to circumvent the unbounded memory problem. Perhaps people will think this is an abuse, but I think it's OK and essentially unavoidable anyway.

Fix any implementation of a universal Turing machine. For the tape, we use removable media. When the head runs off the end or beginning of the current disc, the machine prompts the user to insert the next or previous one. We can either use a special marker to denote the left end of the simulated tape, or have a tape that's unbounded in both directions.

The key point here is that everything the C program must do is finite. The computer only needs enough memory to simulate the automaton, and `size_t` only needs to be big enough to allow addressing that (actually rather small) amount of memory and on the discs, which can be of any fixed finite size. Since the user is only prompted to insert the next or previous disc, we don't need unboundedly large integers to say "Please insert disc number 123456..."

I suppose the principal objection is likely to be to the involvement of the user but that seems to be unavoidable in any implementation, because there seems to be no other way of implementing unbounded memory.

# Answer
> -1 votes
The problem isn’t that computers, being limited by the real world, cannot implement a Turing-complete machine. The problem in this question here is that the C language itself doesn’t allow it.

The C language could easily be changed to be Turing complete. Adding an integer type of unlimited size that can be used in malloc() and in pointer arithmetic would have solved the problem. In practice it wouldn’t make any difference, since we can’t even build a computer where 64 bit pointer sizes are the limit.

# Answer
> -3 votes
In practice, these restrictions are irrelevant to Turing completeness. The real requirement is to allow the tape to be arbitrary long, not infinite. That would create a halting problem of a different kind (how does the universe "compute" the tape?)

It's as bogus as saying "Python isn't Turing complete because you can't make a list infinitely large".

\[Edit: thanks to Mr. Whitledge for clarifying how to edit.\]

# Answer
> -3 votes
# Choose `size_t` to be infinitely large

You could choose `size_t` to be infinitely large. Naturally, it is impossible to realize such an implementation. But that's no surprise, given the finite nature of the world we live in.

# Practical Implications

But even if it were possible to realize such an implementation, there would be practical issues. Consider the following C statement:

```
printf("%zu\n",SIZE_MAX);

```

This prints a decimal representation of `SIZE_MAX` to standard out. Presumably, `SIZE_MAX` is $O(2^{size\\\_t})$. So if `size_t` is infinitely large, `SIZE_MAX` is also infinitely large. The only way I know to print a decimal form of an infinitely large number is to produce an infinite stream of decimal digits. This means that `printf` will not terminate in some cases.

Fortunately, for our theoretical purposes, I could not find any requirement in the specification that guarantees `printf` will terminate for all inputs. So, as far as I am aware, we do not violate the C specification here.

# On Computational Completeness

It still remains to *prove* that our theoretical implementation is Turing Complete. We can show this by implementing "any single-taped Turing Machine".

Most of us have probably implemented a Turing Machine as a school project. I won't give the details of a specific implementation, but here's a commonly used strategy:

* The number of states, number of symbols, and state transition table are fixed for any given machine. So we can represent states and symbols as numbers, and the state transition table as a 2-dimensional array.
* The tape can be represented as a linked list. We can either use a single double-linked list, or two single-linked lists (one for each direction from the current position).

Now let's see what's required to realize such an implementation:

* The ability to represent some fixed, but arbitrarily large, set of numbers. In order to represent any arbitrary number, we choose `MAX_INT` to be infinite as well. (Alternatively, we could use other objects to represent states and symbols.)
* The ability to construct an arbitrarily large linked list for our tape. Once again, there is no finite limit on the size. This means we cannot construct this list up-front, as we would spend forever just to construct our tape. But, we can construct this list incrementally if we use dynamic memory allocation. We can use `malloc`, but there's a little more we must consider:
    + The C specification allows `malloc` to fail if, e.g., available memory has been exhausted. So our implementation is only truly universal if `malloc` never fails.
    + However, if our implementation is run on a machine with infinite memory, then there is no need for `malloc` to fail. Without violating the C standard, our implementation will guarantee that `malloc` will never fail.
* The ability to dereference pointers, lookup array elements, and access the members of a linked list node.

So the above list is what is necessary to implement a Turing Machine in our hypothetical C implementation. These features must terminate. Anything else, however, may be allowed to not terminate (unless required by the standard). This includes arithmetic, IO, etc.

# Answer
> -3 votes
The problem here is that you're artificially limiting the set of C programs to just the ones that use pointers (and size\_t, intptr\_t, what have you), but that's not necessary. If you're forced to use only the standard library, then "no" is *kinda* correct like in the accepted answer, but the **semantics** of C are indeed Turing complete.

Say you have a Real Turing Machine (TM) and it provides a library for pushing and popping from two stacks of unbounded size, and (for thoroughness) lets also say that they just compile to push and pop assembler instructions. Now your C program can push and pop infinitely to two stacks, unrestrained by the semantics of C. Et voila, Turing completeness.

This is not the only way we can show that C is Turing complete, and it turns out that this is not a high bar to meet for programming languages. The real challenge is in constructing a language that is *not* turing complete (e.g. SQL), and giving a proof for it.

Note: Other answers seem to suggest that Turing completeness requires arbitrary memory access, but that's simply not true. A push-down automaton with two unbounded stacks is sufficient, hence the scenario above.

# Answer
> -3 votes
**Mapping "C" to a Turing equivalent abstract model of computation**

C as it currently exists is not Turing complete because C inherently requires some fixed pointer size. We can however map a C like language to an abstract model of computation that is Turing complete.

The basic syntax and semantics of C could be mapped to an abstract model of computation that is Turing equivalent. The RASP model of computation is a model that "C" can be mapped to.

A variation of the RASP model is shown below that the x86/x64 language maps to. Since it is already known that "C" maps to the x86/x64 concrete models of computation we know that "C" maps to the following abstract model:

```
Instruction
     : INTEGER ":" OPCODE                     // Address:Opcode
     | INTEGER ":" OPCODE INTEGER             // Address:Opcode Operand
     | INTEGER ":" OPCODE INTEGER "," INTEGER // Address:Opcode Operand, Operand
HEXDIGIT [a-fA-F0-9]
INTEGER  {HEXDIGIT}+
OPCODE   HEXDIGIT{4}
// OPCODE distinguishes between INTEGER literal and machine address operand.
// OPCODE INTEGER is space delimited.

```

**Mapping the C language to the above abstract model of computation would enable the C language to become equivalent to a Turing machine.**

Because the x86/x64 language maps to the above abstract model this also provides the basis for recognizing the subset of Turing equivalent x86/x64/C computations. As long as the required pointer size is no larger than the pointer size that is available the computation is Turing equivalent on finite hardware.

Turing equivalent computations derive equivalent output or fail to halt on equivalent input between the concrete machine and its Turing machine equivalent.

# Answer
> -4 votes
The main argument here was that the size of the size\_t is finite, although can be infinitely large.

There is a workaround for it, though I am not sure if this coincides with ISO C.

Assume you have a machine with infinite memory. Thus you are not bounded for pointer size. You still have your size\_t type. If you ask me what is sizeof(size\_t) the answer will be just sizeof(size\_t). If you ask if it is greater than 100 for example the answer is yes. If you ask what is sizeof(size\_t) / 2 as you could guess the answer is still sizeof(size\_t). If you want to print it we can agree on some output. The difference of these two can be NaN and so on.

The summary is that relaxing the condition for size\_t have finite size won't break any programs already existing.

P.S. Allocating memory sizeof(size\_t) is still possible, you need only countable size, so let's say you take all evens (or similar trick).

---
Tags: computability, turing-completeness, c
---


# Question
Title: How to remove an ordering requirement from a board game simulation?
## The Problem:

I'm trying to simulate part of the game tantrix which is a board game played with hexagonal tiles. Each tile has 3 lines of different colors that each start at one side of the hexagon and end at another side. a line is drawn between these tiles. Adding multiple tiles together one can make a line consisting of more than one tile. These hexagonal tiles are placed on a board based on some rules:

* In real life the first tile is placed on the board without restrictions, as it marks how all other tiles are placed as they are aligned to the first tile.
* The second tile is placed next to it at 1 of the 6 sides, at this point the only requirement is that the sides that are connected to each other have the same color.
* From the third tile onward the new tile needs to be placed connecting to 2 sides instead of 1, again both of these sides need to have the same color as the side they connect to.

With these simple rules in mind I want to simulate a small part of the game with the intent to find all configurations of the board that satisfy a given condition, and then print those configurations: All connections with the color red form a single continuous line.

For now i'm interested in simulating games using 14 tiles (which is 1/4th the entire set). The tiles that I choose are such that they are all the tiles with 3/4 colors (let's say red, blue and green).

---

## The Program:

I started writing a program in c++ to see if I can find these configurations. There are several things that I'm storing for these tiles:

* The coordinates on a grid: This is useful when I need to get information on adjacent tiles and when I need to keep track where a given tile is on the playing board.
* 6 "state" variables which can be either `r`,`g`,`b`,`y` (red,green,blue,yellow): These 6 variables store how the 6 sides are colored.
* An identifier variable: In the game each tile is identified by a number on the back. This number is also helpful when referencing tiles that haven't been placed on the board yet.

Also interesting is that tiles can be rotated using a function `rotate()` which basically takes `state[0]` and places it in `state[1]`, `state[1]` in `state[2]` etc. My current mindset was to do the following:

* Loop through all tiles and place 1 on the board at coordinates `{0,0}` then remove it from the set of unplaced tiles.
* For each tile, see if it fits anywhere on the existing grid and save those coordinates and the rotation of the tile if it fits, then rotate the tile once and try again, do this until all 6 rotations have been checked.
* Once all valid states have been found for one tile move on to the next.

The problem with this solution is that it will find different configurations based on the order of the list. Therefor I initially though of checking all orders of the list, which would basically mean checking `14! = 87178291200` versions of the same list and finding all possible configurations with them.

Currently the main algorithm looks like this (written in c++):

```
//provide a board with tiles layed on them and premVec an list of tiles to still place on the board.
void calcboard(std::vector<tile> permVec, board b) {
    bool secondToAdd;
    std::list<tileRot> valid = std::list<tileRot>();
    secondToAdd = true;
    //iterate through all tiles in the list
    for (int iTile = 0; iTile < 13; iTile++) {
        //obtain the list of valid tiles and rotation for the iTileth tile of the list
        valid = getValidSpacesForTile(permVec.at(iTile), secondToAdd, b);
        //we now have a list of all valid positions for all rotations for the tile to insert next given the previous board.
        for (tileRot tileValid : valid) {
            //add the tile to the board so we can recursively see how the next tile fits the board.
            b.addToBoard(tileValid.t);
            //check if there are still tiles to place
            if (permVec.size() > 0) {
                //create a copy of the list
                std::vector<tile> cpy = permVec;
                //remove the placed element from the copy
                cpy.erase(cpy.begin() + iTile);
                //calculate all board options for the remaining tiles.
                calcboard(cpy, b);
            } else {
                totalBoards++;
                //check if the board contains a single line for state "r" (currently potentially broken)
                if (checkLineContinuous(r, b))
                {
                    //we've found a line that works, print the board.
                    printf("Board %d is valid!\n", totalBoards);
                    b.printBoard();
                }
                else
                {
                    //we've found an invalid board.
                    printf("Board %d is invalid!\n", totalBoards);
                }
            }
            //remove the tile from the board so it can be added somewhere else.
            b.removeFromBoard(tileValid.t);
        }
        secondToAdd = false;
    }
}

```

This function is called once for each permutation of the remaining list of 13 tiles once the first tile is placed on the board. This is repeated 14 times taking each tile as starting tile. therefor this function is called 14! times which is far from optimal.

The problem is there are probably a lot of calculations done which aren't needed. For example if you would take a grid of tiles and add 1 to all the X coordinates you essentially have the same configuration of the board (the only thing different being the arbitrary coordinates that have no reflection on the real world situation). currently we are doing a calculation for both these cases, but ideally we would do each configuration once and then exclude all configurations that only differ in their coordinates.

There are probably a lot more optimizations to do that i'm not thinking about right now but i think the most important thing is the fact that I use all permutations of the list. Having a different order to the list is going to influence which configurations can be made. Is there a way to mitigate this and make it so that I don't have to do this.

How can I remove the need to calculate every permutation of the set of 13 tiles? Are there any other optimizations to be done?

Here is the full project for anyone who wants to take a closer look: https://pastebin.com/HEjaGxAL

I hope my explanation is clear, feel free to ask any questions if it's not.

# Answer
> 1 votes
Let's consider a *configuration* to be the location of all tiles, i.e., a state of the board at a particular time. To be valid a configuration must satisfy four requirements: (1) every tile (other than the starter tile) must be adjacent to at least two other tiles; (2) adjacent tiles must have the same color at the edge they share; (3) the red edges must form a continuous path; (4) it uses each of the 14 tiles at most once. Your task is to enumerate all configurations that are reachable by a sequence of legal moves.

I'm pretty sure that every valid configuration is reachable by some sequence of moves. Therefore, we don't need to enumerate all sequences of moves; it suffices to enumerate all valid configurations (i.e., enumerate over just the final state after making the moves). Because most configurations are reachable by a large number of moves, this can potentially significant speed up enumeration.

Define the *shape* of a configuration to be the locations where tiles are present (i.e., if we imagine we erase all colors).

Here is one plausible high-level schema for enumerating valid configurations:

1. Enumerate all valid shapes (i.e., satisfying requirements (1) and (4)).
2. For each shape, enumerate all valid possibilities for the locations of the red edges (satisfying requirements (3)).
3. For each shape and path of red, enumerate all valid possibilities for the colors on the tiles (satisfying conditions (2) and (4)).

This will then give you an enumeration of all valid configurations.

# Enumerating shapes

There are many ways to enumerate all possible shapes, and this probably is not the performance bottleneck, so any method will probably work fine.

Here is one possible approach. Without loss of generality, we can assume that hex at the origin is filled and there are no filled hexes above or to the left of it. (Effectively, we've translated the shape into a canonical position.) Then, enumerate all ways to build up the shape recursively, starting from the origin. At any point, we'll have a "boardmap" (which maps each hex location to one of three possibilities: "filled by a tile in the final shape", "not filled in the shape", "unknown/to be determined") and a hex tile we just placed. Our recursive function will enumerate all $2^6$ possibilities for which subsets of neighboring locations are filled vs empty, filter that set to keep only ones that are consistent with the boardmap so far and that ensure there are at least 2 neighbors filled and ensure that you don't place more than 14 tiles in total, and then temporarily fill in the boardmap with those 6 states for the neighbors and recurse. To account for the starter tile, whenever you place a tile, optionally allow that to be marked in the boardmap as a starter tile if the boardmap doesn't already contain a starter tile, and allow any starter tile to have only 1 filled neighbor. Keep track of all shapes reached during this search; that's your enumeration of shapes.

If you want to avoid duplicating each shape 6 times due to rotational symmetry, you can post-filter the list to keep only one shape from each rotational equivalence class. One approach: store the shapes in a hashtable, and before adding a shape to the hashtable, generate its 6 rotational equivalents and only add it if none of those are already present. A faster approach: when you form a shape, compute its hash and the hash of all of its 6 rotations, and keep only the shape whose hash value is lowest.

# Enumerating red paths

Choose a tile to be the starting point for the red path (whenever I write "choose", I mean you should enumerate all possibilities). Then choose the next tile in the path, and so on.

This will enumerate each path twice (once where you start from one endpoint, once where you start from the other endpoint). It is easy to deduplicate if you want: e.g., hash the two endpoints of the path and keep the red path only if you started from the endpoint with lower hash value.

# Enumerating tile colors

Now we are given a shape and the location of all red edges, and we must enumerate over all valid ways to fill in the other colors. I expect this will be the most performance-sensitive step.

One plausible approach is to visit the locations in the shape in some order, and when you visit a location, choose a tile from your supply of remaining tiles and place it there (but ensuring that it is consistent with rule (2) and with previously filled-in edge colors). This can be easily implemented with a recursive search, if you have an ordering in mind. At each step in the recursive traversal, you have a "colormap" that indicates for each location in the shape what the colors of some edges of some tiles are (others are not known yet), and a "supply" of tiles that you haven't used yet (initially this is all 14 tiles), and a location that you just filled in.

I imagine the order in which you visit tiles will greatly affect the performance of this step. A good order might help you prune many possibilities during the recursive traversal. I don't know how to choose an optimal order, but I will suggest one heuristic that might be reasonable.

Let $R$ be the set of hex locations that have red edges (i.e., that the red path goes through), and $r\_0$ be a starting point of the red path. If $x$ is a location, let $d(r\_0,x)$ denote the distance between $r\_0$ and $x$ (i.e., the number of steps it takes to get from $r\_0$ to $x$, if in each step you can move from one hex to another adjacent hex). Also let $d(R,x) = \min\_{r \in R} d(r,x)$ denote the distance between $P$ and $x$ (i.e., the smallest number of steps to get from $x$ to some location on the red path).

Now I suggest you compute $100 d(R,x) + d(r\_0,x)$ for each location $x$ in the shape, sort in order of this value, and visit the tiles in that sorted order.

---

This answer outlines one possible way to approach the problem. It's surely not the only way and I make no claim it is the best way, it is just one possibility you could try. If I understand your approach correctly (which I might not), it might speed up on your approach by avoiding the need to enumerate orders of moves.

---
Tags: optimization, board-games, c++
---


# Question
Title: Why are complex numbers needed to define qubits?
I have started learning about quantum computing, and I have been told that you can forget about the physics and think of qubits as a natural generalization of the notion of bit. According to this view, one should think about a qubit as a generalization of a bit, where the states $0$ and $1$ are in superposition; there is "a little bit of $0$ and a little bit of $1$".

This is all fine, I think, but if I were to model this formally, I would model a qubit as a real probability coefficient $\alpha \in \[0,1\] \subseteq \mathbb{R}$, representing the amount of $0$ in my qubit (thus $1-\alpha$ being the amount of $1$). Instead, in quantum computing you define a qubit as

$$\alpha\_0|0\rangle + \alpha\_1|1\rangle$$ where $\alpha\_0, \alpha\_1 \in \mathbb{C}$, and $|\alpha\_0|^2 + |\alpha\_1|^2 = 1$.

Given that complex numbers rarely appear in classical computer science, this seems an odd design choice if we are to approach quantum computing from a purely theoretical computer science point of view. I assume that the reason for complex numbers showing up here is that they are strictly necessary in quantum mechanics, but this is quite unsatisfactory of an answer for a theoretical computer scientist. My questions are two:

1. Is there an intuitive, non-physics way, of justifying these complex numbers?
2. Is it maybe that restricting to real numbers as coefficients yields a computational model equivalent to classical probabilistic Turing machines (in terms of efficiency)?

I would appreciate references where I could find more about the definition of qubits from a purely TCS point of view.

# Answer
> 4 votes
You can run any standard quantum algorithm on a real-amplitude quantum computer with one additional qubit and only constant-factor slowdown (or perhaps linear-factor slowdown considering loss of parallelism) by replacing each $a{+}bi$ in your unitary matrices by $\big(\begin{smallmatrix}a&-b\\b&a\end{smallmatrix}\big)$. Likewise, you can simulate a quaternionic quantum computer on a standard quantum computer with one additional qubit by replacing $a{+}bi{+}cj{+}dk$ with $\big(\begin{smallmatrix}a+bi&-c+di\\c+di&a-bi\end{smallmatrix}\big)$. So these models are all polynomially equivalent.

I doubt that there's a good non-physical argument for the appearance of complex numbers. In physics they're related to the duality between zeroth and first derivatives of position in harmonic oscillation (the same reason that complex numbers are used in modeling AC circuits), and that duality doesn't exist in the discrete quantum circuit model. Another argument from physics is that in Lagrangian QM the amplitude of a transition is $\int e^{iS(γ)} \\, \mathrm dγ$ (where $γ$ ranges over "histories"), and there doesn't seem to be anything you can sensibly replace $i$ with in the real case. But this model, where each history contributes an amplitude with the same absolute value but a different phase, only works because of cancellation of nearby histories, and there aren't any "nearby" histories in the quantum circuit model.

---
Tags: complexity-theory, quantum-computing, real-numbers
---


# Question
Title: pictorial representation of pre and post ordering for edge types
I am reading chapter 3 **Decomposition of Graphs** of *Algorithms* by Dasgupta, Papadimitriou & Vazirani and they show a pictorial representation of pre and post numbers with brackets for tree, forward, back and cross edges. I have pasted the image of the area I am unclear on.

I am assuming that **u** is the node/vertex we see first and then we see **v** later. Comparing to the 2nd image showing the definitions on a graph, I am taking **u** as node **A**.

What I don't get is the order for the other 2 back and cross edges. What I have is

* `u v u v` for back edge.
* `u u v v` for cross edge.

Essentially the order is flipped with `u` and `v` in what the textbook has. Could someone clarify why this is the case with the image below.

I read this answer but I came out more confused with the explanation.

Surprisingly I was able to correctly identify the pre and post numbers in this figure in the textbook. It is the letters `u` and `v` that have me confused.

# Answer
> 2 votes
"I am assuming that $u$ is the node/vertex we see first and then we see $v$ later." That is a wrong assumption, which makes that summarizing table unintelligible.

The right assumption consists of two parts.

* We are given a directed graph that contains $(u,v)$, the edge from $u$ to $v$.
* We have just completed one depth first search (DFS) on that graph, which has discovered both $u$ and $v$.

Given the assumption above, that table lists the correspondence between the "pre/post ordering for $u$ and $v$", and the "edge type" of $(u,v)$. Please note that I rephrase "pre/post ordering for $(u,v)$" as in the table to "pre/post ordering for $u$ and $v$", since the meaning of "$(u,v)$", the edge from $u$ to $v$ does not fit the former phrase exactly.

* The first row, "$\stackrel{\[}{u}\\,\stackrel{\[}{v}\\,\stackrel{\]}{v}\\,\stackrel{\]}{u}\ $ Tree/forward" says that $u$'s discovery time and departure time enclose $v$'s discovery time and departure iff $(u,v)$ is a tree edge or a forward edge. $u$ is visited first in this case.
* The second row, "$\stackrel{\[}{v}\\,\stackrel{\[}{u}\\,\stackrel{\]}{u}\\,\stackrel{\]}{v}\ $ Back" says that $v$'s discovery time and departure time enclose $u$'s discovery time and departure time iff $(u,v)$ is a back edge. $v$ is visited first in this case.
* The third row, "$\stackrel{\[}{v}\\,\stackrel{\]}{v}\\,\stackrel{\[}{u}\\,\stackrel{\]}{u}\ $ Cross" says that $v$'s discovery time and departure time are before $u$'s discovery time and departure time iff $(u,v)$ is a cross edge. $v$ is visited first in this case.

Neither do we assume $u$ is visited first nor do we assume $v$ is visited first. The node that is visited first on each row of that table is, of course, the node that appears first from the left on that row.

---

**Exercise** (as given in the book). With the same assumption, "do you see why no other orderings are possible?" For example, why is "$\stackrel{\[}{v}\\,\stackrel{\[}{u}\\,\stackrel{\]}{v}\\,\stackrel{\]}{u}$" not possible? why is "$\stackrel{\[}{u}\\,\stackrel{\]}{u}\\,\stackrel{\[}{v}\\,\stackrel{\]}{v}$" not possible?

---
Tags: depth-first-search
---


# Question
Title: Longest path in a strongly connected component
So if we assume that we have some strongly connected component G with n vertices. I would like to find the length of the longest path in that component.

My idea is: In a strongly connected component we can get from one vertex to every other vertex.

If we start at some vertex u then we can visit each of the remaining n-1 vertices by going from the vertex we are currently on to some adjacent vertex, setting the vertex we reach as the current one and repeating until we have no unvisited vertices left. As such the longest path always has length n-1.

Another idea is that we can run depth first search on the connected component and the highest level found will be the length of the longest path.

Intuitively these ideas make sense to me but not sure how to structure them formally or even if they are right. Could I get some guidance on this?

# Answer
> 1 votes
You won't be able to find any efficient algorithm for your problem, unless $\mathsf{P}=\mathsf{NP}$.

Consider an instance of Hamiltonian path: given a graph $H=(V,E)$ on $n$ vertices decide whether it contains a simple path of length $n-1$. This is a well-known $\mathsf{NP}$-hard problem.

Construct $G$ from $H$ by adding two vertices $x$ and $y$, the edges $(x,y)$ and $(y,x)$, and all the edges $(y,v)$ and $(v,y)$ for $v \in V$. Notice that the only strongly connected component of $G$ is $G$ itself.

There is a simple path of length $n+1$ in $G$ if and only if there is a path of length $n-1$ in $H$.

Indeed, if $P = \langle v\_1, v\_2, \dots, v\_n \rangle$ is a path of length $n-1$ in $H$, then $\langle x, y, v\_1, v\_2, \dots, v\_n \rangle$ is a path of length $n+1$ in $G$.

Conversely, if $P$ is a path of length $n+1$ in $G$, $P$ must have $x$ as one if its endpoints (as otherwise $x$ would have one in-neighbor and one out-neighbor in $P$, but the only in/out neighbor of $x$ is $y$, contradicting the hypothesis that $P$ is simple). Then $P$ is of the form $\langle x, y, v\_1, v\_2, \dots, v\_n \rangle$ and $\langle v\_1, v\_2, \dots, v\_n \rangle$ is a path of length $n-1$ in $H$.

---
Tags: graph-traversal, check-my-answer, connected-components, directed-graphs, path
---


# Question
Title: Can we find the largest intersecting subfamily of convex polygons in quadratic time?
Let $\mathcal{F} = \\{P\_1, P\_2,\ldots,P\_m\\}$ be a family of (closed) convex polygons in the plane, each represented by their vertices in (say) clockwise order. Let $n$ be the total number of vertices (you can assume general position, no two vertices are the same, no edges intersects a vertex other than its endpoints, no three edges intersect at the same point).

I'm curious to know if you can you compute a subfamily of largest cardinality possible such that all polygons share a *single common intersection point* in $\mathcal{O}(n^2)$ time? (In the Real RAM model, i.e. you can store an arbitrary precision real number in a register and perform arithmetic operations on them in constant time)

The best I've managed to come up with is $\mathcal{O}(n^2\log(n))$:

* I can modify the Bentley-Ottman algorithm (with the segments being the polygon edges) so that at every event point $p$, I count the number of "lower hull" edges and "upper hull" edges under $p$ on the sweep line (modifying my search tree so this can be done in $\mathcal{O}(\log(n))$ time) and compute the difference, giving me the number of polygons containing $p$. I simply keep track of the "best" point $p$, then test every polygon against $p$ in $\mathcal{O}(n)$ total time.

Alternatively, by computing the $\mathcal{O}(m^2)$ points which are the leftmost in the intersection of a pair of polygons (which can be shown to be doable in $\mathcal{O}(nm)$ time) and then counting the total number of polygons which contains each point (in $\mathcal{O}(nm^2)$ time), you can solve the problem in $\mathcal{O}(nm^2)$ time, which is better for small $m$ (and you can probably also get $\mathcal{O}(n^\alpha m^\beta)$ for different values of $\alpha + \beta \> 2$ using more sophisticated simplex range counting datastructures).

Is anything faster possible (asymptotically)? Or is there some (conditional) lower bound showing that $\mathcal{O}(n^2)$ is hard/impossible to achieve?

# Answer
> 0 votes
As Discrete lizard pointed out in a comment, I misinterpreted the statement of "sharing a common point", which I read as "pairwise sharing a common point".

You can thus ignore the below answer. I will delete it later.

---

I'm not an expert in this area but I *do actually believe* that the problem you are talking about is surprisingly enough NP-complete.

The problem, known as Maximum Clique in convex planar sets (graph class: Conv) was proved NP-hard by Kratochvíl and Kuběna \[1\] who write the following:

> We show that complements of planar graphs have intersection representations by convex sets in the plane, i.e., for every planar graph, one can assign convex sets in the plane to its vertices in such a way that two of the sets are disjoint if and only if the correspondning vertices are adjacent. This fact has a complexity consequence — it follows that the problem of determining the clique number of an intersection graph of convex sets in the plane is NP-hard. We note that the complexity of this problem for intersection graphs of straight line segments in the plane is unknown.

\[1\] Kratochvíl, Jan, and Aleš Kuběna. "On intersection representations of co-planar graphs." Discrete Mathematics 178.1-3 (1998): 251-255

---
Tags: algorithms, data-structures, computational-geometry, polygons
---


# Question
Title: Big theta notation in substitution proofs for recurrences
Often in CLRS, when proving recurrences via substitution, $\Theta(f(n))$ is replaced with $cf(n)$.

For example, on page 91, the recurrence

$$ T(n) = 3T(⌊n/4⌋) + \Theta(n^2) $$

is written like so in the proof

$$ T(n) \le 3T(⌊n/4⌋) + cn^2. $$

But can't $\Theta(n^2)$ stand for, let's say, $cn^2 + n$? Would that not make such a proof invalid?

Further in the proof, the statement

\begin{align} T(n) &\le (3/16)dn^2 + cn^2 \\ &\le dn^2 \end{align}

is reached. But if $cn^2 + n$ was used instead of $cn^2$, that step would instead be the following

$$ T(n) \le (3/16)dn^2 + cn^2 + n $$

Can it still be proven that $T(n) \le dn^2$ if this is so? Do such lower order terms not matter in proving recurrences via substitution?

# Answer
Let me also suggest the following vision of the situation: $\Theta(f)$ is set of functions, which satisfy well know definition. So, when you wrote $T(n) = 3T(⌊n/4⌋) + \Theta(n^2)$, then this means $T(n) \in 3T(⌊n/4⌋) + \Theta(n^2)$, where right side is again set $g+\Theta(f) = \\{g+\phi \colon \phi \in \Theta(f) \\}$.

So, $T \in g+\Theta(f)$ mean that **exists** element of $g+\Theta(f)$ which is equal to $T$, but we cannot say, that $T$ equals to **any** member of $g+\Theta(f)$.

Same is if we write $$T(n)- 3T(⌊n/4⌋) \in \Theta(n^2)$$ Now, knowing the definition of belonging to a set, we just use it and write, that $\exists c\_1, c\_2 \gt 0, N\in \mathbb{N}$, such that for $n \gt N$ $$c\_1 n^2 \leqslant T(n)- 3T(⌊n/4⌋) \leqslant c\_1 n^2$$ saying exactly we do not "replace" $T(n)- 3T(⌊n/4⌋)$ in equality, but we "estimate" it in inequality.
> 1 votes

# Answer
By definition, a function $f(n)$ is $\Theta(n^2)$ if there exist constant $b,c,N$ such that for all $n \geq N$, $$ bn^2 \leq f(n) \leq cn^2.$$ In particular, as long as $n \geq N$, we can always replace $f(n)$ by $cn^2$ when upper-bounding an expression.

In your example of $cn^2 + n$, when $n \geq 1$ we have $n \leq n^2$ and so $cn^2 \leq (c+1)n^2$.
> 0 votes

---
Tags: asymptotics, proof-techniques, recurrence-relation
---


# Question
Title: Need help finding/writing an algorithm to reassign items to groups with minimal changes
I have some users in groups, like this (groups are letters, users are numbers):

```
{
  a: [1, 2, 3],
  b: [4],
  c: [5],
  d: [6],
  e: [7, 8, 9, 10]
}

```

I receive a new description of the grouping of these users like this:

```
[1, 2, 3, 4, 5, 6, 11],
[7, 8, 9, 10]

```

Now, I need to rearrange the users to minimize "changes", so in this case, they'd end up like this:

```
{
  a: [1, 2, 3, 4, 5, 6, 11],
  e: [7, 8, 9, 10]
}

```

A more nuanced example is this:

```
from:
{
  a: [1, 2, 3, 4, 5, 6]
  b: [7],
}

to:
[1, 2, 3, 7]
[4, 5, 6]

options:
{
  a: [1, 2, 3, 7],
  c: [4, 5, 6]
}
{
  a: [4, 5, 6]
  b: [1, 2, 3, 7], // THIS IS BEST
}

```

In this example, the second choice is best, because we move `[1, 2, 3]` to `b` rather than `[4, 5, 6]` to `c` and `[7]` to `a`.

I've been trying to come up with some heuristics, like starting with the largest invalidated group, then in that group, take the largest group that are still together after the change, and letting them keep their place.

That kind of thing seems to work, except in the second example, I can't think how to make it pick option 2 over option 1.

I'm wondering if this is a solved problem, if it can even be done without multiple passes and comparisons, and if I'm attacking this in a vaguely sensible way.

Any guidance would be greatly appreciated.

# Answer
> 1 votes
Every user either remains in their initial group, or moves to some other group for a cost of 1. So it suffices to look for a matching between new groups and old groups that maximises the number of users who don't need to move; subtracting the number of stationary people from the total number of people gives the number of people who need to move.

To do this, create an instance of the Assignment Problem, a.k.a. Maximum-weight Bipartite Matching, in which you have a vertex in A for every current group, a vertex in B for every new group, and an edge between every pair of vertices with weight equal to the number of users shared by the two groups (edges with weight 0 can be omitted). The goal is to find a matching -- a subset of edges, no two of which share an endpoint -- of maximum weight. To solve problem instances the size of your examples, trying all possibilities with brute force would be fine, but they can be solved more efficiently using the Hungarian Algorithm or linear programming, as described on the linked page.

# Answer
> 0 votes
I arrived at this, which passes my many tests but I'm not sure if it's guaranteed to give an optimal solution:

export function regroup<T>(
  before: Record<string, Array<T>>,
  after: Array<Array<T>>,
  generateKey: (items: Set<T>) => string
): Record<string, Array<T>> {
  // construct three working values - we will move groups from afterSets into
  // result, with the new key being the best match from the 'before' dictionary
  const beforeOrderedBySize = new Map(
    sortBy(
      Object.entries(before).map(([k, v]) => [k, toSet(v)]),
      ([, v]) => -v.size
    )
  )
  const afterSets = new Set(map(after, toSet))
  const result: Map<string, Set<T>> = new Map()

  // find best new set for each old set by key
  for (const [k, oldSet] of beforeOrderedBySize) {
    let highScore = 0
    let bestSet: Set<T> | null = null

    // find best match between old and new sets
    for (const newSet of afterSets) {
      const score = jaccardSimilarity(oldSet, newSet)
      if (score > highScore) {
        highScore = score
        bestSet = newSet

        // exact matches go straight through - (prevents extra loops)
        if (score === 1) break
      }
    }

    // move best set into result, removing from candidates
    if (bestSet) {
      result.set(k, bestSet)
      afterSets.delete(bestSet)
    }
  }

  // left over new groups need new keys
  for (const remainingGroup of afterSets) {
    result.set(generateKey(remainingGroup), remainingGroup)
  }

  return mapValues(Object.fromEntries(result.entries()), fromSet)
}
```

---
Tags: algorithms
---


# Question
Title: Complexity of inverting a diagonal matrix
What is the complexity of inverting a $n \times n$ diagonal matrix?

From what I learn in algebra, the inverse of a diagonal matrix is obtained by replacing each element in the diagonal with its reciprocal.

So is it correct to say that the complexity of inverting a diagonal matrix is $\mathcal{O}(n)$?

# Answer
> 1 votes
It's unclear what $n$ is in your question. If your matrix has dimensions $n \times n$ and your model of computation allows you to perform basic arithmetic operations in constant time then, yes, computing the inverse matrix takes $O(n)$ time.

---
Tags: complexity-theory, computation-models, numerical-algorithms
---


# Question
Title: Deteremine if Language is in $R$ or $RE$
$$L =\left \\{ \langle M \rangle \mid \exists x\in \Sigma^\* \left(\left | x \right |\leq 10000 \wedge H(M, x\right) \right \\}$$

Where $H(M, x)$ denotes whether Turing machine $M$ halts on input $x$.

My guess is neither $R$ or $Re$ because I would have to run infinite TM's in order to find out if every TM halts on x or is not halting on x. Is my intuition correct?

# Answer
The language is in RE: simply generate all inputs $x$ with $|x|\le 10000$ (they are finitely many), and simulate $T$ on all inputs **in parallel**. Whenever one simulation halts, accept.

The language is not in co-RE, as otherwise it would be decidable and we could solve the Halting problem. Indeed, to decide whether a Turing machine $T$ halts on empty input, we could create a new machine $M$ that simulates $T$ if $x=\varepsilon$ and does not halt otherwise. Then $M \in L$ if an only if $T(\varepsilon)$ halts.
> 2 votes

---
Tags: turing-machines, computability, automata, undecidability
---


# Question
Title: How does an admissible heuristic ensure an optimal solution?
When using A\* (or any other best path finding algorithm), we say that the heuristic used should be **admissible**, that is, it should never overestimate the actual solution path's length (or moves).

How does an admissible heuristic ensure an optimal solution? I am preferably looking for an intuitive explanation.

If you want you can explain using the **Manhattan** distance heuristic of the **8-puzzle.**

# Answer
> 10 votes
While Anton's answer is absolutely perfect let me try to provide an alternative answer: being admissible means that the heuristic does not overestimate the effort to reach the goal, i.e., $h(n) \leq h^\*(n)$ for all $n$ in the state space (in the 8-puzzle, this means just for any permutation of the tiles and the goal you are currently considering) where $h^\*(n)$ is the optimal cost to reach the target.

I think the most logical answer to see why $A^\*$ provides optimal solutions if $h(n)$ is admissible is becauase it sorts all nodes in OPEN in ascending order of $f(n)=g(n)+h(n)$ and, also, because it does not stop when generating the goal but when expanding it:

1. Since nodes are expanded in ascending order of $f(n)$ you know that no other node is more promising than the current one. Remember: $h(n)$ is admissible so that having the lowest $f(n)$ means that it has an opportunity to reach the goal through a cheaper path that the other nodes in OPEN have not. And this is true unless you can prove the opposite, i.e., by expanding the current node.
2. Since $A^\*$ stops only when it proceeds to expand the goal node (as oppossed to stop when generating it) you are sure (from the first point above) that no other node leads through a cheaper path to it.

And this is, essentially, all you will find in the original proof by Nilsson et al.

Hope this helps,

# Answer
> 20 votes
If the heuristic function is not admissible, than we can have an estimation that is bigger than the actual path cost from some node to a goal node. If this higher path cost estimation is on the least cost path (that we are searching for), the algorithm will not explore it and it may find another (not least cost) path to the goal.

Look at this simple example.

Let $A$ and $G$ be respectively the *starting* and *goal* nodes. Let $h(N)$ be an estimate of the path's length from node $N$ to $G$, $\forall N$ in the graph. Moreover, let $c(N, X\_{i})$ be the *step cost function* from node $N$ to its neighbour $X\_i$, $\forall N$ and $i=1..m$, where $m$ is the number of neighbours of $N$ (i.e., a function that returns the cost of the edge between node $N$ and one of its neighbours).

Let the heuristics be

* $h(B) = 3$
* $h(C) = 4$

This heuristics function $H$ is not admissible, because $$h(C) = 4 \> c(C, G) = 2$$

If the *$A^\*$ algorithm* starts initially from node $A$, it will select next node $B$ for expansion and, after this, it will reach node $G$ from there. And the path will be $A \rightarrow B \rightarrow G$ with cost $4$, instead of $A \rightarrow C \rightarrow G$ with cost $3$. If the heuristic function was admissible this would not have happened.

# Answer
> 3 votes
I'd like to expand upon Anton's comment in his answer, and provide an explicit answer to the situation posed by Ashwin in the comments. I think it'll be helpful to answering the primary question.

Let's consider the situation

Where A is the starting node and G is the goal node. The numbers on the nodes are the heuristic costs, while the numbers on the edges are the costs to travel between those two nodes.

We can see that the heuristic function is admissible (i.e it doesn't overestimate the cost of reaching the goal) and consistent (ie. it decreases as we get closer to the goal node).

Here's how the A\* algorithm would find the optimal solution for this graph:

```
Iteration 1: It checks the f(x) for all of A's neighbours

 - f(B) = x + x = 2x
 - f(C) = 1.1x + 0.5x = 1.6x

```

Since f(C) is smaller, it picks C as the next node.

```
Iteration 2: Check f(x) for C's neighbours and the existing paths

 - f(B) = x + x = 2x (A->B)
 - f(G) = 2.1x + 0 = 2.1x (C->G)

```

Clearly, the path from A-\>B is cheaper and thus A\* will shift its focus to that path.

```
Iteration 3: Check f(x) for B's neighbours and the existing paths

 - f(G) = 2x + 0 = 2x (B->G)
 - f(G) = 2.1x + 0 = 2.1x (C->G)

```

Since B-\>G is cheaper here and we've reached the goal node (plus traversed all paths), the algorithm ends with the (optimal) solution A -\> B -\> C.

---
Tags: algorithms, artificial-intelligence, search-algorithms, heuristics
---


# Question
Title: Graph add at most 2 edges to make all graph nodes degree even
Given an undirected graph that is represented by its adjacency matrix, return whether or not is it possible to add no more than two edges to this graph in order to make all the degrees of nodes even. Keep in mind that in the resulting graph there should be at most one edge between any pair of nodes.

For

```
graph = [[false, true, false, false],
         [true, false, true, false],
         [false, true, false, true],
         [false, false, true, false]]

```

the output should be true.

This is my proposed broken solution:

```
boolean addEven(boolean[][] graph) {
    int odd = 0;
    int even = 0;
    for (int i = 0; i<graph.length; i++) {
        int k = 0;
        for (int j = 0; j<graph[0].length; j++) {
            if (graph[i][j] == true) {
                k++;
            }
        }
        if (k%2==1) {
            if (k == graph[0].length-1) {
                return false;
            }
            odd++;
        } else {
            even++;
        }
    }
    if (odd == 2 && even == 3) {
        return false;
    }
// Given that we have at most 2 new edges to be added the number of odd nodes should not be more than 2
    if (odd <=4) {
        return true;
    } else {
        return false;
    }
}

```

# Answer
Your proposed "broken" solution is actually quite close to the actual solution. You don't need any well known algorithm to do it, but instead you have to notice the following things:

1. Given that `odd == 2`, and the two odd vertices are $v,u$ \- then we can "fix" them by either connecting them if they are not connected, or by finding another vertex $w$ such that $(v,w),(w,u)\notin G$ and then add the two edges.
2. Given that `odd == 4`, the only way to "fix" them is by connecting them to each other, in 2 groups of 2: each edge on two different vertices.

Then, the actual code would look like this:

```
boolean addEven(boolean[][] graph) {
    int odd = 0;
    List<Integer> odd_vertices = new ArrayList<Integer>();

    for (int i = 0; i < graph.length; i++) {
        int deg = 0;
        for (int j = 0; j<graph[0].length; j++) {
            if (graph[i][j] == true) {
                deg++;
            }
        }
        if (deg % 2 == 1) {
            odd++;
            odd_vertices.add(i);
        }
    }
// Given that we have at most 2 new edges to be added the number of odd nodes should not be more than 2
    if (odd == 0) {
        return true;
    } else if (odd == 2) {
        int a = odd_vertices.get(0);
        int b = odd_vertices.get(1);
        for (int k = 0; k < graph.length; k++) {
            if (!graph[a][k] && !graph[b][k]){
                return true;
            }
        }
        return false;
    } else if (odd == 4) {
        int a = odd_vertices.get(0);
        int b = odd_vertices.get(1);
        int c = odd_vertices.get(2);
        int d = odd_vertices.get(3);
        if ((!graph[a][b] && !graph[c][d]) ||
            (!graph[a][c] && !graph[b][d]) ||
            (!graph[a][d] && !graph[b][c])) {

           return true;
        }
        return false;
    } else {
        return false;
}

```

Of course, this code is just to illustrate how the changes are reflected in the code. You can change it to be more general or optimize it, but I will keep it as is (especially because its hard to write code without a proper editor)
> 3 votes

---
Tags: graphs
---


# Question
Title: Does Master Theorem apply to $T(n) = 4T(n/2) + n^2 \log n$
Based on CLRS Theorem 4.1, master theorem doesn't apply to $T(n) = 4T(n/2) + n^2 \log n$. However, I saw the 4th condition of master theorem on slides of Bourke.

If $f(n)=\Theta(n^{\log\_ba}\log^kn)$, then $T(n)=\Theta(n^{\log\_ba}\log^{k+1}n)$. So $T(n)=3T(n/3)+n\log n$ can apply to case #2, see for example this question.

With the same logic, $T(n) = 4T(n/2) + n^2 \log n$ should be $T(n) = \Theta(n^2\log^2n)$. But it's actually $T(n) = \Theta(n^2\log n)$. Is there anything wrong of my thinking?

# Answer
You can expand the recurrence $T(n) = 4T(n/2) + n^2 \log n$ directly: \begin{align} T(n) &= n^2 \log n + 4T(n/2) \\ &= n^2 \log n + 4(n/2)^2 \log(n/2) + 16T(n/4) \\ &= n^2 \log n + 4(n/2)^2 \log(n/2) + 16(n/4)^2 \log(n/4) + 64T(n/8) \end{align} and so on. We can simplify the terms: they are $n^2 \log n$, $n^2 \log(n/2) = n^2 (\log n - 1)$, $n^2\log (n/4) = n^2(\log n - 2)$, and so on. Unrolling the recurrence all the way gives \begin{align} T(n) &= n^2 (\log n + \log (n/2) + \cdots + \log(n/(n/2)) + 4^{\log n}T(1) \\ &= n^2 \sum\_{k=1}^{\log n} k + n^2 T(1) \\ &= \frac{1}{2} n^2 \log n(\log n - 1) + n^2 T(1) \\ &= \Theta(n^2\log^2 n). \end{align}

This is also what the master theorem gives (case 2 in the Wikipedia version).
> 2 votes

---
Tags: time-complexity, runtime-analysis, master-theorem
---


title: Condition in the Dependent Loops

text:
# Question
Title: Condition in the Dependent Loops
I'm stuck with nested for loops that are dependent on the previous loop:

```
for (i=1; i<=n; i++)
  for (j=1; j<=i; j++)
    x = x+1

```

the part that is confusing me is `j<=i`. I'm trying to figure out the asymptotic running time.

# Answer
Suppose that you start with some value in $x$. The inner loop increases $x$ by $i$. Therefore the outer loop increases $x$ by $1+2+3+\cdots+n = n(n+1)/2$. So overall, your code increases the value in $x$ by $n(n+1)/2$.

The running time of your code is proportional to the number of times that $x$ is increased, hence it is $\Theta(n^2)$.
> 0 votes

---
Tags: algorithms, algorithm-analysis, loops
---


# Question
Title: Number of binary trees with given height
I was wondering how many binary trees we have with height of $h$ with $n$ nodes(another question is how many binary trees we have with height $ \lfloor{lg (n)}\rfloor$).

Edit: I forgot to add the number of nodes.

# Answer
Take the height $h$ as the length of the longest root to leaf path. After fixing the root, we count the number in two cases:

1. both left and right subtrees are of height $h$. number of trees $=A\_h^2$
2. only one subtree has height $h$. number of trees $=2 \cdot A\_h \cdot (A\_0+A\_1+...+A\_{h-1})$

$$ A\_{h+1} = A\_h^2 + 2 \cdot A\_h \cdot (A\_0+A\_1+...+A\_{h-1}) $$
> 2 votes

# Answer
I assume that a binary tree is given by the following specification: a binary tree is either (a) empty or (b) is composed of a root and two (ordered) subtrees.

I also assume that height is defined so that a complete binary tree of height $h$ has $2^{h+1}-1$ nodes (for example, a single node has height $0$).

Let $A\_h$ be the number of binary trees with height at most $h$. Then $A\_{-1} = 1$ and $A\_h = 1 + A\_{h-1}^2$. This is A003095. The number of trees with height exactly $h$ is $A\_h - A\_{h-1}$, which is A001699. Both sequences have asymptotics of the form $\alpha^{2^h}$ for some $\alpha \> 1$.
> 5 votes

# Answer
Let us assume that the number of nodes are $n$. Also, consider that $a\_{n,h}$ represents the number of different binary trees with $n$ nodes having height $h$. We construct the solution recursively.

Consider that $m$ is the current root, then for a binary tree of height $h$ we consider two cases:

1. The left subtree has the height of $h-1$. Also, we know that the left subtree contains $m-1$ nodes. So, the number of binary trees with $m-1$ nodes and height are given by $a\_{m-1,h-1}$. Now, the right subtree can have any height in $\[0, h-1\]$, so the number of ways of forming right subtree is given by $\sum\limits\_{i=1}^{h-1}a\_{n-m,i} $. Therefore, total ways in this case are: $ a\_{m-1,h-1}\sum\limits\_{i=1}^{h-1}a\_{n-m,i} $
2. Now, consider that left subtree has a height less than $h-1$. Then, the right subtree(consists of $n-m$ nodes) must have a height equal to $h-1$ which is given by $a\_{n-m, h-1}$. Now, the left subtree can have any height in $\[0, h-2\]$, so the number of ways of forming left subtree is given by $\sum\limits\_{i=1}^{h-2}a\_{m-1,i} $. Therefore, total ways in this case are: $ a\_{n-m,h-1}\sum\limits\_{i=1}^{h-2}a\_{m-1,i} $

As we have $n$ different ways to choose the node, we have the number of different binary trees of height $h$ and $n$ nodes given by the following formula:

$a\_{n,h}$ = $\sum\limits\_{m=1}^{n} (a\_{m-1,h-1}\sum\limits\_{i=1}^{h-1}a\_{n-m,i}+a\_{n-m,h-1}\sum\limits\_{i=1}^{h-2}a\_{m-1,i})$

This recurrence relation can be solved using the base case as:

1. $a\_{0,0}=1$
2. $a\_{i,0}=a\_{0,i}=0$, for all $i\>0$
> 1 votes

---
Tags: data-structures, counting
---


# Question
Title: $\overline{SAT}$ vs. $UNSAT$, Is it the same?
I know this question may look stupid, but still..
Is the meaning of both "have no satisfiable assignment"?

# Answer
> 3 votes
They are not *precisely* the same language. For instance, $\overline{SAT}$ has words that are not even formulas. $UNSAT$ on the other hand, has *only* formulas that are not satisfiable.

In terms of complexity measures - the two languages are equivalent, since we can check in polynomial time whether a given input word is a formula or not and therefore we have a poly-time reduction from $\overline{SAT}$ to $UNSAT$ and vice versa.

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


# Question
Title: Given a CFG G (in Chomsky normal form) and a string w, determine whether w has more than one parse tree in G in polynomial time
So I have the following language:

C = {\<G,w\>|G is a CFG in Chomsky normal form and w has more than one parse tree in G}

How to prove that this language is in P (decidable in deterministic polynomial time)?

I tried to come up with a polynomial-time algorithm and tried to show a reduction to a different language in P, but couldn't figure it out.

# Answer
You can modify the CYK parsing algorithm so that it *counts* the number of parse trees for each word.

Given a word $w = w\_1 \ldots w\_n$, for each $1 \leq i \leq j \leq n$ and non-terminal $A$, we will count the number of parse trees rooted at $A$ and generating $w\_i \ldots w\_j$. If $i = j$ then this number is either zero or one, depending on whether $A \to w\_i$ is a rule. Otherwise, all parse trees are of the form $$A \to BC \to^\* (w\_i \ldots w\_k) (w\_{k+1} \ldots w\_j)$$ and so if we know, for each $i \leq k \< j$ and for each $B,C$ such that a rule $A \to BC$ exists, how many parse trees there are for $w\_i \ldots w\_k$ rooted at $B$ and for $w\_{k+1} \ldots w\_j$ rooted at $C$, then we can count the number of parse trees of $w\_i \ldots w\_j$ rooted at $A$.

You are interested in whether the number of parse trees of $w\_1 \ldots w\_n$ rooted at $S$ is larger than one or not. Therefore you can cap the numbers at two, thus avoiding large numbers and so reducing the running time.
> 0 votes

---
Tags: complexity-theory, context-free, polynomial-time, ambiguity
---


# Question
Title: Isn't an improper subset of edges of a cyclic graph, cyclic and thus not a minimum spanning tree?
This is the formal definition of a minimum spanning tree taken from *Algorithms* by Dasgupta, Papadimitrious and U. Vazirani.

> *Input:* An undirected graph $G = (V,E)$; edge weights $w\_e$.
>
> *Output*: A tree $T = (V,E')$, with $E' \subseteq E$, that minimizes $$ \operatorname{weight}(T) = \sum\_{e \in E'} w\_e. $$

My confusion arises from the fact that the edges in the minimum spanning tree are an improper subset of the edges in the original graph. If the graph were cyclic, then we would have removed the cycles in the minimum spanning tree and would have had fewer edges. How is it that we have an improper subset (containing all the edges of the original graph)?

This is the example given right before the definition and the graph clearly contains cycle edges.

# Answer
> 3 votes
It looks like you misread or misunderstand the standard set notation "$E'\subseteq E$".

That notation just means $E'$ is a subset of $E$, i.e. every element of $E'$ is also an element of $E$.

---

We do not speak of "an improper subset", most of the time if not ever.

Why?

Suppose $A$ and $B$ are two sets. $A$ is a subset of $B$ iff every element of $A$ is also an element of $B$. If, furthermore, $A$ is not $B$, then we say $A$ is a proper (or strict) subset of $B$.

If we want to mention "an improper subset" of $B$, what would it mean?

* It should mean $B$ itself. That is how I would understand that phrase upon first reading. Then, why do we want to say "an improper subset of $B$", a pretty long phrase, when we can just say "$B$", which is concise? The phrase "an improper subset" seems implying there are more-than-one such subsets for a given set, which is simply wrong.
* It could just means "subset" when it is used in distinction to "proper subset" (which sounds unnatural to me, but maybe that is only me). Again, why not just use "subset", which is concise?

---
Tags: graphs, minimum-spanning-tree, definitions
---


# Question
Title: Transforming SAT to Quadratic Programming in polynomial time
I would like to show that Quadratic Programming is NP-hard.

I am currently reading a couple of papers which state that QP is NP-Hard and prove it by transforming SAT to QP, however I am finding the diction quite tough since I am just a beginner in the field. Would anyone happen to know the answer to this question who can maybe explain it to me in simpler terms?

# Answer
The reduction of SAT to quadratic programming is pretty simple. The idea is that we can use the quadratic objective to "force" the variables to be Boolean, and so we can implement an integer linear program whose feasibility is equivalent to the SAT instance.

Given a SAT instance on a set of variables $x\_1,\ldots,x\_n$, we define the following quadratic program: $$ \begin{align\*} & \min \sum\_{i=1}^n x\_i - \sum\_{i=1}^n x\_i^2 \\ \text{s.t.} & \\ & 0 \leq x\_i \leq 1 & 1 \leq i \leq n \\ & x\_{i\_1} + \cdots + x\_{i\_j} + (1 - x\_{k\_1}) + \cdots + (1 - x\_{k\_\ell}) \geq 1 & \forall \text{ cl. } x\_{i\_1} \lor \cdots \lor x\_{i\_j} \lor \bar{x}\_{k\_1} \lor \cdots \lor \bar{x}\_{k\_l} \end{align\*} $$ The linear constraints have a $0,1$ solution if and only if the SAT instance is satisfiable. Since $0 \leq x\_i \leq 1$, a solution is $0,1$ if and only if $\sum\_{i=1}^n x\_i - \sum\_{i=1}^n x\_i^2 = 0$, and for any other solution $\sum\_{i=1}^n x\_i - \sum\_{i=1}^n x\_i^2 \> 0$. Therefore the SAT instance is satisfiable if and only if the minimum is $0$ (or at most $0$).
> 6 votes

# Answer
Given $a,b,c\in\mathbb Z$ the quadratic program $$\exists x,y\in\mathbb Z$$ $$ax^2+by-c=0$$ is known to be $\mathsf{NP}$-complete by https://www.sciencedirect.com/science/article/pii/0022000078900442. If you had no non-linear constraints but a non-linear objective it is called a linear program having a non-linear objective (for example a convex objective). $\mathsf{SAT}$ can be converted to $\mathsf{SUBSETSUM}$ which reduces to the quadratic program.
> 0 votes

---
Tags: complexity-theory, reductions, np-hard
---


title: Maximum matching for general graph

text:
# Question
Title: Maximum matching for general graph
I am studying the maximum matching problem and I was trying to understand why the classical augmenting path algorithm does not work for the general graph (i.e. for non bipartite graph) and you must recur to the blossom algorithm.

The explanations that I found (1. here, 2. and here) are based on the fact that the direction that I choose to start exploring an odd loop in the Depth First Search (DFS) could make me miss an augmented path.

But it seems to me that this issue can be solved by considering the same vertex distinct during the DFS if I am entering it through a matched edge or an unmatched one, why isn't this enough? To be more precise, what I mean is that during a DFS, you still avoid loops, so you stop if you enter a node that is already in the path between the root and the current node, but you still explore nodes that you have visited in previous paths if you are entering them from a different type of edge (matched or not matched).

# Answer
> 0 votes
I found the answer myself at the end.

Consider this graph and matching (full edge are matched and dashed are not) and suppose we start by exploring the red path from node 1 to 9:  we cannot continue since entering node 7 would create a loop, but during this path we marked node 8 as visited from a non matched edge, and so we will not enter node 8 again through a not matched edge and we will miss the following augmenting path: .

I think that this one is the minimum graph in terms of number of nodes that fails for the algorithm, so it is actually not trivial to understand that the algorithm is flawed

# Answer
> 1 votes
I think the issue will be that, if we allow each vertex to be considered twice (once per incoming edge type), then we need some way to remember that if we have already visited one "flavour" of a vertex on the path from the BFS root so far, we must avoid visiting its other flavour further along the same path (since such a path would no longer be simple). This seems to entail keeping track of all, or at least all minimal (w.r.t. set inclusion) sets of vertices used on the path to each vertex considered in the BFS so far, which in the worst case would multiply time (and possibly space) requirements by a factor exponential in $|V|$.

Why is it not necessary to explicitly keep track of which vertices have been used in the usual Hopcroft-Karp algorithm for maximum matching in bipartite graphs, which considers each vertex only once? Because the BFS step used in that algorithm to find augmenting paths automatically ensures that all paths from the BFS root are shortest paths, and thus that they are all simple.

---
Tags: algorithms, graphs, matching
---


# Question
Title: Where does the decimal to binary "Divide by 2" algorithm come from?
I don't know if this board would be an appropriate place for this question, but I have been trying to figure out how the divide-by-2 decimal to binary conversion trick works: in which you divide the number by 2, record its remainder and in the end write out the remainders in reverse to the get the final binary string. I have been using this for a long time but have never really considered why this works. Is there any explanation that could serve as a "proof" or even a basis for how people came up with this in the first place ? Thanks!

# Answer
The algorithm follows fairly directly from our usual representation of numbers. Since most of us are more familiar with decimal, let's start there. Let's pick a number--say, 937. Since this is decimal, this means 9 * 102 \+ 3 * 101 \+ 7 * 100. So, repeatedly taking the remainder after dividing by 10 gives us the digits.

If we convert to binary, that's 11'1010'1001, because 937 is 1 * 29 \+ 1 * 28 \+ 1 * 27 \+ 0 * 26 \+ \[...\] + 1 * 20.

Just like in decimal, taking the remainder with repeated division by the number base we care about (2 in this case) gives us the digits of the number, starting from the least significant and progressing to the most significant, because that's pretty much how we define the representation of a number in a particular base.
> 1 votes

---
Tags: binary
---


# Question
Title: Tips on speeding up hierarchical linkage clustering algorithm
I implemented a hierarchical linkage algorithm for a set of 5,000 points. Each point is defined with a longitude and a latitude.

I read about this algorithm here.

These are the steps:

1. Compute distance matrix between all points (great-circle distance, not Euclidean)
2. Find the pair of points with the minimum distance between them
3. If the minimum distance is larger than a threshold value
    * the algorithm finishes
4. Otherwise
    * The two points are merged, and removed from the list of points.
    * The center point of this pair is added to the list of points
5. Go back to 1

I do not consider single, complete, etc. types of linkage, since the points are substituted by a central point. Therefore, the distance is just the distance between all points (instead of point-cluster).

It runs okay for small amount of pairs, but it takes 1 second per iteration as soon as I run it for 5,000 points; potentially 83 minutes although it probably stops halfway due to the distance threshold.

Although I use Haversine formulation in the calculation of distances, it does not change much if I use a simple Euclidean approach; it then takes 1 second for 3 iterations.

Am I making a mistake in understanding and implementing this algorithm? If not, are there ways in which this could be sped up?

I am using MATLAB R2018b.

Thank you!

# Answer
Yes. After you merge two points, you can update the distances of just the affected nodes, without having to recompute all pairs of distances again. That will be vastly faster.
> 1 votes

---
Tags: algorithms, clustering
---


# Question
Title: Proof of existence of $L\in R\setminus P$
I saw some proof but I didn't understood it, any simple one?

# Answer
> 1 votes
Look at the time hierarchy theorem for an explanation. In particular, we know (using this theorem) that $P\subsetneq E\subsetneq EXP\subsetneq R$, and we could have added a lot more complexity classes in between them.

---
Tags: complexity-theory, formal-languages, computability
---


# Question
Title: What is the machine epsilon and number of mantissa bits for TI-83?
I am trying to determine how many bits the TI-83 Plus uses to store floating point numbers. I am using the algorithm for approximating the machine epsilon given in "Numerical Mathematics and Computing" by Cheney and Kincaid. In TI-BASIC, it looks like this:

```
: 1 -> E
: While (1+E) > 1
: E/2 -> E
: End
: Disp 2*E

```

The program returns 9.31322575E-10, which is equal to $2^{-30}$. This is an approximation within a factor of 2.

Here's where I get confused. In the textbook I mentioned above, they say that the number of binary digits used in the mantissa, $k$, is given by $u=2^{-k}$, where $u$ is the number we just found. This is easy to verify for things like IEEE-754 format, because the mantissa is stored as its base 2 representation, so k is the number of bits allocated to the mantissa. However, as far as I can tell from sources like this, the TI-83 does not use IEEE-754 floating point, but different floating point encoding scheme with 7 bytes of binary-coded decimal for the mantissa (that's 14 decimal digits). If that is true, then it seems to me like the machine epsilon should be $10^{-14}$. Furthermore, this means the number of mantissa bits is 56, rather than 30.

How can I rectify these two things?

# Answer
> 2 votes
> the TI-83 does not use IEEE-754 floating point, but different floating point encoding scheme with 7 bytes of binary-coded decimal for the mantissa (that's 14 decimal digits).

Yes, and in order to deal with that, the program should take into account the base of 10:

```
1->E
While (1+E)>1
E/10->E
End
Disp 10*E

```

This results in $10^{-9}$, not $10^{-14}$ \- though actually 14 digits would imply that $\epsilon = 10^{-13}$. There's still something missing to explain that result, and that thing is that the TI83+ sometimes rounds to 10 digits, for example for printing, but also for the purpose of comparisons. For the purpose of subtraction, that rounding is not performed. You can see the difference with a program like this, showing that there is more internal precision than 10 digits after all:

```
1->E
While (1+E)>1
E/10->E
End
10E->E
For(X,1,5
Disp 1+E-1
E/10->E
End

```

This program shows that evaluating $1+E-1$ for $E = 10^{-12}$ still does not yield zero, while for $E = 10^{-13}$ it does yield zero. We should be careful not to conclude that therefore $\epsilon = 10^{-12}$, it's more complicated. There seems to be a special rule the zeroes out small differences. That elusive 14th digit does *exist* though it's well hidden, for example this demo shows it:

```
1+8|E~13->X
Disp X*2-2

```

(this is SourceCoder syntax, `|E` is the small E made by pressing `2nd` and `,`, `~` is unary negation `(-)`).

This program doesn't print zero, so the 14th digit has to exist internally, even though the TI83+ tries very hard to deny it. Whether this means we should say that $\epsilon = 10^{-13}$ is not clear to me. $1 + 10^{-13}$ is technically different from $1$, but they compare equal and evaluating their difference yields zero.

---
Tags: floating-point, numerical-analysis
---


# Question
Title: Why we still need Short Term Memory if Long Term Memory can save temporary data?
If RAM is a short term memory and SSD is a long term memory, why don't microarchitecture of computer nowadays use SSD or another long term memory for saving temporary data like hidden variable for programming?

If it's about speed, then SSD can improve its speed, is it possible that SSD will become faster than RAM at some point?

If SSD has *address* for *memory location* and *data* for *opcode/instruction/operand* like RAM, then will it possibly act like RAM?

# Answer
There's two simple reasons, one fundamental and one related to our current technology. First the technical one: volatile storage is (generally) faster than non-volatile storage. It has fewer requirements - it only needs to store the data for a short while until it gets refreshed, so it's not a surprise that it often is faster.

But the fundamental reason is that memory gets slower to access the bigger it is. This is why modern architectures don't just have 'RAM' and 'disk', there's layers upon layers of increasing size memory, with only the topmost layer being non-volatile:

1. CPU registers
2. L1 cache
3. L2 cache
4. L3 cache
5. RAM itself
6. Cache on the disk micro-controller
7. The disk itself
> 40 votes

# Answer
@orlp is already discussed speed. There's probably more than could be added (e.g., about latency vs. bandwidth), but let's leave that aside for now.

### Write Endurance

Instead, let's start by considering a completely separate point: write endurance. Most SSDs use Flash memory. Writing to Flash memory slowly wears it out. SSDs do wear leveling to help distribute writes evenly across available memory, to maximize the life of the device as a whole.

Main memory gets written drastically more often than storage though. As a simple rule of thumb, I'd figure 100 times as often (could be more or less, of course, but let's go with 100 for now).

So, if you used Flash as main memory, you'd be writing to it around 100 times as often as you do as an SSD. Expected lifetime of an SSD is typically around 5-10 years. So as main memory, that would be about 0.05 to 0.1 years. In other words, you'd expect your main memory to need replacement around once a month or so. Heavy computation might easily reduce that to less than a day.
> 21 votes

# Answer
Others have talked about different technologies, like L1 caches, etc. so I thought I'd give a more theoretical explanation.

Memory access time scales with square root of capacity, i.e. random access within a pool of N bits will take around $O(√N)$ time. This takes into account the various different forms of hardware we might use, from fast on-board caches up to distant datacentres. It is essentially due to the finite speed of light and how much we can fit within a certain radius, given the (roughly) Euclidean space we live in.

If we have $M$ bits of storage total, allocating it all to one big pool will subject all memory access to the slowest possible time, namely $O(√M)$

If we split $M$ into two equal-size pools of size $\frac{M}{2}$ (either on separate devices, or as known locations within a single device), this reduces to $O(√\frac{M}{2}) = O(\frac{√M}{√2}) \approx O(0.7 \times √M) = 0.7 \times O(√M)$; i.e. a $30\\%$ speedup compared to a single pool.

We get a speedup because when we are accessing one pool, we are *guaranteed* that the other pool's data will not be needed. Hence we could, in principle, arrange for our desired memory to by physically closer when we issue the read. To make (physical) space for this, we can temporarily move the unwanted memory out of the way.

If we split $M$ into two *unequal* pools of size $P \times M$ and $Q \times M$, where $P + Q = 1$ and $P \< 0.5$, their access times will be:

* $O(√(P \times M)) = O(√P \times √M) = √P \times O(√M)$
* $O(√(Q \times M)) = O(√Q \times √M) = √Q \times O(√M)$

If we choose a very small value for P, like $P = 0.01$, we get a factor of $√P = √0.01 = 0.1$, which is a $90\\%$ speed improvement. The smaller we make $P$, the faster its (smaller) pool will be.

$Q$ will also get slower, but only a little since it's a small change *relative* to its previous size. For example, going from $Q = 0.9$ to $Q = 0.99$ multiplies its access time by $\frac{√0.99}{√0.9} \approx \frac{0.995}{0.95} \approx 1.05$ (about $5\\%$ slower), whilst the pool for $P$ would get faster by $\frac{√0.01}{√0.1} \approx \frac{0.1}{0.32} \approx 0.31$ (about $69\\%$ faster)

My current laptop has about 226GB of disk space and 16GB RAM, so $P = \frac{16GB}{16GB + 226GB} \approx 0.07$. Hence *in theory*, splitting up my laptop's memory between disk and RAM gives that RAM access speeds of $√0.07 \approx 0.26$ times what they would be if pooled (a $74\\%$ speedup).
> 9 votes

# Answer
According to Google, the fastest SSD drive in 2020 has a 45 microsecond read access time. RAM access time is about 10 ns, that is 4,500 times faster. A factor of 4,500 is enough to make SSD without RAM completely unusable. We *do* come close to the point where it may make sense for low end computers to have less RAM and rely on swapping, since sequential reads/writes run at up to 6 / 4 GB per second, especially if multiple applications are run at the same time, but are not all used at the same time.

And there is the rather fatal point of write endurance. Although that would only matter if SSD write speeds were the same as RAM; as it is the *time* to destroy your SSD drive would still be quite long.
> 4 votes

# Answer
When we talk about speed, we need to distinguish between latency and throughput. Latency is fundamentally restricted by physics; for example DRAM can be accessed in about 10 ns, flash can be accessed in about 1 μs, HDD can be accessed in about 10 ms. Throughput can be achieved with engineering and economics; for example if one hard disk can access 100 MB/s sequentially, then 10 disks can achieve 1 GB/s.

You can easily make an SSD have the same throughput as RAM, but you can't match the latency or write endurance.

DRAM and SSDs are incomparable at a number of levels:

* DRAM latency is about 2 orders of magnitude less than flash memory.
* The CPU accesses DRAM directly using an address line. The CPU waits a fixed number of cycles for DRAM transactions. Whereas flash memory needs more sophistical protocols for access; they have controllers that remap addresses; they have very variable read/write times; they have to undergo unpredictable garbage collection.
* DRAM bandwidth is about an order of magnitude better than flash memory (something like 30 GB/s vs. 3 GB/s).
* DRAM can be rewritten an infinite number of times, whereas a flash memory cell can be rewritten 100~100k times depending on the technology (NAND, NOR, MLC, etc.).
* Almost any real-world algorithm will rewrite the contents of some memory locations thousands, maybe millions of times. DRAM can withstand this, but flash certain cannot.
* The minimum data access size for flash memory is around 4096 bytes, whereas for RAM it is around 64 bytes. Most algorithms have many components that access only a small piece of memory (like a single number), so flash memory would waste a lot of bandwidth transferring unused data.
* Writing and especially erasing flash cells are *really slow*. You can hide these operations behind a DRAM buffer... but then you're back to the characteristics of DRAM.

However, there are some exceptions:

* Some microcontrollers like those from Texas Instruments use FeRAM which is low-latency, non-volatile, and infinitely rewritable. These chips do not have separate DRAM and flash; they just use FeRAM for short- and long-term memory.
* Some computers/CPUs can execute instruction code directly from ROM or flash without having to load it into RAM.
* XPoint memory (a.k.a. Intel Optane) has characteristics in between DRAM and flash, in terms of cost, latency, and capacity.
> 3 votes

# Answer
In earlier days, when microprocessors were fairly slow internally, the Texas Instruments 9900 used external memory for its registers, making context changes as simple as pointing to another block in memory.

As has been said earlier, the balance of native speeds, endurance and cost of the various technologies decides what type of memory are used where.

If enduring memory gets fast enough to be used as the main memory of a CPU, that will lead to a revolution in OS design and how programs are distributed.

That is because the programs can be stored in memory as directly executable, as in the old days of MS-DOS and terminate-and-stay-ready (TSR) module code. That means that when installed, they are ready to run instantly. You would not start a program per se, but just resume it.

Basically, secondary memory would be subsumed into primary memory.

As well, the distribution media could just contain a memory image of a program so there would be no need for the slow translation and construction process involved in traditional installation processes, but a basic read-in directly to memory.

Conceivably, where some large programs are already being provided on SSDs for plug and play installation, they could be on enduring memory modules that are ready to run by just plugging straight into a system.

Of course, OSs would need to be modified to really take advantage of the new program topologies, as memory instructions would begin to be far more used than the IO instructions typically used for secondary memory devices like SSDs. Currently, the interface code to secondary devices are a major OS bottleneck and really slow down program execution, often substantially negating the quantum leap in speeds available from SSDs over HDDs.

In the end, while OS makers would be updating their products over time, the widespread merging of primary and secondary memory might be an opportune time to move to new OSs that are not bound by the 1960s, 70s and 80s architectures upon which current OSs are based. A brave new world awaits!
> 2 votes

# Answer
Even if the bytes of an SSD could otherwise compete performance wise with RAM and Cache, they have an advantage that SSD doesn't: physical distance between the CPU and memory is significant enough that the time it takes the electrons to travel between the two makes a big difference.

Of course, other answers about the current state of technology are also quite important. RAM is cheaper and chips are faster when smaller at the moment.

As this answer points out, speed declines as the square of the physical distance: https://superuser.com/a/1021891/306431
> 1 votes

# Answer
And also, programs designed today rather expect there to be a difference between 'things I want to persist' and 'things that I want to go away on exit'. If that suddenly changed to 'everything persists' then we'd have to code a little differently.

Not to mention concurrency. Suppose I write a program that has a variable 'foo'. Now I'm running 17 copies of that program. Clearly I don't want all of those variables to resolve to the same persistent storage location; we need process-local storage. So there are 17 different mappings of my address space to persistent storage. Now those 17 processes exit, but I suppose that the 17 instances of 'foo' still exist in this new 'everything persists' regime. Will they ever be useful again? I start a new instance of the program. Which of those 17 old instances does my new 'foo' map to?

We can imagine that the persistent copy is erased on program exit, but then we're using persistent storage to simulate ephemeral storage, which seems like adding complication for no gain.

Conclusion: As a programmer, I want ephemeral storage. And since I want that, there's little point in mapping it to persistent storage.
> -4 votes

---
Tags: storage
---


title: Theory behind regex implementations

text:
# Question
Title: Theory behind regex implementations
In a 2007 article, Russ Cox (at presents, he leads the development of the Go programming language at Google) argues that regex engines in languages like Java, Perl, PHP, Python, Ruby are built on a different theoretical framework from implementations like awk or sed. Cox claims a difference in performance between 60s and 20microseconds (the difference is an order of magnitude of millions!). Link to the article.

Is this issue still up-to-date? That is, is the theory behind these groups of implementations basically different?

Is there any real life scenario when a programmer would need to pick some Jurassic implementation like awk (due to its solid theoretical framework) because otherwise the task at hand could not be dealt with?

# Answer
> 13 votes
It isn't a matter of implementation. It's a matter of different approaches to parsing that unfortunately have similar names.

NFAs and DFAs (finite-state machines) can only recognize regular languages. Regular expressions are a way of specifying regular languages, and they can be compiled into efficient NFAs or DFAs that recognize the language. This is all taught in undergraduate CS courses.

The so-called "regexes" in Perl and its many imitators have a name that sounds like an abbreviation of "regular expression", and they syntactically resemble the regular expressions of sed and awk, but they are not regular expressions. They are really specifications of backtracking parsers. Backtracking parsers aren't limited to recognizing regular languages. (The name "regex" is Larry Wall's fault. He made a deliberate decision to not call them "regular expressions" because he knew that they weren't, but he should have invented an entirely different name.)

You don't need a Jurassic implementation of NFA/DFA based regular expression matching; modern maintained libraries are available for popular languages. But they lack many features of Perl-style regexes, and they don't offer much in exchange. They certainly have much better worst-case performance, but the pathological worst cases of backtracking parsers can be fixed by modifying the regexes, without losing the extra flexibility of backtracking.

The article by Cox is disingenuous. He evidently wants you to believe that the authors of regex libraries are ignorant of the theory of regular languages, and if they had just studied the standard undergraduate CS curriculum then they would have implemented their libraries in a different way and made them faster. That's false. It's impossible to implement Perl-style regexes that way, and he knows it. The popularity of Perl-style regexes is probably due in large part to their flexible feature set that goes far beyond what's available in any true regular expression library.

# Answer
> 7 votes
Cox's post is still relevant and up-to-date. The key quote is this one:

> Most of the time, in fact, regular expression matching in Perl is fast enough. As the graph shows, though, it is possible to write so-called “pathological” regular expressions that Perl matches very very slowly. In contrast, there are no regular expressions that are pathological for the Thompson NFA implementation.

Later in the post, Cox gives examples that are relevant in the real world:

> Examples include using `(.*) (.*) (.*) (.*) (.*)` to split five space-separated fields, or using alternations where the common cases are not listed first.

---
Tags: complexity-theory, regular-expressions
---


# Question
Title: Why every finite language is polynomial?
I understand that it's possible to build TM that check all the finite number of cases, so it's definitely in $R$, but I'm not sure why it's in $P$

# Answer
Suppose that the longest word in the language has length $m$. The Turing machine reads the first $m+1$ symbols on the input tape. Based on that, it can decide whether the input belongs to the language or not. This Turing machine runs in *constant* time.
> 3 votes

---
Tags: complexity-theory, formal-languages, computability, polynomial-time
---