# Question
Title: Are all databases reducible to this ultimate abstract database design?
I've designed a few databases in my time, and on more than one occasion the drive to abstract common elements from specific tables has led me to create generic top-level tables which contain those common elements. For example:

```
Table      Column         Column

Hamburgers Item           Topping
           Cheeseburger   Tomatoes
           Mushroomburger Swiss

```

Could be "simplified" ("normalized") as:

```
Table      Column         Column

FoodTypes  ID             Name
           1              Hamburger
           2              Topping

Food       Item           TypeID
           Cheeseburger   1
           Mushroomburger 1
           Tomatoes       2
           Swiss          2

```

Recently I've gone over the deep end with this approach, abstracting and re-abstracting a fairly complex database design until I was left with something both very simple and yet completely un-resembling of the actual data being stored.

This has led me to the conclusion that all databases could be "summarized" in a single monstrous table called "Entries" with columns:

```
ID       Type     Value1     Value2

```

For example:

```
ID       Type     Value1     Value2
4321     Item
8746     Descrip  4321       Food
5673     Item
9876     Descrip  5673       Hamburger
0341     Item
1234     Descrip  0341       Lettuce
5478     Relation 5673       0341
2381     Descrip  5478       Topping
2244     Relation 5673       4321
2160     Descrip  2244       Class
4436     Relation 0341       4321
7547     Descrip  4436       Class

```

Here, using these 4 columns in 1 table, I have created two objects sharing a common superclass, given them an attribute, and defined not only a relationship between them but the class of that relationship as well. We could now say "Lettuce is a Topping of Hamburger, both of which are Foods".

There would of course be a set of rules for this system, but that is beyond the scope of this question.

My question is, is this not logically the case? If so (or if there is a different, "correct" answer), what is this in relation to real databases? Does such a system exist, or should it not?

I'm not sure if I've gone far enough in my analysis, and I feel like I'm on the verge of some insight which is profoundly obvious to mathematicians and computer scientists (like "yes, all relational data can be described in terms of binary operands like F\[a, b\]).

# Answer
> 11 votes
This insight was made at least as far back as 1886, by Alfred Kempe. In fact, he observed that any set of relationships (not just those that are already relations) can be captured as a binary relation. At the time this seems to have come as a shock to Charles Sanders Peirce, who had built his relation algebra on the idea that any relation can be captured by means of ternary relations, and who up to this time apparently believed this to be the best possible. Kempe used graphs to illustrate his notion, while Peirce used edge-labelled graphs. In a long and admiring review Peirce revised his theories to accommodate binary relations as a possible foundation, and distinguished the two approaches:

> Mr. Kempe's conception depends upon considering the diagram purely in its self-contained relations, the idea of its representing anything being altogether left out of view; while my doctrine depends upon considering how the diagram is to be connected with nature.

In terms of modern database representations, RDF corresponds to Peirce's ternary relations, while key-value stores correspond to Kempe's graphs. As Raphael pointed out in a comment, these are essentially the ideas behind graph databases.

As an aside, the arguments about binary/ternary/quaternary/quinternary/... tuples being the "best" foundation for data representation still rage on in the W3C semantic web working groups. I believe that the original insight of the relational model was that for efficiency, one should use relations of the right arity; relationships that are naturally represented as tuples should not be transmogrified into more complicated data structures just for reasons of purity. However, this argument also goes the other way: relationships where different instances naturally have different arities should not be shoehorned into a rigid relational schema just to preserve the purity of the data model.

* A. B. Kempe, *A Memoir on the Theory of Mathematical Form*, Philosophical Transactions of the Royal Society of London **177**, 1886, 1–70.
* C. S. Peirce, *The Critic of Arguments* (1892 essay), in *Collected Papers of Charles Sanders Peirce*, Vol. III, Harvard University Press, 1933, 250–265.

---
Tags: databases, normal-forms
---


# Question
Title: Realtime hardware/software versus PC software/hardware, how are these distinct and alike?
This question stems from a few answers and comments on a question I posted in signal processing found here.

I guess I am a little confused. Are there any concrete differences between realtime software/hardware and just a regular PC?

I would try to list what I think the differences are but the list I have come up with is ambiguous and short.

The only thing I think makes sense to separate the two ideas is that PC software can run part of its code part of the time, real-time runs all of its code each time. So a PC can load a program but not all programs and run just that program for however long it pleases, real-time is just a single program with a bunch of if-else, switch logic basically a huge abstract collection of relays (PLC) that gets ran through every time it is called.

Yes I realize this is a pretty poor description, so I ask is there any good concrete ways to separate these ideas?

# Answer
> 7 votes
In general, the difference between "normal" and "real-time" is some sort of guarantee on the time it takes to complete job. In a normal system, usually you have no guarantees at all. Programs can get interrupted by other programs, the OS scheduler might not be completely fair, the processor does complicated things that alter the runtime between executions of the same code...

For most applications this does not matter.

Real-time systems are built such that one can guarantee that job X is always completed after at most Y seconds. This is important for example for the chip that decides when to deploy air bags--if that takes longer than expected, you're dead. To be able to give these guarantees you have to use special operating systems (or no operating system at all) that guarantees appropriate scheduling. It is also necessary to know a lot of details about the hardware you're using. Does your chip have a cache? What kind of replacement policy does it use? How many cycles does an addition take? Is that always the same number? What's the branch prediction algorithm? etc.

Many people confuse real-time systems with very powerful processors that can churn through data "in real time". But that's not (always) the case. The important thing is not how long it takes in absolute time, the important part is that it never takes longer than expected. There are trade-offs both in hard- and software between throughput (expected computation speed) and predictability (worst-case speed).

---
Tags: terminology, computer-architecture, real-time
---


# Question
Title: The choice of programming language and the length of a program
I wonder how it's possible that:

> it can be shown that all reasonable choices of programming languages lead to quantification of the amount of absolute information in individual objects that is invariant up to an additive constant.

from the Preface to the First Edition, An Introduction to Kolmogorov Complexity and Its Applications by Li & Vitanyi.

I don't know how they defined "*reasonable choice of programming language*", but in my sense, it seems natural that the choice of programming language could mix the rank of the complexity. If the programming language fits the object, the program would be shorter, and if not, it would be longer.

But, if I understood it all right, the paragraph above says that no matter which programming language you choose for the strings(objects), the rank of the length of the programs would not change!

Is it really possible? and could someone explain how it's possible?

It is well known that either AND and NOT or OR and NOT can be a primitive function for a computer,

and if I want to implement AND with (OR and NOT), it goes like

NOT(NOT a OR NOT b) instead of just AND!!!

# Answer
> 5 votes
What Li and Vitanyi mean by a reasonable programming language is one that is Turing-complete. This means that you can simulate it on a Turing machine and you can simulate a Turing machine on it, so it has the same expressive power as a Turing machine. This gives you a kind of class of languages. I can prove that C is equivalent to a Turing machine, and that Java is equivalent to C, so Java is equivalent to a TM. In over fifty years, no-one has found a reasonable mechanism that is more powerful than a Turing machine (without resorting to things like time travel). This means that the Turing complete languages are considered those that are most reasonable for expressing the principle of computation (see the Church -Turing thesis).

This means that if we agree that the information content of a string should be defined as the length of the shortest program in a Turing complete language, we can never disagree much beyond that. Say that we have a string $x$ and you recon that this string contains only fifteen bits of information. I can then simulate your Turing-complete language in my Turing-complete language and run your fifteen bit program. Since my simulation of your language does not depend on $x$, we can never disagree by more than a constant amount, and for large enough $x$, the difference will become negligable.

So up to a constant term, the information content is a property of the string itself.

---
Tags: computability, kolmogorov-complexity
---


# Question
Title: How to convert NFA with null moves to NFA without null moves?
I am converting NFA **with $\varepsilon$-moves**  to the NFA **without**  $\varepsilon$-null moves. I understand that if, there is a $\varepsilon$-move between, $q\_i$ and $q\_j$, then all edges from $q\_j$ have to be repeated from $q\_i$. And if the $q\_j$ is a final state, then $q\_i$ will also be a final state.

But, if $q\_j$ does not contain any transition, i.e., there are no edges starting from $q\_j$, then what has to be done?

# Answer
If $q\_j$ is a final state, you already said you would make $q\_i$ into a final state. If there's no transitions from $q\_j$ to another state in the FSM, then you are staying there forever- either as an accepting state or as a trap state. Either way, staying in $q\_i$ is the same as staying in $q\_j$ if you can't go anywhere from $q\_j$.
> 2 votes

# Answer
Simply put, you do exactly as you said. If $q\_j$ does not contain any transition you don't have anything to do so you do nothing more than removing $q\_j$ and updating $q\_i$ as final if $q\_j$ is final.
> 0 votes

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


# Question
Title: Is there an affordable experiment which shows chips can't get much smaller?
If I am correct, chips cannot get much smaller because of Heisenberg's uncertainty principle. My friend and I want to perform an experiment (which is cheap, i.e. doesn't require million-dollar equipment) which shows that if a chip is too small, it will mess up. Is there any such experiment?

# Answer
> 8 votes
I think you are right that the Heisenberg uncertainty principle is involved in the limit. I don't think we are anywhere near the Heisenberg limit. The limit we are currently approaching is that we currently compute with devices based on atoms. An atom is about 1 angstrom = .1 nm wide. We are currently making transistors that are about 22 nm wide, so we're getting close to needing to make 1 atom transistors. If we want to scale beyond that we're going to need to find ways of computing that involve storing and manipulating multiple states per atom.

The wikipedia article on fundamental limits of computation is a good starting point. I think what you really want is the Bekenstein bound.

