# Question
Title: What are efficient approaches to implement unit propagation in DPLL-based SAT solvers?
I'm trying to decompose deduction steps of DPLL algorithm -- unit propagation and pure literal elimination -- for parallelization. However, I want a baseline and asymptotic analysis to compare to my parallel approach for these two deduction procedures.

My naive approach to unit propagation would be to perform linear scan on all clauses, and that of pure literal elimination is again to linear scan and count the number of + and - polarities. But, it wouldn't make sense to compare my algorithm to the most naive approach available.

After reading this paper -- "The Quest for Efficient Boolean Satisfiability Solvers" -- I came to know of two more approaches:

1. Head-tail lists
2. Two-watched literals (which disables pure literal search)

But I believe there can be better data structures to represent the input formula and thus better algorithms and complexity analyses.

I'm only concerned with the approaches to deduce assignments at the beginning of DPLL procedure pseudocode as given on Wikipedia's page, and not branching heuristics or CDCL.

Are there any resources and comparisons of approaches to implement unit propagation (and possibly PLE) in DPLL? Or is two-watched literals still the most popular/ efficient technique till date?

# Answer
> 3 votes
#### Theory

##### Unit Propagation

For unit propagation, two-watched literals *with circular updates* is asymptotically optimal. I suggest reading "Optimal Implementation of Watched Literals and More General Techniques" which generalizes the concept and proves optimality. (It can also be helpful to read "An Efficient Algorithm for Unit Propagation" to see why head/tail meets the same optimality, though with larger storage costs and backtracking costs.)

When a watcher is falsified, it must find some unassigned literal in the clause to replace it. (If it cannot, then in a two-watcher scheme the remaining watcher has become unit; in a one-watcher scheme the clause has become empty.) Critically, when doing this search for a replacement literal one must begin where the last search ended, treating the clause as a circular buffer.

When done this way, updating watchers takes constant time when amortized across the search tree. Therefore unit resolution takes amortized linear time. (Older solvers did not do this circular tracking, and instead always began the search from the start of the clause; this leads to quadratic worst-case complexity instead.)

When backtracking, watched literals require no updates.

##### Pure Literal Elimination

For pure literal elimination, after unit propagation we need to determine all unassigned literals with zero instances of a polarity. Polarity count can only change when a clause transitions between satisfied and unsatisfied, so when a literal is assigned/unassigned we must necessarily scan over all the clauses it occurs in (not just watches, but occurs) and update polarity counts. Care must be taken not to double-count clauses, but updating literals in a clause is already linear so this doesn't affect asymptotic worst case.

When a literal has zero instances of a polarity, it may be assigned. No unit propagation is necessary, since a pure literal has no clauses to resolve with.

When backtracking, polarity counts *do* require updates.

##### Conditional Autarkies

As an aside, the kind of pure literals DPLL seeks to find are actually a special case of a more general concept called *conditional autarkies*.

An autarky `α` is a (partial) assignment that satisfies all clauses it touches. A conditional autarky is an autarky with an assumption, i.e. if `α_aut` is an autarky for `F ∧ α_con`, then `α_con ∪ α_aut` is a conditional autarky.

Given a conditional autarky for `F`, the formula `F ^ (α_con → α_aut)` is not implied but is equisatisfiable. Note that the conditional part may be empty, so vanilla autarkies may also be assumed.

Pure literals are just a special case of autarky, satisfying every clause they touch. If the literal is only pure after assigning some variables then that is a conditional pure literal, a special case of a conditional autarky.

---

### Practice

##### Unit Propagation

Modern solvers spend a bulk of their time doing unit propagation, so this is a highly-optimized section of code. Although the worst case for unit resolution is amortized linear, in practice the number of clauses updated is less than this. With watched literals you might even hit a best case of not being a watcher for any clauses! That's one of the reasons why this is so efficient in practice.

To optimize storage, a clause will store the two watchers as the first two literals in its elements list. This partitions the clause into the watcher half (size 2) and the remainder half. This allows the search for a new watcher to never consider the other watcher as viable.

Memory is slow, so cache misses are a significant cause of latency in watchlist updates. Iterating a watchlist is fast, since it is contiguous and the prefetcher does its thing well. But to actually iterate the literals of a clause (as well as retrieve the clause search position for circular updates) requires an indirection which is almost certainly going to be a cache miss.

To remedy this, each watch in a watchlist stores a cached literal from the clause called a 'blocking literal'. If this literal is satisfied, we don't need to do anything and move on. This check is likely to hit cache and be ~free. Otherwise we go ahead and perform the indirection to find a new watcher. (And the blocking literal will be updated to a more likely useful literal as a side effect.)

The next optimization is to note that for binary clauses, the watcher along with the blocking literal is enough space for the entire clause. No indirection is required at all and no clause ID is needed, provided we know this is a binary clause. To do that, we declare that our solver doesn't support more than 2^31 literals. This lets us store literals in a u32 with the MSB free for other uses; in our case we will set this MSB if the clause is binary.

That is, if the MSB is set then this value (with the MSB cleared) is the other literal of a binary clause, else this value is a blocking literal for a long clause and the clause ID is the next u32 after it. The result is that we get a watchlist containing variable-length elements:

```
[Other][Blocking][Clause ID][Blocking][Clause ID][Other][Other]etc.

```

As we iterate, we check the MSB to know which case we are in. Large real-world problems contain huge numbers of binary clauses. Not only does this speed up solving such problems due to more things fitting in cache and fewer indirections, but it saves a substantial amount of memory as well since binary clauses never allocate clause IDs.

Allocating clauses is an entirely other thing that is left as an exercise for the reader. (Hint: storing data together means it lives in cache together, so store the clause metadata like search position contiguous with the clause literals.)

I'd recommend reading over CaDiCal's propagation code with these concepts in mind.

##### Pure Literal Elimination

Pure literal elimination during assignment search loop is practically never worth it. Given everything outlined above, tacking on more tracking to count polarities nullifies the efficiency of propagation for something that almost never provides value. It also requires occurrence lists instead of just watch lists. You can have both, but the memory costs for occurrence lists are difficult to minimize.

This inefficiency also rears its head during backtracking, because now you have to increase polarity counts on clauses no longer satisfied. Unit propagation with watched literals doesn't require any work for backtracking.

All of this is especially true with clause learning. If `p` is some conditional pure variable, then `(α_con → p)` is merely a single clause and the solver can learn a lot more than this on its own.†

PLE *can* be cheaply performed once at the start of search. Since no unit propagation is occurring, the propagation engine remains unscathed. This is fairly common in basic solvers, but advanced solvers do not explicitly do this.

##### Bounded Variable Elimination

A much more powerful technique called bounded variable elimination can be performed during preprocessing or inprocessing. This takes a variable and generates all of the resolvents over it, adding them to the formula and removing the original clauses uttering this variable. The variable now no longer appears anywhere; the 'bounded' part comes in when we decide not to do this if the formula would become unhelpfully larger if we went through with it.

BVE is one of the more important processing techniques to apply in modern solving. As part of BVE, pure literals are trivially detected because they have no resolvents to produce. This technique subsumes performing any explicit PLE at the start of search.

This isn't quite the same as assigning pure literals during assignment search, but given this technique is applied arbitrarily often during search it probably approximates it pretty well at a negligible cost. Due to this, research into integrating PLE to propagation is, as far as I know, dead.

---

<sub>

There is a bleeding-edge paradigm called satisfiability-driven clause learning (SDCL), which not only learns clauses from conflicts but learns clauses by solving small generated formulas during search. This allows it to learn not just implied clauses, but also equisatisfiable ones (called 'redundant clauses').

The generated formulas are called pruning predicates, and are a function of the formula being solved and the current partial assignment. If the predicate is satisfiable, then the current partial assignment may be pruned from the search space.

One kind of redundant clause, SBC (sometimes SET), can be found by solving a so-called positive reduct. All satisfying assignments for the positive reduct are conditional autarkies for F. So in effect this is finding conditional autarkies (rather than just conditional pures) during the search.

Incorporating this with practical effectiveness is an open problem.

For more on this I suggest reading "Encoding Redundancy for Satisfaction-Driven Clause Learning".

</sub>

---
Tags: time-complexity, satisfiability, sat-solvers
---


# Question
Title: What are the examples of multi-threading in a web server?
So I’ve been reading about multi-threading these past few days. Can you give me a real life example where the multi-threading might be used in a REST API web server?

# Answer
> 0 votes
A web server serves hypertext transfer protocol requests. While there is no requirement whatsoever on *arrival times* and *service times*, the idea is a successful service sometimes gets requests even more frequently than $\frac 1 {\text service-time}$: for requests to neither be discarded nor queue up, there must be some concurrency in processing.
There are different approaches to unwanted and/or illegal disclosure of confidential data. Typically, threads sharing any given processor "core" concurrently enjoy identical access rights, while separate computers/processors/cores are restricted individually:
If serious about confidentiality, better restrict *multi-threading* to reducing the service time of *single requests*.
This is where the *REST* of the protocol (& API (client side, mainly)) comes into the picture:
Keeping all information feasible with the client and transferring it per request (REpresentational State Transfer) means identifying requests for the same confidentiality domain was extra effort.

# Answer
> 0 votes
There is a thesis turned into free (and open) book that covers pretty much every aspect of concurrent Web servers and applications (including REST): Concurrent Programming for Scalable Web Architectures (thanks to Benjamin Erb).

But the main idea is simple and old: as long as separate requests are independent from one another (and HTTP pretty much mandates that) we can process them completely separately and concurrently, i.e. each one in its own (logical) thread. Sure enough in the real world there are lots of nuances that make straightforward implementation not very practical and you need to "upgrade" this basic idea with various mechanisms (thread pool, connection pool, asynchronous IO, and so on).

---
Tags: threads
---


title: Context-free pumping lemma of $a^nb^n$

text:
# Question
Title: Context-free pumping lemma of $a^nb^n$
I know $a^nb^n$ with $n\geq0$ is considered a context-free language, but if I try:

Using pumping length $p = 3$

$n = p$, thus we have $aaabbb$

$u =aa$ and $y = bb$

$v = a$, $w = b$ and $x=λ$, then $|vwx|=2\leq p=3$ and $|vx| = 1 \geq 1$

$uv^iwx^iy \notin L$, for instance, with $i=2$ we have: $$aaaabbb$$

