# Question
Title: Is it possible to create a human thinking and acting program on a computer?
Does Artifical Intelligence need something else, something that is not so limited as a computer to achieve the goal of building a humanly thinking and acting program?

If so, what might this be? I don't know much about quantum computers, but might they be a solution?

# Answer
> 1 votes
Quantum computers have the same power as classical computers, only they can apparently solve some problems much faster. In order to simulate a human, you need to consider two aspects:

* Cognitive aspect: The program should behave like a human being.
* Physical aspect: The object should *look* like a human being.

Turing suggested a way of sidestepping the second issue. He suggested limiting the interaction to a text-based "chat". Even in this case, the computer has to careful regarding reaction times: the computer can presumably type faster than a human and perform calculations faster.

There are several variants of the Turing test, but one of them involves many testers and two interviewees: a bona fide human and a computer. The computer is trying to pass as human. An interviewer gets assigned either the human or the computer, and should guess which is which. The computer passes the Turing test if the interviewer guesses no better than a random coin toss.

Current computers are not able to pass the Turing test. Whether they could potentially pass the test is at this point a philosophical and religious question. One advantage that humans have over computers is their large brain and their long learning period. However, if we could build large enough computers, so far we don't understand the algorithmic behavior of the brain, and so cannot mimic it. Artificial intelligence tries to ape human intelligence using different "hardware". Whether this approach can be successful or not is not clear.

In the past few decades, focus has switched from trying to emulate the brain to trying to solve certain tasks, such as translation. Modern techniques use statistical tools that are not aimed at mimicking behavior but only at mimicking competence. This approach works much better than earlier approached which did try to understand what human cognitive processes are based on. Perhaps this approach is hopeless if the goal is passing the Turing test.

So what is missing for artificial intelligence to succeed? Higher processing power? Computation techniques mimicking brain functions? Mechanisms like the Universal Grammar which might be hiding in our genes? Nobody knows. But for many people, there is no *theoretical* barrier, only practical ones.

---
Tags: artificial-intelligence
---


# Question
Title: Non-deterministic Turing machine to solve graph colouring
Consider the *graph coloring problem*: given an undirected graph $G$ and a natural number $n$ return yes if we can color the graph with n different colors and no otherwise.

I am able to design a deterministic Turing machine that would solve it with a greedy approach trying the different combinations of coloring with the $n$ colors. I think this takes exponential time although I'm not sure how to proof it.

However, I am not able to conceive a nondeterministic Turing machine that would do so. Can someone guide me designing an algorithm for this machine?

# Answer
> 3 votes
The algorithm would be as follows:

1. Go through each vertex and "guess" a coloring using non-determinism. This takes time $O(V\log n)$, since this is the time it takes to write all the colors.
2. Check that the coloring is legal, which also takes polynomial time. If it's not legal, it rejects, and otherwise it accepts.

By definition, a non-deterministic Turing machine accepts an input if there is some accepting computation path. So the machine accepts iff some valid coloring exists.

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


# Question
Title: If P is equal to NP, then what happens to the problems those can be solved in polynomial time?
Suppose that an algorithm $A$ is able to solve a problem in **NP** in polynomial time. Does this effect the good old sorting, searching, shortest path, minimum spanning tree etc. algorithms? Can this improvement pave the way for a $O(n)$ sort or $O(log^\*n)$ search?

Edit: P vs. NP problem can also be interpreted as "can we find something without searching?" that's why I wonder if that effects the other problems as well.

# Answer
First of all, it is not clear what you mean by an algorithm which is able to solve *any* problem in NP; usually one algorithm solves one problem. However, given a polynomial time algorithm for solving some NP-complete problem, you can solve any NP problem in polynomial time. However, every problem will require a different algorithm.

This doesn't necessarily affect problems which are already in P. Indeed, we have *unconditional* lower bounds on search and sort which show that no $O(n)$ sort or $O(\log^\* n)$ search algorithm exist, in restricted computation models. Even when tight bounds are not available (or when you consider a computation model for which good lower bounds are not available), there is no reason to assume that an algorithm for NP-complete problems is relevant.

On the other hand, if P=NP then *more difficult* problems are affected: you can show using a padding argument that P=NP implies EXP=NEXP, for example. But the implication doesn't go the other way around.
> 2 votes

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


# Question
Title: Are all NP-complete languages log-space reducible to each other?
NP-complete languages are reducible to each other in polynomial time. Does this mean that they are also log-space reducible to each other?

It seems as if this is true because in log-space, we can have polynomially many computations.

# Answer
> 7 votes
Wikipedia makes the following points:

1. It is unknown whether all NP-complete languages are NP-complete also with respect to logspace reductions.
2. However, "all known" NP-complete languages are NP-complete also with respect to logspace reductions.
3. There are some hints that a weaker class of reductions, AC0 reductions, may result in a different notion of NP-completeness.

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


# Question
Title: Reachability matrix in time $O(|V| \cdot |E|)$
Suppose that we are given a directed graph and we want to find out if a vertex $j$ is reachable from another vertex $i$ for all vertex pairs $(i, j)$ in the given graph. Reachable mean that there is a path from vertex $i$ to $j$. The reachability matrix is called transitive closure of a graph.

I want to write an algorithm that rus in time $O(|V| \cdot |E|)$ and calculates the transitive closure of a directed graph $G=(V,E)$.

I have tried the following:

```
 Transitive_Closure(G)
         for v=1 to |V|
               for u=1 to |V|
                        T(v,u)=0
         for v=1 to |V|
                for each u in Adj[v]
                        T(v,u)=1
                        for each w in Adj[u]
                                T(v,w)=1

```

But isn't the time complexity $O(|V| \cdot |E|^2)$? Or am I wrong?

This algorithm definitely finds the transition matrix, but it's even in $\Omega(|V|^3)$:

```
    Transitive_Closure(G)
      for i = 1 to |V|
          for j = 1 to |V|
              T[i,j]=A[i,j] // A is the adjacency matrix of G
      for k = 1 to |V|
          for i = 1 to |V|
              for j = 1 to |V|
                  T[i,j]=T[i,j] OR (T[i,k] AND T[k,j])

```

**EDIT**: Is the following algorithm right?

```
Transitive_Closure(G)
1.  for each vertex u in G.V
2.       for each vertex v in G.V
3.            T[u,v]=0
4.   for each vertex u in G.V
5.        BFS(G,u)
6.   return T

BFS(G,s)
1.  for each vertex u in G.V-{s}
2.       color[u]=WHITE
3.       d[u]=inf
4.       pi[u]=NIL
5.  color[s]=GRAY
6.  d[s]=0
7.  pi[s]=NIL
8.  Q=empty set
7.  ENQUEUE(Q,s)
8.  while Q!= empty set
9.          u=DEQUEUE(Q)
10.        for each v in G.Adj[u]
11.             if color[v]==WHITE
12.                color[v]=GRAY
13.                d[v]=d[u]+1
14.                pi[v]=u
17.                ENQUEUE(Q,v)
18.        color[u]=BLACK
19.        T[s,u]=1

```

# Answer
> 2 votes
This algorithm doesn't work. Consider a graph with four vertices 1,2,3,4 and edges $1\to2\to3\to4$. Your algorithm outputs $T(1,4)=0$ even though 4 is reachable from 1.

The running time analysis of the algorithm can be improved to $O(VE)$. The first loop takes time $O(V^2)$. The number of pairs $(v,u)$ in the second loop is the number of edges $E$, and for each pair $(v,u)$, the maximal number of $w$s is $V$. So the second loop runs in time $O(VE)$.

# Answer
> 2 votes
This answer summarizes some of the comments. The well-known Floyd–Warshall algorithm runs in time $O(V^3)$, and there is a matrix multiplication based algorithm running in time $O(V^\omega)$, which is however not so useful in practice.

The following algorithm runs in time $O(V(V+E))$. Starting at each vertex $v$, run a DFS/BFS from $v$ to find all nodes reachable from $v$. This is not quite $O(VE)$, but given that the output size $V^2$, the $V^2$ term in the running time is unavoidable.

What if we don't want to output the entire matrix, but only the non-zero entries? In this case we can modify this algorithm to run in time $O(VE)$. First we use DFS/BFS to find all the connected components. Let $V\_i,E\_i$ be the number of vertices and edges in the $i$th component, and note that $E\_i \geq V\_i-1$. We run the previous algorithm on each connected component, thus achieving a running time of $O(\sum\_i V\_i(V\_i+E\_i)) = O(\sum\_i V\_iE\_i)$. Using $V\_i \leq V$ and $\sum\_i E\_i = E$, we see that the overall running time is $O(VE)$ (in addition to $O(V+E)$ for the initial BFS/DFS).

In fact, this modification isn't really needed. The running time of BFS/DFS in component $i$ is $O(V\_i+E\_i) = O(E\_i)$, and so the running time of the original algorithm is in fact only $O(\sum\_i V\_i E\_i) = O(VE)$, given that we don't output the entire matrix but only the non-zero entries.

---
Tags: algorithms, algorithm-analysis, graphs
---


# Question
Title: n closest points in a set of lat/long coordinates
Here's my problem:

I have a website where people can search based on their location (which is converted to lat/long coordinates). I have many products stored in a database with their lat/long coordinates. I also have a function to calculate the distance between two points based on their coordinates.

Now I'm looking for a way to find one of these things:

* The n nearest products to the user's location.
* All the products within a radius of x kilometers from the user's location.

Both solutions would be fine for my application.

Currently I just iterate over all the database entries, find their distance, and sort them. This obviously gets way too slow with a lot of entries.

Are there any algorithms/data structures I can apply here to make it faster?

Thanks in advance!

# Answer
> 2 votes
Your problem (at least the second variant) is known as *2D range searching*. Commonly used data structures are range trees and k-d trees. Searching for *range searching* on the web will open you a window into the area. These lecture notes come up, for example.

---
Tags: sorting, databases, nearest-neighbour
---


# Question
Title: Quadratic lower bound for deciding the set of palindromes
How to prove a single tape Turing machine needs at least n squared time to decide palindrome?

This is an exercise from the "computational complexity - a modern approach" book.

# Answer
The lower bound you are after is a common application of *crossing sequences*. You can find many proofs of your lower bound on the web, for example these lecture notes, which come up if you search for `palindromes quadratic lower bound`.
> 2 votes

---
Tags: complexity-theory, turing-machines, lower-bounds
---


# Question
Title: Why is it important to solve a problem in Polynomial time, In cryptography?
I have just started to learn Cryptography.

I am trying to learn "Merkle-Hellman Knapsack Cryptosystem".

So, right at the beginning of the discussion, a question came in my mind:

Why is it important to solve a problem in Polynomial time?

# Answer
> 6 votes
The concept of polynomial time is a theoretical concept that is supposed to capture what kinds of problems are possible to solve "in practice". In practical cryptography, the goal one is interested in is that no government body can break the system in less than a 100 years (say). However, this concept is hard to reason about, for many reasons. One reason is that the set of problems that can be solved in a 100 years depend on your hardware, budget, and so on. Moreover, even given a specific algorithm for a problem, it is hard to estimate how much time exactly it will require to run. To circumvent these difficulties, cryptography theory suggests the following idea:

