# Question
Title: Nested Loop Time Complexity vs Successive Loops
An algorithm has a calculation whose worst case time complexity $T(x)=O(x^2)$ that outputs solutions $y$ & $z$ for input $x$ (the algorithm's worst case time complexity is greater than quadratic time):

```
for (i = 1; i <= x; i++)
    {
    for (j = 1; j <= i; j++)
        {
           // Some quadratic time calculation of x that gives y & z
        }
    }

```

A different algorithm using successive loops is created for a given $x$ that outputs the same $y$ & $z$:

```
for (i = 1; i <= x; i++)
    {
         // Some quadratic time calculation of x that gives y
    }
for (i = 1; i <= x; i++)
    {
         // Some quadratic time calculation of x that gives z
    }

```

Is the time complexity of the second algorithm $T\_s(x)=O(x^2)$?

# Answer
I think that the first algorithms running time is actually $\mathcal{O}(x^4)$.

* The outer for loop executes exactly $x$ times,
* the inner for loop executes at most $x$ times during every one of these $x$ iterations of the outer loop

In fact, the inner loop executes exactly $\frac{x(x+1)}{2}$ times, and $\frac{x(x+1)}{2} = \frac{x^2 + x}{2} = \mathcal{O}(x^2)$, since our asymptotic notation allows us to essentially ignore the constant factors.

So already we have a growing complexity of $\mathcal{O}(x^2)$. If we now consider the contents of the inner for loop, which you say is a quadratic time calculation of $x$. I read this as follows: the complexity of the inner loops body is a quadratic function of x $\rightarrow \mathcal{O}(x^2)$. My answer is based largely upon this assumption.

If my assumption is correct, then a time complexity of $\mathcal{O}(x^4)$ easily follows from this reasoning: the outer and inner for loop collectively produce $\mathcal{O}(x^2)$ iterations of some algorithm that takes $\mathcal{O}(x^2)$ steps to complete itself. An *extremely* informal *(read: not quite right, but right enough to demonstrate a point)* mathematical argument for this might be:

($x$ *outer loop iterations*) $\cdot$ ($x$ *inner loop iterations*) $\cdot$ ($x^2$ *loop body steps*) $= x^4$ *total steps*.

With the second algorithm, the same reasoning can be used. Again, we have some procedure, which takes $\mathcal{O}(x^2)$ steps to run, which is being executed $x$ times. This gives us $\mathcal{O}(x^3)$ steps in total. Since we have two loops of this form, we can conclude that algorithm 2 has a time complexity of:

$\mathcal{O}(x^3) + \mathcal{O}(x^3) = \mathcal{O}(x^3)$

Note that in this case we have two consecutive loops that, asymptotically speaking, do essentially the same amount of work. In reality it might be that our first loop which calculates $y$ performs some constant factor amount more or less steps than our second, which calculates $z$, but here that doesn't matter, since we're focusing on the rate of growth of our running time. One way of thinking about it is as follows:

$\mathcal{O}(x^3) + \mathcal{O}(x^3) = \mathcal{O}(x^3 + x^3) = \mathcal{O}(2 \cdot (x^3)) = \mathcal{O}(x^3)$.

Here we can drop the 2, since its a constant factor.
> 3 votes

# Answer
Algorithm 2 seems better in running time at first look, Provided that when your body inside loops takes same amount of time in iterations in both of the Algorithms. i.e. If I consider the asymptotic time as quadratic for the body of loop in each iteration for both algorithms, then Algorithm 1 will have O(x^4) time and Algorithm 2 will have O(x^3) time (As suggested in other answers given).

*But what we see is not always exactly true*. As there also exists '**Amortised Analysis**' in the algorithms, which should be considered in the case, when the body inside the loops can take worst case time for few iterations and for other large part of iterations it takes totally different asymptotic time.

( If we have to consider the amortized analysis, then more information about the operations within the loop is needed to be sure. )

If more detailed information is needed on Amortised analysis, you can refer to "Chapter 17: Amortized Analysis" in "CLRS Introduction to Algorithms" book. It'll be an awesome read.
> 1 votes

# Answer
The time complexity of the second algorithm would be $T\_s(x)=O(x)$. This is because the algorithm runs for a total of $2x$ times, which is $O(x)$.

The first algorithm would run $x$ times for its first run, $x-1$ for its second and so on so you get:

$\text{Algorithm 1} = 1 + 2 + ... + x-1 + x = O(n^2)$

The difference between the 2 algorithms is as such,

* Algorithm 1: will run the outer loop $i$ times, and inner loop will run $i-j$ times. This is equivalent to $O(x^2)$, since $n ( n - y ) = n^2 - ny = O(n^2)$.
* Algorithm 2: Will *always* run the first loop $x$ times, and the second loop $x$ times, giving $O(2x) = O(x)$.

Although your complexity time is correct due to the definition of $O$, since Algorithm 2 is $g(n)= O(n) \leq O(n^2)$, and so $g(n) =O(n^2) $.

This has to do with the actual definition of O-notation. Take a look at this link for more information.

***Edited to reflect quadratic function in body loop:***

Where the quadratic is taking some time (the exponent can be 2 for quadratic, or for any number x \>= 1)

$\text{Work required} = O(n^x)$

$\text{Algorithm 1(without taking quadratic into account)} = O(n^2)$

$\text{Algorithm 1 complete} = n^x * n^2 = n^{x+2} = O(n^{x+2})$

For algorithm 2, we can assume

$\text{Algorithm 2} = n^x * n + n^x * n = n^{x+1} + n^{x+1} = 2n^{x+1} = O(n^{x+1})$

So in your example $\text{x = 2}$, so it would actually be $O(n^3)$ and not $O(n^2)$
> 0 votes

---
Tags: algorithm-analysis, runtime-analysis, loops
---


title: Sorting the number sequence

text:
# Question
Title: Sorting the number sequence
I have

* $4$ variables $n\_1, n\_2, n\_3, n\_4 \in \mathbb N$ that sum to $N$.
* $4$ positive real constants $c\_1 \< c\_2 \< c\_3 \< c\_4$.

Given a particular tuple $(k\_1,k\_2,k\_3,k\_4)$, how do I find the partial sum of the ordered (w.r.t. the sum $c\_1 n\_1 + c\_2 n\_2 + c\_3 n\_3 + c\_4 n\_4$ in an increasing manner) sequence

$$\sum\_{n}^{(k\_1,k\_2,k\_3,k\_4)} (c\_1 n\_1 + c\_2 n\_2 + c\_3 n\_3 + c\_4 n\_4)$$

from the minimum to the given $(k\_1,k\_2,k\_3,k\_4)$?

I think this problem involves some sorting algorithm. This should already be studied in some linear programming problem but I am just not aware of how to do this efficiently (e.g. using Python).

# Answer
> 1 votes
There's a simple $O(N^3 \log N)$ algorithm, though you might be able to do much better. First, compute all $N^3$ quadruples, and the corresponding linear combinations $\sum\_i c\_i n\_i$. Then sort them. Then find the location of the given quadruple. Then compute the running sum.

---
Tags: optimization, sorting, linear-programming
---


# Question
Title: Is it possible to solve the halting-after-$n$ steps problem more efficient than just execute $n$ steps?
The halting-after-$n$ steps problem may be defined as the question if a given turing machine halts after a maximum of $n\in\mathbb{N}$ steps. Is it theoretically possible to solve this problem in general in less than $n$ execution steps (just execution the program) or can't this be done? If not, why not?

Thank you

# Answer
> 3 votes
The time hierarchy theorem, or rather its proof, gives some answer to this question. If you look at the proof, you should get a lower bound of $\Omega(n/\log n)$.

In more detail, consider the language $L$ of all triples $\langle M,x,1^t \rangle$ such that $M$ halts on $x$ after at most $t$ steps. Suppose that this can be solved in time $f(n)$, where $n$ is the input length (which is $t + |M| + |x|$). Then you can construct a Turing machine which on input $\langle x,1^t \rangle$ determines whether $\langle x,x,1^t \rangle \in L$, if so runs into an infinite loop, otherwise halts. When run on itself as input, this machine either halts in time $f(t + O(1)) + O(1)$ or never halts. Hence if $f(t + O(1)) + O(1) \leq t$, we reach a contradiction. This shows that $f$ has to essentially be at list linear.

---
Tags: turing-machines, halting-problem
---


# Question
Title: Beam size is a parameter in some RNNs like TensorFlow's Magenta. What is beam size?
Magenta's `melody_rnn_generate` method includes a parameter `beam_size`. What is it and how does affect the melody?

# Answer
> 2 votes
**Beam size**, or beam width, is a parameter in the beam search algorithm which determines how many of the best partial solutions to evaluate. In an LSTM model of melody generation, for example, beam size limits the number of candidates to take as input for the decoder. A beam size of 1 is a best-first search - only the most probable candidate is chosen as input for the decoder. A beam size of $k$ will decode and evaluate the top $k$ candidates. A large beam size means a **more extensive search** \- not only the single best candidate is evaluated.

Beam search is a heuristic search algorithm that uses breadth-first search to build its search tree and reduces the search space by eliminating candidates to reduce the memory and time requirements. Without the beam search, the worst time and space complexity for the best-search would be $\mathcal{O}(b^m)$ where $b$ is the branching factor and $m$ is the maximum depth. With beam search, the worst time complexity is $\mathcal{O}(kb)$ and the worst case space complexity is $\mathcal{O}(k)$.

In the case of melody creation with Magenta, a beam size larger than the default of 1 will build a search tree for each candidate evaluation, as visible in this incomplete sketch of the graph ('h' represents an arbitrary heuristic cost):

A larger beam generally means a **more accurate prediction** at the expense of memory and time. In one trial using `attention_rnn`, for example, modifying the beam width from 1 to 4 decreased the average negative log-likelihood of sequence (melody) generation from 84.2 to 38.6.

1 - Beam search (Wikipedia)

2 - Notes on the Complexity of Search (MIT)

---
Tags: graphs, machine-learning, artificial-intelligence, search-algorithms, neural-networks
---


# Question
Title: What is branch factor for beam search in RNNs like TensorFlow's Magenta?
TensorFlow's Magenta melody generation module has a parameter for `branch_factor`. What is it?

# Answer
**Branch factor** in beam search refers to average number of branches at each level of a search tree. When predicting a sequence in an LSTM model, such as note selection in melody generation, $b$ branches will be decoded. Increasing the branch factor from 1 to 4 in the call to melody\_rnn\_generate will maintain the average number of branches to be at $b$.

Specifically for Magenta, it generates 4 branches for each event sequence. It will **increase the accuracy** of the prediction at the expense of time, and in melody creation at the risk of getting stuck in a local optimum. For example, increasing the branch factor from 1 to 2 decreased the average negative log-likelihood of a melody generation implementation from 36 to 8, but also made the sequence prediction more dependent on the primer sequence (repeating the primer note).
> 1 votes

---
Tags: artificial-intelligence, search-algorithms, neural-networks
---


title: What's wrong with this

text:
# Question
Title: What's wrong with this
Here's the question: Do more baby names start with "A" or "B"? Write code to count and print those two counts ("A" count, then "B" count).

I then write this code down:

table = new SimpleTable("baby-2010.csv");

count1 = 0;

count2 = 0;

for (row: table) {

// your code here

if (row.getField("name").startsWith("A")) {

count1 = count1 + 1; }

if (row.getField("name").startsWith("B")) {

count2 = count2 + 2; }

} print("A count:",count1) print("B count:",count2)

I ran the code which then came out like this: A count: 258 B count: 198

Any ideas as to why this might be wrong?

# Answer
First off, I don't think this is the appropriate place for this question.

Second; why are you incrementing count2 by 2 each time you find a "name" field that begins with a B? Surely this should be incremented by 1, like count 1 is.

Out of interest, do you know what the correct results should be?

Could you post them?
> 0 votes

---
Tags: counting
---


title: The height of 5-balnced tree is O(logn)

text:
# Question
Title: The height of 5-balnced tree is O(logn)
Binary tree with external leaves is a 5-balanced tree if the path from the root to the farthest external leaf is no more than 5 times as long as the path from the root to the nearest external leaf, and if his right and left subtrees are 5-balanced too. Show that the height of such a tree is O(logn).

I was trying to prove it by finding the minimum number of nodes in such a tree with height h and then saying that the height of the tree is at most the log of this number, but I'm not sure how to find it. Thanks

# Answer
> 2 votes
Suppose that the tree has depth $D$. Then all leaves are at distance at least $D/5$ from the root, which means that the tree contains the full binary tree of depth $D/5$ as a subtree. This implies that $n \geq 2^{D/5}$, and so $D = O(\log n)$.

Note that this argument doesn't use the recursive part of the definition.

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


title: Number of cliques in a graph

text:
# Question
Title: Number of cliques in a graph
I think the number of cliques in a graph is generally exponential in the of vertices of that graph. Does anyone know any reference for that?

# Answer
I am assuming you mean the number of *maximal cliques*, as the number of cliques of a complete graph is trivially $2^n$ (any subset of the vertices forms a clique).

For the number of maximal cliques, take the complement of a disjoint union of triangles. Since the number of *maximal independent sets* is exactly the same (in the complement), you can count the number of maximal independent set in a graph that is a disjoint union of triangles. This number is $3^{n/3}$ (Moon and Moser, 1965).

See also: The number of cliques in a graph: the Moon and Moser 1965 result.
> 5 votes

---
Tags: graphs, reference-request, clique
---


# Question
Title: Confusing method of proving PSPACE-completness
I don't understand a way of proving PSPACE-completness. The way was used by my lecturer. I can use reduction, however following method confuse me:

*We consider sequence (of polynomial length) of configurations and check if transitions betweens configurations in sequence are legal. We also check if machine accept word $w$. In other words, we analyze run of polynomial-space machine $M$ on word $w$ and check if this run is legal and accepting.*

I can't understand why such reasoning work. I don't show exact example because my lecturer use this technique fairly often.

Can you explain me why it work?

# Answer
This technique is also known as *computation history* method. Given a Turing machine $M$ you (or another TM $M'$) inspect its computation "flow" or "history" configuration by configuration. You can think of TM **configuration** as snapshot of the tape content plus machine's state at some particular time. Every step of a TM generates a new configuration. The set of all that configurations is a computation history. If computation halts then that set is finite.

**UPDATE: (on David Richerby comment)** The following paragraph may be irrelevant to the question since I overlooked "sequence (of polynomial length) of configurations" in OP which is different from "the sequence of configurations where each is of polynomial length".

*Polynomial length requirement: because you want to prove PSPACE membership, maximum number of used tape cells must be polynomial. That's why an accent made on polynomial length.*

Transitions betweens configurations in sequence are legal: you want be sure that machine's transitions between states were really made according to the machines's transition rules, otherwise the run is not legal. For example if a configuration $C\_i$ differs from the configuration $C\_j$ by 3 symbols (assuming a single tape TM) then you can say that transition is not legal, since the TM cannot change 3 symbols in a single step.

Also note that if one TM $M$ simulates another TM $M'$ then if $M'$ uses polynomial space then the whole simulation also uses polynomial space since simulation itself takes polynomial space.

**Example of use of configurations:** Assume you know that a certain class of TM machines use no more than, say, $n$ cells of tape where $n$ is input size. Then halting problem for this class of TMs is decidable. Since a TM has finite number of states $|Q|$ and alphabets $|\Sigma|$, and since we that it uses at most $n$ cells, we simply can compute that the TM has at most $n|Q||\Sigma|^n$ configurations. Then you simulate that TM and check if at some point it repeats it's configuration then there must be an infinite loop and so it never halts (since the tape use is bounded!, the TM may not move infinitely move its head to the right and right symbols). The latter class is also known as *linear bound automata*.
> 2 votes

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


# Question
Title: What TSP variant doesn't return to start point?
For my case I have starting point and several cities.

I want the shortest route to visit all cities without returning starting point.

I have read several TSP algorithm and all include the return a full cycle.

So what TSP variation should I look for to solve my problem?

# Answer
You can reduce to a normal TSP variant by adding a dummy city that is distance $0$ away from each of the existing cities. (See also this answer on StackOverflow.)

**Edit:** it seems that my suggested modification is not quite appropriate: as I understand it, your Hamiltonian path has a fixed starting point but no fixed end point. One way to solve this is to add two dummy cities $v$ and $w$ such that:

* $v$ is only connected to the starting point and to $w$,
* $w$ is connected to everything.
> 6 votes

# Answer
Turn it into an instance of the Hamiltonian $s-t$ path problem, as suggested in the comments of your original post.

Take your input graph and add two new vertices $s$ and $t$. Both of them should be connected to all other cities, but not to one another. All edges incident to $s$ or $t$ should be weighted 0.

Your 'salesman' can then start at $s$, visit all cities included on the original graph, and finish up at $t$.
> 0 votes

---
Tags: optimization, hamiltonian-path
---


# Question
Title: How to compute (n^(n-1)^(n-2)^(n - 3)^(...)^2^1) mod m efficiently?
I'm trying to solve this problem (https://open.kattis.com/problems/exponial) by using fast-exponentiation but I'm getting time limit exicted.

How can I compute it efficiently?

# Answer
> 1 votes
I describe an algorithm for calculating infinite modular power towers in this Math.SE answer.

You can use it for your problem by applying it on $n, n-1, \ldots, 2, 1, 1, \ldots$.

And as proven by Anders Kaseorg, there is a simpler method that uses the identity

$$n^k \equiv n^{\varphi(m) + (k \bmod \varphi(m))} \mod m$$

when $k \geq \varphi(m)$.

---
Tags: reference-request, number-theory
---


title: Asymptotic vs real-world complexity

text:
# Question
Title: Asymptotic vs real-world complexity
Let's say an algorithm has an asymptotic time complexity of $\Theta(N)$. However in practice, $N$ is bound by a small upper limit (e.g. the size of a character set). Can we then say the complexity is $\Theta(1)$? Or is there a better way of describing the performance of an algorithm in a particular real-life situation?

# Answer
If $N$ is bounded by a small upper limit, asymptotics cease to be useful. At that point you want either exact operation counts, or even better just measure actual speed.
> 2 votes

# Answer
Keep in mind algorithms do not know the input before they receive it. Algorithms are (typically) blind in that regard.

For example, if you have an algorithm that computes something about an alphabet of size $n$, the algorithm doesn't know that your alphabet may be restricted to 26 characters, or all ASCII characters, or all unicode characters. The algorithm only knows that it will receive $n$ characters and compute something about them. The algorithm would then still take an amount of operations as a function of $n$, not $O(1)$ necessarily.

With that being said, if you have hard coded in the algorithm that the input is only the size of a particular alphabet you could then argue that it actually is $O(1)$. Although, I would then argue that it's not a valid solution for all alphabets, but you might not care if it does solve your problem. Even if you do have the input size upper bounded, it can still be good to represent it as a function of $n$ while specifying the upper bound as well. For example, if I know my input size is upper bounded by $2^{32}$, then sure the algorithm runs in $O(1)$, but that's not going to be helpful to anyone. It'd be better to say it runs in $O(f(n))$ until an upper bound of $n \leq 2^{32}$.
> 1 votes

---
Tags: algorithms, runtime-analysis
---


# Question
Title: Combination generator - sets of size k from n
unique numbers $1 - n$
combinations (sets) of size $k$
$k \< n$

do not re-use an $n$ in a set \[1, 1, 1\] is not valid

How to generate all *unique* sets of size $k$?
\[1,2,3\] = \[3,2,1\] order does not matter

the number of sets will be ${\binom{n}{k}}$

input
$n = 4, k = 2$
output
\[1, 2\]
\[1, 3\]
\[1, 4\]
\[2, 3\]
\[2, 4\]
\[3, 4\]

I have found that is often called n chose k

hard coded it looks like

```
for (i = i; i <= n - 1; i++)
    for (j = i + 1; j <= n - 1; j++)

```

I tried coding the first solution from Yuval Filmus but it does not work for me
It returns \[1,2\], \[1,2\]
Had to adjust for 0 based arrays

```
public static void Combinations(int n, int k)
{
    bool[] A = new bool[n];
    int[] B = Enumerable.Range(1, k).ToArray();
    Generate(1, A, B, k, n);
}
public static void Generate(int l, bool[] A, int[] B, int k, int n)
{
    Debug.WriteLine(string.Join(", ", B));
    if (l == k + 1)
    {
        Debug.WriteLine("l == k + 1");
        return;
    }

    for (int i = 0; i < n; i++)
    {
        if (!A[i])
        {
            A[i] = true;
            B[l - 1] = i + 1;
            Generate(l + 1, A, B, k, n);
            A[i] = false;
        }
    }
}

```

# Answer
## Ordered combinations

Here is a simple recursive routine, which has access to a Boolean array $A$ of length $n$, whose initial entries have the value *false*, and to an integer array $B$ of length $k$. The routine is called with $\ell = 1$.

**Generate($\ell$):**

* If $\ell=k+1$, output $B$, and exit the current recursive call.
* Go over elements $i$ from $1$ to $n$:
* + If $A\[i\]$ is *false*:
* + - Set $A\[i\]$ to *true*.
* + - Set $B\[\ell\]$ to $i$.
* + - Call Generate($\ell+1$).
* + - Set $A\[i\]$ to *false*.

The array $B$ consists of the current tuple, and the array $A$ keeps track of which elements are currently used (this is an optimization, since the information can be gleaned from $k$).

It is possible to convert this algorithm to an iterative one, and to improve its complexity for large $k$ (in particular, for the extreme case $k=n$). Take a look at Section 7.2 of Volume 4A of Knuth's Art of Computer Programming (see here for table of contents).

## Unordered combinations

These are somewhat simpler, since we don't need the array $A$. The recursive routine is called with $\ell=1$:

**Generate($\ell$):**

* If $\ell = k+1$, output $B$, and exit the current recursive call.
* If $\ell = 1$, set $\max$ to 0, otherwise set $\max$ to $B\[\ell-1\]$.
* Go over all elements $i$ from $\max+1$ to $n-(k-\ell)$:
* + Set $B\[\ell\]$ to $i$.
* + Call Generate($\ell+1$).

This generates unordered combinations (like you asked in the question), each of them itself ordered. In the code, $\max$ is just the maximum element in the current tuple. You can also pass it as a parameter as in bstrauch24's answer.

Again, the algorithm can be made iterative, and Knuth (same place) has even more information.
> 1 votes

# Answer
Here is a recursive solution in python:

```
n, k = 4, 2

def dfs(A, start):
    if len(A) == k:
        print(A)

    for i in range(start, n + 1):
        A.append(i)
        dfs(A, i + 1)
        A.pop()

dfs([], 1)

```
> 1 votes

---
Tags: combinatorics
---


# Question
Title: Decision tree complexity of deciding whether array is "zigzag"
I am currently studying for a test on data structures.

I have to find the lower and upper bounds for the following problem:

> Input: an array with $n$ numbers.
>
> Output: boolean answer for the question if there exist $1\le i\le j\le n$ so that:
>
> * All the elements in the array between $1$ and $i$ are in ascending order.
> * All the elements in the array between $i$ and $j$ are in descending order.
> * All the elements in the array between $j$ and $n$ are in ascending order. We call this type of array a *zigzag* array.

I have these ideas: in general, in order to find an upper bound I am looking for an efficient algorithm. For lower bound I am using the decision tree model. For example: in order to find the lower bound for comparison sort algorithms of $n$ numbers, we have $n!$ leaves on the binary decision tree, so we have $n!$ different possibilities for sorting $n$ numbers, which results in an $Ω(n \log n)$ lower bound.

For upper bound I am thinking about just moving from the first element step by step and finding if the array is a zigzag or not, so upper bound is $O(n)$

Lower bond: I don't know how many different possibilities of zigzag arrays of length $n$ we have, so i don't know how so solve it. If one of you has a different method of finding the lower bound I will be happy to know.

# Answer
You can prove a lower bound of $n-3$ comparisons, almost matching the trivial upper bound of $n-1$ comparisons (surely the gap can be closed with a bit more work). The proof uses an adversary argument. Whenever the algorithm compares two elements $s\<t$, the answer is always $A\[s\]\<A\[t\]$ unless $s=n-1$ and $t=n$, in which case the answer is $A\[n-1\]\>A\[n\]$.

It is always consistent that the array is zigzag, with $i=n-1$ and $j=n$ (the order is $A\[1\] \< A\[2\] \< \cdots \< A\[n-2\] \< A\[n\] \< A\[n-1\]$). Now suppose you make less than $n-3$ comparisons. In particular, if you think of your comparisons as edges on the graph on vertices $\\{1,\ldots,n-2\\}$ (we ignore comparisons to $A\[n-1\]$ or $A\[n\]$), then the graph is disconnected. In particular, there are vertices $s\<t \leq n-2$ which weren't compared. It is therefore consistent that $A\[s\] \> A\[t\]$ whereas $A\[t\] \< A\[n-1\] \> A\[n\]$ (for example, the order could be $A\[1\] \< \cdots \< A\[s-1\] \< A\[t\] \< A\[s\] \< \cdots \< A\[n-2\] \< A\[n\] \< A\[n-1\]$), in which case the array isn't zigzag since it has two disjoint decreasing parts. Hence the algorithm doesn't know the answer.
> 1 votes

---
Tags: data-structures, decision-tree
---


# Question
Title: Accurate way to compute the sum of exponentials
In my work, I had to essentially compute the following quantity.

Given a sequence of positive floating point numbers $\\{a\_i\\}\_{i=1}^n$, such that

$$6000 \leq a\_i \leq 7000$$

I needed to compute the following quantity (for some $n\>1$, but for now can assume $n=1000$):

$$\log\_2\left(\frac{\sum\_{i=1}^n 2^{a\_i}}{n}\right)$$

Direct computation is infeasible as the exponents are too large. So I rewrote the above expression as $$a\_1 + \log\left(\frac{1+\sum\_{i=2}^n 2^{a\_i-a\_1}}{n}\right)$$

This also seemed a bit daunting but was better than what I had. My question was, is there a better way/algorithm to compute the above quantity? I appreciate any help on this.

The following observation might help:

$$\frac{\sum\_{i=1}^n a\_i}{n}\leq \log\_2\left(\frac{\sum\_{i=1}^n 2^{a\_i}}{n}\right)\leq \max\_{1 \leq i \leq n} a\_i$$

# Answer
> 4 votes
Let $a = \max\_i a\_i$. Then your expression is equal to $$ a + \log\_2 \frac{\sum\_i 2^{a\_i-a}}{n}, $$ and this should be a very good approximation (this is "renormalization"). Don't forget to add the numbers in decreasing order of magnitude (that is, sort the $a\_i$'s so that they are in decreasing order).

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


# Question
Title: Decision tree complexity of finding parameters of "zigzag" array
I am currently studying for a test on data structures.

I have to find the lower and upper bounds for the following problem:

> An array is called a *zigzag* array if there are $1 \leq i \leq j \leq n$ so that the array increases from $1$ to $i$, decreases from $i$ to $j$, and increases from $j$ to $n$.
>
> Input: a zigzag array. Output: the position of $i$ and $j$.

My answer:

* Upper bound: just going on the array and finding $i$ and $j$, which takes $O(N)$.
* Lower bound: I think that we need to find pairs $i$ and $j$ for which $k$ is bigger than $i$ in $n$ elements, I don't know how to solve it.

# Answer
> 0 votes
The obvious lower bound is $\Omega(\log n)$, since there are $\binom{n+1}{2}$ possible answers. It is likely that using smart binary search you can find $i,j$ in $O(\log n)$ queries. I suggest starting with the easier case in which $j = n$, that is, the array increases and then decreases, and you want to find its maximum in $O(\log n)$ queries. Such arrays are known as *bitonic*, and indeed you can find $i$ in $O(\log n)$ comparisons (see for example this solution).

---
Tags: data-structures, decision-tree
---


# Question
Title: NP-completeness of solving quadratic equations over $\mathbb{Z}_2$
> Let $\chi$ be a degree 2 equation over $\mathbb{Z}\_2$ of the form: $$x\_{i\_1}x\_{j\_1} + x\_{i\_{2}}x\_{j\_1} + \cdots + x\_{i\_m}x\_{j\_m} + x\_{k\_1} + \cdots + x\_{k\_l} = b $$ for $ k\_i \in \\{1, \dots, n\\}, b \in \\{0,1\\}$ for some $m, l \in \mathbb{N}$
>
> Prove that deciding whether a system of such equations has a solution is NP-complete.

---

So, we should to prove two things:

1) The problem $\in NP$