I know I'm wrong in some part of the process, that's I'm attempting to 'break' the lemma, to fully understand it.

# Answer
> 1 votes
You picked a wrong decomposition. Similarly to the pumping lemma for regular languages, the pumping lemma for context-free languages states that for every context-free language $L$, there exists *some* legal decomposition for every string $s$ with $|s| \geq p$ where $p$ is a pumping length of $L$.

By legal decomposition, I mean dividing $s$ into partitions $uvwxy$ such that

* $|vx| \geq 1$
* $|uvw| \leq p$
* $uv^nwx^ny \in L$ for all $n \in \mathbb{N}\_0$

In the case of the string $aaabbb$ with $p = 3$, a legal decomposition would be eg. $u, w, y = \epsilon$, $v = aaa$, $x = bbb$.

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


# Question
Title: Halting problem. Decider “recognising itself” in the input? Part 2
This is a "revision" of this question, it contained an error I now see. In a nutshell, I was wondering if in the halting problem proof the decider $D$, after recognising its source code in the input fed to it, could leverage the fact it can look at the source code of $H$ to help its clone in the input make the right prediction if the simulation was run. By treating the "clone in the input" effectively as the same as itself and therefore helping it out, $D$ would manage to make the right prediction even in the case what is going on in the simulation from the input is happening to the original $D$ too, and there actually is a real $H$ trying to trick it. The question I linked to explains the idea more thoroughly and (maybe) more clearly, but at its core the idea was about $D$ realising that its "clone" described in the input would do the exact same things that the original $D$ does, so $D$ starts acting as it was its clone with the intent of saving it from being tricked.

The error I made in the first question was to think that when programming $H$ you have a set of finitely many possible halting states to choose from, and that therefore $D$ could be programmed to possibly halt in any of the states in this set, so that after reading $H$'s source code it could simply choose to end in that state to ensure halting.

What I am wondering now is: couldn't $D$ still ensure halting of $H$ by using a more sophisticated technique? I'll try and explain more or less what I mean. Sorry for the lack of rigour and the very cloudy outline, please let me know what points need to be clarified the most.

Even if $D$ cannot directly terminate in $H$'s halting state, maybe it could trigger $H$ to decide to halt itself by tricking it into believing the "not halting" prediction was made by $D$. Imagine in the physical implementation of the Turing machine the halting prediction is made by printing 0 or 1 in some special square. The special square is easily recognisable from the external world maybe because the tape has some mark on the other side at that position, or (as in Turing 1936) the special square is the one immediately to the left of where the machine description given as input begins. $H$ cannot see the external world and it has to orient itself only based on the landscape of zeros and ones that $D$ left behind after halting. Now, $D$ can be as intelligent as we like, and had both complete access to $H$'s source code and all the time it needed to learn about it, and crucially it can deduce that everything that it does is what its alter ego described in its input would do if the simulation was left running (even if it obviously it can't run the whole simulation because of infinite recursion). Couldn't $D$ be able to arrange some portion of the tape in such a way that after it halts and $H$ is triggered, $H$ is tricked into thinking it is experiencing a reality where the special square says "not halting"? But actually the landscape that $H$ is using to orient itself is some sort of "virtual machine"/"virtual reality" built by $D$ and the true special square is in another part of the tape. By the way, I think this argument can be adapted even to the slightly different framework found in the original Turing paper (circular and circle free machines).

If we take away the ability to keep track of some special square from the outer world, and you ask whether $D$'s prediction can be accessed by any other subroutine/agent existing inside the universe run by the Turing machine, then I think the answer is no. But I also think that subroutines/agents can be built in such a way that they can access the actual prediction ($D$ won't lie to them) and use such information to do anything consistent with the assumption of $D$ being a universal decider.

One objection I see is "what if we make $H$ very intelligent too, so much so that it is always able to fight back and be one step ahead of $D$, hack trough the virtual machine built to trick it etc...? Here I think there is still a crucial problem: $H$ to win has to behave in a way that contradicts what has predicted the simulation of itself will do if left running, while $D$'s goal is compatible with staying coherent with the simulation of itself. What I mean is that at the very beginning $H$ will try to analyse the source code of the subroutine $D$ to understand its behaviour and avoid being tricked by it. But $D$'s behaviour is contingent on what course of action $H$ in its input will take to try and retrieve $D$'s true answer. This course of action has to be exactly predicted by $D$ if it is really a universal decider, then $H$ has to exactly predict $D$ and all of its predictions and yet somehow manage to do something that $D$ predicted it would not do in those circumstances, which is a contradiction. But note that this is not a proof by contradiction that $D$ must not exist: we made two assumptions, the first one is the existence of $D$ and the second one is the existence of this super powerful $H$ always capable of being one step ahead of $D$. Therefore, this is only a proof by contradiction that at least one of these two assumptions must be false.

So my question would be: can $D$ trick $H$ in the way I described? Can you spot any reason why my argument falls apart?

Edit: I got why the previous argument doesn't work. But, in my understanding $H$ has to copy-paste its input (or print it as quines do) to duplicate it and give the two copies to $D$, so I was wondering what would happen if $D$ realises that it has the power to decide if $H$ halts or not and stops trying to predict the behaviour of machines described by its input and treats those descriptions as simply some strings (disregarding they encode a machine description). Maybe the copy-paste procedure leaves in those strings some information about something like how many $H$ calls is some $H$ call nested in, so that $D$ can create some behaviour coherent with the predictions. Suppose you have a set of strings, all are meant to be equivalent descriptions of $H$, but each one pops up as description of $H$ only when $H$ is called inside itself some specific number n of times, then if $D$ alternates predictions back and forth (string1:halt, string2:loop, string3:halt etc...) depending on the number of nested calls, its predictions would be true. I started to wonder about this because it looks like to have a description of itself printed/copied in the exact same way the machine is actually implemented and then simulating it with a universal Turing machine, you need more complexity than you have, am I wrong?

# Answer
The answer is pretty much the same as before: The person who designs the Turing machine $H$ won't let it happen. They won't allow $D$ to behave any differently when it's inside $H$ than when it's outside of $H$. Sure, you can try to make $D$ fiendishly complicated, but at the end of the day, *it's not difficult to embed a Turing machine inside another* so that it behaves exactly the same as when it's not embedded.

For example, $D$ might play weird tricks with the tape - like moving a million squares to the right just to check it's not in a small blank space of a tape that has other stuff on it - the designer of $H$ would just groan, curse the designer of $D$, edit the copy of $D$ so that it always moves twice as many spaces as the original $D$ did, make sure it starts on an odd-numbered space, and make sure the rest of $H$ only uses even-numbered spaces.

Or as in your original question, $D$ might go to a halting state after computing the answer. In fact that's not even trickery - that's what $D$ is supposed to do. The designer of $H$ will make those states non-halting and then add transitions back to the rest of $H$.

Or $D$ might try to use the same alphabet symbols used by $H$, like drawing "special squares" in the wrong places. Then the designer of $H$ will just change them to other symbols that don't conflict. Or they change the symbols they are using for their part of $H$, so they don't use the same ones $D$ is sneakily writing.

There is absolutely nothing you can possibly do to $D$ to make it "smartly" recognize that someone has copied and pasted and edited it, that can't be easily bypassed by the person doing the copying and pasting and editing. Even if you can think of something really really really fiendish, the designer of $H$ could embed a universal Turing machine (a Turing machine simulator), and run $D$ inside that.

---

You seem to think there is some reason that $H$ must contain an exact copy of $D$. That is not true. $H$ can contain whatever the designer of $H$ wants it to contain. It's possible that someone can find a program that $D$ doesn't decide correctly, which doesn't contain anything at all based on $D$! However, including a (possibly slightly modified) copy of $D$ is a *surefire* way to design $H$. 100% of the time it works every time.

The point is that $H$ checks what $D$ would say if it was run with $H$ as a parameter, and then does the opposite. Therefore, obviously, $H$ does the opposite of whatever $D$ says it does. You are trying to get around it by proposing that when $H$ checks what $D$ would say, it gets a different result than what $D$ actually says, or it "crashes". But that is impossible to achieve. It is impossible to write a $D$ which can't be checked. Think of it like a sandboxed program which can't tell that it's running inside a sandbox.

---

In a comment, you wrote:

> D would see from H's description that H is running D as a simulation in a universal Turing machine and would take that into account to trick H as in the other cases

It's possible that with certain combinations of $D$ and $H$, $D$ run with input $H$ can detect that $H$ tries to simulate $D$ with input $H$. Fiendishly difficult, and not always possible (the designer of $H$ is able to hide it), but sometimes possible (let's say they don't hide it). Let's imagine that it *can* detect this. Then, when a human simulates $H$, $H$'s simulation of $D$ will return, for example, non-halting. Then $H$ will halt. "Haha!" you say, "I really wanted $H$ to halt all along! My crafty little $D$ has tricked $H$ into halting, which was the real prediction and it's correct!"

Except, when the same human runs $D$ with input of $H$, it will make the exact same detection, and it will again return non-halting to trick $H$, except it's not embedded into $H$ and so it just predicts non-halting. Which is a wrong prediction, because as I said in the last paragraph, $H$ halts. You still lose, good day sir.
> 2 votes

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


title: a generalized job assignment problem

text:
# Question
Title: a generalized job assignment problem
> The following problem is from a past algorithms course exam and I'm using it to test my knowledge.

> There are m machines and n jobs. Each machine can doing a subset of jobs. Each machine i has a capacity $C\_i$, meaning that it has $C\_i$ units of processing time. Each job $j$ has a demand $D\_j$, meaning that it requires $D\_j$ units of processing time to complete. We'd like to assign all the jobs to the machines, so that each job is assigned to only one machine, and no machine is overloaded (i.e. the total demands assigned to machine i doesn't exceed its capacity $C\_i$).

Input: $m$ positive numbers $C\_1,\cdots, C\_m$, n positive numbers $D\_1,\cdots, D\_n$, and for each $1\leq i\leq m$ and $1\leq j\leq n,$ a boolean variable $x\_{i,j}$ indicating whether machine $i$ can do job $j$.

Output: Does there exist an assignment such that all the jobs are assigned to machines, so that each job is assigned to only one machine and no machine is overloaded?

> Question: prove the above problem is NP-complete, or give an algorithm to solve the decision problem in polynomial time.

