# Question
Title: Computationally 'hard' polynomial-time reduction to other NP-complete problems / Hierarchy of NP-complete problems
As we all know there exist plenty of polynomial-time reductions from one NP-complete problem to another. Are there any NP-complete problems that have a rather large polynomial bound for reductions to other NP-complete problems, like a poly-time sub-hierarchy of NP-complete problems...?

E.g. lets assume I have NP-complete problem A and B. They are reducible to each other in lets say at most $n^3$. Does there exist a NP-complete problem such that the best known reduction to both A and B (and all other) is, lets say, $n^{100}$.

1. Question: Are there (non-special-tailored) NP-complete problems with a large best known (deterministic?) polynomial-time reduction?
2. Question: Is there a upper (deterministic?) polynomial bound for polynomial-time reductions between NP-complete problems

(There is a question here asking for a hierarchy of NP-complete problems but with a different base-problem, so solution does not really answer my question: Understanding reductions: Would a polynomial time algorithm for one NP-complete problem mean a polynomial time algorithm for all NP-complete problems?)

# Answer
> 6 votes
There are no upper bounds on the complexity of polynomial-time reductions between $\mathrm{NP}$-complete problems, other than that they're in polynomial time.

Let $\mathrm{NP}\_k = \mathrm{NTIME}\[O(n^k)\]\setminus\mathrm{NTIME}\[O(n^{k-1})\]$. By the nondeterministic version of the time hierarchy theorem, there are problems in $\mathrm{NP}\_k$, for all $k$.

Let $X$ be any $\mathrm{NP}$-complete problem. There is some $t$ such that $X\in\mathrm{NTIME}\[n^t\]$. Consider some problem $L\in\mathrm{NP}\_k$ for some $k\>t$. If we have a reduction from $L$ to $X$ that runs in time $n^r$, then we can solve an instance of $L$ in time $O(n^{rt})$ by first running the reduction, which creates an $X$-instance of length $O(n^r)$, and then solving that instance in time $O((n^r)^t)$. This contradicts the nondeterministic time hierarchy theorem if $k\>rt$.

# Answer
> 0 votes
The graph of explicitly described reductions between NP-complete problems looks a lot more like a tree than a complete graph. So for most pairs of NP-complete problems the best known reduction follows a rather long path through that tree. Due to the blowup at each step I doubt that you'd want to implement the resulting reductions.

I doubt that there is an upper bound on the reduction size. You surely can come up with artificial problems that are very difficult to reduce to, say, SAT. I'm not aware of any family of problems with known (increasing) lower bounds for reductions though.

---
Tags: complexity-theory, time-complexity, np-complete, polynomial-time
---


# Question
Title: Which algorithm for counting the occurrences of a certain pattern (spots) in an image?
**The Problem :**

Finding the number of occurrences of a certain pattern (or shape) in an image. In my example, the problem is about finding the number of spots (in variety of sizes) in an image. See figure 1 below:  What I'm looking for here is an orientation. What class of algorithms can lead to a solution for this type of problems?

# Answer
> 3 votes
The best way to get an orientation is to read a textbook on computer vision or image processing. There are lots of techniques known, and that's often the best way to get an introduction to a broad topic like this.

Anyway, for some specific techniques, I would recommend that you learn about the following candidate approaches:

Your task looks pretty easy, so I imagine you should be able to find a very effective combination of techniques if you learn about them and try them out on sample images.

# Answer
> 1 votes
There is one book freely available worth mentioning: Computer Vision Algorithms and Applications by Richard Szeliski.

If there is possibility that background is black and elements are not overlapping the object detection eases to scan through pixels while they are black and then using modified flood fill algorithm, connecting everything that is not black an marking as visited pixels underneath.
During flood fill all pixel positions should be stored to calculate center and probably other statistics like principal component.

# Answer
> 1 votes
First thing, you must be clear about the pattern because computer vision has still focused on pattern specific algorithms.

If I consider your pattern is circularity if I am not wrong you are asking how to measure the number of circular instances in an image?

To solve such query, you should go for the question "How to measure the circularity?" The question will lead you towards the hough transform algorithms. There are number of algorithms based on Hough Transform.

I prefer this, and that is your answer to measure circular instances in an image. It will also give you how much circular they are.

T.J Atherton, D.J. Kerbyson. "Size invariant circle detection." Image and Vision Computing. Volume 17, Number 11, 1999, pp. 795-803.

# Answer
> 0 votes
If the images your problem should deal with are like the ones you show, then you must check the watershed algorithm. There is a paper by Vicent and Soille, that has a good algorithm. However prior to apply this, you should also implement, digitalization (automatic is preferable), and distance transform. Some filtering is advisable too before you apply watersheding

---
Tags: machine-learning, image-processing, computer-vision, pattern-recognition
---


# Question
Title: Fibonacci Heap / Binomial Heap - Decrease Key
I've been implementing a Fibonacci Heap in C this past week and today I just hit a mental roadblock that I can't figure out.

Decrease Key is a function that almost all min heaps have (vice versa with increase key with max heaps). However all of the decrease key functions declarations look like this:

```
// Big Theta 1 performance.
void decrease_key(Node n);

```

That's great, but what about `Node find_node(Object data);`?

Before you can decrease the key of the node, you have to locate it first. So the call of

`decrease_key(52,17)` first needs to search for `52`, then update it to `17`, and then restructure the tree (unless structure is lazy, such as fib tree). Doesn't that absolutely murder the complexity of that call? Locating an element in the tree cannot be fast. You'd approach `n` very quickly, only skipping Node roots that are greater than the element you are looking for (since their children are even larger).

None of the documents online which feature Fibonacci heaps or binomial heaps talk AT ALL about locating a node inside the tree. I assume that I just loop over each node, and perform the following logic?

```
for every node n in the list
   int c = compare(n, data)
   if (c > 0)
      call logic recursively on his child
   if (c == 0)
      decrease_key(n, data)
   otherwise
      error cannot compare greater

```

Furthermore, why is there a `decrease_key` but not a `increase_key`, or frankly a `set`? I suppose `increase_key` is a much harder problem to solve?

Thanks

# Answer
The call takes a specific node because that's what you typically want to do. Since you're given a pointer to the node you're supposed to be changing, you don't need to find it.

Your heap is storing a set of objects ordered by priority, and you're much more likely to want to adjust the priority of a specific object ("Crap, my algorithms homework is due tomorrow – I thought it wasn't until Thursday!") than you are to want to adjust the priority of whatever object has some given priority. In any case, there might be multiple objects with the same priority. Would your version of `decrease_key` adjust the priority of all of them?

I'm not familiar with Fibonacci heaps but certainly with ordinary heaps, an operation of "adjust the priority of the items that have priority $k$" would, in the worst case, involve a linear search through the whole heap. The ordering of the heap items isn't strong enough to let you do better than that: for example, the largest item in the heap could be at any leaf.

In ordinary heaps, `increase_key` and `set_key` aren't a problem: just adjust the key value and then filter up or down as appropriate.
> 2 votes

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


# Question
Title: "Breadth course" problem – find maximum independent set given all maximal cliques
One of the undergraduate degree requirements at my university is that all Letters and Science students must take a "breadth course" in each of seven categories. If a course has multiple associated categories, you have to pick one; you can't satisfy multiple breadth requirement categories with a single course.

For example, while `CHINESE 110A Introduction to Literary Chinese` is both an "arts and literature" course and an "international studies" course, you can only use it for one of the two categories. If you then take `COMLIT 156 Fiction and Culture of the Americas`, which satisfies "arts and literature", you've now got both of the categories taken care of.

I'm trying to write a program that determines the maximum number of categories you can fulfill with a given set of courses. I suspect I can do this by creating an undirected graph as follows:

* Each node of the graph represents a particular course applied to a particular category.
* The graph has a clique for every category containing all of the nodes with that category, as well as a clique for every course containing all of the nodes with that course.

For the example case, we'd make a graph that looks like this:

Then, the number of requirements fulfilled would be the size of the maximum independent set of the graph.

Where I'm having trouble is in finding that maximum independent set. I'm aware that algorithms exist to find the maximum independent set of any graph in exponential time, but is there a more efficient algorithm I could use to take advantage of the fact that I already know all the maximal cliques?

# Answer
The question asks about the complexity of the following decision problem:

**Independent Set with Maximal Cliques**
*Input:* graph $G$, set $C$ of maximal cliques in $G$, positive integer $k$
*Question:* is there an independent set $S \subseteq V(G)$ with at least $k$ elements?

The intuition is presumably that $C$ can be quite large, so instead of $|V(G)|$ or $m=|E(G)|$, we instead have $|C|$ as being the dominant term of the instance size $n = |V(G)|+m+|C|$. It is quite easy for $|C|$ to be superpolynomial in $|V(G)|$ when $G$ has many edges, and then brute force will decide the problem in subexponential time. So this problem "should" be easier than if $C$ isn't provided.

The way to break this intuition is to show that even when $|C|$ is quite small (for instance, because the graph contains no triangles and hence no larger cliques either) the problem still remains NP-hard.

This is the case. By Poljak's construction, every graph $G$ can be 2-subdivided by inserting two new vertices into every edge, turning each edge into a a path of length 3. This ensures that the modified graph $G'$ is triangle-free. Moreover, $G'$ has an independent set with at least $m+k$ elements iff $G$ has an independent set with at least $k$ elements. This is a logspace reduction from Independent Set to the special case of Independent Set with Maximal Cliques where $C = E(G)$. Hence the problem remains NP-hard even if $C$ is given.

* Svatopluk Poljak, *A note on stable sets and colorings of graphs*, Comment. Math. Univ. Carolin. 15 (1974) 307-309. (PDF)
> 2 votes

# Answer
This is an instance of bipartite matching. You have one left-vertex for each course, one right-vertex for each category, and an edge between each course and each category it can be used for. Now you want to find a maximum matching in this bipartite graph. There exist standard polynomial-time algorithms for finding a maximum matching in a bipartite graph.
> 2 votes

---
Tags: algorithms, graphs
---


# Question
Title: Is it possible to reduce a SAT problem to it's simplest form with no assumed variables in P time?
So as you read in the title I want to know if it is possible in polynomial time to reduce a SAT problem to it's simplest version in CNF format with no assumed variables?

The simplest form is with minimal gates in the circuit, assumed variable is not important it was assuming the value of a variable.

An example, I have a problem which has only one solution and it is phrased in CNF/SAT but a simpler version in CNF would be a list of conjunct clauses with only one var is it possible to simplify to that.

What if i already know the problem has a solution can simplification run in P time?

# Answer
No, this is not possible, unless $P=NP$.

Why? The formula $x \wedge\lnot x$, which is always false, is technically in CNF. But, this is unsatisfiable.

Suppose we could do this in polynomial time? Then to check of a problem is satisfiable, we just minimize it. If it minimizes to our false formula, then it's not satisfiable. If it minimizes to anything else, it must be satisfiable! So we've solved SAT in polynomial time.

In terms of gates, we have the same problem: if a formula is UNSAT, then always outputting LOW is the minimal gate circuit that's equivalent.
> 2 votes

---
Tags: satisfiability
---


title: P versus NP and what we are looking for

text:
# Question
Title: P versus NP and what we are looking for
I was reading the other day about this problem, refreshing it, and on a couple of places over the internet I read somebody explaining something in the line of '..does not matter as long as is polynomial, a N^20 or N^30 will do it, we know that maybe the solution does not make the problem tractable but if we can produce an algorithm having polynomial time complexity that will be good enough..."

