# Question
Title: Do problems that have unary encodings automatically become unary languages?
This problem has confused me a lot, can any of you help me out. Thank you.

# Answer
> 1 votes
A unary language is a subset of $\sigma^\*$ for some letter $\sigma$. If your language is of this form, then it is unary. Otherwise it isn't.

A unary *encoding* is an encoding of some data as a subset of $\sigma^\*$. For example, one possible unary encoding of the natural numbers is $n \mapsto 1^n$. Any language in which instances are unary encoded is a unary language, simply because it is a subset of $\sigma^\*$. For example, the language of all primes encoded in unary is a unary language.

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


# Question
Title: Different ways to generate a big number with some small numbers
Imagine we have a set of numbers $\\{x\_1,x\_2,\dots,x\_m\\}$. We want to compute the different ways to make a big number $P$ by those small numbers.

For example, if $P = 5$ and we have $\\{1,2,3,4,5\\}$ we can make $P$ by:

* 1+1+1+1+1 or
* 2+3 or
* 1+4 or ...

# Answer
This is a well-known problem called the subset sum problem. Essentially we are looking for a subset of the elements that sums up to a target value, P. The problem is NP-hard, meaning it does not admit a polynomial time solution unless P = NP. Here is a link that explains how to solve this problem. There are multiple algorithms for the problem. The recursive one runs at in an exponential time of $O(2^n)$. This problem is mostly associated with a Dynamic Programming solution since its run-time is $O(P\cdot n)$, such a running time is called pseudo polynomial, since it is polynomial in the value of the input instead of its size (which is the log of the value).
> 2 votes

# Answer
You can solve this recursively. Let us assume that $x\_1 \< \cdots \< x\_m$.

* If $P = 0$, return the empty sequence.
* Otherwise, let $\ell$ be the maximal index such that $P \geq x\_\ell$. For $i=1,\ldots,\ell$, run recursively on $P-x\_i,\\{x\_i,\ldots,x\_m\\}$, and prefix $x\_i$ to each such solution.
> 0 votes

---
Tags: search-algorithms
---


# Question
Title: Given a set of sets, find the magnitude (number of elements) of the smallest set containing at least one element from each set
I know that the hitting problem is NP hard, but is it possible to find the magnitude of the smallest set? Also, provide the runtime.

# Answer
> 1 votes
When we say that hitting set is NP-hard, we mean that the following decision problem is NP-hard: given a set system $S$ and an integer $k$, decide whether there is a hitting set for $S$ of size at most $k$.

---
Tags: runtime-analysis
---


title: Guidance for Theory of Computation

text:
# Question
Title: Guidance for Theory of Computation
I have been studying Introduction to Theory of Computation by Micheal Sipser and I just complected it. Now I want to take this a step further what should I do next to increase my skills. I tried looking at some papers from FOCS but they were beyond my understanding. I want to know what should I study next.

# Answer
Theory of Computation, as practiced in the US, focuses mainly on two areas: algorithms and complexity. For algorithms, the standard textbook is Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein, also known by its acronym CLRS. For complexity, there's the advanced textbook Computational Complexity: A Modern Approach, but it might be too much for a beginner.
> 3 votes

# Answer
Let me tell you the road map. First thing you need to learn is discrete mathematics, try some books at your own. Once you are comfortable with discrete mathematics then again go through data strcurures one more time. Once you are ok with data structure. Its time to learn the algorithms from coreman book or from any other book. Now once you have a learned algorithms. It is the time to learn theory of computation. I will suggest you learn theory of computation from ullman book (if you are pure theory person) and from Cohen if don't like theory that much. Note that to learn theory of computation you need

1. Discrete Mathematics
2. Data structure
3. Algorithms

if you have this much then follow this method. Suppose you have *less time* then directly try to read theory of computation book and go back and forth between the topics which you need in order to understand the concepts of theory of computation.

Once more if you really needs to learn the theory of computation, do programming on the exercises on topics like regular expression, turing machines etc.

Now suppose that you have understood the theory of computation then there are two possible directions, you might be interested in compiler design or in complexity theory. For compiler design, there is a famous book by Rajeev motwani et.al. Try to explore both directions.
> 2 votes

# Answer
If you're looking to increase your *development skills*, a more hands-on approach to Automata, Automata and Computability: A Programmer's Perspective is an easy read that comes with a fantastic visualization tool for many topics in the field: DFA, NFA, PDA, TM, etc. It's great for getting your feet wet with developing general automata, IMO.
> 1 votes

---
Tags: reference-request
---


title: Time complexity of recursive function

text:
# Question
Title: Time complexity of recursive function
I am trying to find out how they calculated the time complexity of this small function . I am studying for an exam and found this question and the final answer is given, but I am trying to understand how they got to this answer, I tried solving this problem using Iterative but when I tried to find the number of Iterations of this function I got stuck !

What I tried: let $T(n,k)$ represent the time complexity of $g$. It satisfies the recurrence

$$ T(n,k)=ck+\sum\_{j=1}^i(2^j-1)k + T(n-i,2^ik)$$

when $i$ is the number of iteration in this function, so according to this function the iteration ends when $n\le k$, which means $n-i=2^ik$, but I couldn't extract $i$ from the equation.

Here is the function, whose time and space complexity are stated to be $\Theta(n)$ and $\Theta(\log n)$:

```
   int g(int n, int k) {
      if (n <= k) return 1;

      int result = 0;
      for (int i = k; i > 0; --i, ++result);

      return result + g(n - 1, 2 * k);
    }

    int f2(int n) {
      return g(n, 2);
    }

```

# Answer
Let $k\_i = 2^i$, and define $m$ to be the minimum value such that $n-(m-1) \leq k\_m$. It's not hard to check that the running time of $f\_2$ is $\Theta(k\_1 + \cdots + k\_{m-1})$. Since $k\_i$ grows exponentially, $k\_1 + \cdots + k\_{m-1} = \Theta(k\_m)$, and so the running time of $f\_2$ is $\Theta(k\_m)$.

It remains to find the minimum integer value of $m$ which satisfies $n-m \< k\_m = 2^m$. Clearly this minimum value is at most $\log\_2 n$, implying that $2^m \leq n$. This also means that the critical value of $m$ satisfies $2^m \> n-\log\_2 n = \Omega(n)$. Therefore $k\_m = \Theta(n)$, and so the running time of $f\_2$ is $\Theta(n)$.

Regarding the space complexity, it is proportional to the depth of the recursion, which as we have seen is very close to $\log\_2 n$.
> 0 votes

---
Tags: time-complexity
---


# Question
Title: Why is building a heap $\mathcal O(n)$ and not $\theta(n)$?
From what I see online, all seem to suggest that heapifying takes $\mathcal O (n)$ time, but it seems like it should *always* takes $\theta(n)$ time, even in the best case. Is something wrong with my pseudocode? Is there a more optimized way to do heapification?

```
Heapification(H[1...n])
for i <- floor(n/2) downto 1 do
  k <-i; v <- H[k]
  heap <- False
  while !heap && 2k <= n do
    j <- 2k
    if j <= n
      if H[j] < H[j+1]
        j <- j+1
      if H[j] > v
        H[k] <- H[j]
        k <- j
      else heap <- true
  H[k] <- v

```

# Answer
> 3 votes
Time complexity of algorithms is usually given as big O. There are many reasons for this, including tradition, but when pertinent reason is that in some cases the time complexity depends on the input. For example, a sorting algorithm might run in $O(n\log n)$ in the worst case, but in $O(n)$ in the best case, and so it is not correct to say that it runs in $\Theta(n\log n)$.

In your particular case, your algorithm runs not only in $O(n)$ but also in $\Theta(n)$. Stating that it runs in $O(n)$ doesn't rule out a matching lower bound — it just doesn't tell the complete story.

---
Tags: asymptotics, heaps, big-o-notation
---


# Question
Title: What to consider while proving NP-completeness?
Suppose that a problem $P$ is known to be NP-hard.
The input to the problem is a set of $k$ lines in 2D, a set of $n$ points, and $m \< n$ pairwise distances among the points.
The goal is to place each point on one of $k$ lines, satisfying the given pairwise distances.
**Disclaimer** *This problem might not be an NP-hard problem, but for the sake of simplicity, suppose that it is.*

Since the problem is assumed to be NP-hard, having a polynomial time solution checking algorithm is sufficient to show NP-completeness.

At first sight, it seems trivial
Step 1: check whether the pairwise distances are satisfied \[takes $O(m)$ time\].
Step 2: check for each point whether the point is on a given line. \[takes $O(n\*k)$ time\].

However, if one of the coordinates has exponentially many bits with respect to the input, then is this considered as a exponential-time checking? Or it is still polynomial-time with respect to the length of the solution?

# Answer
> However, if one of the coordinates has exponentially many bits with respect to the input, then is this considered as a exponential-time checking? Or it is still polynomial-time with respect to the length of the solution?

The length of the solution/certificate must be polynomial in the size of the original instance. Therefore, if the certificate/solution can be exponential in the size of the input (due to the numbers needing exponential representation) then you do not have a valid proof of membership in $NP$. The problem might be $\exists \mathbb{R}$-hard.
> 2 votes

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


# Question
Title: If a problem is not in NP, prove that every NP problem can be efficiently reduced to it
I understand that an NP-hard problem is a problem X such that any problem in NP can be reduced to X in polynomial time.

Does there exist a problem that is hard to solve but problems in NP cannot be reduced to it in polynomial time i.e. it does not satisfy the definition of NP-hard but is strictly not in NP? If not, what is the proof that if I can efficiently solve a problem that is strictly not in NP, then I can efficiently solve every problem in NP?

I suppose an analogous question can also be asked for P and NP. If a problem is in NP, then can every problem in P be reduced in polynomial time to it?

Note: The linked question asks the converse problem - does there exist a problem outside NP that cannot be reduced to a problem in NP. Indeed there are, for example the "(Non-)equivalence of two regular expressions" problem. However, from my understanding, every problem in NP can be reduced to this problem in polynomial time. Please correct me if I have misunderstood.

# Answer
> 5 votes
> I suppose an analogous question can also be asked for P and NP. If a problem is in NP, then can every problem in P be reduced in polynomial time to it?

No. There is a stupidly simple argument here: the empty language (i.e., a problem with no yes-instances) is in NP, but no problem in P can be reduced to it.

> Does there exist a problem that is hard to solve but problems in NP cannot be reduced to it in polynomial time i.e. it does not satisfy the definition of NP-hard but is strictly not in NP?

Yes (conditional on some complexity theory assumptions). Let's take some stupidly hard problem $L$. To keep this answer as simple as possible we will assume that $L$ is undecidable but this is not necessary; a language obtained by applying the Time Hierarchy Theorem to the Ackermann function would easily suffice. Assume that instances of $L$ can be padded, i.e., adding extra zeroes at the end does not change whether an instance is a yes- or no-instance. Starting with undecidable language $L'$, $L$ could be obtained by taking every string from $L'$ and appending a $1$ followed by an arbitrary amount of zeroes. Clearly $L$ is still undecidable.

Now consider the subset of $L$ containing only those strings whose length can be expressed as a tower of powers of two (i.e., $1, 2, 2^2, 2^{2^2}, 2^{2^{2^2}}, \ldots$). We split this subset into three languages $L\_0, L\_1, L\_2$, depending on the height of the tower of powers of two. $L\_0$ contains those strings where the tower has a height which is a multiple of $3$, $L\_1$ contains strings whose height is $1$ modulo $3$, $L\_2$ those strings whose height is $2$ modulo $3$.