I think the problem might be NP-complete. The decision problem asks whether an assignment assigns at least k jobs, where k is a parameter to the decision problem. Clearly the problem is in NP; one can verify in polynomial time that an assignment satisfies that no machine is overloaded and each job is assigned to one machine. One can do this by checking the jobs assigned to machine i and verifying that the total sum of the $D\_j$'s associated with machine i is at most $C\_i$. One can then check at the same time that no job is assigned to two different machines.

But I'm not sure which NP-complete problem to reduce from. For instance, I know the following well-known problems are NP-complete: vertex cover, 3-SAT, hamiltonian cycle, set cover, hamiltonian path, clique, independent set, 3 coloring, subset sum etc.

> Maybe Vertex cover would be useful?

# Answer
> 2 votes
This problem is a generalization of the decision version of the bin packing problem (BPP). While all bins in BPP have the same given capacity, the capacities of the machines in this problem are variable.

The decision version of BPP is $\mathsf{NP}$-complete. So you have guessed correctly: this problem is $\mathsf{NP}$-complete since this problem is in $\mathsf{NP}$ as proved in the question.

---
Tags: algorithms, graphs, np-complete
---


# Question
Title: Linearity property of summation applied to Big Theta notation (CLRS math background appendix)
Section A.1 of the Mathematical Appendix of the CLRS, the third edition, page 1146, contains the following formula stating linearity property of summation applied to $\Theta$ notation: $$ \sum\_{k=1}^{n}\Theta\left ( f \left ( k \right ) \right )=\Theta \left ( \sum\_{k=1}^{n} f\left ( k \right )\right ). $$ And states that the $\Theta$-notation on the left-hand side applies to the variable $k$, but on the right-hand side, it applies to $n$. How does $\Theta$-notation come to apply to a variable, if it applies to functions? What is implied here?

# Answer
> 2 votes
The expression $\Theta(f(k))$ stands for a function $g(k)$ which is $\Theta(f(k))$, that is, there exist $C\>c\>0$ and $K\>0$ such that $cf(k) \leq g(k) \leq Cf(k)$ for all $k \ge K$. In this sense, $\Theta(f(k))$ is with respect to $k$, since it only has to apply for large $k$.

Here is what the equation in CLRS says, verbosely:

> Suppose that $g(k) = \Theta(f(k))$. Then $$ \sum\_{k=1}^n g(k) = \Theta\left(\sum\_{k=1}^n f(k)\right). $$

Even more verbosely:

> Let $f,g$ be functions mapping positive integers to positive reals.
>
> Suppose that there exist constants $C\>c\>0$ and $K\>0$ such that $cf(k) \leq g(k) \leq Cf(k)$ for all $k \ge K$. Then there exist constants $D\>d\>0$ and $N\>0$ such that $$ d\sum\_{k=1}^n f(k) \leq \sum\_{k=1}^n g(k) \leq D\sum\_{k=1}^n f(k).$$ for all $n \ge N$.

For the proof, we pick $N = K$. Let $S\_g = \sum\_{k=1}^K g(k)$ and $S\_f = \sum\_{k=1}^K f(k)$. If $n \geq N$ then $$ \sum\_{k=1}^n g(k) \geq \frac{S\_g}{S\_f} \sum\_{k=1}^K f(k) + c \sum\_{k=K+1}^n f(k) \geq \min\left(\frac{S\_g}{S\_f},c\right) \sum\_{k=1}^n f(k). $$ Similarly, $$ \sum\_{k=1}^n g(k) \leq \frac{S\_g}{S\_f} \sum\_{k=1}^K f(k) + C \sum\_{k=K+1}^n f(k) \leq \max\left(\frac{S\_g}{S\_f},C\right) \sum\_{k=1}^n f(k). $$ Therefore we can take $d = \min(S\_g/S\_f,c)$ and $D = \max(S\_g/S\_f,C)$.

In fact, similar reasoning shows that for positive functions, the definition of big Theta remains the same even if we remove $K$ from the picture, requiring the inequalities to hold for *all* inputs. However, the proof above can be extended to functions satisfying weaker conditions. For example, it suffices that $\liminf\_{k\to\infty} f(k) \> 0$. In this case, we have $f(k) \geq \eta$ for some $\eta \> 0$ and all $k \geq L$, and so $$ \sum\_{k=1}^{M\_f} f(k) \geq \sum\_{k=1}^L f(k) + (M\_f-L)\eta, $$ which is positive for some $M\_f \geq L$. Similarly, $$ \sum\_{k=1}^{M\_g} g(k) \geq \sum\_{k=1}^{\max(K,L)} g(k) + (M\_g-\max(K,L))c\eta, $$ which is positive for some $M\_g \geq \max(K,L)$. Taking $M = \max(M\_f,M\_g)$, we can repeat the above proof, replacing $K$ with $M$.

# Answer
> 2 votes
In mathematics we have so-called variable-binding operators, such as, for example, composite sum and product, with respect to finite family of some monoid's elements. In same way we can consider $\Theta$ notation.

In our case we have two such operators in one and same expression. If we have symbol $k$ as bound variable of sum, then we need also some symbol for bound variable for Theta, which represent variable for function inside Theta. This brings us to the one of the possible refinements $$\sum\_{k=1}^{n} \Theta\big(f\_k(x)\big) = \Theta\left(\sum\_{k=1}^{n} f\_k(x)\right),x \to x\_0\quad(1)$$ Now in left hand we have algebraic finite sum of sets $\Theta\big(f\_k(x)\big),x \to x\_0$ (each is same with $\Theta\big(f\_k\big)$), which equal to set defined on right hand. Following expression, possibly, wouldn't raise so many questions $$\sum\_{k=1}^{n} \Theta\big(f\_k\big) = \Theta\left(\sum\_{k=1}^{n} f\_k\right)\quad(2)$$

**Addition.**

The wonderful answer from Yuval Filmus gives me possibility to express the following thoughts, in the hope, that they will be useful

1. Mathematics is an attempt to unambiguously express one's thought in writing and convey it to another person, even if a conversation is impossible. This led to the creation of many formal rules that some people find complicated and cumbersome, but make the concept of a question more understandable to others.

The given example is a case, when a formally formulated statement makes it just ambiguous for specialists.

The mentioned book itself defines - page 44 - asymptotic notations as sets. The expression $\Theta\big(g(n)\big)$ is uniquely defined by the function $g$ and hides the dummy variables $c\_1, c\_2, n\_0$ and $n$, were with respect to last variable is considered asymptotic. If the function $g$ depends on a single variable, then it makes no sense to write $\Theta\big(g(n)\big)$ and the notation turns into $\Theta\big(g\big)$. To be pedantic, if/when we **insist on definition based on set**, we cannot use dummy variable inside $\Theta$ for operators like sum from outside, because formally $\Theta\big(g(n)\big) = \Theta\big(g(k)\big) = \Theta\big(g\big)$. On the other hand, for example, $\Theta\big(f(1)\big)$, $\Theta\big(f(2)\big)$ etc., expresses a completely different meaning than, perhaps, the authors wanted to put into this statement. Formally $\Theta\big(f(1)\big) = \Theta\big(1\big)$.

2. Problem of page 1146 is not in understanding right-hand side as applied to $n$, but, as is written in book, in sentence "$\Theta$-notation on the left-hand side applies to the variable $k$". Based on what was written in the previous point, we cannot formally understand the left-hand side exactly. Probably, better to sacrifice brevity for the sake of a clear understanding of the issue and, following the adjacent answer, write $$\text{if } g \in \Theta(f)\text{, then }\sum\limits\_{k=1}^{n} g(k) \in \Theta\left(\sum\limits\_{k=1}^n f(k)\right)\quad(3)$$
3. On page 1146 formula under discussion is considered as "linearity property ". But to express the well-known property of linearity in mathematics for $\Theta$, then we do not need even $n$ summands, but is enough two ones: $\Theta$ is linear means $\Theta(f+g)=\Theta(f)+\Theta(g)$, but not $(3)$. If we insist on $n$ summands, then we can write it as (2).

---
Tags: asymptotics, landau-notation, summation
---


# Question
Title: How to determine tag, index and offset size in a two-way associative cache
How to determine tag, index and offset size in a two-way associative cache with a 1MB two-way set associative cache with 8 byte blocks

# Answer
I am going to assume a 32 Bit address.

The offset is trivially $log(8)=3$ as it basically indexes the amount of bytes in each block.

The Index is a bit more difficult:

$\frac{1MB}{8B} = 128K$

$\frac{128K}{2} = 64K$

$log(64k) = 16$

We calculate the total amount of blocks, then the amount of blocks per cache set and then get the log of that.

The Tag is just the remaining bits in the address: $32-16-3=13$ Bits.

So the address looks like this: \[Tag: 13 Bits\]\[Index: 16 Bits\]\[Offset: 3 Bits\]
> 0 votes

---
Tags: cache
---


# Question
Title: An electronic book is made up of 500 pages there are 16 lines of 2400 bits lines of each page. computer space it will ocuppy on a computer in GB
An electronic book is made up of 500 pages and there are 16 lines of 2400 bits lines of each page. compute the space it will ocuppy on a computer in GB

# Answer
> 0 votes
I mean if this is all the information you have then it's just $$\frac{500\*16\*2400 bits}{(1024^3)\*8} ≈ 0.002235 GB = 2.28 MB $$

---
Tags: algorithms
---


# Question
Title: Proof that a minimal DFA for a finite language has exactly one trap state
> Suppose $L$ is a language with a finite number of strings. We know that $L$ is regular. If $M$ is the minimal DFA for $L$, prove that $L$ has exactly one state that we can't exit if we enter it.