2) Another NP-complete problem can be reduced to that problem.

I have no idea how to start. Please hint me. It is tempting to use $SAT$ problem, but, when I am trying to convert that problem I got stuck: How to get $1$ (the truth value)?

# Answer
> 9 votes
You can express the constraint $x \lor y = z$ (where $\lor$ is the OR operator) as the equation $(1-x)(1-y) = (1-z)$, that is, $xy+x+y+z=0$. Using this primitive you can express SAT, showing that your problem is NP-hard. Showing that it is in NP is easier.

---
Tags: np-complete, np-hard
---


# Question
Title: When are adjacency lists or matrices the better choice?
I was told that we would use a list if the graph is *sparse* and a matrix if the graph is *dense*. For me, it's just a raw definition. I don't see much beyond it. Can you clarify when would it be the natural choice to make?

Thanks in advance!

# Answer
First of all note that *sparse* means that you have very few edges, and *dense* means many edges, or almost complete graph. In a complete graph you have $n(n-1)/2$ edges, where $n$ is the number of nodes.

Now, when we use matrix representation we allocate $n\times n$ matrix to store node-connectivity information, e.g., $M\[i\]\[j\] = 1$ if there is edge between nodes $i$ and $j$, otherwise $M\[i\]\[j\] = 0$.
But if we use adjacency list then we have an array of nodes and each node points to its adjacency list **containing ONLY its neighboring nodes**.

