# Question
Title: Construct Optimal Directory Trees Efficiently
**Question:**

I want to construct a optimal directory tree structure to access $n$ ($n \< 256$) elements using only the keyboard with as few key presses as possible. For this one could consider the directory as double linked list with connections between the first and the last element. To access element E, one then would traverse the list until the appropriate subdirectory S, enter S and restart from there until E is selected.

There are some natural requirements:

* the elements in the tree structure are lexicographically ordered
* the arity of the tree might be \>2.
* I would like to apply custom weights to some elements
* the cost to be minimised is the weighted average of the total click count to access all elements (i.e. $c = \sum\_{e \in E} w(e)\*c(e)$, where $E$ is the set of elements, $w(\cdot)$ the weight for each element and $c(\cdot)$ the cost to access each element. $c(\cdot)$ depends on the chosen directory structure, of course.)

I'm struggling to find a good solution here. I do not know any standard tree that would fit in here as there might be no elements in intermediate nodes.

So, I'm looking for hints to literature. Maybe someone even knows an efficient algorithm? Bruteforce in Python takes too long to run, Bruteforce in C++ take too long to code :).

**Motivation**

I feed my stereo from a single board computer using the DLNA protocol. I want to access my music (artist-folders are the elements) as fast as possible. The stereo only supports "up", "down", "enter" and "escape" to navigate.

**Clarifications**

$c(e)$ is the number of clicks needed to access element $e$ from the top of the directory. $c(\cdot)$ depends on the directory structure. To access the lexicographically third element in a long list, one needs exactly 3 clicks (2x down, 1x enter). For the directory structure $((a, b), (c, d))$ one would only need 2 clicks to enter $c$ (2x enter).

Naming the subdirectories will not be a problem. Since the elements keep their order, I can use the names of the first and the last elements, as in a dictionary.

# Answer
One way is to use a Huffman code, over an alphabet of size $k$, whre $k$ is the number of letters you're willing to use on the keyboard. Make the weight for an entry be the "probability" for that entry (how often that entry is selected). Then a Huffman code will minimize the expected number of key presses. There's a standard algorithm for constructing a Huffman code.

The potential drawback is that it doesn't use the keys of the keyboard in the way you suggest; rather than using up/down to move forward/backward in a directory, the $k=4$ keys are all treated as equal, and each keypress moves you one level down in the tree. In other words, each directory has at most $k$ entries, and you select an entry with a single keypress. You might or might not be happy with the user experience. If you prefer, you can set $k=2$ and use only the up/down keys for selection (each directory has two entries; press 'up' to select the first or 'down' to select the second, and it will jump immediately to that entry). This will require fewer key presses than the approach you are imagining, but does require you to find a way to name each of the resulting nodes in the tree with a human-understandable category (i.e., pick a name for that directory/entry).
> 2 votes

---
Tags: search-trees
---


title: "Type" of a function template?

text:
# Question
Title: "Type" of a function template?
In C++ a simple function like

```
int id_int(int x){return x;}

```

has type `id_int :: int->int` a class template like

```
template<class T>
class List<T>{...};

```

has kind `List :: *->*`

But what is the type or kind of a function template like

```
template<class T>
T id(T x){return x;}

```

Could it be `id :: \x. x->x`? Does this even make sense?

# Answer
A function like `T id(T x){return x;}` is actually a (parametrically) polymorphic function, and there are many frameworks that allow assigning a type to such beasts.

One of the most popular frameworks to talk about such things is system F, which allows expressing the type of the above statement as: $$\forall T:\*.\ T\rightarrow T$$

This requires the ability to *quantify over types* to form other types, which is the main feature of system F. Note that because `id` is a *value*, it's type has itself a *kind*, that is $$\forall T:\*.\ T\rightarrow T\ \ :\ \ * $$

in keeping with the analogy with `List`, whose kind is, as you noted, $\*\rightarrow \*$, which makes it a *type constructor*.

Note also that the `List` type constructor is not a term in system F, for that you need to go further out to system ${F}\_\omega$, which was designed in part to study how polymorphism and type constructors may interact.
> 1 votes

---
Tags: type-theory
---


# Question
Title: What is the set of all minimal 3CNF formulas?
**Definition:** A **minimal** 3CNF formula is an **un**satisfiable 3CNF formula with **minimum** clauses connected by conjunctions, where each clause is disjunction of 3 literals, that is if **any** of it's clauses is removed from the formula, then the 3CNF formula becomes **satisfiable**.

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

In a **minimal** **k**-cnf formula, there should be 2**k** different **k** literals clauses exactly, so in a **minimal** 3CNF formula, there should be 23=8 different 3 literals clauses exactly.

That's what I think anyway, but correct me if I am wrong.

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

# Answer
> 2 votes
The number of minimal formula is finite. Indeed, if a formula is minimal, then no clause can be repeated. Now there are $(2n)^3=8n^3$ possible clauses, so there are at most $2^{8n^3}$ different formulas with no repeated clauses. Thus there are at most $2^{8n^3}$ minimal formula, which is finite.

I don't know of any clean way to count the number of minimal formula; probably there is no simple formula for it. You could try computing the number for $n=1,2,3$ by brute-force, then looking up the resulting sequence in OEIS, but I don't expect you to find any simple expression for this number.

What you are thinking is wrong. A minimal, unsatisfiable formula can have more than 8 clauses.

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


# Question
Title: Context Free Grammar: at least 2 1's, at most 2 0's
Been having some trouble trying to come up with a CFG for this language: all binary strings that contain least 2 1's and at most 2 0's

So far, I've come up with this:

S --\> T | 0T | T0 | T0T | 00TT | TT00 | 0T0T | T0T0 | 0TT0 | T00T

T--\> 1T | V

V--\> 11Z | 1Z1 | Z11

Z--\> 1Z | epsilon

I realize this is mostly likely incorrect/redundant, so any feedback would be extremely helpful. Thank you!

# Answer
*Hint*

If $L\_{i j}$ is the language with at least $i$ $1$s and at most $j$ $0$s

$$\begin{align} L\_{2 2} &= 1 \\, L\_{1 2} \\, | \\,?\\ ... \\ L\_{0 0} &= \\,? \end{align}$$

---

Edited to answer the correct question.
> 1 votes

# Answer
Your language is regular, for example it is described by the regular expression $$ 111^\* + 111^\*01^\* + 1^\*011^\* + 101 + \\ 111^\*01^\*01^\* + 1^\*0111^\*01^\* + 1^\*01^\*0111^\* + 1010 + 1001 + 0101. $$ You can convert this regular expression, or (better) a finite state automaton (deterministic or non-deterministic) accepting the language, into a context-free grammar.
> 0 votes

# Answer
I'll write down some simple productions, and on the right hand side I note the conditions for each non-terminal symbol. For example "A = ≥ 2, ≤ 1" means "A must produce a sequence containing ≥ 2 ones, and ≤ 1 zeroes".

```
S -> 0A | 1B       A = ≥ 2, ≤ 1. B = ≥ 1, ≤ 2
A -> 0C | 1D       C = ≥ 2, 0. D = ≥ 1, ≤ 1
B -> 0D | 1E       E = ≥ 0, ≤ 2
C -> 1F            F = ≥ 1, 0
D -> 0F | 1G       G = ≥ 0, ≤ 1
E -> 0G | 1E
F -> 1H            H = ≥ 0, 0
G -> 0H | 1G
H -> 1H | eps

```

We can take some shortcuts for non-terminals that have only one production or are only used once:

```
S -> 0011H | 01D | 10D | 11E
D -> 01H | 1G
E -> 0G | 1E
G -> 0H | 1G
H -> 1H | eps

```

Another advantage is that both grammars are unambiguous. For parsing, the first version is in LL(1), which is about the easiest kind of grammar for parsing.
> 0 votes

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


# Question
Title: What exactly is going on in a proof by induction of a recurrence relation?
In CLRS, it works through an example going through a recurrence relation proof using the "substitution method".

We have the recurrence $$T(n) = 2T(\lfloor n/2 \rfloor) + n \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4.19)$$

It claims:

> We guess that our solution is $T(n) = O(n \lg(n)).$