I know this statement is true because $L$ has a finite number of strings, so a string with a length longer than the length of the longest string in $L$ (let's call that string $s$) will not be accepted by $M$. Also, the last state that $s$ lands on cannot go to any other state which eventually leads to an accepting state.

Is there a better more solid way to prove this?

# Answer
Recall that in the minimal DFA, each state corresponds to an equivalence class of the Myhill–Nerode relation.

All words which are not a prefix of a word in $L$ form an equivalence class $X$, which satisfies the following: if $w \in X$ then $w\sigma \in X$ for all symbols $\sigma$. Therefore, the state corresponding to $X$ cannot be exited.

On the other hand, any other state in the minimal DFA can be exited, since we can always enter $X$ (for example, if we read more letters than the length of the longest word in $L$). Therefore the state corresponding to $X$ is the unique one which cannot be exited.
> 4 votes

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


# Question
Title: Why are computers so fundamentally insecure?
This really isn't a complicated question to ask but it is one to answer...

From the very fundamentals of binary code why are computers and similarly, computer language, just so insecure?

Should we just scrap all of it one day and start over? Computer security challenges are not necessarily winning against viruses, are they? If anything, from my layman's viewpoint, it seems that vulnerabilities are increasing.

# Answer
The point of a general-purpose computer is that it can do almost anything. It's an extremely flexible tool.

The point of a secure system is that it can't do most things. It can only do the things that are specified in the security requirements.

This is the inherent tension between security and flexibility (or usefulness or convenience or usability). General-purpose computers tend towards the flexibility end since that is the whole point. If you want security, buy a pocket calculator from a trustworthy vendor.

---

It *is possible* that the bridge can be crossed by dividing the system up into compartments, so that within a compartment there is full flexibility, but different compartments can't access each other. For example: processes, users, Docker containers or virtual machines.

But inevitably, people want different compartments to access each other. For a start, I want my mouse and keyboard and display screen to be able to interact with all compartments - otherwise why bother having them? But then a compartment running malicious code can trick me into thinking it's the login screen compartment so I type in my password. So instead we can say that the system always displays a compartment identifier at the top of the screen. Now we have increased security because it won't say "login screen" unless it's the login screen. But we have also decreased flexibility - what if I want to play a game in full-screen without this distracting title bar? Maybe we add a permission flag that says the title can be turned off for certain compartments. But then the video game may contain malware, so that after I leave and come back, it shows a fake login screen, including a fake login screen title. We decreased security again to gain flexibility. You see the tradeoff?

Secure Attention Key fits in this category. Only the system can respond to Ctrl-Alt-Del, so if you press Ctrl-Alt-Del and the system responds, you know your input was received by the system itself and not some program pretending to be the system. Remember the Windows XP login screen? But now, imagine you have a virtual machine and you want to log into the virtual machine, but you can't because the necessary key combination can only be received by the host system. (In practice, VMs from that era just *overwrite Windows code* to send the keypress to the VM. How does it know it's sending it to the VM and not some malware?)

---

It doesn't just apply to user interaction, but also network interaction, and disk interaction, for example. Perhaps we say that Word can only access files under /Files/Word and Firefox can only access files under /Files/Firefox. Cool... until you want to download a Word file and open it. Now you have to use the file manager (with access to all files) to move the file from /Files/Firefox to /Files/Word, before you can open it. High security, low convenience.

Or maybe we say Word also has access to all files the user double-clicks on that are associated with Word. Now you have three problems: (1) what if the user opens the file with File-\>Open instead of double-clicking, (2) what if the user opens the file by clicking in Firefox instead of in the file browser, (3) if Firefox can somehow trigger this behaviour when the user single-clicks in the download list, what prevents Word from sending the same trigger for files the user never clicked at all? Maybe we now have to enforce a standard file browser dialog for all file operations. Medium convenience, medium security. Low security if any application can just tell the system that the user clicked on any file. Low security if they can trick the user into clicking on files, such as by opening up a file browser dialog right before the user clicks.

---

XKCD sums up the situation well:

Systems often bake in these holes (since, again, it's their purpose) to the point where it's hard to create a solid boundary again. Both X11 and Win32, for example, contain big balls of compatibility mud that any process can call into, with not much security other than whether you can access it or not. And you can't even stop certain processes from accessing it - giving programs access to display stuff on the screen is the entire point of having a windowing system.

There's a compatibility ratchet mechanism here. Even when the system includes a technical mechanism to prevent access to something, applications come to rely on whatever access they have. In Windows 8 there is now ProcessSystemCallDisablePolicy which allows you to block access to the windowing system from specific processes. It's only narrowly applicable, because so much code *relies* on the available flexibility. Google tried to block it for Flash but Flash was using it to list the fonts installed on the system. A single call forces you to leave access enabled, or else people won't use your shiny new operating system that makes all their programs crash. Meanwhile, adding new access is easy.

---

In fact, it doesn't even always require a bug to break a security boundary, just an unexpected interaction. Windows lets one process send events (window messages) to another process's window. It also has a timer-expired event (WM\_TIMER), one of whose arguments is a function pointer. See the problem? This was fine for Windows 3.1.

You can try to patch up holes that are too big, while being careful to allow legitimate calls. Windows's User Interface Privilege Isolation prevents medium-integrity processes from sending WM\_TIMER messages (and *all* messages) to high-integrity processes. Such patches necessarily still leave many holes open, since they try to avoid blocking messages that actual software requires to work properly, so they are unlikely to guarantee security.
> 4 votes

# Answer
Designing a security system is a compromise between

* I want my computer to allow me any kind of usage, even remote, without constraints. After all, it is mine.
* I also want to grant my friends some limited access, though managing this should be easy. After all, it is mine.
* I don't want aliens to access my system or use it in any way. After all, it is mine.

This quickly leads to complexity, because scenarios are innumerable, and bugs are not avoidable. They will never be.
> 1 votes

# Answer
Another thing to add to the first answer:

Let's say your computer is not a computer, but a house. You buy a house and you buy a security system with it to keep it safe. The security system depends on what you can afford and how valuable your house/ the things inside are - it can be a simple door with a key, a high wall around your property, cameras, hell even lasers that shoot anything on sight.

Now, even if you've had nothing valuable in your house, people would probably try to get in just for the challenge. If you keep something valuable there, they will try to get in to steal it. So either way people will try, and the more people try the more likely it is that one of them is smarter/ more creative than the people that created your security system.

I think it's very similar with computers. There are no concepts for complete safety, whether you are a regular person or the FBI or whomever else. Because all concepts were thought of by humans, and so all concepts can be bypassed/ broken by (equally smart) humans.
> 0 votes

---
Tags: security
---


# Question
Title: Travelling Salesman Problem Easy Algorithms
I'm looking for a easier algorithm to implement to solve the travelling salesman problem (in javascript). Unluckily all of the ones i found are really hard to understand/ to implement.

The ones i already have are the nearest/farthest-neighbour-algorithms. Do you guys have any other suggestions?

# Answer
It is an *extremely* hard problem to solve. But some reasonable heuristics are easy to explain/code.

One is to start at a random vertex, each step move to the vertex that hasn't been visited yet that is closest. Rinse and repeat.

Another is to start with a minimal spanning tree of the graph, pick any vertex as starting point (root), and visit the vertices in preorder. If you are asked to visit a vertex that you already visited, just skip it for the next one in preorder. Think about it as walking along the "outside" of the tree, taking shortcuts to the next when asked to visit a vertex again. This works rather well if the distances have the triangular property (i.e., $c(u v) \le c(u x) + c(x v)$ for all vertices).

See if you can come up with another idea.
> 0 votes

# Answer
There’s a trivial algorithm running in n! . That would be good enough for n=12. N=16 would talk about 43,000 times longer - probably just outside what you’d call a solution. Here’s a method that should save you just enough time to solve for n=16:

Take a sub tour abcd. If the distance abcd is longer than the distance acbd then abcd cannot be part of an optimal tour (since swapping b and c creates a shorter tour). If both sub tours have the same length we can arbitrarily exchange b and c if b is later in the alphabet than c. So we accept exactly half of the subsequences in an attempt to find an optimal tour.

Now we pick any fixed city b as the second city. We don’t need to try different cities as the second city because we can rotate the tour. We then pick any a and c as the first and third city, picking their order so that a comes before c in the alphabet. There are 15 x 14 / 2 = 105 choices for these three cities.

Then we choose the fourth city d. But instead of 13 choices, the requirement that abcd is not longer than acbd removes on average half the choices, so 6.5 on average. For cities 15 and 16 there is only one choice.

Total choices for the order of all cities is 15! / 2^13 ≈ 160,000,000. You’ll need to implement this in an efficient way. For general n, it is (n-1)! / 2^(n-3).

You could improve this by choosing which sequences abcde are possible. B, c and d can be visited in six different orders, and only one can be optimal.
> 0 votes

# Answer
Brute-force is not that difficult. All you need to do is to generate all permutations of a vector `(0, 1, ... n-1)` and compute the length of the corresponding cycle.

To generate the permutations, consider the input vector, extract one element at a time and recurse on the remaining elements.

E.g.

```
Permute(0, 1, 2, 3) ->
 0 + Permute(1, 2, 3),
 1 + Permute(0, 2, 3),
 2 + Permute(0, 1, 3),
 3 + Permute(0, 1, 2)

```
> 0 votes

---
Tags: algorithms, traveling-salesman
---


# Question
Title: How does vector space model differs from traditional B-tree indexes
I've asked the following question on StackOverflow: https://stackoverflow.com/questions/71819288/mongodb-vs-elasticsearch-indexing-parallel-arrays

I think that getting theoretical information on this subject can help me better to grasp the context and maybe I'll be able to answer my own question.

Note: I've changed the title, here it is more comments for clarification.

How does ElasticSearch like solutions differs from traditional databases? On storing, retrieving, modeling data. Most importantly, in case I want to do exact matching and filtering. Will there be real benefit of using such a technology considering I created my NoSQL databases indexes perfectly.

# Answer
**\*In response to the original question, inverted index vs btree indexes\***

Lets look at what these 2 types of indexes are

***Forward Index/Index***

**Here the search key(attribute on which the index is built) is the name of the document**. Consider a telephone book, where names are sorted alphabetically. While searching the phone number for a person whose name starts with N, you directly go the page where names from N start and then continue searching till you find the name you are looking for.

***Inverted Index***

**Here the search key is a part of the content of any of the document**. Take for instance the index at the back of a reference book. The keywords are listed alphabetically and the index show the page numbers on which a given keyword is present. In this case too if you want to find where a keyword starting with P occurs, you would directly go to the page where keywords for P are listed and then search further.

Knowing both these ideas, you might think, can one use a forward index to search the pages where a keyword occurs, or can you use an inverted index to find the phone number of a person, and the answer is yes, you can search anything using any type of index theoretically. However, **the main purpose of an index is to make the lookup/search take less time**, and this depends on what you are trying to search and what indexes you are using to search.

> Consider a database having reviews for a movie stored area wise. Assume it has 3 columns id, area\_code, review. Id is the primary key, areacode is a unique integer representing some area and review is a text review.
>
> Lets say you want to find out what the users of area 007 think about your movie, in this case you create an index on the column movie and easily find out the reviews for that area.
>
> Now consider that you want to find out the number of users who gave a positive review to your movie. A review would be a text, of highly variable length and content and very high redundant content. But you assume that certain terms like "excellent", "mind bending", "masterpiece" etc could be found in a positive review. So here you use an inverted index, which basically would tell you in which reviews there were positive terms used, so you can get a rough estimate of the count.
>
> And finally you can combine both scenarios where you want to find out the good reviews of a particular area, so you use both the indexes.

**This is a theoretical description of what those indexes are and how they are to be used**. But when you need to implement them, you need to think about how it would perform (reducing disk accesses or as in my example at the beginning, you need some way to reduce the number of pages you have to go through) and one way to approach this is to use B-trees.

You can read upon B-trees anywhere, **but to answer your question, a both the forward and inverted index can use B-trees**, because in both the cases you have an index file which needs to be accessed efficiently, and B-tree lets you do exactly that.
> 0 votes

---
Tags: data-structures
---


# Question
Title: How can you convince your colour-blind friend that two balls have the same colour?
I was reading about zero-knowledge proofs. I understand how one can convince their colour-blind friend that the two chosen balls have different colours.

Now what happens if the two chosen balls have the **same** colour - is there a zero-knowledge proof that will convince your colour-blind friend that they are the **same** colour? If you follow the classic protocol then you will obtain a 50% chance of guessing correctly that the balls were swapped.

However, this does not rule out the case when the balls are different colour and you were simply lying to obtain the same 50% chance of guessing correctly. In other words, your colour-blind friend will not know whether you are lying or telling the truth.

# Answer
> 18 votes
#### Summary

Suppose Victor, who is colour-blind would like Peggy, who can tell colours to convince him that two balls (the unknown pair) are the same colour. Assume Victor has another pair (the known pair) of balls that have different colours. All balls are either green or red.

**Here is the zero-knowledge proof (ZKP).** See later sections for the rigorous specification.

Victor will select one ball from the unknown pair and one ball from the known pair randomly and secretly. Then ask Peggy whether the selected pair are the same colour. Repeat this routine as many times as needed.

If Peggy changes his answer if and only if Victor select a different ball from the known pair, Victor gains confidence that the unknown pair are the same colour. Otherwise, the protocol ends immediately with Victor gaining no information.

#### The setup: preconditions and goals

The ingenious zero-knowledge proof (ZKP) for the case of two balls of different colors is not applicable directly to the case of two balls of the same colour. It turns out the verifier needs to bring two extra balls, at least.

Preconditions:

1. There are two people, Victor and Peggy. Victor is colour-blind. Peggy are allowed to lie in whatever way.
2. Victor has two balls, the known pair, one of which is red and one of which is green. Victor does not know which one is red, however.
3. There are two other balls, the unknown pair. Both are either red or green. Both may or may not be the same colour.
4. All balls are identical except possibly by their colour.

Goals:

1. Victor wants to be convinced of the same-colour-ness of the unknown pair if they are the same color. Victor should not be fooled into believing the same-colour-ness of the unknown pair if they are not.
2. If the unknown pair are the same colour, at the end of protocol, Victor should not have gained any information except that same-colour-ness as long as Peggy did not found Victor had violated the protocol.

#### A simple interactive ZKP that proves two balls are the same colour.

1. Victor selects a ball $U$ from the unknown pair and a ball $K$ from the known pair. Victor will keep track of $K$ and the known pair until the end of step 3 below.

Victor displays $U$ and $K$ in some random order to Peggy, asking "are they the same colour?" Peggy replies with either "YES" or "NO".
2. Victor selects ball $U'$ from the unknown pair *secretly* and *randomly*, which may or may not be $U$. Victor also select ball $K'$ from the known pair *secretly* and *randomly*, which may or may not be $K$. In any case, Victor knows whether $K'$ *is* $K$ or not.

Victor displays $U'$ and $K'$ in some random order to Peggy, asking "are they the same colour?" Peggy replies with either "YES" or "NO".
3. Note that if the unknown pair are the same colour and Peggy responds correctly, then her two replies are the same if and only if $K'$ *is* $K$. If that is the case, Victor becomes more likely to believe that the unknown pair are the same colour. Otherwise, Victor will claim Peggy cannot prove that the unknown pair are the same colour and stop the whole protocol.
4. Victor passes the known pair to Peggy, who passes them back after making sure they have different colours as well as shuffling them randomly secretly. If Peggy find they are the same colour instead, Peggy will claim Victor violate the protocol and stop the whole protocol.
5. Repeat step 2 to 4 as many times as necessary until Victor is convinced that the unknown pair are the same colour.

#### Can Victor just run step 1 repeatedly?

Someone might wonder, can Victor just repeat step 1 with secret and random selections each time, gather the results so that he will know whether the unknown pair have the same colour as one of the balls in the known pair?

That scheme implies that Victor at the end of a successful run of the protocol knows that the colour of the unknown pair is the same as a particular ball in the known pair, a ball that Victor that identify. This is information beyond the same-colour-ness of the unknown pair, even though Victor still does not know the actual colour of the unknown pair. For example, Victor can confidently present three balls of the same color, which is a task that he could not do with certainty had he not known that extra piece of information.

In general, had Victor been able to track the balls selected from the known pair across the whole protocol, he would be able to associate the colour of the unknown pair with one particular ball in the known pair.

These three steps and especially step 4 are designed to prevent leak of knowledge, even if Victor tries to gain extra knowledge without violating the protocol in any way that can be detected by Peggy.

#### There are many other solutions

This answer shows a brilliant simpler solution, assuming the availability of two identical boxes in addition to the required known pairs of balls.

This answer is a simpler-to-explain variant of this answer.

# Answer
> 11 votes
## Zero Knowledge

*You can't prove the balls are the same if you only have two balls with no means of testing the difference.*

This is essentially asking for proof of philosophical zombies (the idea that two physically identical objects are different in some undefinable way, while being identical in every definable way).

Scenario 1: you have a red and green ball. I lie every time, claiming they're the same color.

Scenario 2: you have two red balls. I tell the truth every time, claiming they're the same color.

You don't know the colors, and my claim is the same in both cases, so you can't determine whether my statement is true or false.

## Partial Knowledge

*Any method you can use to differentiate the balls defeats the zero knowledge portion, but that might be acceptable in some cases. If you modify the conditions to include a known pair of balls that doesn't match, that gives you extra knowledge (the pair doesn't match) by definition. However, no additional knowledge is gained during each test, so it's zero knowledge given the context of additional starting knowledge.*