Now if a graph is sparse and we use matrix representation then most of the matrix cells remain unused which leads to the waste of memory. Thus we usually don't use matrix representation for sparse graphs. We prefer adjacency list.

But if the graph is dense then the number of edges is close to (the complete) $n(n-1)/2$, or to $n^2$ if the graph is directed with self-loops. Then there is no advantage of using adjacency list over matrix.

In terms of space complexity
Adjacency matrix: $O(n^2)$
Adjacency list: $O(n + m)$
where $n$ is the number nodes, $m$ is the number of edges.

When the graph is undirected tree then
Adjacency matrix: $O(n^2)$
Adjacency list: $O(n + n)$ is $O(n)$ (better than $n^2$)

When the graph is directed, complete, with self-loops then
Adjacency matrix: $O(n^2)$
Adjacency list: $O(n + n^2)$ is $O(n^2)$ (no difference)

And finally, when you implement using matrix, checking if there is an edge between two nodes takes $O(1)$ times, while with an adjacency list, it may take linear time in $n$.
> 24 votes

# Answer
To answer by providing a simple analogy.. If you had to store 6oz of water, would you (generally speaking) do so with a 5 gallon container, or an 8oz cup?

Now, coming back to your question.. If the majority of your matrix is empty, then why use it? Just list each value instead. However, if your list is *really* long, why not just use a matrix to condense it?

The reasoning behind list vs matrix really is that simple in this case.

P.S. a list is really just a single column matrix!!! (trying to show you just how arbitrary of a decision/scenario this is)
> 4 votes

# Answer
Consider a graph with $N$ nodes and $E$ edges. Ignoring low-order terms, a bit matrix for a graph uses $N^2$ bits no matter how many edges there are.

How many bits do you actually need, though?

Assuming that edges are independent, the number of graphs with $N$ nodes and $E$ edges is ${N^2 \choose E}$. The minimum number of bits required to store this subset is $\log\_2 {N^2 \choose E}$.

We will assume without loss of generality that $E \le \frac{N^2}{2}$, that is, that half or fewer of the edges are present. If this is not the case, we can store the set of "non-edges" instead.

If $E = \frac{N^2}{2}$, $\log\_2{N^2 \choose E} = N^2 + o(N^2)$, so the matrix representation is asymptotically optimal. If $E \ll N^2$, using Stirling's approximation and a little arithmetic, we find:

$$\log\_2 {N^2 \choose E}$$ $$= \log\_2 \frac {(N^2)!} {E! (N^2 - E)!}$$ $$= 2E \log\_2 N + O(\hbox{low order terms})$$

If you consider that $\log\_2 N$ is the size of an integer which can represent a node index, the optimal representation is an array of $2E$ node ids, that is, an array of pairs of node indexes.

Having said that, a good measure of sparsity is the entropy, which is also the number of bits per edge of the optimal representation. If $p = \frac{E}{N^2}$ is the probability that an edge is present, the entropy is $- \log\_2{p(1-p)}$. For $p \approx \frac{1}{2}$, the entropy is 2 (i.e. two bits per edge in the optimal representation), and the graph is dense. If the entropy is significantly greater than 2, and in particular if it's close to the size of a pointer, the graph is sparse.
> 3 votes

---
Tags: graphs, data-structures, lists, adjacency-matrix
---


title: Numerator of HRRN scheduling formula

text:
# Question
Title: Numerator of HRRN scheduling formula
In the HRRN scheduling, priority formula is

P = (W+E)/E , where W: waiting time and E: estimated run time.

CPU finds the job that has highest priority value and does that job.

However, the formula is equivalent to P = 1 + W/E. If we just "minus 1" and make a new formula P' = W/E, the order of jobs does not change.

So the question is, why do we use P = (W+E)/E rather than P' = W/E? Is there any specific reason (like P must be greater than 1)? Or are they just using the original formula since it was made?

# Answer
You can use either formula, since as you mention, the resulting algorithms are completely equivalent. The reasoning behind the standard formula $(W+E)/E$ is that it is the ratio between the *expected completion time* to the *expected running time*. Presumably when the algorithm was first suggested, the expected completion time was denoted by its own variable.
> 1 votes

---
Tags: operating-systems, process-scheduling
---


# Question
Title: What exactly is a linear function, and what is a nonlinear function?
I am learning a bit about machine learning, and I frequently see things labeled "linear function" or "nonlinear function."

For example when discussing a neural network created by combining individual logistic regression nodes, a book I read noted that logistic regression is a linear function, and that the entire network would be no more powerful than a linear model except that a nonlinear function (such as relu or tanh) is applied to each node. I don't really appreciate this, because I don't have a firm grasp on the definition of linear function.

To use a simpler (to me) example, I was confused when I learned that both SVM and linear regression are linear models. It is easy for me to see how linear regression is a linear model, because its calculations are similar to the definition of a line, `y = mx + b`, that I learned in middle school. SVM seems more exotic to me.