> Consider a cryptosystem which depends on a parameter $n$ tending to infinity. Analyze the security of the cryptosystem in terms of the asymptotic complexity of breaking it.

The asymptotic complexity doesn't depend too much on the exact hardware (as long as it's not a quantum computer); if next year a new CPU is revealed running 10 times as fast, a system that requires $O(2^n)$ time for breaking will still require $O(2^n)$ time for breaking. Moreover, we make the following assumption:

> An algorithm runs "fast" if it runs in polynomial time (in $n$).

Polynomial time is a natural class for many reasons, the reason here being that it is the smallest class which is closed under function composition and contains superlinear functions. Putting both ideas together, we get:

> A cryptosystem depending on a parameter $n$ is secure if it cannot be broken in time polynomial in $n$.

Here $n$ should be a reasonable parameter. One way of enforcing it is to require the encryption procedure to run in polynomial time in $n$.

This definition has led to a beautiful theory of theoretical cryptography. However, in practice polynomial time is not such a good notion, especially in cryptography, for two reasons:

* Polynomial time could be very slow in practical. For example, an encryption procedure running in time $O(n^{10})$ or $10^{10} n$ is not practical.
* Super-polynomial time could be practical, depending on the value of $n$. For example, $2^{n/2}$ is very practical for $n = 64$.

In applied cryptography, therefore, one tries to give running time estimates for a particular system (a particular setting of $n$) which is not asymptotic. Usually one calculates the number of "basic operations", a concept which is not defined precisely but is a better proxy than asymptotic complexity. When possible, actual simulations are run to show that the cryptosystem can be broken with weakened parameters, and to extrapolate the time it takes to break the full cryptosystem.

One problem with this approach is that it is going to be very difficult to prove that a system is secure. While this is true even for theoretical cryptography (we cannot prove the security of any cryptosystem), here it is seems that the best one can do is try to break the system and fail; proving a meaningful lower bound is probably too much to ask for.

One way to circumvent this difficulty in some situations is to use oracle (or black box) models. Suppose that a cryptosystem relies on some cryptographic primitive which we trust. We can imagine replacing this primitive by an idealized component. In this case, sometimes lower bounds on the number of queries to the black box can be proved. This allows us to gauge the security of the model, making the implicit assumption that the algorithm implementing the black box is completely opaque.