You have a red ball, a green ball, and an unknown ball (that's guaranteed to be red or green). You already know red and green are different (proven by the Wikipedia method), and now you have a third ball. By keeping track of the balls' positions out of my sight, then asking whether the balls match or not, you can determine whether I'm lying or not.

* If I claim red and green are the same, or that red and red or green and green are different, I can't be trusted to know the difference, end test.
* If I consistently say red and green are different, I'm telling the truth.

There are two scenarios: unknown is red, or unknown is green. First, presume unknown is red.

* Lie: If I claim unknown and green are the same, then you can sometimes show me red and green, and sometimes show me unknown and green. Because I don't know which case is happening (because unknown isn't green), I'll get it wrong about half the time.
* Truth: If I claim unknown and red are the same, you can sometimes show me green and red, and sometimes show me unknown and red. Because I'm consistently able to differentiate green from red, while claiming unknown is red, you can know unknown isn't green (or I would have gotten it wrong half the time).

Second, presume unknown is green, then switch the above tests.

* Truth: If I claim unknown and green are the same, you'll show me red and green or unknown and green and I'll consistently get it right.
* Lie: If I claim unknown and red are the same, you'll show me green and red or unknown and red and I'll get it wrong half the time.

In these cases, you don't know which is red and which is green, but you can build collections of red and green balls and determine which collection a new ball belongs to. Of course, if I constantly lie, you can't get any useful information out of me, but you know I'm lying.

**Zero Extra Knowledge**: To prevent building collections of red and green balls, you can randomly shuffle the known red and green ball after finishing the protocol. Now, you know the unknown ball matches the known ball I claimed it matched, but you can't use that information to match the unknown ball to any particular unknown ball from a previous or future test.

## Multiple Discrete Colors

*The above won't work with an unknown number of colors. However, it will work for a finite number of discrete colors if you have one of each color already. Essentially, you do tests for each color. For all but one color, I'll easily tell the ball never matches. But for one color, I'll claim they match. I can lie when they clearly don't match, but I can't consistently lie when they do match, as above.*

For each color, X:

* Compare unknown to colorX. If I claim they're different, move to next X.
* If I claim unknown matches colorX do a test with each other color, Y.
* Do the test as we did with red and green above, but now with colorX and colorY. If I'm telling the truth, my statements will always be correct.
* If I'm lying (i.e., colorX and unknown don't actually match), there will be a particular colorY that does match unknown, and I won't consistently tell them apart.

Again, you can't determine what color a normal person would use to describe each ball, but you can determine which group to put a new ball in. By shuffling the known balls after the protocol, you can prevent building collections of balls, since you don't know which ball from this test matches the unknown ball in a previous or future test.

## Matching the Initial Question Better

*The question posits a scenario where I hand you a pair of balls and claim they're the same. Other answers use an independent pair of non-matched balls to test the pair I handed you, and those answers are probably better for general use. However, I went with the idea of using only three balls total, so I'll expand that here since the four-ball solutions already exist.*

I'll hand you three balls, call them A, B, and C, and tell you A and B match, while C doesn't. There is still a requirement that you somehow know each ball *must* be red or green.

* 1,. You use the standard Wikipedia protocol to prove that C doesn't match A (shuffle A and C and if I get it right consistently I can clearly differentiate between them).
* 2a. EITHER use my protocol to prove that B matches A. If it matches A, I was right.
* 2b. OR use the standard protocol to prove that C also doesn't match B. Because C doesn't match A or B, A must match B. If C doesn't match B, I was right.

This is still not zero knowledge in the context of the original question, because you've learned not only that A matches B, but that A and B don't match C. However, I think it's the minimal amount of extra knowledge you can gain while proving A matches B.