The researchers that I know of in this area are Rolf Landauer, Charles H Bennett, and Seth Lloyd. (I think Charles H Bennett considers himself a computer scientist while the other two consider themselves physicists.) Richard Feynman was also very interested in this question and has a book called *Feynman Lectures on Computation* (which you can read about at http://quantum.quniverse.sk/buzek/zaujimave/p257\_s.pdf). Also @PeterShor is an active member here and is *the* expert on quantum computation.

Here's a Scientific American article by Bennett and Landauer:

http://web.eecs.umich.edu/~taustin/EECS598-HIC/public/Physical-Limits.pdf

Here's Seth Lloyd's article in Nature: http://arxiv.org/abs/quant-ph/9908043

Here's a web page at Cambridge: http://www.sp.phy.cam.ac.uk/~SiGe/Fundamental%20Limits%20of%20Computation%20-%20Landauer%20and%20Heisenburg.html

---
Tags: computer-architecture
---


# Question
Title: Please explain "decidability" and "verifiability"
I am trying to (intuitively) understand the two terms "decidability" and "verifiability".

I have done a reasonable amount of searching and going through the various texts I can put my hands on. However, their intuitive understanding seems to escape me, specially for the second one.

Out of the many definitions found, the following one found in this page, clearly explained decidability to me.

> A language is called decidable if there exists a method - any method at all - to determine whether a given word belongs to that language or not.

However, I fail to find a parallel definition for verifiability.

In the Theory of Computation book by Sipser, we find,

> P = the class of languages for which membership can be *decided* quickly.
>
> NP = the class of languages for which membership can be *verified* quickly.

In light of the above, I want to understand verifiability.

Please provide as many examples as you can, at one moment, I try catch the meaning, in the next one, I get confused again.

# Answer
The key to understand here is that P and NP are classes of decision problems. That means that all of them have yes/no answers.

So when we say a problem like 3-SAT is NP-Complete, it means that given an instance of 3-SAT (aka a word potentially in the language), there is no known efficient way to test if the word is or is not in the language.

To say something is in NP means that there exists some sort of "proof" for each string in the language, which is polynomial in the length of the input.

For example, in 3-SAT, we're asking, does there exist an assignment of True/False to a set of variables in a boolean formula, such that the formula comes out to be true. The word we're testing is the boolean formula. There's no known way to find if there is a single solution that makes the whole formula true. But, if we have a set of true/false values for the variables, it's very easy to check (in polynomial time) if it causes the formula to evaluate to true.

The key point here is that the word we're testing is NOT the true/false values for each variable. The word we're testing is the formula containing the variables, and the language is the set of all boolean formulas which evaluate to true.

We don't know how to efficiently test if the word (formula) is in the language (can evaluate to true), but given a set of true/false assignments, we can verify if it evaluates to true i.e. it is a "proof" that the word (formula) is in the language. Thus the problem is in NP, but not known to be in P.

NP is actually the class of non-deterministic polynomial solvable decision problems. This is because, in a non-deterministic turing machine, we have "decision" points where we can take one of multiple actions, and our polynomial certifier is basically just telling is which decision to take at each decision point.
> 7 votes

# Answer
suppose you give me a problem and you asked me a solution so let's say that you can check only polynomial amount of my proof (that is : you can run efficient computer program on my proof) when I send you my proof of the solution all what you do is to run your program and decide according to what the program output .
for example : suppose you ask me if a graph is 3-colorable , then what I have to do is to sent a 3 coloring of the graph then you check if all adjacent vertices have different colors then the coloring is legal and the program terminate with "accept"(otherwise the proof is not accepted and we terminate with "reject") .
that's called to verify "quickly".
if you can build a "efficient" "computer program"(or simply: polynomial algorithm) that say if an input(a string of length n) is in the language (or if the program output 1\\"accept") this is what do mean by complexity class P.
example : suppose I give you a list of strings (lets say telephone book ) and asked you about a name that you must say if it is in the book or not . one solution is to go throw all the names and compare each name with the given name, that says you can solve it in linear time.
another example is : given a graph G=(V,E) and an edge e=(u,v) and you want to say if the edge is in the graph .
> 1 votes

---
Tags: complexity-theory, formal-languages, terminology, computability
---


# Question
Title: Proof that fast broadcasts have to target larger cycles first
I am having trouble trying to formulate a simple proof. I can clearly see that what I am trying to prove is correct but to prove it I am not sure what to do.

The problem is a broadcasting problem on a graph. My graph contains two cycles. The two cycles are joined by a single vertex $v$. If the vertex $v$ contains some info that it wants to broadcast to all other vertices on the graph what is the minimum number of rounds required to achieve this.

So a proof I am trying to formulate is that in order to achieve the minimum broadcast time I would have to first broadcast on the largest of the two cycles.

I was thinking of a proof by contradiction. Something like assume that we first broadcast on the smaller cycle and somehow show that it could lead to a broadcast time that is larger than the time if we were to start on the larger cycle.

To clarify, suppose we have two cycles $C\_1$ and $C\_2$ such that $|C\_1| \ge |C\_2|$. So the minimum broadcast time from vertex $v$ denoted by $b(v)$ would require us to broadcast on the larger cycle first.

# Answer
> 2 votes
Let $b\_0$ be the minimal broadcasting time of an information from vertex $v$ to the cycle $C\_0$ and $b\_1$ be the minimal broadcasting time of an information from vertex $v$ to the cycle $C\_1$.

Remark that since $C\_0$ and $C\_1$ are cycles the fastest way to broad cast is for $v$ to broadcast first one of his neighbor and then the other.

Since $C\_0$ and $C\_1$ are only connected by $v$ and $v$ already have the information we know that spreading the information through $C\_i$ will not improve the minimal broadcasting time for $C\_{1-i}$.

3 cases (first one developed the others just ideas):

1. $b\_0\>=b\_1+2$ (hence $|C\_1|\>|C\_2|+3$) if $v$ start broadcasting his two neighbor in $C\_0$ and then those of $C\_1$. The time the information reach the last vertex in $C\_0$ will be $b\_0$ and the last vertex in $C\_1$ $b\_1+2$ hence $b\_0$ in total. And you can't do better by definition of $b\_0$
2. $b\_0=b\_1+1$ if you start twice by $1$ you will do at best $b\_0+2$ and you do better by choosing $0$
3. $b\_0=b\_1$ it doesn't really matter but if the parity of the two cycle is different you may want to start by the odd one (or even not sure :D)

---
Tags: graphs
---


# Question
Title: The sum of all integers less than n with a zero
For example, if n=14, the output should be 10; n=22, the output should be 30=10+20; n=102, output=(10+...+100)+101+102=5703

In this problem, n is smaller than $10^{18}$ , and the algorithm should finish within 1 second.

# Answer
> 3 votes
Let $S(m)$ be the sum of all numbers with at most $m$ digit, i.e $S(m)=10^{m+1}\cdot (10^{m+1} - 1) / 2$.

Let $C(m)$ be the number of at most m digit numbers which contains $0$.

Let $F(m)$ be the sum of numbers with zero in them such that they have at most $m$ digits.

Then is easy to find a recursive relation for $C(m)$ (hint: what is its dual?), after that you can find a recursive relation between $C(m),F(m),S(m)$ as follow:

The main problem is finding $F(m)$, but we know that, new number of m digit with zero in it, is created by number of $m-1$ digit with zero in it and padded by the numbers $0...9$, or $m-1$ digit numbers without zero padded with new zero to the end, or $m-1$ digit numbers with zero in them:

$F(m) = \[F(m-1) \cdot 10 + C(m-1) \cdot 45\] + (S(m-1) - F(m-1))\cdot 10 +F(m-1)\Rightarrow$

$F(m) = F(m-1)+S(m-1)\cdot 10+C(m-1)\cdot 45$

Now for calculating upto specific number, first you need to find the number of its digit, then, write it as sum of power of 10, then you can find each possible sum to each digit (from right to left).

For such a small range this works much less than a second (because is $O(\log n)$), anyway you can preprocess it.

# Answer
> 4 votes
Here are some hints. First, as András suggests, it is easier to sum instead all integers *without* a zero, and then use the well-known formula $1+\cdots+n = n(n+1)/2$.

Let $S\_n$ be the sum of zero-less numbers up to and excluding $n$, and let $T\_k$ be the sum of zero-less numbers of width *exactly* $k$. We start by calculating $S\_{10^k} = T\_1 + \cdots + T\_k$. We have $$ \begin{align\*} T\_1 &= 1 + \cdots + 9 = 45, \\ T\_2 &= 11 + \cdots + 99 = (1 + \cdots + 9 + 10 + \cdots + 90)\cdot 9 = 45 \cdot 11 \cdot 9, \\ T\_3 &= 111 + \cdots + 999 = (1 + \cdots + 9 + 10 + \cdots + 90 + 100 + \cdots + 900)\cdot 81 \\ &= 45 \cdot 111 \cdot 81. \end{align\*} $$ In general we get the formula $$ T\_k = 45 \cdot (1+10+\cdots+10^{k-1}) \cdot 9^{k-1} = 5 \cdot (10^k-1) \cdot 9^{k-1}, $$ from which it is easy to compute $S\_{10^k}$: $$ S\_{10^k} = \frac{5}{9} \sum\_{\ell=1}^k 90^k - \frac{5}{9} \sum\_{\ell=1}^k 9^k = 50 \frac{90^k-1}{89} - 5 \frac{9^k-1}{8}. $$ For the general case, let's take as an example $n = 1234$. Zero-less numbers less than $1234$ come in the following forms:

* Numbers less than $1000$: there are $1 \cdot S\_{1000}$ of these.
* Numbers of the form $1XYZ$ where $X\<2$: there are $1 \cdot S\_{100}$ of these.
* Numbers of the form $12YZ$ where $Y\<3$: there are $2 \cdot S\_{10}$ of these.
* Numbers of the form $123Z$ where $Z\<4$: there are $3 \cdot 1$ of these.

The general case is similar. Suppose $n = d\_k \cdots d\_0$, where none of the digits is zero. Then $$ S\_n = d\_k S\_{10^k} + (d\_{k-1}-1) S\_{10^{k-1}} + \cdots + (d\_1-1) S\_{10} + (d\_0-1). $$ If one of the digits is zero, say $n = 1230456$, then we can replace $n$ with $1230000$, and use the same recipe as before, stopping at the first zero digit.

---
Tags: algorithms
---


title: Assumptions of One Way Functions

text:
# Question
Title: Assumptions of One Way Functions
I try to get the intuition behind the notion of *strong one way function* and *weak one way function* by reading the scribe One-Way Functions. Particularly, I am interested in examples and definitions of the weak and strong one way function. I known it's very broad notion, therefore I will be as specific as possible in my questions.

**Strong one way function**. $\forall$ nonuniform PPT $A$, $\exists \epsilon s.t. \forall n \in N, Pr\_{x\in\\{0,1\\}^n}\[A(1^n, f(x)) \in f^{-1}(f(x))\] \leq \epsilon(n)$

> Q:$1^n$ as the first parameter of the PPT $A$ represent the length of the initial input, the usage of it is justified as *"this ensures that the output of A doesn't shrink the size if its too must as in the f(x)=|x| example".* Unfortunately I didn't get the previous explanation (may be because the lost the sign, which takes an additional bit). In my opinion putting in A the size of $x$ might help $A$ get the right output $x$.
>
> Q: in the lecture it mentioned that $f(x)=|x|$ is hard, *"because it will take $2^c$ time to write a valid inverse of something such that $f(x)=c$"*. It happens because we cannot find $x$ with probability with negligible more than 0.5, but it's due to another problem not a computational but rather information theory problem, by running the function we lost the information about the sign of the input $x$, if it's a correct reasoning, why actually it would take $2^c$ time? In addition for me it looks like the great discover to find the strong one way function, however do have more assumption of hard function like $f(x)=|x|$?

**Definition of weak one way function**.$\exists$ $q(x)$, $\forall$ nonunoform PPT A, $\forall$ n $\in$ N, $Pr\_{x \in \\{0,1\\}^n}\[A(1^n,f(x)) \in f^{-1}(f(x))\] \leq 1-\frac{1}{q(n)}$

> Q: in the lecture there was an assumption that the multiplication is weak one function, how we can actually show that the multiplication is weak one way function, and do we have more assumptions of examples of weak one way functions?

I am very sorry for being naive, even though I will appreciate any help.

# Answer
As for your first question, the reason behind adding $1^n$ as an input to $A$ is to allow it a running time of (at least) a polynomial in $n$. In most applications of one-way functions, $n$ is not a secret, so there is no reason to hide it; in fact, for most functions you can determine $n$ from the output size.

To see what fails if we leave $1^n$ out, consider the situation in the second question. You're misreading the notation - $|x|$ is the *length* of the string $x$. If $x$ is $n$ bits long then $|x|$ is $O(\log n)$ bits long, and so no machine can find a preimage in time polynomial in $|x|$. However, it is easy to find a preimage in time polynomial in $n$. Add ing$1^n$ as a parameter to the adversary $A$ ensures that $|x|$ is not considered a hard function.

Finally, one-way functions, weak or strong, are not known to exist, even assuming P$\neq$NP. This is similar to the situation in computational complexity, where no worst-case hard functions are known. However, some functions are conjectured to be one-way - ask your professor for their favorite ones.
> 1 votes

# Answer
The reason for the $1^n$ is explained here: Why does key generation take an input 1k, and how do I represent it in practice?. Please read that answer for further explanation. This is a standard trick in complexity-theoretic cryptography, and on first reading you can ignore it and focus on the conceptual aspects of the definition.
> 0 votes

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


# Question
Title: Equivalence of logical Formula (Kripke structures)
Can someone explain me how to find if these formulas are equivalent with Kripke structures?

AG(Fp or Fq) , A(GFp or GFq)

AGF(p and q) , A(GFp and GFq)

AFG(p and q) , A(FGp and FGq)

Thank you in advance for your help :)

