# Question
Title: How does the use of oracle Turing machines not lead to contradictions?
How can we ensure that we are continuing to make sound and valid statements about complexity classes when using oracle Turing Machines? According to my understanding (based on the definitions given in introductory textbooks on the subject) oracle Turing machines can determine the membership status of a string with respect to an oracle language in one computation step. However the oracle languages often used are provably impossible to solve in constant time (take an EXPTIME-complete oracle, for example). To me this seems like "opening the door" to contradictions and after all, anything follows from a contradiction.

# Answer
There's a number of ways to look at this.

One is that in proofs, implication is kind of like a function, that takes as input a proof of something, and outputs a proof of something else.

We can write functions that operate on values that we don't have.

For example, let's consider the halting number $h$, which is not computable. I can write the function

$haltingPlusOne : \\{h \\} \rightarrow \mathbb{N}$

$haltingPlusOne(x) = x + 1$.

This function takes as input the Halting number, and returns the Halting number plus one. Clearly this is a well defined function: if we give it the right input, it gives the right output. The fact that we can't find the right input doesn't make it any less valid of a transformation.

I see proofs with oracles as similar. They're basically functions which say, give me a Turing machine that solves problem $X$, and I'll give as output a proof of some theorem.

It's also important to realize that when we say something like "There is no Turing Machine that can decide the halting problem," that is saying that, there's no TM matching the standard definition of a TM that decides the halting problem.

An oracle is basically saying "Assume we have a TM that matches the normal definition except also assuming we can solve some problem". So there's no contradiction, since we're not assuming there's a normal TM accepting the problem, we're assuming there's a special TM accepting the problem.

In a very informal analogy, think of it like this. If I can prove to you that no humans without superpowers can fly, there's no contradiction saying that there's a superhero that can fly.

These oracles are purely logical objects. We don't know how to build physical machines that emulate them, the way we can with Turing machines, but as far as we know, there's no inherent contradiction between their definitions and our basic axioms. As logical objects, these oracles do exist. We know they're not standard Turing Machines or Lambda-Calculus terms or Partial-recursive functions. The Church-Turing thesis says that there's no more powerful model, but it's not a theorem, it's just a conjecture, and is too informal to ever really be proved.
> 8 votes

# Answer
Well, I would say that it is an essential feature of oracle TM that they have access to an oracle that is hard to solve. If you can decide the oracle $A$ in constant time, then for every class $B$ you would have $B=B^A$. So why to have the oracle at all in this case?

So what is the point in using a oracle TM then? I would say it allows us mainly theoretical considerations about the (degree of) hardness of problems. The oracle can even be undecidable. In this case you can define a whole hierarchy of undecidable problems (Turing degree). Of course, if your oracle is the halting problem you cannot convert your oracle TM into a traditional TM.

The oracle TM concept also is important to define a strong form of reductions (Turing reductions).

Note that the more theoretical motivation of oracle TM can have implications outside of the *oracle world*. You maybe know the famous $\sf P$ vs $\sf NP$ relativizing result.

As a last remark note that in order to query the oracle you have to write the query string $w$ first on the oracle tape. Thus, you cannot decide the membership in constant time, but in time $|w|$.
> 2 votes

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


# Question
Title: Supporting queries for finding how many intervals in a dynamic set of 1D intervals contain a given point
You want to create a data structure that can store 1 dimensional intervals and also support the query for finding the total amount of intervals intersecting a given point.

One solution would be for each query to scan through every interval and see if it is contained in this interval or not, this would give us `O(amountOfQueries*n)` time.

I'm not sure how you would achieve better bounds for these queries with interval trees. In these trees every node is an interval but it also contains the maximum end point of the set of all intervals in the right sub tree.

If for each query you decide to search for all intervals that contain it in this interval tree, then you can still get the `O(n)` time if all intervals contain this point.

So, how can interval trees help in this case?

# Answer
I think I have an algorithm but I'm not sure if it's correct.

We want to maintain an augmented binary search tree $S$ on each interval end point. The splitting element will always be the median end point so that the total height of our tree in the end is in the order of $\log\_{2}N$.

In every node we use some data structure to store all intervals that go through the splitting element.

Assuming nothing more for our data structure, we can see that if $x\_q$ is the query point, every time we visit a node we check to see if $x\_{q}$ is to the right or to the left of the splitting element. If it is to the left, then no interval stored in any node of the right subtree will intersect $x\_{q}$ so we will only need to check the left sub tree. The same applies to the case where $x\_{q}$ is to the right of the splitting element.

So far we can find all relevant intervals in $O(\log n)$ time, but to find the exact intervals that intersect $x\_{q}$, we have to see what's going on in this structure that we have for every node, so we also have to query each such structure along a root to leaf path to find exactly the intervals that intersect $x\_{q}$

To do this, we can have two sorted lists $L$, $R$ on every node, each list will store the same intervals but $L$ will store them in a sorted order according to the left point and $R$ according to the right point.

Then whenever we visit a node we see if $x\_{q}$ is to the left of the splitting element. If that's the case, we do a binary search on $L$ to find the right most interval that contains this point, since we know the index of this interval in $L$ we can find the total amount of intervals.

We process similarly $R$ if $x\_{q}$ is to the right of the splitting element.

This algorithm will give us a $O(\log ^2 N)$ complexity.
> 0 votes

---
Tags: data-structures, search-trees, intervals
---


# Question
Title: Confusion about the Time Hierarchy Theorem and relativization
I know that $\mathsf{P}^A = \mathsf{EXP}$ for any $\mathsf{EXPTIME}$-complete language $A$.

Is it true that $\mathsf{DTIME}^A(n^k) = \mathsf{EXP}$ for any fixed $k$ and any $\mathsf{EXPTIME}$-complete oracle $A$?
If not, what do these complexity classes equal and why?

I am just confused because then it seems to me that we would then have $\mathsf{DTIME}^A(n^k) = \mathsf{DTIME}^A(n^j)$ for $k \< j$ and this would contradict the fact that the Time Hierarchy Theorem holds under any oracle.

# Answer
> 8 votes
It is **not true** that for $A$ being $\sf EXP$-complete ${\sf DTIME}^A(n^k) = {\sf EXP}$, but you are right with ${\sf P}^A={\sf EXP}$.

Here is the reason for this. In order to make use of the oracle you have to transform your problem via a reduction. This reduction is a *polynomial* reduction. The running time of this particular reduction might need $\omega(n^k)$ steps. In this case you cannot use the oracle in the desired way.

As you already observed ${\sf DTIME}^A(n^k) \neq {\sf EXP}$ because this would imply for all $k,j$ that ${\sf DTIME}^A(n^k)={\sf DTIME}^A(n^j)$, which cannot be true since the time hierarchy theorem relativizes.

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


# Question
Title: How do you represent basic arithmetic using boolean function?
Say you have an arithmetic problem involving two variables, how do you give a Boolean formula for that using standard techniques so that one gets a minimal formula for a given number of quantifiers?

Consider for example a function that decides if $(1)$ $x\>y$ or $(2)$ a function that decides $x|y$?

# Answer
> 1 votes
Hint: Use the standard reduction from CircuitSAT to SAT. Equivalently: Use the Tseitin transform.

I assume you do know how to write a boolean circuit to test whether $x\>y$. If not, consult a textbook.

---
Tags: arithmetic, boolean-algebra
---


# Question
Title: Direct Cache Mapping - Determine Tag Size
In the following direct cache map, there is a list of 32-bit memory address references, given as word addresses. I gathered that the index size is 3 bit and there is no offset.

However, I used 4 bits to determine the tag--is this correct? When does the tag bits change? How many bits are typically used?

```
Address  Binary Address   Tag       Index   H/M

3        00000011        0000        011    Miss
180      10110100        1011        100    Miss
43       00101011        0010        011    Miss
2        00000010        0000        010    Miss
191      10111111        1011        111    Miss
88       01011000        0101        000    Miss
190      10111110        1011        110    Miss
14       00001110        0000        110    Miss
181      10110101        1011        101    Miss
44       00101100        0010        100    Miss
186      10111010        1011        010    Miss
253      11111101        1111        101    Miss

```

# Answer
The tag should be all bits not used for index/offset; thus, you should use the top 5 bits, not just the top 4. To see why, let's look at an example direct-map cache with 8 lines, where memory addresses are given as word addresses (so there are no byte offset bits) with a block size of 1 word (so there are no block offset bits either).

Let's say the cache has the following state

```
idx        tag          data
000        10000        insert data here (not important)
001        10010
010        11001
011        01010
100        10010
101        01000
110        01010
111        01010

```

Now, I want to read the word at address `10011001`. The index is then `001`, and I compare the address's tag bits (the top 5; `10011`) to the tag of the address of the data in the cache at index `001` (`10010`), and discover that they don't match. We have a cache-miss and replace the block at index `001` with the data we retrieve from memory and then update the tag of that entry.

If we had instead used only the top 4 bits for the tag, then we would do the tag comparison and think that the data in the cache was from the correct address (`10011` and `10010` differ only by the bottom bit).

In general, a byte address is broken into the following pieces for the cache:

```
[        tag bits        ][   index bits   ][   block offset bits   ][   word offset bits   ]

```

The word offset bits indicate which byte within a word we want; there are 2 (to indicate which of the 4 bytes in the word; because you're dealing with **word** addresses, we don't need these).

The block offset bits indicate which word within a block we want; say 4 words are read into a cache-line, then we'd need 2 bits to indicate which word within the block we want. There are `log_2(cache_width)` of these generally. Because your cache has only one word per line, we don't need these either.

The index bits indicate which line of the cache we should look at. There are `log_2(lines)` of these necessary. Your cache has 8 lines, so we'll need 3 bits for the index (which will be the bottom 3).

Finally, the other remaining bits in the address are used for the tag, to differentiate between blocks in the cache that otherwise have the same index bits. Because in our example (and your problem), the addresses are 8 bits, then the remaining 'unclaimed' top 5 bits are used.
> 0 votes

---
Tags: computer-architecture, cpu-cache, memory-hardware
---


# Question
Title: are regular languages closed under division
I am trying to solve this question which appeared in previous exam paper

Can someone help me what i am failing to understand

For languages $A$ and $B$ define $A \div B = \\{x \in \Sigma^{\ast} : xy \in A \text{ for all } y \in B\\}$. If $R$ is regular and $L$ is any language, is it always the case that $R\div L$ is regular? Explain.

I am thinking as regular languages closed under right quotient hoping we can use the same proof here but I understand that in right quotient we prove it for any **$y$ that belongs to $B$ but for division it is for all $y$ in $B$** .

Also if I have $L\_1$ is regular and $L\_2$ is context-free, is $L\_1/L\_2$ Always regular? Always context-free but not always regular? Or not always context-free? Which one is true?

When $L\_1$ is context-free and $L\_2$ is regular, is $L\_1/L\_2$ always regular? Always context-free but not always regular? Or not always context-free?

Any ideas will really help me in preparing for my test.

# Answer
If $L\_1$ is regular and $L\_2$ is any language, then $L\_1 / L\_2$ is regular. In fact, the construction of a DFA for $L\_1 / L\_2$ is almost trivial (with one caveat): It's the same as the DFA for $L\_1$, except that the "final" states are the the states which can reach the original accepting states given a string from $L\_2$.

