# Question
Title: Algorithm for executing a command against a million hosts
Consider the following problem: you are given a set of one million machines (hosts), and you would like to have the ability to execute at will an arbitrary command against the whole set; for the moment, let us suppose you want to run one command at a time. How to do that efficiently?

Is also desirable to have the ability to query at any moment the progress (status of execution on each host), as well as to consult afterwards the outcome of each individual execution (both exit code and stdout/stderr); hence, the outcome must be persisted somewhere.

Ideally, if you could deliver instantaneously the command at all the hosts, and coordinate them to start at the same time, you would have an ideal time of the command duration (assuming command takes same time on every host). Thus, I presume that a big part of the problem is how to deliver as fast as possible the command to all the hosts; the problem may get more elaborated if we add the quality of being fault-tolerant (that is, to ensure that the execution does take place on all available hosts even if some of the auxiliary machines used for the delivery fail or have issues).

If I execute a dummy echo command using ssh on an intranet I have access to (after having automated the authentication with keys); the time for getting back a response is at best 0.25 secs. Thus, running one million times ssh against each one of the hosts does not sound promising if done serially (it would take almost 3 days to finish the execution serially on this environment).

Even if we could deliver the command within a few milli-seconds to each machine using a custom protocol other than ssh, doing the delivery from a single source may not be the best approach. I suppose that the problem may benefit from some parallel/distributed algorithms, as well as network/graph theory. It would also be nice to avoid using a centralized approach too, if one does not want to rely on the availability of a fixed set of machines for doing the delivery (which ideally should be a subset of the one million hosts, so we do not need additional infrastructure machines).

Is there an standard name for this kind of problem? Any known algorithms or approaches?

# Answer
Assuming the hosts and network are reliable, and that the cost of sending a message from any machine to any other machine is the same, then you would use some sort of *broadcast tree*. For example, if the machines are all numbered 0, ..., 7, then node 0 would send to node 4, 2, and 1, node 4 would send to nodes 6, and 5. Node 2 would send to node 3. Node 6 would send to node 7.

Generalize that to $2^n$ nodes, and the total time is $O(n)$. So with 220 nodes, node 0 would send about 20 messages, rather than 1 million.

As you make the assumptions weaker, the problem gets increasingly more difficult.

If the cost of sending messages is different for different pairs of machines, then you would want to do some kind of minimum spanning tree based algorithm, maybe.

If you don't know anything about the network as a whole, but each node knows something about its neighbors then you might use some kind of *flooding* algorithm.

If the network is not reliable (links can appear and disappear) then the problem gets quite difficult. I think there are various ways of posing the problem as a *Steiner tree problem*, but now you are way outside my area of expertise.
> 3 votes

---
Tags: algorithms, distributed-systems, parallel-computing, computer-networks
---


# Question
Title: Recursive and recursively enumerable language definition for a layman
I've come across many definitions of recursive and recursively enumerable languages. But I couldn't quite understand what they are .

Can some one please tell me what they are in simple words?

# Answer
Not really. You should read a few books. Perhaps we can recommend some.

That said, a language is recursive if there is a Turing machine than can always reply "yes" or "no" if a given string is part of this language. If we lift this requirement to merely say "yes" for strings of the language (it can run forever if it is not) then we have a recursively enumerable language. It is not hard to see, that a recursive language can be decided by a Turing machine, while a recursively enumerable language can have its strings listed (for example, by running an infinite number of Turing machines in parallel — yes this is possible, see dove-tailing — on all strings of the alphabet, and outputting a string if the corresponding TM accepts). There are many, many equivalent definitions.
> 16 votes

# Answer
A problem is recursive or *decidable* if a machine can compute the answer.

A problem is recursively enumerable or *semidecidable* if a machine can be convinced that the answer is positive.
> 20 votes

# Answer
A *Language* is just a set of strings. Possibly of infinite cardinality.

A language is *recursive enumerable* if there exists a TM that keeps outputting strings that belong to the language (and only such strings), such that eventually every string in the language will be in the output.

A language is *recursive* if, the above TM not only outputs all the strings in the language, but also do it in order! (say, lexicographically).

I'm sure you can easily think of recursive languages (and build a TM that outputs them by order). It's quite difficult to come up with recursive enumerable languages (that are not recursive), unless you read some more about undecidability and diagonalization. But such languages do exist.
> 3 votes

# Answer
Recursive languages are decidable by some Turing Machine, i.e., there is a TM that can, given any input string (over the appropriate alphabet) correctly answer yes if the string is in the language, or no if it isn't.

Recursively enumerable languages are only recognized, i.e., there exists a Turing Machine that accepts when the string is in the language but it may loop forever if the string is not in the language.
> 2 votes

# Answer
I feel the main difference between recursive and recursively enumerable languages is that Recursive Turing machine halts in non-final state if it does not accepts a string

Recursively enumerable Turing machine if it not accepts a string may halt in non final state or loop for ever which is not the case for recursive languages
> 0 votes

# Answer
==\> A language is recursive if there exists a Turing machine that accepts every string in the language and rejects if it is not in the language. for example lets take Turing machine M and String w: if string w is a member of the Turing machine M, then M halts in its final state otherwise it rejects the computation. ==\>==\> A language is recursive enumerable if there exists a Turing machine that accepts every string in the language and rejects if it is not in the language may be loop forever. for example lets take Turing machine M and String w: if string w is in the language , then M halts in its final state. Otherwise it rejects the computation or may be run forever.
> 0 votes

---
Tags: formal-languages, computability, turing-machines
---


# Question
Title: What is the natural language of computers mathematics or logic?
I was reading about the history of computers where i came by machine code

> A Machine code or machine language is a set of instructions executed directly by a computer's central processing unit (CPU). Each instruction performs a very specific task, such as a load, a jump, or an ALU operation on a unit of data in a CPU register or memory.

The computer here does logical operations like load or jump steps using the machine code.

From the Wikipedia page a computer is

> A general-purpose device that can be programmed to carry out a set of arithmetic or logical operations automatically.

This means from the machine code the computer can perform logical or arithmetic operations, but which principle computers are based on the logical principle or the mathematical principle ?

What can be said also as the natural language of a computer ?

====

\[Edit\] both answers solved my problem.

====

# Answer
There is really no such thing as a *natural language* for computers. Natural language is a concept from linguistics, and pertains mostly to humans (and perhaps also to some animals).

The corresponding concept for computers is *machine language* or *native code*, which is what the computing core of the computer (the CPU) runs. Machine codes consists of various instructions, some of which perform arithmetic and logical operations. Others are in charge of control flow, of memory access, and so on.

Related to machine language is *assembly code*, which is a readable representation of machine code. While machine code consists of bytes, assembly code consists of textual symbols. (Assembly code also usually contains some features which make it a barebones programming language.)
> 6 votes

# Answer
(Digital) computers are based on logic. Mathematics can express more than logic can, but computers cannot express everything that mathematics does. For instance, mathematics is allowed to make claims such as axiom of choice, i.e. a claim that no matter whether the elements of a set are finite sets, infinite sets or uncountably infinite etc, there is a procedure to select all elements from those sets in some order.

Mathematicians just assume that that's true and move on to prove other theorems. Logicians shrug and silently point out that that's just not something you can prove using logic. In other words, mathematics may assume existence of some true facts in this world, which it isn't able to prove. Logic doesn't.

Digital computers "speak" logic in the sense that whatever algorithm you write, it must be constructible. Mathematics can live happily with functions it cannot construct. More so, computers are also limited in the sense of what functions they can compute, and that would be very imprecisely speaking equivalent to some predicate logic with limited notions of quantification and recursion. This is while mathematics has no problems accommodating functions like busy-beaver and other non-computable functions.

There was a movement in mathematics in the 60's when mathematicians tried to reduce it to only constructable proofs (aka constructivism), but most mathematicians today don't subscribe to this paradigm.

---

Bottom line: digital computers are a proper subset of logic, but it's hard to give a precise placement in the taxonomy of logics. Somewhere between predicate and first-order logics, with (probably) some extra-logical predicates.
> 5 votes

---
Tags: complexity-theory, computability, logic
---


title: The finer details of Meek's STV

text:
# Question
Title: The finer details of Meek's STV
Meek's version of the Single Transferable Vote system \[.pdf\] is used in multiple big elections including those of New Zealand and Stack Exchange.

Demonstration (with thanks to the Department of Internal Affairs of New Zealand).

I have a basic understanding of how the votes are counted, but there's one thing I haven't been able to figure out.

What happens if positions are left blank?

For example: Assume 6 candidates and no limit on the amount of choices.

One could vote (where left is first vote and right is last): `3 4 5 6 1 2` or `4 5 6` and leave the rest blank.

In the STV system, the following is legal as well: `0 2 4 0 1 6` What would happen in that case?

Will the choices be shifted to clear it from any left-open positions or will the votes be counted at the moment indicated by the position? Those options will (likely) influence the election both in different ways.

I'm not a CS expert in any way, just trying to get the hang of an interesting system to implement my own vote counter.

# Answer
> 2 votes
In Meek STV, there is the concept of the *quota* or *threshold* that a candidate must exceed to be considered elected. This threshold is changed from round to round in the Meek STV system. The threshold changes based on how many votes are **thrown away**.

Let's say that your code is `4 5 6` and the rest blank, then once all those candidates are either elected or eliminated, the remaining part of your vote is considered "thrown away". Based on this, the threshold is changed for what candidates need to be elected in the next round.

In the STV system, the vote `0 2 4 0 1 6` is considered the same as `2 4 1 6 0 0`, i.e. the zeros are automatically put at the end.

In the Stack Exchange moderator elections, it is possible to choose only a second candidate and a third candidate, but not a first. That is the same thing as choosing a first candidate and a second candidate.

Related on Meta Stack Exchange: How are moderator election votes counted, in pure English?

# Answer
> 0 votes
Elections always have the notion of a *spoiled ballot*. Your example, `0 2 4 0 1 6` is not "legal." It is a *ballot* but not a well formed one. It would be thrown out of the process and none of the choices would count.

The program that counts the ballots must *validate* each ballot to make sure it makes sense.

If the ballot is an ordered list of choices (as in the paper you pointed to) then the program must make the following validation checks:

* each entry in the list contains a single candidate identifier in the range `1`...`6`.
* no entry in the list (other than the one indicating the end of the list) is empty.
* no entry in the list is a repeat (has the same candidate identifier) as any other entry.

Failing any of these validation checks makes the ballot *invalid* or *spoiled*, and the ballot is *rejected*.

If the ballot is a list of the candidates where you must fill in a number next to each candidate (as in the example New Zealand ballot you pointed to) then the checks would be:

* There is either a single preference number in the range `1`...`6`, or no preference number entered next to each candidate's name.
* No two candidates have the same preference number entered next to their name.
* The preference number `1` is next to some candidates name.
* If the preference number `k` (in the range `2`...`6`) is entered next to some candidates name then the preference number `k-1` must be entered next to some other candidates name.

