# Question
Title: "Implied atomic propositions" in propositional boolean formula
Suppose we have a propositional boolean formula F and let M be the set of all models of that formula.

I am wondering if there is an efficient way to find all atomic propositions that are implied by the formula. Informally, this means that they can only have one specific value in all models M.

Does this problem have a specific name in literature? What is the complexity?

**Examples:**

Formula "(A)": the predicate A is implied by the formula, it can only ever have the truth value true in any model of the formula.

Formula "(A or B)": no predicate is implied by the formula, there are models where A is false, there are models where A is true, there are models where B is false, there are models where B is true.

Formula "A and (B or C)": in all models of this formula, A has to be true.

# Answer
> 5 votes
Suppose we had a TM $M$ which, given $F$ and some atomic $A$ occurring in $F$ it can efficiently (PTIME) decide whether all models of $F$ make $A$ true, i.e. whether $F \models A$.

Then we can efficiently decide the validity of any formula $G$ as follows.

Take $A$ to be any atom not in $G$. Craft $F := \lnot (G \land (\top \lor A))$, and use $M$ to decide if $F \models A$.

We then have $$ (F \models A) \iff (F \models \bot) \iff \models \lnot F \iff \models G \land (\top \lor A) \iff \models G $$

The first $\iff$ is nontrival, but easy to prove by considering the models where $A$ holds, and the others where $\lnot A$ holds, and exploiting our choice of $A$. It is left as an exercise ;-)

So, we constructed a polynomial reduction of validity to this problem. Since validity is coNP hard, we deduce this problem is also coNP hard.

---
Tags: propositional-logic
---


# Question
Title: How to compare/cluster millions of strings?
I have around 1,000,000 of strings of variable length (from 200 to 50000) that can contain 5 characters (A, B, C, D, E).

What I actually want is to cluster them together if they are similar enough. By similar enough I mean they have an edit distance \< $t$. This $t$ should be dependent on the length of the strings being compared. So for example, if I'm comparing two 200-length strings, $t$ could be 20, while comparing two 1000-length strings $t$ could be $100$

I've been reading a lot of literature lately but can only seem to find approaches that are not actually viable for so many strings, and I'm not much into probabilistic approaches so maybe you can help me out there.

The problem is that comparing them in pairs to cluster them would already be very costly even if the comparison was performed in $O(1)$ time (which is obviously not the case).

I've been reading about using indexes such as BWT and mixing it with things like the pigeonhole principle (Given two strings $P$ and $T$, let $p\_1$, $p\_2$, ..., $p\_{k+1}$ be a partitioning of $P$ into $k+1$ non-overlapping non-empty substrings. If $P$ occurrs in $T$ with up to $k$ edits, then at least one of $p\_1$, $p\_2$, ..., $p\_{k+1}$ must match exactly) but as I said before, I think it is unfeasible because of the quantity of strings and their length.

Also, some algorithms perform comparison in $O(t \cdot min(m,n))$ where $t$ is the desired edit distance (they will be clustered together if edit distance \<= $t$) and $m$ and $n$ are the length of the strings. But this can also be a problem because with large strings, $t$ could also be large.

So, do you know about anything that could help me in my case? Also, algorithms that can be made parallel are very welcome, as I intend to run this in a very large cluster with 400+ cores. Is there any fast probabilistic algorithm that can reduce the amount of comparisons needed for example?

# Answer
> 3 votes
The length of each string is at least 200, and you only consider two strings similar if their edit distance is less than 20. So if $S,T$ are similar, then there must exist $U$ such that (1) $U$ is a substring of $S$, (2) $U$ is a substring of $T$, and (3) the length of $U$ is at least 10.

This suggests that one heuristic is to find all length-10 substrings and look for collisions. In other words, build a hashmap whose keys are substrings and values are the containing strings; for each string $S$, compute all length-10 substrings $U$, and add a mapping from key $U$ to string $S$ into a hashmap. This can be done in linear time; a rolling hash may improve efficiency.

Now iterate through the hashmap and find all pairs of strings $S,T$ that share a common length-10 substring. For each pair $S,T$, compute the edit distance and check whether the edit distance is \< 20. I suggest using the optimized edit distance computation with "early out": if the edit distance is $\ge 20$ you don't care what its actual value is. This computation can be done in $O(20 \cdot (n+m)) = O(n+m)$ time per pair, where $m,n$ are the lengths of $S,T$. Length 10 is large enough that probably won't be too many pairs $S,T$ that contain a common length-10 substring but whose edit distance is $\ge 20$, so you probably won't waste too much time computing the edit distance on pairs you aren't interested in.

There are other approaches, based on metric trees, BK trees, and other methods. See, e.g., Efficient map data structure supporting approximate lookup. You might also look into the computational biology literature, which deals with a similar problem when clustering DNA sequences. There the alphabet has 4 characters, rather than 5 characters, and strings can be much longer, but they also want to find similar pairs from a large database, and they have developed practical and efficient algorithms.

---
Tags: algorithms, reference-request, strings, clustering
---


# Question
Title: What is the space in big-O notation of the minimal DFA accepting the intersection of two finite languages where their minimal DFAs are given
Given two **minimal** deterministic finite automatons called A and B where A accepts the **finite** language L(A) and B accepts the **finite** language L(B) and the alphabet of both languages and automatons are Σ={0,1}.

This implies that |Σ|=2.

Because that both A and B are **minimal**, there is no possibility to remove any state and transition neither from A nor from B, so L(A) and L(B) are unchanged.

C is **minimal** deterministic finite automaton that accepts L(C), where L(C)=L(A)∩L(B)

This implies that L(C) is **finite** and their alphabet is Σ={0,1} as well.

Because that C is **minimal** if one of its states and transitions of C is removed then L(C)≠L(A)∩L(B) anymore.

Assume that |A| is the number of states of automaton A, |B| is the number of states of automaton B and |C| is the number of states of automaton C.

I already know that I can construct C as the product of A and B so L(C)=L(A)∩L(B), but then |C|=θ(|A|•|B|), but C is **not necessarily m̲i̲n̲i̲m̲a̲l̲**. The running time of the algorithm that constructs the product takes θ(|A|•|B|).

It is possible then to run Hopcroft's algorithm to minimize automaton C in running time of O(|C|•log(|C|)), so still L(C)=L(A)∩L(B) and after that |C|≤|A|•|B|.

Because that |C|=θ(|A|•|B|) **before** the minimization, then Hopcroft runs in:

O(|A|•|B|•log(|A|•|B|)).

So in total the running time to get the minimal automaton C, so L(C)=L(A)∩L(B) this way takes O(|A|•|B|•log(|A|•|B|)).

Let me know if there is more efficient, faster and better time complexity algorithm to achieve the same thing.

**But** my **real** question is what is the space of the minimal automaton C after all this?

I know that it is |C|=Ω(1) in the best case, when L(A)∩L(B)=∅, because minimal automaton that accepts the empty language, only needs one state, which is the starting state, not final and trap, i.e. the automaton remains in this state for each read character from the input tape.

In this case |QC|=1 ∧ |FC|=0 ∧ δC(q0C,0)=δC(q0C,1)=q0C

But of course that this case won't happen always, so I am asking what will be the largest space of automaton C in the **worst** case?

For sure |C|=O(|A|•|B|), but can it be any better?

I think that yes, i.e. |C|=O(|A|+|B|)

Because it is always true that |L(C)|≤|L(A)| ∧ |L(C)|≤|L(B)|, where |L(A)| is the cardinality of L(A) as a set of words/strings, |L(B)| is the cardinality of L(B) as a set of words/strings and |L(C)| is the cardinality of L(C) as a set of words/strings and |L(A)|, |L(B)| and |L(C)| are all **finite** natural numbers, because L(A), L(B) and L(C) are all **finite** sets of words/strings. So the cardinality of the language is the number of words/strings in that language as set of words/strings. So if |L(C)|≤|L(A)| ∧ |L(C)|≤|L(B)| then L(C) never has more words/strings than both L(A) and than L(B).

If L(C) is smaller language both than L(A) and L(B) and may have fewer/lesser words/strings, then the **minimal** automaton C doesn't need more states than the **minimal** automaton A and **minimal** automaton B, so I don't think that it is right that |C|=O(|A|•|B|) when A, B and C are minimal and L(C)=L(A)∩L(B), but what I said is **not** a **proof**.

I need a proof that this statement is correct or refutation that this statement is incorrect and wrong, but I don't know how to either prove it or refute it.

It should be noted that if minimal automaton C doesn't have more states than minimal automaton A and B then:

|C|≤|A| ∧ |C|≤|B| and thus |C|≤min(|A|,|B|).

Any help or directions?

**EDIT:** I have just found and discovered 1 hour ago that the length of each word in L(A) and L(B) are equal, i.e. ∀ w,x,y,z: w∈L(A) ∧ x∈L(A) ∧ y∈L(B) ∧ z∈L(B) then |w|=|x|=|y|=|z|, where |w| is the length of the word w, |x| is the length of the word x, |y| is the length of the word y and |z| is the length of the word z. Sorry that I didn't know this before.

I also want to know the relationship between |C| and (|A|,|B|) when |A|→∞ ∧ |B|→∞, i.e. both the number of states of automaton A and automaton B are going to infinity.

You don't have to delete anything, just edit your answers and insert html that shows that the claim remains true with the new assumption or it doesn't true with that assumption.

# Answer
> 3 votes
Here is a concrete version of D.W.'s idea. Let $n$ be even, and consider the language $$ C\_n = \\{ w^2 : w \in \\{0,1\\}^n \\}. $$ (Note that $C\_n$ is a *language* rather than an *automaton* as in the original post.)

The words in $\\{0,1\\}^n$ are all pairwise inequivalent, and so the DFA complexity of $C\_n$ (the number of states in a minimal DFA for $C\_n$), which we denote by $D(C\_n)$, is at least $2^n$.