This is the approach taken by theoretical cryptography – assuming the existence of some secure cryptographic primitive (which we can't prove at the moment), it constructs cryptosystems and proves their security. However, this doesn't necessarily have practical implications, since in reality the parameter $n$ is fixed rather than tending to infinity. Even in cases in which we can rigorously prove that some cryptosystem requires $T(n)$ time to break (given some assumptions on the cryptographic primitives), usually the guarantees are very weak, and in order to get reasonably large $T(n)$, an impractically large $n$ is required.

For more information, check this classic paper on concrete security and this notorious article debunking theoretical cryptography.

# Answer
> 1 votes
Problems that can be solved in polynomial time are problems that can be solved quickly. It doesn't matter, whether an algorithm takes $O(n)$ or $O(n^2)$, it still take polynomial time, which is still much faster than a problem that grows exponentially with the input size.

So, now that you know that it can be solved, this means that it is easy to solve than more difficult problems. However, I think you refer (or want to get a deeper grasp) of the difference between **P** and **NP**. Both are categories of problems that can be solved in polynomial time, however only non-deterministic process can solve NP in polynomial time. In other words, polynomial time, makes it easy for a problem to be checked (so I am thinking of factorization in encryption).

PS: this might not be the best answer, but this could point you the direction for understanding

---
Tags: complexity-theory, polynomial-time, cryptography
---


title: If O(f) = O(g), why also Θ(f) = Θ(g)?

text:
# Question
Title: If O(f) = O(g), why also Θ(f) = Θ(g)?
How we can prove that if $O(f(x))=O(g(x))$ then $Θ(f(x))=Θ(g(x))$?

# Answer
> 2 votes
Hint: Follow these steps:

1. Since $O(f) = O(g)$ then in particular $f = O(g)$ and $g = O(f)$.
2. Since $f = O(g)$ and $g = O(f)$ then $f = \Theta(g)$ (which is equivalent to $g = \Theta(f)$).
3. Since $f = \Theta(g)$, if $h = \Theta(f)$ then also $h = \Theta(g)$, and vice versa, and so $\Theta(f) = \Theta(g)$.

It is somewhat confusing that $O(f) = O(g)$ means one thing and $f = O(g)$ means another thing; if $O(f)$ is the collection of all functions $h$ such that for large enough $n$ and some $C \> 0$, $h(n) \leq Cf(n)$, then $O(f) = O(g)$ is set equality while $f = O(g)$ should more properly be written $f \in O(g)$.

---
Tags: time-complexity
---


# Question
Title: What are some interesting applications of the skyline problem?
*You are given a set of $n$ rectangles in no particular order. They have varying widths and heights, but their bottom edges are collinear, so that they look like buildings on a skyline. For each rectangle, you’re given the $x$ position of the left edge, the $x$ position of the right edge, and the height. Your task is to draw an outline around the set of rectangles so that you can see what the skyline would look like when silhouetted at night.* Source

Drawing in practice I imagine can come in different forms, for example if a building is described by a triple `(leftX, height, rightX)` then the output can be a left to right ordered list $\\{x\_{1},h\_{1},x\_{2},h\_{2},x\_{3},h\_{3},x\_{4},h\_{4},...\\}$ where each $x\_{i}$ represents a vertical edge and each $h\_{i}$ represents a horizontal edge.

This problem is clearly defined and there are some quite efficient algorithmic solutions, however I could not find anywhere the motivation for this problem. Why would anyone want to solve it? Are there any interesting applications where being able to solve this problem efficiently is important?

# Answer
The "skyline problem" is an example of finding the Pareto front of a set of points in 2-D space. More generally it's an example of multi-objective optimization which has many applications.

You might find this thread relevant.
> 5 votes

---
Tags: reference-request, computational-geometry, graphics, applied-theory
---


# Question
Title: A non-regular language satisfying the pumping lemma
I got a problem to solve, which is to demostrate that the language $L$, given by:

$L = \\{ab^nc^n\mid n \geq 0\\} \cup \\{a^kw \mid k\geq 2 \wedge w \in \Sigma^\*\\}$

1. Satisfies the pumping lemma.
2. Is not regular.

For the question 1. I think it would suffice to demonstrate that for all $w \in L$, $w$ can be decomposed in the form $\alpha \beta \gamma$, where $|\beta| \neq 0$, and that every string $\alpha \beta^m \gamma \in L$, where $m \geq 0$, but after that I have no clear what I have to do, because I start thinking about cases, what if I have a string $w \in \\{ab^nc^n\mid n \geq 0\\}$... I should decompose it the way $\alpha = \epsilon, \beta = a$ and $\gamma = \text{the rest of the string}$ (because if we use $w = ab^0c^0 = a$, $\beta$ will have to be $a$, because we know that $\beta \neq \epsilon$), but in this case $\alpha \beta^m$ may not be in $L$, for example, if we choose $m = 0, \alpha \beta^m \gamma$ won't be in $L$, so I don't know what I'm doing wrong... perhaps I'm making mistakes in several steps.

Now, for the question 2. I don't even have an idea on how to start, if someone would help me I would really appreciate it

# Answer
> 6 votes
You are not supplying the definition of $L$, so here is one definition which works:

$$ L = \\{ a b^n c^n : n \geq 0 \\} \cup \\{ a^k w : k \neq 1 \text{ and } w \in \Sigma^\* \text{ doesn't start with $a$} \\}. $$

Choose a pumping length of $3$. A word $ab^nc^n \in L$ can be pumped by pumping the $a$ part. A word $aabw$ or $aacw$ can be pumped by pumping the $aa$ part. A word $aaaw$ can be pumped by pumping the first $a$. Finally, a word $bw$ or $cw$ can be pumped by pumping the $b$ part or $c$ part.

Your definition seems to be

$$ L' = \\{ a b^n c^n : n \geq 0 \\} \cup \\{ a^k w : k \neq 2 \text{ and } w \in \Sigma^\* \\}, $$

but for this language the pumping lemma does work. Indeed, apply it to $ab^nc^n \in L'$ for large enough $n$. Then $ab^nc^n = xyz$ so that $|y| \geq 1$ and $xy^iz \in L'$ for all $i \geq 0$. Considering the case $i = 2$, we see that $y = a$ necessarily. But then, taking $i = 0$ we get $xz = b^nc^n \notin L'$.

Perhaps the exercise meant you to use the version of the pumping lemma in which $i \geq 1$ instead of $i \geq 0$.

We can show that $L$ is not regular in many ways:

1. Use one of the many general versions of the pumping lemma which can force the $b^nc^n$ to be pumped. For example, the general version on Wikipedia states that there exists $p$ such that any word $uwv \in L$ with $|w| \geq p$ can be partitioned as $w = xyz$ so that $|xy| \leq p$, $|y| \geq 1$ and $uxy^iz \in L$ for all $i \geq 0$. Choose $u = a$, $w = b^nc^n$ for $n \geq p$ and $v = \epsilon$, and follow the usual argument.
2. If $L$ were regular then $L \cap ab\Sigma^\* = \\{ ab^nc^n : n \geq 1 \\}$ would also be regular, and you can prove that it isn't using the usual pumping lemma.
3. Use the Myhill–Nerode criterion. The words $ab^n$ are pairwise inequivalent, and so $L$ is not regular.

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


# Question
Title: Computer Science and Programming for a complete novice
everyone! I am going to learn mathematics in a university, but it will be rather ''pure'' math, so, I want to get some exposure to computer science on my own. The problem is, I've never tried any programming or computer science activities. I'm not sure where should I start. Now, I realise that internet is full of online or video courses about cs or codes, but they are specific, for example, ''how to learn C++/Python'' or ''algorithms''. As far as I'm concerned, what I need is some kind of introductory book for computer science( basics, how this and that works and why, what is this and what is that ). Though, some people say that it's better to learn some programming language first even before getting exposed to theoretical material. Thanks in advance, I will appreciate any answers.

# Answer
I started progamming as a kid and (at adulthood) graduated in Computer Science. I really don't know what's the best to learn first.

Computer Science is a breed of mathematics and programming is a craftworking. To implement the ideas of the first you must use the second.

IMHO programming is something you learn by demand while CS is a knowledge you study by passion.

The modern languages today (C#, Java, Javascript) are complex tools of trade and one learning it must dive in to learn it idiosyncracies (and not to mention the libraries and frameworks like jQuery, Hibernate, etc).

So while you are not willing to become a pro programmer I can advice you to use more "crude" languages like C||C++.

To get start in CS go to the basics: Algorithms.

There are a lot of classical and well studied problems like sorting, path finding/evalutaion, finding substring, etc.

While studing these problems you can learn how to implement some know solutions again IMHO that's can the best approach to get starting.
> 2 votes

---
Tags: reference-request
---


# Question
Title: Do we need recursion in programming language to solve any problem?
My question is simple: If we want to be able to solve **every problem, that we can solve using recursions**, do we need programming language to allow us use recursions?

Assuming we are allowed to use: conditional evaluation of blocks (if/else), cycles(for,while), dynamic allocation of memory.

I know, that we won't be able to implement everything the way we want. However, I'm asking whether we are able to solve everything, just by using different implementation - or by modification of algorithm to be non-recursive.

# Answer
> 4 votes
You do not need recursion, and as you suggest, and as confirmed by Dave Clarke's answer, you only need conditionals, loops and memory allocation and assignment.

You can use it to simulate recursion. Or more simply you can use it to implement arbitrary Turing machines. Just do it for a universal TM, so you get to implement only one :)

You can actually almost also do it without loops, but not quite. **You need at least one loop** if you expect to have infinite computations, which is implied by Turing power.

However, it could be an implicit loop that loops back to the beginning of the program, unless you execute a termination statement.

You can remark that control of a Turing Machine has exactly that: a single loop applied to a case statement, looking up a transition table.

If you wonder how abitrary many loops can be encoded into a single loop, is is very similar to dovetailing techniques use to explore space according to several indices. Think of indexing all pairs of natural numbers, with or without upperbounds, with a single integer.

**Added after the question was modified:**

If you consider "*every problem, that we can solve using recursions*", rather than "*any problem*", you do not change the question, unless you are a lot more precise (and restrictive) about what else is available, and what use of recursion you allow.

But an unrestricted recursion will give you at least one unlimited loop, which is usually enough to get Turing Power, if you allow unlimited memory allocation.

Note that there are limited uses of recursion that keep you below Turing Power, in precise settings. Look for example at primitive recursive functions.

I understand from your later comment that you made that change, so as to limit the request for solvability to what was already solvable, thus excluding such problems as the halting problem. If that is the intent, it is of course better stated. But, I guess, everyone had instinctively understood it that way, and the change was disconcerting (at least for me).

# Answer
> 8 votes
In short, to answer your questions:

(1) You can convert any recursive algorithm into its non-recursive form.

(2) As stated by the others, you have all the features you need.

## Computational Power (Turing-completeness)

You probably know that you cannot solve **any** problem, for instance, the halting problem is *undecidable*. And so are many other problems, such as deciding whether an arbitrary formula in first order logic is provable. Thus, with today's knowledge on computability, even the most advanced computer/programming system imaginable won't be able to process every query even if all the data is available.

When assessing the computational power of languages, computer scientists often use the notion of **Turing-completeness**: If you can describe (and run) any Turing machine in your programming language, then it is Turing complete and can solve any problem which can be solved by a Turing machine.

To get a feel for Turing machines, I strongly encourage you to use a Simulator and try to solve some simple problems.

In particular, have a look at the syntax of the sample program in the Simulator, which should give you an idea of your minimal language.

## Expressive Power and Minimality

When it comes to language design, expressive power is more important to me than the ability to solve any computable problem. Many useful domain-specific languages are not Turing-complete, but address specific problems very well.

However, equally powerful computational models such as the Lambda Calculus (functional programming) or the Pi Calculus (concurrent programming) show that you can have a very small set of elegant, composable language elements to construct larger systems, to be able to *reason* about their composition while having the computational power of Turing machines at the same time. Beautiful.

So if it is minimality you are looking for, take a closer look at the Lambda Calculus. Other noteworthy well designed minimal languages are:

* LISP
* Prolog
* Smalltalk and in particular Self

Feel free to add more languages to your personal list (and please let me know ;)

# Answer
> 3 votes
If you have all the features you mention, you don't need recursion.

Using dynamic memory you can implement a stack. This can be used to save "partial computations" and the while loop can loop through them, thereby mimicking recursion.

But just because you can do it, doesn't mean it's a good idea.

# Answer
> -1 votes
To complete others' answers, I think you might want to check the difference between a recursive process, and a recursive procedure. A recursive procedure doesn't necessarily execute a recursive process. When Babou writes that you can do everything without loops, he is probably secretly thinking about recursive procedures yielding iterative processes.

---
Tags: computability, programming-languages, computation-models, turing-completeness
---


title: Approximating the Kolmogorov complexity

text:
# Question
Title: Approximating the Kolmogorov complexity
I've studied something about the Kolmogorov Complexity, read some articles and books from Vitanyi and Li and used the concept of Normalized Compression Distance to verify the stilometry of authors (identify how each author writes some text and group documents by their similarity).

In that case, data compressors were used to approximate the Kolmogorov complexity, since the data compressor could be used as a Turing Machine.

Besides data compression and programming languages (in which you would write some kind of compressor), what else could be used to approximate the Kolmogorov complexity? Are there any other approaches that could be used?

# Answer
> 9 votes
I guess one possible answer to your question is this: Take a pseudorandom number generator $G$. Try to chose a generator which has some powerful *attacks* against it: a random number generator attack for $G$ is (for our purposes), an algorithm $A$ which, when given an imput string $s$, determines a *seed* $A(s)$, such that $G(A(s))=s$. Then approximate the KC of $s$:

```
input: s
Compute A(s);
if |A(s)| + |G| > |s| output: |s|
otherwise output: |A(s)| + |G|

```

Where $|G|$ is the length of the program that computes $G(s)$ (often quite short, as for linear generators).

Note that in practice, random number generator attacks are not as described: they may **fail** or produce incomplete results. In that case, you may adapt the algorithm so that it returns $|s|$ when the result of the attack is unsatisfactory. The same remark goes for compression algorithms.

The caveat to this approach as opposed to compression algorithms is that compression algorithms are in general much more suited to computing KC as they are tailored to work on *any* string, whereas an attack can work only if $s$ happens to be in the image of $G$ (*very unlikely*).

# Answer
> 8 votes
Any probability distribution. If you have a computable probability distribution that gives your data probability $p(x)$, then by the Kraft inequality, there's a computable compressor that compresses it in $-\log p(x)$ bits (round up if you object to fractional bits). This means pretty much any generative machine learning algorithm can be used.

This is why Kolmogorov complexity is so interesting, not because it's the ultimate compression algorithm (who cares about compression anyway), but because it's the ultimate *learning* algorithm. Compression and learning are basically the same thing: finding patterns in your data. The statistical framework built on this idea is called Minimum Description Length, and it was directly inspired by Kolmogorov complexity.

See also this question over at the cstheory StackExchange.

# Answer
> 5 votes
grammar coding is a less-frequently used version of a compression algorithm and can be taken as a "rough" estimate of Kolmogorov complexity. grammar coding is not as commonly used as a compression algorithm as other more common approaches maybe mainly because it doesnt improve much on compression from eg Lempel-Ziv on text based-corpuses, but it may do well on other kinds of data. the idea is to "compress" a string using grammar rules. a grammar derivation can result in a DAG (vs a less complex tree) so there is substantial representational complexity possible.

another option is to find smallest/minimal circuits representing a string but this is known to have very high complexity of computation and could succeed only on small strings.

generally the closer any approximation comes to calculating $K(x)$, the more intractable it is.

in an informal sense, generally *any* "approximation" of $K(x)$ must also be a "compression algorithm".

there are also other compression algorithm methods besides Lempel-Ziv "run length encoding" type approaches, for example vector algebra and the SVD can be used as a compression algorithm. also Fourier transforms are frequently used to compress images eg in JPG standard.

---
Tags: computability, approximation, data-compression, kolmogorov-complexity
---


# Question
Title: If p(n) is a polynomial in n, then is 1/p(n) polynomially bounded?
This is part of a homework exercise. Given is an algorithm that errs with probability $\frac{1}{2}-\frac{1}{p(n)}$ for some polynomial in the input size $n$. I'm trying to prove that a polynomial number of repetitions is sufficient to reduce the error probability to $\frac{1}{2^n}$.

Using the Chernoff bound I derived that $k \geq \frac{2n \ln(2)}{\bar{p}-1+\frac{1}{4\bar{p}}}$ with $p = \frac{1}{2}+\frac{1}{p(n)}$ repetitions is sufficient. However, I'm having a difficulty in showing that this quantity is polynomially bounded. Could someone shine some light on this?

# Answer
> 1 votes
In order to estimate the lower bound on $k$, you use the estimate $1/(1+\epsilon) = 1-\epsilon+\Theta(\epsilon^2)$, which is true as $\epsilon\to0$ (which is certainly your case). Using this, we can analyze the denominator: $$ \begin{align\*} \bar{p}-1+\frac{1}{4\bar{p}} &= \frac{1}{p(n)}-\frac{1}{2}+\frac{1}{2}\frac{1}{1+2/p(n)} \\ &= \frac{1}{p(n)}-\frac{1}{2}+\frac{1}{2}\left(1 - \frac{2}{p(n)} + \Theta\left(\frac{1}{p(n)^2}\right)\right) \\ &= \Theta\left(\frac{1}{p(n)^2}\right). \end{align\*} $$ Therefore the lower bound on $k$ is of order of magnitude $$\Theta(np(n)^2).$$

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


# Question
Title: Does last carry bit get added onto the sum calculated by full adder?
**Note:** This problem is from Introduction to Computing Systems: From Bits and Beyond(2nd) edition, 3.15, page 86.

**The Problem:**

I was able to do the problem and ended up with sum being 0010 and the last carry bit of 1.

Using a tow bit full adder, would the last carry bit be appended to the beginning of the sum, making it 10010(18 the correct answer with decimal alue addition)) or does it get omitted, making the answers different?

If it does get appended, how would I justify the answers are the same? The full adder takes account carry bits and binary bits?

# Answer
> 2 votes
Addition on $w$-bit registers (or memory locations) is effectively addition modulo $2^w$, that is the carry bit is thrown away. However, on x86 CPUs at least, before getting thrown away, it is copied to the *carry flag* or *overflow flag* (so the carry bit is actually not thrown away). An additional instruction, "add with carry", adds two inputs together with the carry flag. Using these instructions, you can (1) detect overflow (which happens if the carry flag is set), and (2) implement addition on multiples on $w$ bits. For example, suppose you want to add two integers $x\_1x\_0$ and $y\_1y\_0$, where $x\_i,y\_i$ is each a $w$-bit memory location. You first add $x\_0$ and $y\_0$, and then add $x\_1$ and $y\_1$ along with the carry.

To answer your specific problem, for 4-bit wide registers, 0111+1011=0010, and additionally the carry flag is set, if any.

---
Tags: arithmetic
---


# Question
Title: why is every self-reducible language in pspace
I understand that every self reducible language recursively queries its oracle with strings of length less than the input size. But how does that show that every such language can be solved in polynomial space?

# Answer
> 1 votes
You haven't defined self-reducible languages, so I'll take as an example SAT, and let you generalize the idea.

In order to solve SAT, we use the following recursive procedure:

1. If there are no variables, output the value of the formula.
2. Set the first variable to TRUE, and simplify the formula. Recurse. If TRUE is returned, return TRUE.
3. Set the first variable to FALSE, and simplify the formula. Recurse. If TRUE is returned, return TRUE.
4. Return FALSE.

When we set the first variable to TRUE, we need to keep a copy of the formula. At depth $k$ of the recursion, we have $k$ formulas, the size of each at most the size of the original formula. So for a formula of size $n$ having $m$ variables, the total space usage is $O(nm) = O(n^2)$, which is polynomial in the input size.

For general self-reducible languages the same technique applies, with similar results. The details depend on your notion of self-reducibility.

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


title: PAC learning model definition

text:
# Question
Title: PAC learning model definition
The probably approximately correct (PAC) learning model is defined as:

A concept class $C$ is said to be PAC-learnable if there exists an algorithm $A$ and a polynomial function $poly(·,·,·,·)$ such that for any $ε\>0$ and $δ\>0$, for all distributions $D$ on $X$ and for any target concept $c∈C$, the following holds for any sample size $m≥poly(1/ε,1/δ,n,size(c))$:

$Pr\[R(hs)≤ε\]≥1-δ$

where $R(hs)$ is the generalization error over a sample $S$ of size $m$ containing instances of variable $X$ following distribution $D$ and $size(c)$ is the maximal cost of the computational representation of $c∈C$.

I know $poly(1/ε,1/δ,n,size(c))$ is a polynomial. But what is the explicit form of $poly(1/ε,1/δ,n,size(c))$? What are the variables? What is its degree?

# Answer
There are no constraints on $poly(\cdot,\cdot,\cdot,\cdot)$ other than its being a polynomial, or more generally, a polynomially bounded function (that is, a function bounded by a polynomial); the difference doesn't matter in this case. Without loss of generality, you can assume that for some $A,B \> 0$, $poly(x,y,z,w) = A(xyzw)^B$.

The definition is trying to model the situation that only a small number of samples is needed to learn the concept. In order to quantify "small", we need first to decide with respect to what quantities it is going to be small (in this case, $\epsilon,\delta,n,size(c)$), and second, how small is "small". In this case, we define "small" to be any function growing at most polynomially in $1/\epsilon,1/\delta,n,size(c)$. In other cases we have more stringent requirements, say we want "small" to be polynomial in $\log \frac{1}{\epsilon}, \log \frac{1}{\delta}, n, size(c)$.

A standard definition in complexity theory is that of polynomial time. We say that an algorithm for solving some problem is *efficient* if on an input of size $n$ it runs in time polynomial in $n$, that is, its running time $T(n)$ is bounded by some polynomial in $n$. In your terminology, we could state this as $T(n) \leq poly(n)$ for some polynomial $n$. As before, if $T(n) \leq poly(n)$ for some polynomial $poly(\cdot)$, then in fact $T(n) \leq An^B$ for some $A,B\>0$, and so without loss of generality we can assume that $poly(n) = An^B$. But we don't want to decide in advance on the values of $A,B$. We are happy as long as *some* values of $A,B$ work.

Your case is similar, only the polynomial is allow to depend on several quantities rather than just one quantity.
> 6 votes

---
Tags: machine-learning
---


# Question
Title: Write an algorithm that finds array elements that sum up to some value
> The following is a pseudo-code named `PractOne`. It takes a finite list `A` of real numbers and gives the pair `(Alp,Bet)`, with `Alp` representing the maximum value of the entry in `A` and `Bet` representing the index of `Alp` in `A`. `Bet` is not always unique.
>
> ```
> function PractOne(A)
>     let Bet = 1
>     let Alp = A[Bet]
>     for i = 1 to length(A)
>         if A[i] > Alp then
>         let Bet = i
>         let Alp = A[Bet]
>     end if
>     next i
>     return (Alp,Bet)
> end function
>
> ```
>
> Please note that the function `length (A)` takes finite list `A=[b_1,..., b_j]` and gives the number of elements `j` in `A`. Also, `A[i]` gives the `i`th element in the finite list `A=[b_1,..., b_j]`.
>
> 1. Create an algorithm (named `PractTwo`) which takes a finite and non-empty list `A` of real numbers which are sorted in increasing order and a real number `C`, if there exists two indices `i`, `j`, such that `1<= i<= j<= length(A)` and `A[i]+A[j]=C`, then `PractTwo(A,C)` gives the pair `(A[i],A[j])`. When there is a case where more than one pair of indices exists with the required properties, then the function will give one of the valid pairs. Also, if the equality `A[i]+A[j]=C` is not satisfied for `i` and `j`, such that `1<= i<= j<= length(A)`, then the function will give back an empty pair `(,)`.
>
> Ensure, `PractTwo` completes its search with a maximum of `d*Length(A)` steps, where `d>0` is some constant not dependable on on `A`.

I have an idea...I'm thinking `PractTwo` requires more steps to factor into it the `1<= i<= j<= length (A)`, so...

> ```
> function PractTwo(A)
>     let Bet = 1
>     let Alp = A[Bet]
>     let j = A[i]
>     for i = 1 to length(A)
>         if A[i] > Alp then
>         let Bet = i
>         let Alp = A[Bet]
>     end if
>     next i
>     return (Alp,Bet)
> end function
>
> ```

I don't think this is complete, is what I've done so far correct?

> 2. Also, show that `PractTwo` gives back the correct value. Also explain how the implementation of `PractTwo` is completed in at most `d*Length(A)` steps.

# Answer
> 3 votes
PractOne seems ok. Could be very slightly improved by starting the loop at 2.

PractTwo is wrong, even without considering what it is supposed to do. You write (line 4) : `let j = A[i]`, but `i` is undefined. I have no idea what you are trying to do.

You have to find `A[i]` and `A[j]` in linear time. Linear time is the requirement to use at most `d*Length(A)` steps.

Achieving linear time requires being a bit more subtle in the computation. You use the fact that the array is sorted in increasing order. You start looking for `A[i]` starting from one end (say from small indices), and looking for `A[j]` from the other end (say from large indices), until `i` meets `j`, stopping before if you find a solution. Sometimes you increase `i` and sometimes you decrease `j` depending on whether the last sum `A[i]+A[j]` was greater or smaller than `C`.

I let you work it out in more details, and do the explanation.

---
Tags: algorithms, arrays, search-problem
---


# Question
Title: Can I overcome cache coherence in coding?
I know that cache coherence is the consistency of shared resource data that ends up stored in multiple local caches.

Can any programming languages handle this problem? If so, how?

# Answer
> 2 votes
I am following the rephrasing of the question by Dave Clarke.

A first remark is that cache is an ubiquitous concept in computation. In programming, you find it at many levels in programming systems. In the computer you have registers that act as caches for the main memory, main memory pages that are caches for the disk, and possibly disk files that cache bulk storage outside the computer. When you analyse memory hierarchy used by modern systems, each level can often be seen as a cache for the next level higher up.

At the low end, it can be even more refined in the processor structure.

At the high end, it also goes further, as caches (called proxies) are being used to speed up internet exchanges. Not to mention the NNTP protocol for distributed information which may be seen as composed only of caches, the memory being the union of all caches, much of the protocol being a form of cache coherence.

Of course, the importance of cache coherence, and the way it is implemented (or ignored) is dependent on the role of the cache, of the context of concerned applications that make use of the cache infrastructure, and their need for time of consistency accuracy.

A basic principle of caching is that it should be essentially invisible to its user. Hence it is expected to be implemented rather in the system that manages access to data rather than in the application accessing the data.

I am not an expert, but I would think that cache coherence is ensure by whatever manages the cache. At the smaller end, for registers, I would guess it is managed by the hardware. For paging I would think it is done by the OS kernel (but I am no system expert). An internet cache will be managed by the system implementing the communication protocol.

Programming languages can of course be used to implement cache systems, including maintaining cache coherence. Probably not any language. I would not use an interpreted language to handle low level caches. Doing system programming in Prolog could be a dubious idea.

However, I do not see what it would mean for a programming language to handle the problem for applications written in that language. The fact that caching may be involved depends on what application the language is used for, and how.

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


# Question
Title: Turing machine for unary encoded quadratic numbers
I want to design a turing machine that accepts strings of the form $0^{n^2}$ where $n \geq 1$ and I want to give an implementation description for this. So I am thinking that the algorithm can go something like this: If we have $0^{1^2}$, we can just cross off that only $0$ and accept. If we have $0^{2^2}$, we can first scan and cross off two zeros and then scan again and cross off the last two zeros since there are four zeros total. And then for $0^{3^2}$, we have $9$ zeros, so in three scans we can just cross off three zeros.

So can anyone tell me if I have the right idea and how I can put this into an implementation description? What I can't think of is, how would it know though that it has just one zero, or 4, or 9, or 16 and so on?

# Answer
A hint: $n^2 = 1 + 3 + 5 + 7 + \dots + (2n-1)$.
> 5 votes

# Answer
Imagine writing a "real" program like this:

```
boolean isQuadratic(String s) {
  if ( s == "0" )
    return true
  else if ( s == "00" )
    return true
  else if ( s == "000" )
    return true
  else if ...
    ...
  else
    return false
}

```

It's pretty clear that this can not work: there are *infinitely many* `else if` statements so you do not get a program at all. The same problem arises for Turing machines.

Think about how you would solve the problem in procedural pseudo code, without using high level API/abstractions, and working on an infinite tape (instead of getting a string of fixed length). Then translate this idea into the formalism of Turing machines.
> 3 votes

# Answer
I think your idea is workable (though there are other ways to do it), but there is still some work to be done to take care of "details".

But first, **in order to use your idea, you have to know what is the value of $n$ for your input.** And you do not know, and have no simple way to know. So you use the great trick of automata theory: you guess. **You guess by using non-determinism.** The first thing the automaton does is to enter a state where it write a sting of symbols $a$ on the tape. The state has non deterministic transitions so that it switches to a new state at some point, after writing some number $n$ of symbols $a$.

Now, the TM much check that the input actually contains $n^2$ symbols $O$.

You must keep carefully your string $a^n$ since it is your reference number for the computation. But you can use the TM to make as many copies as needed, using different symbols to avoid confusion. Basically, you will need one copy $b^n$ to implement a loop counter that erases $n$ symbols $0$ at each turn. To erase $n$ symbols ... you think hard.

And this is already help beyond a simple hint.

As stated in some comments it may not be the simplest solution. Its main advantage is that it teaches you to use non-determinism to guess (and check) ... and that makes life so much easier in automata theory.
> 2 votes

---
Tags: turing-machines
---


# Question
Title: If the language $A$ is decidable and the language $B$ is recognizable, then the language $A \cap B$ is recognizable?
I am discussing with a friend the following question:

If the language $A$ is decidable and the language $B$ is recognizable, Then the language $A \cap B$ is recognizable?

I believe it is. My point is that if the machine that recognizes B never halt in some string, so the bigger machine will never know what to answer.

The image makes my point.

But my friend says that the $A \ cap B$ is a subset of $A$, then it is decidable.

# Answer
> 3 votes
You are correct, without further information we can only say that $A\cap B$ is recognizable.

A simple example would be to let $B$ be any recognizable (but not decidable) language - the Halting Problem for example, if you want to be melodramatic, and let $A = \Sigma^{\ast}$. Then $A \cap B = B$, so clearly can't be decidable.

It is of course possible that the intersection happens to be decidable, (for example if $A \cap B = \emptyset$ is a trivial example), but this may not be true in general.

---
Tags: formal-languages, computability
---


# Question
Title: What is the worst case running time for an algorithm that combines insertionsort and mergesort?
Suppose that we have an algorithm "combination" that uses insertionsort for $n \< 100$ and mergesort for $n \geq 100$. Is the worst case running time of "combination" then $n^2$ or $n\log n$?

I was thinking that it's simply $n^2$, since the algorithm "combination" allows inputs larger than 100, in which case the worst case running time is $n^2$.

# Answer
> 2 votes
In fact, the running time of mergesort for large $n$ doesn't depend on what happens for small $n$. Recall the recurrence for mergesort:

$$ T(n) = 2T(n/2) + O(n), \qquad T(1) = O(1). $$

This recurrence holds even if you run insertion sort for $n \< 100$, since the running time of insertion sort on at most 100 elements can be swallowed in the big O constants. Even if you use exhaustive search on all $n!$ permutations for $n \< 100$, mergesort will still run in time $O(n\log n)$; the only change is that the big O constant would be rather huge.

---
Tags: algorithms, time-complexity, runtime-analysis, sorting
---


title: Digital Logic Settle Time

text:
# Question
Title: Digital Logic Settle Time
I have an exam tonight and I'm reviewing my midterm exam. I got this question completely wrong, with no solution given.

```
b) [10 marks] Consider implementing the logic formula 'signal 1' below as a
hardware circuit without any optimization.  You have 2-input 'AND' gates
that settle in 125 ps, 2-input 'OR' gates that settle in 150 ps, and
infinitely fast wires.  After all (original) inputs have been asserted, how
long does it take the circuit to settle?  Show any numerical calculations.

signal 1 = (p \/ q \/ r) \/ (s /\ t)

                                                               ans: ____ ps

```

I had no idea what to do so I simply multiplied every AND gate I saw by 125ps and every OR gate I saw by 150ps. I know this is not how to do it because of the number of gates. Can someone please explain this problem to me?

# Answer
This is the circuit corresponding to the logic formula 'signal 1', withhout any optimization.

```
_p_
   \
    OR_
_q_/   \
        OR_
_r_____/   \
            OR__
_s_        /
   \      /
    AND__/
_t_/

```

The signal takes 150ps to stabilize after the first OR gate, thus providing correct input for the second which then takes another 150ps to provide a correct input to the last Or gate. Total time is 300ps.

In the same time, the signal from s and t entries is ANDed in 125ps, so that it already stabilized and ready for the last OR gate when the previous one is ready after 300ps.

Thus the last OR gate can stabilize on correct signal after 300ps, and takes an additional 150ps to do that, bringing the whole time to 450ps.

One (longish) way to get the result is to check every path from an entry to an exit, adding the duration of every gate encountered. The highest value obtained is the answer. The previous way of computing is better.

**The optimized version**

Using OR associativity, you could change the formula to:

`signal 2 = (p \/ q )\/ (r \/ (s /\ t))`

which corresponds to the circuit:

```
_p_
   \
    OR________
_q_/          \
               \
_r______        OR__
        \      /
_s_      \    /
   \      OR_/
    AND__/
_t_/

```

This circuit would take only 425ps.
> 0 votes

---
Tags: logic, digital-circuits
---


# Question
Title: Are there algorithms with non-convex and non-concave computational complexity?
If I am not mistaken, an algorithm that runs in time $\Theta(f(n))$ also runs in $\Theta(f(n) + a\sin(bn))$ where $a,b$ are conveniently chosen constants. Therefore I believe that the computational complexity of each algorithm *can* be described using a function that is **neither convex nor concave**.

However, this seems like a made-up case. Are there some algorithms, whose complexity in $\Theta$ notation can be described **only** using a non-convex non-concave function, or can each complexity be conveniently transformed to a convex or concave function?

# Answer
Yes, there are algorithms whose complexity in $\Theta$ can only be described using a non-convex, non-concave function. Here's one such algorithm (that serves no practical purpose, but still).

* Read the length of the input $n$
* If $n$ is even, halt
* If $n$ is odd, loop for $n^2$ steps, then halt.

Suppose the complexity $T(n)$ of this algorithm is $\Theta(f(n))$, then there are $c,k$ so that for sufficiently large $n$, $cf(n)\leq T(n)\leq kf(n)$. Suppose (for contradiction) that $f$ is convex.

Let $n$ be odd and sufficiently large, we have that $2f(n)\leq f(n-1)+ f(n+1)$ (by concavity) and thus $\frac{2}{k}T(n)\leq\frac{1}{c}(T(n-1)+T(n+1))$. Substituting the original run time:

$$\frac{2}{k}(n+n^2)\leq\frac{2}{c}n$$

In other words, we have (up to some constants) $n^2\leq n$ which is a contradiction. So $f$ can not be convex, and by a similar argument can not be concave either.
> 3 votes

---
Tags: algorithms, complexity-theory, asymptotics
---


title: std::hash and separate chaining

text:
# Question
Title: std::hash and separate chaining
I'm attempting to implement my own generic hash table using separate chaining. I'm using the std::hash() method to create my hash function. I noticed in the description of std::hash() that:

For two different parameters k1 and k2 that are not equal, the probability that std::hash()(k1) == std::hash()(k2) should be very small, approaching 1.0/std::numeric\_limits::max()

Does this mean that given any two unequal strings, std::hash() will more than likely not select the same bucket? Does this mean my attempt to implement the hash table using separate chaining is moot considering this?

I'm implementing my hash table as a vector of lists. I thought there would be more collisions and therefore more elements in each list, but using the above function pretty much always gives me only one element in each list.

Please let me know if I'm misunderstanding this. Thanks.

# Answer
> 2 votes
No, `1/numeric_limits::max()` is the probability that two randomly picked objects have same hash code, not more.

Probability of collisions during insertion into hash table is calculated differently.

Given your vector has size M (i. e. $M$ buckets), and you already inserted $N$ entries into the hash table, the fraction of empty slots, i. e. the slots with zero entries, is $e^{-N/M}$, because in hash tables with separate chaining slots with 0, 1, 2, ... entries are Poisson-distributed. This means that the probability of any collision during inserting N+1-th entry is $1 - e ^{-N/M}$.

For example, if your vector has size 64 and you inserted 32 entries, probability of collision during insertion 33-th entry is $1 - e ^{-0.5} \approx 0.39$.

---
Tags: hash, hash-tables
---


title: TSP polynomial Time

text:
# Question
Title: TSP polynomial Time
How can it be proved that TSP cannot be solved in polynomial time ( Please bear that I don't have a hardcore computer science background).

# Answer
It's an open problem whether or not the Travelling Salesman Problem (TSP) can be solved in polynomial time. Proving that this is not possible would imply that $P \neq NP$.

What is known though, is that TSP is just as hard as a variety of other problems, such as SAT or the CLIQUE problem. In particular, if we could solve SAT efficiently (which most people believe isn't possible - though no proof exists), then we could also solve TSP efficiently. This can be shown by a process called a Polynomial Time Reduction between both problems. In other words, the goal is to transform an instance of TSP into an instance of SAT, then using the solution to that SAT instance to obtain a solution to your original TSP instance. If you are interested, then I recommend you look into the complexity classes $NP$ and $NPC$, and read about polynomial-time reductions between problems in this class.
> 3 votes

---
Tags: algorithms, graphs
---


# Question
Title: Question about big O notation for function
I'm just starting to learn Big O Notation and I was trying to understand how this function would scale:

$\frac{n(n-3)}{4}$

If the function was $n^2$, it would be quadratic, so O(n^2). However, the denominator gives me pause. Is this still a O(n^2) function? This is not homework. Thanks in advance for the help and clarification.

# Answer
> 1 votes
The denominator is just a constant so $O(\cdot)$ doesn't care about it. For all $n\geq 0$, $\tfrac14n(n-3)\leq 1\cdot n^2$ so $\tfrac14n(n-3)\in O(n^2)$.

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


# Question
Title: Reduction from 3 SAT to Monotone Exact 1 in 3 SAT
Can someone please help with a clear reduction from a 3SAT to a Monotone Exact 1 in 3 SAT. I tried searching by didn't find much.

# Answer
Here are some ideas to get you started. You can find on the internet simple gadget reductions from 3SAT to 1-in-3SAT. In monotone 1-in-3SAT you are not allowed to use negations, but if you allow clauses of width 2, you can add clauses $$ x\_i^+ \lor x\_i^- $$ for each variable $i$. This clause forces $x\_i^- = \lnot x\_i^+$, and so allows you to simulate negations. If you really insist that your clauses have width 3, you need to be slightly more devious. Try to figure out a way yourself, and only if you're unsuccessful, take a look at my solution below:

> For example, you can add three new variables $a,b,c$, replace $x\_i^+ \lor x\_i^-$ with the pair of clauses $ x\_i^+ \lor x\_i^- \lor a$, $x\_i^+ \lor x\_i^- \lor b$, and add the clause $ a \lor b \lor c$.
> 6 votes

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


title: What do we know about $NP \cap co-NP$?

text:
# Question
Title: What do we know about $NP \cap co-NP$?
* What do we need about the intersection of $NP$ and $co-NP$ apart from the fact that $P$ is a subset of it?

(beyond what these answers here say, What do we know about NP ∩ co-NP and its relation to NPI?, if $L\in NP\cap Co-NP$ is NP-Hard, then $NP=Co-NP$)

* Is there an example of a decision question which is known to be $co-NP /\ NP$ or $NP /\ co-NP$? (and great consequences of such a thing existing in the even that P not the same as NP)
* Do we know anything about how BPP, RP, co-RP or ZPP intersect NP or co-NP? (apart from the fact that $(P \subset (ZPP = RP \cap co-RP)) \subset BPP$ and hence whatever intersection with NP and co-NP follows just from this)

# Answer
> 9 votes
There is no decision problem that is (unconditionally) known to be in $coNP \setminus NP$. If we had a decision problem that we could prove is in $coNP$ and could prove is not in $NP$, then we would have proven that $NP \ne coNP$, from which it follows that $P \ne NP$. In other words, if we knew of such a problem, a proof that is in $coNP \setminus NP$ would provide a proof that $P \ne NP$. But of course we don't know of any proof that $P \ne NP$; that is a famous open question.

For similar reasons, there is no decision problem that is known to be in $NP \setminus coNP$.

The closest we have is the following: we know of decision problems that are in $NP \setminus coNP$, if $NP \ne coNP$. For instance, if $NP \ne coNP$, then SAT is in $NP \setminus coNP$. (You can replace SAT with any other problem that is known to be NP-complete.) It is widely conjectured that $NP \ne coNP$, so SAT is a good candidate for such a problem -- but we don't know any proof that $NP \ne coNP$ (that's another famous open problem).

We can also say that if $NP = coNP$, then there is no decision problem in $NP \setminus coNP$. From this plus the above discussion, we obtain the following useful fact:

> There is a problem in $NP \setminus coNP$ if and only if $NP \ne coNP$. If there is any problem in $NP \setminus coNP$, then SAT is one such problem.

The same remains valid if you replace SAT with any other NP-complete problem. Symmetrically, we also know:

> There is a problem in $coNP \setminus NP$ if and only if $NP \ne coNP$. If there is any problem in $coNP \setminus NP$, then TAUTOLOGY is one such problem.

You can replace TAUTOLOGY with any other problem known to be coNP-complete.

So, this is pretty much a complete characterization of those classes, up to our lack of knowledge whether $NP=coNP$ or not.

---
Tags: complexity-theory, np-complete, probability-theory, probabilistic-algorithms
---


title: Different weight sets for same problem?

text:
# Question
Title: Different weight sets for same problem?
Considering the case that we have a fixed set of training examples and a fixed ANN (i.e same number of input,output and intermediate layers). Is it possible that there exists more than one set of weights that all produce same desired results when applied to test examples. Basically can different weight matrix lead to same result behaviorally?

# Answer
I am not an expert on this field, but I believe the answer is yes.

If you think of a Neural Net as drawing a plane between multiple datasets in a multidimensional space, you can visualize a way in which separable data can be divided by multiple planes.

If you take the degenerate example in which there are only two points plotted on a simple 2-dimensional graph, you could certainly have a wide range of NNs that would correctly separate these two points. As you increase the number of neurons in your network, you increase the number of dimensions across which you can separate data, but even fairly densely clustered data still has effectively infinite space between it at a given level of magnification, leaving space for all kinds of networks that correctly separate test data.

Looking at it another way, you can apply the pigeon-hole principle here. If there are only n permutations of classification and \>n permutations of weights, then by definition at least 1 permutation will have multiple permutations of weights that select that classification. This is the case in most ANNs, in which you are classifying a comparatively finite set of inputs using a set of multiple neurons using floating point values.

As for the problem you're trying to actually solve, I am not sure that speed of your weights is a rational way to evaluate this problem. Different NN implementations may use different algorithms, but typically calculating an output using weights, even on a very complex NN is still quite fast. Once the weights have been calculated, it's just some simple multiplication to classify an entry.

The TRAINING process can be very time-intensive, however. The only way I can think of in which the weights affect your training process is with respects to which starting weights you choose. In this case, you could very well have "better" starting weights that result in a faster training process. The way to think of starting weights is like determining your location on a graph. Neural Network training algorithms try to work themselves into a minimum error state, and some weights are "closer" to a minimum than others. Also, some weights might put the training process into a situation where it is more likely to fall into local minima, which could make some starting weights more accurate than others.

That said, it's very difficult (not realistic?) to know for any given set of training data what your starting weights should be. You could randomly assign starting weights and train with each set to try and pinpoint the ideal training starting weight, but that weight would only be valid for that one set of training data on that specific neural network (and once you have trained the network, essentially your optimal starting weight IS a finished network).

So, ultimately, I'm not sure how useful this information will be for what you're trying to accomplish, but I'm interested in knowing more about what it is you think you might do!
> 2 votes

# Answer
Yes, it is absolutely possible. The best way to see why this is the case is to consider trivial cases. As always, remember the heuristic from mathematics: if you want to see whether a theorem is true, look first at some small examples. If you can find a small counterexample, then you know the theorem is false and you don't have to think about more complicated cases.

So, here is a very simple counterexample. Consider the trivial case where our training set has exactly one point in it (there's only one example in the training set). Then there certainly can be multiple weight settings that all reproduce that one example correctly.

For instance, suppose we have a neural network with one input, one output, and multiple layers. Suppose the neural network has dozens of intermediate nodes and connections. Then there are dozens of weights that can be chosen to try to fit the training set. We have dozens of degree of freedom.

Now suppose our training set has only a single point: the input $5$ should map to the output $7$. Well, it is immediately clear there there will be multiple settings of the weights, where each setting correctly causes the model to output $7$ when you give it the input $5$.

This is analogous to having a system of linear equations where you have more unknowns than equations: it's like you have a system of linear equations with dozens of unknowns and only one equation (one constraint). Such a system of linear equations has multiple valid solutions. Intuitively, when you have more degrees of freedom than constraints, typically you should expect there to be multiple solutions.
> 2 votes

---
Tags: machine-learning, neural-networks
---


# Question
Title: A little confusion with the Knapsack problem (a worked example)
I'm going through a worked example on the Knapsack problem:

My problem is that I don't understand quite follow the last bulletpoint. Where does the $x\_4 = 4/5$ comes from? I know $x\_4$ has to be a fraction of 1 (otherwise it breaks the inequality) but why specifically $4/5$? Any insight is highly appreciated.

# Answer
The (non-negative) variables $x\_1,x\_2,x\_3,x\_4$ must satisfy the constraint $$ 2x\_1+2x\_2+4x\_3+5x\_4 \leq 8. $$ If $x\_1=x\_2=1$ then this simplifies to $$ 4x\_3+5x\_4 \leq 4, $$ which implies in particular that $x\_3 \leq 1$ and $x\_4 \leq 4/5$ (since $x\_3,x\_4 \geq 0$).
> 3 votes

---
Tags: algorithms, dynamic-programming, linear-programming
---


# Question
Title: Question about 'Software Transactional Memory' by Shavit and Touitou
I've been reading the paper `Software Transactional Memory` by Shavit and Touitou. I understand how STM works in general but I need to understand this paper as it is the founding paper of the concept. However, I'm missing something rather fundamental of transactions. When I reed through the paper I never see what happens when a transaction fails. In general STM should retry a transaction when it fails, until it succeeds.

What the paper proposes is the following:

When a transaction starts it acquires the ownership of all the memory locations. Next, it computes the new values of each memory reference and writes them back to global memory. Finally, the transaction releases the ownerships. The transaction has succeeded and returns "success".

If a transaction tries to acquire ownership of a memory reference that is already owned by another transaction it will "help" this transaction by running the same transaction. But only if the owning transaction is not in the `failed` state or `success` state.

A transaction goes into the `success` state when it has successfully acquired all the locks. It goes into the `failed` state when

But, nowhere in the paper can I find something about retrying a transaction?

For example, I have applied the pseudocode in the text to this scenario:

Suppose a transaction `T1` that wants to run on dataset `[A, B, C]` and a transaction `T2` that wants to run on dataset `[C, D, E]`. No other transactions are running in the system.

In order of execution:

* `T1` successfully acquires the locks for `A`, `B` and `C`
* `T1` now has the state `success` because it acquired all the ownerships.
* `T2` wants to acquire the locks for `C`, `D` and `E`.
* `T2` can not acquire the lock for `C`.
* `T2` its status changes to `Failure`
* `T2` releases all the ownerships it had (none at the moment)
* `T2` knows that `C` is the reference that caused the failure.
* `T2` executes the same transaction as the process that owns `C`.
* `T2` notices that `T1` already is in the `success` state so it aborts.
* `T1` safely executes its transactions and commits the changes to the global memory

So nowhere in this scenario is `T1` executed again?

Any insights are greatly appreciated!

# Answer
> So nowhere in this scenario is T1 executed again?

"Retry" is *not* among the main topics of the classic STM paper.

You can let the initiator of $T\_1$ call `StartTransaction()` (treat $T\_1$ as a new transaction) upon each `Failure` until it receives a `Success`. The authors have just ignored it probably because they want to focus on the ingenious STM concept.

Retry is of course a big topic itself, for instance, in Composable Memory Transactions.
> 2 votes

---
Tags: concurrency
---


title: Algorithm analysis of nested loop

text:
# Question
Title: Algorithm analysis of nested loop
so I have this code:

```
for (int i=1; i < n; i=i*5)
      for (j=i; j < n; j++)
        sum = i+j;

```

And I'm wondering, what's the time complexity of this for loop?

To start off, I know the first line is logn base 5, with an additional check to exit out of the for loop.

Then, for the second line, I have the following:

```
i = 1
    j = 1, 2, 3,…, n        (n-5^0)+1
i = 5
    j = 5, 6, 7, …, n       (n-5^1)+1
i = 25
    j = 25, 26, 27,…, n     (n-5^2)+1
…
i = n
    j = n                   (n-5^k)+1

```

But now, I'm stuck. Any help is appreciated.

# Answer
> 0 votes
If you're interested in knowing the big-oh (O) then : logn (for first for statement) * (n-logn) times

Therefore, n\*logn - log^2(n)

For big oh complexity, the complexity for above mentioned nested loops would be:

n\*logn (since big-oh is only interested in larger values)

And as David motioned, that link has detailed explaination.

---
Tags: algorithms, time-complexity, runtime-analysis, loops
---


# Question
Title: Are there any natural $\Pi_2^P$-complete problems?
I know that the quantified Boolean formula problem for a formula $$ \psi = \forall x\_1 \ldots \forall x\_n \exists y\_1 \ldots \exists y\_n \phi $$ where $\phi$ contains no quantifiers and only the variables $x\_1, \ldots, x\_n, y\_1, \ldots, y\_n$ is an example of a $\Pi\_2^P$-complete problem. However, I wonder whether there are any natural problems known to be $\Pi\_2^P$-complete, just as *Circuit Minimization* is a natural $\Sigma\_2^P$-complete problem (see Polynomial hierarchy for details)?

# Answer
> 11 votes
There are very many natural complete problems for $\Pi\_2^p$, and there is a survey \[1\] on completeness for levels of the polynomial hierarchy, containing many such problems. The paper *On the complexity of min-max optimization problems and their approximation* \[2\] contains a nice overview of "min-max problems" with several proofs of completeness. The latter paper is opened with the following sentence:

> The computational complexity of optimization problems of the min-max form is naturally characterized by $\Pi\_2^p$, the second level of the polynomial-time hierarchy.

**Some problems:** Here are some examples, all of which are $\Pi\_2^p$-complete, listed in the aforementioned survey \[1\].

* $\forall \exists \text{3SAT}$: Given 3-SAT formula $\phi(x,y)$, is it true that for all $x$ there exists a $y$ such that $\phi(x,y)$ is satisfiable?
* NOT-ALL-EQUAL-$\forall\exists\text{3SAT}$
* MINMAX SAT, MINMAX CIRCUIT, MINMAX CLIQUE
* LIST CHROMATIC NUMBER
* GRAPH SATISFIABILITY
* DYNAMIC HAMILTONIAN CIRCUIT, LONGEST DIRECTED CIRCUIT
* SUCCINCT TOURNAMENT REACHABILITY
* CONSTRAINTS OVER PARTIALLY SPECIFIED FUNCTIONS
* ARGUMENT COHERENCE
* 3-COLORING EXTENSION, 2-COLORING EXTENSION
* (STRONG) ARROWING, GENERALIZED RAMSEY NUMBER
* etc., etc.

**References:**

\[1\] Schaefer, Marcus, and Christopher Umans. "Completeness in the polynomial-time hierarchy: A compendium." SIGACT news 33.3 (2002): 32-49. (PDF)

\[2\] Ko, Ker-I., and Chih-Long Lin. "On the complexity of min-max optimization problems and their approximation." Minimax and Applications. Springer US, 1995. 219-239. (PDF)

---
Tags: complexity-classes
---


# Question
Title: Maximum edges in degree-restricted digraph
How many edges can there be in a loop-free, asymmetric $n$-vertex digraph, if each node can have maximum total degree $k$ and minimum total degree $m$?

That is,

1. There are no edges $(v,v)$ (self-loops),
2. if there is an edge $(u,v)$, there is no edge $(v,u)$,
3. $d\_{\mathrm{in}}(v) + d\_{\mathrm{out}}(v)\leq k$ for every vertex $v$, and
4. $d\_{\mathrm{in}}(v) + d\_{\mathrm{out}} \geq m$ for every vertex $v$.

Thanks in advance.

# Answer
> 3 votes
The question has changed and will probably change again in the future. It wasn't clear to start with, so the question I was trying to answer is:

> How many edges can a directed graph on 22 vertices have, if the out-degree is at most 4, and the in-degree is at least 3?

Connect each node $x$ to nodes $x+1,x+2,x+3,x+4$, all indices taken modulo $22$. This satisfies all your conditions and has 88 edges, which is also trivially the maximum.

---
Tags: graphs
---


title: Which of these problems is not in NP?

text:
# Question
Title: Which of these problems is not in NP?
I see one solved ex on Algorithms.

> Which of the following is in NP?
>
> 1. Decision Version of TSP
> 2. Array is Sorted?
> 3. Finding the maximum flow network
> 4. Decision version of 0/1 knapsack?

This Ex Says Three of these problem is in NP. I Think all of them is in NP. Any expert could verify?

# Answer
> 5 votes
In fact, checking whether an array is sorted can be done in time $O(n)$, and there are efficient (polynomial time) algorithms for computing the maximum flow as well. On the other hand, the traveling salesperson problem is known to be NP-hard, as is the knapsack problem.

However, that is not what your question is about. Finding the maximum flow is not a decision problem, and so it is not eligible for being in NP. All other problems are decision problems, and as the preceding paragraph demonstrated, they are all in NP (one in them is even in P, and the other are NP-complete).

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


# Question
Title: Fastest known complexity for combinatorial ILP algorithm?
I'm wondering, what is the best known algorithm, in terms of Big-$O$ notation, to solve Integer Linear Programming?

I know that the problem is $NP$-complete, so I'm not expecting anything polynomial. And I know there are lots of heuristics and such that are used in practical applications like CPLEX, but I'm more interested in the formal, worst-case complexity of an exact algorithm.

Some $NP$-complete problems have algorithms in time $O(b^n p(n))$ where $1 \< b \< 2$ and $p$ is a polynomial. Vertex cover, independent set and 3SAT fall into this category, but general-SAT and TSP don't (as far as we know).

Can any such statements be made about Integer Programming, or particular sub-instances?

If anyone has a reference for the related problem of Quantifier Free Presburger Arithmetic, I'd be very interested in that too.

# Answer
> 4 votes
From what I can tell by searching, the definite survey seems to be:

Aardal, Karen, Robert Weismantel, and Laurence A. Wolsey. "Non-standard approaches to integer programming." Discrete Applied Mathematics 123.1 (2002): 5-74.

In particular, Section 2.1 discusses integer programming in bounded dimension, and presents algorithms due to different authors. Indeed, the survey lists many references, and discusses some practical implementations.

For a fixed number of variables, integer linear programming is polynomial time solvable by Lenstra's algorithm.

---
Tags: algorithms, complexity-theory, reference-request, np-complete, integer-programming
---


# Question
Title: Prove if $\{x^iy^jz^k \mid i \le2j\text{ or }j \le 3k\}$ is regular or not
$$L = \\{x^iy^jz^k \mid i \le2j\text{ or }j \le 3k\\}$$

To Prove: If given language is regular or not.

I know that it is not a regular language but I am not able to come up with the string which I can use in the pumping lemma to prove that it is not regular.

We can also divide $L$ into two parts: $$\begin{align\*} L\_1 &= \\{x^iy^jz^k \mid i \le 2j\\}\\ L\_2 &= \\{x^iy^jz^k \mid j \le 3k\\}\\,, \end{align\*}$$

so I just need the strings to be used in the pumping lemma for $L\_1$ and $L\_2$.

# Answer
It's not regular. **Hint**: Let $p$ be the integer of the pumping lemma and pump the string $x^{6p}y^{3p}z^{2p}$.
> 4 votes

# Answer
Decomposing the language $L$ into union or intersection of two simpler languages is useful to prove that L is regular, but it will not help you (in general) to prove that $L$ is not regular. The union or intersection of two non regular languages can be regular.

However, you can use these closure properties differently, to eliminate $x$. Consider the language $R=x^\*y^\*$. This language is regular. Its intersection with $L$ is $L'=L\cap R=\\{x^iy^j \mid i \le 2j\\}$ keeping only the words were $z$ has exponent $0$.
This is because $L\_2\cap R=\\{\epsilon\\}$. So $L'=L\cap R=(L\_1\cup L\_2)\cap R=(L\_1\cap R)\cup(L\_2\cap R)=(L\_1\cap R)\cup\\{\epsilon\\}=L\_1\cap R$ because $\epsilon\in L\_1\cap R$.

If $L$ were regular, then $L'$ would also be regular because $R$ is regular, and the intersection of regular languages is regular.

Thus if you can prove that $L'=\\{x^iy^j \mid i\le 2j\\}$ is not regular, you can infer that $L$ is not regular.

And you should be able to prove it for $L'$.

There are other ways of using closure properties to simplify the language. For example you could use an erasing homomorphisn to replace all $z$ by the empty word, which would lead you to the same language $L'$, And regular languages are closed under arbitrary homomorphism.

Closure properties can be very friendly, if you learn to use them. Then can considerably simplify some problems. See How to prove that a language is not regular?

With thanks to **Hendrik Jan** for catching a shameful bug.
> 2 votes

---
Tags: formal-languages, regular-languages
---


# Question
Title: Does every problem in NP have an exponential time algorithm?
I am not sure that every problem in NP have an exponential time algorithm. Since NP does not mean "not polynomial.", I think the answer is false. But I have no concrete reason about that.

# Answer
Yes, every **NP** problem has an exponential-time algorithm. One definition of **NP** is the "succinct certificates" definition: a language $L$ is in **NP** if, and only if, there is a relation $R$ on strings such that:

* there is a polynomial $p$ such that, whenever $(x,y)\in R$, $|y|\leq p(|x|)$,
* $x\in L$ if, and only if, $(x,y)\in R$ for some $y$, and
* there is a deterministic *Turing machine* that decides if $(x,y)\in R$ in polynomial time or not.

So, to decide if $x\in L$, all you need to do is try all possible $y$s of length at most $p(|x|)$ to see if $(x,y)\in R$ for some $y$. There are exponentially many possible values of $y$ to try.

To see the intuition behind succinct certificates, consider 3-colourability. There, a certificate is a 3-colouring of the graph. To describe a 3-colouring needs just a constant number of bits to say what colour each vertex of the graph has, so the length of the certificate is bounded by a polynomial. Obviously, a graph is 3-colourable if, and only if, it has a 3-colouring. And if I claim to have a 3-colouring of a graph, you can check that in deterministic polynomial time: just make sure I didn't give the same colour to two adjacent vertices.

To get a succinct certificate for any **NP**-problem, use the definition that a problem is in **NP** if it's decided by a nondeterministic Turing machine in polynomial time. Use a description of an accepting run of that machine as the certificate.
> 15 votes

---
Tags: algorithms, np
---


title: Length Preserving One way function

text:
# Question
Title: Length Preserving One way function
In the proof of existence of length preserving one way functions assuming the existence of one way functions, see

Length-preserving one-way functions

We need $p(n)$ to be a function which can not only be computed in polynomial time, but also, its inverse should be polynomial time computable. How do we ensure that ? $p(n)$ can be chosen to be monotonically increasing. But is that sufficient ?

# Answer
> 2 votes
$p(n)$ is just a polynomial that indicates the length of the output of the function $g$, as a function of the length of the input. Imagine that it's something like $27n$ or $2n^2$, and then read through the proof and you'll see how it works.

I didn't see any requirement to compute an inverse of $p(\cdot)$ in that proof. I'm not sure where you got that from. But anyway, if you wanted to invert it, any such polynomial is monotonic and can be easily inverted, e.g., by using binary search or using Newton's method.

---
Tags: complexity-theory, one-way-functions
---


# Question
Title: Idea behind $\mathsf{NP}\subseteq\mathsf{P}/\mathsf{Poly}\implies\mathsf{P}=\mathsf{NP}$ not true?
$\mathsf{3SAT}$ in $n$ variables is an $\mathsf{NP}$ complete problem.

Augment input to $\mathsf{3SAT}$ with constants $\\{a\_i\\}\_{i=1}^{n^c}$ where each constant $|a\_i|\<n^e$ to get an artificial problem ${\mathsf{3SAT}}\_{aug}$. There is a direct reduction from $\mathsf{3SAT}$ to ${\mathsf{3SAT}}\_{aug}$.

Assume that $\mathsf{NP}\subseteq \mathsf{P}/\mathsf{Poly}$ where suppose there exists $n^c$ constants for a fixed $c$ that will help solve any $n$-variate $\mathsf{3SAT}$ instance in $n^d$ time for a fixed $d$, however finding those constants offline takes exponential amount of time.

Since by hypothesis of $\mathsf{NP}\subseteq \mathsf{P}/\mathsf{Poly}$, we have constants that help solve $\mathsf{3SAT}$ in poly time, let augmented input to ${\mathsf{3SAT}}\_{aug}$ contain constants that help solve ${\mathsf{3SAT}}\_{aug}$ in poly time.

**${\mathsf{3SAT}}\_{aug}$ is $\mathsf{NP}-\mathsf{complete}$:** $\mbox{ }$ Since $\mathsf{3SAT}$ reduces to ${\mathsf{3SAT}}\_{aug}$, ${\mathsf{3SAT}}\_{aug}$ problem remain $\mathsf{NP}-\mathsf{complete}$.

**${\mathsf{3SAT}}\_{aug}$ is in $\mathsf{P}$:** $\mbox{ }$ Follows from hypothesis of $\mathsf{NP}\subseteq \mathsf{P}/\mathsf{Poly}$.

So why then is still $\mathsf{NP}\subseteq\mathsf{P}/\mathsf{Poly}\implies\mathsf{P}=\mathsf{NP}$ not true?

# Answer
> Since $\mathsf{3SAT}$ reduces to ${\mathsf{3SAT}}\_{aug}$, ${\mathsf{3SAT}}\_{aug}$ problem remain $\mathsf{NP}-\mathsf{complete}$.

The "reduction" isn't a polynomial time one. To create an input for ${\mathsf{3SAT}}\_{aug}$ you need to compute the constants $\\{a\_i\\}$ which takes exponential time.
> 2 votes

# Answer
Assume $\mathsf{NP}\subseteq \mathsf{P}/\mathsf{Poly}$. Let $\Pi$ be a NP-complete problem, by assumption, this problem can be solved by some circuit family. It is true that the problem $\hat{\Pi}$ where the input is a pair consisting of input to $\Pi$ and a circuit making an appropriate computation, is in $\mathsf{P}$. However, from this fact you cannot conclude that the original problem $\Pi$ is in $\mathsf{P}$. To obtain a solution to $\Pi$ using $\hat{\Pi}$ you have to guess the circuit - and this is not a priori possible in $\mathsf{P}$. You could guess the circuit nondeterministically, but then the argument would prove that $\mathsf{NP} = \mathsf{NP}$. However, if you start with a $\Sigma\_2$ set instead, it is possible to fix this reasoning and obtain $\Sigma\_2=\Pi\_2$ (Karp-Lipton theorem).
> 6 votes

---
Tags: complexity-theory
---


# Question
Title: Relativization results in class separation
We know that $P\neq NP$ problem cannot be demonstrated by relativization because there exists oracle relative to which they are equal.

Is there natural complexity classes that has been shown to be equal but are separate under some oracle?

# Answer
> 7 votes
Yes, check out the classes IP (interactive polynomial time) and PSPACE (polynomial space).

In 1988, Fortnow and Sipser \[1\] showed that these two classes have contradictory relativizations, that is, there exist oracles $A$ and $B$ ($A$ can be chosen to be $\text{PSPACE}$ itself) such that $$\text{IP}^A = \text{PSPACE}^A\text{, and}$$ $$\text{IP}^B \neq \text{PSPACE}^B .$$

Later, Shamir \[2\] showed that $\text{IP} = \text{PSPACE}$.

Chang et al. furthermore showed that for a random oracle $A$, $\text{IP}^A \neq \text{PSPACE}^A$ \[3\]. See *ibid.* for a nice introduction and overview. This result actually disproves *the Random Oracle Hypothesis* which states that

> the relationships between complexity classes which hold for almost all oracles must also hold in the unrelativized case \[3\].

**References**

\[1\] Fortnow, L. & Sipser, M., **Are there interactive protocols for co-NP languages?**, Inform. Process. Lett. 28, No. 5 (1988), 249-251.

\[2\] Shamir, A. **IP = PSPACE**, in "Proceedings, IEEE Symposium on Foundations of Computer Science, 1990," pp. 11-15.

\[3\] Chang, R., Chor, B., Goldreich, O., Hartmanis, J., Håstad, J., Ranjan, D., & Rohatgi, P. (1994). **The random oracle hypothesis is false**. Journal of Computer and System Sciences, 49(1), 24-39.

---
Tags: complexity-theory
---


# Question
Title: What advanced math topics are recommended for computer science?
I am enrolled in a computer science degree at the moment. I have looked around trying to find answers, but people tend to ask 'what is the minimum math needed for computer science' as opposed to what is recommended. I am very interested in theoretical computer science topics. My interests sort of jump around but right now I have a distinct interest in cryptography.

I have always loved math. In high school I did advanced math units - equivalent to calc 1 & 2, as well as discrete math. Right now I am doing a linear algebra unit and a calc 3 unit (as well as my cs units). Next semester I will be doing a unit on number theory. But what else? What other units would actually help with computer science? For example, I can't imagine learning about differential equations would be applicable to computer science.

# Answer
> 2 votes
If you want to do theoretical computer science, more math the better. Ultimately, learning math is not so much about learning specific topics, though that is of course important, it is also about gaining mathematical maturity, which means being able to think mathematically, being able to formalise and prove things, being able to abstract away inessential details and capture the essence of a problem. Of course, actually knowing lots of useful theorems is important too.

For crypto you'll need (at least) algebra (group theory etc), number theory, and discrete mathematics. Some logic wouldn't hurt either.

Linear algebra will help with machine learning and computer graphics.

Logic, topology and category theory will help for many Theory B topics (programming language semantics etc).

The list goes on ...

---
Tags: mathematical-programming
---


# Question
Title: Computational Complexity of 'Generic'/'Relaxed' Horn 3SAT
Horn 3SAT are described as the 3SAT with at most one positive literal. And its in P. What about the complexity of relaxed case of 2-Horn 3SAT i.e.

Each clause is in CNF, has exactly 3 literals, with at most 2 positive literals.

Can someone please help with the reference.

# Answer
Schaefer's dichotomy theorem gives you the answer. Apply it and see what you get, and let us know.

Looking at the modern formulation, in your case $\Gamma$ contains the three relations $\lnot x \lor \lnot y \lor \lnot z, x \lor \lnot y \lor \lnot z, x \lor y \lor \lnot z$. For each of these relations $R$, you have to go over the list of polymorphisms, and check whether one of them is a polymorphism of $R$. For example, to check whether the binary AND function is a polymorphism of $\lnot x \lor \lnot y \lor \lnot z$, you have to check whether $$ (\lnot x\_1 \lor \lnot y\_1 \lor \lnot z\_1) \land (\lnot x\_2 \lor \lnot y\_2 \lor \lnot z\_2) \\ \Longrightarrow \lnot (x\_1 \land x\_2) \lor \lnot (y\_1 \land y\_2) \lor \lnot (z\_1 \land z\_2). $$ If every $R \in \Gamma$ has one of the six polymorphisms, then your problem is in P. Otherwise, it's NP-complete.
> 3 votes

---
Tags: complexity-theory
---


# Question
Title: Efficient algorithm for this optimization problem? Dynamic programming?
I've created a diagram that depicts what I'm trying to accomplish.

**Full-size Image**

In the input sequence, the nodes are as close together as possible. But I want the white nodes to be as close to their respective black nodes as possible. The edges between nodes can be lengthened to try to minimize this error. They cannot be shortened. So, `1 -> 2` can be no less than 4, for example.

I've included a possible solution. The edges that have been lengthened are labeled. Note that lengthening an edge shifts all the nodes to its right.

This axis is continuous, but I could possibly discretize it if that helps.

I'm thinking a dynamic programming approach could work here but I'm not sure - I was never very good with DP.

What's the fastest running algorithm that can solve this? Can this be categorized / re-framed as a well-known problem?

# Answer
This is just an extension to @Sébastien Loisel's answer.

Notice minimize $(x\_i-y\_i)^2$ subject to $x\_i-x\_{i-1}\ge c\_i$ is equivalent to minimize $(x\_i-(y\_i-c\_i))^2$ subject to $x\_i\geq x\_{i-1}$. Let $a\_i=y\_i-c\_i$, then this is precisely the isotonic regression problem. There exist a $O(n)$ time algorithm.
> 5 votes

# Answer
If you discretize the axis then you can use dynamic programming. For each ball $b$ and feasible location $\ell$ (within some reasonable bounds), calculate the best mean squared error for the first $b$ balls. This can be done usually only the same kind of information for ball $b-1$.
> 4 votes

# Answer
This is a quadratic program. You are trying to minimise the sum of $(x\_i-y\_i)^2$ subject to $x\_i-x\_{i-1}\ge c\_i$.
> 2 votes

---
Tags: algorithms, dynamic-programming
---


# Question
Title: What type of algorithms are faster with a quantum computer?
I am a beginning CS student and I am learning algorithms. I heard that even with quantum computers, that general sorting algorithms can never have better than $n\log n$ time. However, I also know that factoring algorithms would be a lot faster. In general terms what kind of algorithms would become substantially faster with quantum computers?

# Answer
> 13 votes
* Shor's algorithm which puts FACTORING in BQP (*bounded error quantum polynomial-time*, effectively the quantum equivalent of P) also can be used to solve the DISCRETE LOGARITHM problem, where we want to find an integer $k$ such that $a^{k} = b$ where $a$ and $b$ are given, in (quantum) polynomial time. The DISCRETE LOGARITHM problem has the same status as the FACTORING problem in that we don't know whether they are polynomial-time solvable, so this might not be a speed up.
* Grover's algorithm gives a quadratic speed up in searching unsorted lists (which can be used as a speed up for a lot of algorithms).
* Simulating quantum systems is also in BQP, but exponentially slower on a classical TM.
* Solving Pell's equation (not really one equation) is in BQP, another exponentially speed-up.
* There's also a number of other, more obscure, problems that are in BQP, but appear not to be in P. Wocjan and Zhang give a good starting point to dig them up.

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


# Question
Title: Do not understand why log n = O(n^c) (for any c>0)
Can anyone help me understand this equation?

> $\log (n) = O(n^c)$ (for any $c\>0$)

Does it mean that $O(\log (n)) \< O(n^c)$ (for any $c\>0$)?

Added:

Please also prove that $\log (n) = O(n^c)$ is true.

# Answer
> 16 votes
It's not actually an equation $f = O(g)$ is a lazy shorthand that should be written $f \in O(g)$. So if you look back at the definition of $O$, you should be able to see what $\log n \in O(n^{c})$ for any $c \> 0$ means:

> For every $c \> 0$, there exists $n\_{0} \geq 0$ and $k \geq 0$ such that $\log n \leq k\cdot n^{c}$ for all $n \geq n\_{0}$.

Always remember that $O(\cdot)$ describes a *set*, $O(\log n) \< O(n^{c})$ doesn't actually make sense (unless you make up a special meaning for $\<$, but then no-one will know what you're talking about). You could say $O(\log n) = O(n^{c})$, as equality for sets has a understood meaning, though of course this statement in particular would be false.

As John Kugelman points out in the comments below, normal set relations *do* make sense, so $O(f) \subset O(g)$, $O(f) \subseteq O(g)$, etc., make sense.

---
Tags: asymptotics
---


title: SPIN / Promela Verification

text:
# Question
Title: SPIN / Promela Verification
I have this code here which performs the 'leader election' among a specified number of processes. In Promela, it is written as:

```
  #define N 5       /* this is the number of processes */
  #define I 3   /* node that is given the smallest number    */
  #define L 10  /* size of the buffer, channel of channels  (>= 2*N) */

   mtype = { one, two, winner };
   chan q[N] = [L] of { mtype, byte};

   byte nr_leaders = 0;

  proctype node (chan in, out; byte mynumber)
  { bit Active = 1, know_winner = 0;
    byte nr, maximum = mynumber, neighbourR;

    xr in;  /* exclusive recv access to channel in */
    xs out; /* exclusive send access to channel out */

    printf("MSC: %d\n", mynumber);
    out!one(mynumber);
  end:  do
    :: in?one(nr) ->
        if
        :: Active ->
            if
            :: nr != maximum ->
                out!two(nr);
                neighbourR = nr
            :: else ->
                /* in case the number equals the max one */
                assert(nr == N);
                know_winner = 1;
                out!winner,nr;
            fi
        :: else ->
            out!one(nr)
        fi

    :: in?two(nr) ->
        if
        :: Active ->
            if
            :: neighbourR > nr && neighbourR > maximum ->
                maximum = neighbourR;
                out!one(neighbourR)
            :: else ->
                Active = 0
            fi
        :: else ->
            out!two(nr)
        fi
    :: in?winner,nr ->
        if
        :: nr != mynumber ->
            printf("MSC: LOST\n");
        :: else ->      /* declare the winner */
            printf("MSC: LEADER\n");
            nr_leaders++;
            assert(nr_leaders == 1)
        fi;
        if
        :: know_winner
        :: else -> out!winner,nr
        fi;
        break
    od
  }

  init {
    byte proc;
    atomic {
        proc = 1;
        do      /* iterate through the processes */
        :: proc <= N ->
            run node (q[proc-1], q[proc%N], (N+I-proc)%N+1);
            proc++
        :: proc > N ->
            break
        od
    }
  }

```

I'm interested in how I can edit this so I can *verify* that **all processes terminate** after I run the code through Spin and that **all the processes agree about the one elected leader** (that there's one leader).

On this link: http://spinroot.com/spin/Doc/SpinTutorial.pdf on page 31, there's a SPIN property liveliness which includes the verification of termination, so that's what I'm trying to implement now, besides the mutual agreement of the leader.

Thanks for the input!

# Answer
For the "all the processes agree about the one elected leader" part:

It is a combination (conjunction) of

1. No more than one process can ever be declared to be the leader: $\Box (\textrm{nr} \\\_ \textrm{leaders} \le 1).$
2. Eventually a leader is elected: $\Diamond (\textrm{nr} \\\_ \textrm{leaders} = 1).$
> 2 votes

---
Tags: computation-models, model-checking
---