# Question
Title: Are there any problems that get easier as they increase in size?
This may be a ridiculous question, but is it possible to have a problem that actually gets easier as the inputs grow in size? I doubt any practical problems are like this, but maybe we can invent a degenerate problem that has this property. For instance, perhaps it begins to "solve itself" as it gets larger, or behaves in some other bizarre way.

# Answer
No, it's not possible: at least, not in an asymptotic sense, where you require the problem to keep getting strictly easier, forever, as $n \to \infty$.

Let $T(n)$ be the best possible running time for solving such a problem, where $n$ is the size of the input. Note that the running time is a count of the number of instructions executed by the algorithm, so it has to be a non-negative integer. In other words, $T(n) \in \mathbb{N}$ for all $n$. Now if we consider a function $T: \mathbb{N} \to \mathbb{N}$, we see there is no such function that is strictly monotonically decreasing. (Whatever $T(0)$ is, it has to be finite, say $T(0)=c$; but then since $T$ is monotonically strictly decreasing, $T(c) \le 0$ and $T(c+1) \le -1$, which is impossible.) For similar reasons, there is no function that is asymptotically strictly decreasing: we can similarly prove that there's no running time function $T(n)$ where there exists $n\_0$ such that for all $n \ge n\_0$, $T(n)$ is monotonically strictly decreasing (any such function would have to become eventually negative).

So, such a problem cannot exist, for the simple reason that running times have to be non-negative integers.

---

Note that this answer covers only *deterministic* algorithms (i.e., worst-case running time). It doesn't rule out the possibility of randomized algorithms whose expected running time is strictly monotonically decreasing, forever. I don't know whether it's possible for such an algorithm to exist. I thank Beni Cherniavsky-Paskin for this observation.
> 40 votes

# Answer
Although it's not quite an answer to your question, the Boyer-Moore string search algorithm comes close. As Robert Moore says on his web page about the algorithm,

> Our algorithm has the peculiar property that, roughly speaking, the longer the pattern is, the faster the algorithm goes.

In other words, generally speaking the algorithm searches for an instance of a target string in a source string and for a fixed source string, the longer the target string is, the faster the algorithm runs.
> 28 votes

# Answer
Clearly, from a pure mathematical, purely CS algorithm viewpoint this is impossible. But in fact there are several real-world examples of when scaling up your project makes it easier, many which are not intuitive to end-users.

**Directions**: the longer your directions get, they can sometimes get easier. For example, if I want Google Maps to give me directions for going west 3000 miles, I could drive to the West Coast -- and would get cross-country driving instructions. But if I wanted to go 6000 miles west, I would end up with significantly simpler instructions: get on a plane from NYC to Hokkaido. Giving me a cross-country route that incorporates traffic, roads, weather, etc. is rather difficult algorithmically, but telling me to get on a plane and looking up flights in a database is comparatively significantly simpler. ASCII graph of difficulty vs distance:

```
           |     /
           |    /
Difficulty |   /                  ____-------
           |  /           ____----
           | /    ____----
            ---------------------------------
                       Distance

```

**Rendering**: say I want a render of one face and a rendering of 1000 faces; this is for a billboard ad so both final images must be 10000px by 5000px. Rendering one face realistically would be hard -- at the resolution of several thousand pixels across you have to use really powerful machines -- but for the crowd of 1000 faces each face need only be ten pixels across, and can easily be cloned! I could probably render 1000 faces on my laptop, but rendering a realistic face 10000px across would take a very long time and powerful machines. ASCII graph of difficulty vs. objects rendered, showing how difficulty of rendering n objects to an image of a set size drops off quickly but then returns slowly:

```
           | -
           |- -                     _________
Difficulty |   --      ______-------
           |     ------
           |
            ---------------------------------
                        Objects

```

**Hardware control**: many things with hardware get much easier. "Move motor X 1 degree" is hard and/or impossible, and you have to deal with all kinds of things that you wouldn't have to deal with for "move motor X 322 degrees".

**Short duration tasks:** Say you want item X to be on for (very small amount of time) every second. By increasing the amount of time that X runs, you will need less complex software as well as hardware.
> 11 votes

# Answer
There are cases. They are the cases where the success criteria is a function of the data, rather than trying to find a single answer. For example, statistical processes whose results are phrased with confidence intervals can become easier.

One particular case I'm thinking of is problems which have a transition from discrete behaviors to continuous behaviors, like fluid flows. Solving the small problem to within a degree of error can involve modeling all of the discrete interactions, which may call for a supercomputer. The continuous behaviors often permit simplifications without yielding results outside of a related error bound.
> 4 votes

# Answer
The question is interesting and USEFUL, because our philosophy in informatics is to solve problems the more we read the more dificult is. But, in fact, the MOST of the problems that are presented in the typical way (difficult) can be easily represented in the "easy" way; even knowing the response of D.W (which is in a wrong considering that easy does not mean faster, means "less slow"; so you do not have to find negative times, you hace to find asymptotic time).

The trick to find one is putting the part of the solution like hints as an entry, and considering the entry of the problem like a constant parameter.

Example: What is the longest way in car between London and Paris avoiding to visit twice a French and a British town and not visiting other country? considerin, you have to go to Birmingham before Ashford, Orleans before Versailles, La Rochelle before Limoge, etc...

It is clear that this problem with long entries will be easier that with short ones.

Example of use: Imagine a playgame managed by the machine, and the IA of the computer have to determine if he has to explore more in the play to find more hints or else, if now is time to deduce what is the best decision to assume.
> 3 votes

# Answer
Consider a program that takes as input what you know about a password and then tries to crack it. I think this does what you want. For example:

* No input-\> Brute force crack over all symbols and a word of any length
* Length of password -\> Brute force all symbols in a word of that length
* Contained symbols -\> Shrinks list of symbols to check
* ...
* Contained Symbols including multiple occurrences and length -\> Only compute permutations
* All symbols in correct order -\> basically solved itself

I should add that this is a trick, since the problem stated like this is inverse to to input size. You could leave out one layer of abstraction and say that the input size is large for no input (check all symbols and lengths of words) and small if you enter the correct password in the beginning.

So it all comes down on how much abstraction you allow.
> 2 votes

# Answer
As a matter of fact, I do have a problem that gets smaller as the data increases. One of my application records attributes of a particular product, say cheese. Attributes are for instance CheeseType, Brand, Country, Area, MilkType, etc. Every month or so, I get a list of new cheeses that came into the market during that time, along with their attributes. Now, these attributes are typed by hand by a group of humans. Some make typos, or just don't know the value for all attributes.

When you make a search in my database, I try to predict from statistics what the cheese tastes like, based on these attributes. What happens, is that for each attribute, I end up with a range of values ; some are valid some are invalid. Eliminating or correcting these invalid ones is only possible if I have enough data. It's about making the difference between real values and noise, without eliminating rare but valid values.

As you can imagine, with low volume, the noise is too important to fix things properly. If you have 5 instances of Cheddar, 1 of Brie , 1 of Bri, and 1 of Chedar, how do I tell which is correct and which is a typo? With more volume, the typos tend to keep very low, but the rare values get a few crucial increments, making them escape from the noise (backed by experience). In this case, I could imagine 50000 Cheddar, 3000 Brie, 5 Bri, 15 Chedar, for instance.

So yes, some problems solve themselves eventually, when you have enough data.
> 0 votes

# Answer
The question asks: "is it possible to have a problem that actually gets easier as the inputs grow in size?" What if the inputs are **resources** to be used by the algorithm to work on a job. It is common knowledge that the more the resources the better. Below is an example, in which the more there are employees the better.

1) You are given two inputs:
i) The number of employees in an industry. This is a natural number and is the main input $n$.
ii) Information about the industry. There are $t$ tasks to be done by the workers, labeled A, B, C, D... There are $p$ places that connect the tasks enabling the employees to switch between tasks. They are labeled 0, 1, 2, 3... The information given is a simple directed graph made up of routes, for example: A-1, 1-2, 2-B, C-3... For simplicity each route has a cost of 1.

2) Problem:
Starting from the first tasks A, and with $n$ employees, you are to find an optimal strategy for the employees to use in order to visit all the tasks. Tasks can be visited more than once. Recall that you cannot switch between tasks unless you find a path between them. The path from task A to B is independent of that from B to A.

3) Output:
The output is the paths between tasks to be taken by the employees. Each path is associated with the number of employees taking it. For example:

A to B with $n1$ employees (a forward path)
A to C with $n2$ employees (a forward path)
B to D with $n3$ employees (a forward path)
D to B with $n4$ employees (a reversed path)
B to E with $n5$ employees (a forward path)

4) Possible solution:
One possible solution is to first compute the shortest path to the closest nodes from A. This will be a forward path. Then recursively compute the forward path for each visited tasks. The result is a tree. For example:

```
          A
      B      C
    D   E

```

Now is the time to determine how the employees are going to traverse the tree so to visit the tasks. Starting from task A with $n$ employees, $n1$ are sent to the left subtree and $n2$ are sent to the right subtree. If $n2 \neq 0$ then none from the left subtree will ever need to go to the right subtree.