Suppose that $M\_1 = (Q, \Sigma, \delta, q\_0, F\_1)$ is the DFA which accepts $L\_1$. Then a DFA which accepts $L\_2$ is $M\_2 = (Q, \Sigma, \delta, q\_0, F\_2)$, where:

$$F\_2 = \left\\{ q \in Q : \exists x \in L\_2. \delta(q,x) \in F\_1 \right\\}$$

Now here's the caveat: this proof sketch is not constructive! To turn this into an algorithm requires some way to enumerate or recognise strings in $L\_2$, and remember, $L\_2$ can be *any* language.

If $L\_1$ is context free and $L\_2$ is regular, $L\_1 / L\_2$ is always context-free (proof left as an exercise), but it is not necessarily regular. (To see why, consider $L\_2 = \\{ \epsilon \\}$.)

**EDIT** I've just noticed that the definition in the question is different from the usual definition of "right quotient". The usual definition is:

$$A/B = \left\\{x\in \Sigma^{\*} : \exists y \in B. xy \in A\right\\}$$

The definition in the question is:

$$A\div B = \left\\{x\in \Sigma^{\*} : \forall y \in B. xy \in A\right\\}$$

My answer us for the usual definition, because these are standard results. The answers are similar for the definition in the question, except that the construction is slightly different. (See David Smith's comment.)

I suspect there is a typo in the original question.
> 2 votes

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


# Question
Title: Difference between edges in Depth First Trees
I have a directed graph, where each node has an alphabetical value. The graph is to be traversed with topological DFS by descending alphabetical values (Z-A).

The result is $M,N,P,O,Q,S,R,T$ (after reversing). Several DFS trees are created during this traversal, and it's the edges between the trees that confuse me. I understand how tree, back, forward and cross edges work in simpler graphs - but this one's harder.

For the example, with the graph

We have the next depth-first trees:

1. $T$
2. $S\rightarrow R$
3. $Q$
4. $P\rightarrow O$
5. $M$
6. $N$

And my question is regarding the edges that connect the trees.

Which are cross edges (like $O,R$), which are back edges and which are forward edges? And giving an example of when they are assigned as back edges / cross edges would be awesome.

# Answer
You could find a nicely description in CLRS 3ed Chapter 22.3. I extracted the next description from there. There are just four types of edge in a graph.

* **Tree edges** are edges in the depth-first forest $G\_\pi$. Edge $(u,v)$ is a tree edge if $v$ was first discovered by exploring edge $(u,v)$.
* **Back Edges** are those edges $(u,v)$ connecting a vertex $u$ to an ancestor $v$ in a depth-first tree. We consider self-loops, which may occur in directed graphs, to be back edges.
* **Forward Edges**: are those nontree edges $(u,v)$ connecting a vertex $u$ to a descendant $v$ in a depth-first tree.
* **Cross edges** are all other edges. They can go between vertices in the same depth-first tree, as long as one vertex is not an ancestor of the other, or the can go between vertices in different depth-first trees.

For that, because you're interested in depth-first forest ( graph contains all depth-first search trees) only two types of edges remain:

1. **Tree Edges**: edges with a first node without parents in the forest of depth first search trees $G\_\pi$
2. **Cross Edges**: edges inside depth-first trees with the description above, and those edges connecting those dfs-trees.
> 4 votes

# Answer
wikipedia has the good explaination about this.

> A convenient description of a depth first search of a graph is in terms of a spanning tree of the vertices reached during the search. Based on this spanning tree, the edges of the original graph can be divided into three classes: forward edges, which point from a node of the tree to one of its descendants, back edges, which point from a node to one of its ancestors, and cross edges, which do neither. Sometimes tree edges, edges which belong to the spanning tree itself, are classified separately from forward edges. If the original graph is undirected then all of its edges are tree edges or back edges.

The four types of edges defined by a spanning tree

In my opinion we use back & forward ages to make a fully spanning tree. In your graph N P M are Isolated nodes so to traverse these nodes we have to put back or forward ages (not sure about this).

See this answer you will get a clear picture.
> 3 votes

---
Tags: algorithms, graphs, terminology, graph-traversal
---


# Question
Title: Why is And-Or-Graph-Search called a search algorithm?
An algorithm in *Artificial Intelligence: A Modern Approach* for planning in stochastic, fully observable environments is called And-Or-Graph-Search, implying that it's a search algorithm. However, I don't see how it is one. Wikipedia defines search algorithms as, "an algorithm for finding an item with specified properties among a collection of items," but And-Or-Graph-Search doesn't do that. It instead finds multiple items (goals states) in order to guarantee it will reach a goal state no matter what the results of its stochastic actions are.

So, why is it a search algorithm?

Here's its pseudo-code:

```

function AndOrGraphSearch(problem) returns a conditional plan, or failure
    OrSearch(problem.initialState, problem, [])
function OrSearch(state, problem, path) returns a conditional plan, or failure
    if problem.GoalTest(state) then return the empty plan
    if state is on path then return failure
    for each action in problem.Actions(state) do
        plan = AndSearch(Results(state, action), problem, [state | path])
        if plan does not = failure then return [action | plan]
    return failure

function AndSearch(states, problem, path) return a conditional plan, or failure
    for each si in states do
        plani = OrSearch(si, problem, path)
        if plan = failure then return failure
    return [if si then plani else if s2 then plan2 else . . . if sn-1 then plann-1 else plann]

```

AndOrSearch is an algorithm for searching And-Or graphs generated by nondeterministic environments. It returns a conditional plan that reaches a goal state in all circumstances. (The notation \[x|l\] refers to the list formed by adding the object x to the front of list l.)

The function is from the book Artificial Intelligence: A Modern Approach.

# Answer
> 1 votes
You can view And-Or Graph search as a search algorithm in two ways:

* As search in the state space: Here, the "items" from the Wikipedia definition are the states, and an "item with specified properties among a collection of items" is a goal state. With And-Or Graph search, finding one such item is generally not enough. Under this view, the definition on Wikipedia is a bit too narrow.
* As search in the space of partial conditional plans: Here, the "items" are partial conditional plans, and an "item with specified properties among a collection of items" is a total conditional plan, i.e., a partial conditional plan with the specified property that it is guaranteed to reach a goal state after a finite number of steps. Unlike a total conditional plan, a partial conditional plan may contain leaf nodes that are neither goal nodes nor have an associated action in the plan. Search steps in this search space are extensions of partial conditional plans by one action, i.e., these steps take a partial plan P and return a new partial plan P' that is like P, but with one non-goal leaf replaced by a valid action assignment to that leaf node.

Both views are legitimate, and the second one is perfectly consistent with the Wikipedia definition.

The analogous distinction in regular graph search would be between searching for a goal state and searching for a path to a goal state.

# Answer
> 0 votes
You are parsing Wikipedia's definition too closely. And-Or Graph Search is an algorithm. An algorithm is allowed to return, for instance, a list of data values. (If you want to get pedantic, a list *is* an item: it is a value of type `list`.)

---
Tags: terminology, artificial-intelligence, search-algorithms
---


title: Making a conjecture of a closed form

text:
# Question
Title: Making a conjecture of a closed form
There's a formula given $$ T(m,n) = \left\\{ \begin{array}{l l} 1 & \quad \text{if $m=0$}\\ 1+T(n \mod m, m) & \quad \text{if $m\>0$} \end{array} \right.$$ We're told to use repeated substitution to make a conjecture about a closed form for $T(F(n),F(n+1))$, where $F(k)$ is the $k^{th}$ Fibonacci number.This is a practice question and I have no idea how to start. Could someone help?

# Answer
> 2 votes
For $F\_0 = 0, F\_1 = F\_2=1, \dotsc$ consider

$$ \begin{align} T(F\_n, F\_{n+1}) &= 1+T(F\_{n+1}\mod{F\_n}, F\_n) & \text{by definition}\\ &= 1+T(F\_{n-1}\mod{F\_n}, F\_n) & \text{since }F\_{n+1} = F\_n+F\_{n-1}\\ &= 1+T(F\_{n-1}, F\_n) & \text{since }F\_{n-1} \le F\_n\\ \end{align} $$ continuing, we see $$ \begin{align} T(F\_n, F\_{n+1}) &= 1+T(F\_{n-1}, F\_n)\\ & = 2 +T(F\_{n-2}, F\_{n-1})\\ & = 3 +T(F\_{n-3}, F\_{n-2}) \end{align} $$ and in general $$ T(F\_n, F\_{n+1}) = k+T(F\_{n-k}, F\_{n-k+1}) $$ so when $k=n$ we have $$ T(F\_n, F\_{n+1}) = n+T(F\_0, F\_1) = n+T(0, 1) = n+1 $$ Now to make a conjecture about the growth of $T(F\_n, F\_{n+1})$ we need to find how large $n+1$, the run time, will be in terms of the size of $F\_{n+1}$. There is a closed form for this, namely $$ F\_k = \frac{\phi^k-\psi^k}{\sqrt{5}} $$ where $\phi = (1+\sqrt 5)/2\approx1.618$ and $\psi = (1-\sqrt 5)/2\approx-0.618$. Since $|\psi|\<1$ that term will be negligible for sufficiently large values of $k$ so we have $F\_k\approx \phi^k/\sqrt5$. Taking the log (to the base $\phi$) of both sides, we have $\log{F\_k}\approx k-\log{\sqrt5}$, so $k$ will be $\log {F\_k}$ plus a constant which we can ignore. In terms, then, of its arguments, $p, q$, with $q \ge p$ we'll have our conjecture: $$ T(p, q) = O(\log q) $$ which happens to be true, even if we don't restrict ourselves to Fibonacci numbers for the arguments.

This function is just the timing function for the Euclidean algorithm, which finds the greatest common divisor of the arguments:

```
gcd(p, q) =
   if p = 0
      return q
   else
      return gcd(q mod p, p)

```

For instance, $$ \gcd(15, 24) = \gcd(9, 15) = \gcd(6, 9) = \gcd(3, 6) = \gcd(0, 3) = 3 $$ after five recursive calls. It happens that the longest this algorithm will take to complete is when the arguments are consecutive Fibonacci numbers. The upshot is that, fortunately for us this is fast, being no worse than proportional to the number of digits in the arguments.

---
Tags: recurrence-relation
---


# Question
Title: Solving recurrence relation $T(2n) \leq T(n) + T(n^a)$
I want to prove that the time complexity of an algorithm is polylogarithmic in the scale of input.

The recurrence relation of this algorithm is $T(2n) \leq T(n) + T(n^a)$, where $a\in(0,1)$.

It seems that $T(n) \leq \log^{\beta}{n}$ for some $\beta$ depends on $a$. But I can't prove this inequality. How to solve this recurrence relation?

I just want to get an upper bound polylogarithmic in n.

# Answer
Your guess is wrong. In fact, it is not hard to show that assuming $T(n) \> 0$ for all $n \> 0$, then $T(n) = \Omega(\log^k n)$ for *all* $k$. Indeed, for this to hold we need that for large enough $n$ we would have $$ (1+a^k) \log^k n = \log^k n + \log^k n^a \geq \log^k (2n), $$ or $\sqrt\[k\]{1+a^k} \log n \geq \log n + \log 2$, which holds as long as $\[\sqrt\[k\]{1+a^k}-1\]\log n \geq \log 2$, and in particular for large enough $n$.

What is the correct order of growth of $T(n)$? To try and find out, write $S(n) = T(2^n)$. The recurrence now becomes $$ S(n+1) = S(n) + S(an). $$ For large $n$, we would expect $S(n+1) - S(n)$ to be very close to $S'(n)$, and so heuristically we would expect that $S$ satisfy $S'(n) = S(an)$. This equation seems a bit hard to solve, but an approximate solution is $S(n) = n^{\Theta(\log n)}$. Substituting back, we deduce that the order of growth of $T(n)$ should be something like $(\log n)^{\Theta(\log \log n)}$.
> 4 votes

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Why are non-relativizing proofs preferred to relativizing ones?
I apologize, but even after these two other posts: here and here I'm still having trouble understanding oracle TMs and relativization. This question comes at the issue from a different angle:

Why are non-relativizing proofs considered more valid than arguments based on relativized results?

For example, we have a non-relativizing proof of IP = PSPACE, but couldn't we just as well say an argument for the opposite by the fact that there exists an oracle separating them (I realize from an answer to a question I previously asked that this oracle exists due to a structural difference between the two complexity classes, but I see that as even more evidence that the classes are different in important ways and may not be equal).

On the flip side, why do we conclude from the fact that there exist oracles $A$ and $B$ such that $P^A = NP^A$ and $P^B \neq NP^B$ that non-relativizing techniques will be needed to resolve P vs. NP and not just resolve that oracles lead to inherent contradictions since we cannot have both P = NP and P $\neq$ NP? Again, I realize from a previous post that we can view oracle TMs as different models of computation that can solve problems ordinary TMs cannot, but I see this as similar to the "theory of types tactic" used in Principia Mathematica which, according to my understanding, Godel (through the Incompleteness theorems) proved to be insufficient to resolving issues of the completeness and consistency of axiomatic systems.

# Answer
> 8 votes
Let me try to answer your multifaceted question using an analogy from number theory (or rather, Peano arithmetic). The platonist point of view holds that every question about natural numbers has a YES/NO answer. This is known as "true arithmetic". However, as Gödel showed, some propositions concerning natural numbers can be neither proved nor disproved. The platonist point of view still holds that these propositions have a definite truth value with respect to the "true" set of natural numbers; Gödel just showed that the no finite list of axioms1 can specify the true set of natural numbers.

Let's see what this implies regarding the P vs. NP question. The platonist point of view holds that either P=NP or P$\neq$NP. It might be that P vs. NP is independent of the foundations of mathematics (say, ZFC), in which case we will be able to prove neither P=NP nor P$\neq$NP. But according to most researchers, this possibility is unlikely. Therefore we would really like to know whether P=NP or not *in the real world*, which is the same as2 whether P=NP or not *according to the standard foundations of mathematics*. This is the research question.

What about relativized models? Let me offer another analogy from number theory. If a polynomial identity is true over the integers then it is also true modulo $p$ for every prime $p$. So in order to disprove an identity, it is enough to show that it doesn't hold for some $p$. We can think of the integers modulo $p$ as a "relativized model". Let's consider an example: $1 + 1 = 0$ modulo $2$ but not modulo $3$. Does it mean that we are no longer sure whether $1 + 1 = 0$ or not? Not at all. We know that $1 + 1 = 2$, and in particular $1 + 1 \neq 0$. But in some relativized models, this equation fails to hold.

The (informal) local-global principle states that in some situations, there is a set of "relativized models" which is complete for some number-theoretic statements. The classical example is quadratic forms: given a quadratic form $Q$ and a number $n$, then $Q$ *represents* $n$ over the rationals (that is, $n$ is in the image of $Q$ when the inputs are arbitrary rational numbers) iff it represents $n$ over the real numbers and the $p$-adics.

Unfortunately, we have no similar theorems for complexity theory. In particular, given the truth value of relativized statements, we can deduce *nothing* about the original statement. The situation is even worse: it is not longer the case that a result true in the "true" world also holds relativized to any oracle. So we cannot even expect statements like the local-global principle to hold here.

Something like "relativized techniques" also occurs in Peano arithmetic. There are statements regarding the natural numbers which can be proved in ZFC but not in Peano arithmetic. The classical examples are the Paris–Harrington theorem and Goodstein's theorem. All proofs in Peano arithmetic are "relativizing" in the sense that they hold in all models of Peano arithmetic. The Paris–Harrington and Goodstein theorems fail in some non-standard models of Peano arithmetic, but these don't represent true arithmetic; in true arithmetic the theorems hold. The problem is with Peano arithmetic rather than with the statements themselves: there are some properties of the natural numbers that it doesn't describe, allowing these non-standard models to creep in. Gödel showed that this problem happens in *all* first-order models of arithmetic.

Now we can address your questions:

1. *Why is a non-relativizing proof of IP=PSPACE preferred over oracle separations of the same two classes?* We only care about the question IP=PSPACE? in the "true" world. It doesn't matter what happens in relativized worlds. Since there exist oracles which separate IP and PSPACE, proofs of IP=PSPACE must be non-relativizing. The situation is analogous to the one involving the Paris–Harrington and Goodstein theorems.

A different problem is that it is perhaps not clear how to define the relativized versions of these classes. This precludes presenting relativized results even as evidence.
2. *P=NP holds with respect to some oracle and fails to hold with respect to another; why do we conclude that non-relativizing techniques are needed rather than that oracles lead to inherent contradictions?* This is the same as the situation of $1+1 \neq 0$ above. This theorem is true, but has different truth values in different "relativized worlds" corresponding to the integers modulo $p$ for different values of $p$. This means that a proof of $1+1 \neq 0$ must include some step that doesn't hold modulo all $p$. It doesn't mean that working modulo $p$ "leads to inherent contradictions".
3. *Aren't we seeing something similar in the "theory of types" developed in Principia Mathematica?* The theory of types was developed as a consistent foundation for mathematics, after Russell discovered that naive set theory is inconsistent (using his paradox). No such foundational difficulties have been encountered in complexity theory.
4. *What are the implications of Gödel's incompleteness theorem?* The incompleteness theorem raises the possibility that P vs. NP is independent of the current foundations of mathematics. But this is considered unlikely by most researchers. Many difficult theorems have been proved in the past; some of them had been open for centuries (for example Fermat's last theorem). The fact that a theorem is difficult is no reason to think that it is beyond solution.