We assume that $T(m) \leq cm\lg(m)$ for all $m \< n$ (in particular, for $m = \lfloor(n/2) \rfloor$, and need to show that $T(m) \implies T(n).$

I'm fine with this; this seems like a standard case of strong induction, but what I don't understand is the explanation of the base case (which we also need to prove):

Could someone explain this paragraph to me? More specifically:

* What are boundary conditions?
* How do we know the base case? We're only given $T(n)$ recursively; there's no initial case when $n$ is, for example, $1$. How, then, do we know that "$T(1) = 1$"?
* I don't understand what the paragraph is getting at. How do we determine the base case in the general case?

Also, I've noticed that, in practice examples, the author has failed to mention the base case completely when doing these types of proof; that is, they assume the inductive hypothesis, and prove that (for all $m\<n$), $T(m) \leq \text{something} \implies T(n) \leq \text{something}$, but they leave it at that, as though that were sufficient for the proof. In fact, these proofs don't even explicitly state the inductive hypothesis. For example, in the case of (4.19), they would write something like: $$ \begin{align} T(n) \leq c\lfloor( n/2) \rfloor \lg(\lfloor n/2\rfloor) \end{align} \\ \leq \ ... \\ \leq cn\lg(n) \ .$$

Is this acceptable, or would that constitute a sloppy proof?

# Answer
> 1 votes
> What are boundary conditions?

The boundary condition here refers to the base case(s) of the induction. This makes more sense in an intuitive manner if we consider, for instance, a 2D case: Suppose $T(m,n)$ is the running time of an algorithm where the input parameters are $m$ & $n$ are non-negative integers. Now, assume we have a recurrence relation of the form, say, $T(m,n) = T(m-1,n)+T(m,n-1)$

Arguably, the boundary condition that needs to be supplied for an inductive proof of $T(m,n)$ would be $T(m,0)\ \forall\ m \geq 0 $ & $T(0,n)\ \forall\ n \geq 0$. Thus, the set of $ (m,0),\ m \geq 0$ along with $ (0,n),\ m \geq 0$ can be thought of as a boundary(identifiable with the first quadrant axes). Thus, coming back to the question at hand, the boundary *conditions* are nothing but the specification of the values of the recurrence at the **edge** of its applicable domain. This in 1D turns out to be point(s) at the end of the interval.

> How do we know the base case? We're only given T(n) recursively; there's no initial case when n is, for example, 1. How, then, do we know that "T(1)=1"?

When setting up a recurrence relation, it is always a good practice to specify the domain of applicability of the relation. This as we just saw above can help identify the boundary of validity of the relation. Now, the next step of how we come to know the exact values taken by the function at the boundary is often a problem of understanding the algorithm for which we have setup the recurrence relation for. In this particular case of $T(1) = 1$, we obtain $T(1)$ by manually computing(using the algorithm) the (worst-case)time it will take to work on an input of size 1.

> How do we determine the base case in the general case?

This is where the understanding of the algorithm(and its correctness) becomes crucial. Knowing the boundary of domain of the recurrence relation and the approximations we want to use to bound the range of the recurrence on a given size of input determines the cases for which we will need to supply the starting terms of the recurrence relation.

For instance, even though the natural boundary point for the example in your question is the input of size 1, due to the approximation being used namely $cnlg(n)$, we need to perturb the boundary in order to get a new domain such that the approximation will work on all possible inputs for the new domain of the recurrence. This is why the input $1$ is discarded and the boundary(in 1D it usually a single point if the interval is finite in a direction) and a new boundary point, $n\_0 = 2$ is chosen.

> Also, I've noticed that, in practice examples, the author has failed to mention the base case completely when doing these types of proof;...In fact, these proofs don't even explicitly state the inductive hypothesis...Is this acceptable or sloppy proof?

You are correct in stating that a base case as well as explicit verification using the inductive hypothesis is needed for the proof of induction to be complete and valid. However, in most treatments of this nature, when the base case/inductive hypothesis is not explicitly invoked, it is usually a passive call to action on the reader that they have been supplied with enough information to figure that out for themselves.

# Answer
> 1 votes
> What are boundary conditions?

Given a recurrence/function $f$ *boundary conditions* are simply a few points, usually small points such as 0,1 or 2, at which $f$ is specified. For example, in the Fibonacci sequence $$F(n) = F(n-1) + F(n-2), F(0) = F(1) = 1$$ $F(0),F(1)$ are boundary conditions. In other words *initial conditions*, *base conditions*.

The excerpt you posted proves the upper bound for the recurrence relation $2T(\lfloor n/2 \rfloor) + n$. It is done using substitution method for solving recurrence relation where you first guess the solution (involving constant(s)) and then find constant(s) that would satisfy boundary conditions.

After you guessed the solution you get an **explicit** (as in your example) equality/inequality of the form $T(n) \leq cg(n)$ which you have to prove in order to establish the upper bound for the recurrence relation $T(n)$. That is usually done using induction. However, the original boundary conditions may fail when you use it with your guessed function $g(n)$ like in the example: $T(1) = 1$, but $c\log(1) = 0$. At this point you should kind of select new boundary conditions (initial points) to prove the inequality $T(n) \leq cg(n)$. **Without base step you cannot complete induction proof.**

So the example "overcomes this obstacle" by choosing a new value $n\_0$ for the inductive proof. However, $T(1) = 1$ is still kept but it is removed from the inductive proof. The example then introduces new boundary conditions $T(2)$ and $T(3)$ instead of $T(1)$. Given $T(1)= 1$, we have $T(2)= 4$ and $T(3)=5$ and so for some constant $c \geq 2$ the following conditions hold $T(2) \leq c2\log(2)$, $T(3) \leq c3\log(3)$.

Now you can prove that $T(n) \< cn\log(n)$ using induction by taking base step $n=2$ and $n=3$ ($n \geq 2$).

> How do we know the base case?

If base case (boundary conditions) of the original recurrence relation fails, you can just remove them from the new equation/inequality and introduce new base case for which the equation/inequality holds.

> I don't understand what the paragraph is getting at.

This paragraph is just **one simple example** demonstrating how a new substitution function fails at the original boundary conditions and how to overcome that problem.

> How do we determine the base case in the general case?

There is no a standard way to do that, use you intuition, guess, and check if it works. You should choose your boundary conditions carefully. In the example you in your post $T(2)$ and $T(3)$ are chosen as new boundary conditions since values of $T(2)$ and $T(3)$ directly depend on the value of $T(1)$ which is troublesome. So we just put $T(2)=4$ and $T(3)=5$ without using $T(1)$.

**Making a good guess**

> Unfortunately, there is no general way to guess the correct solutions to recurrences. Guessing a solution takes experience and, occasionally, creativity. Fortunately, though, you can use some heuristics to help you become a good guesser.

> Is this acceptable, or would that constitute a sloppy proof?

This inequality should be proven. Assume that our claim is true for all integers less than or equal to $n$. We need to show that the inequality is true for $n+1$.

$$ T(n+1) = 2T((n+1)/2) + (n+1) \leq 2c\frac{n+1}{2}\lg{\frac{n+1}{2}} + (n+1) = c(n+1)\lg{\frac{n+1}{2}} + (n+1)=(n+1)(c\lg{\frac{n+1}{2}} + 1) \leq (n+1)(c\lg{\frac{n+1}{2}} + c) = c(n+1)(\lg{\frac{n+1}{2}} + 1) = c(n+1)(\lg{\frac{n+1}{2}} + \lg2) = c(n+1)\lg{(n+1)}$$

---
Tags: proof-techniques, recurrence-relation
---


# Question
Title: Is this possible to solve 4SAT in polynomial time?
I know and admit that this is **long**, but please read it slow and understand everything.

I think that this is one of the most interesting questions asked in computer science ever.

I do**n't** expect for quick answers. Take your time to read slowly and to understand everything. I can wait. I do**n't** rush.

In 1SAT, the turing machine needs to determine whether or not a 1CNF formula is satisfiable or not, where 1CNF formula is conjunction of clauses, where each clause is 1 literal only, which is either positive or negative variable.

This problem is known to be in $\Bbb{P}$, the class of all problems solvable in polynomial time, but it's **not** NP-Complete problem at all.

In 2SAT, the turing machine needs to determine whether or not a 2CNF formula is satisfiable or not, where 2CNF formula is conjunction of clauses, where each clause is disjunction of 2 literals at most, where each literal is either positive or negative variable.

Interesting is that if you turn out every disjunction into conjunction in the given 2CNF formula, then you get 1CNF formula and the problem becomes 1SAT, which is already known to be in $\Bbb{P}$ and if this formula is satisfiable, then the original 2CNF formula is satisfiable as well, but if the given 1CNF formula is unsatisfiable, this is **not** necessarily means that the original 2CNF formula is unsatisfiable as well.

Because the fact that in the original 2CNF formula you have disjunction between each pair of literals, instead of conjunction, you can allow one of the literals to be false in the input, but not both. So if it is **not** possible to set both literals to true in the same clause so the 2CNF formula evaluates to true, then the algorithm or turing machine has to decide which of them should be false, so the 2CNF formula evaluates to true.

Indeed this is a decision problem, but it's known to be in $\Bbb{P}$ as well, because it is possible just to build implications graph and finding contradiction circle to prove that the 2CNF formula is unsatisfiable. If no contradiction circle is found, then the 2CNF formula is satisfiable.

So even though from 1SAT to 2SAT the problem becomes decision problem (which literal in each clause should be set to false), the turing machine still can solve it deterministically in polynomial time, but unfortunately 2SAT is**n't** NP-complete too.

In 4SAT, the turing machine needs to determine whether or not a 4CNF formula is satisfiable or not, where 4CNF formula is conjunction of clauses, where each clause is disjunction of 4 literals at most, where each literal is either positive or negative variable.

Interesting is that if you turn out every disjunction into conjunction in the given 4CNF formula, then you get 1CNF formula and the problem becomes 1SAT, which is already known to be in $\Bbb{P}$, and if the given 1CNF formula is satisfiable, then the original 4CNF formula is satisfiable as well, but if the 1CNF formula is unsatisfiable, it does**n't** necessarily mean that the 4CNF formula is unsatisfiable as well.

So in that case the algorithm or turing machine will have to go back to the original 4CNF formula and in each clause turn out the middle disjunction into conjunction, i.e. if

(l1 ∨ l2 ∨ l3 ∨ l4) is arbitrary clause from arbitrary 4CNF formula, then the meaning of turning out the middle disjunction into conjunction is to turn that arbitrary clause to (l1 ∨ l2) ∧ (l3 ∨ l4).

If you do that, then you get 2CNF formula and the problem becomes 2SAT, which is also known to be in $\Bbb{P}$, and if this 2CNF formula is satisfiable then the original 4CNF formula is satisfiable as well, but if the 2CNF formula is **un**satisfiable then it does**n't** necessarily mean that the original 4CNF formula is **un**satisfiable as well, because in the original 4CNF formula there is disjunction between the two pairs of literals, but not conjunction, so the turing machine does**n't** have to find an input, so both the pairs of literals evaluate to true, but it's enough if one of them evaluates to true and the other evaluates to false.

As you can see 4SAT is decision problem as 2SAT is, which pair of literals should evaluate to false in each clause and which shouldn't, i.e. should evaluate to true.

This question is **similar** to the previous one, when the turing machine has to solve 2SAT and it needs to determine which literal should be false in each clause, instead of pair, but turing machine can solve 2SAT deterministically in polynomial time by building implications graph and trying to find contradiction circle, so it doesn't have to determine which literal should be false in each clause.

Same here with 4SAT, I don't think that the turing machine has to decide which pair of literals should evaluate to false in each clause.

I believe that there is a method that the turing machine can do deterministically to solve 4SAT in polynomial time, maybe similar to the method to solve 2SAT in polynomial time.

I don't think that 4SAT is so difficult problem.

When you turn out the middle disjunction to conjunction in each clause, you get 2CNF formula and the turing machine can deterministic-ally build the implications graph for it in polynomial time.

If the turing machine doesn't find contradiction circle, then the original 4CNF formula is satisfiable.

But if the turing machine did find contradiction circle, then the turing machine will have to modify the graph, so there is no contradiction circle in the graph.

If there is a way to do this modification, so there is no contradiction circle in the graph, then the 4CNF formula is satisfiable, even though the given 2CNF formula isn't.

But if the turing machine proves that does not exist such modification to the implications graph, so every contradiction circle can be resolved, then the original 4CNF formula is unsatisfiable.

In each 4CNF clause, deciding which pair of literals should be true and which should be false is to decide which edge should be in the implications graph and which edge shouldn't be in the implication graph.

If the turing machine assumes that all pairs can be true, then all edges are in the graph, but then if it finds contradiction circle, then to decide in each clause which pair of literals should be false is to decide which edge should be removed from the implications graph, so there is no contradiction.

Interesting that moving from 1SAT to 2SAT, the problem becomes decision problem, but both 1SAT and 2SAT are**n't** np-complete, even though both can be solved in polynomial time.

When moving from 2SAT to 4SAT, the problem again becomes decision problem, but 4SAT is np-complete, unlike 2SAT, because boolean satisfiability problem, which was the first problem to be proved np-complete in cook's and karp's paper, can be reduced to 4SAT in polynomial time.

My interesting question is can turing machine solves 4SAT deterministic-ally in polynomial time as it can in 2SAT?

I don't think that the turing machine really needs to decide in each clause which edge should be removed from the implications graph as in 2SAT the turing machine doesn't have to decide which literal should be false in each clause.

I think there should be a much efficient method that the turing machine can use to solve 4SAT deterministic ally in polynomial time as it does in 2SAT.

What do you think?

What is your opinion?

# Answer
> 2 votes
The problem is that when you split your clauses, you don't transform your $4SAT$ problem to a $2SAT$ problem. You still have an $NP$-complete problem to which an efficient $2SAT$-algorithm cannot be applied. You need to prove separately that your new problem is in $P$.

---
Tags: satisfiability, propositional-logic, sat-solvers, 2-sat
---


# Question
Title: Typical NP-complete/hard problems in machine learning
I know little about machine Learning, but I work on optimization (solving NP-hard problems with SAT solvers or MIP). Examples of this would be solving TSP, Steiner tree problems, path finding with constraints, etc.

I was wondering, is there any problem in ML that is NP-hard for which there are only approximations or small attempts of trying to solve them? I would like to look at them to see if my work can be applied there.

I am only interested in discrete optimization (so over integers/Booleans). Something that one could typically solve with constraint programming. Examples of such problems are scheduling tasks, finding paths in a graph given some weird constraints, TSP, vehicle routing... My research is on constraint programming applied to graphs, so if the problem can be modelled as a graph problem, that is a plus. My knowledge of ML is limited. I know the high-level concepts such as what regression, classification or supervised/unsupervised mean. Never actually implemented one of this ML things. I am watching a coursera class form Stanford on ML, but it is portrayed in a way that doesn't let me really see what are the NP-hard challenges.

# Answer
Many theoretical problems in ML are NP-hard.

1. I think the famous AlphaGo is trying to solve a NP-hard problem.
2. Contextual bandit problem and its combinatorial variants are np-hard.
3. In social network analysis, the famous influence maximization problem is a NP-hard problem.
4. There are many others. You can search in google. Also you can find related papers in two famous ML conferences: NIPS and ICML.
> 9 votes

# Answer
In deep learning optimizing weights of the neurons in multi-layer network is np-hard. General explanation can be found here. More information and math about this problem can be found in this thesis by J. Stephen Judd.
> 4 votes

---
Tags: optimization, np-complete, machine-learning, np-hard
---


title: $P\ne BPP$ implies $P\ne NP$

text:
# Question
Title: $P\ne BPP$ implies $P\ne NP$
> Prove: $P\ne BPP$ implies $P\ne NP$.

Obviously $P\subseteq BPP$ so the assumption is really $BPP\subsetneq P$. I'm trying to show the implication by contradiction. Let's assume that $P=NP$ and let's look at some language $L\in BPP$. Then, it has a proper probabilistic TM which decides it.

At first, I thought that I could just show some $NP$ machine which uses the $BPP$ machine but a relation between the two classes it not yet known, so it's probably not what I'm supposed to do.

We did learn Adleman's theorem and I think it could be used here (though we haven't define $P/poly$). Adelman's theorem claims that for every $x$ there's a $y$ s.t.

