# Question
Title: size of intersection of 2 languages size is not decidable
I think that the next language is not decidable but I can't think of reduction to show it. I would appreciate some hint or intuition

$EQ = $ { $\<M1,M2\>$ |$ M1\\,\\,\\, and\\,\\,\\, M2 \\,\\,\\, are\\,\\,\\, TMs\\,\\,\\, and\\,\\,\\, |\\,L(M1)\\,∩\\,L(M2)\\,|\\, $$= 2020\\, $}

# Answer
> 2 votes
Consider an instance of Halting problem $\langle M, x \rangle$. Construct a new Turing Machine which $M\_x$ which will accept the strings $0$, $00$, $000 \ldots 0^{2020}$ if the machine $M$ halts on the input $x$; and it will reject all other strings. Let $M\_u$ be the TM which accepts all the strings.

Convince yourself that $|L(M\_x) \cap L(M\_u)|$ will be 2020 if $M$ halts on $x$, and otherwise $0$.

The proof follows easily.

(Informal) Hint: Whenever you have such a question, try thinking about how can you solve the Halting problem (or some other undecidable language) using the *hypothetical* decider for the given language.

# Answer
> 1 votes
welcome to the site :)

I assume you already know that the Halting problem $L\_H$ is undecidable (as it is usually the first specific undecidable language students learn of). So, let us try and find a reduction $L\_H \leq EQ$.

We want to know whether some given TM $M$ halts given the input word $w$ by transforming the pair $\langle M, w \rangle$ to some $EQ$-instance $f(\langle M, w \rangle) = \langle M\_1, M\_2 \rangle$ such that $\langle M, w \rangle \in L\_H$ if and only if $\langle M\_1, M\_2 \rangle \in EQ$. Let us consider some dummy TM $M\_{2020}$ which just accepts 2020 inputs (any set of 2020 words will do the trick) and modify $M\_{2020}$ such that it only ever accepts if $M$ halts on $w$ to get another TM $M\_{2020}(M, w)$. Since we know $M$ and $w$ when we construct $M\_{2020}(M, w)$, we can implement it to do the following:

1. Read the input and if it is one of the 2020 words accepted by $M\_{2020}$, make note of that (we can use the states to store this).
2. Clear the tape and write $w$ to it.
3. Run $M$ on $w$.
4. If $M$ halts on $w$, accept the original input.

Such a construction can be performed by another TM, this is a bit tedious to show formally but by noting that we can essentially "embed" $M$ in $M\_{2020}(M, w)$ it should be intuitive that this can be done (as $M\_{2020}$ is a *fixed* TM).