This leaves one question which you haven't asked: *Why do we care about relativized results?* I don't know the historical reason. It might be that these techniques are commonplace in related ares that served as sources of inspiration. At the very beginning, people might have expected that relativized results *do* imply absolute results. A good example is the random oracle hypothesis, which states that if a complexity theory statement holds with respect to a random oracle, then it holds absolutely. For example, although the P vs. NP is "undecided" with respect to an arbitrary oracle, Baker, Gill and Solovay showed that P$\neq$NP with respect to a random oracle. Does that imply that P$\neq$NP? The fact that IP=PSPACE disproved this hypothesis. Since that point, much less attention has been given to oracle results, and they are now quite unfashionable. They have become an object of study in their own right, but with no pretensions to be relevant for separating P from NP.

---

**Endnotes:**

1. The usual axiomatization of Peano arithmetic actually uses a finite number of axiom *schemes*. Gödel's result holds in even greater generality, as Andrej Bauer indicates in his thoughtful comments.
2. See Andrej Bauer's comments for a dissenting opinion.

---
Tags: complexity-theory, proof-techniques, oracle-machines, relativization
---


# Question
Title: LALR(1) parsers and the epsilon transition
I am having trouble getting my head wrapped around epsilon transitions while creating an LALR(1) parse table.

Here's a grammar that recognizes any number of 'a' followed by a 'b'. 'S' is an artificial start state. '$' is an artificial 'EOS' token.

```
0.    S -> A $
1.    A -> B b
2.    B -> B a
3.    B -> epsilon

```

Itemsets:

```
i0: S -> . A $
    A -> .B b
    B -> .B a
    A -> B . b  ! because B could -> epsilon
    B -> B . a  !    "

i1: S -> A . $

i2: S -> A $ .

i3: A -> B . b  ! from i0
    B -> B . a

i4: A -> B b .  ! from i0 or i3; the LALR algorithm compresses identical states.

i5: B -> B a .  ! from i0 or i3: the LALR algorithm compresses identical states.

```

I previously had a description on how this would work to parse a simple string. I removed it because I know less now than I did before. I can't even figure out a parse tree for 'ab'.

If someone could show me how I have mis-constructed my itemsets and how I'd reduce the epsilon transition I'd be grateful.

# Answer
> 2 votes
Your states and itemsets are not quite correct. The epsilon production must appear in relevant itemsets, and you have combined two states into one, which would produce a shift-reduce conflict if the epsilon production were added to the itemset (which should be done).

The following was generated with bison (using the `--report=all` command-line option); it differs from the theoretic model because the grammar has been "augmented" with an extra start symbol and an explicit end-of-input marker (`$end`). Also, it has done some table compression, so in the action tables, you can think of `$default` as meaning "either `a` or `b`".

It is worth explaining how State 0 comes about, since it shows how epsilon productions are handled (no differently from other productions).

We start with `$accept: . S $end`, by definition. (`$accept` is the starting state). Then the closure rule is applied as long as possible. Remember that the closure rule is: If any item in the itemset, the `.` is immediately before a non-terminal, add all the productions for that non-terminal with an initial `.`. Hence we add:

```
S: . A

```

continuing with `A`:

```
A: . B 'b'

```

continuing with `B`:

```
B: . B 'a'
B: .

```

We can't apply closure any longer, so we're done. Since the state now has an item with the dot at the end (the epsilon production for B), a reduction is possible.

```
State 0
    0 $accept: . S $end
    1 S: . A
    2 A: . B 'b'
    3 B: . B 'a'
    4  | .

    $default  reduce using rule 4 (B)
    S  go to state 1
    A  go to state 2
    B  go to state 3

State 1
    0 $accept: S . $end

    $end  shift, and go to state 4

State 2
    1 S: A .

    $default  reduce using rule 1 (S)

State 3
    2 A: B . 'b'
    3 B: B . 'a'

    'b'  shift, and go to state 5
    'a'  shift, and go to state 6

State 4
    0 $accept: S $end .

    $default  accept

State 5
    2 A: B 'b' .

    $default  reduce using rule 2 (A)

State 6
    3 B: B 'a' .

    $default  reduce using rule 3 (B)

```

In State 0, the closure rule has added the epsilon production (line 4). Furthermore, no item in the state 0 itemset has the point before a terminal. So with *any* lookahead, the parser is forced to reduce the epsilon production, after which it will use the `goto` function for state 0 to decide to move to state 3. (In your state machine, states 0 and 3 are conflated, but I do not believe this is correct.) State 3 will definitely shift a terminal; with the input `ab$end`, it will shift the `a` and move to state 6, which will then reduce a `B`. And so on.

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