Again, failing any of these checks makes the ballot *invalid* or *spoiled*, and the ballot is *rejected*.

---
Tags: algorithms, databases, voting
---


# Question
Title: Is program analysis part of programming language theory?
1. If I am correct, programming language theory studies

* syntax and semantics of programming languages, and
    * design and implementation of programming languages (e.g. compiler, ...)
2. Does programming in programming languages, i.e. creating programs in programming languages, belong to programming language theory?
3. Does program analysis (correctness and performance of programs) belong to programming language theory? My thought is:

* semantics of a programming language is used for verifying correctness of programs in the language, so it seems like the answer is yes, although I am not sure if analysis of programs' performance belongs to programming language theory.
    * program analysis also seems to belong to software engineering, which makes me feel perhaps it doesn't belong to programming language theory.

Thanks.

# Answer
> 1 votes
"Programming language theory" more or less includes everything you have listed, but of course there is overlap with other areas, such as software engineering, algorithms, security, human-computer interaction, and good old mathematics.

For instance, if you look at last year's programme of the Principles of Programming Languages (POPL) conference you will see not only topics about design, implementation and semantics of programming languages, but also about security, program analysis, papers about resource complexity, and many others.

In general I would say it good to be open about what "belongs" to a "research area". It is a shame to miss opportunities for new discoveries because of narrow-mindedness.

---
Tags: programming-languages, performance, software-engineering, software-verification
---


title: Alignment of RGBD with a thermal camera

text:
# Question
Title: Alignment of RGBD with a thermal camera
I have a thermal camera that I would like to overlay, automatically, to the output of a RGB-D camera (e.g. Kinect).

I have retrieved the intrinsic and extrinsics parameters of both cameras.

My objective is to calculate the disparity map between the two. That is, to map the matrix resulting from the depth image to the thermal image, in order to estimate the distance of each point in the thermal image. From an intuitive standpoint, I should be able to align them because I have depth information in this case.

A solution that comes to my mind, it is as follows:

* *Step 1*: for each pixel of the depthmap, estimate its corresponding 3D point. Let's call it **Depth\_3D**.
* *Step 2*: transform **Depth\_3D** in **Ther\_3D**. That is, given the 3D position of the point of the depth camera, find the 3D position of the same 3D point (object in the real world), but respect to the thermal camera. The relative position and orientation of the two cameras is known.

Problem: to perform *step 2*, I need the 3D rotation matrix (let's call it **R3D**) and 3D translation vector (let's call it **T3D**) to be able to map from the depth camera to the thermal camera, in the real world.

* *Step 3*: Finally, using the intrinsic parameters of the thermal camera, project each Ther\_3D into the thermal image.
* *Step 4*: assign the depth to the obtained pixel, so that, at the end of the loop, the depth map of the thermal image is complete.

My doubt is about how to calculate R3D and T3D (please see step 2) using their relative position and orientation. Other solutions are welcome of course.

Thanks in advance.

# Answer
> 1 votes
Step 2 is just a change of coordinate system from one camera's coordinate system to the other camera's coordinate system. It's easy to do, using a "change of basis".

The extrinsic parameters of the depth camera tell you how to transform from the depth camera's coordinate system to the world coordinate system (a transform between two 3D coordinate systems). The extrinsic parameters of the thermal camera tell you how to transform from the 3D world coordinate system to the thermal camera's coordinate system. If you combine these two transformations, you have a way to transform from Depth\_3D to Ther\_3D.

So if you have the extrinsic parameters, you should already know how to do this.

See, e.g., https://en.wikipedia.org/wiki/Pinhole\_camera\_model and https://en.wikipedia.org/wiki/Camera\_matrix and https://en.wikipedia.org/wiki/Camera\_resectioning, or any textbook that describes camera intrinsic and extrinsic parameters.

---
Tags: computer-vision
---


title: Find k nearest neighbors on a sphere

text:
# Question
Title: Find k nearest neighbors on a sphere
Given a set $S$ of $N$ points on a sphere, and another point $P$ on the sphere, I want to find the $k$ points in $S$ that are the closest (Euclidean or great circle distance).

I'm willing to do a reasonable amount of pre-computation. The solution must be exact and efficient (faster than linear time).

# Answer
Use the space partitioning approach to nearest neighbor search.

For instance, one approach is to use a $k$-d tree on on the surface of the sphere. You can express every point on the sphere using spherical coordinates: every point on the sphere has coordinate $(1,\theta,\phi)$. Thus, we have a 2-dimensional space with coordinates $(\theta,\phi)$. Now organize your points using a $k$-d tree, where here we are in $k=2$ dimensions. There are standard algorithms for nearest neighbor search in a $k$-d tree; heuristically, the expected running time is $O(\lg N)$.

You will have to make small modifications to the data structure to reflect that the coordinates "wrap around" modulo $2\pi$, but this is not hard. The key subroutine used in nearest neighbor search in a $k$-d tree is: given a point $P$ and a "rectangular" region $R$, find the distance from $P$ to the nearest point in $R$. In your case, the region $R$ is $\[\theta\_\ell,\theta\_u\] \times \[\phi\_\ell, \phi\_u\]$, i.e., the set of points $\\{(1,\theta,\phi) : \theta\_\ell \le \theta \le \theta\_u, \phi\_\ell \le \phi \le \phi\_u\\}$. It is easy to compute the distance from $P$ to the closest point in $R$. This will then let you use the standard algorithm for nearest neighbor search in a $k$-d tree.

Alternatively, instead of a $k$-d tree, you could use any other binary space partitioning tree, or you could look at metric trees, though I don't have any reason to expect them to be significantly better.
> 4 votes

# Answer
Here are links to two different software packages that address your question. It may be worth studying each to see if the methods they employ satisfy your needs:

(1) Matlab GridSphere. "A geodesic grid is an even grid over the surface of a sphere. The algorithm is optimized for a grid generated by GridSphere and won't work on an arbitrary geodesic grid."

(2) DarkSkyApp sphere-knn .js. "provides fast nearest-neighbor lookups on a sphere....well-tested and works correctly regardless of where on the earth things are located."
> 2 votes

---
Tags: data-structures, computational-geometry, nearest-neighbour
---


title: Strahler of tree like refutations

text:
# Question
Title: Strahler of tree like refutations
I am reading the paper *Measuring the hardness of SAT instances* by Ansótegui, Bonet, Levy and Manyà (Proc. 23rd AAAI Conf. on AI, pp. 222–228, 2008) (PDF). I am trying to understand the last part of the demonstration of the Lemma 3 (in bold). For this, I get an example. Let be $\Gamma = (a+b)(a+b')(a'+c)(a'+c')$ then its tree-like refutation is:

Following the demonstration of the last part of the Lemma 3 (in bold), $\[b\rightarrow 1\]\Gamma=(1)(a)(a'+c)(a'+c')$, and adding the literal $b'$ where $\[b\rightarrow 1\]$ has removed it, we get $\Gamma' = (1)(a+b')(a'+c)(a'+c')$. In accordance the paper the tree-like refutation of $\Gamma'$ is a proof for $\Gamma \vdash b'$. According to the paper, similarly, for $\[b\rightarrow 0\]$, $\[b\rightarrow 0\]\Gamma = (a)(a'+c)(a'+c')$, and adding the literal $b$ where $\[b\rightarrow 0\]$ has removed it, we get $(a+b)(a'+c)(a'+c')$. My questions are,

1) Is there any difference between these Strahlers? for me there is not any difference, but why the author consider the function $\max$?

2) From the demonstration,

> Adding a cut of $x$ to these two proofs, we get a proof of $\Gamma \vdash \Box$.

Is it a rule of sequente calculus, if yes, following wikipedia Could you help to identify who are $\Sigma$, $\Pi$, $\Delta$ and $\Sigma$?

What means cut of $x$?

> **Lemma 3** The space satisfies the following three properties:
>
> 1. $s(\Gamma \cup \\{\Box\\})$ = 0
> 2. For any unsatisfiable formula $\Gamma$, and any partial truth assignment $\phi$, we have $s(\phi(\Gamma))\leq s(\Gamma)$.
> 3. For any unsatisfiable formula $\Gamma$, if $\Box\notin\Gamma$, then there exists a variable $x$ and an assignment $\phi\colon\\{x\\}\to\\{0,1\\}$, such that $s(\phi(\Gamma))\leq s(\Gamma)-1$.
>
> **The space of a formula is the minimum measure on formulas that satisfy (1), (2) and (3). In other words, we could define the space as:3**
>
> **$$s(\Gamma) = \min\_{x, \overline{x}\in\Gamma, b\in\\{0,1\\}} \big\\{ \max\\{s(\[x\mapsto b\](\Gamma))+1, s(\[x\mapsto\overline{b}\](\Gamma))\\}\\;\big\\}$$** **when $\Box\notin\Gamma$, and $s(\Gamma\cup\\{\Box\\}) = 0$**.

# Answer
> 1 votes
You have asked (at least) two questions. The answer to your first question is that sometimes it is much easier to refute a formula given that $x=0$ compared to given $x=1$. Hence the $\max$. In other cases, $x=1$ is easier. That's why we need to go over both possible values of $b$. Finally, the reason why the formula in part 3 of the lemma also maximizes over the variable $x$ is that $x$ represents the last variable which is cut (the one at the root of the tree).

The answer to your second question is as follows. The cut rule allows deriving $a \lor b$ given $a \lor x$ and $b \lor \bar{x}$. Here $a,b$ are arbitrary formulas, in this context clauses. In particular, from $x$ and $\bar{x}$ you can conclude contradiction. The cut rule is the only rule in the resolution proof system.

---
Tags: satisfiability
---


# Question
Title: Simpler proof of Rabin's Compression Theorem?
I was doing a presentation on Rabin's Compression Theorem, when someone in the audience brought up a point I have no answer to.

Rabin's Compression Theorem states that every reasonable complexity class has a problem that can be solved optimally in it. The proof is a little involved, but not horribly difficult.

The audience member proposed a much simpler proof. For the given complexity class, calculate the target volume of computation from the input length. Then write that many hashes to the output.

Does this really prove the same result?

Also, I have had a lot of trouble finding Rabin's original paper. Does anyone know how to get it?

A formal version of the argument would be: Given a constructible function $f$, find a program that is optimal for $O(f(x))$ time, where $x$ is the length of the input.

```
def program(input):
    x = len(input)          # takes O(x) to read input of length x
    target = f(x)           # f is constructable, computing f(x) takes at most O(f(x))
    for _ in range(target): # takes exactly O(f(x)) to loop f(x) times
        print('1')          # assume we can append to the output in O(1)

```

The runtime of the algorithm is clearly $O(f(x))$.