My educated guess makes me think, that, if we can have a polynomial tractable algorithm , with today's computing resources, then that will be great, because we can use the solution, but looks like for P vs NP question as long as is polynomial that would be all.

How accurate are the comments I found on the internet?

# Answer
P vs NP is settled as soon as we find a $O(n^k)$ algorithm for an NP-complete problem (for any constant $k$) or show that no NP-complete problem has such an algorithm.

Whether or not $k$ is too big to yield a tractable algorithm is a different problem. Having a practical algorithm for, say, SAT, would indeed be very useful, many problems we currently solve heuristically (e.g. in chip design) could then be solved to optimality.
> 4 votes

---
Tags: complexity-theory
---


# Question
Title: How to solve the feasibility problem in 0-1 integer programs?
I have an NP-hard 0-1 integer program that I need to solve. The issue with this problem is that even finding a feasible solution (ignoring the objective function) is NP-hard.

Let us look at two examples to illustrate my problem. On the one hand, the knapsack problem is an NP-hard problem which is defined as follows:

$$ \begin{align\*}\tag{$\mathit{P}\_1$} & {\underset{\mathbf{ x }}{\text{maximize}}} & & \sum\_{j=1}^nv\_jx\_j\\\\[3pt\] & \text{subject to} & & \sum\_{j=1}^{n} w\_jx\_j \leqslant\mathit{W},\\\\[3pt\] & & & x\_j \in\\{0, 1\\}, \forall\\, j. \end{align\*} $$ However, finding a feasible solution to the knapsack problem is not NP-hard. In other words, find $x\_j\in\\{0, 1\\}$ for $j=1,\ldots, n$ such that $\sum\_{j=1}^{n} w\_jx\_j \leqslant\mathit{W}$ is easy.

On the other hand, the variable-sized bin packing problem is also NP-hard and is given by the following 0-1 integer program:

$$ \begin{align\*}\tag{$\mathit{P}\_2$} & {\underset{\mathbf{ x }, \mathbf{ y }}{\text{minimize}}} & & \sum\_{j=1}^ny\_j\\\\[3pt\] & \text{subject to} & & \sum\_{i=1}^{m} a\_ix\_{ij} \leqslant\mathit{V}\_jy\_j,\forall\\, j\\\\[3pt\] & & & \sum\_{j=1}^n x\_{ij}=1, \forall\\, i.\\\\[3pt\] & & & x\_{ij}, y\_j \in\\{0, 1\\}, \forall\\, i, j. \end{align\*} $$ However, finding a binary variables $x\_{ij}$ for $i=1\ldots,m$ and $j=1,\ldots,n$ seems to be as hard as finding a solution to the bin packing problem.