# Question
Title: Why does the principle of locality of computation not relativize?
Although I have trouble understanding oracle TMs, I appreciate that non-relativizing techniques will be needed to resolve P vs. NP (as well as most other open problems in TCS). However, one of the techniques I've read about that does ***not*** relativize is using the fact that all of a Turing machine's computation is local and I'm wondering why this is a valid approach.

After all, the oracle tape has to be read somehow and if it is not locally then how? As I learned through this post regarding the Time Hierarchy Theory and relativization, the oracle of a polytime OTM must be accessed via a polytime reduction so it cannot just act arbitrarily. Is it just that the oracle tape is read only? Or is that even if computation is local for an OTM, we just regard this aspect as irrelevant since a call to the oracle is seen as taking one step? Thanks.

# Answer
> 3 votes
When you go into a special "oracle" step, the oracle reads the entire contents of the oracle tape and determines its output based on the entire tape. This is the non-local aspect of oracle computation.

---
Tags: proof-techniques, oracle-machines, relativization
---


# Question
Title: Function that is not Space Constructible
I'm reading Sipser's *Introduction to the Theory of Computation*, and I'm reading about space-constructible functions. He gives the following definition:

> A function $f: \mathbb{N} \to \mathbb{N}$ is *space constructible* if the function that maps the string $1^n$ to the binary representation of $f(n)$ is computable in space $O(f(n))$.

He follows up by saying,

> All commonly occurring functions that are at least $O(\log n)$ are space constructible, including the functions $\log\_2 n$, $n \log\_2 n$, and $n^2$.

My question: What is an example of a function that is $\Omega(\log n)$ that is *not* space constructible?

# Answer
Usually such examples are specifically "tailored", using hard problems. Perhaps the easiest way is to take the halting problem: $$HALT=\\{\langle M\rangle: M\text{ is a TM that halts on }\epsilon\\}$$ and consider the encodings of TMs as numbers, in such a way that no two numbers are encoded to the same TM (e.g. by leading 0s). This can be achieved using unary encoding, for example.

Now, consider the function $f:\mathbb{N}\to \mathbb{N}$ defined as follows: $f(n)=2n$ if $n$ represents a TM in HALT, and $f(n)=2n+1$ otherwise.

This function is $\theta(n)$, but clearly it is not space constructible, since constructing it would enable you to solve the halting problem.

A similar example can be constructed from a problem which is harder than PSPACE (e.g. a problem complete in EXPSPACE).

However, these example are somewhat "ugly". A more elegant example is the busy beaver function, which is non-computable simply because it "grows too fast".
> 4 votes

# Answer
Most functions are not space constructible. For example, let $A$ be a non-computable set, and define $$ f(n) = \begin{cases} 2n & \text{if } n \in A, \\ 2n+1 & \text{if } n \notin A. \end{cases} $$ This is a monotone increasing function which is $\Theta(n)$ but isn't space constructible.

Here is a more interesting example. Instead of taking $A$ to be non-computable, take a language which is in $\mathrm{SPACE}(n^2) \setminus \mathrm{SPACE}(n)$. Such a language exists by the space hierarchy theorem. Again $f(n)$ is a monotone $\Theta(n)$ function, which is computable in space $O(n^2)$ but not in space $O(n)$.
> 2 votes

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


# Question
Title: Dynamic Programming - Adding up N Integers
I'm studying for a final and the professor gave us a practice problem to prepare, but it's extremely difficult and I've been hacking at it for hours with no luck. Here it is:

It's driving me bonkers so I hope somebody out there can show me how it's done!

Thanks

# Answer
Hint: For each $i \< j$, compute the series of operations minimizing the cost of evaluating the sum $a\_i + \cdots + a\_j$, in increasing order of $j-i$. If $j = i+1$ then the cost is simply $a\_i + a\_j$. Otherwise, suppose that the last operation is $(a\_i + \cdots + a\_k) + (a\_{k+1} + \cdots + a\_j)$. Go over all $k$, and for each $k$ compute the minimal cost using the dynamic programming table. Deduce the best $k$ and the minimal cost.
> 1 votes

---
Tags: dynamic-programming
---


# Question
Title: What is With High Probability on Probabilistic Algorithms?
I watched lecture from MIT about Skip List. Overall, I understand the material, but one thing. What is "with-high-probability"? I really don't get it at all. I've seen the lecture notes but still didn't get it.

They just said, "Event $E$ occurs with high probability (w.h.p.) if, for any $\alpha\geq1$, there is an appropriate choice of constants for which $E$ occurs with probability at least $1 − O(1/n^\alpha)$".

Something from algorithmist.com didn't help, either.

What is $\alpha$ and what is $1 − O(1/n^\alpha)$? Not understanding this thing make me confused of the analysis of why "With high probability, every search in an $n$-element skip list costs $O(\lg n)$".

# Answer
> 5 votes
An event happens *with high probability* with respect to a parameter $n$ if it happens with probability $p\_n$ and $\lim\_{n\to\infty} p\_n = 1$. Usually the parameter $n$ is clear from the context. In this case, for example, it is probably the number of elements in the list.

The definition of "with high probability" in the lecture notes is even more specific, specifying how fast $p\_n$ should converge to $1$: an event happens with high probability if it happens with probability $p\_n \geq C/n^\alpha$ for some $C,\alpha\>0$. For example, if you choose a random number from $\\{0,\ldots,n\\}$ then it is non-zero with high probability since the probability that it is non-zero is $1-1/(n+1) \geq 1-1/n$ (so in this case $C=\alpha=1$).

---
Tags: algorithms, terminology, probabilistic-algorithms
---


# Question
Title: Why is the running time of edit distance with memoization $O(mn)$?
I understand without memoization it is going to be $O(3^{\max\\,\\{m,n\\}})$ because every call results in extra three calls: thus we end up having a call tree with three children for each node, with height $\max\\,\\{m,n\\}$, m and n being lengths of two given strings.

However I am not getting why it is $O(mn)$ after memoization. Can someone please help me understand this?

I also know that, in the case of dynamic programming, the complexity will be number of distinct sub-problems we solve (because we save the solution of subproblems).

How do I calculate distinct sub-problems I am solving in Edit Distance.

P.S. I am not asking here for tabulation approach (top-down method) or explanation int the form of tabulation approach. This question on Stack Overflow contains the code of Edit Distance with memoization.

# Answer
I'm assuming $n,m$ are the lengths of the input strings. The number of sub-problems are the number of different inputs to the recursive procedure `edit_distance`, ignoring the `memo` input. You can check that `s1` is always a suffix of the first input string and that `s2` is always a suffix of the second input string. Since there are $n+1$ suffixes of the first input string and $m+1$ suffixes of the second input strings, the total number of sub-problems is $(n+1)(m+1) = O(nm)$.

If evaluating the body of `edit_distance` (minus the recursive calls) took $O(1)$, then the total running time would be $O(nm)$. However, this is actually not the case. The function `make_pair` and the ensuing hash take $\Theta(|s\_1|+|s\_2|)$, which for a majority of function calls is $\Theta(n+m)$. Therefore the running time is actually $\Theta(nm(n+m))$ rather than $\Theta(nm)$. This slowdown is avoided in the dynamic programming solution, which does run in time $O(nm)$.