So how can we know if something is a linear function/model versus a nonlinear one? Does it have to do with how the inputs are gathered, or the nature of the calculations afterward?

# Answer
> 3 votes
A linear function is a function of the form $$ \ell(x\_1,\ldots,x\_d) = \sum\_{i=1}^d a\_i x\_i + a\_0, $$ where sometimes the constant term isn't allowed.

A linear classifier is a classifier which is of the form "$\ell(x\_1,\ldots,x\_d) \geq 0$", where $\ell$ is linear.

Using the "kernel trick", you can masquerade non-linear classifiers as linear classifiers; SVM with a non-linear kernel is linear in that sense. In brief, we fix a mapping $\Phi\colon \mathbb R^d \to \mathbb R^D$ (where $D$ is possibly infinite), and then use a classifier of the form "$\ell(\Phi(\vec{x})) \geq 0$". The kernel trick is a way to evaluate the classifier (and train the model) without actually computing $\Phi$.

# Answer
> 3 votes
> how can we know if something is a linear function/model versus a nonlinear one?

A (classification)model is considered to be linear if it uses a linear combination of the input variables(that define a data point) to determine the class it belongs to.

For instance, in the SVM technique (without kernels), given the training set of data points, the algorithm comes up with a separating hyperplane i.e., a generalisation of the line in 2D and the plane in 3D (each of which can be represented by linear equation, of the form, $\overline \alpha^{T}(\overline x-\overline c)=0$ where $\overline c$ is some point that lies on the hyperplane and $\overline \alpha$ is the normal vector to the hyperplane, usually taken to be of unit magnitude).

> Does it have to do with how the inputs are gathered, or the nature of the calculations afterward?

The choice of inputs gathered can definitely simplify the model in question. Another way to simplify the model is to transform the inputs from one space to another. For example, if the set of data points are labeled by which side they lie on with respect to the parabola $y= x^2$, then instead of working with input points of the form $(x,y)$ directly, we can transform the data to $(r,s) = (x,\sqrt y)$, then the classifer in the transformed space has the neat form $r-s = 0$ which is a linear classifier and thus easier to learn. Moreover, the inputs being transformed into a space where they satisfy linear relationships among themselves are easier to interpret usually.

---
Tags: machine-learning
---


# Question
Title: Number of bits to encode number of accepting paths of an $NP$ machine?
Can polynomial number of bits always encode the number of accepting paths of an $NP$ machine?

Can polynomial number of bits always encode the number of accepting paths of any machine in the polynomial hierarchy?

# Answer
The transcript of a computation of a machine in the polynomial hierarchy has polynomial length (since the running time of the machine is polynomial). Hence the total number of computations is $2^{p(n)}$ for some polynomial $p(n)$, and so the number of bits needed to encode the number of accepting computations is $\log \[2^{p(n)}\] = p(n)$, that is, polynomial.
> 1 votes

---
Tags: complexity-theory, np
---


# Question
Title: How to balance the inflow and outflow of each vertex in a bipartite graph?
I have a situation where in a group of people, every person is trading with multiple people and giving them some money. It can be visualised as a directed bipartite graph with `L` and `R` as the total set of people. A directed edge from `l` to `r` means `l` gave `r` some money with weight `w` which is the weight of the edge. Now I'm an auditing firm and want to make sure that the total amount given out by a person should be as close as possible to the amount received by him. I can limit each such transaction (implying I can reduce the weight of any edge in the graph). What is the best way to solve this approximately with the minimum restrictions required (in terms of actual amount)?

Ex. if

```
a -> 10 -> b
b -> 10 -> c
c -> 5  -> a

```

can be limited to

```
a -> 5 -> b
b -> 5 -> c
c -> 5 -> a

```

by reducing `10` units of transactions

# Answer
> 1 votes
You can write a linear program. For each edge you have a restriction variable. You want to minimize the sum of the restriction variables. For constraints you want to have the sums of the differences between outgoing edges and the incoming edges (minus their restriction variables) to be smaller than a threshold that you choose.

---
Tags: graphs, approximation, network-flow
---


# Question
Title: Time Complexity analysis for Map-Reduce model
I am trying to redesign my algorithm to run on Hadoop/MapReduce paradigm. I was wondering if there is any holistic approach for measuring time complexity for algorithms on Big Data platforms.

As a simple example, taking average of n (= 1 billion) numbers can be done on O(n) + C (assuming division to be constant time operation). If i break this massively parallelizable algorithm for Map Reduce, by dividing data over k nodes, my time complexity would simply become O(n/k) + C + C'. Here, C' can be assumed as the startup job planning time overhead. Note that there was no shuffling involved, and reducer's job was nearly trivial.

I am interested in a more complete analysis of algorithm with iterative loops over data and involve heavy shuffling and reducer operations. I want to incorporate, if possible, the I/O operations and network transfers of data.

# Answer
> 1 votes
S. Arora, B. Barak, Computational Complexity Modern Approach, Chapter 13 is a good introductory resource to this topic:

> Communication complexity concerns the following scenario. There are two players with unlimited computational power, each of whom holds an $n$ bit input, say $x$ and $y$. Neither knows the other’s input, and they wish to collaboratively compute $f(x, y)$ where the function $f : \\{0, 1\\}^n \times \\{0, 1\\}^n \rightarrow \\{0, 1\\}$ is known to both. Furthermore, they had foreseen this situation (e.g., one of the parties could be a spacecraft and the other could be the base station on earth), so they had already — before they knew their inputs $x, y$ — agreed upon a protocol for communication. The cost of this protocol is the number of bits communicated by the players for the worst-case choice of inputs $x, y$.

# Answer
> -2 votes
See you are right but you know its quite hard to say a specific time complexity of map reducing. It depends upon the query. But in that case it should be o(nlogn/k)+c+c' because of k nodes. These all shorts of queries including a mapping phase of a map reducing texhnique follows a Btree concept.So from that place for inner computations we may say that its time complexity \> o(nlogn)+c+c'.

Correct my suggestions please.

---
Tags: algorithms, algorithm-analysis, runtime-analysis, parallel-computing
---


title: A Question on SAT

text:
# Question
Title: A Question on SAT
> A logical formula is unsatisfiable **if and only if** for the formula to be true, at least one of its variables must be both true and false.

I discovered SAT today, and wanted to try my hands at solving it. I arrived at the above statement as a general principle for any attempt I want to make at solving SAT. Is the principle true?

# Answer
> 5 votes
Your statement is not very precise, because you don't define "requires" but it looks like you're close to discovering resolution proofs. Using the resolution rule you can derive new clauses from your formula. If you can derive both x and not x, then the formula is not satisfiable.

---
Tags: satisfiability
---


title: $\mathsf{NL}$ versus $\mathsf{NL}[2]$

text:
# Question
Title: $\mathsf{NL}$ versus $\mathsf{NL}[2]$
There is an equivalent definition for the class $\mathsf{NL}$ with verifier. Those verifiers are deterministic Turing machines that can read the witness tape only once in one way from left to right.

Given a function $f:\mathbb{N}\to\mathbb{N}$ we say that $\mathsf{NL}\[f(n)\]$ is the class obtained by the above definition but the verifier can read the witness $f(n)$ times for an input of size $n$ (i.e. when the verifier finished reading the witness the goes straight to the beginning of it).

We can see of course that $\mathsf{NL}=\mathsf{NL}\[1\]$.

The question is whether $\mathsf{NL}=\mathsf{NL}\[2\]$.

**Clarification**: **Prove** or **Disprove** that $\mathsf{NL}=\mathsf{NL}\[2\]$.

It is clear that $\mathsf{NL}\subseteq \mathsf{NL}\[2\]$. For the second part I tried to construct a verifier that can read the witness only once for $L\in \mathsf{NL}\[2\]$. I said that the verifier expects a witness of the form $w\sharp w$ and runs the $\mathsf{NL}\[2\]$ verifier for $L$ with $w$ and then when it finishes and wants to read it again with second copy of $w$. But the major problem with my approach is that maybe someone tricked me and put a non equal sub-witnesses and I won't be able to find out about this with $\log(n)$ space thus it does not work.

# Answer
> 11 votes
You can show that $\mathsf{NL}\[2\] \subseteq \mathsf{NL}$ as follows. We are given an $\mathsf{NL}\[2\]$ machine $M$, and we want to simulate it with an $\mathsf{NL}$ machine $M'$. The first that $M$ does is to guess the state $\sigma$ of $M'$ after it finishes reading the witness tape for the first time. It then simulates two copies of $M$, one starting at $M$'s initial state, and the other starting at $\sigma$. After going through the witness tape, it verifies that the first copy has reached $\sigma$, and that the second copy has reached an accepting state.

In this way you can show that $\mathsf{NL}\[O(1)\] = \mathsf{NL}$.

---
Tags: complexity-theory, turing-machines, nondeterminism
---


# Question
Title: $UP^{\ O}\neq P^{\ O}$ for some oracle $O$
The definition of the class $UP$ is here. It is of course easy to see that $P\subseteq UP$.

I have a problem of proving that there is an oracle $O$ and a language $L$ such that $L\in UP^{\ O}$ but $L\notin P^{\ O}$, i.e. $UP^{\ O}\neq P^{\ O}$.

I find a lot of struggle of finding an explicit $O$, and more struggle to proof it without finding one. I don't have access to the paper which is in the complexity zoo in the link above, can you please explain why it is true or provide me with access to the paper?

# Answer
Here is the construction from Rackoff's paper *Relativized questions involving probabilistic automata*. We construct the oracle $O$ using diagonalization, in steps. At step $t$ we will construct the initial segment $O\_t$ of $O$ which consists of $O \cap \bigcup\_{i=0}^{n\_t} \Sigma^i$ for some $n\_t$, where $n\_0 \< n\_1 \< \cdots$ is an increasing sequence. We will maintain the following invariant: $O\_t$ contains at most one string of each length. This will guarantee that the following language is in $UP^O$: $$ L = \\{ x : \exists y \in O \cap \Sigma^{|x|} \\}. $$

The construction will use an enumeration $M\_i$ of all polynomial time Turing machines, with the guarantee that the running time of $M\_i$ is at most $in^i$. It is a standard fact that such an enumeration exists.

Let $O\_{t-1}$ be the initial segment constructed at step $t-1$ (or $\emptyset$ in the first step). We now show how to construct $O\_t$. Choose the smallest $a\_t \> n\_{t-1}$ such that $ta\_t^t \< 2^{a\_t}$. Run $M\_t$ on the string $0^{a\_t}$, answering NO to all queries outside of $O\_{t-1}$. Let $b\_t$ be the length of the largest string queried, and let $n\_t = \max(a\_t,b\_t)$. If $M\_t$ accepts, set $O\_t = O\_{t-1}$, guaranteeing that $0^{a\_t} \notin L$. Otherwise, set $O\_t = O\_{t-1} \cup \\{x\\}$, where $x$ is some string of length $a\_t$ which $M\_t$ didn't query (such a string must exist since $ta\_t^t \< 2^{a\_t}$), guaranteeing that $0^{a\_t} \in L$. You can check that $O\_t$ satisfies the invariant stated above.

By construction, $L \in UP^O$ (the UP machine guesses $y$ of the same length as the input and verifies that $y \in O$), while $L \notin P^O$ since $M\_t$ answers incorrectly on the string $0^{a\_t}$, by construction.

Beigel, in the paper On the relativized power of additional accepting paths, shows that $P^O \neq UP^O$ for a random oracle, crediting this result to Rudich's PhD thesis. In fact he proves even stronger separations, showing that allowing more accepting paths increases the (relativized) power of polytime machines.
> 1 votes

---
Tags: complexity-theory, polynomial-time, oracle-machines
---