# Answer
> 2 votes
First, these can all be looked at as LTL formulas. Therefore, their equivalence can be determined by their behaviour on traces (no need for Kripke structures with a complicated structure).

This answer is just a bunch of **spoilers**, so read only if you already tried your best.

For the first pair - they are equivalent. Intuitively, this is because there are infinitely many p's or infinitely many q's iff there are infinitely many (p's or q's). Foramlly,

$\pi\models G(Fp \vee Fq)$ iff at every index $i$, $\pi^i\models (Fp\vee Fq)$, meaning that in every index, there is eventually a $p$ or a $q$. Equivalently, this means that there are infinitely many $p$'s or $q$'s, which is equivalent to $\pi\models GFp\vee GFq$.

For the second pair - they are not equivalent. Try and think of a counter example. If you really can't - leave a comment.

The third pair are also equivalent. Informally - this is because they both state that after a finite prefix, both $p$ and $q$ always hold. The formal argument just follows from the semantics.

---
Tags: logic, linear-temporal-logic
---


# Question
Title: Algorithm to find a line that divides the number of points equally
I have recently been asked in an interview to devise an algorithm that divides a set of points in a coordinate system so that half of the points lie on one side of the line, and the rest on the other side.

The points are unevenly placed and the line must not pass through any of the points.

Can any one give any approach to solve the problem? Analysis of the algorithm is appreciated.

Hints: Count the points, use medians.

The number of points is assumed to be even.

# Answer
One approach is choosing a "generic" direction (in practice, a random direction), projecting all points along this direction, and then using a median algorithm (your line should correspond to any translation which lies between the two medians). If you choose a bad direction then points might clump together, making it impossible to separate them along that direction. However, if you choose a "generic" direction then this won't happen (assuming that the points are distinct). Since there are linear time median algorithms, this is an $O(n)$ algorithm. Using the randomized quickselect algorithm, you get a practical linear time algorithm.
> 9 votes

---
Tags: algorithms, machine-learning, computational-geometry, classification
---


title: Shortest paths candidate

text:
# Question
Title: Shortest paths candidate
Let $G = (V,E)$ be a directed graph with a weight function $w$ such that there are no negative-weight cycles, and let $v \in V$ be a vertex such that there is a path from $v$ to every other vertex. Let $f : V \to \mathbb R$ be a given function. Describe an algorithm that runs in $O(|V| + |E|)$ time that answers yes/no to the question: is it true that for all $u \in V, f(u) = \delta(v,u)$, where $\delta(v,u)$ is the weight of the shortest path from $v$ to $u$?

Obviously what comes to mind is Bellman-Ford algorithm, but it doesn't satisfy the time requirement. I don't really see how having the candidate $f$ function helps us in this regard.

# Answer
> -1 votes
The idea is to build a graph with only the edges that are candidates for the shortest path from $v$ to $u$ assuming that $f$ is the required solution.

If during the process we find an edge that lead to a shorter path then we return false.

Otherwise, at the end, we check that all the nodes are still connected (with a DFS) hence that there exists a path with the required weight.

> if $f(v)\neq 0$ then return false
>
> $\forall e=(v\_1,v\_2)\in E $ do
>
> if $f(v\_2) \> f(v\_1)+w(e)$ then return false
>
> if $f(v\_2) \< f(v\_1)+w(e)$ then remove $e$ from $E$
>
> done
>
> build $cV$ the set of reachable vertices in the new graph (with a DFS)
>
> return $V=cV$

Correction: \- if there exists $u\in V$ such that $f(u)\>\delta(v,u)$ then there exists $e=(v\_1,v\_2)\in E$ such that $f(v\_2) \> f(v\_1)+w(e)$. Let $e\_1,...,e\_n$ be the shortest path from $v$ to $u$ if $f(v\_{i+1}) \leq f(v\_i)+w(e\_i)$ then $f(u)\leq \delta(v,u)$ contradiction.

Hence the algorithm return false.

* otherwise if there exists $u\in V$ such that $f(u)\<\delta(v,u)$ then $u$ is disconnected from $v$ in the resulting graph. Hence the algorithm return false. $u$ is connected, hence there exist a path $e\_1,...,e\_n$ from $v$ to $u$ such that $f(v\_{i+1}) = f(v\_i)+w(e\_i)$ hence $f(u)\geq \delta(v,u)$ contradiction.
* otherwise if for all $u\in V$ $f(u)=\delta(v,u)$ then all the edges belonging to the shortest path verify $f(v\_{i+1}) = f(v\_i)+w(e\_i)$ hence are still in the graph at the end hence all the vertices are still connected. Also there are no edges such that $f(v\_2) \> f(v\_1)+w(e)$ otherwise $f(v\_2)\>\delta(v,v\_2)$.

Complexity:

$O(|E|)$ to build the new graph plus $O(|E|)$ for the DFS plus $O(|V|)$ for set equality hence $O(|V|+|E|)$.

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: Trace dependents & precedents of a program in an imperative language
We have some programs in a very basic imperative language, the programs contain some basic features: assignment, condition, loop, scalar variables, 1-dimensional arrays and 2-dimensional arrays... Note that a variable or an array may not be initialized (or already hold a value before the execution of a program).

My question is... is there some existing work to identify all the dependents and precedents of a program by static analysis of the syntax, without executing the program? Or, is it very trivial to do that?

Without giving a formal definition of dependent and precedent, I illustrate these 2 notions by the following program:

```
a[2,2] = 0;
i = 1;
While i <= 10 do {
  a[2,2] = a[2,2] + a[i,1];
  i = i + 1
}

```

Just from the syntax of the program, we can say, the script precedes `a[2,2]`, because the value of `a[2,2]` is totally determined by the execution of the program. Also, we can say, the script depends on `a[1,1]` to `a[10, 1]`, because the values of `a[1,1]` to `a[10, 1]` determine the running of the program.

I guess roughly we can say, if a variable is on the right side of the first assignment containing it, the script depends on it; if a variable ever appears on the left side of an assignment, the script precedes it. A variable can be both precedent and dependent for a script at same time.

So, is it really that trivial? Which elements may complicate the issue? Is there some existing research?

# Answer
> 2 votes
The analysis you want is called *reaching definitions* in the compiler community.

For your case you would put a "fake" definition of each variable you are interested in at the beginning of the program (representing definitions that are entering your script from outside) and then determine whether that definition reaches any of the uses. If no fake definition reaches any use then the variable is defined inside the script, otherwise its value may be coming in from outside. The interesting cases involve conditionals and loops (some variables may be defined on one side of a conditional and not the other.)

I can highly recommend the following text books if you want to learn more:

* Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D.: *Compilers: Principles, Techniques, and Tools*, 1986.
* Cooper, Keith D.; Torczon, Linda: *Engineering a Compiler*, 2005.

Reaching definitions analyzes scalars (so you would analyze each a\[i,j\] independently, as you did in your example.)

You could try to analyze entire arrays simultaneously, but this is a research topic (because parts of the array can be defined and other parts not). The classic papers on trying to analyze entire arrays are

* Zhiyuan Li: Array privatization for parallel execution of loops. *Int'l Conf on Supercomputing*, 1992.
* Dror E. Maydan, Saman P. Amarasinghe, and Monica S. Lam: Array data-ﬂow analysis and its use in array privatization. *Symp Principles of Programming Languages*, (POPL-20):2-15, 1993.
* Peng Tu and David Padua. Automatic array privatization. *Int'l Workshop on Languages and Compilers for Parallel Computing*, (LCPC-6):500–521, 1993.

---
Tags: programming-languages, formal-methods
---


title: Can this grammar be simplified?

text:
# Question
Title: Can this grammar be simplified?
So, I have a book here, which has an example for context sensitive grammar, and the grammar is the famous $0^n1^n2^n$ , and it has:

$$ \begin{align} S &\rightarrow 0BS2 \mid 012 \\ B0 &\rightarrow 0B \\ B1 &\rightarrow 11 \\ \end{align} $$

I agree that the above works, but what is wrong with just saying: $S\rightarrow 0S12 |\epsilon$

The above also generators the same number of $0$s as $1$s and $2$s.

# Answer
> 5 votes
Your grammar will generate: $S\rightarrow 0S12\rightarrow 00S1212\rightarrow 001212$ which is not in the required language.

# Answer
> 2 votes
By one definition, context sensitive grammars have productions $\alpha \rightarrow \beta$, where the length of $\beta$ can't be less than the length of $\alpha$. This rules out your alternative grammar outright.

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


# Question
Title: Are there any problems in $APX - PTAS$ that are not $APX$-complete?
I have a question about the structure of the complexity class $APX$. Obviously, unless $P=NP$, no problem in the class $PTAS$ can be $APX$-complete (under the AP-reduction). However, what about the rest of problems in $APX$? Are there any problems known that are in $APX$, do not have a $PTAS$ (unless $P=NP$) and at the same time are provably not $APX$-complete (unless $P=NP$)?

For the class $NP$, Ladner's Theorem guarantees the existence of problems in $NP - P$ that are not $NP$-complete (unless $P=NP$) - the so-called $NP$-intermediate problems. I am curious if any similar result has been proved for $APX - PTAS$ with respect to approximation preserving reductions.

It is possible that the answer to this question is trivial - to be honest, the only $APX$-complete problem I know is MAX-3-SAT. However, I wonder how hard it is with respect to other problems in $APX - PTAS$.

# Answer
Yes, at least under some reasonable assumptions. Crescenzi, Kann, Silverstri & Trevisan show that Minimum Bin Packing, Mininum Degree Spanning Tree and Minimum Edge Coloring are APX-intermediate unless the polynomial hierarchy collapses.

Considering that the paper is from 1996, I'm sure there's now a significantly larger number of known APX-intermediate problems.
> 7 votes

---
Tags: complexity-theory, approximation, complexity-classes
---


title: Randomized Algorithms Probability

text:
# Question
Title: Randomized Algorithms Probability
I'm taking a grad level randomized algorithms course in the fall. The professor is known for being very detail oriented and mathematically rigorous, so I will be required to have an in-depth understanding of probability. What would be a good probability book to learn from that would be intuitive, but also have some mathematical rigor to it?