In fact, if I apply the first-fit algorithm to the following instance of bin packing: two bins with capacities $V\_1=3$ and $V\_2=4$, respectively, and three items with values $a\_1=2$, $a\_2=2$ and $a\_3=3$. The first-fit algorithm (if it processes the items in the order $a\_1$, $a\_2$ and $a\_3$ will put item 1 into bin 1, item 2 into bin 2 and there is no bin left (i.e., $n=2$). Hence, the first-fit algorithm should output error or something since it cannot assign all items to the $n$ bins. Clearly, the optimal assignment can be items 1 and 2 into bin 2 and item 3 into bin 1. How to solve this issue with the greedy first-fit algorithm?

In general, if I have a 0-1 integer program that is hard to check its feasibility, how to design an algorithm that makes few errors? For example, for the bin packing problem, all the papers I found are not interested in finding feasibility but they are trying to the solve the problem when it is feasible. In many practical cases we cannot pack all the items in $n$ bins using our greedy approaches (even though the optimal algorithm can).

Any suggestions where to find solutions to feasibility of 0-1 integer programs?

# Answer
> 2 votes
The fundamental misconception seems to be: you seem to expect there to be some good way to solve NP-hard problems. But the whole point of NP-hard problems is that there is (most likely) no good, general way to find optimal solutions to NP-hard problems in a reasonable amount of time. So, you seem to be asking for something that (most likely) doesn't exist.

To answer your specific questions:

> \[Here's an example where the grey first-fit algorithm doesn't find the optimal solution to a bin-packing problem.\] How to solve this issue with the greedy first-fit algorithm?

You can't. The greedy first-fit algorithm isn't guaranteed to find an optimal solution (and often won't). Morever, as you said, it's NP-hard even to find a feasible solution -- therefore, you shouldn't expect the greedy first-fit algorithm to be guaranteed to find a feasible solution, either. It's no surprise that it fails to find a feasible solution to a NP-hard problem. And there is (most likely) no way to fix it, while still having an efficient running time.

> In general, if I have a 0-1 integer program that is hard to check its feasibility, how to design an algorithm that makes few errors?

In general, there may be no way.

> Any suggestions where to find solutions to feasibility of 0-1 integer programs?

There's lots of literature on methods for solving integer linear programming (ILP). None of them are guaranteed to find feasible solutions within a polynomial running time (after all, the problem of finding a feasible solution *is* NP-hard), though some of them might work well enough on some problems that you run into in practice. Rather than study the literature and try to implement the known methods, you're probably better off using an off-the-shelf ILP solver -- the developers who implemented the ILP solver did that for you.

# Answer
> 1 votes
Did you check Lenstra

http://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1981d/art.pdf

I understand from that report that the feasability problem with a fixed number of variables can be done in polynomial time

---
Tags: algorithms, integer-programming
---


# Question
Title: How to deal with cost variation in a dynamic graph when applying Dijkstra
What are the methods to deal with variations in cost in a dynamic graph when applying Dijkstra? For instance, I select the shortest path in a graph, however, the weight of this path changed after I selected (I made the selection using an estimate). How do I deal with this variation?

# Answer
So if I get this right, you computed Dijkstra for your whole graph (that has no negative cycles) and then you are interested in the shortest path between two specific points. You used estimates, and after choosing the shortest (estimated) path, you compute the real path length (you don't do this before for performance reasons I guess).

Now here are my thoughts on this:

* The real path length will very likely vary from the one you computed using estimates. That's why it is called estimates. So you first have to decide whether you are interested in the *definitely* shortest path or if it is sufficient to find a *most likely* or *approximately* shortest path.
* For most applications the latter case is sufficient and hence your solution works.
* If not, you have some possibilities. You could ignore the decreasing performance and just compute Dijkstra with the real values. This would be the easiest solution.
* The best solution that comes to my mind is:
    1. Estimate the length of all edges
    2. Compute Dijkstra
    3. Find shortest path between the desired nodes
    4. If the shortest path contains one or more estimates: Compute the distances between *all nodes along the shortest path* and replace the corresponding estimates with your results. Go to 2.
    5. Break; the computed path is indeed the shortest path
> 0 votes

---
Tags: graphs, shortest-path, graph-traversal
---


# Question
Title: What's the theory behind the operator precedences of common operators?
Could for example the precedence ordering of addition, multiplication, exponentiation, boolean and/or and zip/cross product be inferred from a few rules?

# Answer
> 3 votes
There is really no theory behind it: operator precedence is a purely human construct.

The reason is that expressions are not linear blocks of text. They are trees. For example, you can represent any arithmetic in Reverse Polish Notation. In a tree, there is no ambiguity. An operator acts on its children, end of story.

Humans are good at reading things linearly, and bad at reading trees hierarchically. So, we write equations and expressions as linear sequences of characters, with rules for parsing, parentheses to imply the tree structure, and operator precedence rules to remove some of the "obvious" parentheses.

One could imagine a system in which 2+3\*4 was (2+3)\*4. Math works just as well in such a system, and the choice is totally arbitrary. It is simply not the arbitrary choice we happen to use.

---
Tags: category-theory, algebra
---


# Question
Title: Planar graphs of bounded degree: mixing time = cover time?
For many planar graphs of bounded degree (binary tree, lattice, cycle) the (1/4)-mixing time and the cover time are equal, up to log-factors. Is this always the case?

# Answer
> 1 votes
The answer turns out to be *no*. A counterexample, kindly suggested to me by Balász Gerencsér, is a $\sqrt{N}$ by $\sqrt{N}$ grid, with a path of length $\sqrt{N}$ glued to it. One can show that

* the mixing time of a simple random walk on this graph is $O(N\log N)$ (by combining Cheeger's inequality and the Spielman-Teng \[1\] bound on the spectral gap)
* the cover time of a simple random walk on this graph is $\Omega(N^{3/2})$ (by combining Matthews method with an expression of the hitting time using effective resistance)

\[1\] Spielman, Daniel A., and Shang-Hua Teng. "Spectral partitioning works: Planar graphs and finite element meshes." Linear Algebra and its Applications 421.2-3 (2007): 284-305.

---
Tags: graphs, planar-graphs
---


# Question
Title: There exist countably many enumerable disjoint and inseparable sets
I want to formally prove that there are countably many disjoint enumerable sets such that any two of them cannot be separated by a decidable set.

I know that there exist a computable function $f$ that takes only values 0 and 1, and this can be used to define two sets (let's say $\mathcal{A}$ and $\mathcal{B}$, where $\mathcal{A}=\\{x$ $s.t. f(x)=1\\}$ and $\mathcal{B}=\\{x$ $ s.t. f(x)=0\\}$).

Could you please help me to extend this arguments to find (countably) many such sets?

# Answer
> 1 votes
Let $\phi$ be an enumeration of the set of recursive partial functions.

For each $i\in\mathbb N$, let $X\_i = \\{ n\ |\ \phi\_n(0)=i \\}$.

These sets are pairwise disjoint by construction. Each $X\_i$ is recursively enumerable but not recursive.

These sets are pairwise inseparable. By contradiction assume there exist $i\neq j$, and a recursive set $A$ with $X\_i \subseteq A$ and $X\_j \subseteq \mathbb N\setminus A$. We reach a contradiction as follows. The function

$$ g(k,y) = \begin{cases} j & \mbox{if } k \in A \\ i & \mbox{o.w.} \end{cases} $$ is computable, hence $g=\phi\_c$ for some $c$. Now exploit the s-m-n lemma to define $h(k) = \mathsf s(c,k)$, so that $\phi\_{h(k)}(y) = g(k,y)$. Since $h$ is recursive total, by the second recursion theorem for some $k$ we have $\phi\_{h(k)} = \phi\_k$. Let us take one such $k$. Finally,

$$ \phi\_k(0) = \phi\_{h(k)}(0) = g(k,0) = \begin{cases} j & \mbox{if } k \in A \\ i & \mbox{o.w.} \end{cases} $$

Now, the result above is either $j$ or $i$. If it is $j$, then $k\in X\_j$, hence $k\notin A$, hence the result above is $i$ -- contradiction. If it is $i$, then $k\in X\_i$, hence $k\in A$, hence the result above is $j$ -- contradiction.

# Answer
> 1 votes
Suppose $A$ and $B$ are computably enumerable disjoint inseparable sets. For each $n$, so are the sets $A\_n = \\{a + n \mid a \in A\\}$ and $B\_n = \\{b + n \mid b \in B\\}$. The pairs $(A\_n, B\_n)$ are all different. Indeed, let $a\_0 \in A$ be the minimal element of $A$. The minimal element of $A\_m$ is $a\_0 + m$. So if $A\_m = A\_n$ then they both have the same minimal element, $a\_0 + m = a\_0 + n$, therefore $m = n$.

---
Tags: computability
---


title: Max flow with priorities

text:
# Question
Title: Max flow with priorities
I'm studying a simple max flow problem:

Each type of object $a\_1, a\_2...$ can be stored in some of several stores $b\_1,b\_2...$. This is described by this graph:

There are $|a\_i|$ objects of the type $a\_i$. Store $b\_j$ can contain at most $|b\_j|$ objects. This shows as capacity constraints on the graph. The other edges have no capacity constraint and just mean "this type of object can be stored in this store". We want to maximize the total number $N$ of objects being stored. Max flow on this graph answers to this question.

Now we add a priority idea. Each type of object $a\_i$ has an integer priority $p(a\_i)$ say from $1$ to $2$ for simplicity. Instead of maximizing the total number of objects, we want to maximize $(N\_1,N\_2)$ in lexicographical order where $N\_p$ stands for the number of objects with priority $p$ being stored.

Do you see a way to formalize this problem as a flow problem (possibly with a broader meaning than just simple max flow)? Or a way to use max flow algorithms to solve it?

# Answer
Thanks to klaus and D.W. answers that helped a lot to find a full solution. Actually, this is a solution without min cost or circulation methods (even though they are possible solutions).

My solution is the following:

* find $N\_1$ as the max flow on the graph with nodes corresponding to objects of priority 2 (lowest) removed. The fact it is the $N\_1$ we want is straightforward to prove.
* find $N$ the global max flow for the full graph (without priority constraints)
* define $N\_2=N-N\_1$ (\*)
* construct a new graph with 2 additional nodes $s\_1$ and $s\_2$ between the source and the object nodes, each of them connected to the objects nodes of corresponding priority. Define maximal capacity of $s \rightarrow s\_p$ as $N\_p$. Solve the max flow. This provides a solution to the problem. (note that only the capacity on $s \rightarrow s\_2$ is important)

As raised by Willard Zhan, point (\*) requires a proof: $N=N\_1+N\_2$.

Proof: Consider a maximal solution $(N\_1,N\_2)$ for the priority problem. Assume it's not a global max flow: $N\_1+N\_2\<N$. Then there is an augmenting path (without cycle) in the residual graph from $s$ to $t$. This path exits only once from the source, providing a way to increase either $N\_1$ or $N\_2$ and leave the other one unchanged. Both contradict the maximality of $(N\_1,N\_2)$ for the lexicographical order.

This proof relies on a nice fact about max flow: there is no need to ever decrease the flow on an edge from the source to find a better flow (when there is one).

This solution generalizes easily to any number of priorities. You need to solve as many max flow problems as priorities plus the last one.
> 3 votes

# Answer
First, build an algorithm to solve the following problem:

Given a threshold $t$ and a flow graph $G$, find the solution that maximizes $N\_2$, subject to the requirement that $N\_1 \ge t$.

That problem can be solved using algorithms for minimum cost circulation, which is a generalization of max flow where we can also have lower bounds on certain edges. (You'll set the cost of all edges out of the source to 1 and the cost of all other edges to 0, as you don't need different costs.)

Then, do binary search on $t$ to find the largest $t$ for which a solution exists.

---

How do you solve the problem above? We need to modify the graph. Instead of adding a single source vertex $s$, we'll add three vertices $s,s\_1,s\_2$. Add an edge $s \to s\_1$ with lower bound on capacity of $t$. Add an edge $s \to s\_2$ with lower bound 0. Add edges $s\_1 \to a\_i$ for each $i$ where $p(a\_i)=1$, and $s\_2 \to a\_i$ for each $i$ where $p(a\_i)=2$. All edges other than the $s \to s\_1$ edge have lower bound on capacity of 0. Now any valid flow for this problem that respects the lower bounds will satisfy $N\_1 \ge t$.
> 4 votes

# Answer
I think you can simply put costs in the middle edges and solve a Min-Cost Max-Flow Problem. The idea is to find the maximum flow that has the minimum total cost.

In your problem, the higher the priority, the lower will be the cost. For example, if $a\_1$ has priority 1 (highest) and $a\_2$ has priority 2 (lowest), you can set all edges that leave an object with its priority:

$$ p(a\_1 \rightarrow b\_2) = 1$$ $$ p(a\_1 \rightarrow b\_1) = 1$$ $$ p(a\_2 \rightarrow b\_2) = 2$$ $$ p(a\_2 \rightarrow b\_3) = 2$$ $$ ... $$

The algorithm will try to take as much items $a\_1$ as possible, because they are cheaper. Then it will try to take as much as possible from item $a\_2$ and so on...

The problem here is that your priorities might not be that simple. Using the costs of the example above, you are saying that $a\_1 $ is *'two times as preferable as'* $ a\_2$.
> 1 votes

---
Tags: graphs, linear-programming, network-flow
---


# Question
Title: Why is Big O not defined here for a hash table?
In this cheat sheet, average time complexity for access to a hash table is listed as N/A.

I'm curious as to why. Since a hash table is mostly mathematical, I would assume it would be O(1) like the other operations ... Search, Insertion, Delete.

http://bigocheatsheet.com/

# Answer
The chart is underspecified. I assume they mean by "Access" to "retrieve the $i$-th element¹.

In hashtables, there is no notion of order. While you *could* pick the $i$-th element in the underlying array, that would have no meaning at all. Hence, this operation does not make sense on hashtables -- n/a.

---

1. Which is of course underspecified or unfair, depending on how you look at it: in a BST, "Access" gives you also the $i$-th *smallest* element, whereas in a plain array you get just some element.
> 6 votes

# Answer
There is no *access method* per se, it is the array with a function to calculate the place. There is no special structure, maybe linked lists would count, but nothing prevents from using for example tree here or second level tier hash in the array.

Also it fully depends on particular has function used, type of elements, collision resolution. To write it in Landau notation It would require to create multivariable complexity, which is fixed for particular choice of the hashtable type used.

There is no available accessor to get predecessor or successor of given value.

The complexity is expected $\mathcal O(1)$ but may degrade to $\mathcal O(n)$ unless it is a perfect setting then should be deterministic $\mathcal \Theta(1)$. But the hash gunction is slightly dependent on array size used, for huge, saturated table with guarantees of good lookup it may require $\mathcal O(\log n)$ bits to compute the hash.

Going a step further, there is also no access for the splay tree, because the accessed element via search changes place and also there is no order invariant, so the access operation would give no meaningful data. The same story goes for the Cartesian tree, where inorder traversal yields the original sequence, which is not sorted so picked element is not ordered.
> 2 votes

---
Tags: data-structures, hash
---


# Question
Title: Why does decreasing the gap size in Shell sort never undo previous sorts?
I came across this sentence in the Wikipedia article on Shell short, which states that

> If the file is then k-sorted for some smaller integer k, then the file remains h-sorted.

I've seen this claim in other texts like Lafore as well, but I can't wrap my head around why it's true. Of course I can't find a counterexample, but why must it be so?

# Answer
Here is an argument that I find a bit easier to understand than the ones I've seen online. It's not super rigorous, but I think it could be made so. To start with, the claim that you ask about can actually be made stronger and still be true. From *Sedgewick and Wayne's Algorithms*:

> when an h-sorted array is k-sorted, it remains h-sorted

That is, we don't even need to assume that $k$ is less than $h$. Now, what does it mean that the array is $h$-sorted? Let us first define:

* An $h$-inversion of two elements $x\_i$ and $x\_j$, where $i \< j$, is an inversion $inv(x\_i,x\_j)$ for which $j-i=h$.

Here, $i$ and $j$ are indices. Simply put, an $h$-inversion is an inversion between elements that are $h$ indices apart in the array. Then we can define:

* An $h$-sorted array is an array with no $h$-inversions.

If we accept these definitions, we only need to show that $k$-sorting the array does not increase the number of $h$-inversions. We will do so by looking at what might happen when we swap two elements $x\_i$ and $x\_{i+k}$ during a $k$-sort. But first, let's adopt the following notation:

* Let $x\_i|$ and $x\_{i+k}|$ denote the elements with index $i$ and $i+k$ *before* the swap, while $|x\_i$ and $|x\_{i+k}$ denotes the elements with index $i$ and $i+k$ *after* the swap.

Then, because we only swap the elements $x\_i$ and $x\_{i+k}$ if $x\_i \> x\_{i+k}$, we have

* $ |x\_{i+k} = x\_i| \> x\_{i+k}| = |x\_i$.

The equalities are obvious because the left hand and right hand sides really refer to the same element, before and after the swap. The notable thing is the inequality, which we will be using soon.

To keep things easy to visualize, let us look at two elements that are to the right of both $x\_i$ and $x\_{i+k}$. More specifically, the elements $x\_{i+h}$ and $x\_{i+k+h}$, with $h\>k$.

$$ \left\\{\ldots, x\_i, \ldots, x\_{i+k}, \ldots, x\_{i+h}, \ldots, x\_{i+k+h}, \ldots\right\\} $$

Since the array starts out $h$-sorted, we have

* $x\_i| \< x\_{i+h}$ , and
* $x\_{i+k}| \< x\_{i+k+h}$.

After the swap we have,

* $|x\_i \< x\_{i+h}$, because $|x\_i \< x\_i|$, as established previously. Thus, no new inversion has been introduced involving indexes $i$ and $i+h$.

And for $x\_{i+k}$ and $x\_{i+k+h}$ we have either

* $|x\_{i+k} \< x\_{i+k+h}$, in which case no new inversion is introduced involving indexes $i+k$ and $i+k+h$,

or, and this is key,

* $|x\_{i+k} \> x\_{i+k+h}$, in which case a new $h$-inversion $inv(x\_{i+k},x\_{i+k+h})$ has been introduced. However, since $x\_{i+k+h} \< |x\_{i+k} = x\_i| \< x\_{i+h}$ and $x\_{i+k+h}$ is $k$ positions to the right of $x\_{i+h}$, we know that $x\_{i+h}$ and $x\_{i+k+h}$ will be swapped later in the $k$-sort, eliminating the $h$-inversion.

Thus, after the full $k$-sort, any such $h$-inversions introduced by the sort will have also been resolved by the sort.

We have only specifically looked at elements to the right of both $x\_i$ and $x\_{i+k}$, but very similar arguments can be made for elements to the left of both, or even with one element sitting in between (when $h\<k$). I won't go into those cases here however, because this is already a long post.
> 5 votes

# Answer
Hint. Let $S$ be a $q$-tuple of some natural numbers, where $q$ is the length of list that we want to sort, and $\pi\_k(S)$ denote the $k$-th element of $S$ (representing the $k$-th number in the list). Performing $g$-sorting on the list is equivalent to:

Creating the set $\mathcal{O}\_g$

$$\mathcal{O}\_g = \\{ makeSet(n) : n \in \mathbb{N} : i \< g \\}$$

where $makeSet(n)$ is used to obtain all the natural numbers $k$ smaller than $q$ where $k$ modulo $g$ gives $n$.

$$ makeSet(n) = \\{ k : k \in \mathbb{N} : k \equiv n \pmod g \\}$$

and then swapping the positions of the elements of $S$ based on every set in $\mathcal{O}\_g$ such that the formula below is satisfied :

$$\forall A \in \mathcal{O}\_g \\; \forall a,b \in A \quad \pi\_a(S) \> \pi\_b(S) \Leftrightarrow a \>b $$

Now let's suppose we first perform $i$-sorting on some a list (represented as the $q$-tuple, $S$) and then perform $j$-sorting on the list again, where $i\>j$:

$S$ would still satisfy the formula above for $\mathcal{O}\_i$ is what the sentence in Wikipedia means.
> 2 votes

---
Tags: algorithms, sorting
---


# Question
Title: Converting a 32-bit bit pattern into floating point number
**In The Scientist and Engineer's Guide to Digital Signal Processing By Steven W. Smith, Ph.D. i have read something like that,**

Single precision or 32-bit floating point forms the floating point number, $v$, by the following relation: $$ v = (-1)^S \times M \times 2^{E-127} $$

The term: $(-1)^S$, simply means that the sign bit, $S$, is $0$ for a positive number and $1$ for a negative number. The variable, $E$, is the number between $0$ and $255$ represented by the eight exponent bits. Subtracting $127$ from this number allows the exponent term to run from to In other words, the exponent is stored in offset binary with an offset of $127$.

Everything I have understood but this,

> Subtracting 127 from this number allows the exponent term to run from 128 to −127. In other words, the exponent is stored in offset binary with an offset of 127.

I need an easy to understand explanation of **subtracting 127 from $E$** and **binary offset**.

# Answer
> 2 votes
Suppose you didn't include that shift of $127$, i.e. your number $\nu$ would have the form $\nu = (-1)^S \cdot M \cdot 2^x$ with $x$ being the exponent.

With $8$ bits for the exponent $x$ can have a value from $0$ to $255$. This means you can represent numbers from $\nu = (-1)^S \cdot M \cdot 2^0$ to $\nu = (-1)^S \cdot M \cdot 2^{255}$ .

However, what if you wanted $\nu$ to be $2^{-10}$? It would not be possible.

For this to be possible you want to allow negative exponents $x$. Instead of $x$ ranging from $0$ to $255$ you introduce a shift of 127 such that $x$ ranges from $-127$ to $+128$ .

Now you can represent numbers $\nu$ that range from $(-1)^S \cdot M \cdot 2^{-127}$ to $(-1)^S \cdot M \cdot 2^{+128}$ .

---
Tags: floating-point, binary
---


title: LTF circuits and $AC^0$

text:
# Question
Title: LTF circuits and $AC^0$
Do we know if all of $AC^0$ can be captured by polynomial sized depth $2$ LTF circuits? (with or without polynomially bounded weights).

---

For any vector $w \in \mathbb{R}^n$ and any number $c \in \mathbb{R}$ we define the LTF (x) gate as the function, $\\{0,1\\}^n \rightarrow \\{0,1\\}$ such that $LTF(x) =0$ if $c + \vec{w}.\vec{x} \leq 0$ or else $LTF(x) = 1$.

# Answer
I doubt that AC0 can be captured by constant depth threshold circuits, but this hasn't been proved. In the case of small weights, perhaps existing methods suffice to rule out all of AC0 being captured by depth 2 threshold circuits. See Razborov's survey for several pointers, include exponential lower bounds for functions which, unfortunately, are beyond AC0

In the case of unbounded weights, we don't have any superpolynomial lower bounds. The best known lower bound for unrestricted depth two threshold circuits due to Kane and Williams, is $\Omega(n^{3/2})$.
> 2 votes

---
Tags: complexity-theory, circuits, boolean-algebra
---


title: NPC problem with sets

text:
# Question
Title: NPC problem with sets
Let us have a finite set $S$ and a finite set of its subsets $S\_1, S\_2 \dots S\_k$. For any $S\_i$ we have two numbers: $l\_i$ and $h\_i$. We need to figure out if there is such a subset $T$ of $S$, that for any $i$ we have $l\_i \leq |T \cap S\_i| \leq h\_i$.

Prove that this problem is in NP & NP-complete by reducing 3SAT to it.

# Answer
I will prove it is NP-hard leaving the proof that it is in NP to you.

Let $\phi = c\_1\land c\_2\dots\land c\_m$ be a 3SAT formula. Define $$S = \\{l \mid l \text { is a literal of } \phi \\}$$ $$S\_i = \\{l \mid l \text { is a literal of } c\_i\\}$$

Since each clause has to have at least one literal with TRUE value we have the following constraints $$l\_i=1 \leq |T \cap S\_i|\leq 3 = h\_i$$ Finally, we have to make sure that $T$ contains no variable $x$ (of $\phi$) and its negation at the same time $$S\_{x} = \\{x,\overline{x} \\} $$ $$l\_x=0\leq |T \cap S\_x| \leq 1=h\_x$$

So, if $\phi$ indeed has a solution then $T$ consists of those literals whose true-value is TRUE. Then it is trivial that all constraints satisfy since $T$ may not have a variable and its negation at the same time and each clause has at least one TRUE literal.

On the other hand, if we have a set $T$ satisfying the above-described constraints then $\phi$ can be constructed by ORing each literal in $S\_i$ (by ORing with arbitrary variables if $|S\_i| \< 3$) and ANDing all clauses corresponding to $S\_i$. This formula is satisfiable since may make each clause TRUE by making true each literal in $S\_i$ and since not $x$ and $\overline{x}$ are in $T$.
> 1 votes

---
Tags: algorithms, complexity-theory, reductions
---


# Question
Title: How do you prove that the set of decimal representation of the 4 divisble natural numbers is regular?
This is from an old exam, the last Task no one could solve correctly and I'm curious how it's done :p

Show that the set of decimal representation (without leading zeroes) of the divisible numbers by `4` (natural numbers) is regular.

By this thread How to prove a language is regular? I know that one can make a DFA to Show that a language is regular.

But is that possible at all because we have infinite natural numbers that are divisible by `4`..

I cannot even imagine how that DFA would look like :o

Maybe there is another way of showing this, too?

**Edit**: Removed..

# Answer
> 4 votes
A decimal number is divisible by 4 if the number formed by its last two digits are divisible by 4. Stated differently, divisibility by 4 depends only on the last two digits. That should be enough for you to show that your language is regular.

The language of numbers in base $b$ divisible by $m$ is regular for all $b,m$, but that's somewhat harder to show.

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


title: Distibutional problem

text:
# Question
Title: Distibutional problem
Given: $n$ tasks with accomplishment times $t\_1, t\_2, \ldots , t\_n$. There is no such task that its accomplishment time is greater than the overall accomplishment time of other tasks.

Question: How to distribute these tasks between two workers in a such way that $|T\_1 - T\_2|$ is minimum ($T\_i$ - the overall accompl. time for the $i$-th worker accordingly).

We will use the local search algorithm, starting with a random distribution and redistributing **one** task on every step only if it leads to reducing $|T\_1 - T\_2|$ as long as it's possible.

Does this algorithm find the optimal distribution or is there any counterexample?

# Answer
We can consider the more general problem of *makespan*, in which we wish to partition the tasks into $m$ sets as evenly as possible (your case is $m=2$). We measure the quality of our solution using the maximum total sum of a set, which we wish to minimize. Finn and Horowitz showed that the locality gap for this problem is $2-2/(m+1)$. This means that a locally optimal solution has objective value larger by a factor of at most $2-2/(m+1)$, and moreover there are examples in which the ratio approaches $2-2/(m+1)$. In particular, local search doesn't always give the optimal solution.

For other local search algorithms for makespan, consult the survey of Schuurman and Vredeveld.
> 2 votes

---
Tags: algorithms, optimization
---


title: Taking mod $2$ with LTF gates

text:
# Question
Title: Taking mod $2$ with LTF gates
Consider the function : $\mathbb{Z}^{\geq 0} \rightarrow \\{0,1\\}$ given as $n \mapsto n \bmod 2$. Does this have an easy implementation using Linear Threshold Function gates?

---

I do not mean that the input is the infinite set of positive integers. Think of the input as coming on a single wire carrying a non-negative integer.

# Answer
> 2 votes
This is impossible. For large enough $n$, all your threshold gates will be "saturated", that is, they will have the same output on all large enough $n$, and in particular won't be able to distinguish between $n$ and $n+1$.

---
Tags: complexity-theory, circuits, boolean-algebra
---


title: Compact mapping from an involuted set

text:
# Question
Title: Compact mapping from an involuted set
Let $S$ be a set (say positive integers $\leq$ N) and $f$ an involution ($f$ is bijective, $f\cdot f=id$, *e.g.* xor with a constant). $g$ is a idempotent mapping choosing an arbitrary representative element in each $f$ mapped pairs. For example $g(x)=\min (x,f(x))$ $$g: S \rightarrow \tilde S \subseteq S$$

I want to build a compact lookup table from $g$'s codomain $\tilde S$ to any problem data, taking $|\tilde S| \leq |S|$ cells in memory. Ideally I wish to construct a bijective mapping $\tilde S \rightarrow \left\[0, |\tilde S| \right\[$.

Can it be done efficiently in general (without hash map or scanning) ? What properties of the involution $f$ could help with that ?

**Edit:** I formulated the problem in the more general/formalized, hoping for a generic solution. Following D.W.'s comment, I'll give a concrete application:

I work with DNA words of $k$ nucleotides bases called $k$-mers. Since there is four bases, $k$-mer are represented as elements of $S=\[0,2^{2k}\[$

However DNA can be read on both strands, with opposite orientations and complementary bases ($A \leftrightarrow T$, $G \leftrightarrow C$). Going from one strand to the other can be represented by this involution (reverse-complement, here for 5-mers): $$ f(x) = \text{reverse}\_2(x) \oplus 0\text b1010101010 $$ where $\text{reverse}\_2(abcdefghij)=ijghefcdab$ inverse the order of 2-bits blocks and $\oplus$ is the bitwise XOR.

Since many applications don't distinguish between a $k$-mers and its reverse-complement, a canonical $k$-mer is picked with $g(x)=\min (x,f(x))$. The cardinality of $g$'s co-domain is: $$ \left|\tilde{S}\right|=\begin{cases} 2^{2k-1} & \text{if }k\text{ is odd}\\ 2^{k-1}\left(2^{k}+1\right) & \text{if }k\text{ is even} \end{cases} $$

In practice saving less than one addressing bit is not worth a complex solution. But cache locality is a good thing to have. $g$ can be chosen differently if it help with that.

# Answer
> 3 votes
I can give two candidate solutions for your specific situation.

# Approach #1: parity

This only works if $k$ is odd. Notice that if $k$ is odd, the parity of $f(x)$ is the reverse of the parity of $x$. In other words, the xor of the bits of $f(x)$ is the complement of the xor of the bits of $x$.

This suggests an encoding. Define $g(x)$ to choose between $x$ and $f(x)$ by always choosing the one with even parity. In other words, $g(x)=x$ if the the bits of $x$ xor to zero, otherwise $g(x)=f(x)$. Now we have $y \in \\{0,1\\}^{2k}$ with even parity, and we want to map it to a $2k-1$ bit index/offset. We can do that by simply truncating the last bit of $y$ (since we know $y$ has even parity, the last bit of $y$ is uniquely determined by all the other bits).

This scheme is simple, easy to implement, efficient, and achieves perfect compression of your table. Unfortunately this doesn't work if $k$ is even. I don't know if there is a simple generalization of this idea to the case where $k$ is even.

# Approach #2: multiple tables

This scheme works for arbitrary $k$. Instead of having a single lookup table, we will have $k/2$ lookup tables $T\_1,T\_2,\dots,T\_{k/2}$, each of which stores a different subset of the space of $k$-mers. The mapping will have the property that $x$ and $f(x)$ map to the same table and same offset/index within the table.

Define $h(x)$ to be the smallest $i$ such that $f(x\_i x\_{k+1-i}) \ne x\_i x\_{k+1-i}$ (here by $x\_i$ I mean the $i$th base in $x$, where $i \in \\{1,2,\dots,k\\}$; so $x\_i$ is two bits). Now we will store $x$ in the table $T\_j$ where $j=h(x)$. For instance, if $h(x)=1$, we'll store $x$ in $T\_1$; if $h(x)=2$, we'll store $x$ in $T\_2$; and so on. Conveniently, we have $h(x)=h(f(x))$. So, we'll define $g(x)$ to compute $j=h(x)$ and then choose between $x$ and $f(x)$ by choosing the value $y$ such that $y\_j \< f(y\_j)$. In other words, if $x\_{h(x)}$ is lexicographically smaller than $f(x)\_{h(x)}$, then $g(x)=x$, otherwise $g(x)=f(x)$.

How do we determine the index into the table? Suppose $h(x)=1$. Then there are 12 possibilities for $x\_1,x\_k$ such that $h(x)=1$ (the other 4 possibilities yield $h(x)\>1$), and our definition of $g$ picks out 6 of them as canonical. So, in total there are $6 \times 2^{2k-4}$ possible values of $x$. Thus $x$ can be easily converted into an index into $T\_1$ by mapping $x\_1,x\_k$ to $\\{0,1,2,3,4,5\\}$, say $i\_1$, and mapping $x\_2,\dots,x\_{k-1}$ to an integer in the range $0..2^{2k-4}-1$, say $i\_2$, and then using $2^{2k-4} i\_1 + i\_2$ as our index. You can generalize to the cases $h(x)=2$, $h(x)=3$, etc. For example, suppose $h(x)=2$. Then there are 4 possibilities for $x\_1,x\_k$; 12 possibilities for $x\_2,x\_{k-1}$, but $g$ picks out 6 of them as canonical; and $2^{2k-8}$ possibilities for $x\_3,\dots,x\_{k-2}$. So you can map $x\_1,x\_k$ to an integer in the range $0..3$, map $x\_2,x\_{k-1}$ to an integer in the range $0..5$, and map $x\_3,\dots,x\_{k-2}$ to an integer in the range $0..2^{2k-8}-1$; then map those to an index in the range $0..4 \times 6 \times 2^{2k-8}-1$. And so on for larger values of $h(x)$.

This strategy works for any value of $k$. It achieves perfect compression. It's not too difficult to implement and should be pretty fast.

---
Tags: data-structures, sets, bioinformatics, finite-sets, succinct-data-structures
---


# Question
Title: Prove or disprove that the following language is context-free
Hi guys I was given this question:

> Prove or disprove that the following language is context-free: $$ L = \\{ \alpha 2 \beta : \alpha,\beta \in 1(0+1)^\*, \[\alpha\]\_2 \< \[\beta\]\_2 \\} $$ where $\[x\]\_2$ is the numerical value of the string $x$ interpreted as a positive number in base 2. For example, $\[1110\]\_2 = 8+4+2 = 14$, $\[10100\]\_2 = 16 + 4 = 20$, thus $1110210100 \in L$, while $111021110 \notin L$ and $1010021110 \notin L$.

I can't figure out either way if its context free or not. When I was trying to prove it was context free with a DPDA I got stuck because I don't know how to compare two binary strings when one is in reverse of the other because when you put the string left of the 2 into a stack and pull it out it comes out reversed. Because of this I can't compare if one is bigger than the other if they are the same length.

On the other hand I tried using the pumping lemma to prove its not context free. For a string $ 1^{m}210^{m} $ I can show for two cases when $ v^{k}xy^{k} $ is composed of just 1's on the left side or right I can either underpump or overpump. For the third case when $ v^{k}xy^{k} $ is composed of the run of 1's on the left and the 0's on the right pumping in either direction doesn't seem to make the left binary number the bigger value.

I am stuck with either direction I have tried so could somebody point me in the right direction?

# Answer
> 2 votes
You can use the pumping lemma in this way.

By closure properties, if $L$ is context free and it is intersected with the regular language $R = \\{ 1^\* 0^\* 2 1^\* 0^\*$} the resulting langauge $L' = L \cap R$ is still context free.

We can apply the Pumping lemma to $L'$ and prove that it cannot be CF, so $L$ is not CF as well.

Let $p$ be the pumping length; pick

$$z = 1^p \\, 0 \\, 0^p \\; 2 \\; 1^{p} \\, 1 \\, 0 ^p$$

First note that if $vwx$ is entirely contained in the first half, then pumping it one time is enough to make the first half longer than the second half; making $\[\alpha\]\_2 \> \[\beta\]\_2$ and pushing the string out of $L$

If $vwx$ is entirely contained in the second half, then pumping it zero times is again enough to make the first half longer than the second half; making $\[\alpha\]\_2 \> \[\beta\]\_2$ and pushing the string out of $L$

So $vwx$ crosses the middle of $z$.

At least one, but at most $p$ positions are contained in $vwx$, so $v$ must be in the $0^p$ before the center and $x$ in the $1^p$ after the center.

If $|v| \<\> |x|$ then - as above - pumping them one (or zero times) would make the first half longer.

But if $|v| = |x| = k \geq 1$ we can still pump it zero times getting the string:

$$z^0 = 1^p \\, 0 \\, 0^{p-k} \\; 2 \\; 1^{p-k} \\, 1 \\, 0^p$$

but

$$ \[ 1^p \\, 0 \\, 0^{p-k} \]\_2 \>= \[ 1^{p-k} \\, 1 \\, 0^p \]\_2$$

(for $k=1$ we have $1^p 0 0^{p-1} = 1^{p-1} 1 0^p$)

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


title: Comb sort average complexity

text:
# Question
Title: Comb sort average complexity
The wikipedia page about comb sort claims that the average complexity of comb sort is Omega(n^2/2^p) where p is the number of increments. Take as example an uniform distributed array of 1000 elements, using the standard shrink factor of 1.3 the length of the gaps list is 23. Is this the p mentioned in the wikipedia article? If it is the complexity is omega of 1000^2 / 2^23 ~ 0.120 Someone could please explain what I don't understand? Thank in advance

# Answer
> 0 votes
The average-case lower bound for uniformly distributed data is $\Omega(\frac{n^2}{2^p})$, $p$ here denotes the number of increments, not actual gaps.

The number of passes is given as the input with gaps, which are in form of list, say $\\{k\_1, k\_2,\dots,k\_p\\}$ where given $k$ is single increment value. There are $p$ increments to go, this $p$ is in the equation.

To avoid explicit list one may use shrink factor, which behaves similarly to shellsort and use the gap divided by consecutive powers of this factor.

---
Tags: algorithm-analysis, runtime-analysis, sorting, average-case
---


# Question
Title: Does a Haskell program count as an inductive proof?
Is the following statement from \[1\] true?

"Since recursion is the main computational technique, a terminating pure Haskell program counts as an inductive proof of a theorem."

My intuition is that inductive proofs require a base case, assume the hypothesis case for k, prove induction step fork+1. I am not clear on how these steps occur in the execution of a program (function?). Also, what logic is employed in such a proof?

Regards, Patrick Browne

\[1\] http://ebooks.iospress.com/volumearticle/44257

---

Thanks for your very helpful answers.

Would it be fair to say that the answer may be morally yes \[1\], but technically perhaps no \[2\].

Below are two Haskell programs together with what I consider to be equational proofs (not inductive) that they evaluate to a desired ground term. The first program is not recursive. So does the quote in my original posting include non-recursive programs?

```
    -- Prog 1 non-recursive
x,y,z:
x = 1
y = x + 2
z = x + y
proveZ = z == 4
-- Equational Proof
[1]: (z)
---> (x + y)
[2]: (x + y)
---> (1 + y)
[3]: (1 + y)
---> (1 + (2 + x))
[4]: (1 + (2 + x))
---> (1 + (2 + 1))
[5]: (1 + (2 + 1))
---> (1 + 3)
[6]: (1 + 3)
---> (4)

-- Prog 2 recursive
data Vector  = Empty | Add Vector Int
size Empty  = 0
size (Add v d)  = 1 + (size v)
proveSize =  size (Add (Add Empty 1) 2) == 2
-- Equational Proof
[1]: (size (Add (Add Empty 1) 2))
---> (1 + (size (Add Empty 1)))
[2]: (1 + (size (Add Empty 1)))
---> (1 + (1 + (size Empty)))
[3]: (1 + (1 + (size Empty)))
---> (1 + (1 + 0))
[4]: (1 + (1 + 0))
---> (1 + 1)
[5]: (1 + 1)
---> (2)

```

The motivation for my original question is that I wish to understand the relationship between the evaluation of a Haskell program and the application of equational logic to the same Haskell program. While Haskell produces the correct answer, as would a non-functional language, is the computation a proof in equational logic? I imagine that Haskell cannot do any form of symbolic proof (e.g. id a == a). In summary is my yes/no opinion reasonable?

\[1\] Fast and Loose Reasoning is Morally Correct: http://www.cs.ox.ac.uk/jeremy.gibbons/publications/fast+loose.pdf

\[2\] Formulating Haskell: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.1399

# Answer
The statement is not true as stated. Even if we imagine a Haskell-like language where *all* functions terminate and values are non-bottom, only some programs would correspond to *inductive* proofs (as opposed to proofs not using induction), but it would be the ones that (directly or indirectly) use recursion. That said, what they are doing induction over may not at all be obvious. (For the OP: every inductive type gives rise to a notion of structural induction with "mathematical induction" just being structural induction over the naturals.) Many patterns of recursion in practical programs, e.g. quicksort, do not correspond to a direct structural induction over their inputs.

For real Haskell, for just about any program proving that it terminates for all inputs requires very strong restrictions on those inputs: all values must be fully defined and all passed in functions must terminate on at least the inputs exercised by the current program. The latter isn't checkable in general, but what we can do instead is reduce a value that stands for a putative proof to normal form, and if we succeed then we have a real proof. Unfortunately, Haskell doesn't evaluate things to normal form but only to weak head normal form. For some types we can force the weak head normal form of one expression to correspond to normal forms via `rnf`, but we can't do this for functions in general.

Even without restrictions, programs in Haskell correspond to proofs in *some* logic, albeit an inconsistent one. This leads to another aspect that they conveniently didn't elaborate on. They say that certain Haskell programs correspond to proofs of theorems, but they don't say what theorems you can state! Haskell (particularly with higher-rank polymorphism) is closely related to the polymorphic lambda calculus and that corresponds to intuitionistic, second-order propositional logic1 (SOPL) (not to be confused with second-order *predicate* logic which is usually what "second-order logic" refers to). While SOPL is uninteresting in the classical case, it turns out to be pretty powerful in the intuitionistic case, capable of embedding intuitionistic first-order *predicate* logic. The embedding is non-obvious and even with it you would not be able to prove something like the Fundamental Theorem of Arithmetic. In practice, most programs correspond to completely trivial theorems or (intutionistic) propositional tautologies.

From my (admittedly very brief) skimming of the paper, it seems that they are more interested in the Prolog-like reasoning the type class system enables than leveraging the propositions-as-types correspondence. So their comments seem to be a bit of a non sequitur anyway.

1 See Chapter 12.
> 8 votes

---
Tags: proof-techniques, functional-programming
---


# Question
Title: In Disjoint Sets, why do we make the smaller tree the subtree of the larger one?
Currently I'm learning about the Disjoint Sets data structure. I understand that, when we create a union of two disjoint sets, we create a kind of "backwards" tree for fast lookup. As Skiena says in his book:

> To minimize the tree height, it is better to make the smaller tree the subtree of the bigger one. Why? The height of all the nodes in the root subtree stay the same, while the height of the nodes merged into this tree all increase by one. Thus, merging in the smaller tree leaves the height unchanged on the larger set of vertices.

I don't get this part, the description is not clear to me. Could someone clarify why we need to make this distinction?

# Answer
> 5 votes
Probably best explained with pictures. Say we have these two sets $A$ of height 2 and $B$ of height 3:

Now we have a choice when joining them:

1. Attach root of $B$ to root of $A$.
2. Attach root of $A$ to root of $B$.

Remember we are optimizing for look-up / $find()$. Let's see what happens in either case.

### Attach root of $B$ to root of $A$.

We end up with this resulting set of height 4:

### Attach root of $A$ to root of $B$.

We end up with this resulting set of height 3!

Wonderful! We've increased the size of the set without increasing the height. In this scenario our find will take at most 3 iterations, same as what we originally had because $B$ was of height 3 to begin with. In the other scenario we have at most 4 iterations because we've increased the height of the new set by 1. This is why it is always preferable to join the shorter tree to the taller one, because it will not increase the height of the taller tree (unless they are the same height). Thus, optimizing for look-up.

---
Tags: data-structures
---


title: Finding a minimum of a noisy function

text:
# Question
Title: Finding a minimum of a noisy function
I have a certain function that calculates numerically, for every $x \in \[0,10\]$, a value $y\geq 0$. I want to find an approximate minimum point of that function. A possible solution is to calculate $y$ for e.g. 10000 values of $x$ in the range $\[0,3\]$ and return the $x$ for which $y$ is smallest. I am looking for fastest solutions.

I know that the general shape of the function is like the following plot:

I.e, it is like a function with a single minimum point, but with some added random noise of bounded size. Without the noise, I could easily find the minimum point using gradient methods, but with noise gradients seem useless. What other search algorithm can I use here?

NOTE: Naturally the approximation quality can depend on the noise size, for example, in the above plot, any answer between $\approx 0.3$ and $\approx 0.7$ would be considered good enough.

# Answer
> 2 votes
Some things you could explore are metaheuristics. The following methods don't make assumptions about the function to be optimized, and some are relatively simple to understand and implement.

Some of these mantain a population of possible solutions, recombining them to create new possible solutions and keeping the best ones.

* Differential evolution
* Particle Swarm
* Evolutionary algorithms

There are a lot more, with a lot of published variations.

It is my understanding that they are very capable, you can expect the error to be much smaller to the error margin you mentioned and the acceptable error can be used as a parameter for the halting condition of the algorithm. If the target function is computationally cheap to evaluate these methods should be very competitive.

In particular differential evolution could be a place to start exploring. You can use an already written implementation on scipy's optimize.

There are other approaches, some of which make assumptions about the function to be optimized. You can see some examples on Wikipedia (Computational optimization techniques section).

---
Tags: optimization, numerical-algorithms
---


# Question
Title: Unknown representation of number as bits
I am self taught in CS and came across this while looking at binary search applied to multiplication. I don't understand this part: OK, we have some x that has binary representation $10110010(1\*2 + 1\*2^4 + 1\*2^5 + 1^7$) ...I understand this, but don't know what following means $x = 2^4(1011) + 0010$. What is name of second notation, where can I find more about this?

Thanks!

# Answer
They've split an 8-bit byte into two four-bit **nibbles** (sometimes spelled "nybble"). The brackets denote multiplication; it's just saying that $$10110010 = 10000\times 1011 + 0010\\,,$$ (written all in binary to avoid having two different bases in the same expression). This is just like saying, in decimal, that $$837\\,487 = 1000\times837+487\\,.$$ There isn't really anything to find out.
> 1 votes

# Answer
Maybe you understand it better if it's written as

$$x=(2\_{10})^4\*(1011\_2)+0010\_2.$$

I use the index to indicate which base I use.

It's similar to saying

$$1234567 = 10^4\*(123)+4567$$
> 1 votes

---
Tags: algorithms
---


# Question
Title: How to count all contiguous subsequences with positive sum?
I have array $t$ with size $n \leq 10^6$. It has only two kinds of elements inside: $1$ or $-1$. I need to count how many contiguous subsequences have positive sum.

This pseudocode demonstrates exactly the behavior I want, but is too slow for large $n$:

```
c = 0
for i = 1 to n do
    for i = j to n do
       if sum(u[i:j]) > 0 then
           c = c + 1
return c

```

Partial sums can be used to optimize it, but it will still be $O(n^2)$.

Here are some examples if they help:

`[-1, 1, -1, -1, -1]` $\rightarrow$ `1`

`[1, -1, 1, 1, -1, 1]` $\rightarrow$ `14`

`[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]` $\rightarrow$ `55`

Does there exist linear or $n \log n$ solution?

# Answer
Given the array $A\_1,\ldots,A\_n$, start by computing $B\_i = \sum\_{j \leq i} A\_j$. You want to count the number of pairs $i\_1 \< i\_2$ such that $B\_{i\_1} \< B\_{i\_2}$, where $0 \leq i\_1,i\_2 \leq n$. Each such pair corresponds to a a contiguous subsequence $A\_{i\_1+1},\ldots,A\_{i\_2}$ whose sum is positive. This is the same as the classical problem of counting the number of inversions in an array (this is what you get if you reverse $B$), which can be solved in $O(n\log n)$.

It is plausible that you can do better in your case since the numbers are $\pm 1$.
> 1 votes

---
Tags: optimization, time-complexity, counting, subsequences
---


# Question
Title: What is the relationship between the complexity class $L^n$ and $NL^m$?
The space hierarchy theorem shows that $$\mathrm{\mathbf{L}}^{1} \subsetneq \mathrm{\mathbf{L}}^{2} \subsetneq \cdots \subsetneq \mathrm{\mathbf{L}}^{m} \subsetneq \cdots \subsetneq \mathrm{\mathbf{PSPACE}}$$ and $$\mathrm{\mathbf{NL}}^{1} \subsetneq \mathrm{\mathbf{NL}}^{2} \subsetneq \cdots \subsetneq \mathrm{\mathbf{NL}}^{m} \subsetneq \cdots \subsetneq \mathrm{\mathbf{NPSPACE}} = \mathrm{\mathbf{PSPACE}}$$ where $$\mathrm{\mathbf{L}}^{m} = \mathrm{\mathbf{DSPACE}}\left( \log^{m}(n) \right)$$ and $$\mathrm{\mathbf{NL}}^{m} = \mathrm{\mathbf{NSPACE}}\left( \log^{m}(n) \right)$$

Thus, there exists a function $\varphi \colon \mathbb{N}^{+} \mapsto \mathbb{N}^{+}$ such that for every $m \in \mathbb{N}^{+}$,

$$\mathrm{\mathbf{L}}^{\varphi(m)-1} \subset \mathrm{\mathbf{NL}}^{m} \subset \mathrm{\mathbf{L}}^{\varphi(m)} \subsetneq \mathrm{\mathbf{PSPACE}}$$

The Savitch's theorem shows that for every $m \in \mathbb{N}^{+}$, $$\mathrm{\mathbf{L}}^{m} \subset \mathrm{\mathbf{NL}}^{m} \subset \mathrm{\mathbf{L}}^{2m}$$

Now, we know that $m+1 \leq \varphi(m) \leq 2m$ and $\varphi(1) = 2$.

Can we find $\varphi$ ? Is it an open problem or not?

# Answer
It is not known whether $\mathsf{L} = \mathsf{NL}$, and this is a famous open question. More generally, I believe that no better bound than $\phi(m) \leq 2m$ is known for any value of $m$, nor is this bound known to be optimal for any value of $m$.
> 2 votes

---
Tags: complexity-theory, space-complexity
---


# Question
Title: How to predict the length and offset of the sequence in and array?
I have an input string similar to `ABCDEFGHIJK` from which a series of sequences has been generated into an array as following:

```
00: 'ABCD'
01: 'BCDE'
02: 'CDEF'
03: 'DEFG'
04: 'EFGH'
05: 'FGHI'
06: 'GHIJ'
07: 'HIJK'
08: 'ABC'
09: 'BCD'
10: 'CDE'
11: 'DEF'
12: 'EFG'
13: 'FGH'
14: 'GHI'
15: 'HIJ'
16: 'IJK'
17: 'AB'
18: 'BC'
19: 'CD'
20: 'DE'
21: 'EF'
22: 'FG'
23: 'GH'
24: 'HI'
25: 'IJ'
26: 'JK'
27: 'A'
28: 'B'
29: 'C'
30: 'D'
31: 'E'
32: 'F'
33: 'G'
34: 'H'
35: 'I'
36: 'J'
37: 'K'

```

The sequences in the array above has been generated by following these steps:

1. Set `length` to `4`
2. Set `offset` to `0`
3. Pick a `sequence` of `length` long characters from `"ABCDEFGHIJK" (Input string)`
4. Put the `sequence` at the bottom of `output array`
5. Increase `offset` by `1`
6. If `offset + length <= 11 (Input string's length)` then `goto 3`
7. Decrease `length` by `1`
8. If `length >= 1` then `goto 2`
9. Exit

By looking at the output array, sequences in the array have a `length` which starts at 4 and gradually goes down to 1, and also an `offset` which is where in the `input string` the `sequence` has begun.

What I'm trying to achieve is to "predict" both the `length` and the `offset` of a `sequence` at a given `index` in the `output array`, only having the `input string's length` and `index in the output array`.

I'm preferably looking for a formula, however an algorithm which doesn't involve simulating the output array will work as well.

# Answer
Let $n$ be the length of the string, and $k$ be the maximum length of the substring. Thus the first $n-k+1$ positions correspond to length $k$, the next $n-k+2$ to length $k-1$, and so on. Denote by $i\_\ell$ the index at which substrings of length $k-\ell$ begin. We have $$ i\_\ell = \sum\_{t=k-\ell+1}^k (n-t+1) = \frac{\[(n-k+1)+(n-k+\ell)\]\ell}{2} = \frac{\ell^2}{2} + \ell\left(n-k+\frac{1}{2}\right). $$ Given $i\_\ell$, we can solve for $\ell$: $$ \ell = \sqrt{(n-k+1/2)^2+2i\_\ell}-(n-k+1/2). $$ Monotonicity shows that for *arbitrary* $i$, the floor of this expression still gives the correct value of $\ell$. This suggests the following algorithm:

1. Let $i$ be the input index.
2. Calculate $\ell = \lfloor \sqrt{(n-k+1/2)^2+2i}-(n-k+1/2) \rfloor$.
3. Calculate $i\_\ell = \ell^2/2 + \ell(n-k+1/2)$.
4. Output length=$k-\ell$ and offset=$i-i\_\ell$.

For example, let's take $i = 10$ in your case (where $n = 11$ and $k = 4$). Then $\ell = \lfloor \sqrt{7.5^2+20}-7.5 \rfloor = \lfloor 1.23\ldots \rfloor = 1$ and $i\_\ell = 1^2/2 + 1\cdot 7.5 = 8$. Hence the length is $4-1=3$ and the offset is $10-8=2$.
> 3 votes

# Answer
# Variables

In this answer I will use the following names for the variables:

* The `n` variable refers to the initial value of `length` (in the case above this is 4)
* The `isl` (input string length) variable refers to the length of the input string (11 in the case above)
* The `index` variable refers to the index of the output array.

# Approach

To solve the problem and find a solution, we should first look at the details we got.

## Input

The formula or algorithm we are looking for receives the following inputs:

* The `index` of the `output_array`
* The `isl` (length of the input string)

But this is not the only input. It also knows the **initial value** of `length` (in your example above it's 4). As mentioned above, we will call this value `n`.

## Facts

From the algorithm you described in your question, we can derive the following facts:

### Partitions of the output array

The `output_array` will have `n` partitions corresponding to the `n` different lengths (in your example above the lengths from 4 to 1). Each partition `i` has a length of $$\text{isl}-(n-i)+1$$ where `i` (the partition number) starts at 0. We notice, that the first partition is the smallest one and the last partition (where the `sequences` have a length of 1) is the largest one with a length of `isl`. From the formula we also see, that the length of the partitions increases from the first partition to last partition by 1.

*Note: We count partitions starting at 0.*

## Deducting the Formula

We need two formulas. One for the `length` of the `sequence` at `index` and one for the `offset` of that same `sequence` in the input string.

### The formula for `length`

The formula for the `length` must look something like this: $$\text{length} = \overbrace{\text{n}}^{\text{minuend}} - \overbrace{\text{something depending on index}}^{\text{subtrahend}}$$

For the first partition (partition 0) the `subtrahend` shall be 0. For the second (partition 1) it shall be 1 and so on.

**Indicator function**

As we can see, we need a function, which can tell us, in which partition the `index` is in. A thing with such a property is like an indicator function. It could look like:

$$\text{partition\_number}(\text{index}) = \begin{cases}0,&\text{if index in partition 0}\\1,&\text{if index in partition 1}\\\ldots\end{cases}$$

An easy way to find such a function is to have an indicator function, which can tell us, if `index` is in a partition `a`, where `a` is at least `i`. Something like:

$$f(\text{index},i) = \begin{cases}1,&\text{if index in partition a \> i}\\0,&\text{else}\end{cases}$$

Because then we would just have to sum the result of `f` for all partitions and would directly have our subtrahend.

To define such a function `f`, we need to know at least the left boundary of partition `i`. We can obtain the left bound of partition `i` by:

$$\text{left\_bound}(i) = i\*\overbrace{(\text{isl}-n+1)}^{\text{Size of first partition}}+\overbrace{\frac{1}{2}\*(i-1)\*i}^{\text{Correction number for partition growth}}$$

So our *indicator function* looks like:

$$f(\text{index},i) = \begin{cases}1,&\text{if } \text{left\_bound}(i)\<=\text{index}\\0,&\text{else}\end{cases}$$

With this function we can now define our `partition_number` function as following:

$$\text{partition\_number}(\text{index})=\sum\_{i=0}^{n-1}{f(\text{index},i)}-1$$

With the `partition_number` for our subtrahend we can now define our formula for the `length_at_index`:

$$\text{length\_at\_index}=n-\text{partition\_number}(\text{index})=n-\sum\_{i=0}^{n-1}{f(\text{index},i)}+1$$

### The formula for `offset`

We can directly make use of the `partition_number` and `left_bound` function we defined above:

$$\text{offset\_at\_index} = \text{index}-\text{left\_bound}(\text{partition\_number}(\text{index}))$$

# A Solution in Javascript

And here the solution of above written in Javascript:

```
function getLeftBoundOfPartitionI(i, isl, n) {
    return i * (isl - n + 1) + .5 * (i - 1) * i
}

function isIndexInPartitionI(index, i, isl, n) {
  return index >= getLeftBoundOfPartitionI(i, isl, n) ? 1 : 0
}

function getPartitionNumber(index, isl, n) {
    partition = 0
    for(var i = 0; i < n; i++) {
    partition += isIndexInPartitionI(index, i, isl, n)
  }
  return partition - 1
}

function lengthAtIndex(index, isl, n) {
    return n - getPartitionNumber(index, isl, n)
}

function offsetAtIndex(index, isl, n) {
  partitionNumber = getPartitionNumber(index, isl, n)
    return index - getLeftBoundOfPartitionI(partitionNumber, isl, n)
}

document.body.innerHTML = offsetAtIndex(16, 11, 4)  // yields 8

```
> 1 votes

---
Tags: algorithms, arrays, hash-tables
---


# Question
Title: Algo to calculate real trade volume from last 24h volume
Is mostly algo query. I use php. I use a local btc exchange and its API only publishes last 24h volume which changes every few minutes. I have logged this for past week.

I want to try to use it to derive into near real-time volume. Is it possible to have such an algo?

Example:

Suppose i want to derive real volume from exposed volume. The Exposed volume is only the sum of last 5 trades.

I have tried by one algo like

`current_volume = volume[current_index] - volume[current_index-5]`

`Real Volume: 1 5 8 4 3 1 7 0 3 2 0 6`

`Exposed Volume: 21 21 23 15 14 13 12 11`

`My Algo: 6 4 0 -7 -7 -8 -11 -4`

But my algo is not giving results that even resemble the real volume.

# Answer
> 1 votes
No. The problem is that the change in 24 hour trade volume (over, let's say, 5 minutes) corresponds to the volume in the last 5 minutes, *minus* the trade volume in the same 5 minutes in the previous day. So if you see the trade volume increase by 10 BTC, this tells you that in the past 5 minutes, we traded 10 more BTC than in the same 5 minutes yesterday. But that doesn't tell you whether the trade volume was 20 (and yesterday's volume 10) or 10000 (and yesterday's volume 9990). Of course, you know the total volume, but, in general, there's no way to know how the total volume is distributed over the time of day.

There is can be practically infinite set of possibilities that explain your observations. Barring some very special cases (for instance, the volume traded going to 0 for an entire day) you won't be able to infer anything.

---
Tags: algorithms
---


# Question
Title: For given set of integers, find and count the pairs with maximum value of bitwise or
Let's say we have given set of integers $A = \\{x\_1, x\_2, x\_3, x\_4, \dots, x\_n\\}$, consisting of exactly $n$ values, all of them positive integers. Now the problem is to find the maximum value of bitwise or operation of all possible pairs $(x\_i, x\_j)$

We define bitwise or as bitwise operation that returns true if atleast one of the bits is turned on, in most programming languages it is declared as "|".

Edit: We assume that the numbers in the set can be written with at most 17 bits, or they are smaller than $2^{17}$.

For example, we have: $n=4, A = \\{12, 3, 4, 11\\}$ the maximum value of bitwise or will be $15$, because $12|3=15, 11|4=15, 12|11=15$ so the result is $15$ and we have exactly $3$ pairs that give this result.

**My thinking**

Obviously we can take each pair and see what is their bitwise or, but this leads us to solution in $O(N^2)$, and I think that there is much faster solution, I think that we don't need to calculate the bitwise or of all numbers, and we can only calculate it for some numbers.

# Answer
> 1 votes
If the numbers have width $c\log n$ then there is a randomized $O(n^{2-1/O(\log c)})$ algorithm that finds the maximum OR correctly with high probability. The idea is to find the maximum OR bit by bit, MSB to LSB. We can do this using $c\log n$ queries of the following form: "Is there an OR whose $k$ most significant bits are $b\_1\ldots b\_k$?". Each such query is equivalent (up to bitwise operations) to the query (applied to a different list): "Is there an OR in which all bits are 1?". Abboud, Williams, and Yu gave a randomized $O(n^{2-1/O(\log c)})$ time algorithm for this problem (which they call *Boolean orthogonal detection*, flipping 0s and 1s).

If the numbers have unbounded width then (depending on the exact model of computation), there is no $O(n^{2-\epsilon})$ time algorithm (assuming SETH). Indeed, deciding whether the maximum OR is all 1s is the same as Boolean orthogonal detection, for which the aforementioned hardness is known (see for example these lecture notes of Russel Impagliazzo).

Finally, if the numbers have bounded width then there is a simple $O(n)$ algorithm. The algorithm computes the set of numbers appearing in the input, and looks up the answer at a (rather large) table.

---
Tags: arrays, bit-manipulation
---


# Question
Title: Simultaneous regression of multiple curves in the same dataset or image?
I am getting the pattern shown in the picture from an experiment. To my human brain it is evident that it consists of some 20 straight lines. I need to find position and slope of all these lines (perform a regression). But I need to do it completely automatically. If this were a a single sequence I would have used RLS(Recursive Least Squares) or Kalman filter. But how can I go about if I want to make 20 simultaneous regressions that do not conflict with each other?

What would be the most generic way to solve these kind of problems (say if I have an image of 20 overlapping boxes and need to find size, position and angle of all of them, at once)? I suppose the solution is more than well-known since this would be fundamental for any image recognition, but I cannot find a generic description of the method.

# Answer
There are many possible methods. In your picture, there aren't too many dots, so the following algorithm might be good enough:

* For each pair of points, find the line through them. Count the number of points that are approximately on that line.
* Choose the line that has the most number of points on it. Output that line. Delete all points that are approximately on that line from the figure.
* Repeat until no points remain.

For fancier methods (e.g., if you have a huge number of points, or some prior model for what kinds of lines you expect to see), you can look at RANSAC and the expectation maximization (EM) algorithm, but given your sample picture, the above simple method might be adequate in your setting.
> 1 votes

---
Tags: pattern-recognition
---


# Question
Title: Dynamic connectivity in forests with constant query time
I'm interested in the dynamic connectivity problem for forests. In this problem a forest is subject to updates (edge insertion that do not create cycles and edge deletion) and queries if two nodes are connected.

Link cut trees and Euler tour trees supports these three operations in $O(\log n)$ (Erik Demaine's notes). The results of Eppstein at. all (Sparsification—a technique for speeding up dynamic graph algorithms, JACM, 1997) for general graphs are $O(\sqrt n)$ for updates and $O(1)$ for queries.

In my use case queries are more common than updates, so I'm looking for an alternative structure (the Eppstein structure is too general and too complicated to implement) that supports updates in sublinear time and queries in constant time. Is there such structure?

# Answer
> 0 votes
An Euler tour tree is a linear representation of a tree. When the tour is stored in a balanced binary search tree keyed (implicitly) by the index in tour, the update and query operations can be done in $O(\log n)$. This is described in the referenced Erik's notes.

The tour can be stored in a two level array (similar to the structure described in section 2.2 of Data Structures for Traveling Salesmen). Each tree tour is stored in $O(\sqrt n)$ arrays with $O(\sqrt n)$ elements in each. Each tour element keeps a reference to its array, and each array keeps an reference to its parent array.

The update operations involves a constant number of arrays so it can be done in $O(\sqrt n)$. The query operation can be done in $O(1)$: The root of the tree containing each element is found and then compared. Each root is found in the position 0 of the first array of the tree tour. To find the tree tour containing a element just follows the element reference to its array and then follows the link to the parent array (that is, the tree tour).

---
Tags: algorithms, graphs, data-structures
---


# Question
Title: If everyone believes P ≠ NP, why is everyone sceptical of proof attempts for P ≠ NP?
Many seem to believe that $P\ne NP$, but many also believe it to be very unlikely that this will ever be proven. Is there not some inconsistency to this? If you hold that such a proof is unlikely, then you should also believe that sound arguments for $P\ne NP$ are lacking. Or are there good arguments for $P\ne NP$ being unlikely, in a similar vein to say, the Riemann hypothesis holding for large numbers, or the very high lower bounds on the number of existing primes with a small distance apart viz. the Twin Prime conjecture?

# Answer
People are skeptical because:

* No proof has come from an expert without having been rescinded shortly thereafter
* So much effort has been put into finding a proof, with no success, that it's assumed one will be either substantially complicated, or invent new mathematics for the proof
* The "proofs" that arise frequently fail to address hurdles which are known to exist. For example, many claim that 3SAT is not in P, while providing an argument that also applies to 2SAT.

To be clear, the skepticism is of the proofs, not of the result itself.
> 96 votes

# Answer
Beliefs are orthogonal to proofs. Belief may direct attempted solutions by researchers or rather their main interest but this does not prevent them from checking a proof anyway.

The problem with $P \ne NP$ that many *standard* ways of attempting a proof are already excluded as not sufficient to infer anything, see here for further details.

There is no inconsistency in gathered poll of suspicions and educated conjectures. Also the belief that something will not be proven is not insightful in any way, without a proof of unprovability.

The years of attempts, claims, and discarded methods render people skeptical.

Please look at the prior papers that tried to contribute something towards the resolution.

> "Extraordinary claims require extraordinary evidence."

*This quite accurately characterizes the skepticism.*
> 44 votes

# Answer
A few reasons, some generic and some specific.

The generic reason is that this is a long-known famous problem which many smart people have tried to solve, and many smart people have gotten wrong. The odds that any one new proof is valid is extremely low based off this history.

In this *specific* case, there has been research on what proofs *don't work*. It has been shown that basically *all known proof techniques* for proving things in computer science **cannot prove P!=NP**.

Wikipedia covers this and points out how "Relativizing proofs" (proofs that work regardless of what oracles your TM has access to), "Natural proofs" (involving circuit lower bounds), and "arithmetization" are all either insufficient to distinguish P and NP (show them equal or different), or any such proof would be a ridiculously more powerful result.

In short, not only have many smart people been working at this a long time and failed, along the way they have proven entire families of proofs cannot be used to solve this problem. So when someone comes up with P!=NP, there is natural skepticism, followed by noticing that one of the many proofs about such proofs is violated, and then there is no longer a need to check the rest of the result.
> 24 votes

# Answer
The reason people are skeptical of proof attempts of P!=NP is the same reason that people are skeptical of proofs of any famous conjecture: false proofs are published every few months and shot down. Meanwhile, correct proofs of famous conjectures seem to have little trouble getting attention, in spite of this (see, for example, the Poincare conjecture or Fermat's Last Theorem), but these proofs often rely on deep knowledge of large-scale efforts by groups of mathematicians (such as Hamilton's Ricci flow for the poincare conjecture or the Taniyama–Shimura–Weil conjecture for Fermat's Last Theorem) even if the final steps were done by a single theorist.

P vs NP is a particularly thorny problem because all the "obvious" methods have not only failed to yield a proof, but been proven to be useless with strong theorems. First time would-be provers are very likely think they have stumbled on a proof but instead have fallen into one of these well-known traps. Remarkably, showing that a number of ways of proving P != NP cannot work are the main advances in the field. It's somewhat outrageous that we cannot even show that 3Sat is not decidable linear time, let alone outside of polynomial time!

I would argue that very few people believe it won't be proven ever however. Indeed, the statement P != NP is a such a basic roadblock in our understanding of computational complexity that it's hard not to think that it's true for a simple and elegant reason.

However, if one wants to be cynical, P != NP is equivalent to the statement that just because a proof is easy (i.e. short) doesn't mean that it's not very hard to find the proof (i.e. takes super-polynomial search time). Indeed most theories believe that there is no sub-*exponential* time algorithm for finding proofs suggesting that, given any one method of finding proofs (i.e. a mathematician thinking or a computer search), there are many theorems with simple short proofs which are extremely difficult to find (potentially millennia of search time). Whether P != NP is such a theorem is not known of course!

That said, someone could publish the proof tomorrow.
> 7 votes

# Answer
People don't believe any "proofs" because of the perceived difficulty.

Let's say we meet aliens who are better at maths than humans. Their average school child is about as good at maths as our greatest mathematicians. Not a smart school child, but an average school child.

They have proved the Riemann Hypothesis, the Twin Prime Theorem and the first Hardy-Littlewood Conjecture, and Goldbach's Hypothesis. What do they think about proving that the Travelling Salesman problem can be solved in polynomial time? They will find it unlikely that anyone could solve this. What do they think about proving that the Travelling Salesman problem *cannot* be solved in polynomial time? I think they will find it even less likely that someone could find a proof.

That's just my opinion, but if someone says they have a proof for P = NP or P ≠ NP, I won't believe it.

PS. The Riemann Hypothesis is open for a longer time because it is a classical mathematical problem that made sense to mathematicians 100 years ago. P ≠ NP is computer science, something a lot newer, and AFAIK the whole notion of NP comes from the 1970's only. There has been progress on the Riemann Hypothesis (we can't prove "all zeroes yada yada" but at least "a large portion of all zeroes yada yada"), unlike P ≠ NP. It's one-dimensional. It's about the zeroes of one single function. P ≠ NP is about all possible algorithms to solve a problem.
> 6 votes

# Answer
Because you might think it is undecidable, and maybe even undecidable whether it is undecidable. Many mathematical theorems are that way.
> 4 votes

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


# Question
Title: If h(n) is a perfect heuristic (that is, h(n) = h*(n)), then does it imply that A* will always take linear time complexity?
That is, if h(n) = h\*(n), then A\* only expands nodes that lie on an optimal path to the goal. But does this imply that A\* will always take a linear time in the solution length to find an optimal solution?

I suspect I may be overthinking this problem, but if h(n) = h\*(n) then we are measuring the exact heuristic cost of arriving at a goal node $n$ from x. But I can't see why this would be true, because even though you have a perfect heuristic, it is not monotone, and so you may have a cheaper f-value that may be expanded at a later point in the search, which no longer means the search space is linear.

# Answer
First, to be specific I’m going to assume your heuristic function runs in constant time and we have a graph G with n nodes, and that you are asking about linearity with respect to n.

I claim that in the worst case A\* will run in quadratic time.

Suppose G is a complete graph where every edge has a weight of 10000 except for the “true path” which winds from the starting node along every other node until the final node, and these edges have weight 1.

By definition of A\*, every time we visit a node, we look across all its edges to queue up nodes into our priority queue of paths to explore. By construction, we visit every node and hence consider every edge. It is a complete graph on n nodes, so there is roughly n^2 edges, thus this process takes quadratic time
> 2 votes

---
Tags: algorithms, graphs, artificial-intelligence, search-algorithms, heuristics
---


# Question
Title: Is there a reasonable algorithm to generate a certain "independent clique graph" with minimal vertices?
In the process of trying to find a solution to the rat and poison puzzle with two rats, I've found myself needing the solve the following problem, **in polynomial time**:

Given any $k\_0, k\_1, k\_2,..., k\_{n-1} \in \[2,\infty)$, we want to produce a simple graph $G = (V, E)$ and some $c\_0, c\_1, c\_2,..., c\_{n-1} \subseteq V$ such that:

* Each set of vertices $c\_i$ is a clique of size $k\_i$ in $G$
* For all $(u, v) \in E$, there exists exactly one $c\_i$ such that $u, v \in c\_i$
* $|V|$ is minimal.

This essentially means that we want a graph with at least $n$ cliques, each of size $k\_i$, such that each edge is in exactly one of these cliques, and we want the smallest such graph. Extra cliques that aren't represented by a $c\_i$ will still occur but don't count as overlap, so $G$ isn't generally a block graph.

# Answer
> 1 votes
My initial thought was the following framework for an algorithm:

```
let c = empty array of size n
let G = ({}, {})
for i in [0, n):
    while there's not an independent set of size k_i in G:
        add a new vertex to G
    let S = an independent set of size k_i in G:
    connect every vertex in S to every other vertex in S in G
    let c[i] = S

```

The glaring issue is that I'm relying on a algorithm for independent set here, and there's no general polynomial-time algorithm for it. What I'm trying to figure out is if there is some structure inherent to this problem that makes independent set feasible to compute.

There's a polynomial time algorithm for finding an independent set on a chordal graph (though I can't find a straightforward presentation of the algorithm anywhere yet), so if I can prove that $G$ is always a chordal graph I've solved the problem.

A graph is chordal iff it has a perfect elimination ordering, an ordering of the vertices such that for any vertex v, v and the neighbors of v that occur later in the ordering form a clique. I'll prove this using induction.

**Base case:** Our starting graph has a trivial empty ordering, so our base case holds.

**Inductive step:** We need to show that adding some number of vertices, then filling out an independent set they are part of into a clique, creates a new graph with an ordering if the original graph already had one.

Let $s$ be the previous ordering (for example, $1342$). Let $t$ be an arbitrary ordering on the new vertices. Let our new ordering be $ts$, the concatenation of the two orderings. Since the only edges these new vertices have are within the new clique, and removing any of the vertices in a clique leaves the remaining vertices in a clique as well, as we move across $t$ and check if it forms a clique with the following neighbors in $ts$, it always will. Since we already know the vertices in $s$ satisfy the ordering criteria by the induction hypothesis, all the vertices in $ts$ satisfy the induction hypothesis and our new graph has a perfect elimination ordering. So the inductive step holds

So by our base case and inductive step, on every step of the algorithm, finding the independent set will take only polynomial time in the total number of nodes and edges, and since adding a $k\_i$-clique can always be done in $k\_i$ or fewer new vertices, the number of vertices is at most $\sum\_{i=0}^{n-1} k\_i$, the number of edges is at most the square of that, and therefore the whole algorithm is polynomial in the sum of the inputs, as desired.

I haven't proved that the result has the minimal number of vertices yet. That's going to have to wait for another day though. Might have to explain the previous parts a bit better too.

---
Tags: graphs, clique
---


# Question
Title: To prove or disprove that language is regular
Suppose the language L = {w | w is an integer whose sum of digits is a multiple of 2}. I strongly feel like this is non-regular language, but how should I choose a string to apply the pumping lemma?

# Answer
The language $L$ *is regular* as shown by the following "flip-flop" style minimal and deterministic automaton $\mathcal{A}$, the crux is that you need only two states (not an unbounded amount of memory) to check parity. $\mathcal{A} = \langle \\{odd,even\\}, \\{0..9\\}, even, \\{even\\}, \delta \rangle$ which transition function $\delta$ is defined by :

* $\delta(x,even) = even$ when $x\in \\{0,2,4,6,8\\}$
* $\delta(x,even) = odd$ when $x\in \\{1,3,5,7,9\\}$
* $\delta(x,odd) = even$ when $x\in \\{1,3,5,7,9\\}$
* $\delta(x,odd) = odd$ when $x\in \\{0,2,4,6,8\\}$
> 3 votes

---
Tags: finite-automata, pumping-lemma
---