# Question
Title: What is the set of all maximal 3CNF formulas?
**Definition:** A **maximal** 3CNF formula is satisfiable 3CNF formula, but if you conjuct it with another any **new different** 3 disjuctive literals clause, then the formula becomes **un**satisfiable.

Please do**n't** confuse with the definition of **minimal** 3CNF formula from my previous question What is the set of all minimal 3CNF formulas

This is **not** the same thing!

But my question about **minimal** 3CNF formulas in the above link is same for **maximal** 3CNF formulas here, i.e.

For some natural number **n**, where **n** is the number of atomic variables, what is the set of all **maximal** 3CNF formulas? Is it finite? If it is then what is it's cardinality, i.e. how many **different maximal** 3CNF formulas is possible?

**Note** that for k-cnf formula n≥k, so in 3CNF formula n≥3.

# Answer
> 2 votes
There are $2^n$ maximal 3CNFs; here I am assuming that each 3-clause contains *at most* three different literals (corresponding to different variables), and that the clauses are different and unordered (both within each clause, and across the formula). Indeed, I show below that if $\varphi$ is a maximal 3CNF then there is a truth assignment $\alpha$ such that $\varphi$ consists of all 3-clauses consistent with $\varphi$, and conversely, each such formula is maximal.

Indeed, let $\varphi$ be a maximal 3CNF. Suppose first that $\varphi$ has at least two different truth assignments $\alpha,\beta$. There is a variable $x\_i$ whose truth value is different in $\alpha$ and $\beta$, say $x\_i$ is true in $\alpha$ but false in $\beta$. In particular, the clause $x\_i$ is not in $\varphi$ (since $\beta$ doesn't satisfy it), and if we add it then the formula remains satisfiable. We conclude that $\varphi$ has a unique satisfying assignment $\alpha$. If $\varphi$ doesn't contain all 3-clauses consistent with $\alpha$ then we can add the missing ones while keeping the formula satisfiable. Thus $\varphi$ must consist of all 3-clauses consistent with $\alpha$.

Conversely, suppose that $\varphi$ consists of all 3-clauses consistent with $\alpha$. Since $\varphi$ contains all clauses of width 1, $\alpha$ is the unique satisfying assignment. By definition, any other 3-clause is inconsistent with $\alpha$, and so $\varphi$ is maximal.

You might be interested in E3CNFs, in which each 3-clause contain *exactly* three literals, each corresponding to a different variables. These can probably be analyzed using the same approach - if you're interested, you're welcome to work it through.

---
Tags: logic, first-order-logic, propositional-logic
---


# Question
Title: What are some of the practical applications of functions that extract the exponent and mantissa of a floating point number?
I'm talking about functions such as Python's math.frexp() :

> **math.frexp(x)**
>
> Return the mantissa and exponent of x as the pair (m, e). m is a float and e is an integer such that x == m * 2\**e exactly. If x is zero, returns (0.0, 0), otherwise 0.5 \<= abs(m) \< 1. This is used to “pick apart” the internal representation of a float in a portable way.
>
> https://docs.python.org/3.4/library/math.html

And:

> In some applications it is useful it obtain the mantissa and exponent of floating point numbers. http://www.technicalc.org/tiplist/en/files/pdf/tips/tip6\_58.pdf

That said, what would be the usefulness of functions such as math.frexp() in real-world applications? What can I use it for?

# Answer
They are among other things very useful for calculating logarithms, or square roots and cubic roots.

For example: log x = log ($2^e * m$) = e * log 2 + log m. With 0.5 ≤ m ≤ 1, you can approximate log m using a polynomial, which wouldn't work for x which can be in the complete range of floating point numbers.

$x^{1/3}$ = $(2^e * m)^{1/3}$. Let e = 3k, 3k+1, or 3k+2, then this equals $2^k * m^{1/3}$ for 0.5 ≤ m ≤ 4. You can either use approximation by a polynomial for m, or you use Newton iteration which will be much faster for m in the small interval.
> 3 votes

---
Tags: arithmetic, floating-point, mathematical-programming, applications
---


# Question
Title: Efficient algorithm for edit distance for short sequences
I have an application that needs to compute billions of levenshtein distance between pairs of strings. The strings are short (70 in length) DNA sequences, consisting only of 4 characters. Also it can be assumed that one of the strings is fixed, i.e., we are comparing one fixed string to a billion other strings.

I know that the dynamic programming implementation of the levenshtein distance is $\mathcal{O}(m n)$, would like to know if there are any room for improvement. I found these two algorithms:

* $\mathcal{O}(n + d^2)$ algorithm, in which $d$ is the edit distance by Berghel et al. However I can't make the assumption that $d$ is small so it might not give any advantage
* $log(n)^{\mathcal{O}(1/\epsilon)}$ approximation in $n^{1+\epsilon}$ time by Andoni et al. But I have two concerns regarding this:
    + Is this algorithm also fast in practice?
    + Does $log(n)^{\mathcal{O}(1/\epsilon)}$ mean the computed edit distance in worst case is $log(n)^{\mathcal{O}(1/\epsilon)}$ times the actual one? In that case it's too much.

Do you know of any other algorithm/idea/approach that might be applicable?

# Answer
> 3 votes
One approach is to build a Levenshtein automaton for the fixed string (see, e.g., here). Given a string $x$ and a distance $D$, you can build a DFA that recognizes all strings that are at distance $\le D$ from $x$. Thus, you can test whether a string is close to $x$ in $O(n)$ time, where $n$ is the length of the string. I'm not sure what the space requirements are to store the DFA (they are linear in $m,n$, but might be exponential in $D$).

Alternatively, you could use an "early-out" algorithm for computing the edit distance. You mentioned that you are only interested in the edit distance if it is less than some threshold $D$. There is an "early-out" algorithm for computing the edit distance whose running time is $O(\max(n,m) \times D)$, which computes the edit distance if it is $\le D$ or else outputs "too big" if it is $\>D$. Basically, you do the standard dynamic programming algorithm for the edit distance, but only compute the elements of the matrix that are $\le D$ away from the diagonal. In your case this might or might not be better than the other alternatives.

# Answer
> -1 votes
If I had to do billions and it was only 4 characters I would represent the characters as
1000
0100
0010
0001
It is then a 35 byte integer

Dot a bit-wise `and` and count the 1's

Not perfect but billions is a lot unless you throw a lot of CPU at it.

---
Tags: strings, edit-distance
---


# Question
Title: What is the complexity to show this theorem?
Given a sum of regular expressions, where each regular expression in the sum is **n-1** concatenations of 0, 1 and (0+1).

There is need to show that the sum of all regular expressions is either equal to or not equal to the regular expression, which is **n-1** concatenations of (0+1).

I want to know what is the complexity to show this theorem?

Actually it is possible to open up all brackets and parentheses, but this increases number of regular expressions in the sum to some exponential number.

Proof in this way is very long and requires a lot of large papers.

I want to know if there is more easier, efficient and faster way to do this proof?

# Answer
> 2 votes
This is just SAT in disguise. Given a clause, you can encode the set of assignments falsifying the clause as a sum of the type you indicated. The formula is unsatisfiable iff every assignment falsifies some clause, that is, iff the sum of the regular expressions is $(0+1)^{n-1}$.

---
Tags: complexity-theory, time-complexity, runtime-analysis, space-complexity, space-analysis
---


# Question
Title: What is the time complexity of this function?
This is an example in my lecture notes. Is this function with time complexity $O(n \log n)$?. Because the worst case is the funtion goes into `else` branch, and 2 nested loops with time complexity of $\log n$ and $n$, so it is $O(n \log n)$. Am I right?

```
int j = 3;
int k = j * n / 345;
if(k > 100){
    System.out.println("k: " + k);
}else{
    for(int i=1; i<n; i*=2){
        for(int j=0; j<i; j++){
            k++;
        }
    }
}

```

# Answer
Time complexity of mentioned algorithm is $O(1)$, because for $K\>100$ you have a constant operation (println), and you know: $j=3,k = 3 \cdot n / 345 \implies 100 = 3\cdot n / 345 \implies n=11500$, means for $n\ge 11500$ your algorithm has a constant running time (also other part is constant, because just for $n\<11500$ will be called).

For being more clear take a look at this question.
> 5 votes

# Answer
EDIT: As pointed out by Saeed Amiri, this is actually $O(1)$, since for asymptotically large $n$, the `else` branch isn't actually taken; the `if` part is executed, which is trivially constant time. The rest of this answer, which I leave for reference, would be correct if, for instance, the condition were `k < 100`. Sorry for the mix-up.

The time-complexity is essentially going to be on the order of the number of times that $k$ is incremented in the nested `for` loop. There is some extra stuff going on, but if you think about it, that's just playing with constant factors. How many times will $k$ be incremented?

When $i = 1$, $k$ is incremented once. When $i = 2$, $k$ is incremented two additional times. When $i = x$, $k$ is incremented $x$ additional times. Let us now assume that $n = 2^m + 1$. Then the last iteration of the inner loop will cause `k` to be incremented $2^m$ times.

$k$ is incremented a grand total of $1 + 2 + ... + 2^m$ times, or $2^{(m+1)} - 1$ times. Recall that \`$n = 2^m + 1$. So $n - 1 = 2^m$, and we have that $k$ is incremented $2(n - 1) - 1$ times in total.

$k$ is incremented a number of times that is linear in $n$; ergo, this is all $O(n)$.
> 4 votes

# Answer
Although the comments about the if/else branches are all correct, I would say the answer is O(log n). The reason is that

```
System.out.println("k: " + k);

```

involves conversion of an integer to string output, and this will be O(log n) in the general case (just to print out each digit, even if a lookup table were used).

Not sure if that was a trick part of the question or not...
> 1 votes

# Answer
Let's see:

`int j = 3;` takes constant time O(1).

`int k = j * n / 345` takes some logarithm time function of **j** and **n** variables

`if (k > 100)` takes constant time O(1).

`System.out.println("k: " + k);` takes logarithm time function of **k**

`for (int i=1; i<n; i*=2)` takes logarithm time function of **n**, Θ(log(n)) to be exact, because if **t** is the number of iterations of this for loop then the value of **i** can be expressed as: **i=2t-1**, if **t=1** in the first iteration, so the loop continues as long as **2t-1 \< n**, where **n** is not changing.

In calculus, if **2t-1 \< n** then **t-1 \< log2(n)**

And if **t-1 \< log2(n)** then **t \< log2(n)+1**

And if in each iteration, **t** is incremented by 1, we can see that this for loop really takes Θ(log(n)) time, **if the running time complexity of the code inside this for loop is constant, i.e. O(1) of course!**

Inside this for loop, there is another for loop:

`for (int j=0; j<i; j++)
 k++;`

Let's analysis this:

`k++;` takes constant time, i.e. O(1) time.

So it's interesting to analysis running time complexity of the inner for loop then.

Let's see:

According to code of this inner for loop, it appears that there are **i** iterations in this inner for loop, so it's running time is **Θ(i)**, not just **O(i)**, because it does**n't** break in the middle, but remember that **i \< n**, because of the outer for loop, so even though in the beginning it takes 1 iteration when **i=1**, 2 iterations when **i=2**, 4 iterations when **i=4**, 8 iterations when **i=8**... and etc, because i doubles itself in the end of the outer for loop in the line **i\*=2**, so in total the execution is 1+2+4+8+... iterations **but** until **i≥n** so the maximum possible number of iterations in this inner for loop is when **i=n-1** in terms of worst case, so if in the last execution of the inner for loop, it ran **n-1** iterations, so before that it ran **(n-1)/2** iterations and before that it ran **(n-1)/4** iterations and before that it ran **(n-1)/8** iterations... so in total the execution was:

n-1+(n-1)/2+(n-1)/4+(n-1)/8... = (n-1)(1 + 1/2 + 1/4 + 1/8...) = (n-1)(2) = 2n-2 = Θ(n)

Recall that **1 + 1/2 + 1/4 + 1/8...=2** is well known sum of geometric sequence.

Recall that the outer for loop takes Θ(log(n))

And the inner for loop takes Θ(n).

And the running time complexity of **for loop inside for loop** is the running time complexity of the outer for loop multiplied by the running time complexity of the inner for loop, thus it takes Θ(nlogn) running time.

So in summary, the running time of this function is **Θ(nlogn)**.

Hope that this answers well your question and teaches you well how to analysis running time complexity of algorithms and functions.
> 0 votes

---
Tags: complexity-theory, time-complexity, algorithm-analysis, runtime-analysis
---


# Question
Title: Is this possible to solve SAT in polynomial time by reducing it to the problem of solving system of nonlinear equations?
Every conjunctive normal form (CNF) formula can be converted to nonlinear system of equations, where each clause becomes an equation in the system and:

If A and B are logical/boolean variables and defined as A∈{T,F} ∧ B∈{T,F} or (A,B)∈{T,F}2 where

{T,F}2={T,F}⨯{T,F} = {(T,T),(T,F),(F,T),(FF)}

Then:

A=x, ¬A=1-x, B=y, ¬B=1-y and A∨B=x+y-x•y

That's how the **left** side of each nonlinear equation in the system is computed.

The **right** side of each nonlinear equation in the system is **obviously** the constant natural number 1.

Finding a solution to this nonlinear system of equations is finding satisfying assignment to the given CNF formula.

That way SAT is reduced to the problem of solving nonlinear system of equations in polynomial time, thus the problem of solving nonlinear system of equations is NP-Hard, because of the fact that SAT is NP-Complete.

But I think that there already exist algorithms that solve nonlinear system of equations in polynomial time and space complexity, if so then also SAT can be solved in polynomial time and space complexity too.

Do I wrong in everything I said?

It sounds too good to be true and

> If it's too good to be true, something's wrong.

quote from John Allison.

# Answer
> 3 votes
It is not currently known whether or not a polynomial algorithm exists to solve these systems of nonlinear equations because, as the reduction provided shows, if such a thing were to exist, it would show that $NP = P$ which remains yet unknown.

---
Tags: complexity-theory, np-complete, satisfiability, sat-solvers
---


# Question
Title: Clock synchronization in a network with asymmetric delays
Assume a computer has a precise clock which is not initialized. That is, the time on the computer's clock is the real time plus some constant offset. The computer has a network connection and we want to use that connection to determine the constant offset $B$.

The simple method is that the computer sends a query to a time server, noting the local time $B + C\_1$. The time server receives the query at a time $T$ and sends a reply containing $T$ back to the client, which receives it at a time $B + C\_2$. Then $B + C\_1 \le T \le B + C\_2$, i.e. $T - C\_2 \le B \le T - C\_1$.

If the network transmission time and the server processing time are symmetric, then $B = T - \dfrac{C\_1 + C\_2}{2}$. As far as I know, NTP, the time synchronization protocol used in the wild, operates on this assumption.

How can the precision be improved if the delays are not symmetric? Is there a way to measure this asymmetry in a typical Internet infrastructure?

# Answer
**Inability to measure asymmetry**

No, you can't measure the asymmetry. Consider these two communication diagrams, the first with a negative clock offset and equal delays and the second with no clock offset and entirely asymmetric delays (but the same round trip time).

The important thing to notice is that, from the perspective of both the PC and the server, the two interactions are exactly identical. They receive messages at the same time. They send messages at the same time.

You can create more cases by 'grabbing' the PC timeline and 'sliding' it, holding the message send/receive points fixed relative to their respective timelines. The asymmetries you cause are exactly negated by the clock offset. In fact, you can even make messages go BACKWARDS IN TIME one way (as long as the round trip time is still the same) and the server/client STILL can't tell!

Therefore it is impossible to measure latency asymmetries. In the worst case, where you have no information other than that one way latencies are positive and sum to the round trip time, the accuracy of clock synchronization is limited to the round trip time.

**Can intermediate infrastructure help?**

Whether or not the intermediate infrastructure can help will be heavily dependent upon your theoretical model of the situation.

If the asymmetry is constant and the intermediate infrastructure is the routers on the communication path between you and the server, then no. Even if each router synchronized their clock with the adjacent router, the errors would compound in the same way as if you had synchronized with the server via communication across the routers.

In the real world you can rely on delays being somewhat symmetric for architectural reasons, repeated synchronizations to reduce asymmetry due to queuing delays (etc), and multiple communication paths to reduce other sorts of asymmetry.

If you put your model's assumptions somewhere in between (because it's interesting to explore model space, of course) I expect the result should also be somewhere in between.
> 12 votes

# Answer
Consider a network of time servers known to be synchronous, $\theta = \\{A, B, C\\}$, and a client machine $P$.

Let $T\_{XY}$ be the one way time of flight from machine $X$ to machine $Y$, with the possibility that $T\_{XY}\neq T\_{YX}$.

Let $\Delta\_{XY} = |T\_{XY} - T\_{YX}|$ be the measure of the asymmetry between machine $X$ and $Y$.

Now, consider that the asymmetry between two synchronous machines can be measured by having the synchronous machines agree to send a one way message to each other at the same time. The difference in the arrival times is $\Delta$ between those machines, i.e.:

$\Delta\_{AB} = |T\_{AB} - T\_{BA}|$

$\Delta\_{BC} = |T\_{BC} - T\_{CB}|$

$\Delta\_{CA} = |T\_{CA} - T\_{AC}|$

can be measured.

Now consider the time of flight of circuits:

$P \rightarrow A \rightarrow B \rightarrow P$, denoted by $C\_{AB}$,

$P \rightarrow B \rightarrow A \rightarrow P$, denoted by $C\_{BA}$.

$C\_{AB} = T\_{PA} + T\_{AB} + T\_{BP}$

$C\_{BA} = T\_{PB} + T\_{BA} + T\_{AP}$

Consider the client machine $P$ to initiate both of these circuits simultaneously, and measures the difference in arrival times, $x$:

$x = C\_{AB} - C\_{BA} = \Delta\_{PA} + \Delta\_{AB} + \Delta\_{BP}$

Both $x$ and $\Delta\_{AB}$ are known by previously mentioned measurements, so moving the unknowns to the left hand side:

$x - \Delta\_{AB} = \Delta\_{PA} + \Delta\_{BP}$

Similarly, for $\\{C\_{AC}, C\_{CA}\\}$ and $\\{C\_{BC}, C\_{CB}\\}$ it can be shown that:

$y - \Delta\_{BC} = \Delta\_{PB} + \Delta\_{CP}$

$z - \Delta\_{CA} = \Delta\_{PC} + \Delta\_{AP}$

Inspecting carefully, we note that $\Delta\_{XY} \equiv \Delta\_{YX}$. The left sides contain values known from measurements, the right sides contain 3 unknowns in 3 equations.

Solving simultaneously,

$\Delta\_{AP} = \frac{r + s - t}{2}$

$\Delta\_{BP} = \frac{r - s + t}{2}$

$\Delta\_{CP} = \frac{t - r + s}{2}$

where,

$r = x - \Delta\_{AB}$

$s = y - \Delta\_{BC}$

$t = z - \Delta\_{CA}$
> 2 votes

# Answer
If you only control the endpoints. You can't. See Craig's answer.

Even if you add more machines and a more complex set of computers, like in Bingo's answer, you can reduce to just to machines making the synchronized ones have instantaneous access to the others (delay $T\_{XY}$ = 0).

Notice that if you do $T\_{AB} = T\_{BC} = T\_{CA} = 0$, you get $\Delta\_{AP} = \Delta\_{BP} = \Delta\_{CP} = 0$.

So what's wrong? $x = C\_{AB}-C\_{BA} = \Delta\_{PA}+\Delta\_{AB}+\Delta\_{BP}$

$\Delta\_{PA} = |T\_{PA} - T\_{AP}|$, not $\Delta\_{PA} = T\_{PA} - T\_{AP}$

And if you use the second, then you can not use the assumption $\Delta\_{XY} \equiv \Delta\_{YX}$ (and if you don't use this, your final equations cancel each other).

So, what can you do? Send a really good clock through mail. ;)

Or, if you have control over all nodes between them, you can check the time to process each packet and calculate the delay between each consecutive pair, that should be symmetrical, if they use the same physical medium both ways.

You may need to account for general relativity, and remember that simultaneity doesn't exist.
> 0 votes

# Answer
NTP actually uses 4 time measurements $t\_0, t\_1, t\_2, t\_3$ to compute the "offset". they are the "time points" in the round trip of the packet from client to server back to client but can be regarded as time offsets. its assumed that the time offset can be off between client and server but that both can count local elapsed time offsets accurately.

the client after receiving the return packet has all 4 values and computes the actual offset. once the relative offset is calculated between client and server, the "absolute time" offset can be synchronized ie the client can accurately estimate the servers exact offset measured wrt its local time offset, ie the "delta".

$t\_0$ = time \[offset\] sent at client
$t\_1$ = time \[offset\] recd at server
$t\_2$ = time \[offset\] sent at server
$t\_3$ = time \[offset\] recd at client

the actual formula is $\theta = {(t\_1 - t\_0) + (t\_2 - t\_3) \over 2}$

note this formula can handle the case where the time from client to server $t\_1 - t\_0$ is not the same as from server to client $t\_3 - t\_2$ (either shorter or longer).

on networks, delay time is due to two major factors, mainly latency and bandwidth.

* latency is the brief delay in routers on sending new \[small\] packets and is roughly a different constant at each router. it can be measured with the traceroute utility.
* bandwidth is the rate at which large amts of data can be sent eg "upload vs download time" and can also be measured by remote "bandwidth measuring" web sites.

in many modern home/business internet connections the upload rate is much smaller than download rates & this would probably affect the $t\_1 - t\_0$ vs $t\_3 - t\_2$ difference whereas latency may be small or somewhat similar between client-to-server and server-to-client.

a basic algorithm to improve accuracy of calculating the offset used in NTP (and can correct for some degree of random network latency) is to repeat the process multiple times and use the "apex of the wedge scattergram". this can be seen on the "clock filter algorithm" on slide 10 of this PPT on NTP by David Mills. see also clock filter algorithm by Mills. (note it can still be employed between a single server and client although the general code is written to allow multiple servers.) this is part of the "mitigation algorithms" described in NTP architecture & algorithms.
> -1 votes

# Answer
If only we could *send packets back in time*

$$B = T\_f + \frac{T\_b - T\_f}{2} - \frac{C\_1 + C\_2}{2}$$

Assumptions:

$(B+C\_2) - T\_b = T\_f - (B+C\_1)$

$T\_f - (B + C\_2) = (B + C\_1) - T\_b$
> -2 votes

# Answer
Here is an idea that sounds absolutely convincing to me and might therefore be absolutely wrong in a dumb way.

Consider the following scenario. We have two nodes $N\_1$ and $N\_2$ with clocks $C\_1$ and $C\_2$, respectively. For sake of simplicity, let us assume that the clocks run with the same speed; we denote their difference by $\delta = C\_1 - C\_2$ which is constant for our purposes. Let us furthermore assume that transmission delays $d\_{1 \to 2}$ and $d\_{2 \to 1}$ are constant¹.

Have $N\_1$ send a message timestamped with $T\_1^m$ to $N\_2$ and let $T\_2^r$ the current time on $C\_2$ upon receiving it (do the same for the other direction). In addition, measure round trip time (on either node) $D$ by sending a message back and forth. Now set up this equation system:

$\qquad\begin{align\*} T\_2^r - T\_1^m &= d\_{1 \to 2} + \delta \\ T\_1^r - T\_2^m &= d\_{2 \to 1} - \delta \\ D &= d\_{1 \to 2} + d\_{2 \to 1} \end{align\*}$

As this system consists of three equations, has three unknowns and we know there is a solution, it can be solved. Of course the nodes have to exchange their measurements so that they can both compute the same value for $\delta$ (if necessary).

1\] I think the assumptions are natural and necessary. They can be justified with the hope that the respective quantities do not change *too* much for the duration of our synchronisation attempt.
> -4 votes

---
Tags: clocks, distributed-systems, computer-networks
---


title: An elementary oracle query

text:
# Question
Title: An elementary oracle query
Why is $P^{NP}\not\subseteq NP$ possible? After all we have a $P$ machine which uses an $NP$ oracle and since $P\subseteq NP$ why cannot the $P$ machine with $NP$ oracle just be replaced by an $NP$ machine?

Similarly why is not the case $P^{coNP}\subseteq coNP$?

# Answer
> 7 votes
A $\mathsf{P^{NP}}$ machine can solve $\mathsf{coNP}$ problems: it can query an $\mathsf{NP}$ oracle, and then return the opposite answer. This is not something that you can obviously simulate with an $\mathsf{NP}$ machine.

More concretely, you can construct $\mathsf{P^{NP}}$ machine which gets a formula as input, accepts if the formula is unsatisfiable, and rejects if the formula is satisfiable. How would you implement this as an $\mathsf{NP}$ machine? We only know how to construct witnesses for *satisfiability* (namely: a truth assignment), but not for *unsatisfiability*.

---
Tags: complexity-theory
---


# Question
Title: monotone min 3-sat polynomial algorithm?
I know that 3SAT is npc but i wonder why my little algorithm won't solve this problem:

given positive 3SAT - meaning: each of the m clauses is a disjunction of 3 literals over the variables x1,…,xnx1,…,xn (nn variables) and each literal is a positive appearance of a variable (no xi xi).

for example: (x1∨x3∨x7)∧(x5∨x4∨x2)(x1∨x3∨x7)∧(x5∨x4∨x2)

In other words: The problem is probably called MIN 3SAT, which every literal is positive but you must find minimum integer k such that there exists a truthful assignment of the variables which sets k variables to TRUE.

What is wrong with this "greedy" algorithm?:

run through all left clauses and find the variable that appears in most of them (can be implemented by counters array..). take this variable, give him truth assignment, remove all clauses which he appeared in, zero the counters array and do again the previous step. stop when no clauses left. it looks like this algo runs in O(m2n)O(m2n) time.

why isn't it an optimal algorithm?

UPDATE: Can someone give me an example to why the greedy algorithm won't give the optimal solution? I can't figure why the greedy approch is not good..

# Answer
> 1 votes
The problem MIN-3SAT is usually know as "minimum vertex cover for 3-uniform hypergraphs". Any reasonable algorithm that you will suggest will give a 3-approximation (or worse), and indeed, it is conjectured (and follows from the unique games conjecture) that no polynomial time algorithm can improve on this approximation ratio.

This means that if you try hard enough, it is extremely likely that you will find an instance in which your greedy approach gives a solution which is roughly 3 times as worse as the optimal solution. I'll let you find it on your own.

---
Tags: satisfiability, 3-sat
---


# Question
Title: Generating values from a probability density function
If I have a probability density function, some f(x) which is \>= 0 everywhere and integrates to 1, is there a method to generate random numbers using that PDF?

I know there is the box-muller transform to convert uniform random numbers to gaussian, but is there anything for the general case, or at least a more general case of PDFs?

# Answer
You can integrate the PDF to a CDF F(x), then uniformly generate a random number x between 0 and 1 and choose a y such that F(y)=x as your sample. This is more or less difficult, depending on your PDF. Some PDFs have analytical solutions, others need numerical methods. For some distribution Rejection sampling works well, some distributions can be sampled from using a suitably constructed Markov chain.

See also this set of slides for more details.
> 5 votes

---
Tags: random-number-generator, monte-carlo
---


# Question
Title: Repeated point in polygon: preprocessing complexity given logarithmic query time?
I am interested in the repeated point in polygon problem, where one is given a polygon in a preprocessing phase and in the online phase, one is asked whether a point is in that polygon. The polygon is not necessarily simple. I am interested in the case where a polygon has many edges.

Let $n$ be the number of vertices of the polygon. I have an algorithm that performs the online phase in $O(\log n)$ time but the preprocessing phase requires $O(n^3)$ time and space in general, $O(n^2)$ time and space for simple polygons, and $O(n)$ time for star-shaped polygons.

Can we do better? Specifically, does anyone know lower or upper bounds, constructive or not, for the preprocessing phase given $O(\log n)$ query time?

I'm working in two dimensions, and the points have floating point coordinates (i.e., not integer coordinates).

---

My algorithm is similar to a standard algorithm and has similar performance characteristics. I discovered it independently so it differs in some immaterial ways but it's not original. It works as follows:

Preprocessing:

1. Translate polygon into first quadrant. (This is to simplify later calculations but isn't strictly necessary.)
2. Create a ray passing from the origin through every endpoint and intersection point of an edge. In each resulting cone no edge crosses another.
3. For each cone, sort the edges crossing that cone by their distance from the origin.

Online:

1. Apply the same translation to the query point as was applied to the polygon.
2. Using binary search, find the cone containing the point, or if none, return false.
3. Using binary search, find the number of edges in the point's cone for which the point and origin are on the same side. Return whether this number is odd.

# Answer
> 0 votes
I am posting this answer because Noinia's answer does not account for how the input size changes when reducing Repeated Point In Polygon to Planar Point Location.

Sarnak's and Tarjan's paper Planar Point Location Using Persistent Search Trees solves a related problem, the Planar Point Location problem, with $O(n)$ space, $O(n \log n)$ preprocessing time, and $O(\log n)$ query time. We can reduce Repeated Point In Polygon to Planar Point Location by first computing all edge intersections of the input polygon and passing all the vertices and edge intersections to the Planar Point Location algorithm. In the worst case this reduction grows the input size from $\theta(n)$ to $\theta(n^2)$ and thus Sarnak's and Tarjan's algorithm yields $O(n^2)$ space, $O(n^2 \log n)$ preprocessing time, and $O(\log n)$ query time.

The space and preprocessing time of the above algorithm are likely not optimal because they don't take advantage of the special structure of the intersection points with respect to the vertices.

# Answer
> 1 votes
Your problem is a special case of planar point location. The algorithm/data structure you found by Snarak and Tarjan can answer point location (and thus point in polygon) queries in $O(\log n)$ time using $O(n \log n)$ preprocessing and $O(n)$ space. That is optimal. There are two other data structures that achieve this: a data structure by Kirkpatrick and a randomized incremental approach. The randomized incremental approach can be improved to $O(n \log^\* n)$ expected preprocessing time in case of a simple polygon, and is fairly simple besides.

# Answer
> -1 votes
I have an algorithm O(log(n)) for this purpose that uses a kind of special data structure that sorts the sides of the polygon when is being created to avoid preprocessing. This sort procedure is executed in O(n\*log(n)).

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


# Question
Title: No polynomial time approximation algorithm better than $n^{1 − ε}$
What does this sentence mean?

For all $ε \> 0$, it is NP-hard to approximate MAX CLIQUE to within $n^{1 − ε}$.

Is the fact that complexity of approximation depends on $\epsilon$ hidden in the statement? I mean, if not, I guess we can make $\epsilon$ arbitrarily small, (like $\epsilon = 0.9999$), and get a very good approximation. So, I guess as we make $\epsilon$ smaller, the complexity should go remarkably higher. Right? In which order?

# Answer
> 2 votes
The sentence means that for every $\epsilon \> 0$ there is a polytime reduction $f\_\epsilon$ that takes an instance $\phi$ of SAT into a pair $(G,k)$ such that:

* If $\phi$ is not satisfiable then $G$ has no $k$-clique.
* If $\phi$ is satisfiable then $G$ has an $n^{1-\epsilon} k$-clique.

An $n^{1-\epsilon}$-approximation algorithm for MAX-CLIQUE can be used to distinguish the two cases.

The running time of $f\_\epsilon$ indeed depends on $\epsilon$, which probably appears in the *exponent*, that is, $f\_\epsilon$ runs in time $n^{g(\epsilon)}$, where $g(\epsilon)$ tends to $\infty$ as $\epsilon \to 0$.

# Answer
> 1 votes
Let eps = 0.000001. It is NP-complete to find a clique within $N^{0.999999}$ of the maximum clique. But for N = 165,000, $N - N^{0.999999}$ \< 2, so finding a clique of size 1 solves the problem, and this is quite trivial! So for tiny eps, the complexity is quite likely exponential, but even for quite large N, a solution is quite trivial.

Let eps = 0.999999. It is NP-complete to find a clique within $N^{0.000001}$ of the maximum clique. For $N ≤ 10^{300,000}$ this is equivalent to finding the maximum clique or a clique with one element less. Which is a little bit easier than finding the maximum clique, but not much. $N ≤ 10^{300,000}$ is obviously a lot larger than any problem that could ever be posed in this universe.

---
Tags: complexity-theory, np-complete, np-hard, approximation
---


# Question
Title: How do solve assignment of one interval to another?
Is there an efficient algorithm for the following problem?

**Input:** Set of holes and pegs. Each hole/peg is an interval $\[\ell,u\]$ with integer endpoints.

**Question:** Can all the holes be filled using the pegs given, satisfying the following conditions?

1. Each peg is assigned to at most one hole.
2. No hole is assigned more than one peg.
3. If peg $p$ is assigned to hole $h$, then the interval $p$ must be contained in the interval $h$.

Here's a picture to help clarify:

**My algorithm:** For each hole, check if any peg can be assigned to this hole.

**Issues:** Unfortunately, this doesn't work. See Scenario 3 in the picture above: my algorithm assigns the same peg ($\[1,2\]$) to multiple holes ($\[1,2\]$ and $\[1,3\]$), which is not legal.

**My second attempt:** I tried to construct an algorithm that marks a peg as unavailable it is used.

1. Let available\_pegs = all input pegs
2. For each hole, check if any peg from available\_pegs can be assigned to this hole.
3. If a peg is found, remove it from available\_pegs and assign it to that hole.

**Issues:** Unfortunately, this doesn't work either. It can fail in Scenario 2: if I assigned peg $\[1,2\]$ to hole $\[1,3\]$, peg $\[1,2\]$ will be marked unavailable and now there is now way to fill the hole $\[1,2\]$. Thus in this example the algorithm would say that there are not enough pegs to assign to all the holes, which is wrong.

# Answer
> 1 votes
This is an instance of bipartite matching (i.e., the assignment problem with no costs). It can be solved by standard methods, such as network flow algorithms (e.g., Ford-Fulkerson), the Hopcroft-Karp algorithm, or using linear programming. See also https://cs.stackexchange.com/a/61264/755.

In particular, you can build a bipartite graph, with one "left vertex" per peg, and one "right vertex" per hole, and an edge from peg $p$ to hole $h$ if the interval $p$ is contained in the interval $h$. Compute the maximum cardinality matching for this bipartite graph. If this matching covers every hole, then the answer to your problem is "yes", otherwise the answer is "no".

---
Tags: algorithms, decision-problem, assignment-problem
---


# Question
Title: Can nested structures be encoded more "readably" with a single delimiter?
Imagine you have two systems of delimiting. One with paired delimiters, `[` and `]`:

```
 [abc]

```

Then another system which uses a single interstitial delimiter, `/`:

```
 a/b/c

```

It's easy to see how to encode structure in the first case, as they nest cleanly:

```
[ab[cd[e]f]]

```

But let's say you are looking to encode arbitrary nested structures in the second scheme, using only some number of interstitial delimiters. Whatever the encoding winds up being, `a/////b//c////d///e///f` would be an example of "following the rules", while `//a//b/c///d///e///f///` would not.

So you're basically able to put a unary-encoded integer from 0..∞ (let's say 0 is `/`, 1 is `//`) between your elements.