The algorithm is optimal: Any program that prints $f(x)$ "1"s requires at least $f(x)$ steps.

As far as I can tell, this proof seems to work. It almost certainly proves something similar. However, I can't understand why the original proof would be so complicated, if this simpler proof works. This makes me worry that maybe I misunderstood something: e.g., about why the original statement is important/interesting, or about whether this simpler proof is correct and proves what it needs to prove. Can anyone help clear this up for me?

# Answer
> 4 votes
It is hard to answer this question since it is hard to find a formal statement of Rabin's compression theorem. Here is one from the book *Complexity Theory and Cryptology: An Introduction to Cryptocomplexity* by Jörg Rothe, page 63:

> For each time constructible function $t(n)$ there exists a decidable set $D\_t$ such that each deterministic Turing machine $M$ deciding $D\_t$ must run in time larger than $t(n)$ for all large enough $n$.

Granted, this is not exactly your statement (it might be a different theorem proven in the same technical report of Rabin from 1960, or perhaps a different publication of Rabin from the same year), and it also differs from the rather unclear statement in Levin's lecture notes, which is closer to your statement but also seems to mention a predicate (though Levin's proof doesn't result in a predicate).

Both statements are somewhat different than your informal statement that every complexity class has a problem that can be solved optimally in it. They also seem to mention that the problem can be chosen to be a predicate.

In order to make progress, I suggest that you update your question with a complete formal statement of Rabin's compression theorem as you understand it, explaining no longer standard notions such as *volume*. Then try to formally prove the theorem along the lines you mention. If you succeed, include the proof. If you fail, you have answered your own question.