# Answer
What textbooks does the course recommend? I like "Probability and Computing" by Mitzenmacher and Upfal and "Randomized Algorithms" by Motwani and Raghavan. They introduce the necessary theory from an algorithms viewpoint. I also recommend a book on inequalities, as bounding things is quite essential to the analysis of randomized algorithms. At the very least this cheat sheet.
> 4 votes

# Answer
You don't actually need a mathematically rigorous text on probability theory. I doubt that the professor will use $\sigma$-algebras and the like (unless they will mention martingales and will prefer to discuss them using these terms; no one would be able to follow). What you probably need is an *understanding* of probability theory, which you can only get by "playing" with it, for example in a course like that. If you have no background at all, just take an introductory text and work through some of the exercises.
> 2 votes

---
Tags: probability-theory, randomized-algorithms
---


# Question
Title: Undecidability of whether a given TM halts or only has loops which can be detected by some TM
This might be a bit of an abstruse question, but it's something I've been trying to prove.

I'm trying to show that it is undecidable whether a given Turing Machine is a member of the set of all Turing Machines that either always halt, or have non-halting loops where all of which can be detected (a positive decision made on it's existence) by some Turing Mahcine.

I'm trying to do a reduction from the Entscheidungsproblem, and my proof looks something like this:

Create a Turing machine $D$ on input $\<M,w\>$ that does the following:

1. Mechanically create TM $M\_2$ which does the following on $x$:

1. if $M$ accepts $w$ (via simulation from UTM): accept $x$.
    2. if $M$ rejects $w$: loop in a manner such that $M\_2$ would not be a member of the aforementioned set.
2. Run decider for above problem on $M\_2$:

* if decider accepts, it should accept because if $M$ accepts $w$, $M\_2$ must always halt and must be a member of the set in question.
    * if decider rejects, it should reject because if $M$ does not accept $w$, $M\_2$ must have a non mechanically detectable loop and is not in the set.

The above Turing Machine $D$ should therefore decide Entscheidungsproblem and shows the reduction. However, I'm not sure how to show that it possible to mechanically create a loop which cannot be mechanically detected, or whether an alternate method of proof would be adequate.

Any insight in this proof would be appreciated.

# Answer
> 2 votes
(too long for a comment)

Here's my attempt at an unambiguous version of what you are trying to get across.

> Is it the case that for every total Turing machine M,
> if
> \[
> for all $\langle d,n\rangle$ in $\\{0,1,2,3,...\\}^2$, $\\:$ if M accepts $\langle d,n\rangle$ then
> $d$ describes a Turing machine that enters a loop on input $n$,
> \]
> then
> \[
> there is a many-one reduction from the Halting Problem
> to the set of $d$ in $\\{0,1,2,3,...\\}$ such that
> \[
> $\hspace{.01 in}d$ describes a total Turing machine or $\big\[\big\[$for all $n$ in $\\{0,1,2,3,...\\}$,
> if $d$ enters a loop on input $n$ then M accepts $\langle d,n\rangle\big\]$ and there exists such an $n\big\]$
> \]
> ?

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


# Question
Title: Why do the sequent calculus NOT left and NOT right rules work?
The rules I am considering are $\frac{\neg A, \ \Gamma \implies \Delta}{\Gamma \implies \Delta, \ A} (\neg L)$ and $\frac{\Gamma \implies \Delta, \ \neg A}{A, \ \Gamma \implies \Delta} (\neg R)$

I am trying to get my head around some of the sequent calculus rules, and while I think I understand most of them, I am struggling to apply any intuition to the negation rules shown above.

The intuition of looking at the left as a conjunction of literals and the right as a disjunction of literals seems to break down, and I am unclear how to explain these rules to myself.

What is a sensible way to view such rules and put some understanding on them?

# Answer
> 6 votes
You could start by considering simplified versions of the rules and build intuition by considering those cases. For instance,

$$\frac{\neg A, \ B \implies C}{B \implies C, \ A} (\neg L)$$

can be interpreted as stating that $(\neg A\wedge B)\Rightarrow C$ implies $B\Rightarrow (C\vee A)$.

So if it is the case that $\neg A$ and $B$ are true implies $C$ is true, *then* if only $B$ is true, either $C$ is true (independently of $\neg A$) or $A$ is true, for otherwise $\neg A$ would be true, which combined with $B$ being true would make $C$ true.

A similar game can be played with the other case.

# Answer
> 5 votes
Applying your intuition, the premise of $(\neg L)$ is: under the hypotheses $\Gamma$, and assuming $A$ is wrong, then one of the conclusions $\Delta$ holds. So if I only know $\Gamma$, what can I conclude?

* Possibly $\Delta$ holds.
* If $\Delta$ doesn't hold, it can only be that the assumption that $A$ is wrong is not met. In other words, $\neg (\neg A)$ is true, which means that $A$ is true.

All in all, from the premise of $(\neg L)$, we get that $\Gamma$ entails $\Delta$ or $A$. That's the conclusion of $(\neg L).

Similarly, with $(\neg R)$: under the hypotheses $\Gamma$, either one of the conslusions $\Delta$ holds, or $\neg A$ holds. Now suppose that in addition to $\Gamma$ we know that $A$ is true. Then among the conclusions $\Delta, \neg A$, the item $\neg A$ cannot be true, because you can't have both $A$ and $\neg A$ (excluded middle). So it must be one (or more) conclusions in $\Delta$ that holds. All in all, $\Gamma$ and $A$ together entail $\Delta$, which is the conclusion of $(\neg R)$.

You'll note that $(\neg L)$ relies on the excluded middle. This rule does not hold in intuitionistic logic, where just because $\neg A$ leads to a contradiction doesn't mean you can prove $A$. $(\neg R)$ works in intuitionistic logic but might not in a fuzzy logic.

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


# Question
Title: Principles of Distributed Computing - "processors" and "states"
So I'm learning about distributed computing, and I do understand a lot of the prerequisite material on algorithms and automata and whatnot... but I'm curious about the definitions I'm seeing as I read my textbook.

> A system consists of $n$ processors $p\_{0},\dots,p\_{n-1}$, where $i$ is the index of the processor $p\_i$. Each processor is modeled with a (possibly infinite) state machine with state set $Q\_i$. The processor is identified with a particular node in the topology graph. The edges incident on $p\_i$ are labeled arbitrarily with the numbers $1$ thru $r$, where $r$ is the degree of the $p\_i$. **Each state of the processor $p\_i$ contains $2r$ special components: $inbuf\_i\[\mathcal{l}\]$ and $outbuf\_i\[\mathcal{l}\]$.**

Does this mean that each state of an n-state state machine has a separate inbuffer and outbuffer? Based on the wording of this, it seems to imply that there are n of each buffer, which would say to me that an outbuffer is mapped directly to the inbuffer of another state in another processor.

# Answer
> Based on the wording of this, it seems to imply that there are n of each buffer

Assuming that each edge in the network graph $G=(V,E)$ corresponds to a bidirectional channel, there are $4|E|$ many buffers in total: For an (undirected) edge $(p\_i,p\_j)$, we have one pair of in/out buffers for $p\_i$ and one pair for $p\_j$.

> Each state of the processor $p\_i$ contains $2r$ special components: $inbuf\_i\[l\]$ and $outbuf\_i\[l\]$.

Let's look at an example to get an intuition for what the above means: Suppose that we have some network where $p\_3$ is connected to $p\_1$ and $p\_2$. Let's assume that process $p\_3$ sends a message $m$ to process $p\_1$ and has received (but not yet processed) a message $m'$ from process $p\_2$. Moreover, $p\_3$ has a local variable $counter$. Then we could represent the current state $\sigma\_3$ of $p\_3$ as $$\sigma\_3 = (inbuf\_3\[1\],inbuf\_3\[2\],outbuf\_3\[1\],outbuf\_3\[2\],counter).$$ According to the above example, $m' \in inbuf\_3\[2\]$ and $m \in outbuf\_3\[1\]$. Note that the state of the network is given by $(\sigma\_0,\dots,\sigma\_n-1)$.
> 6 votes

---
Tags: distributed-systems
---


# Question
Title: DFA: Can the set of States Q be empty by definition?
Can the set of states Q be empty by definition?

I was wondering about this question when doing exercises in the pumping lemma for finite automaton.

# Answer
> 6 votes
In a DFA - no, because the definition includes a *single* initial state $q\_0$, which means that $q\_0\in Q$, and therefore $Q\neq \emptyset$.

In an NFA, however, this is indeed possible.

---
Tags: terminology, automata, finite-automata
---


# Question
Title: Load balancing. Why not use priority queues?
I have recently learned about various randomized algorithms for load balancing. The model is always that there are $m$ balls and $n$ bins and the balls arrive one at a time. The task is to minimize the maximum load of any bin. However there is something I don't understand.

Why not just keep a priority queue of the loads of the bins and allocate any new ball to the bin with the lowest current load? This seems to give you the optimal load without any complications.

# Answer
> 2 votes
You are correct that using a priority queue is a good idea. It doesn't give an optimal answer though. (Assuming that what you are trying to optimize is the time that the last processor finishes executing the last job.) This scheduling problem is NP-complete, and the priority queue based method gives an answer that is within a factor of 2 of optimal. See, for example, http://www.cs.princeton.edu/courses/archive/spr05/cos423/lectures/11approx-alg.pdf. The wikipedia page on Job Shop Scheduling also gives some information.

---
Tags: priority-queues, online-algorithms, balls-and-bins
---


# Question
Title: Intuitive way to understand the triangle spectrum?
Image on the top is in the time domain, image on the bottom is in the frequency domain.

Why do we see -2T and 2T on image of the time domain and why do we see -1/2T and 1/2T of the image in the frequency domain?

# Answer
Suppose there is a sound with frequency 440Hz. How large is each period of this periodic signal? It must be (1/440)s. The same applies in your case.
> 2 votes

---
Tags: fourier-transform
---


# Question
Title: If A many-one reduces to B, does the complement of A many-one reduce to the complement of B?
If A many-one reduces to B, does the complement of A many-one reduce to the complement of B? My gut says no but I am having a hard time finding a counterexample.

# Answer
Let's try an example. Here is a reduction from the set of even numbers to the set of squares: $x \mapsto 2^x$ (check it!). It is also a reduction from the set of odd numbers to the set of non-squares. Is that just by chance?

We can make the following twist: the mapping $x \mapsto 2^{x+1}$ maps the set of even numbers to the set of non-squares. Is it always the case that we can modify a reduction from $A$ to $B$ to a reduction from $A$ to $\overline{B}$?
> 1 votes

---
Tags: complexity-theory, formal-languages, reductions
---


# Question
Title: Modeling the problem of finding all stable sets of an argumentation framework as SAT
As a continuation of my previous question i will try to explain my problem and how i am trying to convert my algorithm to a problem that can be expressed in a CNF form.

Problem: Find all stable sets of an argumentation framework according to Dung's proposed framework.

Brief theory: Having an argumentation framework AF, with A the set of all arguments and R the set of the relations, a stable set is a set which attacks all arguments not in their set and there is no attack relation between arguments in the stable set. Example:

Let's say we have an argumentation framework AF ,A={1,2,3,4}(arguments of AF) and attack relations R{1,3} and R{2,4}. It's obvious that the set {1,2} is a stable extension of the framework because:

a)it attacks all arguments not in their set (3 and 4)

b)it's conflict free(no attacks between arguments in the set) because argument 1 does not attack argument 2 and the opposite