This can still be expanded for many colors.

* I hand you balls A, B, \[$C\_1$, $C\_2$, ... $C\_n$\].
* For each pair in \[B, \[$C$\]\] you prove that pair is distinct using the Wikipedia method.
* Then you prove that A doesn't match anything but B.

Again, there's the requirement you somehow know there can only be (n+1) ball colors.

## Conclusion

I don't know if any of the above is actually useful in a real-world application, but I think it's a sufficient answer to your question. None of the given answers are truly zero knowledge, but do allow for zero *extra* knowledge given the modified constraints.

# Answer
> 9 votes
This seems like a simpler-to-explain variant of John L.'s answer.

Victor has four boxes: one contains two red balls (RR), one contains two green balls (GG), one contains RG, and one contains the two unknown balls.

Victor repeatedly shows Peggy one of the boxes at random, and asks her if the balls in it have the same color.

A sufficiently long series of experiments in which Peggy produces correct answers to the first three boxes and a consistent answer "yes" to the fourth box will convince Victor that she is telling the truth and that the answer for the fourth box is "yes".

# Answer
> 7 votes
With the following assumptions it should be easy (which are actually weaker assumptions than the accepted answer I think)

1. All balls are only 1 of 2 colors
2. In addition to the 2 balls (pair 1) that need to be proven to be equal you have 2 additional balls (pair 2), one of each color.

If necessary, first prove to him that the additional balls are in fact different color, using the known ZKP method to do that.

Then simply use that same ZKP method on the pairs of balls. Pair 1 and pair 2 can only be distinguished if pair 1 has the same color balls.

# Answer
> 4 votes
Interesting! In fact, the following condition from the Wikipedia page: *if the statement is false, no cheating prover can convince the honest verifier that it is true, except with some small probability.* \- makes the things complicated, while the prover can pretend they do not distinguish between the balls.

I think that there are much better solutions to this question than the following mere sketch.

A quite artificial almost-ZKP I have on my mind is as follows. Let us have the two pencils, red and green, such that they are undistinguishable to the verifier, having the colours exactly as the green and red balls (this assumption is greatly artificial, but I do not know how to do better). The prover can convince the verifier that the pencils are really different using the Wikipedia technique. Then they iterate the following step. The verifier marks the two balls by letters using the both pencils in such a way that the marks done with the same pencil are equal on the both balls, but their distribution varies. Say, he marks the first ball with $A$ by the red pencil, and with $B$ by the green pencil, and the second ball is marked with $B$ by the red pencil, and with $A$ by the green. So, the sets of the letters are the same: $\\{A,B\\}$. Then the prover must name the two letters forming the set. If the balls have the equal color, then they always succeed in the naming, because the marks done by the pencil with the other color are distinguishable. If the balls have different colors, then the marks done in the corresponding colors are not visible by the prover, and they would not see one of the two given letters.

Besides the assumption of the existence of such pencils, this proof has another flaw, but I do not know whether it is relevant to ZKP. The verifier cannot know which one of the pencils is red and which is green, but in the case the balls have different colours, the verifier can retrieve the information that some ball is the same colour as the given pencil if the prover always names (or at least tries to name) the marks done on the balls. The possible solution is: if the prover cannot name the two distinct letters, they simply reject to guess. Since the prover want to prove that the balls are of the same colour, and does not want to reveal any additional information, it is unreasonable to them to make the false guesses.

Another possible solution (though, somewhat not complete) is inspired by John's L remark about usage of the additional balls. Let us suppose the common knowledge that the balls are taken from a box containing balls of $n$ possible colours. Then the prover can take $n-1$ other balls from the box (all having distinct colours different from the colour of the two chosen balls) and prove to the reviewer that the colours of these $n-1$ balls are all different and that they are different from the colour of the both chosen balls. Then by pigeonhole principle the reviewer will be convinced that the chosen balls must have the same colour. But additionally the reviewer get the knowledge that the $n-1$ balls taken from the box by the prover have different colours, and some information leak happens there. I wonder if there is a way to fix it.

# Answer
> 0 votes
Take two balls A and B of the same color (both red or both green), then take a third ball C of opposite color.

Give all three balls to your color-blind friend and convince them that A and C have different colors, then convince them that B and C have different colors using the known method. During this process, the friend should keep track of all three balls, so in the end, they will still know which ball is A, B and C.

The friend is only color-blind to red and green as per problem statement. So now they know that if C is red, A and B must be both green, and if C is green, A and B must be both red.

# Answer
> 0 votes
What is wrong with following (sorry for missing the obvious)?

> First: (as *verb*) **convincing** someone of something may give linguistic connotation you want to potentially fool someone of something which is not the case. In ZKP wikipedia page one uses **proving** and one also use convincing (as *adjective*) in 'convincing proof'. For what follows, if permitted, I stick to **proof**

> Next, P (prover) **wants** to prove to (colour-blind) V (verifier) to have the knowledge k where in this case k = 'balls have *same* colour'. P wants to leak no extra information to V (or to any other spectator)

> What is wrong with following ... (similar to *different* colour): P defines following protocol to be followed by V: each time in a row, V hides balls behind the back, P closes eyes and V swaps balls or not. P looks at one ball and cooperates (after all P wants to prove something to V) by, as a perfect thinker guessing if balls were swapped or not. If balls have same color, there is no way P can **always** guess correctly. So P will soon one time in the row guess incorrectly. The protocol could continue and probability of P guessing correctly would converge to $0.5$. But, isn't a **single** incorrect guess a proof? Because probability to always guess correct is zero.

---
Tags: zero-knowledge-proofs
---


# Question
Title: Question on formal languages, proving equality
I'm new here and im struggling right now on the following task:

I have to show that:

(L1 ∩ L2) o L3 = L1 o L3 ∩ L2 o L3

L1, L2 and L3 are three languages over the alphabet Σ. o stands for the concatenation of two languages.

kind regards

# Answer
> 1 votes
That claim is false (in general). Consider for example $\Sigma = \\{a,b\\}$, $L\_1 = \\{a\\}$, $L\_2 = \\{ab\\}$ and $L\_3 = \\{\varepsilon, b\\}$.

Then, $(L\_1 \cap L\_2) = \emptyset$ and hence $(L\_1 \cap L\_2) \circ L\_3 = \emptyset$. However $ab$ belongs to both $L\_1 \circ L\_3$ (since $a \in L\_1$ and $b \in L\_3$) and $L\_2 \circ L\_3$ (since $ab \in L\_2$ and $\varepsilon \in L\_3$), showing that $(L\_1 \circ L\_3) \cap (L\_2 \circ L\_3) \neq \emptyset$.

---
Tags: formal-languages
---


# Question
Title: Number of binary words that form a group of Hamming weight at most d
Consider binary words in {0,1}^n whose Hamming weight is at most some constant d. We want to select some of these words such that they form a group under addition. How many words can we choose at most?

# Answer
Your structure is known as a *group anticode* with maximal distance $d$. The obvious construction is to take all vectors of the form $(x\_1,\ldots,x\_d,0,\ldots,0)$, obtaining a group of size $2^d$. Ahlswede, Another diametric theorem in Hamming spaces: optimal group anticodes showed that this is optimal, and furthermore, the solution I described is unique up to isomorphism, except when $d = 2$, in which case another solution is $(0,0,0,\bar{0}),(1,1,0,\bar{0}),(1,0,1,\bar{0}),(0,1,1,\bar{0})$.
> 1 votes

---
Tags: combinatorics, coding-theory, algebra, group-theory, hamming-distance
---


# Question
Title: A decidable language that can't be decided by a circuit ensemble of linear size
Let Size(O(n)) be the set of languages the can be decided by a circuit ensemble (a sequence of circuits C\_i for every natural i s.t input size is i) such that every circuit's size is linear (in input size). I would like to prove there exists a decidable language that doesn't belong to the set defined above. I tried using a fixed input size and using an upper bound for the number of possible languages that can be implemented by such circuit, and to show it is a polynomial upper bound (while there are 2^2^n languages). Problem is, I'm pretty sure this proof doesn't hold, because this circuit ensemble consists of C\_n which can be in size n2^n and all other circuits are constant on 0, and since n is fixed it can be perceived as an O(1) upper bound for all circuits.

If anyone could help I'd very much appreciate. Thanks

# Answer
You can show more: there is a function in $\mathsf{EESPACE}$ (doubly exponential space) which has *maximal* circuit complexity. Given an input $x$ of length $n$, enumerate all Boolean circuits with $n$ inputs in increasing order of size, until you encounter all Boolean functions. Choose a Boolean function $f$ of maximal circuit complexity, and output $f(x)$.
> 0 votes

---
Tags: time-complexity, computability, computation-models, decidability
---