Now observe that $M\_{2020}(M, w)$ accepts some input $x \in L(M\_{2020})$ precisely when $M$ halts on $w$, hence we have that $L(M\_{2020}) = L(M\_{2020}(M, w))$ if and only if $\langle M, w \rangle \in L\_H$, otherwise we have $L(M\_{2020}(M, w)) = \emptyset$. It follows that $$ | L(M\_{2020}(M, w)) \cap L(M\_{2020}) | = \begin{cases} 2020, & \text{if $M$ halts on $w$} \\ 0, & \text{otherwise} \end{cases} $$ and thus (denoting $\langle M\_{2020}, M\_{2020}(M, w) \rangle$ as $f(\langle M, w \rangle$) we have $\langle M, w \rangle \in L\_H \Leftrightarrow f(\langle M, w \rangle)$ and therefore a suitable reduction.

An easier way to prove that the language is not decidable is by using Rice's theorem which (roughly speaking) says that properties of functions computed by TMs (we call these *semantic* properties) cannot be decided algorithmically unless they are trivial. If we fix some TM $M\_1$ and consider an arbitrary TM $M$ then asking whether $L(M\_1) \cap L(M)$ has size 2020 is such a semantic property and hence Rice's theorem immediately gives us that $EQ$ is undecidable. The theorem (for me, at least) is basically the formal underpinning of the informal intuition I gave above.

---
Tags: turing-machines, reductions
---


# Question
Title: Max independent set in planar graphs PTAS proof
I've been searching a few hours for a proof to Max independent set in planar graphs beeing in PTAS but I couldn't find anything, I'm searching for one without any reductions and I wonder if anyone here can help me find one.

Thanks in advance.

# Answer
> 0 votes
I haven't got any paper, but looking through my favorite book regarding approximation algorithms i've got something.

It is named: The Design of Approximation Algorithms. You find it free for download (even legal) on https://www.designofapproxalgs.com.

Take a look at page 269 (ff.) especially page 271 should be interesting for you as they describe and proof a PTAS for max independent set in planar graphs.

It might not be "front of the line" research or results but hope it helps.

---
Tags: complexity-theory, approximation, planar-graphs
---


# Question
Title: What is the concept of "encoding" in NP-completeness
Hi I have been reading Ch 34(NP-Completeness) Section 34.1 of CLRS and I am confused why do we need to consider different encodings. Everything is represented as binary at the end so why consider different encodings of the input? Any help is highly appreciated.

# Answer
Everything is in binary in your electronic computer. However:

1. We don't want to have to throw away all of the theory of computation if somebody builds a really fast ternary computer.
2. More importantly, the stuff we wish to compute upon isn't binary. It's strings and graphs and numbers and things like that. So the very first thing you need to do is to encode your string/graph/number into a form that fits into your model of computation. And, since we are forced to encode, we'd better consider whether our encoding is a good one.
> 1 votes

# Answer
We have to use an encoding to map the instance of the problem into binary (or whatever the computer uses as its alphabet), and often it doesn’t matter what encoding you use. For example, we don’t want to worry about binary versus ternary.

More precisely, we don’t want to worry about the difference between any two encoding schemes which are polynomially equivalent. What do I mean by this? Suppose we have a problem $P$, where an instance $I$ of $P$ can be encoded (in binary, say) as either $f\_1(I)$, with length $n\_1(I)$, or $f\_2(I)$, with length $n\_2(I)$. We say that $f\_1$ and $f\_2$ are polynomially equivalent when there are polynomials $p\_1$, $p\_2$ such that, for all instances $I$, $n\_1(I)\leq p\_1(n\_2(I))$ and $n\_2(I)\leq p\_2(n\_1(I))$.

This is often so obvious that we forget the distinction. For example, no programmer seriously considers representing an integer $n$ as a string of length $n$ when any kind of speed is required. But what about sparse polynomials and dense polynomials, for example? To expand on that example, a SAT problem can be considered as a big polynomial, and we’re asking if it has a root over $GF(2)$. But it’s critical that we give that polynomial in some kind of sparse representation. The dense form of the polynomial lists the $2^k$ terms, where the SAT problem has $k$ variables. In that representation, we have to input $2^k$ bits to the machine. If we have to do that, then we can solve this problem, let’s call it DENSE-SAT, in polynomial time, just by exhaustion. We can’t solve the problem any faster, of course, but the huge input changes the meaning of polynomial time so that our previously terrible algorithm looks good in comparison to the input length.

So in general we have to be slightly careful to specify the input format. Not very careful, because it doesn’t matter up to polynomial equivalence, but careful enough.
> 1 votes

---
Tags: np, encoding-scheme
---


# Question
Title: How to determine if given “complex” time complexity is $O(n^2)$?
If a given time complexity, such as these:

1. $(n + \log n) * \sqrt{n+\log n}$
2. $n * (200 + \log^2 n)$
3. $(7+n^3)\log(n^5)$

is not determinable by just looking at it whether is it in class $O(n^2)$ or not, how do I decide? If a time complexity is given, and in it there are more types of expressions (exponential, logarithmic, polinomial, ... ) how do I decide which one determines the $O(n^2)$ or $O(n\log n)$ or ... complexity?

# Answer
Sometimes, you can replace them by $n$. For example, in $F\_1(n) = (n+\log(n))\times \sqrt{n+\log n}$, replace $\log(n)$ by $n$. So, $F\_1(n) \leqslant 2n \sqrt{2n}$ and it means $F\_1(n) = O(n\sqrt{n})$. Also, in multiplication or summation, you can ignore constants (not all the time in power functions). Hence, $F\_2(n) = n \times (200 + \log^2(n)) = \Theta(n \log^2(n))$. Or in $F\_3(n) = (7 + n^3) \log(n^5) = 5 \times (7 + n^3) \log(n) = \Theta(n^3 \log(n))$ (as $\log(n^c) = c \log(n)$).
> 1 votes

---
Tags: algorithms, time-complexity, big-o-notation
---


# Question
Title: What is the maximum number of indices one can create on a table with N columns?
Say, I have a database table with $N$ columns. What is the (theoretical) maximum number of indices I can create on that table? For $N = 1,2,3$ it's easy enough to calculate the answer $(1, 4, 15)$, but is there any formula? Also, is there a "name" for this number?

# Answer
I assume you mean the following: given $N$ columns, there are

* $N$ single columns, giving $N$ different indices
* $N(N-1)/2$ pairs of columns, and 2 ways to combine each pair, giving $N(N-1)$ different indices
* $\frac{N(N-1)(N-2)}{2 \cdot 3}$ triples of columns, and $3 \cdot 2$ ways to combine each triple, giving $N(N-1)(N-2)$ different indices

and so on. This number doesn't have a (well-known) name, but the sequence does have its own OEIS entry:

> Eighteenth- and nineteenth-century combinatorialists call this the number of (nonnull) "variations" of n distinct objects, namely the number of permutations of nonempty subsets of {1,...,n}.

Various formulas are given to compute it, including a recurrence relation $a\_n = n(a\_{n-1} + 1)$ and the rather surprising $a\_n = \lfloor{e \cdot n! - 1}\rfloor$.

One could argue that you can create *more* indices by taking into account that columns can be used in ascending and descending mode. For indices with more than one column, this even has an influence on which records are 'near' each other.
> 4 votes

---
Tags: databases, permutations
---


# Question
Title: Solve the online unweighted 0-1 knapsack problem efficiently
I have $n$ items and a bin of size $B$ units. Each item $j$ consumes $w\_j$ units of $B$ when placed into the knapsack. The item appears one-by-one in an online fashion. Once item $i$ appears, we must either place it into the bin (irrevocably) or ignore it. The objective is to maximize the number of items placed into the bin. (All inputs are positive integers.)

The offline algorithm is easy: place the items in the order $w\_1\leq w\_2\leq\cdots\leq w\_n$ until the bin is full.

How can I solve this problem in an online fashion? My approach is to randomize the choices: once item $j$ appears, place it into the bin with probability $p\_j$ and ignore it otherwise.

# Answer
Well as you already noticed, or at least didn't mention, it is easy to see that there is no deterministic competitive Algorithm for your problem. (Counterexamples only need two items, and you can use the fact that the algorithm is deterministic.)

Your approach taking randomization actually isn't enough as some difficulties cannot be overcome by randomization. But there are a few relaxation models of your problem.

Some of those, and a few details to my answer can be found in the paper by Susanne Albers, Arindam Khan and Leon Ladewig named "Improved Online Algorithms for Knapsack and GAP in the Random Order Mode" (see section 1.1).
> 1 votes

---
Tags: algorithms, online-algorithms
---


title: Why is the hitting set problem in NP

text:
# Question
Title: Why is the hitting set problem in NP
I am citing the definition of the **Hitting Set Problem** from (Gardy & Johnson, 1979):

> **INSTANCE**: Collection $C$ of subsets of a set $S$, a positive integer $K$.
>
> **QUESTION**: Does $S$ contains a *hitting set* for $C$ of size $K$ or less, that is, a subset $S' \subseteq S$ with $|S'| \leq k$ and such that $S'$ contains at least one element from each subset in $C$?

The problem definitions from other sources (none of which elaborates on the size of $C$ in relation to $|S|$):

https://theory.stanford.edu/~virgi/cs267/lecture5.pdf

http://cs.indstate.edu/~arash/algo2lec8.pdf

http://www.et.byu.edu/~jka/521/slides/lecture22.pdf

http://www.cs.toronto.edu/~lalla/373s14/assignments/A3Sol.pdf

http://www.cse.iitd.ernet.in/~amitk/SemI-2015/tut12.pdf

Given a set $S$ with $|S| = n$, a collection $C$ of its subsets can have up to $2^n$ elements (where each element is a subset of $S$).

Given a certificate, $S' \subseteq S$, of the **Hitting Set Problem**, how could we possibly check if $S'$ contains at least one element from each subset in $C$ in polynomial time w.r.t $n$?

# Answer
> 2 votes
You cannot check, in general, whether $S'$ contains at least one element from each subset $C$ in polynomial time w.r.t. $n$.

However, in order to show that the problem is NP it suffices to show that you can check to above condition in polynomial time w.r.t. the instance size, which is in $\Omega( \sum\_{X \in C} |X| + \log n)$.

---
Tags: complexity-theory, time-complexity, np-complete, np, vertex-cover
---


# Question
Title: When does a Monte Carlo algorithm solve a problem?
When can we say that a Monte Carlo algorithm solves a problem?

To quote from Wikipedia on Monte Carlo algorithms

> For instance, the Solovay–Strassen primality test is used to determine whether a given number is a prime number. It always answers true for prime number inputs; for composite inputs, it answers false with probability at least ½ and true with probability less than ½.

What would happen if the Solovay–Strassen Test would answer true for only 1% of composite inputs?

Would we then still say that it solves the problem of testing primality?

Or is there some requirement like that a Monte Carlo algorithm has to answer true for more than half the cases?

# Answer
> 2 votes
In general Monte Carlo is used to solve a wide variety of different types of problems. In this particular case you want to learn if a random variable is the constant 1, or not. The idea is straightforward, sample the random variable multiple times, (each sample independently from previous sample to avoid bias) and check if all results were 1. If at least some of the result was 0, we know for sure the random variable is not constant 1 (in Solovay-Strassen Test context, the number is composite).

It is important to emphasize, since Monte Carlo is a randomized algorithm, that it is said to solve the problem if the probability of returning the wrong answer is below some threshold (a small number we will call $\epsilon$).

What happens if all outcome were 1? There is a chance that it is the constant 1, but also there is a chance we were not lucky and all outcome were 1 when they can also be 0. If the probability of sampling a 1 is $p \< 1$, then after $n$ samples the probability of getting all 1 is $P\_n = p^n$. Note that while $n$ increase $P\_n \rightarrow 0$. We can specify a threshold, let's say $\epsilon = 10^{-10}$, such that if $P\_n \< \epsilon$ (i.e. the probability of having a false positive is less than $\epsilon$) we are ok with that result.

---

Now the answer to your question. $\forall p \< 1, \epsilon \> 0 \space \exists n \space p^n \< \epsilon$. What is this telling you exactly?

Whatever the success probability is, as far as it is less than $1$ (for example $p = 0.99$ or $p=0.01$ or $p=0.5$) and threshold $\epsilon$ there exist an $n$ such that if we run the experiment $n$ times (sample $n$ times the random variable independently) we are going to fail with probability at most $\epsilon$. So Monte Carlo can be applied for non-degenerated values of $p$, just the number $n$ of sample must be adjusted to satisfy the $\epsilon$ threshold requirement.

---
Tags: algorithms, randomized-algorithms, definitions
---


# Question
Title: Method to change value in a key for a min heap
How would you write a method to change the value of a min heap where bool changeKey(int oldKey, int newKey). The keys are unique, no duplicate keys are permitted. If there is a key in the heap with value oldKey, and no existing entry with key newKey, it will change it to newKey, keeping the the heap properties and returning true. If there is no key in the heap with value oldKey, or an existing entry has value newKey, then it will take no action and return false. Also an auxiliary map is used to store the locations of the keys in an array. I know how to write methods for insertion but haven't seen any implementations of this.

# Answer
> 1 votes
1. Find the key's node
2. Change the node's key to the new key
3. Heapify the node
4. Update the mapping in the auxiliary map

This will work in $O(log(n))$ worst case.

If the old key is the new key the node wont move. You can also explicitly check it before searching for the node, if you prefer.

---
Tags: algorithms, data-structures, heaps
---


# Question
Title: on coq: Why is the proof complete after proving only for one induction when we have more than one variable?
So I'm learning coq. And I came across the proof for associativity in addition `forall (a b c : nat)`

Appearntly when we do `induction a.` after `intros a b c.`, it creates 2 subgoals

and afterwards we simply need to show that the two sides in both subgoals are equivalent, and the proof is completed.

So I'm just wondering why we don't need to do `induction b.` and `induction c.` to complete the proof? Why only performing induction on `a` is able to complete the proof?

Or in other words, how come in the function that returns the proof, we just get `b` and `c` for "free"? Constructively don't we need something like a double induction applied twice?

# Answer
> 3 votes
You do not *have* to prove things by induction. For example, you can prove $\forall n : \mathbb{N} \\,.\\, n = n$ *without* induction by applying reflexivity. In your proof, we use induction on $a$, but then *we do not need* to use induction on $b$ and $c$ because we can finish the proof simply using other methods. We *could have* used induction on $b$ and $c$, and you should try to do so, to see how unecessary applications of induction just make your proof longer and less clear.

P.S. This has absolutely nothing to do with constructivity.

---
Tags: proof-techniques, induction, proof-assistants, automated-theorem-proving, coq
---


# Question
Title: Is it correct to say L is RE if I can map reduction from LH to L?
I seem to be not understanding correctly what reductions means for Languages.

for example, Lets say there is a Language called LM.

I want to see if LM is recursive or not, to do that lets say I find a reduction from L-Halting problem to LM.

and I assume that LM is recursive, so I show that then L-Halting problem is also recursive, which of course is false therefore LM is not recursive.

but can I say that LM is RE because I found a way to reduce LH to LM? if not how can I show that LM is RE?

# Answer
Let's clear things a bit, since there are many equivalent/similar definitions that could lead to misunderstandings.

* You can show that a language $L$ **is** recursive by constructing a recursive function $\chi\_L$ (or a Turing machine or any other equivalent computation model) that decides it, i.e. $$\chi\_L (x) = \begin{cases} 1 & \quad ; x \in L \\ 0 & \quad ; \text{otw}. \end{cases}$$ notice that $\chi\_L$ must be defined for all inputs.
* You can show a that language $L$ **is not** recursive, by finding a "Turing reduction" from a non-recursive language to it. This is probably what you mean by reduction, and it is defined as follows:

> We say that a language $A$ is Turing-reducible to a language $B$, written $A \le\_T B$, if we can construct a recursive function (or Turing machine) that decides $A$ by assumption that there is such function for $B$.

As you see by definition, Turing reduction somehow "transfers recursiveness" from $B$ to $A$.

> For any $A$ and $B$ such that $A \leq\_T B$, if $B$ is recursive, then so is $A$.

Hence if we already know that some $A$ is not recursive, then finding a reduction $A \leq\_T B$ for any $B$ makes it non-recursive too.
* You can show that a language $L$ **is** RE, by constructiong a recursive function $\varphi\_L$ (or Turing machine) that $Dom(\varphi\_L) = L$ (or halts on/accepts it), for example $$\varphi\_L(x) = \begin{cases} 1 & \quad ; x \in L \\ \uparrow & \quad ; \text{otw.} \end{cases}$$

where $\uparrow$ means "not defined" (or "does not halt"). There are other definitions of RE-ness, like its namesake "enumerability", which you can easily observe that are equivalent to this one.
* But in showing a language $L$ **is not** RE, Turing reduction does not help, since it does not necessarily transfer RE-ness. For example observe that $\overline{L\_{HALT}} \leq\_T L\_{HALT}$ (Indeed, any language is Turing-reducible to it's complement and vice versa), but we know that $L\_{HALT}$ is RE, while $\overline{L\_{HALT}}$ is not.

But there are other kinds of *stronger* reduction that do transfer RE-ness. One such reduction is called "many-one redicibility":

> We say that a language $A$ is many-one-reducible to a language $B$, written $A \leq\_m B$, if there is a total recursive function $f$ such that for any input $x$ $$x \in A \iff f(x) \in B$$

This is a *stronger* reduction in the sense that $A \leq\_m B$ implies $A \leq\_T B$ (and not necessarily vice versa). So, like Turing reduction, it transfers recursiveness. Furthermore, it also transfers RE-ness.

> For any $A$ and $B$ such that $A \leq\_m B$, if $B$ is RE, then so is $A$.

To see how this is true, just take $\varphi\_A(x) = \varphi\_B(f(x))$.

Hence the correct method to show a language $B$ is not RE, is to find a many-one reduction $A \leq\_m B$ for some non-RE language $A$. Notice that the above example does not work here, because $\overline{L\_{HALT}} \nleq\_m L\_{HALT}$.

For further reading, see *Computability Theory* by *S. Barry Cooper* Pt. I, Ch. 7.
> 0 votes

---
Tags: computability
---


# Question
Title: Does a megabyte represent (2^8)^1000000 bits in base2? Isn't that more than enough combinations to represent everything?
Every introductory CompSci resource I can find goes through how 8 bits are in a byte, etc. So a byte can store some 2^8 values in binary. Then when asking about four bytes, we can assume this is (2^8)^4=2^32.

But I can't find anywhere if this pattern holds up until the total amount of hard drive or memory storage. For instance, if even a single megabyte can really hold (2^8)^1000000 bits, isn't this a number so large that it could store all data in existence everywhere in the universe many times over? The number of possible combinations from a number that large would surely never be reached. Yet in reality, we all know a megabyte isn't much.

I can't help but feel somewhere that the exponentiation must stop, and we instead multiply bytes together. Or is it really the case the numbers can get this big? Such as a gigabyte representing ((2^8)^1000)^3 bits?

If I can represent a number, let's say, 1 million in 32 bits, and I wanted to store 10^50 numbers this large, wouldn't the required bits be 2^32\*10^50? First of all, I'd never need to store 10^50 of any unit of data on my hard drive, that's astronomically massive, and secondly, 2^32\*10^50 is quite a small number, far below (2^8)^1000000. So what's really happening here that we need so much storage, and a megabyte isn't much?

# Answer
> 3 votes
A megabyte represents $8\cdot10^6$ bits. We can write $2^{8\cdot10^6}$ bit-strings using this much memory. But, this number is **not** the same as how many such bit-string we can store! Well, we can only store a **singl**e bit-string of size $8\cdot10^6$ bits in $1$ megabyte.

To understand this better: consider a single page of a document. On a single-spaced page with 12 point font, we can put around 3000 characters. The number of possible pages that can be written in English on this single page of the document would be $26^{3000}$. But, how many characters can we actually write on such a page? quite simply 3000.

---
Tags: binary
---


# Question
Title: "State of the art" algorithms deciding entailment of propositional formulas?
I fail to find much about how to efficiently calculate whether a propositional formula entails another.

Considering the following two points...

1. We can check, for each truth assignment which makes the first formula true, whether it also makes the second true. If all of them do, the first entails the second. It works for disjunctive normal forms, conjunctive normal forms, ... anything really. But this can be prohibitively expensive for large numbers of propositions.
2. If we translate both formulas to disjunctive normal form we can more efficiently check for entailment, but we need to do the transformation to DNF first.

... what are the best algorithms to check entailment?

I was under the impression that this must be a problem that's long been solved, but where are the papers that deal with entailment of arbitrary propositional formulas? How do I calculate a yes/no answer without using DNFs?

# Answer
Checking whether $P \Rightarrow Q$ is the same as checking that $P \land \lnot Q$ is unsatisfiable. Using the Tseytin transformation, you can convert $P \land \lnot Q$ into a form suitable for a SAT solver.

Conversely, satisfiability is a special case of your problem, since $P \Rightarrow \bot$ iff $P$ is unsatisfiable.
> 1 votes

---
Tags: algorithms, propositional-logic
---


# Question
Title: Show that f(x,y)=x+y (with |x|=|y|) isn't a one way function
I have to prove that the function $f\colon \mathbb N × \mathbb N \to \mathbb N$ defined by $f(x, y) = x + y$ and $|x| = |y|$ isn't a one-way function. How do I go around doing that?

# Answer
> 1 votes
A function $f$ is one-way if given $f(z)$ for random $z$, it is hard to find an input $w$ such that $f(w) = f(z)$. So in order to show that $f$ isn't one way, you need to show that given $f(z)$ for random $z$, it is not hard to find an input $w$ such that $f(w) = f(z)$. Good luck!

---
Tags: complexity-theory, proof-techniques, mathematical-analysis, one-way-functions
---


# Question
Title: How to decide whether a real life problem can be dealt with by computers?
I get that complexity theory will be helpful to decide whether the resources at hand can deal with a mathematical function, but when presented with a non-purely mathematical problem - like building a robot that can cook, drive or make beds - how can we know whether it's feasible?

# Answer
The way we decide is we try to solve it and see if we are successful; or we look to see whether someone else has solved it (e.g., in the research literature).

Usually the question doesn't really make sense, as it is not well-defined what it means to "solve" or "deal with" a problem. It's not like in mathematics, where it is a crisp black-and-white. Instead, one may need to measure how well computer systems can address the problem, in what contexts they do or don't suffice, what their strengths and limitations may be, and so on.

Normally, the way we assess all of this is through experiments, not mathematics: we try techniques and evaluate how well they work empirically, and see what we can learn from that.
> 1 votes

# Answer
There are already robots (i.e. automated machines) that can cook - every factory in the food processing industry uses a production line to turn raw materials into its finished products. These machines are complex and expensive and only economically viable for large scale food production.

If by "cook" you mean "prepare a healthy and nutritious meal using fresh ingredients available in my kitchen that is not the same as any other meal we have had in the previous week" then that is a much more complex scenario, and is unlikely to be automated in the near future.

Similarly, there are already test vehicles which can drive themselves in a wide variety of situations, so this problem has effectively been solved at a technical level. Cruise control and semi-automated parking are already options for some standard cars, and we are likely to see more and more automation of everyday driving over the next ten to twenty years.

"Making beds" as a daily task has (in my part of the world) largely been superseded by the use of duvets. I only have to "make my bed" when I change the sheets and duvet cover, and the effort involved in that is hardly worth automating. In situations such as hospitals and hotels where beds have to be made and re-made frequently, the solution has been to change bed and mattress design to make the task simpler.

As you say, formal complexity theory has little or nothing to say about these problems, which have technological solutions constrained by market economics rather than computing power.
> 0 votes

---
Tags: robotics
---


# Question
Title: Is the BPP class closed for union and intersection?
Just like the title says. I want to prove that given two languages $L\_1,L\_2 \in BPP$, $L\_1 \cup L\_2 \in BPP$ and $L\_1 \cap L\_2 \in BPP$

# Answer
Let $T\_1$ (resp. $T\_2$) a polynomial-time probabilistic Turing machine with error probability of at most $1/3$ for $L\_1$ (resp. $L\_2$).

Let $T'\_1$ (resp. $T'\_2$) be a Turing machine for $L\_1$ (resp. $L\_2$) obtained by running $T\_1$ (resp. $T\_2$) $9$ times and returning the majority result. The error probability of $T'\_1$ (resp. $T'\_2$) is at most $p\_F = \sum\_{i=5}^9 \binom{9}{i} (1/3)^i (2/3)^{9-i} \< \frac{1}{6}$.