My exhaustive abstract algorithm:

```
argnum=number of arguments;

Ai[argnum-1]=relation "attacks" ,where 1<=i<=argnum

P[2^argnum-1]=all possible relations that can be generated from all the arguments

S[2^argnum-1]=empty; where S are all the stable sets

j=0; //counter for while
k=1; //counter for counting stable sets
while j<2^argnum-1
    if P[j] attacks all arguments not in P[j](check using Ai[])
        if all arguments in P[j] are conlfict-free
            S[k++]=P[j];
        end if
    end if
    j++;
end while

```

I want to solve the above problem either by transforming the above algorithm to CNF or by using a different algorithm and finally use a SAT Solver(or anything similar if exists) give CNF as input and get stable sets as output.

I wonder if someone can give me any feedback of how i can transform any algorithm like the above to CNF in order to be used into a SAT Solver.

I decided to use precosat.

# Answer
> 6 votes
Finding a stable argument set is equivalent to finding an independent set in the directed graph of argument attacks, with the added restriction that some member of the set must be adjacent to each vertex in the graph *not* in the independent set. The problem is at least as hard as the indepependent set decision problem and is thus NP-hard. The decision version of the stable argument set problem is reducible to Boolean SAT as follows:

**Input:** Given a set of $n$ arguments $ARG\_{1}$ to $ARG\_{n}$, let the SAT propositional variable $ATTACK\_{i,j}$ be true if $ARG\_{i}$ attacks $ARG\_{j}$.

**Output:** Let $INDSET\_{1} ... INDSET\_{n}$ be a new set of propositional variables. $INDSET\_{i}$ will be true in the SAT solution iff $ARG\_{i}$ is part of the stable set found.

**Generating the clauses:**

1. For every pair of variables $INDSET\_{i}$, $INDSET\_{j}$, add clauses that require

$\overline{(INDSET\_{i} \land INDSET\_{j})} \lor (\overline{ATTACK\_{i,j}} \land \overline{ATTACK\_{j,i}})$.

These clauses prohibit any stable set argument from attacking another.
2. Let $NEEDATTACK\_{1} ... NEEDATTACK\_{n}$ be a new set of propositional variables. For each $INDSET\_{i}$ variable, add clauses that require

$INDSET\_{i} \oplus NEEDATTACK\_{i}$

These clauses record which arguments must be attacked by the stable set arguments.
3. Let $GOTATTACK\_{1} ... GOTATTACK\_{n}$ be a new set of propositional variables. For each $GOTATTACK\_{j}$ variable, add clauses that require

$GOTATTACK\_{j} = (INDSET\_{1} \land ATTACK\_{1,j})$ $\lor$ ... $\lor$ $(INDSET\_{n} \land ATTACK\_{n,j})$

These clauses record which arguments have been attacked by the stable set arguments.
4. For each $GOTATTACK\_{i}$ variable, add clauses that require

$NEEDATTACK\_{i} \oplus \overline{GOTATTACK\_{i}}$

These clauses require that every argument that needed to be attacked by some stable set argument was in fact attacked.

The Boolean expressions can be converted to circuits and from there to CNF using Tseitin transformations.

To obtain all the stable sets, when the SAT solver returns a set of $INDSET$ variables, you must construct a CNF clauses that forbids that solution and append it to the CNF formula. Rerun the solver and it will either find a new solution or report that the formula is now unsatisfiable. If "unsatisfiable" is reported, then you know you've found all the stable sets. If a new solution is found, construct another CNF clause to forbid that solution, append it to the formula and run the solver again.

# Answer
> 4 votes
The SAT solvers I have used are designed to find one solution. There are also SAT solvers that exhaustively eliminate all possible solutions, intended for random SAT benchmark instances. These solvers are optimized to discard information during search, instead focusing on finding one (or the presence of one) solution. Optimizing for enumerating all solutions requires a different approach, maintaining a memory-efficient data structure containing all the information found during search. If your approach requires finding all different solutions or optimizing over them, then more general tools may be needed. (Although sometimes it is perfectly reasonable to re-run the solver from scratch for a large number of different instances where each forbids the solutions found previously; if the runtime is low enough then it does not matter that the runs do not share data.) For a good list of state-of-the-art SAT solvers, many freely available, see the results of the SAT Challenge 2012.

I cannot prescribe a particular solver since I do not have a good handle on your problem domain. Personally, I would try to express a small but nontrivial instance of your problem as a constraint satisfaction problem using the MiniZinc language or using the Minion input format, as a sequence of SAT instances, as a Z3 SMT instance, and as as an input to clasp. By doing so, you will likely find aspects of some of these tools have limitations that make them more or less suitable for your task. I would initially do this quickly, to quickly explore the space of tools, then focus more time on the one or two most promising tools.

(The ordering above reflects my personal familiarity with the toolsets, not any particular recommendation. Note that clasp tends to perform well at the SAT Challenge.)

However, expressing real problems in these generic modelling paradigms is often challenging. There is even an annual workshop that deals with the general problem of modelling and model reformulation. Application papers describing how to use SAT/CP/SMT/ASP approaches to solve specific new problems are definitely welcome at the main conferences in these areas.

---
Tags: algorithms, complexity-theory, time-complexity, np-complete, satisfiability
---


title: Bounding rectangle of a line

text:
# Question
Title: Bounding rectangle of a line
\[Input\]: the begin and end points of an arbitrary line (small red points) and the line width (green line)
\[Example\]: begin=(20,20), end=(100,50), width=5

\[Output\]: The set of pixels (not the total area) that are in the yellow rectangle
\[Example\]: {(20,20), (20,21), (20,22),...etc.}

How can i calculate the output set?

# Answer
An algorithm to know if a point $P$ is in the rectangle $ABCD$ is to check that

* $\vec{AB}\cdot \vec{AP}\leq 0$,
* $\vec{DC}\cdot \vec{DP}\geq 0$,
* $\vec{DA}\cdot \vec{DP}\leq 0$, and
* $\vec{CB}\cdot \vec{CP}\geq 0$.

Since you have the two extremity point and the width $A,B,C$ and $D$ should be easy to compute. And you can restrict the point you are checking to $(x,y)$ such that $min(A\_x,B\_x,C\_x,D\_x)\leq x \leq max(A\_x,B\_x,C\_x,D\_x)$ and $min(A\_y,B\_y,C\_y,D\_y)\leq y \leq max(A\_y,B\_y,C\_y,D\_y)$.

It may not be optimal but it should be working.

Ps: I agree with @Dukeling.

**\[Edit\]** to compute $A$

If begin and end have the same abscissa (or ordinate) then it easy. Otherwise:

Let $begin=(b\_x,b\_y)$, $end=(e\_x,e\_y)$, $A=(x,y)$ and $width/2=w$ you know that: $$\vec{beginend}=((e\_x-b\_x),(e\_y-b\_y))$$ $$\vec{beginA}=((x-b\_x),(y-b\_y))$$ hence: $$\vec{beginend}\cdot\vec{beginA}=(e\_x-b\_x)(x-b\_x)+(e\_y-b\_y)(y-b\_y)=0$$ hence: $$ x = b\_x -\frac{(e\_y-b\_y)(y-b\_y)}{(e\_x-b\_x)} $$ Also $|\vec{beginA}|=w$ hence: $$(x-b\_x)^2+(y-b\_y)^2=w$$ hence: $$(b\_x -\frac{(e\_y-b\_y)(y-b\_y)}{(e\_x-b\_x)}-b\_x)^2+(y-b\_y)^2=w$$ Solve this equation and you have $y$, then replace the solution in $$ x = b\_x -\frac{(e\_y-b\_y)(y-b\_y)}{(e\_x-b\_x)} $$ and you have $x$.

Notice that you have two solution one for $A$ the other for $D$ ...

Do the same for $B$ and $C$ with appropriate vectors.
> 1 votes

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


# Question
Title: Is there a program to solve a metric TSP for 80 edges at optimum?
i'm going to use the Christofides heuristic algorithm in order to solve a TSP for about 80 edges. Eventually i should have a solution, that is within the factor 1.5 of the optimum.

But when i'm finished, i'd like to check my solution but i don't know how. So i thought about using a computer-program to find the optimal solution to see, if my solution is within the 3/2-range.

i am not quite sure, if this is really possible or how long it might take. if it would take less than a month, i think, it would be worth a try.

# Answer
It should be no problem to solve this instance with an integer linear programming based approach. You could try the online interface to the Concorde TSP solver.
> 2 votes

---
Tags: complexity-theory, graphs
---


title: Compare speed of two algorithms?

text:
# Question
Title: Compare speed of two algorithms?
$$T(n) = 2T(n/2) + \Theta(n), n \> 1$$ $$T(n) = \Theta (1), n \le 1$$

$$G(n) = G(\lfloor n/2 \rfloor) + G (\lceil n/2 \rceil) + \Theta(n), n \> 1$$ $$G(n) = \Theta (1), n \le 1$$

Prove $T(n)$ and $G(n)$ have the same asymtotic running time.

I tried using the sandwich theorem but got nowhere. Please be really explicit and show all your steps in your answer. Thank you.

# Answer
Hint: Start by replacing $\Theta(n)$ with $n$ and $\Theta(1)$ by $1$. Prove by induction that $$G(2^{\lfloor \log\_2 n \rfloor}) \leq G(n) \leq G(2^{\lceil \log\_2 n \rceil}).$$ Prove that $G(2^n) = F(2^n)$, and solve the recurrence for $F$. Conclude that $G(n) = \Theta(F(n))$.

If you want to be completely formal, you'll have to address the $\Theta(n)$ and $\Theta(1)$ summands. The idea is to replace $\cdots = \cdots + \Theta(n)$ with $\cdots \geq \cdots + cn$ and $\cdots \leq \cdots + Cn$, and then compute lower and upper bounds on $G$.
> 4 votes

# Answer
To prove that both recurrences have the same asymptotic growth, solve both. These are very classical examples of recurrences, for example showing up in the analysis of mergesort. You could use the Master Theorem, but it is even easier to have a look at the recursion trees. For both recurrences you have almost the same situation: There are $n$ "elements" for every level of the tree, and we have $\Theta(\log n)$ levels. Such every level contributes $c\cdot n$, where $c$ is the constant of the $\Theta(n)$, which gives in both cases a growth rate of $\Theta(n \log n)$.
> 4 votes

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


# Question
Title: Proving that if coNP $\neq$ NP then P $\neq$ NP
I am new in complexity theory and this question is a part of a homework that I have and I am stuck on it.

> Let ${\sf coNP}$ be the class of languages $\\{\overline{L}: L \in {\sf NP} \\}$.
>
> Show that if ${\sf NP} \neq {\sf coNP}$, then ${\sf P}\neq {\sf NP}$.

# Answer
It is maybe easier to consider the contrapositive, that is ${\sf P}={\sf NP} \Rightarrow {\sf NP}={\sf coNP}$.

So assume ${\sf P}={\sf NP}$, then

1. for every $L\in {\sf NP}$, we have $L\in {\sf P}$, and since the languages in ${\sf P}$ are closed under complement, $\bar L\in {\sf P}$ and therefore $L\in {\sf coNP}$.
2. for every $L\in {\sf coNP}$, we have $\bar L\in {\sf P}$, and since the languages in ${\sf P}$ are closed under complement, $ L\in {\sf P}$ and therefore $ L\in {\sf NP}$.

