# Question
Title: How can we express value of cosine similarity of two documents into percentage?
We were doing project work for plagiarism checking. For this purpose, we have taken a term frequency vector of two documents and measured the similarity using a cosine similarity measure. The value of cosine similarity is limited between 0 and 1. We know that the value of cosine similarity will be 1 if two documents exactly match with one another. In this case, we can say 100% match. Moreover, the value will be 0 for no match i.e. 0 % match. Furthermore, if the value is 0.65, then how do we find the percentage from this score? The definition and formula of cosine similarity are shown in the following figure.

# Answer
Suppose that your two vectors $x,y$ belong to $\\{\pm1\\}^n$. The formula of cosine similarity in this case gives the cosine similarity as $$ \frac{1}{n} \sum\_{i=1}^n x\_i y\_i = \frac{\\#\\{i : x\_i = y\_i\\} - \\#\\{i : x\_i \neq y\_i\\}}{n} = 1 - 2\Pr\_i\[x\_i \neq y\_i\] = 2\Pr\_i\[x\_i=y\_i\] - 1. $$ As can be seen, the range of cosine similarity is actually $\[-1,1\]$.

Sometimes other proxies of cosine similarity are used. For example, cosine distance is one minus cosine similarity; this ranges over $\[0,2\]$. Similarly, "half cosine distance" is half the cosine distance, which ranges over $\[0,1\]$. In the case above, half cosine distance is exactly $\Pr\_i\[x\_i \neq y\_i\]$.

Starting with the actual cosine similarity $S$, you can extract $\Pr\_i\[x\_i = y\_i\]$ as $\frac{1+S}{2}$. In the case of two vectors $x,y \in \\{\pm 1\\}^n$, this is the percentage of indices in which $x\_i$ equals $y\_i$. For general vectors $x,y$, the quantity $\frac{1+S}{2}$ no longer has this interpretation. It is just a distance measure.
> 1 votes

# Answer
Suppose $x\_{ij}$ is number of times that word $j$ appears in document $i$. Then the *cosine similarity* between document $A$ and document $B$ is the normalised dot product:

$$\mathit{sim}(A,B) = \frac{\sum\_j x\_{Aj} x\_{Bj}}{\sqrt{\left(\sum\_j x\_{Aj}^2\right) \left(\sum\_j x\_{Bj}^2\right)}}$$

This is normalised to be between $0$ and $1$, as you rightly said. Because the components of the vectors are word counts, there are no negative numbers here.

By the way, on natural language texts, the cosine measure is not considered to be a good measure because it weighs extremely common words (e.g. "the", "and", "but") more highly. One option is to drop these words (called "stop words"), but then you'd better hope that the document isn't about The Who.

The other option is to use a measure which estimates the information content of each word, such as measures based on tf-idf. Other options include a $\chi^2$ test.

You could, if you wanted to, interpret this as a percentage just by multiplying it by 100, or perhaps using $\frac{200}{\pi}\arcsin\left( \mathit{sim}(A,B) \right)$, but it doesn't really have a natural interpretation as a percentage. A percentage is a *proportion* or a *probability*, but cosine similarity is an *angle*.

You occasionally hear percentages like this thrown around, such as that humans and chimpanzees share 98.8% of our DNA, but it's always far from obvious exactly what that measures and whether or not it makes sense to interpret it as a percentage.

Finally, it's not clear to me that a measure based on treating the document as a "bag of words" is a good way to detect plagiarism in the first place. An author often uses a similar vocabulary in a lot of their works, but for detecting *copying*, surely the order in which the words appear makes a difference?
> 1 votes

# Answer
Multiply the cosine by one hundred.
> 0 votes

---
Tags: matching, data-mining
---


title: Determining circumference of a graph

text:
# Question
Title: Determining circumference of a graph
The **circumference** of a graph is the length of any longest cycle in the graph. The problem of determining circumference of a graph should be NP-complete. However, for graphs of moderate size, is there also a clever brute-force approach?

I referred to the link, where someone mentioned that the **Johnson's algorithm** is the most efficient. However, I'm not sure about the source of this algorithm or if there's an existing implementation based on it. When it comes to finding the longest cycle, I currently feel that the software *Mathematica* might be most effective (although there is no direct command for it). As for open-source programs, the one I've come across is the one below, but its efficiency doesn't seem to be notably high.

I once raised this question on the Mathematica stack, and they suggested that I should start by looking for algorithms. Are there any references or surveys on the theory or algorithms related to finding the longest cycle?

# Answer
> 5 votes
Unfortunately the following problem is very hard:

**Problem:** Long Cycle
**Input:** A graph $G$ and an integer $k$
**Question:** Does $G$ have a simple cycle of length at least $k$?

The problem is clearly NP-complete as it is a generalization of Hamiltonian Cycle (the problem has a cycle of length at least $n$ if and only if the graph is Hamiltonian).

There is no fast algorithm for this problem, and to the best of my knowledge, the fastest FPT algorithm runs in time $O(4.884^k \cdot n^{O(1)})$ \[1\].

---

\[1\] Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi, Long directed (s,t)-path: FPT algorithm, Information Processing Letters, 2018

---
Tags: graphs
---


title: Confused about Turing Recognizability

text:
# Question
Title: Confused about Turing Recognizability
If Turing Recognizability means a T.M. will either halt on input $w$ if $w$ is in the language, or run forever if $w$ is not in the language.

How can we know the language is Turing Recognizable if we run the T.M. on a $w$ not in the language and thus it never halts so we do not get to the next input.

# Answer
> How can we know the language is Turing Recognizable if we run the T.M. on a w not in the language and thus it never halts so we do not get to the next input.

We don't determine that a language is Turing recognizable by *running* it; rather, we determine that it is recognizable through a mathematical argument. We prove this by giving a machine $M$, and *proving* that for all inputs $w$, the machine $M$ will accept if $w$ is in the language and either halt or run forever otherwise.

The reason we do this by proof is that we can't run it for all possible inputs (that would be impossible and take an infinite amount of time). So instead, we use a mathematical proof that works for *all* possible inputs at once.
> 1 votes

# Answer
A language $L$ is recognisable if there exists a TM $M$ s.t $M$ accepts $w$ if and only if $w \in L$.

Note that the requirement does not necessarily mean $M$ **rejects** $w$; it could simply not halt.

> How can we know the language is Turing Recognizable if we run the T.M. on a w not in the language

Thus to answer your question, I would stipulate that there exists no requirement for $M$ to halt on $w \notin L$

If you simply want to find strings in the language, follow Pal's comment:

For $i=0 \dots n$ steps:

1. Run $M$ on all words up to length $i$ for at most $i$ steps
2. If $M$ accepts, $w$ is in $L(M)$

And by setting $n$ to infinity every $w$ in $L(M)$ will be found.
> 0 votes

# Answer
The source of the confusion is that recognizability is defined in terms of a "there exists" statement.

Recognizability is "one-sided" in regards to "yes" instances and "no" instances. Decidability is a strictly stronger condition than recognizability. Suppose the language $L$ is turing-recognizable (Chomsky Type 0):

There exists a Turing machine $M$ such that:

* If $w$ is in the language $L$, then it is guaranteed $M$ will halt, and yield a "yes" output.
* If $w$ is not in the language $L$, then we know $M$ will not output a "yes", but it does not tell if $M$ will output a "no" or will run forever.

If $L$ is undecidable, then every such $M$ which satisfies the above two conditions also will run forever on certain words $w$ not in $L$. We can also construct a $M$ which halts if and only if $w$ is in $L$ by forcing a loop sequence if a "no" answer is reached.
> 0 votes

---
Tags: turing-machines, chomsky-hierarchy
---


# Question
Title: What are the examples of scalable and non-scalable data structures?
Big data era, people say the big data systems must use the scalable data structures and store.

I didn't get the point here. I need some examples.

What are the good examples of (1) scalable and (2) non-scalable data structure respectively?

Can any one give me an idea on it?

# Answer
If I understand correctly, scalable structures refer to structures that can grow with the input grows without concern for memory. Off the top of my head I'd imagine scalable structures such as a tree structure that can grow and search elements quickly, generally `O(log(n))` even tho they're a bit more memory intensive.

Where a non scalable structure would be something like an array or any type of structure that has its memory statically allocated to it. While it takes longer to search, generally `O(n)` but has a predictable memory size. I hope this helps. Note that trees (or other structures that often are dynamically allocated) can be written as array based such as an array based heap that has both static memory allocation but `O(log(n))` search capabilities.

It would make sense for big data to use scalable structures since the amount of data is by definition- big and they likely need to query it in an efficient way. I hope I understood your question and this helps.
> 4 votes

# Answer
According to me the scalble and non-scalble data can be illustrated as follows: Non-Scalble data: The Non-Scalble data is nothing but the data for a software, algorithm, ect . Which is not in that format , need change in which that software is family .. that type of data we call it as a Non-Scalble data for that respective software, Algorithm, ect ....

Scalable Data: The scalable data is just data which has no specific format , in others words it's continuously changing but still that respective software, Algorithm, ect is accumulating or understand that; that type of data is called as the sacalab data for that respective software, Algorithm, ect.

**List item**
> -1 votes

---
Tags: data-structures
---


# Question
Title: Combining chunks on an infinite grid into regions
I am working on an floorplan application where I save elements on an infinite grid in a sparse manner. Specifically, I have the following Python class representing a sparse grid (basically a dictionary mapping coordinates to elements):

```
from collections.abc import MutableMapping

class SparseGrid(MutableMapping):
    """ An n-dimensional grid saved in a sparse format. """

    def __init__(self, dimensions=2):
        self._dimensions = dimensions
        self._grid = {}

    def __getitem__(self, coords):
        return self._grid[coords]

    def __setitem__(self, coords, value):
        if len(coords) != self._dimensions:
            self._raise(coords)
        self._grid[coords] = value

    def __delitem__(self, coords):
        del self._grid[coords]

    def __len__(self):
        return len(self._grid)

    def __iter__(self):
        return iter(self._grid.values())

    def __contains__(self, value):
        return value in self._grid.values()

    def _raise(self, coords):
        raise ValueError(f"Expected {self._dimensions} coordinates, got {len(coords)}: {coords}")

    def coordinates(self):
        return self._grid.keys()

    def items(self):
        return self._grid.items()

```

The grid can contain a lot of elements, but the number of different possible elements is small. As such I was able to colour-code them and I had the idea to save the elements to a PNG image, which should help a lot with file-size (over, say, saving them to a JSON dict or some similar approach). However, since the grid can conceivably span tens/hundreds of thousands or even upwards of a million of units in any direction, creating such an image in memory would be impractical, even if the end file size would probably still be small (since PNG is pretty good at compressing large areas of the same colour -- in this case black, representing empty space). As such, I decided to split the grid into chunks and save each chunk as a separate image.

```
from collections import defaultdict
from enum import Enum
from pathlib import Path

class Element(Enum):
    WOOD = 150, 60, 50
    STONE = 150, 150, 150
    GRASS = 100, 200, 0

    def __init__(self, r, g, b):
        self.colour = r, g, b

class Plan(SparseGrid):
    """ A sparse grid of `Element`s. """

    def save(self, file, chunk_size=1024):  # After combining logic is implemented, should probably start with size 1 or 2 here
        file = Path(file)
        file = file.with_name(file.stem + '_{},{}_{}.cnk')

        chunks = defaultdict(list)
        for x, y in self.coordinates():
            chunks[x // chunk_size, y // chunk_size].append((x, y))

        #TODO: Combine neighbouring chunks:
        # for each size up to let's say 2048 (doubling each step), do a horizontal and vertical pass
        # if chunks are neighbours, combine them into a single chunk
        # keep in mind that this way the horizontal/vertical sizes won't necessarily be the same
        #
        # Is this actually worth it? It will result in a lot of empty space with bigger chunks ...
        # I could use logic where I only combine if the resulting chunk is at least 50% full

        # Save the chunks
        for chunk, elements in chunks.items():
            self._save_chunk(file, elements, *chunk, chunk_size)

    def _save_chunk(self, file, elements, chunk_x, chunk_y, size):
        file = file.with_stem(file.stem.format(chunk_x, chunk_y, size))

        # Generate the image
        img = np.zeros((size, size, 3), dtype=np.uint8)
        for x, y in elements:
            img[y % size, x % size] = self[x, y].colour

        # Save the image
        img = Image.fromarray(img)
        img.save(file, format='PNG', compress_level=9)

    @classmethod
    def load(cls, file):
        plan = cls()
        file = Path(file)

        # Load the chunk files
        for chunk_file in file.parent.glob(file.stem + '_*,*_*.cnk'):
            plan._load_chunk(chunk_file)

        return plan

    def _load_chunk(self, file):
        coords, size = file.stem.split('_')[-2:]
        chunk_x, chunk_y = map(int, coords.split(','))

        # Load the image
        img = np.array(Image.open(file))
        xs, ys = np.where(img.any(axis=2))
        colours = img[img.any(axis=2)]

        # Parse the Blocks
        for x, y, colour in zip(xs, ys, colours):
            self[chunk_x * size + x, chunk_y * size + y] = Element(*colour)

```

Note that this code isn't properly tested so it probably contains bugs, I'm posting it more for demonstration's sake.

My question concerns the `TODO` part in the above code. Splitting the image into chunks obviously decreases the efficiency of PNG compression and thus increases overall file size. This is particularly true in the case of small regions on intersections of chunks. The main idea of the process described in the `TODO` is to only save each distinct region on the grid as its own PNG file, where regions have a lot of empty space between them. While the grid can easily expand to dimensions upwards of a million, populated regions are expected to be at most a few thousand units large. The below image illustrates the idea of the algorithm (the colours represent elements, the chunkified regions are black and empty space is white).

I also thought of doing something BST-based but I don't think a tree would help in the case of chunks that are close in coordinate space, but far away on the tree. For instance, (0, 0) and (0, -1) are neighbours in coordinate space, but in the tree you'd have to go all the way to the root and back down the tree to get to the other one.

My question is, since I don't want to reinvent the wheel, is there some sort of existing approach to such region-searching on a grid? Or in general, a more efficient way to save such a sparse grid?

# Answer
I think you've gotten yourself on the wrong path by trying to use PNG, splitting up into multiple chunks so the PNG files aren't too big, etc.

Instead, store your data using any sparse matrix datastructure. There are many simple schemes. As you suggest, "a dictionary mapping coordinates to elements" is a reasonable data structure. I suggest storing that directly. There are many ways you could serialize it to disk efficiently. There is no reason to go through PNG or via splitting into chunks.
> 1 votes

---
Tags: search-trees, python, square-grid, sparse-matrices
---


title: Memory efficient undo data structure

text:
# Question
Title: Memory efficient undo data structure
I was playing a puzzle game and started wondering how they implemented their undo feature. The game only has five possible moves, and only when the player does a move does the game state change, but the game state can be quite complicated.

The standard undo implementation would be to keep track of a stack of all past game states. However, since the game state can get quite complicated, this can end up taking up a lot of memory.

Assuming the game state changes deterministically, a more memory efficient implementation would be to only keep track of all performed moves, because they require way less memory. However, an undo operation would then require recalculating all past moves which would take up a lot of processing power instead.

I was wondering if there is any literature on a data structure that tries to optimize both. Intuitively, I expect it to be possible to implement a data structure that only requires storing a logarithmic number of game states while also requiring a logarithmic number of move calculations for every undo operation. Of course this still requires storing all past moves, but the assumption is that this is significantly less memory than storing all past game states.

To be clear, I have some ideas myself of how this could be implemented. I am mostly interested in whether there already exists some literature on the topic, because I was unable to find any.

For some context, the game that made me bring this into question is called baba is you. I suspect they simply store a log of changes to the game state rather than the entire game states, because this usually, though not always, requires significantly less memory. However, it still made me wonder about this. Moreover, the game state does not always change deterministically in baba is you, but this could be fixed by storing some rng seed together with the performed moves.

# Answer
Yes. A relevant technical term is 'persistent data structure'. (See also .) There are many techniques for building persistent versions of standard data structures (trees, lists, arrays, etc.), so you can represent your state as a standard data structure, then replace all of those data structures with persistent versions.
> 1 votes

---
Tags: data-structures, reference-request, stacks, computer-games
---


# Question
Title: Are 2 independent PDAs equivalent to a turing machine?
I was thinking about the language $a^nb^nc^n$, which is obviously not context free, but if we run it through 2 automata at the same time (the first for $a$ and $b$ and the second for $b$ and $c$ and they both accept, the construction would basically accept the language)

# Answer
> 7 votes
No, such a construct can recognise at most the intersection of two context-free languages. To see where it's lacking, consider $L = \\{\textsf{a}^n~|~n\in\mathbb{N}~\text{is composite}\\}$. I conjecture that to express $L$ as the intersection of CFLs requires infinitely many CFLs.

The paper *An infinite hierarchy of intersections of context-free languages* by Liu and Weiner (Math. Systems Theory 7, 185–192 (1973). https://doi.org/10.1007/BF01762237) presents languages that can be written as intersection by $k$ context-free languages but not by intersecting $k-1$-languages. For $k=3$ the language is $\\{\\; a^k b^\ell c^m a^k b^\ell c^m \mid k,\ell,m \in \mathbb{N}\\}$. Thus, that language is the intersection of three cf-languages, but not the intersection of two cf-languages. For other $k$ the same pattern is repeated. The quote that paper "The proof is quite complicated".

The language $\\{\textsf{a}^n\textsf{b}^n\textsf{c}^n\textsf{d}^n\textsf{e}^n~|~n\in\mathbb{N}\\}$ seems as complicated but is in fact the intersection of two cf-languages: $\\{ \textsf{a}^m\textsf{b}^m\textsf{c}^n\textsf{d}^n\textsf{e}^p \mid m,n,p\in \mathbb N \\} \cap\\{ \textsf{a}^m\textsf{b}^n\textsf{c}^n\textsf{d}^p\textsf{e}^p \mid m,n,p\in \mathbb N \\} $.

# Answer
> 6 votes
What you actually ask is: can language of every grammar be represented as an intersection of two context-free languages?

The answer is **no**.
To prove that, we can observe that, while the class of context-free languages is not closed under intersection, the class of context-sensitive languages is. This means that intersection of two CFLs is always a CSL (since every CFL is also a CSL). If you could represent language of every grammar as an intersection of two (or, in general, any $k\in\mathbb{N}$) CFLs, it would mean that every grammar has context-sensitive language, which we know is not true.

# Answer
> 3 votes
The language $\\{a^nb^nc^n | n \in \mathbb{N}\\}$ belongs to a strict subset of context-sensitive languages that can be expressed in terms of an intersection of two context-free languages.

Having two PDAs cannot recognize a language like $\\{a^nb^nc^nd^ne^n | n \in \mathbb{N}\\}$.

---
Tags: formal-languages, turing-machines, pushdown-automata
---


# Question
Title: Show Recognizing two Regular Expressions as equal is in PSPACE
If I have $EQ\_{REX} = \\{\langle R,S \rangle|\text{ $R$ and $S$ are equivalent regular expressions}\\}$, how do I show that $EQ\_{REX}\in PSPACE$ ?

What I know so far is that there are decidable algorithms for transforming a regular expression into a NFA and then into a DFA, but these algorithms can take a long time and produce a DFA that takes up exponential space. I also know that $EQ\_{DFA}$ is decidable.

So $EQ\_{REX}$ is provably decidable because you can turn *R* and *S* into DFAs and then show that the DFAs are equivalent. But I'm not sure how to analyze the complexity of a machine like this, and something tells me that it is not in **NP**.

Is there a way to show that this particular machine is in **PSPACE** (or **NPSPACE**, because they are equivalent)? How would I analyze its complexity? Or am I taking the wrong approach entirely, and should instead try to show that this problem is reducible to some other **PSPACE-complete** problem?

# Answer
> 5 votes
Hint: One obvious algorithm for this problems goes as follows. Given two regular expressions $R,S$, convert them to NFAs $N\_R,N\_S$ and then to DFAs $D\_R,D\_S$. Using the product construction, construct a DFA for $D\_R \Delta D\_S$ (here $A \Delta B$ is the symmetric difference), and check whether the language it accepts is empty.

While this algorithm doesn't quite use polynomial space (why?), you can follow the same general plan to solve your problem. It might be helpful to use NPSPACE=PSPACE or perhaps coNPSPACE=PSPACE.

---

Here is a complete answer. Let $R,S$ be two regular expressions. The idea is that if $L(R) \neq L(S)$ then there is a word in $L(R) \Delta L(S)$ whose length is at most exponential in $|R| + |S|$ (where $|R|$ is the length of $R$). This puts your problem in coNPSPACE=PSPACE, since you can guess and verify such a word.

Indeed, once you convert $R$ and $S$ to (polynomial size) NFAs, you can keep track of the set of possible states in both NFAs, and so verify that a word is accepted by one or not the other. You also need your machine to terminate if it guessed wrong, so you need to limit the length of the word to exponential in $|R| + |S|$. Fortunately, counting up to $\exp(|R|+|S|)$ takes only a polynomial size counter.

It remains to show that if $L(R) \neq L(S)$ then there is an exponential size witness. Indeed, the DFA for $L(R) \Delta L(S)$ has exponential size: the DFAs for $L(R)$ and $L(S)$, constructed from the corresponding NFAs, have exponential size, and the product construction maintains this property for $L(R) \Delta L(S)$. Finally, it is known that if a DFA with $n$ states accepts some word, then it accepts some word of length less than $n$.

# Answer
> 1 votes
A good account of this result is in the lecture notes of Dexter Kozen, although the original work of Meyer and Stockmeyer contains a refined space bounds. You may consult that version in Stockmeyer's thesis, proposition 4.11 and theorem 4.13, for instance.

For the part on showing that if the languages are inequivalent then the algorithm accepts it comes handy to use Theorem 10 of Rabin and Scott paper.

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


# Question
Title: Is there an algorithm for the distrubution of ducks into ponds?
**The following is small-scale example is meant to illustrate the general distribution problem**

Consider 4 parks, each with exactly 1 pond. Parks are marked as vertices in the following undirected graph:

Each park has a number of ducks in them, and each pond has a maximum capacity of ducks (the parks themselves do not have a max capacity):

* Park A has 8 ducks and its pond has a max capacity of 5 ducks.
* Park B has 4 ducks and its pond has a max capacity of 6 ducks.
* Park C has 10 ducks and its pond has a max capacity of 4 ducks.
* Park D has 11 ducks and its pond has a max capacity of 9 ducks.

Now, all ducks have to fly to a pond in *another* park. Ducks can only fly to adjacent parks as marked by the edges - or they can fly away if all adjacent ponds are full (meaning that surplus/leftover ducks are not important wrt. the objective and can be ignored). The **objective** is to fill all ponds to their max capacity.

Is there an algorithm or a class of algorithms that can be used for this problem? I am not interested in the solution for the example, but rather more general approaches (though you are of course welcome to use the example to demonstrate a general approach).

Cheers!

# Answer
This can be solved with max-flow: create a bipartite graph with parks on one side and ponds on another, have an edge with infinite capacity if a duck from park A can fly to pond B, and for each park have an edge from the source to it whose capacity is the number of ducks at that park, and for each pond an edge to the sink with the pond's capacity.
> 2 votes

---
Tags: algorithms, graphs, combinatorics
---


title: State Machines as Functors

text:
# Question
Title: State Machines as Functors
I'm looking for more examples of the following model of state machines:

in David Spivak's book on category theory, he gives in section 3.1.2.10 and in application 4.3.1.9, a description of a finite state machine in terms of category theory. The basic definition is that you fix an alphabet $\Sigma$ and take the list monoid $\mathcal{M} := (list(\Sigma), ++, \[\])$, then describe the state machine as a functor $X : \mathcal{M} \to \mathsf{Set}$. Given two state machines $X$ and $Y$ (described as functors), you can talk about "refinement" via natural transformations $\alpha : X \Rightarrow Y$. The story seems to end here.

This is an interesting model of state machines. I've never seen it before, and I am having trouble finding similar descriptions of state machines. I would like to see how far it has been (can be?) extended. E.g., talk about things like bisimulations, language acceptance, turing machines, computability, etc. Does anyone have more sources?

# Answer
> 2 votes
A very similar construction/viewpoint has been recently studied by Colcombet and Petrişan in \[CP20\]. They see a deterministic finite automaton as a functor $$\mathcal{A} \colon \mathcal{I} \to \mathsf{Set}$$ where $\mathcal{I}$ is the category induced by the three objects $\textsf{initial}$, $\textsf{states}$ and $\textsf{accept}$, whose morphisms are generated by:

* a morphism $i\colon \textsf{init} \to \textsf{states}$,
* a morphism $f\colon \textsf{states} \to \textsf{accept}$, and
* for each letter $a\in\Sigma$, a morphism $a\colon \textsf{states} \to \textsf{states}$.

Moreover, they add the restriction that $\mathcal{A}(\textsf{init})$ has cardinality 1, and $\mathcal{A}(\textsf{final})$ has cardinality 2. This construction is based exactly on the same idea as the one in David Spivak's book, except that his construction cannot specify initial states and final states.

One thing that is quite pleasant with this approach is that you can obtain other classical automata models by changing the category used in the codomain of $\mathcal{A}$ (and the constraints on $\mathcal{A}(\textsf{init})$ and $\mathcal{A}(\textsf{final})$). For instance, non-deterministic automata are obtained by considering the category $\mathsf{Rel}$, and weighted-automata over a field $\mathbb{K}$ by taking the category of $\mathbb{K}$-vector spaces.

A soft introduction to \[CP20\] can be found in \[slides by Petrişan\] starting from page 21. However, I do not know of any work modelling a Turing machine (or a machine with the ability to write) using the framework of category theory.

---
Tags: computability, automata, simulation, category-theory
---


title: lower bounds for exact algorithms

text:
# Question
Title: lower bounds for exact algorithms
I am working on building exact algorithms for NP-hard problems. Let's consider an NP-hard problem $P$. The brute force approach runs in $2^n$ time. In order to prove that there is no $2^{o(n)}$ time algorithm for $P$, we provide a reduction from the 3-SAT problem (Assuming ETH holds).
I want to prove that no exact algorithm exists that runs in time $c^n$ for any value of $c$ less than two. In other words, I would like to prove that there is no better algorithm than brute force. How is this done?

# Answer
That is very unlikely to be true, because the problem size n will depend on exactly how problem instances are represented.

If one representation is 20% larger, then the time to solve the problem is unaffected, but the time would be not $2^n$ but $2^{n/1.2}$ or $c^n$ for $c = 2^{1/1.2}$.

And many problems have solutions that are exponential but much faster than $2^n$.
> -1 votes

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


# Question
Title: Minimum edges removed to turn a strongly connected graph into an acyclic graph
If I start with a directed graph that is strongly connected, is there a straightforward way / algorithm to find the smallest set of edges to remove, such that the result is a directed but acyclic graph?

To be clear, the result is neither necessarily a tree (could have more than one way from A to B), nor is the graph still connected, could have disconnected components. I just can't have cycles.

# Answer
> 1 votes
This is a classic NP-complete problem called Feedback Arc Set.

The problem is solvable in fixed parameter tractable time $k^{O(k)}$, and there is an approximation algorithm, however it's open whether there is a constant factor approximation.

The word *feedback* refers to a cycle in a graph, and the problem is "hitting" all cycles with as few arcs (directed edges) as possible.

Note that deleting an arc is equivalent to reversing it(!)

In so-called tournament graphs (compete digraphs), the problem is slightly easier. In undirected graphs, the problem is MST.

---
Tags: algorithms, graphs, dag, directed-graphs, connected
---


# Question
Title: What does the set {n | n is an integer and n = n + 1} represent?
I am reading Michael Sipser's book *Introduction to the Theory of Computation*, which mentions the set $$S = \\{ n \mid \text{$n$ is an integer and $n = n + 1$}\\}.$$ This doesn't make any sense to me. I would understand if $n$ were equal to infinity or something, so it probably wouldn't matter if we added $1$ to it. Am I understanding it correctly? Or is this just an empty set?

# Answer
But infinity isn't an integer. Since there is no integer $n$ such that $n=n+1$, you're right that the set is empty.
> 18 votes

# Answer
This is an empty set which is usually denoted by {}. In this case, the integer *n* is equal to itself while incremented by 1 which is mathematically impossible. Thus, this is an empty set.

EX: n = 2, then n = n + 1, 2 = 2 + 1. This is impossible.
> -1 votes

---
Tags: terminology, computability, number-theory
---


# Question
Title: Number of matchings in a bipartite graph having missing edges
Suppose we have a bipartite graph with $N$ vertices on either side. In the full bipartite graph, the number of edges is $N^2$ and the number of possible matchings (i.e. assignments) is $N!$.

Now suppose a few known edges ($O(1)$ edges) are missing from the full bipartite graph.

How can we find the number of matchings?

Is there a closed formula?

# Answer
> 1 votes
The problem is #P-hard, which means it is believed that there is no efficient algorithm for this problem.

See Counting and finding all perfect/maximum matchings in general graphs and Number of Matchings in a Bipartite.

When the number of missing edges is small, e.g., a fixed constant, there are algorithms whose running time is polynomial in $N$ (but exponential in the number of missing edges), via the inclusion-exclusion principle.

---
Tags: graphs, combinatorics, matching, assignment-problem
---


# Question
Title: Finding a cycle of length log(n) given min degree
Let $G = (V, E)$ be an undirected graph such that every $v\in V$ has $\deg(v) \geq 3$. We must create an algorithm that outputs a cycle of length O(log(n)) if it exists. This algorithm must return in linear time. If such a cycle exists return True, if it doesn't return False.

I had a couple ideas of where to start, but didn't really have a good way to tie them together. My first idea was construction of this graph. Since it has at least degree of 3 I noticed it can always be in a tree-like structure like so:

it can extends further down. It is shaped like this because of the minimum degree 3 requirement. If we inspect the length for the tree we can see the distance is $\log{n}$ edges of height.

After this we could maybe run an algorithm for cycle finding?? I'm just looking for ideas of how to do this problem in linear time in a clean and concise way, any help would be great.

# Answer
> 1 votes
Assume that the graph is non-empty, pick an arbitrary vertex $s$ and construct the first $\lceil \log n \rceil$ levels of the BFS tree $T$ from $s$.

You will encounter some non-tree edge $(u,v)$ in the process. This is trivially true when $n=4$, as the only possible graph that satisfies the degree constraints is $K\_4$ (the case $1 \le n \le 3$ is impossible), therefore we assume $n \ge 5$. If no non-tree edge is encountered, then the number of vertices in the first $\lceil \log n \rceil$ levels of the tree must be at least $1 + 3 \cdot \sum\_{i=0}^{\lceil \log n \rceil -2} \ge 1 + 3 (2^{\log n - 1} -1) = 1+ \frac{3}{2}n - 3 = \frac{3}{2}n-2 \> n$, which is a contradiction.

The edge $(u,v)$ provides you with a cycle of length at most $2 (\lceil \log n \rceil - 1) + 1$. This cycle is is obtained as the union of $(u,v)$ with the unique path from $u$ to $v$ in $T$.

---
Tags: algorithms, graphs, trees
---


title: RISC-V execution model

text:
# Question
Title: RISC-V execution model
I'm reading a text book on CPU architecture and I have something that confuses me: The text book defines 4 different instruction execution models in CPUs, Stack (where a CPU only has a stack and is able to perform operations on the first and second elements of the stack and push the result back), Accumulator (the CPU loads a value from the memory and add it to the current accumulated value), Register-Memory (where a CPU has a regiser and performs operations on values from both the memory and the register), Register-register (where a CPU performs operations on values that are only stored in the register). Each execution model has a different format of instructions, my question is, which of these models is used by the RISC-V architecture? because it seems to be, when looking at the RISC-V ISA, that it does all of the above.

# Answer
In the terminology that you're using, RISC-V is a register-register ISA.

For integer and floating point instructions:

* All arithmetic and logic operations take registers as operands and write the result to a register.
* The only operations that access memory are load and store operations.
* There is no dedicated accumulator register.
* There is no dedicated stack pointer register. The ABI might specify one, but the hardware does not.

While they are not all requirements, together they imply a register-register ISA.

There is one main exception: The RISC-V "A" extension supports atomic read/modify/write memory operations (e.g. atomic swap, atomic add, etc).
> 3 votes

---
Tags: computer-architecture, cpu, risc-v
---


# Question
Title: Why are seeds connected in Linear Congruential Generators?
I looked through `Java`'s `Random` class and saw that the initial seed is created using:

```
public Random() {
        this(seedUniquifier() ^ System.nanoTime());
    }

```

But every consecutive seed is derived from old seed using:`nextseed = (oldseed * multiplier + addend) & mask;`

Why is that? Why not use system time everytime?

# Answer
The first time your program asks for the system time, it's more or less random. Specifically, if the clock really does have nanosecond resolution, then the lowest-order 30 bits or so are truly unpredictable.

The second time your program asks for the system time, your deterministic program receives a number that is quite predictable if you already had the first result. Say the second call happens a millisecond, plus or minus a microsecond, later. There is a certain amount of jitter in the system, but you would be lucky if you obtained about 10 bits of additional entropy from this second call.

And this is assuming that your system clock really does have nanosecond precision, which may not be true. Remember, Java was designed to run on much lower-speed CPUs (e.g. microcontrollers and smartcards) than you are probably programming on.
> 1 votes

---
Tags: randomness, pseudo-random-generators, random-number-generator
---


# Question
Title: Compiler that compiles to a Turing machine?
I am interested in finding/writing a compiler that compiles a program written in a simple source language to a Turing machine (instead of assembly). Does anyone know if there is a good approach for writing such a compiler, or if there is a Turing machine compiler already out there (that would be ideal)? Of course it is possible to do this in theory; it's just that it's very challenging (for me at least) to work out the details in practice.

# Answer
**Laconic**

This is the highest profile attempt I've heard of so far. It was announced on this paper by Adam Yedidia and Scott Aaronson: https://www.scottaaronson.com/busybeaver.pdf and on this blog post by Scott: https://scottaaronson.blog/?p=2725

**Laconic language features**

Data types:

* integer:

```
int myInteger;

```
* list of integer: `list`
* list of `list`: `list2`

Variable assignment with `=` and built-in integer functions such as addition `+` and multipication `*`:

```
int x;
x = 1;
x = (a+b)*c

```

"Functions", though a better term for them would be "macros", since they have no scope, no return value, and just directly modify variables globally:

```
func addY(x, y) {
 x = x + y;
 return;
}

```

C-like `if` and `while` constructs, e.g.:

```
while (x < y) {x = x+1;}

```

The video also mentions the `print` statement for debug purposes:

```
print x;

```

Here's the full Goldbach program to give a better idea:

```
func zero(x) {
    x = 0;
    return;
}

func one(x) {
    x = 1;
    return;
}

func incr(x) {
    x = x + 1;
    return;
}

/* Computes x modulo y */
func modulus(x, y, out) {
    out = x;

    while (out >= y) {
        out = out - y;
    }

    return;
}

func assignXtoYminusX(x, y) {
    x = y - x;
    return;
}

/* Figures out if x is prime, and puts the output in y */
/* Does not modify x, modifies y */
func isPrime(x, h, y) {
    if (x == 1) {
        zero(y);
        return;
    }

    y = 2;

    while (x > y) {
        modulus(x, y, h);

        if (h == 0) {
            zero(y);
            return;
        }
        incr(y);
    }

    return;
}

int evenNumber;
int primeCounter;
int isThisOnePrime;
int foundSum;
int h;

evenNumber = 2;
one(foundSum);

while (foundSum) {
    zero(foundSum);
    evenNumber = evenNumber + 2;
    one(primeCounter);

    while (primeCounter < evenNumber) {
        isPrime(primeCounter, h, isThisOnePrime);

        if (isThisOnePrime) {
            assignXtoYminusX(primeCounter, evenNumber);
            isPrime(primeCounter, h, isThisOnePrime);
            assignXtoYminusX(primeCounter, evenNumber);

            if (isThisOnePrime) {
                print evenNumber;
                print primeCounter;

                one(foundSum);
            }
        }

        incr(primeCounter);
    }
}

halt;

```

**Not-Quite-Laconic (NQL)**

https://github.com/sorear/metamath-turing-machines

This project proposes a Laconic-like language but with a different compilation technique that has led to smaller Turing machines in certain cases of interest, from the README:

> Not-Quite-Laconic is a language and compiler for generating Turing machines with small state counts. It is directly inspired by Adam Yedidia's Laconic, and the language is similar, but the implementation is less so. Laconic and the programme of constructing small Turing machines to establish upper bounds on provable BB(k) values are discussed on Scott Aaronson's blog.
>
> NQL uses a different compilation methodology based on register machines and constructing binary decision diagrams to compress large programs without an explicit call stack. It achieves "a few" times smaller state counts than Laconic for the range of programs relevant to the BB(k) problem; e.g. 1919 states for a ZF proof enumerator. On very small programs it cannot compete with hand-coding, and behavior on much larger programs is unknown; Laconic may regain the upper hand,

It appears that most of the newer research has moved from Laconic to NQL, suggesting that it is a superior implementation. E.g. most of the smallest machines listed at https://bbchallenge.org/story#what-is-known-about-bb are in NQL.

Here's their Goldbach program to give an idea:

proc zero(x) {
    x = 0;
}

proc one(x) {
    x = 1;
}

proc incr(x) {
    x = x + 1;
}

/* Computes x modulo y */
proc modulus(x, y, out) {
    out = x;

    while (out >= y) {
        out = out - y;
    }
}

proc assignXtoYminusX(x, y) {
    x = y - x;
}

/* Figures out if x is prime, and puts the output in y */
/* Does not modify x, modifies y */
proc isPrime(x, h, y) {
    if (x == 1) {
        zero(y);
        return;
    }

    y = 2;

    while (x > y) {
        modulus(x, y, h);

        if (h == 0) {
            zero(y);
            return;
        }
        incr(y);
    }
}

global evenNumber;
global primeCounter;
global isThisOnePrime;
global foundSum;
global h;

proc main() {
    evenNumber = 2;
    one(foundSum);

    while (0 < foundSum) {
        zero(foundSum);
        evenNumber = evenNumber + 2;
        one(primeCounter);

        while (primeCounter < evenNumber) {
            isPrime(primeCounter, h, isThisOnePrime);

            if (0 < isThisOnePrime) {
                assignXtoYminusX(primeCounter, evenNumber);
                isPrime(primeCounter, h, isThisOnePrime);
                assignXtoYminusX(primeCounter, evenNumber);

                if (0 < isThisOnePrime) {
                    /* print evenNumber;
                    print primeCounter; */

                    one(foundSum);
                }
            }

            incr(primeCounter);
        }
    }
    return;
}
```

> 4 votes

# Answer
It's my first approach. I also want to add functions and variables in future. https://github.com/kamosevoyan/TuringLanguage\_compiler
> 0 votes

---
Tags: turing-machines, compilers
---


title: Use of pointers in linked list

text:
# Question
Title: Use of pointers in linked list
The following code is from GeeksForGeeks

```
void deleteN(Node** head, int position)
{
    Node* temp;
    Node* prev;
    temp = *head;
    prev = *head;
    for (int i = 0; i < position; i++) {
        if (i == 0 && position == 1) {
            *head = (*head)->next;
            free(temp);
        }
        else {
            if (i == position - 1 && temp) {
                prev->next = temp->next;
                free(temp);
            }
            else {
                prev = temp;

                // Position was greater than
                // number of nodes in the list
                if (prev == NULL)
                    break;
                temp = temp->next;
            }
        }
    }
}

void printList(Node* head)
{
    while (head) {
        printf("[%i] [%p]->%p\n", head->number, head,
            head->next);
        head = head->next;
    }
    printf("\n\n");
}

```
1. Why are we calling a pointer to the head pointer that already represents the entire linked list in the delete function? Why are we not doing the same in the display function?
2. What is the difference between traversing via `*head=(*head)->next` and \`\`\` head=head-\>next \`\`\` methods?

# Answer
> 0 votes
That's poorly written, confusing code, and it would be better not to study it too closely. That said, there is a good reason it takes a `Node**`. The pointer to the first node may change when deleting a node, if the deleted node is the first one, so `deleteN` has to communicate the new value to the caller. It could have done that by returning it, in which case calls to `deleteN` would have to look like

```
head = deleteN(head, position);

```

But if you did it that way, accidentally ignoring the return value would silently produce buggy code (and the worst kind of buggy code—undefined behavior—because `head` would be left pointing to a freed heap object). So it's probably better to do what they did, and make the caller pass `head` by reference so that it can't fail to be updated.

`*head = (*head)->next` is not traversing the list. It's updating the caller's pointer, and it happens at most once per call of `deleteN`.

# Answer
> 0 votes
In deleteN, head needs to be a pointer to pointer, because its value might be modified in the function (due to that miserable lack of by-reference argument passing). In printList, it is a plain pointer.

Note that calling both arguments the same way is poor practice (ppHead and pHead could have been better; this emphasizes than in all accesses ppHead requires one more indirection than pHead).

ppHead= ppHead-\>next would just not work, as ppHead is a pointer to a pointer, and does not have a next field (it has no field at all).

---
Tags: data-structures, linked-lists
---


title: Knapsack with fixed size

text:
# Question
Title: Knapsack with fixed size
We have $3n$ items with profits $p\_1, \dots, p\_{3n}$ (sum = $P$) and weights $w\_1,\dots,w\_{3n}$ (sum = $W$). We want to determine whether we can choose **exactly** $n$ items with profit at least $P/2$ and weight at most $W/2$.

Is this problem NP-hard? It is very similar to the usual knapsack problem, but the constraint of choosing exactly $n$ items makes it difficult to reduce directly from knapsack.

# Answer
The problem is NP-Hard. You can reduce from the partition problem: given a multi-set $X = \\{x\_1, \dots, x\_n\\}$ of non-negative integers, is there a subset $S$ of $X$ such that $\sum\_{x \in S} x = \frac{1}{2} \sum\_{x \in X} x$?

To obtain an instance of your problem you can create one $y\_i$ for each integer $x\_i$ and set $p\_i = w\_i = x\_i$. Then create $2n$ additional "dummy" items with weight 0 and profit 0.

If there is a solution $S = \\{x\_{i\_1}, \dots, x\_{i\_k}\\}$ to the partition instance, then you can obtain a solution to your problem by selecting the items $y\_{i\_1}, \dots, y\_{i\_k}$ plus $n-k$ dummy items.

If there is a solution to the instance of your problem with non-dummy items $y\_{i\_1}, \dots, y\_{i\_k}$ (and any number of dummy items) both the total weight and the total profit of the selected items must be exactly $\frac{1}{2} \sum\_{x \in X} x$. Then, the set $S = \\{x\_{i\_1}, \dots, x\_{i\_k}\\}$ is a solution for the partition instance.
> 2 votes

---
Tags: np-hard, knapsack-problems
---


title: Proving asymptotic classes

text:
# Question
Title: Proving asymptotic classes
I am trying to teach myself asymptotic notations. I feel like I'm in over my head. I read the explanations in the text book, and Khan Academy. But when I try to do proofs, I can't grasp anything.

I'm trying to prove that If f (n) = ω(g(n)), then f (n) is not in O(g(n)) or o(g(n)).

I know that they don't intersect, as ω proves the lower bound (not tight) and O and o prove upper bounds. But I have no idea how to set up a proof to solve this.

Any help would be appreciated.

# Answer
> 0 votes
With a simplified notation, $\omega$ holds if $\forall\\,c:f\>c\\,g$, while $O$ holds if $\exists\\,c: f\le c\\,g$.

These are obviously contradictory statements.

---
Tags: algorithm-analysis, asymptotics
---


title: Dangling else determinism

text:
# Question
Title: Dangling else determinism
The natural grammar for dangling "else" is ambiguous. But there exists an unambiguous version of the grammar that links the "else" to last uncompleted "if" statement. Is this version also deterministic? Is this language deterministic?

Natural grammar (ambiguous): $$ S \rightarrow if~expr~S | if~expr~S~else~S | cmd $$

Unambiguous grammar: $$\begin{align\*} S &\rightarrow U~|~F\\ U &\rightarrow if~expr~S~|~if~expr~F~else~U\\ F &\rightarrow if~expr~F~else~F~|~cmd \end{align\*}$$

# Answer
As pointed by @Pseudonym a context-free language is deterministic if and only if it has a grammar such that is $LR(k)$, for some $k$.
Let's take $k = 1$, the grammar is $LR(1)$ (and $LALR(1)$) so it is deterministic.
> 0 votes

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


# Question
Title: Complex search algorithm - Points on a sphere - Best approach
I have a very complex search problem which I can't wrap my head around:

> While reading please remember I'm not asking for a specific solution! Only a general approach how such a problem can be solved and what kinds of algorithms to use (more below)

I have a sphere with around **120 000** weighted and named points mapped on its surface.

Now I take a section out of the sphere with somewhat around 10 of the highest weights (not guaranteed the 10 hightest weights!)

The Problem: **I want to find the spot where the section was taken out, so that i could assign each point the "name" it would have had on the sphere**

---

Characteristics of the points **on the sphere**.:

* 120 000
* The coordinates are exact
* The points are weighted

---

Characteristics of the points **in the sector**:

* The points are also weighted. The proportions are *roughly* the same as on the sphere, unfortunately I don't know a single inital weight. So my only chance is to compare the proportions.
* Not every point which is on the sphere is also visible in the section (sometimes only 5-10%). However the weigths matter:

+ The hightest weighted points do always appear.
    + The first non-visible points have guaranteed less weight than most of the visible points.
* The section could be rotated
* All points are a bit offset (not by much), but they aren't exactly on the spot where they were on the sphere
* Other errors could be possible too (like counting 2 points only once)

---

Additional info which might make the problem simpler:

* The sector is only around 1°x1° to 5°x5°. So maybe i could use a flat map instead of a sphere. (Just like Google Maps if you zoom out enougth
* The first non-visible points have guaranteed less weight than most of the visible points.

---

What I'm asking for:

> What is the **general approach** to solve this problem? Are there *any algorithms* you might now on which I can orientate myself?
>
> Anything between pure **brute-force** and **AI** is welcome!

---

Example image of a sector region which is detected by my algorithm: (A larger red rectangle = higher weight)

---

If you think this is a good question please consider upvoting to draw attention.

# Answer
Let me start by suggesting a brute-force method, then suggest some ways to speed it up:

Pick a pair of (high-weight) points $P\_0,P\_1$ in the sector. For each pair of points $Q\_0,Q\_1$ on the sphere, guess that maybe $P\_0=Q\_0$ and $P\_1=Q\_1$: align the sector (rotate & translate it) so that $P\_0$ is on top of $Q\_0$ and $P\_1$ is on top of $Q\_1$. There is a unique way to do this. Then check your candidate placement of the sector, by mapping the sector onto the globe and looking at all the other points in the sector to see how well they match the points on the sphere. If you enumerate all pairs of points $Q\_0,Q\_1$ on the sphere, you're guaranteed to find the correct placement of the sector for at least one of them. So, this algorithm works, at the cost of being slow: it takes $O(n^2)$ time, where $n$ is the number of points on the sphere.

You can dramatically speed this up in several ways.

First, you can filter by the distance $d(P\_0,P\_1)$ between the two points. Instead of enumerating all points $Q\_0,Q\_1$, only enumerate pairs $Q\_0,Q\_1$ such that $d(Q\_0,Q\_1) \approx d(P\_0,P\_1)$. How do you do that? You enumerate all possibilities for $Q\_0$, and for each such $Q\_0$, enumerate all points $Q\_1$ that are at distance approximately $d(P\_0,P\_1)$ from $Q\_0$. The latter can be done using a data structure for nearest neighbor search. If you choose two points $P\_0,P\_1$ that are close to each other, probably there will be only a small number of points $Q\_1$ at that distance from $Q\_0$. So, heuristically, the running time might become much closer to $O(n)$.

Second, you might be able to filter using the weights. You could pick a pair of high-weight points $P\_0,P\_1$ in the sector, and only consider points $Q\_0,Q\_1$ whose weights are above some threshold. You'd have to experiment how to choose that threshold. Or, you could enumerate the points $Q\_0$ in sorted order of the weight, highest weight first.

You can increase robustness to small errors in the location of the points in the sector by repeating the above multiple times for multiple different choices of $P\_0,P\_1$.
> 1 votes

# Answer
I think this sounds like a pretty fascinating question.

If you can simply normalize all the weights to be between 0 and 1, both on the initial sphere and in the segment, then you can get the weight values to be comparable.

If that does not work, one algorithm I would try would be using a weighted k-means clustering algorithm both on the initial sphere, and also on the segment which you receive. This algorithm is discussed somewhat in this paper:

*On Initializations for the Minkowski Weighted K-Means*

I would suggest performing k-means in a way that you have a proportional number of clusters in the rectangular segment as compared to the number of points.

10 clusters for 5000 points in the segment? 240 clusters for the large sphere.

Now, once we have the membership of each point in each segment, (i.e. which centroid each one belongs to) we take each point and redefine it as a proportion of either the average value of its segment, or of the maximum value in its segment.

This normalizes all of the weights in a way that preserves the local proportions. Then, you could compare your clusters inside the segment to the clusters and shapes in the whole sphere.

This should be more robust if the proportions are locally a lot more similar to the original proportions than they would be globally.

A third option could be to treat these like constellations, and use a constellation finding approach.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Is there an oracle $A$ with $P^A = NP^A$, but $EXP^A \not= NEXP^A$?
Is there an oracle $A$ with $P^A = NP^A$, but $EXP^A \not= NEXP^A$ ?

I found a proof with padding arguments (wikipedia), that $$ P = NP \Rightarrow EXP = NEXP $$ If an oracle $A$ exists with $P=NP$ and $EXP\not=NEXP$ relative to $A$ then the padding technique would be a proof methode, that circumvents the Relativization Barrier.

Maybe padding arguments can help to solve problems like P vs. NP.

# Answer
Yes, there is an oracle with $P^A = NP^A$ and $EXP^A \not= NEXP^A$.

It is an exercise in Odifreddi: Classical Recursion Theory Vol. II on page 253. An example is in Kurtz : Sparce sets in NP - P: relativization S.I.A.M J. Comp. 14(1985) 113-119
> 0 votes

---
Tags: complexity-theory, p-vs-np, oracles
---


title: product of every difference

text:
# Question
Title: product of every difference
Given a sorted array where every element is distinct, we need to evaluate product of every difference, modulo $ 10^9 + 7 $

$$ \prod\_{i \< j} (arr\[j\] - arr\[i\]) \\% (10^9 + 7) $$

Best approach I can think of is finding frequency of primes in product by grouping elements with same modular residue, which allows $ O(N * M / \log M) $ if $M$ is maximum number in array.

I have considered mathematical ways by polynomial multiplication and divide and conquer, which seems most promising but can't solve completely.

Is there any way to find this for arrays of length upto $ 10^ 5 $, and numbers upto $ 10 ^ 9 $?

# Answer
I think a divide and conquer (D&C) approach is valid, and leads to an $O(n \log^3 n)$ solution (maybe the log exponent can be reduced).

The D&C technique reduces the problem to the following: Given two arrays $A$ and $B$ compute

$$\prod\_{a \in A, b \in B} a - b$$

Consider the following polynomial:

$$P\_A(X) = \prod\_{a \in A} a - X$$

If we can evaluate $P\_A$ on every element of $B$, then the product of all those results gives the desired solution. To compute the polynomial $\prod\_{a \in A} a - X$ you can use a divide and conquer based algorithm and using polynomial multiplication in $O(n \log n)$ you can compute $P\_A$ in $O(n \log^2 n)$.

Once $P\_A$ has been computed, you can evaluate it on every element in $B$ in $O(n \log^2 n)$ time see this answer.

Since every step of the D&C problem is solvable in $O(n \log^2 n)$, the whole problem is solvable in $O(n \log^3 n)$.

Note that the computation of $P\_A$ can be done recursively in the outer D&C as well, so that part should not impart an extra log factor. Therefore the critical part if you want to reduce the complexity is the multipoint evaluation.
> 1 votes

---
Tags: discrete-mathematics, number-theory, divide-and-conquer, polynomials, fast-fourier-transform
---


# Question
Title: Understanding crossover points in efficiency between insertion and merge sorts
Self-taught programmer here. I'm reading CORS, and right at the beginning, question 1.2-2, there asks a question:

> For inputs of size $n$, insertion sort runs in $8n^2$ steps, which merge sort runs in $64n\lg n$ steps. Which values of $n$ does insertion sort beat merge sort?

I simplified this to $n=8\lg n$, and ran it through a CAS, to get two approximations for $n$, $n\approx 1.099$ and $n\approx 43.559$.

I'm unsure how to intrepret these values in relation to the question. My initial assumption is the merge sort is faster for all $n\geq2$, but then we get to $n\geq44$, and... insertion sort becomes faster than merge sort again? That seems impossible.

My first intuitive answer was that whenever $n \< 8\lg n$, insertion is faster. However, once I started to try to attain a value, is when I ran into the two roots and couldn't find a clear explanation.

# Answer
> 1 votes
Understand that the purpose of the exercise is to let you realize that there can be crossover points. But the given functions are imaginary and just mean to show trends. (In practice, the expressions are more complicated and low order terms become dominant for low $n$.) So don't care about small $n$.

Obviously, this MergeSort beats the InsertionSort as of $n=44$, and the advantage becomes larger and larger with $n$. The main lesson is that $O(n\log(n))$ is significantly better than $O(n^2)$.

---
Tags: algorithms, sorting, efficiency, mathematical-analysis
---


title: Complexity of a Set of Formulas

text:
# Question
Title: Complexity of a Set of Formulas
**Notation**: We write $|\alpha|$ to denote the length in characters of an expression $\alpha$ in propositional logic.

Consider an expression $\alpha\_n$ in disjunctive normal form built from $2n$ variables where each conjunct contains $n$ variables chosen from those $2n$ original variables. All $\binom{2n}{n}$ conjuncts are included. We observe that as $n$ grows for $n \geq 2$, $|\alpha\_n|$ is bounded below by $2^n$.

Here is an example over the variables $a,b,c,d$ where $n=2$: $$ \alpha\_2 = (a \land b) \lor (a \land c) \lor (a \land d) \lor (b \land c) \lor (b \land d) \lor (c \land d)$$

**Question**: Let $\beta$ be a Boolean circuit built from the usual operations $\land$, $\lor$, and $\lnot$. Is there an equivalent set of Boolean circuits $\beta\_n$ (where $\alpha\_n \leftrightarrow \beta\_n$ over the $2n$ inputs) such that the growth of $|\beta\_n|$ is polynomially bounded, that is, there is some constant $c$ such that $|\beta\_n| = O(n^c)$? Or is this impossible? Note that what I am asking is not equivalent to counting the number of true variables.

# Answer
Yes. You can build a Boolean circuit $\beta\_n$ of size $O(n \lg n)$, that is equivalent to $\alpha\_n$. It works by counting the number of "true"s among the inputs, compares it to $n$, and outputs true if it is greater or equal, or false if it is less.

What's the size of this circuit? Adding up the number of "true"s can be done with $2n-1$ additions of $1+\lg n$ bit numbers, which takes $O(n \lg n)$ gates. Comparing to $n$ can be done with another $O(n)$ gates. Therefore, the total size of the circuit is $O(n \lg n)$, which is indeed polynomially bounded in $n$, as requested.
> 2 votes

---
Tags: complexity-theory, logic, propositional-logic
---


# Question
Title: What would be an algorithm for calculating the ideal column widths of a table to show on-screen, to minimize the table's height?
I've you've ever had a table of text like in Word or Google Docs, you'd know that there are ideal widths for each table column to minimize the height of the table and fit the most text, here's an example. I've tried thinking about how I could implement that myself, but have no ideas. I wonder if this would be some sort of optimization math equation, but I haven't touched math in forever. If it was, how would it optimize all the column widths? I did some looking up, as well as asking both GPT 3.5 and 4 to write a Python script for this, but they both had issues.

# Answer
> 1 votes
There is a reasonably efficient algorithm for this. I will assume that you have a value $w$ that is the maximum possible width for the table, and you want to find column widths that sum to at most $w$, that minimize the table height. For instance, $w$ might be the width of the page or of the text region on the page.

The solution will be to use binary search repeatedly. In particular, we'll do binary search on the height $h$ of the table.

I assume the text for each column is given. Therefore, given any proposed width $w\_i$ for a column, you can compute the height required for that column (by formatting the text into a box of width $w\_i$).

Now I suggest you use binary search on $h$, the height of the table, to find the minimum achievable height, given that the total table width must be no greater than $w$. Suppose we have a particular $h$. For each column, say the $i$th column, find the minimum width $w\_i$ for that column that ensures its height will be at most $h$ (this can be done using binary search over $w\_i$ combined with the fact from the prior paragraph). This gives a minimum width $w\_i$ for each column. Now compute the sum $w\_1+\dots+w\_k$; if this is greater than $w$, then conclude that height $h$ is not attainable (within the constraint on max table width); otherwise conclude that height $h$ *is* attainable. Continue using binary search on $h$ to find the smallest $h$ that is attainable.

The total running time will be at most something like $O(n^2 \lg^2 n)$, where $n$ is the size of the input. There are probably optimizations to significantly improve this.

---
Tags: algorithms
---


# Question
Title: The updated convex hull algorithms in 2023?
I'm studying the convex hull algorithms in the high dimensions. There were two papers by Bernard Chazelle and T.M. Chan from the 90s, to have achieved the at then the state of the art complexity. However, when I tried to find the recent papers, most of ones I found was about the "approximation" of the convex hull, rather than finding the convex hull accurately.(Within the roundness)

Is there any updated high dimension algorithms that surpassed the ones from Bernard Chazelle and T.M. Chan's papers?

# Answer
> 1 votes
The algorithm by Chazelle in the linked paper, for general dimension, is optimal in terms of worst case asymptotic complexity. So in terms of theoretical results for finding exact solutions, this paper is pretty much the last word. Indeed, Raimund Seidel notes in the chapter on convex hulls from the *Handbook of Computational Geometry* (Third edition, 2018) that

> ...in the sense of asymptotic worst case complexity the convex hull problem has been solved completely...

although he also notes the algorithm from Chazelle is not practical. I recommend reading the chapter to get an idea of the variants of the problem (mostly in terms of the description of the convex hull, which is more important in higher dimensions) and the theoretical status.

---
Tags: linear-programming, convex-hull
---


title: Detecting non-airtight geometry

text:
# Question
Title: Detecting non-airtight geometry
I have a finite region of 3D space that some (arbitrarily-shaped, concave) geometry occupies, and I need to identify whether that geometry forms a closed 3D volume (or multiple disjoint closed 3D volumes). That is, I need to identify if, and where, the geometry isn’t airtight. The geometry is, effectively, a series of one or more rooms (that are ideally closed).

My current strategy is, in a nutshell, to define a valid and invalid area of the entire 3D space, then identify whether there are any paths from the valid area to the invalid area.

To do this, I first find an AABB of the total geometry, double the extents of that AABB, and use the result as the root of an octree. Upon splitting twice, the resulting octree has a “shell” of octants that enclose the geometry, but are themselves empty. The geometry occupies the gooey, nougat center of the octree (the innermost 8 octants at subdivision level 2). After fully finding the leaf nodes of this octree, I run a connected component labelling algorithm to find connected components containing both shell, non-intersecting leaf nodes and nougat non-intersecting leaf nodes. If any connected components contain such a mix, the geometry is reported as having a leak.

This approach, however, reports false positives; all the negative space surrounding the (concave) geometry is filled with non-intersecting leaf nodes that don’t have any notion of being outside the geometry, but are still within the nougat of the tree and, consequently, result in the detection of a leak. **I need to define whether an octree node *should* be contained within a volume bounded by intersecting leaf nodes, and whether it *is* bounded by intersecting leaf nodes.** If there is a discrepancy between the two, I’ve not only found a leak, but the location of that leak.

I have one idea for proceeding, which is to create an alpha shape/complex to create a volume out of the intersecting leaf nodes while “closing up” holes, create another alpha shape constructed with an alpha of 0 (that is, with any holes preserved), then query both of these shapes with every non-intersecting leaf node to find the node’s containment status and note discrepancies between the alpha shapes. I can already see that this approach will, with the variation of the alpha value, erroneously capture certain non-intersecting leaf nodes and mark them as should be inside, and it will also fail to detect leaks that are of a size greater than the alpha value because these holes will not be closed up.

# Answer
> 0 votes
A mesh is airtight if every edge belongs to exactly two faces. It is a purely topological test.

But life can be made harder with multiple vertices having the same coordinates, degenerate faces where edges have been merged, self-intersecting surfaces...

---
Tags: computational-geometry, space-partitioning
---


# Question
Title: Which algorithms could be suitable for solving my disjunctive programming problem?
Following a previous post on the cs stack exchange (link to question), I have been searching to no avail for an implementation of a disjunctive programming solver in C# (or wrapped in C#). In this question, I'll go into more depth in regards to my specific problem in case there is a better solution.

I am looking for an algorithm that can arrange tasks in a non-overlapping manner, whilst also satisfying a reasonably open set of possible conditions - ie: task 1 must happen before task 2, task 2 happens before a set time, task 1 is *favoured* to happen during the day.

I understand that one abstraction of this problem involves sets of inequalities, some of which must be disparate. This leads to the need for disjunctive rather than linear programming (if my understanding of the reply to my previous question is correct). For example:

```
x1 < x2 - d1 OR x2 < x1 - d2  //task x1 and x2 cannot overlap
x3 < x2 - d3 OR x2 < x3 - d2  //task x3 and x2 cannot overlap
x1 < x3 - d1                  //task x3 must happen after x1
x1 < 100                      //task x1 starts before 100

min( [start times st. dev. or similar] )   //example cost function

```

*where x1, x2, x3 are the start times for tasks (variables to be solved) and d1, d2, d3 are their durations (constants).*

The mathematician in my brain sees these sets of inequalities as inefficient however, as their number goes up with the factorial O(n!) so if anyone knows a more suitable approach please do not hesitate to let me know!

Any information you can add is much appreciated, but I am hoping for the name of an algorithm that can solve this sort of problem - preferably one already implemented in C# or with a C# wrapper.

Thanks everyone in advance!

# Answer
The prior answer already explained a standard way to solve this kind of problem: introduce boolean (0-or-1) variables to model the disjunction, and then solve with an off-the-shelf integer linear programming (ILP) solver.
> 1 votes

# Answer
What about using a local search solver like Timefold or LocalSolver? In particular, LocalSolver has a C# API, which seems to address your need.
> 0 votes

# Answer
You can use CPLEX to solve by modeling your problem as MIP or CP.

For the MIP algorithms in CPLEX is branch and cuts algorithms.

For the CP algorithm in CP Optimizer is filter method.

You can refer the official website in Cplex to realize the detailed.

MIP Solver CP Opimizer
> 0 votes

---
Tags: algorithms, linear-programming, integer-programming, mathematical-programming
---


# Question
Title: Could SAT solvers be significantly more efficient if they allowed for non-CNF formula?
SAT Solvers focus on CNF formulas. For many implications it is much mroe natural to use implications and conjunctions to encode problems, and when converting to CNFs, information is lost, and the solver may need to extra work.

Is it possible that if we would rewrite SAT solvers to solve formulae using conjunctions and implications (and actually use that information, not just rewrite to CNF first), that this would open up significant efficiencies for problems that are naturally encoded using conjunctions and implications?

# Answer
That's a natural idea. However, to the best of my knowledge, despite attempts, no one has succeeded in making such an approach do better than just converting to CNF and using an existing SAT solver.

First, I want to note that many implications *are* already natively supported. The implication $u \implies x$ is equivalent to $\neg u \lor x$, which is a CNF clause. Similarly, the implication $(u \land v \land w) \implies x$ is equivalent to $\neg u \lor \neg v \lor \neg w \lor x$, which is also a CNF clause. So many implications (specifically, all Horn clauses) are already in CNF form, and thus no modification to the SAT solver is needed. Also, while implications like $(u \lor v) \implies x$ are not directly in CNF form, they are equivalent to $(u \implies x) \land (v \implies x)$, which in turn is equivalent to $(\neg u \lor x) \land (\neg v \lor x)$, which is a conjunction of two CNF clauses. So this type of implication is also natively supported.

Second, I want to note that no information is lost.

Third, a lot of engineering has gone into SAT solvers, with sophisticated methods, like 2 watched literals, conflict analysis, clause learning, backjumping, and more. It is easier and simpler to implement these methods when every clause is in CNF. If you had multiple forms of clauses, then implementing these methods would be more complicated and harder to maintain. Also it would likely introduce a constant-factor slowdown to have to handle all of these cases. So any speedup from native support for alternative clause formats might be outweighed by the slowdown from code that has to check all of these cases. From an engineering perspective, it makes sense to have a simple API and internal representation of the formula.

I'm not saying there is a fundamental barrier to your idea. I'm saying that there are engineering tradeoffs, and so far as I know, to date the engineering tradeoffs don't seem to favor the approach you identify. That could always change as new methods are discovered.

The only case I know of where extending a SAT solver to support additional clause formats has been successful is CryptoSat/CryptoMiniSat, which contains specialized support for XORs.
> 2 votes

---
Tags: sat-solvers
---


# Question
Title: How to interpret the concept of adjacent initial states in the FLP impossibility paper?
Link: https://dl.acm.org/doi/pdf/10.1145/3149.214121

In the proof for Lemma 2, the authors define two initial states to be adjacent if the only difference between them is the value in the input register $x\_p$ for a single process $p$. Then, they claim that any two initial configurations can be joined by a chain of initial configurations, each adjacent to the next.

However, if two initial states differ in the internal storage of a single process $p$, then there is no way to make them adjacent. The definition of *initial state* seems to include the internal state as suggested from the following excerpt.

> The values in the input and output registers, together with the program counter and internal storage, comprise the *internal state*. *Initial states* prescribe fixed starting values for all but the input register; in particular, the output register starts with value b.

I know this doesn't change the point of the Lemma, as the decision value cannot depend solely on the internal state of some process in an initial configuration, but I was wondering what the authors intended with the precise definition of adjacent initial configurations.

# Answer
I think the authors assume that the processes start with identical (or empty) internal storage. This seems a reasonable assumption: if the internal storage is arbitrary, a process that reads it could be correct by coincidence, or if it were random, then the process can succeed with a certain probability. And if the storage is a function of the input value, then the process might as well compute that function later.
> 0 votes

# Answer
My reading of

> *Initial states* prescribe fixed starting values for all but the input register; in particular, the output register starts with value $b$.

on page 376 is that, for any consensus protocol $P$ considered in the paper, the program counter and the internal storage of every process $p$ are uniquely determined. Otherwise the proof of Lemma 2 does indeed not work.
> 0 votes

---
Tags: distributed-systems
---


# Question
Title: Is there a 2SAT encoding for a NAND gate
I am trying to encode some circuit checking algorithms, but encountered difficulty creating a 2SAT representation for a NAND circuit. Is there a proof that this is not possible?

# Answer
It seems, based on the comments in other answers, that what you are after is a 2-CNF formula $\phi(q, a, b)$ equivalent to $q \iff \overline{a \land b}$. This is indeed not possible; the only possible clauses in $\phi$ are of the form $(\ell\_1 \lor \ell\_2)$, with $\ell\_1, \ell\_2 \in \\{a, \bar{a}, b, \bar{b}, q, \bar{q}\\}$, and thus there are at most $36$ possible clauses. Given that adding a clause more than once does not change the truth table of a formula, all possible 2-CNF formulas over variables $a, b, q$ are completely defined by a subset of the at most $36$ possible different clauses, and you can check by a program that the desired truth table is not achieved by any of the possible subsets.

Below my Python code:

```
import itertools
import more_itertools

lts = ['a', 'b', 'q', '~a', '~b', '~q']

potential_clauses = []
for i in range(len(lts)):
    for j in range(i, len(lts)):
        potential_clauses.append((i, j))

def target(a, b, q):
    return q != (a and b)

def eval_clause(valuation, clause):
    lits = []
    for var in 'abq':
        if valuation[var]:
            lits.append(var)
        else:
            lits.append('~' + var)

    for lit in clause:
        if lit in lits:
            return True
    return False

def eval_clauses(valuation, clauses):
    for clause in clauses:
        if not eval_clause(valuation, clause):
            return False
    return True

for clauses in more_itertools.powerset(potential_clauses):
    works = True
    for prod in itertools.product([0, 1], repeat=3):
        a, b, q = prod
        valuation = { 'a' : a, 'b': b, 'q': q}
        if target(a, b, q) != eval_clauses(valuation, clauses):
            works = False
            break
    if works:
        print("Found it! " + clauses)

```
> 2 votes

# Answer
There is no proof that it is impossible, but it is believed that it's unlikely to be possible, because if you could convert every circuit with NAND gates to 2CNF, you would have a proof that P = NP. (This is because there are known polynomial-time algorithms to test the satisfiability of 2CNF; if such a conversion existed, then by the universality of NAND gates, this conversion would give a polynomial-time way to test the satisfiability of arbitrary boolean circuits, and the latter is known to be NP-complete.)
> 1 votes

# Answer
If you could encode Q = A NAND B using a conjunction of disjunctive clauses with 2 literals, then you could transform any circuit into a polynomial-size 2-SAT formula (NAND gates are universal). This would allow to check whether there is a set of inputs for which the circuit outputs "true" in polynomial-time.

However this problem is known to be NP-Complete.
> 0 votes

---
Tags: logic, satisfiability, circuits, software-verification, combinatory-logic
---


title: Validity of time complexity analysis

text:
# Question
Title: Validity of time complexity analysis
Given recurrence equation :

$T(N) = T(N-1) + T(N-2) + N$

Given base case

$ T(1) = -3$

So I rewrote the equation as

$ T(n)+ n - T(1) = T(n-1)+ (n-1) - T(1) + T(n-2)+(n-2)-T(1)$

Substituting $ V(n) = T(n) + n - T(1)$ we get :

$V(n) = V(n-1) + V(n-2) $

which is the Fibonacci relation , hence :

$ T(n) = \frac{\phi^{n} - \psi^{n}}{\sqrt {5}} +n-3$

where $\phi$ is the golden ratio.

Is the substitution correct theoretically as asymptotically the constant term is dominated by the linear term ?

# Answer
> 2 votes
Your substitution is correct and indeed leads to Fibonacci. Anyway the final answer does not respect $T(1)=-3$ and there is a sign error.

I would prefer to rework the recurrence independently of $T(1)$, writing

$$T(n)+n=T(n-1)+n+T(n-2)+n$$

or $$U(n)=U(n-1)+U(n-2)+3$$

then

$$U(n)+3=U(n-1)+3+U(n-2)+3$$ and

$$V(n)=V(n-1)+V(n-2).$$

The general solution is thus

$$V(n)=U(n)+3=T(n)+n+3=aF\_n+bF\_{n-1}$$ where $F\_{-1}=1$.

Only now do we introduce the known initial condition $V(1)=1$, which gives $a=1$ and $b$ free.

Hence,

$$T(n)=F\_n+bF\_{n-1}-n-3.$$

---

Regarding the asymtotic behavior, we have two cases.

* if $b\ne-\phi$, $T(n)\sim\left(1+\dfrac b\phi\right)F\_n$ and the behavior is geometric of common ratio $\phi$,
* if $b=-\phi$, the growing $\phi$ exponential cancels out and $T(n)\sim-n-3$.

---
Tags: time-complexity, check-my-answer
---


# Question
Title: Question Regarding Design Constraints in Software Engineering Exam
I recently had a software engineering exam, and there's a particular question that's causing some confusion between my professor and me. I'd like to get some insights from the community to better understand this issue. If I can convince my professor I was right, I could get a higher grade.

The Question:

The question in the exam was as follows:

"The design constraints imposed on the sorting system are:

a. Programming language and algorithms

b. Security and system interaction

c. Platform and schedule

d. Usability and performance"

In our textbook, "Essentials of Software Engineering" by Frank F. Tsui, it states that: " The thinking process related to design constraints can be summarized as follows:

User-interface Typical and maximum input sizes Platforms Schedule requirements " And my professor said that the correct answer is c), based on this section of the book.

Then the book goes:

"The steps and thoughts related to design decisions for the sorting problem can be summarized as follows:

Programming language: Typically this will be a technical design decision, although it is not uncommon to be given as a design constraint.

Algorithms : ... Algorithms are usually design decisions, but they can be given as design constraints or even considered functional requirements. "

My professor marked my answer as incorrect and insisted that the correct answer is "c. Platform and schedule." However, my perspective is that "a. Programming language and algorithms" is a valid choice as well, based on the information from our textbook. His response was : "Design constraints (limit) and design decisions (decisions) are two different ones which are different in chapters 1.1.4 and 1.1.5 respectively. The question on the test was about design constraints, and programming language and algorithms are design decisions."

I've discussed this with my professor, but we couldn't come to an agreement. I believe that the textbook's explanation supports my answer.

I would greatly appreciate it if someone could provide their insights on this matter. Am I interpreting the book correctly? Is "Programming language and algorithms" a valid choice as design constraints based on the provided book excerpt? If so, how can I approach this situation with my professor to clarify my perspective?

I want to ensure that I have a clear understanding of the material and the exam evaluation. Your input would be valuable in resolving this issue.

Thank you in advance for your assistance.

# Answer
I would argue that the answer is "all of the above".

* Programming language and algorithms: is it worth the cost of a new compiler and associated tools to use the newest wiz-bang language, or do you make do with the language and tools you have already purchased? What algorithms will allow the application to perform in a timely manner?
* Security and system interaction: does the computer that runs the application have enough resources (both compute power for security and external interfaces for system interaction) to successfully perform the job.
* Platform and Schedule: does a development system need to be purchased to run on the proposed platform, does the proposed platform have the resources to successfully run the application? Can the project be completed within the scheduled time frame?
* Usability and Performance: big time constraint here, if your application runs too slow or has a terrible user interface, it will never sell.
> 0 votes

---
Tags: software-engineering
---


# Question
Title: Translating non-deterministic finite automata with counters to deterministic ones
I know there are algorithms for translating regular NFAs into their corresponding DFAs. Can these algorithms be applied to automata that employ transitions involving counters in a straightforward way, or are there special considerations that need to be taken into account, or even different algorithms altogether?

# Answer
> 3 votes
Yes, they can be employed in a straightforward way. However, the size of the formulas blows up exponentially big.

Let $\ell\_{s \to t}$ denote the formula on the NFA transition from $s$ to $t$. For instance, these formulas might look like $\text{ctr} \ge 3$ (require the counter to be at least 3, i.e., the transition is only active if the counter is at least 3) or $\text{ctr}' = \text{ctr}+1$ (update the counter by adding one to the counter, when the transition is followed). Let $Q$ denote the set of states of the NFA.

Then each state of the DFA will be a subset of $Q$. Also, the transitions are as follows: the formula on the transition from state $S$ to state $T$, where $S,T \subseteq Q$, is given by $\varphi\_{S \to T}$, defined as

$$\varphi\_{S \to T} := \bigwedge\_{t \in T} \bigvee\_{s \in S} \ell\_{s \to t} \land \bigwedge\_{s \in S} \bigwedge\_{t' \notin T} \neg \ell\_{s \to t'}.$$

Here, I adopt the convention that if there is no transition from $s$ to $t$ in the NFA, then we let $\ell\_{s \to t}$ be the formula $\text{False}$.

The DFA's transitions will involve CNF formulas with literals $\ell$ given by formulas on the NFA transitions or their negations (i.e., conjunctions of clauses, where each clause is a disjunction of those $\ell$ formulas or their negation).

For instance, if the states of the NFA are $a,b,c,d$, then the DFA would have a transition from the state $\\{a,b\\}$ to the state $\\{b,c\\}$ with the formula

$$(\ell\_{a \to b} \lor \ell\_{b \to b}) \land (\ell\_{a \to c} \lor \ell\_{b \to c}) \land \neg \ell\_{a \to a} \land \neg \ell\_{a \to d} \land \neg \ell\_{b \to a} \land \neg \ell\_{b \to d}.$$

As an "optimization", you can test satisfiability of each formula $\varphi\_{S \to T}$ and if it is not satisfiable, then exclude the transition $S \to T$ from the DFA.

We can compare to is determinism = non determinism for one counter automata?. Notice that the situation there is a bit different. One-counter automata allow only specific operations on the counter: increment, decrement, and test for zero. This limits the set of formula that can appear as $\ell$. Now, if we apply the above construction to a non-deterministic one-counter automaton, the formulas $\ell\_{s \to t}$ for the NFA will be of this limited form ($\text{ctr'} = \text{ctr} + 1$, $\text{ctr'} = \text{ctr} - 1$, $\text{ctr'} = 0$, or $\text{ctr'} \ne 0$), but after we apply the above construction, we'll obtain a DFA where the transitions contain formulas that are much more complex. As a result, this does give a way to construct a DFA with formulas on the transitions, but the resulting DFA will not be a deterministic one-counter automaton, because its transitions are not limited to just increment, decrement, or test for zero. In other words: Can you determinize a NFA involving counters? Yes, if you allow the resulting DFA to have complex formulas in each transition (e.g., complex conditions on the counter), but not if you require the DFA to abide by the limitations associated with one-counter automata.

---
Tags: automata, finite-automata, nondeterminism
---


title: Datatypes and number representaton

text:
# Question
Title: Datatypes and number representaton
*I'm a freshman in computer science and I have a question that has been bugging me after my programming and electronics classes were over.*

**My question** is that in an integer datatype (assume **short** datatype in Java, where the range is from -32768 to +32767.) I understand (based on what has been taught) that this is because the leftmost bit MSB is reserved for sign. *However, how does the representation for negative numbers work then? Doesn't it need an extra 1 on the left side?*

Another follow up: isn't sign magnitude an inefficient and usually unused method to perform arithmetic? How then is the output perfect and fast?

* **(please do correct me if I'm wrong, I'd love to grasp every bit of this correctly)** *

# Answer
Let us do 8-bit numbers, it's less writing.

**The left-most bit is *not* the sign.** It contributes $-128$ to the value. More precisely, here are the values of the bits, where bit 0 is the right-most one and bit 8 is the left-most one:

| Bit | Value |
| --- | --- |
| 0 | $2^0 = 1$ |
| 1 | $2^1 = 2$ |
| 2 | $2^2 = 4$ |
| 3 | $2^3 = 8$ |
| 4 | $2^4 = 16$ |
| 5 | $2^5 = 32$ |
| 6 | $2^6 = 64$ |
| 7 | $2^7 = 128$ |

Bit 8 contibutes a negative value. For example `11010000` represents the number $-128 + 64 + 16 = -48$. What represents $-1$? Because $$-128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = -1$$ the number $-1$ is represented by `11111111`.

Is it clear now?
> 2 votes

# Answer
You may notice that the smallest value (negative) has a larger mantissa by one unit than the largest value (positive), and in total there are $2^{16}$ distinct values. These are sure signs that the two's complement representation is used for signed values.

https://en.wikipedia.org/wiki/Two%27s\_complement

---

**Addendum:**

The sign/magnitude representation has a big flaw: it has two zeroes.

$$\cdots-3,-2,-1,-0,+0,+1,+2,+3\cdots$$

This creates a quirk in the linearity. While this seems inoccuous, it would make the implementation of arithmetic more complicated and costly.
> 1 votes

---
Tags: programming-languages
---


# Question
Title: If P != NP, can every NP-complete language be partitioned into two NP-complete subsets?
Assuming $\mathsf{P} \neq \mathsf{NP}$, then all NP-complete languages are countably infinite. I know not all subsets are NP-complete, but I am wondering if there's a simple proof that every NP-complete language can be partitioned into two subsets $X,Y$ such that both $X$ and $Y$ are NP-complete.

# Answer
> 1 votes
Yes, I think a partition always exists. My idea is to first prove it for $\text{Clique}$ and then use the fact that $\text{Clique}$can be reduced to every other $\textsf{NP}$-complete problem.

In a first step, we prove that it is possible for the language $\text{Clique}$ by considering the length of inputs. We will measure the length of an input $x$ for $\text{Clique}$ in the number of nodes to avoid a technical problem. Let $\text{Clique}\_{even}=\\{x\in\text{Clique}\mid |x| \text{ is even}\\}$ and $\text{Clique}\_{odd}=\\{x\in\text{Clique}\mid |x| \text{ is odd}\\}$. Then $\text{Clique}=\text{Clique}\_{odd}\cup \text{Clique}\_{even}$ is a partition with the desired property: Both languages are in $\textsf{NP}$ and we can reduce $\text{SAT}$ to both languages by using the reduction from $\text{SAT}$ to $\text{Clique}$ where we add an additional isolated node if the size of the constructed graph doesn't fit the restriction.

Now, let $L$ be an arbitrary $\textsf{NP}$-complete language. So, there is a polynomial-time reduction $f$ from $\text{Clique}$ to $L$. In particular, there is a polynom $p$ that bounds the size of the constructed object, so $|f(x)|\leq p(|x|)$. Without loss of generality we can assume $|x|\<|f(x)|$, so $|x|\<|f(x)|\<p(|x|)$.

We use this polynom $p$ to define two sets $N\_1,N\_2$ of the natural numbers. Set $1,2,\dots,p(1)\in N\_1$, $p(1)+1,\dots,p(p(1)+1)\in N\_2$, $p(p(1)+1)+1,\dots,p(p(p(1)+1)+1)\in N\_1$ and so on. So, $N\_1$ and $N\_2$ consist of infinitely many finite sequences of consecutive numbers. Next, let $L\_1=\\{x\in L\mid |x|\in N\_1\\}$ and $L\_2=\\{x\in L\mid |x|\in N\_2\\}$. Both $L\_1$ and $L\_2$ are in $\textsf{NP}$, we can just use the algorithm for $L$ and then check the length afterwards.

Finally, we show that $\text{Clique}$ can be reduced to $L\_1$, the reduction to $L\_2$ is analogous. Let $x$ be some input for $\text{Clique}$. If $|x|$ coincides with the end of a sequence in $N\_2$ (for example $p(p(1)+1)$) then we can apply $f$ and $|f(x)|\in N\_1$, so the reduction works correctly. Otherwise, we can add isolated nodes to the graph represented by $x$ until $|x|$ coincides with an end of a sequence in $N\_2$. We have to add at most polynomially many nodes because the length of the sequences is bounded by $p$. Thus, $L\_1$ and $L\_2$ are NP-complete.

The technical assumption can probably be avoided by choosing a diferent langauge than $\text{Clique}$. Also notice that the statement allows us to partition any $\textsf{NP}$-complete language into arbitrarily (finitely) many languages which are $\textsf{NP}$-complete. So, the size-blowup in the reduction $f$ can probably not be avoided.

# Answer
> 0 votes
Tricky. If you can enumerate all the possible instances of your problem N, then you divide them into "even" and "odd" instances. You could now have one problem saying NOdd asking "Is I is an odd instance of N, and does N answer YES" and a problem NEven asking "Is I an even instance of N, and does N answer YES".

Sounds easy. But I'm sure someone can construct a problem where one of NOdd and NEven is trivial. Actually, NOdd has exactly the same instances as N. So if you apply the "NEven" construction to Odd instead of N, then the resulting language always returns NO and is therefore trivial.

If N is very compressed (with no redundancy at all), so that some instance of some problem in NP can only be solved by constructing exactly ONE instance in N, then that one instance cannot be both in NEven and in NOdd, and one of the two languages is not NP-complete.

So we have a different question now: Is there an NP-complete problem, and a problem in NP with an instance where not AT LEAST instance of the the NP-complete problem, but EXACTLY one instance can be used to solve the problem in the NP language?

---
Tags: complexity-theory
---


title: Resources to learn NLP

text:
# Question
Title: Resources to learn NLP
I am an undergraduate student in mathematics. I have a fair bit of experience with deep learning in computer vision research and am willing to dabble into NLP. I hope that things won't be very disjointed and some of the knowledge can be transferred.

I wanted to know if y'all can recommend some YouTube playlists that start from scratch as far as NLP is concerned, and then gets pretty deep into the subject. I would also like it to have a research-oriented flavor. Thanks in advance.

# Answer
> 0 votes
I like The Stanford CS224N 2021 YouTube channel, which focuses on deep learning models for NLP (but many things changed since 2021, esp. LLMs). For a pre-deep-learning NLP courses, I like:

---
Tags: machine-learning, reference-request, natural-language-processing
---


# Question
Title: Number of non-zero elements in intersection of two bloom filters
Let us assume I use bloom filters of size $m$ bits with $k$ hash functions.

Now I have two set $X$ and $Y$. Let $B(X)$ be bloom filter of the set $X$. In general I know that $B(X\cup Y)= B(X) \lor B(Y)$. Let us assume that $|X|=n, |Y|=m, |X\cap Y|=l$.

So I can use formula from wiki for math expectation for number of non zero element in $B(X\cup Y)$.

Howewver it is not true that $B(X\cap Y)= B(X) \land B(Y)$. Can I theoretically compute how many non-zero elements $B(X) \land B(Y)$ should have?

# Answer
Focus on a particular bit position, say the $i$th bit position. Let $E$ be the event that this bit is set in $B(X) \land B(Y)$. Now all you need to do is to estimate $\Pr\[E\]$. Then the expected number of non-zero elements in $B(X) \land B(Y)$ will be $m\Pr\[E\]$.

To help us estimate $\Pr\[E\]$, let's break this down into cases. Define $S=X \setminus Y$, $T=Y \setminus X$, $U=X \cap Y$. Also define the event $E\_S$ to represent that this bit is set in $B(S)$, $E\_T$ that it is set in $B(T)$, and $E\_U$ that it is set in $B(U)$.

It will be easier to estimate $\Pr\[\neg E\]$. Note that

$$\Pr\[\neg E\] = \Pr\[\neg E\_U \land \neg (E\_S \land E\_T)\] = \Pr\[\neg E\_U\] \cdot \Pr\[\neg (E\_S \land E\_T)\].$$

Now

$$\Pr\[\neg E\_U\] = (1 - \frac{1}{m})^{kn\_U} \approx \exp \\{-kn\_U/m\\},$$

where $l=|X \cap Y|=|U|$. Also

$$\begin{align\*} \Pr\[\neg E\_S\] &= (1 - \frac{1}{m})^{k n\_S} \approx \exp\\{k n\_S/m\\}\\ \Pr\[\neg E\_T\] &\approx \exp\\{kn\_T/m\\} \end{align\*}$$

so we have

$$\Pr\[E\_S \land E\_T\] = \Pr\[E\_S\] \cdot \Pr\[E\_T\] \approx (1 - \exp\\{k n\_S/m\\}) (1 - \exp\\{kn\_T/m\\}).$$

It follows that

$$\Pr\[\neg E\] \approx \exp\\{-kn\_U/m\\} \cdot \[1 - (1 - \exp\\{k n\_S/m\\}) (1 - \exp\\{kn\_T/m\\})\],$$

and

$$\Pr\[E\] \approx 1 - \exp\\{-kn\_U/m\\} \cdot \[1 - (1 - \exp\\{k n\_S/m\\}) (1 - \exp\\{kn\_T/m\\})\].$$

Multiply by $m$, and that is your desired estimate for the number of non-zero elements in $B(X) \land B(Y)$.

If you want to express this estimate in terms of the sizes $|X|$, $|Y|$, and $|X \cap Y|$, note that $n\_U=|X\cap Y|$, $n\_S=|X|-|X\cap Y|$, and $n\_T=|Y| - |X\cap Y|$, and plug into the formula above.

If you want to estimate the size of $|X \cap Y|$ from the number of non-zero elements in $B(X) \land B(Y)$, you just need to invert the above equation. You could use binary search on $n\_U$ to find the value of $n\_U$ that gives the closest match between expected number of bits set and actual bits set.
> 1 votes

---
Tags: probability-theory, probabilistic-algorithms, bloom-filters
---