It is likely that there is some easy version of the theorem that does follow from your argument, but the actual theorem is harder, requiring either a delicate priority argument (like in the book) or a Kolmogorov complexity argument (like in Levin's notes). This may be due to one of two features of Rabin's theorem:

1. It gives a predicate rather than an arbitrary function.
2. The actual guarantee is a bit different. For example, in Levin's version you should be able to compute the function in all volumes which are asymptotically larger than the optimal complexity.

Also, depending on your computation model, your own function might not be computable in your own time bound (though multitape machines seem fine here).

Why am I so sure that there is something wrong with your argument? Your argument is very simple, and I find it hard that it was missed by both Rabin and Levin. It is much more probable that it just doesn't work, or that it proves a weaker version of the theorem.

---
Tags: complexity-theory, complexity-classes, check-my-answer
---


title: Complexity of cubic graph decomposition

text:
# Question
Title: Complexity of cubic graph decomposition
I am aware that deciding the existence of decomposition of a cubic graph into edge-disjoint claws is polynomial time solvable. Since a cubic graph has a decomposition into edge-disjoint claws if and only if it is bipartite.

> What is the complexity of deciding the existence of decomposition of a cubic graph into vertex disjoint claws? Is it NP-complete?

In the former problem, we partition the edge set into edge-disjoint claws while in the later one we partition the vertex set into vertex-disjoint claws.

# Answer
> 2 votes
It turns out that the problem is eqivalent to the 1-perfect code problem in cubic graphs. Therefore, Deciding the existence of decomposition of a cubic graph into vertex disjoint claws is NP-complete.

---
Tags: complexity-theory, graphs
---


# Question
Title: Counting the solutions to a restricted 0-1 knapsack problem
Consider the counting knapsack problem $\mathsf{\\#IDKNAP}$ :

**Input**: $n \in \mathbb{Z\_+}$, $s \in \mathbb{Q}\_+$, where $s$ is represented by a fraction $\frac{p}{q}$ in its lowest terms.

**Output**: the number of 0-1 solutions (i.e. those having $s\_i\in \\{0,1\\}$) to $s\_1 + s\_2 + \dots + s\_n \leq s$.

> What is the counting complexity of $\mathsf{\\#IDKNAP}$?

Let $k := \lfloor s \rfloor$. The problem asks for the number of $n$-bit vectors with at most $k$ bits set to $1$. The solution is $\sum \limits\_{i=0}^k \binom{n}{i}$, for which there is no closed form in general, and thus cannot be computed in polynomial time in the input size.

So (I think) $\mathsf{\\#IDKNAP}$ would be either $\mathsf{NP~Hard}$ or $\mathsf{\\#P~Hard}$. It seems to be insufficiently general to encode arbitrary $\\#\mathsf{KNAPSACK}$ problems, which are $\mathsf{\\#P~Hard}$. On the other hand, $\mathsf{\\#IDKNAP}$ has exponentially less input size than general knapsacks, for which the weight vector $(w\_1,\ldots,w\_n)$ has at least $n$ bits.

# Answer
There are almost-matching lower and upper bounds for the running time of the best algorithm for this problem, considered as a function of $n$. In particular, we can prove that the complexity is $\Omega(n)$ and $O(\text{poly}(n))$, when considered only as a function of $n$.

For the upper bound, there's an algorithm whose running time is polynomial in $n$. Without loss of generality we can take $k \le n$ (for terms where $i\>n$ contribute nothing to the sum). Also you can compute ${n \choose i}$ in time polynomial in $n$. Therefore, the whole sum can be evaluated in time polynomial in $n$. In other words, it's solvable in pseudo-polytime.

The size of the output can be as large as $2^n$ (e.g., where $k=n$), so the output can take $\Theta(n)$ bits to represent. This is exponential in the size of the input. Thus, any algorithm for the problem must have worst-case running time at least $\Omega(n)$.
> 2 votes

---
Tags: time-complexity, knapsack-problems, counting
---


# Question
Title: What is the time complexity of generating n-th prime number?
Say I want to find the n-th prime. Is there an algorithm to directly calculate it or must I do with sieving? I know always calculate the next prime with a sieve principle, but what if I want the n-th prime?

Duplicate:

https://math.stackexchange.com/questions/1257/is-there-a-known-mathematical-equation-to-find-the-nth-prime

# Answer
What do you mean by "directly"? This is not well-defined. Arguing that an algorithm doesn't do something during its computation is not a nice well-defined concept (when that something is a semantic condition).

It is probably one of the most common mistakes that people make when thinking about algorithms because they look at obvious cases and think it is simple to formalize the concept that algorithms for a problem does performs some task like computing some other things during its computation but that is not simple at all!

Moreover why would we care? What we care about in practice is not that the algorithm computes all previous primes, but rather time and space efficiency. So I guess a better way of asking your question is asking if there is more efficient way of computing $n$th prime number than sieve-based methods.

If you are asking if there is a provably correct and efficient algorithm to find $n$th prime given $n$ in binary the answer is that is an open question. We don't know if there is any such algorithm, and we don't know if there isn't one. AFAIK, it is consistent with our current state of knowledge that there are algorithms for generating the $n$th prime that run in linear time in $n$. In fact, it can even be the case that we can generate the $n$th prime from bits of $n$ using a polynomial-size constant-depth circuit with threshold gates ($\mathsf{TC^0}$), in simplified non-technical terms: there can be a parallel algorithm with polynomial number of processors that generates the $n$th prime number in constant time and each processor computes very simple functions. So there is big gap between algorithms that we have (upper-bounds) and lower-bounds we can prove for the problem.

However we have algorithms that work efficiently and correctly assuming conjectures like conjectures about how primes are distributed.

See the Wikipedia article on generating prime numbers if you haven't. Also you may want to check this question: Which is the fastest algorithm to find prime numbers?
> 14 votes

# Answer
When $n$ is not big, then I think the sieve-based algorithms perform well. We just need to keep a list of size $O(n \log n)$ and run one of a well-known sieve-based algorithms for generating primes.

When $n$ is big and we can't afford to keep a list of size $O(n \log n)$, we can use an *in-place sieve method*. But I personally prefer to have a small list of primes and use Miller-Rabin test to iterate through possible primes.

The sieve-based algorithms are the most efficient algorithms we currently know for generating prime numbers.

It is not clear what you mean by generating $n$th prime "directly". If you mean that there is any known algorithms as fast as sieve-based algorithms for generating the $n$th prime number that doesn't compute the previous primes numbers then the answer is that we don't know any such algorithm.

If by "direct" you mean a polynomial in one variable that gives the $n$th prime number, then we can actually prove that there is no polynomial function with integer coefficient for calculating nth prime number. And even if there was such a polynomial the algorithms for evaluating polynomials use $\Omega(\log m)$ operations where $m$ is the power of the polynomial to be evaluated.

Note that although we have efficient algorithms for testing primality of a given number (e.g. AKS which is polynomial-time) they don't give an algorithm for finding primes.

P.S: Here you can find a good implementation of Miller-Rabin test, which can be extended to arbitrary large numbers.
> 4 votes

# Answer
The cop-out but realistic answer for small inputs would be $O(1)$ for tiny inputs and roughly $O(\log n)$ below some finite threshold as it can be done as a binary search through a table of primes. Since we can get good starting bounds it might be even smaller -- our search range is a small fraction of the table.

What is often done for medium sizes, say 100k to 100M, is sparse tables followed by sieving the range between entries. With enough entries the sieving doesn't take long, so the result is pretty fast and even 1k of tables plus a decent sieve takes you to 100M or so. It doesn't scale well however. I know one application that does this for large sizes at the expensive of ridiculous amounts of table storage, but was also done before open source implementations of the next paragraph were available.

Beyond these toy input sizes, we can do a binary search on the prime count. The extended LMO method is complexity $O\big(\frac{x^{2/3}}{\log^2{n}}\big)$. I believe that would come out to $O\big(\frac{x^{2/3}}{\log{n}}\big)$ for the nth prime. In practice typically one does a good approximation, a single call for the fast prime count, followed by sieving the remainder as this is typically an extremely small range and usually faster than a second prime count, much less $\log n$ of them.

As to your question of whether this can be done directly, the last paragraph gives a well-defined algorithm, so yes, but it isn't a closed form function. Calculating the nth prime by sieving to n works fine for small inputs, but is *massively* slower for large inputs. Even at just $10^{10}$, primesieve is about 2000x slower than the inverse fast prime count method, and the gap keeps widening.
> 1 votes

---
Tags: algorithms, primes
---


# Question
Title: How can I compute an exponential modulo a large integer?
Does anyone have the computational power to check whether or not

$F(m)^d \equiv m \pmod n$, where the values of the variables are found below.

According to Wolfram Alpha, I found the result of the computation $F(m) \equiv m^e \pmod n$, however I don't know how reliable Wolfram is with computations of this size and I am unable to compute $F(m)^d ≡ m \pmod n$ in Wolfram, since the numbers are too large.

m=112951412120151619251851615182016118201
n=145906768007583323230186939349070635292401872375357164399581871019873438799005358938369571402670149802121818086292467422828157022922076746906543401224889672472407926969987100581290103199317858753663710862357656510507883714297115637342788911463535102712032765166518411726859837988672111837205085526346618740053
d=89489425009274444368228545921773093919669586065884257445497854456487674839629818390934941973262879616797970608917283679875499331574161113854088813275488110588247193077582527278437906504015680623423550067240042466665654232383502922215493623289472138866445818789127946123407807725702626644091036502372545139713

What Wolfram says $F(m)$ is:
F(m)=22759056015886739716909089234835188351754889051525507970444538546831824365432006473081682583255424846673851966695239042380796121790409431507631093425
e=65537

# Answer
Modular exponentiation is a well-known algorithm. It is routinely available in libraries and languages that can manipulate large integers, including Wolfram Alpha.

When making computations modulo a large number, one does not first make the whole computation in $\mathbb{N}$ and then take the remainder of the result, because for something like an exponentiation the intermediate result would be exceedingly large. Rather, the result is calculated with reductions modulo $n$ at each step. The basic idea for exponentiation is to write down the exponent $d$ in binary, and proceed one digit at a time, with the rules $$ \begin{align\*} x^{2d} &= (x^d)^2 & \text{adding a binary digit \\(0\\) to the right of \\(d\\)} \\ x^{2d+1} &= (x^d)^2 \cdot x & \text{adding a binary digit \\(1\\) to the right of \\(d\\)} \\ \end{align\*} $$ All computations are multiplications modulo $n$, it is never necessary to make computations involving larger numbers. There are variations on this algorithm, including iterating over the digits of $d$ from right to left instead of left to right. The number of multiplications is at most twice the number of digits of $d$.

There are techniques to perform a multiplication $a \cdot b \pmod n$ without calculating $a \cdot b$ which could be as large as $(n-1)^2$, the most popular being Montgomery reduction. Multiplication modulo $n$ can be done in time $O(\ell^2)$ where $\ell$ is the number of digits of $n$; it follows that exponentiation modulo $n$ can be done in time $O(\ell^3)$.

You can easily verify whether the value of $F(m)$ computed by Wolfram Alpha satisfies the equation $F(m)^d \equiv m \pmod n$ by running the modular exponentiation algorithm. (Easily with a computer, not by hand, for numbers of this size.)

We've seen how to compute $m^d \pmod n$ knowing $m$, $d$ and $n$. Solving the equation $F(m)^d = m \pmod n$ where $F(m)$ is the unknown is a different matter. Computing the $d$th root modulo $n$ is a hard problem in general, for which the only known methods are exponential in $\ell$ in the worst case. The problem is tractable (i.e. has polynomial complexity) when $n$ is prime, or more generally given a factorization of $n$.

It is apparent given the notations and the value of $e$ that these numbers are an example of an RSA key pair. An RSA key pair is generated starting with a number $n$ of the form $n = p \cdot q$ where $p$ and $q$ are (probable) primes and with a number $e$ satisfying certain conditions that I won't go into here; the knowledge of the factorization of $n$ makes it easy to compute a number $d$ such that $\forall m, (m^d)^e \equiv m \pmod n$ and $\forall m, (m^e)^d \equiv m \pmod n$. (If the factorization of $n$ was not known, then finding $d$ given $n$ and $e$ or equivalently finding $e$ given $n$ and $d$ would be a hard problem: it would be literally breaking the RSA cryptosystem.)

Given this supplementary knowledge, the $d$th root of $m$ modulo $n$ can be computed with a tractable operation: exponentiation. The solution $F(m)$ is $m^e \pmod n$.

The Python programming environment provides a convenient way of making calculations on large integers.

```
% python
Python 2.7.3 (default, Mar 13 2014, 11:03:55)
[GCC 4.7.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> m=112951412120151619251851615182016118201
>>> n=145906768007583323230186939349070635292401872375357164399581871019873438799005358938369571402670149802121818086292467422828157022922076746906543401224889672472407926969987100581290103199317858753663710862357656510507883714297115637342788911463535102712032765166518411726859837988672111837205085526346618740053
>>> d=89489425009274444368228545921773093919669586065884257445497854456487674839629818390934941973262879616797970608917283679875499331574161113854088813275488110588247193077582527278437906504015680623423550067240042466665654232383502922215493623289472138866445818789127946123407807725702626644091036502372545139713
>>> e=65537
>>> pow(m,e,n)
141781201173392662619041096248902274075236734827860244551641082388116267289894721928886528279400665340976615948053755946789302972467196231829204061441862114262117040263042768989461016645192295451421289297123899909172989906731037919155114663997141846344255396618911673987467404521083471325973763420396488985050L
>>> pow(pow(m,e,n),d,n)
112951412120151619251851615182016118201L
>>> pow(pow(m,e,n),d,n) == m
True

```
> 12 votes

# Answer
I get a different number for $F(m)$. You can download `sage` and try for yourself.

> sage: power\_mod(112951412120151619251851615182016118201,65537,145906768007583323230186939349070635292401872375357164399581871019873438799005358938369571402670149802121818086292467422828157022922076746906543401224889672472407926969987100581290103199317858753663710862357656510507883714297115637342788911463535102712032765166518411726859837988672111837205085526346618740053) 141781201173392662619041096248902274075236734827860244551641082388116267289894721928886528279400665340976615948053755946789302972467196231829204061441862114262117040263042768989461016645192295451421289297123899909172989906731037919155114663997141846344255396618911673987467404521083471325973763420396488985050

With this value of $F(m)$, the other computation checks out:

> sage: power\_mod(141781201173392662619041096248902274075236734827860244551641082388116267289894721928886528279400665340976615948053755946789302972467196231829204061441862114262117040263042768989461016645192295451421289297123899909172989906731037919155114663997141846344255396618911673987467404521083471325973763420396488985050,89489425009274444368228545921773093919669586065884257445497854456487674839629818390934941973262879616797970608917283679875499331574161113854088813275488110588247193077582527278437906504015680623423550067240042466665654232383502922215493623289472138866445818789127946123407807725702626644091036502372545139713,145906768007583323230186939349070635292401872375357164399581871019873438799005358938369571402670149802121818086292467422828157022922076746906543401224889672472407926969987100581290103199317858753663710862357656510507883714297115637342788911463535102712032765166518411726859837988672111837205085526346618740053) 112951412120151619251851615182016118201
> 0 votes

# Answer
In Mathematica, you can use the PowerMod\[\] function to compute the modulo n power raise to the large power d. I agree with each of the two prior posts that the value of F = m^e mod n from Wolfram Alpha was incorrect.

```
In[30]:= F = PowerMod[m, e, n]

Out[30]= 1417812011733926626190410962489022740752367348278602445516410\
8238811626728989472192888652827940066534097661594805375594678930297246\
7196231829204061441862114262117040263042768989461016645192295451421289\
2971238999091729899067310379191551146639971418463442553966189116739874\
67404521083471325973763420396488985050

In[31]:= PowerMod[F, d, n]
Out[31]= 112951412120151619251851615182016118201

In[32]:= PowerMod[F, d, n] - m
Out[32]= 0

```
> 0 votes

---
Tags: arithmetic, multiplication, modular-arithmetic
---


# Question
Title: Can a second process execute when the Operating System is performing a context switch?
A process was running on a uniprocessor system. It is being context switched. While the scheduler is performing this context switch can another process be allocated the CPU while the context switch is being performed?

# Answer
> 2 votes
(1) First, lets define our terms. From Wikipedia:

> In computing, a context switch is the process of storing and restoring the state (more specifically, the execution context) of a process or thread so that execution can be resumed from the same point at a later time.

In other words, a context switch is the act of transfering control from one process to another. To recall the current process, the CPU has to take a snapshot of its state before allocating resources to the new process.

(2) Now let's answer exactly what get's saved. Also from Wikipedia:

> registers and memory maps, updating various tables and lists, the PC, stack pointer, *etc.*

So, pretty much everything in the CPU needs to be stored somewhere else before loading in a new process' state.

---

Now let's consider your question by reasoning about two arbitrary processes, **PID 1** and **PID 2**

PID 1 is preparing to hand the CPU to PID 2 and begins storing its state. Thus, all critical CPU elements are in use. One by one as these elements are stored, they are freed (often the timing is more complex) and the CPU can allocate those resources to PID 2.

Squeezing in an extra process would just cause overhead in the primary context switch between PID 1 and PID 2. You might even consider it a context switch inside of a context switch for any *nontrivial process*. Sure, if the ALU is open, it could probably do a quick calculation or two but what good would those results do when not a part of a process which is far more than just a few calculations?

---

Theoretically possible? Sure. Reasonable, NO. Instead of trying to use that time "lost" during a context switch, innovations focus on classifying different degrees of context switches. Basically, if you have a lightweight switch between a process, or perhaps a thread, the entire processor is not held up while doing so. For more reading, I suggest: https://en.wikipedia.org/wiki/Light-weight\_process to see the difference in process types.

Clarification: The scheduler is a kernel space process.

# Answer
> 1 votes
The scheduler is *using the CPU* to perform the context switch, it is not something that is happening somewhere else, so the CPU is busy in doing the context switch and that means nothing else not even a process can do anything in the mean time.

The confusion seems to stem from the fact that we think CPU as a resource, much like other resources like memory and IO devices. Then we say that a process "uses" these resources to perform the desired operations. This way of saying things make it look like process are "real" things on their own and do stuff using resources, like a person uses different tools. This way of looking at things is just at a specific layer of abstraction. If you look at the hardware you will find that there is no thread OR process or all these abstract objects. There is only CPU and other hardware components and as soon as you switch on the system the CPU starts fetching stream of instructions and execute them. From this point of view there is no process, kernel or thread.

---
Tags: operating-systems
---


# Question
Title: Why is the minimum height of a binary tree $\log_2(n+1) - 1$?
In my Java class, we are learning about complexity of different types of collections.

Soon we will be discussing binary trees, which I have been reading up on. The book states that the minimum height of a binary tree is $\log\_2(n+1) - 1$, but doesn't offer further explanation.

Can someone explain why?

# Answer
> 12 votes
A binary tree has 1 or 2 children at non-leaf nodes and 0 nodes at leaf nodes. Let there be $n$ nodes in a tree and we have to arrange them in such a way that they still form a valid binary tree.

Without proving, I am stating that to maximize the height, given nodes should be arranged linearly, i.e. each non-leaf node should have only one child:

```
                              O 1
                              |
                              O 2
                              |
                              O 3
                              |
                              O 4
                              |
                              O 5
                              |
                              O 6
                              |
                              O 7
                              |
                              O 8

```

Here, formula to compute relation of height in terms of number of nodes is straight-forward. If $h$ is the height of the tree, then $h = n-1$.

Now, if we try to construct a binary tree of $n$ nodes with minimum height (always reducible to a complete binary tree), we have to pack as many nodes as possible in upper levels, before moving on to the next level. So, the tree takes the form of following tree:

```
                              O
                              |1
                              |
                       O------+-----O
                       |2           |3
                       |            |
                   O---+---O    O---+----O
                   |4      |5    6        7
                   |       |
               O---+--O    O
                8      9    10

```

Let us start with a particular case, $n = 2^m - 1$.

We know that, $$ 2^0 + 2^1 + 2^2 + ... + 2^{m-1} = 2^m - 1 $$

Also, it is easy to prove that, a level $i$ can have at most $2^i$ nodes in it.

Using this result in the above sum, we find that for each level $i$, from $0$ to $m$, there exists a corresponding term $2^{i-1}$ in the expansion of $2^m - 1$. This implies, that a complete binary tree $2^m - 1$ nodes is completely filled and has height, $h(2^m-1) = m-1$, where $h(n) = $ height of a complete binary tree with $n$ nodes.

Using this result, $h(2^m) = m$, since tree with $2^m-1$ nodes is completely filled and thus a tree with $(2^m-1)+1 = 2^m$ nodes has to accomodate the extra node in the next level $m$, increasing the height by 1 from $m-1$ to $m$.

Until now we have proved, $$h(2^m) = m,$$ $$h(2^{m+1}) = m+1$$ as well as, $$h(2^{m+1} -1) = m$$

Thus, $\forall n \in \mathbb{Z}, 2^m \leq n \< 2^{m+1}$ $$m \leq h(n) \< m+1$$

But, taking log (base 2) on both sides, $$m \leq \log\_2(n) \< m+1$$ $$m = \lfloor \log\_2(n) \rfloor$$

Thus, $\forall n, n \in \[2^m, 2^{m+1})$ $$h(n) = m = \lfloor \log\_2(n) \rfloor$$

And we can generalize this result $\forall n \in \mathbb{Z}$ using induction.

PS: The book that states height of a complete binary tree as $\log\_2(n+1)-1$ is not valid for all $n$ because $\log\_2(n)$ would give non-integral values for most integers $n$ (i.e. for all but perfect binary trees), but height of a tree is purely integral.

# Answer
> 20 votes
I'm assuming that by $n$, you mean the total number of nodes in the binary tree. The height (or depth) of a binary tree is the length of the path from the root node (the node without parents) to the deepest leaf node. To make this height minimum, the tree most be fully saturated (except for the last tier) i.e. if a specific tier has nodes with children, then all nodes on the parent tier must have two children.

So a fully saturated binary tree with $4$ tiers will have $1+1\cdot2+1\cdot2\cdot2+1\cdot2\cdot2\cdot2$ nodes maximum and will have a depth of $3$. Thus if we have the depth of a binary tree, we can very easily find the maximum number of nodes (which occurs when the tree is fully saturated). If you recall from your algebra classes this is just a geometric series and can therefore be represented like this:

$$ \text{nodes}=1+2+2^{2}+2^{3}+...+2^{\text{depth}}=\sum\_{k=0}^{\text{depth}} 2^{k}=\frac{1-2^{\text{depth}+1}}{1-2}. $$

So let's rearrange: $$ \text{nodes}=2^{\text{depth}+1}-1, $$ then solve for the depth: \begin{eqnarray} \text{nodes}+1&=&2^{\text{depth}+1}\\ \log\_{2}(\text{nodes}+1)&=&\log\_{2}(2^{\text{depth}+1})=\text{depth}+1\\ \log\_{2}(\text{nodes}+1)-1&=&\text{depth}. \end{eqnarray} and there's your formula. Now keep in mind this only yields integer values when the every tree is completely filled up (a 'perfect' binary tree) so if you get a non-integer value, remember to round up.

# Answer
> 4 votes
To keep the height minimum, it is easy to see that we need to fill all the levels except possibly the last. Why? otherwise, we could just move up the last level nodes into empty slots in the upper levels.

Now, imagine that I have some unspecified number of beans and I give you one bean at a time and ask you to construct a binary tree with minimum height possible. I might run of out beans by the time either you filled up the last level completely or at least have one bean in the last level. Let us say, you have your tree height *h* at this point.

In either case, *h* doesn't change. So which means you have a complete binary tree of height *h* with my constraint. But I assumed imaginary beans in the last level (if you couldn't fill the last level). So it is actually, $$ 2^{0}+2^{1}+2^{2}+2^{3}+\dots+2^{h}=2^{h+1}-1 \leq n\\,. $$ So minimum $$h = \lg(n+1)-1\\,.$$ But apply ceiling since we are adding imaginary beans and not deleting them.

---
Tags: data-structures, binary-trees, discrete-mathematics, trees
---


# Question
Title: Number of ways an integer $n$ can be split into a product of $k$ distinct integers given a prime factorization
What is the best algorithm for computing the number of ways an integer $n$ can be split into a product of $k$ *distinct* integers given a prime factorization $n=p\_1^{a\_1}p\_2^{a\_2} \ldots p\_i^{a\_i}$?

Clearly, there are simple exponential time algorithms, but I'm wondering if any algorithms polynomial in $\log n$ are known, or at least polynomial in $i + \max \\{a\_j | 1 \leq j \leq i\\}$. I was thinking along the lines of Yuval Filmus's answer, but could not make it work for the distinct integer case in polynomial time.

# Answer
> 2 votes
I'll show how to solve the case $k=2$ and without the constraint that all factors have to be distinct, and let you generalize and take care of the constraint. Each decomposition corresponds to a choice of non-negative integers $b\_1,c\_1,b\_2,c\_2,\ldots,b\_i,c\_i$ such that $a\_j = b\_j + c\_j$. The number of such decompositions is thus $(a\_1+1)\cdots(a\_i+1)$.

There might be a slight problem with that, depending on what you mean by *decomposition*. Consider for example $n=2$. According to the count above, we get the two decompositions $1 \cdot 2$ and $2 \cdot 1$. Perhaps we want to count them as the same decomposition. In this case, we need to roughly divide the count above by 2. Why only roughly? Since if $n = m^2$, then the decomposition $n = m \cdot m$ only appears once. So if $n$ is a square, we need to divide the count above by 2, and add 1/2 (why?).

If we want to count the number of decompositions in which both factors are distinct, we need to check whether $n$ is a square, and then adjust our counts accordingly. Details left to the reader.

For general $k$, if you are OK with ordered decompositions (and ignoring the constraint that all factors be distinct), then all you need do is figure out how many non-negative integer solutions exist for the equation $a = b\_1 + \cdots + b\_k$. If you care about unordered decompositions (so $1\cdot 2$ and $2\cdot 1$ are considered the same) or require all factors to be distinct, you have more work to do. Inclusion-exclusion type formulas could be helpful.

---
Tags: number-theory, counting
---


# Question
Title: If set membership problem can be solved for a particular language does this imply that the language is regular?
If we know that a language is regular, we can solve the set membership question for a given string by running it through the corresponding DFA for that language. But what about the other way? Means, if set membership question can be solved for a particular language does this imply that the language is regular?

# Answer
Since any irregular, but decidable language answers the question with "no, there are irregular languages that are decidable", maybe some nuance for how this relates to the usual complexity classes.

For one thing, every regular language has at most linear time complexity (just use a DFA that recognizes the language and run the word on it and check whether you end up in an accepting state). Therefore, the deterministic time hierarchy theorem implies that there are languages that are decidable, but irregular, since it implies that the set of languages that, say, require at least quadratic but at most cubic time is nonempty; similarly for languages that require $\Theta(2^{2^{2^n}})$ time. On the other hand, there are irregular languages that have linear time complexity, as illustrated by the example $\\{a^nb^n : n \in \mathbb{N}\\}$ that David gave.

Another surprising thing I became aware of only recently is that SAT, the NP-complete problem of deciding whether a CNF formula is satisfiable, is context-sensitive. To see this, remember that the automata recognizing context-sensitive languages are the linear bounded automata, which are nondeterministic Turing machines that are only allowed to use the space used for the input (or alternatively, only use linearly much additional space - using a speedup theorem, those definitions should be equivalent); here are references on the matter.

And finally, a restricted version of the question ("does NP-completeness imply regularity?") can be answered by "no, there are irregular languages that are NP-complete". If P=NP, then all irregular languages that can be decided in polytime are NP-complete (since the reduction has all the power required for deciding any NP-problem, and so reductions always work), and if P$\neq$NP, then all NP-complete languages are irregular: if they weren't, then there would be a regular language that is NP-complete, but regular languages can be decided in linear time, contradicting P$\neq$NP.

So to sum up: decidability doesn't tell you much about where in the complexity zoo we are, and even knowing a language can be solved in linear time doesn't tell you anything about regularity. On the other hand, irregularity doesn't tell you much about time complexity either (maybe that implies that the language requires at least linear time - but I can't prove that off the cuff, not sure it's true!).
> 7 votes

# Answer
No. The language is only regular if its set membership problem can be decided by a DFA. For example, the set membership problem of the language $\\{a^nb^n\mid n\geq 0\\}$ can be solved but this language is known not to be regular (e.g., by the pumping lemma).

Thanks to reinierpost for pointing out that this is way simpler than I was originally making it, and for persisting when it took me multiple hours to understand that.
> 5 votes

---
Tags: computability, regular-languages, automata
---


# Question
Title: How do Quantum Computers destructively interfere the wrong answer?
From various sources (one being this), I've heard that quantum computers find the correct answer in a sea of possible ones by destructively interfering the wrong ones with each other, and the right one keeps building on itself. How does this work? Does every wrong answers have an opposite, but still wrong, answer? How can the correct answer not? Or am I completely misled here?

Thanks

EDIT: This question differs form this because an answer to my previous question tells me about quantum interference to solve this problem, but does not explain how, and neither does the links.

# Answer
> 2 votes
It depends very strongly on the problem being solved. Some graphs are very amenable to quantum random walks; others aren't. Some operations work well with quantum phase estimation, but that technique isn't so useful for understanding what a black box is doing.

Grover's algorithm works based off of the fact that you can negate every amplitude in a system across the average of all the amplitudes. The amplitude of solutions is pushed away from the global average, and towards high values, by negating the phase of solutions (e.g. by conditioning on a predicate) before each average-flip.

---
Tags: quantum-computing
---


# Question
Title: Approximating sign function by tanh in Multi Layer perceptrons
This is an exercise problem from the book "Learning from Data".

Given $w\_1$ and $\epsilon \gt 0$, find $w\_2$ such that, $$\lvert \mbox{sign}(w\_1^Tx\_n)-\tanh(w\_2^Tx\_n)\rvert \le \epsilon$$ Where $w\_1, w\_2, x\_n$ are all real vectors.

I know that for large $y$, $\mbox{sign}(y) \approx \tanh(y)$. But I am unable to proceed. Any help would be appreciated.

Thanks

# Answer
Here's one solution. The central insight is that your error becomes exponentially smaller as $w^tx$ increases. In particular, $1-tanh(x)$ approximates $1$ exponentially fast. That is, for positive $x$:

$$\frac{1-tanh(x)}{1-tanh(x+1)} \geq \frac{tanh(0)}{tanh(1)} \approx 4.19\ldots = \alpha$$

In fact, its asymptote is at $e^2$. I didn't know that, but Wolfram Alpha did. You can use this fact to estimate your error. Let $\tau = sign(w\_1^Tx)$ be the target, and let $E(w\_2^Tx)=|\tau-tanh(w\_2^Tx)|$ be the error. Figure out a weight vector $w$ that will give you $w^Tx=1$. Then $E(kw^Tx) \geq \alpha \cdot E((k+1)w^Tx)$ for any positive number $k$, because of the exponential improvement we just discovered. This is great; now we've reduced our problem to finding a good $k$. We know that for $k=0$, your estimate is $tanh(0)=0$ so $E(0)=1$, and every time you increment $k$ by $1$, your estimate becomes at least $\alpha \approx 4.19$ times as good. So, we solve the following simple equation:

$$\frac{1}{\alpha^k} \leq \varepsilon, \quad\text{so} \quad k \geq \ ^\alpha log\left(\frac{1}{\varepsilon}\right)$$

Hope this helps.
> 3 votes

---
Tags: neural-networks
---


# Question
Title: Is non-determinism in a non-deterministic turing machine different from that of finite automata and push down automata?
Let a input string be given as $w\_1w\_2...w\_n$. Then if a NFA is currently in state $r$ ( and has read the input upto alphabet $w\_i$ ) then before reading the next input symbol the NFA splits into two NFA, one being in state $r$ and other being in $s$, if there is a transition of the type $r \xrightarrow{\epsilon} s$. If there is a cycle of the type $r \xrightarrow{\epsilon} s \xrightarrow{\epsilon} q\_1....\xrightarrow{\epsilon} q\_k \xrightarrow{\epsilon} r$, where $q\_i$ are some states of NFA, then it's no use remembering another NFA in state $r$ upto the point where input has been read till alphabet $w\_i$.
If a PDA ( non-deterministic ) is in state $r$ ( and input is read till $w\_i$ ) and there exists a cycle $r \xrightarrow{\epsilon,\epsilon \to a} s \xrightarrow{\epsilon,\epsilon \to a} q\_1....\xrightarrow{\epsilon,\epsilon \to a} q\_k \xrightarrow{\epsilon,\epsilon \to a} r$ ( where transition $\epsilon,\epsilon \to a$ means thatnothing after $w\_{i}$ is read from input, nothing is popped or read from stack and alphabet $a$ is pushed onto the stack ) then before reading the next input alphabet $w\_{i+1}$ there will be infinite PDA in states $r,s,q\_1,...q\_k$ because unlike the NFA although the states are finite stack contents can be different ( infinite possibilities ), if I am not wrong.

As with NFA and PDA the power of non-determinism comes from $\epsilon$ transitions. So I assume that non-deterministic Turing machine also gets it's non-determinism from $\epsilon$ transitions like NFA and PDA ( more like PDA ). I know that a deterministic Turing machine can simulate a non-deterministic one ( I know the proof which uses bread-first search ). But now I am doubtful as to how that is possible. Because if a cycle of the type in PDA above, exists in the state diagram of the non-deterministic Turing machine then before reading the next symbol $w\_{i+1}$ the deterministic Turing machine even when simulating a configuration in some branch of non-deterministic Turing machine ( while bfs ) would have to keep track of infinite Turing machine ( again the states are finite but the symbols on the tape have infinite possibilities ).
So how exactly non-determinism in defined in case of Turing machines ? Am I misunderstanding something trivial ? Do non-deterministic Turing machines use $\epsilon$ transitions ?

I am sorry for my trivial doubts. If anything is incorrect I can update my question.

# Answer
Non-determinism is the same concept in all contexts – the machine is allowed several options to proceed at any given point. However, the semantics are a bit different since DFAs/NFAs and PDAs always define *total* functions, while Turing machines (deterministic or non-deterministic) in general define *partial* functions.

A partial function is one defined only on part of the domain. If $f$ is not defined on $x$ then we write $f(x) = \bot$. (So $f$ is really a total function, but there is a special element in the range signifying that the output is undefined.) A deterministic Turing machine $M$ defines a partial function as follows: if $M$ halts on $x$ then $M(x)$ is the contents of the tape when $M$ halts on $x$; and otherwise, $M(x) = \bot$.

A deterministic Turing machine *decider* has two kinds of halting states, accepting and rejecting, and defines a partial function as follows: if $M$ halts on $x$ at an accepting state, then $M(x)=1$; if it halts at a rejecting state, then $M(x)=0$; if it doesn't halt, then $M(x)=\bot$. If $M$ always halts then we say that it *accepts* the language $L = \\{x : M(x) = 1\\}$.

A non-deterministic Turing machine (which is always a decider) is allowed to "branch" (have several possible options at any given point in time), and has the following semantics:

* $M(x) = 1$ if on input $x$, the machine $M$ halts on all branches, halting at an accepting state for at least one branch.
* $M(x) = 0$ if on input $x$, the machine $M$ halts on all branches, always halting at a rejecting state.
* $M(x) = \bot$ if on input $x$ there exists a branch on which $M$ doesn't halt.

Given this definition, it is hopefully clear how to simulate a non-deterministic Turing machine using a deterministic Turing machine decider: you try all branches, checking whether any of them leads to an accepting halting state. After all branches have halted, you can decide whether to go to an accepting state or to a rejecting state. If the non-deterministic Turing machine doesn't halt on some branch, then so would the deterministic one.

---

What about $\epsilon$-moves? They cause trouble in that the corresponding automaton might never halt. *For finite automata (NFAs and PDAs) we silently ignore non-halting computations.* Our reason for doing that is that the resulting languages are always computable, even though the naive algorithm for simulating them deterministically (simulating all computation paths) doesn't quite work. This is not so difficult for NFAs, which can be converted to DFAs. However, deterministic PDAs are strictly weaker than non-deterministic PDAs. Nevertheless, you can show that every PDA is equivalent to one without $\epsilon$-transitions (though the proof might go through context-free grammars).

You can simulate $\epsilon$-moves in Turing machines, but you have to be careful that there are no loops which cause non-halting computations. In some cases, however, we can use the same trick as above. For example, suppose that your Turing machine is space-constrained: we know an upper bound on the space that it uses (depending on the input length). In that case every non-halting computation necessarily cycles (since the Turing machine has finitely many states, including the tape contents), and so if we "ignore" non-halting computations as above, the resulting model of computation is still computable. More generally, this works as long as we are guaranteed that every non-halting computation cycles. (This is the case for NFAs but not for PDAs.)
> 9 votes

---
Tags: turing-machines, finite-automata, pushdown-automata, computation-models, nondeterminism
---


title: Proving non-regularity of $u u^R v$?

text:
# Question
Title: Proving non-regularity of $u u^R v$?
This particular language:

$$L = \\{ u u^R v \\,:\\, u, v \in \\{0, 1\\}^+\\}$$

is giving me a lot of trouble. I highly suspect that its non-regular, considering that $\\{ u u^R : u \in \\{0, 1\\}^+\\}$ is non-regular, and I can't seem to reason out a DFA for it.

However, trying to achieve a contradiction with the pumping lemma is giving me a *lot* of trouble. because of the arbitrary $v$ in the construction. In particular, if the string starts with $00$ or $11$ it is automatically in the language because we can pick $v$ as the remainder and the first two characters are trivially the reverse of each other.

Issues like this seem to thwart my every attempt at applying the pumping lemma. With $p$ as the pumping length, I tried something like $(01)^p (10)^p 1$ but you can simply pump up the starting character to obtain a string that starts with $00$ (and pumping down also works), so this string doesn't work for contradicting the pumping lemma.

I'm pretty stuck on ideas for strings that will contradict the pumping lemma, so I could appreciate a hint on the problem. (Perhaps it *is* regular? That's still in the back of my mind too)

# Answer
You can also use another approach: suppose that your language $L$ is regular; then you can intersect it with another regular language:

$L\_R = (01)^\* (10)^\* 1$

and - by the closure properties of regular languages - you get another regular language:

$L' = L \cap L\_R = \\{ (01)^n\\,(10)^m1 \mid m \geq n \> 0 \\}$.

Now it is easier to prove that $L'$ is not regular using the pumping lemma (just pick $n = p$, the pumping length), leading to a contradiction.
> 3 votes

# Answer
When you are stuck in a place like this, it pays to check if the method can work at all. That is, try to prove the opposite. Since the Pumping lemma does not characterise REG, this is actually possible.

*Claim:* Your language $L$ fulfills the conditions of the Pumping lemma with $p=1$.

Let $w = uu^Rv$ for $u, v \in \Sigma^+$; say $|w|=n$ and $|u|=m$. With the (canonical) notation from the Pumping lemma, pick $x = \varepsilon$, $y=w\_1$ and $z = w\_2\cdots w\_n$.

By definition, $|y| \geq 1$ and $|xy| \leq p$. Furthermore,

* $xy^0z = (u\_2\cdots u\_m) \cdot (u\_2\cdots u\_m)^R \cdot u\_1 v \in L$,
* $xyz = w \in L$, and
* $xy^iz = u\_1 u\_1^R (u\_2 \cdots u\_m) u^R v \in L$, for $i \geq 2$.

Q.e.d. -- $L$ has the Pumping property.

That is, the Pumping lemma *can not* be used here, you need other methods.
> 5 votes

# Answer
Use the Myhill–Nerode criterion instead. I claim that the words $(01)^n$ for $n \geq 1$ are pairwise indistinguishable. Indeed, consider $(01)^n$ and $(01)^m$, where $n \> m$. Clearly $(01)^m(10)^m0$ is in your language. I claim that $(01)^n(10)^m0$ isn't. If it was, then we could write $(01)^n(10)^m0=uu^Rv$ for non-empty $u,v$. Note that the two symbols at the center of $uu^R$ are either $00$ or $11$. Neither cases can happen since the occurrences of $11$ and $00$ lie to the right of the center of $(01)^n(10)^m0$.
> 4 votes

# Answer
Use closure properties. Assume $L$ is regular. Take the regular language $L\_R = (0 1)^\* (1 0)^\* 1 1$, the language $L \cap L\_R = \\{ (0 1)^n (1 0)^n 1 1 \colon n \ge 1\\}$ is also regular. Consider the homomorphism:

$\begin{align} h(a) &= 0 1 \\ h(b) &= 1 0 \\ h(c) &= 1 1 \end{align}$

then you have that $h^{-1}(L \cap L\_R) = \\{a^n b^n c \colon n \ge 1\\}$ is again regular. Now use the homomorphism:

$\begin{align} g(a) &= 0 \\ g(b) &= 1 \\ g(c) &= \epsilon \end{align}$

and so $g(h^{-1}(L \cap L\_R)) = \\{ 0^n 1^n \colon n \ge 1\\}$ is regular. But this last one is the canonical example of a non-regular language, so our assumption that $L$ is regular is wrong.
> 2 votes

---
Tags: formal-languages, pumping-lemma
---


# Question
Title: What is the relation between universality and chaotic behavior in Elementary Cellular Automata?
So i know that rule 110 from Elementary Cellular Automata is universal but i am wondering if we had other chaotic behaviors let's say there exists a system that shows nearly infinite chaotic behaviors {a structure at a time} similar to ECA structures, how can we prove or disprove universality from that system ?

Suppose we have a system with one specific rule to execute and the input can be defined by different number of cells {i.e input = 5 cells} these 5 cells for example can show (2000) chaotic behavior... 4 cells can show nearly (1800), for example to get a structure from the (1800) structures, i can change the 4 cells by changing the rule set of these 4 cells just like in ECA =\> 'two white cells will result in a black cell', i can define a similar rule set on the 4 cells, 5 cells or more generally on x cells where x \< infinite.

That system with same input {4 cells} with different rule set can simulate most of the structures in Elementary Cellular Automata like rule 30, 90 & 60 and others, what can be proved about such system and how universality is related to it ?

# Answer
Chaotic behavior does not seem to imply universality, from what I can see. I don't see any reason to expect it would.

For instance, here's an example to challenge your intuition that the two concepts are somehow related. Wikipedia lists the dynamic system given by the map $x \mapsto 4x (1-x)$ and $y \mapsto x + y \bmod 1$ as an example of a chaotic system. However I doubt that this system is universal in any meaningful sense.

As David Richerby wrote, the way you prove universality is "by proving that the thing can simulate some other universal system". I don't think "chaotic behavior" -- whatever that might mean -- is a helpful guide to determining whether a particular system is universal.
> 3 votes

---
Tags: complexity-theory, computability, cellular-automata
---


title: use of C library in operating systems

text:
# Question
Title: use of C library in operating systems
I wonder, how is that operating systems make use of libraries as stdio.h if they themselves are the services? I am right? Is the operating system that interacts with the hardware to operations of I/O? How you write to a file system with the C library, for example?

# Answer
The kernel of the system doesn't use the C library (at least not it's I/O facilities).

The kernel does offer *system calls* like `read(3)` and `write(3)` in Unix, and translates them into whatever magic the underlying hardware requires to do this. For example, as a *very rough* description of how this goes, to write to a serial port, the kernel copies the individual bytes to the serial port's register, signals that a new character is ready to transmit, and waits for it to be shipped off before placing the next one there. To write into a file the kernel keeps track of where the writing to the file has to take place, asks for space in the underlying device if the file will grow, and writes into the allocated space. Each filessystem has its own (rather complex) data structures on disk and in memory to keep track of free and allocated space, and so on. To manipulate it (and the underlying blocks on disk) usually another complex layer talking to the hardware is interposed.

Thus one way of looking at an operating system kernel is as a huge library offering nifty functions (system calls) that allow the programmer to access complex, even under the hood radically different functionalities, by a simple interface. That the programmer uses the convenience of the standard C library, some other language's library, or even chooses to write the system calls directly in assembler, is irrelevant.

The kernel does write messages on occasion. For this it has internal functions (in the case of e.g. Linux it is `printk` that mimics `printf(3)`) to do this by tickling the underlying hardware the right way.
> 3 votes

# Answer
The C language standard has provisions for *hosted* and *freestanding* runtime environments and makes clear which language features are required for each. Hosted environments are required to provide the standard C library, freestanding environments are not. Operating system kernels and embedded systems are typically built for freestanding environments and so do not use the standard libraries at all.

Note that the hosted vs. freestanding division relates primarily to libraries. As mentioned in this stackoverflow question macros defined in some header files are still usable in freestanding implementations.
> 3 votes

---
Tags: operating-systems, c
---


# Question
Title: Feasible to apply image "interlacing" concept to video streaming for smoother buffering?
The current state of video buffering technology is to encode a video multiple times at different resolutions, then when your network speed changes you change which video you are buffering from.

Would it be possible to give this same user experience but implement something like the interlacing method used in PNGs or in progressive JPGs (Adam7 algorithm or similar) to make this work more efficiently?

The basic concept would be that the video is encoded once, at its highest possible quality. Then as your network speed changes you can only download a certain percent of a frame each second. Since the data would be interlaced you would see a lower quality frame from not having enough bandwidth to download it all in a timely fashion.

This would be particularly interesting to see used in video calls so that the video can't stutter, just get worse in quality.

# Answer
Such a concept exists, for example in MPEG-4 Scalable Video Coding. It's complicated, it comes at a cost in coding efficiency (quality/bitrate), and I don't know of anything that supports it. However it's an area of active research and it might be the way of the future. Given the *current* state of the art, it's a lot more practical just to do multiple transcodes, segment, and switch between them.
> 3 votes

---
Tags: algorithms, data-structures, computer-architecture
---


# Question
Title: Is there any strategy to brute force search?
I don't know how to state it elegantly, but basically, I want to implement a brute force search algorithm, but there are many different ways that I could enumerate through the search space. This might be naive of me, but I imagine that how I choose to enumerate through the search space could greatly affect whether or not my algorithm works well in practice.

Consider the following decision problem as a simplified example.

**Input:** A polynomial $p(x)$ with integer coefficients and a natural number $k$.

**Question:** Does there exist $i \in \[k\]$ such that $p(i) = 0$?

Now, there could be many different algorithms for solving this problem, but I decide to choose a brute force approach. Consider the following strategies for enumerating through the search space.

**Ascending Strategy:** I could check if $p(1)$ is 0, then $p(2)$, then $p(3)$, ..., until I find an $i$ such that $p(i) = 0$ or I try every $i \in \[k\]$.

**Descending Strategy:** I could check if $p(k)$ is 0, then $p(k-1)$, then $p(k-2)$, ..., until I find an $i$ such that $p(i) = 0$ or I try every $i \in \[k\]$.

**Popularity Strategy:** I could store a small list $L$ of most popular solutions and try those first before trying the numbers in $\[k\] - L$.

**Sieve Strategy:** I could do a sort of sieve enumeration. I try all numbers divisible by 2 in $\[k\]$, then numbers divisible by 3 in $\[k\]$, then 5, then 7, then 11, then 13, and so on. (Assuming that I have access to some large pre-computed list of primes.)

**Randomness Strategy:** Maybe there is an interesting enumeration strategy that utilizes a large string of random bits.

Basically, I'm looking to answer the following questions about brute force search algorithms:

**Question A:** Are there any benefits to choosing a specific enumeration strategy?

**Question B:** Are there any examples of search problems where in practice you would choose an interesting enumeration strategy? I feel like there may be some search problems where in practice a variant of the Popularity Strategy works effectively.

# Answer
> 5 votes
The answer to both of your questions is yes! Definitely, even though in the worst-case you will have to enumerate the whole search space with brute-force (to prove there is no solution), it absolutely makes sense to consider *how* you traverse the search space. In general, you will find *a lot* of literature and discussion on the topic from the field of AI, and in particular e.g. SAT/CSP solving. A quick and gentle introduction is given by the Russell and Norving book.

I like using the Sudoku puzzle as an example. To decide whether a partially filled puzzle has a solution, you can exhaustively check every possible way of completing it. The naive approach is a blind backtracking search. This is extremely wasteful. A better idea is this: for the next cell to assign to, always pick the one with the fewest legal values. In general, this is a "fail-first heuristic", and the intuition is that this choice is most likely to fail soon, and it thereby prunes the search tree aggressively. There is actually a known "wisdom" in the field: "to succeed, you must fail quickly". Roughly, the sooner you fail, the faster you get to concentrate your effort on the hard part of the problem.

It might seem like the above is very problem specific, and only applies to say Sudoku puzzles. Fortunately, this is not the case. It is quite helpful to model your problem, or try to you see your problem, as e.g. a SAT/CSP instance. Then you can immediately apply known tricks to speedup your brute-force, devise better heuristics, and so on. Of course, you might do several magnitudes better by using a good CSP/SAT-solver instead of brute-force. This is beneficial even if nothing considerably better than brute-force is known for your problem. This is due to the fact that instances tend to have structure that is exploitable by smart solvers, and it is difficult to detect the same structure yourself with e.g. brute force.

An older answer of mine gives a bit more concreteness. I think every strategy you mention has been experimented with, most notably randomness. For instance, random restart strategies are very powerful, and are in use in modern solvers.

# Answer
> 3 votes
Brute forcing can indeed be somewhat improved by heuristics, based on some knowledge of the problem at hand.

There is no universal strategy that can work anywhere, especially if it is a blind one (independent of the history of outcomes for different trials). Moreover, there are probably problems elusive of any strategy.

An example of a heuristic strategy is simulated annealing, where you assume that the better solutions you find, the closer you are to the optimum. Such a property may not hold at all for other questions.

**Question A**: no, there is no general strategy to be applied blindly.

---
Tags: algorithms, search-algorithms, decision-problem, np, search-problem
---


# Question
Title: Why are transcendental functions of large numbers inaccurate on computers?
For instance, why is it hard to accurately compute sin(1e99)? I suspect it has something to do with rounding error.

# Answer
There's nothing fundamentally hard about computing $\sin(10^{99})$. You simply compute $x = 10^{99} \bmod 2\pi$, then compute $\sin(x)$. (Why is this valid? It's because $\sin(x)=\sin(y)$ if $x\equiv y \pmod{2\pi}$.) It's not too hard to compute $x$ if you use a numerical representation that has enough digits of precision, and then to compute $\sin(x)$ using standard methods.