For $n=\infty$ the employees will all just move forward. For $n = 1$ the employee will have to use reverse paths in order to visit other tasks. For D to B for example the algorithm will compute that shortest path. This is extra computation. Why not directly compute a shortest path from D to E?! Fine, hopefully that is **still** extra computation.

But of course computation time will not decrease infinitely (by the way for $n$ too large it will lead to poor resource management and stuff).
> -1 votes

# Answer
Consider the NP-complete problem 3-SAT. If you keep augmenting the problem by providing inputs of the form x\_i = true/false, you either end up converting the individual disjunctions into two-variable clauses, thereby creating a 2-SAT problem which is decidedly P, or you simply end up getting a true/false answer.

For the case where there is redundancy in the x\_i = true/false inputs (same input provided a lot of times, or contradictory inputs) you can easily sort the inputs and either ignore the redundant values, or report an error if the values contradict.

In any case, I think this represents a 'realistic' problem that gets easier to solve as the number of inputs grows. The 'easier' aspect is in converting an NP-complete problem to a P problem. You can still game the system by providing ridiculous inputs such that just the sorting would take longer than brute forcing the problem.

Now, a really cool scenario would be if we are willing to accept T(0) (utilizing D.W.'s notation in the answer above) can be infinite. For example, T(0) could be equivalent to solving Turing's Halting Problem. If we could devise a problem such that adding more inputs converts it into a solvable problem, we have struck gold. Note that it is not enough to convert it into a solvable problem asymptotically - because that is just as bad as brute forcing the problem.
> -1 votes

---
Tags: algorithms, asymptotics
---


# Question
Title: Are all non-terminals of the CFG given by the LHS of productions?
A definition for terminals and non-terminals of a CFG says that

> terminals: The symbols that do not appear at the LHS of productions.

Therefore,

**Are all non-terminals of the CFG given by the LHS of productions?**

# Answer
> 2 votes
Given the definition you appear to be using, yes. There are only two types of symbols in a CFG, so this definition provides a dichotomy. This implicit defintion of CFGs, where the productions are provided and the terminals and non-terminals are inferred from the productions, is common in programming language circles (or at least well known), where the practical form of the grammar is the interesting aspect.

Note that this is not the only way to define a CFG, the more typical formal way gives explicit sets of terminals and non-terminals, and expresses the rules as a finite relation from the non-terminals to the set of finite strings over the non-terminals and terminals. So in this there is no "left-hand-side" as such, as being on the left entirely depends on the notation you would use to represent the productions. Moreover there's no specification that all terminals or non-terminals need to be used.

# Answer
> 3 votes
No. Not all non-terminals necessarily appear at the LHS of productions, that is, not every non-terminal must have productions for it.

Of course, such non-terminals are rather useless and can be removed from the grammar without changing the language. Also the dual is actually possible: there might be terminal symbols that do not appear at the RHS of productions. For example $a^\*$ is a context-free language over the alphabet $\\{a,b\\}$.

---
Tags: context-free
---


# Question
Title: Help coming up with a solution to a combinatorial problem
So here is the problem:

Say I want to find the only possible combinations to find the sum of a specific number using only the numbers 1, 2, & 3 with a specific number of additions.

I know this sounds confusing, but let me give an example:

Say we were trying to find the number of possible combinations to add up to the number 6 using, as stated above, only the numbers 1, 2, & 3 with exactly 2 additions.

The solution is easy:

Since we are trying to add up to 6 using exactly 2 additions with the only three numbers we are allowed to use (1, 2, & 3), we only get: {3 + 3}.

Similarly, If we were trying to find the number of possible combinations to add up to the number 4 with exactly 2 additions we get: {1 + 3} & {2 + 2}.

So, I am asking is there an algorithm out there that I can use to solve this when the numbers get bigger? Is there a clever way to solve this with code? I've been thinking about this for a while and can't seem to solve it.

Thanks!

# Answer
> 2 votes
One way to solve this is using generating functions. The number of ways to get the number 6 using "2 additions" of 1, 2, or 3 is the coefficient of $x^6$ in $(x+x^2+x^3)^2$. This generalizes: the number of ways to get the number $n$ using "$k$ additions" of 1, 2, or 3 is the coefficient of $x^n$ in $(x+x^2+x^3)^k$. I'll let you play with some examples to see why this is so.

Once you know this fact, you can then use polynomial multiplication and repeated squaring to compute the polynomial $(x+x^2+x^3)^k$ and then read off the answer.

See also Calculating the number of multiplications necessary to evaluate a polynomial.

---
Tags: algorithms, combinatorics, dynamic-programming, approximation, discrete-mathematics
---


# Question
Title: What would be the real-world implications of a constructive $P=NP$ proof?
I have a high-level understanding of the $P=NP$ problem and I understand that if it were absolutely "proven" to be true with a provided solution, it would open the door for solving numerous problems within the realm of computer science.

My question is, if someone were to publish a indisputable, constructive proof of $P=NP$, what are some of the immediate effects that we would see of such a discovery?

I'm not asking for opinionated views of what the world would look like in 5-10 years. Instead, it is my understanding that this is such a fundamentally unsolvable problem that it could radically change the way we compute... many things (yeah, this is where my ignorance is showing...) that we can't easily calculate today.

What kind of near-immediate effect would a thorough, accurate, and constructive proof of $P=NP$ have on the practical world?

# Answer
People have given good answers assuming that $P=NP$ with some really large constant. I'm going to play the optimist and assume that we find a proof of $P=NP$ with a tractably small constant. Perhaps not likely, but I'm going to try to give some insight into what sorts of things would happen if we could efficiently solve all $NP$ problems.

* Compilers: Some computer programs would get slightly faster, since compilers use graph coloring for register allocation. We would be able to allocate for large numbers of registers exactly. Existing compilers using an approximate solution (like chordal graphs) would get better output, and those using an exact solution would get faster.
* Facility location: Businesses would be able to find the optimal place to place factories and supply depots to ship to their stores, when there are possibly thousands of stores and factories. Would likely not be a huge improvement over modern approximations, but would reduce costs.
* Buying plane tickets: airline tickets are weird since they don't follow triangle equality. Sometimes it's cheaper to fly from A -\> B -\> C than directly from A -\> C, something that doesn't come up when modelling distances. It would be easy to make a website that finds the absolute cheapest sequence of flights that visit some number of cities and starts and ends in your hometown.
* Circuit design: electrical circuits on a chip are basically Boolean formulas. Things like minimization could be efficiently calculated, so our hardware would get a bit more efficient.
* Scheduling: mad that your school put two of your exams on the same time? If $P=NP$ your school could either how many timeslots they need so no student has a conflict, or given a number of time slots, minimize the number of conflicts.

This is just a sampling of practical applications that we'd see if $NP$-completeness weren't a barrier. I'm sure I've missed many, but if the given construction had a good constant, the implications would be far reaching.
> 37 votes

# Answer
We won't necessarily see any effects. Suppose that somebody finds an algorithm that solves 3SAT on $n$ variables in $2^{100} n$ basic operations. You won't be able to run this algorithm on any instance, since it takes too long. Or suppose that she finds an algorithm running in $n^{100}$ basic operations. We will only be able to use it on 3SAT instances on a single variable, since for more variables it takes too long.

On the other hand, suppose that P$\neq$NP, and that even the stronger exponential time hypothesis holds. Then in general, 3SAT should be untractable. Yet SAT solvers seem to be doing well on certain problems.

What's happening here? There are several problems with the P vs. NP question:

1. It only concerns the worst case.
2. It is only asymptotic.
3. All polynomial time bounds are the same.

These problems cast doubt on its relevance to the real world. Now it *could* happen that some really fast algorithm is found for 3SAT, so fast that even symmetric encryption would become breakable. But I consider this highly unlikely. On the other hand, it is perfectly consistent for P to be different from NP while factoring being practical; that would break certain public key encryption schemes. This is a likely situation which would have repercussions, but it is unrelated to the P vs. NP question.

The P vs. NP question might be natural from a mathematical point of view, but its practical relevance is doubtful, in my view. Research on the question, on the other hand, might or might not have practical repercussions; it is not guided by this aspect.
> 36 votes

# Answer
A very nice read here is \[1\], where Impagliazzo considers five possible "worlds" where relationships between complexity classes are different. For instance, in a world called *Algorithmica* (see Section 2.1), we have that $\sf P = NP$ (or some other "moral equivalent" holds, such as $\sf NP \subseteq BPP$).

In *Algorithmica*, virtually any optimization problem would be trivial. Programming languages could be languages where one specifies the properties a desired output should have in relation to the input, instead of specifying how computation should be performed. Computers could also find proofs for any theorem in time roughly the length of the proof. (This view is very optimistic of course, and depends on an efficient algorithm for some $\sf NP$-complete problem).

---

\[1\] Russell Impagliazzo. A Personal View of Average-Case Complexity. Complexity Conference, 1995.
> 18 votes

# Answer
Even without P=NP, today's computers are unbelievable powerful.

---

**Edit 22 Jan 2018** I found out now how I should have "interpreted" the text quoted in the example below. It was my own fault, the inverse element was required to be *unique*. Here is my input file from 22 Dec 2014 (addinvrig.in) and here is the fixed input file from today (addinvrigFixed.in). The crucial line is `(x+(-x))+((-y)+y)=((-y)+y)+(x+(-x)).` The power of the automated reasoning tools themselves is still fascinating to me, even if they cannot save me from misinterpreting other people's writings.

Using automated reasoning tools is surprisingly useful for me, when I come across cited theorems where I am unsure how to "interpret" the text:

> In 1974, Karvellas \[ 3 \] studied additive inverse semiring and he proved the following:
> (Karvellas (1974), Theorem 3(ii) and Theorem 7) Take any additive inverse semiring (S, +, ·).
> (i) For all $x, y \in S$, $(x \cdot y)' = x' \cdot y = x \cdot y'$ and $x' \cdot y' = x \cdot y$
> (ii) If $a \in aS \cap Sa$ for all $a \in S$ then $S$ is additively commutative.

I adapted my prover9 input files for this theorem, and was immediately shown a counter-example for the theorem as cited. Slightly modifying the assumptions produced many similar true theorems, which makes it most likely that Karvellas actually stated and proved a correct theorem, which was only cited incorrectly here. Googling for the reference of this theorem only turned up another paper which cited Karvellas even less accurate.

---

This is an unbelievably incomplete collection of computer aided results for specific problems which are intractable in general if P!=NP. Maybe this collection makes it clear to at least some readers that we all tend to underestimate the powers of computers in this domain. Many other answers to this question seem to suggest that there would be no big consequences if computers would get (slightly) better at solving intractable problems. But computers get better at solving intractable problems all the time (because quite some time and money is spend to make this happen), and this has very real consequences. If P=NP would be proved, then perhaps the awareness of what computers can actually do (even today) would increase, and more people would use computers to help them with such tasks. (PS: I'm convinced that P!=NP, but this is not relevant for this answer.)
> 10 votes

# Answer
### P vs. NP, technically vs. morally

As Yuval said it is possible that P=NP is technically true but *morally* false. P=NP is morally true (even if not necessarily technically) if there is a *fast* deterministic algorithm (say $O(n^2)$, or maybe even $O(n^{\lg^\* n})$ with small constants, nothing like $2^{65536}+2^{1024}n^{256}$) that solves one of famous NP-complete problems like SAT. IIRC, Russell Impagliazzo once said that he would consider the P vs. NP problem as essentially settled if someone shows SAT can be solved in $O(n^{\lg n})$ time.

### So what happens if P=NP is *morally* true?

This brings us back to why NP is such an interesting class of problems. The intuition in general is that we often want to find objects of reasonable size (formalized as polynomial size) that hold a property $Q$ and the property $Q$ is easy to verify (formalized as computable in polynomial time). This class of problems encompasses almost all problems we are interested in. To go beyond it you need to think about interactions between players like games. The number of natural interesting problems that are not in NP (or PH) is very small compared to natural interesting NP problems. If P=NP is *morally* true then all of these problems can be solved very fast. Just to give an example, you can learn best weights for very complicated machine learning models. You can break encryption protocols.

### Comparison with the case where P$\neq$NP is *morally* true

By P$\neq$NP is *morally* true I mean that we cannot solve SAT (or any of other famous NP-complete problems) much faster than brute-force then these problems cannot be solved in practice for *general* inputs of even rather small input size of say 100.

### Does P$\neq$NP is *morally* true mean we cannot solve NP-hard problems in practice?

Even if P$\neq$NP is *morally* true, it is still possible that for some of these problems we are interested not in general inputs and worst-case but a class/distribution of inputs that can be solved efficiently. E.g. it can be the case that solving SAT in the worth case requires exponential time but in practice we can already solve SAT on many interesting classes like software verification, hardware verification, etc. much faster.

This is kind of similar to solving a simpler problem, e.g. TSP cannot be even approximated efficiently if P$\neq$NP is morally true, yet we already can approximate the special case of TSP on Euclidean graphs.

If you know you want to solve an NP-complete problem not on general inputs but on inputs with particular properties you don't need to care about the general problem. You only need to solve the simpler problem. Unfortunately it is often not easy to determine what kind of inputs you care about in practice.

Still heuristics can perform amazingly well in practice as we see with SAT or Integer Programming or Machine Learning. (PAC learning using the very simple model of 3-DNFs is intractable if NP$\neq$RP, and lots of experts think that RP=P).
> 8 votes

# Answer
There are many opinions on the real-world implications of P=NP. As seen in other good responses there are mainly 2 schools of thought. One is that a P-time algorithm might be very difficult or unfeasible to actually implement due to "unexpected anomalies" associated with the abstraction. eg:

* the program might be too "large" to actually code
* there could be a very large constant involved such that for all instances within reach of "terrestrial computation", they are still long-running, ie the efficiency doesnt "kick in" except for very large instances. it is known that some algorithms actually fit into this case as recently pointed out by Knuth (question 15)

> In general I'm looking for more focus on algorithms that work fast with respect to problems whose size, n, is feasible. Most of today's literature is devoted to algorithms that are asymptotically great, but they are helpful only when n exceeds the size of the universe.

A famous case study is done by Impagliazzo as cited by J. in other answer. However, his essay has been extrapolated somewhat in the meantime. Here's a great new reference by an expert that charges into this question in a sort of sci-fi future scenario, ch2/ p11. summarizing

The golden ticket: P, NP, and the search for the impossible by Lance Fortnow

* "if it turns out that P=NP and we have efficient algorithms for all NP problems, the world will change in ways that will make the Internet seem like a footnote in history. Not only would it be impossible to describe all these changes but the biggest implications of the new technologies would be impossible to predict."
* Algorithm quickly implemented on supercomputer. Boeing immediately contracts to get a better wing design for a new aircraft allowing it to fly from London to Sydney nonstop.
* Search algorithm used to find a new algorithm that is even faster, optimizing the original P=NP solution. Ends with result of 42 million lines of unintelligible code. Called the "Urbana algorithm"
* Algorithm used to find customized cancer treatments/ near-cures taylored to individuals. cures cancer, AIDS, diabetes but the common cold remains a mystery
* Super scheduling algorithm allows forecasters to "make incredible advances in weather prediction, allowing accurate predictions of temperature, winds, cloud cover, and precipitation nearly a year ahead of time. Similar algorithms now save lives by accurately predicting storms, tornados, hurricanes so people can prepare or evacuate as needed."
* Highly accurate face recognition
* Computer can reconstruct 3d models of a scene in realtime from different camera angles
* Computer algorithms control camera operations for sporting event (instead of human controlled)
* Automated commentary and replays are generated by the algorithm including well-chosen angles and statistics, and generated in any language in realtime
* Fantasy baseball/ sports take on new dimension with highly accurate simulations
* Food recipe tastes improved by the algorithm
* The algorithm could be used to "learn just about anything, including what makes good art, popular music, and words that stir the soul. remember that P=NP means that what we can test, we can find. So once you have an algorithmic process to recognize greatness, you can use the algorithm again to quickly find that greatness."
* Politician uses computer algorithm to recognize great speeches and generate one that fits the patterns. Speech goes viral on the internet.
* People generate complete works of art from incomplete/ unfinished art eg symphonies. they use algorithm to generate new Beatles/ Elvis records. New art, novels, plays, and poetry eg romantic comedy with Humphrey Bogart/ Julia Roberts.
* Amazon can create customized novel for individuals on demand. NBC creates live action adventure television series created entirely by computer
* Simulated virtual reality in video games allowing any actions of the players instead of a fixed set of possible story lines.
* Law enforcement uses algorithm as "incredible tool in solving crimes, seemingly doing the impossible in tracking down suspects." computer algorithm can reconstruct probable faces (for composite sketches) using only DNA. Police match a murder suspect using massive search of drivers license photos database aligned with the generated sketch (from DNA).

Unfortunately not a lot that Fortnow outlines above is supported by actual scientific literature except maybe an imaginative extrapolation of Impagliazzos worlds. it would take much more to dissect this point-by-point, but to summarize, it all appears to be entertaining but fantastic/ wishful thinking (or maybe that is his veiled point). In fact there are scientific principles that are in conflict with many of the items. And notice Fortnow is a sports fan so develops an extended metaphor in that area, but could this be more an indication of humans thinking in grooves?

For example the "butterfly effect" is known to imply that accurate weather prediction past a (say) several-day horizon is impossible due to "sensitive dependence on initial conditions" (and Fortnow has later admitted on his blog to repeated criticism on exactly this point). Also, there is a lot of evidence that computers fail on highly human-subjective tasks such as generating or identifying influential art (a task that even expert humans do not succeed at consistently).

Actually the whole question is verging on counterfactual or a false premise. Note that a large majority of expert scientists polled think/ believe, despite lack of incontrovertable proof so far, P≠NP. and it is natural to compare it with other known laws/ restrictions/ limitations such as thermodynamics (eg impossibility of perpetual motion/ free energy) and statistics, eg the "no free lunch theorem".

So the bottom line is that maybe even expert scientists cannot exactly predict the outcome of P=NP. So maybe the best answer for now is to admit that humans don't have a good answer at this time.
> 7 votes

# Answer
> What kind of near-immediate effect would a thorough, accurate proof of P=NP, with a provided solution, have on the practical world?

There's likely a great deal of great things that would come of it, but nobody would care.

The problem is that the foundation of (almost) all modern encryption is based on the assumption that P **not** equal NP. The encryption that protects your password as it goes over the internet, and as it's saved in databases. The encryption that protects *credit card data* as it goes over the internet... The encryption that protects the billions of daily financial transactions that tie our global economy into the giant organism it is.

Best case, P = NP means that stops. People go back to using cash and banks try to record these cash withdrawals on some disconnected medium since transactions to a central office are no longer trustworthy. This lasts for maybe a few months until better encryption is implemented globally. Best case.

Worst case, P = NP means that someone breaks the world. Currency is built on the concept of trust. You value a dollar, because you trust that your neighbor will give you a dollar's worth of goods or services for it. You value your computer saying you have 500 dollars in the bank, because you can swipe your card and get 500 dollars worth of goods and services...

What if you *couldn't* trust that? If P = NP, someone could impersonate various banks, government, people - and effectively randomize the amount of currency in every account. *Delete* the currency in every account. Sure, various banks have backups to account for it, but how long has their encryption been broken? Which transactions were good, and which were impersonated? It's impossible to know.

Once that trust is broken, chaos ensues. Any benefits from being able to deal with the Travelling Salesman Problem (for example) are ignored as people struggle to feed themselves.

Reality is likely somewhere in between, but hopefully this paints a big enough picture of how important a problem this is.
> 3 votes

# Answer
Massive drop in the expense of equipment, electricity, and cloud approaches will occur. Many things are being calculated with brute force right now, or approximations that still use some heavy brute forcing. We no longer will be doing all of those massively-paralalized brute force calculations.

That is by no means the only use of cloud computing, but it is still going to be a noticeable factor on energy use, cloud processing etc. Just the energy savings could be noticeable on our carbon footprint.

AI will also become much better. We may finally have a computer that can be the best GO players, and your graphing calculator will beat you at chess.
> 2 votes

# Answer
I wouldn't expect a revolution. We learnt to live in a world where P$\ne$ NP and found workarounds where they were critical (such as approximate solutions).

And the conjecture being disproved doesn't mean that all problems of practical usefulness would be solved in a snap of the fingers. In the first place, they still can be harder than NP.
> 0 votes

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


# Question
Title: Regular languages closed under quotients with arbitrary languages
When proving that that the quotient of a regular language $R$ and an arbitrary language $B$, I understand you take a DFA $M$ accepting $R$, and then construct a DFA that is the same, but its final states are those from which we can reach a final state of $M$ with a string from $B$. How can we just say it's possible to take such a set?

Does this proof also work for a similar property (I don't know the name) that creates the set $\\{ x \mid \forall y \in B : xy \in R \\} $?

# Answer
The *(right) quotient* of $R$ by $B$ is the language $$ RB^{-1} = \\{x \in A^\* \mid \exists y \in B,\ xy \in R\\} $$ and indeed, if $(Q, A, \cdot, q\_0, F)$ is the minimal DFA of $R$, then $RB^{-1}$ is accepted by the automaton $(Q, A, \cdot, q\_0, S)$, where $$ S = \\{q \in Q \mid \exists y \in B\ \ q \cdot y \in F\\}. $$ On the other hand, let $R/B = \\{x \in A^\* \mid \forall y \in B\ \ xy \in R\\}$. Then one gets $$ R/B = \bigcap\_{y \in B} \\{ x \in A^\* \mid xy \in R \\} = \bigcap\_{y \in B} Ry^{-1} $$ Since $R$ is regular, there are only finitely many distinct languages of the form $Ry^{-1}$, and each of it is regular. It follows that $R/B$ is also regular.

This gives a proof that the languages $RB^{-1}$ and $R/B$ are regular for any $B$. However, if you want to find **effectively** an automaton accepting these languages, this is a different story and you may need to identify which of the right quotients $Ru^{-1}$ are of the form $Ry^{-1}$ with $y \in B$, a question that might be undecidable, depending on $B$ and $R$...
> 4 votes

---
Tags: formal-languages, regular-languages, closure-properties
---


title: Is C → A B C | A left-factorizable?

text:
# Question
Title: Is C → A B C | A left-factorizable?
$$C \to A B C \mid A$$

Obviously has the same FIRST(C) for the both productions.

But how can this be left-factorised?

---

Tried:

$$C \to A B C'$$ $$C' \to A C \mid \varepsilon$$

The FIRST sets are disjoint, but is this correct?

Should $B \to \varepsilon$ (or $C \to \varepsilon$) be added as well, so that it handles $A B A$?

# Answer
> 2 votes
Your proposed factoring won't work correctly because both productions start with the same nonterminal. Remember that for an LL(1) parser you cannot have two productions that start with the same nonterminal (usually) because if you see anything in the FIRST set for that nonterminal, you wouldn't know which production to pick.

To left-factor the grammar, try something like this:

> C → AX
>
> X → BC | ε

Notice that this gives you the same strings as before, but (assuming that at least one of B and C doesn't produce ε) is LL(1).

# Answer
> 1 votes
IIRC, the left factorization take the common part out of the rules and add a non-term with the non common part, thus:

$$\newcommand{\ang}\[1\]{\langle#1\rangle} \begin{array}{rl} \ang{C} \to & \ang{A} \ang{C'}\\ \ang{C'} \to & \ang{B} \ang{C} \\; | \\; \epsilon\\ \end{array}$$

---
Tags: formal-grammars, parsers
---


# Question
Title: Scientifically acceptable method for comparing performance of algorithms
I am comparing several different algorithms for navigation applications. Since I may possibly be publishing a paper comparing the performance of these algorithms with each other, I was wondering the best way to go about measuring performance.

As far as I know, there are two ways to compare performance: writing the code in a compiled language like C and measuring the time of execution, or counting the number of FLOPS. However, I am aware that different processors have different capabilities which results in different execution times on different platforms.

These algorithms will be implemented on low-cost embedded systems (the main application is satellites, where low power is key).

So in summary: **what is the scientifically accepted way of comparing the performance of different algorithms?**

# Answer
There is no single answer. The answer depends upon the specific situation you are in. It's not that there is a single scientifically accepted way of evaluating performance. Instead, a paper should be driven by the claims you want to make. First, figure out what claims you want to make about your scheme. Then, figure out what evidence is needed to support those claims.

For instance, perhaps you would like to claim that your scheme is fast enough to deploy on low-cost embedded systems. Well, then your next step is to make that claim more precise: what counts as fast enough? how do you know? what specific systems do you mean? Then, you can evaluate performance on those systems, by that metric, and assess whether it is fast enough.

Or maybe you would like to claim that your scheme is faster than previously published approaches. Your next step would be to make that more precise: which previous approaches are you going to compare to? on what platform? with what workload? And then you'd evaluate on those platforms.

The right metric to use for performance will depend on your specific situation. For some, maybe it is wall-clock time. For others, maybe it is energy consumption (power). For still others, maybe it is guaranteed low-latency, or memory usage, or something else entirely.

In short: there is no single scientifically accepted method. Instead, think of science as (a) being precise about what claims you are making, and then (b) providing appropriate evidence to support those claims. What constitutes "appropriate evidence" will depend upon your specific situation. You can often look to other publications in your field to see what evaluation method they used, as initially guidance, but ultimately this is a matter of critical thinking: evaluating evidence in a logical, careful, thoughtful manner.
> 6 votes

# Answer
There are basically two ways to do it, big-O, and actual measurement.

Big-O matters if the size of the input dataset can become quite large. That's when you want O(1), O(n), or O(n log n). If the size of the dataset is more predictable, big-O becomes less important compared to actual times.

Regardless of big-O, there are constant factors, and it is generally under-appreciated how large those can be. (In an academic sense, a factor of 50 might not be important, but in real time, it's a different story.)

It's hard to compare different algorithms in real time, because it depends on how well they've been optimized. Often the same algorithm can be optimized several different ways, compounding its speed, and that's *before* the compiler's optimizer does its job. If I can give an example, *here's a case* where the same algorithm had multiple optimizations performed against it, reducing its time by a factor of 730. (People who have done serious performance tuning on real software are not too surprised by such a ratio.)

Only when an algorithm has been carefully tuned (which in general you cannot assume has been done) can its execution time be compared with another.
> 2 votes

# Answer
The paper should include both:

* a theoretical estimate of the time complexity, based on a count of a representative operation (like FP arithmetic operation, swap of two elements, comparisons...);
* an empirical measurement, preferably obtained for different problem sizes and realistic data distributions. The platform used to perform the test should be one which is popular in the corresponding application domain.

For top quality results, I recommend to run different problems for each size and provide the **standard deviation** in addition to average running time. (This is too rarely done.)
> 0 votes

---
Tags: algorithm-analysis, performance
---


# Question
Title: Deriving from a terminal word in a context free grammar
Just to make it clear. (since my book doesn't mention anything like this)

Suppose we have a context free grammar $G=(V,T,P,S)$. where $T=\\{a,b\\}$ (The other sets doesn't really matter).

Since $\Rightarrow^\*$ is the reflexive transitive closure of the relation $\Rightarrow$ on the set $(V\cup T)^\*$, I see no problem in writing a thing like $ab \Rightarrow^\* ab$ (where $ab\in T^\*$ and there are no variables on the left hand side of the arrow) since the $\Rightarrow^\*$ relation is reflexive.

Now I want to ask wether it common to write a thing like $ab \Rightarrow^\* ab$?

By definition I see no problem.

Thanks.

# Answer
There is absolutely no problem writing $ab \Rightarrow^\* ab$. It definitely happens in proofs.
> 3 votes

---
Tags: formal-languages, context-free, formal-grammars, tree-grammars
---


# Question
Title: Explaining the relevance of asymptotic complexity of algorithms to practice of designing algorithms
In algorithms and complexity we focus on the asymptotic complexity of algorithms, i.e. the amount of resources an algorithm uses as the size of the input goes to infinity.

In practice, what is needed is an algorithm that would work fast on a finite (although possibly very large) number of instances.

An algorithm which works well in practice on the finite number of instances that we are interested in doesn't need to have good asymptotic complexity (good performance on a finite number of instances doesn't imply anything regarding the asymptotic complexity). Similarly, an algorithm with good asymptotic complexity may not work well in practice on the finite number of instances that we are interested in (e.g. because of large constants).

Why do we use asymptotic complexity? How do these asymptotic analysis related to design of algorithms in practice?

# Answer
The interesting question is: what is the alternative? The only other method I know is testing/benchmarking. We program the algorithms, let them run on (a representative sample of) the finite input set and compare the results. There are a couple of problems with that.

* The results are not general in terms of machines. Run your benchmark on another computer and you get different results for sure, quantitatively, and maybe even qualitatively.
* The results are not general in terms of programming languages. Different languages may cause very different results.
* The results are not general in terms of implementation details. You literally compare *programs*, not algorithms; small changes in the implementation can cause huge differences in performance.
* If the worst-case is rare, a random input sample may not contain a bad instance. That is fair if you are concerned with average case performance, but some environments require worst-case guarantees.
* In practice, input sets change. Typically, inputs become larger over time. If you don't to repeat your benchmark every six months (yes, some data grow that fast), your results are worthless soon¹.

That said, ignoring all kinds of effects and constants in the analysis is typical, but can be called lazy (with respect to practice). It serves to *compare algorithmic ideas* more than to pinpoint the performance of a given (even pseudocode) implementation. It is well known to the community that this is coarse and that a closer look is often necessary; for example, Quicksort is less efficient than Insertion sort for (very) small inputs. To be fair, more precise analysis is usually *hard*².

Another, a posteriori justification for the formal, abstract viewpoint is that on this level, things are often clearer. Thus, decades of theoretic study have brought forth a host of algorithmic ideas and data structures which are of use in practice. The theoretically optimal algorithm is not always the one you want to use in practice -- there are other considerations but performance to make; think Fibonacci heaps -- and this label may not even be unique. It is hard for a typical programmer concerned with optimising arithmetic expressions would come up with a new idea on this level (not to say it does not happen); she can (and should) perform those optimisations on the assimilated idea, though.

There are formal, theoretic tools to close the gap to practice to some extent. Examples are

* considering memory hierarchy (and other I/O),
* analysing the average case (where appropriate),
* analysing numbers of individual statements (instead of abstract cost measures) and
* determining constant factors.

For example, Knuth is known for literally counting the numbers of different statements (for a given implementation in a given model), allowing for precise comparison of algorithms. That approach is impossible on an abstract level, and hard to do in more complex models (think Java). See \[4\] for a modern example.

There will always be a gap between theory and practice. We are currently working on a tool³ with the goal to combine the best of both worlds to make sound predictions for both algorithmic costs and runtime (on average), but so far we have not been able to do away with scenarios where one algorithm has higher costs but smaller runtime (on some machines) than an equivalent one (although we can detect that, and support finding the reason).

I recommend for practictioners to use theory to filter the space of algorithms before running benchmarks:

```
if ( input size forever bounded? ) {
  benchmark available implementations, choose best
  schedule new benchmarks for when machine changes
}
else {
  benchmark implementations of all asymptotically good algorithms
  choose the best
  schedule new benchmarks for when machine changes or inputs grow significantly
}

```

---

1. There can be crazy changes in absolute and relative performance once the number of cache misses increases, which typically happens when inputs grow but the machine stays the same.
2. As in, leading researchers in the field are not able to do it.
3. Find the tool here. An example use has been published in Engineering Java 7's Dual Pivot Quicksort Using MaLiJAn by S. Wild et al. (2012) \[preprint\]
4. Average Case Analysis of Java 7’s Dual Pivot Quicksort by S. Wild and M. Nebel (2012) -- \[preprint\]
> 25 votes

# Answer
I assume that this question arises from teaching a course which includes asymptotic analysis. There are several possible answers as to why this material is taught in introductory classes:

* Asymptotic analysis is a mathematical abstraction which yields itself to analysis. As (arguably) mathematicians, we want to be able to analyze algorithms, and they only way to tame their complexity is using asymptotic analysis.
* Evaluating the asymptotic performance of an algorithm does point out some principles which are useful in practice: for example, concentrate on that part of the code which takes the majority of time, and discount any part of the code which takes an asymptotically negligible part of time.
* Some of the techniques of asymptotic analysis are useful. I'm referring here mainly to the so-called "master theorem", which in many circumstances is a good description of reality.
* There is also a historical reason: when people first started to analyze algorithms, they earnestly thought that asymptotic complexity reflects practical usage. However, eventually they were proved wrong. The same thing happened with P as the class of efficiently solvable problems, and NP as the class of intractable problems, both of which are misleading in practice.

Personally, I think that asymptotic analysis is a reasonable part of the curriculum. More questionable parts include formal language theory and complexity theory (anything that has to do with a Turing machine). Some people make the argument that while these subjects are not useful to the would-be programmer per se, they do instill in her a certain mind-thought which is necessary to be a good practician. Others argue that theory sometimes influences practice, and these rare cases are enough to justify teaching these rather arcane subjects to the general computer science audience. I would rather have them learn history or literature, or any other subject they are actually interested in; both are as relevant to their future job prospects, and more important for them as human beings.
> 11 votes

# Answer
There are two serious reasons to use asymptotic analysis of running times:

* to abstract away unimportant details. In many applications where we need non-trivial algorithms, most of the time is spent on problem instances that require medium to large numbers of operations, and we are more interested in the general trend than the exact operation count. In these applications, behavior for small $n$ is uninteresting.
* to allow mathematical tractability. Cases such that it is possible to find exact expressions for the operation count are exceptional. Studying asymptotics opens more possibilities (like asymptotic approximations of complicated functions are handy).

And there are many others (like machine independence, meaningfulness, comparability...).
> 7 votes

# Answer
As noted in Raphael's answer, exact computation of worst-case running time can be very difficult. Exact computation can also be unnecessary since the RAM model already introduces approximations. For example, do all operations really take equal time? Specific implementations (hardware, optimizations) might speed up an algorithm by constant factors. We want to understand how effective an algorithm is *independent* of these factors. This is a big motivation for the use of asymptotic analysis.
> 6 votes

# Answer
Because asymptotics are "simple" (well, simpler than doing the exact analysis for finite cases, anyway).

Compare e.g. the encyclopaedic "The Art of Computer Programming" by Knuth, which does detailed analysis of all important algorithms (and many not-so-important ones) with the rule-of-thumb analysis that is often enough to get an asymptotic estimate (or just a bound), as practiced in most "algorithms" books.

You are certainly right. *If* the problem is important enough, a Knuth style (or perhaps a bit less detailed) analysis may well be warranted. In *many* cases, a hint at the asymptotic complexity (perhaps average with dispersion) fitted to experimental data is enough. In *most cases*, to do a *rough classification* of competing algorithms, as a first weed-out round comparing asymptotics can be precise enough. And if there are no contenders, getting the bad news of the exact cost in minute detail is just masochism.
> 3 votes

# Answer
Here by asymptotic analysis I assume we mean the behavior of algorithm as the size of the input goes to infinity.

The reason we use asymptotic analysis is because **it is useful in predicting the behavior of algorithms in practice**. The predictions allow us to make decisions, e.g. when we have different algorithms for a problem which one should we use? (Being useful doesn't mean it is always correct.)

The same question can be asked about any simplified model of real world. Why we use simplified mathematical models of the real world?

Think about physics. The classical Newtonian physics is not as good as relativistic physics in predicting the real world. But it is a good enough model for building cars, skyscrapers, submarines, airplanes, bridges, etc. There are cases where it is not good enough, e.g. if we want to build a satellite or send a space probe to Pluto or predict the movement of massive celestial objects like stars and planets or very high speed objects like electrons. *It is important to know what are the limits of a model.*

1. **It is typically a good enough approximation of the real world.** In practice we see often that an algorithm with better asymptotic analysis works better in practice. It is seldom the case that an algorithm has better asymptotic behavior So if the inputs can be large enough then we can typically rely on asymptotic analysis as a first prediction of algorithms behavior. It is not so if we know the inputs are going to be small. Depending on the performance we want we may need to do a more careful analysis, e.g. if we have information about the distribution of the inputs the algorithm will be given we can do a more careful analysis to achieve the goals we have (e.g. fast on 99% of inputs). The point is as a first step asymptotic analysis is a good starting point. In practice we should also make performance tests but keep in mind that also has its own issues.
2. **It is relatively simple to compute in practice.** Typically we can compute at least good bounds on the asymptotic complexity of an algorithm. For simplicity let's assume that we have an algorithm $A$ that outperforms any other algorithm on every input. How can we know $A$ is better than others? We can do asymptotic analysis and see that $A$ has better asymptotic complexity. What none of them are better than the other in all inputs? Then it becomes more tricky and depends on what we care about. Do we care about large inputs or small inputs? If we care about large inputs then it is not common that an algorithm has better asymptotic complexity but behaves worst on large inputs that we care. If we care more about small inputs then asymptotic analysis might not be that useful. We should compare the running time of the algorithms on inputs we care. In practice, for complicated tasks with complicated requirements asymptotic analysis might not be as useful. For simple basic problems that algorithm textbooks cover it is quite useful.

In short asymptotic complexity is a relatively easy to compute approximation of actual complexity of algorithms for simple basic tasks (problems in a algorithms textbook). As we build more complicated programs the performance requirements change and become more complicated and asymptotic analysis may not be as useful.

---

It is good to compare the asymptotic analysis to other approaches for predicting the performance of algorithms and comparing them. One common approach is performance tests against random or benchmark inputs. It is common when computing the asymptotic complexity is difficult or unfeasible, e.g. when we are using heuristics as in say SAT solving. Another case is when the requirements are more complicated, e.g. when a program's performance depends on outside factors and our goal might be to have something that finishes under some fixed time limits (e.g. think about updating interface shown to a user) on 99% of the inputs.

But keep in mind that performance analysis also has it's issues. It does not provide mathematical grantees on the performance on less we actually run the performance test on all inputs that will be given to the algorithm (often computationally infeasbile) (and it is often not possible to decide some inputs will never be given). If we test on against a random sample or a benchmark we are implicitly *assuming* some *regularity* about the performance of the algorithms, i.e. the algorithm will perform similarly on other inputs that were not part of the performance test.

The second issue with performance tests is that they depend on the test environment. I.e. the performance of a program is not determined by the inputs alone but outside factors (e.g. machine type, operation system, efficiency of coded algorithm, utilization of the CPU, memory access times, etc.) some of which might vary between different runs of the test on the same machine. Again here we are assuming that the particular environments that performance test are carried out are similar to the actual environment unless we do the performance tests on all environments that we may run the program on (and how can we predict what machines someone might run a sorting algorithm on in 10 years?).

Compare these to computing the asymptotic running time of say MergeSort ($\Theta(n \lg n)$) and comparing it with the running time of say SelectionSort ($\Theta(n^2)$) or BinarySerch ($\Theta(\lg n)$) with LinearSearch ($O(n)$).
> 3 votes

# Answer
how about a simple near-visceral illustrative example using one of the most ubiquitous algorithms/applications in CS, namely sorting? Bubblesort takes $O(n^2)$ both average and worst case time and quicksort about $O(n \log n)$ on average and only $O(n^2)$ "rarely" in worst case. a nice way to see the difference is to look at the side-by-side, synchronized animations of sorting random arrays & their performance. almost always the bubblesort will take "longer" and one will be left *waiting* for it to finish in comparison to quicksort.

now imagine that *wait* repeated in the code as many times as the code is called. how does one mathematically quantify/justify this apparent superiority of the quicksort algorithm? (ie is its name really justified or is it just a marketing slogan?) via asymptotic complexity measurements. one is left looking at the animations *subjectively feeling* that bubblesort is somehow a *weaker* algorithm and asymptotic complexity analysis can *prove* this quantitatively. but note that asymptotic complexity analysis is just one tool in the bag of tools to analyze algorithms and its not always the ultimate one.

and its worth looking at the side-by-side code also. bubblesort seems to be *conceptually simpler* and doesnt use recursion. quicksort is not as immediately comprehended esp the "median of 3" pivot principle. bubblesort might be implemented just in loops without a subroutine, whereas quicksort might typically have at least one subroutine. this shows the pattern that more code sophistication can sometimes improve the asymptotic complexity at the expense of code simplicity. sometimes there is an extreme tradoff similar to the concept of diminishing marginal returns (orig from economics) where very large amts of code complexity \[requiring entire papers full of thms and proofs to justify\] only buys very small improvements in asymptotic complexity. this shows up as an example esp with matrix multiplication and can even be graphed.
> -2 votes

---
Tags: algorithms, complexity-theory, education
---


# Question
Title: Depth first or breadth first ordering in binary search trees?
Let's say that I make a binary search tree and store it in an array so that I end up with an array that is more cache friendly to binary search compared to a sorted array.

The binary tree is full on all levels except possibly the last level, where it is filled from left to right.

Specifically index 0 is the root node, and to get to a left child, you multiply current index by 2 and add 1. To get to a right child you multiply current index by 2 and add 2.

Going this route, as i understand it, the node order is breadth first.

I've seen people mention that depth first is better (in a paper about parallel GPU bvh construction), and was wondering, is there a good reason to choose depth first over breadth first, or is it highly dependent on specific usage patterns?

# Answer
> 5 votes
There's a paper on this: Khuong and Morin. Array Layouts For Comparison-Based Searching

They compare the Eytzinger, B-Tree, Van Emde Boas, and sorted array layouts and conclude that Eytzinger works best. The reasons are fairly complex, since things like simple address arithmetic and branch predictability combine with memory prefetch and processor features like speculative execution. They also rely on doing a fair amount of extra work by prefetching blocks which have only a small chance of matching the search argument.

However they do give a clear exposition of each mechanism.

# Answer
> 5 votes
Think about what happens when you move from one layer in the tree to the next. When you start getting to layers with progressively more nodes, you'll eventually get to a spot where the layers are so big that they can't fit into memory caches. When that happens, if you've laid out the memory in a BFS order, then going from one layer to the next will almost always cause a cache miss because the memory fetched for the first layer won't include the node from the next layer in it. In other words, every link followed will cause a cache miss. On the other hand, if you use DFS order, then the memory for the nodes will have the nodes broken apart into smaller chains of nodes corresponding to the paths taken by DFS. If you do lookups in a way that follows those chains, it's possible that you'll have no cache misses at all when going from one node to the next, which can dramatically speed up lookups.

The ordering I've actually heard most for making cache-friendly BSTs is the van Emde Boas layout, which is formed as follows:

* If the tree has height two or less, lay it out in DFS or BFS order (they're the same here).
* Otherwise, split the tree at the middle level into a "top tree" of the first half of the nodes and up to $\sqrt{n}$ "bottom trees" formed from the lower levels. Recursively compute the van Emde Boas layouts of each of these trees, then concatenate them together in order.

You can prove that this layout is optimal assuming that you don't know anything about the particular sizes of the caches of the machines in the computer (it's known as a *cache-oblivious* data structure).

If you do know the cache size, though, the "best" choice is probably to use a B-tree instead of a BST, since B-trees are specifically designed to play nicely with caches. Although they were designed for on-disk storage, they work really well in main memory, as some recent work has shown.

# Answer
> 2 votes
I might be confused as I usually see DFS or BFS in connection with tree *traversing*, as opposed to binary *searching*. You mean to store tree items sequentially in an array in the traversed order, I guess...

But what I think you are after are cache-oblivious algorithms (also here and here). There are many links I could post here but instead you could try to search for "cache oblivious {tree, btree, layout, heap, search, ...}". Especially interesting is so-called "van Emde Boas layout" which makes the optimal number of memory transfers.

Also try to look at D-heap and B-heap, even if they are not exactly binary search related.

---
Tags: binary-trees, search-trees, cpu-cache
---


title: Probable focal point of a set of rays

text:
# Question
Title: Probable focal point of a set of rays
Given a set of two-dimensional rays, how can I determine the probable focal area of the rays?

For simplicity, assume a circle focal area.

Imagine a number of people throwing paper airplanes at a circular target. Some small percent are throwing in the completely wrong direction.

Is there any algorithm that can help me determine a circle (or ideally polygon) of the intended location of the rays?

# Answer
> 1 votes
One possible approach is to try RANSAC. RANSAC is applicable where we expect: (a) some fraction of the observations (the rays) are erroneous (outliers) and should be ignored, and (b) the remaining ones are all approximately consistent with some low-dimensional probabilistic model. The RANSAC method then tries to find the best model that (a) minimizes the number of outliers, and (b) among all such models, is as consistent as possible with the remaining observations.

In your case, RANSAC might work well enough. Some small fraction of the rays are in a completely wrong direction, and will be ignored as outliers. The remaining ones should all be roughly consistent. The model could be (for instance) a two-dimensional Gaussian with diagonal covariance matrix. Such a model has 4 free parameters, so given 2 or more rays, you can fit a Gaussian to it. Given a model, you can identify which rays are inliers (plausibly consistent with the model) and which rays are outliers.

Given this, one way to apply RANSAC to your problem would be to repeat the following recipe 1000 times:

* randomly pick 5 rays
* fit a Gaussian to those 5 rays
* for each ray, compute the likelihood that it came from that Gaussian, and throw away all those whose likelihood is below some threshold (these are the outliers)
* fit a new Gaussian to all those remaining rays (the inliers)
* count how many rays remain consistent with the revised model (i.e., count the number of inliers)

Then keep the model with the largest number of inliers, and use the corresponding Gaussian as your model. In particular, the mean of that Gaussian is your best guess for the target, and the equal-likelihood contour of that Gaussian (the counter corresponding to 2 standard deviations away from the mean) is your circle. All of the above constants (1000, 5, 2) can be tuned, and variants of this algorithm can be considered.

Why does this work? Suppose 80% of the rays are correct and 20% are thrown in the completely wrong direction. Then a random sample of 5 of the rays will, with probability $0.8^5 \approx 0.33$, contain only good rays, and when you fit a Gaussian to them, will give a reasonable estimate of the target and the surrounding circle. The remaining 67% of samples will have at least one bad ray, which causes a bad model, but the bad models will be thrown away.

The general idea of this sort of approach is: (1) identify a scoring function, which given a model gives you a score for the model; (2) repeatedly pick a random sample of a few rays, fit a model to that sample, use the model to identify outliers, discard the outliers and fit a model to the remaining inliers, and then compute the score of the resulting candidate model; keep the best model you've ever seen. You can play with the type of model you allow, and the scoring function you use.

Some form of expectation-maximization (EM) potentially might yield even better results.

---
Tags: graphics, polygons
---


# Question
Title: How to solve an optimization problem that deals with the optimal combination of given ratios?
I'm volunteering for a non-profit, and was asked to write a program for this problem, but I'm having a little trouble tackling it. Here's the problem:

So they're a daycare, and they get paid by the government depending on specific ratio's of staff to children. Here are the possible ratios and their pay:

* one staff to 3 children (3:1). Pays 14.71 dollars per hour
* one staff to 2 children (2:1). Pays 9.10 dollars per hour
* one staff to 1 child (1:1). Pays 7.28 dollars per hour

With every possible number of staff and number of children in the daycare, there is a combination of ratios that will give the maximum profit. How do I find those ratios? Are there any clever ways to approach this problem?

The inputs of this ideal program would be number of staff and number of children, and the output would be the combination of ratios that produces the maximum profit.

# Answer
> 1 votes
If the number of children $n$ is fixed and there is no limit on the number of staff members you can potentially hire, here's one way you can maximize the amount the government pays you:

You can use linear programming (LP). Let $s\_1$ denote the number of staff you hire to manage one-child classrooms; $s\_2$ the number of staff you hire to manage two-child classrooms; and $s\_3$ the number of staff you hire to manage three-child classrooms. The number of children you can handle, with this configuration of staff, is $s\_1 + 2s\_2 + 3s\_3$. Also, the amount paid by the government is $7.28 s\_1 + 9.10 s\_2 + 14.71 s\_3$. You want to maximize the payoff, subject to the constraints $s\_1 \ge 0$, $s\_2 \ge 0$, $s\_3 \ge 0$ and to the constraint $s\_1 + 2 s\_2 + 3 s\_3 \ge n$ (i.e., you have capacity to take care of $n$ children).

Of course, this formulation is silly, because under this formulation the way to maximize your profit is to maximize the number of staff chosen. That's because this formulation doesn't take into account the cost of hiring staff or any other consideration. So you'll need to adjust it to incorporate the additional constraints you have.

Fortunately, this LP formulation makes it easy to incorporate additional constraints. For instance, suppose there are only 100 qualified people who you'd possible be willing to hire as staff, so you simply can't hire more than a total of 100 staff members. That can be handled by adding the additional constraint $s\_1 + s\_2 + s\_3 \le 100$.

In practice there's probably some cost per staff member you hire, so in practice we probably want to maximize not the amount the government pays us, but the amount of "profit" left over after paying the staff members. Suppose each staff member costs 5 dollars per hour. Then you would adjust the above by maximizing the revenue minus the costs, i.e., $(7.28 s\_1 + 9.10 s\_2 + 14.71 s\_3) - (5.00 s\_1 + 5.00 s\_2 + 5.00 s\_3)$.

In practice you want to only hire an integer number of staff, so you might want to use an integer linear programming (ILP) solver rather than a LP solver.

I still question whether this is the right metric for a non-profit to be maximizing. Instead of focusing only on "profit", I would anticipate that a non-profit would care about the benefit to stakeholders or soceity: e.g., the benefit to the children served, or the number of children served, or some combination of benefit and leftover "profit". For instance, all else being equal, is the benefit greater if a child is cared by a single staff member rather than sharing a staff member with two other children? I suspect so, but that isn't incorporated in your "profit maximization" formulation. Thus, I suspect the right objective function to maximize might be something different, chosen to take into account that the goal of a non-profit is not to derive a profit but to accrue some social benefit.

# Answer
> 1 votes
First of all you should specify what is the input and the desired output of the algorithm.

I will assume that the input is the number of staff and the number of children, and the output the desired combinations of children/stuff that maximize the profit. I think it can be expressed as a Knapsack Problem. In the knapsack problem the objective is to choose a combination of objects where each object has a value and a weight, the combination must be choosen such that the sum of the weights doesn't exceed a given maximum weight capacity (The knapsack capacity) and the sum of the values is maximized.

In your problem each object is the combination of staff/children. Here I'm assuming that the amount of money paid by 3:1 is for example the same of the amount to be paid by a 9:3 combination.

The value of each object is the amount of dollars by hour given by the rules you've described above.

The weights are number of staff and children in each item, for example an object could be (4,5) and the weight of the "knapsack" is the maximum staff and children given by the input of the algorithm. Note that this is not the classic version of the Knpasack problem because you have two dimensions in the weight (The number of staff and the number of children), more over in the "classic" version known as 0-1 knapsack every item can be picked only once, I don't really know of if that is your case you should adapt the problem according to your constraints (And not in the inverse way).

Before the edit I said that you may apply the Dynamic Programming algorithm, you should be careful because it applies when the problem is 0-1 i.e. when each object is allowed to be choosen only once. Depending on your final model of the problem an exact algorithm may or me be not used (Remember that Knapsack is NP-Hard).

---
Tags: algorithms, optimization, assignment-problem
---


title: Why is this NPDA?

text:
# Question
Title: Why is this NPDA?
I am studying PDA at the moment, and I came up with this question.

The figure above tells me that although both PDA accept the same language, one is non-deterministic and the other is deterministic. I don't understand the reason why the first one in non-deterministic. As far as I know, the conditions for DPDA is that

1) every transition should have at most one move

2) if $\delta$(q,a,X) is not empty, then $\delta$(q,$\epsilon$,X) should be empty.

However, since the first PDA does satisfy the above conditions therefore I thought it is DPDA.

What am I missing?

Thanks in advance.

# Answer
The first PDA doesn't comply the second condition because $|\delta (q0,a,\epsilon)| = |\delta (q0,\epsilon,\epsilon)| = 1$.
> 5 votes

---
Tags: automata, pushdown-automata
---


# Question
Title: Are there any problems that require exponential time in quantum computing?
Given the fact that the qbits have superpositions, and have more representational power compared to circuits, are there any problems that require at least exponential time to guarantee a solution with a quantum computer?

I've checked the Complexity Zoo and couldn't find any complexity class mentioned there that fits this description.

# Answer
Most problems that require exponential time on a classical computer also require exponential time on a quantum computer. For example EXPTIME-complete problems will require exponential time on either a classical or a quantum computer.

The class of problems solvable in polynomial time on a quantum computer is called BQP. It is believed unlikely that BQP contains the NP-complete problems. Thus the NP-complete problems probably take exponential time on quantum computers.

One of the most interesting problems that is known to be in BQP, but believed not to be in P is the integer factoring problem. But integer factoring is believed unlikely to be NP-complete.
> 12 votes

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


# Question
Title: Is there a way to incrementally degrade the quality of a PRNG?
I have an application that depends on a random number generator to perform. The application might be sensitive to the quality of the random numbers, but I don't know for sure. I'd like to test this, and if it is, what the degree of sensitivity is.

I've currently got a xorshift1024\* PRNG plugged in. It's fast and I can directly inject a full 1024 bit state.

I need to be able to degrade it in a controlled fashion, ranging from it's high quality native mode to something quite bad. By quite bad, I mean something far far worse than a simple linear congruential generator. I'm not interested in slowly changing it's output distribution from uniform to say, normal. I just want to be able to make it (technically) crappier and crappier.

I have the sense that this might be a common requirement in other testing applications, so there might be a best practice methodology. At this point my only alternative is to switch off the generator entirely.

Is there a way to incrementally degrade the quality of my PRNG?

# Answer
> 4 votes
There are many possible ways to degrade its output, but here is one simple choice:

Think of your PRNG as outputting a sequence of bits. For a good PRNG, each bit would be uniformly distributed (equally likely to be 0 or 1), independent of the previous bits. We can build a degraded PRNG where each bit of the output is 1 with probability $p$ or 0 with probability $1-p$, independent of all of the previous bits. This gives us a parameter $p$ that can be varied from $1/2$ down to $0$: with $p=1/2$, there's no degradation, and smaller values of $p$ correspond to increasing amounts of degradation. Effectively, $p$ is a tuning knob that allows us to control the amount of degradation.

From this, you can derive a way to get other quantities. If you want a 32-bit integer, you generate each of its bits using this degraded PRNG. etc.

This model has some nice properties. For instance, if you generate a random $k$-bit value using your degraded PRNG, the resulting value will have $k h\_2(p)$ bits of entropy. This varies from $k$ bits smoothly down to $0$ bits as $p$ varies from $p=1/2$ down to $p=0$. As a very crude approximation, the $k$-bit value will be approximately uniformly distributed on a set of size $2^{k h\_2(p)}$; as $p$ gets smaller (as you introduce more degradation), the size of this set gets smaller smoothly.

Of course, we can't tell you whether this is the "right" degradation model for your particular application, as that will depend on your particular application. There are many other possible ways of degrading a PRNG's output, and since we haven't been given any specific criteria for selecting among them, I have semi-arbitrarily chosen one that is especially simple to implement and simple to think about.

---
Tags: pseudo-random-generators
---


# Question
Title: Scheduling distributed computational graph
I work in computational fluid dynamics. And I spend most of my time waiting for simulation to complete.

The common way to improve simulation performance is to use a suitable distributed linear algebra library, a big computer with Infiniband, tweek some parameters and hope for the best.

Most of my simulations can be seen as many iterations of a single big "computational graph" of mul/div/add, without a single branch. It seems that finding a optimal scheduling for this computation could be seen as a optimization problem.

The absence of branch, the complete knowledge of the architecture (Memory hierarchy, number of functional units, communication interface...) and the fact that the same graph will be used many time make me think that some very aggressive optimization could be done ahead of time.

As some work been done in computer science to find a optimal scheduling for a "computational graph" and a given architecture?

# Answer
> 1 votes
The general problem of mapping a graph, where nodes are computational operations and edges are transfers of data (i.e. dependencies), to computational resources is known as graph partitioning.

The general graph partitioning problem is NP-hard and therefore not directly solvable. However, there are good heuristic approaches. There are a number of open-source frameworks for graph partitioning, for example Metis, Scotch and Zoltan.

---
Tags: graphs, optimization, computer-architecture, scheduling, linear-algebra
---


# Question
Title: Can the zero-one principle be used to prove the stability of a sorting network
When dealing with sorting networks, we can check the validity of a sorting network with only $2^n$ sequences of $0$ and $1$ (where $n$ is the size of the collection to sort) thanks to the zero-one principle:

> The zero-one principle states that, if a sorting network can correctly sort all $2^n$ sequences of zeros and ones, then it is also valid for arbitrary ordered inputs.

I have used this principle to prove that my sorting networks worked. However, I also wanted to check whether some of them were stable or not: in order to do so, I tried to feed pairs of $(0, index)$ and $(1, index)$ to the networks instead of simple $0$ and $1$ and checked whether the indices of elements with the same values were still in the correct order after the sort (of course, the sequences were sorted based only on the first value of the pair). It was sufficient to prove that my sorting networks weren't stable since the algorithm was able to find at least one sequence that wasn't stably sorted per network.

However, even if every sequence was stably sorted, I still wouldn't be sure whether the sorting networks are stable or not without answering this question: can the zero-one principle be used to prove the stability of a sorting network?

# Answer
> 2 votes
You can use a $0/1/2$ principle, in which the inputs are $\\{0,1,2\\}$, and $1$-inputs are also annotated by their indices. The network should sort the input successfully, maintaining the order of the $1$-entries. This is clearly a necessary condition, and it's not too hard to show that it is sufficient.

That doesn't quite answer your own question, though I conjecture that your criterion isn't sufficient. All one needs to do in order to prove my conjecture is to give a sorting network satisfying your condition but not mine. You can try looking for such a network using a computer. If you can find no such network, perhaps your criterion does work after all.

---
Tags: algorithms, sorting
---


title: Find value of b

text:
# Question
Title: Find value of b
The following system of restrictions is given:

$$y\_1+ 2 y\_2 \leq 4 \\ 2y\_1+y\_2 \leq 2 \\ y\_1+b y\_2 \leq 3 \\ y\_1, y\_2 \geq 0$$

For which values of b is there a degenarate basic feasible solution?

Can we make a drawing to see when we will have a degenarate basic feasible solution?

The first tableau is:

$\begin{matrix} B & b & P\_1 & P\_2 & P\_3 & P\_4 & P\_5 & \theta & \\ P\_3 & 4 & 1 & 2 & 1 & 0 & 0 & 2 & L\_1\\ P\_4 & 2 & 2 & 1 & 0 & 1 & 0 & 2 & L\_2\\ P\_5 & 3 & 1 & b & 0 & 0 & 1 & \frac{3}{b} & L\_3 \end{matrix}$

We assumw that $\frac{3}{b} \leq 2$.

We choose $P\_2$ to get in the basis.

We get the following tableau $(\star)$:

$\begin{matrix} B & b & P\_1 & P\_2 & P\_3 & P\_4 & P\_5 & \theta & \\ P\_3 & 4-\frac{6}{b} & 1-\frac{2}{b} & 0 & 1 & 0 & -\frac{2}{b} & & L\_1'=L\_1-2L\_3'\\ \\ P\_4 & 2-\frac{3}{b} & 2-\frac{1}{b} & 0 & 0 & 1 & -\frac{1}{b} & & L\_2'=L\_2-L\_3'\\ \\ P\_2 & \frac{3}{b} & \frac{1}{b} & 1 & 0 & 0 & \frac{1}{b} & & L\_3'=\frac{L\_3}{b} \end{matrix}$

We have a degenerate basic feasible solution if $4-\frac{6}{b}=0$ or $2-\frac{3}{b}=0$. Both of the above equalities give $b=\frac{3}{2}$.

Then we suppose that $b\> \frac{3}{2}$.

We choose $P\_5$ to get in the basis.

Then we get the same tableau as the initial one.

If after the tableau $(\star)$ we choose $P\_1$ to get in the basis we get the following tableau:

$\begin{matrix} B & b & P\_1 & P\_2 & P\_3 & P\_4 & P\_5 & \theta & \\ P\_3 & \frac{6b-9}{2b-1} & 0 & 0 & 1 & \frac{2-b}{2b-1} & \frac{3}{1-2b} & & L\_1''=L\_1'-\left(1-\frac{2}{b} \right)L\_2''\\ \\ P\_1 & \frac{2-\frac{3}{b}}{2-\frac{1}{b}} & 1 & 0 & 0 & \frac{1}{2-\frac{1}{b}} & \frac{1}{1-2b} & & L\_2''=\frac{L\_2'}{2-\frac{1}{b}}\\ \\ P\_2 & \frac{4}{2b-1} & 0 & 1 & 0 & \frac{1}{1-2a} & \frac{2}{2b-1} & & L\_3''=L\_3'-\frac{1}{b}L\_2'' \end{matrix}$

Is it right so far? Do we have to check now what happens if P\_4 gets in the basis and what if P\_5 gets in the basis?

# Answer
I don't know your method so I can't comment on it. Below is another method which gives the answer in this case, but may be less efficient than yours for larger systems.

---

A degenerate basic feasible solution exists if there is a solution for which more than two constraints are tight. So the first step is to find basic feasible solutions without the constraint $y\_1+by\_2 \leq 3$. Some of these might already be degenerate, and for these we can choose any value of $b$ for which the solution satisfies $y\_1+by\_2 \leq 3$. For the rest, we need to choose $b$ so that the solution satisfies $y\_1+by\_2 = 3$, if any.

We therefore need to go over all possible basic feasible solutions of the first two and last two inequalities, and this we can do by going over all $\binom{4}{2}$ choices of tight constraints:

1. $y\_1 + 2y\_2 = 4$, $2y\_1 + y\_2 = 2$: then $y\_1 = 0$, $y\_2 = 2$. The constraint $y\_1 = 0$ is also tight, so any value of $b$ for which $0 + 2b \leq 3$ works here.
2. $y\_1 + 2y\_2 = 4$, $y\_1 = 0$: covered by case 1.
3. $y\_1 + 2y\_2 = 4$, $y\_2 = 0$: then $y\_1 = 4$, so the second constraint is violated.
4. $2y\_1 + y\_2 = 2$, $y\_1 = 0$: covered by case 1.
5. $2y\_1 + y\_2 = 2$, $y\_2 = 0$: then $y\_1 = 1$, so the first constraint is satisfied. For this to be degenerate, we need $1 + 0b = 3$.
6. $y\_1 = y\_2 = 0$: all constraints are satisfied. For this to be degenerate, we need $0 + 0b = 3$.

All in all, we get $b \leq 3/2$.
> 2 votes

---
Tags: linear-programming
---