$$x\in A \implies M(x,y) = 1 \\ x\not\in A \implies M(x,y) = 0$$

so it boils down to the problem of finding such $y$, but I don't think this problem (finding $y$) is in $NP$ (or even possible)

Also, I understood that one can use the polynomial hierarchy theorem but we were not taught it.

# Answer
> 3 votes
Use the fact that $\mathsf{BPP}\subseteq\Sigma\_2$. Also note that if $P=NP$ then the entire polynomial hierarchy collapses to $P$.

---
Tags: complexity-theory
---


# Question
Title: Is there an algorithm for a number line from $0$ to $n$
Where $n + 1 = 0$ and $0 - 1 = n$?

The $n + 1 = 0$ case can be achieved by using the modulus operator, but I can't figure out how to treat the $0 - 1 = n$ case.

# Answer
> 3 votes
For $a,b \in \\{0,\ldots,n\\}$, subtraction is given by $$ a - b = \[a + (n+1-b)\] \bmod{(n+1)}. $$

# Answer
> 1 votes
You could simply compute $(a - b) \bmod{(n+1)}$. But you should also be aware of the least positive remainder and the least absolute remainder. Some libraries/languages may output the least positive remainder (for example Ruby and Python), while others may output the least absolute remainder like in C++. In the later case if the remainder is negative you simply add it to $n+1$.

---
Tags: algorithms, modular-arithmetic
---


# Question
Title: MAX-2-XOR-SAT: Why does the special case work?
I'm a new user so I cannot respond directly to this post here.

I'm confused about the answers to the question, namely that **MAX-2-XOR-SAT** is in $P$ iff each clause is of the form $(x\_i \oplus \neg x\_j)$ (or is it $(x\_i \oplus x\_j)$? There were two different answers). Couldn't you make a simple substitution $\neg x\_i \rightarrow y\_i$ such that this is always the case, so that you can get the special case always? For example, you could convert, $(x\_1 \oplus \neg x\_2) \wedge (x\_1 \oplus x\_3)$, to $(x\_1 \oplus y\_2) \wedge (x\_1 \oplus x\_3)$.

Forgive me if there is something obvious I am missing...I'm new to this field.

Thank you!

---

**EDIT**

To clear up confusion, I'm asking if a substitution is made for *all* clauses with a matching variable. Take for example,

$$(x\_1 \oplus x\_2) \land (\neg x\_1) \land (x\_1 \oplus \neg x\_3)$$

By substituting $\neg x\_3 \rightarrow y\_3$ we get:

$$(x\_1 \oplus x\_2) \land (\neg x\_1) \land (x\_1 \oplus y\_3)$$

Where each 2-clause is of the form $(x\_i \oplus x\_j)$. It seems that in this case it still remains in $P$. Which raises a new question, how do single clauses affect the complexity of the solution?

# Answer
No, you can't make a substitution like that. The resulting formula isn't equivalent to the original formula.

Consider

$$(x\_1 \oplus x\_2) \land (x\_1 \oplus \neg x\_2).$$

This formula is not satisfiable. However, if we apply your substitution, we end up with the formula

$$(x\_1 \oplus x\_2) \land (x\_1 \oplus y\_2).$$

The resulting formula now has 6 variables and is satisfiable. For example, you can set $x\_1=\text{True}$, $x\_2=\text{False}$, $y\_2=\text{False}$.

The problem is that your substitution doesn't ensure that $y\_i = \neg x\_i$, so it doesn't preserve satisfiability. (If you wanted to preserve satisfiability, you could do that by making your substitution and then adding clauses of the form $(y\_i \oplus x\_i)$ ... but while that would preserve satisfiability, it wouldn't preserve the maximum number of clauses that can be simultaneously satisfied, so it still wouldn't help for solving MAX-2-XOR-SAT.)
> 1 votes

---
Tags: complexity-theory, optimization, satisfiability
---


# Question
Title: Syntax directed translation , definition and actions
I have trouble understanding Syntax directed translation/definition/actions. I am reading dragon book but it confuses me even more.

Having production for simple arithmetic

$$ \mathit{expr} \rightarrow \mathit{expr} + \mathit{expr} \mathbin{|} \mathit{expr} - \mathit{expr} \mathbin{|} \mathit{num} $$

$$ \mathit{num} \rightarrow 0 \mathbin{|} 1 \mathbin{|} 2 \mathbin{|} \dots \mathbin{|} 9 $$

If I understood it correctly, SDT just adds attributes to the nodes and define rules.

for this production rules can looks like

$$ \mathit{expr}.\mathit{val} = \mathit{expr}.\mathit{val} + \mathit{expr}.\mathit{val} \mathbin{|} \mathit{expr}.\mathit{val} - \mathit{expr}.\mathit{val} \mathbin{|} \mathit{num}.\mathit{val} $$

$$ \mathit{num}.\mathit{val} = 0 \mathbin{|} 1 \mathbin{|} \dots \mathbin{|} 9 $$

this all together is called Syntax directed definiton.

Now what starts to confuse me:

It is often written that SDT is used to transfer infix to postfix notation e.g

$\mathit{expr} \rightarrow \mathit{expr} + \mathit{expr}$ will have semantic rule such as $\mathit{expr}.\mathit{val} = \mathit{expr}.\mathit{val} \mathbin{\\|} \mathit{expr}.\mathit{val} \mathbin{\\|} \text{'+'}$, where $\\|$ represents concating of strings.

Is STD strictly defined to trasnform notation to postfix?

Also, where in this fall actions?

By definition

> A syntax-directed translation scheme is a notation for specifying a translation by attaching program fragments to productions in a grammar. A translation scheme is like a syntax-directed definition, except that the order of evaluation of the semantic rules is explicitly specified. Program fragments embedded within production bodies are called semantic actions

and example

$$ \mathit{expr} \rightarrow^{+} \mathit{expr}\ \ \\{\\, \mathit{print}(\text{'+'}) \\,\\}\ \ \mathit{expr} $$

I cannot find what is the usage of this. Which leads to sum of questions: What is STD (rules) for and what are uses of actions in it?

I appreciate all answers, I read wiki but did not help.

Thanks.

# Answer
Syntax directed translation uses the hierarchical structure of the input to generate the output. In other words, you exploit the grammar structure to help you to translate the program.

**Translating using semantic rules**

Semantic actions allow to embed code into a cfg which helps you to translate the program/source code. The following Ruby code should help you to figure out how things work. The following simple translator translates a single line infix expression into postfix expression.

First of all note that I use grammar that is suitable for top-down recursive descent parser, namely without left recursion and unambiguous. Transformation of this grammar is given in your book. So, you have to be familiar at least with a top-down recursive descent parsing method which is simple if you understand and have no problems with direct/indirect recursive calls.

Also please pay attention to how I embedded `print`s into `while` loops in order to emit postfix notation. As an exercise try to move the `print` to another line to get infix notation.

I wrote deliberately in Ruby so that you could play with the code and see it in action and modify it easily. If you have Ruby installed just type `ruby parser.rb` and see output.

```
@source = "1*2-3*4"
@index = 0

def get_token()
  @token = @source[@index]
  @index+=1
end

def exp()
  term()
  while(@token == '+' || @token == '-')
    op = @token #store the operator + or -
    get_token() #move to the next input symbol
    term()
    print op # <= semantic action (print operator + or -)
   end
end

def term()
  factor()
  while(@token == '*' || @token == '/')
    op = @token #store the operator
    get_token() #move to the next input symbol
    factor()
    print op # <= semantic action (print operator * or /)
  end
end

def factor()
  if ('0'..'9').include?(@token) #if @token is a digit
    tk = @token #store in temp variable
    get_token() #move to the next input symbol
    print tk # <= semantic action (print a digit)
  else
    puts 'Syntax Error'
  end
end

get_token()
puts exp()

```

**Example outputs:**

`1*2-3*4` is translated into `12*34*-`
`1+2-3*7` is translated into `12+37*-`

**Computing expression value using node attributes**

The following piece of code demonstrates node attributes in action to compute the value of an infix expression. Semantic actions this time around are lines which compute attribute of each tree node, that is, actual value of the expression.

```
@source = "9*3-3*7-2"
@index = 0

def get_token()
  @token = @source[@index]
  @index+=1
end

def exp()
  exp_t = term()
  while(@token == '+' || @token == '-')
    op = @token
    get_token()
    term_t = term()
    # compute attribute of the tree node
    if op == '+'
      exp_t += term_t
    else
      exp_t -= term_t
    end
  end

  return exp_t #return attribute to one level up in the tree
end

def term()
  term_t = factor()
  while(@token == '*' || @token == '/')
    op = @token
    get_token()
    val = factor()
    # compute attribute of the tree node
    if op == '*'
      term_t *= val
    else
      term_t /= val
    end
  end

  return term_t #return attribute to one level up in the tree
end

def factor()
  if ('0'..'9').include?(@token) #if @token is a digit
    tk = @token #store in temp variable
    get_token() #move to the next input symbol
    return tk.to_i #to_i means convert to integer
  else
    puts 'Syntax Error'
  end
end

get_token()
puts exp()

```