**Remark:** Note that if ${\sf P}={\sf NP}$ the polynomial time hierarchy collapses to the lowest level, which implies that ${\sf P}={\sf NP}={\sf coNP}={\sf PH}$.
> 20 votes

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


# Question
Title: Correctness-Proof of a greedy-algorithm for minimum vertex cover of a tree
There is a greedy algorithm for finding minimum vertex cover of a tree which uses DFS traversal.

1. For each leaf of the tree, select its parent (i.e. its parent is in minimum vertex cover).
2. For each internal node:
if any of its children is not selected, then select this node.

How do I prove that this greedy strategy gives an optimal answer? That there is no vertex cover smaller in size than the one that the above algorithm produces?

# Answer
> 11 votes
We first observe the following: There is an optimal cover $C$, and no leaf is in $C$. This is true since in any optimal cover $X$ you can replace all leaves in $X$ with their parents, and you get a vertex cover which is not larger than $X$.

Now take any optimal cover $C$ that does not contain leaves. Since no leave is selected, all parents of the leaves have to be in $C$. In other words, $C$ coincides with the greedy cover on the leaves and their parents. Next, we take out all edges that have been covered already. We can now apply the same argument again: In the remaining tree, no leaf needs to be selected, but then their parents have to be selected. And this is exactly what the greedy algorithm does. (A vertex becomes a leaf iff all of its children are selected in the previous step.) We repeat this argument we determined a complete vertex cover.

# Answer
> 5 votes
Hint: Construct a matching of the same size as your vertex cover by matching each vertex in the cover with an unselected child. Prove that $|M| \leq |C|$ for any matching $M$ and any vertex cover $C$. Conclude that the vertex cover is minimum and the matching is maximum.

---
Tags: algorithms, trees, greedy-algorithms
---


# Question
Title: Showing filling a container with rectangles is hard by reducing from SUBSET-SUM
Given a set of rectangles, $D = \\{ (a\_1, b\_1), (a\_2, b\_2) \dots , (a\_n, b\_n) \\}$, where in each pair $(a\_i, b\_i)$, $a\_i$ represents the height of the rectangle and $b\_i$ the width, and given another pair $(w, h)$ representing the width and height of a container $C$, does exist a way that taking some of the squares in $D$, the **whole** container C is perfectly filled? Here, $a\_i, b\_i, w, h \in \mathbb N$.

I am trying to reduce it from Subset Sum, but can't find the way... Hope you guys can give me a hint over it!

# Answer
Hint: Follow frafl's advice and set $b\_i = h = 1$.
> 1 votes

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


# Question
Title: Finding the path of a negative weight cycle using Bellman-Ford
I wrote a program which implements Bellman-Ford, and identifies when negative weight cycles are present in a graph. However what I'm actually interested in, is given some starting vertex and a graph, which path do I actually trace to get to the original vertex having traveled a negative amount.

So to be clear say I have a graph with vertexes, a, b, c, and d and there is a negative cycle between a, b, and d, then when I check for negative weight cycles

```
// Step 1: initialize graph
   for each vertex v in vertices:
       if v is source then distance[v] := 0
       else distance[v] := infinity
       predecessor[v] := null

   // Step 2: relax edges repeatedly
   for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u

   // Step 3: check for negative-weight cycles
   for each edge (u, v) with weight w in edges:
       if distance[u] + w < distance[v]:
           "Graph contains a negative-weight cycle"

```

Instead of it just telling me that a negative cycle is there, I would like it to tell me, go from `a -> b -> d -> a`. After the relaxing step what do I have to change in my check for negative weight cycles to get it to output this information?

* Here is the best information I've been able to find, but I'm still having trouble making sense of it.
* Also this which suggests that I need to run breadth first search on the predecessor array to find the information, but I'm not exactly sure where to start (what do I queue first?)
* Here is a stack overflow question which shows how to find one of the nodes in the path.

# Answer
> 4 votes
Per Kleinberg–Tardos, you want to run Bellman–Ford for *n* iterations and find a cycle in the predecessor array.

To find a cycle in the predecessor array, start by coloring every node white. For each node *u* in an arbitrary order, set *v* := *u*, and, while *v* is white and has a predecessor, recolor *v* gray and set *v* := predecessor\[*v*\]. Upon exiting the loop, if *v* is gray, we found a cycle; loop through again to read it off. Otherwise, none of the gray nodes are involved in a cycle; loop through again to recolor them black.

---
Tags: algorithms, graphs, shortest-path
---


title: Randomized convex hull

text:
# Question
Title: Randomized convex hull
I've been recently studying Monte-Carlo and other randomized methods for a lot of applications, and one that popped into my mind was making an (approximate) convex hull by examining random points, and try to get them inside the convex hull. I would like to know if there are algorithms for convex hulls that can improve the $O(n \log n)$ bound of comparison based algorithms, and the $O(n\cdot h)$ bound for Jarvis march and related to $O(n)$, either by building an approximate convex hull in $O(n)$ (with or without some approximation criteria) or by building an exact convex hull in expected linear time.

# Answer
Two linear time approximation algorithms in the two-dimensional case are due to Bentely, Preparata and Faust and Stojmenović and Soisalon-Soininen.

A fast exact algorithm which works in expected linear time is due to Bentley, Clarkson and Levine. The paper is quite old, so maybe there are newer developments.
> 3 votes

---
Tags: algorithms, asymptotics, computational-geometry, randomized-algorithms
---


# Question
Title: Lower-bound complexities for finding common elements between two unsorted arrays
I'm facing some problems that deal with finding common elements between unsorted arrays and I'd like to know whether there are well-known lower-bounds for the *worst-case* and, eventually, what are these lower-bounds.

The problems are pretty simple:

> Given two unsorted arrays of distinct integers, $A$ and $B$, of size $m$ and $n$, determine *all* the common elements between the two arrays(the output must be sorted)

Which I believe has a lower-bound complexity of $\Omega((m+n)\log(\min(m,n)))$ (and $O(1)$ space complexity, if we exclude the input arrays), even though I cannot find any proof of this fact. \[I found an algorithm with this complexity, so I(hopefully) am not underestimating the complexity.\]