However, a standard `double` won't have enough precision to perform this computation. It only has about 53 bits of precision; that's a lot less than the $99 \lg 10 \approx 329$ bits of precision you'd need to be able to distinguish $10^{99}$ from $10^{99}+1$. (A standard IEEE `float` cannot even represent values in excess of $3\*10^{38}$). Of course, $\sin(10^{99})$ is *very* different from $\sin(10^{99}+1)$. So, if you want to compute $\sin(10^{99})$, just stuffing $10^{99}$ into a `float` or `double` and then trying to invoke the $\sin(\cdot)$ function on that is not going to end well.

If you want to compute $x$ to at least $b$ bits of precision, you'll probably need a numerical representation that can represent $10^{99}$ to at least $329+b$ bits of precision (probably more than that, for intermediate values that arise during the modular reduction). A `float` or `double` ain't gonna be enough for that.
> 6 votes

# Answer
Taking the sine of large numbers is a **numerically unstable** operation.

Considering an argument like $10^{99}$, you can get a completely different value of the sine by adding, say $1$ to it. Think that this is a relative change of $10^{-99}$ !

---

Indeed, $$|\sin(a+1)-\sin(a)|=|2\sin(\frac12)\cos(a+\frac12)|\>0.95|\sin(a+\frac12)|,$$