It's obviously *possible* to encode, though the results won't necessarily be pretty or visually intuitive. One way would be to consider you have two factors to record at each step.

* Whether a nesting level is being entered or not for the ensuing token or if it's going to stay the same. So for `a?b`, we want to know ...`a[b`... or ...`ab`...
* how much of a nesting drop the ensuing token has after it. So for `d?e`, we want to know e.g. ...`d[e]`... or ...`d[e]]`... or ...`d[e]]]`

The first is just a yes or no, and the second is a number which can range from 0 to however many nesting levels you've gotten so far. So multiply the nesting level to drop by 2, add 1 if you're going a level deeper in and leave it alone otherwise.

```
[ab[cd[e]f]] => a 0 b 1 c 0 d 3 e 4 f => a/b//c/d///e////f

```

That's pretty mechanical, but if I've got it right, I think it verifies it can be done.

**But here's my question**: Is there a known encoding for this kind of problem that would more intuitively convey the structure to a human reader, perhaps at the cost of making longer strings? Let's say a system that would decay such that simple cases like `[ab[cd]e]` could look more like `a/b//c///d//e` or similar, while still being able to encode everything distinctly?

I realize the quality I'm asking for is a bit "nebulous", but perhaps you see what I mean. One thing I don't like about the encoding I chose above is it imposes a left-to-right "leaning" property, when there isn't anything particularly left-like or right-like about the nesting properties being encoded. I wonder how that might be excised by making different choices.