In fact, the NFA complexity of $C\_n$ (the number of states in a minimal NFA for $C\_n$), which we denote by $N(C\_n)$, is also at least $2^n$. Indeed, consider any NFA for $C\_n$, and let $\sigma(w)$ be the set of states reachable from the initial state upon reading $w$. It is not hard to check that $\sigma(w) \neq \sigma(w')$ for $w \neq w' \in \\{0,1\\}^n$, implying the lower bound.

On the other hand, we can write $C\_n = A\_n \cap B\_n$, where $$ A\_n = \\{ x \in \\{0,1\\}^{2n} : \mathsf{EVEN}(x) = w^2 \\}, B\_n = \\{ x \in \\{0,1\\}^{2n} : \mathsf{ODD}(x) = w^2 \\}, $$ where EVEN and ODD extract the letters in even and odd positions, respectively. It is not hard to check that the DFA complexity of $A\_n$ is $O(2^{n/2})$. This shows that $$ N(C\_n) = \Omega(D(A\_n) \cdot D(B\_n)). $$ In particular, since $D(A\_n)$ is unbounded as a function of $n$, it follows that $$ D(C\_n) \notin O(D(A\_n) + D(B\_n)). $$ Indeed, given $n$, $D(C\_n) \geq 2^n$ whereas $D(A\_n) + D(B\_n) = O(2^{n/2})$.

The same calculation also refutes your conjecture $D(C\_n) \leq \min(D(A\_n),D(B\_n))$.

# Answer
> 2 votes
I don't have a complete answer, but I suspect the bound $|C| = O(|A| \times |B|)$ is tight -- I suspect we can construct a counterexample to your conjecture that $|C| = O(|A|+|B|)$, as follows.

If $x \in \\{0,1\\}^\*$ is a string, let $\text{odd}(x)$ denote the bits at odd-numbered positions, and $\text{even}(x)$ the bits at even-numbered positions. For instance, $\text{odd}(01010) = 000$ and $\text{even}(01010) = 11$.

Fix an integer $n\>0$. Let $S,T \subset \\{0,1\\}^n$ be two sets of $n$-bit strings. Define the languages

$$\begin{align\*} L(A) &= \\{x \in \\{0,1\\}^{2n} : \text{odd}(x) \in S\\}\\ L(B) &= \\{x \in \\{0,1\\}^{2n} : \text{even}(x) \in T\\} \end{align\*}$$

Then we have

$$L(A) \cap L(B) = \\{x \in \\{0,1\\}^{2n} : \text{odd}(x) \in S, \text{even}(x) \in T\\}.$$

If $S,T$ are "randomly chosen" subsets $\\{0,1\\}^n$, then on average we expect $A$ needs about $2^n$ states and $B$ needs about $2^n$ states, and it seems that the minimal DFA $C$ for $L(A) \cap L(C)$ will apparently need about $2^{2n}$ states. This is not a proof, but perhaps by choosing appropriate sets $S,T$ you can construct an explicit counterexample where $|C| \ge c \times |A| \times |B|$ for some constant $c\>0$.

# Answer
> 0 votes
The following solution is invalid. Step (3) is false. The minimal machine may not be a tree, though, as @YuvalFilmus notes, it is in general a DAG.

---

Furthermore, the supposed solution is a tree with all leaf nodes accepted. If they are all accepted and they all go nowhere, they are all equivalent (accepting $\epsilon$).

---

The key to this is that the languages $L(A)$ and $L(B)$ are finite.

1. Remove the (unique in a minimal DFA) rejection state, assuming that no transition implies rejection.
2. Then the minimal DFAs $A$ and $B$ have no cycles.
3. Furthermore, no state is equivalent to any state reachable from it, otherwise the language is not finite.

This implies that, given a binary alphabet,

* $A$ and $B$ are binary trees,
* rooted at the initial state,
* with (apart from the degenerate empty language) all leaf states accepted.

We can find a DFA $C$ that accepts $L(A) \cap L(B) $ by laying the two trees on top of one another, root to root, and collating them:

* A $C$ state is accepted only if both the corresponding $A$ and $B$ ones are.
* A $0$ or $1$ branch is developed in $C$ only if the corresponding branches exist in $A$ and in $B$.

The resulting DFA $C$ might not be minimal. The tree might have sterile branches that need pruning. For example, if all the words in $L(A)$ have even length, and all the words in $L(B)$ have odd length, none will coincide.

Thus the minimal DFA $C$ that accepts $L(A) \cap L(B) $ is no bigger than either, and can be discovered in similar time. $$|C| \le min (|A|, |B|) $$

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


# Question
Title: Unrecognizable languages relationship to NP-hard languages
I would like to know if there exists an NP-hard language which is also a member of co-RE\R? I think it depends if P=NP or not, but i'm not sure.

Can I simply assume NP-hard is in R?

Can you direct me how to think about it?

# Answer
> 3 votes
There are **NP**-hard languages arbitrarily high in the arithmetical hierarchy.

To answer your specific question, the complement of the halting problem is **NP**-hard and it's in $\mathrm{coRE}\setminus\mathrm{R}$. To see this, let $M$ be a Turing machine that tries all variable assignments for a $\mathrm{SAT}$ instance. Let it loop forever if it finds a satisfying assignment and let it halt if it doesn't, or if the input isn't a valid encoding of a $\mathrm{SAT}$ instance. Now, for any string $x$, $x\in\mathrm{SAT}$ iff $\langle M\rangle,x\in\overline{\mathrm{HALT}}$ so we have a reduction from $\mathrm{SAT}$ to the complement of the halting problem.

---
Tags: complexity-theory, computability, np-hard, semi-decidability
---


# Question
Title: Halting problem with Proof of The Immerman-Szelepcenyi Theorem (knowledge of the theorem might not be necessary to clear my doubt)
So, I was reading this pdf on complexity theory. On page 18 pf pdf (Page 12 of book) The Immerman-Szelepcsenyi Theorem is mentioned with proof. The following lines are from the book :

> The idea is to cycle through all possible configurations $\sigma$ of $M$, for each one checking whether it is a final configuration that is reachable from the initial configuration by a computation of $M$. In case no such accepting configuration is found we know $x\notin A$ so we let $\overline M$ accept $x$.

My question here that the machine $M$ may not halt for a string $x\notin A$. Then the logic of "cycle through all possible configurations" won't make any sense. What am I missing here?

On a side note is this book too high level for me? (I am graduate in Computer Science) Getting stuck at page 12 is not a good sign right?

# Answer
> 9 votes
As the proof (sketch) itself notes:

> Note that on a given input $x$ of length $n$ there are $2^{f(n)}$ possible configurations.

This means there is only a finite space of configurations **for a machine that operates in less than $f(n)$ amount of space!**

Intuitively, if you have an array `[0,1,0,...,]` of length $n$, then all possible combinations of configurations of that array is $2^n$, and so a machine which could only modify an array of bits of size at most $n$ will either halt in that time, or end up in a loop with exactly the same state as previously, and this is easy to decide.

If you allow arbitrary amounts of space then as you note, it is undecidable whether or not a state is reachable or not.

---

It's hard to say whether a given piece of work is "too high level" for someone or not. To paraphrase Euclid, there is no "royal road" to theoretical computer science, so you should expect to have at least some difficulty working through technical material.

As Paul Halmos suggests: "Don't just read it, fight it!". This suggests that difficulty in mathematical reading is rather widespread (I certainly experience it sharply as well).

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


title: Run time of a Simple Recurrence

text:
# Question
Title: Run time of a Simple Recurrence
Given the recurrence $T(n) = T(\sqrt{n}) + \theta(lglgn)$, provide an asymptotically tight bound on it's run time.

My solution was to let $m = 2\sqrt{n}$, which leads to the recurrence $S(m) = S(m/2) + \theta(lg(2lg(m) + lg4)) = S(m/2) + \theta(lglgm)$.

By case 3 of the master rule, this means that $S(m) \in \theta(lglgm)$, because $lglgm \in \Omega(m^{log\_2 1})$.

Since $lglgm = lg(lg2 + 0.5lgn) \in \theta(lglgn)$, we have that $T(n) \in \theta(lglgn).$

The provided solution to this problem says that $T(n) \in \theta((lglgn)^2)$, could someone help me find my mistake?

The solution is on page 2 of the below PDF, problem 1-2(d): https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/assignments/ps1sol.pdf

# Answer
> 4 votes
First let's see how we arrive at the solution. Let's try expanding it: $$\begin{align} T(n) & = T(n^{\frac{1}{2}}) + \Theta(\lg \lg n)\\ & = T(n^{\frac{1}{4}}) + \Theta(\lg \lg n^{\frac{1}{2}}) + \Theta( \lg \lg n)\\ & = T(n^{\frac{1}{4}}) + \Theta(\lg 2^{-1} \lg n) + \Theta( \lg \lg n)\\ & = T(n^{\frac{1}{4}}) + \Theta(\lg \lg n - 1) + \Theta( \lg \lg n)\\ & = T(n^{\frac{1}{4}}) + 2 \cdot \Theta( \lg \lg n)\\ & = T(n^{\frac{1}{8}}) + 3 \cdot \Theta( \lg \lg n)\\ & \vdots\\ \end{align}$$ At this point you should see every time we recur we do $\Theta(\lg \lg n)$ work. So if we recurse $k$ times then total time is $\Theta(k \lg \lg n)$. Now we just need to find this $k$.

$k$ will be equal to how many times we can take the square root before resolving to a base case. Let's assume our base case is $2$, and all $n$ are of the form: $$n = 2^{2^k}$$ We then can take the square root of $n$ exactly $k$ times before reaching $2$. This is because every time we take the square root of $2^{2^k}$, we cut the exponent in half, e.g. $\sqrt{2^{2^k}} = 2^{2^{k-1}}$. This clearly results in taking the square root $k$ times, or more formally $\log\_2 \log\_2 n$ times. Therefore we reach the conclusion that the total time is: $$ T(n) = \Theta((\lg \lg n)^2)$$

With that being said this issue seems to be with your domain transformation. Going from $T(n)$ to $S(m)$, you're essentially saying a function of the form $T(n) = T(\sqrt{n}) + \Theta(f)$ is equivalent to a function of the form $S(m) = S(\frac{m}{2}) + \Theta(f)$ because after the domain transformation you can kinda abuse $\Theta$ notation to remove a lot of non-arbitrary values.

For more on domain transformations to solve recurrences check the notes 5.2 here.

---
Tags: asymptotics, recurrence-relation, master-theorem
---


# Question
Title: Datastructure for managing (abstract) sets
I am looking for a datastructure to represent the complex relationships between a bunch of *abstract* sets. The "abstract" means that these sets are not defined by their elements, but by their relationship to each other. This means that for me a set is nothing more than a named thing with a relations to other named things in the same space. For two sets $A,B$ the relation can be

* they represent the same set, i.e. $A=B$,
* they are complementary, i.e. $\bar A=B$,
* they are disjoint $A\cap B=\varnothing$ but not complementary,
* they are overlapping, i.e. they are not equivalent but have a non-empty intersection,
* one is a *proper* subset of the other set, e.g. $A\subset B$
* essentially unknown, but maybe some of the former cases can be excluded.

Besides storing these relationships, I want to ask questions on the datastructure like

* Are the sets $A$ and $B$ disjoint?
* Name me a subset of $A\cap\bar B\cap \bar C$.
* What is the relation between the sets $X$ and $\bar Y\cap Z$?

Also the datastructure should be updatable. There will be inserted new sets all the time which must be integrated in the structure correctly. There can be *lots* of sets and it is no option to explicitely store the relation between any pair of sets. Instead, some relations should be *deducable* by the query algorithms. For example, if we have $A\subset B\subset C$, then we will not store $A\subset C$ as this follows logically from the other two relations.

I thought about lots of tree like structures or cycle-free directed graphs. But maybe someone already developed exactly what I am looking for.

---

One more thing: I would prefer when the datastructure does note introduce big differences between sets and their complement. This means, asking whether $A\cap B$ is empty should not invoke vastly different algorithms than asking this for $A\cap \bar B$.

---

**Update**

To answer some comments, here are some more details on my intend.

You can think about this as a big (hyper-)graph problem, where the whole graph is too big to be stored but has much structure, so maybe can be stored very efficiently in another way. The nodes of the graph are sets. The (hyper-)edges are relations between the sets. The edges are colored to represent the six possible relation types from above. In this sense, the graph is an edge-colored complete graph. Note that the edge type **unknown** is very important to me!

To describe the queries in general, let me introduce the following notation: given a set $A$, we write $A^+=A$ and $A^-=\bar A$. The following queries should be supported as efficient as possible:

1. Given a sequence of nodes $A\_i$ and a sequence of signs $s\_i\in\\{+,-\\}$. Which of the following three options is true for $\bigcap\_i A\_i^{s\_i}$: it is empty, there is a node representing a subset of this intersection, we do not know anything.
2. Given two sequences $A\_i$, $B\_i$ of nodes and two sequences $s\_i$ and $r\_i$ of signs. What kind of edge is between $\bigcap\_i A\_i^{s\_i}$ and $\bigcap\_i B\_i^{r\_i}$?

The last query seems trivial for the graph stored with all its edges. But as I said, the graph is probably too big to be stored in this naive way.

Of course, I never stated that for sets $A\_i$ and signs $s\_i$ my data structure must contain the set $\bigcap\_i A\_i^{s\_i}$, *but* information can be deduced in other ways. For example, assume $A$ and $B$ are sets, but $A\cap B$ is not stored. But we have a set $C\subset A,B$. So we know that $A\cap B$ $-$ despite being not stored explicitely $-$ is not empty. If we lack any of these information, then we may conclude that "we do not know anything about $A\cap B$". The fact that $A\cap B$ is empty is stored by an edge between $A$ and $B$ signalling that these sets are disjoint.

Why I wrote *hyper-edge* instead of just edge? It might be necessary to store that $A\cap B\cap C=\varnothing$ but no two of these sets are disjoint. This cannot be deduced from any two set relation. So we may need edges involving more than just two sets.

# Answer
One simple approach:
For each abstract set $A$ create a node. Let each node maintain a list of
1) complementary sets
2) disjoint sets
3) overlapping, i.e. they are not equivalent but have a non-empty intersection
4) proper subsets