so that you can find arbitrarily tiny $\epsilon=\dfrac1a$ such that

$$|\sin(a(1+\epsilon))-\sin(a)|\>0.5.$$
> 4 votes

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


title: Big O Proof for Logarithmic Function

text:
# Question
Title: Big O Proof for Logarithmic Function
I am an undergraduate student in Computer Engineering and going through one of the textbook examples, I am asked to prove that

$T(n)$ is $O(\log{}n)$

Where $T(n)= 5\log\_{2} 2n +7$. I understand that this means that I must prove that $5\log\_{2} 2n +7 \leq\lambda log(n)$

For some in n in a neighborhood of infinity. How exactly would I proceed with this?

# Answer
> 1 votes
$$5\log\_2(2n)+7=5\log\_2 n+5\log\_2 2+7=5\log\_2 n +12$$ Since for example $12\le 12\log\_2 n$ for $n\ge 2$, it follows that $$5\log\_2 n +12\le 5\log\_2 n +12\log\_2 n=17\log\_2 n $$ for $n\ge 2$. This yields $O(\log n) $.

---
Tags: asymptotics, proof-techniques
---


# Question
Title: Proof that a given language is not context-free
Given the language $L = \\{w \in \\{a,b\\}^\* \\, | \\, |w| = n \cdot \sqrt{n} \text{ and } n \geq 42\\}$ and the assignement to proof that $L \notin CFL$ with the Pumping lemma.