A Turing machine for $L\_1 \cup L\_2$ (resp. $L\_1 \cap L\_2$) simulates $T'\_1$ and $T'\_2$ and accepts if and only if at least one of (resp. both of) $T'\_1$ and $T'\_2$ accept. By the union bound, the probability of error of this Turing machine is at most $2 \cdot p\_F \< 2 \cdot \frac{1}{6} = \frac{1}{3}$.
> 3 votes

---
Tags: complexity-theory, proof-techniques, complexity-classes, randomness
---


title: Proof that if P=PSPACE, RP=BPP

text:
# Question
Title: Proof that if P=PSPACE, RP=BPP
Like the title says. I can't figure out how to prove this.

I think it probably has to do with the polynomial hierarchy collapsing but I'm not sure.

# Answer
> 3 votes
$P \subseteq RP $, $BPP \subseteq PSPACE $.

So $PSPACE \subseteq P $, $--\>$ $BPP \subseteq RP $.

---
Tags: complexity-theory, proof-techniques, complexity-classes, probability-theory
---


title: Online shortest path in ordered DAG

text:
# Question
Title: Online shortest path in ordered DAG
Suppose I have an edge-weighted connected rooted DAG $G = (V, E, r \in V, w \in E \to \mathbb{Z})$ where there exists a sequence of nonempty sets (called "levels") $L\_0 = \\{r\\}, L\_1 \subset V, \ldots, L\_n \subset V$ such that $L\_0 \cup \ldots \cup L\_n = V$ and the outgoing edges of the nodes in $L\_i$ only connect to nodes in $L\_{i + 1}$.

Is there an online algorithm that can maintain a set of shortest paths as more levels are added to this DAG? In other words, it can answer the query "what is the minimum weight path from the root to some node $n$ in the bottom level of the graph?", even as more levels are added.

I couldn't find any research addressing this question.

# Answer
If I understand your problem correctly then you probably didn't find any research because the problem is easy to solve.

Unless I missed something, you want to maintain an edge-weighted "layered" DAG $G=(L\_0, \cup \dots \cup L\_k, E)$ (as defined in your question) and support the following two operations:

* Init(): Create a graph with only one layer $L\_0$, a single vertex $r \in L\_0$, and no edges.
* Query(): return $\min\_{v \in L\_k } d(r,v)$.
* Add\_Layer($L\_{k+1}, E'$): you are given a new set $L\_{k+1}$ of vertices and a set of weighted edges $E' \subseteq(L\_k \times L\_{k+1})$. The vertex set of $G$ is updated to $L\_0 \cup \ldots \cup L\_k \cup L\_{k+1}$ and the edge set of $G$ is updated to $E \cup E'$.

You can do the above by storing: 1) for each vertex $v \in L\_k$, the distance $D\[v\]$ form $s$ to $v$ in $G$, and 2) the minimum distance $d^\*$ from $s$ to a vertex of the last level.

The init operation amounts to setting $D\[r\]=0$. To perform the query operation just return $d^\*$.