Neither $L\_0, L\_1$ or $L\_2$ are in $NP$. If they were, we could decide $L$ by padding instances to make their length the appropriate tower of powers of two, and then solving them using the $NP$ algorithm. Obviously the padding can increase the length of the instance exponentially, but if $L$ is sufficiently hard (e.g., undecidable) this does not matter.

Now, to answer the original question, can every problem in $NP$ be reduced in polynomial time to $L\_0, L\_1$ and $L\_2$ (all of which are outside $NP$)? If we take some problem instance of a problem in $NP$, then at least one of the reductions (to $L\_0, L\_1$ or $L\_2$) will result in an exponentially smaller instance. This is because the reduction, being polynomial, cannot increase the size of the instance too much, so (due to the large gaps in instance sizes) must - for at least one of $L\_0, L\_1$ or $L\_2$ \- give a much smaller instance as output.

Intuitively, this sounds very unlikely. It would mean we could take an arbitrary problem in $NP$ and in polynomial time output an exponentially smaller instance (albeit of a much harder problem).

Formally, this would mean that $NP\subseteq P/poly$, a consequence which is regarded as unlikely since it would imply the collapse of the polynomial hierarchy.

# Answer
> 4 votes
## Hartmanis et al proved that there are sparse set in $PSPACE\backslash NP$ iff $EXPSPACE \neq NEXPTIME$ and it is highly believed they are correct. This sparse set is not in NP and is not NP-hard because it is sparse.

Sparse language: In computational complexity theory, a sparse language is a formal language (a set of strings) such that the complexity function, counting the number of strings of length n in the language, is bounded by a polynomial function of n.

Mahaney's theorem is a theorem in computational complexity theory proven by Stephen Mahaney that states that if any sparse language is NP-Complete, then P=NP. The proof idea is easy. Take SAT which is np-compelete and suppose for the sake of contradiction there exists a sparse np-complete language S. Now solve the SAT instance via self reduction mapping tree for example you want to solve $\phi (x\_1,x\_2,...,x\_n)$ convert this formula to $\phi (x\_1=T,x\_2,...,x\_n)\land \phi (x\_1=F,x\_2,...,x\_n)$ and solve this new formula as. Repeating this argument makes exponentially tree for formula but we know that SAT is polynomially reducible to S which is sparse, you can use this fact to pruning the self reduction tree to keep the size of the tree bounded in a polynomial and solving sat with a polynomial algorithm. For the detail of manhaney's theorem you can read manhaney's proof, it is easy to find other resources for proof just google it.