# Answer
> 2 votes
I'll propose a new idea inspired by the everyday slinky. It might be more difficult to perceive exactly what the nesting is, but it might give you a better overall view. We can use a technique similar to the compression and decompression of slinkies:

Take for example the nesting: `[a b c d [e f [g] h i] j k l m]`. We can visualize it in two dimensions based on nest depth like so:

```
a b c d           j k l m

        e f   h i

            g

```

Or alternatively, the inverse:

```
            g

        e f   h i

a b c d           j k l m

```

For either of these we need to determine which should be the compression and which should be the decompression (high vs low nests).

We could try both out:

1. High level is compression, low level is decompression:

`a b c d e f g h i j k l m`
2. Low level is compression, high level is decompression:

`a b c d e f g h i j k l m`

Personally I think option two is more visually representative because the large space between the upper levels represents the lack of deeper nests clearly and the condensed space represents the densely packed nests more easily.

---

Further we could make a formal algorithm. Let's assume input is given as a (value, depth) pair = $(x\_i, d\_i)$. Let $d\_m$ denote the maximum depth of all values in the sequence. For the deepest level, we will pad the elements with 0 spaces, and the highest level we will pad the elements with $2^{d\_m - 1}$ spaces on both sides. The only caveat is that we do not pad the left most value on the left and not the right most value on the right. Take the example: `[[ab[cd[efg]h][ij]k]lm]`.