Assuming $L \in CFL$, would it be possible to start with defining a language $L' := L \cap a^+$ which has to be context-free since $CFL$ is closed under intersection with $REG$. Now I would have to proof that $L' = \\{w \in a^+ \\, | \\, |w| = n \cdot \sqrt{n} \text{ and } n \geq 42\\}$ isn't regular because the alphabet contains only one symbol.

Let $k$ be the constant of the Pumping lemma and $m \> k$ and $m \> 42$. So $z = a^{m^2\cdot\sqrt{m^2}} = a^{m^3} \in L'$.

$|z| = |uvw| = m^3 ...$

How to continue?

# Answer
You're off to a good start. You recognize that all you have to do is show that the language $L'$ isn't regular. You let $k$ be the integer of the PL and choose an integer $m$ with $m\>k$ and $m\>42$ so you choose to pump the string $z=a^{m^3}$. Write this as $uvw$ with $|v|=t$ and $0\<t\<k$. Now we'll have $|uv^2w|=m^3+t\<m^3+m$. This string can't be in $L'$ since it's strictly smaller than the next largest string in $L'$, namely the one with length $(m+1)^3$, since obviously $$ m^3+m\<m^3+3m^2+3m+1 $$ Since $L'$ isn't regular, $L$ can't be a CFL.
> 3 votes