The other problem adds some restrictions(and hence I'd expect to be able to lower the complexity):

> Given two unsorted arrays of distinct integers, $A$ and $B$, of size $m$ and $n$; knowing that common elements between the arrays have the same relative order in both arrays and that for every couple of consecutive common elements, their distance is at most $k$(constant), determine all the common elements between the two arrays maintaining their relative order and using at most $O(k)$ memory in addition to the input arrays.

I've tried to think about this second problem but I cannot see how the restrictions change the complexities. What puzzles me is that I believe that finding a single couple of elements between two unsorted arrays is $\Theta((n+m)\log(\min(n,m)))$, and since this is a special instance of this second problem then the restrictions do not add anything to the problem itself.

Are my guesses correct, and if so where can I find proofs for these lower-bounds? Do the restrictions change anything at all or the solution for the first problem is the best we can achieve in both cases?

---

Probably my questions can be summarized by the following:

> Given two arrays of distinct integers $A$ and $B$ of size $m$ and $n$, what is the lower-bound complexity for finding *one* common element?

Because, once a common element is found, the second problem can be solved in linear time.

---

**Edit**

The algorithm(s) that I thought are pretty simple:

For problem 1: Build two heaps for $A$ and $B$(which takes linear time and can be done in-place), then compare the minimum of the heaps, if they match print it and remove both, otherwise remove the smallest one and continue until the heaps are empty(this clearly takes $O((m\log(m) + n\log(n)) = O(\max(m,n)\log(\max(m,n)))$).

An other solution is to sort one array in-place, scan the other array and use bisection search to find matches. If we sort the smallest array (with size $m$) then the complexity is $O(m\log(m) + n\log(m)) = O(\max(m,n)\log(\min(m,n)))$. This technique yields the values in the other in which their are found in the biggest array, and it can be used to solve the second problem.

But, as you can see, I'm not using the extra restrictions at all and both algorithms use $O(1)$ space instead of $O(k)$(yes, it's still constant but $O(k)$ should give a bit more freedom).

# Answer
For the first question, when $m = n$, you can get an easy $\Omega(n\log n)$ lower bound (in appropriate computation models) by taking $A = B$. More generally, following the method outlined here, it seems that (assuming $n \geq m$) you can get a lower bound of $\Omega(\log (m! \binom{n+1}{m})) = \Omega(n\log m)$ by considering the problem of Set Intersection. (In the proof of Theorem 4, fix the order of the $X$s, and vary the order of the $Y$s and their location.)

As for your algorithm, perhaps it modifies the input arrays? Perhaps this is not allowed in the intended computation model, in which the input is read-only, the work tape is read-write, and the output tape is write-only. (This is just a guess.) In any case, it will really help if you explained your algorithm.
> 4 votes

---
Tags: time-complexity, arrays, lower-bounds
---


# Question
Title: Proving that the largest number of leaves in an $n$-ary tree of height $k$ is $k^n$
How to prove that the largest number of leaves in an $n$-tree of height $k$ is $k^n$?

# Answer
The claim is that an $n$-ary tree of height $h \geq 0$ has at most $n^h$ leaf nodes. The base step $h=0$ is obviously true. Assume the claim is also true for $h=1,2,\ldots,k$, for some $k \geq 0$. In a tree of height $k+1$, we have a root and $n$ subtrees each of which contain at most $n^k$ leaves. Thus the maximum number of leaves is $n \cdot n^k = n^{k+1}$. This completes the proof.
> 2 votes

---
Tags: combinatorics, trees, discrete-mathematics
---


# Question
Title: Why do most books say that a 1 bit branch predictor mispredicts on the first loop iteration?
I am reading two books, *Computer organization and design* by *David A Patterson*, and *Digital Design and Computer Architecture* by *Harris and Harris*. These books claim that a 1 bit branch predictor mispredicts on the first and last iterations of every loop.
I don't understand why it mispredicts on the first iteration. I think that the first prediction result depends on the history of the CPU, so we don't know whether the predictor would predict correctly or not.
My question is whether I have to assume that the initial state of the 1 bit predictor is for the branch to be taken.

# Answer
> 6 votes
I believe the assumption is that the loop has been encountered previously (i.e., assuming a long-running program with the loop encountered multiple times and assuming no aliasing in the branch predictor), so the first iteration has the predictor set based on the last iteration of the previous encounter (i.e., not-taken) and, of course, the last iteration has the predictor set based on the previous iteration (i.e., taken). This results in two mispredictions.

In general, a one-bit branch predictor will have two mispredictions per instance of unusual branch direction; first for the unusual instance and second for the instance immediately after that unusual instance. By providing some form of hysteresis (as with a 2-bit predictor) or resistance to change (e.g., by randomly dropping misprediction information, possibly with probabilities determined by static branch prediction--so far as I know, a technique that is only theoretical), such unusual branch behavior is less likely to cause mispredictions for the usual behavior of a branch.

# Answer
> 0 votes
Hennessy and Patterson clearify this a little bit in an example in "Computer Architecture: A Quantitative Approach (3rd edition)". On page 197, they give an example on 1-bit branch predictors. Consider the following pseudo code:

```
for (int i = 0; i < 9; ++i) {
    do_sth();
}

after_loop();

```

This pseudo code results in 3 branches: the if statement in the beginning, a branch to form the loop and a branch to exit the loop. The following sequence of operations would be possible:

```
do_sth(); // will be mispredict
do_sth(); // will not be mispredicted
do_sth(); // -"-
do_sth(); // -"-
do_sth(); // -"-
do_sth(); // -"-
do_sth(); // -"-
do_sth(); // -"-
do_sth(); // -"-
after_loop(); // will be mispredicted

```

The question is: why will the first `do_sth_else()` be executed after a mispredict?

Hennessy and Patterson define a branch-prediction buffer as (emphasize mine)

> \[...\] a small memory indexed by the *lower portion of the address* of the branch instruction. The memory contains a bit that says wether the branch was recently taken or not.

If the lower part of the branch's address was not encountered before, it will be mispredicted. The address of the branch for the first execution of `do_sth_else()` was not encountered before (otherwise, the loop must have been executed before, which is not the case), hence it will be mispredicted.

I believe you are right that this omits the branch history of the CPU. But as the lower portion of the branch address is used, I believe it is very likely that a misprediction will happen. So my answer to your question is: No, you don't have to assume that the state is `taken`, but it is very likely. You could flush a lot of `NOP` operations to generate situations where this is not the case.

---
Tags: computer-architecture
---


title: Deletion in min/max heaps

text:
# Question
Title: Deletion in min/max heaps
I think I'm confused about deletion in heaps, and since I have an exam today, I'm looking for your help to correct me.

I will post photos since it will makes it a bit more clear.

Note(forget about deleting the root)

What I understand is that , heaps only deletes the root element or the top. So, I made 2 solutions and I'm kindly asking which solution is the correct one.

Q:the heapness will be violated, I will have to replace it by the rightmost element bottom down right? (32)

# Answer
A min-heap typically only supports a delete-min operation, not an arbitrary delete(x) operation. I would implement delete(x) as a composition of decrease-key(x, $-\infty$), and delete-min. Recall, that to implement decrease-key, you would bubble up the element to maintain the heap property (in this case all the way to the root). In a binary heap, to implement the delete-min operation, you replace the root by the last element on the last level, and then percolate that element down.

To summarize, to delete(x), bubble-up the element all the way to the root, then delete the element and put the last element in the heap at the root, then percolate down to restore the heap property.
> 5 votes

# Answer
There's no need to bubble-up the element all the way to the root. You can replace the item to be removed with the last element in the heap. If that new element is less than its parent, then bubble it up. If it's greater than its children, bubble it down.

I implemented this in my DevSource article, A Priority Queue Implementation in C#. Full source is available at http://www.mischel.com/pubs/priqueue.zip.

See my Stack Overflow answer about this at https://stackoverflow.com/a/8706363/56778
> 6 votes

---
Tags: data-structures, heaps
---


title: CNF: Recursion in CFG

text:
# Question
Title: CNF: Recursion in CFG
How can I deal with recursive terminals in CFG when converting it to CNF? For example,

S -\> MN

M -\> AM | A

N -\> BN | B

A -\> a

B -\> b

How can I reduce terminals M and N?

# Answer
> 3 votes
In your example the problem is in the so-called chain productions $M\to A$ and $N\to B$. Just look how these single nonterminals can finally be rewritten into terminals: $M \Rightarrow A \rightarrow a$. Remove the $M\to A$ chain production and replace it by $M\to a$.

In general, if we have any sequence of nonterminals $X\_1 \Rightarrow X\_2 \Rightarrow \dots X\_n \Rightarrow c$ add the production $X\_1\to c$. Then remove the chain productions of the grammar.

Recursion in general is not a problem. It is the essence of context-free grammars! The only requirement of Chomsky Normal Form is that productions are of the form $A \to BC$ and $A\to a$ with $A,B,C$ nonterminals (=variables) and $a$ terminal (letters).

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


# Question
Title: Design a Turing Machine Checking if Apples and Bananas are Even
I am having trouble with a past exam paper. I have to design a Turing Machine to do the following, but I don't really know where to start with this question. Any help would be very much appreciated.

---

Design a Turing Machine TM checking if the numbers of sold apples and bananas are even. Formally, given a string w over the alphabet {a,b}, TM should terminate with the following result string.

```
ab if the number of apples and bananas are even
a if the number of apples is even but bananas are odd
b if the number of apples is odd and bananas are even
ϵ if the number of apples and bananas are both odd

```

Thanks

# Answer
> 5 votes
I'm not going to give you a direct solution, but let's think about this problem together, shall we? We will focus on 4 states. Why four? Well, you have two variables, each with two possible states, so $2^2 = 4$. So, for right now let's call our states $1$, $2$, $3$ and $4$:

* $1$ is the state denoting an even number of apples and bananas. This is our **start** state.
* $2$ is the state denoting an odd number of apples and an even number of bananas.
* $3$ is the state denoting an even number of apples and an odd number of bananas.
* $4$ is the state denoting an odd number of apples and an odd number of bananas.

Now, let's see how we move between states. For the moment, let's ignore the possibility of $\varepsilon$ for the input.

**From state $1$ ($a$=even, $b$=even):**

* If we get an $a$, go to state $2$. Eat the apple and output nothing.
* If we get a $b$, go to state $3$. Eat the banana and output nothing.

**From state $2$ ($a$=odd, $b$=even):**

* If we get an $a$, we go to state $1$. Eat the apple and output nothing.
* If we get a $b$, we go to state $4$. Eat the banana and output nothing.

**From state $3$ ($a$=even, $b$=odd):**

* If we get an $a$, we go to state $4$. Eat the apple and output nothing.
* If we get a $b$, we go to state $1$. Eat the banana and output nothing.

**From state $4$ ($a$=odd, $b$=odd):**

* If we get an $a$, we go to state $3$. Eat the apple and output nothing.
* If we get a $b$, we go to state $2$. Eat the banana and output nothing.

At this point we are pretty full and sick of apples and bananas. So let's consider what happens when we run out of food. It should be clear that we are going to be in one of the four states above. So let's augment each of them with an additional rule each:

The rule is simple: when the input for any one of those states is $\varepsilon$, output the correct sequence of characters for that state and then go to a $halt$ state.

I hope this helps!

# Answer
> 0 votes
This is the answer to my question. I have used four states each with an arc to the halting state. https://i.stack.imgur.com/iAsdO.jpg

---
Tags: turing-machines
---


# Question
Title: Can we have a general function of any function this way?
Lets say we need a function to add two numbers and another function to multiply two numbers.

To take a trivial example, consider the function $F(a, b, c, d) = a \cdot (c+d) + b \cdot (c\cdot d)$ If $a=1$ and $b=0$, then $F$ adds $c$ and $d$. If $a=0$ and $b=1$, then $F$ multiplies $c$ and $d$.

So to evaluate both add and mult I can have only one function $F$ with variable inputs.

Can we have a general function that can evaluate any arbitrary function ? of course with an upper bound on the complexity ? If yes how do we prove in theory that such a general function is possible ? What is this called in theory ?

# Answer
> 1 votes
"Universal Boolean Function" is what i was looking for .

# Answer
> 5 votes
The function you are describing is known as a *universal Turing machine*. A universal Turing machine is given a Turing machine $T$ and an input $x$, and outputs $T(x)$ (if $T$ doesn't halt, the universal Turing machine also doesn't halt).

If you want your function to have restricted complexity, you can just stop the computation once it has gone on for too long, and output zero, say. For any Turing machine with the correct complexity, the restricted universal Turing machine will still be correct. A variant is to accept a *clocked* Turing machine, which provides its own bound on the running time (which you can choose to ignore at your discretion).

---
Tags: algorithms, terminology
---


title: Complexity of $Ax\geq 0$

text:
# Question
Title: Complexity of $Ax\geq 0$
May be it's a stupid question (sorry if it's the case).

What is the complexity the decision problem:

Input: $A\in\mathcal{M}\_{n,m}(\mathbb{Z})$

does there exists $x\in\mathbb{N}^n,x\>0$ such that $Ax\geq 0$?

Where $x\geq 0$ means for all $x\_i\geq 0$ and $x\>0$ means there exists $x\_j\>0$.

I know that integer linear programming is NP-complete but it's expressed has $Ax\leq b$ and I failed to reduce $Ax\leq b$ to $Ax\geq0$ ...

# Answer
Your problem is in polynomial time, as the following claim implies.

**Claim** Let $A$ be an $m\times n$ matrix with rational entries. There exists an integer $x \> 0$ such that $Ax \geq 0$ if and only if there exists a real $x \> 0$ such that $Ax \geq 0$.

**Proof** The forward implication is trivial. For the backward implication, suppose that there exists a real $x \> 0$ such that $Ax \geq 0$. In particular, the polytope $P = \\{ x \geq 0 : Ax \geq 0 \text{ and } \sum x = 1 \\}$ is non-empty. Pick some vertex $x$ of $P$. Since all entries of $A$ are rational, all coordinates of $x$ are also rational. Therefore for some integer $N\>0$, all entries of $Nx$ are integral. Furthermore $Nx \> 0$ and $A(Nx) = N(Ax) \geq 0$. $\square$

Given a matrix $A$, in order to determine whether there exists a real $x \> 0$ such that $Ax \geq 0$, check whether the polytope $P = \\{ x \geq 0 : Ax \geq 0 \text{ and } \sum x = 1 \\}$ is non-empty using linear programming. This can be done in polynomial time.
> 4 votes

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


# Question
Title: Is the universe problem for one-counter automata with restricted alphabet size undecidable?
Consider the following *universe problem*.

> **The universe problem.** Given a finite set $\Sigma$ for a class of languages, and an automaton accepting the language $L$, decide if $L=\Sigma^\*$.

In \[1\], it is stated and proved that the universe problem is undecidable for a particular class of one-counter automata. This result then follows for the class of all non-deterministic one-counter automata. I'm wondering if it is known whether this problem is still undecidable when we restrict the size of the input alphabet of the automaton.

I think that with alphabet size 1 the problem becomes decidable, but what about size 2? And if that turns out to be decidable what is the smallest value of $n \in \mathbb{N}$ such that the problem is undecidable.

I think it's probable that the answer to this question is known but I'm having trouble finding an answer. If it is already known then I would appreciate a reference.

---

\[1\] Ibarra, O. H. (1979). Restricted one-counter machines with undecidable universe problems. Mathematical systems theory, 13(1), 181-186

# Answer
> 3 votes
It must be undecidable for an alphabet with two symbols. It is possible to code any alphabet into two letters, e.g., map 16 symbols to the length 4 binary strings $aaaa, aaab, \dots, bbbb$. Then equality to $\Sigma^\*$ is equivalent to equality to all possible codes for strings. In the 16 letter example this means equality to all strings of a multiple of four letters. Clearly that is not universality. That is obtained by adding those binary strings that are not coding. That is a regular set and can be generated by a one counter automaton.

The same explanation, with $\LaTeX$ for those who appreciate it. Assume universality is undecidable for $\Sigma$. Let $h: \Sigma^\* \to \\{0,1\\}^\*$ be an injective morphism. Now $L = \Sigma^\*$ iff $h(L) = h(\Sigma^\*)$. This in turn is equivalent to $h(L) \cup R = \\{0,1\\}^\*$ where $R$ is the (fixed) regular language $\\{0,1\\}^\* - h(\Sigma^\*)$. Hence we cannot decide whether the binary one counter language $h(L) \cup R$ is universal. Note that language is one counter as the family is closed under morphisms and union (with regular languages).