**Examples:**
`9*3-3*7-2` results in `4`
`9*3-3*7` results in 6
`1-1+1*1` results in 1
> 4 votes

---
Tags: automata, compilers
---


# Question
Title: Can this algorithm still be considered a Binary Search algorithm?
While doing the second code kata (which asks you to implement a binary search algorithm five times, each time with a different method), I've come up with a slightly different solution which works as follows:

If i have a sorted array of lenght 100 and I see its starting field contains the number 200 and its ending field contains the number 400, me, as a maths studying human, would be likely to start searching around field 35 if I was searching the number 270, and not the field 50 like in a normal binary search algorithm.

Then, if the number on field 35 of the array is 270, 35 is the index I was searching for.

If that isn't the case I can compare the number I got (say 280) and repeat the operation taking the lower part of the array (so I have 35 fields with the starting field containing 200 and the ending field containing 280) if the number I found is greater than what I'm searching for, or the upper part of the array (say I got 260: now I have 65 indexes, the first one containing 260 and the final one containing 400. Orientatively, I would head torward index 4 of this sub array, which is index 39 of the entire array) if the number I got is smaller than the number I'm searching for.

The question is: can this algorithm be considered a binary search algorithm? If not, has it got its own name?

# Answer
I would not call this a binary search.

It is clearly similar to binary search and it's natural to see it as a refinement of binary search. However it has significantly different algorithm complexity characteristics, Interpolation Search has expected run time of O(log(log(n)) assuming the data is uniformly distributed, however it pays for this by having O(n) worst case run time.

I prefer to say "The worst case run time of binary search is O(log(n))" rather than "Depending on the choice of bounding elements the worst case run time of binary search is O(log(n))". This means that I can not classify Interpolation search as a binary search algorithm.
> 23 votes

# Answer
Yes, this is known as Interpolation Search. With some caveats (depending on your computational model and the distribution of the data) its expected running time is $O(\log \log n)$, better than binary search.
> 17 votes

# Answer
I think the correct terminology would be dychotomial pondered search.

You search in a flat array with subsequent pondered seeking based on the supposed flat distribution of the numbers in it.

This corresponds to how a person would search a word in a dictionary. But it can be very inefficient if the distribution of data is irregular.
> -1 votes

---
Tags: algorithms, terminology, search-algorithms, binary-search
---


title: if $L\in BPP$ then $NP\subseteq BPP$

text:
# Question
Title: if $L\in BPP$ then $NP\subseteq BPP$
> Let $L$ to be the following problem: $$L = \\{ \langle M,x,1^t \rangle \mid \text{$M$ accepts $x$ after $t$ steps with probability at least $3/4$} \\}.$$ Show that if $L\in BPP$ then $NP\subseteq BPP$.

I already showed that $L$ is $BPP$-hard. I think a reduction from $3SAT$ to $L$ need to be shown (logarithmic/polynomial? not sure)

It's not clear to me how to do that - I'd be glad for guidance.

# Answer
This is similar to the proof that PP contains NP. Given a 3SAT instance $\varphi$ on $n$ variables, construct a machine $M$ that with probability $3/4 - 2^{-n}/4$ accepts, and with probability $1/4 + 2^{-n}/4$ chooses a random truth assignment and accepts if the truth assignment satisfies $\varphi$. If $\varphi$ has $N$ satisfying assignments, then $M$ accepts with probability $$ p = \frac{3}{4} - \frac{2^{-n}}{4} + \frac{M}{2^n} \left(\frac{1}{4} + \frac{2^{-n}}{4}\right). $$ If $M = 0$ then $p \< 3/4$, whereas if $M \geq 1$ then $p \geq 3/4 + 2^{-2n}/4$.

I'll let you fill in the rest of the argument.
> 1 votes

---
Tags: complexity-theory
---


title: Number of Pairs in Array

text:
# Question
Title: Number of Pairs in Array
so hey, I've been recently reading about the Two-Pointer algorithm that allows us to find pairs $(i,j)$ such that $a\[i\] + a\[j\] = x$ in $O(m+n)$ instead of the trivial $O(mn)$ time.

I was wondering how can I find the *number of pairs* $(i,j)$ in time less than $O(mn)$. I was trying to use Two-Pointer but it seems that it doesn't work when there duplicate elements because there can be no way of moving one pointer without missing some pairs like $\[1, 1, 2, 3, 3\]$ and $x = 4$ or maintaining the linear time, unless I'm missing something here.

> Is there is some magical way of finding the number of pairs $(i,j)$ such that $a\[i\] + a\[j\] = x$ in less than $O(mn)$ time?

# Answer
You observed correctly that the number of pairs can grow quadratically with input size. In the worst case, the array contains only two types of numbers, but with great multiplicity.

$$\[1,1,1,1,1,2,2,2,2,2\]$$

Here, each of the five ones can be combined with each of the five twos, thus creating 25 pairs that sum up to three. It is generally impossible to visit each pair once and maintain linear time complexity.

Luckily, it is not neccessary to visit each pair once, as we can calculate the multiplicity of the pair from the multiplicities of its members. In this case:

$$5 \cdot 5 = 25$$

To find all pairs in linear time, run-length encode the array first. So

$$\[0,1,1,1,1,1,2,2,2,2,2,3\]$$

becomes

$$\[(0,1),(1,5),(2,5),(3,1)\]$$

Then, apply the two-pointer algorithm and calculate the multiplicity of each resulting pair directly. Here, the result could be a pair of zero and three with multiplicity one, and a pair of one and two with multiplicity 25.

$$\[(0,3,1),(1,2,25)\]$$

In total, there are 26 pairs.
> 6 votes

---
Tags: optimization, time-complexity, asymptotics, arrays
---


# Question
Title: what are Structural recursion, primitive recursion, recursion combinator and recursion principles?
Recently, I encountered terminologies such as primitive recursion and recursion combinator. One of the sources is here link

I googled and read some, but missing the points of them. I know that recursion occurs when a function appears within its definition. While $\lambda$-calculus cannot express such recursive definitions directly, it can use combinators to implement recursion.

So, what are Structural recursion, primitive recursion, recursion combinator and recursion principles? how each related to others?

Hoping someone could explain these clearly, so I can go in the right direction. now I am struggling to figure out their "points".

Thanks in advance!

# Answer
> 4 votes
The recursion combinator you mention seems to be the recursor associated to an inductive (or recursive) data type. In the paper this seems to be the type describing the syntax of lambda terms. Here, I'll take lists as a simpler recursive type.

Note that the "lists of naturals type" can be intuitively described as the "least" type admitting these constructors: $$ \begin{array}{l} nil : list \\ cons : nat \to list \to list \end{array} $$ Recursive types as the one above have an associated induction principle. For instance, if we wanted to prove a property on all lists $p(l)$, it would suffice to prove

1. the base case $p(nil)$, and
2. the inductive case $p(l) \implies p(cons\ n\ l)$ for any $n,l$.

If we had more constructors, we would have move base or inductive cases, accordingly.

Similarly, we can define a function $f : list \to A$ by induction. That is to define $f(l)$ on all lists, all we have to do is to define

1. what is the result in base case, i.e. $f(nil) = a : A$
2. provided we already defined $f(l)$, we need to define $f(cons\ n\ l)$ for all $n,l$.

Note that step 2 amount to define a function $g : nat\to A \to A$, which takes $n:nat$ and $f(l):A$ and produces $g(n)(f(l)) = f(cons\ n\ l)$.

We can generalize this by crafting a combinator that given $a,g$ produces $f$ defined as above. This is called the (primitive) recursor.

$$ \begin{array}{l} rec : A \times (nat \to A \to A) \to (list \to A) \\ rec(a,g)(nil) = a \\ rec(a,g)(cons\ n\ l) = g(n)(rec(a,g)(l)) \end{array} $$

Usually this is called `fold_right` or `foldr` in functional programming languages.

Note how, roughly, $a$ replaces $nil$, and $g$ replaces $cons$. Indeed, in the general case, the recursor takes one argument for each constructor of the recursively defined type at hand.

If you have a general fixed point combinator like Church's $Y$, you can easily encode the above. However, in many type theories, you don't have that luxury, since $Y$ causes the inconsistency of the related logic. Instead, for any recursive type you define, you get a restricted version of $Y$ which is the recursor: each type has its own recursion combinator. This ensures the termination of the calculus, which is important to ensure the consistency of the logic.

---
Tags: recursion, primitive-recursion, variable-binding
---


# Question
Title: A problem similar to the Bin packing problem?
I'm working on a problem that is very similar to the bin packing problem, but for me, the objective is to minimize the maximum weight given m bins. The problem statement is:

Given n items, each with a certain weight less than some maximum weight (w\_max), how do you pack them into m bins so that you minimize the maximum weight (over all bins)?

I'm looking at a possible approach that would simply iterate by grouping the two smallest weight items until the number of groups equals the number of bins.

Has anyone heard of a similar problem and know of an approach to solve this with some guarantees?

# Answer
One way to solve your problem is to use binary search over the maximum weight. In other words, pick a threshold $t$, and check whether it's possible to pack your items into $m$ bins, without using more than a total weight of $t$ in each bin. This is exactly the bin packing problem: is it possible to pack the items into $m$ bins of capacity $t$? You can apply any algorithm for bin packing to this problem. Then, use binary search on $t$.

Be warned that it is NP-hard, so don't expect an efficient algorithm that produces the optimal solution in a reasonable amount of time for large problem instances.
> 1 votes

---
Tags: partitions, packing
---


# Question
Title: Who was the first to show that there is a Universal Turing-Machine that uses a binary alphabet?
The title says it all, I think.

We know there are universal Turing-machines that only use a binary alphabet. But who proved this first?

Turing himself showed the existence of a universal Turing machine ... but did he also show that such a machine can exist using only a binary alphabet? Or was that someone else?

Or was it just 'obvious' to him and others that this would be the case, and hence no explicit 'first' proof or publication of this result exists?

Of course, it is obvious that you can *represent* any *number* using binary. But, first of all, Turing-machines can compute things about things other than numbers. Indeed, all that matters is that the Universal Turing-machine is able to represent, in binary, whatever symbol set the Turing-machine to be simulated is using, and a program, again in binary, that describes the state-transitions of that machine-to-be-simulated. Of course, since all of those things are enumerable, all representations of those things can still be done in binary, that is still fairly obvious.

But what is far less obvious to me, is that you can do all the *computations* on those *represented objects* still using only two symbols. For example, you'll need some way to indicate separations between the objects, and as those objects change (e.g. when the machine-to-be-simulated changes a symbol on the tape), you'll need to change the corresponding binary representation, and since they are of variable length, you'll need to constantly shift the location of those objects on the tape that the Universal machine is working with.

Indeed, to me the tricky part is to come up with some clever way to encode any kind of Turing-machine and input tape that the Universal machine will take in at its input, and to somehow simulate the behavior of that machine, keeping track of what state that machine is in and where it is on the tape, again, all with just two symbols. Yes, we now know it can all be done, and I successfully went through this exercise myself. However, I thought it was all rather less than obvious.