For example, consider the following node

```
NODE: 123F65
----
|  |-> compls
|  |-> disjoints
|  |-> overlappings
|  |-> propers
----

```

Assume that you have created a set $A$. Allocate a new node for this set and let $A$ point to this node.

```
 HASH TABLE
 ______________
 |A| |-> 123F65
 ______________

```

Then assume you add a new set $B$ with a property $A=B$. You don't create a new node, just make $B$ point to the same location $A$ points to, 123F65.

```
 HASH TABLE
 ______________
 |A| |-> 123F65
 |B| |-> 123F65
 ______________

```

Then assume you add a new set $C$ which is a proper subset of $B$. Create a new node for $C$ and make $C$ point to that node. Additionally add $C$ to to the list of proper subsets of $B$ in 123F65.

```
NODE: 123F65
----
|  |-> compls
|  |-> disjoints
|  |-> overlappings
|  |-> [ C ]
----

NODE: 153F60
----
|  |-> compls
|  |-> disjoints
|  |-> overlappings
|  |-> propers
----

HASH TABLE
 ______________
 |A| |-> 123F65
 |B| |-> 123F65
 |C| |-> 153F60
 ______________

```

So for example, if I want to find out if $A$ and $B$ is disjoint, I would check if $A$ is a subset of any $B$'s complementary or if $B$ is a subset of any $A$'s complementary. If yes then the answer is "disjoint", otherwise they are not disjoint or insufficient information.

Note that this data structure is just a kick-off. You may have to change it as you will ask different questions or you want to speed up queries.
> 1 votes

# Answer
I suggest you maintain a knowledge base of constraints on sets and translate the knowledge base to a formula on boolean variables. The knowledge base will consist of constraints of the form $A=B$, $A=\overline{B}$, $A =B \cap C$, $A=\emptyset$, $A \ne \emptyset$.

Each of the operations you mentioned can be implemented by adding constraints of these form to your knowledge base. For instance, to require that $A$ is a proper subset of $B$, require that $A \cap \overline{B} \ne \emptyset$ and $\overline{A} \cap B = \emptyset$; this can be done by introducing new sets $C,D,E,F$ and constraining $C=\overline{B}$, $D = A \cap C$, $E = \overline{A}$, $F=E \cap B$, $D \ne \emptyset$, and $F = \emptyset$. And so on. This part is mechanical.

To answer queries about the knowledge base, we'll translate the knowledge base to a boolean formula. Introduce abstract elements $a\_1,\dots,a\_n$, where $n$ counts the number of abstract sets in the knowledge base. Also, introduce boolean variables $x\_{S,i}$ (one for each abstract set $S$ and each $i$ with $1 \le i \le n$). We'll generate a formula $\varphi$ that is a conjunction of constraints on the boolean variables . The intended meaning is that $x\_{S,i}$ is true if $a\_i \in S$, and that $x$ will satisfy $\varphi$ only if the corresponding sets are consistent with the knowledge base.

Here is how you translate the constraints in the knowledge base to boolean formulas:

* To constrain $A = B$, add the constraints $x\_{A,i}=x\_{B,i}$ for all $i$.
* To constrain $A = \overline{B}$, add the constraints $x\_{A,i}=\neg x\_{B,i}$ for all $i$.
* To constrain $A = B \cap C$, add the constraints $x\_{A,i}= x\_{B,i} \land x\_{C,i}$ for all $i$.
* To constrain that $A = \emptyset$, add the constraints $x\_{A,i}=\text{False}$ for all $i$.
* To constrain that $A \ne \emptyset$, add the constraint $x\_{A,1} \lor \cdots \lor x\_{A,n}$.

You can check whether the constraints are simultaneously satisfiable by checking whether the resulting formula $\varphi$ is satisfiable. This could be done using a SAT solver (using bit-blasting to convert these boolean constraints to CNF clauses).

You can answer the query "is $A$ empty?" (i.e., do the constraints imply that $A = \emptyset$?) by temporarily adding $A = \emptyset$ to the knowledge base, generating a new formula $\varphi'$, and testing whether $\varphi'$ is satisfiable using the SAT solver. If $\varphi'$ is satisfiable, then the answer to the query is "yes", otherwise the answer is "no".

You can translate the other kinds of queries you are interested in into this form by adding some additional constraints. For instance to answer the query "are $A,B$ disjoint?", you create a new set, add the constraint $C = A \cap B$, then answer the query "is $C$ empty?" (using the SAT solver). To respond to the query "name me a subset of $A$", create a new set $B$, add the constraint that $\overline{A} \cap B = \emptyset$, and return $B$ (no need to invoke the SAT solver).

To support a streaming sequence of queries, you could use a SAT solver that supports incremental solving (i.e., the ability to push and pop clauses onto a stack). See, e.g., https://stackoverflow.com/q/16422018/781723.

This might look pretty straightforward. The one technical trick is how I chose $n$, and in particular, that the number of abstract elements needed is upper-bounded by the number of $A \ne \emptyset$ constraints. I haven't tried to carefully prove that this is enough, but I think it suffices. I actually suspect it is possible to reduce $n$ further, specifically, to the number of $A \ne \emptyset$ constraints plus one. If true, this would improve efficiency -- but I haven't thought carefully about whether that's actually a valid optimization.

There are no guarantees that this scheme will be efficient. Your problem is at least as hard as SAT (i.e., NP-hard), so it follows that there will be some sequences of operations and queries that will very hard to answer in any reasonable amount of time. Given that your problem is at least as hard as SAT, my thinking is that translating to SAT and then using existing SAT solvers (and benefiting from all of the work that has gone into improving SAT solvers) might be your best hope for a solution that is often efficient in practice.
> 1 votes

---
Tags: algorithms, graphs, data-structures, sets
---


# Question
Title: Clarification of definition of class $DisNP$
I an trying to learn about $DisNP$ Complexity class. I couldn't find this class in any book. But, regarding it, I found this definition in a paper:

Definition: A disjoint NP-pair (NP-pair for short) is a pair of nonempty sets $A$ and $B$ such that $A, B \in NP$ and $A \cap B = Empty$. $DisNP$ denote the class of all disjoint NP-pairs.

Now I am aware that when a problem like $SAT$ etc. is said to be in $NP$, it means that assuming we have a NDTM we can get the solution in polynomial time. Or in other words, if we can guess the solution, then the verification takes polynomial time.

But, what does it mean when we say a set $A \in NP$ or a set $B \in P$.

Does the elements of the sets represent the solution for which the corresponding $SAT$ instance for each set is true i.e. set $A$ and $B$ contain the solutions of some $SAT$ instances $SAT\_A$ and $SAT\_B$ such that $SAT\_A$ is satisfiable iff its solution is in the set $A$?

I am not clear how we use sets (which I assume have binary strings) for defining $P, NP, NPC$?

# Answer
> 2 votes
A disjoint NP pair consists of two NP languages $A,B$ which are disjoint. For example, $A$ could consist of all graphs which are $k(n)$-colorable (where $n$ is the number of vertices and $k$ is an arbitrary function), and $B$ could consist of all graphs having a clique of size $k(n)+1$.

Disjoint pairs of NP languages are used in proof complexity. For example, the disjoint pair discussed above (for $k(n) = n^c$) is used to prove exponential lower bounds on the size of proofs in the cutting planes proof system. See for example these notes. (For the state-of-the-art regarding cutting planes, see the recent paper Random CNFs are Hard for Cutting Planes.)

---
Tags: complexity-theory
---


# Question
Title: Given regular grammars (each is either left or right linear), does exist word/string so it can be derived from all regular grammars?
Given regular grammars (each is either left or right linear), does exist word/string so it can be derived from all regular grammars, i.e. a word/string that can be derived from each regular grammar.

Suppose that S1, ... , Sn are regular grammars. Then is the following statement is true:

∃w: S1→w ∧ ... ∧ Sn→w ?

In other words:

∃w∀i: 1≤i≤n→(Si→w) ?

Does exist polynomial algorithm (both in time and space) that can find the answer to this question quickly?

**EDIT:** The language of each given regular grammar is **finite** and 'w' is a word of length m, where m is natural number given as input to the algorithm.

Also the alphabet of each regular grammar is Σ={0,1} and thus |Σ|=2.

In other words, does exist word of length m that can be derived from each regular grammar, where the language of each regular grammar is finite and alphabet of each regular grammar is {0,1}?

# Answer
Your problem is PSPACE-complete. Indeed, the easier problem of DFA intersection is already PSPACE-complete, see for example Descriptional and computational complexity of finite automata—A survey by Holzer and Kutrib. For comparable results from the point of view of exponential time algorithms, see Problems on Finite automata and the exponential time hypothesis by Fernau and Krebs.

It is well-known that regular grammars are essentially equivalent in power to NFAs (even considering description complexity), and for this reason your problem is essentially equivalent to the NFA intersection problem, in which you are given a collection of NFAs and have to decide whether the intersection of languages accepted by them is empty — this is the problem considered in the papers above.

The same problem for regular expressions is also PSPACE-complete, see for example Complexity of decision problems for simple regular expressions by Martens, Neven and Schwentick, which considers restricted cases of the problem.
> 2 votes

---
Tags: algorithms, complexity-theory, formal-languages, regular-languages, formal-grammars
---


# Question
Title: Use machine learning algorithms data structure to store information (memory)
> DISCLAIMER : I'm pretty new to machine learning field, so forgive me if my questions are somehow naive ... I already searched on Internet about this topic and find nothing interesting so I am asking here ....