To implement Add\_Layer($L\_{k+1}, E'$), you proceed as follows:

* Set $d^\*$ to $+\infty$,
* For each vertex $v \in L\_{k+1}$:
    + Set $D\[v\] = +\infty$
    + For each edge $(u,v)$ in $E'$:
        - Update $D\[v\]$ to $\min\\{D\[v\], D\[u\] + w(u,v) \\}$
    + Update $d^\*$ to $\min\\{d^\*, D\[v\]\\}$

Notice that this requires time proportional to $|L\_{k+1}| + |E'|$, and is therefore asymptotically optimal. Notice also that this solution does not need to store $G$.
> 4 votes

# Answer
Suppose you have the length of the shortest paths from the root to all the nodes in level $L\_i$, and call this $s \in L\_i \to \mathbb{Z}$. Now suppose that the edges from $L\_i$ to $L\_{i + 1}$ are called $E\_i$. Then the length of the shortest path to a node $n$ in $L\_{i + 1}$ is defined by $\min \\{w(x, n) + s(x) \mid (x, n) \in E\_i\\}$. Maintaining the actual paths is an easy extension.
> 1 votes

---
Tags: graphs, shortest-path, online-algorithms
---


# Question
Title: What is and amplification factor in pseudo-random generators?
I can't seem to find an answer to this. For instance, I have this question:

Show that, if $P=NP$, there aren't any pseudo-random generators (even with amplification factor $n+1$).

My gut tells me this is because, in a world where $P=NP$, pretty much any process can be efficiently inverted so there aren't one-way functions (which pseudo-random generators rely on).

# Answer
Amplification is equivalent to "stretch", the number of (seemingly) random bits that your algorithm generates given the truly random seed.

Let $G:\\{0,1\\}^\*\rightarrow\\{0,1\\}^\*$ be a PRG that maps strings of length $n$ to strings of length $l(n)$, then $l(n)$ is said to be the stretch function of $G$. If $l(n)\>n$ and $l$ is injective, then you have $\forall n :|Im(G)\cap\\{0,1\\}^n|\le 2^{n-1}$. You can use this to construct a language $L\in NP$, such that $L\in P$ allows you to break $G$ (construct a distinguisher with success probability $\ge\frac{1}{2})$. Note that you can relax the injectivity requirement by ignoring some of the output (i.e. given a PRG with stretch $l(n)\>n$, you can construct a PRG with stretch $l'(n)=n+1$).
> 3 votes

---
Tags: complexity-theory, complexity-classes, p-vs-np, pseudo-random-generators, one-way-functions
---


# Question
Title: What would be the complexity for this relation?
The function:

```
    for (int i=1; i<n²; i++)
        for (int j=i; j<n; j++)
            print(j)

```

Putting it into a relation, I got:

$C1 + \sum\_{i=1}^{n^2}(C2+\sum\_{j=i}^n(C3))$

After solving it

$C1+C2n^2+C3n^3-(C3\frac{n^4}2 + C3\frac{n^2}2)+C3n^2$

What I can't figure out is the complexity of this relation.

Solution (from the answer to this post):

$C1 + \sum\_{i=1}^{n^2}C2+\sum\_{i=1}^n\sum\_{j=i}^nC3$

$C1 + C2\sum\_{i=1}^{n^2}1+\sum\_{i=1}^nC3\sum\_{j=i}^n1$

$C1 + C2(n^2-1+1)+\sum\_{i=1}^nC3(n-i+1)$

$C1 + C2n^2+\sum\_{i=1}^nC3n - \sum\_{i=1}^nC3i + \sum\_{i=1}^nC3$

$C1 + C2n^2+C3n\sum\_{i=1}^n1 - C3\sum\_{i=1}^ni + C3\sum\_{i=1}^n1$

$C1 + C2n^2+C3n(n-1+1) - C3(\frac{n(n+1)}2) + C3(n-1+1)$

$C1 + C2n^2+C3n^2 - C3(\frac{n^2+n}2) + C3n = O(n^2)$

# Answer
Trace what happens with your code rather than simply plugging the limits into the summation formulas. The inner loop won't actually be performed $n^2$ times, since its limit will be reached as soon as $i=n$ in the outer loop.

In other words, your timing function should be $$C\_1+\sum\_{i=1}^{n^2}C\_2+\sum\_{i=1}^n\sum\_{j=i}^nC\_3=O(n^2)$$
> 1 votes

# Answer
How did you get this factor: $-(C\_3 n⁴/2 + C\_3 n²/2) + C\_3n²$ ?

Considering the formula you showed shouldn't it be something like this:

$C\_1 + \sum\_{i=1}^{n^2}( C\_2 + \sum\_{j=1}^{n}(C\_3)) = C\_1 + n^2\*(C\_2 + n\*C\_3) = n^3\*C\_3 + n^2 * C\_2 + C\_1$ ? (And with it being in $O(n^3)$)

Edit: I mistook that $i$ in $j=i$ for a $1$. In that case I don't see how that function fits in any $O$ class. The dominating factor ($n^4$) is negative and $O$ is supposed to be an approximation of the number of operations an algorithm performs related to its domain size. With that said, for a large enough $n$, your function becomes negative.
> 1 votes

---
Tags: algorithms, algorithm-analysis, summation
---


# Question
Title: Is UTF-8 the final character encoding for all future time?
It *seems* to me that Unicode is the "final" character encoding. I cannot imagine anything else replacing it at this point. I'm frankly confused about why UTF-16 and UTF-32 etc. exist at all, not to mention all the non-Unicode character encodings (unless for legacy purposes).

In my system, I've hardcoded UTF-8 as the one and only supported character encoding for my database, my source code files, and any data I create or import to my system. My system internally works solely in UTF-8. I cannot imagine ever needing to change this, for any reason.

Is there a reason I should expect this to change at some point? Will UTF-8 ever become "obsolete" and replaced by "UniversalCode-128" or something, which also includes the alphabets of later discovered nearby galaxies' civilizations?

# Answer
> 35 votes
**UTF-8 might not last forever, but you probably don't have to worry too much.**

Two universal truths:

* We can't predict the future.
* Nothing lasts forever, especially in software.

But that doesn't mean the benefit of (trying to) future-proof your code always outweighs the cost.

**Is UTF-8 likely to become obsolete any time soon?**

I would say no. UTF-8 is quite common, which makes it harder to replace. Unicode also still has quite a bit of empty space, meaning there isn't likely to be a pressing need to replace it soon. Between 2010 and 2020, less than 40k characters have been added. It will take about 240 years to use up the remaining ~1 million unallocated characters if we assume we keep going at the same rate. This is a lot faster than I imagined, but still quite a while away and assuming it will keep going at the same rate is quite an assumption.

It also doesn't seem like there'd be a need to replace it due to a fundamental flaw in the encoding. With other types of standards or technologies there may be some security issue that could be exploited, but this doesn't seem likely with character encodings that only tells you how characters are stored.

I speculate if a need to replace it arises, it would be due to inefficiencies or constraints in new technology. Someone could develop some new piece of technology that rethinks how data is stored or loaded, which might make UTF-8 less than ideal or unusable. But there would still be plenty of systems without that technology for quite a few years.

Note that I didn't ask "are we likely to see a new character encoding any time soon". Anyone can create a new standard, but that doesn't mean it will be widely adopted nor replace other standards.

**How bad would it be for you if there's a new standard?**

Probably not that bad.

Even if there is a new standard that's widely adopted, your system will likely keep functioning for the foreseeable future with little to no changes. There are a lot of legacy systems out there.

If your system doesn't support the new encoding, you may have some issues with the user or other systems trying to send you data you don't support. But your system could still use UTF-8 internally, even if this means you don't support some characters (which might not be *good*, but it won't necessarily break your system).

Also, if it were to be replaced due to a reason other than running out of space (which, as noted above, doesn't seem likely any time soon), UTF-8 could likely be extended to include any characters in the new encoding. Meaning you can just convert from one encoding to the other where required and UTF-8 would still be usable.

**Unicode versus Unicode?**

The difference between UTF-8, UTF-16 and UTF-32 seems minor when compared to other (non-Unicode) encodings. They all support the same characters, so it shouldn't be a huge issue if one replaces the other.

If another one of those were to become the widely adopted one, it would probably be trivial to convert between them where required and continue to use UTF-8 everywhere else.

# Answer
> 19 votes
When it comes to software, the future always means needing to handle more data--- bigger files, and more of them in a shorter period of time. How does UTF-8 processing scale in those situations?

UTF-8 uses a variable number of bytes per character. This saves a lot of space if your text is ASCII plus the occasional emoji or accented letter. But a drawback of variable-length encoding is that jumping to an arbitrary position scales linearly with the size of the document. A fixed width encoding like UTF-32 would use more space but jumping to a position in the document is constant time. Depending on the size of the document and speed of the medium you're reading it from, linear time seeking vs. constant time seeking could make a huge difference in the performance of your application. It is better to be able to tradeoff space for time or the reverse as the situation demands.

# Answer
> 10 votes
UTF-8 might not last forever, but if you permit long UTF-8 again, it will outlast all other encodings that exist today. I have heard it projected that we will eventually run out of UTF-16 codepoints, necessitating the abandoning of UTF-16. We can go all the way to 0x7FFFFFFF.

Table from Wikipeida:

```
1   U+0000     U+007F     0xxxxxxx
2   U+0080     U+07FF     110xxxxx  10xxxxxx
3   U+0800     U+FFFF     1110xxxx  10xxxxxx  10xxxxxx
4   U+10000    U+1FFFFF   11110xxx  10xxxxxx  10xxxxxx  10xxxxxx
5   U+200000   U+3FFFFFF  111110xx  10xxxxxx  10xxxxxx  10xxxxxx  10xxxxxx
6   U+4000000  U+7FFFFFFF 1111110x  10xxxxxx  10xxxxxx  10xxxxxx  10xxxxxx  10xxxxxx

```

There's some debate how to extend this should it ever arise Do we go 1111111x for 0x7FFFFFFF to 0xFFFFFFFF and say larger code points cannot occur, or we do 11111110 beginning a 7 byte sequence for 36 bits of codepoint and permitting 11111111 for 8 byte sequence.

Editorial: I do not mind the fact this answer is mildly controversial. The whole answer is about the fact that UTF-8 and UTF-32 are more future-proofed than any other well-known encodings.

# Answer
> 9 votes
UTF-8 is an elegant hack to remain backward compatible with ASCII and trivially compatible with Latin-1, which were both widely entrenched when Unicode started to take hold. UTF-8 can be extended further and still remain backward compatible with itself, by adding 5- and 6-byte encodings. So if Unicode decides it needs a few more bits to represent its character repertoire, there will be some hitches to make sure you programs get updated, but your existing data should be just fine. (Just as UTF-16 is backward compatible with UCS-2.) UTF-8 is deeply entrenched, so if it ever becomes obsolete, the new encoding system will almost certainly be backward compatible with UTF-8. Your existing data won't need to be converted, just as your ASCII documents are still perfectly good today.

How could UTF-8 become obsolete? It seems like Unicode has so much room for expansion that running out is almost unimaginable. On the other hand...

* Unicode did run out of space once before, when it was a 16-bit system. I believe the limits of 16-bit was an impetus for the Han Unification, which combined substantially similar characters among several Pacific Asian languages.
* Our idea of text being a serial stream of code points could evolve to the point that the Unicode approach isn't sufficient or scalable. Current best practice is to split content from styling almost completely. But it's hard to get that separation right (see CSS and evolving markup languages). It's not too hard to imagine at least some styling creeping back into the textual representation. Depending how that's done, it could have a massive multiplicative effect on the scale of Unicode.

In fact, some of this has already happened. The Han Unification largely works, but to render a multi-lingual document properly, you need to know which spans of CJK symbols are Chinese, Japanese, or Korean. Because while the general shape of the unified symbols are the same and the concepts they represent align, they generally should be drawn with language-specific fonts. If you have just the text and not the styling, it's impossible for a machine to know which strings are from which language. So Unicode has a way to add language tags to get it right (just like you need some special characters to handle some Bidi edge cases). This is arguably styling (or, at least, mark-up) embedded directly in the text. And they're not widely supported.
* Emoji. I was surprised that Unicode adopted emoji (beyond a handful to preserve legacy documents). In my mind, it doesn't seem to fit what Unicode set out to do, but the consortium's membership includes smart phone makers. There are many emoji, and the number is growing at quick pace. Combining characters are used to style your smiley by setting the character's gender, hair color, skin tone, occupation, etc. Emoji are becoming a generative script.
* Icons. Now that we have a wider range of device resolutions and some extensions to font technology (thanks to emoji), software is turning to fonts for clean resolution-independent icon rendering. Unicode has recognized a couple hundred wing dings, so why not icons? If they can be assigned a semantic meaning (e.g., "SAVE ICON") instead of a descriptive name (e.g., "FLOPPY DISC ICON"), all the better. And if they start to fold in some styling information (e.g., "SAVE ICON", "DISABLED SAVE ICON", "PRESSED SAVE ICON", ...) we could see a massive number of these becoming standardized.
* Private use. Currently, private use areas are used for icons (as above), for corporate logos, and sometimes even for original names (which I've heard is or was a trending in Japan). Documents with private use code points have semantic gaps and are inherently tied to styling information (custom fonts). I wouldn't be surprised if Unicode doesn't eventually start to allocate dedicated code points to corporate logos, and/or we'll see styling slither into our text documents.
* Aliens. This won't happen for a long time, but it's easy to imagine alien languages being written in ways that cannot be represented as a linear stream of code points. What if the alien's script cannot be divorced from styling information? What if they have a generative writing system that cannot be reproduced with finite sets of glyphs, combining marks, and shaping rules?

# Answer
> 7 votes
Your question appears to slightly conflate two related concepts (as people often do):

1. **Unicode** is a standard, whose primary part is a "coded character set" - a list of "code points", and a lot of metadata around them, attempting to catalogue all the world's writing systems. It has a defined "code space" of the numbers 0 to 10FFFF (hexadecimal) inclusive (most of which has not yet been filled with actual defined code points).
2. UTF-8, UTF-16, and various other "encoding schemes" are **ways of storing and transmitting Unicode code points**. They can all represent all the code points, present and future, that the Unicode code space can theoretically hold.

When you talk about "something which also includes the alphabets of later discovered nearby galaxies' civilizations", you are implicitly talking about **superseding or extending the Unicode character set itself**.

If your system can "only" represent the code points of Unicode as we know it today (regardless of *how* it represents them), it would need to be upgraded *if you needed to store these extra alphabets*. It's impossible to say what this would involve; the new system might be cleverly designed to allow easy upgrades, or it might be that we adopt a system from Alpha Centauri, and all Unicode text needs carefully re-processing into their system. At that point, whether you picked UTF-8 or UTF-EBCDIC to store your Unicode would feel like an irrelevant detail.

If Unicode is *not* superseded or extended, any system capable of storing all Unicode code points will remain capable of storing them. So the theoretical limitations of UTF-8 in particular are not to do with *what it can store*, but **how convenient it is to work with**.

Currently, UTF-8 is the most popular encoding scheme, for various reasons - it has backwards-compatibility with ASCII, is compact when storing text containing mostly Latin characters, and works in multiples of 8 bits. Consequently, there are many tools for working with it - the virtuous cycle of standardisation. However, a new encoding scheme might become popular due to changes in common requirements - for instance, given an extremely "wide" memory, you could allocate a fixed width for each grapheme (i.e. even wider than the 32 bits required to fix the width of each code point).

If that happened, we *can* see what the upgrade would look like - you would need to convert your UTF-8 text to and from this encoding scheme in order to use tools built for it, which might be slow. But if you were still representing Unicode code points, such a transform is guaranteed to be possible without losing any data in either direction.

# Answer
> 5 votes
> I'm frankly confused about why UTF-16 and UTF-32 etc. exist at all

UTF-16 exists because Unicode was originally supposed to be a fixed-width 16-bit encoding and many systems were designed during this era and needed to be retrofitted to support more characters. These aren't some niche systems or systems that are on their way out, they are major current techologies like windows, .net, Java and QT.

UTF-32 exists because some people think it's easier if each code point is stored in a fixed-size unit. IMO this is largely illusory as there is not a 1:1 mapping between unicode code points and what users would call characters (for example most users would say that "Spın̈al Tap" has 10 characters but it requires 11 unicode codepoints to represent) but it nevertheless exists as a perceived advantage.

I don't think either of these encodings is going to go away any time soon. So if your system interacts widely with other stuff you are likely to end up dealing with other unicode encodings sooner or later.

> Will UTF-8 ever become "obsolete" and replaced by "UniversalCode-128" or something, which also includes the alphabets of later discovered nearby galaxies' civilizations?

If we ever establish meaningful contact with intelligent alien life then some decisions would need to be made as to how to represent their languages on our computers and vice-versa. That could eventually mean switching away from computing standards as we know them today to a new set of interplanetary standards.

I think realistically though it's incredibly unlikely that will happen. IMO even if alien-life exists and even if we discover it, it would be impractical to establish meaningful communications without faster than light communications and/or travel and that would mean breaking physics as we know it.

Assuming we don't establish contact with aliens and assuming that we keep using computers that resemble those we use today, it seems unlikely that our text representation systems will be radically changed, it's possible that at some point the codepoint space will be expanded, but I think it's more likely that greater use will be made of combining characters, variant selectors etc to allow new languages to be represented with fewer code-point allocations.

# Answer
> 2 votes
There is a theoretical possibility that over a million code points might not be enough. This is made less likely by the fact that characters can be made from more than one code point, so we could easily reserve one of the 17 pages for "intergalactic languages", where the first code point specifies one of 65,000 languages and the second code point a character in the language.

We *might* extend UTF-8 to 5 byte characters, but that would break lots of current code that correctly expects 4 byte only.

Why more than 65536 code points? It turned out to be not enough, once more and more languages were added, and Chinese / Japanese characters gettng more complete. Using multiple codepoints to extend the character set as I suggested would be a desparate measure, and even a few non-terrestrial civilisations would likely not require it. Doing this without need would be very wrong. There are emojis consisting of many codepoints, but there is a good reason for that.

# Answer
> 1 votes
**1. Unicode is *the* standard in all fields**

Unicode is the unwreckable standard, and *multi-byte* UTF-8 with its ASCII subset for most purposes, like HTML, the most compact, even for Asian script when mingled with plain Latin script.

*Two-byte* UTF-16 has the fixed size advantage: taking the nth 256 bytes from a file form 128 UTF-8 chars. Whereas UTF-8 could have a have a half multi-byte sequence at the block limits. However UTF-16 is a historical error, as Unicode grew out the 16 bit range, and now for many Unicode *code points*, symbols, need two UTF-16 chars. So its fixed-size advantage is moot.

UTF-32, four bytes per code point, is natural, though Unicode is still in the 3 byte range, and will be for some time. So it is guaranteed to at least waste ¼, and even ¾ for plain Latin script.

UTF-8, UTF-16, UTF-32 do not really compete. In the programming language Java char is UTF-16, String literals are stored in the .class as UTF-8. The latest java versions even allow String, text in Unicode, to store *solely internally* the text in say ISO-8859-1.

*UTF-8 will be the main Unicode Transformation Format for text files.*

**2. Unicode has flaws**

Unicode might be the Esperanto of encodings (like with clever features), but that does not come without flaws. The main one is that there are different code point sequences for the principly the same text; there is no **canonical** form of Unicode. So `é` can be one single code point, or two: `e` and a zero-width `´`. Again Java offers conversion in `java.text.Normalizer`.

Another (minor) flaw under Windows, one can determine when a file content is not in UTF-8, but without reading the content that is not feasible, if the encoding is apriori unknown. But that would hold for any other universal encoding too.

Flaws will not imply a future demise of Unicode. However not without glitches. There might come a time when a canonical form of Unicode becomes obligatory; needing a conversion of existing UTF-8 to say UTF-8C.

**3. Chaotic Changes Possible**

* An "UTF-24" could be more politically correct, as with UTF-8 Asian scripts have a serious disadvantage.
* A redesign of Unicode itself seems academically interesting, and could find its proponents, people favoring something new.

This is counter-balanced by the numerous UTF-8 data: XML in general, jason, general Linux encoding in UTF-8, Windows multiple single-byte encodings (which make UTF-8/UTF-16 the lingua-franca for portable text in many applications).

**Conclusion**

There is no reason to fear a demise of UTF-8.

I was one of the earlier adapters of UTF-8 in programming. And now keep my projects in UTF-8.

# Answer
> 1 votes
UTF-8 is an elegant way to encode a large range of numbers with a variable number of 8-bit bytes. As long as we don't need more characters than it can represent (unlikely unless the people of year 3000 write entirely with emojis that don't exist yet), there really isn't much reason to switch to another encoding. There is far too much momentum in English-centric computing to warrant an encoding that prioritizes other languages...

...That is, unless we encounter intelligent life and start having to integrate our information systems with theirs. All bets are off at this point. There's no guarantee they chose 8-bit clusters as their primary computing data unit. There's also no guarantee they're using binary or electricity as their primary means of computing. But even if they also used 8-bit bytes with 1 mapped to high voltage and 0 mapped to low, the probability that they created the exact same symbols and corresponding bit-encoding is so unlikely that calling it *astronomically unlikely* wouldn't cut it.

At that point, there will inevitably be a long negotiation process to develop standard codepoints, hopefully with some ability to bring in more intelligent species' languages later. During this time, there will be dozens of competing standards and the growing pains of changing encodings like those that characterized the 90s and early 00s. After a couple decades, humans and aliens will have it figured out and produce a standard that encodes both species' symbols without undue preferential treatment. A decade or two later, most new software will use that encoding.

Maybe then, we'll finally get rid of the wealth of obsolete ASCII control codes and reassign uppercase letters to higher codepoints in order to make room for alien letters.

Even still, there's always a chance that UTF-8 will still work as a multibyte encoding after the addition of an alien race or two. The main difference is that it won't correspond to the same Unicode assignments. We could also potentially keep our own encodings and then have translation layers between them. Anything can happen with aliens.

---
Tags: encoding-scheme
---


# Question
Title: Algorithm to get the number of iterations needed, if possible, to get an specific 2 element array
I am fairly new to algorithms and I am dealing with a problem I cannot fully translate into mathematical language.

So, I am given the array \[1,1\] and I can only perform one sum between their numbers per step, ie you can only pick between:

```
[x(s+1), y(s+1)]=[x(s)+y(s),y(s)]

```

or

```
[x(s+1),y(s+1)]=[x(s), x(s)+y(s)]

```

but not both at the same time

Thus,

```
0: [1,1]
1: [2,1],                      [1,2]
2: [3,1],        [2,3],        [3,2],        [1,3]
3: [4,1], [3,4], [5,3], [2,5], [5,2], [3,5], [4,3], [1,4]
...and so on.

```

The goal is to know how many steps are needed in order to get a given \[x,y\] array.

This far, I know that

```
if (min(x,y)==1) --> steps =max(x,y)-1

if (x%2 ==0 and y%2==0) (both even) --> steps= not possible
if (max(x,y)%min(x,y) == 0) (one is multiple of the other or x,y are the same ) --> steps= not possible
if (x%3 ==0 and y%3==0) (both divisble by 3) --> steps= not possible

```

Also I plotted for each pair (x,y) how many steps are needed, and I can see a pattern happening for every multiple of x or y, but I can't write it as a mathematical function when x or y is \>= 5.

Any guidance will be much appreciated.

# Answer
> 2 votes
You have observed several impossible situations for $x$ and $y$, such as when $x$ and $y$ are both even or multiples of $3$, etc. More generally, we have the following characterization. For all positive integer $x$ and $y$,

$$(x,y)\text{ is reachable} \iff \gcd(x,y)=1$$ where $\gcd(x,y)$ is the greatest common divisor of $x$ and $y$. That characterization can be proved easily by mathematical induction on $n=x+y$, since $$\gcd(x,y)=\gcd(x, x+y)=\gcd(x+y,y).$$

"The goal is to know how many steps are needed in order to get a given pair $(x,y)$." Here is a simple Python program that should be fast enough. It takes less than a hundredth of a second even if $x$ and $y$ have hundreds of decimal digits. The crux of the program is, `count += x // y` and `x, y = y, x % y`, which uses integer division and remainder to reduce $x$ to be smaller than $y$.

```
def number_of_iterations_needed(x, y):
    count = 0

    if x < y:
        x, y = y, x
    # Now x >= y

    while x % y != 0:
        count += x // y
        x, y = y, x % y
    # Now x % y == 0

    if y != 1:
        return None  # impossible
    else:
        count += x - y
        return count

```

In fact, the above program is just an augmented version of the well-known Euclidean algorithm, the granddaddy of all algorithms. Its time-complexity should be about the same as the time-complexity of the Euclidean algorithm, which is $O(\ln(\min(x,y))$. It uses about $O(1)$ space.

If you are searching for a closed form for the number of iterations needed given $x$ and $y$, you will probably not be able to find one since, as indicated on that Wikipedia page, nobody has come up with a closed form after more than two thousand years.

# Answer
> 0 votes
You can solve this problem in time $O(xy)$ using dynamic programming.

For $x,y \ge 1$, let $OP\[x,y\]$ be the minimum number of operations needed to obtain array $\[x,y\]$. If it is impossible to obtain array $\[x,y\]$ let $OP\[x,y\] = + \infty$.

Then $OP\[1,1\]=0$ and, for $x\>1$ or $y\>1$: $$ OP\[x,y\] = \begin{cases} 1 + OPT\[x, y-x\] & \text{if } x\<y \\ 1 + OPT\[x-y, y\] & \text{if } x\>y \\ +\infty & \text{if }x=y \end{cases}. $$

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


# Question
Title: The number of bits needed to address 64KB
Introduction to computer science Level 109 I don’t understand the question

# Answer
> 1 votes
You are apparently the victim of poor typography.

Number of bits = log2(64 * 210) = log2(216) = 16.

Does that make it clear?

Nevertheless, this is the wrong forum for this question. This forum is for computer science educators.

---
Tags: algorithms
---


title: MAC protocol with throughput of 1

text:
# Question
Title: MAC protocol with throughput of 1
Consider a MAC protocol (ALOHA, CSMA, TDMA, etc.) that, even for very high loads, always results in a throughput of 1 (normalized with respect to the channel speed).

Why is that not good if the throughput is equal to 1?

# Answer
There can be many reasons, but one example would be fairness. Suppose you have a modified version of ALOHA where one priority user has transmission probability set to 1 and all others to 0. Assuming the priority user always has a message to send, this scheme has a throughput of 1. However, this is an awful scheme if you care about any of the other users, because they are going to experience infinite delay.

This is why researchers often prefer working with network utility functions as performance metrics to account for the welfare of the network instead of just overall throughput.
> 2 votes

---
Tags: computer-networks, performance, communication-protocols
---


# Question
Title: What class this graph connectivity problem belong to
We are given a Boolean circuit $C(x\_1, \dots, x\_n,y\_1, \dots, y\_n)$ with $2n$ inputs and we have to determine if the graph $G\_C = (V\_C, E\_C)$ (specified below) is connected: $$V\_C = \\{0,1\\}^n, \\ E\_C = \\{((a\_1, \dots, a\_n), (b\_1, \dots, b\_n)) : C(a\_1, \dots, a\_n,b\_1, \dots,b\_n) = 1\\}.$$

To which class this problem belongs? I know that graph connectivity can be done so fast (as fast as to be in **P**) and using a small amount of space. Does this is different in this particular graph? Is this problem in **P**, **EXP**, **PSPACE**?

# Answer
> 3 votes
$G$ has $2^n$ vertices, and for any two vertices $v\_i,v\_j$ we can check whether $(v\_i,v\_j)\in E$ in polynomial time (since circuit value problem is in P). By executing DFS on $G$ from any vertex you can find out whether $G$ is strongly connected in $O(|V|+|E|)=O\left(2^{2n}\right)$ time, which puts your problem in $E$, as the circuit's description is of size $\Omega(n)$.

Your problem is PSPACE-hard. Given a machine $M$ which uses $\le n^c$ space and input $x$, denote by $G\_x$ its computation graph, i.e. the graph whose vertices are all possible configurations using $\le |x|^c$ cells and $(C\_i,C\_j)\in E\_{G\_x}$ iff $C\_i$ is followed by $C\_j$ in the computation of $M$. Now adjust $G\_x$ by adding edges from every vertex to $C\_x$, the initial configuration of $M$ on input $x$, and from the accepting configuration $C\_{acc}$ (assume without loss of generality that it's unique) to all other vertices. Clearly this new graph $G\_x'$ is strongly connected iff there is a path from the from $C\_x$ to $C\_{acc}$ in $G\_x$. Given $M,x$ you can construct in polynomial time a circuit $C\_{G\_x'}$ that takes two vertices $C\_i,C\_j$ of $G\_x'$ and outputs 1 iff there is an edge from $C\_i$ to $C\_j$ (checking whether one configuration is immediately followed by another is easy). I leave it to you to complete the details here.

---
Tags: graphs
---


# Question
Title: Fastest algorithm for connectivity problem
Let $G = (V,E)$ be any undirected graph. Let $k$ be some number and $C = |u \longrightarrow v|$ where $u \longrightarrow v$ means there is a path from $u$ to $v$. We want to add $k \subseteq V \times V\ E$ edges into $G$ such that $C$ is maximised in the new graph.

Question : What is the fastest algorithm for this problem?

I can solve the above problem in $n^{O(k)}$ time by brute force method.

# Answer
> 2 votes
If I understand you correctly, you want to maximize the number of pairs of vertices that are connected.

In a connected (undirected) graph, all vertices are reachable from each other, so the number is always $n^2$.

You can always connect to components with an edge by placing it arbitrarily between the components, and this will increase the number from $a^2 + b^2 \leq (a+b)^2$ to $(a+b)^2$.

If $a \geq b \geq c$, then

$$(a + b)^2 - a^2 - b^2 \geq \max((b+c)^2 - b^2 - c^2 , (a+c)^2 - a^2 - c^2).$$

It follows that the optimal solution is to iteratively connect the two largest components in your graph, which corresponds to, given $k$ edges, connecting the $k+1$ largest components of your graph.

Finding the $k+1$ largest components can be done in $O(n+m)$ time.

---
Tags: algorithms
---


title: Does 2SAT contained in SAT?

text:
# Question
Title: Does 2SAT contained in SAT?
Is it true that $2 S A T \subseteq S A T ?$ and in general is $k S A T \subseteq S A T $ where k is any positive integer is true?

Thanks.

# Answer
Yes.

The definition for SAT is: $SAT:=\\{\varphi\in\Sigma^\*|\varphi\text{ is a logic formula, and }\exists a.\varphi(a)=True\\}$

The definition for kSAT is: $kSAT:=\\{\varphi\in\Sigma^\*|\varphi\text{ is a 2CNF logic formula (its just a specific form) and }\exists a.\varphi(a)=True\\}$

As you can see, from the definition we would have $kSAT\subseteq SAT$.

***It's important to note*** that the 2SAT problem is **known to be easy** (aka is in $P$), although SAT is **not known to be easy, but is known to be $NP-Complete$**.

In addition, for every $k\ge 3$, we have $kSAT$ is $NP-Complete$
> 1 votes

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


# Question
Title: Are non-ordered (Slabbed) Neural Networks in wide modern use and what does Fiesler (1994) mean by Clamping Function and Ontogenic function?
In Fiesler (1994) Neural Network Classification and Formalization, he talks a lot about a more general version of neural networks, one that is not ordered into layers, but rather the network is called slabbed and the "layers" are instead called clusters. Unlike for feed-forward networks, slabbed networks may be cyclical and terminate when a stable state has been reached, rather than when propagation has reached output neurons.

Much of this paper is outdated (terminology in particular). Is this an outdated concept or are these types of networks being used and/or researched?

Also from this paper, he mentions "clamping functions", but I am not sure what he means. Here is an excerpt where he talks about clamping functions:

"clamping functions, which determine if and when certain neurons will be insusceptible to incoming information, that is, they retain their present activation value independent of external stimuli"

I have seen a few more recent uses of "clamping" in literature, but they tend to be referring to something different. What exactly is he talking about here and is there a modern name for this?

Similarly, he refers to ontogenic functions and ontogenic networks, which I believe we call dynamic networks, but what is the ontogenic function? I understand it dictates how the network changes, but mathematically what are the inputs and outputs? What triggers the change to start and/or stop?

I am very interested in this formal definition of neural network as a mathematical object (this tuple with topology, interconnection structure, transition functions and intial state), does anyone know of a source that gives a similarly rigorous definition of a neural network, but with more modern terminology and ideology (I imagine some developments in theory may have allowed for networks to be more general)?

# Answer
I have not heard of recent work on this kind of thing, but there's a huge amount of literature and I know only a tiny slice of it.

Today much of the work on neural networks is concerned with feedforward neural networks, which don't have a cyclical structure. The most common form is

$$z(x) = L\_n(\cdots (a(L\_1(x))))$$

where $f:\mathbb{R}^n \to \mathbb{N}^k$, each $L\_i$ is a linear function, and each $a$ represents an activation function: i.e., $a(x\_1,\dots,x\_d) = (a(x\_1),\dots,a(x\_d))$ and $a$ is a simple nonlinear function called the activation function. The ReLU $a(x)=\max(0,x)$ is a common choice of activation function. There is some cleverness in the structure of the linear layers. Finally, the output of the neural network is $f(x)=\text{softmax}(z(x))$ where

$$\text{softmax}(z\_1,\dots,x\_k) = ({e^{z\_1} \over e^{z\_1} + \dots + e^{z\_k}}, \dots, {e^{k\_1} \over e^{z\_1} + \dots + e^{z\_k}}).$$

This is not the only architecture, but it is probably the most commonly seen, and as you can see, it has a relatively clean formalization.
> 2 votes

---
Tags: machine-learning, neural-networks
---


title: Adaptive arithmetic coding confusion

text:
# Question
Title: Adaptive arithmetic coding confusion
I'm confused about the point of adaptive arithmetic coding.

I understand that static arithmetic coding involves using preset probabilities of symbols that remain static during the whole process. I also understand that adaptive arithmetic coding involves change all probabilities after each symbol encountered.

However, what is the point of changing the probability after each symbol? Why wouldn't you just go through an entire file first and determine the probabilities and then do the arithmetic coding as a second pass?

Additionally, I don't understand how changing the probability of symbols impacts the compression? If we know the true probabilities of the symbols in the file we are compressing, then will it make the file smaller?

# Answer
First, consider "going through an entire file". There are a few assumptions worth thinking about here.

Files can be very big, and traversing them twice can be expensive. This is one reason why most real-world compression standards are based around blocks or windows.

There are situations where you don't have "the entire file" to begin with, such as a communication channel. TLS (prior to 1.3, at least) supports compression, for example.

Files are not always homogeneous. Archives (e.g. tar) are a case in point. A statistical model that is appropriate for one part of a file may not be appropriate for another part. Adaptive coding adapts to this, too.

As to your final question, if both the encoder and decoder knew the true probabilities of the symbols in the file we are compressing, then that wouldn't need to be transmitted. And, indeed, we sometimes do this in the real world. The JPEG standard, for example, specifies default coding tables for those times when they are appropriate, and lets an encoder supply their own when they are not.

Transmitting a static coding table efficiently (i.e. compressing it) is a nontrivial problem, especially for a large code alphabet. For a well-designed scheme, the cost of transmitting the table *should* be equal to the "learning cost" of using an adaptive code.
> 2 votes

---
Tags: algorithms, probability-theory, data-compression, encoding-scheme, huffman-coding
---


title: Quick Sort with first element as pivot

text:
# Question
Title: Quick Sort with first element as pivot
I'm studying Quick-Sort and I am confused as to how it works when the first element is chosen as the pivot point.

I am trying to trace the first step in the Quick-Sort algorithm, to move the pivot S\[1\] (17) into its appropriate position.

Example: \[17, -10, 7, 19, 21, 23, -13, 31, 59\].

```
^# = pivot
^ pointer

```

My understanding:

```
17, -10, 7, 19, 21, 23, -13, 31, 59
^#                               ^

```

Comparison 1. No swap.

```
17, -10, 7, 19, 21, 23, -13, 31, 59
^#                           ^

```

Comparison 2. No swap.

```
17, -10, 7, 19, 21, 23, -13, 31, 59
^#                      ^

```

Comparison 3. Swap.

```
-13, -10, 7, 19, 21, 23, 17, 31, 59
                     ^   ^#

```

Comparison 4. Swap.

```
-13, -10, 7, 19, 21, 17, 23, 31, 59
                 ^   ^#

```

Comparison 5. Swap.

```
-13, -10, 7, 19, 17, 21, 23, 31, 59
             ^   ^#

```

Comparison 6. Swap.

```
-13, -10, 7, 17, 19, 21, 23, 31, 59
          ^  ^#

```

Comparison 7. No swap.

```
 -13, -10, 7, 17, 19, 21, 23, 31, 59
       ^      ^#

```

Comparison 9. No swap.

```
-13, -10, 7, 17, 19, 21, 23, 31, 59
  ^          ^#

```

Comparison 10. No swap.

Is this how it works? Would it take 10 comparisons and 4 swaps to move pivot S\[1\] (17) into the correct position?

# Answer
You only need to compare each elemnt with the pivot once.

You can do so by keeping the pivot in place and then swapping elements in the remainder of the array.

```
17, -10, 7, 19, 21, 23, -13, 31, 59
 #   ^                           ^

```

start

```
17, -10, 7, 19, 21, 23, -13, 31, 59
 #           ^                    ^

```

move left pointer to first element larger than pivot. 3 compares

```
17, -10, 7, 19, 21, 23, -13, 31, 59
 #           ^           ^

```

move right pointer to first element smaller than pivot. 3 compares

```
17, -10, 7, -13, 21, 23, 19, 31, 59
 #           ^           ^

```

swap elements at pointer

```
17, -10, 7, -13, 21, 23, 19, 31, 59
 #                ^      ^

```

move left pointer to first element larger than pivot. 1 compare

```
17, -10, 7, -13, 21, 23, 19, 31, 59
 #               ^^

```

move right pointer to first element smaller than pivot (but not past left pointer. 1 compare

```
-13, -10, 7, 17, 21, 23, 19, 31, 59
             #

```

swap pivot with last element smaller than it. 1 swap

total = 8 compares and up to n/2 swaps per partition.
> 0 votes

# Answer
Quicksort doesn't swap the pivot into its correct position in that way, but it lies on the hypothesis that each recursive call sorts the sub-array and then merging sorted sub-arrays would provide a completely sorted array:

* let $V$ be the array to sort
* $pivot \leftarrow pick()$ *picks a pivot, in your case it's always the first element in $V$*
* let $V\_{\lt}$ be a list $s.t. \forall a \in V\_{\lt} \ a \in V \ \wedge \ a \lt pivot$
* let $V\_{=}$ be a list $s.t. \forall a \in V\_{=} \ a \in V \ \wedge \ a = pivot$
* let $V\_{\gt}$ be a list $s.t. \forall a \in V\_{\gt} \ a \in V \ \wedge \ a \gt pivot$

Quicksort then proceeds recursively calling itself on $V\_{\lt}$ and $V\_{\gt}$, thus assuming to get those two back with their values sorted.

The final step is then to return the concatenation of $V\_{\lt}$, $V\_{=}$ and $V\_{\gt}$, in this order.

Providing a numerical example:

$V = \[17, -10, 7, 19, 21, 23, -13, 31, 59\]$

Steps:

1. Initial run

$pivot = 17$

$V\_{\lt} = \[-10, 7, -13\] $

$V\_{=} = \[17\] $

$V\_{\gt} = \[19, 21, 23, 31, 59\] $
2. Recursion on $V\_{\lt} = \[-10, 7, -13\] $

$pivot = -10$

$V\_{\lt} = \[-13\] $

$V\_{=} = \[-10\] $

$V\_{\gt} = \[7\] $

*skips recursion on $V\_{\lt}$ and $V\_{\gt}$ since they're of size 1, thus already sorted*

returns $V\_{sort}$ = concatenation of $V\_{\lt}$, $V\_{=}$ and $V\_{\gt}$ = $\[-13, -10, 7\]$
3. Recursion on $V\_{\gt} = \[19, 21, 23, 31, 59\] $

$pivot = 19$

$V\_{\lt} = \[\] $

$V\_{=} = \[19\] $

$V\_{\gt} = \[21, 23, 31, 59\] $
4. Recursion on $V\_{\gt} = \[21, 23, 31, 59\] $

$pivot = 21$

$V\_{\lt} = \[\] $

$V\_{=} = \[21\] $

$V\_{\gt} = \[23, 31, 59\] $
5. Recursion on $V\_{\gt} = \[23, 31, 59\] $

$pivot = 23$

$V\_{\lt} = \[\] $

$V\_{=} = \[23\] $

$V\_{\gt} = \[31, 59\] $
6. Recursion on $V\_{\gt} = \[31, 59\] $

$pivot = 31$

$V\_{\lt} = \[\] $

$V\_{=} = \[31\] $

$V\_{\gt} = \[59\] $

returns $V\_{sort}$ = concatenation of $V\_{\lt}$, $V\_{=}$ and $V\_{\gt}$ = $\[31, 59\]$
7. Back from recursion in 5.

returns $V\_{sort}$ = concatenation of $V\_{\lt}$, $V\_{=}$ and $V\_{\gt}$ = $\[23, 31, 59\]$
8. Back from recursion in 4.

returns $V\_{sort}$ = concatenation of $V\_{\lt}$, $V\_{=}$ and $V\_{\gt}$ = $\[21, 23, 31, 59\]$
9. Back from recursion in 3.

returns $V\_{sort}$ = concatenation of $V\_{\lt}$, $V\_{=}$ and $V\_{\gt}$ = $\[19, 21, 23, 31, 59\]$
10. Back from recursion in 2.

returns $V\_{sort}$ = concatenation of $V\_{\lt}$, $V\_{=}$ and $V\_{\gt}$ = $\[-13, -10, 7, 21, 23, 31, 59\]$

As you can see, from the step 3 and onwards, the chosen pivot isn't an optimal one, since there only are elements at its right, preventing the algorithm to run in optimal time of $\mathcal{O}(n log\_2 n)$

*EDIT:* following Kai's comment, I fixed the definitions of $V\_{\lt}$, $V\_{=}$ and $V\_{\gt}$. I also acknowledge this is the simpler and less efficient Lomuto's partition.
> 0 votes

# Answer
place the pindex point to the last index in the array.Compare each and every element with pivot if the element is greater the pivot swap with pindex and decrement the pindex..The Following code helps you for the implementation of partition

```
def partioning(a,s,e):
pivot=a[s]
pi=e
for i in range(1,e):
 if(a[i]>=pivot):
   a[i],a[pi]=a[pi],a[i]
   pi-=1
a[pi],a[s]=a[s],a[pi]
return pi

```
> 0 votes

---
Tags: algorithms, sorting, quicksort
---


# Question
Title: Possible error in Computer Networks, V Edition by Tanenbaum & Wetherall
Under section 5.4 Quality of Service on page 404:

> Multimedia applications in particular, often need a minimum throughput and maximum latency to work.

Isn't this statement incorrect? Shouldn't it be :

*Multimedia applications in particular, often need a maximum throughput and minimum latency to work.*

# Answer
> 3 votes
I don't have a copy of this book to confirm the context, but I suspect that the sentence as written was intended to be interpreted as:

> Multimedia applications in particular, often need *the network to provide guarantees of a certain* minimum throughput and maximum latency to work.

In other words, in order for a multimedia application to function, the channel must ensure *at least* a certain throughput and *at most* a certain latency—exactly what is written.

The key word to notice here is the indefinite article "a". Both of the following sentences are correct, with different meanings:

1. Multimedia applications often need **a** minimum throughput and maximum latency to work.
2. Multimedia applications benefit from maximum throughput and minimum latency.

To further confuse matters, the following sentence means the same thing as 2.

3. Multimedia applications benefit from **a** maximum **of** throughput and **a** maximum **of** latency.

Isn't English grand?

---
Tags: computer-networks
---


# Question
Title: Can an $NDTM$ simultaneously perform a set of operations on all strings of a given length?
Can an $NDTM$ perform a set of operations on all strings of a given length $b$, at the same time? Aka can it operate on all strings of a given length by doing something like: spawn $2^b$ branches then operate on each string of length b on each branch?

How could it do this tho if the branches can't communicate? That's what I'm having a hard time with. How does any given branch, if it doesn't know what strings the other branches are running, know what string to run the operations on (so that all the strings are covered by $2^b$ branches)?

# Answer
> 1 votes
The easier way to think of NTM's is not as they are capable of "spawning branches", but as they are capable of "splitting into two branches, and each branch knows who it is (the first branch is 0, and the second is 1)"

In this way of thinking (that also actually represents what's going on inside the TM), splitting into $2^b$ branches means doing the "split" operation $b$ times.

Lets do a simple example with $b=2$:

In the first split, we have two branches: 0,1. In the second split, the "0" branch splits into branches "00" and "01" (notice that these are not numbers! They are strings) and the "1" branch splits into "10" and "11".

Notice that every string of length 2 is either one of the 4 final branches, and therefore this is how we would be able to non-deterministically check every string of length $b=2$.

The same applies for any other $b$ (note that if its not a constant, it will maybe harm the time or space complexity of the machine)

---
Tags: turing-machines, nondeterminism
---


# Question
Title: Algorithm to compute power function on interval [0, 1]
I am looking for an efficient algorithm to compute $$f(x) = x^a, x\in\[0, 1\] \land a\\,\text{constant}$$

If it helps, $a$ is either $2.2$, or $1/2.2$. Knowing valid values for $x$ and $a$ could make it possible to take some shortcuts a general `pow` function cannot make.

General tailor series expansion has some serious convergence problems when $x \to 0^+$, at least when $a \< 1$.

* The algorithm must be faster than `pow`
* The maximum error on the specified interval must be less than or equal to $10^{-4}$.

# Answer
> 2 votes
The Weierstrass Approximation Theorem states that any continuous function can be approximated on a bounded interval $\[a, b\]$ as closely as desired by a polynomial. In practice, instead of using Taylor series expansions, one uses polynomial minimax approximations $p(x)$ which approximate the function on the chosen interval with the minimal maximum error (thus the name).

When one looks at the graph of the error function $f(x) - p(x)$ one observes that it oscillates such that all extrema are of equal magnitude and neighboring extrema have opposite sign (equi-oscillation property), and that there are a total of $n+2$ extrema for a polynomial of degree $n$. This behavior of the error function can be used to construct the minimax polynomial, as also noted in gnasher729's answer.

The standard algorithm used to do this is called the Remez algorithm, named after the Russian mathematician who published it in 1927. This functionality can be found in ready-to-use form in widely used tools such as Maple and Mathematica, as well as the software tool Sollya, which provides an `fpminimax` command to generate minimax polynomial approximations. One can also create one's own implementation of the Remez algorithm, and I have used such code for this answer.

While the minimax polynomial is well defined mathematically, when the coefficients need to be stored in a finite-precision floating-point format and the polynomial evaluated is evaluated in finite-precision floating-point arithmetic, the error function $(f(x) - p(x)$ becomes deformed and no longer satisfies the equi-oscillation criterion. That means we wind up with a polynomial that is merely close to the true minimax polynomial. Many tools do not adjust for this effect at all, delivering coefficients based on high-precision internal computations. Sollya takes the finite-precision storage of the coefficients into consideration, and thus can often deliver superior results.

A minimax polynomial of degree five suffices to approximate $x^{2.2}$ to within the accuracy desired by OP. $f(x)=p(x)+\epsilon, \\:\\: |\epsilon| \< 7.4\cdot10^{-5}$. We can observe the equi-oscillation property of the error function $f(x) - p(x)$ and its seven extrema by plotting it, e.g. with Wolfram Alpha. Exemplary C code looks as follows:

```
/* Approximate x**(2.2) on [0,1] with minimax polynomial. Max. err < 7.4e-5 */
float pow_2p2_minimax (float x)
{
    const float c0 =  1.06425546e-1f; //  0x1.b3eb46p-4
    const float c1 = -3.56089801e-1f; // -0x1.6ca2cep-2
    const float c2 =  5.86735249e-1f; //  0x1.2c6890p-1
    const float c3 =  6.73461437e-1f; //  0x1.58cff0p-1
    const float c4 = -1.05324369e-2f; // -0x1.59207cp-7
    const float c5 =  7.38649687e-5f; //  0x1.35cfe8p-14
    return ((((c0 * x + c1) * x + c2) * x + c3) * x + c4) * x + c5;
}

```

Note that the minimax polynomial does *not* return zero at the origin. If we desire this property, we can add this additional constraint by using $f(x) = x^{2}p(x) +\epsilon$. An example, with $|\epsilon| \< 1.33 \cdot 10^{-4}$, is shown in this exemplary C implementation (plot of error function):

```
/* Approximate x**(2.2) on [0,1] with constrained minimax. Max. err < 1.33e-4 */
float pow_2p2_constraint (float x)
{
    const float c0 = -3.66555989e-1f; // -0x1.775a74p-2
    const float c1 =  1.19028902e+0f; //  0x1.30b6c8p+0
    const float c2 = -1.55231142e+0f; // -0x1.8d6448p+0
    const float c3 =  1.19035530e+0f; //  0x1.30bb20p+0
    const float c4 =  5.38091123e-1f; //  0x1.1380aep-1
    return x * x * ((((c0 * x + c1) * x + c2) * x + c3) * x + c4);
}

```

The computation of $x^{1/2.2}$ is a bit trickier. The easiest approach that does not suffer from premature underflow seems to be the following: Compute $y = \sqrt{\sqrt{x}} = x^{\frac{1}{4}}$, then compute $y^{\frac{20}{11}} = p(y) + \epsilon$ = $x^{\frac{5}{11}} = x^{1/2.2}$. The square root function is very fast on many modern processors, but slow on others, so this may not be a universal win, depending on how `pow()` is implemented. To achieve the error bound desired by OP, a minimax polynomial of degree six is needed, resulting in $|\epsilon| \< 7.5 \cdot 10^{-5}$. Exemplary C code looks like so:

```
/* Approximate x**(1/2.2) on [0,1] with minimax polynomial. Max. err < 7.5e-5 */
float pow_0p4545_minimax (float x)
{
    const float c0 =  3.07896197e-1f; //  0x1.3b4924p-2
    const float c1 = -1.06079876e+0f; // -0x1.0f9082p+0
    const float c2 =  1.48817670e+0f; //  0x1.7cf926p+0
    const float c3 = -1.18180847e+0f; // -0x1.2e8b00p+0
    const float c4 =  1.42678642e+0f; //  0x1.6d41e0p+0
    const float c5 =  1.98969673e-2f; //  0x1.45fdeep-6
    const float c6 = -7.45610159e-5f; // -0x1.38bb48p-14

    /* compute x**0.25 */
    x = sqrtf (sqrtf (x));
    /* compute (x**0.25)**(20/11) = x**(1/2.2) */
    return (((((c0 * x + c1) * x + c2) * x + c3) * x + c4) * x + c5) * x + c6;
}

```

# Answer
> 0 votes
You achieve the best approximation of a continuous function by a polynomial of degree n if the error has n+2 minima / maxima of same magnitude with opposite sign. A polynomial interpolating at n+1 points has degree n. So if you think a cubic polynomial might be good enough, create a spreadsheet where you enter 4 interpolation points, calculate the interpolation polynomial and the error, draw a graph of the error, then move the interpolation points around until the error has five minima / maxima with same value and opposite sign.

If you want to keep the relative error small, approximate f(x) /x.

# Answer
> 0 votes
For f(x) = $x^{1/{2.2}}$, calculate it as $x \cdot x^{-1/2} \cdot x^{1/{22}}$.

Most processors provide a fast approximation to x^-1/2 which can be improved enough with one step of Newton iteration very quickly. And x^1/22 is quite smooth. Remember you don’t have to limit the error in x^1/22 but in the product.

---
Tags: numerical-algorithms
---


# Question
Title: What is the difference between luma and luminance?
I understand the following (correct me if I'm wrong):

## Statements

1. Luma as the weighted sum of RGB **gamma corrected** components, but luminance is the weighted sum of RGB **linear** components.
2. The gamma correction has two forms: gamma compression and expansion. When we want to encode luminance into imaging systems, we turn it into luma using gamma compression (so $\gamma \<1$ when we raise the RGB components to a higher power).

So in short, Luma is the stuff in the "computer world" and Luminance is exists in the "physical world", is this correct? Because Luminance is roughly equivalent to the $Y$ value in CIE-XYZ colour space.

## Questions

1. When I have my images, are the pixel values already in linear RGB components or are they gamma corrected RGB components? That is, how is luma represented internally in imaging systems?
2. When we want to emit the colour in the screen, we perform gamma expansion, is this right? If so, will the light that comes out of the screen be considered as luminance?
3. When light waves travel, what physical property does luminance represent? Is it the amplitude of light waves?
4. In the CIE-XYZ colour space, is Y the only one that has physical meaning? Meaning to say X and Z are rather arbitrary factors dependent on the human visual system and nothing to do with physics itself,is this correct?

# Answer
There are actually three related terms:

* *Luminance* is a physical measure which represents the luminous intensity per unit area of light travelling in some direction. The units are candela per square metre. This is, if you like, an objective measure of how "intense" light is.
* *Relative luminance* is a measure how "intense" light appears to a human; since humans can't see X-rays or infra-red, that doesn't register. The CIE standard defines a "standard observer" (more on this later) under various conditions. This is normalised into a range from 0 to 1 or 0 to 100, where the higher value is a reference white.
* *Luma* is defined as the relative luminance calculation performed on a *gamma-compressed video signal*.

So if you take a real-world light source, and point an image sensor at it, the image sensor will output $R'G'B'$ values, where the prime denotes gamma compression.

If you were to uncompress those signals (i.e. convert the gamma-compressed $R'$ into its corresponding linear-space $R$, then:

* $Y = 0.2126 R + 0.7152 G + 0.0722 B$ is the relative luminance
* $Y' = 0.2126 R' + 0.7152 G' + 0.0722 B'$ is the luma

Relative luminance is exactly Y in CIE-XYZ. Y is calculated by calculating the inner product of the power spectral density of a light source with the luminosity function which represents the "standard observer".

(Note that CIE standard actually defines more than one luminosity function, because the human eye behaves differently in low-light condition; Y is defined in terms of the photopic luminosity function.)

The only reason why we define luma is for signal processing and compression reasons. It's easier to compress based on the luma signal than the relative luminance because the transformation is simpler; in fact, it's achievable using relatively cheap 1960s-era analog electronics. And since there's a more-or-less monotonic relationship between the two, luma key is close enough to keying on relative luminance.

OK, now to your questions:

**When I have my images, are the pixel values already in linear RGB components or are they gamma corrected RGB components? That is, how is luma represented internally in imaging systems?**

High-quality image formats tell you. Along with an array of triplets of numbers (which are just numbers), there should be information about what colour space the image is in.

Unless you have been told otherwise, it's safe to assume that any standard dynamic range still image pulled off the Internet is in sRGB. This is gamma-compressed, although the gamma is not constant.

For video, there are lots of colour spaces in use. Broadcast television follows the ITU-R recommendations (e.g. Rec 601 is standard definition, Rec 709 is high-definition, etc), and film tends to use Cineon.

But each camera manufacturer typically defines its own colour space too, which represents the best approximation of the sensors in the camera. ARRI cameras, for example, output their own colour space known as ARRI Log C.

It's something of a mess.

**When we want to emit the colour in the screen, we perform gamma expansion, is this right? If so, will the light that comes out of the screen be considered as luminance?**

"Gamma" is a confusing concept because it refers to two distinct things. Strictly speaking, "gamma" should refer to the nonlinearity of a hardware device, such as a sensor or display. All image data should be linear, intermediate work should be in a linear space, and gamma should only be applied when data is acquired or displayed.

"Gamma compression" refers to a technique for compressing linear data in a file format, so that fewer bits per sample are required.

It just so happens that a lot of modern display vendors and file format designers have agreed on the same standard, sRGB. So if you have data compressed in sRGB format and a display which works in sRGB, the operation of decompressing the file format and the operation of preparing the data for display cancel each other out. In general, that need not be the case.

For a properly calibrated display, yes, Y is relative luminance.

**When light waves travel, what physical property does luminance represent? Is it the amplitude of light waves?**

Answered above. Luminance is the physical measure of the intensity of light, and relative luminance is the perceived intensity of light (for a standardised human observer).

**In the CIE-XYZ colour space, is Y the only one that has physical meaning? Meaning to say X and Z are rather arbitrary factors dependent on the human visual system and nothing to do with physics itself,is this correct?**

What I hope you can now see is that Y, relative luminance, is also defined on the human visual system.
> 14 votes

# Answer
When light waves travel, what physical property does luminance represent? Is it the amplitude of light waves?

Close, intensity of light (ie energy, power etc) goes as the square of the amplitude. Luminance would appear to be proportional to intensity.
> 0 votes

---
Tags: image-processing, graphics, physics
---


# Question
Title: Intelligent use of XOR operator to find missing number
I've come across the following problem on leetcode & tried to solve it with the following code however there seems to be an even better solution that takes advantage of XOR. Leetcode has a description for XOR solution however I can't grasp it in its entirety.

*I just can't wrap my head around why we need to initialize missing variable with length of array,* why not initialize it with Zero & when we do initialize it with Zero, why can't this algo find the missing number? Can someone please explain it?

Following was my solution before I learned Leetcode suggested XOR solution is even better & faster

```
class Solution {
    public int missingNumber(int[] nums) {
        if(nums.length == 1)
            return nums[0] == 0 ? 1 : 0;

        int missing = 0;
        boolean tempNums[] = new boolean[nums.length+1]; //cuz one is missing

        for(int i:nums) {
            tempNums[i] = true;
        }

        for(int i=0; i<tempNums.length; i++)
            if(!tempNums[i]) {
                missing = i;
                break;
            }
        return missing;
    }
}

```

# Answer
> 2 votes
Let us use a simpler example to verify the fact.

Suppose $n=1$, i.e., we are given an array containing one (distinct) number taken from 0, 1.

* If the given number is 0, then the missing number must be $1=1\land0$.
* If the given number is 1, then the missing number must be $0=1\land1$.

To summarize, if the given number is $a$, then the missing number is $1\land a=n\land a\not=0\land a$.

---

What are the fundamental reasons behind this magic in general situations?

It turns out the bitwise XOR operator, commonly denoted by "$\land$" in programming languages, behaves like the ordinary plus operator.

* It is *commutative* and *associative*. So the order of operations does not matter at all.
* *$0$* functions as a zero, i.e., $a\land 0=a$. So $0$'s can be removed.
* $a\land a = 0$ for every number $a$. So if the same number appear twice, they cancel each other.

Outside of programming languages, the bitwise XOR is more commonly written as "$\oplus$", where the plus symbol, "$+$" in the center reminds us it behaves like ordinary addition.

Now consider the expression, $$(0\oplus1\oplus2\oplus3\cdots\oplus n)\oplus( a\_0\oplus a\_1\oplus a\_2\cdots\oplus a\_{n-1}). $$ Whenever there is a pair of the same number, we can remove them. So all numbers are cancelled out between each other, except that missing number, since that missing number is the only number that appears in $$0\oplus1\oplus2\oplus3\cdots\oplus n$$ but not in $$a\_0\oplus a\_1\oplus a\_2\cdots\oplus a\_{n-1}.$$ So,

$$(0\oplus1\oplus2\oplus3\cdots\oplus n)\oplus( a\_0\oplus a\_1\oplus a\_2\cdots\oplus a\_{n-1})=\text{the missing number} $$

Let us change the order of "summation" on the left-hand-side. We can pair $0$ with $a\_0$, $1$ with $a\_1$, $2$ with $a\_2$, $\cdots$, $n-1$ with $a\_{n-1}$, leaving only $n$ unpaired. We see that the left-hand-side is $$(0\oplus a\_0)\oplus(1\oplus a\_1)\oplus(2\oplus a\_2)\oplus\cdots(n-1\oplus a\_{n-1})\oplus n. $$ Now, just move $n$ to the front of the expression.

---

"I just can't wrap my head around why we need to initialize the missing variable with length of array. Why not initialize it with Zero & when we do initialize it with Zero, why can't this algo find the missing number?"

There is nothing special about initializing the missing variable with $n$, the length of array. You can certainly initialize it with any number, including zero. Then you should pair the *remaining* numbers with $a\_0, a\_2,\cdots, a\_{n-1}$ (*arbitrarily*, each number exactly once). For example, we have

$$0\oplus(1\oplus a\_0)\oplus(2\oplus a\_1)\oplus\cdots(n\oplus a\_{n-1})=\text{the missing number} $$

In fact, we do not have to do the pairing at all. We can even precompute directly $$f(n) = 0\oplus1\oplus2\oplus3\cdots\oplus n =\begin{cases} n&\text{ if }n=0\pmod4\\ 1&\text{ if }n=1\pmod4\\ n+1&\text{ if }n=2\pmod4\\ 0&\text{ if }n=3\pmod4\\ \end{cases}$$ and then compute $$f(n)\oplus a\_0\oplus a\_1\oplus a\_2\cdots\oplus a\_{n-1},$$ which will yield the missing number as well. Hence we have the following faster program to compute the missing number.

```
public int missingNumber(int[] nums) {
    final int length = nums.length;
    // missing = length, 1, length + 1, 0 when length = 0, 1, 2, 3 mod 4.
    int missing = length % 2 == 0 ? length + (length / 2 % 2) : (length + 1) / 2 % 2;
    for (int i : nums) missing ^= i;

    return missing;
}

```

The above approach is very similar to Approach #4 Gauss' Formula on Leetcode.

# Answer
> 1 votes
Start with a list of any n integers. Duplicate the integers and calculate the XOR if these 2n integers. What’s the result? Rearrange the 2n integers in any way and calculate their XOR. What’s the result. Remove a number x from the list and calculate the XOR. What’s the result? Remove another number y and calculate the XOR. What’s the result?

Now go back to your problem, and the answers you gave before tell you immediately what your result will be.

---
Tags: algorithms, integer-programming, java, bit-manipulation
---