Of course, I am no Turing ... and so was it obvious to Turing that it could be done? Reading his paper, I don't think Turing really proves this .. or even considers this. In his paper, for example, he still uses special symbols (i.e. not 0 or 1) to, for example, indicate the left boundary of the simulated tape. But was it still so obvious to Turing that it didn't even deserve mentioning?

So, let me put it this way: is there a publication that can be considered the 'first' proof of the result that you can have a dully binary Universal Turing machine? I would be very interested in knowing what that is.

Thank you!

# Answer
> 6 votes
A large part of what is known goes unpublished, when it is considered trivial. What counts as trivial is, of course, different in different times and for different communities. For instance, we do not consider particularly interesting about binary numbers that they are as expressive as decimals, but that the machines that operate on binary representations are simpler.

In his famous 1936 article, Turing is satisfied with the premise that the alphabet of the machine is finite, which leads me to believe that differences beyond that are considered trivial by him, for general purposes.

He discusses the difference between machines with infinite and finite sets of symbols, and reaches the conclusion that using an infinite set of symbols would, at some point, make it impossible to concretely differentiate them from each other (which could be another way of illustrating the fact that real numbers can't be listed). He then states that the effect of this restriction is not very serious, because you can, at least to some extent, conveniently represent bigger alphabets by groups of symbols of smaller ones, considering that any effective computation can only use, in practice, what amounts to a finite number of symbols.

I suggest that you try to imagine how to simulate an $n$-symbol TM (I would start with $n=8$) on a two-symbol one. It is a good exercise.

---
Tags: turing-machines, computation-models, turing-completeness, history
---


title: Showing a problem is $P$-complete

text:
# Question
Title: Showing a problem is $P$-complete
Consider the well-known language: $$L = \\{\langle M,x,1^t \rangle \ \ |\ \text{$M$ accepts $x$ after $t$ steps}\\}$$

I've encountered some technical problem while trying to show a logarithmic reduction from some $L'\in P$ (which will show completeness of $L$)

Basically, the reduction is: $$f(x) = \langle M\_{L'},x,n^c\rangle $$

Where $n^c$ is the time it takes for $M\_{L'}$ to decide some input, $x$.

At first everything seems legitimate, but... How do we construct $M\_{L'}$ at the first place?

In other words, do we have an "access" (as the reduction function) to the machine description?

# Answer
You need to show that for every $L'\in P$ there exists a logspace reduction from $L'$ to $L$. Your $f$ has $\langle M\_{L'}\rangle$ hardcoded into it. The encoding was part of its definition, $f$ does not ask what is the encoding of the machine for $L'$ when it tries to compute $f(x)$.

One way to think of this is as follows: consider the sequence of functions $\left\\{f\_{s ,c}\right\\}\_{c\in\mathbb{N}, s\in\\{0,1\\}^\*}$ where $f\_{s, c}(x)=\left(s, x, 1^{|x|^c}\right)$. Since $L'\in P$, there exists a function in this sequence which is a reduction from $L'$ to $L$ (the specific index depends on the machine deciding $L'$, but we don't really care about it).
> 2 votes

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


title: Equivalence of dfferent TM definitions

text:
# Question
Title: Equivalence of dfferent TM definitions
I stumbled upon these two defintions of a turing machine:

http://www.cs.um.edu.mt/gordon.pace/Teaching/Complexity/CoursePage/Notes/chapter5.pdf

http://scholar.harvard.edu/files/harrylewis/files/s6\_sols.pdf

The difference which bothers me is that the second one allows only left and right movements whereas the first allows left, right and not moving the head at all.

First definition: $\delta\_1: Q\_1 \times \Gamma\_1 \mapsto Q\_1 \times \Gamma\_1 \times \\{L,R,S\\}$

Second definition: $\delta\_2: Q\_2 \times \Gamma\_2 \mapsto Q\_2 \times \Gamma\_2 \times \\{L,R\\}$

Are they equivalent? If they are equivalent it should be possible to transform a TM that can do $\\{L,R,S\\}$ into a TM which always has to move left or right (does only $\\{L,R\\}$)?

How is this possible?

# Answer
Yes they are equivalent and it is always possible. Informally: you can exchange any $S$ move state with pair of states that goes $L$ then $R$ (or in the other direction).

Formally:
Prove that standard Turing Machine is equivalent to class of Turing Machines with $S$ (no move).
Let $M$ denote standard TM, there exists a TM $M'$ with no move option such that $L(M) = L(M')$. This way is trivial, simply do not use $S$ move in the extended version.
In the other direction:
Given TM $M'$ with no move option, construct equivalent TM $M$ such that $L(M') = L(M)$.
Construct new transition function $\delta'$ for $M$ such that for each state with move $\in \\{L, R\\}$ in $\delta$ there is equivalent state in $\delta'$.
For each $S$ move in $\delta$ put two states in $\delta'$.
So for $\delta(q\_x, a, b, S, q\_y)$ put two states to $\delta'$, $\delta(q\_x, a, b, L, q\_n)$ and $\delta(q\_n, \*, \*, R, q\_y)$. The $q\_n$ matches the acceptance with $q\_x$. If the $S$ move was accepting state, make the second state accepting. This gives the equivalence in the accepting states and the head (heads) position.
$L(M') = L(M)$, so these classes are equivalent.
> 1 votes

---
Tags: turing-machines, computation-models, simulation
---


# Question
Title: Why is the log in the big-O of binary search not base 2?
I am new to understanding computer science algorithms. I understand the process of the binary search, but I am having a slight misunderstanding with its efficiency.

In a size of $s = 2^n$ elements, it would take, on average, $n$ steps to find a particular element. Taking the base 2 logarithm of both sides yields $\log\_2(s) = n$. So wouldn't the average number of steps for the binary search algorithm be $\log\_2(s)$?

This Wikipedia article on the binary search algorithm says that the average performance is $O(\log n)$. Why is this so? Why isn't this number $\log\_2(n)$?

# Answer
> 87 votes
When you change the base of logarithm the resulting expression differs only by a constant factor which, by definition of Big-O notation, implies that both functions belong to the same class with respect to their asymptotic behavior.

For example $$\log\_{10}n = \frac{\log\_{2}n}{\log\_{2}10} = C \log\_{2}{n}$$ where $C = \frac{1}{\log\_{2}10}$.

So $\log\_{10}n$ and $\log\_{2}n$ differs by a constant $C$, and hence both are true: $$\log\_{10}n \text{ is } O(\log\_{2}n)$$ $$\log\_{2}n \text{ is } O(\log\_{10}n)$$ In general $\log\_{a}{n}$ is $O(\log\_{b}{n})$ for positive integers $a$ and $b$ greater than 1.

Another interesting fact with logarithmic functions is that while for constant $k\>1$, $n^k$ is NOT $O(n)$, but $\log{n^k}$ is $O(\log{n})$ since $\log{n^k} = k\log{n}$ which differs from $\log{n}$ by only constant factor $k$.

# Answer
> 10 votes
In addition to fade2black's answer (which is completely correct), it's worth noting that the notation "$\log(n)$" is ambiguous. The base isn't actually specified, and the default base changes based on context. In pure mathematics, the base is almost always assumed to be $e$ (unless specified), while in certain engineering contexts it might be 10. In computer science, base 2 is so ubiquitous that $\log$ is frequently assumed to be base 2. That wikipedia article never says anything about the base.

But, as has already been shown, in this case it doesn't end up mattering.

---
Tags: algorithms, runtime-analysis, binary-search
---


# Question
Title: multiple sequence alignment using HMM and simulated annealing
Can anyone help me with Multiple Sequence Alignment (MSA) using Hidden Markov Model (HMM) by giving an example or a reference except these 2 references:

1-Eddy, Sea.R., et al.Multiple alignment using hidden markov models, 2-Boer Jonas, Multiple alignment using hidden Markov models, Seminar Hot Topics in Bioinformatics.

I know that there are 3 states: match, deletion and insertion and I know the emission probabilities and transitions probabilities can be learned by viterbi algorithm but what is vague is that if I want to do multiple alignment I need to have HMM and if I want to have HMM I need to have aligned sequences but we know that sequences are unaligned and also with simulated annealing we can Enter randomness to the model and have better solutions and also this algorithm is different with E-M algorithm and I have another question how many states our model of HMM for this problem should have at the first step, does the number of states change during the time of convergence or it is fixed from the first??

If anybody can help me to understand what really happens in this MSA with HMM I'll appreciate.

I should explain that there have been found more sequences of DNA,RNA and protein but there are less information about structures and functions of each protein so we do MSA to understand the similarities between sequences and find out whether they are homologous (have a same ancestor) or not and find out the unknown structure and functions of sequences.

# Answer
> 0 votes
part of this question already has an answer in multiple sequence alignment using HMM and simulated annealing and about the number of states in HMM it is a challenge yet.

---
Tags: hidden-markov-models, bioinformatics
---


# Question
Title: Steiner tree problem with the known optimal subset of Steiner vertices in approximation algorithms
I want to prove that the hardness of the Steiner tree problem lies in determining the optimal subset of Steiner vertices that need to be included in the tree and I need to show this by proving that if this set is provided, then the optimal Steiner tree can be computed in polynomial time.

It is clear that we can find an MST on the union of this set and the set of required vertices with Kruskal algorithm, and by contradiction proof, can be said that if this union of sets didn't give the MST so the subset of Steiner vertices is not the optimal subset. Any hints or tips would be appreciated.

# Answer
It can be proved as I mentioned with contradiction, assume that $S1$ is the optimal subset of steiner nodes and $R$ is the required nodes, so we give the subgraph of main graph including $S1$ and $R$ nodes and the edges between them to Kroskal algorithm then we have a MST for them, we assume that it is not equal to OPT (solution for steiner tree problem), so the given subset (S1) was not optimal I mean at least one steiner node was not given or was given falsly.
> -1 votes

---
Tags: algorithms, approximation
---


title: Right moving turing machines and FSA's

text:
# Question
Title: Right moving turing machines and FSA's
I stumbled upon the following post while learning about turing machines:

Right moving turing machine

I kind of understand the intuition behind why a TM that only moves to the right works like a FSA but I can't think of a general way to create a let's say DFA (or NFA, doesn't really matter) which accepts the same language as a given right moving TM.

So my question would be:

Given an only right moving TM $M$, what would be a general method for constructing a DFA $D$ such that $L(M) = L(D)$?

Alternatively, given an only right moving TM $M$, how to construct a NFA $N$ such that $L(M) = L(N)$?

# Answer
> 3 votes
As Yuval indicated in the comment, a right-moving TM is already essentially a FA. Here's the construction:

Given a TM move rule $\delta(q, x)=(p, y, d)$ where, as usual, $q$ is the current state, $x$ is the contents of the current cell, $p$ is the new state, $y$ is the symbol replacing $x$ in the current cell, and $d$ is the direction to move the head. Since the machine can only move right, it is immaterial what gets overwritten on the current cell and since $d$ is always *move right*, we can ignore both of these, leaving us with moves of the form $\delta(q, x)=(p)$, i.e., the moves for a FA.

The construction above is for a DFA, the one for a NFA is essentially the same.

---
Tags: turing-machines, finite-automata
---


title: Question about space complexity

text:
# Question
Title: Question about space complexity
I'm trying to represent a directed acyclic graph using a structure similar to an adjacency list. The difference is, for a given vertex v, I need to know precisely which nodes are inwardly adjacent to v, and which nodes are outwardly adjacent to v. To get around this, my idea was to use a list of pairs, where each pair consists of two sets - which correspond directly to the inward and outward adjacency sets of any vertex in the graph.

I understand that the maximum number of edges in a directed acyclic graph of size $n$ is $\frac{n(n-1)}{2}$. In the proposed graph encoding, the existence of a vertex u in vertex v's 'in' set implies the existence of an edge (u, v). The existence of a vertex u in vertex v's 'out' set implies the existence of an edge (v, u). Additionally, $u \in in(v) \iff v \in out(u)$. Therefore, my intuition tells me that this representation of a directed acyclic graph has a space complexity of $\mathcal{O}(2|E|)$, since the existence of each edge $(v, u)$ is implied twice; once by $v \in in(u)$ and once by $u \in out(v)$.

My question is, does my intuition fail me?

# Answer
You say "using a structure similar to an adjacency list". So space complexity required for storing undirected graph using adjacency list is $O(|V| + |E|)$, in your case $O(|V| + 2|E|)$. That is implemented using a list of nodes where each node has two fields: label of the vertex and pointer to the list of adjacent nodes (in your case two lists).

But I don't know how you are going to use the graph. If you are interested in simply a set of edges then you could store them in a list as triples $\<u,v,weight\>$. But if at some point for a node $v$ you want to systematically loop on all adjacent vertices (inward or outward) then you should use adjacency list.

Finally if you want to decide in $O(1)$ if there is an edge $\<u,v\>$ then you should use hash like data structure to store pairs $\<u,v\>$.
> 2 votes

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


# Question
Title: Is there a "natural" example of a total, computable but non-primitive recursive function?
Every example of a total, computable but non-primitive recursive function seems to be explicitly constructed for proof theory, or in Godelian proofs of "what is the name of this book?" kind. But is there a non-primitive recursive function or algorithm that occurs naturally, like in physics or number theory or even in industry software?

# Answer
> 3 votes
This answer gives us a hint, namely that an interpreter for a language more powerful than primitive recursion, is itself not primitive recursive. For example, System F has no self-interpreter, and thus any interpreter for System F is not self-recursive.

This then extends to Turing-complete languages: JavaScript, Python, Ruby, etc. Any interpreter you run is utilizing functions more powerful than primitive recursion.

---
Tags: computability
---


# Question
Title: Find non-overlapping subsets that maximize the sum of their values
> Given a set of elements $N$, a set $S$ of subsets of $N$, and a function $v:S \to \mathbb R$, determine a set $R\subseteq S$ of *non-overlapping* subsets that maximizes the total value.

Has this problem already been studied somewhere, or is it linked to some well-known optimization problem?

# Answer
> 2 votes
Yes this problem has already been studied. It is a well-known $NP$-complete problem known as Set-Packing. Your problem is a weighted optimization variation, but the same principles apply.

# Answer
> 0 votes
You can reduce it to the following graph theoretic problem, but I don't know if it is in $P$.

Denote each set in $S$ as a vertex and give it a weight $f(S)$, in other words your vertices are weighted. Then if two sets are overlapping connect them by and edge. Then you have to find a subset $V'$ of vertices such that if $v,u \in V'$ then $(u,v) \notin E$, that is they are not adjacent to each other and sum of weights of vertices in $V'$ have to be maximal.

**UPDATE**: According to ryan's post it is NP-complete.

---
Tags: optimization, sets
---


# Question
Title: Find hamming codewords in r=2^k dimensions
There is the original problem, and an equivalent problem.

The equivalent problem: construct a set $A$ that contains bit arrays of length $r-1$, where $|A|=2^{r-1}/r$ and $hamming \space distance (i, j) = 3 \quad \forall i, j \in A, \space i \neq j$.

Misha Lavrov gave an excellent answer on Math.SE that solves the original problem. However, I don't get his construction.

If you could prove that his algorithm solves the problem for any $r=2^k$, or provide your own algorithm that solves the problem / equivalent problem for any $r=2^k$, I'd really appreciate it.

---

The original problem: choose $2^r/r$ bit arrays, where each bit array is of length $r$, and $r=2^k$ for all $k \ge 2$, such that the chosen arrays can be split into 2 sets, $A$ and $B$, where

1. $|A|=|B|=2^{r-1}/r$
2. $\forall x \in A.(\exists y \in B.(hamming \space distance (x, y) = 1))$ and $\forall y \in B.(\exists x \in A.(hamming \space distance (x, y) = 1))$
3. $hamming \space distance (i, j) = 3 \quad \forall i, j \in A, \space i \neq j$
4. $hamming \space distance (i, j) = 3 \quad \forall i, j \in B, \space i \neq j$

Here is the answer for $k = 2$, where blue circles are chosen bit arrays.

---

*(P.S. Instead of $n=2^r$ dimensions in my question on Math.SE, I used $r=2^k$ here, because Misha's answer referred to bit arrays of length $r$. I hope this is not too confusing.)*

# Answer
I completely misunderstood Misha's answer. Here is my updated understanding of the equivalent problem. All quotes are from his answer.

1. Let $S = \\{0,1\\}^{r-1}$, $|S| = 2^{r-1}$ bit arrays, each bit array has length $r-1$.
2. Let $S\_i = \\{x\ |\ x \in S\ and\ x\_i = 1\\}$, where $x\_i$ is the $i^{th}$ bit of bit array $x$. We set the $i^{th}$ bit of array $x$ to $1$.

An even number of bit arrays is always chosen from $S\_i$. If initially an odd number of bit arrays is chosen, then choose the bit array corresponding to the parity bit as well, so finally an even number of bit arrays are chosen.

This corroborates with Misha's answer, as the coordinates numbered off exactly match the parity bit coverage.

> * Among the coordinates numbered $0\dots001, 0\dots011, 0\dots101, 0\dots111, \dots, 1\dots111$, an even number are $1$'s.
>     * Among the coordinates numbered $0\dots010, 0\dots011, 0\dots110, 0\dots111, \dots, 1\dots111$, an even number are $1$'s.
3. Repeat step 2 for all $i \in \[1,\ r-1\]$.

Let $A$ be the set of chosen bit arrays from $S\_i$ for all $i$, where chosen bit arrays are hamming codewords.

The hamming code is an even parity bit, single error correction code for arrays of length $r - 1$.

The following describes single error correction, where "vertex" means "bit arrays", and "picked vertices" means "bit array in $A$" or "hamming codeword".

> If a vertex is not one of the picked vertices, find all the parity conditions that fail, let $i$ be the coordinate with a $1$ in all the bits corresponding to the failed conditions; change the $i^{\text{th}}$ coordinate, and you will get a picked vertex.

This solves the equivalent problem of finding set $A$.

---

Now, to solve the original problem.

*(I originally thought the $00\dots00^{\text{th}}$ coordinate was for double error detection, and was wondering why I needed that in a single error correction code. I was completely wrong.)*

> Given a vertex, if it is one of the picked vertices, change the $00\dots00^{\text{th}}$ coordinate, and you will get another picked vertex.

This is equivalent to prepending a new bit, $b$, for each bit array within the set $A$ that we derived earlier, thus making all bit arrays have length $r$.

Arbitrarily let bit $b = 0$. Define $A\_{new} = \\{b\ x\_1\dots x\_{r-1}\ |\ x \in A\\}$.

Let $B = \\{\neg b\ x\_1\dots x\_{r-1}\ |\ x \in A\\}$, so all bit arrays are same as $A\_{new}$, except for every array, the $b$ bit is flipped.

This fits well with Misha's explanation that bit arrays from $A\_{new}$ and $B$ are nearly-identical, because the only difference is the flipped bit $b$.

> the $00\dots00^{\text{th}}$ coordinate of a vertex \[...\] is the "free" coordinate where we pick a vertex with $0$ and also pick a nearly-identical vertex with $1$.

This solves the original problem, such that the $2^r/r$ bit arrays are in sets $A\_{new}$ and $B$.
> 0 votes

---
Tags: graphs, optimization, combinatorics, colorings, hamming-code
---


# Question
Title: Algorithm to mimimally pair up points in 3D space
Given a set of $n$ points $P$ and a set of $n$ points $Q$ in 3 dimensional space, what's the fastest algorithm to uniquely pair points in $P$ with points in $Q$ so that the sum of the square of the distance between points in $P$ and their corresponding point in $Q$ is minimized? Each point in $P$ must be matched with one and only one point in $Q$, and vice versa.

*Another way to look at the problem:* if $P$ and $Q$ are matricies with 3 columns and $n$ rows, how can I reorder the rows of $P$ so as to minimize the frobenius norm of $P - Q$?

This problem can be solved in $O(n^3)$ by creating a cost matrix $M$ where $m\_{i,j}$ is the distance between point $P\_i$ and point $Q\_j$, and then by using the hungarian algorithm to find the minimal assignment, however I feel like there's a faster way.

Even if there isn't an exact solution, are there any fast approximations?

**Edit:** for my specific use-case, the points in $P$ are the points on a $m \times m \times m$ grid and $n=m^3$

# Answer
As an approximate solution in $O(n^2)$ you can construct the cost matrix $M$ and then solve the stable marriage problem.
> 1 votes

---
Tags: optimization, computational-geometry, euclidean-distance
---


# Question
Title: The impact of caching on the system performance or on the user experience
I am working on modeling a certain system's cache layer and comparing two algorithms.

One outperforms the other one; it shows the higher cache hit rate (%).

But what is important is the impact of such an improvement at cache layer on the entire system performance and on the user experience.

The system performs message deliveries from producers to consumers. So the latency would be a good measure of the user experience.

However, because I am new to this area so I am a little lack of the background knowledge on it.

Is there any one who has worked on similar topics? Could you give me reference papers to get some understandings on what kind of measure can be used, how those can be represented, ... etc.

(For example, a paper with title "Improving Web Caching System by Adaptive ABC algorithm" can have such information.)

# Answer
I think that a good starting point to understand how the memory (including caching) works is What Every Programmer Should Know About Memory from U. Drepper. In fact, this is one of the best papers I have ever read about computers.

More recently, I found How misaligning data can increase performance quite entertaining. It is a direct application of the things you can learn from the first one.
> 1 votes

---
Tags: reference-request, performance
---


# Question
Title: Fixed-length decision-tree-like feature selection to minimize average search performance
I have a complex query $Q$ used to search a dataset $S$ to find $H\_\text{exact} = \\{s \in S \mid \text{where $Q(s)$ is True}\\}$. Each query takes on average time $t$ so the overall time in the linear search is $t\cdot |S|$. I can break a query down into simpler sub-queries q\_i and find $H\_\text{approx} = \\{s\in S \mid \forall q\_j(s) \text {is True}\\}$ and where $H\_\text{exact}\subseteq H\_\text{approx}$. Each subquery $q\_i$ is much faster to compute, so overall it is faster to find $H\_\text{approx}$ and then use $Q$ to find $H\_\text{exact}$.

Each $Q$ has many $q\_i$. The overlap between different $Q$ is high. I'm looking for a way to determine a decision-tree-like set of fixed questions $q\_j$ which minimize the average time to find a H\_exact, based on a large sample of search queries.

To make this more concrete, suppose the data set contains the 7 billion people in the world, and the complex queries are things like "the woman who lives in the red house on the corner of 5th and Lexington in a city starting with B."

The obvious solution is to check every person in world and see who matches the query. There may be more than one such person. This method takes a long time.

I could pre-compute this query exactly, in which case it would be very fast .. but only for this question. However, I know that other queries are for the woman who lives on the blue house on the same corner, the man who lives on the same corner, the same question but in a city starting with C, or something totally different, like 'the king of Sweden.'

Instead, I can break the complex question down into a set of easier but more general sets. For example, all of the above questions have a gender-role based query, so I can precompute the set of all people in the world who consider themselves a 'woman.' This sub-query takes essentially no time, so the overall search time decreases by roughly 1/2. (Assuming that by other knowledge we know that a Swedish "king" cannot be a "woman." Hatshepsut was an Egyptian woman who was king.)

However, there are sometimes queries which aren't gender-based, like "the person who lives on 8th street in a red house in a city starting with A." I can see that the subquery "lives in a red house" is common, and pre-compute a list of all those people who live in a red house.

This gives me a decision tree. In the usual case, each branch of the decision tree contains different questions, and the methods to select the optimal terms for the decision tree are well known. However, I'm building on an existing system which requires that all branches must ask the same questions.

Here's an example of a possible final decision set: question 1 is 'is the person a woman?', question 2 is 'does the person live in a red house?', question 3 is 'does the person live in a city starting with A or does the person live in a city starting with B?', and question 4 is 'does the person live on a numbered street?'.

When a query $Q$ comes in, I see if its $q\_i$ match any of the pre-computed questions $q\_j$ I've determined. If so, then I get the intersection of those answers, and ask the question $Q$ on that intersection subset. Eg, if the question is "people who live in a red house on an island" then find that "person lives in a red house" is already precomputed, so it's only matter of finding the subset of those who also live on an island.

I can get a cost model by looking at a set of many $Q$ and check to see the size of the corresponding $H\_\text{approx}$. I want to minimize the average size of $H\_\text{approx}$.

The question is, how do I optimize the selection of possible $q\_j$ to make this fixed decision tree? I tried a GA but it was slow to converge. Probably because my feature space has a few million possible $q\_j$. I've come up with a greedy method, but I'm not happy with the result. It too is very slow, and I think I'm optimizing the wrong thing.

What existing research should I be looking at for ideas?

# Answer
> 1 votes
The solution I found (I asked the question) is to use superimposed coding, and more specifically, a variant of Zatocoding which has better support for hierarchical descriptors.

The method I used comes from 'An Efficient Design for Chemical Structure Searching. I. The Screens', Alfred Feldman and Louis Hodes, J. Chem. Inf. Comput. Sci., 1975, 15 (3), pp 147–152.

The non-hierarchical solution is to look at the information density. Each descriptor will be assigned $s\_i=-log\_2(f\_i)$ bits where $f\_i$ is the frequency in the data set ($0\<$f\_i\<=1.0). Compute the total number of bits $D$ (the size of the decision tree) using $D=\sum(s\_i f\_i)/M\_c$ where $M\_c$ is the Mooers compression factor 0.69 (from $log\_e 2$). Once you have determined the total number of bits to use, select $s\_i$ bits randomly for each descriptor for bit assignment.

The hierarchical solution from Feldman and Hodes replaces $s\_i=-log\_2(f\_i)$ for descriptors which are a subset of other descriptors. In that case, use $s\_i=-log\_2(f\_i/g\_i)$ where $g\_i$ is the frequency of the least frequent parent. In addition, when doing the bit assignment do not select bits which are also used by the parent's bit assignment.

There's still a problem of how to come up with the right descriptors, but that will be domain specific.

---
Tags: algorithms, optimization, machine-learning, greedy-algorithms, databases
---


# Question
Title: Complexity to generate every combination of every size for a given sequence
I would like to estimate complexity in space and time of generating every combination of every size for a given sequence.

Exemple :

```
 seq = [1,2,3]
 combinations = [{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}]

```

From what i know, for a given sequence of size n and a fixed combination size k, the number of combination generated is ${n}\choose{k}$, so i suppose than complexity in time and space is $O({{n}\choose{k}})$.

What we want is the sum for every value of $k$, $O({\sum\_{i=1}^n{{n}\choose{i}}})$

I know that for a sum the complexity equals to the most complex element of the sum.

For the binomial coefficient, if n is even, the biggest one will be $n \choose \frac{n}{2}$

So i can put a an upper born as $O(n.{n \choose \frac{n}{2}})$

Is there a more precise way to determine the complexity of this operation ?

# Answer
Each element in the sequence is part of the combination or not (a binary choice). Since there are $n$ elements, this gives $2^n$ possible combinations.

Using a gray code to iterate over the elements we can make sure that we iterate over every possible combination by only putting in or taking out a single element every time.

Assuming your elements are numbered $1\dots n$ we can use the following algorithm. If our current combination $C\_k$ contains an even amount of elements, toggle element $1$ to get $C\_{k+1}$. Otherwise, toggle element $\min(C\_k)+1$ to get $C\_{k+1}$.

Starting from the empty combination $\\{\\}$ we get:

\begin{matrix} \\{\\} & \text{even} & \text{toggle $1$}\\ \\{1\\} & \text{odd} & \text{toggle $\min(\\{1\\}) + 1$}\\ \\{1, 2\\} & \text{even} & \text{toggle $1$}\\ \\{2\\} & \text{odd} & \text{toggle $\min(\\{2\\}) + 1$}\\ \\{2, 3\\} & \text{even} & \text{toggle $1$}\\ \\{1, 2, 3\\} & \text{odd} & \text{toggle $\min(\\{1, 2, 3\\}) + 1$}\\ \\{1, 3\\} & \text{even} & \text{toggle $1$}\\ \\{3\\} & \text{odd} & \text{toggle $\min(\\{3\\}) + 1$}\\ \cdots & \cdots &\cdots \end{matrix}

By separately storing whether we are currently even/odd and flipping it, and storing our combination in sorted order we can always get to the next combination in $O(1)$ time. So it simply takes $O(2^n)$ time to generate all combinations.
> 5 votes

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


# Question
Title: Bottom-Up Evaluation of Inherited Attributes
I came across $2$ translation schemes of Syntax Directed Translation (SDT) in compilers which are as follows :

* Using a top-down translation scheme, we can implement any $L$-attributed definition based on a $LL(1)$ grammar.
* Using a bottom-up translation scheme, we can also implement any $L$-attributed definition based on a $LL(1)$ grammar (each $LL(1)$ grammar is also an $LR(1)$ grammar).

What these $2$ Definitions actually mean ? I am not getting ..

---

I am well aware of $L$-attributed definition and $S$-attributed definition of SDT and top down parsing and bottom up parsing but It is just that I am unable to recollect this information and phrase it according to the definitions given above.

---

It would be good, if I can get one example of both definitions so, that I can phrase it meaningfully of what is said .

# Answer
> 3 votes
* Using a top-down translation scheme, we can implement any $LL$-attributed definition based on $LL(1)$ grammar.
* Using a bottom-up translation scheme, we can **also** implement any $LL$-attributed definition based on $LL(1)$ grammar (**each** $LL(1)$ grammar is also an $LR(1)$ grammar). Using bottom-up translation scheme, we implement $LR$ grammar actually but since $LL(1) \subset LR(1)$ we can safely implement $LL(1)$ grammar as well.

# Answer
> 1 votes
LL Means Left read and Left derived and LR is Left read and Right derived the left and right part generally makes the difference between how the parser is written and if it top down or bottom up parsing.

The dragon book should be your go-to reference for anything related to parsers and parsing techniques.

---
Tags: formal-grammars, compilers, parsers, attribute-grammars
---


# Question
Title: Is there a dual concept to "Turing Complete" in logic?
Two computing models can be shown to be co complete if each can encode a universal simulator for the other. Two logics can be shown to be co complete if an encoding of the rules of inferences (and maybe axioms if present) of each be shown to be theorems of the other. In computability this has led to a natural idea of Turing completeness and the Church Turing Thesis. However, I have not seen where the logical co completenesses has led to any naturally induced idea of total completeness of similar quality.

Since Provability and Computability are so closely related, so I think it isn't too much to consider that there could be a concept in logic that is a natural dual to Turing Completeness. Speculatively, something like: there is a "true" theorem that isn't provable in a logic if and only if there is a computable function that isn't describable by a computing model. My question is, has anyone studied this? A reference or some keywords would be helpful.

By "true" and "computable" in the previous paragraph I'm referring to the intuitive but ultimately undefinable ideas. For example, someone could show that the finiteness of Goodstein sequences is "true" but not provable in Peano arithmetic without fully defining the concept of "true". Similarly, by diagonalization it can be shown that there are computable functions that are not primitive recursive without actually fully defining the concept of computable. I was wondering, even though they tend to ultimately be empirical concepts, perhaps the concepts could be related to each other well enough to relate the concepts of completeness.

# Answer
I'm not sure why you say "true" is ultimately undefinable, as there is a precise definition for what it means for a first order formula to be true.

What's unique in the case of computability, is that for any definition (as wild as your dreams) for a "computational model", you can finally associate it with a set of functions (the functions it can compute). Thus, you can naturally compare different models, and upon fixing one (based on some empirical justification such as "it is a good representation of computation in the real world") you can call any other model complete if it computes exactly the same set of functions.

However, how do you compare different logics? It seems there is no natural property you can attach to an arbitrary logic, and use it to compare it to other systems. You can perhaps, fix the logic, e.g. first order predicate logic, and ask about completeness of an axiomatic system. Suppose you work in ZFC, and believe it consists of the natural axioms that represent the world. Now, when given a different axiomatic system, you can ask whether they have the same theory, and call this system complete in the case the answer is yes. I think the difference from the computability case, is that for computability, there is a stronger consensus on what the "base model" should be. The reason for this consensus is that many independent models of computation were later shown to be equivalent, so this seems like a very strong empirical evidence for what our "base model" should be.
> 1 votes

---
Tags: computability, logic, turing-completeness
---


title: Semi decidability proof

text:
# Question
Title: Semi decidability proof
I'm studying for my theory of computation exam and came accross the following question:

*Construct an appropriate Turing machine for the following language and prove or disprove it's semi-decidability:*

$A := \\{w \in \\{0, 1\\}^\*\ |\ \exists x \in \\{0, 1\\}^\* .f\_w(x) = |x| \\}$

The way I interpret this is that $A$ consists of all TM encodings $w$ which describe a TM $M'$ that for at least one input $x\in\\{0, 1\\}^\*$ outputs the length of $x$. So now I try to come up with a TM $M$ for $A$, this TM should simulate TM encodings $w\in\\{0, 1\\}^\*$ and check whether the TM $M'$ it simulates computes $f(x) = |x|$ for at least one $x$. In order to do this, $M$ would have to try computing all possible inputs for $M'$ and check if $f(x) = |x|$ is true for at least one input, if such an input $x$ exists than $M$ will terminate and accept the encoding of $M'$ which is $w$. If such an input $x$ doesn't exist then $M$ will keep simulating $M'$ forever and therefore won't halt. Hence I conclude that $A$ is semi decidable since it halts if a solution exists and otherwise doesn't.

Does this make any sense?

Also, since I need to prove/disprove $A$'s semi-decidability, I conclude that $A$ is not decidable (Rice's theorem), is that correct?

# Answer
What you have to do is systematic search for a string $x$ such that $f\_w(x) = |x|$ or in other words $M\_w(x) = |x|$. Given $w$ your TM $M$ should try ALL input strings $x$, not just to simulate $M\_w$ on a single $x$.

If you wait $M\_w(x)$ until it halts then you ($M$) may stuck in case $M\_w$ does not halt on $x$. So, that option is not possible.

One possible way is to systematically try all pairs $(x,i)$ which means "simulate $M\_w(x)$ for $i$ steps". Your strings may be encoded an put in one to one correspondence with integers. So a pair $(i,j)$ means simulate $i$th string $s\_i$ for $j$ steps on $M\_w$. Each time you simulate $(i,j)$ you check if after $j$ steps $M\_w(s\_i)$ halts and if yes then compare its output with $|s\_i|$. If the output is equal to $|s\_i|$ then ACCEPT and halt, otherwise you go to the next pair $(i,j)$. Thus so on until you ($M$) find a pair $(i,j)$ such that $M\_w(s\_i)$ halts after $j$ steps and its output is equal to $|s\_i|$.

In other words, you simply give a chance to your machine $M$ to run on every $x$ for a certain number of steps, and after running for the certain number of steps you check if it halts and if it halts you compare its output with the input length.

Now to prove that it is semi-decidable notice that if indeed there is $x$ such that $f\_w(x) = |x|$ then there are integers $m$ and $n$ such that $s\_m = x$ and $M\_w(s\_m)$ halts after $n$ steps. You will eventually find that pair $(m, n)$ after a finite number of steps since you systematically try all pairs $(i,j)$. If such pair does not exist at all then your machine never halts and will run forever. Thus that set is semi-decidable. Similar post
> 1 votes

---
Tags: turing-machines, semi-decidability
---


# Question
Title: Proving unsatisfiability of a propositional formula
I have a propositional formula $F$ and an assignment of truth variables $A$. The assignment $A$ assigns a truth value to each variable in $F$ and then it can be evaluated.

I have a function which for a given formula $F$ and a given assignment $A$ checks if both $A$ and $\overline A$ evaluate to the same truth value. It looks like this:

```
boolean checkSymmetry (Formula F, Assignment A) {

    if (evaluate(A) == evaluate((not A)))
        return true;
    else
        return false;
}

```

Now I want to use method `checkUnsatisfiability` to check if a given formula $F'$ is "symmetric" as described above. Something like:

```
boolean checkSymmetryWithCheckUnsatisfiability (Formula F) {

    /* The checkSymmetry problem is reduced to the checkUnsatisfiability problem to which I have a solution. */
    boolean result = cleverUseOfCheckUnsatisfiability(F);

    // result is true if Formula F is "symmetric", otherwise false
    return result;
}

```

All right, so there is no way to reduce checkUnsatisfiability to checkSymmetry since that would mean reducing an NP-Complete to an easy one which is impossible unless $P = NP$, thanks to @xavierm02 and especially @chi for clarifying this.

Since checkSymmetry is easy and checkUnsatisfiability is hard It should be possible to reduce checkSymmetry to checkUnsatisfiability in polynomial time, is that correct? If so, how would I do that?

# Answer
> 2 votes
If we take the problem precisely as stated, the answer is negative, assuming $P\neq NP$. Indeed, `checkSymmetry` is trivially implementable in polynomial time, since it takes as input both the formula $F$ and the assignment $A$, so it can check those. Hence, if a reduction existed, that would imply that unsatisfiability is polynomially decidable, hence $P=NP$.

---

(Update: my guess below was not what the OP wanted, but I am leaving it here anyway.)

However, I guess your `checkSymmetry` is meant to take only $F$ as input, and check something equivalent to the validity of $F \iff \bar F$, where $\bar F$ is $F$ with every atomic formula negated.

Then, we can reduce checking validity of any propositional formula to checking symmetry.

Given any $F$, take $G := P \land \lnot F$, where $P$ is an atomic formula not occuring in $F$. We have $$ \models F \iff \models (G \iff \bar G) $$

($\Rightarrow$) Assume $\models F$: we deduce immediately $\models \bar F$.

We need to prove that $$ \models (P \land \lnot F) \iff (\lnot P \land \lnot \bar F) $$ but we know $F$ and $\bar F$ are true for all assignments, so the above simplifies to $\models \bot \iff \bot$ which is trivial.

($\Leftarrow$) Assume $\models G \iff \bar G$. We need to prove $\models F$. Let $A$ be an assignment for $F$. Extend it to $B:=A\[P\mapsto \top\]$. We have $$ B \models G \iff \bar G $$ which is $$ B \models (P \land \lnot F) \iff (\lnot P \land \lnot \bar F) $$ which, thanks to the choice of $B(P)$ simplifies to $$ B \models \lnot F \iff \bot $$ hence $B \models F$, and we also have $A \models F$ since $P$ does not occur in $F$.

---
Tags: reductions, satisfiability, propositional-logic
---


# Question
Title: Probability that all indices divisible by 100 in a hash table with linear probing are occupied
I am trying to solve this question on Sedgewick's and Wayne's Algorithms book:

> Suppose that a linear-probing table of size 10^6 is half full, with occupied positions chosen at random. Estimate the probability that all positions with indices divisible by 100 are occupied.

So we had 500.000 inserts on the hash table and need to check the probability of positions 0, 100, 200, ..., 99900 being occupied. So far I thought about calculating the events one by one: On the first insert there are 10^4 / 10^6 probability of inserting in an index divisible by 100. On the second, we have to consider that the first index divisible by 100 was chosen, so there is a 9.999 / 10^6 probability.

And since we have more inserts (500.000) than indices divisible by 100, I thought about computing the probability of 10.000 inserts occupying the indices divisible by 100 and then multiplying this probability by 50, since we could "try" this insert pattern 50 times.

P = (10.000 / 10^6 * 9.999 / 10^6 * ... * 1 / 10^6) * 50

Is this line of thought correct? Also, the tricky part here is that we are talking about a linear-probing hash table. So if we insert an element on index 99 twice, the second element will occupy index 100. This also means that inserting an element on index 1 100 times will mean that index 100 is occupied. I am not sure how to deal with this extra requirement. Any ideas?

# Answer
> 2 votes
This problem may be reduced to the following simple probability problem with concrete numbers.

Assume you have an urn with 8 black and 12 white balls, total 20 balls. You randomly draw 15 balls from the urn one by one **without replacement**. What is the probability that all black balls are selected?

How does it relate to the original problem? Occupying slots one by one is equivalent to drawing balls without replacement. Both number of slots and balls decrease. "Drawing a ball" corresponds to "eventually occupying a slot" after linear probing (searching).

We have address space of $10^6$ slots equivalent to having $10^6$ balls in an urn. Then you have positions with indices divisible by 100 equivalent to having $10000$ $(=10^6/100)$ black balls. $500000$ positions are occupied means that you draw $500000$ balls. Finally, the requirement "all positions with indices divisible by 100 $(=10^6/100)$ are occupied" means "all $10000$ black balls must be selected".

Thus it is the hypergeometric distribution that describes the probability of $k$ successes in $n$ draws, without replacement, from a finite population of size $N$ that contains exactly $K$ successes, wherein each draw is either a success or a failure (black or white). The probability is equal to

$$ P(k \text{ successes})= \frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}$$

So, if we take urn-balls model then we have $$ P(8 \text{ black balls})= \frac{\binom{8}{8}\binom{20-8}{15-8}}{\binom{20}{15}}$$

As for the original problem then we have $$ P(10000 \text{ occupied slots})= \frac{\binom{10000}{10000}\binom{10^6-10000}{500000-10000}}{\binom{10^6}{500000}}$$

Now, our numbers in the original problem is too large to compute the binomial coefficients. You could get around the problem using Stirling's approximation.

---
Tags: probability-theory, hash-tables
---


title: Ant colony optimization algorithm

text:
# Question
Title: Ant colony optimization algorithm
if i have an equation like $$f\_n = x + y + z + a + b$$ and each variable has a discrete answer like $a = 0, 1 , 3$ . $b = 2 ,4,5$ etc. i want to find the global optimum minimization point. I used Ant colony optimization (ACO) to solve the equation but i am stuck in the heuristic information and how to compute these parameters, as I saw in the traveling sale's man problem eta = one over distance between two cities. But here there is no relation between $x$ and $y$ .

Second i want to make sure that when computing $\delta\_\tau$ pheromone updating trail , its equal to $$f\_n(\text{best answer in iteration k})\over f\_n(\text{worth answer in iteration k})$$ as i saw another equations in papers and got distracted. I built a matlab model but it didn't give me the optimum point at each run time . Thank you

# Answer
> 0 votes
There is no simple answer for how to choose parameters. This is a heuristic, so there are no guarantees.

Here are a few strategies that are widely used:

1. Random search: Try many different parameters. In each trial, you randomly choose all parameters, solve the optimization problem using those parameters, and then remember the solution. Take the best solution found.
2. Grid search: Systematically search over the space of possible parameters. For instance, if there are two parameters $\alpha$ and $\beta$, you might let $\alpha$ range over values $0.1$, $1$, $10$, and $100$, and let $\beta range over a similar set, and try all combinations; then take the best solution found.
3. Try smaller problems: Construct a smaller problem (e.g., synthetically). Find the best parameter settings for it (by applying one of the prior two methods). Then, use those parameter settings on your larger problem, and hope they'll be good for your larger problem, too.

---
Tags: algorithms, graphs, optimization
---


# Question
Title: Print the number of subarrays of an array having negative sums
**Problem statement**: Given an array of N integers, find its number of negative subarrays (i.e sub arrays having negative summation). E.g: for an array $\[1,-2, 4, -5, 1\]$ there are 9 subarrays whose sum is negative. Subarray means sequential array within an array.

**My code**: It's complexity is $\theta(n^{2})$ as we can see. I have applied brute force technique. How can I improve my code/pseudocode?

```
    int sum=0,count=0;
    for(int i=1,k,j;i<=N;i++){
        for(k=1;k<=N-i+1;k++){
            for(j=0;j<i;j++){
                sum += arr[j+k-1];
            }
            if(sum<0)
                count++;
            sum = 0;
        }
    }

```

# Answer
> 2 votes
An $O(n \log n)$ solution:

Find prefix sums $S\[i\] = \sum\_{k=0}^{i} a\[k\]$

Set $S\[-1\] = 0$

Now count the number of inversion pairs in $S\[-1\], S\[0\], \dots, S\[n-1\]$

---
Tags: algorithms, searching
---