```
a    b   c  d efg h  i  j   k      l        m

```

The big problem with this is that it does not guarantee a unique encoding. If you do want a unique encoding with a similar approach but maybe not as visually comprehensive, follow the same algorithm only padding the left side and starting at 1, rather than 0 spaces. So `[[ab[cd[efg]hij]k]lm]` becomes:

```
a    b  c  d e f g  h  i  j    k        l        m

```

Although keep in mind this only is unique for a sequences of depths, not necessarily unique nestings. For example `[ab][cd][ef][gh]` would be considered the same as `[abcdefgh]` because they're all at the same depth.

# Answer
> 4 votes
`\n` and `\t` would get the job done as best as I could tell. In memory they're each only a character, but visually they offer a lot more. You then have an encoding scheme of `\n` then $x$ `\t` characters where $x$ is the nesting level. So this:

```
[a b [c d [e] f]]

```

in memory becomes:

```
a\nb\n\tc\n\td\n\t\te\n\tf

```

visually becomes:

```
a
b
    c
    d
        e
    f

```

---

As Evil mentions, you could similarly remove `\n` and `\t` between characters at the same level to achieve something like this:

```
ab
    cd
        e
    f

```

---
Tags: encoding-scheme
---


# Question
Title: Finding $L^*$ when $L=\{a^nb^n | n \geq 1\}$
Let $L=\\{a^nb^n | n \ge 1\\}$, then $L^\star=L^0 \cup L^1 \cup L^2 \cup L^3 \cup \dots = \\{\epsilon\\} \cup \\{a^nb^n\\} \cup L^2 \cup L^3 \cup \cdots$ .

How to find $L^2$ and $L^3$, and is $L^2=\\{a^nb^na^nb^n\\}$? In this video https://youtu.be/rnGpW6RRAcw at 31:51, the professor said that $L^2 = \\{a^{n\_1}b^{n\_1}a^{n\_2}b^{n\_2}\\}$, how did she find this form.

# Answer
> 6 votes
$L^2 = LL = \\{uv | u,v\in L\\}$. In words, $L^2$ is a set of all strings that formed by concatenation of all strings from $L$. For instance, if $u=a^kb^k \in L$ and $v=a^tb^t \in L$ then $uv = a^kb^ka^tb^t$. That's why $L^2 =\\{ a^{n\_1}b^{n\_1}a^{n\_2}b^{n\_2}\\}$ for all $n\_1, n\_2 \geq 1$. Similarly $L^3, L^4,\dots$

Example with a finite set: $L=\\{ab, cd\\}$. Then $L^2 = \\{abab, abcd, cdab, cdcd\\}$.

---
Tags: formal-languages, kleene-star
---


# Question
Title: How to polynomially reduce euclidean tsp to regular tsp?
The normal tsp seems way harder than the euclidean one, is the euclidean tsp np complete? If so is there a simple reduction that gives an answer to the tsp if you have the euclidean tsp algorithm?

# Answer
> 2 votes
There is not known to be a polynomial reduction from Euclidean TSP to regular TSP, since regular TSP is in NPO, but Euclidean TSP seems to involve comparing sums of square-roots.
As far as I'm aware, even PP^(PP^PP) is not known
to be able to make the necessary comparisons.
"..., is the euclidean tsp np complete?"

For the above reason, it's not even known to be in classes that seem to
be significantly bigger than NP.    Furthermore, if it is in NP then  NP = coNP ,
since from the minimum tour length in a node-induced finite grid graph,
one can trivially deduce whether-or-not that graph has a Hamiltonian cycle.
"... is there a simple reduction that gives an answer
to the tsp if you have the euclidean tsp algorithm?"

I agree with Raphael that there's probably no *simple* reduction for that.

---
Tags: complexity-theory, np-complete, reductions, traveling-salesman
---


# Question
Title: Does exist an algorithm to find all equivalence classes of given regular expression without kleene star? If yes then what is it?
Does exist an algorithm to find all equivalence classes of given regular expression without kleene star?

If yes then what is it?

Note that alphabet of the given regular expression is binary, i.e. it contains only 2 symbols exactly.

This is important, because I can easily construct NFA from the given regular expression and then construct the DFA from that NFA, but the result DFA is not minimal and the result DFA's number of states is exponential.

Of course I can run Hopcroft's algorithm to minimize the DFA, but if DFA's number of states is Θ(2n) then Hopcroft's algorithm runs in Θ(2nlog(2n)) = Θ(2nn) = Θ(n2n) and this might take too much time to get the minimal DFA for the given regular expression.

Also my computer has only 4GB of RAM.

If the given regular expression is long and the result NFA is big, then in the middle time conversion from NFA to DFA, there might be out of memory exception thrown and my application won't make it to call Hopcroft's algorithm at all.

For the given regular expression, running the algorithm to find all it's equivalence classes is considered to be much better than constructing NFA from the regular expression, constructing DFA from the NFA and run Hopcroft's algorithm to minimize it, but if and only if the algorithm to find all the equivalence classes won't use too much resources and won't take too much time to finish, then I can use the equivalence classes to efficiently construct the minimal DFA quickly for the given regular expression.

I tried to google the answer for this question, but I didn't find it yet.

Thinking about this algorithm myself is very difficult and hard.

I am very curious to find out what is this algorithm already.

# Answer
No such algorithm is forthcoming. As I mentioned in an answer to one of your other questions, you can encode SAT as a regular expressions that equals $(0+1)^n$ iff the given formula is unsatisfiable. This means that the algorithm you are looking for will be able to solve SAT.
> 3 votes

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


# Question
Title: Can deterministic Turing machine beats/wins (if possible) the "Bombs and Levers" game in polynomial time?
The description of this game is already exists in this link

I am quoting from this link the description of the game to ease the reading of this question:

---

In a game, where there are **m** active bombs, each one with a number above zero, and **n** standing levers, where each can be either pushed forward or pulled backward, and each lever is connected to some bombs with green wires/cables and connected to some bombs with red wires/cables.

If any lever is pushed forward then all bombs that are connected to this lever via green wire/cable are defused and all bombs that are connected to this lever via red wire/cable, their number is decremented by 1.

If any lever is pulled backward then all bombs that are connected to this lever via red wire/cable are defused and all bombs that are connected to this lever via green wire/cable, their number is decremented by 1.

A defused bomb cannot explode, but any active bomb that it's number reaches zero explodes immediately.

Only standing levers can be touched (either pushed forward or pulled backward). You shouldn't touch already touched (either pushed forward or pulled backward) levers.

To win/beat the game the purpose is to defuse all the active bombs without exploding any of them.

---

My greedy algorithm described in this question suppose to run in polynomial time, but it's not proven if it is correct.

Even though proving it's correctness is very difficult for me I am attempting to prove it, but this question is**n't** about this greedy algorithm at all.

Now this question is more general:

Can deterministic Turing machine beats/wins the game described in this question in polynomial time?

If yes, then there should exist polynomial time algorithm that returns all steps that should be followed to beat/win the given instance of this game (if it is possible).

The deterministic Turing machine or the algorithm does**n't** have to be greedy necessarily.

# Answer
Your problem is NP-hard. It is an easy proof In fact, it is NP-complete because we can reduce it to SAT in polynomial time

We reduce 3-SAT to your problem.

We have a lever for each variable and a bomb for each clause, the red cables are connected to clauses/bombs that have positive literals belonging to that variable/lever and the green cables are connected to clauses/bombs that have negative literals belonging to that variable/lever.

Each bomb has the number 3 written on it, meaning that the bomb will explode if it is decremented three times. Whenever we set a lever that is connected to the bomb in the direction that doesn´t deffuse the bomb we decrement the counter in the bomb. This is the same as setting a variable true if the literal in a clause is false or viceversa. If we do this three times that means that the clause has not being satisfied in the original 3-SAT problem and the bomb explodes.

If the instance is satisfiable, you can always choose the right positions for the levers so that no bomb explodes. If there is a variable assignment that satisfies the clauses that means that the bombs can be defused. A defused bomb cannot explode anymore so that we don´t have to worry about a defused bomb anymore.

So, can your problem be solved in polynomial time? We don´t know. People will have to give a solution to the P vs NP problem first, come back in a hundred years and maybe we will have an answer
> 5 votes

---
Tags: algorithms, complexity-theory, turing-machines, search-problem
---