# Question
Title: Find two very frequent items in a given array of comparable items
I am new to this community and I have a question regarding a problem I was trying to solve. Could anyone review my algorithm for solving this problem? I want to emphasize also that the algorithm must use the Quickselect algorithm (i.e. https://en.wikipedia.org/wiki/Quickselect).

The question is :

> Given an array A\[1..n\], write an algorithm that checks if there are two elements satisfying the following conditions (Algorithm runtime should be O(n)):
>
> 1. $ x \< y $
> 2. The value of x appears **more than** n/3 times
> 3. The value of y appears **more than** n/4 times

The algorithm that I suggest for solving this problem is the following:

1. Find the median of the array A\[1..n\] using QuickSelect and store its value inside a variable M.
2. Partition the array around M.
3. Find the median of the array A\[1...n/2\] using QuickSelect (left part of the partitioned array from above) and store its value inside a variable M1.
4. Find the median of the array A\[n/2...n\] using QuickSelect (right part of the partitioned array from above) and store its value inside a variable M2.
5. Partition the two sub-arrays from stages 3-4 around M1 and M2
6. The elements must satisfy $x,y \in \\{M, M1, M2\\}$ because the array now is "almost sorted" and the distance between two medians is n/4 (here I am not sure if I can say it is correct because of the pigeonhole principle).
7. Iterate over the array and count the occurrences of M,M1,M2 to check if they're satisfying the conditions of the question then return true if yes, or false otherwise.

EDIT: To be more specific my main concern about this algorithm is in stage 6 where I claim that the elements we are searching for (i.e x,y) must satisfy $x,y \in \\{M, M1, M2\\}$.
In other words, this is equivalent to the question that if we are given an array A\[1..n\] and two elements x and y which occurs n/3 times and n/4 times respectively, can we find what those elements are by partitioning the array A\[1..n\] for the first time around the median of A\[1..n\] and then partitioning the 2 sub-arrays to the left of the median (A\[1..n/2\]) and to the right of the median (A\[n/2..n\]) around **their median** ?

My motivation behind this claim is the fact that x and y each occur more than n/4 which means that if nor x nor y "sitting" on the median of A\[1..n\] then the median must be an element such that x\<M\<y therefore if we split the 2 sub-arrays A\[1..n/2\] and A\[n/2..n\] around their medians we can say that their medians must be x and y (because each one of the sub-arrays is of size n/2 and the values x or y occur more than n/4 which is more than half of n/2).
Otherwise, if the median of A\[1..n\] is x or y (let's say x) then with pretty much similar reasoning we can say that one of the medians of the 2 sub-arrays must be y.

Will appreciate any clue or review for this algorithm, thanks!

# Answer
> 1 votes
Your algorithm is pretty good, although there is ambiguity.

"the median of the array $A\[1..n\]$" is ambiguous. Is the median of the array $\[3,5\]$ $3$ or $5$ or $4$?

"the array $A\[1..n/2\]$" is ambiguous when $n$ is odd.

While it is common to use $n/2$ to denote/mean $n/2$ or $\lfloor n/2\rfloor$ or $\lceil n/2\rceil$, whichever that is suitable on the fly in complexity analysis or in summary understandings, it may lead to off-by-one error in the current case. It is not immediately clear the size of the interior of each interval is no more than $n/4$.

---

Here is a clearer way to express your algorithm.

1. Use QuickSelect to find the $\lfloor n/4\rfloor$-th, $\lfloor n/2\rfloor$-th and $\lfloor 3n/4\rfloor$-th smallest elements of $A$. Let them be $M\_1$, $M\_2$, $M\_3$.
2. For each $i\in\\{1,2,3\\}$, iterate over the array and count the occurrences of $M\_i$. If there are a pair of elements among $M\_i$s that satisfy the wanted conditions, return true. Return false otherwise.

---

Here is how we can explain the correctness of the algorithm. Why $x,y \in \\{M\_1, M\_2, M\_3\\}$?

Assume $n\ge4$ and all $M\_i$s as well as the largest element are distinct. The number of elements

* less than $M\_1$ is at most $\lfloor n/4\rfloor-1\le n/4$.
* bigger than $M\_1$ and smaller than $M\_2$ is at most $\lfloor n/2\rfloor-\lfloor n/4\rfloor-1\le n/2-(n/4-1)-1= n/4$.
* bigger than $M\_2$ and smaller than $M\_3$ is at most $\lfloor 3n/4\rfloor-\lfloor n/2\rfloor-1\le 3n/4-(n/2-1)-1= n/4$.
* bigger than $M\_3$ is at most $n-\lfloor 3n/4\rfloor-1\le n-(3n/4-1)-1= n/4 $

So, the number of elements in any group is at most $n/4$. That is still true when $n\lt4$ or some of $M\_i$s and the largest element are the same, since there is no element in the relevant groups.

Suppose value $z$ appears more than $n/4$ times. Consider all elements that are the same as $z$. If none of them is $M\_i$ for some $i$, then all of them must be contained in one of the groups of elements computed above, which is impossible since the number of elements in any group is at most $n/4$. So $z$ must be one of $M\_i$s.
Thanks to the explicit counting above, we can be confident in the logic deduction here.

---
Tags: algorithms, runtime-analysis, arrays, selection-problem
---


# Question
Title: What does it mean for a machine language to be Turing-complete?
I was reading the Wikipedia article on Turing completeness, but I was having a hard time putting together all of the concepts. In simple terms, what does it mean for an instruction set to have Turing-completeness?

# Answer
> 1 votes
A turing complete program means it can do anything a Turing Machine can do. Ok, what in the world is a Turing Machine? Well, Alan Turing had a brillant idea, a made up machine which has a infinitely long piece of tape (otherwise known as memory). The machine also has a head, which can do 3 things:

1. Read the symbol on the square under the head.
2. Edit the symbol by writing a new symbol or erasing it.
3. Move the tape left of right by one square so that the machine can read and edit the symbol on a neighbouring square.

With only these simple components, a turing machine can theoretically compute anything given enough time. So, a computer language is said to be turing complete if it can do what the turing machine can, or in other words run any computer problem given enough time and memory.

---
Tags: turing-machines, turing-completeness, theory
---


# Question
Title: How can this MIPS processor execute one instruction in one cycle?
I'm reading section 7.3 (SINGLE CYCLE PROCESSOR) of Digital Design and Computer Architecture, Second Edition by David Money Harris.

At the end of the section the autor shows this MIPS processor and says that "Each instruction in the single-cycle processor takes one clock cycle".

The autor also says that "Result must setup at the register file before the next rising clock edge, so that it can be properly written". If I'm correct, he is saying that the processor has the whole cycle time to execute that instruction, but Result should be present at the rising edge of the clock of that same cycle because the PC, Register File and Data Memory are changed only during the clock edge. Thus, the processor has only the rising time, not the cycle time, to execute the instruction.

I don't understand how he can say that an instruction can be executed in one cycle time if the elements are chained like that and even the Register File has to wait for its own result to be processed and arrive at WD3 in the same cycle.

# Answer
The register file in this design is multi-ported, and the read ports work like combinational circuits. The only thing between the read input and the output port is propagation delay. The clock signal is only needed to *write* a value.

The same is true for data memory, which is assumed to be a combinational circuit for the purpose of issuing a read.

If the value of a register is modified, and then the same register is read on the next instruction, then there may be a propagation delay before the newly-loaded value is valid at the read port, but that's a limitation on the clock speed, not on the correctness of the data path. As long as the input to a latch is correct at the time the latch is loaded, the CPU will work correctly.
> 1 votes

---
Tags: computer-architecture, clocks, mips
---


# Question
Title: Number of bits for physical address and virtual address
According to my understanding a 32-bit machine determines the number of bits of physical address as 32 bits , and hence , we can address a physical memory space of 4GB. So the number of bits of physical address depends on the machine type . My question is what about the virtual address ? I mean what is used in a machine to determine the number of bits of a virtual address ? In paging for example , the number of bits for a virtual address is not necessarily the same as that of physical address. So what determines the number of bits of virtual address in a system ?

# Answer
> 1 votes
A 32 bit machine usually has 2^32 bytes of address space *per process*. So the total address space can be much larger. An old PowerPC processor had a total of 2^52 bytes of address space, which just means it could handle one million processes. On the other hand, RAM can also be larger, for example there were 32 bit Intel processors that could address 64 GB of RAM. You would need at least 16 processes to use that RAM.

---
Tags: virtual-memory
---


title: Redistricting algorithm

text:
# Question
Title: Redistricting algorithm
Here in the USA there is a lot of controversy over the practice of gerrymandering. Every ten years the states are divided up into new congressional districts and whoever is in charge creates bizarrely shaped districts to suit their own political ends.

So the question is -- is there an algorithm to optimize, or at least automate, this process?

Express it like this:

Given a flat plane of pixels, where each pixel has a weight, divide the plane up into n polygons such that the sum of the weights of pixels in each polygon have the same value within a tolerance of k%, such that the total number of sides to all the polygons is as small as possible.

# Answer
Yes, and no.

France is divided into administrative regions, which are divided into departments, which are divided into communes. These boundaries were redrawn during the French Revolution.

This was one proposal for the department boundaries for Metropolitan France (which is the part of France in Europe excluding Corsica), from September 1789:

Now clearly this doesn't respect population density, but the point that I want to make is that if you value minimising the number of sides of a polygon, this is what you're going to get.

If you do respect population density but still try to minimise the boundary, what you tend to end up with is a Voronoi tessellation around population centres.

Looking at a modern map, you can see that this geometric proposal was rejected in favour of boundaries that follow naturally-occurring boundaries (e.g. rivers, mountain ranges, perhaps major roads), that respect existing means of travel (e.g. public transport routes), and at least try to take into account shared community interest where practical.

So at the very least, it would seem to make more sense not to draw boundaries in arbitrary places, but to start with existing political administrative boundaries, such as suburbs, city limits, postal areas, and cadastral boundaries, and merge them using a clustering algorithm, with some combined weight that involves both the importance of natural boundaries (e.g. a large river weighs more highly than a minor road), and some notion of compactness. There are several well-defined measures of compactness, such as the area of the shape expressed as a proportion of a circle with the same perimeter.

Ultimately, drawing electoral district boundaries is a political process, not an algorithmic one. Australia has one of the most open processes for redistribution (which is their term for "redistricting"). It involves several steps of community consultation, and requires the reasoning behind proposed boundaries to be published.

Ultimately, the best protection against gerrymandering is probably that: transparency and community consultation.
> 1 votes

---
Tags: algorithms
---


title: Sorting optimization to presorted array

text:
# Question
Title: Sorting optimization to presorted array
I'm looking up the complexities of sorting algorithms. There can be performance harm when the array is already presorted when running certain algorithms. E.g. Using last element as pivot in quick sort would harm the performance when the array has already been pre-sorted. However, when I attempt to cross check with other sources for ways to walk around it, it seems there's no source suggesting putting in place a check to see if the array has already been sorted is one way to walk around, despite the simplicity of this solution.

So I wonder is it practically feasible? If so, why people are not implementing this on every sorting algorithms just before they begin to check if the array has already been presorted before the sorting algorithm executes? Especially when such checking only involve O(n) time at max.

# Answer
> 1 votes
I think what you have read are the implementations of most sorting algorithm in their basic form, which focuses mainly on the idea of how they sort elements. This makes them easy to teach, understand, and analyze. But they can be improved and modified. One sorting algorithm, which is being used in practice, with the kind of optimization you are thinking of is Timsort, which is based from mergesort and insertion sort.

Another fairly recent sorting algorithm that takes advantage of data having presorted runs is Quadsort.

---
Tags: time-complexity, sorting
---


# Question
Title: Mathematical Induction vs Strong Induction
In Rosen's book Discrete Mathematics and Its Applications, 8th Edition it is mentioned that:

> You may be surprised that mathematical induction and strong induction are equivalent. That is, each can be shown to be a valid proof technique assuming that the other is valid.

One of the examples given for strong induction in the book is the following:

> Suppose we can reach the first and second rungs of an infinite ladder, and we know that if we can reach a rung, then we can reach two rungs higher … prove that we can reach every rung using strong induction

If the two proof techniques are "equivalent", how can I prove the above example using mathematical induction (as opposed to strong induction)?

# Answer
> 1 votes
In this case it is simple: Instead of proving "For every n ≥ 0, I can reach rung n on the ladder", you prove "For every n ≥ 0, I can reach rung n on the ladder, plus I can reach rung n-1 if n ≥ 1".

The statement is true for n = 0. The induction step n-\>n+1 works for n = 0 (because I can reach rungs 0 and 1); for n ≥ 1 I could reach rung n and n-1. Since I can reach rung n-1, I can also reach rung (n-1) + 2 = n+1, therefore I can reach rung n and n+1, so the statement is true for n+1.

---
Tags: discrete-mathematics
---


# Question
Title: How can I implement this algorithm to find all pairs of points at a distance of 1?
I am trying to find an algorithm which, given a set of N points on a 2D plane, can find all pairs of points at a distance of exactly 1. I believe this is similar to this question. I looked at the answers to the linked question.

One answer mentions a "Well Separated Points Decomposition", although I am unsure of how to use it to enumerate all the pairs of points in the answer.

Another answer mentions the "incidence reporting problem", but I am unable to fill in the details of the algorithm that is described.

Can someone please explain how either of those two algorithms works?

# Answer
It very much depends on your data. Say you have two million points, with $x\_i$ randomly in the interval \[0, 1000000\]. Simple and fast: Sort the points by first coordinate, then for every point $(x\_i, y\_i)$ you compare with the points $(x\_j, y\_j)$ for j ranging from i + 1 to n as long as $x\_j ≤ x\_i + 1$. On average you compare with two other points.

Now assume you have two million points, with coordinates randomly in the interval \[0, 2\]. The algorithm above is totally useless. Divide the x-axis into intervals of size d for a suitable d, say 0.01, then for each of these intervals you collect all points with $x\_i$ in the interval, and sort them by $y\_i$.

For example, you will have all points with $0.37 ≤ x\_i ≤ 0.38$. You compare them to points with $x\_j$ in the intervals from $\[0.00, 0.01\]$ to $\[1.37, 1.38\]$. For each $x\_i$ and each interval you compare with, you calculate two ranges where $y\_j$ might be ($(x\_j, y\_j)$ is somewhere on the circle around $(x\_i, y\_i)$ with radius 1). Since the points are sorted by $y\_j$ you can access all these points quickly.

You compare each $(x\_i, y\_i)$ with points within a total area of about $2\cdot \pi \cdot d)$, so the smaller d is, the more area you save, but the overhead grows.
> 1 votes

---
Tags: computational-geometry
---


# Question
Title: finding a hemisphere that contains all points of a given set S
Let $S$ be a finite set of points on the unit sphere $\mathbb{S}^2$. My question would be: is there an easy way to either find a great circle $C$ such that all points in $S$ are inside one of the hemispheres defined by $C$ or return that such a great circle does not exist.

This can of course also be seen as a problem in 3D, i.e. does there exist a plane through the origin, such that one of the halfplanes contains all of the points.

The only thing I could think of was like a "perceptron" style algorithm, but I'm not sure, if that algorithm would terminate, if a solution exists and also when to stop if it does not exist.

Does anyone have a "more sophisticated" idea?

# Answer
As suggested by Nathaniel, first find the convex hull of $S$. Now note that there would exist a plane of the convex hull with the *property* that its one side contains all the points in $S$ and the other side contains the origin. Let this plane be $ax + by + cz = d$. Then, the plane passing through the origin would be $ax + by +cz = 0$; it would induce the required halfspace.

You can get the plane $ax + by + cz = d$ by finding the convex hull in $O(n \log n)$ and verifying the property for each plane in $O(n)$ time.
> 1 votes

---
Tags: algorithms, computational-geometry
---


# Question
Title: fpaq0.cpp is supposedly a "0-order" compressor. Why does it use a context then?
In http://mattmahoney.net/dc/dce.html#Section\_32 Matt Mahoney states:

```
The simplest of these is the order 0 coder fpaq0.

```

in http://mattmahoney.net/dc/dce.html#Section\_41 he states:

```
An order 0 model uses no context.

```

but in http://mattmahoney.net/dc/fpaq0.cpp the Predictor (model) is defined with a context:

```
class Predictor {
  int cxt;  // Context: last 0-8 bits with a leading 1
  int ct[512][2];  // 0 and 1 counts in context cxt
public:
  Predictor(): cxt(1) {
    memset(ct, 0, sizeof(ct));
  }

  // Assume a stationary order 0 stream of 9-bit symbols
  int p() const {
    return 4096*(ct[cxt][1]+1)/(ct[cxt][0]+ct[cxt][1]+2);
  }

  void update(int y) {
    if (++ct[cxt][y] > 65534) {
      ct[cxt][0] >>= 1;
      ct[cxt][1] >>= 1;
    }
    if ((cxt+=cxt+y) >= 512)
      cxt=1;
  }
};

```

Why is that?

# Answer
From Matt Mahoney himself in an email:

"It is bytewise order 0, not bitwise. It models byte probabilities independently one bit at a time. The bit probabilities depend on previous bits."
> 1 votes

---
Tags: data-compression, encoding-scheme
---


# Question
Title: Find a perfect matching with weights as close as possible to each other
Given a set of jobs $J$ and a set of machines $M$, where the link between machine $i\in M$ and job $j\in J$ has a positive weight $w\_{ij}$. The problem is to select a perfect matching between the jobs and the machines such that the weights of the matching are as close as possible to each other, i.e., the best solution is where all the weights of the matching are equal.

Can we solve this problem in polynomial-time?

# Answer
> 4 votes
You haven't specified what you mean by "as close as possible to each other", so let me assume that you want to minimize the difference between the minimal weight and the maximal weight.

Denote by $m$ the number of edges. Thus, the graph contains at most $m$ different weights. For each pair of weights $a \< b$, you can use a perfect matching algorithm to determine whether there is a perfect matching involving only the edges whose weights are in the interval $\[a,b\]$. After solving $O(m^2)$ many instances of perfect matching, you can find an interval $\[a,b\]$ supporting a perfect matching and having minimal $b - a$.

There might be smarter algorithms, but this already shows that the problem is solvable in polynomial time.

---
Tags: algorithms, np-hard, polynomial-time, matching, bipartite-matching
---


# Question
Title: A function which is both $o(\log^* n)$ and $\omega(1)$
I've been trying to find a function $T(n)$ whose asymptotic rate of growth satisfies both of the following conditions:

1. $T(n)= o(\log^\*n)$
2. $T(n)= \omega(1)$

But I can't think of a function with this rate of growth.

# Answer
> 3 votes
Take $ T(n) = (\log^\*n)^{1/2}$

# Answer
> 2 votes
If $f(n) = o(g(n))$, then the function $h(n) = \sqrt{f(n) g(n)}$ satisfies $h(n) = o(g(n))$ and $h(n) = \omega(f(n))$.

# Answer
> 2 votes
A notable function that is not upper bounded by any constant but grows slower than $\log^\* n$ is $\alpha(n)$, the inverse of the Ackermann function.

This function appears naturally in the analysis of Union-Find with path compression.

---
Tags: asymptotics
---


# Question
Title: First-order model checking on general graphs is intractable
I read that the first-order model checking problem is intractable on general graphs.

How is this shown? Would be happy about some reference!

Thanks in advance

# Answer
> 0 votes
You can represent classical NP-complete problems as model checking of first-order formulas in the language of graphs, for example subgraph isomorphism, dominating set, clique, vertex cover, and so on.

---
Tags: graphs, model-checking, parameterized-complexity
---


title: Encoding set values in $o(n)$ memory

text:
# Question
Title: Encoding set values in $o(n)$ memory
Apache Spark, a distributed computation framework, has a construct called accumulators which are global variables with an associative addition action. These can be used to aggregate statistics during the computation process. The problem with these variables is that parallel tasks can fail without "rolling back" the value of the accumulator, so at the end of the process if any tasks were re-run, the accumulator will have a larger value than it should have in reality.

In my case I want to count the amount of elements I filter out in my process.

If I simply use an integer/long counter and increment it each time I filter out an element, I will possibly get inaccurate results because of the problem previously described.

An idea I had is to use a set as the accumulator, collecting in it all the unique identifiers of the elements I filtered out, then getting its size at the end of the process. This will produce an accurate result but will have a performance impact of storing a possibly very large list of identifiers in memory.

Thus I am curious if there is any mathematical construct I can use which has the following properties:

1. Occupies $o(n)$ of memory. By that I mean that its size will grow very little a a function of the size of the dataset I am running on.
2. Has an associative "addition" method that recognizes when a value added to it was already added previously
3. Has a "size" method that returns the amount of unique values added to it.

A set satisfies the second and third constraint but not the first, however a set has the property of retrieving its values, which I do not need. Is it maybe possible to achieve all three when this is not needed?

I know this is probably overkill for a programming problem but at this point I am just curious if anything like this exists.

thanks.

# Answer
No such data structure can exist that satisfies (1) and (2): if $n$ arbitrary elements can be added to it, and it has to keep track of whether each of them has been seen already or not, then it has to have at least $2^n$ configurations, and therefore maintain $\Theta(n)$ memory at least (i.e. keeping a single bit for each element it has seen or not).
> 2 votes

# Answer
A possible strategy to check the final value of your accumulator is accurate would probably be to subdivide into multiple smaller accumulators. This way you can separate the tasks into multiple steps.

Checking the value of each step will allow you to be able to confirm the accuracy of your program running in a parallel computed environment. If you are able to check the value of these subdivided tasks is not accurate to the value they are supposed to represent, the system can rerun the task for this particular section before adding back into the total value.

This will ensure the required time to fix the adjusted value \<O(n) and allow to implement security measures to ensure any miscalculated values are checked without having to check every value again in a single step, thereby running the same calculation with equal to the same amount of risk.

If I understand your question correctly, this is a general pseudo approach I may consider. There may be solutions not considered, it depends on the language and environment you are working in.

Parallel computations should be for the most part reliable.
> 0 votes

---
Tags: data-structures
---