As you state "I think that" I can also confirm the question is decidable for a one letter alphabet. It is decidable for push-down automata (hence context-free languages) as one letter CFL are (effectively) equivalent to regular languages.

---
Tags: formal-languages, reference-request, automata, undecidability, decision-problem
---


title: Longest path in grid like graph

text:
# Question
Title: Longest path in grid like graph
This was a question at SO, and I think it's very interesting, I thought about it, but I could not provide any efficient algorithm neither showing the NP-Hardness:

> Find the length of the longest non-decreasing sequence through adjacent, non-repeating cells (including diagonals). For example, in the following grid, one legal path (though not the longest) that could be traced is 0-\>3-\>7-\>9 and its length would be 4.
>
> 8 2 4
>
> 0 7 1
>
> 3 7 9
>
> The path can only connect adjacent locations (you could not connect 8 -\> 9). The longest possible sequence for this example would be of length 6 by tracing the path 0-\>2-\>4-\>7-\>7-\>9 or 1-\>2-\>4-\>7-\>7-\>8.

For first attempts and possible misinterpretations is not bad to see this answer at SO.

My question: above problem is in $P$?

# Answer
> 3 votes
If all numbers are distinct then you can find the longest path using straightforward dynamic programming. The general problem is probably NP-complete, since deciding whether a grid graph has a Hamilton path is NP-complete, as shown by Itai, Papadimitriou and Szwarcfiter. Grid graphs are finite induced subgraphs of the infinite rectangular grid, in which non-diagonal cells are not adjacent; however it seems reasonable to conjecture that Hamilton path is NP-complete also for finite subgraphs of the infinite rectangular grid with diagonals. Given that, it is likely that your problem is also NP-complete.

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


title: Complexity of a subset sum variant

text:
# Question
Title: Complexity of a subset sum variant
Is this variant of the subset sum problem easy/known?

> Given an integer $m$, and a set of positive integers $A = \\{x\_1, x\_2, ..., x\_n\\}$ such that every $x\_i$ has at most $k=2$ bits set to $1$ ($x\_i = 2^{b\_{i\_1}}+2^{b\_{i\_2}},\\;\\; b\_{i\_1},b\_{i\_2}\geq 0$); is there a subset $A' \subseteq A$ such that the sum of its elements is equal to $m$ ?

Is it in $\sf{P}$? Is it still $\sf{NP}$-complete?

And if every $x\_i$ has at most $k=3$ bits set to $1$? For $k=1$ the problem is trivial.

# Answer
It is still $\sf{NP}$-complete, even for $k=2$. Given an instance of subset sum, we can transform it in to this variant by splitting up the numbers and adding some extra bits.

First, the sum of all numbers in the problem will be less than $2^m$ for some value of $m$.

Now, let's take a number $n$ from the original problem which has $k$ bits set. We will split this number in to $k$ numbers with exactly 2 bits set such that the sum of those numbers is $n+2^{k+m}$. We can do this recursively, by finding $\lceil{k}\rceil$ numbers that sum up to the first $\lceil{k}\rceil$ bits plus $2^{k+m-1}$ and $\lfloor{k}\rfloor$ numbers that sum up to the last $\lfloor{k}\rfloor$ bits plus $2^{k+m-1}$.

In addition to that number we will also add the number $2^{k+m}$ to the problem. A solution must either contain this number or all of the $k$ numbers constructed previously. If the original target value was $t$ the new target value will be $t+2^{k+m}$.

If the original problem had more than one number, we can repeat this process taking $k+m+1$ for the new value of $m$.

There are only two ways the bit at position $k+m$ can be set: the answer can contain the number $2^{k+m}$ or all of the $k$ numbers that sum up to $n+2^{k+m}$. So we have reduced subset sum to your subset sum variant.

As an example, let's take ${\\{2,3,5\\}}$ with target value $7$. This problem could be encoded as the subset sum variant presented here by taking the following binary numbers:

2 gets mapped to $0100\ 1$ and $0000\ 1$. (Using the extra bit is not strictly necessary here.)

3 gets mapped to $1000\ 00\ 1, 0100\ 00\ 1$ and $0000\ 00\ 01$

5 gets mapped to $1000\ 00\ 000\ 1, 0010\ 00\ 000\ 1$ and $0000\ 00\ 000\ 01$.

The new target value would become $1110\ 10\ 010\ 01$.

If the original problem is represented with $n$ bits, then the transformed problem has at most $O(n^4)$ bits. The original problem will have at most $O(n)$ numbers each with at most $O(n)$ bits, so the sum of all of them is also O(n). The transformed problem will have $O(n^2)$ numbers (since each $n$-bit number is split in to $n+1$ $2$-bit numbers, with their length being at most $O(n^2)$ since we use $n$ additional bits for each number. So the total size of the transformed problem is $O(n^4)$ bits.
> 8 votes

# Answer
*This is information extracted from question by Vor.*

For $k \geq 3$ the problem remains NP-complete. I found a quick reduction from monotone X-SAT (see the schema of the reduction here).

The problem remains NP-complete even if $k = 2$, see Tom's answer for details. Here is a small representation of his reduction from SUBSET SUM:
> 0 votes

---
Tags: complexity-theory, reference-request, decision-problem
---


# Question
Title: Is a single symbol, not in a set, a language?
I was reading about Turing machines and realized I'm not sure about the difference between the following scenario. Given the alphabet $\Sigma = \\{a, b \\}$, we have the following assertions:

1. $a \in R $
2. $\\{a\\} \in R$

I think that assertion $1$ is incorrect because $a$ is just a symbol, not a language. On the other hand $\\{a\\}$ is the language which contains only the $a$ symbol. Given that information, we can prove that $\\{a\\} \in R$ by trivially building a TM. Here, $R$ denotes the set of recursive languages.

Is my reasoning wrong? Thanks in advance.

# Answer
By the standard definitions, a **language** is always a set of (finite-length) **words**. This means that "$a$" is not a language, but either a symbol or a word.

If $R$ denotes all the regular languages (or alternatively, all the recursive languages), then indeed $a \notin R$. On the other hand, $\\{a\\}$ is a language, which is also regular (and recursive).

To complete the standard definitions:

1. an *alphabet* is a finite set of symbols
2. a *word* is a finite-length string of symbols
3. a *language* is a set of words (and can be finite or infinite)

of course, there are many possible extensions to the above definitions, such as infinite-alphabet, infinite-length words, etc.
> 6 votes

# Answer
I guess this is not what you were looking for, but I'd like to answer this from the viewpoint of pure set theory:

1. Let $\Sigma$ be **any** finite set, we call its elements *symbols* and $\Sigma$ an *alphabet*.
2. A *word* over $\Sigma$ is a tuple of elements from $\Sigma$. Tuples can be defined using set theory in a lot of different ways (some of them can be found in WP:Tuples). Especially for the $1$-tuple, there are at least three definitions. Let $(a)$ be the tuple that contains only the set $a$. Then one can define e.g.
    * $(a):=a$,
    * $(a):=\\{\\{a\\},\\{\\{\\{\emptyset\\},a\\}\\}\\}=\\{(1,a)\\}$ (tuple as finite function) or
    * $(a):=\\{a,\\{\emptyset,a\\}\\}=(\emptyset,a)$ (nested ordered pairs).
3. A *language* over $\Sigma$ is a set of words, i.e. a set of tuples whose elements are in $\Sigma$.

If we assume that tuples (and thus words) are finite, then languages are always countable. Whether a symbol $a \in \Sigma$ is also a language (over $\Sigma$ or any other alphabet) now depends on your definition of tuples:

1. If $(a)=a$ then any finite set $S$ can be seen as a language over $S$, containing all words of length $1$. So if $a\in \Sigma$ is a finite set (remember all "objects" in set theory are sets), then it is a language.
2. If not only $a \in \Sigma$, but $a \subset \Sigma$ (e.g. WP:Peano arithmetic), then $a$ is even a language over $\Sigma$ if we define $(a):=a$ and similar cases are possible for the other definitions of tuples, if $\\{(a)\\} \in \Sigma$.

Conclusion: if you like to **ensure** that $a \in \Sigma$ is not a language, make your symbols uncountable, e.g. let $\Sigma=\\{\[i-1,i\]\mid i\in {1,\dots,k}\\}$, where $\[a,b\]$ means the closed real interval.
> 0 votes

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


# Question
Title: $\mathsf{2EXP} = \mathsf{EXP}^{\mathsf{EXP}}$?
It is clear that any language in $\mathsf{EXP}^{\mathsf{EXP}}$ can be computed in $\mathsf{2EXP} = \mathsf{DTime}(2^{2^{\mathsf{poly}(n)}})$.

My question is whether the converse is true: is $\mathsf{2EXP} \subseteq \mathsf{EXP}^{\mathsf{EXP}}$?

# Answer
> 8 votes
Consider the problem $$A^f = A\_{TM}^f = \\{\langle M,x,t \rangle \mid M\in DTM \text{ and } M(x) \text{ halts and accepts in } f(|t|) \text{ steps}\\}.$$

Now $L^{\exp}$ is complete for $\mathsf{EXP} = \mathsf{DTime}(\exp (n^{O(1)}))$ and $L^{\exp\exp}$ is complete for $\mathsf{2EXP} =\mathsf{DTime}(\exp\exp(n^{O(1)}))$.

We show that $L^{\exp \exp}$ is in $\mathsf{EXP}^\mathsf{EXP}$.

Given $\langle M,x,t \rangle$, we simply write $\langle M,x,1^{\exp(|t|)} \rangle$ on the query tape and ask it from $L^{\exp}$ and return its answer as output.

This algorithm is in $\mathsf{EXP}^\mathsf{EXP}$, therefore $\mathsf{2EXP} \subseteq \mathsf{EXP}^\mathsf{EXP}$.

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


# Question
Title: Is it possible that the union of two undecidable languages is decidable?
I'm trying to find two languages, $L\_1, L\_2 \in RE \setminus R$, such that $L\_1 \cup L\_2 \in R$.

I have already proved that if $L\_1\cap L\_2 \in R$ **and** $L\_1 \cup L\_2 \in R$, such $L\_1, L\_2$ don't exist (because otherwise we'll be able to construct a Turing Machine $M\_1$ which will decide $L\_1$, for instance).

However, I cannot prove that it's impossible in the case $L\_1\cap L\_2 \in RE \setminus R$, and I can't find such languages.

# Answer
Take $L\_1=\\{0\cdot x:x\in \Sigma^\*\\}\cup \\{1\cdot x: x\in A\_{TM}\\}$ and $L\_2=\\{1\cdot x:x\in \Sigma^\*\\}\cup \\{0\cdot x: x\in A\_{TM}\\}$. Clearly both languages are in $RE\setminus R$.

However, their union contains $\\{0\cdot x\\}\cup \\{1\cdot x\\}=\Sigma^\*\setminus\\{\epsilon\\}$, and therefore equals $\Sigma^\*\setminus \\{\epsilon\\}$, and is therefore decidable.
> 10 votes

---
Tags: formal-languages, turing-machines, undecidability
---