I wonder if a ML algorithm can be consider as a way to store data ? There is programs that "contains" thousands of decimal of PI (e.g. https://www.quora.com/What-is-the-smallest-C-program-generating-pi-without-using-the-math-library) : in some way it's a "compressed" version of the first thousands decimal of PI, right ?

In the same way ML (e.g. Deep Neural Net) seems to store information. Can we mesure how many bits is stored in a Deep Neural Net ? Can we use ML algorithms data structure to compress information and retrieve it later (even if it's not 100% accurate) ? ...

Is there (not too technical ) papers that discuss these possibilities ?

Thanks :)

# Answer
> 2 votes
ML algorithms are definitely capable of storing information. Generally, any ML algorithm can be trained to remember a set of data. This is commonly referred to as overfitting and something that most ML researchers try very hard to avoid.

Also feature learning and compression are common themes in ML. In this case, the goals are actually to find efficient ways to represent the data. This allows to store information efficiently. Because you asked for some illustrative papers: image compression with autoencoders, image compression with PCA, ...

Methods like generative models are probably also interesting as their purpose is to discover the distribution of some data in order to generate new data. This technique can be used to generate new images that are not just random noise for example.

These are just some examples with some random papers that are top hits when searching for the terms I mentioned. Probably every machine learning algorithm can be said to store some sort of information, but for some models the stored information is more useful/meaningful than for other models.

Generating pi with machine learning has probably not been done (at least it has not been published). However, nothing keeps you from trying it out. You could try to overfit a model to learn digits of pi or you could just try what happens when you feed an LSTM with a very large sequence of pi-digits (you would have to find a reasonable objective, but might be interesting), or do some sequence to sequence learning with encoders and decoders to predict digits for pi. Probably, the methods would not perform well from a ML perspective, but some interesting things might happen.

PS: as you might have noticed, I have mentioned quite some neural networks. There are other methods out there as well: do not get too biased.

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


title: Caesar Cipher - logic circuit

text:
# Question
Title: Caesar Cipher - logic circuit
my teacher asked the class to do a digial circuit that encrypted a message using cesar's cipher, and a circuit to decrypt, but my only idea is to solve it using a circuit that does P + K mod N, where P is The position of the letter in the alphabet, K the value of the key, and N is the number of letters in the alphabet. Or use an adder circuit, for example, when P and K have 4 bits, and N equals 8. Even if an overflow occurs, the sum between them would still give me a result within my representation. However, in my case I am using an alphabet with 94 symbols, so how can I solve this problem?

I appreciate any help.

# Answer
> 1 votes
You can instead subtract $N-K$ and test if you go negative and then add $N$ again. Or test the number against $N/2$ and if greater subtract $N-K$ otherwise add $K$.

With 94 symbols you only need 7 bits. If you go with the post check you'll need to add a bit to account for overflows for certain values of input and $K$.

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


# Question
Title: Highest Response Ratio Next (Scheduling Algorithm)
In CPU scheduling HRRN(Highest Response Ratio Next) algorithm chooses the next process to be scheduled using the formula (W+S)/S where W-\> waiting time & S-\>Service Time. Can someone share their intuition behind this formula? How does this calculate Highest Response Ratio?

# Answer
It's a variation on Shortest Job Next (SJN) and is an attempt to avoid the starvation problems for estimated long running jobs on busy systems with many short running jobs.

When a job has just hit the scheduling queue it's wait time is zero and it's priority is 1. As the wait time increases it's priority is increased by a factor weighted by it's ESTIMATED\* run time. Consider 2 processes, one with an estimated run time of 5, the other with 10. Assuming they are placed in the run queue at the same time, both will have an initial priority of 1.

Process A (s=5) priority = 1 + 0/5 = 1

Process B (S=10) priority = 1 + 0/10 = 1

As the processes wait, their priority increases proportional to their expected run time, let's say both have waited an interval of 10:

Process A (S=5) priority = 1 + 10/5 = 3

Process B (S=10) priority = 1 + 10/10 = 2

As you can see the priorities of each process increase, but at different rates. After the initial scheduling interval, process A is going to be picked to run before process B. Once a process is picked to run, its wait time is reset to 0.
Let's assume that process A was picked to run after the previous wait period, but process B had to wait another 10 intervals, and process A became computable again. The new priorities would be:

Process A (S=5) = 1 + 0/5 = 1

Process B (S=10) = 1 + 20/10 = 3

Assuming other processes with higher priority blocked both processes for another interval of 10 the new priorities become: Process A = 1 + 10/5 = 3 Process B = 1 + 30/10 = 4

And again both wait 10: Process A = 1 + 20/5 = 5 Process B = 1 + 40/10 = 5

At this point both processes again have equal priority and either COULD be picked, but on a busy system it's not guaranteed. If they wait again the new priorities would become:

Process A = 1 + 30 / 5 = 7

Process B = 1 + 50/10 = 6

Again process A becomes the higher priority, but B is still increasing it's priority. A will be picked first and it's wait again reset to 0, but since B is still accumulating wait time it's priority will keep increasing until it becomes the highest priority on the system and all other processes will have to wait for it to run.

Opinion time: This seems like a better algorithm than straight SJN, but in practice it could still provide unsatisfactory perceived user response on a busy general purpose system. Users would perceive a "bursty" system which sometimes gave quick answers, but with long pauses. I prefer preemptive style scheduling for interactive systems. For non-interactive systems, this may provide better overall throughput since it reduces expensive context switches.

* Note that these are all ESTIMATED run times either based on a default initial value or on the average of the previous estimate and the actual last run time. This leads to a scheduling problem if the estimate is wildly inaccurate or has a series of short run times followed by a very long run.
> 4 votes

# Answer
here while calculating waiting time above, we are getting it as 5 for process3 which is actually how much process3 waited till time unit 9 as it has already arrived at 4, therefore it is 9-4=5 and same for process4 and process5 that how much they waited till time unit 9 as they have already arrived at 6 & 8 , which is 9-6=3, 9-8=1 respectively.

and further same while calculating response ratio again for process4 and process5. which is how much process4 and process5 waited till time unit 13 i.e. 13-6=7, 13-8=5 respectively.

the highest response ratio next therefore does not suffer from starvation, as the process waiting for longer period of time will even compete with the processes arriving and having shorter service time and each and every process will get a chance to get the CPU processing.
> 0 votes

# Answer
I found this psuedocode from another website on how to step through the process of HRRN.

Steps for HRRN:

1. First, loop queue to find the highest ratio.
2. calculate each ratio and compare to the highest ratio
3. if response ratio is greater than highest ratio then update
4. If the element is at the start of the queue, dequeue it and set the list to it's next element.
5. Go back to the start of the queue and find the element before the dequeued element.
6. Assign prev next to dequeued process next.
7. Return the highest ratio element in the list
8. Repeat once the running process has completed the job or is pre-emptied.
> 0 votes

---
Tags: operating-systems, process-scheduling
---


# Question
Title: Determine the optimal strategy and maximize the reward
Given an array of length `n` filled with objects which contain 2 ints (`size` and `reward`).

Now 2 players are taking turns, each player has an int value we call `strength`. Let's call them player A and player B, player A goes first.

Player A can pick whichever object from the array he wants and decrease the `size` of the object by his `strength` (`pickedObj.size -= playerA.strength`), he can also skip his turn by simply not picking an object.

Player B is simple minded and for all his turns uses the same greedy strategy: he picks the object with the smallest `size` and decreases it's `size` by his `strength` (`pickedObj.size -= playerB.strength`), player B can't skip turns.

Once a player decreases the `size` of an object to 0 (or bellow) he receives the reward (`playerX.reward += finishedObj.reward`) associated with that object. Each player starts with 0 reward points (`playerX.reward = 0`).

Given an array with `n` objects, player A with `strength = m` and player B with `strength = k`, compute the maximal amount of `reward points` that player A can win.

**Examples:**

Example 1:

```
obj[] array = `{ (9,5), (6,2), (7,3) }`;
playerA.strength = 4;
PlayerB.strength = 5;

int solution = determineMaxReward(array, 4, 5);

// The solution (max amount of money player A can win) is 10.

```

Explanation:

1. Round 1: Player A skips this round, player B picks `arr[1]` and therefore decreases it's `size` by his `strength` (now `arr[1] = (1,2)`).
2. Round 2: Player A picks and finishes `arr[1]` (`playerA.reward += 2`), player B picks `arr[2]` (`arr[2] = (2,3)`)
3. Round 3: Player A picks and finishes `arr[2]` (`playerA.reward += 3`), player B picks `arr[0]` (`arr[0] = (4,5)`)
4. Round 4: Player A picks and finishes `arr[0]` (`playerA.reward += 5`)

That's an optimal game for player A, the at the end he is left with 10 reward points which is the maximal amount of reward points he can possibly achieve.

Example 2:

```
obj[] array = `{ (2,1), (2,5) }`;
playerA.strength = 1;
PlayerB.strength = 2;

int solution = determineMaxReward(array, 1, 2);

// The solution (max amount of money player A can win) is 5.

```

Example 3:

```
obj[] array = `{ (9,3), (10,3), (4,1), (8,1), (9,2) }`;
playerA.strength = 5;
PlayerB.strength = 3;

int solution = determineMaxReward(array, 5, 3);

// The solution (max amount of money player A can win) is 10.

```

**My current unproven (in the sense of optimality) approach:**

For each object, I compute the minimal number of picks player A needs to make in order to finish that object. Then I reduce to the knapsack problem, size of the knapsack being the number of picks player A can do during the game, then the best way to fit the objects with their size and reward into the knapsack (such that the reward is maximized) is found.

Now I'm not sure if this is optimal, I can't find a counterexample where my approach doesn't work but I also can't prove that it's optimal. Any help/comments are appreciated.

This is a problem I have been struggling with for a while now, I encountered it during a programming contest in the context of dynamic programming.

# Answer
> 1 votes
The key observation is that, for player A, picking an object which is not being picked by player B is equivalent to skipping the turn and saving this pick for later (for example use a variable `savedPicks`). Now instead of having to decide upon which object to pick the problem becomes deciding if player A should pick the current object picked by player B or save the pick for later. So we iterate through the objects depending on how player B picks them and either also pick the object as he does or save a pick for later.

Now the problem is solvable with DP, observe that your state consists of the current object which is targeted by player B, the remaining size of the object and the number of picks player A has saved.

There are three transitions:

1. Object is finished, move to the next one,
2. Player A skips the round and saves a pick for later (`savedPicks++`),
3. Player A uses a saved pick to pick the current object (potentially getting the reward if his pick finished the current object).

Solve each of the three transitions, apply memoization (save already computed states, use a 3 dimensional array for example), don't forget the base case (all objects have been finished).

Happy coding!

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


title: More details about the Baillie–PSW test

text:
# Question
Title: More details about the Baillie–PSW test
It's clear that Mathematica uses the Baillie–PSW test for its PrimeQ function (which tests primality), and as I read in the Mathematica documentation, it starts with trial division, then base 2 and 3 Miller–Rabin, and then Lucas pseudoprime test. My question is:

> Can we remove base 2 and 3 and use only a random base?

Also, can any one suggest a good reference about this primality test other than Wikipedia?

# Answer
> 10 votes
The advantage in using base 2 is that we know all of the psp's base 2 up to $2^{64}$. It has been verified that none of these psp(2)'s passes a Lucas test when the parameters $P, Q$ are chosen in accord with any of the methods in the Baillie/Wagstaff paper.

If you choose a random base, there might be some composite $n$ that passes both the Fermat and Lucas tests. For example, $n = 5777$ is a strong psp base 76, and is also a Lucas pseudoprime.

By the way, if you implement a Lucas test, I would also recommend adding the following check, which is virtually free once you reach the end of the Lucas calculation. If $n$ is an odd prime and $(n, QD) = 1$ where $D = P^2 - 4Q$, (and, as usual, $\left(\frac{D}{n}\right) = -1$ (a Jacobi symbol), then $V\_{n+1} \equiv 2Q \pmod n$. If $D, P$, and $Q$ are chosen by method $A^\*$ (see Baillie/Wagstaff), then 913 is the only odd composite number up to 25 billion for which this congruence holds. (The B/W paper gives a limit of $10^8$, but I've recently carried the calculation farther). So, in addition to the sprp(2) and slprp(P,Q) tests, this congruence adds additional strength to the primality test.

# Answer
> 5 votes
References for the test:

* Pomerance, Selfridge, Wagstaff, "The Pseudoprimes to 25 x 10^9", July 1980. Page 1024-1025, Check if n is a strong probable prime base 2. Check whether n is a Lucas probable prime using method A (Selfridge) or B. The authors offer $30 to the first finder of a counterexample or proof of non-existence. It references the next paper when discussing the test.
* Baillie and Wagstaff, "Lucas Pseudoprimes", October 1980. Page 1401. Trial divide to some convenient limit. Check whether n is a strong probable prime base 2. Check whether n is a strong Lucas probable prime using method A (Selfridge) or B.
* Pomerance, "Are there counter-examples to the Baillie-PSW Primality Test?", 1984. References PSW80: Check whether n is a strong probable prime base 2. Check whether n is a Lucas probable prime using the Selfridge parameters (method A). He mentions that even if condition 1 is weakened, every composite to n \<= 25\*10^9 still fails. The short paper repeatedly calls this combination of a strong base-2 prp and Lucas-Selfridge prp tests the "Baillie-PSW" test.

All of these describe using a strong base-2 probable prime test. The slightly earlier PSW paper indicates a Lucas test, while the BW paper recommends a strong Lucas test. The 1980 papers indicate that one of two specific parameter selection methods should be used, while Pomerance's 1984 paper drops the non-Selfridge method.

In my opinion, the paper by Baillie and Wagstaff is the primary reference, though should be read in combination with Pomerance, Selfridge, and Wagstaff. Consensus over time is that the Selfridge (method A) parameter selection should be used. Other variations commonly used include the extra-strong test, the "almost" extra-strong test, and Frobenius tests. See the page "Pseudoprime statistics, Data, and Tables" for more info and links.

To answer your Mathematica questions:

1. Based on Pinch (1993), Mathematica used to do a base 2 strong pseudoprime test, as it should, but used a borked "Lucas" test that was not the test Baillie et al. indicated. Pinch found pseudoprimes to their test. He also indicates that Wolfram modified their Lucas test in some way, but not to use the Lucas test that should be used for BPSW. Without information from Wolfram, we don't know what they've done in the last 24 years since then. Perhaps they beefed up their "Lucas" test and added the base-3 M-R test to cover up issues. Maybe they're now using a proper Lucas test. We don't know.
2. If the correct Lucas test was used, then the base 3 test could be removed and we'd be left with a similar BPSW test to that used by most other packages. We'd know there were absolutely no counterexamples less than 2^64, and no known larger counterexamples. Adding another test, whether base 3 or a random base, would add a bit more certainty for \>64-bit inputs. I don't think that's a bad idea.
3. Replacing the base-2 test with a random-base test is, in my opinion, a bad idea. We have well known results for using base 2, including the very nice no-64-bit-counterexamples one. It makes the test deterministic. While using a random base will still retain the anti-correlation property with regard to the Lucas test, it has different tradeoffs. Personally I think it's a better idea to use a proper BPSW test (base 2 SPRP + strong/AES/ES Lucas) plus one or more random-base tests if you want to defeat adversaries who secretly know BPSW pseudoprimes. Or add the extra work for a Frobenius test on top of the Lucas test.

# Answer
> 1 votes
You are asking two questions. I will only answer the first.

It is very likely that Mathematica uses the base 2 and 3 test as an *optimization*. These bases are probably faster to test (because of their magnitude), and they work for both numbers. You can skip this test if you want, but the resulting function would be slower on average.

---
Tags: reference-request, number-theory, primes
---


# Question
Title: construct a TM decides in linear time, if valid bracket
I want to construct a 2-tape Turing Machine, which decides in linear time if the input string over $\Sigma^\* := \\{(, \[, \], )\\}$ is a valid bracket.

I have not constructed too many TM's yet, this is why I need your help.

# Answer
If you are not allowed to use two or more tapes then as Yuval Filmus commented you cannot solve in linear time. Otherwise you can convert the following steps into TM instructions:

```
 Initially input on the tape 1, the tape 2 is empty.
 Machine reads input symbols stored on the tape 1, and tape 2 is used as stack (for push/pop operations).

 1)  x = Read a symbol.
 2)  If x is '[' or '(' Then
 3)    push x and go to 1)
 4)  Else If x is ')' Then
 5)    sym = pop()
 6)    If sym != '(' Then
 7)       Reject and Halt.
 8)    Else
 9)       go to 1)
 10) Else If x is ']' Then
 11    sym = pop()
 12)   If sym != '[' Then
 13)      Reject and Halt.
 14)   Else
 15)      go to 1)
 16) Else If x is '$' Then (if end of input)
 17)   If stack is empty Then
 18)      Accept and Halt
 19)   Else
 20)      Reject and Halt
 21) Else
 22)   Reject and Halt

```

I think translation to a TM of this piece of code is quite tedious work.

In computability theory if you want to prove existence of a TM then informal description (or just description using one of the high-level programming languages) is enough. You may use a single tape TM model or multitape model. However, when dealing with time complexity selection of a model matters.
> 2 votes

---
Tags: turing-machines, decision-problem
---


title: Small world theorem for set constraints

text:
# Question
Title: Small world theorem for set constraints
Let $S\_1,\dots,S\_n$ be variables representing unknown sets. A *set expression* has the form $S\_i$, $\overline{E}$ (the complement of $E$), or $E \cap E'$, where $E,E'$ are set expressions. A *constraint* has the form $E = \emptyset$ or $E \ne \emptyset$, where $E$ is a set expression. Given a conjunction of constraints, the problem is to determine whether they are satisfiable, i.e., whether there is an assignment from variables to sets that makes all of the constraints hold.

Conjecture: if there exists a satisfying assignment, then there is a satisfying assignment where all sets are subsets of a universe $U$ with $k$ elements, where $k$ is the number of constraints of the form $E \ne \emptyset$.

Is this conjecture true?

I suspect it is, but I can't seem to prove it. I can prove it if there is no complement operator, but my proof strategy seems to go awry if there are complements. (Proof strategy: suppose the constraints are $E\_1 \ne \emptyset$, .., $E\_k \ne \emptyset$, and suppose we have any satisfying assignment. Let $x$ be the smallest element of $E\_1 \cup \dots \cup E\_k$, where $x$ is an element of $E\_i$; then add $x$ to $U$, discard $E\_i$, and repeat. Once this is finished, replacing each set $S\_i$ with $S\_i \cap U$ still leaves all constraints satisfied.) If this conjecture is true, it is a sort of "small-world theorem", which says that a not-too-large universe suffices for checking satisfiability. These kinds of theorems are helpful for improving the performance of constraint-solving algorithms.

# Answer
> 2 votes
The conjecture is true, and the proof strategy listed there can be made to work.

Let $s = (s\_1,\dots,s\_n)$ be a satisfying assignment for the variables that makes all of the constraints hold. We'll write $E(s)$ for the result of evaluating the expression $E$ with the variables $S\_i$ set to $s\_i$. In the following, define $U$ by the procedure listed in the question: let $E\_1 \ne \emptyset$, ..., $E\_k \ne \emptyset$ be the constraints of second type; pick any element of $E\_1(s) \cup \cdots \cup E\_k(s)$, call it $x$; add $x$ to $U$; delete all of the constraints $E\_i \ne \emptyset$ such that $x \in E\_i$; and repeat. Define $s'\_i = s\_i \cap U$.

Now I claim that $s'\_1,\dots,s'\_n$ is also a satisfying assignment that makes all of the constraints hold.

First, let's consider the constraints of the form $E = \emptyset$. I claim that if $E(s) = \emptyset$, then $E(s') = \emptyset$. In particular, I claim that $E(s) \cap U = E(s') \cap U$ for all set expressions $E$. The proof is by recursion: by definition of $s'$, we have $S\_i(s) \cap U = S\_i(s') \cap U$; also if $t \cap U = t' \cap U$, then $\overline{t} \cap U = \overline{t'} \cap U$; and if $t\_1 \cap U = t'\_1 \cap U$ and $t\_2 \cap U = t'\_2 \cap U$, then $(t\_1 \cap t\_2) \cap U = (t'\_1 \cap t'\_2) \cap U$. So this means that $s'$ satisfies all of the constraints of the first type (all of the constraints of the form $E = \emptyset$), since $s$ does.

Next, consider the constraints of the form $E \ne \emptyset$. We know $E(s) \ne \emptyset$. Therefore, there was a step in the iterative definition of $U$ when we chose some element $x \in E(s)$ and added it to $U$. We proved earlier that $E(s) \cap U = E(s') \cap U$. Since $x \in E(s)$ and $x \in U$, it follows that $x \in E(s') \cap U$, and thus $E(s') \ne \emptyset$. This means that $s'$ satisfies all of the constraints of the second type, too.

We've shown that if there is any satisfying assignment for all constraints, then there exists a satisfying assignment where all sets are subsets of $U$. This completes the proof of the conjecture.

---
Tags: satisfiability, sets, boolean-algebra, constraint-satisfaction
---


# Question
Title: Complexity of simplifying two-variable algebraic expression
Given algebraic expression of two variables x and y, I want to simplify this algebraic expression until it cannot be simplified anymore. What algorithm can I use for this?

For instance:

x+x+y+y = 2•x+2•y = 2•(x+y)

x•x+y•y=x2+y2

(x+y)•(x+y)=(x+y)2

x•x+x•y+x•y+y•y=x2+2•x•y+y2=(x+y)2

The most simplified algebraic expression is the one with the fewest characters. Expressions will have only addition, multiplication, and exponentiation with a constant.

What is the complexity of this problem?

Does exist polynomial time and space algorithm to solve this problem? I tried to find over the Internet the algorithm to simplify algebraic expressions, but I didn't find anything. The problem is that I don't know where to start.

# Answer
Minimizing the number of characters is a tough one.

The field of symbolic computation might be relevant, but I don't know of any algorithms that find a simplified form with the fewest characters.

Here's one approach you can use, that won't be optimal. Express the expression as a polynomial over variables $x,y$. Then, factor the polynomial. Computer algebra systems will include algorithms to do that for you. For the size problems you are talking about, this should be very efficient.

This won't necessarily find the optimal expression. For instance, $x^2 + y^2 + 2xy + 1$ is irreducible (can't be factored), but there is a shorter equivalent expression, namely $(x+y)^2 + 1$. However, in many cases it will find a way to simplify the expression to some extent.

Another approach, which also isn't optimal, is to use a template-based method. Suppose you have a "template" for what you expect the simplified expression might look like: e.g., you are interested in expressions of the form

$$T(x,y) = \sum\_{j,k} a\_{j,k} (b\_{j,k} x + c\_{j,k} y)^k + \sum\_{j,k} d\_{j,k} x^j y^k.$$

Then given an expression $f(x,y)$, it is possible to determine whether there is an equivalent expression of the form above. In particular, pick many random values $(x\_i,y\_i)$, evaluate the expression $f$ at each of those values, and set up one equation per value

$$f(x\_i,y\_i) = T(x\_i,y\_i).$$

Here since we can evaluate $f(x\_i,y\_i)$, the left-hand side of each such equation is a constant. Expanding out the definition of $T(x\_i,y\_i)$, the right-hand side is an expression in the unknowns $a\_{j,k},b\_{j,k},c\_{j,k},d\_{j,k}$. Thus, each value $(x\_i,y\_i) we pick gives us one equation on those unknowns. After sufficiently many equations, it should be possible to solve that system of (nonlinear) equations for the unknowns. (Computer algebra packages typically also include methods to solve a system of nonlinear equations for you.) There may be many solutions, in which case you could enumerate all solutions, or consider simpler templates and find one solution per template.

This might give you multiple candidates for simplified expressions, and you can keep the one that has the fewest characters. Again, there will be cases where it is not the optimal solution, but it might be useful for small expressions.

Finally, if you care about optimality more than efficiency, you could enumerate all expressions in order of increasing length, and test each one to see if it is equivalent to the original expression. A simple way to test whether two expressions are equivalent are to evaluate them at some randomly selected points; this is fast, but might occasionally err on the side of failing to realize that two inequivalent expressions are inequivalent. A more comprehensive test is to convert both expressions to polynomials, then check that their coefficients are equal. This should give the optimal solution, but I expect it will be inefficient: the running time is exponential in the length of the solution.
> 1 votes

---
Tags: algorithms, complexity-theory, time-complexity, space-complexity
---


# Question
Title: 2-tape TM that accepts words from $L := \{bin(n)$#$w \in \Sigma^* | n \in \mathbb N \land w \in \{0,1\}^* \land |w| \le n\}$ in $O(n)$
Let $\Sigma := \\{0,1,$#$\\}$ be the input-alphabet and $L := \\{bin(n)$#$w \in \Sigma^\* | n \in \mathbb N \land w \in \\{0,1\\}^\* \land |w| \le n\\}$ the alphabet. $|w|$ means the length of the word $w$ and $bin(n)$ the binary representation of $n$.

I need to construct a 2-tape TM which has $O(n)$ complexity and accepts the words from $L$, i.e. the machine terminates in an acceptable state iff the input is contained in $L$ und for all other input words the machine terminates in a not acceptable state.

EDIT: I already constructed a 1-Tape TM which reduces a binary number by 1 and which is supposed to help me with solving this problem but I don't know how.

# Answer
Think over how to convert binary representation of $n$ into unary one using two tapes. The result should be stored on the second tape. For example, if $n=6$ then the unary representation could be $111111$. Then compare number of symbols of $w$ and number of $1$s of the unary representation of $n$. If the number of $1$s is less than or equal to $|w|$ then accept, otherwise reject.

Since number of bits in $bin(n)$ is no more than $log(n)$ number of unary bits is no more than $2^{log(n)} = n$, so writing down each bit on the tape should not take more than $O(n)$ time, and comparison $w$ with the unary $1$s also takes $O(n)$.

So you just need to design and algorithm for conversion from binary to unary representation of $bin(n)$ using two tapes that runs in $O(n)$ time.
> 0 votes

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


# Question
Title: Is there an existing data structure that is of fixed size, and will push the oldest/last element out if a new element is inserted?
I'm looking for a data structure that will push its oldest/last element out if a new element is inserted. For example, let `D` represent the structure. `D` contains 3 elements of the type `Number` `D`'s default values will be initialized to `1, 2` and `3`.

$$D = \[1, 2, 3\]$$

If a `Number` that contains the value `5` is inserted into `D`, `3` will be pushed out, while `1` and `2` are shifted right.

$$D = \[5, 1, 2\]$$

The first thing that comes to mind would be an array, but the definition does not include the pushing behavior.

# Answer
> 44 votes
Fixed-size queues are often implemented using what some people call circular buffers. If you remove the protection against it being full, you get the desired behaviour.

Of course, no *actual* pushing will happen in the array -- that would be too expensive -- but it will *look* like it from the outside.

---
Tags: data-structures, arrays, queues
---


# Question
Title: how does a harddisk work? block / sector
Can someone explain me the way harddisks work? :/

The size of a block is specified in the filesystem, am I right? As you can see in the picture from wikipedia, the disk is divided into circle sectors. But the blocks on the outer tracks are obviously larger (physically)...

So the "bit-density" on the outer blocks is way smaller than on the blocks near the middle of the disk? I think that I am missing something.... Maybe someone can help me out with another picture / sketch.

Thanks a lot and sorry for the "nooby" question :)

# Answer
> 0 votes
Why would the bit density have to be the same?

Imagine that the platter is a piece of paper and the write head is a pen. The head can write, say, 1000 bits per second by being raised and lowered to make marks on the paper. Writing one bit corresponds to lowering the pen for 1ms. If the sector is close to the centre, the paper will be moving fairly slowly, so holding the pen down for 1ms will leave a short line; if it's towards the edge of the disc, the paper will be moving much faster and 1ms will leave a longer line. Now consider the read head: wherever it is on the disc, if it sees ink for a millisecond, that's a 1; if it sees paper for a millisecond, that's a 0. The data density is lower at the edge of the disc but the heads can do their job without needing to know where on the disc they are. What you might call the "temporal bit density" (a term I just made up) is constant across the disc.

In contrast, if you wanted the "spatial bit density" to be constant across the whole surface of the disc, then the heads have to read and write much faster at the edge of the disc. In this set-up, each 1/0 corresponds to a fixed length, and that length will come past the heads much more quickly if it's at the outer edge of the disc than if it's at the centre. This is a much more complex scenario.

# Answer
> 1 votes
This is something that has changed over the decades.

In the past, the blocks were laid out exactly as you see in the picture. The bit density of the outer blocks was less than those of the inner blocks. This made the hardware easy to build at the expense of being less efficient.

In modern times, we no longer need to make the hardware easy. We're interested in maximum efficiency of the harddrive. Modern harddrives do not have nice easy angular wedges like the old ones do. They, instead, try to keep the bit density as even as possible (maximized at all places).

---
Tags: computer-architecture, storage
---


# Question
Title: Maximum sum difference between two sorted array elements under one condition
We're given two arrays $A$ and $B$ with size $N$ and $M$ respectively. We want to find a set $P = \\{(a\_1, b\_1), \dots, (a\_s,b\_s)\\}$ such that

* for each $i\in\\{1, \dots, s\\}$, $a\_i\in A$, $b\_i\in B$ and $a\_i\>b\_i$ and $a\_i,b\_i$ musn't be chosen before;
* $\sum\_{i=1}^s (a\_i-b\_i)$ is maximized.

A natural approach is to sort array $A$ in descending order and $B$ in ascending order, initialize $i$ and $j$ to $1$, then iterate: while $A\[i\] \> B\[j\]$ add $A\[i\] - B\[j\]$. How we can prove that this solution works?

# Answer
> 0 votes
Two sets A and B. Using i and j only once maximize the ∑(a\[i\] - b\[j\]). Not required to use and i and j.

I don't know if this is a hard proof but

For $A\[i\] \> B\[j\]$
∑(a\[i\]−b\[i\]) = ∑(a\[i\]) - ∑(b\[i\])

So the problem is reduced to maximize $A\[i\] \> B\[j\]$
Reverse sorting maximizes the number of $A\[i\] \> B\[j\]$

Or another way to say it
maximizes ∑(a\[i\]) and minimizes ∑(b\[i\])
Descending sorting maximizes ∑(a\[i\])
Ascending sorting minimizes ∑(b\[i\])

---
Tags: sorting, arrays, greedy-algorithms
---


# Question
Title: How to define a language for an independent set problem of a graph?
Let a graph $G=(V,E)$ have an independent set $I\subseteq V$ with $\\{u,v\\}\notin E$ for all $u,v \in I$ and $k \in \mathbb{Z}\_{\>0}$ where $|I|=k$.

How can I define the language $L\_{P\_{Independent Set}}$ to this decision problem?

I know that $I$ could be written as $I = \\{u,v\\} \in V | \\{(u,v)\\}\notin E \\}$ but don't really understand how to describe the language.

# Answer
> 1 votes
A language $L$ describes decision problem $p$ means that $\forall x \in L $ the instance $x$ is a Yes/Accept instance of $p$.

For the independent set problem, we have to define language $L$ such that every $x\in L$ is an independent set of graph $G=(V, E)$.

So one possible way to define decision language for independent set problem is $$\begin{array}{ll} L & = \\{I \mbox{ such that } I\subseteq V \mbox{ and }\forall u,v\in I,\\;\\; (u,v)\notin E\\} \\ & = \\{I \\;\\;|\\;\\; I\subseteq V \mbox{ and }\forall u,v\in I, \\;\\; (u,v)\notin E\\} \end{array} .$$

If you wish to define the language generally you can write it as $$ \begin{array}{ll} L & =\\{(G=(V,E),I) \mbox{ such that } I\subseteq V \mbox{ and }\forall u,v\in I,\\;\\; (u,v)\notin E\\}\\ & =\\{(G=(V,E),I) \\;\\;|\\;\\; I\subseteq V \mbox{ and }\forall u,v\in I,\\;\\; (u,v)\notin E\\} \end{array} .$$

---
Tags: formal-languages, graphs
---


# Question
Title: Can I say is lossy compression to discard data having a way to recover it?
I'm working on a compression algorithm for a specific kind of data. I have found a way to discard (important) parts of the data during compression as I have also found a way to recover the missing parts during decompression.

The decompression algorithm most of the times will infer the data equal to the discarded one. However, in punctual cases, it will infer similar data that works just as well as the original.

So my question is: **Can I claim that my algorithm is lossy?**

# Answer
> 2 votes
> However, in punctual cases, it will infer *similar* data that works just as well as the original.

From this I would conclude it is lossy because it is similar data, rather than lossless, which would be a perfect reconstruction.

That being said, I'm not entirely what you mean by "data that *works* just as well", but if the data works **exactly** how the original data would *work*, for your use case it might be considered lossless because the information you need and compress is not lost. You must be careful to specify that the compression of the information you wish to recover is lossless, but the compression of the data as a whole is lossy.

As example, if my goal is to save (using compression) simple arithmetic equations to later determine if they are odd or even. I might compress $f = 4 + 3 + 8 +1$ into the number of even ($e$) and odd ($o$) terms it has: $ C(f) = 2e2o$. This is clearly lossy, I can't perfectly reconstruct which terms created $f$, but for my purposes I can clearly determine whether it is odd or even after compression. Even further I could reconstruct *similar* data (as you stated) that works just as well as the original, for my purposes.

---
Tags: data-compression
---


# Question
Title: Can quantum computer compute the minimal intersection DFA of numerous minimal DFAs in polynomial time using polynomial number of qubits?
Can **quantum** computer compute the **minimal** intersection DFA of numerous **minimal** DFAs in polynomial time using polynomial number of **qu**bits, where the language of each given **minimal** DFA is finite and it's alphabet is Σ={0,1} and all words/strings in all languages are in the same length equal to the given number of **minimal** DFAs?

Remember that **minimal** DFA is deterministic finite automaton that there is no possibility to delete any of it's states and change it's transitions function δ so the language accepted by this DFA is unchanged.

**EDIT:** According to what I read here

3yakuya says in his answer:

> As far as we believe, a quantum Turing machine is able to simulate any quantum computer, and it is also equivalent to classical deterministic Turing machine in terms of computability.

I don't know why he/she uses the word "believe", I think that it is known fact, because quantum computers where designed to solve every problem **correctly**, so it should be possible for quantum computer to compute the minimal intersection DFA of numerous minimal DFAs **correctly**, i.e. this is a task that can be accomplished and computed by quantum computer.

3yakuya then says:

> However, if we consider practical computability, things may look a bit different. Imagine a problem where we have a classical solution which runs with O(2n)O(2n) complexity. It is definitely solvable, but for any reasonable data size it will require massive amounts of operations. In practice, it will run for thousands of years, even on the fastest computers. Now imagine we have a quantum algorithm solving the same problem, but with O(n)O(n) complexity. Out of a sudden, exact same problem can be solved in minutes, which is very reasonable (especially compared to thousands of years).

If quantum computer runs the **classical** algorithm (that can also be run by deterministic turing machine) to compute the minimal intersection DFA, by first computing the product intersection DFA (not minimal) and then minimize it by using Hopcroft's algorithm, then this will take too much time for the quantum computer to finish and no one will wait until it is done, and the same is correct for deterministic turing machine, but if quantum computer runs **quantum** algorithm to compute the same thing, but much more efficiently than the **classical** algorithm (without computing products and calling any minimization algorithm), but getting the minimal intersection DFA more directly and quickly by **quantum** algorithm, which suppose to run only by quantum computer, but not by deterministic turing machine, then it is expected that the quantum computer running this quantum algorithm will finish much faster and at most polynomial time.

So until now there is hope, but after the first quote and before the second quote, 3yakuya said:

> In other words, as far as we know the space of problems solvable by quantum computers is the same as space of problems solvable by classical computers.

That's really bad! Computing the minimal intersection DFA of numerous minimal DFAs is PSPACE-Complete problem! That means, the machine needs non-polynomial amount and quantity of memory to finish the computation!

The main reason that deterministic turing machine won't do that, because in reality, deterministic turing machine have finite tapes! Not infinite! For some large input, the turing machine (deterministic) won't have enough tape to write down the result, i.e. the minimal intersection DFA!

But I thought that "out of memory" problem can occur in classical computers, because their memory is a finite array of bits, where each bit has two states only: 0 and 1, so to describe larger object, the classical computer needs more memory, and in fact more bits, but quantum computer has qubits rather than bits, and **single** qubit suppose to have "infinitely" states, which are 0, 1 and the superpositions of 0 and 1. If so, quantum computer should have like "infinite memory", no? Out of memory expected to occur in classical computer, but not in quantum computers, so space problems for quantum computers suppose to be O(1), in contrast to classical computers, which is **rarely** O(1), but most of them are much worse than O(1). Maybe I misunderstand what really quantum computer is or 3yakuya is wrong in what he/she says?

If 3yakuya is right, then the answer to my question is NO, quantum computer won't be able to compute the minimal intersection DFA, because it will require non-polynomial number of qubits or something and that's too many.

# Answer
> 2 votes
No. The size of the minimal DFA for the intersection might be exponentially large. Therefore, no computer can compute it in polynomial time, not even a quantum computer -- it requires exponential time even to write down the answer. In particular, if you have $n$ languages, each of whose minimal DFA has size $m$, then the minimal DFA for their intersection can be as large as $\Theta(m^n)$. This is exponential in $n$.

Separately: it is known that $\mathbf{BQP} \subseteq \mathbf{PSPACE}$. it is generally believed/conjectured that $\mathbf{BQP} \subsetneq \mathbf{PSPACE}$ (i.e., it is a proper subset); if that is correct, then it follows that no PSPACE-complete problem can be solved by a quantum computer in polynomial time.

---
Tags: complexity-theory, formal-languages, finite-automata, quantum-computing
---


# Question
Title: Question regarding terminology used to describe Benes networks
I'm studying a routing problem on a cyclic butterfly network. The paper I am reading states that two properties of the cyclic butterfly network make it efficient for the routing algorithm it describes. I'm new to this subject, and I'm struggling to understand the first property, which is:

"(1) It embeds a Benes network - meaning that if we traverse the columns and back any permutation of the row labels can take place without collisions"

It adds that this is trivially true for a square grid. In this context do collisions mean collision of packets of information? Why is this trivially true for a square grid, but not the cyclic butterfly network?

Kind regards

S

# Answer
> 0 votes
I think they are talking about a path that goes from the left edge to the right edge, and then back to the left edge again. That path will never visit any node more than once. By "without collisions", they mean that the left-to-right part of the path will never intersect with the right-to-left part of the path.

I think.

---
Tags: graphs, parallel-computing, routing
---


# Question
Title: How to convert a graph into a Boolean formula that represents all paths from a source node to a sink node?
I have a DAG. I want to construct a boolean formula $\varphi$ that represents all paths from a source node to a sink node.

In particular, I have a variable for each vertex. A path $v\_1 \to v\_2 \to \dots \to v\_k$ is represented as the subformula $v\_2 \lor \dots \lor v\_{k-1}$. I want a formula $\varphi$ that is a conjunction of all of these subformulas (one subformula per path from a source node to a sink node).

How can I construct $\varphi$ in CNF form?

Input example:

```
    W
    ^  (r1 and r2 both reach w)
R1    R2

 X    X (this signifies a connection to R1 and R2)

b1    b2
^     ^
|     |
c1    c2

```

Desired output in CNF format:

```
(b1 or R1)
and
(b1 or R2)
and
(b2 or R1)
and
(b2 or R2)

```

The output represents all paths from c1 or c2 to w.

# Answer
> 0 votes
If you don't want to allow introduction of any temporary values, then you just need to enumerate all paths in the graph. There are many ways to do that. A simple method is a recursive algorithm, where at each step you move one step forward to a vertex $w$, then recursively find all paths from $w$.

However, the running time and size of the output is proportional to the number of paths, which might be exponentially large. Therefore, this cannot be said to be efficient in practice.

---

If you are willing to allow introduction of temporary variables into the formula, then you can solve this problem without needing exponential time or space. Suppose the variables are $v\_1,\dots,v\_n$. I'll describe an algorithm that outputs a boolean formula $\varphi(v\_1,\dots,v\_n,t\_1,\dots,t\_k)$ in CNF form, where $t\_1,\dots,v\_k$ are temporary variables, with the following property: if $\varphi(v\_1,\dots,v\_n,t\_1,\dots,t\_k)$ is true, then there is a path that goes through the vertices $v\_i$ such that $v\_i=\text{True}$); and if there's a path that goes through a set of vertices, then there exists $t\_1,\dots,t\_k$ such that $\varphi(v\_1,\dots,v\_n,t\_1,\dots,t\_k)$ (where $v\_i$ is true if the path goes through $v\_i$, and false otherwise).

In particular, we construct a boolean circuit $C$ that accepts boolean inputs $v\_1,\dots,v\_n$ and $n^3$ bits representing a sequence of edges $e\_1,e\_2,\dots,e\_m$ (with $m \< n$). The circuit outputs true if $e\_1,e\_2,\dots,e\_m$ represents a path (i.e., the destination of $e\_i$ matches the source of $e\_{i+1}$) from source to sink, and if $v\_i$ is true if and only if $v\_i$ appears somewhere in that path. It's possible to build a polynomial-size circuit to check this.

Now we convert this circuit to CNF, using the Tseitin transform. This introduces some additional temporary variables. We let $\varphi$ denote this formula. It depends on the variables $v\_1,\dots,v\_n$, and on some temporary variables; the temporary variables include the $n^3$ input bits that represent the path, plus all temporary variables introduced by the Tseitin transform. The Tseitin transform outputs a CNF formula that is satisfiable just when the circuit outputs true, so this gives us a CNF formula of the desired form.

---

If you don't want to work through the details of the Boolean circuit, here is an explicit construction of such a formula. The variables will be named $x\_v$ where $v \in V$ is a vertex. I'll also use temporary variables named $y\_{v,i}$ where $v$ ranges over vertices and $i \in \\{1,2,\dots,n\\}$. The intuition is that $y\_{v,i}=\text{True}$ will indicate that the $i$th step of the path is at vertex $v$. For convenience, add a self-loop (a self-edge) $v \to v$ to the graph for each sink vertex $v$.

The formula is a conjunction of several different types of clauses, each with a different purpose:

* The path starts at a source vertex: $\bigvee\_v y\_{v,1}$ where in this clause $v$ ranges over the source vertices.
* At each step, the path is at a single vertex: for each $i$ we have $\bigvee\_v y\_{v,i}$ ("at least one"), and for each $i$ and each pair of different vertices $v,w$ we have $(\neg y\_{v,i} \lor \neg y\_{w,i})$ ("at most one").
* The path ends at a sink vertex: $\bigvee\_v y\_{v,n}$ where in this clause $v$ ranges over the sink vertices.
* Each step traverses an edge: for each $i$ and each non-edge $(v,w) \notin E$, we have the clause $(\neg y\_{v,i} \lor \neg y\_{w,i+1})$.
* A vertex $v$ is visited ($x\_v=\text{True}$) iff it appears at some step of the path: for each non-source non-sink vertex $v$, we have a clause $(\neg x\_v \lor y\_{v,1} \lor y\_{v,2} \lor \dots \lor y\_{v,n})$; and for each $i$ we have a clause $(\neg y\_{v,i} \lor x\_v)$.

Taking the conjunction of all of those clauses gives a boolean formula in CNF form.

---
Tags: algorithms, graphs, boolean-algebra
---


# Question
Title: $L = \{ w \in \{0, 1, 2\}^*: |0| + |2| = |1| \}$ where |0| denotes number of 0s in the string w
I have come up with:

```
S→0SX | 1SY | 2SZ | SS | ϵ
X→1
Y→0 | 2
Z→1

```

I think I am wrong. Any directions?

# Answer
> 2 votes
These observations may help when using induction:
1) Since the number of $1$s is equal to the sum of numbers of $0$s and $2$s, any string in $L$ is of even length.
2) Starting from $S$ any number of steps of a derivation without using $S \rightarrow SS \ | \ \epsilon$ results in a string $a\_1a\_2 \dots S \dots a\_{n-1}a\_n$ where number of $1$s is equal to the sum of $0$s and $2$s.
3) If $x = a\_1a\_2 \dots a\_{n-1}a\_n \in L$ ($|x|$ is even and number of $1$s in $x$ is equal to the total number of $0$s and $2$s) then $x$ has at least one of substrings $12, 21, 01$ or $10$ which is derived from $S \rightarrow 0S1 \ | \ 1S0 \ | \ 1S2 \ | \ 2S1$.

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


# Question
Title: Approximate a smooth f(x,y) function with a polynomial function
I have a discrete function of two real variables defined as a set of point in a rectangular domain. The function is smooth. I need to approximate it with a polynomial function of the 2nd degree with the error as little as possible. What algorithm can I use to find out the constants for the polynomial?

# Answer
Wikipedia:

> In statistics, polynomial regression is a form of regression analysis in which the relationship between the independent variable $x$ and the dependent variable $y$ is modelled as an $n^{th}$ degree polynomial in $x$.

One possible solution is the polynomial regression, that is, curve fitting method. Given a set of points $Y$ you may use one of two algorithms: closed form solution or gradient descent. When number of points is very large then the gradient descent is faster than closed form solution. Also note that we measure error using residual sum of squares (RSS). Both algorithms finds coefficients by minimizing the RSS. This post may help as well.
> 3 votes

---
Tags: algorithms, approximation, polynomials
---


# Question
Title: Lower bound on competitive ratio of $m$-machine scheduling
Given a sequence of positive reals $a\_1, a\_2, \dots, a\_n$ and an integer $m$, for each $j$ assign $a\_j$ to a machine $i$, $1\< i \< m$, so as to minimize the maximum, over $i$, of the sum of all reals assigned to machine $i$.

Theorem: There is no randomized $m$-machine scheduling algorithm with a competitive ratio less than $4/3$ for any $m \geq 2$.

The following is the Proof Sketch given in the paper:

> Consider the job sequences $m \times 1$ and $m \times 1, 2$. (Here $m \times 1$ denotes a sequence of $m$ 1’s.) If the algorithm schedules the $m$ 1‘s on $m$ different machines with probability $p$, the worst-case ratio between its cost and the optimal cost is at least $\max\\{2 – p, 1 + p/2\\} \sim 4/3$.

I have problem understanding the proof. I would really appreciate if anyone can explain the proof in details, especially how to arrive at the worst-case ratio of $\max\\{2-p, 1+p/2\\}$.

# Answer
> 2 votes
Consider first the sequence $m \times 1$. If the algorithm schedules all the 1's in different machines, then its competitive ratio is 1. Otherwise, its competitive ratio is at least 2 (since the maximum is at least 2 instead of the optimum 1). This case gives an average competitive ratio of at least $p \cdot 1 + (1-p) \cdot 2 = 2-p$.

Consider next the sequence $m \times 1, 2$. If the algorithm schedules all the 1's in different machines, then its competitive ratio is 3/2, since the maximum is 3 while the optimum is 2. If it doesn't schedule the 1's in different machines, we use the trivial bound on the competitive ratio. This case gives an average competitive ratio of at least $p \cdot (3/2) + (1-p) \cdot 1 = 1 + p/2$.

We conclude that the competitive ratio is at least $\max(2-p,1+p/2)$. If $p \leq 2/3$ then $2-p \geq 4/3$, whereas if $p \geq 2/3$ then $1+p/2 \geq 4/3$, and so whatever the value of $p$, we get that the competitive ratio must be at least $4/3$.

---
Tags: algorithms, scheduling, online-algorithms, competitive-ratio
---


# Question
Title: Using Graphs to construct semi-supervised learning solution
I am currently trying to design a graph-based approach for content tagging. In principle I am trying to two two things:

1. Use an algorithm such as Latent Dirichlet Allocation (LDA) or some variant of it to discover terms in documents that relate to a certain topic, thereby allowing me to tag a document as relating to that topic. None of the documents are labelled yet, so this step is entirely unsupervised
2. Allow user feedback on whether the labels are correct. This firstly allows us to sharpen labels on specific documents (i.e. override the output from 1. if incorrect). And secondly, it allows us to use these user-defined labels in a semi-supervised learning algorithm, which might perform better than what is done in step 1 (though this part is out of scope for this question).

Step 1 I could represent with a simple graph as follows:

The LDA algorithm outputs the terms found in the document along with some weighting according to their frequency. In addition, it outputs a set of topics along with the terms that are associated with each topic (again, weighted according to how strongly the term is associated with the topic).

Now for point 2 I need to incorporate user feedback, so I need to link a user to a document to indicate that the user has read it and then link the user to the topic, indicating that the user believes the document is about that topic.

But this doesn't really work. "Document is\_read\_by User" correctly describes the relationship between the document and the user, but "User believes\_document\_related\_to Topic" is not a valid relationship because it is contingent on a *specific* book - in this case 1984 by George Orwell.

**My question is**, how could I build this relationship with a graph? I.e for each user I want to be able to capture the following information.

* According to User "Karl" the document "1984 by George Orwell" is about the topic "Surveillance"

(Of course, the idea is to allow multiple users to give feedback, thereby strengthening/weakening the relationship between the document and the topic).

# Answer
> 1 votes
One way to express this as a graph is to draw an edge from the document (1984 by George Orwell) to the topic (Surveillance), labelled with the user who approved that relationship (e.g., the label might be: user\_believes\_doc\_is\_related\_to: "Karl").

---
Tags: graphs, machine-learning, natural-language-processing
---


# Question
Title: Building vertex-edge visibility graph among polygonal obstacles on 2d plane
I want to implement algorithm for computing vertex-edge visibility graph among polygonal obstacles, but I can't find any description or scientific paper describing such algorithm. Currently I understand how to extend Lee's algorithm for vertex-vertex visibility graph to compute vertex-edge graph, but I want to achieve better than $O(n^2 log(n))$ complexity. I read paper of Mount and Ghosh about their $O(nlog(n))$ algorithm based on triangulation of free space, and seems it allows extension to produce vertex-edge graph. But that algo has too complicated implementation :)

I wonder if there is a way to extend Overmars and Welzl algorithm $O(n^2)$ or algorithm with similar complexity to produce vertex-edge visibility graph? It's implementation seems to be quite simple. Point me on some papers, links, or describe it here if you can.

# Answer
I'm not sure if this is what you're after, but here's an $O(n + k)$ approach from J. O'Rourke and I. Streinu, Computational Geometry 10 (1998), pp. 105-120:

> $G\_{VE}$ may be constructed in $O(n + k)$ time for a polygon with $n$ vertices and $k$ visibility edges, by a slight modification of Hershberger's algorithm that constructs $G\_v$ in this time bound \[8\] from a polygon triangulation. Supplementing with Chazelle's linear-time triangulation algorithm achieves the claimed bound.
> 1 votes

---
Tags: computational-geometry, shortest-path
---


# Question
Title: If we can simulate $NP$-machines why isn't it trivial that $NP=coNP$?
I'm looking at some proof that shows $NP^{NP\cap coNP} = NP$.

Let's consider the non-trivial direction. Consider $L\in NP^{NP\cap coNP}$. Then, there's an $A\in NP\cap coNP$ such that $L\in NP^A$.

Since $A\in NP\cap coNP$, there're two machines $M\_A$ and $M\_{\overline A}$ to decide $A$ and $\overline A$, respectively.

Also, there's a machine $M\_L$ to decide $L$ which uses an oracle of $A$.

Let $M$ which acts in the following manner:

1. Act as $M\_L$.
2. instead of querying the oracle:
3. simulate the query on $M\_A$
4. simulate the query on $M\_\overline A$
5. write on the result tape the proper result and proceed

I don't understand few things:

1. How do we simulate $M\_A$ and $M\_\overline A$ exactly?
2. If we can do the above then why both $M\_A$ and $M\_\overline A$ are needed? (just simulate one of them to infer if $x\in A$ or not)
3. Finally, as a consequence of #2, we could infer that $NP=coNP$

I'd be glad for clarifications since this questions bothers me a lot and clearly, I'm missing something crucial of how those machines are simulated.

# Answer
> 1 votes
When we say "Simulate $M\_A$ on the query string $s$", we simply mean execute $M\_A(s)$. Note that you construct a non-deterministic machine for $L$, thus you are able to simulate other non-deterministic machines. If both $M\_A(s)$ and $M\_{\overline{A}}(s)$ output $0$, then stop and reject $x$ (the initial input). Only when one of the machines outputs $1$, you can be sure about whether or not $s\in A$, and can continue simulating the oracle machine for $L$.

Note that this newly constructed non-deterministic polynomial time machine, $M(x)$, may accept its input $x$ only in computations where for each query $s$ raised during the computation, either $M\_A(s)$ or $M\_{\overline{A}}(s)$ output 1. Using this observation, you can simply show that $M$ indeed decides $L$.

---
Tags: complexity-theory
---


# Question
Title: CFG for palindromes containing atleast 3 c's
Input alphabet = {a,b,c}

I tried with the following grammar :-

S -\> aSa / bSb / T
T -\> cTc / cSc / cBc
B -\> c / cXc
X -\> a / b / aXa / bXb / epsilon

This grammar is not able to generate 'cacac' .Is there any way to write this grammar with less number of productions or are any productions redundant here ?

Thanks.

# Answer
> 0 votes
You have a symbol S that needs to generate a palindrome with at least 3 c's. Create a symbol X that needs to generate a palindrome with at least 1 c, and a symbol Y that needs to generate a palindrome with no requirement for c's.

```
S -> aSa | bSb | cXc
X -> aXa | bXb | cYc | c
Y -> aYa | bYb | cYc | a | b | c | eps

```

I think the essential step was not to start writing down productions, but to write down which different symbols you need to produce which kinds of output. The productions are then trivial.

---
Tags: context-free
---


# Question
Title: What is the best Approximation algorithm to schedule a task graph?
If I have a task graph T and want a schedule to optimize the make-span, what is currently the best approximation algorithm for this problem? Are there any constant approximation algorithms?

# Answer
> 2 votes
You get a $2-\frac1m$-approximation (where $m$ is the number of machines), by greedily scheduling tasks as they become available, and this is essentially the best we can do at the moment. Improving this is actually a major open problem in scheduling (see e.g. this ).

---
Tags: approximation, scheduling, process-scheduling
---


title: proving $IP^\star = NP$

text:
# Question
Title: proving $IP^\star = NP$
> Consider the following complexity class $IP^\star$, a variant of $IP$. A language $L$ is in $IP^\star$ if there's a proof system $(P,V)$ s.t. $V$ is a verifier runs for a polynomial time and:
>
> $$x\in L \implies Pr\[(P,V)(x) = 1\] \ge 3/4 \\ x\not\in L \implies \> Pr\[(P,V)(x) = 1\] = 0 \\ $$
>
> Prove that $NP = IP^\star$.
>
> Note: in this definition as far as I understand, we have a single $P$ (for both cases).

Now, one side is easy ($NP\subseteq IP^\star$), since by definition $NP$ language has a perfect polynomial-verifier - so we're satisfying the demands.

The other side is the tricky one. Consider a language $L\in IP^\star$. We want to show that $L\in NP$. Obviously we shall utilize $V$ somehow. The certificate could be the "conversation" between $V$ and $P$. Then our $NP$ TM could simulate the conversation between $P$ to $V$.

Yet, that's alone isn't good enough - we have a $1/4$ probability to make a mistake if $x\in L$.

Amplifying the probability isn't good enough too. We need perfect soundness.

So maybe we shall use the non-determinism of our machine somehow?

# Answer
If $x \in L$ then the probability that $(P,V)(x,r) = 1$ is positive, where $r$ is the randomness involved; the probability is over the choice of $r$. In particular, there is some $r$ such that $(P,V)(x,r) = 1$.

In contrast, when $x \notin L$, the probability that $(P,V)(x,r) = 0$. That is, there is no $r$ such that $(P,V)(x,r) = 1$.

States differently, when $x \in L$, there is some conversation for which the verifier outputs 1, whereas when $x \notin L$, there is no such conversation. Since the verifier runs in polytime, the conversation has polynomial length, and can be verified to be a valid conversation in polynomial time. This puts $L$ in NP.

---

What is the difference between IP\* and IP? IP\* has perfect soundness – when $x \notin L$, the probability of error is 0 – whereas IP has neither perfect soundness nor perfect completeness. This makes IP much stronger.
> 3 votes

---
Tags: complexity-theory, probabilistic-algorithms, interactive-proof-systems
---


# Question
Title: What graph problems are hard to solve even for a small number of verticies?
The only graph problem that I worked with is TSP. It is exponentially hard, but there are tons of heuristics which allows to find near to optimum solution.

So I was wondering, is there any graph problems (or optimization problems which could be mapped onto graph) that are exponentially hard and can not be solved (even approximatly) efficiently for small and mid-sized systems? (let's say 10-20 verticies)

# Answer
> 0 votes
I recommend you look at a list of NP-complete problems on graphs. For each one, research whether there exists a known approximation algorithm. For some problems we have hardness of approximation results (which say that there is no polynomial-time algorithm that achieves approximation factor $\alpha$, unless $P=NP$). Those are potential candidates that might be of interest. In particular, I'd recommend you study the standard methods for dealing with intractability, then look for a candidate problem where none of those seem to work. You might also look at graph problems that are APX-complete as candidates worthy of further exploration.

For instance, graph coloring might be a possible candidate to look at. I haven't studied that problems so I don't know whether good heuristics exist. I doubt it will be hard on graphs with only 10-20 vertices, but it might be hard with somewhat larger graphs.

---
Tags: graphs, optimization, np-complete, np-hard
---