# Answer
Use the pumping lemma for CFLs. Let N be the pumping lemma's constant, and take $\sigma = a^{N^{3/2}}$, which certainly has $\lvert \sigma \rvert \ge N$. So we can write $\sigma = v w x y z$ with $\lvert w x y \rvert \le N$ and $w y \ne \epsilon$ such that for all $k \ge 0$ we have $v w^k x y^k z \in L$.

But here only lengths matter. Call $u = \lvert w y \rvert$, so that the length of the pumped string is:

$\begin{align} \lvert v w^k x y^k z \rvert = N^{3/2} + (k - 1) u \end{align}$

where we know that $u \le N$.

Now look for $n$ such that $(n + 1)^{3/2} - n^{3/2} \> N$. By the binomial theorem:

$\begin{align} (n + 1)^{3/2} - n^{3/2} &= n^{3/2} \left( (1 + 1/n)^{3/2} - 1 \right) \\ &= n^{3/2} \left( 1 + \frac{3}{2 n} + \dotsb - 1 \right) \\ &\ge \frac{3 \sqrt{n}}{2} \\ & \> N \end{align}$

This is $n \> 4 N^2 / 9$. This provides a stride larger than $N$ between lengths of strings in the language, the pumped string will fall short.
> 3 votes

# Answer
For any context-free language $L$, the set $S$ of lengths of words in $L$ is *eventually periodic*, that is there exists an $m\>0$ such that $x \in S$ iff $x + m \in S$ (this is one form of Parikh's theorem). In your case, if $L$ were linear then $S = \\{ k^3 : k^2 \geq 42 \\}$ would be eventually periodic. However, an eventually periodic set is either finite or has positive density, whereas this set $S$ is neither.

A more general form of Parikh's theorem states that the set of *histograms* of words in a context-free language (the histogram of a word counts how many times each symbol appears in it) is *semi-linear*, which is a union of *linear* sets, a linear set being a set of the form $\\{ x + n\_1 y\_1 + \cdots + n\_r y\_r : n\_1,\ldots,n\_r \in \mathbb{N} \\}$, where $x,y\_1,\ldots,y\_r \in \mathbb{N}^\Sigma$. This is useful for proving that languages defined using more complicated constraints are not context-free.
> 3 votes

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


title: Convert a CFG into CNF

text:
# Question
Title: Convert a CFG into CNF
I'm still new to `CFG and CNF` and have trouble sometimes understanding the concepts.

I'm trying to convert this CFG into Chomsky Normal Form:

```
G: S -> aSbS | bSaS | epsilon

```

I think the language generates all strings with same number of a and b, i.e. `{a^n b^n |n>-0}`.

But to convert it into CNF, I've finished adding a new start state and eliminating epsilon-productions:

```
S_0 -> S | epsilon
S -> aSbS | bSaS | aS | bS | a | b

```

Perhaps I need two non-terminals(variables) A -\> a and B -\> b :

```
S_0 -> S | epsilon
S -> ASBS | BSAS | AS | BS | a | b
A -> a
B -> b

```

I'm stuck here and really don't know what the next step should be. There seem to be no unit productions or useless symbols.

# Answer
> 1 votes
Wikipedia has a good breakdown of how to convert to CNF.

Your first steps are correct, if incomplete: you should have the following:

```
S_0 -> S | epsilon
S -> ASBS | BSAS | AS | BS | A | B
A -> a
B -> b

```

(Notice the S rule.)

The next thing you need to do is decompose your `S` state(s) into multiple states, each with two or less nonterminals:

```
S -> T | W | AS | BS | A | B
T -> AU
U -> SV
V -> BS
W -> BX
X -> SY
Y -> AS

```

Does this get you unstuck?

---
Tags: context-free, normal-forms
---


# Question
Title: What specifically makes quantum computers useful?
I know that quantum computers are able to process a superposition of all possible states with a single pass through the logic.

That seems to be what people point to as being what makes quantum computers special or useful.

However after you have processed the superpositional inputs, you have a superpositional result, of which you can only ask a single question and it collapses into a single value. I also know that it isn't (currently?) possible to clone the superpositional state, so you are stuck with getting an answer to that one question.

In both cases, it looks like that multi processing ability really hasn't gotten you anything since it's effectively as if only one state was processed.

Am i misinterpreting things, or does the real usefulness of quantum computing come from something else?

Can anyone explain what that something else is?

# Answer
**Destructive interference** is the primary thing that makes quantum computers more powerful. In a classical probabilistic computation, having two paths to an output always makes that outcome more likely. In a quantum computer, it can make the outcome *less* likely.

Quantum algorithms are carefully designed so that wrong answers tend to be destructively interfered, leaving only the desired solutions as measurement outcomes. This is tricky to do, and not every problem allows for it. Grover's Search Algorithm is an excellent example of this effect, so here's a beginner-level post about Grover's algorithm.

Other useful properties quantum computers have access to:

(Scott Aaronson likes to say everything interesting about quantum is due to superpositions preserving the 2-norm instead of the 1-norm like probability distributions do. All the more specific useful effects I mentioned do derive from the underlying math.)
> 17 votes

# Answer
Some of your questions are open theoretical questions. There are several ways to answer your question. A general way to think about QM computing is that it harnesses spintronics ie quantum property of spin for computation. So it is a logical next step in the miniaturization of electronics/logic, and computation in general. There are theoretical limits on gate width that are being brushed up against in current fabrication technology, a consequent plateauing of Moores law and spintronics represents the "next frontier".

Spintronics represents a different computing paradigm than binary logic. So it has interesting theoretical properties worthy of exploration even without implementations. However there is a general hope in the field that QM computing is *extremely scalable* and that once the principles are figured out for a few qubits, the systems could be scaled to many qubits "without too much trouble". Theoretically it is shown to scale in processing complexity in a much different/more dramatic way than classical computing, ie roughly there is $2^x$ processing capability where $x$ is the number of qubits, ie exponential rise in computational capability for linear increase in qubits. This sounds almost like out of science fiction but is an apparently "real/intrinsic" property as far as anyone knows.

A key breakthrough in 1996 is Shor's algorithm, that showed factoring can be solved in "quantum polynmomial time" and it is credited as inciting major interest in quantum computing. Factoring is of course at the heart of modern cryptographic systems in the widely used RSA algorithm.

It is an open theoretical question if quantum computers can solve other major problems in "faster" time. This is known as the BPP=? BQP question.

A controversial QM computer is built by DWave which has been proven to be "useful" in solving some problems, and they have successfully demonstrated a form of quantum scaling on a "somewhat weaker" type of QM system known as adiabatic computing. It is an open question whether it can/ will ever demonstrate unequivocal speed increases, actively under research eg by Google, Nasa, Lockheed etc.

In short quantum computers are not exactly *"useful"* in the same sense as classical computers, that exact nature of their usefulness is being actively researched, and only limited/ experimental/prototype systems are current in existence. They are conjectured to be "at least as useful" as conventional computation upon their realization, and possibly/hopefully "more useful" in certain not-exactly-foreseeable ways.
> 5 votes

# Answer
A rather controversial answer, but keep it in mind nevertheless.

i would say **nothing** makes quantum computers more useful (at least currently)!

Sure, the standard theoretical treatment of quantum mechanics into computing, with respect to a classical theoretical treatment, indeed offers new possibilities (as other answers have noted). So what is the *catch* here?

The *catch* is this: It is **not certain** quantum computers are indeed more powerful than ordinary / classical computers (a fact related to the $P$ vs $NP$ problem as well) and that classical computers cannot simulate quantum computers. Sure "*quantum theory*" will tell you so. Why quotes in "*quantum theory*"? Because it is not quantum theory, actualy it is just a specific "*interpretation of quantum theory*". Hope all these are understood and clear.

Related references:

1. Is there a formal proof that quantum computing is or will be faster than classical computing?
2. Quantum computer emulated by a classical system (IOP paper)
3. First 'Quantum Computer' No Faster Than Classic PC
4. Can quantum measurements beat classical computers?
5. Beating a quantum computer by simulating quantum mechanics
> 5 votes

---
Tags: computation-models, quantum-computing
---