($\Theta(\cdot)$ is similar to $O(\cdot)$; whereas $O(\cdot)$ is only an upper bound, $\Theta(\cdot)$ is both a lower bound and an upper bound. I need to use it here since the fact that the algorithm runs in time $O(nm(n+m))$ doesn't preclude the possibility that it actually runs in time $O(nm)$; to preclude this possibility we need a *lower bound* on the running time.)
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis, dynamic-programming, edit-distance
---


# Question
Title: Approximate the order of summation of two vectors
Assume we are given two vectors $A,B$ that each contains $c$ numbers: $A=\[a\_i\>0\]\_{1 \times c}$. We want to see the weighted summation of which one is larger. In other words, given two vectors $A$ and $B$:

$$ws(A) = \sum\_{1 \leq i \leq c}{i.a\_i}, ~~~~ws(B) = \sum\_{1 \leq i \leq c}{i.b\_i}$$

we want to know $ws(A)\>ws(B)?$

For making the problem simpler, I add another condition to the problem:

$$\sum\_{1 \leq i \leq c}{a\_i} = \sum\_{1 \leq i \leq c}{b\_i}$$

Now, is there any way to approximately claim which one of these vectors is larger without running the summation (We may consider the summation of a small number of elements and decide based on that)?

# Answer
> 2 votes
Let's consider the problem of comparing the sums of two vectors $A$ and $B$ that have all their $N$ real values in the range $\[0, c\]$.

First, let's start with two facts.

**Union Bound.** Let $Y\_1, \ldots, Y\_K$ be K events in a probability space. Then \begin{equation} Pr\left(\bigcup\_{j=1}^KY\_j\right) \leq \sum\_{j=1}^K Pr\left(Y\_j\right). \end{equation} (The inequality is equality for *disjoint* events $Y\_j$.)

**Hoeffding Bound (1, 2).** Let $X\_1, \ldots, X\_R$ be $R$ independent random variables, each taking values in the range $\mathcal{J} = \[\alpha, \beta\]$. Let $\mu$ denote the mean of their expectations. Then \begin{equation} Pr\left(\left|\frac{1}{R}\sum\_{i=1}^RX\_i - \mu\right|\geq \epsilon\right) \leq e^{-2R\epsilon^2/(\beta-\alpha)^2} \end{equation}

**Idea**

The first idea is that we are going to approximate the values of the sums for the two vectors $A$ and $B$ within some precision $\varepsilon$ with high probability (*high confidence* if you prefer). Then the argument that the two expectations that we have for the actual sums of the vectors $A$ and $B$ are well separated will be a simple application of the Union bound assuming that we have very high confidence for both expectations.

**Definitions**

Let $S(A), S(B)$ be the actual sum for the vectors $A$ and $B$ respectively and $S^\*(A)$ and $S^\*(B)$ be the approximations of the two values that we are going to come up with. In particular, $$\begin{array}{rcl} S(A) &=& \mu\_A\cdot N \\ S(B) &=& \mu\_B\cdot N \end{array}$$ where $\mu\_A$ and $\mu\_B$ are the true mean values of the entries of the vectors respectively.

We now reduce the problem of approximating the sums to that of approximating the mean values $\mu\_A$ and $\mu\_B$; let's call the approximations $\mu\_A^\*$ and $\mu\_B^\*$.

**Well Separated Approximations of Sums.** We will say that the two approximated sums are *well separated* if the following holds: \begin{eqnarray} \left|S^\*(A) - S^\*(B)\right| &=& \left|\mu\_A^\*\cdot N - \mu\_B^\*\cdot N\right| \\ &=& \left|\mu\_A^\* - \mu\_B^\*\right|\cdot N \\ &\geq& 2\cdot\epsilon\cdot N \end{eqnarray} where $\epsilon$ is the accuracy within which we have approximated the means $\mu\_A^\*$ and $\mu\_B^\*$.

(The intuition is that the sums are *well separated* if their respective mean values are *well separated*.)

**Continuation**

By the Hoeffding bound, if we require that our estimate is incorrect bounded by some small probability $\delta/2$ (it will be apparent soon why I divide $\delta$ by two), then we need $$R \geq \left\lceil\frac{(\beta-\alpha)^2}{2\epsilon^2}\cdot\ln\frac{2}{\delta}\right\rceil = \left\lceil\frac{c^2}{2\epsilon^2}\cdot\ln\frac{2}{\delta}\right\rceil$$ *samples* (*runs*) so that we can come up with the real values $\mu\_A^\*$ and $\mu\_B^\*$ that approximate the true real values $\mu\_A$ and $\mu\_B$ respectively within $\epsilon$ with probability at least $1-\frac{\delta}{2}$. In other words, it is only with probability at most $\frac{\delta}{2}$ that we will not have good estimates for each of the $\mu\_A^\*$ and $\mu\_B^\*$.

Now, by the Union bound, either of our estimates is incorrect with probability at most $\delta/2 + \delta/2 = \delta$. Or, the other way around, with probability at least $1-\delta$ *both* of our estimates $\mu\_A^\*$ and $\mu\_B^\*$ are within $\epsilon$ of their true values.

**Theorem**

Drawing $R$ samples from each vector where $$R \geq \left\lceil\frac{c^2}{2\epsilon^2}\cdot\ln\frac{2}{\delta}\right\rceil$$ it is guaranteed that with probability $1-\delta$ both of our estimates for $\mu\_A^\*$ and $\mu\_B^\*$ are within $\epsilon$ of their true values, and thus the approximations $S^\*(A)$ and $S^\*(B)$ that we have for the sums $S(A)$ and $S(B)$ are within $\epsilon\cdot N$ of their true values. Thus, it suffices to check if the inequality $$\left|S^\*(A) - S^\*(B)\right| \geq 2\cdot\epsilon\cdot N$$ holds. If the inequality holds, then with probability $1-\delta$ (that's our *confidence*) the two sums are different and in fact we can say which one is bigger with the same confidence.

**Concluding Remark**

Just to note that with the approach above we need $\epsilon^{-1} = o\left(\sqrt{N}\right)$ so that the number of samples/runs $R$ is *sublinear* (btw, *sublinear algorithms* is an active field of research) and thus it makes sense to take samples from the huge vectors $A$ and $B$ rather than computing the sums directly. This also means that with this approach the separation bound between the two approximated sums should be $\Omega\left(\sqrt{N}\right)$.

**References**

\[1\] Wassily Hoeffding. Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, 58(301):13–30, March 1963

\[2\] L. Devroye, L. Györfi, and G. Lugosi. A Probabilistic Theory of Pattern Recognition. Springer, 1996.

**Code**

Below is some code that I wrote yesterday for playing around with the problem. The difference is I think that I did not divide by 2 the $\delta$, and moreover, for the approximations I am expressing $\delta$ as a negative power of $e$ ($\approx 2.71828\ldots$) so that I can simplify the calculations and not take logarithms. Other than that, I generate two big arrays with slightly skewed entries; the first one with values between 0 and 9 and the other one with values between 1 and 10. In principle this needs a GMP implementation, but I guess the following will do for now. I really enjoyed the problem! Thanks! I am of course very interested in seeing different approaches to the problem.

```
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <ctgmath>

#define SIZE 1000000
#define EPSILON 0.1
#define DELTA_EXPONENT 4

#define MIN_VALUE  0
#define MAX_VALUE 10

/************************************************************************************/

void assignRandomValues (unsigned int * array, const unsigned long int size, const int low, const int high);
unsigned int trueSum (unsigned int * array, const unsigned long int size);
bool areTheApproximationsSufficientlyDifferent (const unsigned long int size, const long double epsilon, const unsigned int difference);
unsigned int approximateSum (unsigned int * array, const unsigned long int size, const int maxValue, const long double epsilon, const int deltaExponent);
long double approximateMean (unsigned int * array, const unsigned long int size, const int maxValue, const long double epsilon, const int deltaExponent);

/************************************************************************************/

int main () {
    unsigned int * a1, * a2, s1, s2, s1Approx, s2Approx, difference;
    bool flag;
    time_t timer;

    // Randomize
    timer = time(NULL);

    // Print the basic properties
    std::cout << "Timer seed: " << timer << std::endl;
    std::cout << "Size      : " << SIZE << std::endl;
    std::cout << "Epsilon   : " << EPSILON << std::endl;
    std::cout << "Delta exp : " << DELTA_EXPONENT << std::endl << std::endl;

    // Reserve memory
    a1 = new unsigned int [SIZE];
    a2 = new unsigned int [SIZE];

    // Generate the arrays
    assignRandomValues (a1, SIZE, MIN_VALUE, MIN_VALUE + (MAX_VALUE - MIN_VALUE)/2 + 4);
    assignRandomValues (a2, SIZE, MIN_VALUE + (MAX_VALUE - MIN_VALUE)/2 - 4, MAX_VALUE);

    // Find and print the true values
    s1 = trueSum (a1, SIZE);
    s2 = trueSum (a2, SIZE);
    std::cout << "The true sum value for a1 is: " << s1 << std::endl;
    std::cout << "The true sum value for a2 is: " << s2 << std::endl;

    // Find and print the approximate values
    s1Approx = approximateSum (a1, SIZE, MAX_VALUE, EPSILON, DELTA_EXPONENT);
    s2Approx = approximateSum (a2, SIZE, MAX_VALUE, EPSILON, DELTA_EXPONENT);
    std::cout << "The approximate sum value for a1 is: " << s1Approx << std::endl;
    std::cout << "The approximate sum value for a2 is: " << s2Approx << std::endl;

    // Print the approximate difference and indicate if they are sufficiently separated
    difference = static_cast<unsigned int>(fabs(static_cast<long double>(s1Approx) - static_cast<long double>(s2Approx)));
    std::cout << "The approximated difference is: " << difference << std::endl;
    flag = areTheApproximationsSufficientlyDifferent(SIZE, EPSILON, difference);
    std::cout << "The approximated difference is sufficiently big (w.h.p.): ";
    std::cout << (flag ? "YES" : "NO") << std::endl;

    // Deallocate memory
    delete [] a1;
    delete [] a2;

    return 0;
}

/************************************************************************************/

void assignRandomValues (unsigned int * array, const unsigned long int size, const int low, const int high) {
    unsigned long int i;

    for (i = 0; i < size; i++) {
        array [i] = low + (rand() % (high - low + 1));
    }
}

/************************************************************************************/

unsigned int trueSum (unsigned int * array, const unsigned long int size) {
    unsigned long int i, sum = 0;
    for (i = 0; i < size; i++)
        sum += array[i];
    return sum;
}

/************************************************************************************/

bool areTheApproximationsSufficientlyDifferent (const unsigned long int size, const long double epsilon, const unsigned int difference) {
    unsigned int bound = static_cast<unsigned int>(ceil(2.0*size*epsilon));
    if (difference > bound)
        return true;
    return false;
}

/************************************************************************************/

unsigned int approximateSum (unsigned int * array, const unsigned long int size, const int maxValue, const long double epsilon, const int deltaExponent) {
    long double mean = approximateMean (array, size, maxValue, epsilon, deltaExponent);
    return static_cast<unsigned int>(round(mean * size));
}

long double approximateMean (unsigned int * array, const unsigned long int size, const int maxValue, const long double epsilon, const int deltaExponent) {
    unsigned long int samples, i, sum, pos, integerPart;
    long double floatingPart, mean;

    samples = static_cast<unsigned long int>(ceil(maxValue * maxValue * deltaExponent / (static_cast<long double>(2.0) * epsilon * epsilon)));

    std::cout << "Requiring " << samples << " samples for the approximation." << std::endl;

    sum = 0;
    for (i = 0; i < samples; i++) {
        pos = rand () % size;
        sum += array[pos];
    }

    integerPart  = sum / samples;
    floatingPart = static_cast<long double>((sum - integerPart * samples)) / static_cast<long double>(samples);
    mean = static_cast<long double>(integerPart) + floatingPart;
    return mean;
}

/************************************************************************************/

```

**Wrapping Up for the Original Question**

In the original question we want to approximate values of the form $i\cdot a\_i$ or $i\cdot b\_i$ and this means that these new values are now in the range $\[0, c\cdot N\]$ assuming that $a\_i, b\_i \in \[0, c\]$ for $i\in{0, 1,\ldots, N}$.

Above, I assumed that $c \ll N$. However, since the number of samples that is required has quadratic dependence on the maximum value that can be found in these new vectors, we really need to draw $R \geq \Omega\left(\frac{c^2\cdot N^2}{\epsilon^2}\ln\left(\frac{1}{\delta}\right)\right)$ samples. On the other hand, a direct summation will perform $O(N)$ additions of $O(N)$ multiplications. Thus, sampling would make sense in terms of savings if we could say that $R=o\left(N\right)$. In other words, ignoring the logarithmic dependence on $\delta$, we want $$\frac{c^2\cdot N^2}{\epsilon^2} = o(N)\\;.$$ This would be true if $$\epsilon = \omega(c\cdot N^{1/2})$$ thus yielding $R=o\left(N\right)$.

The question is if this $\epsilon$ is meaningful for comparisons. The answer is yes when the two vectors are significantly different (contrary to the helper that original vectors have values that add up to the same number). Let's see what I mean by an example.

**Example**

Let $c=N$. Moreover, let $$ \begin{array}{rcl} A &=& \left\langle 1, 1, \ldots, 1, \ldots, 1\right\rangle \\ B &=& \left\langle 1, 2, \ldots, i, \ldots, N\right\rangle \end{array} $$ be two vectors with $N$ elements. Then, the requested summation of the products $i\cdot a\_i$ and $i\cdot b\_i$ can be seen as the summation on the vectors $$ \begin{array}{rcl} F &=& \left\langle 1, 2, \ldots, i, \ldots, N\right\rangle \\ G &=& \left\langle 1^2, 2^2, \ldots, i^2, \ldots, N^2\right\rangle \end{array} $$ Note that $S(F) = \sum\_{i=1}^N f\_i = \Theta\left(N^2\right)$ and $S(G) = \sum\_{i=1}^N g\_i = \Theta\left(N^3\right)$. Similarly, their mean values are significantly different, since $\mu\_{F} = \Theta\left(N\right)$ while $\mu\_G = \Theta\left(N^2\right)$

The accuracy $\epsilon$ that we are talking about involves the estimate of these last true mean values $\mu\_F$ and $\mu\_G$. Thus, if we set $$\epsilon = \Theta\left(c\cdot N^{1/2+\xi}\right) = \Theta\left(N^{3/2+\xi}\right)$$ for some $\xi\in(0,1/2)$ there will be cases (like in this example) where the mean values will be significantly far away on the real line and thus we will be able to tell which one is bigger than the other with few samples (and as a consequence we will be able to separate the two sums on the real line with that many samples).

**Concluding the Wrap-Up**

Now if we revisit our definition for *well-separated* sums, we are going to require the following inequality for our definition: $$\left|S^\*(F)-S^\*(G)\right| \geq 2\cdot N^{5/2+\xi}$$ for some $\xi\in\left(0, 1/2\right)$. Actually any $\xi\in\left(0,1/2\right)$ will do. The larger the $\xi$ the fewer samples that we draw. However, the catch is that the larger the $\xi$, the more restrictive our inequality is for separating the two sums. In other words, the closer $\xi$ is to $1/2$ the more unlikely it is to encounter vectors that can be separated using our method, since we require the gap between their true values to be even larger.

I believe the above clears up everything, but in case it does not, just drop me a line and I will try to explain more the details.

---
Tags: algorithms, approximation
---


# Question
Title: Do an ambiguous grammar and its corresponding unambiguous version generate the same language?
If I have an ambiguous grammar G and its disambiguated version D. Then which one is true **L(D) ⊂ L(G)** , **L(G) ⊂ L(D)** or **L(G)=L(D)**?

As I tried with some examples to transform a grammar to it unambiguous version but i found that both are equivalent.

I mean is there a specific set relation between both. Please help me and provide an example if possible.

# Answer
> 6 votes
When you disambiguate a grammar, you usually want at least to keep the language the same. So the answer is that you want $\mathcal L(G)=\mathcal L(D)$.

If you accepted that $\mathcal L(G)\subset \mathcal L(D)$ then you could simply choose $\mathcal L(D)=\Sigma^\*$, since $\Sigma^\*$ has an unambiguous grammar. Of course $\Sigma$ is the terminal alphabet.

If you accepted that $\mathcal L(D)\subset \mathcal L(G)$ then you could simply choose $\mathcal L(D)=\emptyset$ since $\emptyset$ has an unambiguous grammar.

I assume you were considering context-free (CF) languages. You should have said so.

And you should remember some facts that will not help:

* Some CF languages are inherently ambiguous, so that you cannot find an unambiguous grammar for them. Furthermore, it is undecidable whether a CF language is inherently ambiguous,
* It is undecidable to know whether a grammar is ambiguous, hence it is not clear when a disambiguating transformation is needed.

See also wikipedia page on ambiguous grammars.

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


# Question
Title: Distribution of cycles length in a graph
Given a random **directed** Graph G:

$$ G=(V,E) \\ \lvert V \rvert = n , \lvert E \rvert = k $$

where for each vertex, **either**: $$ d\_{incoming}(v) = 1 , d\_{outgoing}(v) = 1 $$ meaning - for each incoming (outgoing) edge to vertex v, there is also an outgoing (incoming) edge from vertex v.

Or: $$ d(v) = 0 $$

What is the distribution of lengths of the longest cycles for this set of random graphs?

This question relates to the riddle presented in the last minute-physics video. (for the general case)

# Answer
When $k = n$ and self-loops are allowed, what you have is a *random permutation*. The expected length of the longest cycle in a permutation is known to be $\alpha n$ for $\alpha \approx 0.624$, see Shepp and Lloyd. If self-loops are not allowed then you will get a different constant $\beta$ that can probably be computed using the methods of Shepp and Lloyd.

When $k \< n$, you just get a permutation on $k$ vertices, so instead of $\alpha n$ or $\beta n$ you would get $\alpha k$ or $\beta k$.
> 4 votes

---
Tags: graphs, combinatorics
---


# Question
Title: Is there an equivalent of lambda calculus for object oriented languages?
Lambda calculus serves as a foundation for all sorts of functional languages and its various extensions are compiler targets for languages like Haskell, ML, etc. So what is the equivalent for object oriented languages? Is there a minimal object calculus that serves as the foundation for object oriented languages?

# Answer
> So what is the equivalent for object oriented languages?

Lambda calculus.

I mean, there is Cardelli's object calculus (and a handful of derivatives), but in general, there's nothing fancy about object oriented languages that requires a new approach to computation.

It's well known (see TaPL for example) how to extend/encode Records and Mutation (and sub-typing/dispatch) onto/in lambda calculus. The underlying structures don't need to change, even though there are often layers above it that add semantic restriction and make things more usable (member access, implied `this`, object layouts, etc).
> 14 votes

# Answer
While not *really* an answer to your specific question, I will suggest that those OO langs that do have lambdas (or specifically do *not*) usually do so for practical reasons. The recent inclusion of lambdas/closures in Java 8 is a case-in-point.

This generated a lot of discussion, even well before Java 8. There is a dense website dedicated to this specific implementation that has a lot of technical and theoretical discussion that might be of interest?

Specifically, check out Bloch's "Controversy" slides.
> -1 votes

---
Tags: programming-languages, lambda-calculus, object-oriented
---


# Question
Title: Why $\theta/2$ in common qubit representation?
If we take angle names as shown on the Bloch sphere below and a typical qubit representation written as $\cos(\theta/2)|0\rangle + \mathrm{e}^{-\mathrm{i}\phi}\sin(\theta/2)|1\rangle$, why do we divide $\theta$ by $2$ in the cosine and sine parameters?

# Answer
**Short diagrammatic answer.** Because states which are orthogonal as vectors, are represented as antipodal points on the Bloch sphere — orthogonal states of qubits are as far from each other as possible and represent a sort of 'opposite' of each other, and the Bloch sphere represents this idea.

**Longer mathematical answer.** Consider the vector-valued function $\def\ket#1{|#1\rangle}$ $$ \ket{\psi\_{\theta,\phi}} = \cos(\theta/2) \ket0 + \mathrm e^{i \phi} \sin(\theta/2) \ket{1}. $$ This function has a period of $4\pi$ in the argument $\theta$, as a result of that division by 2; this might be part of what you are finding strange. However, when we consider *quantum state vectors*, we are not actually interested in the vector itself, as we are in the equivalence class of all vectors *which are the same up to scalar factors* (*i.e.* global phases).

Because $\ket{\psi\_{\theta,\phi}} \ne \mathbf 0$, we always have $\ket{\psi\_{\theta,\phi}} \ne \ket{\psi\_{\theta+2\pi,\phi}} = -\ket{\psi\_{\theta,\phi}}$; but we **do** have $\ket{\psi\_{\theta,\phi}} \propto \ket{\psi\_{\theta+2\pi,\phi}}$ instead. That is, adding $2\pi$ to the angle $\theta$ gives you a vector $\ket{\psi\_{\theta+2\pi,\phi}}$ which represents the same state. Because we only care about the state-vector inasmuch as it represents a state, this vector-valued function with peridod $4\pi$ is used to stand for a *state-valued* function with period $2\pi$.

This becomes clearer if we use density operators to represent states, because global phases of state vectors do not affect the density operator. Define the operator $$ \rho\_{\theta,\phi} = |\psi\_{\theta,\phi}\rangle\\!\langle\psi\_{\theta,\phi}| = \begin{bmatrix} \cos^2(\theta/2) & \mathrm e^{-i\phi}\\!\cos(\theta/2)\sin(\theta/2) \\ \mathrm e^{i\phi} \\!\cos(\theta/2)\sin(\theta/2) & \sin^2(\theta/2) \end{bmatrix};$$ using the double-angle formulae $$ \begin{gather\*} \cos(\theta) = 2\cos(\theta/2)^2 - 1= 1 - 2\sin(\theta/2)^2\\ \sin(\theta) = 2\cos(\theta/2)\sin(\theta/2) \end{gather\*} $$ we may re-write $\rho\_{\theta,\phi}$ as $$ \rho\_{\theta,\phi} = \frac{1}{2}\begin{bmatrix} \cos(\theta) + 1 \\;&\\; \mathrm e^{-i\phi} \sin(\theta) \\ \mathrm e^{i\phi} \sin(\theta) \\;&\\; 1 - \cos(\theta) \end{bmatrix} ,$$ which is not the best representation for thinking about qubits, but certainly makes it very clear that the density operator corresponding to $\ket{\psi\_{\theta,\phi}}$ is periodic in $\theta$ with period $2\pi$.

As icing on the cake, note that $\rho\_{\theta,\phi}$ is Hermitian by construction. So are the Pauli spin operators $\mathbf 1, X, Y, Z$, and those four are linearly independent. That means that we can decompose $\rho\_{\theta,\phi}$ as a linear combination of those four operators. We may easily show, from the last expression for $\rho\_{\theta,\phi}$, that $$ \rho\_{\theta,\phi} = \tfrac{1}{2}\Bigl(\mathbf 1 + \cos(\phi)\sin(\theta) X + \sin(\theta)\sin(\phi) Y + \cos(\theta) Z \Bigr).$$ If you take the coefficients for $X$, $Y$, and $Z$, and map them to coordinates in $\mathbb R^3$, what you obtain is the Bloch sphere representation: that is, the Bloch sphere not only represents qubit states, but it is specifically representing the decomposition of the density operator into spin matrices.
> 5 votes

---
Tags: quantum-computing
---


title: Parity function

text:
# Question
Title: Parity function
How is the parity function defined in standard way if inputs are in $\\{-1,+1\\}$ instead of $\\{0,1\\}$. For $\\{0,1\\}$, parity is $x\_1\oplus x\_2\oplus\cdots\oplus x\_{n-1}\oplus x\_n$. I am looking for how is inner product mod $2$ defined if inputs are in $\\{-1,+1\\}$. Is it $\frac{1}{4}\sum\_i(x\_i+1)(y\_i+1)\mod 2$ or just $\sum\_i x\_iy\_i \mod 2$?

What if one replaces $2$ by $p$ a prime or $N$ a composite?

# Answer
In the representation of bits by $\pm 1$, the most important aspect is in fact the sign. In fact the best way to describe the mapping from $\\{0,1\\}$ to $\\{-1,+1\\}$ is the function $f(x) = (-1)^x$. This is a representation in which logical AND and OR are awkward at best, but PARITY is dead easy. Let $a = f(x)$, $b = f(y)$, and $c = f(x \oplus y)$: $$c := f(x\oplus y) = f(x + y - 2xy) = (-1)^{x + y - 2xy} = (-1)^{x + y} = f(x) f(y) = ab.$$ Thus, in the sign representation, parities are computed by multiplication.
> 2 votes

---
Tags: boolean-algebra
---


title: Feature values range

text:
# Question
Title: Feature values range
Suppose I am about to use SVM for learning a classification or ranking function. Suppose that my feature vectors are two dimensional and that values for one dimension are, say, natural numbers and the values for the other dimension are real numbers in $\[0,1\]$. Can this difference in magnitudes somehow negatively affect learning? Are there some guidelines for scaling feature values? Any references appreciated.

# Answer
> 1 votes
I don't see how there should be any negative consequences of this. To see why, you can "vectorize" your feature matrix so that you still have scalars for each "new" feature. That is, instead of a matrix of n features each with k values, you have a vector of length n×k with scalar features. SVMs with a mixture of categorical/integral + real components is standard.

---
Tags: machine-learning, features, svm
---


# Question
Title: How is it valid to use oracles in mathematical arguments?
Oracles do not exist. If one did exist, then you would replace them with a subroutine with computational requirements and you would no longer need an "Oracle". Thus, Oracles do not exist almost by definition. I don't understand how one can make an mathematical argument based on something that does not exist (excluding unbounded memory machines, of course). Have a problem, ask the "magic" Oracle, problem solved $O(1)$ time. Of course you can't say anything about what is happening in the oracle, because its "magic". From this point of view, Turing Machines (bizarre fetish formalism if you ask me) with Oracles do not exist. Also, that X historic proofs rely on oracles makes oracle arguments valid is a circular argument.

# Answer
Oracles are a very general formalization of the idea, "If I could solve $X$ efficiently, I could use that to solve $Y$ efficiently." I accept that it sounds a bit silly to go as far as "If I could solve problem $X$ *in constant time*, I could use that to solve $Y$ efficiently" but, actually, that doesn't make any real difference at the level of detail we're working at, here.

For example, consider an oracle $O\_1$ that can solve SAT in constant time, versus an oracle $O\_2$ that solves SAT in, say, cubic time. The problems you can solve in polynomial time with access to $O\_1$ are exactly the same as the ones you can solve in polynomial time with access to $O\_2$. Sure, the polynomial will be better if you use $O\_1$, but it's still a polynomial if you use $O\_2$. In fact, the answer won't change whatever polynomial bound you assume on the running time of the oracle so we choose to simplify the analysis by choosing the simplest polynomial possible: $1$.

In some cases, you can see oracle arguments as hedging your bets. Although you lead your question with "Oracles don't exist", we don't actually know that. Suppose somebody produced a polynomial-time algorithm for SAT tomorrow. Wouldn't it be a shame if all we could solve with it was SAT? But because we have all kinds of oracle reductions available to us, we could already solve any **NP**-complete problem efficiently (the many-one reductions used to prove problems **NP**-complete are just a very restricted kind of oracle reduction). Conversely, if somebody proves tomorrow that SAT has no efficient algorithm, then all that work on oracles tells us that all the other **NP**-complete problems are also genuinely hard.

But remember that oracle arguments are conditional: *if* I could do $X$, *then* I could also do $Y$. If it turns out that you can't do $X$ then, OK, maybe you can't do $Y$ after all. But it's still a perfectly valid what-if question. So, for example, it still makes sense to consider Turing machines with an oracle for the halting problem, even though we know for a provable fact that no Turing machine can actually solve the halting problem. There's nothing wrong with asking the what-if, as long as we remember that it is a what-if.

To address a couple of other points,

> I don't understand how one can make an mathematical argument based on something that does not exist (excluding unbounded memory machines, of course).

So we're allowed to use some non-existent things but not others? Why?

> Turing Machines (bizarre fetish formalism if you ask me)

Are you trying to get a rise out of me, Agent Kujan?

> Also, that X historic proofs rely on oracles makes oracle arguments valid is a circular argument.

Yes, that's circular. But it's also a strawman: I've never heard anyone make that argument.
> 12 votes

# Answer
There are several applications to oracles.

First, there is usage in proving lower bounds (i.e. Turing reductions): if you know that a problem $L$ cannot be solved within some complexity (or computability) class $C$, and you show that an oracle to $L'$ allows you to solve $L$ within $C$, then you can conclude that $L'$ is also not in $C$.

Second, there is a pure-mathematical interest in adding oracles. For example, consider an oracle to $A\_{TM}$. The fact that even under this oracle there are problems that are undecidable leads to the beautiful concept of the arithmetical hierarchy. Moreover, there is an interesting connection to logic - the arithmetical hierarchy corresponds to definable sets.
> 10 votes

# Answer
There are many mathematical objects that "do not exist" (afaik, and whatever that means), and which have been the support of mathematical reasonning for centuries (maybe not many centuries). The first example that comes to mind is the real numbers, and more generally non denumerable sets. All you need is that the non-existing object have properties that are defined well enough so that you can reason with them.

Using an axiomatic system requires in no way the existence of a physical model that could serve as a model for these axioms. The funny thing is that physicists themselves do that all the time. They imagine laws that could govern the universe to see whether they may explain better observed phenomena. Many (most) of these systems turn out not to fit reality, though understanding why is often a source of knowledge and progress.

You can see Turing Machines as an axiomatic system that describe a kind of computation that seems to fit well what is physically realizable (as stated by the Church-Turing thesis). Lambda Calculus is another one, different but equivalent. But nothing forbid adding more axioms that leads to new theories of computability that are mathematically sound ... but probably useless for effective computation in this world (I do not know about other worlds).

But they are not more useless than the non-computable reals that are implicitly (hopefully) taught in all schools of the world. I just mean that the distinction with computable reals is not usually made.

Oracles are just like extra axioms, or extra computational object like the non computable reals, that are helpful for abstract reasonning, but not so helpful for actual computation.

Now, existence is also a somewhat relative matter. In your question you state at first

> Oracles do not exist. If one did exist, then you would replace them with a subroutine with computational requirements and you would no longer need an "Oracle".

I answered so far about oracle that are not realizable at all, since that seemed to be what you were concerned with in your question. But being realizable, i.e. computable, has degrees and that is what complexity analysis is about. Not being computable is just the worst case. Replacing the oracle by a subroutine imposes to you the complexity of that subroutine. But maybe you want to hypothesize that there are faster ways.

Some problems are not computables (what I talked about), then some others are computable but with high complexity. It may be that versions with lower complexity do not exist, as far as we know, but we can wonder what would happen if they did. Indeed, progress in physics has introduced the possibility of new computing technology (quantum computing) that may change the complexity of some problems. This is enough to justify oracle based analysis, even for problem that already have a solution, as the oracle allows us to analyse what would happen with a more efficient solution.

And then there are problem for which we do not know what the complexity is, and analyzing complexity of the use of solutions of such problems can be done only with oracles.
> 5 votes

# Answer
It is incorrect to say that oracles do not exist by mathematical definition. An oracle is merely an abstraction for something that solves a problem. When making logical arguments, you have to start with assumptions (and you should state them as formally as possible.) Proving that `"If I could do X, then I could do Y"` can be useful for a number of reasons. One of those reasons can be as simple as that it's entirely possible to do X, there are multiple ways to do it, and which one is chosen by a given implementation is simply irrelevant to what you're proving. Another is that it *may* be possible to do X and that your proof that that would lead to the ability to also do Y would have significant consequences if someone else comes along and shows a way to do X.

In cryptography, for instance, it's common for papers to make arguments based on oracles that allow an attacker to determine the ciphertext for a given plaintext. Clearly, there are plenty of ways to accomplish that. How the attacker does so is not relevant to the argument being made, though, thus it is abstracted away as a 'black box.'
> 1 votes

# Answer
"one can make an mathematical argument based on something that does not exist (excluding unbounded memory machines, of course)" by making sure it works for ("unbounded memory machines" and) something that does exist - random number generators.

Just say "if for each bit produced by that RNG, the bit was a 1 if and only if the contents of the oracle tape at that time encoded an element of the set, then the combination will have a high-enough probability of halting with the right answer without exceeding its resource limitations."
> 0 votes

# Answer
I found nice answers to my concerns/confusions (OP) in these threads:

Why is Relativization a barrier?

> The reason this transfer from oracle-less framework to framework with oracles works is that simple diagonalization is based on black-box simulation of TMs and it doesn't matter how machines works, whether it has an oracle or not.

Why are non-relativizing proofs preferred to relativizing ones?

> This leaves one question which you haven't asked: Why do we care about relativized results? I don't know the historical reason. It might be that these techniques are commonplace in related ares that served as sources of inspiration. At the very beginning, people might have expected that relativized results do imply absolute results.... Since that point, much less attention has been given to oracle results, and they are now quite unfashionable. They have become an object of study in their own right, but with no pretensions to be relevant for separating P from NP.

This paper backs up the previous quote: Relativization: a Revisionistic Retrospective, Hartmanis, et. all.

http://www.csee.umbc.edu/~chang/papers/revisionist/rev-book.pdf
> -3 votes

---
Tags: complexity-theory, turing-machines, proof-techniques, p-vs-np, oracle-machines
---


# Question
Title: Papadimitrou and standard landau notation
*This is a homework. I'd appreciate if you didn't give away answer straightaway but instead pointed me to the right direction.*

From huge majority of sources the definition of $\mathcal{O}(n)$ is:

$f, g : N \to R^+$

$f \in \mathcal{O}(g) \Leftrightarrow \exists{c,n\_0} \in N \\\> \forall n \> n\_0 : f(n) \leq c\cdot g(n)$

but in Papadimitriou's book there is a different definition I haven't seen anywhere before:

> The **order of** $f$, denoted $\mathcal{O}(f)$, is the set of all functions $g:N\rightarrow N$ with the property that there are positive natural numbers $c\>0$ and $d\>0$ such that, for all $n\in N$, $g(n) \leq c \cdot f(n)+d.$

I assume the first definition evaluates the functions as continuous functions whereas the second definition is concerned only about the points on $n \in N$. Therefore undefined values that asymptotically goes to $\pm\infty$ are not an issue anymore.

For example if we take $f(n)=\frac{1}{n}$ and $g(n)=1$. We know that $f(n)\in g(n)$ because $\lim\_{x\to\infty}\frac{\frac{1}{x}}{1}=0$. We find the value for $f(1)$ and raise the $g(n)$ above this point such as: $f(n) \leq 6\cdot f(n)$ or $f(n) \leq f(n)+6$

Is my assumption correct? If it is how can I prove this equivalence?

# Answer
The two definitions are not equivalent. However, the case where they aren't equivalent is one that we aren't interested in for algorithm analysis.

The standard definition implies the Papadimitriou definition. The proof is fairly straightforward, by following the definitions carefully.

> Suppose that $\exists c, n\_0 \in \mathbb{N}, \forall n \gt n\_0, f(n) \le c \cdot g(n)$. Let $c$ and $n\_0$ be such constants. We want to prove that there exist $c',d' \in \mathbb{N}^\*$ such that $\forall n \in \mathbb{N}, f(n) \le c' \cdot g(n) + d'$. Take $c' = c$ and $d = \max\\{f(x) \mid x \le n\_0\\}$. If $n \le n\_0$ then $f(n) \le d'$; if $n \gt n\_0$ then $f(n) \le c \cdot g(n)$. Either way, for any $n \in \mathbb{N}$, $f(n) \le c' \cdot g(n) + d'$.

The converse is not true. Again, unfolding the definition works up to a point, but then one little extra assumption is needed to make the proof go through.

> Suppose that we have $c', d'$ such that $\forall n \in \mathbb{N}, f(n) \le c' \cdot g(n) + d'$. We want to find $c$ and $n\_0$ such that $\forall n \ge n\_0, f(n) \le c \cdot g(n)$. If there is an $n\_0$ such that $\forall n \ge n\_0, g(n) \ge 1$, then we can factor $g(n)$: for any $n \ge n\_0$, $f(n) \le (c' + d'/g(n)) g(n) \le (c' + d') g(n)$, so we can take $c = c' + d'$.

The case where this proof fails is when there is no $n\_0$ such that $\forall n \ge n\_0, g(n) \ge 1$, i.e. when there are infinitely many integers $x$ such that $g(x) = 0$. (More generally, for real-valued functions, the problem case is when there is a set of values $(x\_k)\_{k\in\mathbb{N}}$ such that $\lim\_{k\to\infty} x\_k = \infty$ and $\lim\_{k\to\infty} g(x\_k) = 0$. Equivalently, that means that $g$ has no positive infimum.) Under the Papadimitriou definition as quoted here, the order of such a function includes all constants, but under the standard definition, there has to be a cutoff point above which $f$ is zero when $g$ is zero. For example, take the function $g : \mathbb{N} \to \mathbb{N}$ defined by $g(x) = 1$ if $x$ is odd and $g(x) = 0$ if $x$ is even. The function $f(x) = 1$ does not satisfy $f \in O(g)$ under the standard definition, but it does under the Papadimitriou definition.

This corner case isn't important in algorithm analysis because complexity functions are never “really” zero. With space complexity, there's always a bit of stack space just for the function call. With time complexity, it takes a few instructions to call a function even if the function does nothing.
> 2 votes

# Answer
The idea of $d$ is that you can say **for all** $n \in \mathbb{N}$ while within the other definition the inequality will hold after some $n$, such that $ n \> k$.

Also, when we talk about algorithms we're mostly concerned with functions defined over the integers.

*Edit:* Let's try to prove both directions:

*(traditional definition $\Rightarrow$ Papadimitriou's)* Given $f,g : N \rightarrow \mathbb{R^+}$ : $\exists c\>0,\delta \>0$ and for $n \ge \delta$ the inequality $f(n) \le cg(n)$ is true. Let $d = \max\_{n \in \[0,\delta\]}\\{f(n) - cg(n)\\}$ then the inequality $f(n) \le cg(n) + d$ is true for all $n$, from where the proof for this direction is done.

*(Papadimitriou's $\Rightarrow$ traditional definition)* Given $f,g : N \rightarrow \mathbb{R^{+}} : \exists \bar{c} \> 0, \bar{d} \> 0$ and *for all* $n \in \mathbb{N}$ the inequality $f(n) \le \bar{c}g(n) + \bar{d}$ holds. $$f(n) \le \bar{c}g(n) + \bar{d} = \bar{c}\left(g(n) + \frac{\bar{d}}{\bar{c}}\right) \Rightarrow f(n) \equiv O\left(g(n) + \frac{\bar{d}}{\bar{c}}\right) \equiv O\left(g\right)$$
> 1 votes

# Answer
Here's a hint: we'll show that Definition 1 (the usual definition) implies Definition 2 (Papadimitriou's).

Suppose that $f\in\mathcal{O}(g)$, so for some $c, k\>0$ we have $f(n)\le c\cdot g(x)$ for all $x\>k$.

Define a new function $d(x)=c\cdot g(x)-f(x)$ and define $d=\min\_{x\>0}\\{d(x)\\}$, so $d\le d(x)$ for all $x\>0$.

* If $d\ge 0$, then $c\cdot g(x)-f(x) \ge 0$ for all $x\>0$ so $f(x)\le c\cdot g(x)\<c\cdot g(x)+1$ for all $x\>0$ and hence $f\in\mathcal{O}(g)$ by definition (2).
* If $d\<0$, then since $c\cdot g(x)-f(x)=d(x)\ge d$ for all $x\>0$ so $c\cdot g(x)-d-f(x)\ge 0$ for all $x \> 0$ and so $f(x)\le c\cdot g(x)+(-d)$ for all $x \> 0$ and since $-d\>0$, $f\in \mathcal{O}(g)$ by definition (2).

A similar argument can be used to show the implication in the other direction.
> 1 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: Is it axiomatic that the Time Hierarchy Theorem holds true in all relativized worlds?
I learned from this post that ${\sf DTIME}^{\text{EXP}}(n^k) \neq \text{EXP}$ for a fixed $k$ for otherwise the Time Hierarchy Theorem would fail in that relativized world. However, is it possible to prove that *no* oracles exist in which the Time Hierarchy Theorem fails? Or is it just that we have not been able to discover any, that we assume that the Time Hierarchy Theorem never fails. Thanks.

# Answer
The proof of the time hierarchy theorem relativizes. This means that all the steps remain true if all Turing machines are given access to the same oracle $O$ (for arbitrary $O$). This implies that the theorem itself remains true if all Turing machines are given access to the oracle $O$.

So yes, it is possible to prove that no oracles exist with respect to which the time hierarchy theorem fails.
> 7 votes

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


title: Count-Min sketch: dyadic ranges

text:
# Question
Title: Count-Min sketch: dyadic ranges
Can anyone give me a proof as to why

> Any range over a unviverse {1...n} can be reduced to at most $2log\_2n$ disjoint dyadic ranges?

Where a dyadic range is a range of the form $\[x2^y+1....(x+1)2^y\]$.

This is in reference to the method for answering range queries with a Count-Min Sketch as mentioned in the original paper on CM-sketches

# Answer
> 2 votes
Here is proof by example: $$ \begin{align\*} &\[0110000,1101011\] = \\ &\[0110000,0110000\] \cup \\ &\[0110001,1000000\] \cup \\ &\[1000001,1100000\] \cup \\ &\[1100001,1101000\] \cup \\ &\[1101001,1101010\] \cup \\ &\[1101011,1101011\] \end{align\*} $$ More generally, the first step is to decompose your range $\[a,b\]$ into $\[a,2^k\] \cup \[2^k+1,b\]$, where $b \< 2^{k+1}$ (one of the ranges can be empty). Writing $b = 2^k + 2^{t\_0} + \cdots + 2^{t\_d}$, where $k \> t\_0 \> \cdots \> t\_d$, we decompose $\[2^k+1,b\]$ as follows: $$ \[2^k+1,b\] = \[2^k+1, 2^k+2^{t\_0}\] \cup \[2^k+2^{t\_0}+1,2^k+2^{t\_0}+2^{t\_1}\] \cup \cdots \cup \[2^k + 2^{t\_0} + \cdots + 2^{t\_{d-1}}+1, 2^k + 2^{t\_0} + \cdots + 2^{t\_d}\]. $$ Decomposing $\[a,2^k\]$ into dyadic ranges is similar but slightly more confusing, and I leave it to you.

---
Tags: sets, streaming-algorithm
---


# Question
Title: Can a schedule with cyclic precedence graph still be serialisable?
We know Every conflict serializable schedule is serializable, but not all serializable schedules conflict-serializable. (\*) so it means there is at least one serializable schedule that not conflict serializable.

One way of Testing conflict serializability is using Directed graph as mentioned http://www.cburch.com/cs/340/reading/serial/index.html

So if a graph for a schedule has a cycle, this schedule is not conflic serializable. so by using (\*) we can say maybe this schedule be a serializable . (i.e we cannot surely determine it's serilizabe or not, just we know it's not conflict serializable)

My inference is right? any idea?

# Answer
> 1 votes
> So if a graph for a schedule has a cycle, this schedule is not conflic serializable. so by using (\*) we can say maybe this schedule be a serializable

Yes. You cannot infer that a history is not serializable just because it is not conflict-serializable.

> so as a conclusion, it's contradict to Serializability Theorem that says that a history H is serializable iff SG(H) is acyclic.

No. You are talking about two different graphs and two different serializability criteria. And you are confusing them. See my explanation below.

---

The key point here is to tell serializability (SR, for short) from conflict-serializability (CSR, for short) and the polygraph (PG, for short) from serializability graph (SG, for short).

The definition for PG can be found in this paper. The results about SR and polygraph below are also in this paper.

The definition for SG and CSR can be found in this book chapter.

In the following, I list some key points on your questions.

1. SR $\supset$ CSR. In other words, if a history $h$ is CSR, it must be SR; however, the converse is not valid.
2. The Serializability Theorem is for CSR (*although it is called Serializability Theorem*):

A history $h$ is CSR $\iff$ SG(h) is acyclic.
3. For SR: a history $h$ is SR $\iff$ PG(h) is acyclic.
4. For a history $h$, SG(h) is more restrictive than PG(h) and leads to an efficient test for CSR. Specifically, we have the following complexity results:
    * Testing whether a history $h$ is CSR (or equivalently, whether SG(h) is acyclic) is polynomial.
    * Testing whether a history $h$ is SR (or equivalently, whether PG(h) is acyclic) is NP-complete.

Notice that the polygraph for a history for SR is quite different from the traditional graphs we learn in class. So don't assume that it is polynomial to test its acyclicity (actually it is *not*).

---
Tags: concurrency, database-theory, databases
---


title: Big O Asymptotic complexity

text:
# Question
Title: Big O Asymptotic complexity
I am trying to rank $\log n $, $\log\_{10} n $, $n \log n $, $n \log n^2 $, $n^{0.8}$, $\sqrt{n}$ in increasing asymptotic complexity. $\log n $ has base 2 unless specified otherwise.

The answer I have is $\log\_{10} n $, $\log n $, $\sqrt{n}$, $n^{0.8}$, $n \log n$, $n \log n^2$,

Is this right? And possibly explain the reason behind it? thank you!

# Answer
The answer is correct. Let's verify it

$\log\_{10}n $ and $\log{n}$ belong to the complexity class $O(\log{n})$, because they differ by a constant factor, hence $\log\_{10}n \asymp \log{n}$.

$n^{0.8} \succ \sqrt{n}$, because $0.8 \> \frac{1}{2}$. The last pair $n\log{n}$ and $n\log{n}^2$ belong to the complexity class $O(n\log{n})$ because they also differ by a constant factor ($n\log{n^2} = 2n\log{n}$), hence $n\log{n} \asymp n\log{n^2}$. Finally we'll show that $\sqrt{n} \succ \log{n}$ and $n\log{n} \succ n^{0.8}$. The last one is obvious and I'll leave to you to prove that $\sqrt{n} \succ \log{n}$ (I claim that is true, if you face problems with it I'll expand the answer with proof).
> 0 votes

---
Tags: asymptotics, landau-notation
---


title: Showing that M is NP-Complete

text:
# Question
Title: Showing that M is NP-Complete
> An instance of $M$ is a collection of sets $S\_1, \dots, S\_m$ and a bound $B$. A solution is a set $T$ containing $B$ distinct items, such that
>
> 1. each item in $T$ belongs to some $S\_i$, and
> 2. each $S\_i$ contains at most one item in $T$.
>
> Show that $M$ is NP-complete by giving a reduction $\mathrm{IS} \to M$

Any help on how to start would be appreciated!

# Answer
> 1 votes
You have to demonstrate that you can convert all instances of the decision problem of independent set to your problem, and then you have to prove that the independent set problem can only be solved if you can solve your problem about sets.

The decision problem of independent set is determining if an undirected graph contains an independent set with a number *K* of vertex.

To do that, you can start by labeling the vertex of every graph with numbers, like this:

It, doesn't matter if the numbers are in order or not, the only thing that matters is that you can number them with a unique numbering (no vertex share a number in the graph).

Then, you have to create the set of sets with the numbers of the labels of the vertex of the graph. If you create the set of sets in the correct way, you will have reduced independent set to your problem.

Good luck

Update

Solution:

> Then you have to create a set with the label of the number of each vertex $v\_i$ and every neighbour of that vertex. For the graph avobe you had something like $\\{1,4\\}$ $\\{2,4\\}$ $\\{3,4\\}$ $\\{4,5\\}$ and $\\{5,6\\}$ So if you can pick $B$ disctint elements according to the rules of your problem, that will mean that there exist an independent set of size at least $B$ on the graph

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