To complete our proof we need last theorem which states there are sparse set in $PSPACE-NP$ if $EXPSPACE \neq NEXPTIME$.(even you can replace nexptime with np in this case. We don't need other direction!)

proof. If $EXPSPACE \neq NEXPTIME$ then we may assume that there exists a set $A, A \subseteq \\{0,1\\}^\*$, st $A\in PSPACE-NEXPTIME$ if we prefix each string in A by a 1 and interpret these strings as binary representation of integers, then we can convert A to tally(a language is tally if its member are like $1^n$) notaion:

$TALLY(A)=\\{1^n:n \in 1A\\}$.

since $A$ is in $PSPACE$ and not in $NEXPTIME$ then $TALLY(A)\in PSPACE-NP$ and it is sparse by the definition so by manhaney's theorem and the fact $p \neq np$ it is not np-hard .

It is unlikely for the Manhaney's theorem and $EXPSPACE=NEXPTIME$ to be true so the language you are looking for is $TALLY(A)$.

# Answer
> 2 votes
See the following Wikipedia article, notably the section on exptime complete problems: https://en.m.wikipedia.org/wiki/EXPTIME

Correction: EXPSPACE-complete problems will do the job. For example, the equivalence problem for regular expressions with squaring. There is a classic TCS paper by Albert Meyer and Larry Stockmeyer from 1972 proving that this is EXPSPACE-complete.

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


# Question
Title: Optimal solution for Weighted points problem
Problem:

> Fix a constant $k$. Given a set of $2d$-dimensional points $N = \\{N\_1, N\_2, N\_3, \dots, N\_n\\}$, each associated with an arbitrary weight, find a set of points $X = \\{X\_1, X\_2, X\_3, \dots, X\_k\\} \subseteq N$ such that the pairwise distance between any two points in $X$ is at least $D$, and $\sum\_{i=1}^k \mathit{Weight}(X\_i)$ is maximized.

It would be nice if I could get the exponential solution and then an efficient heuristic so that I can relate to why and how the problem reduces. The greedy way to do it would be to sort the points by weight and exclude points which are at distance $D$ from the current point that is being processed. Is there a better way to do it?

# Answer
> 3 votes
This problem is a variation of the Maximal Independent Set (MIS) problem in graph theory. To understand that you need to convert your point set $N$ into a graph $G=(N,E)$, where any two vertices $N\_1,N\_2 \in N$ are connected by an edge if and only if the distance between $N\_1$ and $N\_2$ is **less** than the threshold $D$. So the set $X$ you are looking for will be one of *independent sets* in the graph $G$. However your case is different, because here:

* Each vertex in $G$ has a numerical weight, and you are trying to maximize the total weight of the independent set instead of its size - this problem is called *Maximal Weighted Independent Set* (MWIS) problem.
* You are looking for an optimal independent set with exactly $k$ vertices.

There is a number of approaches to this class of problems, for example - this one. You can try to adapt their approach to your case with *fixed size* of the optimal independent set (which might not exist).

Another approach to this problem uses the fact, that the graph $G$ belongs to a class of Unit Disk Graphs. There is a number of *approximation algorithms*, developed for the MWIS, which use geometric specifics of such graphs - for example, this one. Again, they don't limit a number of vertices in the solution set. General discussion of heuristics for problems on unit disk graphs can be found here.

As for the straightforward **heuristic algorithm** for MWIS with predefined size of the solution - your approach is correct. I'll describe it in more details here. At first a definition:

* An anti-neighborhood $A(N\_i)$ of any point $N\_i \in N$ is a subset of $N$, such that for any point $N\_j \in A(N\_i)$ the distance between $N\_i$ and $N\_j$ is greater or equal than $D$.

We'll assume that each anti-neighborhood is represented by a tree-like data structure, which can perform three operations:

* Build a set from a list of points in $O(n\log n)$ time.
* Find a point (in the set) with maximal weight in $O(1)$ time.
* Compute intersection of two sets in $O(n\log n)$ time.

So, the algorithm:

**Step 1**. Find point $X\_1$ with maximal weight and build its anti-neighborhood $A(X\_1)$.

**Step 2**. Find point $X\_2 \in A(X\_1)$ with maximal weight and build the intersection $A(X\_1) \cap A(X\_2)$.

**...**

**Step $m$**. Find point $X\_m \in \bigcap\_{i=1}^{m-1}A(X\_i)$ with maximal weight and build the intersection $\bigcap\_{i=1}^{m}A(X\_i)$.

**...**

The intersection of anti-neighborhoods may become empty at some step - in this case the problem doesn't have a solution.

The total time of this algorithm will be $O(kn\log n)$. It's unclear how close this heuristic solution will be to the optimal one.

---
Tags: algorithms, approximation, greedy-algorithms
---


# Question
Title: Solve SUBSET SUM for Reciprocals of Primes
Let $p\_1, ..., p\_n$ distinct prime numbers with $P = \prod\_{i=1}^{n}{p\_i}$ and $A=(a\_1, ..., a\_n)$ with $a\_i = P/p\_i$.

## Problem

Show the SUBSET SUM problem $(A, \alpha)$ can be solved in polynomial (not pseudo-polynomial) time for every $\alpha \in \mathbb{N}$ and $P, p\_1, ... , p\_n$ unknown.

## First attempts

$P$ and $ p\_1, ... p\_n$ can be calculated with $P = \sqrt\[n-1\]{\prod\_{i=1}^{n}{a\_i}}$ and $p\_i = P / a\_i$.

Now we can write the problem as $\alpha/P = 1/p\_{i\_1} + ... + 1/p\_{i\_n}$

# Answer
The observation is that the denominator of the reduced fraction $1/p\_{i\_1} + \cdots + 1/p\_{i\_m}$ is $p\_{i\_1} \cdots p\_{i\_m}$. To see this, it suffices to notice that the (unreduced) numerator isn't divisible by any $p\_{i\_j}$. Indeed, the numerator is simply $$ \frac{p\_{i\_1} \cdots p\_{i\_m}}{p\_{i\_1}} + \cdots + \frac{p\_{i\_1} \cdots p\_{i\_m}}{p\_{i\_m}}. $$ All terms but the $j$th are products of $p\_{i\_j}$, but the $j$th term isn't, so the numerator isn't divisible by $p\_{i\_j}$.

As a consequence, if $\alpha/P$ is a sum of reciprocals of distinct primes, then we can read off the primes from the prime factorization of the reduced form of $\alpha/P$. We can compute this reduced form efficiently using GCD. Since we know $p\_1,\ldots,p\_n$, we can figure out whether the denominator is a product of a subset of $\\{p\_1,\ldots,p\_n\\}$, and if so, it only remains to check whether $\alpha/P$ is equal to the sum of reciprocals of prime in this subset.
> 3 votes

---
Tags: algorithms, complexity-theory, cryptography, primes, subset-sum
---


title: Floating point arithmetic on division

text:
# Question
Title: Floating point arithmetic on division
I am trying to figure out how $(x/y)$ in floating point arithmetic

$fl(fl(x) / fl(y))$ where $fl(x) = x(1-\delta\_1)$, $fl(y) = y(1-\delta\_2)$, $fl = (1-\delta\_3)$

I have:

$= x/y \cdot ((1-\delta\_1)/(1-\delta\_2))(1-\delta\_3)$

after arithmetic

$= x/y \cdot (\delta\_3 \delta\_1 - \delta\_1 - \delta\_3 + 1)/(1-\delta\_2)$

Not sure how to fully write the rest I believe i have to shorten them using the info that $\delta \< \epsilon$ and $\delta^2 \leq \delta$

# Answer
I don't know exactly where you're trying to get to with this, but I *think* you probably want to Taylor expand the division:

$$\frac{1}{1 - \delta\_2} = 1 + \delta\_2 + \delta\_2^2 + \delta\_2^3 + \cdots$$

Then, for example, if $\epsilon$ is the machine epsilon and $\delta\_2 \> 0$:

$$1 + \delta\_2 \le \frac{1}{1 - \delta\_2} \le 1 + \delta\_2 + \epsilon$$

That is quite a tight bound, when you think about it. (Exercise: Prove that this is true if $\delta\_2 \le 0$, too.)
> 1 votes

---
Tags: floating-point
---


# Question
Title: Is there a running hash algorithm that can efficiently handle arbitrary updates to a file's contents?
This question is about file-hashing/fingerprinting algorithms (similar to `SHA-1` and `MD5` and so on). Those algorithms are handy because they give you a small (and fixed-sized) hash code for any file, which can be later used to efficiently determine if that file is different from another file, and (if we are willing to ignore the unlikely possibility of hash-collisions) also whether two files are the same.

One small downside to computing the hash/fingerprint for a file is that you have to read the entire file in order to do so; if the file is very large (e.g. gigabytes or more) this can be an expensive operation.

A good way to avoid that expense is to compute the file's hash code as you are writing it to the disk, and store the hash code with the file. You can even resume updating the hash code later on, if/when you append more bytes to the end of the file, and (assuming no bugs or filesystem corruption) you'll have the file's fingerprint/hash cheaply available to you at all times.

However, the above "update as you go" approach seems like it may break down if you want to update the file in other ways besides appending -- in particular, if you want to truncate the file, or overwrite some existing bytes within the file with new values, you might have to then re-read the entire file in order to update the fingerprint/hash to the appropriate new value.

My question is, is there a type of hashing/fingerprinting algorithm that can efficiently handle file-truncation and byte-overwrite operations, and still provides reasonably good-quality hashing/fingerprinting? ("efficiently" in this case means that one could perform one of these operations on the file and then compute the correct new hash/fingerprint without having to re-read other parts of the file)

# Answer
One way to achieve it is to keep a dynamic balanced tree augmented with hashes. This will give you logarithmic slowdown for overwrites and truncation, and also will work with any hashing algorithm.

Let the file be partitioned in blocks of fixed size, $H$ be a hash-function, and $h\_t$ be a value stored in a node $t$. If $t$ is a leave, then $h\_t$ is a hash of the corresponding block. If $r$ is a parent of $a$ and $b$, then $h\_r = H\[(h\_a,h\_b)\]$.
> 2 votes

# Answer
There is a faster way than Dmitri's method. You can hash a length-$k$ sequence $f$ to $\sum\_{i=1}^k h(i,f(i))$, where $h$ is any two-input hash function. This way, you can update the hash of a file even if you only know the part of the file that has been changed. Such a hashing technique is good enough in the sense that changing or rearranging terms in the sequence at random will almost surely result in a different hash. However, it would not be cryptographically secure since each term in the sequence contributes independently to the sum and it may be possible to engineer a collision without too much work.
> 2 votes

---
Tags: efficiency, hashing
---


# Question
Title: What is the difference between Big(O) and small(o) notations in asymptotic analysis?
What is the difference between $O$ (big oh) and $o$ (small oh) notations in asymptotic analysis? Even though I understand that $o$ is used for a bound that is not tight, is it allowed to use $O$ notaion for a bound that is also not tight? For example can I say that $5n=O(n^3)$?

I am also confused by what this statement in CLSR means "The main difference is that in $f(n) =O(g(n))$, the bound $0 \le f(n) \le cg(n)$ holds for some constant $c \> 0$, but in $f(n) = o(g(n))$, the bound $0 \le f(n) \< cg(n)$ holds for all constants $c \> 0$." As the value of $c$ will differ in the inequality "$0 \le f(n)\< cg(n)$ for all $n \> n\_0,c\>0$. " for different $n\_0$.

# Answer
Bigoh notation $O$:

This is anlogous to $\le$. $f(n) = O(g(n))$ means that for large enough value of $n$ value of $f(n)$ will be within some constant factor of value of $g(n).$

Smalloh notation $o$:

This is anlogous to $\<$ relation. Now, $f(n) = o(g(n))$ means that if you are given any constant $c\>0$ you will be able to find out some constant $n\_0\>0$ such that for all $n\ge n\_0$, $f(n) \< c.g(n)$ holds.

Intuitively smalloh notation says that $f(n)$ is asymptotically slower than $g(n)$.

For example $3n = O(5n)$ but $3n\ne o(5n)$ because for latter case if I give you $c=1/5$ you will not able to find out value of $n\_0$ such that for all $n\ge n\_0, 3n \< c.5n$.
> 1 votes

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


title: Complexity of negation cancellation

text:
# Question
Title: Complexity of negation cancellation
Consider propositional logic over the connectives $\land$, $\lor$, and $\lnot$. Notation: $| \alpha |$ is the length of formula $\alpha$.

We are given a formula $\phi$. Cancel all cancellable negations in $\phi$ by applying all possible valid biconditionals (EDIT: such as the examples below) to get $\phi'$; for clarity we note that $\phi \leftrightarrow \phi'$. We are also given that $\phi'$ is monotonic. Are there examples where $| \phi' |$ must grow exponentially, or is $| \phi' |$ bounded by a polynomial? If there's an example of exponential growth, please show it.

EDIT: The following biconditionals are examples of what I'm trying to get at, formulas which can be used to cancel negations while preserving equivalence. The procedure would presumably be to unify the left-hand side of the formula with $\phi$ via unification and substitute the right-hand side as appropriate per unification.

$$\alpha \land (\lnot \alpha \lor \beta) \leftrightarrow \alpha \land \beta$$ $$\lnot \lnot \alpha \leftrightarrow \alpha$$

# Answer
I suspect the answer is that in general $\phi'$ might need to be of exponential size, but I am not certain. There are known examples of a boolean circuit $C$ (with negations) of polynomial size that computes a monotone function, while the smallest monotone boolean circuit $C'$ (with no negations) has exponential size. See http://www.cs.cornell.edu/~eva/Gap.Between.Monotone.NonMonotone.Circuit.Complexity.is.Exponential.pdf and Simple example of exponential gap between monotone and non-monotone circuits. It's possible that perhaps this could be extended to an argument that covers your case as well: if there is a polynomial-size formula $\phi$ corresponding to $C$ (this would need to be checked), the results above imply that any monotone formula $\phi'$ computing the same function would need to be of exponential size, so there would necessarily be an exponential gap for some functions, no matter what set of substitution rules ("biconditionals") you use. The gap in this argument is verifying whether Tardos's example can indeed be computed by a polynomial-size circuit; it's not clear whether it can, as circuits are more powerful than formulas, and I haven't verified this, but perhaps you can do so.
> 1 votes

---
Tags: complexity-theory, logic, propositional-logic
---


# Question
Title: Find two numbers in sorted array whose product is close to N
Given a sorted array of numbers, is there a good algorithm for finding two numbers in that array whose product is as close as possible to a given number N?

I know that there is a good O(n) (?) algorithm for the related problem of finding two numbers that sum to a given number N. You begin with ptr1 at the start of the array and ptr2 at the end, and if \*ptr1 + \*ptr2 \> N you decrement ptr2, else increment ptr1.

But for multiplication, it feels possible this method could "miss" the optimal solution by overshooting it somehow? Is there a good way to solve the multiplication variant in something that isn't just O(n^2)?

# Answer
This answer is compilation of above comments but this include reasoning why this algorithm works.

```
1. find(A, val)
2.    start = 1
3.    end = A.length
4.    minn = (start,end)                //minn is pair used to store answer
5.    minnErr =   |A[start]*A[end]-val|        //minnErr is difference between best
                                  //pair of values seen so far and targate value.
6.    while(start < end)
7.        if (|A[start]*A[end]-val| < minnErr) //if this pair of values is
                                                      //even better than remember it.
8.            minnErr = |A[start]*A[end]-val|
9.            minn = (start, end)

10.       if A[start]*A[end] > val:              // here
11.           end = end - 1
12.       elif A[start]*A[end] < val:
13.           start = start + 1
14.       else:
15.              break
16. return minn

```

Algorithm works as follows:

here answer is pair of indices of element of array which has product closest to target value.

* We keep two pointers $start$ and $end$. Which are initialized to $1$ and $array\space size$ respectively.
* Now in every iteration we compare $A\[start\] * A\[end\]$ with $minnErr$.
* If current pair have better solution than we record it.
* If $A\[start\]\*A\[end\] \< val$ than we increase $start$ by $1$. Now note that all $(i,j): i\< start, j\le end$ can never be solution because for any such $(i,j)$ we have $A\[i\]\*A\[j\] \le A\[start\]\*A\[end\] \< val$.
* if $A\[start\]\*A\[end\] \> val$ than we decrease $end$ by $1$. Now here(considering decremented value of $end$) all $(i,j): i\ge start, j\>end$ can never be solution because for any such $(i,j)$ we have $A\[i\]\*A\[j\] \ge A\[start\]\*A\[end\] \> val$.
* if $A\[start\]\*A\[end\] = val$ than we stop here as this is best solution.

credits: @G. Bach, @greybeard
> 1 votes

# Answer
Vimal’s answer is a start. In real live you want to get it right if no product is within a billion of val, and you want to get it right if the arrays contain negative values, or if val is negative itself.

So you don’t start with minnErr = one billion. You start with minn = (1,1) and minnErr = error for a\[1\], a\[1\].

Then you split the array into positive and negative numbers. You examine the product of the smallest positive numbers, the largest negative numbers, and the largest negative times the smallest positive.

When that is done, if val \> 0, you examine pairs of positive numbers, and pairs of negative numbers as before. But if val \< 0, then you examine the products of negative and positive numbers, starting with the smallest negative and smallest positive numbers and proceeding to the largest ones. The order of the numbers must be reversed for this.

(Why so complicated? Say val = 1. If the positive numbers at all around 1,000 and the negative ones around -10^12 with the exception of one value -0.001, then the closest is -0.001 * 1000 = -1 even though it is negative).
> 1 votes

---
Tags: algorithms
---


# Question
Title: What does $ \forall \alpha_1, \dots , \alpha_n . \tau $ mean formally as a type?
I was learning about polymorphic types but I couldn't understand the notation, can someone explain it means (context cs421 UIUC):

$$ \forall \alpha\_1, \dots , \alpha\_n . \tau $$

its supposed to be a type but I have no idea what it's suppose to mean.

Perhaps writing some of my thoughts or questions might be helpful in clarifying what I'm confused about:

1. Why is there a dot separating the quantifier and the type
2. How does this relate to normal FOL? e.g. if I had $$ \forall x \phi(x) $$ that would mean that for all values x can take in the universe at hand, the proposition $\phi(x)$ is true (assuming the whole expression is true, which it may not be but whatever)
3. Is $\tau$ a function of the (meta?) variables $$ \forall \alpha\_1, \dots , \alpha\_n $$?
4. What do $$ \forall \alpha\_1, \dots , \alpha\_n $$ stand for?
5. Are $$ \forall \alpha\_1, \dots , alpha\_n $$ meta-variables? What is their domain?
6. Could I have a couple of concrete examples of what they are
7. I am still confused what entails a monomorphic type vs a polymorphic type. In slide 54 they define that a monomorphic type can be a "type variable $\alpha, \beta, \gamma, \delta, \epsilon $". However, I find that very very confusing because consider the value $e$ with type $\alpha$ ($e:\alpha=\<e,\alpha\>$). What confuses me is that $\alpha$ can be ANY value, so doesn't that mean $e$ is polymorphic? How is that different from specifying the type value pair for that expression $e:\forall \alpha. \alpha$. They both seem the same to me. This is confusing me a lot. Whats the difference?

I think the lectures assume the definition of them its clear but it really isn't. Can I have a more formal specification of it?

For example when we are told $$x:\tau$$ as a notation its not clear at all it really just means the tuple $$ \langle x, \tau \rangle$$ (until I looked it up at Wikipedia). But Wikipedia didn't save my day for this question, unfortunately...

---

Crossposted: https://www.quora.com/unanswered/What-does-forall-alpha\_1-dots-alpha\_n-tau-mean-formally-as-a-type

# Answer
The notation is explained in your course material, e.g. here starting on slide 47. In the notation $$T = \forall \alpha\_1, \dots, \alpha\_n.\tau$$ $\alpha\_i$ are type variables, the $\tau$ is a monomorphic type, and $T$ is a universally quantified, polymorphic type. While free type variables may occur in $\tau$, the quantified variables $\alpha\_i$ do not occur free in $\tau$.

> 1. Why is there a dot separating the quantifier and the type

This is a just a syntactic convention used in type theory. The dot separates the quantifier part from the type it applies to.

> 2. How does this relate to normal FOL? e.g. if I had $ \forall x \phi(x) $ that would mean that for all values x can take in the universe at hand, the proposition $\phi(x)$ is true

There's a strong relationship between logical formulas and types in programming languages, called Curry-Howard isomorphism.

> 3. Is $\tau$ a function of the (meta?) variables $ \forall \alpha\_1, \dots , \alpha\_n $?

$\tau$ is not a function, it's a monomorphic type. You can think of the quantification as adding more context to this monomorphic type thus making it polymorphic. The quantification basically "hides" the variables from the context the whole expression appears in.

> 4. What do $ \forall \alpha\_1, \dots , \alpha\_n $ stand for?
> 5. Are $ \forall \alpha\_1, \dots , \alpha\_n $ meta-variables? What is their domain?

$\alpha\_i$ are type variables that (typically) occur free in $\tau$, but are bound by the quantification and do not occur free in $\forall\alpha\_i.\tau$ anymore. Like variables in a mathematical expression represent placeholders for concrete values, type variables represent placeholders for more concrete types.

> 6. Could I have a couple of concrete examples of what they are

The most common example of a polymorphic type is the list type $\forall \alpha . \alpha\\;\mathsf{list}$ (this is the notation for Ocaml, in Haskell the notation would be $\forall \alpha.\[\alpha\]$). In your real code this polymorphic type might be used as a monomorphic type when $\alpha$ is replaced by a concrete type like $\mathsf{int\\;list}$, $\mathsf{bool\\;list}$ or even $\mathsf{(int\\;list)\\;list}$.

Sometimes you may still deal with polymorphic types, for example the empty list literal $\[\\,\]$ has the polymorphic type $\forall\alpha.\alpha\\;\mathsf{list}$. Note that this is different from when you use $\[\\,\]$ in your real code when it usually will be specialized to $\mathsf{int\\;list}$ (or whatever concrete lists you are dealing with) when type inference happens. So $\[\\,\]$ may have one polymorphic type or one of many monomorphic types, where the latter are all very different.

The above linked PDF gives more examples on slide 55.
> 3 votes

---
Tags: programming-languages, type-theory, type-checking, type-inference, polymorphisms
---


# Question
Title: Why does cpu benchmark increases faster than cpu frequency?
Since duration of an instruction is just the number of cpu cycles needed times the time of a cycle, which is the inverse of the frequency, I do not get why the ratio of cpu benchmark of a two processors of a same trademark is not exactly the inerse of the ratio of the frequencies. Cpu is supposed not to loose time by being inefficient but only to obey and realize the processors instructions that we ask, which are the same in a test of benchmark of the two processors. Could you enlight me ?

# Answer
If processor A and processor B took exactly the same amount of processor cycles to do the same work, and processor B had exactly twice the clock speed of processor A, then the time for a benchmark running on processor B would be exactly half the time of the same benchmark running on processor A.

But they don't take exactly the same number of cycles.

One big effect is that historically, the speed of RAM hasn't increased as much as the speed of processors. On an Apple II computer, every memory access took exactly one processor cycle. On a modern desktop computer, a memory access takes in the order of 100 processor cycles. If processor B has twice the clock speed of processor A, but the RAM isn't twice as fast, then a benchmark will not run in half the time.

But on the other hand, there are effects that make modern processors take less cycles for the same work than older ones. Examples are:

Larger and larger RAM caches, which mean there is less use of slow RAM.

Vector units, which may process for example 16 byte operations or four double precision floating point operations just as fast as a single byte or floating point operation.

Multiple processing units; where the processor can decode and process multiple instructions in the same cycle.

Shortened latency; for example a floating point multiplication might take7 cycles on an older processor, 5 on a newer, and 3 on the latest processor.

64 bit operations, more registers: A modern processor can add two 64 bit numbers in a single operation, while an older processor would need multiple operations. More registers means that more values can be kept in registers and need not be loaded and stored to memory all the time.

And so on.
> 0 votes

# Answer
Part of the benchmark might be limited by CPU time; other parts might be limited by IO or memory latency or other factors. Speeding up the clock frequency will speed up the first parts but not the second parts. As a result, doubling the clock frequency won't necessarily double the speed at which the benchmark is executed. So, the two ratios aren't necessarily equal.
> 0 votes

---
Tags: cpu
---


title: How to calculate conditional entropy

text:
# Question
Title: How to calculate conditional entropy
I'm new to information theory and I am struggling to understand this problem. Let $p(x,y)$ given by:

How can we calculate $H(X|Y)$? I know $H(X|Y)=H(X|Y=0)+H(X|Y=1)$ but then I don't know how to go further.

# Answer
$${\displaystyle \mathrm {H} (Y|X)\ =-\sum \_{x\in {\mathcal {X}},y\in {\mathcal {Y}}}p(x,y)\log {\frac {p(x,y)}{p(x)}}}$$

Based on chain rule, we have:

\begin{aligned}\mathrm {H} (Y|X)&=\sum \_{x\in {\mathcal {X}},y\in {\mathcal {Y}}}p(x,y)\log \left({\frac {p(x)}{p(x,y)}}\right)\\\\[4pt\]&=-\sum \_{x\in {\mathcal {X}},y\in {\mathcal {Y}}}p(x,y)\log(p(x,y))+\sum \_{x\in {\mathcal {X}},y\in {\mathcal {Y}}}{p(x,y)\log(p(x))}\\\\[4pt\]&=\mathrm {H} (X,Y)+\sum \_{x\in {\mathcal {X}}}p(x)\log(p(x))\\\\[4pt\]&=\mathrm {H} (X,Y)-\mathrm {H} (X).\end{aligned}

So for $H(X|Y)$ in your sample, we have: $$ H(X|Y) = -( 0.25 \times \log(\frac{1}{2}) ) - ( 0.25 \times \log(\frac{1}{2}) ) -( 0 \times \log(\frac{0}{0.5}) ) -( 0.5 \times \log(\frac{0.5}{0.5}) ) $$
> 1 votes

---
Tags: information-theory, entropy
---


# Question
Title: Is it NP-complete to test if a graph contains $t$ $k$-cliques?
Given a graph $G$ along with two non-negative integers $t, k \in \mathbb{N}$, The instance $(G,t,k)$ is a yes instance of the problem if and only if the graph $G$ contains $t$ cliques with $k$ vertices (there are $t$ copies of $K\_k$, a cliques of size $k$ in the graph $G$). How to prove that $(G,t,k)$ is NP-complete?

It is obvious that it is in NP. I have tried to prove that $k$-CLIQUE language $(G,k)$ is reducible to a $(G,t,k)$ language. But I can't get the idea, how to get $t$ of $k$-CLIQUES.

# Answer
This problem is clearly NP-hard since it is a generalization of many NP-hard problems. The most obvious one is the maximum clique problem, i.e. finding a clique of the maximum size in a graph. The decision version of this problem is a special case of your problem where you set $t$ equal to one. (See below for the hardness-proof).

**Further reading.**

Other example is the triangle packing problem, assuming you are looking for pairwise vertex-disjoint cliques (note that for the maximum clique it does not matter if the cliques have to be vertex disjoint since we chose $t=1$). In the triangle packing problem we are looking for a set of $k'$ vertex-disjoint triangles ($K\_3$) in a graph, which is a special case of your problem where we set $k = 3$ and $t = k'$.

Note that the maximum clique problem is one of the Karp's 21 hard problem, which are probably some of the most important/original proven hard problems. In his paper "Reducibility Among Combinatorial Problems" \[Karp, 1972\], he provides some of the very first hardness reductions using Cook's theorem. Here is a link to the wiki page of the paper where you can find more information and a link to the original paper.
> 2 votes

---
Tags: complexity-theory, graphs, np-complete
---


# Question
Title: largest bitwise-or subset with a maximum number of on bits?
Suppose I have the following set of bit sets:

```
 [1,]    0    1    1    1    0    1    0    1    0     0
 [2,]    1    0    1    1    0    0    0    1    0     1
 [3,]    0    0    1    0    1    1    0    1    1     0
 [4,]    1    0    1    0    0    0    0    1    1     1
 [5,]    0    1    0    1    0    1    0    1    1     0
 [6,]    0    1    1    1    1    0    0    1    0     0
 [7,]    1    1    0    0    0    1    1    0    0     1
 [8,]    1    1    0    1    1    1    0    0    0     0
 [9,]    0    1    1    0    1    1    0    0    0     1
[10,]    0    1    1    1    0    0    1    1    0     0

```

How would I go about finding the largest set such that the bitwise-or of that set does not exceed n bits in the "on" position.

For example, if I *or* rows 1 & 10...

```
 [1,]         0    1    1    1    0    1    0    1    0     0
[10,]         0    1    1    1    0    0    1    1    0     0
[1 or 10,]    0    1    1    1    0    1    1    1    0     0

```

This gives me 7 bits in the "on" position.

Now suppose my limit was 8 bits... how would I go about finding the largest set?

Edit: I know how to do this as a mixed-integer-linear program, but I'm assuming there's a nifty graph approach.

# Answer
This problem is NP-hard. It is called "the minimum-k-union problem". Given a universe $U$ and a family of sets $\mathcal{F}$ over this universe. Are there $k$ distinct sets in $F$ such that the union of all these sets has size at most $d$.

Your presentation is the matrix formulation of this problem where each column corresponds to an element in the universe and each row corresponds to a set in the family. We are looking for $k$ rows such that the number of columns having at least one "1" is at most $d$.

The Problem is NP-hard and has approximation algorithms. Here is a link for one of them.
> 1 votes

---
Tags: algorithms, sets, weighted-graphs
---


# Question
Title: Time complexity described by recurrence relation
I need to find the time complexity described by the following recurrence relation.

$T(n) = T(n/2) + T(n/3) + T(n/6) + n$

$T(1) = \Theta(1)$

The solution must be something like $T(n) = \Theta(f(n))$.

Obviously the standard form of the master theorem can't help me and any other special cases that I have found weren't useful.

# Answer
If we draw recurrence tree for this relation than it would be something like following:

```
         T(n)            -> Cost: n
    /     |    \
T(n/2)  T(n/3)  T(n/6)   -> total cost: n/2 + n/3 + n/6 = n
   .
   .
  T(1) --------------->  highest depth which is about lg(n).

```

So, there are $lg(n)$ levels and every level has at least cost $n$ so $T(n) = \mathcal{O}(n\lg{n})$.

Now let's conjecture that $T(n) = \Omega(n\lg{n})$ and try to prove it.

---

We will prove this by induction.

Let's assume that $T(n) \ge c.n\lg{n}$ for some $c \> 0$.

$T(n+1) = T(\frac{n+1}{2}) + T(\frac{n+1}{3}) + T(\frac{n+1}{6}) + n+1$

$\therefore T(n+1) \ge c.\frac{n+1}{2}.\lg{\frac{n+1}{2}} + c.\frac{n+1}{3}.\lg{\frac{n+1}{3}} + c.\frac{n+1}{6}.\lg{\frac{n+1}{6}} + n+1$

$\therefore T(n+1) \ge c.(n+1)\lg{(n+1)} + (n+1 - c.(n+1)(\frac{\lg{2}}{2} + \frac{\lg{3}}{3} + \frac{\lg{6}}{6})$

$\therefore T(n+1) \ge c.(n+1)\lg{(n+1)} + (n+1 - c.(n+1)(\frac{\lg{432}}{6}))$

$\therefore T(n+1) \ge c.(n+1)\lg{(n+1)} \space \space \space $

$\[\because (n+1 - c.(n+1)(\frac{\lg{432}}{6}) \< 0, \space \text{for } c\ge 1\]$

---

Hence, we have proved that $T(n) = \Omega(n\lg{n})$ but we also have $T(n) = \mathcal{O}(n\lg(n))$.

So, that implies $T(n) = \Theta(n\lg{n})$.
> 1 votes

---
Tags: complexity-theory, time-complexity
---


# Question
Title: Are Context-Free Grammars with only one Production Rule always Unambiguous?
Consider the following (Context-Free) Grammars with only one production rule (not including the epsilon production):

* $S \rightarrow aSb\\;|\\;\epsilon$
* $\require{cancel} \cancel{S \rightarrow aSSb\\;|\\;\epsilon}$
* $S \rightarrow aSbS\\;|\\;\epsilon$
* $S \rightarrow aSaSb\\;|\\;\epsilon$
* $S \rightarrow aaSaaSbb\\;|\\;\epsilon$
* $S \rightarrow aSbScSdSeSf\\;|\\;\epsilon$
* $\require{cancel} \cancel{S \rightarrow aSSbcSd\\;|\\;\epsilon}$
* etc...

Are all these Grammars unambiguous? Will every Grammar with only one production rule (not including the epsilon production) *always* be unambiguous? It would seem so, but I'm not totally sure.

> Edit: Vimal Patel has shown that examples like the 2nd and last are, in fact, ambiguous. Discounting these examples and assuming that the non-terminal symbol $S$ never appears next to itself, does my belief still hold?

Grammars that only contain ***one*** unique terminal symbol could be ambiguous. (ex. $S\rightarrow aSaSa\\;|\\;\epsilon$) However, Grammars with at least ***two*** distinct terminal symbols seem like they should always be unambiguous.

> Edit II: Vimal Patel has also shown that production rules which **both** begin and end with the non-terminal $S$ are ambiguous (i.e. $S \rightarrow SaSaSbS\\;|\\;\epsilon$) discounting this as well, does my belief still hold?

I've tried showing that Grammars like these are $LL(1)$. However, it seems only Grammars of the form $S \rightarrow aSb\\;|\\;\epsilon$ are $LL(1)$. Grammars like $S \rightarrow aSaSb\\;|\\;\epsilon$ are *not* $LL(1)$. (Illustrated in the parse table below.)

Despite the example Grammar above not being $LL(1)$, it still seems to be unambiguous. Maybe it's simply a matter of using a higher $k$ for $LL(k)$?

In short, are (Context-Free) Grammars with only **one** production rule (not including the epsilon production) and **at least two** unique terminal symbols always unambiguous?

I would really love some help, any at all would be greatly appreciated.

# Answer
> 5 votes
Unfortunately, your conjecture is wrong.

For instance $S \rightarrow aSSb | \epsilon$ is ambiguous.

To see that take $w: aabb$. For this string we have following two distinct derivation tree possible. In following derivation trees $e$ represents $\epsilon$

```
        S                            S
  /  /    | \                  / /    |    \
a  S      S  b                a S     S     b
 / | \ \   \                    |   / / | \
a  S  S b   e                   e  a S  S  b
   |  |                              |  |
   e  e                              e  e

```

---

**Second counter example:**

Consider grammar $S \rightarrow SaSbSaS | \epsilon$ It's easy to see that this grammar is ambiguous. (hint: take $w: abaaba$.)

---

**Third counter example:**

Consider grammar $S \rightarrow abSabSab | \epsilon$. Take $w = abababababab$. It's easy to see that there are two distinct derivation trees.

Actually this grammar is directly derived from grammar $S \rightarrow aSaSa|\epsilon $ by homomorphism $h(a) = h(ab)$.

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


# Question
Title: Fastest algorithm to find all the possible paths of length $n$ from a give node in a directed graph?
I am trying to find the fastest algorithm to find all the possible paths of length $N$ from a given node in a directed graph.

My solution is to do a modification of breadth first search from the given node for $N$ iteration. Its time complexity is around $\theta(V+E)$. But the problem is $|V|$ & $|E|$ becomes exponential because as long as there is an edge, the same node can be visited again.

Can there be a solution of this problem with polynomial time complexity? It seems this problem has optimal substructure solution. Is there any solution using dynamic approach?

# Answer
> 3 votes
This problem is NP-hard, since the Hamiltonian Path problem is a special case of this problem where we set N=n and check whether the answer is strictly greater than zero.

This problem is actually #P-hard wich is believed to be strictly harder than NP.

The version of the problem where you only look for the existence of such a path is called the longest path problem. A well-known problem in theory. It is fixed-parameter tractable when parameterized by the length of the path (check Parameterized Algorithms book by Cygan et al for description and methods).

# Answer
> 1 votes
The above answer considers the version of this problem where vertices cannot be visited multiple times. However it seems that the intention of the question is that vertices could be visited multiple times.

The number of such paths can be exponential in |V| and |E|, so they cannot be listed in polynomial time.

The problem of counting the number of such paths is equivalent to computing the $N$th power of the adjacency matrix of the graph. If $A$ is the adjacency matrix of the graph, then the value of the cell $(i, j)$ of $A^N$ is the number of $N$-length paths from vertex $i$ to vertex $j$.

While in general such paths cannot be listed in polynomial time, they however can be listed with polynomial delay (i.e. outputting a new path in polynomial time). For all lengths $k \le N$, compute by dynamic programming numbers $cnt\[v\]\[k\]$, which represents the number of paths of length $k$ from the starting vertex to vertex $v$. Now such paths can be extracted by traversing this dynamic programming structure backwards. If $cnt\[v\]\[N\]$ is positive, find vertex $u$ such that there is edge from $u$ to $v$, and $cnt\[u\]\[N-1\]$ is positive. Extract the $N-1$ length path to $u$ recursively, add $v$ as the last vertex of the path and subtract $cnt\[v\]\[N\]$ by one.

---
Tags: algorithms, graphs, counting
---


# Question
Title: How do you find a hash function that respects a custom equality function?
I've been tasked with hashing arbitrary types in C++, with the caveat that `A == B` implies `hash(A) == hash(B)` even if equality of `A` and `B` is determined by a custom equality function `==`.

For simplicity we can assume that `==` is an equivalence relation.

For example, the expected behavior of the `hash` function on std::vectors is as follows:

Given

```
using namespace std;
vector A = vector();
vector B = vector();

```

`A == B` will be true because `==` is overloaded for `std::vector` to mean equality of the underlying data. Correspondingly, `hash(A) == hash(B)` should also be true.

I can't simply hash the addresses of `A,B`as integers because `A == B` but `hash(&A) != hash(&B)` in general.

I've thought of one solution, but I wonder if its optimal. It seems terribly inefficient. The solution is to build the `hash` function as new values are hashed:

```

using namespace std;

<template class Key>
class Hasher{

    public:

       unordered_map<pair<Key,Integer>> hashedKeys;
       int max_hash

       Hasher(int max_hash){
          this->max_hash = max_hash;
       }

       int hash(Key key){

          // If key has already been hashed, used that hash_value
          if ( hashedKeys.count(key) == 1){
               return hashedKeys[key];
          }

          // For pairs of saved (Key key, int hash_value)
          for(unordered_map<Key,Integer>::iterator it=hashedKeys.begin(); it!=hashedKeys.end(); it++;){

             // If an equal key has been inserted, just use its hash_value
             if(key == *it){
                hashedKeys.insert(key, *it.second);
                return *it.second; //use hash value of equal Key
             }
          }

          // If no other Keys equal this one, randomly hash it, and save
          int hash_value = rand() % max_hash;
          hashedKeys.insert(key, hash_value);
          return hash_value;

       }
}

```

I could do some extra bookkeeping to ensure that inequivalent Keys are less likely to be mapped to the same hash by the random assignment, but that's largely besides the point.

Ignoring collision resolution, hashing a new value is `O(hashedKeys.size())`, while hashing a previous hashed value is `O(1)` We also require `O(n)` additional space to store the computed hash values, where most hash functions require `O(1)`.

In a situation where a cache is large and new keys are constantly being inserted, the `O(n)` search is incredibly inefficient, so I'd prefer another approach if possible, or a proof that improvement is impossible.

Take the class ParityInteger:

```
class ParityInteger{
   public:
      int number;

      ParityInteger(int n){
         number = n;
      }

      bool operator==(const ParityInteger& other){
         return (number % 2) == (other.number % 2);
      }
}

```

The ideal `hash` for such a class is:

```
int hash(ParityInteger n){
   return n%2;
}

```

which basically assigns a ParityInteger to a representative of its equivalence class.

Besides my method in the class `Hasher`, is there any better way to automatically find a function which assigns equivalent members of an arbitrary type to the same integer, without being trivial?

Given a computable equivalence relation `==` for some type, is there an algorithm to compute a nontrivial function `hash` such that `==` is a congruence relation wrt `hash`.

**EDIT:** It seems that the naive `Hasher` algorithm I put forward is essentially optimal assuming you treat `==` as a blackbox: https://cstheory.stackexchange.com/questions/33223/on-partitioning-a-collection-into-equivalence-classes

# Answer
The way I can think of to do this is by some sort of normalization: that is, you need to find a function $f$ such that, if $\equiv$ is your custom equality and $==$ is the normal C++ (or whatever language you use) equality, for all $x,y$, we have $x \equiv y$ if and only if $f(x)==f(y)$. We call $f(x)$ the *normal form* of $x$.

Then, the trick is, instead of computing hashes, you compute hashes of normal forms.

Hash functions are specifically designed to produce large changes in output for small changes in input: that's what makes them well suited to hashtables and cryptography. So there's not likely a way to make a hash function that is invariant over some custom equality, except to have it compute on normal forms.

What you've described might work from a correctness point of view, but there are a few things to consider:

1. It is not hashing. That is, a hash is essentially a function that takes some variable-sized data and produces a fixed size output (in your case, an int). You haven't designed a function at all, you've just defined a way to assign random identifiers to input.
2. You lose all the advantages of hashing. One main use case of hashing is quickly comparing two things.

If you hash a bunch of things ahead of time, then you very quickly check that any of those two things are for sure different, and if their hashes are the same, you know with high probability that they are actually the same. With your version, you get fast comparison, but to compute all your hashes you'll have already compared all $n^2$ unhashed pairs at least once, so you will never save work.

The other thing hashes are useful for is indexing complex data in a data structure. That is, you convert your key into a hash, and each time you do a key lookup, you compute the hash and use it to find the key in a data structure, possibly a tree or hashtable. With yours, you end up doing $n$ comparisons each time you lookup the hash key, which means you'd be better to just use an unordered list as your data structure and search through it each time, comparing each element to the key you're looking for.

Using unique identifiers instead of hashes is a fine way to index data, but then you definitely do NOT want to generate random identifiers, since there's still a risk of a collision. Usually you'd just keep a counter and generate one plus the last identifier each time you allocate a new one.
> 5 votes

# Answer
If you don’t know the equality function then you let hash(x) = 0. Seriously. All your algorithms will work, but slowly because of collisions. All the other suggestions will make your hashing slow instead so you lose nothing. Actually, if you have multiple dictionaries containing these keys, operations are quadratic in the size of each dictionary, instead of quadratic in the total number of hashed values.

For a known custom equality function you just write a custom hash function. Just calculate hashes of all or some of the items that are used for the equality check and combine them.

For example, if you are comparing arrays by comparing the size and all items, you could calculate a hash of the array size, the first, last, and median element, and the element at index 1,000,000,000 modulo array size, and combine these five numbers. There is a good chance for non-equal arrays to have non-equal hashes.
> 3 votes

# Answer
Suppose the objects you want to compare are strings containing terminating programs that output either 1 or 0 (and written in Visual Basic, because why not), and the equality function returns true if and only if the output of the two programs given as operands is the same. (The termination assumption is there to ensure that this equality is well-defined.)

First, notice that the only valid hash functions are those that produce at most 2 distinct output values: If, to the contrary, there are some three inputs `A`, `B`, `C` that yield distinct hash values, then at least one of `A == B`, `A == C` or `B == C` holds by the pigeonhole principle, but the RHS of the corresponding `A == B` $\implies$ `hash(A) == hash(B)` constraint fails. (This also holds for your ParityInteger example.)

So the only valid hash functions are:

1. Functions that always return the same value (as mentioned in gnasher729's answer, these are valid and maybe even OK as a "let's just get this to compile" stopgap but give you none of the benefits hash functions are intended to have)
2. Functions that compute what the input program will finally write out, either by simulating it or by some more complicated static analysis, and return (a function of only) this output value.

Why so strict for the second possibility above? If the hash function ever returns the "wrong" answer for some program `A`, and the "right" answer for some other program `B` that produces the same output as the first program, then `A == B` $\implies$ `hash(A) == hash(B)` is violated.

Note that simulation always works but is slow in the worst case (all we are guaranteed is that the hash function will finish in finite time; it's not even O(anything)!), and coming up with static analysis techniques that correctly determine the result of *every* terminating program in O(something) time seems *hard*, since this amounts to discovering a way of running terminating programs unboundedly faster than simulating them. (E.g. all NP-complete problems can be solved by terminating programs that return 0 or 1, so if you could find a polynomial-time static analysis approach you would have shown P=NP; probably stronger statements along these lines can be made.)
> 1 votes

# Answer
The assumption is: You have an "equality" operator. The equality operator follows the usual rules, and it is also stable over time: If x = y or x ≠ y today, then x = y or x ≠ y tomorrow as well. You need a hash function which is guaranteed to hash equal values to equal hashes. Since equality is stable over time, if hash (x) is calculated and stored today, then hash (x) must return the same value tomorrow as well. And we assume there is no way to calculate a good hash function that only looks at the value of x, so if we want a good hash function it must be based on comparing values.

We can start with hash(x) = 0. We may be able to do better. For example, you might have an equality operator comparing arrays, and although you don't know the exact rules, you might know that arrays with different number of elements are always different. This divides all possible values into a large number of equivalence classes.

So we can start with hash (x) = hash ("number of elements in x"). This means that if we hash n values, using some method that compares values for equality, the difficulty doesn't grow with the number of values hashed, but only with the number of values in each equivalence class. If we are happy with only one hash value per equivalence class, we are done.

Otherwise, he problem is that once we have hashed k different values in some equivalence class, and we are given an arbitrary element x in the same equivalence class, we need to check if x is one of the previously hashed values. If we know nothing more about the equality function than what we have used, then we need to compare x with all previously hashed values until we find one that is equal, or compare with all previously hashed values if none are equal. So to hash k values in the same equivalence class that are all not equal takes about $n^2 / 2$ comparisons.

We may be able to do better if you know *something* about the equality function. You may be able to divide all values in an equivalence class into overlapping groups, so each value would belong to one or more groups, where only values in the same group can be equal, and all groups a value x belongs to can be calculated. In that case, instead of comparing x with all values, you would calculate which groups it belongs to, keep track of hashed values in each group, and compare x with all the values in these groups.

Summary: You divide the set of values x into equivalence classes, such that you can calculate which equivalence class each x belongs to. (If you know nothing about the equality operator then you have only one equivalence class). You then hash the equivalence classes. You now have a useful hash function. If you have various hash tables, then the average number of collisions due to the bad hash function equals the average number of items from each equivalence class in each hash table.

Otherwise, you calculate hash values for the items in each equivalence class. You define overlapping groups for each equivalence class, such that you can calculate which groups any value x belongs to, and such that only values belonging to the same group can be equal (If you know nothing more about the equality operator, then you have only one group). To calculate the hash value of x, you must either find an x' = x whose hash value has already been calculated, or assign a new hash value to x and remember it. To do this, you calculate which groups x belongs to, and compare it against all values belonging to any of those groups. You now have a good hash function that doesn't cause collisions. The complexity of calculating the hash code of a previously unhashed x is proportional to the number of previously hashed values belonging to any of the groups that x belongs to. For previously hashed values, you may be able to change the order of lookups if the same values are hashed repeatedly.
> 0 votes

---
Tags: time-complexity, hash, hash-tables, hashing, c++
---


# Question
Title: Complexity of finding 7th smallest element in a min-heap?
I don't know if it's allowed to traverse nodes in a min-heap.

Because, if traversal is allowed then for finding $7^{th}$ smallest element, only a constant number of nodes need to be checked, thus giving the complexity of $\Theta(1)$.

But if traversing is not allowed, then for finding $7^{th}$ smallest element, I'll need to call `extract_min()` 6 times, leading to a complexity of $\Theta(\log n)$, which I think should be correct, but not sure.

My understanding is, if I'm traversing, then it's not a min-heap, it will be an augmented min-heap. Is it correct?

# Answer
> 0 votes
If you had a "black-box" min heap where the only operations available to you are adding elements and extracting (reading and simultaneously removing) the smallest item, then the time complexity is O (n) obviously.

It is imaginable that you have a specific implementation where even finding the second smallest element cannot be done in constant time. You might have in your data structure O (log n) items that *might* be the second smallest, and the O (log n) operation to remove the smallest item will also determine the second largest. I find it hard to describe an algorithm that works that way, but I'm sure it's possible.

The way a min-heap is usually implemented (or the way it is implemented if I had to implement it, or the way it is implemented in a random text book), finding the 7th smallest element can be done in constant time.

---
Tags: data-structures, time-complexity
---


# Question
Title: Is Half - Palindrome subset of a context-free language context-free?
Suppose we have $L$ being a context-free language. Let $L'=\\{x \in \Sigma^\* | xx^R \in L \\}$, is $L'$ context-free as well? I know that if $L$ is regular then $L'$ is regular as well by constructing a DFA. Is it possible to create a PDA here as well? I am stuck on this or even if there is a counter example?

# Answer
Let $L=\\{a^n b^n c^m d d c^k b^k a^m\\}$, then $L$ is context-free. I claim $L'=\\{a^n b^n c^n d\\}$ which is not context-free.

Suppose $x\in L'$. Then $x$ must be of the form $a^i b^j c^k d$. Then $x x^R = a^i b^j c^k d d c^k b^j a^i \in L$, which means that $i=j=k$. Conversely, it's clear that $\\{a^n b^n c^n d\\} \subseteq L'$.
> 4 votes

---
Tags: formal-languages, automata, regular-languages, context-free, pushdown-automata
---


title: Knapsack up to the heaviest item

text:
# Question
Title: Knapsack up to the heaviest item
There are $n$ items with weights $w\_1,\ldots,w\_n$ and values $v\_1,\ldots,v\_n$. There is a knapsack with capacity $W$. A subset of items is called *feasible up to heaviest item* if, once the heaviest item is removed from the subset, the weight of the remaining set is at most $W$. The *knapsack up to heaviest item* problem is to find a subset that maximizes the total value subject to being feasible up to one item.

I was trying to solve this problem, and I think I found that it is NP-hard - by reduction to standard knapsack problem. Given a standard knapsack problem, construct a knapsack-up-to-heaviest-item problem as follows.

* There are $n+1$ items: the $n$ items in the original problem, plus one "big item".
* The big item has value $v\_B \> \sum\_{i=1}^n v\_i$ and weight $w\_B \> \sum\_{i=1}^n w\_i$.
* The size of the new knapsack is $W+w\_B$.

In the new problem, any optimal solution must contain the big item, since if it does not contain the big item, the sum of weights in the knapsack is less than $W+w\_B$, so the big item can be added and the solution is still feasible. Moreover, in any optimal solution, the heaviest item is the big item. Hence, once the big item is in the knapsack, the problem is equivalent to the original knapsack problem.

My questions:

* Has this problems been studied before?
* Is my hardness proof correct?

# Answer
> 2 votes
The problem (are there items such that all except the largest fit, and the total value is ≥ V) is obviously in NP. It is also NP complete because we can use it to solve Knapsack:

Given a knapsack problem, add an item with sufficiently large weight w, and sufficiently large value v, solve the problem with V + v, and the solution with the large item removed is the solution for the knapsack problem.

We can also solve this problem using knapsack: For each item with weight w and value v, solve knapsack removing this item and all items with weight \> w and a goal for the value of V - v.

---
Tags: reference-request, np-hard, knapsack-problems
---


# Question
Title: Is the power of a natural number logspace-computable?
Given a constant $n\in\mathbb{N}\_+$, is the simple power function $$ λ\\,x\in\mathbb{N}\_+.\\,x^n $$ logspace computable by a logspace transducer (which has a read-only input tape, a working read-write tape (on which the transducer is allowed to use $\mathcal{O}(\log (\text{input size}))$) cells, and a write-only output tape), assuming that the input and the output are in binary? (It is not even clear to me how to do it for $n=2$ in logspace.) Any ideas or references?

# Answer
> 0 votes
Yes, iterated multiplication is even in uniform TC0:

Hesse, William; Allender, Eric; Mix Barrington, David (2002). "Uniform constant-depth threshold circuits for division and iterated multiplication". Journal of Computer and System Sciences. 65: 695–716. doi:10.1016/S0022-0000(02)00025-9.

Explanation: We have TC0 ⊆ NC1 ⊆ L, where TC0 denotes the class of Boolean circuits with constant depth and polynomial size, where unbounded fan-in threshold gates are allowed, NC1 denotes the class of Boolean circuits with logarithmic depth and polynomial size, and L denotes logspace.

---
Tags: space-complexity, transducers
---


# Question
Title: How do I call a system like a grammar, but where a rule has to be applied to all matches at once?
For example, given rules $\\{ a \to x, a \to y \\}$ and input $aa$ , I am usually allowed to derive strings $\\{ xx, xy, yx, yy \\}$. I would like to restrict this to only performing *"consistent"* rewrites, so that the language would be like $\\{ xx, yy \\}$. It is evidently possible to synchronize rewrites in distant parts of a sentence within the usual formal grammar setting, but I wonder if this possibility is better explored under a different name or in a different arrangement.

I notice that context-sensitive grammars pose trouble with this *"consistency"* condition. For example, given a ruleset $\\{ aa \to x\\}$ and initial string $aaa$, I am not sure if I should allow anything to be derived. Then again, it is entirely possible that only *some* rules, and specifically some context-free rules, may be enhanced with consistency.

I am rather sure the system I have in mind *defines a language*, and even that I could with some thinking propose a formal way to rewrite a given grammar so that some select context free rules are made consistent. But I wonder if this is actually widely known under some other name.

# Answer
> 3 votes
Usually, grammar systems where the rules have to be applied in parallel, are called L systems, after the theoretical biologist Aristid Lindenmayer who observed that development in plants must change cells in parallel.

The first example at wikipedia has rules : (A → AB), (B → A), and the string (= line of cells) develop as follows: A → AB → ABA → ABAAB → ABAABABA → ...

Note that in replacing the letters we actually apply a string homomorphism. I think that formally such a system is called D0L-system, with 0 (for zero) to indicate the rules are applied in a context-free manner, i.e., without looking at the neighbours, and D for determinism, in the sense that the mapping applied is a homomorphism, and not a finite substitution.

If one wants to choose between different homomorphisms at various steps of the derivation, we can choose between different homomorphisms. Such a system is usually called DT0L-system, where the T is for tabled: each homomorphism is a table to choose from.

The first DT0L example I could online find, is from the article *L Systems* by Kari, Rozenberg and Salomaa. Its tables are Td = \[a → b, b → bb, c → a\] and Tn = \[a → c, b → ac, c → c\]. In each step we can choose between the two tables.

Starting with a we get b (in both cases) then bb or ac, then bbbb, acac, ba, cc, then b$^8$, acacacac, baba, cccc, bbb, acc, aa and then cc (but that was already generated). Und so weiter und so fort.

PS. An homomorphism (in language theory) is specified as a letter to string mapping, like \[a → c, b → ac, c → bb\], and then extended to strings, following the mapping letter-by-letter, so aabac → ccaccbb. A finite substitution axtends this by allowing choice in each of the images of the letters, then a letter (and consequently a string) is mapped to a set of strings. Example \[a → aa,c ; b → ε,ac,bb\]. Now aba maps to the set aaaa, aac, caa, cc, aaacaa, aaacc, cacaa, cacc, aaabba, aabbc, cbbaa, cbbc. I think.

---
Tags: formal-languages, formal-grammars
---


# Question
Title: Examples of simple/common problems with quadratic running time
Are there some examples of simple or common problems which have (in a practical sense) quadratic complexity? I would have thought there were a lot of them, but upon further investigation, I can't seem to find any. (see https://en.wikipedia.org/wiki/Computational\_complexity\_of\_mathematical\_operations)

* Bubble sort / insertion sort are $O(n^2)$ worst-case, but there are tons of simple $O(n \log n)$ sort algorithms
* Multiplication of $n$-bit numbers is $O(n^2)$ for the conventional method, but then you have Karatsuba multiplication which is $O(n^{log\_2 3} \approx n^{1.58})$
* Matrix multiplication is $O(n^3)$ for conventional implementation but in the $O(n^{2.376})$ to $O(n^{2.807})$ range for more clever implementations
* Fast Fourier Transform is $O(n \log n)$ instead of the simple $O(n^2)$ DFT
* Dijkstra's algorithm was $O(|V|^2)$ but someone thought of a $O(|E|+|V| \log |V|)$ implementation

# Answer
It is true that many algorithms that have quadratic running time are not the state of the art for their problems today. Among which are quadratic sorting algorithms for example bubble-sort, select-sort and insertion-sort, which are overcome by merge-sort and heap-sort. On a side note, quick-sort, the standard sorting algorithm in different areas, has a worst running time of $O(n^2)$ and is only used because the probability of having bad running time (say worse than a constant factor of $O(n \log n)$ is very small and it has smaller overhead than the other efficient sorting algorithms).

Also solving maximum matching on bipartite graphs by reducing to maximum flow and solving with Ford and Fulkerson's method is $O(nm)$ which is quadratic in sparse graphs, which is again overcome by the algorithm from Hopcroft and Karp with running time $O(\sqrt n m)$.

However, some of the problems with quadratic running time are conjectured to be optimal up to a log factor. These problems are not only interesting because of their quadratic running time and that this time is probably optimal, but also because they lead a list of problems that are either as hard or strictly harder than them.

## The 3-sum problem

* **The problem.** Given a set of $n$ integers, find if 3 of them add up to zero.
* **Quadratic algorithm.** Sort the values in the list. For each value $v$ in the list, look if there are two values summing up to $-v$. Such a search can be done in $O(n)$ in sorted array using sliding window technique. Since we do it for every element in the list we get a running time of $O(n \log n + n^2) = O(n^2)$. Note that the $n \log n$ is for sorting the array as a pre-processing step.
* **Similar problems.** The problem has many variants that are equivalent in a sense that have the same running time. Including the version of the problem where repetitions are not allowed or the version where you get three sets of values and you have to choose a value form list to sum up to zero (or to some value $v$). More Interesting are the reductions from the 3-sum problem variants to different Geometry problems as checking a point-set in the plane if three are co-linear. This problem is solvable in quadratic time using the point/line dual construction and is also expected to be optimal by the 3-sum conjecture. Another example is the Geombase problem, where you have a set of points each lying on one of the lines $y=0;y =1$ or $y=2$ and you need to find if there is a non horizontal line crossing three of the points. This problem is also equivalent to three sum in the sense that the reduction can be done in both directions. Similarly, the problem given a set of $n$ lines, do three of them intersect in one point is almost optimal in $O(n^2)$ if 3-sum conjecture is true.

---

## The orthogonal vectors problem.

* **The problem.** Given a set of $n$ vectors of dimension $d$, are two of them orthogonal.
* **The algorithm.** For constant values of $d$, checking all pairs of vectors is in $O(d n^2) = O(n^2)$.
* **Similar problems.** Based on this conjecture, the following problems are almost optimal with a running time of $O(n^2)$. Edit distance, longest common subsequence and graph diameter in sparse graphs.

Here is a brief description for each of these problems:

* Edit distance: Given two strings, what is the least number of modifications (deletions, insertions..) are needed to make the strings equal. The problem can be generalized to a set of operations on both or one of the strings and cost for each operation and we want to minimize the total cost.
* Longest common subsequence: Given two strings, a subsequence of the string is a string resulting from the original string by deleting some characters. What is the longest string that is a subsequence of both input strings (Note that this problem is a special case of edit distance.
* Graph diameter is the longest shortest path in the graph, that means the minimum $d$ such that you can go from any node to any other node in less than $d$ steps.

**Note** there is a reduction from SAT to Orthogonal vectors proving that if the Orthogonal vectors conjecture fails, then SETH fails as well.
> 11 votes

---
Tags: complexity-theory, time-complexity
---


# Question
Title: Designing a PDA that keeps track of the stack size
Would it be possible/legal to design a PDA that can use the stack as a way to keep track of the number of inputs seen? (i.e the size of the stack would act as some sort of counter).

What I was thinking:

1. First transition would require you to push a "1" to the stack
2. All future transitions would require you to pop the top of the stack (let's call this $x$) and push $x+1$ onto it.

The language of the stack would be the set of all natural numbers excluding 0.

I'm having trouble understanding whether the "push $x+1$" move would work

# Answer
> 2 votes
Note that in your model, you only ever have a single item $x$ on the stack, namely the current number of inputs seen. Thus, you're not really using the stack.

This is sometimes called a *register*, and there are models called register machines, or sometimes *cost register automata*, introduced by Alur in 2011.

The power of this model, and certain algorithmic properties of it, depend on what you allow to do with the register. If you allow reading it's value and comparing it to e.g. 0, then very quickly things become undecidable. But if you only allow simpler things, you get all kinds of interesting models.

---
Tags: computability, automata
---


# Question
Title: Showing that $n\log n - n$ is $\Omega(n)$
Prove that $n\log{n} − n$ is $\Omega(n)$.

I do know the answer:

$\log{n} ≥ 2, \forall n \ge 4$.

Thus, $n\log{n}−n\ge n ,\forall n\ge 4 \implies n \log n − n ∈ Ω(n)$.

But can someone please explain how its done. where did $2$, $\forall n$ and $4$ came from. Then how was $n, \forall n \ge 4$ added.

# Answer
> 3 votes
According to the definition of big Omega, in order to show that $n\log n - n = \Omega(n)$, we need to come up with $n\_0$ and $c$ such that all $n \geq n\_0$ satisfy $n\log n - n \ge cn$.

Let us assume that the logarithm is to base 2. When $n \geq 4$, we have $\log n \geq \log 4 = 2$, and so $n\log n - n \geq 2n - n = n$. Therefore we can take $n\_0 = 4$ and $c = 1$ and satisfy the requirements for $n\log n - n = \Omega(n)$.

The choice of $4$ is arbitrary — any $n\_0 \> 2$ would work (for an appropriate value of $c$).

---
Tags: asymptotics
---


title: Question about machine epsilon

text:
# Question
Title: Question about machine epsilon
I am studying over my notes, and there is something I don't understand about $e\_m$. We represent the floating point numbers as $1.d\_1d\_2...d\_t \times \beta^e$. Now, my professor defines $\epsilon\_m$ as the smallest $x$ such that $fl(1+x) \> 1$. But then she writes

$$\epsilon\_m = \beta^{1-t} \hspace{1cm} \text{ (for "chopping")}$$ and

$$e\_m = \dfrac 12 \beta^{1-t} \hspace{1cm} \text{ (for rounding)}$$ However, I think these should be $\beta^{-t}$ and $\dfrac 12 \beta^{-t}$, respectively.

The number $1$, and the next number right after, are

$$1.00 \cdots 00 \times \beta^0$$ and $$1.00 \cdots 01 \times \beta^0$$ where the $1$ is in the $t^{th}$ decimal place. Therefore their difference is $\beta^{-t}$ so if $x = \beta^{-t}$, then $1+x$ is itself a floating point number, so $fl(1+x) = 1+x\>1$.

Am I wrong, or are the notes wrong?

Thank you very much.

# Answer
> 1 votes
There is a huge discrepancy in your notes. Either you assume that you are using base 2, in which case there should be no beta introduced, but just the number 2 used. Or you don't assume that you are using base 2, but for example base 10, then the number before the decimal point can't be forced to be 1 (or you could only represent 1 ≤ x \< 2, 10 ≤ x \< 20, 100 ≤ x \< 200 etc. which would be obviously nonsense).

In base two, following your notes, the smallest floating point number ≥ 1 is $1 + 2^{-t}$. When "cutting off" (rounding down), the smallest x such that fl(1 + x) = 1 is x = $2^{-t}$.

When "rounding" (round to nearest), with x \< $2^{-t-1}$ 1 + x will be rounded down to 0. With $2^{-t-1}$ \< x \< $1.5 \cdot 2^{-t-1}$ 1+x will be rounded to $1 + 2^{-t}$. The tricky one is x = $2^{-t-1}$. With IEEE 754 rules, the rounding mode is "round to nearest even" which means that if a number is exactly halfway between two floating point numbers, it is rounded to the number where the lowest mantissa bit is even, in this case rounded to 1. So the "machine epsilon" as defined would be slightly larger than $2^{-t-1}$. Or undefined, because there is no smallest x.

Instead of "machine epsilon" you will find more often the term "ulp" (unit in lowest position), which is the value of the lowest mantissa bit of the number 1, or ulp(x) which is the value of the lowest mantissa bit of the number x. The huge advantage is that the definition doesn't depend on the rounding mode.

# Answer
> 1 votes
There is definitely an inconsistency in what you've written here. My guess is that $t$ doesn't mean what you think it means. You are using it here to describe the size of the significand field, that is, the number of digits after the radix point. (It's not a decimal point in general!)

My guess is that your lecturer is using it to refer to the *precision*. The precision of the floating point format includes the implicit $1$. That is, your floating point number is:

$d\_1.d\_2 d\_3 d\_4 \ldots d\_t \times \beta^e$

where $d\_1$ is always $1$. If you interpret $t$ that way, the two epsilons make more sense.

This is the way that the IEEE-754 standard defines these constants. For example, a binary32 (formerly called "single precision") floating point number has a precision of 24 bits, in that the mantissa is 24 bits. However, the significand field is only 23 bits, because the leading one bit is implicit.

---
Tags: floating-point
---


title: Finding the hidden treasure

text:
# Question
Title: Finding the hidden treasure
Let's assume I am trying to find a hidden treasure.

The treasure is hidden at an uknown position x. We know that the position x of the treasure is somewhere on the integer axis (in other words x is an integer). In order to find the treasure I have to take with me a detector. The detector can spot the treasure only if it is above it.

My starting position is the 0 point and I can move back and front until I cross the treasure, so that my detector can track it. I am always moving on the integer line. Which is the most efficient way to move through the axis in order to track the treasure?? I have to find an algorithm that allows me to find the treasure by covering a distance $O(|x|)$

**My approach**: After some consideration, I think that the most efficient way to find the treasure is the following: Starting from 0 I move front until I reach number $2$. Then I move back until I reach number $-2^2$. Then I move front until I reach number $2^3$. Then I go back again until I reach number $-2^4$ and so on...

However, I am having difficulties on proving that there is a constant $c$ (for which I have to calculate an upper bound) so that my algorithm is going to help me find the treasure at $c |x|$ moves at most. Any help is much appreciated! Thanks in advance!

P.S. I am new at the computer science stack exchange so I am not sure about the tags. Correct them or add more if necessary.

# Answer
Your problem is known variously as the *lost cow problem* or the *cow-path problem*, and is a standard example in online algorithms. The algorithm you describe is 9-competitive, which is optimal for deterministic algorithms. For randomized algorithms the competitive ratio is roughly 4.6. See for example a writeup apparently by Rudolf Fleischer.
> 4 votes

# Answer
I will suggest a similar strategy. Note that your strategy yields a constant factor better than the one presented here but the proof is more technical.

Let us divide the strategy in rounds $1, 2, \dots$, where in round $i$ we go $2^{i-1}$ steps to the right, then we go back to the center and we repeat the exact same to the left. This means we go one step to the right then back to the middle and one to the left and back again then two to the right and two to the left then 4 to the right and so on. The total number of steps is upper bounded by

$$4\sum\limits\_{i=0}^{\left\lceil \log x\right\rceil} 2^i$$ $$\leq 4 \sum\limits\_{i=0}^{\log x + 1} 2^i$$ $$\leq 4\sum\limits\_{i=0}^{\log (2x)} 2^i$$ $$\leq 4 \cdot 2^{\log(2x)+1}$$ $$= 4\cdot 2^{\log(4x)}$$ $$= 16x,$$ where the factor 4 in the first line means going to the right $2^i$ steps then back to the center and repeating on the left side.
> 2 votes

# Answer
Your approach is correct. Without loss of generality, suppose that $2^{2n-1} \< x \le 2^{2n+1}$. Now, if you count the number of steps needed to find $x$ with your algorithm, you'll find out that it contains the sum of geometric progression which can be bounded by $2^{2n+3} = 16\cdot 2^{2n-1} = O(x)$ since $2^{2n-1} \< x$.
> 0 votes

---
Tags: algorithms, time-complexity, online-algorithms, upper-bound
---


title: Quantum Supremacy Task

text:
# Question
Title: Quantum Supremacy Task
I’m trying to understand the task performed by Google’s Sycamore that recently achieved alleged Quantum Supremacy. I’ve read the paper in Nature but the actual task that would have taken 10,000 years to compete is over my head. Is anyone able to explain it in simpler terms?

# Answer
> 19 votes
First of all it seems that *google* has exaggerated a little bit by shooting the $10000$ years results. It seems that *IBM*, on his current and most powerful classic super computer, is able to perform the same task in $2.5$ days, saving the entire search space (*Hilbert space*) on a *$250$ petabytes* hard drive. This does not mean that *googl*e's result is not to be taken into consideration: it is definitely a milestone but it will not change the world as many claim, it will not provide us with stable and multipurpose quantum computers within a year or two ( to tell the truth, with current technologies it is not even practically possible to get computers with enough *qbits* and keep them in a consistent state).

Having made this premise, we come to the experiment:

Essentially (and in simple terms, very simple terms) what they did was to correctly sample from the possible outputs of a $53$ *qbits* random quantum circuit using a statistical test called linear cross-entropy benchmark and sampling about $5000000$ results in about $200$ seconds. The test was a stochastic triumph.

***Some notes***:

1. people (outside the discipline) are going crazy blathering of a proof of $P = NP$ or $BQP = BPP$ and then some... All these things are false, none of these important open problems have been solved by the experiment.
2. The real importance of having scalable quantum computers lies in being able to perform simulations of physical systems efficiently, which entails dramatic results in the industrial field: desig of new medicines, design of new materials, etc.
3. Quantum computers will not spell the end of cryptography: not all cryptographic methods can be efficiently cracked by a quantum computation and, in addition, we already know post-quantum cryptographic techniques: for example lattice cryptography.

# Answer
> 13 votes
The task performed by the Sycamore computer was meaningless. The output of the computation is essentially a random number.

So why does anyone care about it? On a very simple level, quantum computers are essentially random number generators. However, they do not generate uniform random numbers. With a properly designed algorithm, we can make certain outputs much more likely than others. The end result is usually that with high probability, the output is a useful number. For example, Shor's algorithm uses a quantum subroutine that with high probability gives a number that helps us find the prime factorization of a number.

Most quantum computations start out with a vector of qubits initialized to random, independent superpositions. This means that any bitstring is equally likely as output.

The "computation" a quantum computer does is to manipulate this random superposition, and to get certain qubits to interact with each other in certain ways, so as to manipulate the output distribution and increase the probability of getting the numbers we care about. This computation is encoded in a *quantum circuit*.

Now the computation Google did used a random circuit. They took some quantum gates and connected them together more-or-less arbitrarily. Why did they do this? Why did they not take a meaningful circuit (e.g. that for Shor's algorithm) and compute the outcome of that instead?

The reason is that their computer is too small to build a meaningful circuit. Had they implemented Shor's algorithm, they could only have used it to factor some very small numbers. This would not have demonstrated quantum supremacy because numbers that small could easily have been factored on a normal computer.

Instead, they chose a random circuit. Nobody understands what the circuit does, so nobody can cheat on a classical computer by exploiting knowledge about what the circuit computes. The only way to get the same output that Google did clasically, is to simulate the computation done by the quantum computer.

What Google computed is meaningless: The computation was specifically designed to be easy on a quantum computer and hard on a classical computer. The result has no intrinsic meaning, and it is purely meant to show off their quantum capabilities.

However, it is still a huge step forward: they showed, for the first time, a quantum computer able to evaluate an arbitrary quantum circuit *and* compute a result that cannot be computed classically. Even if the outcome of the computation is essentially meaningless, the fact they were able to obtain it at all is still very impressive.

---
Tags: algorithms, quantum-computing
---


# Question
Title: What are the vertical and horizontal focal lengths?
In this paper,

http://www.vision.caltech.edu/malaa/publications/aly08realtime.pdf

the author mentioned "the vertical and horizontal focal lengths" but didn't have any clear definition.

My understanding about "focal length" is the distance between the lens and the image plane.

Does anyone have the idea about these focal lengths?

Thank you.

# Answer
Note that they assume a pinhole camera model. The term 'focal length' means something different here than it does with a lens camera.

All you ever really need to know about the pinhole camera model can be expressed as: $$x\_\mbox{imageplane} := x\_\mbox{world}/z\_\mbox{world}$$ $$y\_\mbox{imageplane} := y\_\mbox{world}/z\_\mbox{world}$$ This describes how points in the scene project to an image plane 1 unit in front of the camera origin (center of projection & center of world coordinate system), with the optical axis along the z direction.

All the other values usually discussed in connection with pinhole cameras 'just' describe which rectangular part of the image plane is mapped to the rectangle of pixels that is your image. Or, conversely, how pixel coordinates can be transformed back into points on the image plane (and from there, can be transformed to directions in the scene).

Of course this rectangle-on-a-2d-plane can be defined by a 2d point $b$ and two 2d vectors $v\_1, v\_2$ such that:

$$\begin{bmatrix}x\_\mbox{image}\\y\_\mbox{image}\end{bmatrix} := \begin{bmatrix}\vec{v\_1}&\vec{v\_2}\end{bmatrix} \begin{bmatrix}x\_\mbox{imageplane}\\y\_\mbox{imageplane}\end{bmatrix} + b$$ If we abbreviate this as $(x\_\mbox{image},y\_\mbox{image}) = f(x\_\mbox{imageplane},y\_\mbox{imageplane})$ the part of the imageplane that your image depicts is the set $f^{-1}(\[0,\mbox{width}\]\times\[0,\mbox{height}\])$ which, as I said, is a rectangle1.

The 'other values', for example:

* optical center: $c\_x, c\_y$ or $c\_u, c\_v$
* horizontal and vertical 'focal length': $f\_x, f\_y$ or $f\_u, f\_v$
* aspect ratio
* field of view angle $\alpha$
* shear (you don't usually want that)

are just used to describe special cases of the above formula.

In your case, $b = (c\_u, c\_v)$ and $v\_1 = (f\_u,0), v\_2 = (0,f\_v)$ such that

$$\begin{bmatrix}x\_\mbox{image}\\y\_\mbox{image}\end{bmatrix} := \begin{bmatrix}f\_u x\_\mbox{imageplane} + c\_u\\f\_v y\_\mbox{imageplane} + c\_v\end{bmatrix} $$

---

1 Note that it is not the rectangle with corners $b, b+v\_1,b+v\_2,b+v\_1+v\_2$. To find it you'd have to compute the inverse of the function $f$.
> 4 votes

# Answer
In pinhole camera model, to measure the corresponding position of 3D real point on the image plane, pixel will be used as unit (not physical distance like millimeter or meter) and so pixel size may differ in x- & y-directions (there may also be skew or offset too).

$$x\_{image} = \phi\_x \frac{u}{w}$$

$$x\_{image} = \phi\_y \frac{v}{w}$$

Where $\[u, v, w\]^T$ are coordinates of a point in 3D (origin is the optical center) and $\phi\_x$ and $\phi\_y$ are separate scaling factors for x- & y-directions for pixels. These parameters are known as the **focal length parameters** in x- and y-direction which are misleading because the focal length can be also expressed in pixels (instead of mm).
> 2 votes

---
Tags: computer-vision
---